Author: dmacvicar Date: Wed Nov 19 09:55:07 2008 New Revision: 11712 URL: http://svn.opensuse.org/viewcvs/zypp?rev=11712&view=rev Log: lets try to make this a documented project Added: trunk/sat-solver/doc/CMakeLists.txt trunk/sat-solver/doc/autodoc/ trunk/sat-solver/doc/autodoc/CMakeLists.txt trunk/sat-solver/doc/autodoc/Doxyfile.cmake trunk/sat-solver/doc/autoinclude/ trunk/sat-solver/doc/autoinclude/History.doc trunk/sat-solver/doc/autoinclude/Mainpage.doc Modified: trunk/sat-solver/CMakeLists.txt Modified: trunk/sat-solver/CMakeLists.txt URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/CMakeLists.txt?rev=11712&r1=11711&r2=11712&view=diff ============================================================================== --- trunk/sat-solver/CMakeLists.txt (original) +++ trunk/sat-solver/CMakeLists.txt Wed Nov 19 09:55:07 2008 @@ -130,6 +130,7 @@ ADD_SUBDIRECTORY(tools) ADD_SUBDIRECTORY(applayer) ADD_SUBDIRECTORY(tests) +ADD_SUBDIRECTORY(doc) FIND_PACKAGE(SWIG REQUIRED) Added: trunk/sat-solver/doc/CMakeLists.txt URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/CMakeLists.txt?rev=11712&view=auto ============================================================================== --- trunk/sat-solver/doc/CMakeLists.txt (added) +++ trunk/sat-solver/doc/CMakeLists.txt Wed Nov 19 09:55:07 2008 @@ -0,0 +1 @@ +ADD_SUBDIRECTORY( autodoc EXCLUDE_FROM_ALL) Added: trunk/sat-solver/doc/autodoc/CMakeLists.txt URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autodoc/CMakeLists.txt?rev=11712&view=auto ============================================================================== --- trunk/sat-solver/doc/autodoc/CMakeLists.txt (added) +++ trunk/sat-solver/doc/autodoc/CMakeLists.txt Wed Nov 19 09:55:07 2008 @@ -0,0 +1,74 @@ +### ################################################## + +FIND_PROGRAM( DOXYGEN doxygen ) +IF ( NOT DOXYGEN ) + MESSAGE( FATAL_ERROR "doxygen not found: install doxygen to build the documentation." ) +ELSE ( NOT DOXYGEN ) + MESSAGE( STATUS "doxygen found: ${DOXYGEN}" ) +ENDIF ( NOT DOXYGEN ) + +FIND_PROGRAM( DOT dot ) +IF ( NOT DOT ) + MESSAGE( "dot not found: you should install graphviz." ) + SET( HAVE_DOT NO ) +ELSE ( NOT DOT ) + SET( HAVE_DOT YES ) +ENDIF ( NOT DOT ) + +SET( SATSOLVER_SOURCE_DIR ${CMAKE_SOURCE_DIR}/src ) +SET( SATSOLVER_DOCINCLUDE_DIR ${CMAKE_SOURCE_DIR}/doc/autoinclude ) +SET( SATSOLVER_EXAMPLE_DIR ${CMAKE_SOURCE_DIR}/examples ) + +SET( DOXYGEN_INPUT ${CMAKE_CURRENT_BINARY_DIR}/Doxyfile ) +SET( DOXYGEN_OUTPUT ${CMAKE_CURRENT_BINARY_DIR}/html/index.html ) +FILE( MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html ) + +### ################################################## + +CONFIGURE_FILE( + ${CMAKE_CURRENT_SOURCE_DIR}/Doxyfile.cmake + ${DOXYGEN_INPUT} + @ONLY + ) + +### ################################################## + +ADD_CUSTOM_COMMAND ( + OUTPUT ${DOXYGEN_OUTPUT} + COMMAND ${CMAKE_COMMAND} -E echo_append "Building Documentation..." + COMMAND ${DOXYGEN} ${DOXYGEN_INPUT} + COMMAND ${CMAKE_COMMAND} -E echo "Done." + WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} + DEPENDS ${DOXYGEN_INPUT} +) + +ADD_CUSTOM_TARGET( doc ALL + DEPENDS ${DOXYGEN_OUTPUT} +) + +ADD_CUSTOM_TARGET( doc_forced + COMMAND ${CMAKE_COMMAND} -E echo_append "Building Documentation..." + COMMAND ${DOXYGEN} ${DOXYGEN_INPUT} + COMMAND ${CMAKE_COMMAND} -E echo "Done." + WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} + DEPENDS ${DOXYGEN_INPUT} +) + +### ################################################## + +INSTALL( FILES + ${CMAKE_CURRENT_BINARY_DIR}/libzypp.doxytag + DESTINATION ${DOC_INSTALL_DIR}/libzypp/libzypp.doxytag +) + +# We could use the thing below but it wont work with cmake older than 2.4.4 +FILE(GLOB docfiles ${CMAKE_CURRENT_BINARY_DIR}/html/*) +INSTALL( FILES + ${docfiles} + DESTINATION ${DOC_INSTALL_DIR}/satsolver/html +) + +#INSTALL( DIRECTORY +# ${CMAKE_CURRENT_BINARY_DIR}/html +# DESTINATION ${DOC_INSTALL_DIR} +#) Added: trunk/sat-solver/doc/autodoc/Doxyfile.cmake URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autodoc/Doxyfile.cmake?rev=11712&view=auto ============================================================================== --- trunk/sat-solver/doc/autodoc/Doxyfile.cmake (added) +++ trunk/sat-solver/doc/autodoc/Doxyfile.cmake Wed Nov 19 09:55:07 2008 @@ -0,0 +1,219 @@ +# Doxyfile 1.4.4 + +#--------------------------------------------------------------------------- +# Project related configuration options +#--------------------------------------------------------------------------- +PROJECT_NAME = @PACKAGE@ +PROJECT_NUMBER = @VERSION@ +OUTPUT_DIRECTORY = +CREATE_SUBDIRS = NO +OUTPUT_LANGUAGE = English +BRIEF_MEMBER_DESC = YES +REPEAT_BRIEF = YES +ABBREVIATE_BRIEF = +ALWAYS_DETAILED_SEC = NO +INLINE_INHERITED_MEMB = NO +FULL_PATH_NAMES = YES +STRIP_FROM_PATH = @CMAKE_SOURCE_DIR@ +STRIP_FROM_INC_PATH = +SHORT_NAMES = NO +JAVADOC_AUTOBRIEF = YES +MULTILINE_CPP_IS_BRIEF = NO +DETAILS_AT_TOP = NO +INHERIT_DOCS = YES +DISTRIBUTE_GROUP_DOC = NO +SEPARATE_MEMBER_PAGES = NO +TAB_SIZE = 8 +ALIASES = +OPTIMIZE_OUTPUT_FOR_C = NO +OPTIMIZE_OUTPUT_JAVA = NO +SUBGROUPING = YES +#--------------------------------------------------------------------------- +# Build related configuration options +#--------------------------------------------------------------------------- +EXTRACT_ALL = YES +EXTRACT_PRIVATE = YES +EXTRACT_STATIC = YES +EXTRACT_LOCAL_CLASSES = YES +EXTRACT_LOCAL_METHODS = NO +HIDE_UNDOC_MEMBERS = NO +HIDE_UNDOC_CLASSES = NO +HIDE_FRIEND_COMPOUNDS = NO +HIDE_IN_BODY_DOCS = NO +INTERNAL_DOCS = NO +CASE_SENSE_NAMES = YES +HIDE_SCOPE_NAMES = NO +SHOW_INCLUDE_FILES = YES +INLINE_INFO = YES +SORT_MEMBER_DOCS = NO +SORT_BRIEF_DOCS = NO +SORT_BY_SCOPE_NAME = NO +GENERATE_TODOLIST = YES +GENERATE_TESTLIST = YES +GENERATE_BUGLIST = YES +GENERATE_DEPRECATEDLIST= YES +ENABLED_SECTIONS = +MAX_INITIALIZER_LINES = 30 +SHOW_USED_FILES = YES +SHOW_DIRECTORIES = YES +FILE_VERSION_FILTER = +#--------------------------------------------------------------------------- +# configuration options related to warning and progress messages +#--------------------------------------------------------------------------- +QUIET = YES +WARNINGS = YES +WARN_IF_UNDOCUMENTED = YES +WARN_IF_DOC_ERROR = YES +WARN_NO_PARAMDOC = NO +WARN_FORMAT = "$file:$line: $text" +WARN_LOGFILE = +#--------------------------------------------------------------------------- +# configuration options related to the input files +#--------------------------------------------------------------------------- +INPUT = @SATSOLVER_DOCINCLUDE_DIR@ @SATSOLVER_SOURCE_DIR@ +FILE_PATTERNS = *.h *.hh *.hxx *.hpp *.h++ *.c *.cc *.cxx *.cpp *.c++ *.tcc *.hcc *.doc +RECURSIVE = YES +EXCLUDE = +EXCLUDE_SYMLINKS = NO +EXCLUDE_PATTERNS = +EXAMPLE_PATH = @SATSOLVER_DOCINCLUDE_DIR@ @SATSOLVER_EXAMPLE_DIR@ +EXAMPLE_PATTERNS = +EXAMPLE_RECURSIVE = NO +IMAGE_PATH = +INPUT_FILTER = +FILTER_PATTERNS = +FILTER_SOURCE_FILES = NO +#--------------------------------------------------------------------------- +# configuration options related to source browsing +#--------------------------------------------------------------------------- +SOURCE_BROWSER = YES +INLINE_SOURCES = NO +STRIP_CODE_COMMENTS = YES +REFERENCED_BY_RELATION = YES +REFERENCES_RELATION = YES +USE_HTAGS = NO +VERBATIM_HEADERS = NO +#--------------------------------------------------------------------------- +# configuration options related to the alphabetical class index +#--------------------------------------------------------------------------- +ALPHABETICAL_INDEX = YES +COLS_IN_ALPHA_INDEX = 5 +IGNORE_PREFIX = +#--------------------------------------------------------------------------- +# configuration options related to the HTML output +#--------------------------------------------------------------------------- +GENERATE_HTML = YES +HTML_OUTPUT = html +HTML_FILE_EXTENSION = .html +HTML_HEADER = +HTML_FOOTER = +HTML_STYLESHEET = +HTML_ALIGN_MEMBERS = YES +GENERATE_HTMLHELP = NO +CHM_FILE = +HHC_LOCATION = +GENERATE_CHI = NO +BINARY_TOC = NO +TOC_EXPAND = NO +DISABLE_INDEX = NO +ENUM_VALUES_PER_LINE = 4 +GENERATE_TREEVIEW = NO +TREEVIEW_WIDTH = 250 +#--------------------------------------------------------------------------- +# configuration options related to the LaTeX output +#--------------------------------------------------------------------------- +GENERATE_LATEX = NO +LATEX_OUTPUT = latex +LATEX_CMD_NAME = latex +MAKEINDEX_CMD_NAME = makeindex +COMPACT_LATEX = NO +PAPER_TYPE = a4wide +EXTRA_PACKAGES = +LATEX_HEADER = +PDF_HYPERLINKS = NO +USE_PDFLATEX = NO +LATEX_BATCHMODE = NO +LATEX_HIDE_INDICES = NO +#--------------------------------------------------------------------------- +# configuration options related to the RTF output +#--------------------------------------------------------------------------- +GENERATE_RTF = NO +RTF_OUTPUT = rtf +COMPACT_RTF = NO +RTF_HYPERLINKS = NO +RTF_STYLESHEET_FILE = +RTF_EXTENSIONS_FILE = +#--------------------------------------------------------------------------- +# configuration options related to the man page output +#--------------------------------------------------------------------------- +GENERATE_MAN = NO +MAN_OUTPUT = man +MAN_EXTENSION = .3 +MAN_LINKS = NO +#--------------------------------------------------------------------------- +# configuration options related to the XML output +#--------------------------------------------------------------------------- +GENERATE_XML = NO +XML_OUTPUT = xml +XML_SCHEMA = +XML_DTD = +XML_PROGRAMLISTING = YES +#--------------------------------------------------------------------------- +# configuration options for the AutoGen Definitions output +#--------------------------------------------------------------------------- +GENERATE_AUTOGEN_DEF = NO +#--------------------------------------------------------------------------- +# configuration options related to the Perl module output +#--------------------------------------------------------------------------- +GENERATE_PERLMOD = NO +PERLMOD_LATEX = NO +PERLMOD_PRETTY = YES +PERLMOD_MAKEVAR_PREFIX = +#--------------------------------------------------------------------------- +# Configuration options related to the preprocessor +#--------------------------------------------------------------------------- +ENABLE_PREPROCESSING = YES +MACRO_EXPANSION = NO +EXPAND_ONLY_PREDEF = NO +SEARCH_INCLUDES = YES +INCLUDE_PATH = +INCLUDE_FILE_PATTERNS = +PREDEFINED = +EXPAND_AS_DEFINED = +SKIP_FUNCTION_MACROS = YES +#--------------------------------------------------------------------------- +# Configuration::additions related to external references +#--------------------------------------------------------------------------- +TAGFILES = +GENERATE_TAGFILE = @PACKAGE@.doxytag +ALLEXTERNALS = NO +EXTERNAL_GROUPS = YES +PERL_PATH = /usr/bin/perl +#--------------------------------------------------------------------------- +# Configuration options related to the dot tool +#--------------------------------------------------------------------------- +CLASS_DIAGRAMS = YES +HIDE_UNDOC_RELATIONS = NO +HAVE_DOT = @HAVE_DOT@ +CLASS_GRAPH = YES +COLLABORATION_GRAPH = NO +GROUP_GRAPHS = NO +UML_LOOK = YES +TEMPLATE_RELATIONS = NO +INCLUDE_GRAPH = NO +INCLUDED_BY_GRAPH = NO +CALL_GRAPH = NO +GRAPHICAL_HIERARCHY = YES +DIRECTORY_GRAPH = NO +DOT_IMAGE_FORMAT = png +DOT_PATH = +DOTFILE_DIRS = +MAX_DOT_GRAPH_DEPTH = 0 +DOT_TRANSPARENT = NO +DOT_MULTI_TARGETS = NO +GENERATE_LEGEND = YES +DOT_CLEANUP = YES +#--------------------------------------------------------------------------- +# Configuration::additions related to the search engine +#--------------------------------------------------------------------------- +SEARCHENGINE = NO Added: trunk/sat-solver/doc/autoinclude/History.doc URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/History.doc?rev=11712&view=auto ============================================================================== --- trunk/sat-solver/doc/autoinclude/History.doc (added) +++ trunk/sat-solver/doc/autoinclude/History.doc Wed Nov 19 09:55:07 2008 @@ -0,0 +1,105 @@ +/** \page history History of satsolver + +\section beginning The beginning + +This project was started in May 2007 when the zypp folks decided to switch +to a database to speed up installation. As I'm not a big fan of databases, +I wondered if there would be really some merit of using one for solving, +as package dependencies of all packages have to be read in anyway. + +Back in 2002 I researched that using a dictionary approach for storing +dependencies can reduce the packages file to 1/3 of its size. Extending +this idea a bit more, I decided to store all strings and relations +as unique 32bit numbers. This has three big advantages: + - because of the unification, testing if two strings are equal + is the same as testing the equality of two numbers, thus very + fast + - much space is saved, as numbers don't take so much space as strings + - the internal memory representation doesn't take more space on a + 64bit system where a pointer is twice the size of a 32bit number + +Thus the solv format was created, which stores a repository as a string +dictionary, a relation dictionary and then all packages dependencies. +Tests showed that reading and merging multiple solv repositories takes +just some milliseconds. + +\section experiments Early solver experiments + +Having a new repository format was one big step, but the other area +where libzypp needed improvement was the solver. Libzypp's solver was +a port from the red carpet solver, which was written to update packages +in an already installed system. Using it for the complete installation +progress brought it to its limits. Also, the added extensions like +support for weak dependencies and patches made it fragile and +unpredictable. + +As I wasn't very pleased with the way the solver worked, I looked at +other solver algorithms. I checked smart, yum and apt, but could not +find a convincing algorithm. My own experiments also were not very +convincing, they worked fine for some problems but failed miserably +for other corner cases. + +\section usingsat Using SAT for solving + +SUSE's hack week at the end of June 2007 turned out to be a turning point +for the solver. Googling for solver algorithms I stumbled over some note +saying that some people are trying to use SAT algorithms to improve +solving on debian. Looking at the SAT entry in wikipedia, it was easy +to see that this indeed was the missing piece: sat algorithms are well +researched and there are quite some open source implementations. +I decided to look at the minisat code, as it is one of the fastest +solvers while consisting of too many lines of code. +Of course, directly using minisat would not work, as a package solver +doesn't need to find just one correct solution, but it also has to +optimize some metrics, i.e. keep as many packages installed as possible. +Thus, I needed to write my own solver incorporation the ideas and +algorithms used in minisat. This wasn't very hard, and at the end of +the hack week the solver calculated the first right solutions. + +\section selling Selling it to libzypp + +With those encouraging results I went to Klaus Kaempf, the system +management architect here at SUSE. We spoke about how to convince the +team to make libzypp switch to the new solver. Fortunately libzypp comes +with a plethora of solver test cases, so we decided to make the solver pass +most of the test cases first. Klaus wrote a "deptestomatic" implementation +to check the test cases. Together with Stephan Kulow, responsible for the +openSUSE distribution, we tweaked and extended the solver until most of +the test cases looked good. +Duncan Mac-Vicar Prett, the team lead of the YaST team, also joined +development by creating ruby bindings for the solver. Later, Klaus +improved the bindings and ported them to some other languages. + +\section attrstore The attribute store + +The progress with the repository format and the solver attracted another +hacker to the project: Michael Matz from the compiler team. He started +with improving the repository parsers so that patches and content files +also generate solvables. After that, he concentrated on storing all +of the other metadata of the repositories that are not used for solving, +like the package summaries and descriptions. In the end of October, a first +version of this "attribute store" was checked in. Its design goals were + - space efficient storage of attributes + - paging/on demand loading of data + - page compression +The first version of the attribute store used a different format for +storing information, we later merged this format with the solv file +format. + +\section zyppinteg libzypp integration + +Integrating the sat-solver into libzypp also started in October 2007 by +Stefan Schubert and Michael Andres from the YaST team. The first +versions supported both the old solver and the new one by using the +old repository read functions and converting the old package data +in-memory into a sat solver pool. Solvers could be switched with +the environment variable ZYPP_SAT_SOLVER. The final decision to +move to the new solver was made in January of 2008, first just by +making the new solver the default one, later by completely throwing out +the old solver code. This had the advantage that the internal solvable +storage could also be done by using the solver pool, something Michael +Matz already played with in a proof of concept implementation showing +some drastic speed gains. The last traces of the old database code +were removed in February. + +*/ \ No newline at end of file Added: trunk/sat-solver/doc/autoinclude/Mainpage.doc URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/Mainpage.doc?rev=11712&view=auto ============================================================================== --- trunk/sat-solver/doc/autoinclude/Mainpage.doc (added) +++ trunk/sat-solver/doc/autoinclude/Mainpage.doc Wed Nov 19 09:55:07 2008 @@ -0,0 +1,6 @@ +/** \namespace zypp libzypp +*/ +** \mainpage Welcome to libzypp + + +*/ \ No newline at end of file -- To unsubscribe, e-mail: zypp-commit+unsubscribe@opensuse.org For additional commands, e-mail: zypp-commit+help@opensuse.org