ilyagr.bsky.social
just playing with tangled
1// Copyright 2021 The Jujutsu Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
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
15use itertools::Itertools as _;
16use jj_lib::backend::CommitId;
17use jj_lib::commit::Commit;
18use jj_lib::default_index::revset_engine::evaluate;
19use jj_lib::default_index::revset_engine::RevsetImpl;
20use jj_lib::default_index::DefaultReadonlyIndex;
21use jj_lib::graph::GraphEdge;
22use jj_lib::repo::ReadonlyRepo;
23use jj_lib::repo::Repo as _;
24use jj_lib::revset::ResolvedExpression;
25use test_case::test_case;
26use testutils::CommitGraphBuilder;
27use testutils::TestRepo;
28
29fn revset_for_commits(
30 repo: &ReadonlyRepo,
31 commits: &[&Commit],
32) -> RevsetImpl<DefaultReadonlyIndex> {
33 let index = repo
34 .readonly_index()
35 .as_any()
36 .downcast_ref::<DefaultReadonlyIndex>()
37 .unwrap();
38 let expression =
39 ResolvedExpression::Commits(commits.iter().map(|commit| commit.id().clone()).collect());
40 evaluate(&expression, repo.store(), index.clone()).unwrap()
41}
42
43fn direct(commit: &Commit) -> GraphEdge<CommitId> {
44 GraphEdge::direct(commit.id().clone())
45}
46
47fn indirect(commit: &Commit) -> GraphEdge<CommitId> {
48 GraphEdge::indirect(commit.id().clone())
49}
50
51fn missing(commit: &Commit) -> GraphEdge<CommitId> {
52 GraphEdge::missing(commit.id().clone())
53}
54
55#[test_case(false ; "keep transitive edges")]
56#[test_case(true ; "skip transitive edges")]
57fn test_graph_iterator_linearized(skip_transitive_edges: bool) {
58 let test_repo = TestRepo::init();
59 let repo = &test_repo.repo;
60
61 // Tests that a fork and a merge becomes a single edge:
62 // D
63 // |\ D
64 // b c => :
65 // |/ A
66 // A ~
67 // |
68 // root
69 let mut tx = repo.start_transaction();
70 let mut graph_builder = CommitGraphBuilder::new(tx.repo_mut());
71 let commit_a = graph_builder.initial_commit();
72 let commit_b = graph_builder.commit_with_parents(&[&commit_a]);
73 let commit_c = graph_builder.commit_with_parents(&[&commit_a]);
74 let commit_d = graph_builder.commit_with_parents(&[&commit_b, &commit_c]);
75 let repo = tx.commit("test").unwrap();
76 let root_commit = repo.store().root_commit();
77
78 let revset = revset_for_commits(repo.as_ref(), &[&commit_a, &commit_d]);
79 let commits: Vec<_> = revset
80 .iter_graph_impl(skip_transitive_edges)
81 .try_collect()
82 .unwrap();
83 assert_eq!(commits.len(), 2);
84 assert_eq!(commits[0].0, *commit_d.id());
85 assert_eq!(commits[1].0, *commit_a.id());
86 assert_eq!(commits[0].1, vec![indirect(&commit_a)]);
87 assert_eq!(commits[1].1, vec![missing(&root_commit)]);
88}
89
90#[test_case(false ; "keep transitive edges")]
91#[test_case(true ; "skip transitive edges")]
92fn test_graph_iterator_virtual_octopus(skip_transitive_edges: bool) {
93 let test_repo = TestRepo::init();
94 let repo = &test_repo.repo;
95
96 // Tests that merges outside the set can result in more parent edges than there
97 // was in the input:
98 //
99 // F
100 // |\
101 // d e F
102 // |\|\ => /|\
103 // A B C A B C
104 // \|/ ~ ~ ~
105 // root
106 let mut tx = repo.start_transaction();
107 let mut graph_builder = CommitGraphBuilder::new(tx.repo_mut());
108 let commit_a = graph_builder.initial_commit();
109 let commit_b = graph_builder.initial_commit();
110 let commit_c = graph_builder.initial_commit();
111 let commit_d = graph_builder.commit_with_parents(&[&commit_a, &commit_b]);
112 let commit_e = graph_builder.commit_with_parents(&[&commit_b, &commit_c]);
113 let commit_f = graph_builder.commit_with_parents(&[&commit_d, &commit_e]);
114 let repo = tx.commit("test").unwrap();
115 let root_commit = repo.store().root_commit();
116
117 let revset = revset_for_commits(repo.as_ref(), &[&commit_a, &commit_b, &commit_c, &commit_f]);
118 let commits: Vec<_> = revset
119 .iter_graph_impl(skip_transitive_edges)
120 .try_collect()
121 .unwrap();
122 assert_eq!(commits.len(), 4);
123 assert_eq!(commits[0].0, *commit_f.id());
124 assert_eq!(commits[1].0, *commit_c.id());
125 assert_eq!(commits[2].0, *commit_b.id());
126 assert_eq!(commits[3].0, *commit_a.id());
127 assert_eq!(
128 commits[0].1,
129 vec![
130 indirect(&commit_a),
131 indirect(&commit_b),
132 indirect(&commit_c),
133 ]
134 );
135 assert_eq!(commits[1].1, vec![missing(&root_commit)]);
136 assert_eq!(commits[2].1, vec![missing(&root_commit)]);
137 assert_eq!(commits[3].1, vec![missing(&root_commit)]);
138}
139
140#[test_case(false ; "keep transitive edges")]
141#[test_case(true ; "skip transitive edges")]
142fn test_graph_iterator_simple_fork(skip_transitive_edges: bool) {
143 let test_repo = TestRepo::init();
144 let repo = &test_repo.repo;
145
146 // Tests that the branch with "C" gets emitted correctly:
147 // E
148 // |
149 // d
150 // | C E C
151 // |/ |/
152 // b => A
153 // | ~
154 // A
155 // |
156 // root
157 let mut tx = repo.start_transaction();
158 let mut graph_builder = CommitGraphBuilder::new(tx.repo_mut());
159 let commit_a = graph_builder.initial_commit();
160 let commit_b = graph_builder.commit_with_parents(&[&commit_a]);
161 let commit_c = graph_builder.commit_with_parents(&[&commit_b]);
162 let commit_d = graph_builder.commit_with_parents(&[&commit_b]);
163 let commit_e = graph_builder.commit_with_parents(&[&commit_d]);
164 let repo = tx.commit("test").unwrap();
165 let root_commit = repo.store().root_commit();
166
167 let revset = revset_for_commits(repo.as_ref(), &[&commit_a, &commit_c, &commit_e]);
168 let commits: Vec<_> = revset
169 .iter_graph_impl(skip_transitive_edges)
170 .try_collect()
171 .unwrap();
172 assert_eq!(commits.len(), 3);
173 assert_eq!(commits[0].0, *commit_e.id());
174 assert_eq!(commits[1].0, *commit_c.id());
175 assert_eq!(commits[2].0, *commit_a.id());
176 assert_eq!(commits[0].1, vec![indirect(&commit_a)]);
177 assert_eq!(commits[1].1, vec![indirect(&commit_a)]);
178 assert_eq!(commits[2].1, vec![missing(&root_commit)]);
179}
180
181#[test_case(false ; "keep transitive edges")]
182#[test_case(true ; "skip transitive edges")]
183fn test_graph_iterator_multiple_missing(skip_transitive_edges: bool) {
184 let test_repo = TestRepo::init();
185 let repo = &test_repo.repo;
186
187 // Tests that we get missing edges to "a" and "c" and not just one missing edge
188 // to the root.
189 // F
190 // / \ F
191 // d e => /|\
192 // |\ /| ~ B ~
193 // a B c ~
194 // \|/
195 // root
196 let mut tx = repo.start_transaction();
197 let mut graph_builder = CommitGraphBuilder::new(tx.repo_mut());
198 let commit_a = graph_builder.initial_commit();
199 let commit_b = graph_builder.initial_commit();
200 let commit_c = graph_builder.initial_commit();
201 let commit_d = graph_builder.commit_with_parents(&[&commit_a, &commit_b]);
202 let commit_e = graph_builder.commit_with_parents(&[&commit_b, &commit_c]);
203 let commit_f = graph_builder.commit_with_parents(&[&commit_d, &commit_e]);
204 let repo = tx.commit("test").unwrap();
205 let root_commit = repo.store().root_commit();
206
207 let revset = revset_for_commits(repo.as_ref(), &[&commit_b, &commit_f]);
208 let commits: Vec<_> = revset
209 .iter_graph_impl(skip_transitive_edges)
210 .try_collect()
211 .unwrap();
212 assert_eq!(commits.len(), 2);
213 assert_eq!(commits[0].0, *commit_f.id());
214 assert_eq!(commits[1].0, *commit_b.id());
215 assert_eq!(
216 commits[0].1,
217 vec![missing(&commit_a), indirect(&commit_b), missing(&commit_c)]
218 );
219 assert_eq!(commits[1].1, vec![missing(&root_commit)]);
220}
221
222#[test_case(false ; "keep transitive edges")]
223#[test_case(true ; "skip transitive edges")]
224fn test_graph_iterator_edge_to_ancestor(skip_transitive_edges: bool) {
225 let test_repo = TestRepo::init();
226 let repo = &test_repo.repo;
227
228 // Tests that we get both an edge from F to D and to D's ancestor C if we keep
229 // transitive edges and only the edge from F to D if we skip transitive
230 // edges:
231 // F F
232 // |\ |\
233 // D e D :
234 // |\| => |\:
235 // b C ~ C
236 // | ~
237 // a
238 // |
239 // root
240 let mut tx = repo.start_transaction();
241 let mut graph_builder = CommitGraphBuilder::new(tx.repo_mut());
242 let commit_a = graph_builder.initial_commit();
243 let commit_b = graph_builder.initial_commit();
244 let commit_c = graph_builder.commit_with_parents(&[&commit_a]);
245 let commit_d = graph_builder.commit_with_parents(&[&commit_b, &commit_c]);
246 let commit_e = graph_builder.commit_with_parents(&[&commit_c]);
247 let commit_f = graph_builder.commit_with_parents(&[&commit_d, &commit_e]);
248 let repo = tx.commit("test").unwrap();
249
250 let revset = revset_for_commits(repo.as_ref(), &[&commit_c, &commit_d, &commit_f]);
251 let commits: Vec<_> = revset
252 .iter_graph_impl(skip_transitive_edges)
253 .try_collect()
254 .unwrap();
255 assert_eq!(commits.len(), 3);
256 assert_eq!(commits[0].0, *commit_f.id());
257 assert_eq!(commits[1].0, *commit_d.id());
258 assert_eq!(commits[2].0, *commit_c.id());
259 if skip_transitive_edges {
260 assert_eq!(commits[0].1, vec![direct(&commit_d)]);
261 } else {
262 assert_eq!(commits[0].1, vec![direct(&commit_d), indirect(&commit_c),]);
263 }
264 assert_eq!(commits[1].1, vec![missing(&commit_b), direct(&commit_c)]);
265 assert_eq!(commits[2].1, vec![missing(&commit_a)]);
266}
267
268#[test_case(false ; "keep transitive edges")]
269#[test_case(true ; "skip transitive edges")]
270fn test_graph_iterator_edge_escapes_from_(skip_transitive_edges: bool) {
271 let test_repo = TestRepo::init();
272 let repo = &test_repo.repo;
273
274 // Tests a more complex case for skipping transitive edges.
275 // J
276 // /|
277 // | i J
278 // | |\ /:
279 // | | H | H
280 // G | | G :
281 // | e f => : D
282 // | \|\ :/
283 // | D | A
284 // \ / c |
285 // b / root
286 // |/
287 // A
288 // |
289 // root
290 let mut tx = repo.start_transaction();
291 let mut graph_builder = CommitGraphBuilder::new(tx.repo_mut());
292 let commit_a = graph_builder.initial_commit();
293 let commit_b = graph_builder.commit_with_parents(&[&commit_a]);
294 let commit_c = graph_builder.commit_with_parents(&[&commit_a]);
295 let commit_d = graph_builder.commit_with_parents(&[&commit_b]);
296 let commit_e = graph_builder.commit_with_parents(&[&commit_d]);
297 let commit_f = graph_builder.commit_with_parents(&[&commit_d, &commit_c]);
298 let commit_g = graph_builder.commit_with_parents(&[&commit_b]);
299 let commit_h = graph_builder.commit_with_parents(&[&commit_f]);
300 let commit_i = graph_builder.commit_with_parents(&[&commit_e, &commit_h]);
301 let commit_j = graph_builder.commit_with_parents(&[&commit_g, &commit_i]);
302 let repo = tx.commit("test").unwrap();
303 let root_commit = repo.store().root_commit();
304
305 let revset = revset_for_commits(
306 repo.as_ref(),
307 &[&commit_a, &commit_d, &commit_g, &commit_h, &commit_j],
308 );
309 let commits: Vec<_> = revset
310 .iter_graph_impl(skip_transitive_edges)
311 .try_collect()
312 .unwrap();
313 assert_eq!(commits.len(), 5);
314 assert_eq!(commits[0].0, *commit_j.id());
315 assert_eq!(commits[1].0, *commit_h.id());
316 assert_eq!(commits[2].0, *commit_g.id());
317 assert_eq!(commits[3].0, *commit_d.id());
318 assert_eq!(commits[4].0, *commit_a.id());
319 if skip_transitive_edges {
320 assert_eq!(commits[0].1, vec![direct(&commit_g), indirect(&commit_h)]);
321 assert_eq!(commits[1].1, vec![indirect(&commit_d)]);
322 } else {
323 assert_eq!(
324 commits[0].1,
325 vec![direct(&commit_g), indirect(&commit_d), indirect(&commit_h)]
326 );
327 assert_eq!(commits[1].1, vec![indirect(&commit_d), indirect(&commit_a)]);
328 }
329 assert_eq!(commits[2].1, vec![indirect(&commit_a)]);
330 assert_eq!(commits[3].1, vec![indirect(&commit_a)]);
331 assert_eq!(commits[4].1, vec![missing(&root_commit)]);
332}