Closed
Description
I found a trace where the size tables seem to behave strangely.
Reproduce it with this program, cargo run --release < trace should work where input file trace can be found here: https://gist.github.com/krobelus/b921d2f2cdde4b4b5101aba34fda87fe.
It crashes in the last line because the computed index is out of bounds.
use std::io::BufRead;
use std::str::FromStr;
fn main() {
let mut x = im::Vector::new();
let mut lines = std::io::BufReader::new(std::io::stdin()).lines();
while let Some(line) = lines.next().map(|l| l.unwrap()) {
let words: Vec<&str> = line.split(' ').collect();
let arg = usize::from_str(words[1]).unwrap();
match words[0] {
"push" => {
for _ in 0..arg {
x.push_back(0u32);
}
}
"remove" => {
x.remove(arg);
}
_ => unreachable!(),
};
}
assert!(x.len() != 0);
eprintln!("{}", x[x.len() - 1])
}Below is a representation of the Vector x just before executing the last line of above program.
I observe that the length of the middle part is reported to be 8215 (the last offset in the size table, see Node::len()).
However, summing the individual lengths of the 3 nodes in the middle part gives a different result:
4093 + 4096 + 45 = 8234. This is the actual length of the middle part.
This diff is a workaround that would prevent the example at hand from crashing, but I think that we need to make the size table report the correct size instead - or are they fine like this? Thank you!
pub fn len(&self) -> usize {
match self.children {
Entry::Nodes(Size::Size(size), _) => size,
- Entry::Nodes(Size::Table(ref size_table), _) => *(size_table.last().unwrap_or(&0)),
+ Entry::Nodes(Size::Table(_), ref children) => {
+ children.iter().map(|child| child.len()).sum()
+ }
Entry::Values(ref values) => values.len(),
Entry::Empty => 0,
}length 8299
middle_level 2
outer_f [length = 0]
inner_f [length = 0]
middle:
Nodes [length = 3], Table(Chunk[4093, 8170, 8215])
Nodes [length = 64], Size(4093)
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 61]
Nodes [length = 64], Size(4096)
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Values [length = 64]
Nodes [length = 1], Size(45)
Values [length = 45]
inner_b [length = 64]
outer_b [length = 1]
Metadata
Metadata
Assignees
Labels
No labels