From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from lists.gentoo.org ([140.105.134.102] helo=robin.gentoo.org) by nuthatch.gentoo.org with esmtp (Exim 4.54) id 1ErHfc-00021K-9d for garchives@archives.gentoo.org; Tue, 27 Dec 2005 16:27:28 +0000 Received: from robin.gentoo.org (localhost [127.0.0.1]) by robin.gentoo.org (8.13.5/8.13.5) with SMTP id jBRGOfRv019223; Tue, 27 Dec 2005 16:24:41 GMT Received: from smtp.gentoo.org (smtp.gentoo.org [134.68.220.30]) by robin.gentoo.org (8.13.5/8.13.5) with ESMTP id jBRGLNMp013766 for ; Tue, 27 Dec 2005 16:21:27 GMT Received: from zb101200.ppp.dion.ne.jp ([219.125.101.200] helo=opteron246.suzuki-stubbs.home) by smtp.gentoo.org with esmtpa (Exim 4.54) id 1ErHYA-00065O-7Q for gentoo-dev@lists.gentoo.org; Tue, 27 Dec 2005 16:19:46 +0000 Received: by opteron246.suzuki-stubbs.home (Postfix, from userid 1000) id C58D6201B78; Wed, 28 Dec 2005 01:20:50 +0900 (JST) From: Jason Stubbs To: gentoo-dev@lists.gentoo.org Subject: Re: [gentoo-dev] Multiple Repo Support Date: Wed, 28 Dec 2005 01:20:50 +0900 User-Agent: KMail/1.9 References: <43A235AD.6030604@leetworks.com> <20051226202833.4c5fe9f9@snowdrop.home> <200512271648.55694.pauldv@gentoo.org> In-Reply-To: <200512271648.55694.pauldv@gentoo.org> Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-dev@gentoo.org Reply-to: gentoo-dev@lists.gentoo.org MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200512280120.50600.jstubbs@gentoo.org> X-Archives-Salt: 5bf420ad-c639-43a7-a2bc-228ae34b64d5 X-Archives-Hash: c337c3a934c99adc2d4ecf4c7a1363b3 > On Monday 26 December 2005 21:28, Ciaran McCreesh wrote: > > On Mon, 26 Dec 2005 21:09:31 +0100 Carsten Lohrke > > Well, any library that changes ABI should use a different SLOT for each > > revision. So SLOT depends should be able to replace the need for = and > > ~ and < and <= dependencies entirely. Which is a good thing, since > > those atoms make dependency resolution a general-case unsolvable > > problem. There's a lot of "should"s that are "aren't"s in there, but in principle that is a very elegant idea. On Wednesday 28 December 2005 00:48, Paul de Vrieze wrote: > Well, it shouldn't be unsolvable. Choosing can be done with the following > process: > > - Get the list of packages with the requested name. > - Sort the list from the newest version, to the oldest. > - Iterate over the packages: > - Apply all restrictions on the package (including exclusions). If the > package satisfies all, test it's dependencies recursively. ^^^ This step fails. When the set of restrictions cannot be resolved, you need to backtrack and try a lesser version of a previous package hence the set of "all restrictions" is constantly in flux. > - If all dependencies match, this package matches the dependency. > Continue with the next depend atom. > - If no match, iterate the next package. If backtracking was all there was to it, it could be done very quickly of course. However, it's essentially a brute force method; I'm not very good with O notation but I think it's O(n^n). I've got an algorithm in my head that'll do it but it goes into an infinite loop in the cases that Carsten mentioned. That's why things are taking so long. I should really write it down... -- Jason Stubbs -- gentoo-dev@gentoo.org mailing list