girt 0.18.0

An incremental, idiomatic Rust implementation of Git
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

//! Reuse only complete closures computed from this one immutable verified graph and bit order.
use std::collections::HashMap;
use std::sync::atomic::AtomicBool;

use super::graph::Graph;
use super::{WriteError, WriteLimits, check};
use crate::ObjectKind;

pub(super) struct Closures<'graph, 'ids> {
    graph: &'graph Graph<'ids>,
    inverse: &'graph [usize],
    remaining: usize,
    cached: HashMap<usize, Vec<u64>>,
    retained_bytes: usize,
    max_bytes: usize,
}

impl<'graph, 'ids> Closures<'graph, 'ids> {
    pub fn new(graph: &'graph Graph<'ids>, inverse: &'graph [usize], limits: WriteLimits) -> Self {
        Self {
            graph,
            inverse,
            remaining: limits.max_visits,
            cached: HashMap::new(),
            retained_bytes: 0,
            max_bytes: limits.max_bytes,
        }
    }

    pub fn reachable(&mut self, root: usize, cancel: &AtomicBool) -> Result<Vec<u64>, WriteError> {
        let before = self.remaining;
        let mut bitmap = vec![0_u64; self.graph.kinds.len().div_ceil(64)];
        let mut stack = vec![root];
        while let Some(index) = stack.pop() {
            check(cancel)?;
            charge(&mut self.remaining)?;
            let bit = self.inverse[index];
            let word = &mut bitmap[bit / 64];
            let mask = 1 << (bit % 64);
            if *word & mask != 0 {
                continue;
            }
            *word |= mask;
            if self.graph.kinds[index] == ObjectKind::Commit
                && let Some(cached) = self.cached.get(&index)
            {
                for (word, &cached) in bitmap.iter_mut().zip(cached) {
                    check(cancel)?;
                    charge(&mut self.remaining)?;
                    *word |= cached;
                }
                continue;
            }
            for &target in self.graph.targets(index) {
                check(cancel)?;
                charge(&mut self.remaining)?;
                let bit = self.inverse[target];
                if bitmap[bit / 64] & (1 << (bit % 64)) == 0 {
                    stack.push(target);
                }
            }
        }
        // A future hit already pays for its root pop. Do not retain a closure whose word union
        // costs more than the remaining traversal, or let a large sparse inventory fill the cache
        // with cheap leaf closures. Clones are bounded separately from the output artifact bytes.
        let work = before - self.remaining;
        if work.saturating_sub(1) > bitmap.len()
            && let Some(bytes) = bitmap
                .len()
                .checked_mul(size_of::<u64>())
                .and_then(|bytes| self.retained_bytes.checked_add(bytes))
                .filter(|&bytes| bytes <= self.max_bytes)
        {
            self.cached.insert(root, bitmap.clone());
            self.retained_bytes = bytes;
        }
        Ok(bitmap)
    }
}

fn charge(budget: &mut usize) -> Result<(), WriteError> {
    *budget = budget
        .checked_sub(1)
        .ok_or(WriteError::Limit("reachability visits"))?;
    Ok(())
}