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 => "non-UTF-8 ref name",
110            Self::InvalidNativeName => "reserved native 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    if std::str::from_utf8(name).is_err()
136        || name.windows(3).any(|bytes| bytes == "\u{fffd}".as_bytes())
137    {
138        return Ok(ImportRefDisposition::Unsupported {
139            reason: ImportSkipReason::NonUtf8RefName,
140        });
141    }
142    if name == b"HEAD" {
143        return match &reference.raw_target {
144            GitRefTarget::Symbolic(target)
145                if target.starts_with(b"refs/heads/") && target.len() > b"refs/heads/".len() =>
146            {
147                Ok(ImportRefDisposition::DefaultHead)
148            }
149            _ => Err(ImportRefFailure::InvalidDefaultHead),
150        };
151    }
152    if name.starts_with(b"refs/pull/") {
153        return Ok(ImportRefDisposition::Unsupported {
154            reason: ImportSkipReason::Pull,
155        });
156    }
157    if matches!(&reference.raw_target, GitRefTarget::Symbolic(_)) {
158        return Ok(ImportRefDisposition::Unsupported {
159            reason: ImportSkipReason::SymbolicRef,
160        });
161    }
162    if name == b"refs/notes/heddle" {
163        return match &reference.raw_target {
164            GitRefTarget::Direct {
165                object_type: GitRefObjectType::Commit,
166                ..
167            } => Ok(ImportRefDisposition::RequiredNotes),
168            _ => Err(ImportRefFailure::MissingRequiredTarget),
169        };
170    }
171    let kind = match &reference.raw_target {
172        GitRefTarget::Direct { object_type, .. } => object_type,
173        GitRefTarget::Symbolic(_) => return Err(ImportRefFailure::UnknownRequiredTarget),
174    };
175    if name.starts_with(b"refs/heads/") && name.len() > b"refs/heads/".len() {
176        if ThreadName::try_new(String::from_utf8_lossy(&name[b"refs/heads/".len()..]).into_owned())
177            .is_err()
178        {
179            return Ok(ImportRefDisposition::Unsupported {
180                reason: ImportSkipReason::InvalidNativeName,
181            });
182        }
183        return match (
184            kind,
185            reference.peeled_commit.as_ref(),
186            reference.direct_oid(),
187        ) {
188            (GitRefObjectType::Commit, Some(peeled), Some(raw)) if peeled == raw => {
189                Ok(ImportRefDisposition::Branch)
190            }
191            (GitRefObjectType::Unknown, _, _) => Err(ImportRefFailure::MissingRequiredTarget),
192            _ => Err(ImportRefFailure::UnknownRequiredTarget),
193        };
194    }
195    if name.starts_with(b"refs/tags/") && name.len() > b"refs/tags/".len() {
196        if MarkerName::try_new(String::from_utf8_lossy(&name[b"refs/tags/".len()..]).into_owned())
197            .is_err()
198        {
199            return Ok(ImportRefDisposition::Unsupported {
200                reason: ImportSkipReason::InvalidNativeName,
201            });
202        }
203        return match kind {
204            GitRefObjectType::Commit | GitRefObjectType::Tag
205                if reference.peeled_commit.is_some() =>
206            {
207                Ok(ImportRefDisposition::CommitTag)
208            }
209            GitRefObjectType::Tag | GitRefObjectType::Tree | GitRefObjectType::Blob => {
210                Ok(ImportRefDisposition::Unsupported {
211                    reason: ImportSkipReason::NonCommitTag,
212                })
213            }
214            GitRefObjectType::Unknown => Err(ImportRefFailure::MissingRequiredTarget),
215            _ => Err(ImportRefFailure::UnknownRequiredTarget),
216        };
217    }
218    let reason = if *kind == GitRefObjectType::Unknown {
219        ImportSkipReason::DanglingUnsupported
220    } else if name.starts_with(b"refs/remotes/") {
221        ImportSkipReason::RemoteTracking
222    } else if name.starts_with(b"refs/replace/") {
223        ImportSkipReason::Replace
224    } else if name.starts_with(b"refs/notes/") {
225        ImportSkipReason::OtherNotes
226    } else {
227        ImportSkipReason::OtherRef
228    };
229    Ok(ImportRefDisposition::Unsupported { reason })
230}
231
232#[derive(Clone, Debug, PartialEq, Eq)]
233pub struct SkippedImportRef {
234    pub raw_name: Vec<u8>,
235    pub reason: ImportSkipReason,
236}
237
238/// Result of classifying a complete, raw-name-sorted frozen ref set.
239/// Dispositions have the same order as the input; no advertised ref is dropped.
240#[derive(Clone, Debug, PartialEq, Eq)]
241pub struct ClassifiedImportRefs {
242    pub default_branch: Vec<u8>,
243    pub dispositions: Vec<ImportRefDisposition>,
244    pub skipped_refs: Vec<SkippedImportRef>,
245    pub native_ref_count: u32,
246    pub partial: bool,
247}
248
249pub fn classify_frozen_import_refs(refs: &[ImportRefIdentity]) -> Result<ClassifiedImportRefs> {
250    let mut native_ref_count = 0usize;
251    let mut dispositions = Vec::with_capacity(refs.len());
252    let mut skipped_refs = Vec::new();
253    let mut default_branch = None;
254    let mut last_name: Option<&[u8]> = None;
255    let mut partial = false;
256    for reference in refs {
257        if reference.raw_name.is_empty()
258            || last_name.is_some_and(|last| last >= reference.raw_name.as_slice())
259        {
260            return Err(invalid(
261                "Git import refs are not strictly sorted by raw name",
262            ));
263        }
264        last_name = Some(&reference.raw_name);
265        let disposition = classify_git_import_ref(reference)
266            .map_err(|error| invalid(format!("Git import ref cannot be represented: {error:?}")))?;
267        if disposition == ImportRefDisposition::DefaultHead {
268            let GitRefTarget::Symbolic(target) = &reference.raw_target else {
269                return Err(invalid("default HEAD is not symbolic"));
270            };
271            default_branch = Some(target.clone());
272        }
273        if matches!(
274            disposition,
275            ImportRefDisposition::Branch | ImportRefDisposition::CommitTag
276        ) {
277            native_ref_count += 1;
278            if native_ref_count > MAX_IMPORT_REFS {
279                return Err(invalid("Git import has more than 512 native refs"));
280            }
281        }
282        // Provider pull refs are outside the imported branch/tag surface.
283        if let ImportRefDisposition::Unsupported { reason } = disposition
284            && reason != ImportSkipReason::Pull
285        {
286            skipped_refs.push(SkippedImportRef {
287                raw_name: reference.raw_name.clone(),
288                reason,
289            });
290            partial = true;
291        }
292        dispositions.push(disposition);
293    }
294    let default_branch =
295        default_branch.ok_or_else(|| invalid("Git import has no symbolic HEAD"))?;
296    let default_index = refs
297        .binary_search_by(|reference| reference.raw_name.cmp(&default_branch))
298        .map_err(|_| invalid("Git import HEAD points to an absent branch"))?;
299    if dispositions.get(default_index) != Some(&ImportRefDisposition::Branch) {
300        return Err(invalid(
301            "Git import HEAD does not point to a supported branch",
302        ));
303    }
304    Ok(ClassifiedImportRefs {
305        default_branch,
306        dispositions,
307        skipped_refs,
308        native_ref_count: native_ref_count as u32,
309        partial,
310    })
311}
312
313#[cfg(test)]
314mod tests {
315    use super::*;
316    #[test]
317    fn unrepresentable_ref_kinds_have_explicit_partial_outcomes() {
318        let target = GitObjectId::Sha1([1; 20]);
319        for (name, object_type, reason) in [
320            (
321                b"refs/remotes/origin/main".as_slice(),
322                GitRefObjectType::Commit,
323                ImportSkipReason::RemoteTracking,
324            ),
325            (
326                b"refs/replace/abc".as_slice(),
327                GitRefObjectType::Commit,
328                ImportSkipReason::Replace,
329            ),
330            (
331                b"refs/pull/12/head".as_slice(),
332                GitRefObjectType::Commit,
333                ImportSkipReason::Pull,
334            ),
335            (
336                b"refs/notes/other".as_slice(),
337                GitRefObjectType::Commit,
338                ImportSkipReason::OtherNotes,
339            ),
340            (
341                b"refs/tags/blob".as_slice(),
342                GitRefObjectType::Blob,
343                ImportSkipReason::NonCommitTag,
344            ),
345            (
346                b"refs/tags/tree".as_slice(),
347                GitRefObjectType::Tree,
348                ImportSkipReason::NonCommitTag,
349            ),
350            (
351                b"refs/custom/x".as_slice(),
352                GitRefObjectType::Commit,
353                ImportSkipReason::OtherRef,
354            ),
355            (
356                b"refs/custom/dangling".as_slice(),
357                GitRefObjectType::Unknown,
358                ImportSkipReason::DanglingUnsupported,
359            ),
360        ] {
361            let reference = ImportRefIdentity {
362                raw_name: name.to_vec(),
363                raw_target: GitRefTarget::Direct {
364                    oid: target.clone(),
365                    object_type,
366                },
367                peeled_commit: None,
368            };
369            assert_eq!(
370                classify_git_import_ref(&reference),
371                Ok(ImportRefDisposition::Unsupported { reason }),
372                "{}",
373                String::from_utf8_lossy(name),
374            );
375        }
376        let symbolic = ImportRefIdentity {
377            raw_name: b"refs/remotes/origin/HEAD".to_vec(),
378            raw_target: GitRefTarget::Symbolic(b"refs/remotes/origin/main".to_vec()),
379            peeled_commit: None,
380        };
381        assert_eq!(
382            classify_git_import_ref(&symbolic),
383            Ok(ImportRefDisposition::Unsupported {
384                reason: ImportSkipReason::SymbolicRef,
385            })
386        );
387        for name in [b"refs/heads/main".as_slice(), b"refs/tags/v1".as_slice()] {
388            let dangling = ImportRefIdentity {
389                raw_name: name.to_vec(),
390                raw_target: GitRefTarget::Direct {
391                    oid: target.clone(),
392                    object_type: GitRefObjectType::Unknown,
393                },
394                peeled_commit: None,
395            };
396            assert_eq!(
397                classify_git_import_ref(&dangling),
398                Err(ImportRefFailure::MissingRequiredTarget)
399            );
400        }
401        let detached_head = ImportRefIdentity {
402            raw_name: b"HEAD".to_vec(),
403            raw_target: GitRefTarget::Direct {
404                oid: target,
405                object_type: GitRefObjectType::Commit,
406            },
407            peeled_commit: None,
408        };
409        assert_eq!(
410            classify_git_import_ref(&detached_head),
411            Err(ImportRefFailure::InvalidDefaultHead)
412        );
413    }
414
415    #[test]
416    fn github_provider_refs_do_not_make_import_partial() {
417        let commit = GitObjectId::Sha1([4; 20]);
418        let mut refs = vec![ImportRefIdentity {
419            raw_name: b"HEAD".to_vec(),
420            raw_target: GitRefTarget::Symbolic(b"refs/heads/main".to_vec()),
421            peeled_commit: None,
422        }];
423        for name in [
424            b"refs/heads/main".as_slice(),
425            b"refs/pull/12/head".as_slice(),
426            b"refs/pull/12/merge".as_slice(),
427            b"refs/tags/v1".as_slice(),
428        ] {
429            refs.push(ImportRefIdentity {
430                raw_name: name.to_vec(),
431                raw_target: GitRefTarget::Direct {
432                    oid: commit.clone(),
433                    object_type: GitRefObjectType::Commit,
434                },
435                peeled_commit: Some(commit.clone()),
436            });
437        }
438        let classified = classify_frozen_import_refs(&refs).expect("GitHub-shaped refs");
439        assert!(!classified.partial);
440        assert!(classified.skipped_refs.is_empty());
441        assert_eq!(classified.native_ref_count, 2);
442        assert_eq!(classified.default_branch, b"refs/heads/main");
443    }
444
445    #[test]
446    fn complete_ref_classification_keeps_unsupported_refs_and_requires_head() {
447        let commit = GitObjectId::Sha1([4; 20]);
448        let head = ImportRefIdentity {
449            raw_name: b"HEAD".to_vec(),
450            raw_target: GitRefTarget::Symbolic(b"refs/heads/main".to_vec()),
451            peeled_commit: Some(commit.clone()),
452        };
453        let branch = ImportRefIdentity {
454            raw_name: b"refs/heads/main".to_vec(),
455            raw_target: GitRefTarget::Direct {
456                oid: commit.clone(),
457                object_type: GitRefObjectType::Commit,
458            },
459            peeled_commit: Some(commit.clone()),
460        };
461        let remote = ImportRefIdentity {
462            raw_name: b"refs/remotes/origin/main".to_vec(),
463            raw_target: GitRefTarget::Direct {
464                oid: commit,
465                object_type: GitRefObjectType::Commit,
466            },
467            peeled_commit: None,
468        };
469        let refs = vec![head, branch, remote];
470        let result = classify_frozen_import_refs(&refs).expect("complete snapshot");
471        assert_eq!(result.default_branch, b"refs/heads/main");
472        assert_eq!(result.native_ref_count, 1);
473        assert!(result.partial);
474        assert_eq!(
475            result.skipped_refs,
476            vec![SkippedImportRef {
477                raw_name: b"refs/remotes/origin/main".to_vec(),
478                reason: ImportSkipReason::RemoteTracking,
479            }]
480        );
481        assert_eq!(result.dispositions.len(), refs.len());
482        assert!(classify_frozen_import_refs(&refs[1..]).is_err());
483        let mut moved = refs;
484        moved[0].raw_target = GitRefTarget::Symbolic(b"refs/heads/absent".to_vec());
485        assert!(classify_frozen_import_refs(&moved).is_err());
486    }
487
488    #[test]
489    fn reserved_branch_is_skipped_before_native_emission() {
490        let oid = GitObjectId::Sha1([8; 20]);
491        let reference = ImportRefIdentity {
492            raw_name: b"refs/heads/heddle/reserved".to_vec(),
493            raw_target: GitRefTarget::Direct {
494                oid: oid.clone(),
495                object_type: GitRefObjectType::Commit,
496            },
497            peeled_commit: Some(oid),
498        };
499        assert!(matches!(
500            classify_git_import_ref(&reference),
501            Ok(ImportRefDisposition::Unsupported {
502                reason: ImportSkipReason::InvalidNativeName
503            })
504        ));
505    }
506}
heddle_object_model/object/thread_replication/git_import_graph.rs

heddle_object_model/object/thread_replication/
git_import_graph.rs
