doc/dependency_resolution/decision_making.docbook

   1 <chapter id='dependency-resolution-decision-making'>
   2 <title>Decision Making</title>
   3 <sect1 id='dependency-resolution-decision-making-dependency-expression-evaluation'>
   4         <title>Dependency Expression Evaluation</title>
   5         <para>
   6         In terms of boolean logic, a dependency expression can
   7         be expressed in disjunctive normal form (DNF), which is
   8         a disjunction of conjunctive clauses. Each conjunctive clause
   9         represents one possible alternative combination of dependency
  10         atoms capable of satisfying the dependency expression.
  11         </para>
  12         <sect2 id='dependency-resolution-decision-making-dependency-expression-evaluation-delayed-disjunction'>
  13                 <title>Delayed Evaluation of Disjunctive Dependency Choices</title>
  14                 <para>
  15                 Disjunctive dependencies, of which virtuals are a special case,
  16                 can be satsified by multiple choices of dependency atoms. These
  17                 choices are delayed until as late as possible in the dependency
  18                 calculation, after packages have been selected to satisfy
  19                 as many non-disjunctive dependencies as possible. As a consequence
  20                 of this delayed evaluation, there is maximal information available
  21                 which makes it possible to optimize choices such that the total
  22                 number of packages required to satisfy all dependencies is minimized.
  23                 </para>
  24         </sect2>
  25 </sect1>
  26 <sect1 id='dependency-resolution-decision-making-look-ahead'>
  27         <title>Look-Ahead</title>
  28         <para>
  29         When there are multiple combinations to choose from,
  30         a look-ahead mechanism will choose an optimal combination
  31         to satisfy constraints and minimize cost. The
  32         following package states influence the cost calculation for
  33         a given combination:
  34         </para>
  35         <itemizedlist>
  36         <listitem>
  37                 <para>installed</para>
  38         </listitem>
  39         <listitem>
  40                 <para>selected (for installation)</para>
  41         </listitem>
  42         <listitem>
  43                 <para>not selected (for installation)</para>
  44         </listitem>
  45         </itemizedlist>
  46         <para>
  47         In cost calculations, virtual packages by themselves are
  48         considered to cost nothing since they do not directly install anything.
  49         It is the dependencies of a virtual package that contribute to it's cost.
  50         </para>
  51         <sect2 id='dependency-resolution-decision-making-look-ahead-constraint-propagation'>
  52                 <title>Constraint Propagation</title>
  53                 <para>
  54                 Combinations that include packages from the "installed" or
  55                 "selected" categories are less costly than those that
  56                 include packages from the "not selected" category.
  57                 When a package is chosen for installation, it transitions to the
  58                 "selected" state. This state change propagates
  59                 to the cost calculations of later decisions,
  60                 influencing later decisions to be consistent with earlier decisions.
  61                 This feedback mechanism serves to propagate constraints and can
  62                 influence the modeling process to
  63                 converge on a more optimal final state.
  64                 </para>
  65         </sect2>
  66         <sect2 id='dependency-resolution-decision-making-look-ahead-expanded-search-space'>
  67                 <title>Expanded Search Space</title>
  68                 <para>
  69                 When evaluating virtual atoms, an expanded search space is
  70                 considered which recursively traverses
  71                 the dependencies of virtual packages
  72                 from all slots matching a given virtual atom. All combinations in
  73                 this expanded search space are considered when choosing an optimal
  74                 combination to satisfy constraints with minimal cost.
  75                 </para>
  76         </sect2>
  77 </sect1>
  78 </chapter>