Add a new part for "Dependency Resolution".

svn path=/main/trunk/; revision=9926

5 files changed, 205 insertions, 0 deletions

diff --git a/doc/dependency_resolution.docbook b/doc/dependency_resolution.docbook
new file mode 100644
index 00000000..7dd18e84
--- /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 00000000..5bcf8438
--- /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 00000000..84d01a9f
--- /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 00000000..8979a9f6
--- /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 5417bb73..d158c1a2 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;