From 2f9e7a89a7edcec5e116ac5d921d1ab9f2ab433c Mon Sep 17 00:00:00 2001 From: Zac Medico Date: Fri, 18 Apr 2008 21:30:10 +0000 Subject: Add a new part for "Dependency Resolution". svn path=/main/trunk/; revision=9926 --- doc/dependency_resolution.docbook | 6 ++ doc/dependency_resolution/decision_making.docbook | 65 +++++++++++++++ doc/dependency_resolution/package_modeling.docbook | 93 ++++++++++++++++++++++ doc/dependency_resolution/task_scheduling.docbook | 36 +++++++++ doc/portage.docbook | 5 ++ 5 files changed, 205 insertions(+) create mode 100644 doc/dependency_resolution.docbook create mode 100644 doc/dependency_resolution/decision_making.docbook create mode 100644 doc/dependency_resolution/package_modeling.docbook create mode 100644 doc/dependency_resolution/task_scheduling.docbook (limited to 'doc') diff --git a/doc/dependency_resolution.docbook b/doc/dependency_resolution.docbook new file mode 100644 index 000000000..7dd18e84b --- /dev/null +++ b/doc/dependency_resolution.docbook @@ -0,0 +1,6 @@ + +Dependency Resolution +&dependency_resolution_package_modeling; +&dependency_resolution_decision_making; +&dependency_resolution_task_scheduling; + diff --git a/doc/dependency_resolution/decision_making.docbook b/doc/dependency_resolution/decision_making.docbook new file mode 100644 index 000000000..5bcf84388 --- /dev/null +++ b/doc/dependency_resolution/decision_making.docbook @@ -0,0 +1,65 @@ + +Decision Making + + Dependency Expression Evaluation + + In terms of boolean logic, a dependency expression can + be expressed in disjunctive normal form (DNF), which is + a disjunction of conjunctive clauses. Each conjunctive clause + represents one possible alternative combination of dependency + atoms capable of satisfying the dependency expression. + + + + Look-Ahead + + When there are multiple combinations to choose from, + a look-ahead mechanism will choose an optimal combination + to satisfy constraints and minimize cost. The + following package states influence the cost calculation for + a given combination: + + + installed + + + selected (for installation) + + + not selected (for installation) + + + + + In cost calculations, virtual packages by themselves are + considered to cost nothing since they do not directly install anything. + It is the dependencies of a virtual package that contribute to it's cost. + + + Constraint Propagation + + Combinations that include packages from the "installed" or + "selected" categories are less costly than those that + include packages from the "not selected" category. + When a package is chosen for installation, it transitions to the + "selected" state. This state change propagates + to the cost calculations of later decisions, + influencing later decisions to be consistent with earlier decisions. + This feedback mechanism serves to propagate constraints and can + influence the modeling process to + converge on a more optimal final state. + + + + Expanded Search Space + + When evaluating virtual atoms, an expanded search space is + considered which recursively traverses + the dependencies of virtual packages + from all slots matching a given virtual atom. All combinations in + this expanded search space are considered when choosing an optimal + combination to satisfy constraints with minimal cost. + + + + diff --git a/doc/dependency_resolution/package_modeling.docbook b/doc/dependency_resolution/package_modeling.docbook new file mode 100644 index 000000000..84d01a9f2 --- /dev/null +++ b/doc/dependency_resolution/package_modeling.docbook @@ -0,0 +1,93 @@ + +Package Modeling + + + Constraint Satisfaction + + Constraint Types + + Dependency resolution involves satisfaction of + many constraints: + + + Persistent configuration parameters, like those that come from + make.profile, make.conf, and the /etc/portage directory. + + + Current command parameters, which may include options, atoms, or sets. + + + + Package Dependencies + + + + + + + Package Dependencies + + Common types of package dependencies: + + + Files required for building or installing. Downloads may + be necessary to satisfy these. + + + Other packages required to be installed for + buildtime or runtime. + + + Blockers that prevent conflicting packages from being installed + simultaneously. + + + + + + + + Conflicts + + Blocker Conflicts + + If one package blocks another package, the two packages + conflict such that they cannot be installed simultaneously. + These conflicts are often due to file collisions. + + + + Slot Conflicts + + If two different packages that occupy the same slot are chosen + to satisfy dependencies, a slot conflict occurs. The two packages + cannot be installed simultaneously and therefore the respective + dependencies will not be satisfied simultaneously. + + + + Indirect Conflicts + + If the dependencies of two parent packages cannot be installed + simultaneously, it creates an indirect conflict between the parent + packages since their respective dependencies cannot be satisfied + simultaneously. + + + + + + Dependency Neglection + + In order to significantly reduce the resources consumed by + the modeling process, the dependencies of + installed packages may be neglected. + + + If a more complete dependency calculation is desired, + there is a --complete-graph option which will ensure that the + dependencies of installed packages are properly considered. + + + + diff --git a/doc/dependency_resolution/task_scheduling.docbook b/doc/dependency_resolution/task_scheduling.docbook new file mode 100644 index 000000000..8979a9f62 --- /dev/null +++ b/doc/dependency_resolution/task_scheduling.docbook @@ -0,0 +1,36 @@ + +Task Scheduling + + Task Dependencies + + All tasks are executed in an order such + that a task's dependencies are satisfied + when it is executed. Dependency relationships between tasks + form a directed graph. + + + + Conflict Avoidance + + In some cases it is possible to adjust package installation order + to avoid having two conflicting packages installed simultaneously. + + + TODO: Automatically uninstall packages when necessary to avoid conflicts. + + + + Circular Dependencies + + TODO: Automatically solve circular dependencies by temporarily disabling + conditional dependencies and then rebuilding packages with the conditional + dependencies enabled. + + + + Parallel Scheduling + + TODO: Spawn an appropriate number of tasks in parallel when desired. + + + diff --git a/doc/portage.docbook b/doc/portage.docbook index 5417bb73e..d158c1a21 100644 --- a/doc/portage.docbook +++ b/doc/portage.docbook @@ -7,6 +7,10 @@ + + + + @@ -34,6 +38,7 @@ &config; +&dependency_resolution; &package; &qa; -- cgit v1.2.3-1-g7c22