diff options
| -rw-r--r-- | doc/dependency_resolution.docbook | 6 | ||||
| -rw-r--r-- | doc/dependency_resolution/decision_making.docbook | 65 | ||||
| -rw-r--r-- | doc/dependency_resolution/package_modeling.docbook | 93 | ||||
| -rw-r--r-- | doc/dependency_resolution/task_scheduling.docbook | 36 | ||||
| -rw-r--r-- | doc/portage.docbook | 5 |
5 files changed, 205 insertions, 0 deletions
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 @@ +<part id='dependency-resolution'> +<title>Dependency Resolution</title> +&dependency_resolution_package_modeling; +&dependency_resolution_decision_making; +&dependency_resolution_task_scheduling; +</part> 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 @@ +<chapter id='dependency-resolution-decision-making'> +<title>Decision Making</title> +<sect1 id='dependency-resolution-decision-making-dependency-expression-evaluation'> + <title>Dependency Expression Evaluation</title> + <para> + 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. + </para> +</sect1> +<sect1 id='dependency-resolution-decision-making-look-ahead'> + <title>Look-Ahead</title> + <para> + 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: + <itemizedlist> + <listitem> + installed + </listitem> + <listitem> + selected (for installation) + </listitem> + <listitem> + not selected (for installation) + </listitem> + </itemizedlist> + </para> + <para> + 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. + </para> + <sect2 id='dependency-resolution-decision-making-look-ahead-constraint-propagation'> + <title>Constraint Propagation</title> + <para> + 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. + </para> + </sect2> + <sect2 id='dependency-resolution-decision-making-look-ahead-expanded-search-space'> + <title>Expanded Search Space</title> + <para> + 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. + </para> + </sect2> +</sect1> +</chapter> 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 @@ +<chapter id='dependency-resolution-package-modeling'> +<title>Package Modeling</title> + +<sect1 id='dependency-resolution-package-modeling-constraint-satisfaction'> + <title>Constraint Satisfaction</title> + <sect2 id='dedependency-resolution-package-modeling-constraint-satisfaction-constraint-types'> + <title>Constraint Types</title> + <para> + Dependency resolution involves satisfaction of + many constraints: + <itemizedlist> + <listitem> + Persistent configuration parameters, like those that come from + make.profile, make.conf, and the /etc/portage directory. + </listitem> + <listitem> + Current command parameters, which may include options, atoms, or sets. + </listitem> + <listitem> + <link linkend='dependency-resolution-package-modeling-constraint-satisfaction-package-dependencies'> + Package Dependencies</link> + </listitem> + </itemizedlist> + </para> + </sect2> + + <sect2 id='dependency-resolution-package-modeling-constraint-satisfaction-package-dependencies'> + <title>Package Dependencies</title> + <para> + Common types of package dependencies: + <itemizedlist> + <listitem> + Files required for building or installing. Downloads may + be necessary to satisfy these. + </listitem> + <listitem> + Other packages required to be installed for + buildtime or runtime. + </listitem> + <listitem> + Blockers that prevent conflicting packages from being installed + simultaneously. + </listitem> + </itemizedlist> + </para> + </sect2> +</sect1> + +<sect1 id='dependency-resolution-package-modeling-conflicts'> + <title>Conflicts</title> + <sect2 id='dependency-resolution-package-modeling-blocker-conflicts'> + <title>Blocker Conflicts</title> + <para> + 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. + </para> + </sect2> + <sect2 id='dependency-resolution-package-modeling-slot-conflicts'> + <title>Slot Conflicts</title> + <para> + 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. + </para> + </sect2> + <sect2 id='dependency-resolution-package-modeling-indirect-conflicts'> + <title>Indirect Conflicts</title> + <para> + 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. + </para> + </sect2> +</sect1> + +<sect1 id='dependency-resolution-package-modeling-dependency-neglection'> + <title>Dependency Neglection</title> + <para> + In order to significantly reduce the resources consumed by + the modeling process, the dependencies of + installed packages may be neglected. + </para> + <para> + 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. + </para> +</sect1> + +</chapter> 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 @@ +<chapter id='dependency-resolution-task-scheduling'> +<title>Task Scheduling</title> +<sect1 id='dependency-resolution-task-scheduling-dependencies'> + <title>Task Dependencies</title> + <para> + 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. + </para> +</sect1> +<sect1 id='dependency-resolution-task-scheduling-conflict-avoidance'> + <title>Conflict Avoidance</title> + <para> + In some cases it is possible to adjust package installation order + to avoid having two conflicting packages installed simultaneously. + </para> + <para> + TODO: Automatically uninstall packages when necessary to avoid conflicts. + </para> +</sect1> +<sect1 id='dependency-resolution-task-scheduling-circular-dependencies'> + <title>Circular Dependencies</title> + <para> + TODO: Automatically solve circular dependencies by temporarily disabling + conditional dependencies and then rebuilding packages with the conditional + dependencies enabled. + </para> +</sect1> +<sect1 id='dependency-resolution-task-scheduling-parallel'> + <title>Parallel Scheduling</title> + <para> + TODO: Spawn an appropriate number of tasks in parallel when desired. + </para> +</sect1> +</chapter> 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 @@ <!ENTITY project "portage"> + <!ENTITY dependency_resolution SYSTEM "dependency_resolution.docbook"> + <!ENTITY dependency_resolution_package_modeling SYSTEM "dependency_resolution/package_modeling.docbook"> + <!ENTITY dependency_resolution_decision_making SYSTEM "dependency_resolution/decision_making.docbook"> + <!ENTITY dependency_resolution_task_scheduling SYSTEM "dependency_resolution/task_scheduling.docbook"> <!ENTITY package SYSTEM "package.docbook"> <!ENTITY package_ebuild SYSTEM "package/ebuild.docbook"> <!ENTITY package_ebuild_phases SYSTEM "package/ebuild/phases.docbook"> @@ -34,6 +38,7 @@ </bookinfo> &config; +&dependency_resolution; &package; &qa; |