2 from basetest
import BaseTest
6 sys
.path
.insert(0, '..')
7 from zeroinstall
.injector
import model
, arch
, qdom
8 from zeroinstall
.injector
.namespaces
import XMLNS_IFACE
10 from zeroinstall
.injector
.solver
import SATSolver
as Solver
11 from zeroinstall
.injector
import sat
14 logger
= logging
.getLogger()
17 def lookup_any(self
, digests
):
22 uri_prefix
= 'http://localhost/tests/'
25 def __init__(self
, n
):
30 def add_requires(self
, lib
, min_v
, max_v
):
31 self
.requires
.append((lib
, min_v
, max_v
))
34 def __init__(self
, name
):
38 def get_version(self
, version
):
39 if version
not in self
.versions
:
40 self
.versions
[version
] = Version(version
)
41 return self
.versions
[version
]
44 def child(parent
, name
, attrs
= None):
45 new
= qdom
.Element(XMLNS_IFACE
, name
, attrs
or {})
46 parent
.childNodes
.append(new
)
49 root
= qdom
.Element(XMLNS_IFACE
, 'interface', {'uri' : uri_prefix
+ self
.name
})
50 child(root
, 'name').content
= self
.name
51 child(root
, 'summary').content
= self
.name
54 for version
in self
.versions
.values():
57 'version': str(version
.n
),
61 attrs
['arch'] = version
.arch
62 impl
= child(root
, 'implementation', attrs
)
63 child(impl
, 'manifest-digest', {'sha1new': '1234'})
64 for lib
, min_v
, max_v
in version
.requires
:
65 req
= child(impl
, 'requires', {'interface': uri_prefix
+ lib
})
66 child(req
, 'version', {
67 'before': str(int(max_v
) + 1),
71 feed
= model
.ZeroInstallFeed(root
)
72 feed
.last_modified
= 1
81 def get_prog(self
, prog
):
82 if not prog
in self
.progs
:
83 self
.progs
[prog
] = Program(prog
)
84 return self
.progs
[prog
]
86 def get_interface(self
, uri
):
87 if uri
not in self
.interfaces
:
88 iface
= model
.Interface(uri
)
89 self
.interfaces
[uri
] = iface
90 return self
.interfaces
[uri
]
92 def get_feed(self
, url
):
93 if url
not in self
.feeds
:
94 feed
= self
.progs
[url
.rsplit('/', 1)[1]].build_feed()
95 self
.feeds
[url
] = feed
96 return self
.feeds
[url
]
98 def get_feed_imports(self
, iface
):
101 def assertSelection(expected
, repo
):
104 expected
= [tuple(e
.strip().split('-')) for e
in expected
.split(",")]
106 for line
in repo
.split('\n'):
108 if not line
: continue
110 prog
, versions
= line
.split(':')
113 prog
, prog_arch
= prog
.split()
116 for v
in versions
.split():
117 cache
.get_prog(prog
).get_version(v
).arch
= prog_arch
119 prog
, requires
= line
.split('=>')
120 prog
, version_range
= prog
.strip().split('[')
121 lib
, min_v
, max_v
= requires
.split()
122 assert version_range
.endswith(']')
123 version_range
= version_range
[:-1]
124 if ',' in version_range
:
125 min_p
, max_p
= map(int, version_range
.split(','))
126 prog_versions
= range(min_p
, max_p
+ 1)
128 prog_versions
= [int(version_range
)]
129 for prog_version
in prog_versions
:
130 cache
.get_prog(prog
).get_version(str(prog_version
)).add_requires(lib
, min_v
, max_v
)
132 root
= uri_prefix
+ expected
[0][0]
133 s
= Solver(model
.network_offline
, cache
, stores
)
134 s
.solve(root
, arch
.get_architecture('Linux', 'x86_64'))
136 if expected
[0][1] == 'FAIL':
142 for iface
, impl
in s
.selections
.iteritems():
143 actual
.append(((iface
.uri
.rsplit('/', 1)[1]), impl
.get_version()))
147 if expected
!= actual
:
148 raise Exception("Solve failed:\nExpected: %s\n Actual: %s" % (expected
, actual
))
151 class TestSAT(BaseTest
):
152 def testTrivial(self
):
153 assertSelection("prog-2", """
157 def testSimple(self
):
158 assertSelection("prog-5, liba-5", """
166 def testBestImpossible(self
):
167 assertSelection("prog-1", """
174 assertSelection("prog-1", """
175 prog: 1 2 3 4 5 6 7 8 9
176 liba: 1 2 3 4 5 6 7 8 9
177 libb: 1 2 3 4 5 6 7 8 9
178 libc: 1 2 3 4 5 6 7 8 9
179 libd: 1 2 3 4 5 6 7 8 9
181 prog[2,9] => liba 1 9
182 liba[1,9] => libb 1 9
183 libb[1,9] => libc 1 9
184 libc[1,9] => libd 1 9
185 libd[1,9] => libe 0 0
188 def testNoSolution(self
):
189 assertSelection("prog-FAIL", """
192 prog[1,3] => liba 2 3
195 def testBacktrackSimple(self
):
196 # We initially try liba-3 before learning that it
197 # is incompatible and backtracking.
198 # We learn that liba-3 doesn't work ever.
199 assertSelection("prog-1, liba-2", """
205 def testBacktrackLocal(self
):
206 # We initially try liba-3 before learning that it
207 # is incompatible and backtracking.
208 # We learn that liba-3 doesn't work with prog-1.
209 assertSelection("prog-2, liba-2", """
212 prog[1,2] => liba 1 2
215 def testLearning(self
):
216 # Prog-2 depends on libb and libz, but we can't have both
217 # at once. The learning means we don't have to explore every
218 # possible combination of liba and libb.
219 assertSelection("prog-1", """
222 libb Linux-i486: 1 2 3
223 libz Linux-x86_64: 1 2
226 liba[1,3] => libb 1 3
229 def testToplevelConflict(self
):
230 # We don't detect the conflict until we start solving, but the
231 # conflict is top-level so we abort immediately without
233 assertSelection("prog-FAIL", """
239 def testDiamondConflict(self
):
240 # prog depends on liba and libb, which depend on incompatible
242 assertSelection("prog-FAIL", """
253 def testCoverage(self
):
254 # Try to trigger some edge cases...
256 # An at_most_one clause must be analysed for causing
258 solver
= sat
.SATProblem()
259 v1
= solver
.add_variable("v1")
260 v2
= solver
.add_variable("v2")
261 v3
= solver
.add_variable("v3")
262 solver
.at_most_one([v1
, v2
])
263 solver
.add_clause([v1
, sat
.neg(v3
)])
264 solver
.add_clause([v2
, sat
.neg(v3
)])
265 solver
.add_clause([v1
, v3
])
266 solver
.run_solver(lambda: v3
)
268 def testFailState(self
):
269 # If we can't select a valid combination,
270 # try to select as many as we can.
271 s
= assertSelection("prog-FAIL", """
276 prog[1,2] => liba 1 2
277 liba[1,2] => libb 1 2
278 libb[1,2] => libc 0 0
282 for iface
, impl
in s
.selections
.iteritems():
283 if impl
is not None: impl
= impl
.get_version()
284 selected
[iface
.uri
.rsplit('/', 1)[1]] = impl
293 solver
= sat
.SATProblem()
295 a
= solver
.add_variable('a')
296 b
= solver
.add_variable('b')
297 c
= solver
.add_variable('c')
299 # Add a clause. It starts watching the first two variables (a and b).
300 # (use the internal function to avoid variable reordering)
301 solver
._add
_clause
([a
, b
, c
], False)
303 # b is False, so it switches to watching a and c
304 solver
.add_clause([sat
.neg(b
)])
306 # Try to trigger bug.
307 solver
.add_clause([c
])
310 solver
.run_solver(lambda: decisions
.pop())
311 assert not decisions
# All used up
313 assert solver
.assigns
[a
].value
== True
315 def testOverbacktrack(self
):
316 # After learning that prog-3 => m0 we backtrack all the way up to the prog-3
317 # assignment, unselecting liba-3, and then select it again.
318 assertSelection("prog-3, liba-3, libb-3, libc-1, libz-2", """
322 libc Linux-x86_64: 2 3
325 prog[2,3] => liba 1 3
326 prog[2,3] => libz 1 2
327 liba[1,3] => libb 1 3
328 libb[1,3] => libc 1 3
331 if __name__
== '__main__':