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

heddle_object_model/object/thread_replication/
git_import_graph.rs
