From owner-freebsd-pkg@FreeBSD.ORG Thu Jul 25 15:02:16 2013 Return-Path: Delivered-To: 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 0F09EB6A; Thu, 25 Jul 2013 15:02:16 +0000 (UTC) (envelope-from vsevolod@FreeBSD.org) Received: from n.highsecure.ru (unknown [IPv6:2001:41d0:8:dd9a::99]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.freebsd.org (Postfix) with ESMTPS id 9D3372D4F; Thu, 25 Jul 2013 15:02:12 +0000 (UTC) Received: from medway.cl.cam.ac.uk (medway.cl.cam.ac.uk [128.232.64.24]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: vsevolod@highsecure.ru) by n.highsecure.ru (Postfix) with ESMTPSA id 46ACD221279; Thu, 25 Jul 2013 16:01:12 +0100 (BST) Message-ID: <51F13DF0.5040209@FreeBSD.org> Date: Thu, 25 Jul 2013 16:02:08 +0100 From: Vsevolod Stakhov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130623 Thunderbird/17.0.7 MIME-Version: 1.0 To: Baptiste Daroussin Subject: The new architecture of pkgng solver Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: pkg@FreeBSD.org 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:02:16 -0000 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)) -- Vsevolod Stakhov