Skip to main content

quarb_git/
lib.rs

1//! Git repository adapter for the Quarb query engine.
2//!
3//! A repository is an arbor with a real DAG for its crosslink
4//! fabric. The root exposes four names:
5//!
6//! - `/branches/<name>`, `/tags/<name>` — the refs. A ref node is
7//!   an *alias for its commit*: same properties, same children.
8//! - `/HEAD` — the checked-out commit, same alias treatment.
9//! - `/commits/<hash>` — every commit. Navigating by literal name
10//!   accepts anything `git rev-parse` does (unique prefixes,
11//!   `HEAD~2`, `v1.0^{}`), without enumerating; enumeration
12//!   (`/commits/*`) lists every commit reachable from any ref, in
13//!   reverse chronological order, batched through one
14//!   `rev-list --all`.
15//!
16//! A commit's properties are its header (`::author`, `::email`,
17//! `::date` as an instant (the author date, offset preserved),
18//! `::committer`, `::subject`,
19//! `::message`, `::parent` — the first parent's hash); its
20//! *children are its tree* — descend `/branches/master/src/lib.rs`
21//! and the blob's content is the node's value (`::`), giving
22//! time-travel file access at any commit. Tree entries carry
23//! `:::type`, `:::mode`, `:::size`, and `:::hash`.
24//!
25//! References are inherent, no schema needed: `::parent-->`
26//! resolves to the first parent, `->parent` enumerates all
27//! parents (merges fan out), and `<-parent` finds the commits
28//! that point *here* (children — served from the enumeration, so
29//! it loads the commit list). Traits name what a node is:
30//! `<commit>`, `<branch>`, `<tag>`, `<tree>`, `<blob>`.
31//!
32//! Everything is read through git plumbing over subprocess
33//! (`rev-list`, `rev-parse`, `ls-tree`, `cat-file`, ...) — no
34//! libgit2, no new dependencies — lazily, one object on first
35//! touch. A walk along `parent` reads ahead: a commit the walk
36//! arrives at is read together with the next of its ancestors (one
37//! `rev-list -n k`, k doubling), so a walk of n commits starts
38//! about log n git processes and not n. The tree and the commits
39//! are kept for the adapter's lifetime; a blob's content is read
40//! again at each read, through one open `cat-file --batch` pipe, so
41//! a large file is never held. The adapter never writes.
42
43use quarb::{AstAdapter, NodeId, Value};
44use std::cell::RefCell;
45use std::collections::HashMap;
46use std::path::PathBuf;
47
48/// An error opening or reading a repository.
49#[derive(Debug, thiserror::Error)]
50pub enum GitError {
51    #[error("git: {0}")]
52    Git(String),
53    #[error("git: running git: {0}")]
54    Spawn(#[from] std::io::Error),
55}
56
57/// A commit's parsed header.
58#[derive(Clone)]
59struct CommitInfo {
60    author: String,
61    email: String,
62    date: i64,
63    /// The author date's UTC offset in minutes (from `%ai`),
64    /// preserved for display on the minted instant.
65    date_offset: Option<i16>,
66    committer: String,
67    subject: String,
68    message: String,
69    tree: String,
70    parents: Vec<String>,
71}
72
73/// What a node is.
74#[derive(Clone)]
75enum Kind {
76    Root,
77    /// `branches`, `tags`, or `commits`.
78    Dir(&'static str),
79    /// A ref (branch, tag, or HEAD): an alias for its commit.
80    Ref {
81        name: String,
82        commit: String,
83    },
84    Commit(String),
85    /// A tree entry: a subtree or a blob.
86    Entry {
87        name: String,
88        oid: String,
89        entry_type: String, // "tree" | "blob"
90        mode: String,
91    },
92}
93
94struct Node {
95    kind: Kind,
96    parent: Option<NodeId>,
97    children: RefCell<Option<Vec<NodeId>>>,
98}
99
100/// A git repository, exposed as an arbor.
101pub struct GitAdapter {
102    repo: PathBuf,
103    /// The mount's rule at the source boundary: a blob's text
104    /// decodes under it (`?encoding=`, else strict UTF-8).
105    decoding: quarb::source::SourceDecoding,
106    nodes: RefCell<Vec<Node>>,
107    commits: RefCell<HashMap<String, CommitInfo>>,
108    /// The parents of the commits held that are not held themselves:
109    /// where a walk goes next (see `commit_info`).
110    frontier: RefCell<std::collections::HashSet<String>>,
111    /// How many commits the last read along a walk took.
112    ahead: std::cell::Cell<usize>,
113    /// The commits the listed refs point at, in the listings' order,
114    /// and where each one not yet asked for stands in it: where a
115    /// sweep of the refs goes next (see `commit_info`).
116    tips: RefCell<Vec<String>>,
117    tip_at: RefCell<HashMap<String, usize>>,
118    /// How many commits the last read along a sweep of the refs took.
119    tips_ahead: std::cell::Cell<usize>,
120    /// The git processes started for commit headers (the tests'
121    /// measure of what a walk costs).
122    header_reads: std::cell::Cell<usize>,
123    /// hash → its `/commits/<hash>` node.
124    commit_nodes: RefCell<HashMap<String, NodeId>>,
125    /// Whether `/commits` has been enumerated (rev-list --all).
126    enumerated: RefCell<bool>,
127    /// hash → the paths its diff (vs first parent) touches.
128    changed: RefCell<HashMap<String, Vec<String>>>,
129    /// commit hash → the tag names pointing at it (lazy).
130    tag_map: RefCell<Option<HashMap<String, Vec<String>>>>,
131    /// commit hash → the commits that list it as a parent (built
132    /// once from the enumeration; `<--` over every commit is one
133    /// pass, not one scan of the list per commit).
134    children_of: RefCell<Option<HashMap<String, Vec<String>>>>,
135    /// One `git cat-file --batch` (contents) and one `--batch-check`
136    /// (sizes) kept open: a blob per request on a pipe, not a git
137    /// process per blob.
138    blobs: RefCell<Option<Batch>>,
139    sizes: RefCell<Option<Batch>>,
140}
141
142/// A `git cat-file --batch[-check]` child on a pipe.
143struct Batch {
144    child: std::process::Child,
145    stdin: std::process::ChildStdin,
146    out: std::io::BufReader<std::process::ChildStdout>,
147}
148
149impl Batch {
150    fn spawn(repo: &std::path::Path, check: bool) -> std::io::Result<Batch> {
151        let mut child = std::process::Command::new("git")
152            .arg("-C")
153            .arg(repo)
154            .args(["cat-file", if check { "--batch-check" } else { "--batch" }])
155            .stdin(std::process::Stdio::piped())
156            .stdout(std::process::Stdio::piped())
157            .stderr(std::process::Stdio::null())
158            .spawn()?;
159        let stdin = child.stdin.take().expect("piped");
160        let out = std::io::BufReader::new(child.stdout.take().expect("piped"));
161        Ok(Batch { child, stdin, out })
162    }
163
164    /// Ask for `oid`: the header line (`<oid> <type> <size>`), or
165    /// `None` when the object is missing.
166    fn header(&mut self, oid: &str) -> std::io::Result<Option<u64>> {
167        use std::io::{BufRead, Write};
168        writeln!(self.stdin, "{oid}")?;
169        self.stdin.flush()?;
170        let mut line = String::new();
171        self.out.read_line(&mut line)?;
172        let mut parts = line.split_whitespace();
173        let _oid = parts.next();
174        match (parts.next(), parts.next()) {
175            (Some("missing"), _) | (None, _) => Ok(None),
176            (Some(_), Some(size)) => Ok(size.parse().ok()),
177            _ => Ok(None),
178        }
179    }
180
181    /// The object's bytes (after `header`, on a `--batch` child).
182    fn body(&mut self, size: u64) -> std::io::Result<Vec<u8>> {
183        use std::io::Read;
184        let mut buf = vec![0u8; size as usize];
185        self.out.read_exact(&mut buf)?;
186        let mut nl = [0u8; 1];
187        self.out.read_exact(&mut nl)?;
188        Ok(buf)
189    }
190}
191
192impl Drop for GitAdapter {
193    fn drop(&mut self) {
194        for b in [self.blobs.get_mut(), self.sizes.get_mut()] {
195            if let Some(b) = b {
196                let _ = b.child.kill();
197                let _ = b.child.wait();
198            }
199        }
200    }
201}
202
203const ROOT: NodeId = NodeId(0);
204/// The most commits one read along a walk takes.
205const AHEAD_MOST: usize = 1024;
206const BRANCHES: NodeId = NodeId(1);
207const TAGS: NodeId = NodeId(2);
208const COMMITS: NodeId = NodeId(3);
209
210impl GitAdapter {
211    /// Open the repository at `path` (any directory inside it).
212    pub fn open(path: &std::path::Path) -> Result<Self, GitError> {
213        Self::open_with_decoding(path, quarb::source::SourceDecoding::default())
214    }
215
216    /// [`open`](Self::open) under a mount's source-boundary rule:
217    /// blobs decode by `?encoding=`, a byte-order mark, else strict
218    /// UTF-8 (a blob that decodes under none has no text).
219    pub fn open_with_decoding(
220        path: &std::path::Path,
221        decoding: quarb::source::SourceDecoding,
222    ) -> Result<Self, GitError> {
223        let adapter = GitAdapter {
224            repo: path.to_path_buf(),
225            decoding,
226            nodes: RefCell::new(vec![
227                Node {
228                    kind: Kind::Root,
229                    parent: None,
230                    children: RefCell::new(None),
231                },
232                Node {
233                    kind: Kind::Dir("branches"),
234                    parent: Some(ROOT),
235                    children: RefCell::new(None),
236                },
237                Node {
238                    kind: Kind::Dir("tags"),
239                    parent: Some(ROOT),
240                    children: RefCell::new(None),
241                },
242                Node {
243                    kind: Kind::Dir("commits"),
244                    parent: Some(ROOT),
245                    children: RefCell::new(None),
246                },
247            ]),
248            commits: RefCell::new(HashMap::new()),
249            frontier: RefCell::new(std::collections::HashSet::new()),
250            ahead: std::cell::Cell::new(1),
251            tips: RefCell::new(Vec::new()),
252            tip_at: RefCell::new(HashMap::new()),
253            tips_ahead: std::cell::Cell::new(1),
254            header_reads: std::cell::Cell::new(0),
255            commit_nodes: RefCell::new(HashMap::new()),
256            enumerated: RefCell::new(false),
257            changed: RefCell::new(HashMap::new()),
258            tag_map: RefCell::new(None),
259            children_of: RefCell::new(None),
260            blobs: RefCell::new(None),
261            sizes: RefCell::new(None),
262        };
263        // Probe: is this a repository at all?
264        adapter.git(&["rev-parse", "--git-dir"])?;
265        Ok(adapter)
266    }
267
268    /// A human-readable locator: `/commits/<short>/path`,
269    /// `/branches/<name>/path`, ...
270    pub fn locator(&self, node: NodeId) -> String {
271        let nodes = self.nodes.borrow();
272        let mut parts = Vec::new();
273        let mut cur = Some(node);
274        while let Some(n) = cur {
275            let nd = &nodes[n.0 as usize];
276            match &nd.kind {
277                Kind::Root => {}
278                Kind::Dir(d) => parts.push(d.to_string()),
279                Kind::Ref { name, .. } => parts.push(name.clone()),
280                Kind::Commit(h) => parts.push(h[..7.min(h.len())].to_string()),
281                Kind::Entry { name, .. } => parts.push(name.clone()),
282            }
283            cur = nd.parent;
284        }
285        parts.reverse();
286        format!("/{}", parts.join("/"))
287    }
288
289    /// Run git for structured output (headers, trees, refs): paths
290    /// come unquoted (`core.quotepath=off`) and the output must be
291    /// UTF-8 — the commands that print messages take
292    /// `--encoding=UTF-8`, so git transcodes a commit written in
293    /// another declared encoding. Output that still is not UTF-8
294    /// is an error, never replaced.
295    fn git(&self, args: &[&str]) -> Result<String, GitError> {
296        let out = self.git_bytes(args)?;
297        String::from_utf8(out).map_err(|e| {
298            GitError::Git(format!(
299                "git {}: output is not UTF-8 at byte {}",
300                args.first().unwrap_or(&""),
301                e.utf8_error().valid_up_to()
302            ))
303        })
304    }
305
306    /// A blob's bytes through the open `cat-file --batch` pipe; a
307    /// pipe that fails is dropped and the one-shot command answers.
308    fn blob_bytes(&self, oid: &str) -> Result<Vec<u8>, GitError> {
309        let batched = (|| -> std::io::Result<Option<Vec<u8>>> {
310            let mut slot = self.blobs.borrow_mut();
311            if slot.is_none() {
312                *slot = Some(Batch::spawn(&self.repo, false)?);
313            }
314            let b = slot.as_mut().expect("spawned");
315            match b.header(oid)? {
316                Some(size) => b.body(size).map(Some),
317                None => Ok(None),
318            }
319        })();
320        match batched {
321            Ok(Some(bytes)) => Ok(bytes),
322            Ok(None) => Err(GitError::Git(format!("blob {oid}: missing"))),
323            Err(_) => {
324                *self.blobs.borrow_mut() = None;
325                self.git_bytes(&["cat-file", "blob", oid])
326            }
327        }
328    }
329
330    /// A blob's size through the open `cat-file --batch-check` pipe,
331    /// with the same fallback.
332    fn blob_size(&self, oid: &str) -> Option<u64> {
333        let batched = (|| -> std::io::Result<Option<u64>> {
334            let mut slot = self.sizes.borrow_mut();
335            if slot.is_none() {
336                *slot = Some(Batch::spawn(&self.repo, true)?);
337            }
338            slot.as_mut().expect("spawned").header(oid)
339        })();
340        match batched {
341            Ok(size) => size,
342            Err(_) => {
343                *self.sizes.borrow_mut() = None;
344                self.git(&["cat-file", "-s", oid])
345                    .ok()
346                    .and_then(|s| s.trim().parse().ok())
347            }
348        }
349    }
350
351    /// The commits that list `hash` as a parent, from an index
352    /// built once over the enumeration.
353    fn children_of(&self, hash: &str) -> Vec<String> {
354        self.enumerate_commits();
355        if self.children_of.borrow().is_none() {
356            let mut index: HashMap<String, Vec<String>> = HashMap::new();
357            for (h, info) in self.commits.borrow().iter() {
358                for p in &info.parents {
359                    index.entry(p.clone()).or_default().push(h.clone());
360                }
361            }
362            for v in index.values_mut() {
363                v.sort();
364            }
365            *self.children_of.borrow_mut() = Some(index);
366        }
367        self.children_of
368            .borrow()
369            .as_ref()
370            .and_then(|i| i.get(hash).cloned())
371            .unwrap_or_default()
372    }
373
374    /// Run git for raw bytes (a blob): the caller decodes.
375    fn git_bytes(&self, args: &[&str]) -> Result<Vec<u8>, GitError> {
376        let out = std::process::Command::new("git")
377            .arg("-C")
378            .arg(&self.repo)
379            .args(["-c", "core.quotepath=off"])
380            .args(args)
381            .output()?;
382        if !out.status.success() {
383            return Err(GitError::Git(
384                String::from_utf8(out.stderr)
385                    .map(|s| s.trim().to_string())
386                    .unwrap_or_else(|_| "(git's message is not UTF-8)".to_string()),
387            ));
388        }
389        Ok(out.stdout)
390    }
391
392    fn push_node(&self, kind: Kind, parent: Option<NodeId>) -> NodeId {
393        let mut nodes = self.nodes.borrow_mut();
394        let id = NodeId(nodes.len() as u64);
395        nodes.push(Node {
396            kind,
397            parent,
398            children: RefCell::new(None),
399        });
400        id
401    }
402
403    /// The `/commits/<hash>` node for a full hash, interning it.
404    fn commit_node(&self, hash: &str) -> NodeId {
405        if let Some(&id) = self.commit_nodes.borrow().get(hash) {
406            return id;
407        }
408        let id = self.push_node(Kind::Commit(hash.to_string()), Some(COMMITS));
409        self.commit_nodes.borrow_mut().insert(hash.to_string(), id);
410        id
411    }
412
413    /// Hold a commit's header, and note where a walk from it goes:
414    /// its parents not yet held.
415    fn learn(&self, hash: &str, info: CommitInfo) {
416        let mut commits = self.commits.borrow_mut();
417        let mut frontier = self.frontier.borrow_mut();
418        frontier.remove(hash);
419        for p in &info.parents {
420            if !commits.contains_key(p) {
421                frontier.insert(p.clone());
422            }
423        }
424        commits.insert(hash.to_string(), info);
425    }
426
427    /// Note the commit a listed ref points at, for the sweep of the
428    /// listing to read it with its neighbours.
429    fn note_tip(&self, hash: &str) {
430        if self.commits.borrow().contains_key(hash) {
431            return;
432        }
433        let mut tips = self.tips.borrow_mut();
434        let mut tip_at = self.tip_at.borrow_mut();
435        if !tip_at.contains_key(hash) {
436            tip_at.insert(hash.to_string(), tips.len());
437            tips.push(hash.to_string());
438        }
439    }
440
441    /// The git processes started so far for commit headers: one per
442    /// keyed commit, one per read along a walk, one per listing.
443    #[doc(hidden)]
444    pub fn header_reads(&self) -> usize {
445        self.header_reads.get()
446    }
447
448    /// A commit's parsed header, fetched on first touch.
449    ///
450    /// A commit that is the parent of one already held is a walk
451    /// arriving: it is read together with the next of its ancestors,
452    /// twice as many as the walk's last read took, up to
453    /// [`AHEAD_MOST`] (one `rev-list -n k` from it, the listing's own
454    /// format and parser, so the values are the listing's). A walk of
455    /// n commits then starts about log n processes. It started one
456    /// `git show` a commit: 400 commits took 1.7 s and a history of
457    /// 1,568 took 5.8 s, where listing all of it takes 0.08 s. A
458    /// commit asked for by name alone is still one commit read.
459    ///
460    /// A commit a listed ref points at is a sweep of the refs
461    /// arriving (`/tags/* | ::subject`): it is read together with
462    /// the commits of the refs that follow it in the listing, by
463    /// the same doubling (one `rev-list --no-walk` of them). The
464    /// sweep started one `git show` a ref: 448 tags on 167 commits
465    /// took 0.7 s, where reading those commits together takes
466    /// 0.03 s. A ref asked for by name is one read of two commits.
467    fn commit_info(&self, hash: &str) -> Option<CommitInfo> {
468        if let Some(i) = self.commits.borrow().get(hash) {
469            return Some(i.clone());
470        }
471        if self.frontier.borrow().contains(hash) {
472            let k = (self.ahead.get() * 2).min(AHEAD_MOST);
473            self.ahead.set(k);
474            self.read_ancestry(hash, k);
475            if let Some(i) = self.commits.borrow().get(hash) {
476                return Some(i.clone());
477            }
478        }
479        let tip = self.tip_at.borrow().get(hash).copied();
480        if let Some(at) = tip {
481            let k = (self.tips_ahead.get() * 2).min(AHEAD_MOST);
482            self.tips_ahead.set(k);
483            self.read_tips(at, k);
484            if let Some(i) = self.commits.borrow().get(hash) {
485                return Some(i.clone());
486            }
487        }
488        self.header_reads.set(self.header_reads.get() + 1);
489        let out = self
490            .git(&[
491                "show",
492                "-s",
493                "--encoding=UTF-8",
494                "--format=%an%x00%ae%x00%at%x00%cn%x00%s%x00%B%x00%T%x00%P%x00%ai",
495                hash,
496            ])
497            .ok()?;
498        let info = parse_info(&out)?;
499        self.learn(hash, info.clone());
500        Some(info)
501    }
502
503    /// `hash` and the next `k - 1` of its ancestors, newest first,
504    /// in one `rev-list`: the commits a walk from `hash` reads next.
505    fn read_ancestry(&self, hash: &str, k: usize) {
506        self.header_reads.set(self.header_reads.get() + 1);
507        let n = k.to_string();
508        let Ok(out) = self.git(&[
509            "rev-list",
510            "--encoding=UTF-8",
511            "-n",
512            &n,
513            "--format=%an%x00%ae%x00%at%x00%cn%x00%s%x00%B%x00%T%x00%P%x00%ai%x1e",
514            hash,
515        ]) else {
516            return;
517        };
518        for (h, body) in split_commit_records(&out) {
519            if self.commits.borrow().contains_key(h) {
520                continue;
521            }
522            if let Some(info) = parse_info(body) {
523                self.learn(h, info);
524            }
525        }
526    }
527
528    /// The listed refs' commits from the one at `at` on, those not
529    /// held and not yet asked for, `k` at most, in one
530    /// `rev-list --no-walk`: the commits a sweep of the refs reads
531    /// next. Each is asked for here once: what git does not answer
532    /// (a tag of a tree names no commit) is left to the single read.
533    fn read_tips(&self, at: usize, k: usize) {
534        let batch: Vec<String> = {
535            let tips = self.tips.borrow();
536            let commits = self.commits.borrow();
537            let mut tip_at = self.tip_at.borrow_mut();
538            let mut batch = Vec::new();
539            for h in &tips[at..] {
540                if batch.len() == k {
541                    break;
542                }
543                if tip_at.remove(h).is_some() && !commits.contains_key(h) {
544                    batch.push(h.clone());
545                }
546            }
547            batch
548        };
549        // one commit alone is the single read's
550        if batch.len() < 2 {
551            return;
552        }
553        self.header_reads.set(self.header_reads.get() + 1);
554        let mut args = vec![
555            "rev-list",
556            "--no-walk",
557            "--encoding=UTF-8",
558            "--format=%an%x00%ae%x00%at%x00%cn%x00%s%x00%B%x00%T%x00%P%x00%ai%x1e",
559        ];
560        args.extend(batch.iter().map(String::as_str));
561        let Ok(out) = self.git(&args) else {
562            return;
563        };
564        for (h, body) in split_commit_records(&out) {
565            if self.commits.borrow().contains_key(h) {
566                continue;
567            }
568            if let Some(info) = parse_info(body) {
569                self.learn(h, info);
570            }
571        }
572    }
573
574    /// Enumerate every commit reachable from any ref: one
575    /// `rev-list --all` with the header format, parsed in bulk.
576    /// The first `k` commits of `rev-list --all`, for a step that keeps
577    /// a prefix (the pushdown scanning round, 2026-11-06): the walk
578    /// stops at k, the nodes keyed by hash so the full enumeration
579    /// finds them again; nothing cached as the listing.
580    fn commits_prefix(&self, k: usize) -> Vec<NodeId> {
581        self.header_reads.set(self.header_reads.get() + 1);
582        let n = k.to_string();
583        let out = self
584            .git(&[
585                "rev-list",
586                "--encoding=UTF-8",
587                "--all",
588                "-n",
589                &n,
590                "--format=%an%x00%ae%x00%at%x00%cn%x00%s%x00%B%x00%T%x00%P%x00%ai%x1e",
591            ])
592            .unwrap_or_default();
593        let mut ids = Vec::new();
594        for (hash, body) in split_commit_records(&out) {
595            if let Some(info) = parse_info(body) {
596                self.learn(hash, info);
597            }
598            ids.push(self.commit_node(hash));
599        }
600        ids
601    }
602
603    fn enumerate_commits(&self) -> Vec<NodeId> {
604        if let Some(c) = self.nodes.borrow()[COMMITS.0 as usize]
605            .children
606            .borrow()
607            .as_ref()
608        {
609            return c.clone();
610        }
611        self.header_reads.set(self.header_reads.get() + 1);
612        let out = self
613            .git(&[
614                "rev-list",
615                "--encoding=UTF-8",
616                "--all",
617                "--format=%an%x00%ae%x00%at%x00%cn%x00%s%x00%B%x00%T%x00%P%x00%ai%x1e",
618            ])
619            .unwrap_or_default();
620        let mut ids = Vec::new();
621        for (hash, body) in split_commit_records(&out) {
622            if let Some(info) = parse_info(body) {
623                self.commits.borrow_mut().insert(hash.to_string(), info);
624            }
625            ids.push(self.commit_node(hash));
626        }
627        *self.enumerated.borrow_mut() = true;
628        // every reachable commit is held: no walk has anywhere to
629        // read ahead to
630        self.frontier.borrow_mut().clear();
631        *self.nodes.borrow()[COMMITS.0 as usize]
632            .children
633            .borrow_mut() = Some(ids.clone());
634        ids
635    }
636
637    /// The tag names pointing at `hash` (annotated tags
638    /// dereferenced), from one cached `for-each-ref` sweep.
639    fn tags_at(&self, hash: &str) -> Vec<String> {
640        if self.tag_map.borrow().is_none() {
641            let out = self
642                .git(&[
643                    "for-each-ref",
644                    "refs/tags",
645                    "--format=%(refname:short)%00%(objectname)%00%(*objectname)",
646                ])
647                .unwrap_or_default();
648            let mut map: HashMap<String, Vec<String>> = HashMap::new();
649            for line in out.lines() {
650                let mut f = line.split('\u{0}');
651                let (Some(name), Some(oid)) = (f.next(), f.next()) else {
652                    continue;
653                };
654                let peeled = f.next().filter(|p| !p.is_empty()).unwrap_or(oid);
655                map.entry(peeled.to_string())
656                    .or_default()
657                    .push(name.to_string());
658            }
659            *self.tag_map.borrow_mut() = Some(map);
660        }
661        self.tag_map
662            .borrow()
663            .as_ref()
664            .and_then(|m| m.get(hash).cloned())
665            .unwrap_or_default()
666    }
667
668    /// The refs under `refs/heads` or `refs/tags` (tags
669    /// dereferenced to their commits).
670    fn refs(&self, dir: NodeId, prefix: &str) -> Vec<NodeId> {
671        if let Some(c) = self.nodes.borrow()[dir.0 as usize]
672            .children
673            .borrow()
674            .as_ref()
675        {
676            return c.clone();
677        }
678        let out = self
679            .git(&[
680                "for-each-ref",
681                prefix,
682                "--format=%(refname:short)%00%(objectname)%00%(*objectname)",
683            ])
684            .unwrap_or_default();
685        let mut ids = Vec::new();
686        for line in out.lines() {
687            let mut f = line.split('\u{0}');
688            let (Some(name), Some(oid)) = (f.next(), f.next()) else {
689                continue;
690            };
691            let deref = f.next().unwrap_or("");
692            let commit = if deref.is_empty() { oid } else { deref };
693            self.note_tip(commit);
694            ids.push(self.push_node(
695                Kind::Ref {
696                    name: name.to_string(),
697                    commit: commit.to_string(),
698                },
699                Some(dir),
700            ));
701        }
702        *self.nodes.borrow()[dir.0 as usize].children.borrow_mut() = Some(ids.clone());
703        ids
704    }
705
706    /// The entries of a tree object, as child nodes of `parent`.
707    fn tree_children(&self, parent: NodeId, tree_oid: &str) -> Vec<NodeId> {
708        if let Some(c) = self.nodes.borrow()[parent.0 as usize]
709            .children
710            .borrow()
711            .as_ref()
712        {
713            return c.clone();
714        }
715        let out = self.git(&["ls-tree", "-z", tree_oid]).unwrap_or_default();
716        let mut ids = Vec::new();
717        // "<mode> <type> <oid>\t<name>" records, NUL-terminated by
718        // `-z` so names arrive raw — never C-quoted the way the
719        // newline-delimited default renders non-ASCII paths.
720        for entry in out.split('\u{0}') {
721            let Some((meta, name)) = entry.split_once('\t') else {
722                continue;
723            };
724            let mut f = meta.split(' ');
725            let (Some(mode), Some(entry_type), Some(oid)) = (f.next(), f.next(), f.next()) else {
726                continue;
727            };
728            ids.push(self.push_node(
729                Kind::Entry {
730                    name: name.to_string(),
731                    oid: oid.to_string(),
732                    entry_type: entry_type.to_string(),
733                    mode: mode.to_string(),
734                },
735                Some(parent),
736            ));
737        }
738        *self.nodes.borrow()[parent.0 as usize].children.borrow_mut() = Some(ids.clone());
739        ids
740    }
741
742    /// The paths a commit's diff touches, relative to its first
743    /// parent (the whole tree for a root commit), computed once.
744    fn changed_paths(&self, hash: &str) -> Vec<String> {
745        if let Some(c) = self.changed.borrow().get(hash) {
746            return c.clone();
747        }
748        let out = self
749            .git(&[
750                "diff-tree",
751                "--root",
752                "--no-commit-id",
753                "--name-only",
754                "-z",
755                "-r",
756                hash,
757            ])
758            .unwrap_or_default();
759        // `-z`: NUL-separated, raw paths (never C-quoted), so they
760        // compare equal to the raw names from `ls-tree -z`.
761        let paths: Vec<String> = out
762            .split('\u{0}')
763            .filter(|p| !p.is_empty())
764            .map(str::to_string)
765            .collect();
766        self.changed
767            .borrow_mut()
768            .insert(hash.to_string(), paths.clone());
769        paths
770    }
771
772    /// The commit a tree entry belongs to and the entry's path
773    /// within it.
774    fn entry_context(&self, node: NodeId) -> Option<(String, String)> {
775        let nodes = self.nodes.borrow();
776        let mut parts = Vec::new();
777        let mut cur = Some(node);
778        while let Some(n) = cur {
779            let nd = &nodes[n.0 as usize];
780            match &nd.kind {
781                Kind::Entry { name, .. } => parts.push(name.clone()),
782                Kind::Commit(h) => {
783                    parts.reverse();
784                    return Some((h.clone(), parts.join("/")));
785                }
786                Kind::Ref { commit, .. } => {
787                    parts.reverse();
788                    return Some((commit.clone(), parts.join("/")));
789                }
790                _ => return None,
791            }
792            cur = nd.parent;
793        }
794        None
795    }
796
797    /// The commit hash a node stands for (commits and ref aliases).
798    fn commit_of(&self, node: NodeId) -> Option<String> {
799        match &self.nodes.borrow()[node.0 as usize].kind {
800            Kind::Commit(h) => Some(h.clone()),
801            Kind::Ref { commit, .. } => Some(commit.clone()),
802            _ => None,
803        }
804    }
805
806    /// The nearest commit-backed ancestor, the node itself included:
807    /// a tree entry answers through the commit it was reached under.
808    fn commit_ancestor(&self, node: NodeId) -> Option<String> {
809        let mut cur = Some(node);
810        while let Some(n) = cur {
811            if let Some(h) = self.commit_of(n) {
812                return Some(h);
813            }
814            cur = self.nodes.borrow()[n.0 as usize].parent;
815        }
816        None
817    }
818}
819
820/// Split `rev-list --format=…%x1e` output into `(hash, body)`
821/// records. Each commit's format expansion is terminated by the
822/// ASCII Record Separator (`%x1e`), so a literal `commit ` line
823/// inside a message body (`%s`/`%B`) can never split a record;
824/// the leading `commit <hash>` header of each record supplies the
825/// hash.
826fn split_commit_records(out: &str) -> impl Iterator<Item = (&str, &str)> {
827    out.split('\u{1e}').filter_map(|record| {
828        let rest = record.trim_start().strip_prefix("commit ")?;
829        let (hash, body) = rest.split_once('\n')?;
830        Some((hash.trim(), body))
831    })
832}
833
834fn parse_info(body: &str) -> Option<CommitInfo> {
835    let f: Vec<&str> = body.trim_end_matches('\n').split('\u{0}').collect();
836    if f.len() < 8 {
837        return None;
838    }
839    Some(CommitInfo {
840        author: f[0].to_string(),
841        email: f[1].to_string(),
842        date: f[2].parse().unwrap_or(0),
843        date_offset: f.get(8).and_then(|iso| {
844            // `%ai` ends `±HHMM`; the offset rides the instant for
845            // display only.
846            let tail = iso.trim().rsplit(' ').next()?;
847            let sign = match tail.as_bytes().first()? {
848                b'+' => 1i16,
849                b'-' => -1i16,
850                _ => return None,
851            };
852            let h: i16 = tail.get(1..3)?.parse().ok()?;
853            let m: i16 = tail.get(3..5)?.parse().ok()?;
854            Some(sign * (h * 60 + m))
855        }),
856        committer: f[3].to_string(),
857        subject: f[4].to_string(),
858        message: f[5].trim_end().to_string(),
859        tree: f[6].to_string(),
860        parents: f[7].split_whitespace().map(str::to_string).collect(),
861    })
862}
863
864impl AstAdapter for GitAdapter {
865    fn root(&self) -> NodeId {
866        ROOT
867    }
868
869    /// `/commits/* @| [..k]` before the history is enumerated walks
870    /// k commits and no more (the pushdown scanning round,
871    /// 2026-11-06).
872    fn select(&self, from: NodeId, plan: &quarb::StepPlan<'_>) -> Option<quarb::Selection> {
873        let k = plan.limit?;
874        if from != COMMITS
875            || plan.axis != quarb::PlanAxis::Child
876            || plan.name.is_some()
877            || !plan.conjuncts.is_empty()
878            || !plan.traits.is_empty()
879            || *self.enumerated.borrow()
880        {
881            return None;
882        }
883        Some(quarb::Selection {
884            nodes: self
885                .commits_prefix(k)
886                .into_iter()
887                .map(|id| (id, 1))
888                .collect(),
889            applied: Vec::new(),
890        })
891    }
892
893    fn children(&self, node: NodeId) -> Vec<NodeId> {
894        let kind = self.nodes.borrow()[node.0 as usize].kind.clone();
895        match kind {
896            Kind::Root => {
897                // branches, tags, commits — plus HEAD as a ref
898                // alias, interned once.
899                if self.nodes.borrow()[ROOT.0 as usize]
900                    .children
901                    .borrow()
902                    .is_none()
903                {
904                    let mut ids = vec![BRANCHES, TAGS, COMMITS];
905                    if let Ok(h) = self.git(&["rev-parse", "HEAD"]) {
906                        ids.push(self.push_node(
907                            Kind::Ref {
908                                name: "HEAD".to_string(),
909                                commit: h.trim().to_string(),
910                            },
911                            Some(ROOT),
912                        ));
913                    }
914                    *self.nodes.borrow()[ROOT.0 as usize].children.borrow_mut() = Some(ids);
915                }
916                self.nodes.borrow()[ROOT.0 as usize]
917                    .children
918                    .borrow()
919                    .clone()
920                    .unwrap_or_default()
921            }
922            Kind::Dir("branches") => self.refs(BRANCHES, "refs/heads"),
923            Kind::Dir("tags") => self.refs(TAGS, "refs/tags"),
924            Kind::Dir(_) => self.enumerate_commits(),
925            Kind::Ref { commit, .. } | Kind::Commit(commit) => {
926                let Some(info) = self.commit_info(&commit) else {
927                    return Vec::new();
928                };
929                self.tree_children(node, &info.tree)
930            }
931            Kind::Entry {
932                oid, entry_type, ..
933            } => {
934                if entry_type == "tree" {
935                    self.tree_children(node, &oid)
936                } else {
937                    Vec::new()
938                }
939            }
940        }
941    }
942
943    /// Literal names under `/commits` go straight through
944    /// `rev-parse` — unique prefixes, `HEAD~2`, `v1.0^{}` — with
945    /// no enumeration.
946    fn children_named(&self, node: NodeId, name: &str) -> Vec<NodeId> {
947        if node == COMMITS {
948            // A known full hash answers from the intern map;
949            // anything else (prefixes, HEAD~2, tag^{}) goes
950            // through rev-parse — enumeration never required.
951            if let Some(&id) = self.commit_nodes.borrow().get(name) {
952                return vec![id];
953            }
954            let Ok(out) = self.git(&[
955                "rev-parse",
956                "--verify",
957                "--quiet",
958                &format!("{name}^{{commit}}"),
959            ]) else {
960                return Vec::new();
961            };
962            return vec![self.commit_node(out.trim())];
963        }
964        self.children(node)
965            .into_iter()
966            .filter(|&c| self.name(c).as_deref() == Some(name))
967            .collect()
968    }
969
970    fn name(&self, node: NodeId) -> Option<String> {
971        match &self.nodes.borrow()[node.0 as usize].kind {
972            Kind::Root => None,
973            Kind::Dir(d) => Some(d.to_string()),
974            Kind::Ref { name, .. } => Some(name.clone()),
975            Kind::Commit(h) => Some(h.clone()),
976            Kind::Entry { name, .. } => Some(name.clone()),
977        }
978    }
979
980    fn parent(&self, node: NodeId) -> Option<NodeId> {
981        self.nodes.borrow()[node.0 as usize].parent
982    }
983
984    /// The kind first (spec: Traits): `<repository>` at the root,
985    /// `<dir>` for a listing, then `<commit>`, `<branch>`, `<tag>`,
986    /// `<tree>`, `<blob>`.
987    fn traits(&self, node: NodeId) -> Vec<String> {
988        let nodes = self.nodes.borrow();
989        let t = match &nodes[node.0 as usize].kind {
990            Kind::Root => "repository",
991            Kind::Dir(_) => "dir",
992            Kind::Commit(_) => "commit",
993            Kind::Ref { .. } => match nodes[node.0 as usize].parent {
994                Some(TAGS) => "tag",
995                Some(BRANCHES) => "branch",
996                _ => "commit",
997            },
998            Kind::Entry { entry_type, .. } => {
999                let base = if entry_type == "tree" { "tree" } else { "blob" };
1000                let mut out = vec![base.to_string()];
1001                drop(nodes);
1002                // <changed>: this path is in its commit's diff
1003                // (blobs by exact path, trees when any descendant
1004                // changed).
1005                if let Some((hash, path)) = self.entry_context(node) {
1006                    let prefix = format!("{path}/");
1007                    if self
1008                        .changed_paths(&hash)
1009                        .iter()
1010                        .any(|p| *p == path || p.starts_with(&prefix))
1011                    {
1012                        out.push("changed".to_string());
1013                    }
1014                }
1015                return out;
1016            }
1017        };
1018        vec![t.to_string()]
1019    }
1020
1021    /// Commit header fields (ref aliases answer for their commit).
1022    fn property(&self, node: NodeId, name: &str) -> Option<Value> {
1023        let hash = self.commit_of(node)?;
1024        let info = self.commit_info(&hash)?;
1025        Some(match name {
1026            "author" => Value::Str(info.author),
1027            "email" => Value::Str(info.email),
1028            "date" => Value::Instant {
1029                secs: info.date,
1030                nanos: 0,
1031                offset_min: info.date_offset,
1032                calendar: Default::default(),
1033            },
1034            "committer" => Value::Str(info.committer),
1035            "subject" => Value::Str(info.subject),
1036            "message" => Value::Str(info.message),
1037            "tree" => Value::Str(info.tree),
1038            "hash" => Value::Str(hash),
1039            "parent" => Value::Str(info.parents.first()?.clone()),
1040            // The paths this commit's diff touches (vs its first
1041            // parent) — deletions included, unlike the tree view.
1042            "changed" => Value::list(
1043                self.changed_paths(&hash)
1044                    .into_iter()
1045                    .map(Value::Str)
1046                    .collect(),
1047            ),
1048            _ => return None,
1049        })
1050    }
1051
1052    /// Data provenance: the repository path as the source; the
1053    /// nearest commit-backed ancestor's author date as the instant
1054    /// (a tree entry answers "this repo, as of that commit" — the
1055    /// same instant `::date` mints). The structural dirs and the
1056    /// root have no commit ancestor and answer source only. No
1057    /// dpid — the commit hash stays on `::hash` / `:::short`.
1058    fn provenance(&self, node: NodeId) -> quarb::Provenance {
1059        let instant = self
1060            .commit_ancestor(node)
1061            .and_then(|h| self.commit_info(&h))
1062            .map(|info| (info.date, 0, info.date_offset));
1063        quarb::Provenance {
1064            source: Some(self.repo.display().to_string()),
1065            path: None,
1066            instant_from: instant.map(|_| quarb::InstantFrom::Node),
1067            instant,
1068            dpid: None,
1069        }
1070    }
1071
1072    /// A blob's content (text, lossily decoded).
1073    fn default_value(&self, node: NodeId) -> Option<Value> {
1074        let (oid, is_blob) = match &self.nodes.borrow()[node.0 as usize].kind {
1075            Kind::Entry {
1076                oid, entry_type, ..
1077            } => (oid.clone(), entry_type == "blob"),
1078            _ => return None,
1079        };
1080        if !is_blob {
1081            return None;
1082        }
1083        // The blob's bytes under the mount's rule; one that decodes
1084        // under none has no text (the leaf stays a leaf).
1085        self.blob_bytes(&oid)
1086            .ok()
1087            .and_then(|bytes| self.decoding.decode(&oid, &bytes).ok())
1088            .map(|d| Value::Str(d.text))
1089    }
1090
1091    /// Commits: `:::short`, `:::n-parents`, `:::tags`,
1092    /// `:::n-tags`. Entries: `:::type`, `:::mode`, `:::size`,
1093    /// `:::hash`.
1094    /// Ruling #29: this adapter's property surface is closed — a
1095    /// commit object cannot grow fields — so its annotations
1096    /// answer at `::` too. `hash` is in the list on purpose:
1097    /// commits expose the oid as a property and tree entries as
1098    /// metadata, but it is one concept — this node's object id —
1099    /// and aliasing is what makes `::hash` answer everywhere in
1100    /// the arbor instead of falling silently null on entries.
1101    fn aliased_metadata(&self, _node: NodeId) -> &'static [&'static str] {
1102        &[
1103            "short",
1104            "hash",
1105            "n-parents",
1106            "n-changed",
1107            "tags",
1108            "n-tags",
1109            "type",
1110            "mode",
1111            "size",
1112        ]
1113    }
1114
1115    /// The `:::` keys this adapter answers (`:meta` lists the ones
1116
1117    /// a node answers).
1118
1119    fn metadata_catalogue(&self) -> &'static [&'static str] {
1120        &[
1121            "short",
1122            "n-parents",
1123            "n-changed",
1124            "tags",
1125            "n-tags",
1126            "type",
1127            "mode",
1128            "hash",
1129            "size",
1130        ]
1131    }
1132
1133    fn metadata(&self, node: NodeId, key: &str) -> Option<Value> {
1134        if let Some(hash) = self.commit_of(node) {
1135            return match key {
1136                "short" => Some(Value::Str(hash[..7.min(hash.len())].to_string())),
1137                "n-parents" => Some(Value::Int(self.commit_info(&hash)?.parents.len() as i64)),
1138                "n-changed" => Some(Value::Int(self.changed_paths(&hash).len() as i64)),
1139                "tags" => Some(Value::list(
1140                    self.tags_at(&hash).into_iter().map(Value::Str).collect(),
1141                )),
1142                "n-tags" => Some(Value::Int(self.tags_at(&hash).len() as i64)),
1143                _ => None,
1144            };
1145        }
1146        let (oid, entry_type, mode) = match &self.nodes.borrow()[node.0 as usize].kind {
1147            Kind::Entry {
1148                oid,
1149                entry_type,
1150                mode,
1151                ..
1152            } => (oid.clone(), entry_type.clone(), mode.clone()),
1153            _ => return None,
1154        };
1155        match key {
1156            "type" => Some(Value::Str(entry_type)),
1157            "mode" => Some(Value::Str(mode)),
1158            "hash" => Some(Value::Str(oid)),
1159            "size" => self.blob_size(&oid).map(|n| Value::bytes(n as i64)),
1160            _ => None,
1161        }
1162    }
1163
1164    /// `::parent-->` — the first parent (the hint is unused: the
1165    /// target is inherently a commit).
1166    fn resolve(&self, node: NodeId, property: &str, _hint: Option<&str>) -> Option<NodeId> {
1167        if property != "parent" {
1168            return None;
1169        }
1170        let hash = self.commit_of(node)?;
1171        let first = self.commit_info(&hash)?.parents.first()?.clone();
1172        Some(self.commit_node(&first))
1173    }
1174
1175    /// A history is acyclic by its nature: a commit's parents
1176    /// precede it, so a walk over `parent` never returns (spec:
1177    /// Model Files, Acyclic links — a source that knows this of its
1178    /// own links carries the promise without a declaration).
1179    fn acyclic_link(&self, label: &str) -> Option<String> {
1180        (label == "parent")
1181            .then(|| "the commit history (a commit's parents precede it)".to_string())
1182    }
1183
1184    /// Every parent is an outgoing `parent` edge (merges fan out).
1185    fn links(&self, node: NodeId) -> Vec<(String, NodeId)> {
1186        let Some(hash) = self.commit_of(node) else {
1187            return Vec::new();
1188        };
1189        let Some(info) = self.commit_info(&hash) else {
1190            return Vec::new();
1191        };
1192        info.parents
1193            .iter()
1194            .map(|p| ("parent".to_string(), self.commit_node(p)))
1195            .collect()
1196    }
1197
1198    /// A commit's reference is its parent: the bare arrows
1199    /// (`/HEAD-->`, `/HEAD<--`) read it.
1200    fn ref_property(&self, node: NodeId) -> Option<String> {
1201        self.commit_of(node).map(|_| "parent".to_string())
1202    }
1203
1204    /// `<--(::parent)` from the enumeration, with no walk: the
1205    /// commits whose `parent` resolves here — `::parent-->` follows
1206    /// the FIRST parent, so a merge counts under its first parent
1207    /// only. Any other property has no referrers; with no property
1208    /// named the question stays the engine's.
1209    fn reverse_resolve(
1210        &self,
1211        node: NodeId,
1212        property: Option<&str>,
1213        _hint: Option<&str>,
1214    ) -> Option<Vec<NodeId>> {
1215        let hash = self.commit_of(node)?;
1216        // With no property named: the commit's reference property.
1217        if property.is_some_and(|p| p != "parent") {
1218            return Some(Vec::new());
1219        }
1220        // The index lists every child; `::parent-->` follows the
1221        // first parent, so keep the children whose first parent is
1222        // here.
1223        let children: Vec<String> = self
1224            .children_of(&hash)
1225            .into_iter()
1226            .filter(|h| {
1227                self.commit_info(h)
1228                    .is_some_and(|i| i.parents.first() == Some(&hash))
1229            })
1230            .collect();
1231        Some(children.iter().map(|h| self.commit_node(h)).collect())
1232    }
1233
1234    /// The commits whose parent is here (the children — served
1235    /// from the enumeration, so this loads the commit list).
1236    fn backlinks(&self, node: NodeId) -> Vec<(String, NodeId)> {
1237        let Some(hash) = self.commit_of(node) else {
1238            return Vec::new();
1239        };
1240        self.children_of(&hash)
1241            .into_iter()
1242            .map(|h| ("parent".to_string(), self.commit_node(&h)))
1243            .collect()
1244    }
1245}
1246
1247#[cfg(test)]
1248mod tests {
1249    use super::*;
1250
1251    // Regression: a commit whose subject and body contain the word
1252    // "commit " must not corrupt enumeration. Records are delimited
1253    // by the trailing %x1e sentinel, not by "commit " in the body.
1254    #[test]
1255    fn record_split_survives_commit_word_in_body() {
1256        let out = "commit aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\n\
1257Ann\u{0}ann@example\u{0}1000\u{0}Ann\u{0}\
1258Revert commit deadbeef\u{0}\
1259Revert commit deadbeef\n\nThis reverts commit deadbeef.\u{0}\
1260tttttttttttttttttttttttttttttttttttttttt\u{0}\
1261pppppppppppppppppppppppppppppppppppppppp\u{0}\
12622026-07-15 12:00:00 +0100\u{1e}\n\
1263commit bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\n\
1264Bo\u{0}bo@example\u{0}2000\u{0}Bo\u{0}second\u{0}second\u{0}\
1265tttttttttttttttttttttttttttttttttttttttt\u{0}\u{0}\
12662026-07-15 13:00:00 +0100\u{1e}\n";
1267        let recs: Vec<(&str, &str)> = split_commit_records(out).collect();
1268        assert_eq!(recs.len(), 2);
1269        assert_eq!(recs[0].0, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
1270        let a = parse_info(recs[0].1).expect("first record parses");
1271        assert_eq!(a.author, "Ann");
1272        assert_eq!(a.subject, "Revert commit deadbeef");
1273        assert_eq!(
1274            a.message,
1275            "Revert commit deadbeef\n\nThis reverts commit deadbeef."
1276        );
1277        assert_eq!(recs[1].0, "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb");
1278        let b = parse_info(recs[1].1).expect("second record parses");
1279        assert_eq!(b.subject, "second");
1280    }
1281}