Mailinglist Archive: zypp-commit (266 mails)

< Previous Next >
[zypp-commit] r11725 - in /trunk/sat-solver/doc: autodoc/ autoinclude/
  • From: dmacvicar@xxxxxxxxxxxxxxxx
  • Date: Wed, 19 Nov 2008 15:29:53 -0000
  • Message-id: <20081119152953.E2E03B82C8@xxxxxxxxxxxxxxxx>
Author: dmacvicar
Date: Wed Nov 19 16:29:53 2008
New Revision: 11725

URL: http://svn.opensuse.org/viewcvs/zypp?rev=11725&view=rev
Log:
convert docs

Added:
trunk/sat-solver/doc/autoinclude/Attributes.doc
trunk/sat-solver/doc/autoinclude/CodeConventions.doc
trunk/sat-solver/doc/autoinclude/Format.doc
trunk/sat-solver/doc/autoinclude/HowItWorks.doc
trunk/sat-solver/doc/autoinclude/Planning.doc
trunk/sat-solver/doc/autoinclude/Policies.doc
trunk/sat-solver/doc/autoinclude/Pool.doc
trunk/sat-solver/doc/autoinclude/Queue.doc
Modified:
trunk/sat-solver/doc/autodoc/Doxyfile.cmake
trunk/sat-solver/doc/autoinclude/History.doc
trunk/sat-solver/doc/autoinclude/Mainpage.doc

Modified: trunk/sat-solver/doc/autodoc/Doxyfile.cmake
URL:
http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autodoc/Doxyfile.cmake?rev=11725&r1=11724&r2=11725&view=diff
==============================================================================
--- trunk/sat-solver/doc/autodoc/Doxyfile.cmake (original)
+++ trunk/sat-solver/doc/autodoc/Doxyfile.cmake Wed Nov 19 16:29:53 2008
@@ -146,7 +146,7 @@
#---------------------------------------------------------------------------
# configuration options related to the man page output
#---------------------------------------------------------------------------
-GENERATE_MAN = NO
+GENERATE_MAN = YES
MAN_OUTPUT = man
MAN_EXTENSION = .3
MAN_LINKS = NO

Added: trunk/sat-solver/doc/autoinclude/Attributes.doc
URL:
http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/Attributes.doc?rev=11725&view=auto
==============================================================================
--- trunk/sat-solver/doc/autoinclude/Attributes.doc (added)
+++ trunk/sat-solver/doc/autoinclude/Attributes.doc Wed Nov 19 16:29:53 2008
@@ -0,0 +1,349 @@
+/** \page about-attrs All about attributes
+
+\section attr-why Why attributes ?
+
+The .solv files contain Solvables, as defined in src/solvable.h
+These are the basic objects for the solver, containing name,
+architecture, evr (epoch-version-release), vendor and dependencies.
+
+However, a (RPM) package has many more properties. Like summary,
+description, license, package group, etc.
+All theses properties are not needed for dependency resolution and
+hence are stored outside of Solvables.
+
+Sat-solver provides the 'Attribute Store' for these properties,
+internally called 'repodata'. See src/repodata.h
+
+
+\section attr-what What are attributes ?
+
+An attribute is a quadruple containing
+
+ - solvable (to which this attribute belongs)
+ - name (describing the content, like 'solvable:description')
+ - type (like 'number' or 'string')
+ - value (according to the type)
+
+
+\section attr-how How to set attributes ?
+
+\subsection attr-how-solvable You need a Solvable
+
+ Attributes belong to a solvable. So you need a solvable first. And
+ solvables belong to a repo which belongs to a pool.
+
+\code
+ /* create a pool */
+ Pool *pool = pool_create();
+
+ /* create a repo */
+ Repo *repo = repo_create(pool, "demo");
+
+ /* create a solvable */
+ Id s = repo_add_solvable(repo);
+\endcode
+
+\subsection attr-how-create You need to create the attribute store
+
+ By default .solv files don't contain additional attributes. So you
+ have to add the attribute store to the repository:
+
+\code
+ Repodata *data = repo_add_repodata(repo, 0);
+\endcode
+
+ The second parameter indicates a 'local pool' for storing strings.
+ By default, strings are stored in the Pool. Setting the second
+ parameter to non-zero will store attribute string values separate
+ from the Pool.
+
+ [Q: Whats the technical reason for the local pool?]
+
+
+\subsection attr-how-space You need space for the attributes
+
+ Space for the attribute store must be explicitly requested. Not for
+ every attribute but you have to signal that a solvable has
+ attributes.
+
+ First you compute the datanum:
+
+\code
+ Solvable *solvable = pool_id2solvable(pool, s);
+ Id datanum = (solvable - pool->solvables) - repo->start;
+\endcode
+
+ datanum is the reference from the attribute store back to the
+ solvable.
+
+ As you can see, the datanum is basically the offset of the solvable
+ within the repo. Remember that the attributes are per-repository (as
+ is the solvable. When calling 'repodata_*' function, use the datanum
+ to represent the solvable.
+
+ Extending the store is done with repodata_extend():
+
+\code
+ repodata_extend(data, solvable - pool->solvables);
+\endcode
+
+ [Q: The offset passed to repodata_extend is per-pool. All other
+ repodata functions are per-repo. Why ?]
+
+
+\subsection attr-how-set Set attributes
+
+ Now you can set attributes. You do this with repodata_set_*()
+ passing the store (data), the solvable reference (datanum), the name
+ of the solvable and the value.
+
+ See src/repodata.h for a complete list of all the repodata_set_*()
+ functions.
+
+ Attributes are named and in good sat-solver tradition, everything is
+ an Id.
+
+\code
+ Id attr_name = str2id(pool, "name_of_attribute", 1);
+\endcode
+
+ See knownid.h for predefined attribute names.
+
+
+\subsubsection attr-how-set-bool Setting a boolean attribute
+
+ A boolean attribute derives is value from its presence. So you don't
+ pass an explicit true/false value but call repodata_set_void() if
+ the attribute is 'true'.
+
+\code
+ repodata_set_void(data, datanum, attr_name);
+\endcode
+
+\subsubsection attr-how-set-num Setting a numeric attribute
+
+ Storing a numeric value is done with repodata_set_num, passing an
+ unsinged integer:
+
+ unsigned int value = 123456;
+ repodata_set_num(data, datanum, attr_name, value);
+
+
+\subsubsection attr-how-set-str Setting a string attribute
+
+ Strings are 'const char' pointers and set like:
+
+\code
+ const char *s = "This is a string";
+ repodata_set_str(data, datanum, attr_name, s);
+\endcode
+
+ If the same string is used multiple times as an attribute value, its
+ more efficient to store it once and use its Id.
+
+
+\subsubsection attr-how-set-id Setting an Id attribute
+
+\code
+ Id id = str2id(pool, "value_of_attribute", 1);
+ repodata_set_id(data, datanum, attr_name, id);
+\endcode
+
+\subsubsection attr-how-set-const Setting a constant attribute
+
+ A constant attribute shares a single value across all instances of
+ the attribute.
+
+ A constant can either be of numeric (unsigned int) type
+
+\code
+ repodata_set_constant(data, datanum, attr_name, 12345);
+\endcode
+
+ or an Id:
+
+\code
+ Id id = str2id(pool, "constant string", 1);
+ repodata_set_constant(data, datanum, attr_name, id);
+\endcode
+
+\subsubsection attr-how-set-array Arrays
+
+ Sometimes an attribute doesn't have a single value, but a varying
+ number of values. Here arrays come in handy.
+
+ The attribute store knows about two types of arrays. Arrays of Ids
+ and arrays of strings.
+
+ You fill an array by multiple calls to (array of Ids)
+
+\code
+ repodata_add_idarray(data, datanum, attr_name, id)
+\endcode
+
+ or
+
+\code
+ repodata_add_poolstr_array(data, datanum, attr_name, "value")
+\endcode
+
+ Every call will add the value to the end of the array.
+
+
+ [Q: can I mix Id and char* in one array ?]
+
+
+\subsubsection attr-how-set-other Other data types
+
+ See repodata.h, there are
+ - checksum
+ - bin_checksum
+ - dirnumnum
+ - dirstr
+
+
+\subsubsection attr-how-set-struct Structural attribute types
+
+ Structural attribute types are (currently) not supported.
+
+
+\subsection attr-how-write-solv Writing the .solv file
+
+ Before writing out a .solv file, you need to internalize the
+ attribute store so it gets stored together with the solvables.
+
+ repodata_internalize(data);
+
+ Thats black MM magic. Don't ask.
+
+
+\subsection attr-how-read-attr Reading attributes
+
+ Reading attribute values isn't that easy because of the way they're
+ stored internally. The storage optimization prevents a direct-access
+ method, so you need to search for the value matching a specific
+ solvable and attribute name.
+
+ Hence the read functions are called 'repodata_lookup_*()' and only
+ exist for some attribute types, namely boolean (void), numeric,
+ string, Id and bin_checksum.
+
+ The preparation steps are similar to writing, you need a pool, a
+ repository and the solvable reference.
+
+\code
+ /* create a pool */
+ Pool *pool = pool_create();
+
+ /* create a repo */
+ Repo *repo = repo_create(pool, "demo");
+
+ Solvable *s;
+
+ /*
+ * now populate the repo
+ * either from a .solv file: repo_add_solv(Repo *, FILE *);
+ * or from the RPM database: repo_add_rpmdb(Repo *, NULL, "/");
+ *
+ * and retrieve a Solvable s
+ *
+ */
+\endcode
+
+\subsection attr-how-read-known Reading known attributes
+
+ For the standard attribute names as listed in knownid.h, the easiest
+ way to retrieve values it through repo_lookup_*() (as opposed to
+ repodata_lookup_*())
+
+\code
+ /* get the summary attribute */
+ const char *summary = repo_lookup_str(s, SOLVABLE_SUMMARY);
+
+ /* get the buildtime attribute */
+ unsigned int buildtime = repo_lookup_num(s, SOLVABLE_BUILDTIME);
+\endcode
+
+ Both lookup functions return 0 if the attribute isn't set.
+
+ The downside of these simple access functions it that you have to
+ know the type of the attribute you're going to retrieve.
+
+
+\subsection attr-how-lookup-generic Generic attribute lookup
+
+ The function repo_lookup() provides a generic way to access
+ attribute values. It is passed a solvable, an attribute name (as Id)
+ and a callback function.
+
+ repo_lookup then tries to retrieve the attribute value and returns
+ non-zero on success.
+
+\code
+ Id attr_name = str2id(pool, "name_of_attribute", 0);
+\endcode
+
+ You can also use predefined Ids from knownid.h
+ Pay attention to the last parameter to the str2id call. It was 1
+ when setting the attribute buts its 0 when reading.
+
+ This is just a short-path to check for existance of an attribute
+ (name). Passing 0 to str2id means 'do not create if not existing
+ before'. So if attr_name is assigned 0 (ID_NULL) in this call, this
+ attribute is not defined within the pool.
+
+\code
+ if(repo_lookup(s, attr_name, callback_function, (void *)callback_data) {
+ /* attribute found */
+ }
+
+ If the solvable s has the attribute attr_name defined, the
+ callback_function is called passing callback_data.
+
+ This function is defined as
+
+ int callback_function( void *cbdata, Solvable *s, Repodata *data, Repokey
*key, KeyValue *kv )
+\endcode
+
+ with
+
+ cbdata: the callback_data from the call to repo_lookup
+ s: the solvable from the call to repo_lookup
+ data: the attribute store associated with the repo
+ key: the attribute name (key->name, an Id) and type (key->type, a
REPOKEY_TYPE_*)
+ kv: the attribute value (depending on the key->type)
+
+ within the callback_function, you usually look at the key->type and
+ access the value according to the type:
+
+\code
+ switch(key->type)
+ {
+ case REPOKEY_TYPE_VOID: /* just existance */
+ ...
+ break;
+ case REPOKEY_TYPE_NUM: /* value is in kv->num */
+ ...
+ break;
+ case REPOKEY_TYPE_STR: /* value is in kv->str */
+ ...
+ break;
+
+ /* ... */
+ }
+ return 1;
+\endcode
+
+ Returning non-zero from the callback_function will end the lookup,
+ signalling you've found what you were looking for.
+
+
+\subsection attr-how-about-attr-name About attribute names
+
+ You are free to choose any name for the attributes. However, when
+ dealing with (RPM) packages, there are a lot of standard attributes
+ in use. src/knownid.h defines most of them, e.g. SOLVABLE_SUMMARY (a
+ string) or SOLVABLE_BUILDTIME (a number). Use the predefined
+ attribute names whenever applicable.
+
+*/
\ No newline at end of file

Added: trunk/sat-solver/doc/autoinclude/CodeConventions.doc
URL:
http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/CodeConventions.doc?rev=11725&view=auto
==============================================================================
--- trunk/sat-solver/doc/autoinclude/CodeConventions.doc (added)
+++ trunk/sat-solver/doc/autoinclude/CodeConventions.doc Wed Nov 19 16:29:53
2008
@@ -0,0 +1,7 @@
+/** \page codeconvpage Code Conventions
+
+\subsection codedoc Code Documentation
+
+- Use doxygen tags only in the pages, not in the source code. There keep just
standard comments.
+
+*/
\ No newline at end of file

Added: trunk/sat-solver/doc/autoinclude/Format.doc
URL:
http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/Format.doc?rev=11725&view=auto
==============================================================================
--- trunk/sat-solver/doc/autoinclude/Format.doc (added)
+++ trunk/sat-solver/doc/autoinclude/Format.doc Wed Nov 19 16:29:53 2008
@@ -0,0 +1,111 @@
+/** \page formatpage Solv file format
+
+Metadata information is stored as '.solv' files
+
+These files have the following format:
+
+\section formatv0 V0 format
+
+\code
+ MAGIC: 'SOLV'
+ U32: 0
+
+ -- sizes --
+
+ U32: NUMID /* number of Ids (names) */
+ U32: NUMREL /* number of RelDeps (dependencies) */
+ U32: NUMSOLV /* number of Solvables (packages) */
+
+ -- string data --
+ U32: SIZEID /* total size of string buffer */
+ U8*: DICT (SIZE SIZEID) /* (raw) string buffer */
+
+ -- reldep data --
+ U8*: RELDICT /* Buffer for RandDeps (Id,Id,u8) */
+
+ -- source data -- /* apparently unused */
+
+ U32: NUMSRCDATA
+ U8 : TYPE /* TYPE_ID, TYPE_U32, TYPE_STR */
+ ID : DATAID
+ ID | U32 | U8*
+
+ -- solvables --
+
+ U32: NUMSOLVDATA
+ U8 : TYPE
+ ID : DATAID
+ U32: NUM/SIZE
+
+ U8*: BITS
+ U8*: DATA
+
+
+V6 format
+=========
+
+ MAGIC: 'SOLV'
+ U32: 6
+
+ U32: NUMID /* number of Ids (names) */
+ U32: NUMREL /* number of RelDeps (dependencies) */
+ U32: NUMDIR /* number of directories */
+ U32: NUMITEM /* number of items (packages) */
+ U32: NUMKEYS
+ U32: NUMSCHEMATA /* number of schemata */
+ U32: NUMINFO
+ U32: FLAGS /* solv file flags */
+ 4:PREFIX_POOL
+
+ -- string data --
+ ID: SIZEID /* total size of string buffer */
+ U8*: DICT (SIZE SIZEID) /* (raw) string buffer */
+
+ -- reldep data --
+ U8*: RELDICT /* Buffer for RandDeps (Id,Id,u8) */
+
+ -- directory data --
+ U8*: DIRDICT /* Buffer for dirs (Id,Id) */
+
+ -- key data --
+ NUMKEYS *
+ ID: name
+ ID: type
+ ID: expanded num/size
+
+ -- schemata data --
+ ID: expanded schemata size
+ NUMSCHEMATA *
+ IDARRAY* keys
+
+ -- file information --
+ ID maxinfolen (IF NUMINFO)
+ ID allinfolen (IF NUMINFO)
+ NUMINFO *
+ ID schema
+ U8 *data
+
+ -- item data --
+ ID maxitemlen (IF NUMITEM)
+ ID allitemlen (IF NUMITEM)
+ NUMITEM *
+ ID schema
+ U8* data
+
+ -- paged vertical data --
+ U32 pagesize
+ NPAGES *
+ U32 len * 2 + compressedflag
+ U8* data
+
+\endcode
+
+key sizes for storage types:
+
+\code
+KEY_STORAGE_VERTICAL_OFFSET: packed size
+KEY_STORAGE_INCORE: packed size
+KEY_STORAGE_SOLVABLE: unpacked size
+\endcode
+
+*/
\ No newline at end of file

Modified: trunk/sat-solver/doc/autoinclude/History.doc
URL:
http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/History.doc?rev=11725&r1=11724&r2=11725&view=diff
==============================================================================
--- trunk/sat-solver/doc/autoinclude/History.doc (original)
+++ trunk/sat-solver/doc/autoinclude/History.doc Wed Nov 19 16:29:53 2008
@@ -1,4 +1,6 @@
-/** \page history History of satsolver
+/** \page historypage History of satsolver
+
+\author Michael Schroeder <mls@xxxxxxx>

\section beginning The beginning


Added: trunk/sat-solver/doc/autoinclude/HowItWorks.doc
URL:
http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/HowItWorks.doc?rev=11725&view=auto
==============================================================================
--- trunk/sat-solver/doc/autoinclude/HowItWorks.doc (added)
+++ trunk/sat-solver/doc/autoinclude/HowItWorks.doc Wed Nov 19 16:29:53 2008
@@ -0,0 +1,233 @@
+/** \page howitworkspage How the SAT solver works
+
+\section theory Theory
+
+CNF - Conjunktive Normal Form
+
+Boolean expression of the form (x|y) & (-a|b|c) & ...
+ a,b,c,x,y are LITERALS
+ There a positive literals (x,y) and negative literals (-a, -b)
+ Terms in parentheses are CLAUSES
+
+Goal: Make the whole expression TRUE
+
+Useful shortcuts:
+- If a positive literal goes TRUE within a clause, the whole clause is TRUE
+- If a negative literal goes FALSE within a clause, the whole clause is TRUE
+
+\section datastruct Data structure
+
+\code
+ Id p; /* first literal in rule */
+ Id d; /* Id offset into 'list of providers */
+ /* terminated by 0' as used by whatprovides;
pool->whatprovides + d */
+ /* in case of binary rules, d == 0, w1 == p, w2 ==
other literal */
+ /* in case of disabled rules: ~d, aka -d - 1 */
+ Id w1, w2; /* watches, literals not-yet-decided */
+ /* if !w2, assertion, not rule */
+ Id n1, n2; /* next rules in linked list, corresponding to w1,w2 */
+
+
+ r->n1 = solv->watches[nsolvables + r->w1];
+ solv->watches[nsolvables + r->w1] = r - solv->rules;
+
+ r->n2 = solv->watches[nsolvables + r->w2];
+ solv->watches[nsolvables + r->w2] = r - solv->rules;
+\endcode
+
+\code
+ * Assertion
+ * keepinstalled (A), install
+ p=A, d=0, w1=p, w2=0
+ * uninstallable (-A), remove
+ p=-A, d=0, w1=p, w2=0
+ *
+ * Binary rules:
+ * (A|B)
+ p=A, d=0, w1=p, w2=B
+ * (-A|B)
+ p=-A, d=0, w1=p, w2=B
+ *
+ * A requires B : !A | provider1(B) | provider2(B)
+ p=-A, d=<whatprovides_offset>, w1=, w2=
+
+ * B updates A : A | provider1(B) | provider2(B)
+ p=A, d=<whatprovides_offset>, w1=, w2=
+
+ *
+ * A conflicts B : (!A | !provider1(B)) & (!A | !provider2(B)) ...
+ p=-A, d=-B1, w1=, w2=
+ p=-A, d=-B2, w1=, w2=
+ p=-A, d=-B3, w1=, w2=
+ ...
+ *
+ * 'not' is encoded as a negative Id
+ *
+
+Action | p | d | w1 | w2
+--------------+----+---------+-------+--------
+Assert A | A | 0 | A | 0
+Assert -A |-A | 0 |-A | 0
+Binary A,B | A | 0 | A | B
+Binary -A,B |-A | 0 |-A | B
+A requires B |-A | prov(B) |-A | whatprovidesdata(B)
+B updates A | A | prov(B) | A | whatprovidesdata(B)
+A conflicts B |-A | -B |-A |-B
+
+addrule(p, d)
+\endcode
+
+
+\code
+/*
+* add rule
+* p = direct literal; always < 0 for installed rpm rules
+* d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is
assertion (look at p only)
+*
+*
+* A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
+*
+* p < 0 : pkg id of A
+* d > 0 : Offset in whatprovidesdata (list of providers of b)
+*
+* A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
+* p < 0 : pkg id of A
+* d < 0 : Id of solvable (e.g. B1)
+*
+* d == 0: unary rule, assertion => (A) or (-A)
+*
+* Install: p > 0, d = 0 (A) user requested install
+* Remove: p < 0, d = 0 (-A) user requested remove
+* Requires: p < 0, d > 0 (-A|B1|B2|...) d: <list of providers for
requirement of p>
+* Updates: p > 0, d > 0 (A|B1|B2|...) d: <list of updates for
solvable p>
+* Conflicts: p < 0, d < 0 (-A|-B1),(-A|-B2),... either p
(conflict issuer) or d (conflict provider) (binary rule)
+* Obsoletes: p < 0, d < 0 (-A|-B1),(-A|-B2),... A: uninstalled, Bx =
provider of obsoletes
+* Learnt: p > 0, d < 0 (A|-B)
+* No-op: p = 0, d = 0 (null) (used as policy rule
placeholder)
+* install one of: p =-SYS, d > 0
+*
+* resulting watches:
+* ------------------
+* Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
+* Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
+* every other : w1 = p, w2 = whatprovidesdata[d];
+* Disabled rule: d < 0, w1 = 0
+*
+* always returns a rule for non-rpm rules
+*/
+\endcode
+
+enablerule:
+ if (d < 0): d = -d - 1
+disablerule
+ if (d >= 0): d = -d - 1
+
+
+\subsection watches Watches
+
+Watches are usually on literals that are not FALSE (either TRUE or UNDEF)
+Execept: If one watch is on a TRUE (set first), the other can be on a
+ FALSE (set later). This is useful on a backtrack.
+
+Watches 'link' rules involving the same literal
+Only for n-ary (n >= 2) rules, not for assertions
+
+
+Watches start at solv->watches[nsolvables]
+
+watches[nsolvables+s] == rule installing s (aka A, B, C,... in CNF clause)
+watches[nsolvables-s] == rule removing s (aka -A, -B, -C, ... in CNF clause)
+
+'watches trigger when literal goes false'
+
+watches[A] = rule involving A
+ rule->n1 = next rule involving A
+watches[B] = rule involving B
+ rule->n2 = next rule involving B
+
+
+\subsection propag Propagation
+
+This distributes decisions among affected rules and checks that rules
+evaluate to 'true'.
+
+Since rules are in CNF (conjunctive normal form), it is sufficient for
+one sub-term (x or y in x|y) to become 'true'.
+
+The interesting case is a 'false' sub-term (x or y in x|y) because
+this requires the 'other' side to become true.
+
+
+\subsection iterat Iterating over installed
+
+The pool marks the minimum and maximum Id of installed solvables.
+There might be other (non-installed) solvables in-between.
+
+\section algo Algorithm
+
+- set up rules for installed packages
+if (installed)
+ foreach(installed): addrpmrulesforsolvable
+ convert dependencies of solvable into rules
+ run through the complete graph of dependencies spawned the solvable
+ foreach(installed): addrpmrulesforupdaters
+ add rules to allow updates: A | upates(A)
+
+- set up rules for solvables mentioned in job
+ foreach (install request)
+ addrpmrulesforsolvable
+ foreach (update request)
+ addrpmrulesforupdaters
+ /* dont look at removals */
+
+- addrpmrulesforweak
+ if suggests: add dependency rule
+ else if freshens: add dependency rule
+ else if enhances: add dependency rule
+
+- add feature rules
+
+- add update rules
+
+- add job rules
+
+During solving, we only look at those rules affected by the job or a
+decision. By use of the linked-list rooted at 'watches', the solver is
+able to wade through all the rules and pick the right ones.
+
+And only those have to evaluate to 'true' during propagation.
+
+\subsection solving Actual solving works as follows
+
+- ensure the SYSTEM solvable gets installed
+- look through the job rules for 'unit' rules
+ (i.e. rules directly installing/removing a solvable)
+
+- These two define the 'initial decisions' which now get propagated
+- propagation either results in other decisions (i.e. one sub-term
+ false requires the other one to become true) or 'free' literals
+ (which are decided by policy heuristics)
+
+- The solver has a 'decisionq' which record decisions (> 0 for
+ 'install', < 0 for 'remove')
+ Every decision has an 'index' (== position in decisionq)
+ There are two 'pointers'
+ - decisionq.count == total number of made decision
+ - propagate_index == number of already propagated decisions
+
+ Decisions are also recorded in decisionmap, indexed by the solvable
+ Id. This is a fast access to decisions (instead of searching in the
+ queue)
+
+ And there is 'decisionq_why', indexed by the decision number (level)
+ returning the rule leading to the decision.
+
+ propagate() now tries to advance propagate_index to decisionq.count
+ in order to propagate all decisions to all (affected) rules.
+ propagate() also ensures that decisions are consistent (else its a
+ solver conflict) and all affected rules evaluate to 'true'.
+
+ When rules are reduced to 'unit' (only one undecided literal, all
+ others 'false'), the last literal must be decided to 'true'.
+
+*/
\ No newline at end of file

Modified: trunk/sat-solver/doc/autoinclude/Mainpage.doc
URL:
http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/Mainpage.doc?rev=11725&r1=11724&r2=11725&view=diff
==============================================================================
--- trunk/sat-solver/doc/autoinclude/Mainpage.doc (original)
+++ trunk/sat-solver/doc/autoinclude/Mainpage.doc Wed Nov 19 16:29:53 2008
@@ -1,6 +1,59 @@
-/** \namespace zypp libzypp
-*/
-** \mainpage Welcome to libzypp
+/** \mainpage satsolver SAT Solver for package management

+\author Michael Schroeder <mls@xxxxxxx>
+
+\section welcome Welcome
+
+Welcome to the sat solver documentation page.
+
+\section whatis What is the SAT solver?
+
+The SAT solver is a package dependency solver library which offers the
following:
+
+- A dependency solver based on SAT algorithms:
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem
+- an efficient file and memory representation for the usually complex
repository and dependency data, with attributes support. See more at \ref
formatpage
+
+See \ref historypage for the SAT solver history.
+
+\section basicidea Basic idea
+
+Express packaga dependencies as boolean expressions.
+(in conjunctive normal form - CNF)
+
+(! == boolean not)
+
+- A requires B -> !A or B
+- A conflicts B -> !A or !B (! (A and B)
+* A obsoletes B -> A conflicts B
+- A provides B -> B == A (replace all occurences of B in CNFs with A)
+
+\subsection datastruct Concepts & Datastructures
+
+- Solvable:
+ - Representation of package with name, version, architecture, dependencies
+- Repo:
+ - Collection of solvables, like a repository or the rpm database
+- Pool:
+ - Collection of repositories. See more at \ref poolpage
+
+\section usage Usage
+
+- The installed packages are represented as a single repo
+- The installed and available packages are represented as a Pool
+
+The solver gets initialized by passing it the complete pool (all Solvables)
+and a single Source (called 'system', representing the installed Solvables).
+
+It then creates rules to flag the Solvables of 'system' as installed.
+
+\section Contributing
+
+See \ref codeconvpage for code conventions.
+
+\section seealso See also
+
+http://del.icio.us/kkaempf/sat for a general overview on references
+about satisfiability, sat-solving and its relation to package
+dependencies.

*/
\ No newline at end of file

Added: trunk/sat-solver/doc/autoinclude/Planning.doc
URL:
http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/Planning.doc?rev=11725&view=auto
==============================================================================
--- trunk/sat-solver/doc/autoinclude/Planning.doc (added)
+++ trunk/sat-solver/doc/autoinclude/Planning.doc Wed Nov 19 16:29:53 2008
@@ -0,0 +1,78 @@
+/** \page future Future Plan and Open issues
+
+\section plan-arch-hand Architecture handling
+- Ensure 'best' architecture is choosen on fresh install [DONE]
+- Ensure update keeps architecture [DONE]
+- Ensure dist-upgrade chooses 'best' architecture
+
+\section plan-log Logging
+- Improve logging so solver decisions are comprehensible
+
+\section plan-wd weak dependencies [DONE]
+- to support 'recommends'
+- mark rules as 'weak' so trackback on assignment conflict can
+- disable such rules and continue
+
+\section plan-rd reverse dependencies [DONE]
+- essentialfor, supplements
+- will be almost for free when weak rules are implemented
+- still rules have to be marked 'reverse' for logging and proposal
+- correctness
+
+\section plan-syntax Syntax
+- Define syntax for 'boolean expression' capability
+- How to express and, or, not within a .spec file ?
+- See 'extended reldeps' below
+
+\section plan-ls Locale supplements [DONE]
+- support local(de), locale(de,at,ch) and locale(<package>:de)
+- eventually extend 'package' to reldep, e.g. locale(package > 5.3-2:de)
+
+\section plan-sup Modalias supplements [DONE]
+- support modalias(<modalias-regexp>) and modalias(<package>:<modalias-regexp>)
+- eventually extend 'package' to reldep, e.g. modalias(package
5.3-2:<modalias-regexp>)
+
+\section plan-ar Architecture rules
+- architecture-specific dependencies
+
+\section plan-locks Locks [NOT A SOLVER ISSUE]
+- ability to keep packages at a specific version
+- ability to prevent installation of specific packages / reldep
+
+\section plan-ext-rd Extended reldeps [DONE IN PART]
+- Boolean AND, OR
+- Compare architecture
+- Compare namespace
+
+\section plan-dep-syn Syntax of dependencies [DONE]
+
+- Two types of conjunctions:
+
+ - "a>5 AND b>5" => a and b can be provided by different solvables
+ - "a>5 WITH b>5" => 'and' operation but a and b are provided by same
+ solvable. (the 'with' operator is a naming
+ proposal)
+
+\section plan-bool-exp Boolean expressions
+
+- Full range of boolean operators (AND, OR, NOT) and conditionals
(IF/THEN/ELSE) for dependencies.
+
+\section plan-src-prio Source priorities [DONE IN PART]
+- Prefer solvables from specific sources
+
+\section split-provides Split-Provides
+- Support for package splits, renames
+
+\section plan-better-sol-prop better solution proposals
+- if transactions are unsolvable, offer understandable proposals what to
change to make the transaction solvable.
+
+\section plan-multiple-sol Multiple solutions
+- compute all possible solutions and rank them
+
+\section plan-sol-rank Solution ranking
+- configurable solution ranking
+- best sources, newest packages, smallest download size,
+- smallest install size, lowest number of installs, lowest number of
+- updates, lowest number of removals, prefer most popular packages, prefer
vendor,
+
+*/
\ No newline at end of file

Added: trunk/sat-solver/doc/autoinclude/Policies.doc
URL:
http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/Policies.doc?rev=11725&view=auto
==============================================================================
--- trunk/sat-solver/doc/autoinclude/Policies.doc (added)
+++ trunk/sat-solver/doc/autoinclude/Policies.doc Wed Nov 19 16:29:53 2008
@@ -0,0 +1,95 @@
+/** \page policies Policies in sat-solver
+
+\section policiesdef Definition
+
+Policies are assumptions (decisions) in the code not reasoned by
+the dependency semantics.
+
+
+\section policies-motivation Motivation
+
+There are local policies, looking at a small set of packages during
+solving.
+Examples:
+- Prefer better architecture (i586/i686) over better version ?
+
+
+There are global policies, looking at the complete transaction after
+solving is complete.
+
+Examples:
+- Choose 'best' transaction.
+ - The smallest one - looking at the number of package changes ?
+ - The smallest one - looking at the download size ?
+ - The biggest one - looking at package versions ?
+
+Global policies are currently not supported at all.
+
+
+Generally, policies help the solver to choose from multiple
+possibilities. In most cases, this can be represented as a filter
+operation working on a list of candidates and filtering out unwanted
+ones - ideally resulting in a single candidate.
+
+
+\section policiesrecog Recognized policies
+
+These are the policies we currently know of (which should be exposed
+via the policy layer)
+
+- Version downgrade
+ Is a version downgrade allowed ?
+ - explicit, by user request
+ - implicit, by dependencies
+
+- Uninstall
+ Should the solver try to uninstall packages in order to
+ satisfy dependencies ?
+
+- Vendor change
+ Can the package vendor change during an update
+ (i.e. replace an OpenSUSE package with a 'packman' one or vice versa)
+
+- Architecture change
+ Can the architecture change during an update
+ (i586 <-> i686, to/from noarch)
+
+- Repository priority
+
+- Order for solving open dependencies
+ Look at requires before conflicts ?
+
+
+\section policiesgenfilter Generic filter
+
+The generic function is 'choose among multiple candidates' by
+- architecture
+- repository
+- vendor
+- version
+- download size
+- install size
+- transaction size (-> global policy)
+ - number of installed/updated/removed packages
+ - number of bytes downloaded
+ - best overall versions
+
+
+\section policiesengineimpl Policy engine implementation
+
+The policy engine should support policies in a generic way.
+
+Some policies might be quite complex, it should be possible to build up
+a policy chain - passing a result back to the default engine after
+applying a specific filter.
+
+Helper functions can help implementing policies, e.g.
+- filter list
+- order list
+
+
+\section policiesapi Policy engine API
+
+- to be defined -
+
+*/
\ No newline at end of file

Added: trunk/sat-solver/doc/autoinclude/Pool.doc
URL:
http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/Pool.doc?rev=11725&view=auto
==============================================================================
--- trunk/sat-solver/doc/autoinclude/Pool.doc (added)
+++ trunk/sat-solver/doc/autoinclude/Pool.doc Wed Nov 19 16:29:53 2008
@@ -0,0 +1,137 @@
+/** \page poolpage The Pool
+
+\section pool-intro Pool Introduction
+
+The pool contains all information required for dependency solving.
+
+- names
+ 'foo', 'bar', 'baz'
+- reldeps
+ 'foo > 1.0', 'bar == 42.17-33'
+- solvables
+ name-epoch:version-release.arch + dependencies
+
+Main purpose of the pool is efficient storage of data in
+terms of memory consumption and access time.
+
+
+The pool is created by reading one or more 'sources', metadata
+repositories. The rpmdb (installed software) is passed explicit
+to the solver.
+
+\subsection pool-string Strings
+
+\li names are stored as strings
+\li all string data is kept in hashtable
+\li strings in the hashtable are unique
+\li strings are represented as 'Id'
+\li string comparison is done by Id comparison
+
+Pool has 'void *stringspace' pointing to allocated memory
+Pool has 'off_t strings[Id]', giving an offset into 'stringspace' for
+each Id
+
+Buffers are allocated in blocks
+
+STRING_BLOCK the hashtable for strings is resized in these steps
+STRINGSPACE_BLOCK increments size for string buffer
+
+
+\subsubsection pool-normal-strings Normal strings
+
+ stringspace + strings[id]
+
+\subsubsection pool-rel-strings Rel expressions
+
+ stringspace + strings[Reldep->name]
+
+Rel Ids have the 31st bit set
+
+\subsection string-to-id String -> Id
+
+\see str2id
+
+\subsection id-to-string Id -> String
+
+\see id2str
+
+\subsection pool-string-edition Edition
+
+The edition is the combination of epoch (e), version (v) and
+release (r) and used for comparing package 'ages' (usually
+named versions)
+
+The string representation of an edition is
+\code
+'<e>:<v>-<r>'
+\endcode
+
+An empty epoch is considered zero (0)
+An empty version is considered ?
+An empty release is considered ?
+
+
+\section pool-comparing-editions Comparing editions
+
+The following comparison rules apply
+
+\code
+ if (e1 != e2)
+ return e1 < e2;
+ else if (v1 != v2)
+ return v1 < v2;
+ else
+ return r1 < r2;
+\endcode
+
+Names can have editions and compared against editions.
+
+In comparisons, empty values within the edition are
+treated as 'any'
+
+Example:
+
+\li A: name == 1.0
+\li B: name >= 1:2.3-4
+
+A name without any edition is said to provide 'all editions'.
+
+'name-1.0-42' matches A, 'name-1:1.0' does not.
+
+
+\section pool-reldeps RelDeps
+
+A relation is the tuple (name, operator, edition) used to
+express dependencies on ranges.
+
+
+\section pool-solvable Solvable
+
+A solvable contains all package information required for
+dependency solving.
+
+Solvables as referenced by Id, pointing into 'pool.solvables'.
+There are 'pool.nsolvables-1' number of solvables.
+
+There is no solvable with Id 0, this Id is reserved and serves
+as an 'end' indicator in lists of solvables.
+
+\section pool-string-vs-rels Strings vs. Relations
+
+Relations (i.e. <name><flag><evr>) and Strings (<name>) are encoded as
+Ids. Relations have the 32th bit set.
+The pool contains a relation dictionary next to the string dictionary.
+
+Here's an example
+
+String dict:
+2 -> bash
+3 -> zlib
+4 -> 1.2.3
+
+Relation dict:
+1 -> 3 >= 4 (i.e. zlib >= 1.2.3)
+
+Some package provides: 2, 0x80000001 (i.e. bash, zlib >= 1.2.3)
+
+*/
\ No newline at end of file

Added: trunk/sat-solver/doc/autoinclude/Queue.doc
URL:
http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/doc/autoinclude/Queue.doc?rev=11725&view=auto
==============================================================================
--- trunk/sat-solver/doc/autoinclude/Queue.doc (added)
+++ trunk/sat-solver/doc/autoinclude/Queue.doc Wed Nov 19 16:29:53 2008
@@ -0,0 +1,35 @@
+/** \page queue The solver Queue
+
+The queue schedules tasks for the solver
+
+The tasks are (cmd, id) pairs.
+
+A command consists of a job and a selection, both parts ORed together.
+The following jobs are defined:
+
+- SOLVER_INSTALL Install selection
+- SOLVER_ERASE Erase selection
+- SOLVER_UPDATE Update selection
+- SOLVER_WEAKENDEPS Ignore as many dependencies of the
+ selected solvable as needed to obtain
+ a solution
+- SOLVER_NOOBSOLETES ignore obsoles of the selection
+ (multiversion install)
+- SOLVER_LOCK lock selection, i.e. keep state
+
+There is also the SOLVER_WEAK flag, which tells the solver that it
+can ignore the request to create a solution.
+
+The following selection exist:
+
+- SOLVER_SOLVABLE id is a solvable id
+- SOLVER_SOLVABLE_NAME id is a solvable name (or a dependency),
+ packages must match with their
+ name/epoch/version/release
+- SOLVER_SOLVABLE_PROVIDES id is a dependency, packages must
+ match with one of their provides
+- SOLVER_SOLVABLE_ONE_OF id is an offset into the whatprovides
+ index, it points to a set of solvable ids
+ terminated by id 0.
+
+*/
\ 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