[Repoze-checkins] r597 - playground/trunk/chris/solver
Chris McDonough
chrism at agendaless.com
Mon Dec 3 18:13:35 UTC 2007
Author: Chris McDonough <chrism at agendaless.com>
Date: Mon Dec 3 18:13:34 2007
New Revision: 597
Log:
Get halfway towards being able to come up with a constraint set.
Modified:
playground/trunk/chris/solver/solve.py
playground/trunk/chris/solver/solver.txt
Modified: playground/trunk/chris/solver/solve.py
==============================================================================
--- playground/trunk/chris/solver/solve.py (original)
+++ playground/trunk/chris/solver/solve.py Mon Dec 3 18:13:34 2007
@@ -6,33 +6,33 @@
from constraint import Problem
def make_dummy_index():
- p = Requirement.parse
+ r = Requirement.parse
def d(name, version):
return Distribution(project_name=name, version=version)
index = {}
index['a'] = {
- d('a', '1.0') : ( p('b>=1.0'), p('c>=1.0'), p('d>=2.0'), ),
+ d('a', '1.0') : ( r('b>=1.0'), r('c>=1.0'), r('d>=2.0'), ),
}
index['b'] = {
- d('b', '1.1') : ( p('d>=2.0'), ),
- d('b', '1.2') : ( p('d==2.1'), ),
+ d('b', '1.1') : ( r('d>=2.0'), ),
+ d('b', '1.2') : ( r('d==2.1'), ),
}
index['c'] = {
- d('c', '1.0') : ( p('d==2.0'), ),
- d('c', '1.1') : ( p('d>=2.0'), ),
+ d('c', '1.0') : ( r('d==2.0'), ),
+ d('c', '1.1') : ( r('d>=2.0'), ),
d('c', '1.2') : ( ),
}
index['d'] = {
d('d', '2.0') : ( ),
- d('d', '2.1') : ( p('e>=1.0'), ),
+ d('d', '2.1') : ( r('e>=1.0'), ),
}
index['e'] = {
- d('e', '2.0') : ( p('f==1.0'), ),
+ d('e', '2.0') : ( r('f==1.0'), ),
}
index['g'] = {
- d('g', '1.0'): ( p('c==1.0'), ),
+ d('g', '1.0'): ( r('c==1.0'), ),
}
return index
@@ -40,6 +40,9 @@
class NotFound:
pass
+class NoDependencies:
+ project_name = None
+
def random_solution(solutions):
return solutions[0]
@@ -55,7 +58,39 @@
import sys
sys.stderr.write('WARNING: %s\n' % msg)
+ def distributions(self, reqt):
+ """
+ Return all the distributions in the index matching reqt.
+ """
+ project_name = reqt.project_name
+ distributions = self.index.get(project_name, [])
+ found = []
+ for distribution in distributions:
+ if distribution in reqt:
+ found.append(distribution.clone())
+ return found
+
+ def requirements(self, distribution):
+ """
+ Return all the requirements of the distribution.
+ """
+ return self.index[distribution.project_name][distribution]
+
def make_graph(self, reqt):
+ """
+ Make a graph based on our index data in the form:
+
+ reqt "a"
+ / \
+ dist a1 dist a2
+ / \
+ reqt "b==1" reqt "b==2"
+ | |
+ dist b1 dist b2
+
+ Leaf nodes in the graph are either a distribution with no
+ requirements or a NotFound node.
+ """
graph = {}
stack = [reqt]
while stack:
@@ -71,9 +106,17 @@
stack.extend(requirements)
return graph
- def paths(self, node, path=None):
+ def paths(self, node=None, path=None):
+ """
+ Return a list of lists, where each inner list represents a
+ path through the graph ending in a node that has no
+ dependencies (or a NotFound node). The entry in the inner
+ list is a (reqt, distribution) tuple.
+ """
if path is None:
path = []
+ if node is None:
+ node = self.reqt
path = path + [node]
children = self.graph.get(node)
if not children:
@@ -86,50 +129,22 @@
paths.append(newpath)
return paths
- def path_sets(self):
- # collect flattened (reqt,distro) pairs into two-tuples and
- # group paths by their first edge
- sets = {}
- paths = self.paths(self.reqt)
- any = []
+ def candidates(self):
+ """
+ Return { distribution_a: [ path1, path2, ...] }
+ """
+ candidates = {}
+ warnings = {}
+ paths = self.paths()
+
for path in paths:
unflattened = unflatten(path)
- if len(unflattened) == 1:
- # this path has no dependencies, so it's good for
- # any
- any.append(unflattened)
- else:
- reqt1 = unflattened[0][0]
- reqt2 = unflattened[1][0]
- key = (reqt1.project_name, reqt2.project_name)
- set = sets.setdefault(key, [])
- set.append(unflattened)
-
- for path in sets.values():
- set.extend(any)
- return sets
+ first, rest = unflattened[0], unflattened[1:]
+ reqt, dist = first
+ pathlist = candidates.setdefault(dist, [])
+ pathlist.append(rest)
- def distributions(self, reqt):
- project_name = reqt.project_name
- distributions = self.index.get(project_name, [])
- found = []
- for distribution in distributions:
- if distribution in reqt:
- found.append(distribution.clone())
- return found
-
- def requirements(self, distribution):
- return self.index[distribution.project_name][distribution]
-
- def candidates(self):
- path_sets = self.path_sets()
- for key in path_sets:
- for path in path_sets[key][:]:
- if path[-1][1] == NotFound:
- self.warn("Req %r could not be met by this index in "
- "path %r" % (path[-1][0], path))
- path_sets[key].remove(path)
- return path_sets
+ return candidates
def unflatten(L):
# unflatten an even-length list L(1,2,3,4) into L((1,2),(3,4))
@@ -140,21 +155,13 @@
def solve(contexts, chooser):
problem = Problem()
for context in contexts:
- solveable = False
- for key, paths in context.candidates().items():
- if paths:
- solveable = True
- problem.addVariable(key, paths)
- if not solveable:
- raise ValueError(
- 'Reqt %r not solved due to %r' % (context.reqt, key))
- solutions = problem.getSolutions()
- solution = chooser(solutions)
- return solution
+ paths = context.candidates()
+ # do something clever with each path
+ pprint(paths)
if __name__ == '__main__':
import sys
reqts = [ Requirement.parse(reqt_str) for reqt_str in sys.argv[1:] ]
index = make_dummy_index()
- contexts = [ RequirementContext(reqt, index) for reqt in reqts ]
- pprint(solve(contexts, random_solution))
+ contexts = [ RequirementContext(reqt, index, False) for reqt in reqts ]
+ solve(contexts, random_solution)
Modified: playground/trunk/chris/solver/solver.txt
==============================================================================
--- playground/trunk/chris/solver/solver.txt (original)
+++ playground/trunk/chris/solver/solver.txt Mon Dec 3 18:13:34 2007
@@ -96,29 +96,29 @@
from pkg_resources import Requirement
from pkg_resources import Distribution
- p = Requirement.parse
+ r = Requirement.parse
def d(name, version):
return Distribution(project_name=name, version=version)
index = {}
index['a'] = {
- d('a', '1.0') : ( p('b>=1.0'), p('c>=1.0'), p('d>=2.0'), ),
+ d('a', '1.0') : ( r('b>=1.0'), r('c>=1.0'), r('d>=2.0'), ),
}
index['b'] = {
- d('b', '1.1') : ( p('d>=2.0'), ),
- d('b', '1.2') : ( p('d==2.1'), ),
+ d('b', '1.1') : ( r('d>=2.0'), ),
+ d('b', '1.2') : ( r('d==2.1'), ),
}
index['c'] = {
- d('c', '1.0') : ( p('d==2.0'), ),
- d('c', '1.1') : ( p('d>=2.0'), ),
+ d('c', '1.0') : ( r('d==2.0'), ),
+ d('c', '1.1') : ( r('d>=2.0'), ),
}
index['d'] = {
d('d', '2.0') : ( ),
- d('d', '2.1') : ( p('e>=1.0'), ),
+ d('d', '2.1') : ( r('e>=1.0'), ),
}
index['e'] = {
- d('e', '2.0') : ( p('f==1.0'), ),
+ d('e', '2.0') : ( r('f==1.0'), ),
}
Given an index, we can create a matrix of "all possible
@@ -133,8 +133,8 @@
index = {}
index['a'] = {
- d('a', '1') : ( p('b==1'), ),
- d('a', '2') : ( p('b==2'), ),
+ d('a', '1') : ( r('b==1'), ),
+ d('a', '2') : ( r('b==2'), ),
}
index['b'] = {
d('b', '1') : ( ),
@@ -160,7 +160,7 @@
index = {}
index['a'] = {
- d('a', '2') : ( p('b==2'), ),
+ d('a', '2') : ( r('b==2'), ),
}
index['b'] = {
d('b', '2') : ( ),
@@ -204,22 +204,11 @@
[ dist a1, dist b1 ]
[ dist a2, dist b2 ]
- Because both of these paths begin with the same two package names
- ((a,b)), they are grouped into a path set. As a result, we will
- only have one path set to consult. The path set is::
-
- [ (dist a1, dist b1), (dist a2, dist b2) ]
-
- We will use each path in a path set as input to a constraint
- domain to see which path can be solved by our index. You may
- believe that all of them can be solved because we took information
- *from* our index to construct them, and that's largely true of in
- the common case. But it's possible that the has a distribution
- with a dependency on something that doesn't actually live in the
- index, so we can seed the graph with "not found" values to
- represent this case. For instance, if b2 depended on package c2
- that didn't exist in the index, the graph would be constructed
- as::
+ It's possible that the solution has a distribution with a
+ dependency on something that doesn't actually live in the index,
+ so we seed the graph with "not found" values to represent this
+ case. For instance, if b2 depended on package c2 that didn't
+ exist in the index, the graph would be constructed as::
reqt "a"
/ \
@@ -233,10 +222,11 @@
|
NotFound
- The single path set for this graph can be represented using the
- following list::
+ For the above graph, the paths are returned
+ as::
- [ (dist a1, dist b1), (dist a2, dist b2, NotFound) ]
+ [ dist a1, dist b1 ]
+ [ dist a2, dist b2, NotFound]
We inject NotFound sentinel values rather than erroring out during
graph construction because it's entirely possible that a different
@@ -246,6 +236,42 @@
it turns out that no solutions can be found, or if the user has a
"warning mode" turned on.
+ Once we've found all possible paths to leaf nodes through the
+ graph rooted at a single requirement, we want to build a mapping
+ in the form::
+
+ { distribution_a: [ path1, path2, ...] }
+
+ Where 'path1' and 'path2' (etc) are lists in the form::
+
+ [ (reqt_r1, distribution_r1), (reqt_r2, distribution2_r2), ... ]
+
+ 'distribution_r1' and 'distribution_r2' etc. represent the
+ requirement dependencies of 'distribution_a'. 'reqt_r1' and
+ 'reqt_r2' represent the requirement in 'distribution_a' that
+ specified the associated distribution. The last distribution in
+ the list will either be a distribution without any dependencies or
+ a NotFound node.
+
+ XXX from here on in is misinformation.
+
+ Because both of these paths begin with the same two package names
+ ((a,b)), they are grouped into a path set. As a result, we will
+ only have one path set to consult. The path set is::
+
+ [ (dist a1, dist b1), (dist a2, dist b2) ]
+
+ We will use each path in a path set as input to a constraint
+ domain to see which path can be solved by our index. You may
+ believe that all of them can be solved because we took information
+ *from* our index to construct them, and that's largely true of in
+ the common case.
+
+ The single path set for this graph can be represented using the
+ following list::
+
+ [ (dist a1, dist b1), (dist a2, dist b2, NotFound) ]
+
In terms of constraint solution programming, you can consider each
package name a "variable". The variable's "domain" is the list of
versions of the package contained in the index. Using the syntax
@@ -308,8 +334,6 @@
At the end of this tortured example, "good" will be [[a 2, b 2]].
We've filtered out the "bad" path (a 1, b1).
- XXX from here on in is misinformation.
-
from pkg_resources import Requirement
from pkg_resources import parse_version
from constraint import Problem
More information about the Repoze-checkins
mailing list