inkandswitch / inkandswitch/keyhive

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

Open
#142 0 comments 0 reactions 0 assignees View on GitHub
bug
Dominant language
Rust
Stars
248
Forks
21
Avg merge
5d 15h
Merged PRs (30d)
9

Description

### 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:

![Image](https://github.com/user-attachments/assets/2ecbab8e-d9c4-4b88-a970-07a87a888fdb)

Here is another example with multiple bundles at different levels:

![Image](https://github.com/user-attachments/assets/1607b21f-dc6f-4819-8aff-86f7407addf9)

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 ):

```rust
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,
digest_ids: HashMap,
}

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 {
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

```shell

```

### Code of Conduct

- [x] I agree to follow this project's Code of Conduct

Contributor guide

Open the contributing guide

Research direction

Start with the provided Rust reproduction and the `missing_bundles()` entry point in the `beelay-core` workspace. Confirm the reported gaps across sequential loose commits and inspect how bundles are selected at different levels. Done means `missing_bundles()` returns bundles without leaving loose commits uncovered between them, with the reproduction serving as regression coverage.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
distributed-systems
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.