test_missing_obj_finder.py 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310
  1. # test_missing_obj_finder.py -- tests for MissingObjectFinder
  2. # Copyright (C) 2012 syntevo GmbH
  3. #
  4. # Dulwich is dual-licensed under the Apache License, Version 2.0 and the GNU
  5. # General Public License as public by the Free Software Foundation; version 2.0
  6. # or (at your option) any later version. You can redistribute it and/or
  7. # modify it under the terms of either of these two licenses.
  8. #
  9. # Unless required by applicable law or agreed to in writing, software
  10. # distributed under the License is distributed on an "AS IS" BASIS,
  11. # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. # See the License for the specific language governing permissions and
  13. # limitations under the License.
  14. #
  15. # You should have received a copy of the licenses; if not, see
  16. # <http://www.gnu.org/licenses/> for a copy of the GNU General Public License
  17. # and <http://www.apache.org/licenses/LICENSE-2.0> for a copy of the Apache
  18. # License, Version 2.0.
  19. #
  20. from dulwich.object_store import MemoryObjectStore, MissingObjectFinder
  21. from dulwich.objects import Blob
  22. from dulwich.tests.utils import build_commit_graph, make_object, make_tag
  23. from . import TestCase
  24. class MissingObjectFinderTest(TestCase):
  25. def setUp(self):
  26. super().setUp()
  27. self.store = MemoryObjectStore()
  28. self.commits = []
  29. def cmt(self, n):
  30. return self.commits[n - 1]
  31. def assertMissingMatch(self, haves, wants, expected):
  32. for sha, path in MissingObjectFinder(self.store, haves, wants, shallow=set()):
  33. self.assertIn(
  34. sha, expected, f"({sha},{path}) erroneously reported as missing"
  35. )
  36. expected.remove(sha)
  37. self.assertEqual(
  38. len(expected),
  39. 0,
  40. f"some objects are not reported as missing: {expected}",
  41. )
  42. class MOFLinearRepoTest(MissingObjectFinderTest):
  43. def setUp(self):
  44. super().setUp()
  45. # present in 1, removed in 3
  46. f1_1 = make_object(Blob, data=b"f1")
  47. # present in all revisions, changed in 2 and 3
  48. f2_1 = make_object(Blob, data=b"f2")
  49. f2_2 = make_object(Blob, data=b"f2-changed")
  50. f2_3 = make_object(Blob, data=b"f2-changed-again")
  51. # added in 2, left unmodified in 3
  52. f3_2 = make_object(Blob, data=b"f3")
  53. commit_spec = [[1], [2, 1], [3, 2]]
  54. trees = {
  55. 1: [(b"f1", f1_1), (b"f2", f2_1)],
  56. 2: [(b"f1", f1_1), (b"f2", f2_2), (b"f3", f3_2)],
  57. 3: [(b"f2", f2_3), (b"f3", f3_2)],
  58. }
  59. # commit 1: f1 and f2
  60. # commit 2: f3 added, f2 changed. Missing shall report commit id and a
  61. # tree referenced by commit
  62. # commit 3: f1 removed, f2 changed. Commit sha and root tree sha shall
  63. # be reported as modified
  64. self.commits = build_commit_graph(self.store, commit_spec, trees)
  65. self.missing_1_2 = [self.cmt(2).id, self.cmt(2).tree, f2_2.id, f3_2.id]
  66. self.missing_2_3 = [self.cmt(3).id, self.cmt(3).tree, f2_3.id]
  67. self.missing_1_3 = [
  68. self.cmt(2).id,
  69. self.cmt(3).id,
  70. self.cmt(2).tree,
  71. self.cmt(3).tree,
  72. f2_2.id,
  73. f3_2.id,
  74. f2_3.id,
  75. ]
  76. def test_1_to_2(self):
  77. self.assertMissingMatch([self.cmt(1).id], [self.cmt(2).id], self.missing_1_2)
  78. def test_2_to_3(self):
  79. self.assertMissingMatch([self.cmt(2).id], [self.cmt(3).id], self.missing_2_3)
  80. def test_1_to_3(self):
  81. self.assertMissingMatch([self.cmt(1).id], [self.cmt(3).id], self.missing_1_3)
  82. def test_bogus_haves(self):
  83. """Ensure non-existent SHA in haves are tolerated."""
  84. bogus_sha = self.cmt(2).id[::-1]
  85. haves = [self.cmt(1).id, bogus_sha]
  86. wants = [self.cmt(3).id]
  87. self.assertMissingMatch(haves, wants, self.missing_1_3)
  88. def test_bogus_wants_failure(self):
  89. """Ensure non-existent SHA in wants are not tolerated."""
  90. bogus_sha = self.cmt(2).id[::-1]
  91. haves = [self.cmt(1).id]
  92. wants = [self.cmt(3).id, bogus_sha]
  93. self.assertRaises(
  94. KeyError, MissingObjectFinder, self.store, haves, wants, shallow=set()
  95. )
  96. def test_no_changes(self):
  97. self.assertMissingMatch([self.cmt(3).id], [self.cmt(3).id], [])
  98. class MOFMergeForkRepoTest(MissingObjectFinderTest):
  99. # 1 --- 2 --- 4 --- 6 --- 7
  100. # \ /
  101. # 3 ---
  102. # \
  103. # 5
  104. def setUp(self):
  105. super().setUp()
  106. f1_1 = make_object(Blob, data=b"f1")
  107. f1_2 = make_object(Blob, data=b"f1-2")
  108. f1_4 = make_object(Blob, data=b"f1-4")
  109. f1_7 = make_object(Blob, data=b"f1-2") # same data as in rev 2
  110. f2_1 = make_object(Blob, data=b"f2")
  111. f2_3 = make_object(Blob, data=b"f2-3")
  112. f3_3 = make_object(Blob, data=b"f3")
  113. f3_5 = make_object(Blob, data=b"f3-5")
  114. commit_spec = [[1], [2, 1], [3, 2], [4, 2], [5, 3], [6, 3, 4], [7, 6]]
  115. trees = {
  116. 1: [(b"f1", f1_1), (b"f2", f2_1)],
  117. 2: [(b"f1", f1_2), (b"f2", f2_1)], # f1 changed
  118. # f3 added, f2 changed
  119. 3: [(b"f1", f1_2), (b"f2", f2_3), (b"f3", f3_3)],
  120. 4: [(b"f1", f1_4), (b"f2", f2_1)], # f1 changed
  121. 5: [(b"f1", f1_2), (b"f3", f3_5)], # f2 removed, f3 changed
  122. # merged 3 and 4
  123. 6: [(b"f1", f1_4), (b"f2", f2_3), (b"f3", f3_3)],
  124. # f1 changed to match rev2. f3 removed
  125. 7: [(b"f1", f1_7), (b"f2", f2_3)],
  126. }
  127. self.commits = build_commit_graph(self.store, commit_spec, trees)
  128. self.f1_2_id = f1_2.id
  129. self.f1_4_id = f1_4.id
  130. self.f1_7_id = f1_7.id
  131. self.f2_3_id = f2_3.id
  132. self.f3_3_id = f3_3.id
  133. self.assertEqual(f1_2.id, f1_7.id, "[sanity]")
  134. def test_have6_want7(self):
  135. # have 6, want 7. Ideally, shall not report f1_7 as it's the same as
  136. # f1_2, however, to do so, MissingObjectFinder shall not record trees
  137. # of common commits only, but also all parent trees and tree items,
  138. # which is an overkill (i.e. in sha_done it records f1_4 as known, and
  139. # doesn't record f1_2 was known prior to that, hence can't detect f1_7
  140. # is in fact f1_2 and shall not be reported)
  141. self.assertMissingMatch(
  142. [self.cmt(6).id],
  143. [self.cmt(7).id],
  144. [self.cmt(7).id, self.cmt(7).tree, self.f1_7_id],
  145. )
  146. def test_have4_want7(self):
  147. # have 4, want 7. Shall not include rev5 as it is not in the tree
  148. # between 4 and 7 (well, it is, but its SHA's are irrelevant for 4..7
  149. # commit hierarchy)
  150. self.assertMissingMatch(
  151. [self.cmt(4).id],
  152. [self.cmt(7).id],
  153. [
  154. self.cmt(7).id,
  155. self.cmt(6).id,
  156. self.cmt(3).id,
  157. self.cmt(7).tree,
  158. self.cmt(6).tree,
  159. self.cmt(3).tree,
  160. self.f2_3_id,
  161. self.f3_3_id,
  162. ],
  163. )
  164. def test_have1_want6(self):
  165. # have 1, want 6. Shall not include rev5
  166. self.assertMissingMatch(
  167. [self.cmt(1).id],
  168. [self.cmt(6).id],
  169. [
  170. self.cmt(6).id,
  171. self.cmt(4).id,
  172. self.cmt(3).id,
  173. self.cmt(2).id,
  174. self.cmt(6).tree,
  175. self.cmt(4).tree,
  176. self.cmt(3).tree,
  177. self.cmt(2).tree,
  178. self.f1_2_id,
  179. self.f1_4_id,
  180. self.f2_3_id,
  181. self.f3_3_id,
  182. ],
  183. )
  184. def test_have3_want6(self):
  185. # have 3, want 7. Shall not report rev2 and its tree, because
  186. # haves(3) means has parents, i.e. rev2, too
  187. # BUT shall report any changes descending rev2 (excluding rev3)
  188. # Shall NOT report f1_7 as it's technically == f1_2
  189. self.assertMissingMatch(
  190. [self.cmt(3).id],
  191. [self.cmt(7).id],
  192. [
  193. self.cmt(7).id,
  194. self.cmt(6).id,
  195. self.cmt(4).id,
  196. self.cmt(7).tree,
  197. self.cmt(6).tree,
  198. self.cmt(4).tree,
  199. self.f1_4_id,
  200. ],
  201. )
  202. def test_have5_want7(self):
  203. # have 5, want 7. Common parent is rev2, hence children of rev2 from
  204. # a descent line other than rev5 shall be reported
  205. # expects f1_4 from rev6. f3_5 is known in rev5;
  206. # f1_7 shall be the same as f1_2 (known, too)
  207. self.assertMissingMatch(
  208. [self.cmt(5).id],
  209. [self.cmt(7).id],
  210. [
  211. self.cmt(7).id,
  212. self.cmt(6).id,
  213. self.cmt(4).id,
  214. self.cmt(7).tree,
  215. self.cmt(6).tree,
  216. self.cmt(4).tree,
  217. self.f1_4_id,
  218. ],
  219. )
  220. class MOFTagsTest(MissingObjectFinderTest):
  221. def setUp(self):
  222. super().setUp()
  223. f1_1 = make_object(Blob, data=b"f1")
  224. commit_spec = [[1]]
  225. trees = {1: [(b"f1", f1_1)]}
  226. self.commits = build_commit_graph(self.store, commit_spec, trees)
  227. self._normal_tag = make_tag(self.cmt(1))
  228. self.store.add_object(self._normal_tag)
  229. self._tag_of_tag = make_tag(self._normal_tag)
  230. self.store.add_object(self._tag_of_tag)
  231. self._tag_of_tree = make_tag(self.store[self.cmt(1).tree])
  232. self.store.add_object(self._tag_of_tree)
  233. self._tag_of_blob = make_tag(f1_1)
  234. self.store.add_object(self._tag_of_blob)
  235. self._tag_of_tag_of_blob = make_tag(self._tag_of_blob)
  236. self.store.add_object(self._tag_of_tag_of_blob)
  237. self.f1_1_id = f1_1.id
  238. def test_tagged_commit(self):
  239. # The user already has the tagged commit, all they want is the tag,
  240. # so send them only the tag object.
  241. self.assertMissingMatch(
  242. [self.cmt(1).id], [self._normal_tag.id], [self._normal_tag.id]
  243. )
  244. # The remaining cases are unusual, but do happen in the wild.
  245. def test_tagged_tag(self):
  246. # User already has tagged tag, send only tag of tag
  247. self.assertMissingMatch(
  248. [self._normal_tag.id], [self._tag_of_tag.id], [self._tag_of_tag.id]
  249. )
  250. # User needs both tags, but already has commit
  251. self.assertMissingMatch(
  252. [self.cmt(1).id],
  253. [self._tag_of_tag.id],
  254. [self._normal_tag.id, self._tag_of_tag.id],
  255. )
  256. def test_tagged_tree(self):
  257. self.assertMissingMatch(
  258. [],
  259. [self._tag_of_tree.id],
  260. [self._tag_of_tree.id, self.cmt(1).tree, self.f1_1_id],
  261. )
  262. def test_tagged_blob(self):
  263. self.assertMissingMatch(
  264. [], [self._tag_of_blob.id], [self._tag_of_blob.id, self.f1_1_id]
  265. )
  266. def test_tagged_tagged_blob(self):
  267. self.assertMissingMatch(
  268. [],
  269. [self._tag_of_tag_of_blob.id],
  270. [self._tag_of_tag_of_blob.id, self._tag_of_blob.id, self.f1_1_id],
  271. )