grit_lib/
tree_sha256.rs

1//! SHA-256 tree digest over repository file contents ([tree-sha256] spec).
2//!
3//! [tree-sha256]: https://github.com/schacon/tree-sha256
4//!
5//! ```rust
6//! use grit_lib::tree_sha256::TreeSha256Options;
7//! # fn main() {
8//! let _ = TreeSha256Options::default();
9//! # }
10//! ```
11
12/// Tag header name for the tree-sha256 digest (reference tool: [`HEADER`](https://github.com/schacon/tree-sha256)).
13pub const TREE_SHA256_HEADER: &str = "tree-sha256";
14
15/// Tag header naming a submodule path excluded from the digest.
16pub const TREE_SHA256_EXCLUDED_HEADER: &str = "tree-sha256-excluded";
17
18mod tag_verify;
19
20pub(crate) use tag_verify::verify_tag_data;
21pub use tag_verify::{
22    parse_tree_sha256_tag_headers, verify_tag, SignatureVerdict, TagVerification, TagVerifyOptions,
23    TreeSha256TagHeaders, TreeSha256Verdict,
24};
25
26use std::fmt;
27use std::path::{Path, PathBuf};
28use std::str::FromStr;
29use std::time::Duration;
30
31use crate::config::ConfigSet;
32use crate::diff::submodule_embedded_git_dir;
33use crate::environment::RepositoryOptions;
34use crate::error::{Error, Result, SubmoduleError};
35use crate::hash::{try_par_hash_with, try_par_hash_with_force, PAR_HASH_MIN_ITEMS};
36use crate::objects::{
37    iter_extra_headers, parse_commit, parse_tree, remove_header_lines, HashAlgo, ObjectId,
38    ObjectKind, TagData, TreeEntry,
39};
40use crate::parallel::ParallelHashError;
41use crate::parallel::ParallelOp;
42use crate::repo::Repository;
43use crate::submodule_gitdir::{submodule_modules_git_dir, submodule_path_config_enabled};
44
45/// 32-byte tree-sha256 digest.
46#[derive(Clone, Copy, PartialEq, Eq, Hash)]
47pub struct TreeSha256(pub [u8; 32]);
48
49impl TreeSha256 {
50    /// Digest bytes.
51    #[must_use]
52    pub const fn bytes(&self) -> &[u8; 32] {
53        &self.0
54    }
55
56    /// Lowercase hex encoding (64 characters).
57    #[must_use]
58    pub fn to_hex(&self) -> String {
59        let mut s = String::with_capacity(64);
60        for b in self.0 {
61            use std::fmt::Write as _;
62            let _ = write!(s, "{b:02x}");
63        }
64        s
65    }
66}
67
68impl fmt::Display for TreeSha256 {
69    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
70        f.write_str(&self.to_hex())
71    }
72}
73
74impl fmt::Debug for TreeSha256 {
75    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
76        f.debug_tuple("TreeSha256").field(&self.to_hex()).finish()
77    }
78}
79
80impl FromStr for TreeSha256 {
81    type Err = Error;
82
83    fn from_str(s: &str) -> Result<Self> {
84        let s = s.trim();
85        if s.len() != 64 || !s.bytes().all(|b| b.is_ascii_hexdigit()) {
86            return Err(Error::TreeSha256InvalidHex);
87        }
88        let mut out = [0_u8; 32];
89        for (i, chunk) in s.as_bytes().chunks(2).enumerate() {
90            let hi = hex_nibble(chunk[0])?;
91            let lo = hex_nibble(chunk[1])?;
92            out[i] = (hi << 4) | lo;
93        }
94        Ok(Self(out))
95    }
96}
97
98fn hex_nibble(b: u8) -> Result<u8> {
99    match b {
100        b'0'..=b'9' => Ok(b - b'0'),
101        b'a'..=b'f' => Ok(b - b'a' + 10),
102        b'A'..=b'F' => Ok(b - b'A' + 10),
103        _ => Err(Error::TreeSha256InvalidHex),
104    }
105}
106
107/// Submodule exclusion and glob options for [`Repository::tree_sha256`].
108#[derive(Debug, Clone, Default, PartialEq, Eq)]
109#[non_exhaustive]
110pub struct TreeSha256Options {
111    /// Glob patterns; `*` matches any byte including `/`, `?` one byte. Trailing `/` is trimmed.
112    pub exclude_globs: Vec<String>,
113    /// Submodule paths excluded exactly (full path from repository root).
114    pub exclude_exact: Vec<String>,
115}
116
117/// Outcome of a successful tree-sha256 computation.
118#[derive(Debug, Clone, PartialEq, Eq)]
119pub struct TreeSha256Report {
120    /// Final tree-sha256 digest.
121    pub digest: TreeSha256,
122    /// Regular file, executable, and symlink entries hashed.
123    pub files: usize,
124    /// Submodule entries whose contents were hashed recursively.
125    pub submodules: usize,
126    /// Excluded submodule paths and the gitlink commit recorded.
127    pub excluded: Vec<(String, ObjectId)>,
128    /// Submodule paths where a cycle was detected in the commit chain.
129    pub cycles: Vec<String>,
130}
131
132/// Why a submodule could not be hashed.
133#[derive(Debug, Clone, PartialEq, Eq)]
134#[non_exhaustive]
135pub enum MissingSubmoduleReason {
136    /// Submodule work tree or git directory is not present.
137    NotCheckedOut,
138    /// Gitlink commit is missing from the submodule object database.
139    MissingCommit,
140}
141
142/// One submodule that blocked hashing.
143#[derive(Debug, Clone, PartialEq, Eq)]
144pub struct MissingSubmodule {
145    /// Full path from the superproject root.
146    pub path: String,
147    /// What went wrong.
148    pub reason: MissingSubmoduleReason,
149}
150
151/// Compute tree-sha256 for `repo` at `oid` (peels annotated tags to commits).
152///
153/// # Errors
154///
155/// Returns [`Error::TreeSha256MissingSubmodules`] when any submodule required for
156/// hashing is missing; the error lists every missing path.
157pub fn tree_sha256(
158    repo: &Repository,
159    oid: ObjectId,
160    options: &TreeSha256Options,
161) -> Result<TreeSha256Report> {
162    tree_sha256_with_chain(repo, oid, options, &[], "")
163}
164
165fn tree_sha256_with_chain(
166    repo: &Repository,
167    oid: ObjectId,
168    options: &TreeSha256Options,
169    parent_chain: &[ObjectId],
170    path_prefix_from_root: &str,
171) -> Result<TreeSha256Report> {
172    let tree_oid = peel_to_tree(repo, oid)?;
173    let root_commit = peel_to_commit(repo, oid)?;
174    let mut commit_chain: Vec<ObjectId> = parent_chain.to_vec();
175    if let Some(c) = root_commit {
176        if !commit_chain.contains(&c) {
177            commit_chain.push(c);
178        }
179    }
180    let mut ctx = ComputeCtx {
181        repo,
182        options,
183        commit_chain,
184        path_prefix_from_root: path_prefix_from_root.to_owned(),
185        records: Vec::new(),
186        missing: Vec::new(),
187        files: 0,
188        submodules: 0,
189        excluded: Vec::new(),
190        cycles: Vec::new(),
191        blob_jobs: Vec::new(),
192    };
193    ctx.walk_tree(tree_oid, b"")?;
194    ctx.finish_blob_jobs()?;
195    if !ctx.missing.is_empty() {
196        return Err(Error::TreeSha256MissingSubmodules(ctx.missing));
197    }
198    ctx.records
199        .sort_by(|a, b| record_sort_key(a).cmp(record_sort_key(b)));
200    let mut concat = Vec::new();
201    for rec in &ctx.records {
202        concat.extend_from_slice(rec);
203    }
204    let digest_bytes = HashAlgo::Sha256.checksum_digest(&concat);
205    let digest_arr: [u8; 32] = digest_bytes
206        .as_slice()
207        .try_into()
208        .map_err(|_| Error::Message("sha256 digest length".into()))?;
209    let digest = TreeSha256(digest_arr);
210    Ok(TreeSha256Report {
211        digest,
212        files: ctx.files,
213        submodules: ctx.submodules,
214        excluded: ctx.excluded,
215        cycles: ctx.cycles,
216    })
217}
218
219fn peel_to_tree(repo: &Repository, oid: ObjectId) -> Result<ObjectId> {
220    let (peeled, kind) = repo.odb().peel_tags(oid)?;
221    match kind {
222        ObjectKind::Tree => Ok(peeled),
223        ObjectKind::Commit => {
224            let obj = repo.odb().read(&peeled)?;
225            Ok(parse_commit(&obj.data)?.tree)
226        }
227        other => Err(Error::TreeSha256InvalidRevision { found: other }),
228    }
229}
230
231fn peel_to_commit(repo: &Repository, oid: ObjectId) -> Result<Option<ObjectId>> {
232    repo.odb().peel_to_commit(oid)
233}
234
235fn record_sort_key(record: &[u8]) -> &[u8] {
236    let Some(sp) = record.iter().position(|&b| b == b' ') else {
237        return record;
238    };
239    let start = sp + 1;
240    let end = record.iter().rposition(|&b| b == 0).unwrap_or(record.len());
241    &record[start..end]
242}
243
244struct BlobJob {
245    path: Vec<u8>,
246    oid: ObjectId,
247}
248
249struct ComputeCtx<'a> {
250    repo: &'a Repository,
251    options: &'a TreeSha256Options,
252    commit_chain: Vec<ObjectId>,
253    /// Path from the top-level repository to this walk's root (empty at the superproject).
254    path_prefix_from_root: String,
255    records: Vec<Vec<u8>>,
256    missing: Vec<MissingSubmodule>,
257    files: usize,
258    submodules: usize,
259    excluded: Vec<(String, ObjectId)>,
260    cycles: Vec<String>,
261    blob_jobs: Vec<BlobJob>,
262}
263
264impl ComputeCtx<'_> {
265    fn walk_tree(&mut self, tree_oid: ObjectId, prefix: &[u8]) -> Result<()> {
266        let obj = self.repo.odb().read(&tree_oid)?;
267        if obj.kind != ObjectKind::Tree {
268            return Err(Error::CorruptObject(format!("expected tree {tree_oid}")));
269        }
270        let entries = parse_tree(&obj.data)?;
271        for TreeEntry { mode, name, oid } in entries {
272            if name.contains(&b'/') || name.contains(&0) {
273                return Err(Error::CorruptObject("invalid tree entry name".into()));
274            }
275            let path = join_path_bytes(prefix, &name);
276            const S_IFMT: u32 = 0o170000;
277            const S_IFDIR: u32 = 0o040000;
278            const S_IFREG: u32 = 0o100000;
279            const S_IFLNK: u32 = 0o120000;
280            const S_IFGITLINK: u32 = 0o160000;
281            match mode & S_IFMT {
282                S_IFDIR => {
283                    let mut child_prefix = path;
284                    child_prefix.push(b'/');
285                    self.walk_tree(oid, &child_prefix)?;
286                }
287                S_IFREG | S_IFLNK => {
288                    self.blob_jobs.push(BlobJob { path, oid });
289                }
290                S_IFGITLINK => self.handle_gitlink(&path, oid)?,
291                _ => {}
292            }
293        }
294        Ok(())
295    }
296
297    fn handle_gitlink(&mut self, path: &[u8], gitlink: ObjectId) -> Result<()> {
298        let global_path = self.global_path_from_root(path);
299        if self.is_excluded(path) {
300            self.push_excluded_record(path, gitlink);
301            self.excluded.push((global_path.clone(), gitlink));
302            return Ok(());
303        }
304        if gitlink_in_commit_chain(&self.commit_chain, gitlink) {
305            self.push_cycle_record(path, gitlink);
306            self.cycles.push(global_path.clone());
307            return Ok(());
308        }
309        let Some(sub_repo) = self.open_submodule_repo(path)? else {
310            self.missing.push(MissingSubmodule {
311                path: global_path,
312                reason: MissingSubmoduleReason::NotCheckedOut,
313            });
314            return Ok(());
315        };
316        if sub_repo.odb().read(&gitlink).is_err() {
317            self.missing.push(MissingSubmodule {
318                path: global_path,
319                reason: MissingSubmoduleReason::MissingCommit,
320            });
321            return Ok(());
322        }
323        self.commit_chain.push(gitlink);
324        let sub_opts = TreeSha256Options {
325            exclude_globs: self.options.exclude_globs.clone(),
326            exclude_exact: self.options.exclude_exact.clone(),
327        };
328        match tree_sha256_with_chain(
329            &sub_repo,
330            gitlink,
331            &sub_opts,
332            &self.commit_chain,
333            &global_path,
334        ) {
335            Ok(sub_report) => {
336                self.commit_chain.pop();
337                self.push_submodule_record(path, &sub_report.digest);
338                self.files += sub_report.files;
339                self.submodules += 1 + sub_report.submodules;
340                // Submodule reports already record excluded/cycle paths from the top repo.
341                self.excluded.extend(sub_report.excluded);
342                self.cycles.extend(sub_report.cycles);
343            }
344            Err(Error::TreeSha256MissingSubmodules(mut miss)) => {
345                self.commit_chain.pop();
346                // Child missing paths are already qualified to the top repository.
347                self.missing.append(&mut miss);
348            }
349            Err(e) => {
350                self.commit_chain.pop();
351                return Err(e);
352            }
353        }
354        Ok(())
355    }
356
357    fn global_path_from_root(&self, local_path: &[u8]) -> String {
358        let local = path_bytes_to_string(local_path);
359        if self.path_prefix_from_root.is_empty() {
360            return local;
361        }
362        qualify_submodule_path(&self.path_prefix_from_root, &local)
363    }
364
365    fn is_excluded(&self, path: &[u8]) -> bool {
366        let global = self.global_path_from_root(path);
367        if self
368            .options
369            .exclude_exact
370            .iter()
371            .any(|p| p.as_bytes() == path || p == &global)
372        {
373            return true;
374        }
375        self.options
376            .exclude_globs
377            .iter()
378            .any(|g| path_matches_glob_bytes(path, g.as_bytes()) || path_matches_glob(&global, g))
379    }
380
381    fn open_submodule_repo(&self, rel_path: &[u8]) -> Result<Option<Repository>> {
382        let wt = match self.repo.work_tree() {
383            Some(w) => w,
384            None => return Ok(None),
385        };
386        let sub_wt = wt.join(path_bytes_to_os(rel_path));
387        if !sub_wt.is_dir() {
388            return Ok(None);
389        }
390        if let Some(git_dir) = submodule_embedded_git_dir(&sub_wt) {
391            return Repository::open(&git_dir, &RepositoryOptions::empty().with_work_tree(sub_wt))
392                .map(Some);
393        }
394        let cfg = self.repo.config()?;
395        let rel_str = path_bytes_to_string(rel_path);
396        let name = submodule_name_for_path(&cfg, &rel_str).unwrap_or(rel_str);
397        let git_dir = resolve_submodule_git_dir(wt, self.repo.common_git_dir(), &cfg, &name)?;
398        if !git_dir.join("HEAD").exists() {
399            return Ok(None);
400        }
401        Repository::open(&git_dir, &RepositoryOptions::empty().with_work_tree(sub_wt)).map(Some)
402    }
403
404    fn finish_blob_jobs(&mut self) -> Result<()> {
405        if self.blob_jobs.is_empty() {
406            return Ok(());
407        }
408        let cfg = self.repo.config()?;
409        // Blob SHA-256 is CPU-bound; use `pack.threads` (defaults to all CPUs), not
410        // `DiffContent` (serial unless `core.preloadIndex` is enabled).
411        let threads = self
412            .repo
413            .thread_policy()
414            .try_resolve(ParallelOp::PackWrite, &cfg)
415            .map(|opts| opts.parallelism().threads())
416            .unwrap_or_else(|_| {
417                self.repo
418                    .thread_policy()
419                    .resolve(ParallelOp::DiffContent, &cfg)
420                    .parallelism()
421                    .threads()
422            });
423        let odb = self.repo.odb();
424        let hash_one = |job: &BlobJob| {
425            let obj = odb.read(&job.oid)?;
426            if !matches!(obj.kind, ObjectKind::Blob) {
427                return Err(Error::CorruptObject(format!("expected blob {}", job.oid)));
428            }
429            Ok(hex_sha256_content(&obj.data))
430        };
431        let hashed: Vec<String> = if self.blob_jobs.len() >= PAR_HASH_MIN_ITEMS {
432            try_par_hash_with_force(&self.blob_jobs, threads, hash_one)
433        } else {
434            let mut total_bytes = 0_usize;
435            for job in &self.blob_jobs {
436                total_bytes += odb.read_info(&job.oid)?.size as usize;
437            }
438            try_par_hash_with(&self.blob_jobs, threads, total_bytes.max(1), hash_one)
439        }
440        .map_err(|e| match e {
441            ParallelHashError::Task(err) => err,
442        })?;
443        for (job, hex) in self.blob_jobs.iter().zip(hashed) {
444            self.records.push(file_record(&hex, &job.path));
445            self.files += 1;
446        }
447        Ok(())
448    }
449
450    fn push_submodule_record(&mut self, path: &[u8], digest: &TreeSha256) {
451        let mut rec = digest.to_hex().into_bytes();
452        rec.push(b' ');
453        rec.extend_from_slice(path);
454        if !path.ends_with(b"/") {
455            rec.push(b'/');
456        }
457        rec.push(0);
458        self.records.push(rec);
459    }
460
461    fn push_cycle_record(&mut self, path: &[u8], commit: ObjectId) {
462        let mut rec = b"cycle:".to_vec();
463        rec.extend_from_slice(commit.to_hex().as_bytes());
464        rec.push(b' ');
465        rec.extend_from_slice(path);
466        if !path.ends_with(b"/") {
467            rec.push(b'/');
468        }
469        rec.push(0);
470        self.records.push(rec);
471    }
472
473    fn push_excluded_record(&mut self, path: &[u8], commit: ObjectId) {
474        let mut rec = b"excluded:".to_vec();
475        rec.extend_from_slice(commit.to_hex().as_bytes());
476        rec.push(b' ');
477        rec.extend_from_slice(path);
478        if !path.ends_with(b"/") {
479            rec.push(b'/');
480        }
481        rec.push(0);
482        self.records.push(rec);
483    }
484}
485
486fn join_path_bytes(prefix: &[u8], name: &[u8]) -> Vec<u8> {
487    let mut path = Vec::with_capacity(prefix.len().saturating_add(name.len()));
488    path.extend_from_slice(prefix);
489    path.extend_from_slice(name);
490    path
491}
492
493fn path_bytes_to_string(path: &[u8]) -> String {
494    String::from_utf8_lossy(path).into_owned()
495}
496
497fn path_bytes_to_os(path: &[u8]) -> std::ffi::OsString {
498    #[cfg(unix)]
499    {
500        use std::os::unix::ffi::OsStrExt;
501        std::ffi::OsStr::from_bytes(path).to_os_string()
502    }
503    #[cfg(not(unix))]
504    {
505        path_bytes_to_string(path).into()
506    }
507}
508
509fn qualify_submodule_path(gitlink_path: &str, sub_path: &str) -> String {
510    if sub_path.is_empty() {
511        return gitlink_path.to_owned();
512    }
513    let base = gitlink_path.trim_end_matches('/');
514    format!("{base}/{sub_path}")
515}
516
517fn file_record(content_hex: &str, path: &[u8]) -> Vec<u8> {
518    let mut rec = Vec::with_capacity(content_hex.len() + path.len() + 2);
519    rec.extend_from_slice(content_hex.as_bytes());
520    rec.push(b' ');
521    rec.extend_from_slice(path);
522    rec.push(0);
523    rec
524}
525
526fn hex_sha256_content(data: &[u8]) -> String {
527    let digest = HashAlgo::Sha256.checksum_digest(data);
528    let mut s = String::with_capacity(64);
529    for b in digest {
530        use std::fmt::Write as _;
531        let _ = write!(s, "{b:02x}");
532    }
533    s
534}
535
536fn resolve_submodule_git_dir(
537    work_tree: &Path,
538    super_git_dir: &Path,
539    cfg: &ConfigSet,
540    submodule_name: &str,
541) -> Result<PathBuf> {
542    if submodule_path_config_enabled(super_git_dir) {
543        let key = format!("submodule.{submodule_name}.gitdir");
544        let value = cfg.get(&key).ok_or_else(|| {
545            Error::Submodule(SubmoduleError::GitDirNotConfigured {
546                name: submodule_name.to_owned(),
547            })
548        })?;
549        Ok(resolve_gitdir_value(work_tree, &value))
550    } else {
551        Ok(submodule_modules_git_dir(super_git_dir, submodule_name))
552    }
553}
554
555fn resolve_gitdir_value(work_tree: &Path, gitdir_cfg: &str) -> PathBuf {
556    let p = Path::new(gitdir_cfg.trim());
557    if p.is_absolute() {
558        p.to_path_buf()
559    } else {
560        work_tree.join(p)
561    }
562}
563
564fn submodule_name_for_path(cfg: &ConfigSet, path: &str) -> Option<String> {
565    for e in cfg.entries() {
566        let key = &e.key;
567        if let Some(rest) = key.strip_prefix("submodule.") {
568            if let Some(name) = rest.strip_suffix(".path") {
569                if e.value.as_deref() == Some(path) {
570                    return Some(name.to_owned());
571                }
572            }
573        }
574    }
575    None
576}
577
578#[must_use]
579pub(crate) fn gitlink_in_commit_chain(chain: &[ObjectId], gitlink: ObjectId) -> bool {
580    chain.contains(&gitlink)
581}
582
583/// Tree-sha256 digest, counts, and timing from explicit tag creation (`CreateTagRequest::tree_sha256`).
584#[derive(Debug, Clone, PartialEq)]
585pub struct TagTreeSha256Outcome {
586    /// Headers written on the tag object.
587    pub claim: TreeSha256Claim,
588    /// Full hash report (files, submodules, excluded gitlinks).
589    pub report: TreeSha256Report,
590    /// Wall time spent computing the digest.
591    pub hash_elapsed: Duration,
592}
593
594/// Digest and excluded submodule paths recorded on an annotated tag.
595#[derive(Debug, Clone, PartialEq, Eq)]
596pub struct TreeSha256Claim {
597    /// Recorded tree-sha256 digest.
598    pub digest: TreeSha256,
599    /// Submodule paths left out of the digest (sorted when written with [`Self::apply_to_tag`]).
600    ///
601    /// Values must be non-empty and must not contain NUL or newline when passed to
602    /// [`Self::apply_to_tag`].
603    pub excluded: Vec<String>,
604}
605
606/// Failure modes when reading or validating a [`TreeSha256Claim`] from tag headers.
607#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
608pub enum TreeSha256ClaimError {
609    /// More than one `tree-sha256` header appeared after `tagger`.
610    #[error("duplicate tree-sha256 header in tag")]
611    DuplicateDigestHeader,
612    /// A `tree-sha256-excluded` path was empty or contained NUL or newline.
613    #[error("invalid tree-sha256-excluded path")]
614    InvalidExcludedPath,
615}
616
617impl TreeSha256Claim {
618    /// Read a claim from post-`tagger` extra headers on `tag`.
619    ///
620    /// Returns `Ok(None)` when no `tree-sha256` header is present. Commit objects are not
621    /// supported.
622    ///
623    /// # Errors
624    ///
625    /// Returns [`TreeSha256ClaimError::DuplicateDigestHeader`] or
626    /// [`TreeSha256ClaimError::InvalidExcludedPath`], or [`Error::TreeSha256InvalidHex`] when the
627    /// digest value is not exactly 64 ASCII hex digits (no trimming; surrounding or trailing
628    /// whitespace is rejected).
629    pub fn from_tag(tag: &TagData) -> Result<Option<Self>> {
630        let header = TREE_SHA256_HEADER.as_bytes();
631        let excluded_key = TREE_SHA256_EXCLUDED_HEADER.as_bytes();
632        let mut digest: Option<TreeSha256> = None;
633        let mut excluded = Vec::new();
634        for (key, value) in iter_extra_headers(&tag.extra_headers) {
635            if key == header {
636                if digest.is_some() {
637                    return Err(TreeSha256ClaimError::DuplicateDigestHeader.into());
638                }
639                digest = Some(tree_sha256_digest_from_tag_header_value(value)?);
640            } else if key == excluded_key {
641                let path = std::str::from_utf8(value)
642                    .map_err(|_| TreeSha256ClaimError::InvalidExcludedPath)?;
643                validate_excluded_path(path)?;
644                excluded.push(path.to_owned());
645            }
646        }
647        Ok(digest.map(|d| Self {
648            digest: d,
649            excluded,
650        }))
651    }
652
653    /// Build a claim from a freshly computed [`TreeSha256Report`].
654    #[must_use]
655    pub fn from_report(report: &TreeSha256Report) -> Self {
656        let mut excluded: Vec<String> = report.excluded.iter().map(|(p, _)| p.clone()).collect();
657        excluded.sort();
658        Self {
659            digest: report.digest,
660            excluded,
661        }
662    }
663
664    /// Replace any existing tree-sha256 headers on `tag` with this claim.
665    ///
666    /// Excluded paths are written in sorted order, then the digest line, immediately after
667    /// `tagger` and before any other extra headers, matching the reference `tree-sha256-tag`
668    /// layout (inside the signed payload, before the blank line).
669    ///
670    /// Each entry in [`Self::excluded`] must be non-empty and must not contain NUL or newline;
671    /// invalid paths are not checked here — callers must only supply paths that would round-trip
672    /// through [`Self::from_tag`].
673    pub fn apply_to_tag(&self, tag: &mut TagData) {
674        let header = TREE_SHA256_HEADER.as_bytes();
675        let excluded_key = TREE_SHA256_EXCLUDED_HEADER.as_bytes();
676        let unrelated = remove_header_lines(&tag.extra_headers, |key| {
677            key == header || key == excluded_key
678        });
679        let mut claim = Vec::new();
680        let mut paths = self.excluded.clone();
681        paths.sort();
682        for path in paths {
683            claim.extend_from_slice(TREE_SHA256_EXCLUDED_HEADER.as_bytes());
684            claim.push(b' ');
685            claim.extend_from_slice(path.as_bytes());
686            claim.push(b'\n');
687        }
688        claim.extend_from_slice(TREE_SHA256_HEADER.as_bytes());
689        claim.push(b' ');
690        claim.extend_from_slice(self.digest.to_hex().as_bytes());
691        claim.push(b'\n');
692        tag.extra_headers = claim;
693        tag.extra_headers.extend_from_slice(&unrelated);
694    }
695}
696
697/// Parse a `tree-sha256` tag header value: exactly 64 ASCII hex digits, no surrounding whitespace.
698fn tree_sha256_digest_from_tag_header_value(value: &[u8]) -> Result<TreeSha256> {
699    if value.len() != 64 || !value.iter().all(|b| b.is_ascii_hexdigit()) {
700        return Err(Error::TreeSha256InvalidHex);
701    }
702    let text = std::str::from_utf8(value).map_err(|_| Error::TreeSha256InvalidHex)?;
703    TreeSha256::from_str(text)
704}
705
706fn validate_excluded_path(path: &str) -> Result<()> {
707    if path.is_empty() || path.bytes().any(|b| b == 0 || b == b'\n') {
708        return Err(TreeSha256ClaimError::InvalidExcludedPath.into());
709    }
710    Ok(())
711}
712
713/// Returns true when `path` matches `pattern` (Git tree-sha256 glob rules).
714#[must_use]
715pub fn path_matches_glob(path: &str, pattern: &str) -> bool {
716    let pattern = pattern.trim_end_matches('/');
717    path_matches_glob_bytes(path.as_bytes(), pattern.as_bytes())
718}
719
720/// Like [`path_matches_glob`], but `path` and `pattern` are raw bytes (`pattern` trailing `/` trimmed).
721#[must_use]
722pub fn path_matches_glob_bytes(path: &[u8], pattern: &[u8]) -> bool {
723    glob_match(path, trim_trailing_slash_bytes(pattern))
724}
725
726fn trim_trailing_slash_bytes(mut pat: &[u8]) -> &[u8] {
727    while pat.last() == Some(&b'/') {
728        pat = &pat[..pat.len() - 1];
729    }
730    pat
731}
732
733fn glob_match(path: &[u8], pat: &[u8]) -> bool {
734    glob_match_at(path, pat, 0, 0)
735}
736
737fn glob_match_at(path: &[u8], pat: &[u8], mut pi: usize, mut si: usize) -> bool {
738    loop {
739        if pi == pat.len() {
740            return si == path.len();
741        }
742        match pat[pi] {
743            b'*' => {
744                pi += 1;
745                if pi == pat.len() {
746                    return true;
747                }
748                while si <= path.len() {
749                    if glob_match_at(path, pat, pi, si) {
750                        return true;
751                    }
752                    si += 1;
753                }
754                return false;
755            }
756            b'?' => {
757                if si >= path.len() {
758                    return false;
759                }
760                pi += 1;
761                si += 1;
762            }
763            c => {
764                if si >= path.len() || path[si] != c {
765                    return false;
766                }
767                pi += 1;
768                si += 1;
769            }
770        }
771    }
772}
773
774#[cfg(test)]
775mod glob_tests {
776    use super::{gitlink_in_commit_chain, path_matches_glob};
777    use crate::objects::ObjectId;
778
779    #[test]
780    fn gitlink_cycle_helper() {
781        let a: ObjectId = "0000000000000000000000000000000000000001".parse().unwrap();
782        let b: ObjectId = "0000000000000000000000000000000000000002".parse().unwrap();
783        assert!(gitlink_in_commit_chain(&[a, b, a], a));
784        assert!(!gitlink_in_commit_chain(&[b], a));
785    }
786
787    #[test]
788    fn star_matches_slash() {
789        assert!(path_matches_glob("a/b/c", "a/*"));
790        assert!(path_matches_glob("nested/sub/file", "nested/*"));
791    }
792
793    #[test]
794    fn question_mark_one_byte() {
795        assert!(path_matches_glob("abc", "a?c"));
796        assert!(!path_matches_glob("ac", "a?c"));
797    }
798
799    #[test]
800    fn trailing_slash_on_pattern_trimmed() {
801        assert!(path_matches_glob("vendor", "vendor/"));
802    }
803}
804
805#[cfg(test)]
806mod claim_tests {
807    use super::{
808        TreeSha256, TreeSha256Claim, TreeSha256ClaimError, TREE_SHA256_EXCLUDED_HEADER,
809        TREE_SHA256_HEADER,
810    };
811    use crate::error::Error;
812    use crate::objects::{parse_tag, serialize_tag, TagData};
813    use std::str::FromStr;
814
815    fn sample_tag(extra: &[u8]) -> TagData {
816        TagData {
817            object: "15c242b3b6ace73d1884e431f0d814d7a0e827a1".parse().unwrap(),
818            object_type: "commit".into(),
819            tag: "t".into(),
820            tagger: Some("T <t@example.com> 1 +0000".into()),
821            extra_headers: extra.to_vec(),
822            message: "msg\n".into(),
823            raw_message: None,
824        }
825    }
826
827    #[test]
828    fn claim_roundtrip_tag() {
829        let digest = TreeSha256::from_str(
830            "c29d81cdc535c4804153b7026e6b276b2dbab25d636341f6cab4179e2b1fd47a",
831        )
832        .unwrap();
833        let claim = TreeSha256Claim {
834            digest,
835            excluded: vec!["z/mod".into(), "a/mod".into()],
836        };
837        let mut tag = sample_tag(b"other x\n".as_slice());
838        claim.apply_to_tag(&mut tag);
839        assert!(
840            String::from_utf8_lossy(&tag.extra_headers).starts_with("tree-sha256-excluded a/mod"),
841            "claim must follow tagger, not unrelated headers: {:?}",
842            String::from_utf8_lossy(&tag.extra_headers)
843        );
844        assert!(
845            String::from_utf8_lossy(&tag.extra_headers).contains("other x\n"),
846            "unrelated headers must remain after the claim block"
847        );
848        let parsed = TreeSha256Claim::from_tag(&tag).unwrap().unwrap();
849        assert_eq!(parsed.digest, digest);
850        let mut want = claim.excluded.clone();
851        want.sort();
852        assert_eq!(parsed.excluded, want);
853        let bytes = serialize_tag(&tag);
854        let round = parse_tag(&bytes).unwrap();
855        assert_eq!(TreeSha256Claim::from_tag(&round).unwrap(), Some(parsed));
856    }
857
858    #[test]
859    fn claim_layout_matches_reference_tool_bytes() {
860        let fixture = include_bytes!("../tests/fixtures/tree_sha256/reference_tool_tag.txt");
861        let parsed = parse_tag(fixture).expect("parse fixture");
862        let claim = TreeSha256Claim::from_tag(&parsed)
863            .expect("from_tag")
864            .expect("claim");
865        let mut rebuilt = TagData {
866            extra_headers: Vec::new(),
867            ..parsed.clone()
868        };
869        claim.apply_to_tag(&mut rebuilt);
870        assert_eq!(serialize_tag(&rebuilt), fixture);
871    }
872
873    #[test]
874    fn apply_replaces_existing_claim() {
875        let digest = TreeSha256::from_str(
876            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
877        )
878        .unwrap();
879        let old = TreeSha256Claim {
880            digest,
881            excluded: vec!["old/path".into()],
882        };
883        let new = TreeSha256Claim {
884            digest: TreeSha256::from_str(
885                "c29d81cdc535c4804153b7026e6b276b2dbab25d636341f6cab4179e2b1fd47a",
886            )
887            .unwrap(),
888            excluded: vec![],
889        };
890        let mut tag = sample_tag(b"");
891        old.apply_to_tag(&mut tag);
892        new.apply_to_tag(&mut tag);
893        let claim = TreeSha256Claim::from_tag(&tag).unwrap().unwrap();
894        assert_eq!(claim, new);
895        assert!(
896            !String::from_utf8_lossy(&tag.extra_headers).contains("old/path"),
897            "previous excluded path must be gone"
898        );
899    }
900
901    #[test]
902    fn duplicate_header_rejected() {
903        let extra =
904            b"tree-sha256 e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855\n\
905tree-sha256 c29d81cdc535c4804153b7026e6b276b2dbab25d636341f6cab4179e2b1fd47a\n";
906        let tag = sample_tag(extra);
907        assert!(matches!(
908            TreeSha256Claim::from_tag(&tag),
909            Err(Error::TreeSha256Claim(
910                TreeSha256ClaimError::DuplicateDigestHeader
911            ))
912        ));
913    }
914
915    #[test]
916    fn bad_hex_rejected() {
917        let extra = b"tree-sha256 not_valid_hex\n";
918        let tag = sample_tag(extra);
919        assert!(matches!(
920            TreeSha256Claim::from_tag(&tag),
921            Err(Error::TreeSha256InvalidHex)
922        ));
923    }
924
925    #[test]
926    fn digest_header_whitespace_rejected() {
927        let hex = "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855";
928        for extra in [
929            format!("tree-sha256 {hex} \n"),
930            format!("tree-sha256  {hex}\n"),
931            format!("tree-sha256 {hex}x\n"),
932        ] {
933            let tag = sample_tag(extra.as_bytes());
934            assert!(
935                matches!(
936                    TreeSha256Claim::from_tag(&tag),
937                    Err(Error::TreeSha256InvalidHex)
938                ),
939                "must reject {extra:?}"
940            );
941        }
942    }
943
944    #[test]
945    fn apply_places_claim_immediately_after_tagger_byte_order() {
946        let digest = TreeSha256::from_str(
947            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
948        )
949        .unwrap();
950        let claim = TreeSha256Claim {
951            digest,
952            excluded: vec!["sub/mod".into()],
953        };
954        let mut tag = sample_tag(b"other existing\n");
955        claim.apply_to_tag(&mut tag);
956        let want_prefix = "tree-sha256-excluded sub/mod\n\
957tree-sha256 e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855\n\
958other existing\n";
959        assert_eq!(
960            String::from_utf8_lossy(&tag.extra_headers),
961            want_prefix,
962            "serialized extra headers must not place unrelated lines before the claim"
963        );
964        let bytes = serialize_tag(&tag);
965        let tagger_end = b"tagger T <t@example.com> 1 +0000\n";
966        let pos = bytes
967            .windows(tagger_end.len())
968            .position(|w| w == tagger_end)
969            .expect("tagger line");
970        let after_tagger = &bytes[pos + tagger_end.len()..];
971        assert!(
972            after_tagger.starts_with(want_prefix.as_bytes()),
973            "full tag bytes must place claim immediately after tagger"
974        );
975    }
976
977    #[test]
978    fn no_claim_returns_none() {
979        let tag = sample_tag(b"change-id abc\n");
980        assert_eq!(TreeSha256Claim::from_tag(&tag).unwrap(), None);
981    }
982
983    #[test]
984    fn invalid_excluded_path_rejected() {
985        let digest_line =
986            b"tree-sha256 e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855\n";
987        let cases: Vec<Vec<u8>> = vec![
988            b"tree-sha256-excluded \n".to_vec(),
989            b"tree-sha256-excluded bad\n more\n".to_vec(),
990            b"tree-sha256-excluded nul\0here\n".to_vec(),
991        ];
992        for extra in &cases {
993            let mut blob = extra.clone();
994            blob.extend_from_slice(digest_line);
995            let tag = sample_tag(&blob);
996            assert!(matches!(
997                TreeSha256Claim::from_tag(&tag),
998                Err(Error::TreeSha256Claim(
999                    TreeSha256ClaimError::InvalidExcludedPath
1000                ))
1001            ));
1002        }
1003    }
1004
1005    #[test]
1006    fn header_constants_match_reference_tool() {
1007        assert_eq!(TREE_SHA256_HEADER, "tree-sha256");
1008        assert_eq!(TREE_SHA256_EXCLUDED_HEADER, "tree-sha256-excluded");
1009    }
1010}
grit_lib/tree_sha256.rs

grit_lib/
tree_sha256.rs
