[gentoo-commits] portage r9926 - in main/trunk/doc: . dependency_resolution

[Zac Medico (zmedico)]

Author: zmedico
Date: 2008-04-18 21:30:10 +0000 (Fri, 18 Apr 2008)
New Revision: 9926

Added:
   main/trunk/doc/dependency_resolution.docbook
   main/trunk/doc/dependency_resolution/
   main/trunk/doc/dependency_resolution/decision_making.docbook
   main/trunk/doc/dependency_resolution/package_modeling.docbook
   main/trunk/doc/dependency_resolution/task_scheduling.docbook
Modified:
   main/trunk/doc/portage.docbook
Log:
Add a new part for "Dependency Resolution".


Added: main/trunk/doc/dependency_resolution/decision_making.docbook
===================================================================
--- main/trunk/doc/dependency_resolution/decision_making.docbook	                        (rev 0)
+++ main/trunk/doc/dependency_resolution/decision_making.docbook	2008-04-18 21:30:10 UTC (rev 9926)
@@ -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>

Added: main/trunk/doc/dependency_resolution/package_modeling.docbook
===================================================================
--- main/trunk/doc/dependency_resolution/package_modeling.docbook	                        (rev 0)
+++ main/trunk/doc/dependency_resolution/package_modeling.docbook	2008-04-18 21:30:10 UTC (rev 9926)
@@ -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>

Added: main/trunk/doc/dependency_resolution/task_scheduling.docbook
===================================================================
--- main/trunk/doc/dependency_resolution/task_scheduling.docbook	                        (rev 0)
+++ main/trunk/doc/dependency_resolution/task_scheduling.docbook	2008-04-18 21:30:10 UTC (rev 9926)
@@ -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>

Added: main/trunk/doc/dependency_resolution.docbook
===================================================================
--- main/trunk/doc/dependency_resolution.docbook	                        (rev 0)
+++ main/trunk/doc/dependency_resolution.docbook	2008-04-18 21:30:10 UTC (rev 9926)
@@ -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>

Modified: main/trunk/doc/portage.docbook
===================================================================
--- main/trunk/doc/portage.docbook	2008-04-18 04:15:07 UTC (rev 9925)
+++ main/trunk/doc/portage.docbook	2008-04-18 21:30:10 UTC (rev 9926)
@@ -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;
 

-- 
gentoo-commits@l.g.o mailing list