From owner-freebsd-pkg@FreeBSD.ORG Thu Jul 25 15:33:49 2013 Return-Path: Delivered-To: freebsd-pkg@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTP id 967EFCC1 for ; Thu, 25 Jul 2013 15:33:49 +0000 (UTC) (envelope-from matthew@freebsd.org) Received: from smtp.infracaninophile.co.uk (smtp6.infracaninophile.co.uk [IPv6:2001:8b0:151:1:3cd3:cd67:fafa:3d78]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.freebsd.org (Postfix) with ESMTPS id E1F6D2F82 for ; Thu, 25 Jul 2013 15:33:48 +0000 (UTC) Received: from rufus.webfusion.com (mail.heartinternet.co.uk [79.170.40.31]) (authenticated bits=0) by smtp.infracaninophile.co.uk (8.14.7/8.14.7) with ESMTP id r6PFXg7O083974 (version=TLSv1/SSLv3 cipher=DHE-RSA-CAMELLIA256-SHA bits=256 verify=NO) for ; Thu, 25 Jul 2013 16:33:43 +0100 (BST) (envelope-from matthew@freebsd.org) DKIM-Filter: OpenDKIM Filter v2.8.3 smtp.infracaninophile.co.uk r6PFXg7O083974 Authentication-Results: smtp.infracaninophile.co.uk/r6PFXg7O083974; dkim=none reason="no signature"; dkim-adsp=none (unprotected policy) X-Authentication-Warning: lucid-nonsense.infracaninophile.co.uk: Host mail.heartinternet.co.uk [79.170.40.31] claimed to be rufus.webfusion.com Message-ID: <51F14556.9040605@freebsd.org> Date: Thu, 25 Jul 2013 16:33:42 +0100 From: Matthew Seaman User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:17.0) Gecko/20130715 Thunderbird/17.0.7 MIME-Version: 1.0 To: freebsd-pkg@freebsd.org Subject: Re: The new architecture of pkgng solver References: <51F13DF0.5040209@FreeBSD.org> In-Reply-To: <51F13DF0.5040209@FreeBSD.org> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Virus-Scanned: clamav-milter 0.97.8 at lucid-nonsense.infracaninophile.co.uk X-Virus-Status: Clean X-Spam-Status: No, score=-1.6 required=5.0 tests=AWL,BAYES_00, RCVD_IN_DNSWL_NONE,SPF_SOFTFAIL autolearn=no version=3.3.2 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on lucid-nonsense.infracaninophile.co.uk X-BeenThere: freebsd-pkg@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Binary package management and package tools discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 25 Jul 2013 15:33:49 -0000 On 25/07/2013 16:02, Vsevolod Stakhov wrote: > Hello, > > At the moment I plan to do the following: > > 1) > - introduce 'the universe' structure, which contains all deps (for > install/fetch/upgrade), rdeps (for deinstall), conflicts and their rdeps > (for install); > - add request list - a list of packages to install, remove or upgrade > - write universal solver code that takes universe and a request list and > then either produces cudf output or uses an internal SAT solver; > - results are written into two lists: packages to add/upgrade and > packages to remove (e.g. due to conflicts). > > 2) > Plan 'provides' logic that means that a dependency can be provided by a > number of (potentially conflicting) packages. It is implemented as pkg > field but it is not used by solver. > > 3) > Internal solver should work based on the following procedure: > > 1. Iterate over the universe and create a boolean problem: > * A depends on B that is provided by B1, B2 or B3 is transferred to a > set of rules: (!A | B1 | B2 | B3) > * A conflicts between B1, B2 and B3 is transferred to the following: > (!B1 | !B2) & (!B1 | !B2) & (!B1 | !B3) > or in case of conflict to a provided feature if A conflicts with B > provided by B1, B2 or B3: > (!A | !B1) & (!A | !B2) & (!A | !B3) > > 2. Explicit requests for install or remove are written as: > (A) - install A > (!A) - remove A > > 3. For all explicit request (e.g. install A) set the value of these > requests either to true (for packages to install) or false (for packages > to deinstall). > > 4. Iterate over the record and set all unary rules to true, for example > (A) & (!A | B1 | B2 | B3) & (!A | !C) which means that A depends on (B1 > or B2 or B3) and conflicts with C. After this step we set A to TRUE as > it is unary rule. > > 5. For all other rules perform propagation procedure, substitute > variables to make a rule as true. For example in the previous example: > * (A) & (!A | B1 | B2 | B3) & (!A | !C) - A is TRUE; > * (!A | !C) - !C should be TRUE as !A is FALSE and C thus is FALSE; > * (!A | B1 | B2 | B3) - !A is FALSE, so one of B1/B2/B3 should be TRUE. > > 6. For the last step there is a choice, what to select. I'd suggest to > follow this logic: > * try installed packages first; > * do not install any packages that are not needed (e.g. set all > available alternatives to FALSE); > > 7. Check the overall expression and if it is FALSE try to reassign the > last assigned variable from the previous step. > > 8. 6 and 7 till the expression is either TRUE or there is no way to > reassign variables (unsolvable solution). > > With this logic we have only a single problematic point - how to convert > the packages universe and request to a SAT problem. On the other hand, > with this architecture we have a *universal* solution for all procedures > (install/remove/upgrade). Moreover, it is compatible with CUDF format, > therefore I suggest to rework the current jobs architecture to this one. > > I'll do it if there are no objections. > > (And, well, we need to think eventually what to do with share libraries > dependencies and flexible dependencies, e.g. Depends: libsomething (>1.4)) > In (1) you say: * A depends on B that is provided by B1, B2 or B3 At the moment, strictly the only data we have about 'B that is provided by B1, B2 or B3' *is* the shlib provides/requires data. All the dependency relationships between pkgs other than that are based on 'package X-N.NN.NN requires package Y-M.MM.MM' where Y-M.MM.MM was the version of the package for Y on the system at the point when package X was built. ie. there are no alternatives visible for the solver to work with. shlibs provides/requires is handy because it can be automatically generated. There are a few other similar sorts of relationships that could be extracted automatically -- for instance dependencies between perl modules -- and we can generate 'conflicts' data based on packages wanting to install files to the same place. But I think a lot of this is going to need some sort of manually specified 'PROVIDES/REQUIRES/CONFLICTS' data within each port. Cheers, Matthew