Mailinglist Archive: zypp-commit (266 mails)

< Previous Next >
[zypp-commit] r11712 - in /trunk/sat-solver: ./ doc/ doc/autodoc/ doc/autoinclude/
  • From: dmacvicar@xxxxxxxxxxxxxxxx
  • Date: Wed, 19 Nov 2008 08:55:08 -0000
  • Message-id: <20081119085508.403BA9E4E1@xxxxxxxxxxxxxxxx>
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@xxxxxxxxxxxx
For additional commands, e-mail: zypp-commit+help@xxxxxxxxxxxx

< Previous Next >
This Thread
  • No further messages