Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

RRB size table reports incorrect length #74

Closed
krobelus opened this issue Mar 6, 2019 · 0 comments
Closed

RRB size table reports incorrect length #74

krobelus opened this issue Mar 6, 2019 · 0 comments

Comments

@krobelus
Copy link
Contributor

krobelus commented Mar 6, 2019

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]

krobelus added a commit to krobelus/im-rs that referenced this issue Mar 8, 2019
When a chunk does not fully fit in a node, we drain as many elements from the
chunk into the node and later push the leftover chunk to a sibling.

This commit makes sure that the size table of the parent node is updated
correctly. We need to add the number of drained elements to the size table
entry of the current element (and all entries to the left).

Closes bodil#74
krobelus added a commit to krobelus/im-rs that referenced this issue Mar 8, 2019
When a chunk does not fully fit in a node, we drain as many elements from the
chunk into the node and later push the leftover chunk to a sibling.

This commit makes sure that the size field of the parent node is updated
correctly. For dense nodes, we can simply add the number of drained elements to
the size. If there is a size table, we add that number to the size entry
corresponding to the current element and all entries to the right.

Closes bodil#74
krobelus added a commit to krobelus/im-rs that referenced this issue Mar 8, 2019
When a chunk does not fully fit in a node, we drain as many elements from the
chunk into the node and later push the leftover chunk to a sibling.

This commit makes sure that the size field of the parent node is updated
correctly. For dense nodes, we can simply add the number of drained elements to
the size. If there is a size table, we add that number to the size entry
corresponding to the current element and all entries to the right.

Closes bodil#74
krobelus added a commit to krobelus/im-rs that referenced this issue Mar 8, 2019
When a chunk does not fully fit in a node, we drain as many elements from the
chunk into the node and later push the leftover chunk to a sibling.

This commit makes sure that the size field of the parent node is updated
correctly. For dense nodes, we can simply add the number of drained elements to
the size. If there is a size table, we add that number to the size entry
corresponding to the current element and all entries to the right.

Closes bodil#74
krobelus added a commit to krobelus/im-rs that referenced this issue Mar 8, 2019
When a chunk does not fully fit in a node, we drain as many elements from the
chunk into the node and later push the leftover chunk to a sibling.

This commit makes sure that the size field of the parent node is updated
correctly. For dense nodes, we can simply add the number of drained elements to
the size. If there is a size table, we add that number to the size entry
corresponding to the current element and all entries to the right.

Closes bodil#74
krobelus added a commit to krobelus/im-rs that referenced this issue Mar 8, 2019
When a chunk does not fully fit in a node, we drain as many elements from the
chunk into the node and later push the leftover chunk to a sibling.

This commit makes sure that the size field of the parent node is updated
correctly. For dense nodes, we can simply add the number of drained elements to
the size. If there is a size table, we add that number to the size entry
corresponding to the current element and all entries to the right.

Closes bodil#74
@bodil bodil closed this as completed in #75 Mar 11, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant