Skip to main content

jouet_git/
stack.rs

1//! Stacked branches, for `jouet stack`: whether each layer really contains
2//! the layer below it, by ancestry and by content.
3//!
4//! Ancestry alone is not enough. A restack that resolves a conflict the
5//! wrong way, or a rebase that drops a commit, leaves a branch that has its
6//! parent's commits in its history but not their changes in its tree. So
7//! every file the parent layer changed is checked in the child's tree too:
8//! the parent's change, merged into the child's version of the file, must
9//! leave it as it is.
10//!
11//! A layer may still change the parent's lines on purpose, in a commit of
12//! its own made on top of them. A file whose version comes from such
13//! commits is not flagged; one a merge made is. The cost: a rebase that
14//! resolves a conflict by dropping the parent's lines inside one of the
15//! layer's own commits looks the same as a deliberate edit.
16//!
17//! Which branches form the stack, and which PRs have merged, is the
18//! caller's to say (gh-stack's metadata, or the PRs' bases on GitHub); this
19//! module only reads git. Refs are read as they are: nothing is fetched.
20
21use crate::{Error, Git};
22use jouet_output::exit::Exit;
23use serde::{Deserialize, Serialize};
24use std::path::{Path, PathBuf};
25
26/// One layer of a stack, bottom first, as the caller found it.
27#[derive(Debug, Clone, PartialEq, Eq)]
28pub struct Layer {
29    pub branch: String,
30    /// The branch it is built on: the layer below, or the trunk.
31    pub parent: String,
32    /// The layer's own PR has merged, so it has left the stack.
33    pub merged: bool,
34    /// The layer below has merged into the trunk, so this layer needs the
35    /// trunk merged in rather than its old parent.
36    pub parent_merged: bool,
37}
38
39/// A stack: its layers, bottom first, and where they land.
40#[derive(Debug, Clone)]
41pub struct Stack {
42    /// The branch the bottom layer targets, such as `main`.
43    pub trunk: String,
44    /// The remote the branches are pushed to.
45    pub remote: String,
46    pub layers: Vec<Layer>,
47}
48
49/// What became of one of the parent's file changes in the child.
50#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
51#[serde(rename_all = "snake_case")]
52pub enum Problem {
53    /// The child has the file as it was before the parent changed it.
54    Reverted,
55    /// Some or all of the parent's change is not in the child's version.
56    Missing,
57    /// The child changed the same lines differently, so jouet cannot tell.
58    Conflicting,
59}
60
61impl Problem {
62    pub fn describe(self) -> &'static str {
63        match self {
64            Self::Reverted => "reverted",
65            Self::Missing => "missing",
66            Self::Conflicting => "changed differently",
67        }
68    }
69}
70
71#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
72pub struct FileProblem {
73    pub path: String,
74    pub problem: Problem,
75    /// The parent's commit whose change is undone, as `abc1234 subject`,
76    /// when the file is as it was just before that commit.
77    #[serde(skip_serializing_if = "Option::is_none")]
78    pub commit: Option<String>,
79}
80
81/// One layer as git sees it.
82#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
83pub struct LayerState {
84    pub branch: String,
85    pub parent: String,
86    /// The local branch's commit; absent when there is no local branch.
87    #[serde(skip_serializing_if = "Option::is_none")]
88    pub local: Option<String>,
89    /// The remote-tracking branch's commit, as of the last fetch.
90    #[serde(skip_serializing_if = "Option::is_none")]
91    pub remote: Option<String>,
92    /// Local commits the remote does not have.
93    #[serde(skip_serializing_if = "is_zero")]
94    pub unpushed: u32,
95    /// Remote commits the local branch does not have.
96    #[serde(skip_serializing_if = "is_zero")]
97    pub behind: u32,
98    /// Whether the parent's tip is in this layer's history; absent when
99    /// either branch is missing, or the layer has merged.
100    #[serde(skip_serializing_if = "Option::is_none")]
101    pub contains_parent: Option<bool>,
102    /// The parent's file changes this layer's tree does not have.
103    #[serde(skip_serializing_if = "Vec::is_empty")]
104    pub content: Vec<FileProblem>,
105    /// The parent merged into the trunk, and the trunk is not merged in.
106    #[serde(skip_serializing_if = "std::ops::Not::not")]
107    pub needs_trunk: bool,
108    #[serde(skip_serializing_if = "std::ops::Not::not")]
109    pub merged: bool,
110}
111
112fn is_zero(n: &u32) -> bool {
113    *n == 0
114}
115
116impl LayerState {
117    /// The commit the layer is at: the local branch, else the remote's.
118    pub fn tip(&self) -> Option<&str> {
119        self.local.as_deref().or(self.remote.as_deref())
120    }
121
122    /// What needs doing, as codes, worst first; empty when the layer is in
123    /// order. Unpushed commits are not a problem, so not listed.
124    pub fn needs(&self) -> Vec<&'static str> {
125        let mut needs = Vec::new();
126        if self.merged {
127            return needs;
128        }
129        if self.tip().is_none() {
130            needs.push("missing_branch");
131        }
132        if !self.content.is_empty() {
133            needs.push("parent_changes_missing");
134        }
135        if self.behind > 0 {
136            needs.push("behind_remote");
137        }
138        if self.needs_trunk {
139            needs.push("needs_trunk");
140        } else if self.contains_parent == Some(false) {
141            needs.push("needs_parent");
142        }
143        needs
144    }
145}
146
147/// The remote the branches are pushed to: `origin`, else the first one.
148pub fn remote(git: &Git) -> String {
149    let remotes = git.line(&["remote"]).unwrap_or_default();
150    let mut names = remotes.lines();
151    let first = names.next();
152    match first {
153        Some(first) if first != "origin" && !remotes.lines().any(|r| r == "origin") => {
154            first.to_string()
155        }
156        _ => "origin".into(),
157    }
158}
159
160/// The commits of a branch: the local branch, and the remote's.
161fn refs(git: &Git, remote: &str, branch: &str) -> (Option<String>, Option<String>) {
162    (
163        git.commit_sha(&format!("refs/heads/{branch}")),
164        git.commit_sha(&format!("refs/remotes/{remote}/{branch}")),
165    )
166}
167
168/// The trunk's commit: the remote's, which is what merged PRs land on, else
169/// the local branch.
170pub fn trunk_tip(git: &Git, stack: &Stack) -> Option<String> {
171    let (local, remote) = refs(git, &stack.remote, &stack.trunk);
172    remote.or(local)
173}
174
175/// A branch's commit: the local branch, which may hold fixes not yet
176/// pushed, else the remote's.
177pub fn branch_tip(git: &Git, remote: &str, branch: &str) -> Option<String> {
178    let (local, remote) = refs(git, remote, branch);
179    local.or(remote)
180}
181
182/// The tip of a layer's parent: the trunk, or the layer below.
183pub fn parent_tip(git: &Git, stack: &Stack, layer: &Layer) -> Option<String> {
184    if layer.parent == stack.trunk {
185        trunk_tip(git, stack)
186    } else {
187        branch_tip(git, &stack.remote, &layer.parent)
188    }
189}
190
191/// Where the parent layer's own changes start: where it branched off its
192/// own parent. None for the trunk, whose changes are not checked.
193pub fn parent_base(git: &Git, stack: &Stack, index: usize, parent: &str) -> Option<String> {
194    let below = index.checked_sub(1).map(|i| &stack.layers[i])?;
195    if below.branch != stack.layers[index].parent {
196        return None;
197    }
198    let grandparent = parent_tip(git, stack, below)?;
199    git.line(&["merge-base", parent, &grandparent])
200}
201
202/// Every layer of the stack, as git sees it now.
203pub fn inspect(git: &Git, stack: &Stack) -> Result<Vec<LayerState>, Error> {
204    let mut out = Vec::new();
205    for (i, layer) in stack.layers.iter().enumerate() {
206        let (local, remote) = refs(git, &stack.remote, &layer.branch);
207        let mut state = LayerState {
208            branch: layer.branch.clone(),
209            parent: layer.parent.clone(),
210            local,
211            remote,
212            unpushed: 0,
213            behind: 0,
214            contains_parent: None,
215            content: Vec::new(),
216            needs_trunk: false,
217            merged: layer.merged,
218        };
219        if let (Some(local), Some(remote)) = (&state.local, &state.remote) {
220            state.unpushed = git.count(&format!("{remote}..{local}")).unwrap_or(0);
221            state.behind = git.count(&format!("{local}..{remote}")).unwrap_or(0);
222        } else if let (Some(local), false) = (&state.local, layer.merged) {
223            // Never pushed: every commit past its parent is unpushed.
224            if let Some(parent) = parent_tip(git, stack, layer) {
225                state.unpushed = git.count(&format!("{parent}..{local}")).unwrap_or(0);
226            }
227        }
228        let tip = state.tip().map(str::to_string);
229        if let (false, Some(tip)) = (layer.merged, tip) {
230            if layer.parent_merged
231                && let Some(trunk) = trunk_tip(git, stack)
232            {
233                state.needs_trunk = !git.is_ancestor(&trunk, &tip);
234            }
235            if let Some(parent) = parent_tip(git, stack, layer) {
236                let contains = git.is_ancestor(&parent, &tip);
237                state.contains_parent = Some(contains);
238                // A layer without its parent's commits plainly lacks their
239                // changes; one with them should have them all.
240                if contains && let Some(base) = parent_base(git, stack, i, &parent) {
241                    state.content = missing_changes(git, &base, &parent, &tip)?;
242                }
243            }
244        }
245        out.push(state);
246    }
247    Ok(out)
248}
249
250/// The file changes from `from` to `to` that are not in `tip`'s tree. A
251/// change is in `tip` when merging it into `tip`'s version of the file
252/// leaves that version as it is; a version equal to the one before the
253/// change has it reverted.
254pub fn missing_changes(
255    git: &Git,
256    from: &str,
257    to: &str,
258    tip: &str,
259) -> Result<Vec<FileProblem>, Error> {
260    let changed = names(git, from, to)?;
261    if changed.is_empty() {
262        return Ok(Vec::new());
263    }
264    // Only a file that differs between the parent and the child can lack
265    // the parent's change.
266    let differs = names(git, to, tip)?;
267    let mut problems = Vec::new();
268    for path in changed.iter().filter(|p| differs.contains(p)) {
269        let change = Change {
270            path,
271            base: blob(git, from, path),
272            theirs: blob(git, to, path),
273        };
274        let mine = blob(git, tip, path);
275        let problem = change.lacked_by(git, mine.as_deref())?;
276        if problem.is_some() && own_edit(git, &change, to, tip)? {
277            continue;
278        }
279        if let Some(problem) = problem {
280            let undone = undone_commit(git, from, to, path, mine.as_deref());
281            problems.push(FileProblem {
282                path: path.clone(),
283                problem: if undone.is_some() {
284                    Problem::Reverted
285                } else {
286                    problem
287                },
288                commit: undone,
289            });
290        }
291    }
292    Ok(problems)
293}
294
295/// One of the parent's file changes: the file before it, and after.
296struct Change<'a> {
297    path: &'a str,
298    base: Option<String>,
299    theirs: Option<String>,
300}
301
302impl Change<'_> {
303    /// What is wrong with `mine`, a version of the file (None when there is
304    /// none), if it lacks this change.
305    fn lacked_by(&self, git: &Git, mine: Option<&str>) -> Result<Option<Problem>, Error> {
306        if mine == self.base.as_deref() {
307            return Ok(Some(Problem::Reverted));
308        }
309        Ok(match (self.theirs.as_deref(), mine) {
310            // The child deleted a file the parent changed, or kept one the
311            // parent deleted.
312            (Some(_), None) | (None, Some(_)) => Some(Problem::Missing),
313            (Some(theirs), Some(mine)) => merge_check(git, mine, self.base.as_deref(), theirs)?,
314            (None, None) => None,
315        })
316    }
317}
318
319/// Whether `tip`'s version of the file comes from the child layer's own
320/// edits, made after it had the parent's change: the newest of its commits
321/// past `to` (the parent's tip) that touched the file is not a merge, and
322/// the version it started from had the change, or came the same way.
323///
324/// A merge is where a restack loses a change, so a version a merge made is
325/// never excused. Neither is a tree that is not a commit yet, such as the
326/// one `stack sync` checks before committing its merge.
327fn own_edit(git: &Git, change: &Change<'_>, to: &str, tip: &str) -> Result<bool, Error> {
328    let mut at = tip.to_string();
329    loop {
330        // `--full-history` keeps a merge that took either side's version.
331        let Ok(log) = git.text(&[
332            "log",
333            "-1",
334            "--topo-order",
335            "--full-history",
336            "--format=%H %P",
337            &format!("{to}..{at}"),
338            "--",
339            change.path,
340        ]) else {
341            return Ok(false);
342        };
343        let mut fields = log.split_whitespace();
344        let (Some(_), Some(before), None) = (fields.next(), fields.next(), fields.next()) else {
345            return Ok(false);
346        };
347        let version = blob(git, before, change.path);
348        if change.lacked_by(git, version.as_deref())?.is_none() {
349            return Ok(true);
350        }
351        at = before.to_string();
352    }
353}
354
355/// The newest of the parent's commits in `from..to` touching `path` that
356/// `mine` (the child's blob, None when it has no such file) undoes: the
357/// file is as it was just before that commit.
358fn undone_commit(
359    git: &Git,
360    from: &str,
361    to: &str,
362    path: &str,
363    mine: Option<&str>,
364) -> Option<String> {
365    let log = git
366        .text(&[
367            "log",
368            "--format=%H %h %s",
369            "--no-merges",
370            &format!("{from}..{to}"),
371            "--",
372            path,
373        ])
374        .ok()?;
375    log.lines().find_map(|line| {
376        let (sha, short) = line.split_once(' ')?;
377        (blob(git, &format!("{sha}^"), path).as_deref() == mine).then(|| short.to_string())
378    })
379}
380
381/// The paths that differ between two commits.
382fn names(git: &Git, a: &str, b: &str) -> Result<Vec<String>, Error> {
383    let out = git.text(&["diff", "--name-only", "-z", "--no-renames", a, b])?;
384    Ok(crate::nul_fields(&out).map(str::to_string).collect())
385}
386
387/// The blob of `path` at `commit`, or None when it has no such file.
388fn blob(git: &Git, commit: &str, path: &str) -> Option<String> {
389    git.line(&[
390        "rev-parse",
391        "--verify",
392        "--quiet",
393        &format!("{commit}:{path}"),
394    ])
395}
396
397/// Whether merging `base`→`theirs` into `mine` would change it: None when
398/// it would not (the change is there), else what is wrong. A missing base
399/// is an empty file.
400fn merge_check(
401    git: &Git,
402    mine: &str,
403    base: Option<&str>,
404    theirs: &str,
405) -> Result<Option<Problem>, Error> {
406    let dir = tempfile::tempdir()
407        .map_err(|e| Error::new(Exit::Failed, format!("creating a temporary directory: {e}")))?;
408    let write = |name: &str, oid: Option<&str>| -> Result<(PathBuf, Vec<u8>), Error> {
409        let path = dir.path().join(name);
410        let bytes = match oid {
411            Some(oid) => cat(git, oid)?,
412            None => Vec::new(),
413        };
414        std::fs::write(&path, &bytes)
415            .map_err(|e| Error::new(Exit::Failed, format!("writing {}: {e}", path.display())))?;
416        Ok((path, bytes))
417    };
418    let (mine_path, mine_bytes) = write("mine", Some(mine))?;
419    let (base_path, _) = write("base", base)?;
420    let (theirs_path, _) = write("theirs", Some(theirs))?;
421    let out = git
422        .command(&[
423            Path::new("merge-file"),
424            Path::new("-p"),
425            Path::new("--quiet"),
426            &mine_path,
427            &base_path,
428            &theirs_path,
429        ])
430        .output()
431        .map_err(|e| Error::new(Exit::Failed, format!("running git merge-file: {e}")))?;
432    Ok(match out.status.code() {
433        Some(0) if out.stdout == mine_bytes => None,
434        Some(0) => Some(Problem::Missing),
435        // A count of conflicts, or an error such as a binary file.
436        _ => Some(Problem::Conflicting),
437    })
438}
439
440fn cat(git: &Git, oid: &str) -> Result<Vec<u8>, Error> {
441    let out = git
442        .command(&["cat-file", "blob", oid])
443        .output()
444        .map_err(|e| Error::new(Exit::Failed, format!("running git cat-file: {e}")))?;
445    if !out.status.success() {
446        return Err(Error::new(Exit::Failed, format!("reading blob {oid}")));
447    }
448    Ok(out.stdout)
449}
450
451/// A stack as gh-stack keeps it.
452#[derive(Debug, Clone, PartialEq, Eq)]
453pub struct GhStack {
454    pub trunk: String,
455    /// The branches, bottom first, with their PR numbers once submitted.
456    pub branches: Vec<(String, Option<u64>)>,
457}
458
459#[derive(Deserialize)]
460struct GhStackFile {
461    #[serde(default)]
462    stacks: Vec<GhStackEntry>,
463}
464
465#[derive(Deserialize)]
466struct GhStackEntry {
467    trunk: GhBranch,
468    #[serde(default)]
469    branches: Vec<GhBranch>,
470}
471
472#[derive(Deserialize)]
473struct GhBranch {
474    branch: String,
475    #[serde(default, rename = "pullRequest")]
476    pull_request: Option<GhPr>,
477}
478
479#[derive(Deserialize)]
480struct GhPr {
481    number: u64,
482}
483
484/// The gh-stack stack holding `branch`, from the `gh-stack` file in the
485/// worktree's git directory or the repository's common one. None when
486/// gh-stack does not track it.
487pub fn gh_stack(git: &Git, branch: &str) -> Option<GhStack> {
488    let dirs = [
489        git.git_dir().ok(),
490        git.line(&["rev-parse", "--path-format=absolute", "--git-common-dir"])
491            .map(PathBuf::from),
492    ];
493    dirs.into_iter().flatten().find_map(|dir| {
494        let text = std::fs::read_to_string(dir.join("gh-stack")).ok()?;
495        parse_gh_stack(&text, branch)
496    })
497}
498
499/// The stack holding `branch` in the text of a `gh-stack` file.
500pub fn parse_gh_stack(text: &str, branch: &str) -> Option<GhStack> {
501    let file: GhStackFile = serde_json::from_str(text).ok()?;
502    let entry = file
503        .stacks
504        .into_iter()
505        .find(|s| s.branches.iter().any(|b| b.branch == branch))?;
506    Some(GhStack {
507        trunk: entry.trunk.branch,
508        branches: entry
509            .branches
510            .into_iter()
511            .map(|b| (b.branch, b.pull_request.map(|p| p.number)))
512            .collect(),
513    })
514}
515
516pub mod sync;
517
518#[cfg(test)]
519mod tests;