[Bug]: Missing Bundles Reported by Sedimentree Leaf Uncompressed Gaps

[zicklag]

What happened?

I've noticed that when creating a chain of sequential loose commits in a sedimentree, and then calling missing_bundles(), it returns a list of bundles that leaves gaps of loose commits in between the bundles.

For example, here is a chain of commits with two bundles. I use short sequential names for the commit and follow the ID with there Level in parenthesis. I've tweaked the top level and set it to 1 and I've changed the level base to base 3 instead of base 10 to produce bundles with relatively fewer commits so that it's easy to visualize:

Here is another example with multiple bundles at different levels:

I have some code to produce the graphs and commits with pseudo-random commit trees ( I can push to a repo if you need to reproduce ):

use std::{collections::HashMap, io::Write};

use anyhow::{Result, anyhow};
use rand::{Rng, SeedableRng, rngs::StdRng};
use resvg::{tiny_skia, usvg};
use sedimentree::{BlobMeta, Digest, DocumentId, Level, LooseCommit, Sedimentree};

#[derive(Clone, Copy, Hash, PartialEq, Eq, Default)]
struct Id(u16, Level);

impl std::fmt::Display for Id {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}({})", hex::encode(self.0.to_be_bytes()), self.1.0)
    }
}

#[derive(Default)]
struct CommitIds {
    n: u16,
    id_digests: HashMap<Id, Digest>,
    digest_ids: HashMap<Digest, Id>,
}

impl CommitIds {
    fn add(&mut self, digest: Digest) -> Id {
        let id = Id(self.n, Level::from(digest));
        self.n += 1;
        self.id_digests.insert(id, digest);
        self.digest_ids.insert(digest, id);
        id
    }

    fn get(&self, digest: Digest) -> Id {
        *self.digest_ids.get(&digest).unwrap()
    }
    fn get_digest(&self, id: Id) -> Digest {
        *self.id_digests.get(&id).unwrap()
    }
    fn iter(&self) -> impl Iterator<Item = (Digest, Id)> {
        self.digest_ids.iter().map(|(d, i)| (*d, *i))
    }
}

fn main() -> Result<()> {
    let mut rng = StdRng::from_seed([0; 32]);
    let mut ids = CommitIds::default();

    let mut random_digest = || {
        let bytes: [u8; 32] = rng.r#gen();
        Digest::new(&bytes)
    };
    let random_blob = || {
        let mut rng = StdRng::from_seed([1; 32]);
        BlobMeta::new(&rng.r#gen::<[u8; 32]>())
    };
    let mut prev_commit = random_digest();
    ids.add(prev_commit);
    let mut commits = vec![LooseCommit::new(prev_commit, vec![], random_blob())];
    loop {
        let digest = random_digest();
        ids.add(digest);
        commits.push(LooseCommit::new(digest, vec![prev_commit], random_blob()));
        prev_commit = digest;

        if Sedimentree::new(vec![], commits.clone())
            .missing_bundles(DocumentId([0; 32]))
            .len()
            >= 6
        {
            break;
        }
    }
    dbg!(commits.len());

    let mut s = String::new();
    s += "digraph {\n";
    for (_digest, id) in ids.iter() {
        s += &format!(
            "c{}[label=\"{}\" color={}]\n",
            id.0,
            id,
            if id.1.0 > 0 { "red" } else { "black" }
        );
    }

    for commit in &commits {
        for parent in commit.parents() {
            let commit = ids.get(commit.digest());
            let parent = ids.get(*parent);
            s += &format!("c{}->c{}\n", commit.0, parent.0)
        }
    }

    let tree = Sedimentree::new(vec![], commits);
    let bundles = tree.missing_bundles(DocumentId([0; 32]));

    for bundle in bundles {
        s += &format!("b{}[label=\"Bundle\"]\n", bundle.start());
        s += &format!("b{}->c{}\n", bundle.start(), ids.get(bundle.start()).0);
        s += &format!("b{}->c{}\n", bundle.start(), ids.get(bundle.end()).0);
        for check in bundle.checkpoints() {
            s += &format!("b{}->c{} [color=green]\n", bundle.start(), ids.get(*check).0);
        }
    }

    s += "}";

    {
        use layout::{backends::svg::SVGWriter, gv};
        std::fs::write("./commit-graph.gitignore.dot", &s)?;
        let g = gv::DotParser::new(&s)
            .process()
            .map_err(|e| anyhow!("{e}"))?;
        let mut gb = gv::GraphBuilder::new();
        gb.visit_graph(&g);
        let mut vg = gb.get();
        let mut svg = SVGWriter::new();
        vg.do_it(false, false, false, &mut svg);
        let svg = svg.finalize();
        std::fs::write("./commit-graph.gitignore.svg", &svg)?;

        let mut opt = usvg::Options::default();
        opt.fontdb_mut().load_system_fonts();
        let tree = usvg::Tree::from_data(svg.as_bytes(), &opt)?;
        let pixmap_size = tree.size().to_int_size();
        let mut pixmap = tiny_skia::Pixmap::new(pixmap_size.width(), pixmap_size.height()).unwrap();
        pixmap.fill(tiny_skia::Color::WHITE);
        resvg::render(&tree, tiny_skia::Transform::default(), &mut pixmap.as_mut());
        pixmap.save_png("./commit-graph.gitignore.png")?;
    }

    Ok(())
}

Version

fdf996c

Which librraies in this workspace are impacted?

beelay-core

On which environment did you encounter this on?

Other

Which OSes have you noticed the issue on?

Ubuntu

Relevant log output

Code of Conduct

• I agree to follow this project's Code of Conduct