I’ve written “Part II. Dependency Resolution” for the sys-apps/portage documentation (installed with USE=doc enabled). The “Decision Making” chapter is posted here. There are also two more small chapters about package modeling and task scheduling.
Portage Dependency Resolution – Decision Making
Dependency Expression Evaluation
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.
Look-Ahead
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:
- installed
- selected (for installation)
- not selected (for installation)
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.
Constraint Propagation
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.
Expanded Search Space
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.