Another Lifetime issue: Conflicting lifetime with recursive function returning an iterator

Hello everyone.

I'm currently trying (and struggling) to write a function which acts on an iterator, and returns another iterator.
The types I'm dealing with are complex, since it's this kind of enum, where one of the possible values contains a vector of the enum type (see below) Playground here

#[derive(Clone, Debug, Eq, PartialEq)]
enum Gate {
    Simple(u64, u64, u64),
    Function(Vec<u64>, Vec<u64>, Vec<Gate>),
}

Then I have a function which iterates over a slice of Gates, and returns an iterator Iterator<Item=Gate> where each value is a modified version of the gate given as parameter.

fn translate_gates<'s>(gates: &'s [Gate], output_input: &'s [u64], translated_gates: &'s mut usize) -> impl Iterator<Item = Gate> + 's {
    gates
        .iter()
        .map(move |gate| translate_gate(gate, output_input, translated_gates))
}

fn translate_gate(gate: &Gate, output_input: &[u64], translated_gates: &mut usize) -> Gate {
    match gate {
        Simple(out, in1, in2) => {
            *translated_gates += 1;
            Simple(output_input[*out as usize], output_input[*in1 as usize], output_input[*in2 as usize])
        }
        Function(outs, ins, gates) => {
            *translated_gates += 1;
            let translated_outputs = outs.iter().map(|&val| output_input[val as usize]).collect();
            let translated_inputs = ins.iter().map(|&val| output_input[val as usize]).collect();
            Function(translated_outputs, translated_inputs, gates.clone())
        }
    }
}

These functions work as well.

But then I would like to write a function that flatten a list of Gates (let's call it a circuit), ie replacing all occurrences of Gate::Function by their somewhat translated sub-circuit (it may be called recursively). And I want a Iterator over the flattened subcircuit, since it might be huge.

The flattening function is recursive, and may return a std::iter::Once if a Simple gate is encountered, or a Map in the other case.
I tried many things using Box / Cloning the gates / additional lifetime specifiers... but I am still failing to make it work.

I know Rust lifetimes is maybe the most discussed topic, but still I was not able to find any answer...

Here is my last attempt:

fn flatten_gates<'a>(
    // gates: impl Iterator<Item=&'a Gate> + 'a,
    gates: &'a [Gate],
    _not_used: &'a HashMap<String, u64>,
    translated: &'a mut usize
) -> impl Iterator<Item=Gate> + 'a {
    gates
        .iter()
        .flat_map(move |gate| -> Box<dyn Iterator<Item=Gate> + 'a> {
            flatten(gate, _not_used, translated)
        })
}

fn flatten<'a>(
    gate: &'a Gate,
    _not_used: &'a HashMap<String, u64>,
    translated: &'a mut usize
) -> Box<dyn Iterator<Item=Gate> + 'a> {
    match gate {
        Simple(..) => Box::new(std::iter::once(gate.clone())),
        Function(outs, ins, gates) => {
            let output_inputs = [outs.to_vec(), ins.to_vec()].concat();
            Box::new(
                translate_gates(gates, &output_inputs, translated)
                    .flat_map(|inner_gate| flatten(&inner_gate, _not_used, translated))
            )
        }
    }
}

Of course this is an overly simplified example compared to my use-case, but I tried to extract only the relevant parts relative to my issue.

Thanks for your help.

That's kind of a red herring; user-defined types (enums and structs at least) aren't awarded extra capabilities or special restrictions compared to built-in types when it comes to lifetimes. If you have an enum containing a Vec, you have to uphold the same rules as if you had a Vec. (And you have to comply with the lifetime rules for each field/varian at the same time.)

Beware the signature of that function. Having the translated_gates, a mutable reference, share its lifetime with the rest of the immutable input references will likely cause headaches down the line.

Boxing doesn't really exempt you from any lifetime requirements except in the case when you use it to give ownership semantics to an unsized type instead of passing it around by reference.

Thank you, that is helpful.


Now for the actual problem: your function declares that all lifetimes come from the outside, i.e. they outlive the function call, and they can be specified by the caller. But then you call the functions with references to locally-owned variables. That's not going to work: those lifetimes are necessarily shorter than the lifetime of the outermost function call, and definitely not chosen by the top-level caller. In addition, the invariance of the mutable reference complicates everything even further, because lifetimes can't anymore shrink freely (which is sometimes useful).

All in all, you'd be much better off by:

  • working with owned rather than borrowed values and iterators; and
  • returning the number of translated gates instead of writing it through a mutable reference.

Accordingly, this compiles and gives you an iterator over pairs of (Gate, usize). By summing the returned usizes, I believe, you should get the same result as the final value of *translated would have been with your approach (but it's best to try it out because I didn't).

2 Likes

Thanks a lot @H2CO3 for answering one of my threads again :wink:

The drawback of using a simplified example is that sometimes, one can think that some things can be simplified :smiley: . In my use case, translated_gates: &'s mut usize is not modified by simply incrementing it, and the modification applied to it depends on the type of Gate.
Especially, when I write something like output_input[*out as usize], it will crash if out >= output_input.len(). In my real case, output_input is passed as a mutable vector, that is expanded upto out with values starting translated_gates.
May be better explained with the code:

pub fn translate_gates<'s>(
    subcircuit: &'s[Gate],
    output_input_wires: &'s mut Vec<WireId>,
    free_temporary_wire: &'s mut WireId
) -> impl Iterator<Item = Gate> + 's {
    subcircuit
        .iter()
        .map(move |gate| translate_gate(gate, output_input_wires, free_temporary_wire))
}
/// This macro returns the translated value of a wire into the outer namespace.
///  If the given wire id is out of bound, then it's considered as a temporary wire.
/// and the $translation_vector is expanded accordingly
macro_rules! translate_or_temp {
        ($translation_vector:ident, $wire_name:expr, $free_temp_wire:expr) => {{
            while $translation_vector.len() <= $wire_name as usize {
                $translation_vector.push($free_temp_wire);
                $free_temp_wire += 1;
            }
            $translation_vector[$wire_name as usize]
        }};
    }

/// This function translate a single Gate from the inner workspace into the outer workspace
/// using the output/input vector. If temporary wires are needed, it will pick one new one, and will
/// increase the 'free_temporary_wire' reference.
fn translate_gate(gate: &Gate, output_input_wires: &mut Vec<WireId>, free_temporary_wire: &mut WireId) -> Gate {
    macro_rules! translate {
        ($wire_name:expr) => {
            translate_or_temp!(output_input_wires, $wire_name, *free_temporary_wire)
        };
    }
    match gate {
        Simple(out, in1, in2) => Simple(translate(*out), translate(*in1), translate(*in2)),
        // ... //
    }
}

I'm not sure whether returning its new value in the Iterator is a good option, because I need this new value for the next iteration, and I cannot know in advance by how much it will be incremented. Do you think that something using the Iterator::fold() function could help? I'm not even sure how to use it properly in this case...

Moreover, in your code example, the vector parameter is passed by value, but in my use-case it cannot be moved, and I cannot clone/copy them, because they may be really huge. This is mainly why I tried myself with Iterators. And ideally I would like to replace the gates: &'s [Gate] in translate_gates by something like gates: impl Iterator<Item=Gate> or gates: impl Iterator<Item=&Gate>. BTW, which would be better?

Finally, you removed the _not_used: &'a HashMap<String, u64>,. Ok, it is clearly unused in the simplified example, unfortunately, I need it in my use-case, and it may add another difficulty in handling the lifetimes

Thanks,

One way around this particular issue is to take an argument of type &’a Cell<usize> instead of &’a mut usizeβ€” You can use Cell::from_mut to produce an &Cell from the &mut you already have.

(I haven’t analyzed the rest of the code to tell what else would need to change)

1 Like

impl Iterator<Item=Gate>
Do you want a return an entity ref in a function call?

do not recommend this behavior

I think you would better create a vec first, and pass it as &mut Vec, then return an impl Iterator<Item=&Gate>

for example

let GAT: Vec<Gate> = vec![];
translate_gates(&gates, &output_inputs, &mut translated_gates, &mut Gate);

you just need to push a new gate into  GAT. 

if you want to return a ref, just believe that you need to allocate it first

I don't think so. Capturing another immutable reference of the same lifetime shouldn't cause any issues.

At some point, you will need to clone something somewhere, because you produce Gates by value (that's the only thing you can do if you want to make new Gates), but then you can't insist that in the recursive calls of flatten(), when those Gates are passed by reference, they have the same 's lifetime that the caller choses. So I don't think you can make a zero-copy version of this function. The same goes for collecting into a local Vec and passing that by reference.

So keeping that in mind, and following @2e71828 's advice about Cell, this compiles and has less cloning than the previous example.

2 Likes

Hello all,

Indeed, the Cell trick does the job. Thanks for this useful thing!