git_zero_core/object/
links.rs

1//! Stream structural links into host-owned indexes without retaining a graph.
2use crate::{Error, ObjectFormat, ObjectId, ObjectInfo, ObjectKind, Result, names::cmp_tree_names};
3
4#[derive(Clone, Copy, Debug, Eq, PartialEq)]
5pub struct LinkLimits {
6    pub max_body_bytes: u64,
7    pub max_links: u64,
8}
9
10#[derive(Clone, Copy, Debug, Eq, PartialEq)]
11pub enum LinkRelation {
12    RootTree,
13    Parent,
14    TagTarget,
15}
16
17#[derive(Clone, Copy, Debug, Eq, PartialEq)]
18pub enum LinkStatus<'name> {
19    NeedInput,
20    Link {
21        id: ObjectId,
22        kind: ObjectKind,
23        relation: LinkRelation,
24    },
25    TreeEntry {
26        id: ObjectId,
27        mode: u32,
28        name: &'name [u8],
29        kind: Option<ObjectKind>,
30        canonical_mode: bool,
31        zero_padded: bool,
32    },
33    Finished,
34}
35
36#[derive(Clone, Copy, Debug, Eq, PartialEq)]
37pub struct LinkProgress<'name> {
38    pub consumed: usize,
39    pub status: LinkStatus<'name>,
40}
41
42#[derive(Clone, Copy)]
43enum Phase {
44    Blob,
45    CommitTree,
46    Parents,
47    Headers,
48    TagObject,
49    TagType,
50    TagName,
51    TagHeaders,
52    Message,
53    Mode,
54    Name,
55    Id,
56    Done,
57}
58
59struct Names<'a> {
60    previous: &'a mut [u8],
61    current: &'a mut [u8],
62}
63struct State {
64    format: ObjectFormat,
65    info: ObjectInfo,
66    limits: LinkLimits,
67    phase: Phase,
68    position: u64,
69    links: u64,
70    header: [u8; 80],
71    header_len: usize,
72    header_overflow: bool,
73    target: ObjectId,
74    mode: u32,
75    mode_digits: u32,
76    padded_mode: bool,
77    previous_mode: u32,
78    previous_len: usize,
79    current_len: usize,
80    has_previous: bool,
81    id: [u8; 32],
82    id_len: usize,
83    failure: Option<Error>,
84}
85
86/// Scan one canonical object body across arbitrary chunks. Blobs/messages are
87/// skipped without retaining them; commit parents and tag targets are emitted
88/// with their expected kinds. Tree names borrow caller scratch until resumption.
89/// Scratch is divided equally into current/previous names; other kinds need none.
90///
91/// This scans syntax and adjacent tree order, not complete graph validity.
92/// Authenticate the body separately with `ObjectDigest`. The host MUST check
93/// target existence/kinds and tree-name uniqueness (including file/directory
94/// aliases separated in Git order), persist parent edges and enforce ref policy.
95/// Gitlinks name external repositories and emit `kind: None`.
96///
97/// Historical noncanonical tree modes with recognized type bits, including
98/// zero padding and old regular-file permissions, are preserved and flagged.
99/// They are not silently rewritten or rejected as graph errors.
100pub struct LinkDecoder<'scratch> {
101    state: State,
102    names: Names<'scratch>,
103}
104
105impl<'scratch> LinkDecoder<'scratch> {
106    pub fn new(
107        info: ObjectInfo,
108        format: ObjectFormat,
109        names: &'scratch mut [u8],
110        limits: LinkLimits,
111    ) -> Result<Self> {
112        if info.size > limits.max_body_bytes {
113            return Err(Error::LimitExceeded);
114        }
115        let midpoint = names.len() / 2;
116        let (previous, current) = names[..midpoint * 2].split_at_mut(midpoint);
117        let phase = match info.kind {
118            ObjectKind::Blob => Phase::Blob,
119            ObjectKind::Tree => Phase::Mode,
120            ObjectKind::Commit => Phase::CommitTree,
121            ObjectKind::Tag => Phase::TagObject,
122        };
123        Ok(Self {
124            state: State {
125                format,
126                info,
127                limits,
128                phase,
129                position: 0,
130                links: 0,
131                header: [0; 80],
132                header_len: 0,
133                header_overflow: false,
134                target: format.zero_id(),
135                mode: 0,
136                mode_digits: 0,
137                padded_mode: false,
138                previous_mode: 0,
139                previous_len: 0,
140                current_len: 0,
141                has_previous: false,
142                id: [0; 32],
143                id_len: 0,
144                failure: None,
145            },
146            names: Names { previous, current },
147        })
148    }
149
150    pub fn position(&self) -> u64 {
151        self.state.position
152    }
153
154    /// Events may consume a prefix. Resubmit the suffix with the same EOF flag.
155    /// Every error is terminal; all emitted metadata remains provisional.
156    pub fn update<'name>(
157        &'name mut self,
158        input: &[u8],
159        end_of_input: bool,
160    ) -> Result<LinkProgress<'name>> {
161        let result = self.state.advance(input, end_of_input, &mut self.names);
162        if let Err(error) = result {
163            self.state.failure = Some(error);
164        }
165        result
166    }
167
168    pub fn finish(&self) -> Result<()> {
169        if let Some(error) = self.state.failure {
170            return Err(error);
171        }
172        if matches!(self.state.phase, Phase::Done) {
173            Ok(())
174        } else {
175            Err(Error::InvalidObject)
176        }
177    }
178}
179
180impl State {
181    fn advance<'name>(
182        &mut self,
183        input: &[u8],
184        eof: bool,
185        names: &'name mut Names<'_>,
186    ) -> Result<LinkProgress<'name>> {
187        if let Some(error) = self.failure {
188            return Err(error);
189        }
190        let mut consumed = 0;
191        loop {
192            if self.position == self.info.size {
193                if consumed != input.len() {
194                    return Err(Error::InvalidObject);
195                }
196                let status = self.end(eof)?;
197                return Ok(LinkProgress { consumed, status });
198            }
199            if consumed == input.len() {
200                if eof {
201                    return Err(Error::InvalidObject);
202                }
203                return Ok(LinkProgress {
204                    consumed,
205                    status: LinkStatus::NeedInput,
206                });
207            }
208            if matches!(self.phase, Phase::Blob | Phase::Message) {
209                let count =
210                    (self.info.size - self.position).min((input.len() - consumed) as u64) as usize;
211                self.position += count as u64;
212                consumed += count;
213                continue;
214            }
215            let byte = input[consumed];
216            consumed += 1;
217            self.position += 1;
218            match self.phase {
219                Phase::Mode => self.mode_byte(byte)?,
220                Phase::Name => self.name_byte(byte, names)?,
221                Phase::Id => {
222                    if let Some(id) = self.id_byte(byte, names)? {
223                        return Ok(LinkProgress {
224                            consumed,
225                            status: LinkStatus::TreeEntry {
226                                id,
227                                mode: self.previous_mode,
228                                name: &names.previous[..self.previous_len],
229                                kind: tree_kind(self.previous_mode)?,
230                                canonical_mode: !self.padded_mode
231                                    && canonical_mode(self.previous_mode),
232                                zero_padded: self.padded_mode,
233                            },
234                        });
235                    }
236                }
237                _ => {
238                    if let Some(status) = self.header_byte(byte)? {
239                        return Ok(LinkProgress { consumed, status });
240                    }
241                }
242            }
243        }
244    }
245
246    fn name_byte(&mut self, byte: u8, names: &mut Names<'_>) -> Result<()> {
247        if byte == 0 {
248            self.phase = Phase::Id;
249            self.id_len = 0;
250            return Ok(());
251        }
252        *names
253            .current
254            .get_mut(self.current_len)
255            .ok_or(Error::BufferTooSmall)? = byte;
256        self.current_len += 1;
257        Ok(())
258    }
259
260    fn id_byte(&mut self, byte: u8, names: &mut Names<'_>) -> Result<Option<ObjectId>> {
261        self.id[self.id_len] = byte;
262        self.id_len += 1;
263        if self.id_len != self.format.id_length() {
264            return Ok(None);
265        }
266        let id = ObjectId::from_bytes(self.format, &self.id[..self.id_len])?;
267        if id.is_zero() {
268            return Err(Error::InvalidObject);
269        }
270        self.tree_entry(names)?;
271        Ok(Some(id))
272    }
273
274    fn header_byte(&mut self, byte: u8) -> Result<Option<LinkStatus<'static>>> {
275        if byte == b'\n' {
276            let status = self.line()?;
277            self.header_len = 0;
278            self.header_overflow = false;
279            if status.is_some() {
280                self.charge()?;
281            }
282            return Ok(status);
283        }
284        if byte == 0 {
285            return Err(Error::InvalidObject);
286        }
287        if self.header_len == self.header.len() {
288            self.header_overflow = true;
289        } else {
290            self.header[self.header_len] = byte;
291            self.header_len += 1;
292        }
293        Ok(None)
294    }
295
296    fn end(&mut self, eof: bool) -> Result<LinkStatus<'static>> {
297        if matches!(self.phase, Phase::Done) {
298            return Ok(LinkStatus::Finished);
299        }
300        let complete = match self.phase {
301            Phase::Blob | Phase::Message => true,
302            Phase::Mode => self.mode_digits == 0,
303            Phase::Headers | Phase::TagHeaders => self.header_len == 0 && !self.header_overflow,
304            _ => false,
305        };
306        if !complete {
307            return Err(Error::InvalidObject);
308        }
309        if !eof {
310            return Ok(LinkStatus::NeedInput);
311        }
312        self.phase = Phase::Done;
313        Ok(LinkStatus::Finished)
314    }
315
316    fn charge(&mut self) -> Result<()> {
317        if self.links == self.limits.max_links {
318            return Err(Error::LimitExceeded);
319        }
320        self.links += 1;
321        Ok(())
322    }
323
324    fn mode_byte(&mut self, byte: u8) -> Result<()> {
325        match byte {
326            b'0'..=b'7' => {
327                if self.mode_digits == 0 {
328                    self.padded_mode = byte == b'0';
329                }
330                self.mode = self
331                    .mode
332                    .checked_mul(8)
333                    .and_then(|mode| mode.checked_add(u32::from(byte - b'0')))
334                    .ok_or(Error::InvalidObject)?;
335                self.mode_digits = self.mode_digits.saturating_add(1);
336            }
337            b' ' if self.mode_digits != 0 => {
338                tree_kind(self.mode)?;
339                self.phase = Phase::Name;
340            }
341            _ => return Err(Error::InvalidObject),
342        }
343        Ok(())
344    }
345
346    fn tree_entry(&mut self, names: &mut Names<'_>) -> Result<()> {
347        let name = &names.current[..self.current_len];
348        if name.is_empty()
349            || name == b"."
350            || name == b".."
351            || name.eq_ignore_ascii_case(b".git")
352            || name.contains(&b'/')
353        {
354            return Err(Error::InvalidFileName);
355        }
356        if self.has_previous
357            && cmp_tree_names(
358                &names.previous[..self.previous_len],
359                self.previous_mode & 0o170000 == 0o040000,
360                name,
361                self.mode & 0o170000 == 0o040000,
362            ) != core::cmp::Ordering::Less
363        {
364            return Err(Error::UnsortedFiles);
365        }
366        self.charge()?;
367        core::mem::swap(&mut names.previous, &mut names.current);
368        self.previous_len = self.current_len;
369        self.previous_mode = self.mode;
370        self.has_previous = true;
371        self.current_len = 0;
372        self.mode = 0;
373        self.mode_digits = 0;
374        self.phase = Phase::Mode;
375        Ok(())
376    }
377
378    fn line(&mut self) -> Result<Option<LinkStatus<'static>>> {
379        let line = &self.header[..self.header_len];
380        let edge = match self.phase {
381            Phase::CommitTree => {
382                let id = link(line, b"tree ", self.format, self.header_overflow)?;
383                self.phase = Phase::Parents;
384                Some(LinkStatus::Link {
385                    id,
386                    kind: ObjectKind::Tree,
387                    relation: LinkRelation::RootTree,
388                })
389            }
390            Phase::Parents if line.starts_with(b"parent ") => Some(LinkStatus::Link {
391                id: link(line, b"parent ", self.format, self.header_overflow)?,
392                kind: ObjectKind::Commit,
393                relation: LinkRelation::Parent,
394            }),
395            Phase::TagObject => {
396                self.target = link(line, b"object ", self.format, self.header_overflow)?;
397                self.phase = Phase::TagType;
398                None
399            }
400            Phase::TagType => {
401                if self.header_overflow {
402                    return Err(Error::InvalidObject);
403                }
404                let kind = ObjectKind::from_tag_header(line)?;
405                self.phase = Phase::TagName;
406                Some(LinkStatus::Link {
407                    id: self.target,
408                    kind,
409                    relation: LinkRelation::TagTarget,
410                })
411            }
412            Phase::TagName => {
413                if !line.starts_with(b"tag ") {
414                    return Err(Error::InvalidObject);
415                }
416                self.phase = Phase::TagHeaders;
417                None
418            }
419            _ => {
420                self.phase = if line.is_empty() {
421                    Phase::Message
422                } else if matches!(self.phase, Phase::TagHeaders) {
423                    Phase::TagHeaders
424                } else {
425                    Phase::Headers
426                };
427                None
428            }
429        };
430        Ok(edge)
431    }
432}
433
434fn link(line: &[u8], prefix: &[u8], format: ObjectFormat, overflow: bool) -> Result<ObjectId> {
435    if overflow {
436        return Err(Error::InvalidObject);
437    }
438    let hex = line
439        .strip_prefix(prefix)
440        .filter(|hex| hex.len() == format.hex_length())
441        .ok_or(Error::InvalidObject)?;
442    ObjectId::from_hex(hex).map_err(|_| Error::InvalidObject)
443}
444
445fn tree_kind(mode: u32) -> Result<Option<ObjectKind>> {
446    Ok(match mode & 0o170000 {
447        0o040000 => Some(ObjectKind::Tree),
448        0o100000 | 0o120000 => Some(ObjectKind::Blob),
449        0o160000 => None,
450        _ => return Err(Error::InvalidObject),
451    })
452}
453
454fn canonical_mode(mode: u32) -> bool {
455    matches!(mode, 0o040000 | 0o100644 | 0o100755 | 0o120000 | 0o160000)
456}
git_zero_core/object/links.rs

git_zero_core/object/
links.rs
