Skip to content
Sign up

flagon-io/g1t

public
0
728 linesCodeBlameRaw
1//! A pull request's test merge commit, as GitHub makes one for every open
2//! pull request: `refs/pull/<number>/head` at the pull request's head, and
3//! `refs/pull/<number>/merge` at a commit merging that head into the tip of
4//! the branch it targets. `pull_request` runs build that commit.
5//!
6//! It is made here, without a sandbox. A fork's head is first copied into
7//! the repository (only the objects it lacks travel). Files only one side
8//! changed since the two last agreed are taken from that side, as catching
9//! up does (catch_up.rs); a file both changed is merged line by line, the
10//! way git merges text, and changes to the same or neighbouring lines that
11//! differ are a conflict, as is a binary file both changed differently.
12//! Then there is no merge commit, as on GitHub, and the merge ref goes.
13//!
14//! What g1t cannot merge itself (a file one side renamed or deleted and the
15//! other changed, a file against a directory, a change too large to list)
16//! is answered as unavailable, and the caller decides what to do without it.
17
18use std::collections::{BTreeSet, HashMap};
19
20use futures_util::future::{try_join, try_join_all};
21use g1t_contracts::repos::{EntryKind, PullMergeRef, PullMergeRefArgs, TreeEntry, pull_head_ref, pull_merge_ref};
22use g1t_contracts::time::parse_rfc3339;
23use g1t_scan::pack::{ObjectKind, object_id, write_pack};
24use similar::{Algorithm, DiffTag, capture_diff_slices};
25use worker::Result;
26
27use crate::catch_up::{Change, Signature, ancestors, commit_object, merge_tree, overlapping, read_dirs};
28use crate::diff::{FileEntry, changed_entries};
29use crate::registry::store_key;
30use crate::store::{GitRepo, GitStore, Scope};
31use crate::{MAX_ANCESTRY, Repos, descends_from, land, nearest_ancestor_in, refs};
32
33/// Files larger than this are not merged line by line.
34const MAX_MERGE_BYTES: usize = 1024 * 1024;
35const ZERO_ID: &str = "0000000000000000000000000000000000000000";
36
37/// One side's change to the base: its lines `start..end` become `lines`.
38#[derive(Debug)]
39struct Hunk<'a> {
40 start: usize,
41 end: usize,
42 lines: Vec<&'a str>,
43}
44
45/// What `side` changed of `base`, as hunks in order, with no two touching.
46fn hunks<'a>(base: &[&'a str], side: &[&'a str]) -> Vec<Hunk<'a>> {
47 let mut out: Vec<Hunk<'a>> = Vec::new();
48 for op in capture_diff_slices(Algorithm::Myers, base, side) {
49 let (tag, old, new) = op.as_tag_tuple();
50 if tag == DiffTag::Equal {
51 continue;
52 }
53 let lines = side[new].to_vec();
54 match out.last_mut() {
55 Some(last) if last.end == old.start => {
56 last.end = old.end;
57 last.lines.extend(lines);
58 }
59 _ => out.push(Hunk { start: old.start, end: old.end, lines }),
60 }
61 }
62 out
63}
64
65/// The base's lines `start..end` with `hunks` (all inside them) applied.
66fn apply<'a>(base: &[&'a str], hunks: &[Hunk<'a>], start: usize, end: usize) -> Vec<&'a str> {
67 let mut out = Vec::new();
68 let mut at = start;
69 for hunk in hunks {
70 out.extend_from_slice(&base[at..hunk.start]);
71 out.extend_from_slice(&hunk.lines);
72 at = hunk.end;
73 }
74 out.extend_from_slice(&base[at..end]);
75 out
76}
77
78/// Merges two texts that each changed `base`, as git does: a change only
79/// one side made is taken, and where the two sides' changes overlap or
80/// touch (no unchanged line between them) they must be the same. `None`
81/// when they conflict.
82pub(crate) fn merge_text(base: &str, ours: &str, theirs: &str) -> Option<String> {
83 fn lines(text: &str) -> Vec<&str> {
84 text.split_inclusive('\n').collect()
85 }
86 let (base, ours, theirs) = (lines(base), lines(ours), lines(theirs));
87 let (mine, other) = (hunks(&base, &ours), hunks(&base, &theirs));
88 let mut out = String::new();
89 let (mut i, mut j, mut at) = (0, 0, 0);
90 while i < mine.len() || j < other.len() {
91 // The earliest change starts a run; every change that overlaps or
92 // touches the run joins it.
93 let first = if j >= other.len() || (i < mine.len() && mine[i].start <= other[j].start) { &mine[i] } else { &other[j] };
94 let (start, mut end) = (first.start, first.end);
95 let (from_mine, from_other) = (i, j);
96 loop {
97 if i < mine.len() && mine[i].start <= end {
98 end = end.max(mine[i].end);
99 i += 1;
100 } else if j < other.len() && other[j].start <= end {
101 end = end.max(other[j].end);
102 j += 1;
103 } else {
104 break;
105 }
106 }
107 let (mine_run, other_run) = (&mine[from_mine..i], &other[from_other..j]);
108 let merged = match (mine_run.is_empty(), other_run.is_empty()) {
109 (false, true) => apply(&base, mine_run, start, end),
110 (true, false) => apply(&base, other_run, start, end),
111 _ => {
112 let (a, b) = (apply(&base, mine_run, start, end), apply(&base, other_run, start, end));
113 if a != b {
114 return None;
115 }
116 a
117 }
118 };
119 out.extend(base[at..start].iter().copied());
120 out.extend(merged);
121 at = end;
122 }
123 out.extend(base[at..].iter().copied());
124 Some(out)
125}
126
127/// What becomes of one path in the merge, the base branch's tree being
128/// where the merge starts.
129#[derive(Debug, PartialEq, Eq)]
130pub(crate) enum Step {
131 /// Put the pull request's version there (`None`: remove it).
132 Take(Option<FileEntry>),
133 /// Both changed the file: merge the three texts, as `kind`.
134 Content { kind: EntryKind, base: Option<String>, ours: String, theirs: String },
135}
136
137/// What the files each side changed since the merge base come to, without
138/// reading any file.
139#[derive(Debug, PartialEq, Eq)]
140pub(crate) enum Plan {
141 Steps(Vec<(String, Step)>),
142 Conflict(Vec<String>),
143 Unsupported(String),
144}
145
146fn text_kind(kind: EntryKind) -> bool {
147 matches!(kind, EntryKind::Blob | EntryKind::Exec)
148}
149
150type Changed = (String, Option<FileEntry>, Option<FileEntry>);
151
152/// The steps that make the merge, from the files the pull request
153/// (`ours`) and the base branch (`theirs`) changed since they last agreed.
154pub(crate) fn plan(ours: &[Changed], theirs: &[Changed]) -> Plan {
155 let their: HashMap<&str, &Changed> = theirs.iter().map(|change| (change.0.as_str(), change)).collect();
156 let paths = |changes: &[Changed]| changes.iter().map(|change| change.0.clone()).collect::<Vec<_>>();
157 // A file on one side where the other has a directory.
158 let ours_paths = paths(ours);
159 if let Some(met) = overlapping(&ours_paths, &paths(theirs)).into_iter().find(|path| !their.contains_key(path.as_str()) || !ours_paths.contains(path)) {
160 return Plan::Unsupported(format!("{met} is a file on one side and a directory on the other"));
161 }
162 let mut steps = Vec::new();
163 let mut conflicts = Vec::new();
164 for (path, base, mine) in ours {
165 let Some((_, _, other)) = their.get(path.as_str()) else {
166 steps.push((path.clone(), Step::Take(mine.clone())));
167 continue;
168 };
169 // Both made it the same, or the base branch's is already there.
170 if mine == other {
171 continue;
172 }
173 let (Some(mine), Some(other)) = (mine, other) else {
174 return Plan::Unsupported(format!("{path} was deleted or renamed on one side and changed on the other"));
175 };
176 let base_kind = base.as_ref().map(|(kind, _)| *kind);
177 let kind = if mine.0 == other.0 {
178 mine.0
179 } else if base_kind == Some(mine.0) {
180 other.0
181 } else if base_kind == Some(other.0) {
182 mine.0
183 } else {
184 conflicts.push(path.clone());
185 continue;
186 };
187 if mine.1 == other.1 {
188 steps.push((path.clone(), Step::Take(Some((kind, mine.1.clone())))));
189 continue;
190 }
191 if !text_kind(mine.0) || !text_kind(other.0) || base_kind.is_some_and(|kind| !text_kind(kind)) {
192 conflicts.push(path.clone());
193 continue;
194 }
195 steps.push((
196 path.clone(),
197 Step::Content { kind, base: base.as_ref().map(|(_, hash)| hash.clone()), ours: mine.1.clone(), theirs: other.1.clone() },
198 ));
199 }
200 if conflicts.is_empty() { Plan::Steps(steps) } else { Plan::Conflict(conflicts) }
201}
202
203/// What GitHub's test merge commits say.
204pub(crate) fn message(head: &str, base: &str) -> String {
205 format!("Merge {head} into {base}")
206}
207
208/// A merge, worked out.
209enum Made {
210 Merged { commit: String, objects: Vec<(ObjectKind, Vec<u8>)> },
211 Conflict(Vec<String>),
212 Unsupported(String),
213}
214
215/// A blob's text, for merging: `Err(true)` when it is binary, `Err(false)`
216/// when it is too large or missing.
217fn as_text(bytes: Option<Vec<u8>>) -> std::result::Result<String, bool> {
218 let bytes = bytes.ok_or(false)?;
219 if bytes.len() > MAX_MERGE_BYTES {
220 return Err(false);
221 }
222 if bytes.contains(&0) {
223 return Err(true);
224 }
225 String::from_utf8(bytes).map_err(|_| true)
226}
227
228/// When a merge of two commits says it was made: the later of their
229/// dates, so that the same two always make the same commit, however many
230/// events ask for it, and a merge ref that is already right stays.
231fn merged_at(head: &g1t_contracts::repos::Commit, base: &g1t_contracts::repos::Commit) -> u64 {
232 let at = |commit: &g1t_contracts::repos::Commit| parse_rfc3339(&commit.authored_at).unwrap_or(0) / 1000;
233 at(head).max(at(base))
234}
235
236/// Merges `head` into `base`, both in `git`.
237async fn make<R: GitRepo>(git: &R, base: &str, head: &str) -> Result<Made> {
238 let (head_log, base_log) = try_join(git.log(head, MAX_ANCESTRY), git.log(base, MAX_ANCESTRY)).await?;
239 let (Some(head_commit), Some(base_commit)) = (head_log.first(), base_log.first()) else {
240 return Ok(Made::Unsupported("the head or the base commit could not be read".to_owned()));
241 };
242 let seconds = merged_at(head_commit, base_commit);
243 let mut objects: Vec<(ObjectKind, Vec<u8>)> = Vec::new();
244 let tree = if descends_from(git, &head_log, base).await? {
245 head_commit.tree_hash.clone()
246 } else {
247 let shared = base_log.iter().map(|commit| commit.hash.clone()).collect();
248 let merge_base = nearest_ancestor_in(git, &head_log, &shared).await?;
249 let Some(merge_base_tree) = merge_base.and_then(|hash| base_log.iter().find(|commit| commit.hash == hash)).map(|commit| commit.tree_hash.clone()) else {
250 return Ok(Made::Unsupported("g1t could not find where the head left the base branch".to_owned()));
251 };
252 let ((ours, ours_cut), (theirs, theirs_cut)) = try_join(
253 changed_entries(git, Some(&merge_base_tree), &head_commit.tree_hash),
254 changed_entries(git, Some(&merge_base_tree), &base_commit.tree_hash),
255 )
256 .await?;
257 if ours_cut || theirs_cut {
258 return Ok(Made::Unsupported("the change is too large to merge without a sandbox".to_owned()));
259 }
260 let steps = match plan(&ours, &theirs) {
261 Plan::Steps(steps) => steps,
262 Plan::Conflict(paths) => return Ok(Made::Conflict(paths)),
263 Plan::Unsupported(why) => return Ok(Made::Unsupported(why)),
264 };
265 // Files both changed, merged line by line.
266 let read = try_join_all(steps.iter().map(|(_, step)| async move {
267 let Step::Content { base, ours, theirs, .. } = step else { return Ok(None) };
268 let base = async {
269 match base {
270 Some(hash) => git.read_blob(hash).await,
271 None => Ok(Some(Vec::new())),
272 }
273 };
274 let (base, (ours, theirs)) = try_join(base, try_join(git.read_blob(ours), git.read_blob(theirs))).await?;
275 Ok::<_, worker::Error>(Some((base, ours, theirs)))
276 }))
277 .await?;
278 let mut changes = Vec::new();
279 let mut conflicts = Vec::new();
280 for ((path, step), texts) in steps.into_iter().zip(read) {
281 match (step, texts) {
282 (Step::Take(entry), _) => changes.push(Change { path, entry }),
283 (Step::Content { kind, .. }, Some((base, ours, theirs))) => {
284 let texts = (as_text(base), as_text(ours), as_text(theirs));
285 let (Ok(base), Ok(ours), Ok(theirs)) = texts else {
286 if matches!(texts, (Err(true), _, _) | (_, Err(true), _) | (_, _, Err(true))) {
287 conflicts.push(path);
288 continue;
289 }
290 return Ok(Made::Unsupported(format!("{path} is too large to merge without a sandbox")));
291 };
292 match merge_text(&base, &ours, &theirs) {
293 Some(merged) => {
294 let blob = merged.into_bytes();
295 let id = object_id(ObjectKind::Blob, &blob);
296 objects.push((ObjectKind::Blob, blob));
297 changes.push(Change { path, entry: Some((kind, id)) });
298 }
299 None => conflicts.push(path),
300 }
301 }
302 (Step::Content { .. }, None) => {}
303 }
304 }
305 if !conflicts.is_empty() {
306 return Ok(Made::Conflict(conflicts));
307 }
308 let dirs: BTreeSet<String> = changes.iter().flat_map(|change| ancestors(&change.path).map(str::to_owned)).collect();
309 let trees: HashMap<String, Vec<TreeEntry>> = read_dirs(git, &base_commit.tree_hash, &dirs).await?.into_values().collect();
310 match merge_tree(&base_commit.tree_hash, &trees, &changes) {
311 Ok(merged) => {
312 objects.extend(merged.objects.into_iter().map(|bytes| (ObjectKind::Tree, bytes)));
313 merged.tree
314 }
315 Err(why) => return Ok(Made::Unsupported(why)),
316 }
317 };
318 let commit = commit_object(
319 &tree,
320 &[base, head],
321 &Signature { name: g1t_contracts::system::USERNAME, email: g1t_contracts::system::EMAIL, seconds },
322 &message(head, base),
323 );
324 let id = object_id(ObjectKind::Commit, &commit);
325 objects.push((ObjectKind::Commit, commit));
326 Ok(Made::Merged { commit: id, objects })
327}
328
329fn unavailable(reason: impl Into<String>) -> Result<PullMergeRef> {
330 Ok(PullMergeRef::Unavailable { reason: reason.into() })
331}
332
333impl<S: GitStore> Repos<S> {
334 /// `pull_merge_ref` (contracts `PullMergeRefArgs`).
335 pub(crate) async fn pull_merge_ref(&self, a: PullMergeRefArgs) -> Result<PullMergeRef> {
336 let Some(target) = self.registry.by_id(&a.repo_id).await? else {
337 return unavailable("the repository is gone");
338 };
339 if let Some((_, message)) = crate::lifecycle::read_only_refusal(&target) {
340 return unavailable(message);
341 }
342 let target = match self.unpaused(target).await? {
343 Ok(target) => target,
344 Err((_, message)) => return unavailable(message),
345 };
346 let git = self.store.open(&store_key(&target)).await?;
347 let refs = refs::all(&git.access(Scope::Read).await?).await?;
348 let find = |refs: &[(String, String)], name: &str| refs.iter().find(|(known, _)| known == name).map(|(_, hash)| hash.clone());
349 let (head_ref, merge_ref) = (pull_head_ref(a.number), pull_merge_ref(a.number));
350 let base_branch = a.target_branch.clone().filter(|branch| !branch.is_empty()).unwrap_or_else(|| target.default_branch.clone());
351 let Some(base) = find(&refs, &format!("refs/heads/{base_branch}")) else {
352 return unavailable(format!("{base_branch} has no commits"));
353 };
354 let head = a.head.clone();
355
356 // The head, kept in the repository, its objects brought from the fork.
357 let held_head = find(&refs, &head_ref);
358 if held_head.as_deref() != Some(head.as_str()) {
359 let write = git.access(Scope::Write).await?;
360 let moved = if !git.log(&head, 1).await?.is_empty() {
361 land::push_ref(&write, &head_ref, held_head.as_deref(), &head, Some(land::EMPTY_PACK.to_vec())).await?
362 } else {
363 let source = match self.registry.by_id(&a.source_id).await? {
364 Some(source) if source.id != target.id => source,
365 _ => return unavailable("the head commit is not in the repository"),
366 };
367 // A working copy removed after its pull request closed is made again.
368 self.live(&source).await?;
369 let source_read = self.store.open(&store_key(&source)).await?.access(Scope::Read).await?;
370 let command = (head_ref.clone(), held_head.clone(), head.clone());
371 land::copy_refs(&source_read, &write, &[command], std::slice::from_ref(&head), std::slice::from_ref(&base)).await?
372 };
373 self.refs_moved(&target.id).await;
374 if let Err(reason) = moved {
375 return unavailable(format!("{head_ref} could not be kept: {reason}"));
376 }
377 }
378
379 let held_merge = find(&refs, &merge_ref);
380 match make(&git, &base, &head).await? {
381 Made::Unsupported(reason) => unavailable(reason),
382 Made::Conflict(paths) => {
383 // No merge commit, so no merge ref, as on GitHub.
384 if let Some(old) = &held_merge {
385 let write = git.access(Scope::Write).await?;
386 if let Err(reason) = land::push_ref(&write, &merge_ref, Some(old), ZERO_ID, None).await? {
387 worker::console_warn!("{merge_ref} of {} not removed: {reason}", target.id);
388 }
389 self.refs_moved(&target.id).await;
390 }
391 Ok(PullMergeRef::Conflict { head, base, paths })
392 }
393 // Made the same for the same head and base: there already when
394 // an earlier event made it.
395 Made::Merged { commit, .. } if held_merge.as_deref() == Some(commit.as_str()) => {
396 Ok(PullMergeRef::Merged { head, base, merge: commit })
397 }
398 Made::Merged { commit, objects } => {
399 let write = git.access(Scope::Write).await?;
400 let pushed = land::push_ref(&write, &merge_ref, held_merge.as_deref(), &commit, Some(write_pack(&objects))).await?;
401 self.refs_moved(&target.id).await;
402 if let Err(reason) = pushed {
403 // Another event for the same pair made it meanwhile.
404 let refs = refs::all(&git.access(Scope::Read).await?).await?;
405 if find(&refs, &merge_ref).as_deref() != Some(commit.as_str()) {
406 return unavailable(format!("{merge_ref} could not be moved: {reason}"));
407 }
408 }
409 Ok(PullMergeRef::Merged { head, base, merge: commit })
410 }
411 }
412 }
413}
414
415#[cfg(test)]
416mod tests {
417 use super::*;
418
419 fn blob(hash: &str) -> Option<FileEntry> {
420 Some((EntryKind::Blob, hash.to_owned()))
421 }
422
423 fn changed(path: &str, base: Option<FileEntry>, now: Option<FileEntry>) -> Changed {
424 (path.to_owned(), base, now)
425 }
426
427 #[test]
428 fn changes_to_different_lines_merge() {
429 let base = "a\nb\nc\nd\ne\n";
430 let ours = "A\nb\nc\nd\ne\n";
431 let theirs = "a\nb\nc\nd\nE\n";
432 assert_eq!(merge_text(base, ours, theirs).as_deref(), Some("A\nb\nc\nd\nE\n"));
433 // Lines added at either end, and one taken out in the middle.
434 assert_eq!(merge_text(base, "top\na\nb\nc\nd\ne\n", "a\nb\nd\ne\nend\n").as_deref(), Some("top\na\nb\nd\ne\nend\n"));
435 }
436
437 #[test]
438 fn the_same_change_on_both_sides_merges() {
439 let base = "a\nb\nc\n";
440 assert_eq!(merge_text(base, "a\nB\nc\n", "a\nB\nc\n").as_deref(), Some("a\nB\nc\n"));
441 }
442
443 #[test]
444 fn different_changes_to_the_same_or_touching_lines_conflict() {
445 let base = "a\nb\nc\nd\n";
446 assert_eq!(merge_text(base, "a\nX\nc\nd\n", "a\nY\nc\nd\n"), None);
447 // Neighbouring lines, with no unchanged line between: git conflicts.
448 assert_eq!(merge_text(base, "a\nX\nc\nd\n", "a\nb\nY\nd\n"), None);
449 // Both added different files from nothing.
450 assert_eq!(merge_text("", "one\n", "two\n"), None);
451 // One unchanged line between them is enough.
452 assert_eq!(merge_text(base, "X\nb\nc\nd\n", "a\nb\nY\nd\n").as_deref(), Some("X\nb\nY\nd\n"));
453 }
454
455 #[test]
456 fn a_missing_final_newline_is_kept() {
457 assert_eq!(merge_text("a\nb\nc", "A\nb\nc", "a\nb\nC").as_deref(), Some("A\nb\nC"));
458 }
459
460 #[test]
461 fn files_only_one_side_changed_are_taken_from_it() {
462 let ours = [changed("src/a.rs", blob("1"), blob("2")), changed("gone.md", blob("3"), None)];
463 let theirs = [changed("src/b.rs", blob("4"), blob("5"))];
464 assert_eq!(
465 plan(&ours, &theirs),
466 Plan::Steps(vec![("src/a.rs".into(), Step::Take(blob("2"))), ("gone.md".into(), Step::Take(None))])
467 );
468 }
469
470 #[test]
471 fn a_file_both_changed_is_merged_by_content() {
472 let ours = [changed("a", blob("1"), blob("2")), changed("same", blob("1"), blob("9"))];
473 let theirs = [changed("a", blob("1"), blob("3")), changed("same", blob("1"), blob("9"))];
474 assert_eq!(
475 plan(&ours, &theirs),
476 Plan::Steps(vec![(
477 "a".into(),
478 Step::Content { kind: EntryKind::Blob, base: Some("1".into()), ours: "2".into(), theirs: "3".into() }
479 )])
480 );
481 // One side made it executable, the other changed it.
482 let ours = [changed("run", blob("1"), Some((EntryKind::Exec, "1".into())))];
483 let theirs = [changed("run", blob("1"), blob("2"))];
484 assert_eq!(
485 plan(&ours, &theirs),
486 Plan::Steps(vec![(
487 "run".into(),
488 Step::Content { kind: EntryKind::Exec, base: Some("1".into()), ours: "1".into(), theirs: "2".into() }
489 )])
490 );
491 }
492
493 #[test]
494 fn what_cannot_merge_says_so() {
495 // A submodule moved two ways.
496 let ours = [changed("vendor", Some((EntryKind::Gitlink, "1".into())), Some((EntryKind::Gitlink, "2".into())))];
497 let theirs = [changed("vendor", Some((EntryKind::Gitlink, "1".into())), Some((EntryKind::Gitlink, "3".into())))];
498 assert_eq!(plan(&ours, &theirs), Plan::Conflict(vec!["vendor".into()]));
499 // Deleted on one side, changed on the other: maybe a rename.
500 let ours = [changed("a", blob("1"), None)];
501 let theirs = [changed("a", blob("1"), blob("2"))];
502 assert!(matches!(plan(&ours, &theirs), Plan::Unsupported(_)));
503 // A file against a directory.
504 let ours = [changed("a", None, blob("1"))];
505 let theirs = [changed("a/b", None, blob("2"))];
506 assert!(matches!(plan(&ours, &theirs), Plan::Unsupported(_)));
507 }
508
509 #[test]
510 fn binary_files_are_told_apart_from_text() {
511 assert_eq!(as_text(Some(b"text\n".to_vec())), Ok("text\n".to_owned()));
512 assert_eq!(as_text(Some(vec![0, 1, 2])), Err(true));
513 assert_eq!(as_text(None), Err(false));
514 assert_eq!(as_text(Some(vec![b'a'; MAX_MERGE_BYTES + 1])), Err(false));
515 }
516
517 /// A store of whole objects, made in the test: commits by hash, trees
518 /// and blobs by their real ids.
519 #[derive(Default)]
520 struct Store {
521 commits: HashMap<String, g1t_contracts::repos::Commit>,
522 trees: HashMap<String, Vec<TreeEntry>>,
523 blobs: HashMap<String, Vec<u8>>,
524 }
525
526 impl Store {
527 fn blob(&mut self, text: &str) -> String {
528 let id = object_id(ObjectKind::Blob, text.as_bytes());
529 self.blobs.insert(id.clone(), text.as_bytes().to_vec());
530 id
531 }
532
533 /// A tree of `files` (`path`, text), its subtrees made as needed.
534 fn tree(&mut self, files: &[(&str, &str)]) -> String {
535 let mut here: Vec<TreeEntry> = Vec::new();
536 let mut dirs: std::collections::BTreeMap<&str, Vec<(&str, &str)>> = Default::default();
537 for (path, text) in files {
538 match path.split_once('/') {
539 Some((dir, rest)) => dirs.entry(dir).or_default().push((rest, text)),
540 None => {
541 let hash = self.blob(text);
542 here.push(TreeEntry { name: (*path).to_owned(), hash, kind: EntryKind::Blob });
543 }
544 }
545 }
546 for (dir, files) in dirs {
547 let hash = self.tree(&files);
548 here.push(TreeEntry { name: dir.to_owned(), hash, kind: EntryKind::Tree });
549 }
550 let id = object_id(ObjectKind::Tree, &crate::catch_up::encode_entries(&here));
551 self.trees.insert(id.clone(), here);
552 id
553 }
554
555 fn commit(&mut self, hash: &str, parents: &[&str], files: &[(&str, &str)]) {
556 let tree_hash = self.tree(files);
557 self.commits.insert(
558 hash.to_owned(),
559 g1t_contracts::repos::Commit {
560 hash: hash.to_owned(),
561 tree_hash,
562 message: hash.to_owned(),
563 author: g1t_contracts::repos::Signature { name: "a".into(), email: "a@example.com".into() },
564 parents: parents.iter().map(|&p| p.to_owned()).collect(),
565 authored_at: String::new(),
566 },
567 );
568 }
569
570 /// The files of a tree in `objects` or the store, by path.
571 fn files(&self, tree: &str, written: &HashMap<String, Vec<TreeEntry>>, blobs: &HashMap<String, Vec<u8>>, prefix: &str) -> Vec<(String, String)> {
572 let entries = written.get(tree).or_else(|| self.trees.get(tree)).expect("tree");
573 let mut out = Vec::new();
574 for entry in entries {
575 let path = format!("{prefix}{}", entry.name);
576 if entry.kind == EntryKind::Tree {
577 out.extend(self.files(&entry.hash, written, blobs, &format!("{path}/")));
578 } else {
579 let bytes = blobs.get(&entry.hash).or_else(|| self.blobs.get(&entry.hash)).expect("blob");
580 out.push((path, String::from_utf8(bytes.clone()).unwrap()));
581 }
582 }
583 out
584 }
585 }
586
587 impl GitRepo for Store {
588 async fn access(&self, _scope: Scope) -> Result<g1t_contracts::repos::GitAccess> {
589 unimplemented!()
590 }
591 async fn branches(&self) -> Result<Vec<g1t_contracts::repos::Branch>> {
592 Ok(Vec::new())
593 }
594 async fn log(&self, git_ref: &str, limit: u32) -> Result<Vec<g1t_contracts::repos::Commit>> {
595 let mut out = Vec::new();
596 let mut at = self.commits.get(git_ref);
597 while let Some(commit) = at.filter(|_| (out.len() as u32) < limit) {
598 out.push(commit.clone());
599 at = commit.parents.first().and_then(|parent| self.commits.get(parent));
600 }
601 Ok(out)
602 }
603 async fn parents(&self, commit_hash: &str) -> Result<Option<Vec<String>>> {
604 Ok(self.commits.get(commit_hash).map(|commit| commit.parents.clone()))
605 }
606 async fn read_tree(&self, tree_hash: &str) -> Result<Option<Vec<TreeEntry>>> {
607 Ok(self.trees.get(tree_hash).cloned())
608 }
609 async fn read_blob(&self, blob_hash: &str) -> Result<Option<Vec<u8>>> {
610 Ok(self.blobs.get(blob_hash).cloned())
611 }
612 async fn read_file(&self, _git_ref: &str, _path: &str) -> Result<Option<Vec<u8>>> {
613 Ok(None)
614 }
615 async fn fork(&self, _target_key: &str) -> Result<()> {
616 Ok(())
617 }
618 }
619
620 fn block_on<F: std::future::Future>(future: F) -> F::Output {
621 let mut future = std::pin::pin!(future);
622 let mut cx = std::task::Context::from_waker(std::task::Waker::noop());
623 loop {
624 if let std::task::Poll::Ready(output) = future.as_mut().poll(&mut cx) {
625 return output;
626 }
627 }
628 }
629
630 /// The merge's files, read from the objects it wrote and the store.
631 fn merged_files(store: &Store, made: Made, base: &str, head: &str) -> Vec<(String, String)> {
632 let Made::Merged { commit, objects } = made else { panic!("not merged") };
633 let mut trees = HashMap::new();
634 let mut blobs = HashMap::new();
635 let mut tree = None;
636 for (kind, bytes) in &objects {
637 let id = object_id(*kind, bytes);
638 match kind {
639 ObjectKind::Tree => {
640 let entries = g1t_scan::pack::parse_tree(bytes)
641 .into_iter()
642 .map(|item| TreeEntry {
643 kind: if item.mode == "40000" { EntryKind::Tree } else { EntryKind::Blob },
644 name: item.name,
645 hash: item.id,
646 })
647 .collect();
648 trees.insert(id, entries);
649 }
650 ObjectKind::Blob => {
651 blobs.insert(id, bytes.clone());
652 }
653 ObjectKind::Commit => {
654 assert_eq!(id, commit);
655 let text = String::from_utf8(bytes.clone()).unwrap();
656 assert!(text.contains(&format!("parent {base}\nparent {head}\n")), "{text}");
657 assert!(text.contains(&format!("\n\nMerge {head} into {base}\n")), "{text}");
658 tree = text.lines().next().and_then(|line| line.strip_prefix("tree ")).map(str::to_owned);
659 }
660 ObjectKind::Tag => unreachable!(),
661 }
662 }
663 let mut files = store.files(&tree.expect("a commit"), &trees, &blobs, "");
664 files.sort();
665 files
666 }
667
668 #[test]
669 fn a_head_behind_its_base_merges_both_sides() {
670 let mut store = Store::default();
671 store.commit("m", &[], &[("README.md", "hi\n"), ("src/lib.rs", "a\nb\nc\nd\ne\n")]);
672 store.commit("h", &["m"], &[("README.md", "hi\n"), ("src/lib.rs", "A\nb\nc\nd\ne\n"), ("src/new.rs", "new\n")]);
673 store.commit("b", &["m"], &[("README.md", "hello\n"), ("src/lib.rs", "a\nb\nc\nd\nE\n")]);
674 let made = block_on(make(&store, "b", "h")).unwrap();
675 assert_eq!(
676 merged_files(&store, made, "b", "h"),
677 [
678 ("README.md".to_owned(), "hello\n".to_owned()),
679 ("src/lib.rs".to_owned(), "A\nb\nc\nd\nE\n".to_owned()),
680 ("src/new.rs".to_owned(), "new\n".to_owned()),
681 ]
682 );
683 }
684
685 #[test]
686 fn a_head_up_to_date_merges_to_its_own_files() {
687 let mut store = Store::default();
688 store.commit("b", &[], &[("a", "1\n")]);
689 store.commit("h", &["b"], &[("a", "2\n")]);
690 let made = block_on(make(&store, "b", "h")).unwrap();
691 assert_eq!(merged_files(&store, made, "b", "h"), [("a".to_owned(), "2\n".to_owned())]);
692 }
693
694 #[test]
695 fn the_same_head_and_base_always_make_the_same_commit() {
696 let mut store = Store::default();
697 store.commit("m", &[], &[("a", "1\n"), ("b", "x\n")]);
698 store.commit("h", &["m"], &[("a", "2\n"), ("b", "x\n")]);
699 store.commit("b", &["m"], &[("a", "1\n"), ("b", "y\n")]);
700 store.commits.get_mut("h").unwrap().authored_at = "2026-10-12T03:00:00.000Z".into();
701 store.commits.get_mut("b").unwrap().authored_at = "2026-10-12T04:00:00.000Z".into();
702 let id = |made: Made| match made {
703 Made::Merged { commit, objects } => (commit, String::from_utf8(objects.last().unwrap().1.clone()).unwrap()),
704 _ => panic!("not merged"),
705 };
706 let (first, text) = id(block_on(make(&store, "b", "h")).unwrap());
707 assert_eq!(id(block_on(make(&store, "b", "h")).unwrap()).0, first);
708 // Dated as the later of the two.
709 assert!(text.contains(" 1791777600 +0000\n"), "{text}");
710 }
711
712 #[test]
713 fn a_conflict_makes_no_merge() {
714 let mut store = Store::default();
715 store.commit("m", &[], &[("a", "1\n"), ("b", "x\n")]);
716 store.commit("h", &["m"], &[("a", "2\n"), ("b", "x\n")]);
717 store.commit("b", &["m"], &[("a", "3\n"), ("b", "y\n")]);
718 let Made::Conflict(paths) = block_on(make(&store, "b", "h")).unwrap() else { panic!("no conflict") };
719 assert_eq!(paths, ["a"]);
720 }
721
722 #[test]
723 fn the_merge_commit_says_what_github_s_does() {
724 assert_eq!(message("abc", "def"), "Merge abc into def");
725 assert_eq!(pull_merge_ref(7), "refs/pull/7/merge");
726 assert_eq!(pull_head_ref(7), "refs/pull/7/head");
727 }
728}