heddle_object_model/object/thread_replication/
git_import_graph.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Git identities and ref classification shared by local and hosted import.
3
4use serde::{Deserialize, Serialize};
5
6use super::invalid;
7use crate::{
8    error::Result,
9    object::{MarkerName, ThreadName},
10};
11
12/// Native refs (branches plus commit tags) one Git import may carry.
13///
14/// This is `heddle_api::import_authority::MAX_IMPORT_SOURCE_REFS` (4096,
15/// HeddleCo/api#389), the bound on a host's complete discovery and weft's
16/// retained-ref cap, so the converter and the import authority cannot drift.
17pub const MAX_IMPORT_REFS: usize = api::import_authority::MAX_IMPORT_SOURCE_REFS;
18
19/// Git object identity retains the hash algorithm; SHA-256 never truncates
20/// into a SHA-1 address. This names commits and raw annotated tag objects.
21#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
22#[serde(rename_all = "snake_case")]
23pub enum GitObjectId {
24    Sha1([u8; 20]),
25    Sha256([u8; 32]),
26}
27
28/// The raw Git ref target, including symbolic refs and object kinds that
29/// cannot become native refs. A dangling direct target has `Unknown` kind.
30#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
31#[serde(rename_all = "snake_case")]
32pub enum GitRefObjectType {
33    Commit,
34    Tag,
35    Tree,
36    Blob,
37    Unknown,
38}
39
40#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
41#[serde(rename_all = "snake_case")]
42pub enum GitRefTarget {
43    Direct {
44        oid: GitObjectId,
45        object_type: GitRefObjectType,
46    },
47    Symbolic(Vec<u8>),
48}
49
50/// A Git ref with its direct target. `peeled_commit` is present only when
51/// this ref resolves to a commit.
52#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
53#[serde(deny_unknown_fields)]
54pub struct ImportRefIdentity {
55    pub raw_name: Vec<u8>,
56    pub raw_target: GitRefTarget,
57    pub peeled_commit: Option<GitObjectId>,
58}
59
60impl ImportRefIdentity {
61    pub fn direct_oid(&self) -> Option<&GitObjectId> {
62        match &self.raw_target {
63            GitRefTarget::Direct { oid, .. } => Some(oid),
64            GitRefTarget::Symbolic(_) => None,
65        }
66    }
67}
68
69#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
70#[serde(rename_all = "snake_case")]
71pub enum GitObjectFormat {
72    Sha1,
73    Sha256,
74}
75
76impl GitObjectFormat {
77    pub(crate) fn sley(self) -> sley_core::ObjectFormat {
78        match self {
79            Self::Sha1 => sley_core::ObjectFormat::Sha1,
80            Self::Sha256 => sley_core::ObjectFormat::Sha256,
81        }
82    }
83}
84
85#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
86#[serde(rename_all = "snake_case")]
87pub enum ImportRefDisposition {
88    Branch,
89    CommitTag,
90    DefaultHead,
91    RequiredNotes,
92    Unsupported { reason: ImportSkipReason },
93}
94
95/// Reasons for refs omitted from native Threads and markers.
96#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
97#[serde(rename_all = "snake_case")]
98pub enum ImportSkipReason {
99    NonUtf8RefName,
100    InvalidNativeName,
101    RemoteTracking,
102    Replace,
103    Pull,
104    OtherNotes,
105    NonCommitTag,
106    SymbolicRef,
107    OtherRef,
108    DanglingUnsupported,
109}
110
111impl ImportSkipReason {
112    pub fn description(self) -> &'static str {
113        match self {
114            Self::NonUtf8RefName => "ref name is not valid UTF-8",
115            Self::InvalidNativeName => "invalid Git ref name",
116            Self::RemoteTracking => "remote-tracking ref",
117            Self::Replace => "replace ref",
118            Self::Pull => "pull ref",
119            Self::OtherNotes => "other notes ref",
120            Self::NonCommitTag => "tag does not point to a commit",
121            Self::SymbolicRef => "symbolic ref",
122            Self::OtherRef => "unsupported ref namespace",
123            Self::DanglingUnsupported => "dangling unsupported ref",
124        }
125    }
126}
127
128#[derive(Clone, Copy, Debug, PartialEq, Eq)]
129pub enum ImportRefFailure {
130    MissingRequiredTarget,
131    InvalidDefaultHead,
132    UnknownRequiredTarget,
133}
134
135/// Classify one raw Git ref before producing native Threads or markers.
136pub fn classify_git_import_ref(
137    reference: &ImportRefIdentity,
138) -> std::result::Result<ImportRefDisposition, ImportRefFailure> {
139    let name = reference.raw_name.as_slice();
140    let Ok(utf8_name) = std::str::from_utf8(name) else {
141        return Ok(ImportRefDisposition::Unsupported {
142            reason: ImportSkipReason::NonUtf8RefName,
143        });
144    };
145    if name == b"HEAD" {
146        return match &reference.raw_target {
147            GitRefTarget::Symbolic(target)
148                if target.starts_with(b"refs/heads/") && target.len() > b"refs/heads/".len() =>
149            {
150                Ok(ImportRefDisposition::DefaultHead)
151            }
152            _ => Err(ImportRefFailure::InvalidDefaultHead),
153        };
154    }
155    if name.starts_with(b"refs/pull/") {
156        return Ok(ImportRefDisposition::Unsupported {
157            reason: ImportSkipReason::Pull,
158        });
159    }
160    if matches!(&reference.raw_target, GitRefTarget::Symbolic(_)) {
161        return Ok(ImportRefDisposition::Unsupported {
162            reason: ImportSkipReason::SymbolicRef,
163        });
164    }
165    if name == b"refs/notes/heddle" {
166        return match &reference.raw_target {
167            GitRefTarget::Direct {
168                object_type: GitRefObjectType::Commit,
169                ..
170            } => Ok(ImportRefDisposition::RequiredNotes),
171            _ => Err(ImportRefFailure::MissingRequiredTarget),
172        };
173    }
174    let kind = match &reference.raw_target {
175        GitRefTarget::Direct { object_type, .. } => object_type,
176        GitRefTarget::Symbolic(_) => return Err(ImportRefFailure::UnknownRequiredTarget),
177    };
178    if name.starts_with(b"refs/heads/") && name.len() > b"refs/heads/".len() {
179        if ThreadName::from_git_branch(&utf8_name["refs/heads/".len()..]).is_err() {
180            return Ok(ImportRefDisposition::Unsupported {
181                reason: ImportSkipReason::InvalidNativeName,
182            });
183        }
184        return match (
185            kind,
186            reference.peeled_commit.as_ref(),
187            reference.direct_oid(),
188        ) {
189            (GitRefObjectType::Commit, Some(peeled), Some(raw)) if peeled == raw => {
190                Ok(ImportRefDisposition::Branch)
191            }
192            (GitRefObjectType::Unknown, _, _) => Err(ImportRefFailure::MissingRequiredTarget),
193            _ => Err(ImportRefFailure::UnknownRequiredTarget),
194        };
195    }
196    if name.starts_with(b"refs/tags/") && name.len() > b"refs/tags/".len() {
197        if MarkerName::from_git_tag(&utf8_name["refs/tags/".len()..]).is_err() {
198            return Ok(ImportRefDisposition::Unsupported {
199                reason: ImportSkipReason::InvalidNativeName,
200            });
201        }
202        return match kind {
203            GitRefObjectType::Commit | GitRefObjectType::Tag
204                if reference.peeled_commit.is_some() =>
205            {
206                Ok(ImportRefDisposition::CommitTag)
207            }
208            GitRefObjectType::Tag | GitRefObjectType::Tree | GitRefObjectType::Blob => {
209                Ok(ImportRefDisposition::Unsupported {
210                    reason: ImportSkipReason::NonCommitTag,
211                })
212            }
213            GitRefObjectType::Unknown => Err(ImportRefFailure::MissingRequiredTarget),
214            _ => Err(ImportRefFailure::UnknownRequiredTarget),
215        };
216    }
217    let reason = if *kind == GitRefObjectType::Unknown {
218        ImportSkipReason::DanglingUnsupported
219    } else if name.starts_with(b"refs/remotes/") {
220        ImportSkipReason::RemoteTracking
221    } else if name.starts_with(b"refs/replace/") {
222        ImportSkipReason::Replace
223    } else if name.starts_with(b"refs/notes/") {
224        ImportSkipReason::OtherNotes
225    } else {
226        ImportSkipReason::OtherRef
227    };
228    Ok(ImportRefDisposition::Unsupported { reason })
229}
230
231#[derive(Clone, Debug, PartialEq, Eq)]
232pub struct SkippedImportRef {
233    pub raw_name: Vec<u8>,
234    pub reason: ImportSkipReason,
235}
236
237impl SkippedImportRef {
238    /// Keep valid Unicode readable; escape invalid bytes rather than displaying
239    /// a replacement character that could name a different, valid Git ref.
240    pub fn display_name(&self) -> String {
241        std::str::from_utf8(&self.raw_name)
242            .map_or_else(|_| self.raw_name.escape_ascii().to_string(), str::to_owned)
243    }
244}
245
246/// Result of classifying a complete, raw-name-sorted frozen ref set.
247/// Dispositions have the same order as the input; no advertised ref is dropped.
248#[derive(Clone, Debug, PartialEq, Eq)]
249pub struct ClassifiedImportRefs {
250    pub default_branch: Vec<u8>,
251    pub dispositions: Vec<ImportRefDisposition>,
252    pub skipped_refs: Vec<SkippedImportRef>,
253    pub native_ref_count: u32,
254    pub partial: bool,
255}
256
257pub fn classify_frozen_import_refs(refs: &[ImportRefIdentity]) -> Result<ClassifiedImportRefs> {
258    let mut native_ref_count = 0usize;
259    let mut dispositions = Vec::with_capacity(refs.len());
260    let mut skipped_refs = Vec::new();
261    let mut default_branch = None;
262    let mut last_name: Option<&[u8]> = None;
263    let mut partial = false;
264    for reference in refs {
265        if reference.raw_name.is_empty()
266            || last_name.is_some_and(|last| last >= reference.raw_name.as_slice())
267        {
268            return Err(invalid(
269                "Git import refs are not strictly sorted by raw name",
270            ));
271        }
272        last_name = Some(&reference.raw_name);
273        let disposition = classify_git_import_ref(reference)
274            .map_err(|error| invalid(format!("Git import ref cannot be represented: {error:?}")))?;
275        if disposition == ImportRefDisposition::DefaultHead {
276            let GitRefTarget::Symbolic(target) = &reference.raw_target else {
277                return Err(invalid("default HEAD is not symbolic"));
278            };
279            default_branch = Some(target.clone());
280        }
281        if matches!(
282            disposition,
283            ImportRefDisposition::Branch | ImportRefDisposition::CommitTag
284        ) {
285            native_ref_count += 1;
286            if native_ref_count > MAX_IMPORT_REFS {
287                return Err(invalid(format!(
288                    "Git import has more than {MAX_IMPORT_REFS} native refs"
289                )));
290            }
291        }
292        // Provider pull refs are outside the imported branch/tag surface.
293        if let ImportRefDisposition::Unsupported { reason } = disposition
294            && reason != ImportSkipReason::Pull
295        {
296            skipped_refs.push(SkippedImportRef {
297                raw_name: reference.raw_name.clone(),
298                reason,
299            });
300            partial = true;
301        }
302        dispositions.push(disposition);
303    }
304    let default_branch =
305        default_branch.ok_or_else(|| invalid("Git import has no symbolic HEAD"))?;
306    let default_index = refs
307        .binary_search_by(|reference| reference.raw_name.cmp(&default_branch))
308        .map_err(|_| invalid("Git import HEAD points to an absent branch"))?;
309    if dispositions.get(default_index) != Some(&ImportRefDisposition::Branch) {
310        return Err(invalid(
311            "Git import HEAD does not point to a supported branch",
312        ));
313    }
314    Ok(ClassifiedImportRefs {
315        default_branch,
316        dispositions,
317        skipped_refs,
318        native_ref_count: native_ref_count as u32,
319        partial,
320    })
321}
322
323#[cfg(test)]
324mod tests {
325    use super::*;
326    #[test]
327    fn unrepresentable_ref_kinds_have_explicit_partial_outcomes() {
328        let target = GitObjectId::Sha1([1; 20]);
329        for (name, object_type, reason) in [
330            (
331                b"refs/remotes/origin/main".as_slice(),
332                GitRefObjectType::Commit,
333                ImportSkipReason::RemoteTracking,
334            ),
335            (
336                b"refs/replace/abc".as_slice(),
337                GitRefObjectType::Commit,
338                ImportSkipReason::Replace,
339            ),
340            (
341                b"refs/pull/12/head".as_slice(),
342                GitRefObjectType::Commit,
343                ImportSkipReason::Pull,
344            ),
345            (
346                b"refs/notes/other".as_slice(),
347                GitRefObjectType::Commit,
348                ImportSkipReason::OtherNotes,
349            ),
350            (
351                b"refs/tags/blob".as_slice(),
352                GitRefObjectType::Blob,
353                ImportSkipReason::NonCommitTag,
354            ),
355            (
356                b"refs/tags/tree".as_slice(),
357                GitRefObjectType::Tree,
358                ImportSkipReason::NonCommitTag,
359            ),
360            (
361                b"refs/custom/x".as_slice(),
362                GitRefObjectType::Commit,
363                ImportSkipReason::OtherRef,
364            ),
365            (
366                b"refs/custom/dangling".as_slice(),
367                GitRefObjectType::Unknown,
368                ImportSkipReason::DanglingUnsupported,
369            ),
370        ] {
371            let reference = ImportRefIdentity {
372                raw_name: name.to_vec(),
373                raw_target: GitRefTarget::Direct {
374                    oid: target.clone(),
375                    object_type,
376                },
377                peeled_commit: None,
378            };
379            assert_eq!(
380                classify_git_import_ref(&reference),
381                Ok(ImportRefDisposition::Unsupported { reason }),
382                "{}",
383                String::from_utf8_lossy(name),
384            );
385        }
386        let symbolic = ImportRefIdentity {
387            raw_name: b"refs/remotes/origin/HEAD".to_vec(),
388            raw_target: GitRefTarget::Symbolic(b"refs/remotes/origin/main".to_vec()),
389            peeled_commit: None,
390        };
391        assert_eq!(
392            classify_git_import_ref(&symbolic),
393            Ok(ImportRefDisposition::Unsupported {
394                reason: ImportSkipReason::SymbolicRef,
395            })
396        );
397        for name in [b"refs/heads/main".as_slice(), b"refs/tags/v1".as_slice()] {
398            let dangling = ImportRefIdentity {
399                raw_name: name.to_vec(),
400                raw_target: GitRefTarget::Direct {
401                    oid: target.clone(),
402                    object_type: GitRefObjectType::Unknown,
403                },
404                peeled_commit: None,
405            };
406            assert_eq!(
407                classify_git_import_ref(&dangling),
408                Err(ImportRefFailure::MissingRequiredTarget)
409            );
410        }
411        let detached_head = ImportRefIdentity {
412            raw_name: b"HEAD".to_vec(),
413            raw_target: GitRefTarget::Direct {
414                oid: target,
415                object_type: GitRefObjectType::Commit,
416            },
417            peeled_commit: None,
418        };
419        assert_eq!(
420            classify_git_import_ref(&detached_head),
421            Err(ImportRefFailure::InvalidDefaultHead)
422        );
423    }
424
425    #[test]
426    fn github_provider_refs_do_not_make_import_partial() {
427        let commit = GitObjectId::Sha1([4; 20]);
428        let mut refs = vec![ImportRefIdentity {
429            raw_name: b"HEAD".to_vec(),
430            raw_target: GitRefTarget::Symbolic(b"refs/heads/main".to_vec()),
431            peeled_commit: None,
432        }];
433        for name in [
434            b"refs/heads/main".as_slice(),
435            b"refs/pull/12/head".as_slice(),
436            b"refs/pull/12/merge".as_slice(),
437            b"refs/tags/v1".as_slice(),
438        ] {
439            refs.push(ImportRefIdentity {
440                raw_name: name.to_vec(),
441                raw_target: GitRefTarget::Direct {
442                    oid: commit.clone(),
443                    object_type: GitRefObjectType::Commit,
444                },
445                peeled_commit: Some(commit.clone()),
446            });
447        }
448        let classified = classify_frozen_import_refs(&refs).expect("GitHub-shaped refs");
449        assert!(!classified.partial);
450        assert!(classified.skipped_refs.is_empty());
451        assert_eq!(classified.native_ref_count, 2);
452        assert_eq!(classified.default_branch, b"refs/heads/main");
453    }
454
455    #[test]
456    fn complete_ref_classification_keeps_unsupported_refs_and_requires_head() {
457        let commit = GitObjectId::Sha1([4; 20]);
458        let head = ImportRefIdentity {
459            raw_name: b"HEAD".to_vec(),
460            raw_target: GitRefTarget::Symbolic(b"refs/heads/main".to_vec()),
461            peeled_commit: Some(commit.clone()),
462        };
463        let branch = ImportRefIdentity {
464            raw_name: b"refs/heads/main".to_vec(),
465            raw_target: GitRefTarget::Direct {
466                oid: commit.clone(),
467                object_type: GitRefObjectType::Commit,
468            },
469            peeled_commit: Some(commit.clone()),
470        };
471        let remote = ImportRefIdentity {
472            raw_name: b"refs/remotes/origin/main".to_vec(),
473            raw_target: GitRefTarget::Direct {
474                oid: commit,
475                object_type: GitRefObjectType::Commit,
476            },
477            peeled_commit: None,
478        };
479        let refs = vec![head, branch, remote];
480        let result = classify_frozen_import_refs(&refs).expect("complete snapshot");
481        assert_eq!(result.default_branch, b"refs/heads/main");
482        assert_eq!(result.native_ref_count, 1);
483        assert!(result.partial);
484        assert_eq!(
485            result.skipped_refs,
486            vec![SkippedImportRef {
487                raw_name: b"refs/remotes/origin/main".to_vec(),
488                reason: ImportSkipReason::RemoteTracking,
489            }]
490        );
491        assert_eq!(result.dispositions.len(), refs.len());
492        assert!(classify_frozen_import_refs(&refs[1..]).is_err());
493        let mut moved = refs;
494        moved[0].raw_target = GitRefTarget::Symbolic(b"refs/heads/absent".to_vec());
495        assert!(classify_frozen_import_refs(&moved).is_err());
496    }
497
498    /// HEAD plus `native` refs alternating branch / lightweight commit tag.
499    fn frozen_refs_with_native(native: usize) -> Vec<ImportRefIdentity> {
500        let commit = GitObjectId::Sha1([5; 20]);
501        let direct = |raw_name: String| ImportRefIdentity {
502            raw_name: raw_name.into_bytes(),
503            raw_target: GitRefTarget::Direct {
504                oid: commit.clone(),
505                object_type: GitRefObjectType::Commit,
506            },
507            peeled_commit: Some(commit.clone()),
508        };
509        let mut refs = vec![ImportRefIdentity {
510            raw_name: b"HEAD".to_vec(),
511            raw_target: GitRefTarget::Symbolic(b"refs/heads/b-00000".to_vec()),
512            peeled_commit: None,
513        }];
514        refs.extend(
515            (0..native)
516                .step_by(2)
517                .map(|i| direct(format!("refs/heads/b-{i:05}"))),
518        );
519        refs.extend(
520            (1..native)
521                .step_by(2)
522                .map(|i| direct(format!("refs/tags/t-{i:05}"))),
523        );
524        refs
525    }
526
527    #[test]
528    fn native_ref_bound_admits_4096_and_refuses_4097() {
529        // The converter and the import authority share one bound (heddle#2022).
530        assert_eq!(
531            MAX_IMPORT_REFS,
532            api::import_authority::MAX_IMPORT_SOURCE_REFS
533        );
534        assert_eq!(MAX_IMPORT_REFS, 4096);
535        for native in [600, MAX_IMPORT_REFS] {
536            let classified = classify_frozen_import_refs(&frozen_refs_with_native(native))
537                .unwrap_or_else(|error| panic!("{native} native refs: {error}"));
538            assert_eq!(classified.native_ref_count as usize, native);
539            assert!(!classified.partial);
540        }
541        let error = classify_frozen_import_refs(&frozen_refs_with_native(MAX_IMPORT_REFS + 1))
542            .expect_err("one native ref past the bound");
543        assert!(
544            error
545                .to_string()
546                .contains("Git import has more than 4096 native refs"),
547            "{error}"
548        );
549    }
550
551    #[test]
552    fn reserved_branch_is_admitted_for_escaped_native_emission() {
553        let oid = GitObjectId::Sha1([8; 20]);
554        let reference = ImportRefIdentity {
555            raw_name: b"refs/heads/heddle/reserved".to_vec(),
556            raw_target: GitRefTarget::Direct {
557                oid: oid.clone(),
558                object_type: GitRefObjectType::Commit,
559            },
560            peeled_commit: Some(oid),
561        };
562        assert!(matches!(
563            classify_git_import_ref(&reference),
564            Ok(ImportRefDisposition::Branch)
565        ));
566    }
567}
heddle_object_model/object/thread_replication/git_import_graph.rs

heddle_object_model/object/thread_replication/
git_import_graph.rs
