<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>
	Sometimes a package installation order exists such that it is
	possible to avoid having two conflicting packages installed
	simultaneously. If a currently installed package conflicts with a
	new package that is planned to be installed, it may be possible to
	solve the conflict by replacing the installed package with a
	different package that occupies the same slot.
	</para>
	<para>
	In order to avoid a conflict, a package may need to be uninstalled
	rather than replaced. The following constraints
	protect inappropriate packages from being chosen for automatic
	uninstallation:
	</para>
	<itemizedlist>
	<listitem>
	<para>Installed packages that have been pulled into the current dependency
	graph will not be uninstalled. Due to
	<link linkend='dependency-resolution-package-modeling-dependency-neglection'>
	dependency neglection</link> and special properties of packages
	in the "system" set, other checks may be necessary in order
	to protect inappropriate packages from being uninstalled.</para>
	</listitem>
	<listitem>
	<para>An installed package that is matched by a dependency atom from the
	"system" set will not be uninstalled in advance since it might not
	be safe. Such a package will only be uninstalled through replacement.</para>
	</listitem>
	<listitem>
	<para>An installed package that is matched by a dependency atom from the
	"world" set will not be uninstalled if the dependency graph does not
	contain a replacement package that is matched by the same dependency
	atom.</para>
	</listitem>
	</itemizedlist>
	<para>
	In order to ensure that package files remain installed in a usable state
	whenever possible, uninstallation operations are not executed
	until after all associated conflicting packages have been installed.
	When file collisions occur between conflicting packages, the contents
	entries for those files are removed from the packages
	that are scheduled for uninstallation. This prevents
	uninstallation operations from removing overlapping files that
	have been claimed by conflicting packages.
	</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>
	The algorithm used to choose packages that will execute concurrently
	with other packages is as conservative as possible in the sense that
	a given package will not be executed if the subgraph composed of its
	direct and indirect dependencies contains any scheduled merges. By
	ensuring that the subgraph of deep dependencies is fully up to date
	in this way, potential problems are avoided which could be triggered
	by other build orders that are less optimal.
	</para>
</sect1>
</chapter>