From a30382c58cffc9d798dc9767a094b1d63470713a Mon Sep 17 00:00:00 2001 From: Kristian Høgsberg Date: Wed, 2 Jul 2008 14:35:58 -0400 Subject: Move DEPSOLVE.txt and REPO.txt into docbook. A little messy, but it's a first step towards pulling all the docs into a nice self-contained document. --- docs/DEPSOLVE.txt | 364 -------------------------------------------------- docs/Makefile.am | 7 +- docs/REPO.txt | 172 ------------------------ docs/package-set.xml | 239 +++++++++++++++++++++++++++++++++ docs/razor-docs.xml | 2 + docs/solver.xml | 370 +++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 615 insertions(+), 539 deletions(-) delete mode 100644 docs/DEPSOLVE.txt delete mode 100644 docs/REPO.txt create mode 100644 docs/package-set.xml create mode 100644 docs/solver.xml (limited to 'docs') diff --git a/docs/DEPSOLVE.txt b/docs/DEPSOLVE.txt deleted file mode 100644 index 43e670a..0000000 --- a/docs/DEPSOLVE.txt +++ /dev/null @@ -1,364 +0,0 @@ -YUM vs RAZOR ------------- - -At a very high level, yum's depsolver does something roughly -equivalent to: - - - For each package being installed or removed - - - For each relevant property (provides, requires, conflicts, - obsoletes): - - - Figure out what additional packages need to be added to - or removed from the system to satisfy this property - -which ends up being roughly O(N^2 * M) where N is the total number of -properties and M is the number of packages being acted on. - -(I just figured that out off the top of my head, and I'm not totally -familiar with the yum code, so it may be wrong.) - -Razor's depsolver is something like: - - - do { - - - For each property to be added to or removed from the system: - - - Figure out what packages need to be added to or removed - from the system to satisfy this property - - - } until we stop adding/remove more packages - -with the key being that it's very easy to find the PROVIDES -corresponding to a REQUIRES and vice versa, because the property -arrays are sorted, and so all properties with the same "name" will be -adjacent to one another in the array, allowing many dependencies to be -satisified in essentially constant time. (Actually... we've been -calling it constant, but it's really O(log N) for heavily-depended-on -packages, because the more packages you have, the more variations on -"requires foo", "requires foo = 1.1", "requires foo > 1.0", etc you're -going to have to scan through.) - -Ideally though, each iteration of the inner loop body happens in -constant time, and thus the inner loop as a whole is O(N), and thus -the depsolver as a whole is O(N * M) (or at least, less than -O(N * M * log N). - - -FILE DEPENDENCIES ------------------ - -Whenever we add a package with a file REQUIRES to a razor_set, we also -add a PROVIDES for that file to the package or packages which provide -that file. This means that if we later add another package that -requires the same file (eg, /bin/sh or /usr/bin/perl), we can resolve -its file requirement exactly like we would resolve a property -requirement, in nearly constant time. - -When adding a *new* file requirement (ie, a requirement on a file that -no existing package depends on), we still have to scan through the -file tree, which is O(log N) in the number of files. - -(AFAICT, there's no reason yum couldn't do the same optimization. -Also, AFAICT, yum currently sticks property dependencies and file -dependencies into the same hash table, so that if any package in the -transaction has a file dependency, it causes *property* dependencies -to become slower to resolve as well...) - - -THE RULES ---------- - -This is what we have figured out for transaction-solving rules; -neither yum nor rpm's algorithm seems to be explained in full -anywhere... - - 1. Every requested install in the initial package set must be - satisfied as either a new install or an update: - - - if the requested package name is the name of an upstream - package: - - - if there is not a corresponding already-installed - package, then install the upstream package - - - else if the upstream package is newer than the - already-installed package, then update the package - - - else it's an error (UP_TO_DATE) - - - else if the requested package name is the name of an - already-installed package: - - - if there is an upstream package that obsoletes the - already-installed package, then behave as though the - user had requested that that package be installed - instead. - - - else it's an error (UP_TO_DATE or INSTALL_UNAVAILABLE?) - - - else it's an error (INSTALL_UNAVAILABLE) - - 2. Every requested removal in the initial package set must be - satisfied as a removal. If any requested package name is not - the name of an installed package, it's an error - (REMOVE_NOT_INSTALLED) - - REQUIRES processing: - - 3. If a package being installed or updated-to REQUIRES a property - that is not provided by any installed or to-be-installed - package, we need to find an installable package that provides - that property. If we find one, install/update it. If not, it's - an error (UNSATISFIABLE). (If we find an upstream package - providing the property that corresponds to a system package - that's being removed, then it's a CONTRADICTION.) - - 4. If an already-installed package REQUIRES a property which is - only provided by a package that is being removed, then that - package needs to be removed as well. - - 5. If an already-installed package REQUIRES a property which is - only provided by a package that is being upgraded or obsoleted - (to a new package which does not provide that property), then: - - - if there is an update for the installed package, then update - the installed package - - - else if there is another installable package that provides - the required property, then install that. - - - else it's an error (UNSATISFIABLE?) - - CONFLICTS processing - - 6. If a package being installed or updated-to CONFLICTS with a - property provided by an installed package: - - - if there is an update for the installed package, which the - new package does not conflict with, then update the - installed package. - - - else it's an error (NEW_CONFLICT) - - 7. If an already-installed package CONFLICTS with a property - provided by a to-be-installed package: - - - if there is an update for the installed package, which does - not conflict with the new package, then update the installed - package. - - - else it's an error (NEW_CONFLICT) - - 8. If a package being installed or updated-to CONFLICTS with a - property provided by a to-be-installed package, then it's an - error (CONTRADICTION). - - OBSOLETES processing. NOTE: OBSOLETES are only matched against - package names, not against arbitrary provided properties - - 9. If a package being installed or updated-to OBSOLETES an - installed package, then obsolete that package. (ie, remove it, - but treat it as updated for purposes of dangling REQUIRES). - - 10. If an already-installed package OBSOLETES a to-be-installed - package, then it's an error. (ALREADY_OBSOLETE) - - 11. If a package being installed or updated-to OBSOLETES another - package being installed or updated-to, then it's an error - (CONTRADICTION). - - - -THE DEPSOLVER -------------- - -We start with two razor_sets, system and upstream, and a list of -requested installations and removals. - - FIXME: what about multiple upstream repos? Having to deal with - arbitrary numbers of razor_sets is possible, but will probably be - messy... It might be easier to either store all upstream repo data - in a single .rzdb file, or else merge all upstream .rzdb files - together into a single razor_set at startup. (Or some combination - of those.) - -We create a bit array of the packages in each set, indicating which -ones are installed; the system bitarray starts out all 1s, and the -upstream bitarray all 0s. Each bit is only allowed to change state -once during the transaction; an installed package can be removed, or -an uninstalled package installed, but trying to reinstall a removed -package, or uninstall a newly-installed package is an error. This -means the packages break down into four categories: - - - installed (1 bit in the system bit array) - - to-be-removed (0 bit in the system bit array) - - to-be-installed (1 bit in the upstream bit array) - - installable (0 bit in the upstream bit array) - - -Depsolver algorithm: - - - Create new razor_transaction_packages ("rtp"s) for each - requested install or remove. These will be "unresolved", because - we haven't yet found the razor_packages that correspond to them. - - - while there are new rtps: - - - sort the new rtps - - - Walk the system property list, upstream property list, and - new rtp list in parallel, and: - - - For each uninstalled PROVIDES: - - - If the property is a valid package name (that is, - either it's a package providing its own name, or it - has a matching OBSOLETES), and it matches the name - of a new rtp of type INSTALL or FORCED_UPDATE with - an unresolved new_package: - - - If the upstream package has the same version as - the system package, we have an UP_TO_DATE error - (FIXME: not quite right. This doesn't deal with - the case where we try to update an application - because of a library update, and it turns out - there's no new version of the application, but - there IS a compat package containing the old - version of the library.) - - - Otherwise, set the rtp's new_package to point to - the package providing this property and set the - appropriate bit in the upstream bit array. - - - For each to-be-installed non-file REQUIRES: - - - See if there's an installed or to-be-installed - package that PROVIDES that property. - - - If not, see if there's an installable package that - PROVIDES that property, and create a new INSTALL rtp - for it if so. - - - If not, see if there's a to-be-removed package that - PROVIDES that property. (If we find such a package, - we have a CONTRADICTION error.) - - - If none of the above, then we have an UNSATISFIABLE - error - - - For each to-be-installed file REQUIRES: - - - (We create fake file PROVIDES to match file REQUIRES - when importing/merging razor sets, so if there is - already another installed package that REQUIRES this - file, there will be a PROVIDES listed for it as well.) - - - See if there's an installed package that PROVIDES - that file. - - - If not, do a binary search of the system file tree - looking to see if some installed package provides - that file but does not have a PROVIDES for it. - - - If not, see if there's an installable package that - PROVIDES that property, and create a new INSTALL rtp - for it if so. - - - (If we actually work with multiple upstream - razor_sets, then we will need to search the upstream - file trees at this point, because it's possible that - a package in one upstream repo would require a file - in another upstream repo. But if we merge the - multiple upstream repos into a single razor_set at - some point, then we would not need to do that, - because it would be guaranteed that we would have - already created a fake PROVIDES if any package - provides the file.) - - - If no installed or installable package provides the - file, see if there's a to-be-removed package that - provides the file. (If we find such a package, we - have a CONTRADICTION error.) - - - If none of the above, then we have an UNSATISFIABLE - error - - - For each to-be-installed PROVIDES: - - - Check if the new PROVIDES conflicts with an - installed CONFLICTS. If so, create a new - FORCED_UPDATE rtp for the installed package, so we - can try to upgrade it to a non-conflicting version. - (If we can't, we'll have an OLD_CONFLICT error.) - - - Check if the new PROVIDES conflicts with an - installed OBSOLETES *and* the PROVIDES property - corresponds to the name of its package. (That is, - OBSOLETES are only matched against package names, - not arbitrary provided properties.) If so, we have - an ALREADY_OBSOLETE error. - - - Check if the new PROVIDES conflicts with a - to-be-installed CONFLICTS. If so, we have a - CONTRADICTION error. - - - For each to-be-installed CONFLICTS: - - - Basically the reverse of the previous case: check if - the new CONFLICTS conflicts with an installed - PROVIDES. If so, create a new FORCED_UPDATE rtp for - the installed package, so we can try to upgrade it - to a non-conflicting version. (If we can't, we'll - have an NEW_CONFLICT error.) - - - Check if the new CONFLICTS conflicts with a - to-be-installed PROVIDES. If so, we have a - CONTRADICTION error. - - - For each to-be-installed OBSOLETES: - - - Check if there's an installed package that PROVIDES - that property. If so, create an OBSOLETED rtp for - the installed package. - - - If not, check if there's a to-be-installed package - that PROVIDES that property. If so, we have a - CONTRADICTION error. - - - - For each installed PROVIDES: - - - If the property is a valid package name (that is, - it's a package providing its own name), and it - matches the name of a new rtp with an unresolved - old_package, then set the rtp's old_package to point - to the package providing this property and clear the - appropriate bit in the system bit array. - - - For each to-be-removed PROVIDES: - - - If there's also an identical to-be-installed - PROVIDES, we're ok and can skip this - - - Otherwise, for each installed REQUIRES of this - property: - - - Look for some other installed or to-be-installed - property that satisfies the REQUIRES. - - - If there isn't one, then for each installed - package in this REQUIRES's package list: - - - If the PROVIDES was lost because the old - package was REMOVEd (not FORCED_UPDATE or - OBSOLETED), then create a new REMOVE rtp for - this package. - - - Otherwise, create a new FORCED_UPDATE rtp - for this package. - - - (We don't need to look at to-be-installed REQUIRES - of this property, because if there are any, they - will cause a CONTRADICTION error when we try to - re-satisfy them the next time through.) diff --git a/docs/Makefile.am b/docs/Makefile.am index 342e364..7b4cab0 100644 --- a/docs/Makefile.am +++ b/docs/Makefile.am @@ -30,7 +30,8 @@ endif EXTRA_DIST += version.xml.in docsdir = $(datadir)/doc/razor -dist_docs_DATA = \ - DEPSOLVE.txt \ - REPO.txt + +content_files = \ + package-set.xml \ + solver.xml diff --git a/docs/REPO.txt b/docs/REPO.txt deleted file mode 100644 index 92a4f56..0000000 --- a/docs/REPO.txt +++ /dev/null @@ -1,172 +0,0 @@ -The repo file format / razor_set data structure ------------------------------------------------ - -The repo starts with a header, containing some number of sections, -terminated by a section with type 0: - - struct razor_set_header { - uint32_t magic; - uint32_t version; - struct razor_set_section sections[0]; - }; - - struct razor_set_section { - uint32_t type; - uint32_t offset; - uint32_t size; - }; - -razor_set_open() mmaps the repo file, and creates a struct razor_set: - - struct razor_set { - struct array string_pool; - struct array packages; - struct array properties; - struct array files; - struct array package_pool; - struct array property_pool; - struct array file_pool; - struct razor_set_header *header; - }; - -by finding the sections with those IDs and creating "struct array"s -pointing to the right places in the mmapped data. (This is the only -processing needed when reading in the file; everything else is used -exactly as-is.) - - -The sections ------------- - -RAZOR_STRING_POOL - - Stores one copy of each string that appears in the repo. (At - the moment, this is: package names, package versions, property - names, property versions, and (basenames of) filenames.) The - strings are arbitrarily-sized, 0-terminated, and not in any - particular order (although the empty string always ends up - being at offset 0). - -RAZOR_PACKAGES - - Array of struct razor_package; one for each package in the - set, sorted by name. - -RAZOR_PROPERTIES - - Array of struct razor_property; one for each unique property - in the set, sorted by type, then name, then relation type (eg, - "<" or ">="), then version. (Properties with no version have - relation type RAZOR_VERSION_EQUAL, and version "".) - -RAZOR_FILES - - Array of struct razor_entry; one for each file owned by any - package in the set. The current sort order (which is subject - to change) is breadth-first, sorted by basename. So eg: /, /bin, - /dev, /etc, /bin/false, /bin/true, /dev/null, /etc/passwd. - -RAZOR_PACKAGE_POOL - - Array of struct list, with each list item containing the index - of a struct razor_package in the packages section. See the - discussion of lists below. - -RAZOR_PROPERTY_POOL - - Array of struct list, with each list item containing the index - of a struct razor_property in the properties section. See the - discussion of lists below. - -RAZOR_FILE_POOL - - Array of struct list, with each list item containing the index - of a struct razor_entry in the files section. See the - discussion of lists below. - - -Data types ----------- -Note that the exact layout of bits involves some historical accidents. -(Particularly the fact that the "name" field in most structs loses its -high bits to a flags field.) - -struct list_head - uint list_ptr : 24; - uint flags : 8; - -struct list - uint data : 24; - uint flags : 8; - - Used to store lists of package, property, or file IDs. "struct - list_head" stores the head of the list, which points to one or - more "struct list"s in the appropriate "pool" section. - ("struct list" should probably be called "struct list_item".) - - "list_first(&head, &pool)" returns a "struct list *" pointing - to the first element of the list (or NULL for an empty list), - and "list_next(list)" will return successive elements, until - NULL is returned. Each "list->data" contains the index of a - package, property, or file in the corresponding section of the - set. - - Peeking underneath the abstraction, a list_head's "flags" is - 0xff if the list is empty, 0x80 if it contains a single - element, or 0x00 if it contains more than one element. In the - single-element case, that element is actually stored in the - list_head directly rather than being stored in a pool (and so - list_first() just casts the list_head* to a list* and returns - it). For multi-element lists, list_ptr is the index in the - pool of the first element of this list; the list continues - through successive elements of the pool until one with - non-zero flags is reached, indicating the end of the list. - -struct razor_package - uint name : 24; - uint flags : 8; - uint version : 32; - struct list_head properties; - struct list_head files; - - name and version are indexes into string_pool. properties is a - list of all of the package's properties, and files is a list - of its files. flags is currently only used during razor_set - merging, to keep track of which set a package came from. - -struct razor_property - uint name : 24; - uint flags : 6; - uint type : 2; - uint relation : 32; - uint version : 32; - struct list_head packages; - - name and version are indexes into string_pool. type is an enum - razor_property_type (eg, RAZOR_PROPERTY_REQUIRES), and - relation is an enum razor_version_relation (eg, - RAZOR_VERSION_GREATER_OR_EQUAL). packages is a list of the - packages that have this property. flags is currently unused. - -struct razor_entry - uint name : 24; - uint flags : 8; - uint start : 32; - struct list_head packages; - - name is an index into string_pool, giving the basename of the - file. start is either 0, or an index pointing to another - razor_entry that is the first child of this entry (for a - non-empty directory). (Entry 0 is always the root of the tree, - so no entry could have entry 0 as a child.) flags is 0x80 - (RAZOR_ENTRY_LAST) if an entry is the last entry in its - directory. Otherwise it is 0. - - Note that given a pointer to a struct_razor_entry (eg, from a - package's "files" list), there is no way to reconstruct its - full name without walking the entire files array up to that - point. Because of this and other problems (fix_file_map()), it - seems like razor_entry should be modified to include a pointer - to its parent. (Storing full paths instead of just basenames - would also fix this problem, but that would use much more - memory.) diff --git a/docs/package-set.xml b/docs/package-set.xml new file mode 100644 index 0000000..c81c16a --- /dev/null +++ b/docs/package-set.xml @@ -0,0 +1,239 @@ + + + + + Package Set File Format + + + File header + + + The repo starts with a header, containing some number of + sections, terminated by a section with type 0: + + + + + + razor_set_open() mmaps the repo file, and creates a struct razor_set: + + + + + + by finding the sections with those IDs and creating struct + array's pointing to the right places in the mmapped data. (This + is the only processing needed when reading in the file; + everything else is used exactly as-is.) + + + + + + The sections + + + + + RAZOR_STRING_POOL Stores one copy of + each string that appears in the repo. (At the moment, this + is: package names, package versions, property names, + property versions, and (basenames of) filenames.) The + strings are arbitrarily-sized, 0-terminated, and not in any + particular order (although the empty string always ends up + being at offset 0). + + + + + + RAZOR_PACKAGES Array of struct + razor_package; one for each package in the set, sorted by + name. + + + + + + RAZOR_PROPERTIES Array of struct + razor_property; one for each unique property in the set, + sorted by type, then name, then relation type (eg, "<" or + ">="), then version. (Properties with no version have + relation type RAZOR_VERSION_EQUAL, and version "".) + + + + + + RAZOR_FILES Array of struct + razor_entry; one for each file owned by any package in the + set. The current sort order (which is subject to change) + is breadth-first, sorted by basename. So eg: /, /bin, + /dev, /etc, /bin/false, /bin/true, /dev/null, /etc/passwd. + + + + + + RAZOR_PACKAGE_POOL Array of struct + list, with each list item containing the index of a struct + razor_package in the packages section. See the discussion + of lists below. + + + + + + RAZOR_PROPERTY_POOL Array of struct + list, with each list item containing the index of a struct + razor_property in the properties section. See the + discussion of lists below. + + + + + + RAZOR_FILE_POOL Array of struct list, + with each list item containing the index of a struct + razor_entry in the files section. See the discussion of + lists below. + + + + + + + Data types + + + Note that the exact layout of bits involves some historical + accidents. (Particularly the fact that the "name" field in most + structs loses its high bits to a flags field.) + + + + + + Used to store lists of package, property, or file IDs. "struct + list_head" stores the head of the list, which points to one or + more "struct list"s in the appropriate "pool" section. ("struct + list" should probably be called "struct list_item".) + + + + "list_first(&head, &pool)" returns a "struct list *" + pointing to the first element of the list (or NULL for an empty + list), and "list_next(list)" will return successive elements, + until NULL is returned. Each "list->data" contains the index of + a package, property, or file in the corresponding section of the + set. + + + + Peeking underneath the abstraction, a list_head's "flags" is + 0xff if the list is empty, 0x80 if it contains a single element, + or 0x00 if it contains more than one element. In the + single-element case, that element is actually stored in the + list_head directly rather than being stored in a pool (and so + list_first() just casts the list_head* to a list* and returns + it). For multi-element lists, list_ptr is the index in the pool + of the first element of this list; the list continues through + successive elements of the pool until one with non-zero flags is + reached, indicating the end of the list. + + + + + + name and version are indexes into string_pool. properties is a + list of all of the package's properties, and files is a list of + its files. flags is currently only used during razor_set + merging, to keep track of which set a package came from. + + + + + + name and version are indexes into string_pool. type is an enum + razor_property_type (eg, RAZOR_PROPERTY_REQUIRES), and relation + is an enum razor_version_relation (eg, + RAZOR_VERSION_GREATER_OR_EQUAL). packages is a list of the + packages that have this property. flags is currently unused. + + + + + + name is an index into string_pool, giving the basename of the + file. start is either 0, or an index pointing to another + razor_entry that is the first child of this entry (for a + non-empty directory). (Entry 0 is always the root of the tree, + so no entry could have entry 0 as a child.) flags is 0x80 + (RAZOR_ENTRY_LAST) if an entry is the last entry in its + directory. Otherwise it is 0. + + + + Note that given a pointer to a struct_razor_entry (eg, from a + package's "files" list), there is no way to reconstruct its full + name without walking the entire files array up to that + point. Because of this and other problems (fix_file_map()), it + seems like razor_entry should be modified to include a pointer + to its parent. (Storing full paths instead of just basenames + would also fix this problem, but that would use much more + memory.) + + + diff --git a/docs/razor-docs.xml b/docs/razor-docs.xml index f2866a5..fad46fd 100644 --- a/docs/razor-docs.xml +++ b/docs/razor-docs.xml @@ -59,6 +59,8 @@ This part presents the design documentation for razor. + + diff --git a/docs/solver.xml b/docs/solver.xml new file mode 100644 index 0000000..5d9578c --- /dev/null +++ b/docs/solver.xml @@ -0,0 +1,370 @@ + + + + + Dependency Solver + + + At a very high level, yum's depsolver does something roughly + equivalent to: + + - For each package being installed or removed + + - For each relevant property (provides, requires, conflicts, + obsoletes): + + - Figure out what additional packages need to be added to + or removed from the system to satisfy this property + + which ends up being roughly O(N^2 * M) where N is the total number of + properties and M is the number of packages being acted on. + +(I just figured that out off the top of my head, and I'm not totally +familiar with the yum code, so it may be wrong.) + +Razor's depsolver is something like: + + - do { + + - For each property to be added to or removed from the system: + + - Figure out what packages need to be added to or removed + from the system to satisfy this property + + - } until we stop adding/remove more packages + +with the key being that it's very easy to find the PROVIDES +corresponding to a REQUIRES and vice versa, because the property +arrays are sorted, and so all properties with the same "name" will be +adjacent to one another in the array, allowing many dependencies to be +satisified in essentially constant time. (Actually... we've been +calling it constant, but it's really O(log N) for heavily-depended-on +packages, because the more packages you have, the more variations on +"requires foo", "requires foo = 1.1", "requires foo > 1.0", etc you're +going to have to scan through.) + +Ideally though, each iteration of the inner loop body happens in +constant time, and thus the inner loop as a whole is O(N), and thus +the depsolver as a whole is O(N * M) (or at least, less than +O(N * M * log N). + + +FILE DEPENDENCIES +----------------- + +Whenever we add a package with a file REQUIRES to a razor_set, we also +add a PROVIDES for that file to the package or packages which provide +that file. This means that if we later add another package that +requires the same file (eg, /bin/sh or /usr/bin/perl), we can resolve +its file requirement exactly like we would resolve a property +requirement, in nearly constant time. + +When adding a *new* file requirement (ie, a requirement on a file that +no existing package depends on), we still have to scan through the +file tree, which is O(log N) in the number of files. + +(AFAICT, there's no reason yum couldn't do the same optimization. +Also, AFAICT, yum currently sticks property dependencies and file +dependencies into the same hash table, so that if any package in the +transaction has a file dependency, it causes *property* dependencies +to become slower to resolve as well...) + + +THE RULES +--------- + +This is what we have figured out for transaction-solving rules; +neither yum nor rpm's algorithm seems to be explained in full +anywhere... + + 1. Every requested install in the initial package set must be + satisfied as either a new install or an update: + + - if the requested package name is the name of an upstream + package: + + - if there is not a corresponding already-installed + package, then install the upstream package + + - else if the upstream package is newer than the + already-installed package, then update the package + + - else it's an error (UP_TO_DATE) + + - else if the requested package name is the name of an + already-installed package: + + - if there is an upstream package that obsoletes the + already-installed package, then behave as though the + user had requested that that package be installed + instead. + + - else it's an error (UP_TO_DATE or INSTALL_UNAVAILABLE?) + + - else it's an error (INSTALL_UNAVAILABLE) + + 2. Every requested removal in the initial package set must be + satisfied as a removal. If any requested package name is not + the name of an installed package, it's an error + (REMOVE_NOT_INSTALLED) + + REQUIRES processing: + + 3. If a package being installed or updated-to REQUIRES a property + that is not provided by any installed or to-be-installed + package, we need to find an installable package that provides + that property. If we find one, install/update it. If not, it's + an error (UNSATISFIABLE). (If we find an upstream package + providing the property that corresponds to a system package + that's being removed, then it's a CONTRADICTION.) + + 4. If an already-installed package REQUIRES a property which is + only provided by a package that is being removed, then that + package needs to be removed as well. + + 5. If an already-installed package REQUIRES a property which is + only provided by a package that is being upgraded or obsoleted + (to a new package which does not provide that property), then: + + - if there is an update for the installed package, then update + the installed package + + - else if there is another installable package that provides + the required property, then install that. + + - else it's an error (UNSATISFIABLE?) + + CONFLICTS processing + + 6. If a package being installed or updated-to CONFLICTS with a + property provided by an installed package: + + - if there is an update for the installed package, which the + new package does not conflict with, then update the + installed package. + + - else it's an error (NEW_CONFLICT) + + 7. If an already-installed package CONFLICTS with a property + provided by a to-be-installed package: + + - if there is an update for the installed package, which does + not conflict with the new package, then update the installed + package. + + - else it's an error (NEW_CONFLICT) + + 8. If a package being installed or updated-to CONFLICTS with a + property provided by a to-be-installed package, then it's an + error (CONTRADICTION). + + OBSOLETES processing. NOTE: OBSOLETES are only matched against + package names, not against arbitrary provided properties + + 9. If a package being installed or updated-to OBSOLETES an + installed package, then obsolete that package. (ie, remove it, + but treat it as updated for purposes of dangling REQUIRES). + + 10. If an already-installed package OBSOLETES a to-be-installed + package, then it's an error. (ALREADY_OBSOLETE) + + 11. If a package being installed or updated-to OBSOLETES another + package being installed or updated-to, then it's an error + (CONTRADICTION). + + + +THE DEPSOLVER +------------- + +We start with two razor_sets, system and upstream, and a list of +requested installations and removals. + + FIXME: what about multiple upstream repos? Having to deal with + arbitrary numbers of razor_sets is possible, but will probably be + messy... It might be easier to either store all upstream repo data + in a single .rzdb file, or else merge all upstream .rzdb files + together into a single razor_set at startup. (Or some combination + of those.) + +We create a bit array of the packages in each set, indicating which +ones are installed; the system bitarray starts out all 1s, and the +upstream bitarray all 0s. Each bit is only allowed to change state +once during the transaction; an installed package can be removed, or +an uninstalled package installed, but trying to reinstall a removed +package, or uninstall a newly-installed package is an error. This +means the packages break down into four categories: + + - installed (1 bit in the system bit array) + - to-be-removed (0 bit in the system bit array) + - to-be-installed (1 bit in the upstream bit array) + - installable (0 bit in the upstream bit array) + + +Depsolver algorithm: + + - Create new razor_transaction_packages ("rtp"s) for each + requested install or remove. These will be "unresolved", because + we haven't yet found the razor_packages that correspond to them. + + - while there are new rtps: + + - sort the new rtps + + - Walk the system property list, upstream property list, and + new rtp list in parallel, and: + + - For each uninstalled PROVIDES: + + - If the property is a valid package name (that is, + either it's a package providing its own name, or it + has a matching OBSOLETES), and it matches the name + of a new rtp of type INSTALL or FORCED_UPDATE with + an unresolved new_package: + + - If the upstream package has the same version as + the system package, we have an UP_TO_DATE error + (FIXME: not quite right. This doesn't deal with + the case where we try to update an application + because of a library update, and it turns out + there's no new version of the application, but + there IS a compat package containing the old + version of the library.) + + - Otherwise, set the rtp's new_package to point to + the package providing this property and set the + appropriate bit in the upstream bit array. + + - For each to-be-installed non-file REQUIRES: + + - See if there's an installed or to-be-installed + package that PROVIDES that property. + + - If not, see if there's an installable package that + PROVIDES that property, and create a new INSTALL rtp + for it if so. + + - If not, see if there's a to-be-removed package that + PROVIDES that property. (If we find such a package, + we have a CONTRADICTION error.) + + - If none of the above, then we have an UNSATISFIABLE + error + + - For each to-be-installed file REQUIRES: + + - (We create fake file PROVIDES to match file REQUIRES + when importing/merging razor sets, so if there is + already another installed package that REQUIRES this + file, there will be a PROVIDES listed for it as well.) + + - See if there's an installed package that PROVIDES + that file. + + - If not, do a binary search of the system file tree + looking to see if some installed package provides + that file but does not have a PROVIDES for it. + + - If not, see if there's an installable package that + PROVIDES that property, and create a new INSTALL rtp + for it if so. + + - (If we actually work with multiple upstream + razor_sets, then we will need to search the upstream + file trees at this point, because it's possible that + a package in one upstream repo would require a file + in another upstream repo. But if we merge the + multiple upstream repos into a single razor_set at + some point, then we would not need to do that, + because it would be guaranteed that we would have + already created a fake PROVIDES if any package + provides the file.) + + - If no installed or installable package provides the + file, see if there's a to-be-removed package that + provides the file. (If we find such a package, we + have a CONTRADICTION error.) + + - If none of the above, then we have an UNSATISFIABLE + error + + - For each to-be-installed PROVIDES: + + - Check if the new PROVIDES conflicts with an + installed CONFLICTS. If so, create a new + FORCED_UPDATE rtp for the installed package, so we + can try to upgrade it to a non-conflicting version. + (If we can't, we'll have an OLD_CONFLICT error.) + + - Check if the new PROVIDES conflicts with an + installed OBSOLETES *and* the PROVIDES property + corresponds to the name of its package. (That is, + OBSOLETES are only matched against package names, + not arbitrary provided properties.) If so, we have + an ALREADY_OBSOLETE error. + + - Check if the new PROVIDES conflicts with a + to-be-installed CONFLICTS. If so, we have a + CONTRADICTION error. + + - For each to-be-installed CONFLICTS: + + - Basically the reverse of the previous case: check if + the new CONFLICTS conflicts with an installed + PROVIDES. If so, create a new FORCED_UPDATE rtp for + the installed package, so we can try to upgrade it + to a non-conflicting version. (If we can't, we'll + have an NEW_CONFLICT error.) + + - Check if the new CONFLICTS conflicts with a + to-be-installed PROVIDES. If so, we have a + CONTRADICTION error. + + - For each to-be-installed OBSOLETES: + + - Check if there's an installed package that PROVIDES + that property. If so, create an OBSOLETED rtp for + the installed package. + + - If not, check if there's a to-be-installed package + that PROVIDES that property. If so, we have a + CONTRADICTION error. + + + - For each installed PROVIDES: + + - If the property is a valid package name (that is, + it's a package providing its own name), and it + matches the name of a new rtp with an unresolved + old_package, then set the rtp's old_package to point + to the package providing this property and clear the + appropriate bit in the system bit array. + + - For each to-be-removed PROVIDES: + + - If there's also an identical to-be-installed + PROVIDES, we're ok and can skip this + + - Otherwise, for each installed REQUIRES of this + property: + + - Look for some other installed or to-be-installed + property that satisfies the REQUIRES. + + - If there isn't one, then for each installed + package in this REQUIRES's package list: + + - If the PROVIDES was lost because the old + package was REMOVEd (not FORCED_UPDATE or + OBSOLETED), then create a new REMOVE rtp for + this package. + + - Otherwise, create a new FORCED_UPDATE rtp + for this package. + + - (We don't need to look at to-be-installed REQUIRES + of this property, because if there are any, they + will cause a CONTRADICTION error when we try to + re-satisfy them the next time through.) + + -- cgit v1.2.3