git_policy_cli/lfs/
lfs_pointer_scan.rs

1//! What:
2//!  The LFS objects a push introduces, found in process: the pointer blobs that the commits to be pushed add.
3//! Why:
4//!  `git-lfs push` starts a scanner (`git rev-list`, `git cat-file`, `git ls-remote`) and, when it finds anything, asks
5//!  the LFS server about it; most pushes add no pointer at all, so the wrapper reads the commits itself with the
6//!  in-process readers and starts `git-lfs` only when a pointer is found. The commits are those reachable from the pushed
7//!  tips and not reached before a known-good tip (the remote's tracking refs, when they describe the destination). Every
8//!  commit is compared with each of its parents, so a pointer added in one commit and removed in the next is still found.
9//!  Anything the readers do not fully understand, and any walk that grows past its limits, returns `None`, so the caller
10//!  asks `git-lfs`.
11//!
12//! In TS you'd write (pseudocode):
13//! ```ts
14//! const oids = newPointerObjects(odb, format, includeTips, stopTips, limits); // undefined: ask git-lfs
15//! ```
16
17#![cfg(unix)]
18
19use crate::lfs_pointer::{Verdict, decode_pointer};
20use crate::repo_read_layout::ObjectFormat;
21use crate::repo_read_object::{ObjectKind, name_length};
22use crate::repo_read_odb::ObjectDatabase;
23use crate::repo_read_tree::{CommitFields, MODE_GITLINK, is_tree_mode, parse_commit, parse_tree};
24use std::collections::{BTreeSet, HashMap, HashSet};
25use std::time::{Duration, Instant};
26
27/// The most commits one scan visits before it gives the question to `git-lfs`.
28pub const MAX_COMMITS: usize = 100_000;
29
30/// The longest one scan runs before it gives the question to `git-lfs`.
31pub const SCAN_BUDGET: Duration = Duration::from_secs(3);
32
33/// What one scan reads and remembers.
34struct Scan<'a> {
35    /// The objects.
36    database: &'a ObjectDatabase,
37    /// The object format.
38    format: ObjectFormat,
39    /// Parsed commits by name.
40    commits: HashMap<Vec<u8>, CommitFields>,
41    /// Committer times of the parsed commits, in seconds.
42    times: HashMap<Vec<u8>, i64>,
43    /// Comparisons already made: a tree followed by the parent trees it was compared with. The same tree compared with
44    ///  other parents (a root commit holding what a later commit also holds) is a different comparison.
45    seen_trees: HashSet<Vec<Vec<u8>>>,
46    /// Blobs that are new relative to some parent, by name.
47    candidates: BTreeSet<Vec<u8>>,
48    /// When the scan gives up.
49    deadline: Instant,
50}
51
52impl Scan<'_> {
53    /// The parsed commit `name`; `None` when it is missing, not a commit, or in a spelling the reader declines.
54    fn commit(&mut self, name: &[u8]) -> Option<CommitFields> {
55        if let Some(known) = self.commits.get(name) {
56            return Some(known.clone());
57        }
58        let object = self.database.read(name)?;
59        if object.kind != ObjectKind::Commit {
60            return None;
61        }
62        let parsed: CommitFields = parse_commit(object.bytes.as_slice(), self.format)?;
63        self.times.insert(name.to_vec(), committer_time(object.bytes.as_slice())?);
64        self.commits.insert(name.to_vec(), parsed.clone());
65        return Some(parsed);
66    }
67
68    /// The committer time of a commit already read.
69    fn time(&self, name: &[u8]) -> i64 {
70        return self.times.get(name).copied().unwrap_or_default();
71    }
72
73    /// The entries of the tree `name`.
74    fn tree(&self, name: &[u8]) -> Option<Vec<crate::repo_read_tree::TreeEntry>> {
75        let object = self.database.read(name)?;
76        if object.kind != ObjectKind::Tree {
77            return None;
78        }
79        return parse_tree(object.bytes.as_slice(), name_length(self.format));
80    }
81
82    /// Record the blobs of `tree` that none of the `parents` (trees at the same place) holds under the same name.
83    fn compare(&mut self, tree: &[u8], parents: &[Vec<u8>]) -> Option<()> {
84        if Instant::now() >= self.deadline {
85            return None;
86        }
87        if parents.iter().any(|parent| {
88            return parent.as_slice() == tree;
89        }) || !self.seen_trees.insert([vec![tree.to_vec()], parents.to_vec()].concat())
90        {
91            return Some(());
92        }
93        let entries = self.tree(tree)?;
94        let mut parent_entries = Vec::with_capacity(parents.len());
95        for parent in parents {
96            parent_entries.push(self.tree(parent)?);
97        }
98        for entry in &entries {
99            if entry.mode == MODE_GITLINK {
100                continue;
101            }
102            let counterparts: Vec<&crate::repo_read_tree::TreeEntry> = parent_entries
103                .iter()
104                .filter_map(|list| {
105                    return list.iter().find(|candidate| {
106                        return candidate.name == entry.name;
107                    });
108                })
109                .collect();
110            if is_tree_mode(entry.mode) {
111                let below: Vec<Vec<u8>> = counterparts
112                    .iter()
113                    .filter(|other| {
114                        return is_tree_mode(other.mode);
115                    })
116                    .map(|other| {
117                        return other.id.clone();
118                    })
119                    .collect();
120                self.compare(entry.id.as_slice(), below.as_slice())?;
121            } else if !counterparts.iter().any(|other| {
122                return other.id == entry.id && !is_tree_mode(other.mode);
123            }) {
124                self.candidates.insert(entry.id.clone());
125            }
126        }
127        return Some(());
128    }
129}
130
131/// How many commits are still popped after only known commits remain queued, because committer times can run backwards.
132const CLOCK_SKEW_SLOP: usize = 5;
133
134/// The committer time in seconds of a commit object's content.
135fn committer_time(bytes: &[u8]) -> Option<i64> {
136    let header_end: usize = bytes.windows(2).position(|pair| {
137        return pair == b"\n\n";
138    })?;
139    let line: &[u8] = bytes[..header_end].split(|byte| {
140        return *byte == b'\n';
141    }).find(|line| {
142        return line.starts_with(b"committer ");
143    })?;
144    let after_email: &[u8] = &line[line.iter().rposition(|byte| {
145        return *byte == b'>';
146    })? + 1..];
147    let text: &str = std::str::from_utf8(after_email).ok()?;
148    return text.split_whitespace().next()?.parse::<i64>().ok();
149}
150
151/// The queue of a date-ordered walk, with each commit marked as known to the destination or not.
152struct Walk {
153    /// Commits waiting to be read, newest first.
154    queue: std::collections::BinaryHeap<(i64, Vec<u8>)>,
155    /// Whether each commit seen is known to the destination (`true`) or to be pushed (`false`).
156    known: HashMap<Vec<u8>, bool>,
157    /// Commits in the queue.
158    queued: HashSet<Vec<u8>>,
159    /// How many queued commits are not known to the destination.
160    unknown_queued: usize,
161    /// Commits whose parents have been followed.
162    expanded: HashSet<Vec<u8>>,
163}
164
165impl Walk {
166    /// Note that `name` is known (or unknown) to the destination, queueing it the first time and, when a commit already
167    ///  followed turns out to be known, marking everything behind it as known too.
168    fn mark(&mut self, scan: &mut Scan<'_>, name: &[u8], known: bool) -> Option<()> {
169        let mut pending: Vec<Vec<u8>> = vec![name.to_vec()];
170        while let Some(current) = pending.pop() {
171            match self.known.get(current.as_slice()).copied() {
172                None => {
173                    scan.commit(current.as_slice())?;
174                    self.known.insert(current.clone(), known);
175                    self.queue.push((scan.time(current.as_slice()), current.clone()));
176                    self.queued.insert(current);
177                    if !known {
178                        self.unknown_queued += 1;
179                    }
180                }
181                Some(false) if known => {
182                    self.known.insert(current.clone(), true);
183                    if self.queued.contains(current.as_slice()) {
184                        self.unknown_queued -= 1;
185                    } else if self.expanded.contains(current.as_slice()) {
186                        pending.extend(scan.commit(current.as_slice())?.parents);
187                    }
188                }
189                Some(_) => {}
190            }
191        }
192        return Some(());
193    }
194}
195
196/// What:
197///  The commits reachable from `include` and not from `stop`, found by a walk ordered by committer time as `git rev-list`
198///  orders it.
199/// Why:
200///   A commit behind a known tip is known, even when it is reached first through another branch, so a merge of an old side
201///  branch does not drag the already-pushed history behind it into the scan. The walk ends once only known commits are
202///  queued, after a few more pops for clock skew; a wrong order can only keep a known commit in the answer, never drop
203///  a new one, because only a real parent chain from a known tip marks a commit known.
204///
205/// In TS you'd write (pseudocode):
206/// ```ts
207/// function newCommits(scan, include, stop): Uint8Array[] | undefined;
208/// ```
209fn new_commits(scan: &mut Scan<'_>, include: &[Vec<u8>], stop: &[Vec<u8>]) -> Option<Vec<Vec<u8>>> {
210    let mut walk: Walk = Walk {
211        queue: std::collections::BinaryHeap::new(),
212        known: HashMap::new(),
213        queued: HashSet::new(),
214        unknown_queued: 0,
215        expanded: HashSet::new(),
216    };
217    for name in stop {
218        walk.mark(scan, name.as_slice(), true)?;
219    }
220    for name in include {
221        walk.mark(scan, name.as_slice(), false)?;
222    }
223    let mut listed: Vec<Vec<u8>> = Vec::new();
224    let mut slop: usize = 0;
225    let mut popped: usize = 0;
226    while let Some((_, name)) = walk.queue.pop() {
227        walk.queued.remove(name.as_slice());
228        let known: bool = walk.known.get(name.as_slice()).copied().unwrap_or(true);
229        if !known {
230            walk.unknown_queued -= 1;
231            listed.push(name.clone());
232        }
233        popped += 1;
234        if popped > MAX_COMMITS || Instant::now() >= scan.deadline {
235            return None;
236        }
237        let parents: Vec<Vec<u8>> = scan.commit(name.as_slice())?.parents;
238        walk.expanded.insert(name);
239        for parent in &parents {
240            walk.mark(scan, parent.as_slice(), known)?;
241        }
242        if walk.unknown_queued == 0 {
243            slop += 1;
244            if slop > CLOCK_SKEW_SLOP {
245                break;
246            }
247        } else {
248            slop = 0;
249        }
250    }
251    return Some(
252        listed
253            .into_iter()
254            .filter(|name| {
255                return !walk.known.get(name.as_slice()).copied().unwrap_or(false);
256            })
257            .collect(),
258    );
259}
260
261/// What:
262///  The names of the LFS objects that the commits reachable from `include` and not from `stop` introduce, sorted, or
263///  `None` when the readers cannot answer.
264/// Why:
265///   The walk follows parents from the tips and does not cross a commit named in `stop`. A pointer counts when its blob is
266///  not what a parent holds at the same path, for every parent of a merge, so an object that exists anywhere in the
267///  pushed history is found once. A root commit is compared with an empty tree. Every blob read is decoded like
268///  `git-lfs` decodes it (`lfs_pointer`); a read that fails, a malformed tree, a missing parent (a shallow clone) or a
269///  walk past [`MAX_COMMITS`] or [`SCAN_BUDGET`] declines.
270///
271/// In TS you'd write (pseudocode):
272/// ```ts
273/// function newPointerObjects(odb, format, include: Uint8Array[], stop: Uint8Array[]): string[] | undefined;
274/// ```
275pub fn new_pointer_objects(
276    database: &ObjectDatabase,
277    format: ObjectFormat,
278    include: &[Vec<u8>],
279    stop: &[Vec<u8>],
280    budget: Duration,
281) -> Option<Vec<String>> {
282    let mut scan: Scan<'_> = Scan {
283        database,
284        format,
285        commits: HashMap::new(),
286        times: HashMap::new(),
287        seen_trees: HashSet::new(),
288        candidates: BTreeSet::new(),
289        deadline: Instant::now() + budget,
290    };
291    for name in new_commits(&mut scan, include, stop)? {
292        let commit: CommitFields = scan.commit(name.as_slice())?;
293        let mut parent_trees: Vec<Vec<u8>> = Vec::with_capacity(commit.parents.len());
294        for parent in &commit.parents {
295            parent_trees.push(scan.commit(parent.as_slice())?.tree);
296        }
297        scan.compare(commit.tree.as_slice(), parent_trees.as_slice())?;
298    }
299    let mut objects: BTreeSet<String> = BTreeSet::new();
300    for candidate in &scan.candidates {
301        if Instant::now() >= scan.deadline {
302            return None;
303        }
304        let blob = database.read(candidate.as_slice())?;
305        if blob.kind != ObjectKind::Blob {
306            return None;
307        }
308        match decode_pointer(blob.bytes.as_slice()) {
309            Verdict::NotUploadable => {}
310            Verdict::Pointer(name) => {
311                objects.insert(name);
312            }
313            Verdict::Decline => return None,
314        }
315    }
316    return Some(objects.into_iter().collect());
317}
318
319/// The scan is controlled in the test module.
320#[cfg(test)]
321#[path = "lfs_pointer_scan_tests.rs"]
322mod tests;
git_policy_cli/lfs/lfs_pointer_scan.rs

git_policy_cli/lfs/
lfs_pointer_scan.rs
