Devuan deployment of britney2
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 

572 lines
25 KiB

  1. import sys
  2. import unittest
  3. from collections import OrderedDict
  4. from . import new_pkg_universe_builder
  5. from britney2.installability.solver import compute_scc, InstallabilitySolver, OrderNode
  6. class TestInstTester(unittest.TestCase):
  7. def test_basic_inst_test(self):
  8. builder = new_pkg_universe_builder()
  9. universe, inst_tester = builder.new_package('lintian').depends_on('perl').depends_on_any_of('awk', 'mawk').\
  10. new_package('perl-base').is_essential().\
  11. new_package('dpkg').is_essential(). \
  12. new_package('perl').\
  13. new_package('awk').not_in_testing().\
  14. new_package('mawk').\
  15. build()
  16. pkg_lintian = builder.pkg_id('lintian')
  17. pkg_awk = builder.pkg_id('awk')
  18. pkg_mawk = builder.pkg_id('mawk')
  19. pkg_perl = builder.pkg_id('perl')
  20. pkg_perl_base = builder.pkg_id('perl-base')
  21. assert inst_tester.is_installable(pkg_lintian)
  22. assert inst_tester.is_installable(pkg_perl)
  23. assert inst_tester.any_of_these_are_in_the_suite((pkg_lintian, pkg_perl))
  24. assert not inst_tester.is_installable(pkg_awk)
  25. assert not inst_tester.any_of_these_are_in_the_suite((pkg_awk,))
  26. inst_tester.remove_binary(pkg_perl)
  27. assert not inst_tester.any_of_these_are_in_the_suite((pkg_perl,))
  28. assert inst_tester.any_of_these_are_in_the_suite((pkg_lintian,))
  29. assert not inst_tester.is_pkg_in_the_suite(pkg_perl)
  30. assert inst_tester.is_pkg_in_the_suite(pkg_lintian)
  31. assert not inst_tester.is_installable(pkg_lintian)
  32. assert not inst_tester.is_installable(pkg_perl)
  33. inst_tester.add_binary(pkg_perl)
  34. assert inst_tester.is_installable(pkg_lintian)
  35. assert inst_tester.is_installable(pkg_perl)
  36. assert universe.reverse_dependencies_of(pkg_perl) == {pkg_lintian}
  37. assert universe.reverse_dependencies_of(pkg_lintian) == frozenset()
  38. # awk and mawk are equivalent, but nothing else is eqv.
  39. assert universe.are_equivalent(pkg_awk, pkg_mawk)
  40. assert not universe.are_equivalent(pkg_lintian, pkg_mawk)
  41. assert not universe.are_equivalent(pkg_lintian, pkg_perl)
  42. assert not universe.are_equivalent(pkg_mawk, pkg_perl)
  43. # Trivial test of the special case for adding and removing an essential package
  44. inst_tester.remove_binary(pkg_perl_base)
  45. inst_tester.add_binary(pkg_perl_base)
  46. inst_tester.add_binary(pkg_awk)
  47. assert inst_tester.is_installable(pkg_lintian)
  48. def test_basic_essential_conflict(self):
  49. builder = new_pkg_universe_builder()
  50. pseudo_ess1 = builder.new_package('pseudo-essential1')
  51. pseudo_ess2 = builder.new_package('pseudo-essential2')
  52. essential_simple = builder.new_package('essential-simple').is_essential()
  53. essential_with_deps = builder.new_package('essential-with-deps').is_essential().\
  54. depends_on_any_of(pseudo_ess1, pseudo_ess2)
  55. conflict1 = builder.new_package('conflict1').conflicts_with(essential_simple)
  56. conflict2 = builder.new_package('conflict2').conflicts_with(pseudo_ess1, pseudo_ess2)
  57. conflict_installable1 = builder.new_package('conflict-inst1').conflicts_with(pseudo_ess1)
  58. conflict_installable2 = builder.new_package('conflict-inst2').conflicts_with(pseudo_ess2)
  59. universe, inst_tester = builder.build()
  60. assert inst_tester.is_installable(essential_simple.pkg_id)
  61. assert inst_tester.is_installable(essential_with_deps.pkg_id)
  62. assert inst_tester.is_installable(conflict_installable1.pkg_id)
  63. assert inst_tester.is_installable(conflict_installable2.pkg_id)
  64. assert not inst_tester.is_installable(conflict1.pkg_id)
  65. assert not inst_tester.is_installable(conflict2.pkg_id)
  66. for line in inst_tester.stats.stats():
  67. print(line)
  68. assert inst_tester.stats.conflicts_essential == 1
  69. def test_basic_simple_choice(self):
  70. builder = new_pkg_universe_builder()
  71. root_pkg = builder.new_package('root')
  72. conflicting1 = builder.new_package('conflict1')
  73. conflicting2 = builder.new_package('conflict2')
  74. bottom1_pkg = builder.new_package('bottom1').conflicts_with(conflicting1)
  75. bottom2_pkg = builder.new_package('bottom2').conflicts_with(conflicting2)
  76. pkg1 = builder.new_package('pkg1').depends_on(bottom1_pkg)
  77. pkg2 = builder.new_package('pkg2').depends_on(bottom2_pkg)
  78. root_pkg.depends_on_any_of(pkg1, pkg2)
  79. universe, inst_tester = builder.build()
  80. # The dependencies of "root" are not equivalent (if they were, we would trigger
  81. # an optimization, which takes another code path)
  82. assert not universe.are_equivalent(pkg1.pkg_id, pkg2.pkg_id)
  83. assert inst_tester.is_installable(root_pkg.pkg_id)
  84. for line in inst_tester.stats.stats():
  85. print(line)
  86. assert inst_tester.stats.eqv_table_times_used == 0
  87. assert inst_tester.stats.eqv_table_total_number_of_alternatives_eliminated == 0
  88. assert inst_tester.stats.eqv_table_reduced_to_one == 0
  89. assert inst_tester.stats.eqv_table_reduced_by_zero == 0
  90. def test_basic_simple_choice_deadend(self):
  91. builder = new_pkg_universe_builder()
  92. root_pkg = builder.new_package('root')
  93. bottom1_pkg = builder.new_package('bottom1').conflicts_with(root_pkg)
  94. bottom2_pkg = builder.new_package('bottom2').conflicts_with(root_pkg)
  95. pkg1 = builder.new_package('pkg1').depends_on(bottom1_pkg)
  96. pkg2 = builder.new_package('pkg2').depends_on(bottom2_pkg)
  97. root_pkg.depends_on_any_of(pkg1, pkg2)
  98. universe, inst_tester = builder.build()
  99. # The dependencies of "root" are not equivalent (if they were, we would trigger
  100. # an optimization, which takes another code path)
  101. assert not universe.are_equivalent(pkg1.pkg_id, pkg2.pkg_id)
  102. assert not inst_tester.is_installable(root_pkg.pkg_id)
  103. for line in inst_tester.stats.stats():
  104. print(line)
  105. assert inst_tester.stats.eqv_table_times_used == 0
  106. assert inst_tester.stats.eqv_table_total_number_of_alternatives_eliminated == 0
  107. assert inst_tester.stats.eqv_table_reduced_to_one == 0
  108. assert inst_tester.stats.eqv_table_reduced_by_zero == 0
  109. # This case is simple enough that the installability tester will assert it does not
  110. # need to recurse to reject the first option
  111. assert inst_tester.stats.backtrace_restore_point_used == 0
  112. assert inst_tester.stats.backtrace_last_option == 1
  113. def test_basic_simple_choice_opt_no_restore_needed(self):
  114. builder = new_pkg_universe_builder()
  115. conflicting = builder.new_package('conflict')
  116. root_pkg = builder.new_package('root').conflicts_with(conflicting)
  117. bottom1_pkg = builder.new_package('bottom1').conflicts_with(conflicting)
  118. bottom2_pkg = builder.new_package('bottom2').conflicts_with(conflicting)
  119. # These two packages have (indirect) conflicts, so they cannot trigger the
  120. # safe set optimization. However, since "root" already have the same conflict
  121. # it can use the "no restore point needed" optimization.
  122. pkg1 = builder.new_package('pkg1').depends_on(bottom1_pkg)
  123. pkg2 = builder.new_package('pkg2').depends_on(bottom2_pkg)
  124. root_pkg.depends_on_any_of(pkg1, pkg2)
  125. universe, inst_tester = builder.build()
  126. # The dependencies of "root" are not equivalent (if they were, we would trigger
  127. # an optimization, which takes another code path)
  128. assert not universe.are_equivalent(pkg1.pkg_id, pkg2.pkg_id)
  129. assert inst_tester.is_installable(root_pkg.pkg_id)
  130. for line in inst_tester.stats.stats():
  131. print(line)
  132. assert inst_tester.stats.eqv_table_times_used == 0
  133. assert inst_tester.stats.eqv_table_total_number_of_alternatives_eliminated == 0
  134. assert inst_tester.stats.eqv_table_reduced_to_one == 0
  135. assert inst_tester.stats.eqv_table_reduced_by_zero == 0
  136. assert inst_tester.stats.backtrace_restore_point_used == 0
  137. assert inst_tester.stats.backtrace_last_option == 0
  138. assert inst_tester.stats.choice_resolved_without_restore_point == 1
  139. def test_basic_simple_choice_opt_no_restore_needed_deadend(self):
  140. builder = new_pkg_universe_builder()
  141. conflicting1 = builder.new_package('conflict1').conflicts_with('conflict2')
  142. conflicting2 = builder.new_package('conflict2').conflicts_with('conflict1')
  143. root_pkg = builder.new_package('root')
  144. bottom_pkg = builder.new_package('bottom').depends_on(conflicting1).depends_on(conflicting2)
  145. mid1_pkg = builder.new_package('mid1').depends_on(bottom_pkg)
  146. mid2_pkg = builder.new_package('mid2').depends_on(bottom_pkg)
  147. # These two packages have (indirect) conflicts, so they cannot trigger the
  148. # safe set optimization. However, since "root" already have the same conflict
  149. # it can use the "no restore point needed" optimization.
  150. pkg1 = builder.new_package('pkg1').depends_on(mid1_pkg)
  151. pkg2 = builder.new_package('pkg2').depends_on(mid2_pkg)
  152. root_pkg.depends_on_any_of(pkg1, pkg2)
  153. universe, inst_tester = builder.build()
  154. # The dependencies of "root" are not equivalent (if they were, we would trigger
  155. # an optimization, which takes another code path)
  156. assert not universe.are_equivalent(pkg1.pkg_id, pkg2.pkg_id)
  157. assert not inst_tester.is_installable(root_pkg.pkg_id)
  158. for line in inst_tester.stats.stats():
  159. print(line)
  160. assert inst_tester.stats.eqv_table_times_used == 0
  161. assert inst_tester.stats.eqv_table_total_number_of_alternatives_eliminated == 0
  162. assert inst_tester.stats.eqv_table_reduced_to_one == 0
  163. assert inst_tester.stats.eqv_table_reduced_by_zero == 0
  164. assert inst_tester.stats.backtrace_restore_point_used == 0
  165. assert inst_tester.stats.choice_resolved_without_restore_point == 0
  166. assert inst_tester.stats.backtrace_last_option == 1
  167. def test_basic_choice_deadend_restore_point_needed(self):
  168. builder = new_pkg_universe_builder()
  169. root_pkg = builder.new_package('root')
  170. bottom1_pkg = builder.new_package('bottom1').depends_on_any_of('bottom2', 'bottom3')
  171. bottom2_pkg = builder.new_package('bottom2').conflicts_with(root_pkg)
  172. bottom3_pkg = builder.new_package('bottom3').depends_on_any_of('bottom1', 'bottom2')
  173. pkg1 = builder.new_package('pkg1').depends_on_any_of(bottom1_pkg, bottom2_pkg).conflicts_with('bottom3')
  174. pkg2 = builder.new_package('pkg2').depends_on_any_of(bottom2_pkg, bottom3_pkg).conflicts_with('bottom1')
  175. root_pkg.depends_on_any_of(pkg1, pkg2)
  176. universe, inst_tester = builder.build()
  177. # The dependencies of "root" are not equivalent (if they were, we would trigger
  178. # an optimization, which takes another code path)
  179. assert not universe.are_equivalent(pkg1.pkg_id, pkg2.pkg_id)
  180. assert not inst_tester.is_installable(root_pkg.pkg_id)
  181. for line in inst_tester.stats.stats():
  182. print(line)
  183. assert inst_tester.stats.eqv_table_times_used == 0
  184. assert inst_tester.stats.eqv_table_total_number_of_alternatives_eliminated == 0
  185. assert inst_tester.stats.eqv_table_reduced_to_one == 0
  186. assert inst_tester.stats.eqv_table_reduced_by_zero == 0
  187. # This case is simple enough that the installability tester will assert it does not
  188. # need to recurse to reject the first option
  189. assert inst_tester.stats.backtrace_restore_point_used == 1
  190. assert inst_tester.stats.backtrace_last_option == 1
  191. def test_corner_case_dependencies_inter_conflict(self):
  192. builder = new_pkg_universe_builder()
  193. root_pkg = builder.new_package('root').depends_on('conflict1').depends_on('conflict2')
  194. conflicting1 = builder.new_package('conflict1').conflicts_with('conflict2')
  195. conflicting2 = builder.new_package('conflict2').conflicts_with('conflict1')
  196. universe, inst_tester = builder.build()
  197. # They should not be eqv.
  198. assert not universe.are_equivalent(conflicting1.pkg_id, conflicting2.pkg_id)
  199. # "root" should not be installable and we should trigger a special code path where
  200. # the installability tester has both conflicting packages in its "check" set
  201. # Technically, we cannot assert we hit that path with this test, but we can at least
  202. # check it does not regress
  203. assert not inst_tester.is_installable(root_pkg.pkg_id)
  204. def test_basic_choice_deadend_pre_solvable(self):
  205. builder = new_pkg_universe_builder()
  206. # This test is complicated by the fact that the inst-tester has a non-deterministic ordering.
  207. # To ensure that it becomes predictable, we have to force it to see the choice before
  208. # the part that eliminates it. In practise, this is easiest to do by creating a symmetric
  209. # graph where one solving one choice eliminates the other.
  210. root_pkg = builder.new_package('root')
  211. # These two packages are used to make options distinct; otherwise the eqv. optimisation will just
  212. # collapse the choices.
  213. nodep1 = builder.new_package('nodep1')
  214. nodep2 = builder.new_package('nodep2')
  215. path1a = builder.new_package('path1a').depends_on(nodep1).depends_on('end1')
  216. path1b = builder.new_package('path1b').depends_on(nodep2).depends_on('end1')
  217. path2a = builder.new_package('path2a').depends_on(nodep1).depends_on('end2')
  218. path2b = builder.new_package('path2b').depends_on(nodep2).depends_on('end2')
  219. builder.new_package('end1').conflicts_with(path2a, path2b)
  220. builder.new_package('end2').conflicts_with(path1a, path1b)
  221. root_pkg.depends_on_any_of(path1a, path1b).depends_on_any_of(path2a, path2b)
  222. _, inst_tester = builder.build()
  223. assert not inst_tester.is_installable(root_pkg.pkg_id)
  224. for line in inst_tester.stats.stats():
  225. print(line)
  226. assert inst_tester.stats.eqv_table_times_used == 0
  227. assert inst_tester.stats.eqv_table_total_number_of_alternatives_eliminated == 0
  228. assert inst_tester.stats.eqv_table_reduced_to_one == 0
  229. assert inst_tester.stats.eqv_table_reduced_by_zero == 0
  230. # The following numbers are observed due to:
  231. # * Pick an option from (pathXa | pathXb)
  232. # * First option -> obviously unsolvable
  233. # * Undo and do "last option" on the remaining
  234. # * "last option" -> obviously unsolvable
  235. # * unsolvable
  236. assert inst_tester.stats.backtrace_restore_point_used == 1
  237. assert inst_tester.stats.backtrace_last_option == 1
  238. assert inst_tester.stats.choice_presolved == 2
  239. def test_basic_choice_pre_solvable(self):
  240. builder = new_pkg_universe_builder()
  241. # This test is complicated by the fact that the inst-tester has a non-deterministic ordering.
  242. # To ensure that it becomes predictable, we have to force it to see the choice before
  243. # the part that eliminates it. In practise, this is easiest to do by creating a symmetric
  244. # graph where one solving one choice eliminates the other.
  245. root_pkg = builder.new_package('root')
  246. nodep1 = builder.new_package('nodep1').conflicts_with('path1b', 'path2b')
  247. nodep2 = builder.new_package('nodep2').conflicts_with('path1b', 'path2b')
  248. end1 = builder.new_package('end1')
  249. end2 = builder.new_package('end2')
  250. path1a = builder.new_package('path1a').depends_on(nodep1).depends_on(end1)
  251. path1b = builder.new_package('path1b').depends_on(nodep2).depends_on(end1)
  252. path2a = builder.new_package('path2a').depends_on(nodep1).depends_on(end2)
  253. path2b = builder.new_package('path2b').depends_on(nodep2).depends_on(end2)
  254. root_pkg.depends_on_any_of(path1a, path1b).depends_on_any_of(path2a, path2b)
  255. _, inst_tester = builder.build()
  256. assert inst_tester.is_installable(root_pkg.pkg_id)
  257. for line in inst_tester.stats.stats():
  258. print(line)
  259. assert inst_tester.stats.eqv_table_times_used == 0
  260. assert inst_tester.stats.eqv_table_total_number_of_alternatives_eliminated == 0
  261. assert inst_tester.stats.eqv_table_reduced_to_one == 0
  262. assert inst_tester.stats.eqv_table_reduced_by_zero == 0
  263. # After its first guess, the tester can pre-solve remaining choice
  264. assert inst_tester.stats.backtrace_restore_point_used == 0
  265. assert inst_tester.stats.choice_presolved == 1
  266. def test_optimisation_simple_full_eqv_reduction(self):
  267. builder = new_pkg_universe_builder()
  268. root_pkg = builder.new_package('root')
  269. conflicting = builder.new_package('conflict')
  270. bottom1_pkg = builder.new_package('bottom1').conflicts_with(conflicting)
  271. # Row 1 is simple enough that it collapse into a single option immediately
  272. # (Ergo eqv_table_reduced_to_one == 1)
  273. row1 = ['pkg-%s' % x for x in range(1000)]
  274. root_pkg.depends_on_any_of(*row1)
  275. for pkg in row1:
  276. builder.new_package(pkg).depends_on(bottom1_pkg)
  277. universe, inst_tester = builder.build()
  278. pkg_row1 = builder.pkg_id(row1[0])
  279. # all items in a row are eqv.
  280. for pkg in row1:
  281. assert universe.are_equivalent(builder.pkg_id(pkg), pkg_row1)
  282. assert inst_tester.is_installable(root_pkg.pkg_id)
  283. for line in inst_tester.stats.stats():
  284. print(line)
  285. assert inst_tester.stats.eqv_table_times_used == 1
  286. assert inst_tester.stats.eqv_table_total_number_of_alternatives_eliminated == 999
  287. assert inst_tester.stats.eqv_table_reduced_to_one == 1
  288. def test_optimisation_simple_partial_eqv_reduction(self):
  289. builder = new_pkg_universe_builder()
  290. root_pkg = builder.new_package('root')
  291. conflicting = builder.new_package('conflict')
  292. another_pkg = builder.new_package('another-pkg')
  293. bottom1_pkg = builder.new_package('bottom1').conflicts_with(conflicting)
  294. # Row 1 is simple enough that it collapse into a single option immediately
  295. # but due to "another_pkg" the entire choice is only reduced into two
  296. row1 = ['pkg-%s' % x for x in range(1000)]
  297. root_pkg.depends_on_any_of(another_pkg, *row1)
  298. for pkg in row1:
  299. builder.new_package(pkg).depends_on(bottom1_pkg)
  300. universe, inst_tester = builder.build()
  301. pkg_row1 = builder.pkg_id(row1[0])
  302. # all items in a row are eqv.
  303. for pkg in row1:
  304. assert universe.are_equivalent(builder.pkg_id(pkg), pkg_row1)
  305. assert inst_tester.is_installable(root_pkg.pkg_id)
  306. for line in inst_tester.stats.stats():
  307. print(line)
  308. assert inst_tester.stats.eqv_table_times_used == 1
  309. assert inst_tester.stats.eqv_table_total_number_of_alternatives_eliminated == 999
  310. assert inst_tester.stats.eqv_table_reduced_to_one == 0
  311. def test_optimisation_simple_zero_eqv_reduction(self):
  312. builder = new_pkg_universe_builder()
  313. root_pkg = builder.new_package('root')
  314. conflicting1 = builder.new_package('conflict1')
  315. conflicting2 = builder.new_package('conflict2')
  316. bottom1_pkg = builder.new_package('bottom1').conflicts_with(conflicting1)
  317. bottom2_pkg = builder.new_package('bottom2').conflicts_with(conflicting2)
  318. # To trigger a failed reduction, we have to create eqv. packages and ensure that only one
  319. # of them are in testing. Furthermore, the choice has to remain, so we create two pairs
  320. # of them
  321. pkg1_v1 = builder.new_package('pkg1', version='1.0-1').depends_on(bottom1_pkg)
  322. pkg1_v2 = builder.new_package('pkg1', version='2.0-1').depends_on(bottom1_pkg).not_in_testing()
  323. pkg2_v1 = builder.new_package('pkg2', version='1.0-1').depends_on(bottom2_pkg)
  324. pkg2_v2 = builder.new_package('pkg2', version='2.0-1').depends_on(bottom2_pkg).not_in_testing()
  325. root_pkg.depends_on_any_of(pkg1_v1, pkg1_v2, pkg2_v1, pkg2_v2)
  326. universe, inst_tester = builder.build()
  327. # The packages in the pairs are equivalent, but the two pairs are not
  328. assert universe.are_equivalent(pkg1_v1.pkg_id, pkg1_v2.pkg_id)
  329. assert universe.are_equivalent(pkg2_v1.pkg_id, pkg2_v2.pkg_id)
  330. assert not universe.are_equivalent(pkg1_v1.pkg_id, pkg2_v1.pkg_id)
  331. assert inst_tester.is_installable(root_pkg.pkg_id)
  332. for line in inst_tester.stats.stats():
  333. print(line)
  334. assert inst_tester.stats.eqv_table_times_used == 1
  335. assert inst_tester.stats.eqv_table_total_number_of_alternatives_eliminated == 0
  336. assert inst_tester.stats.eqv_table_reduced_to_one == 0
  337. assert inst_tester.stats.eqv_table_reduced_by_zero == 1
  338. def test_solver_recursion_limit(self):
  339. builder = new_pkg_universe_builder()
  340. recursion_limit = 200
  341. pkg_limit = recursion_limit + 20
  342. orig_limit = sys.getrecursionlimit()
  343. pkgs = [builder.new_package('pkg-%d' % i) for i in range(pkg_limit)]
  344. for i, pkg in enumerate(pkgs):
  345. # Intentionally -1 for the first package (wrap-around)
  346. ni = i - 1
  347. pkg.not_in_testing()
  348. pkg.depends_on(pkgs[ni])
  349. try:
  350. sys.setrecursionlimit(recursion_limit)
  351. universe, inst_tester = builder.build()
  352. solver = InstallabilitySolver(universe, inst_tester)
  353. groups = []
  354. for pkg in pkgs:
  355. group = (pkg.pkg_id.package_name, {pkg.pkg_id}, set())
  356. groups.append(group)
  357. expected = {g[0] for g in groups}
  358. actual = solver.solve_groups(groups)
  359. assert actual
  360. assert expected == set(actual[0])
  361. assert len(actual) == 1
  362. finally:
  363. sys.setrecursionlimit(orig_limit)
  364. def test_solver_simple_scc(self):
  365. builder = new_pkg_universe_builder()
  366. # SCC 1
  367. pkga = builder.new_package('pkg-a').not_in_testing()
  368. pkgb = builder.new_package('pkg-b').not_in_testing()
  369. pkgc = builder.new_package('pkg-c').not_in_testing()
  370. # SSC 2
  371. pkgd = builder.new_package('pkg-d').not_in_testing()
  372. pkge = builder.new_package('pkg-e').not_in_testing()
  373. pkgf = builder.new_package('pkg-f').not_in_testing()
  374. pkgg = builder.new_package('pkg-g').not_in_testing()
  375. pkgh = builder.new_package('pkg-h').not_in_testing()
  376. # SSC 3
  377. pkgi = builder.new_package('pkg-i').not_in_testing()
  378. # SSC 1 dependencies
  379. pkga.depends_on(pkgb)
  380. pkgb.depends_on(pkgc).depends_on(pkgd)
  381. pkgc.depends_on(pkga).depends_on(pkge)
  382. # SSC 2 dependencies
  383. pkgd.depends_on(pkgf)
  384. pkge.depends_on(pkgg).depends_on(pkgd)
  385. pkgf.depends_on(pkgh)
  386. pkgg.depends_on(pkgh)
  387. pkgh.depends_on(pkge).depends_on(pkgi)
  388. universe, inst_tester = builder.build()
  389. solver = InstallabilitySolver(universe, inst_tester)
  390. expected = [
  391. # SSC 3 first
  392. {pkgi.pkg_id.package_name},
  393. # Then SSC 2
  394. {pkgd.pkg_id.package_name, pkge.pkg_id.package_name, pkgf.pkg_id.package_name,
  395. pkgg.pkg_id.package_name, pkgh.pkg_id.package_name},
  396. # Finally SSC 1
  397. {pkga.pkg_id.package_name, pkgb.pkg_id.package_name, pkgc.pkg_id.package_name},
  398. ]
  399. groups = []
  400. for ssc in expected:
  401. for node in ssc:
  402. groups.append((node, {builder.pkg_id(node)}, {}))
  403. actual = [set(x) for x in solver.solve_groups(groups)]
  404. print("EXPECTED: %s" % str(expected))
  405. print("ACTUAL : %s" % str(actual))
  406. assert expected == actual
  407. def test_solver_no_scc_stack_bug(self):
  408. """
  409. This whitebox test is designed to trigger a bug in Tarjan's algorithm
  410. if you omit the "w is on stack of points" check from the pseudo code
  411. (or it is wrong). It makes tons of assumptions about how compute_scc
  412. works, so it is very sensitive to even minor tweaks.
  413. There is no strongly-connected component in this test, but if we
  414. trigger the bug, the algorithm will think there is one.
  415. """
  416. graph = OrderedDict()
  417. def _order_node(**args):
  418. node = OrderNode()
  419. node.before = args['before']
  420. node.after = args['after']
  421. return node
  422. graph['A'] = _order_node(
  423. before=['C', 'B'],
  424. after=['A0'],
  425. )
  426. graph['B'] = _order_node(
  427. before=['F'],
  428. after=['A'],
  429. )
  430. graph['C'] = _order_node(
  431. before=['E', 'D'],
  432. after=['A'],
  433. )
  434. graph['D'] = _order_node(
  435. before=[],
  436. after=['C'],
  437. )
  438. graph['E'] = _order_node(
  439. before=['B'],
  440. after=['C']
  441. )
  442. graph['F'] = _order_node(
  443. before=[],
  444. after=['B'],
  445. )
  446. graph['A0'] = _order_node(
  447. before=['A0'],
  448. after=[],
  449. )
  450. # We also assert that the order is correct to ensure that
  451. # nodes were visited in the order we expected (the bug is
  452. # visit order sensitive).
  453. expected = [
  454. ('F',),
  455. ('B',),
  456. ('D',),
  457. ('E',),
  458. ('C',),
  459. ('A',),
  460. ('A0',)
  461. ]
  462. actual = compute_scc(graph)
  463. print("EXPECTED: %s" % str(expected))
  464. print("ACTUAL : %s" % str(actual))
  465. assert expected == actual
  466. if __name__ == '__main__':
  467. unittest.main()