libvctrl 0.5.1

A robust, content-addressed version control engine for arbitrary data, designed for embedding into applications.
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

use crate::domain::hash::Hash;
use crate::domain::object::Object;
use crate::error::VctrlError;
use crate::storage::traits::ObjectStore;
use std::collections::{HashSet, VecDeque};

const MAX_MERGE_BASE_VISITED: usize = 100_000;

pub fn find_merge_base(
    store: &dyn ObjectStore,
    a: Hash,
    b: Hash,
) -> Result<Option<Hash>, VctrlError> {
    let mut ancestors = HashSet::new();
    let mut queue = VecDeque::new();
    let mut visited_count = 0;

    queue.push_back(a);
    while let Some(hash) = queue.pop_front() {
        if visited_count > MAX_MERGE_BASE_VISITED {
            return Err(VctrlError::Other("merge base search exceeded limit".into()));
        }
        visited_count += 1;

        if !ancestors.insert(hash) {
            continue;
        }
        if let Some(Object::Commit(commit)) = store.get(&hash)? {
            for parent in &commit.parents {
                queue.push_back(*parent);
            }
        }
    }

    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    queue.push_back(b);
    while let Some(hash) = queue.pop_front() {
        if visited_count > MAX_MERGE_BASE_VISITED {
            return Err(VctrlError::Other("merge base search exceeded limit".into()));
        }
        visited_count += 1;

        if !visited.insert(hash) {
            continue;
        }
        if ancestors.contains(&hash) {
            return Ok(Some(hash));
        }
        if let Some(Object::Commit(commit)) = store.get(&hash)? {
            for parent in &commit.parents {
                queue.push_back(*parent);
            }
        }
    }
    Ok(None)
}

pub fn is_ancestor(
    store: &dyn ObjectStore,
    ancestor: Hash,
    descendant: Hash,
) -> Result<bool, VctrlError> {
    let base = find_merge_base(store, ancestor, descendant)?;
    Ok(base == Some(ancestor))
}