Sign in

flagon-io/g1t

public

Where people and agents ship software together. The open-source git platform for the whole job: issues, agents, checks and deploys to the edge.

gitagentscloudflarerustforgemcp

g1t/services/repos/src/catch_up.rs

760 lines30,109 bytesCodeBlame

Pick any line to see why it is the way it is: the commit, the pull request and issue it came from, and what the agent was thinking.

Catching up with main takes seconds when the two sides touched different files1//! Bringing a pull request up to date with the branch it would merge into,
2//! without a sandbox, when that is safe.
3//!
4//! When the pull request and the default branch changed different files
5//! since they last agreed, the merge cannot conflict, and its result is
6//! known without merging any file: the default branch's tree, with the
7//! files the pull request changed taken from the pull request. Only the
8//! trees on the way to those files change. They are rebuilt here, with one
9//! merge commit on top whose parents are the pull request's head and the
10//! default branch's head, written as a pack of whole objects and pushed to
11//! the pull request's branch, if it is still where it was.
12//!
13//! When both sides changed a file, the merge needs git itself (and maybe an
14//! agent), so the answer is that a sandbox is needed, and nothing is pushed.
15
16use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
17
18use futures_util::future::{try_join, try_join_all};
19use g1t_contracts::audit::{AuditActor, NewAuditEntry, Surface};
20use g1t_contracts::credentials::Decision;
21use g1t_contracts::repos::{
22 EntryKind, NeedsAgentReason, PullBranchUpdate, RepoPath, TreeEntry, UpdatePullBranchArgs,
23};
24use g1t_contracts::{FailureCode, Outcome};
25use g1t_kit::now_ms;
26use g1t_scan::pack::{ObjectKind, TreeItem, encode_tree, extend_pack, object_id, write_pack};
27use worker::Result;
28
29use crate::registry::{can_read, can_write, store_key};
30use crate::store::{GitRepo, GitStore, Scope};
31use crate::{MAX_ANCESTRY, Repos, UNVERIFIED, descends_from, diff, land, nearest_ancestor_in, not_found};
32
33/// The mode git writes for an entry of each kind.
34fn mode(kind: EntryKind) -> &'static str {
35 match kind {
36 EntryKind::Tree => "40000",
37 EntryKind::Blob => "100644",
38 EntryKind::Exec => "100755",
39 EntryKind::Symlink => "120000",
40 EntryKind::Gitlink => "160000",
41 }
42}
43
44/// Git orders a tree's entries by name, comparing a subtree's name as if
45/// it ended in `/`.
46fn sort_key(entry: &TreeEntry) -> Vec<u8> {
47 let mut key = entry.name.as_bytes().to_vec();
48 if entry.kind == EntryKind::Tree {
49 key.push(b'/');
50 }
51 key
52}
53
54/// A tree object's bytes, its entries in git's order.
55pub(crate) fn encode_entries(entries: &[TreeEntry]) -> Vec<u8> {
56 let mut sorted: Vec<&TreeEntry> = entries.iter().collect();
57 sorted.sort_by_key(|entry| sort_key(entry));
58 let items: Vec<TreeItem> = sorted
59 .into_iter()
60 .map(|entry| TreeItem {
61 mode: mode(entry.kind).to_owned(),
62 name: entry.name.clone(),
63 id: entry.hash.clone(),
64 })
65 .collect();
66 encode_tree(&items)
67}
68
69/// The directories above a path, nearest the root first: `a/b/c` is in
70/// `a` and `a/b`.
71fn ancestors(path: &str) -> impl Iterator<Item = &str> {
72 path.match_indices('/').map(move |(at, _)| &path[..at])
73}
74
75/// The paths at which the two sides' changes meet, so that the merge is not
76/// a matter of taking each side's files: a file both changed, or a file on
77/// one side where the other has a directory (a file `a` against `a/b`).
78pub(crate) fn overlapping(ours: &[String], theirs: &[String]) -> Vec<String> {
79 let their_files: HashSet<&str> = theirs.iter().map(String::as_str).collect();
80 let their_dirs: HashSet<&str> = theirs.iter().flat_map(|path| ancestors(path)).collect();
81 let mut met: BTreeSet<String> = BTreeSet::new();
82 for path in ours {
83 if their_files.contains(path.as_str()) || their_dirs.contains(path.as_str()) {
84 met.insert(path.clone());
85 }
86 for dir in ancestors(path) {
87 if their_files.contains(dir) {
88 met.insert(dir.to_owned());
89 }
90 }
91 }
92 met.into_iter().collect()
93}
94
95/// One file the pull request changed, as it is on the pull request: its
96/// kind and blob, or `None` when it deleted it.
97#[derive(Clone, Debug)]
98pub(crate) struct Change {
99 pub path: String,
100 pub entry: Option<(EntryKind, String)>,
101}
102
103/// The merged tree's id, and the tree objects written for it.
104#[derive(Debug)]
105pub(crate) struct Merged {
106 pub tree: String,
107 pub objects: Vec<Vec<u8>>,
108}
109
110enum Node {
111 Leaf(EntryKind, String),
112 /// A subtree left as it is.
113 Subtree(String),
114 /// A subtree being changed.
115 Dir(Dir),
116}
117
118#[derive(Default)]
119struct Dir {
120 entries: BTreeMap<String, Node>,
121}
122
123/// A tree, ready to change. Its entries are checked to write back to
124/// exactly its id: a tree holding something this cannot write, such as an
125/// unusual file mode, is refused rather than changed.
126fn load(id: &str, trees: &HashMap<String, Vec<TreeEntry>>) -> std::result::Result<Dir, String> {
127 let entries = trees
128 .get(id)
129 .ok_or_else(|| format!("tree {id} was not read"))?;
130 if object_id(ObjectKind::Tree, &encode_entries(entries)) != id {
131 return Err(format!("tree {id} holds entries g1t cannot write back exactly"));
132 }
133 Ok(Dir {
134 entries: entries
135 .iter()
136 .map(|entry| {
137 let node = match entry.kind {
138 EntryKind::Tree => Node::Subtree(entry.hash.clone()),
139 kind => Node::Leaf(kind, entry.hash.clone()),
140 };
141 (entry.name.clone(), node)
142 })
143 .collect(),
144 })
145}
146
147/// The directory at `node`, read if it was not yet.
148fn open<'a>(
149 node: &'a mut Node,
150 trees: &HashMap<String, Vec<TreeEntry>>,
151) -> std::result::Result<&'a mut Dir, String> {
152 if let Node::Subtree(id) = node {
153 *node = Node::Dir(load(id, trees)?);
154 }
155 match node {
156 Node::Dir(dir) => Ok(dir),
157 _ => Err("a file is where a directory was expected".to_owned()),
158 }
159}
160
161/// Removes the file at `parts`, and any directory that leaves empty.
162fn remove(
163 dir: &mut Dir,
164 parts: &[&str],
165 trees: &HashMap<String, Vec<TreeEntry>>,
166) -> std::result::Result<(), String> {
167 let (name, rest) = parts.split_first().ok_or("an empty path")?;
168 if rest.is_empty() {
169 return match dir.entries.get(*name) {
170 Some(Node::Leaf(..)) => {
171 dir.entries.remove(*name);
172 Ok(())
173 }
174 Some(_) => Err(format!("{name} is a directory, not a file")),
175 None => Err(format!("{name} is not there to remove")),
176 };
177 }
178 let child = dir
179 .entries
180 .get_mut(*name)
181 .ok_or_else(|| format!("{name} is not there"))?;
182 let inner = open(child, trees)?;
183 remove(inner, rest, trees)?;
184 if inner.entries.is_empty() {
185 dir.entries.remove(*name);
186 }
187 Ok(())
188}
189
190/// Puts a file at `parts`, making the directories it needs.
191fn insert(
192 dir: &mut Dir,
193 parts: &[&str],
194 kind: EntryKind,
195 hash: &str,
196 trees: &HashMap<String, Vec<TreeEntry>>,
197) -> std::result::Result<(), String> {
198 let (name, rest) = parts.split_first().ok_or("an empty path")?;
199 if rest.is_empty() {
200 if matches!(dir.entries.get(*name), Some(Node::Subtree(_) | Node::Dir(_))) {
201 return Err(format!("{name} is a directory, not a file"));
202 }
203 dir.entries.insert((*name).to_owned(), Node::Leaf(kind, hash.to_owned()));
204 return Ok(());
205 }
206 let child = dir
207 .entries
208 .entry((*name).to_owned())
209 .or_insert_with(|| Node::Dir(Dir::default()));
210 insert(open(child, trees)?, rest, kind, hash, trees)
211}
212
213/// Writes a changed directory and those in it; returns its id.
214fn write(dir: Dir, objects: &mut Vec<Vec<u8>>) -> String {
215 let mut entries = Vec::with_capacity(dir.entries.len());
216 for (name, node) in dir.entries {
217 let (kind, hash) = match node {
218 Node::Leaf(kind, hash) => (kind, hash),
219 Node::Subtree(hash) => (EntryKind::Tree, hash),
220 // Git keeps no empty directories.
221 Node::Dir(inner) if inner.entries.is_empty() => continue,
222 Node::Dir(inner) => (EntryKind::Tree, write(inner, objects)),
223 };
224 entries.push(TreeEntry { name, hash, kind });
225 }
226 let bytes = encode_entries(&entries);
227 let id = object_id(ObjectKind::Tree, &bytes);
228 objects.push(bytes);
229 id
230}
231
232/// The tree of `base_root` with `changes` applied: deletions first, so a
233/// file can take the place of a directory the pull request emptied.
234/// `trees` holds every tree of the base on the way to a changed path.
235pub(crate) fn merge_tree(
236 base_root: &str,
237 trees: &HashMap<String, Vec<TreeEntry>>,
238 changes: &[Change],
239) -> std::result::Result<Merged, String> {
240 let mut root = load(base_root, trees)?;
241 for change in changes.iter().filter(|change| change.entry.is_none()) {
242 let parts: Vec<&str> = change.path.split('/').collect();
243 remove(&mut root, &parts, trees).map_err(|why| format!("{}: {why}", change.path))?;
244 }
245 for change in changes {
246 if let Some((kind, hash)) = &change.entry {
247 let parts: Vec<&str> = change.path.split('/').collect();
248 insert(&mut root, &parts, *kind, hash, trees)
249 .map_err(|why| format!("{}: {why}", change.path))?;
250 }
251 }
252 let mut objects = Vec::new();
253 let tree = write(root, &mut objects);
254 // A subtree that came out as it was is already stored.
255 let mut seen = HashSet::new();
256 objects.retain(|bytes| seen.insert(object_id(ObjectKind::Tree, bytes)));
257 Ok(Merged { tree, objects })
258}
259
260/// Who a commit is by, and when.
261pub(crate) struct Signature<'a> {
262 pub name: &'a str,
263 pub email: &'a str,
264 /// Seconds since the epoch, in UTC.
265 pub seconds: u64,
266}
267
268/// A commit object's bytes, authored and committed by `by`.
269pub(crate) fn commit_object(tree: &str, parents: &[&str], by: &Signature, message: &str) -> Vec<u8> {
270 let mut out = format!("tree {tree}\n");
271 for parent in parents {
272 out.push_str(&format!("parent {parent}\n"));
273 }
274 // Git takes everything up to `<` as the name.
275 let name: String = by.name.chars().filter(|c| !matches!(c, '<' | '>' | '\n')).collect();
276 let email: String = by.email.chars().filter(|c| !matches!(c, '<' | '>' | '\n')).collect();
277 let line = format!("{name} <{email}> {} +0000", by.seconds);
278 out.push_str(&format!("author {line}\ncommitter {line}\n\n{message}\n"));
279 out.into_bytes()
280}
281
282/// What the merge commit says.
283pub(crate) fn merge_message(base: &str, branch: &str, number: u32) -> String {
284 if branch == base {
285 // A fork carries its change on a branch named like the default.
286 format!("Merge {base} into pull request #{number}")
287 } else {
288 format!("Merge {base} into {branch}")
289 }
290}
291
292/// The trees at `dirs` (and the root, `""`) under `root`, by path: each
293/// one's id and entries. A directory that is not there is left out. Each
294/// level is read at once.
295async fn read_dirs<R: GitRepo>(
296 repo: &R,
297 root: &str,
298 dirs: &BTreeSet<String>,
299) -> Result<HashMap<String, (String, Vec<TreeEntry>)>> {
300 let mut found: HashMap<String, (String, Vec<TreeEntry>)> = HashMap::new();
301 if let Some(entries) = repo.read_tree(root).await? {
302 found.insert(String::new(), (root.to_owned(), entries));
303 }
304 let depth = |path: &str| path.matches('/').count();
305 let deepest = dirs.iter().map(|dir| depth(dir)).max().unwrap_or(0);
306 for level in 0..=deepest {
307 let wanted: Vec<(String, String)> = dirs
308 .iter()
309 .filter(|dir| !dir.is_empty() && depth(dir) == level)
310 .filter_map(|dir| {
311 let (parent, name) = dir.rsplit_once('/').unwrap_or(("", dir.as_str()));
312 let (_, entries) = found.get(parent)?;
313 entries
314 .iter()
315 .find(|entry| entry.name == name && entry.kind == EntryKind::Tree)
316 .map(|entry| (dir.clone(), entry.hash.clone()))
317 })
318 .collect();
319 let read = try_join_all(wanted.iter().map(|(_, id)| repo.read_tree(id))).await?;
320 for ((dir, id), entries) in wanted.into_iter().zip(read) {
321 if let Some(entries) = entries {
322 found.insert(dir, (id, entries));
323 }
324 }
325 }
326 Ok(found)
327}
328
329fn needs_agent(reason: NeedsAgentReason, detail: impl Into<String>, paths: Vec<String>) -> Outcome<PullBranchUpdate> {
330 Outcome::Ok(PullBranchUpdate::NeedsAgent {
331 reason,
332 detail: detail.into(),
333 paths,
334 })
335}
336
337impl<S: GitStore> Repos<S> {
338 pub(crate) async fn update_pull_branch(&self, a: UpdatePullBranchArgs) -> Result<Outcome<PullBranchUpdate>> {
339 let actor = Some(a.actor.clone());
340 let Some(source) = self.registry.by_id(&a.source_id).await? else {
341 return Ok(not_found());
342 };
343 let target = match &source.fork_of {
344 Some(id) => self.registry.by_id(id).await?,
345 None => Some(source.clone()),
346 };
347 let Some(target) = target.filter(|repo| can_read(repo, &actor)) else {
348 return Ok(not_found());
349 };
350 // The merge is pushed as the person asking, so they must be able to push.
351 if !can_write(&source, &actor) {
352 return Ok(Outcome::fail(
353 FailureCode::Forbidden,
354 if source.fork_of.is_some() {
Invite-only launch: sign in with GitHub, repository access and lifecycle, many emails, a new look355 "Only whoever opened this pull request can update it.".to_owned()
Catching up with main takes seconds when the two sides touched different files356 } else {
Invite-only launch: sign in with GitHub, repository access and lifecycle, many emails, a new look357 g1t_contracts::access::needs(
358 g1t_contracts::access::Capability::Push,
359 &format!("{}/{}", source.namespace, source.name),
360 )
Catching up with main takes seconds when the two sides touched different files361 },
362 ));
363 }
364 if !a.actor.verified {
365 return Ok(Outcome::fail(FailureCode::Forbidden, UNVERIFIED));
366 }
Invite-only launch: sign in with GitHub, repository access and lifecycle, many emails, a new look367 if let Some((code, message)) = crate::lifecycle::archived_refusal(&target) {
368 return Ok(Outcome::fail(code, message));
369 }
Catching up with main takes seconds when the two sides touched different files370 let from_fork = source.id != target.id;
371 let base_branch = target.default_branch.clone();
372 let branch = a.branch.clone().unwrap_or_else(|| base_branch.clone());
373 if !from_fork && branch == base_branch {
374 return Ok(Outcome::fail(
375 FailureCode::Invalid,
376 format!("{base_branch} cannot be merged into itself."),
377 ));
378 }
379
380 let source_git = self.store.open(&store_key(&source)).await?;
381 let target_git = self.store.open(&store_key(&target)).await?;
382 let (history, target_history) = try_join(
383 source_git.log(&branch, MAX_ANCESTRY),
384 target_git.log(&base_branch, MAX_ANCESTRY),
385 )
386 .await?;
387 let (Some(head), Some(base)) = (history.first(), target_history.first()) else {
388 return Ok(Outcome::fail(
389 FailureCode::Conflict,
390 "This pull request has no commits to bring up to date.",
391 ));
392 };
393 if descends_from(&source_git, &history, &base.hash).await? {
394 return Ok(Outcome::Ok(PullBranchUpdate::UpToDate {
395 commit: head.hash.clone(),
396 }));
397 }
398 let shared: HashSet<String> = target_history.iter().map(|commit| commit.hash.clone()).collect();
399 let merge_base = nearest_ancestor_in(&source_git, &history, &shared).await?;
400 let Some((merge_base, merge_base_tree)) = merge_base.and_then(|hash| {
401 target_history
402 .iter()
403 .find(|commit| commit.hash == hash)
404 .map(|commit| (hash, commit.tree_hash.clone()))
405 }) else {
406 return Ok(needs_agent(
407 NeedsAgentReason::Unsupported,
408 format!("g1t could not find where this pull request left {base_branch}."),
409 Vec::new(),
410 ));
411 };
412
413 let ((ours, ours_cut), (theirs, theirs_cut)) = try_join(
414 diff::changed_paths(&source_git, Some(&merge_base_tree), &head.tree_hash),
415 diff::changed_paths(&target_git, Some(&merge_base_tree), &base.tree_hash),
416 )
417 .await?;
418 if ours_cut || theirs_cut {
419 return Ok(needs_agent(
420 NeedsAgentReason::Unsupported,
421 "The change is too large to merge without a sandbox.",
422 Vec::new(),
423 ));
424 }
425 let met = overlapping(&ours, &theirs);
426 if !met.is_empty() {
427 return Ok(needs_agent(
428 NeedsAgentReason::Overlap,
429 format!("This pull request and {base_branch} both changed some of the same files."),
430 met,
431 ));
432 }
433
434 // The trees on the way to each changed file, on both sides.
435 let dirs: BTreeSet<String> = ours
436 .iter()
437 .flat_map(|path| ancestors(path).map(str::to_owned))
438 .collect();
439 let (on_pull, on_base) = try_join(
440 read_dirs(&source_git, &head.tree_hash, &dirs),
441 read_dirs(&target_git, &base.tree_hash, &dirs),
442 )
443 .await?;
444 let changes: Vec<Change> = ours
445 .iter()
446 .map(|path| {
447 let (parent, name) = path.rsplit_once('/').unwrap_or(("", path.as_str()));
448 let entry = on_pull.get(parent).and_then(|(_, entries)| {
449 entries
450 .iter()
451 .find(|entry| entry.name == name && entry.kind != EntryKind::Tree)
452 .map(|entry| (entry.kind, entry.hash.clone()))
453 });
454 Change {
455 path: path.clone(),
456 entry,
457 }
458 })
459 .collect();
460 let trees: HashMap<String, Vec<TreeEntry>> = on_base.into_values().collect();
461 let merged = match merge_tree(&base.tree_hash, &trees, &changes) {
462 Ok(merged) => merged,
463 Err(why) => {
464 return Ok(needs_agent(
465 NeedsAgentReason::Unsupported,
466 format!("g1t could not merge this itself: {why}."),
467 Vec::new(),
468 ));
469 }
470 };
471
Invite-only launch: sign in with GitHub, repository access and lifecycle, many emails, a new look472 // The person's commit name and address: their noreply address
473 // unless they chose to show their own. An agent's commit is its
474 // person's. Without identity, the noreply address all the same.
475 let person = a
476 .actor
477 .acting
478 .as_ref()
479 .map_or((a.actor.id.clone(), a.actor.username.clone()), |acting| {
480 (acting.on_behalf_of.id.clone(), acting.on_behalf_of.username.clone())
481 });
482 let author = match &self.identity {
483 Some(identity) => g1t_kit::call::<_, Option<g1t_contracts::accounts::CommitIdentity>>(
484 identity,
485 "commit_identity",
486 &g1t_contracts::accounts::CommitIdentityArgs { user_id: person.0.clone() },
487 )
488 .await
489 .ok()
490 .flatten(),
491 None => None,
492 }
493 .unwrap_or_else(|| g1t_contracts::accounts::CommitIdentity {
494 name: person.1.clone(),
495 email: g1t_contracts::accounts::noreply_address(&person.0, &person.1),
496 });
Catching up with main takes seconds when the two sides touched different files497 let commit = commit_object(
498 &merged.tree,
499 &[&head.hash, &base.hash],
500 &Signature {
Invite-only launch: sign in with GitHub, repository access and lifecycle, many emails, a new look501 name: &author.name,
502 email: &author.email,
Catching up with main takes seconds when the two sides touched different files503 seconds: now_ms() / 1000,
504 },
505 &merge_message(&base_branch, &branch, a.number),
506 );
507 let commit_id = object_id(ObjectKind::Commit, &commit);
508 let mut objects: Vec<(ObjectKind, Vec<u8>)> = merged
509 .objects
510 .into_iter()
511 .map(|bytes| (ObjectKind::Tree, bytes))
512 .collect();
513 objects.push((ObjectKind::Commit, commit));
514
515 // A fork lacks what the default branch gained since it was made:
516 // those objects come from the repository, with the merge after them.
517 let pack = if from_fork {
518 let target_access = target_git.access(Scope::Read).await?;
519 let fetched = land::fetch_pack(&target_access, &base.hash, Some(&merge_base)).await?;
520 extend_pack(&fetched, &objects).map_err(worker::Error::RustError)?
521 } else {
522 write_pack(&objects)
523 };
524 let source_access = source_git.access(Scope::Write).await?;
525 // Only if the branch is still where it was: a push that landed
526 // meanwhile is kept, and this is refused.
527 let pushed = land::push_pack(&source_access, &branch, Some(&head.hash), &commit_id, pack).await?;
Mission control shows where you are needed and what agents landed without you; git answers in about 200ms528 self.refs_moved(&source.id).await;
Catching up with main takes seconds when the two sides touched different files529 let git_ref = format!("refs/heads/{branch}");
530 let path = RepoPath {
531 namespace: source.namespace.clone(),
532 name: source.name.clone(),
533 };
534 let mut target_entry = self.audit_target(&path).await?;
535 target_entry.git_ref = Some(git_ref.clone());
536 let mut entry = NewAuditEntry::new(
537 AuditActor::of(&a.actor),
538 "git.push",
539 Surface::Git,
540 target_entry,
541 &Decision::allow("person"),
542 g1t_contracts::new_id("req", now_ms()),
543 );
544 if let Err(reason) = pushed {
545 entry.result = Some("conflict".to_owned());
546 entry.message = Some(reason);
547 self.record_git(entry).await;
548 return Ok(Outcome::fail(
549 FailureCode::Conflict,
550 format!("{branch} moved while it was being brought up to date. Nothing was lost; try again."),
551 ));
552 }
553 entry.result = Some("ok".to_owned());
554 self.record_git(entry).await;
555 // As any push does: the pull request's head moves, its checks run
556 // again, and whether it merges cleanly is worked out anew.
557 self.publish_push(&source, &git_ref, Some(&head.hash), &commit_id, Some(a.actor.id.clone()))
558 .await?;
559 Ok(Outcome::Ok(PullBranchUpdate::Updated {
560 commit: commit_id,
561 previous: head.hash.clone(),
562 }))
563 }
564}
565
566#[cfg(test)]
567mod tests {
568 use super::*;
569
570 fn entry(name: &str, kind: EntryKind, hash: &str) -> TreeEntry {
571 TreeEntry {
572 name: name.to_owned(),
573 hash: hash.to_owned(),
574 kind,
575 }
576 }
577
578 fn paths(list: &[&str]) -> Vec<String> {
579 list.iter().map(|path| (*path).to_owned()).collect()
580 }
581
582 #[test]
583 fn different_files_do_not_meet() {
584 assert!(overlapping(&paths(&["src/a.rs", "README.md"]), &paths(&["src/b.rs", "docs/x.md"])).is_empty());
585 }
586
587 #[test]
588 fn the_same_file_meets() {
589 assert_eq!(overlapping(&paths(&["src/a.rs", "b"]), &paths(&["src/a.rs"])), ["src/a.rs"]);
590 }
591
592 #[test]
593 fn a_file_against_a_directory_meets() {
594 // Ours made `a` a file where theirs put files under `a/`.
595 assert_eq!(overlapping(&paths(&["a"]), &paths(&["a/b"])), ["a"]);
596 // And the other way round.
597 assert_eq!(overlapping(&paths(&["a/b/c"]), &paths(&["a/b"])), ["a/b"]);
598 // A shared prefix of a name is not a directory.
599 assert!(overlapping(&paths(&["ab"]), &paths(&["a/b"])).is_empty());
600 }
601
602 #[test]
603 fn modes_are_written_as_git_writes_them() {
604 assert_eq!(mode(EntryKind::Tree), "40000");
605 assert_eq!(mode(EntryKind::Blob), "100644");
606 assert_eq!(mode(EntryKind::Exec), "100755");
607 assert_eq!(mode(EntryKind::Symlink), "120000");
608 assert_eq!(mode(EntryKind::Gitlink), "160000");
609 }
610
611 // Ids below come from git itself (`git mktree --missing`,
612 // `git hash-object`, `git commit-tree`) in a scratch repository.
613 const EMPTY: &str = "e69de29bb2d1d6434b8b29ae775ad8c2e48c5391";
614 const HELLO: &str = "ce013625030ba8dba906f756967f9e9ca394464a";
615 const SUBMODULE: &str = "1111111111111111111111111111111111111111";
616
617 #[test]
618 fn entries_sort_as_git_sorts_them() {
619 // `a` as a directory sorts after `a.b` and `a-c` but before `a0`:
620 // it compares as `a/`.
621 let entries = vec![
622 entry("a0", EntryKind::Exec, HELLO),
623 entry("a", EntryKind::Tree, "4b825dc642cb6eb9a060e54bf8d69288fbee4904"),
624 entry("a.b", EntryKind::Blob, EMPTY),
625 entry("a-c", EntryKind::Symlink, HELLO),
626 entry("vendor", EntryKind::Gitlink, SUBMODULE),
627 ];
628 let id = object_id(ObjectKind::Tree, &encode_entries(&entries));
629 assert_eq!(id, "59710ac869a643ad7e179b924af6fb3009b84859");
630 }
631
632 #[test]
633 fn the_empty_tree_is_gits() {
634 assert_eq!(
635 object_id(ObjectKind::Tree, &encode_entries(&[])),
636 "4b825dc642cb6eb9a060e54bf8d69288fbee4904"
637 );
638 }
639
640 /// A base with `README.md`, `bin/run` (executable), `docs/old.md`,
641 /// `src/lib.rs` and a submodule `vendor/dep`.
642 fn base() -> (String, HashMap<String, Vec<TreeEntry>>) {
643 let mut trees = HashMap::new();
644 let bin = vec![entry("run", EntryKind::Exec, HELLO)];
645 let docs = vec![entry("old.md", EntryKind::Blob, HELLO)];
646 let src = vec![entry("lib.rs", EntryKind::Blob, EMPTY)];
647 let vendor = vec![entry("dep", EntryKind::Gitlink, SUBMODULE)];
648 let mut id = |entries: Vec<TreeEntry>| {
649 let id = object_id(ObjectKind::Tree, &encode_entries(&entries));
650 trees.insert(id.clone(), entries);
651 id
652 };
653 let root = vec![
654 entry("README.md", EntryKind::Blob, HELLO),
655 entry("bin", EntryKind::Tree, &id(bin)),
656 entry("docs", EntryKind::Tree, &id(docs)),
657 entry("src", EntryKind::Tree, &id(src)),
658 entry("vendor", EntryKind::Tree, &id(vendor)),
659 ];
660 let root = id(root);
661 (root, trees)
662 }
663
664 #[test]
665 fn the_base_tree_matches_git() {
666 assert_eq!(base().0, "cdbaeedd6c31387975e65e67f9d453589d3c73d1");
667 }
668
669 #[test]
670 fn changes_are_applied_to_the_base() {
671 let (root, trees) = base();
672 let changes = vec![
673 // Added in a new directory.
674 Change { path: "src/net/http.rs".into(), entry: Some((EntryKind::Blob, HELLO.into())) },
675 // Made executable: the same blob.
676 Change { path: "src/lib.rs".into(), entry: Some((EntryKind::Exec, EMPTY.into())) },
677 // Deleted, leaving its directory empty.
678 Change { path: "docs/old.md".into(), entry: None },
679 // A symlink added at the top.
680 Change { path: "latest".into(), entry: Some((EntryKind::Symlink, HELLO.into())) },
681 ];
682 let merged = merge_tree(&root, &trees, &changes).unwrap();
683 assert_eq!(merged.tree, "3097aeb8d4a86f097eca63da84e432ebeb456158");
684 // The root, src and src/net; docs is gone, bin and vendor untouched.
685 assert_eq!(merged.objects.len(), 3);
686 }
687
688 #[test]
689 fn a_file_can_replace_a_directory_the_pull_request_emptied() {
690 let (root, trees) = base();
691 let changes = vec![
692 Change { path: "docs".into(), entry: Some((EntryKind::Blob, HELLO.into())) },
693 Change { path: "docs/old.md".into(), entry: None },
694 ];
695 let merged = merge_tree(&root, &trees, &changes).unwrap();
696 assert_eq!(merged.tree, "088fc1bb6d44a71fcd0c33d4022e7bb1628b7202");
697 }
698
699 #[test]
700 fn a_tree_that_cannot_be_written_back_is_refused() {
701 let (root, mut trees) = base();
702 // Entries that do not hash to the id they are filed under, as a
703 // tree with a mode g1t does not know would not.
704 let entries = trees.remove(&root).unwrap();
705 trees.insert(root.clone(), entries[1..].to_vec());
706 let changes = vec![Change { path: "x".into(), entry: Some((EntryKind::Blob, HELLO.into())) }];
707 assert!(merge_tree(&root, &trees, &changes).is_err());
708 }
709
710 #[test]
711 fn a_file_is_not_put_where_a_directory_still_is() {
712 let (root, trees) = base();
713 let changes = vec![Change { path: "src".into(), entry: Some((EntryKind::Blob, HELLO.into())) }];
714 assert!(merge_tree(&root, &trees, &changes).is_err());
715 }
716
717 #[test]
718 fn the_merge_commit_matches_git() {
719 let commit = commit_object(
720 "cdbaeedd6c31387975e65e67f9d453589d3c73d1",
721 &["74257edb70e8dc5d2f31af4b76fe898608f829da", "110bda84f45f58e44d3699be9efe91276381b43d"],
722 &Signature { name: "octo", email: "octo@users.g1t.sh", seconds: 1_700_000_000 },
723 &merge_message("main", "feature", 7),
724 );
725 assert_eq!(object_id(ObjectKind::Commit, &commit), "f8d35e9d454b11a179215ee1283ac71b7216f024");
726 }
727
728 #[test]
729 fn a_fork_on_the_default_branch_is_named_by_number() {
730 assert_eq!(merge_message("main", "main", 12), "Merge main into pull request #12");
731 assert_eq!(merge_message("main", "fix-login", 12), "Merge main into fix-login");
732 }
733
734 #[test]
735 fn a_pack_of_the_merge_reads_back() {
736 let (root, trees) = base();
737 let changes = vec![Change { path: "src/new.rs".into(), entry: Some((EntryKind::Blob, HELLO.into())) }];
738 let merged = merge_tree(&root, &trees, &changes).unwrap();
739 let mut objects: Vec<(ObjectKind, Vec<u8>)> =
740 merged.objects.iter().map(|bytes| (ObjectKind::Tree, bytes.clone())).collect();
741 let pack = write_pack(&objects);
742 let read = g1t_scan::pack::Pack::parse(&pack).unwrap();
743 assert!(read.tree(&merged.tree).is_some());
744
745 // Extended with a commit, it still reads, and its checksum holds.
746 let commit = commit_object(
747 &merged.tree,
748 &[&root],
749 &Signature { name: "octo", email: "octo@users.g1t.sh", seconds: 1 },
750 "m",
751 );
752 let commit_id = object_id(ObjectKind::Commit, &commit);
753 objects.clear();
754 objects.push((ObjectKind::Commit, commit));
755 let extended = extend_pack(&pack, &objects).unwrap();
756 let read = g1t_scan::pack::Pack::parse(&extended).unwrap();
757 assert!(read.tree(&merged.tree).is_some());
758 assert_eq!(read.commits(), [commit_id]);
759 }
760}