Rust - Collecting slices of a Vec in a recursive function

user_11840637 0
Viewed 259

I am currently trying to build a huffman encoding program and am struggling with a problem I have while traversing my generated huffman tree to create a lookup table. I decided to implement said traversal with a recursive function. In the actual implementation I use the bitvec crate to save bitsequences, but for simplicitly I will use Vec<bool> in this post.

The idea I had was to save a collection of all codewords in the Vec codewords and then only save a slice out of that vector for the actual lookup table, for which I used a HashMap.

The issue is how exactly I would solve adding a 0 or a 1 for both the left and right traversal. My idea here was to save a clone of a slice of the current sequence, append a 0 to codewords, then append that clone to the end of codewords after traversing to the left so that I can push a 1 and traverse to the right. The function I came up with looks like this:

use std::collections::HashMap;

// ignore everything being public, I use getters in the real code
pub struct HufTreeNode {
    pub val: u8,
    pub freq: usize,
    pub left: i16,
    pub right: i16,
}

fn traverse_tree<'a>(
    cur_index: usize,
    height: i16,
    codewords: &'a mut Vec<bool>,
    lookup_table: &mut HashMap<u8, &'a [bool]>,
    huffman_tree: &[HufTreeNode],
) {
    let cur_node = &huffman_tree[cur_index];

    // if the left child is -1, we reached a leaf
    if cur_node.left == -1 {
        // the last `height` bits in codewords
        let cur_sequence = &codewords[(codewords.len() - 1 - height as usize)..];
        lookup_table.insert(cur_node.val, cur_sequence);
        return;
    }

    // save the current sequence so we can traverse to the right afterwards
    let mut cur_sequence = codewords[(codewords.len() - 1 - height as usize)..].to_vec();
    codewords.push(false);
    traverse_tree(
        cur_node.left as usize,
        height + 1,
        codewords, // mutable borrow - argument requires that `*codewords` is borrowed for `'a`
        lookup_table,
        huffman_tree,
    );

    // append the previously saved current sequence
    codewords.append(&mut cur_sequence); // second mutable borrow occurs here
    codewords.push(true); // third mutable borrow occurs here
    traverse_tree(
        cur_node.right as usize,
        height + 1,
        codewords, // fourth mutable borrow occurs here
        lookup_table,
        huffman_tree,
    );
}

fn main() {
    // ...
}

Apparently there is an issue with lifetimes and borrowing in that snippet of code, and I kind of get what the problem is. From what I understand, when I give codewords as a parameter in the recursive call, it has to borrow the vector for as long as I save the slice in lookup_table which is obviously not possible, causing the error. How do I solve this?

This is what cargo check gives me:

error[E0499]: cannot borrow `*codewords` as mutable more than once at a time
  --> untitled.rs:43:5
   |
14 |   fn traverse_tree<'a>(
   |                    -- lifetime `'a` defined here
...
34 | /     traverse_tree(
35 | |         cur_node.left as usize,
36 | |         height + 1,
37 | |         codewords, // mutable borrow - argument requires that `*codewords` is borrowed for `'a`
   | |         --------- first mutable borrow occurs here
38 | |         lookup_table,
39 | |         huffman_tree,
40 | |     );
   | |_____- argument requires that `*codewords` is borrowed for `'a`
...
43 |       codewords.append(&mut cur_sequence); // second mutable borrow occurs here
   |       ^^^^^^^^^ second mutable borrow occurs here

error[E0499]: cannot borrow `*codewords` as mutable more than once at a time
  --> untitled.rs:44:5
   |
14 |   fn traverse_tree<'a>(
   |                    -- lifetime `'a` defined here
...
34 | /     traverse_tree(
35 | |         cur_node.left as usize,
36 | |         height + 1,
37 | |         codewords, // mutable borrow - argument requires that `*codewords` is borrowed for `'a`
   | |         --------- first mutable borrow occurs here
38 | |         lookup_table,
39 | |         huffman_tree,
40 | |     );
   | |_____- argument requires that `*codewords` is borrowed for `'a`
...
44 |       codewords.push(true); // third mutable borrow occurs here
   |       ^^^^^^^^^ second mutable borrow occurs here

error[E0499]: cannot borrow `*codewords` as mutable more than once at a time
  --> untitled.rs:48:9
   |
14 |   fn traverse_tree<'a>(
   |                    -- lifetime `'a` defined here
...
34 | /     traverse_tree(
35 | |         cur_node.left as usize,
36 | |         height + 1,
37 | |         codewords, // mutable borrow - argument requires that `*codewords` is borrowed for `'a`
   | |         --------- first mutable borrow occurs here
38 | |         lookup_table,
39 | |         huffman_tree,
40 | |     );
   | |_____- argument requires that `*codewords` is borrowed for `'a`
...
48 |           codewords, // fourth mutable borrow occurs here
   |           ^^^^^^^^^ second mutable borrow occurs here

What am I missing here? Is there some magical function in the vector API that I'm missing, and why exactly does this create lifetime issues in the first place? From what I can tell, all my lifetimes are correct because codewords always lives for long enough for lookup_table to save all those slices and I never mutably borrow something twice at the same time. If there was something wrong with my lifetimes, the compiler would complain inside the if cur_node.left == -1 block, and the cur_sequence I take after it is an owned Vec, so there can't be any borrowing issues with that. So the issue really is with the core idea of having a recursive function with a mutable reference as a parameter.

Is there any way for me to solve this? I tried making codewords owned and returning it, but then the compiler cannot ensure that the bitsequence I'm saving inside lookup_table lives for long enough. The only idea I still have is to save owned vectors inside lookup_table, but at that point the codewords vector is obselete in the first place and I can simply implement this by having a cur_sequence vector as parameter which I clone in every call, but I chose my approach for a better cache performance in the actual encoding process right after, which I would then lose.

ownership rust huffman-code recursion lifetime
1 Answers

The problem is that when you create a slice cur_sequence from codewords like you did in let cur_sequence = &codewords[(codewords.len() - 1 - height as usize)..];, the compiler extends the lifetime of the reference to codewords to at least the same as cur_sequence (why: The compiler wants to ensure that the slice cur_sequence is always valid, but if you change codewords (say, clear it) then it's possible that cur_sequence is invalid. By keeping an immutable reference to codewords, then borrow rules will forbid modification of codewords when the slice is still alive). And unfortunately you save cur_sequence in lookup_table, thus keeping the reference to codewords alive all over the function, so you cannot mutably borrow codewords anymore.

The solution is to maintain the indexes of the slice by yourself: create a struct:

struct Range {
    start: usize,
    end: usize
}

impl Range {
    fn new(start: usize, end: usize) -> Self {
        Range{ start, end}
    }
}

then use it instead of the slices:

let cur_range = Range::new(
    codewords.len() - 1 - height as usize,
    codewords.len() - 1
);
lookup_table.insert(cur_node.val, cur_range);

In this way, the responsibility to keep the ranges valid is yours.

complete code:

use std::collections::HashMap;

// ignore everything being public, I use getters in the real code
pub struct HufTreeNode {
    pub val: u8,
    pub freq: usize,
    pub left: i16,
    pub right: i16,
}

struct Range {
    start: usize,
    end: usize
}

impl Range {
    fn new(start: usize, end: usize) -> Self {
        Range{ start, end}
    }
}

fn traverse_tree(
    cur_index: usize,
    height: i16,
    codewords: &mut Vec<bool>,
    lookup_table: &mut HashMap<u8, Range>,
    huffman_tree: &[HufTreeNode],
) {
    let cur_node = &huffman_tree[cur_index];

    // if the left child is -1, we reached a leaf
    if cur_node.left == -1 {
        // the last `height` bits in codewords
        // let cur_sequence = &codewords[(codewords.len() - 1 - height as usize)..];
        let cur_range = Range::new(
            codewords.len() - 1 - height as usize,
            codewords.len() - 1
        );
        lookup_table.insert(cur_node.val, cur_range);
        return;
    }

    // save the current sequence so we can traverse to the right afterwards
    let mut cur_sequence = codewords[(codewords.len() - 1 - height as usize)..].to_vec();
    codewords.push(false);
    traverse_tree(
        cur_node.left as usize,
        height + 1,
        codewords, // mutable borrow - argument requires that `*codewords` is borrowed for `'a`
        lookup_table,
        huffman_tree,
    );

    // append the previously saved current sequence
    codewords.append(&mut cur_sequence); // second mutable borrow occurs here
    codewords.push(true); // third mutable borrow occurs here
    traverse_tree(
        cur_node.right as usize,
        height + 1,
        codewords, // fourth mutable borrow occurs here
        lookup_table,
        huffman_tree,
    );
}

fn main() {
    // ...
}
user_93079460
Related