{"id":4,"date":"2008-04-18T21:31:13","date_gmt":"2008-04-19T04:31:13","guid":{"rendered":""},"modified":"2011-03-30T17:01:14","modified_gmt":"2011-03-31T00:01:14","slug":"portage_dependency_resolution_decision_m","status":"publish","type":"post","link":"https:\/\/blogs.gentoo.org\/zmedico\/2008\/04\/18\/portage_dependency_resolution_decision_m\/","title":{"rendered":"Portage Dependency Resolution &#8211; Decision Making"},"content":{"rendered":"<p>I&#8217;ve written &#8220;Part II. Dependency Resolution&#8221; for the sys-apps\/portage documentation (installed with USE=doc enabled). The &#8220;Decision Making&#8221; chapter is posted here. There are also two more small chapters about <a href=\"http:\/\/dev.gentoo.org\/~zmedico\/portage\/doc\/portage.html#dependency-resolution\">package modeling and task scheduling<\/a>.<\/p>\n<p><strong>Portage Dependency Resolution &#8211; Decision Making<\/strong><\/p>\n<p><strong>Dependency Expression Evaluation<\/strong><\/p>\n<p>In terms of boolean logic, a dependency expression can<br \/>\nbe expressed in disjunctive normal form (DNF), which is a<br \/>\ndisjunction of conjunctive clauses. Each conjunctive clause<br \/>\nrepresents one possible alternative combination of dependency<br \/>\natoms capable of satisfying the dependency expression.<\/p>\n<p><strong>Look-Ahead<\/strong><\/p>\n<p>When there are multiple combinations to choose from, a<br \/>\nlook-ahead mechanism will choose an optimal combination to<br \/>\nsatisfy constraints and minimize cost. The following package<br \/>\nstates influence the cost calculation for a given combination:<\/p>\n<ul>\n<li>installed<\/li>\n<li>selected (for installation)<\/li>\n<li>not selected (for installation)<\/li>\n<\/ul>\n<p>In cost calculations, virtual packages by themselves are<br \/>\nconsidered to cost nothing since they do not directly install<br \/>\nanything. It is the dependencies of a virtual package that<br \/>\ncontribute to it&#8217;s cost.<\/p>\n<p><code><strong>Constraint Propagation<\/strong><\/p>\n<p>Combinations that include packages from the \"installed\" or<br \/>\n\"selected\" categories are less costly than those that include<br \/>\npackages from the \"not selected\" category. When a package<br \/>\nis chosen for installation, it transitions to the \"selected\"<br \/>\nstate. This state change propagates to the cost calculations of<br \/>\nlater decisions, influencing later decisions to be consistent<br \/>\nwith earlier decisions. This feedback mechanism serves to<br \/>\npropagate constraints and can influence the modeling process<br \/>\nto converge on a more optimal final state.<\/p>\n<p><strong>Expanded Search Space<\/strong><\/p>\n<p><\/code><\/p>\n<p><code>When evaluating virtual atoms, an expanded search space is<br \/>\nconsidered which recursively traverses the dependencies of<br \/>\nvirtual packages from all slots matching a given virtual<br \/>\natom. All combinations in this expanded search space are<br \/>\nconsidered when choosing an optimal combination to satisfy<br \/>\nconstraints with minimal cost.<\/code><\/p>\n","protected":false},"excerpt":{"rendered":"<p>I&#8217;ve written &#8220;Part II. Dependency Resolution&#8221; for the sys-apps\/portage documentation (installed with USE=doc enabled). The &#8220;Decision Making&#8221; chapter is posted here. There are also two more small chapters about package modeling and task scheduling. Portage Dependency Resolution &#8211; Decision Making Dependency Expression Evaluation In terms of boolean logic, a dependency expression can be expressed in &hellip; <a href=\"https:\/\/blogs.gentoo.org\/zmedico\/2008\/04\/18\/portage_dependency_resolution_decision_m\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Portage Dependency Resolution &#8211; Decision Making<\/span><\/a><\/p>\n","protected":false},"author":65,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[3],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/blogs.gentoo.org\/zmedico\/wp-json\/wp\/v2\/posts\/4"}],"collection":[{"href":"https:\/\/blogs.gentoo.org\/zmedico\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.gentoo.org\/zmedico\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.gentoo.org\/zmedico\/wp-json\/wp\/v2\/users\/65"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.gentoo.org\/zmedico\/wp-json\/wp\/v2\/comments?post=4"}],"version-history":[{"count":2,"href":"https:\/\/blogs.gentoo.org\/zmedico\/wp-json\/wp\/v2\/posts\/4\/revisions"}],"predecessor-version":[{"id":73,"href":"https:\/\/blogs.gentoo.org\/zmedico\/wp-json\/wp\/v2\/posts\/4\/revisions\/73"}],"wp:attachment":[{"href":"https:\/\/blogs.gentoo.org\/zmedico\/wp-json\/wp\/v2\/media?parent=4"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.gentoo.org\/zmedico\/wp-json\/wp\/v2\/categories?post=4"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.gentoo.org\/zmedico\/wp-json\/wp\/v2\/tags?post=4"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}