FST walker for forward/backward transitions

[joshtriplett]

For some uses, it would make sense to statefully walk through the FST, stepping forward with input bytes, but also popping off the last input and returning to the previous state.

I'd love to have something with roughly the following interface:

impl FstWalker {
    fn new(fst: &Fst) -> FstWalker;
    fn push(&mut self, input: u8) -> bool; // false if no transition
    fn node(&self) -> Node;
    fn pop(&mut self);
    fn value(&self) -> &[u8];
}

The FstWalker would internally maintain the byte-string pushed so far, which it may want to reserve_exact on based on the longest key in the Fst to avoid needing to grow it. value() would return the current byte-string.

The node() function would allow calling is_final() and/or final_output().

I can build this easily enough based on the interfaces already provided by raw::Fst, but I'm wondering if this looks like something useful enough to provide in the fst crate itself. If I wrote a patch for this, would you be interested?

(I also don't know if this would beat the performance of just recursing on the fst, but I plan to test that.)

[BurntSushi]

@joshtriplett I'm having a hard time groking this request. Would it be possible to provide a more concrete example that uses this?

If doing this is possible outside of the crate, then I'd be tempted to play it conservative and not increase the API surface area more than it is. But if it provides a powerful convenience for something that's common, then I could definitely be swayed.

[ibrierley]

Just out of interest, I'm tagging this onto this question, but it may not be appropriate (newish to Rust and fst, but exploring options for a project), so apologies if so, but it came up when I was searching.

One thing I wanted to do was link the fst to a separate results set from it's value. So lets say I have a key of london_ec1_4qa I wanted to retrieve a value. With this value, check elsewhere for some criteria. If that criteria isn't met, step back to london_ec1 for example, then back to london.

I may not be looking at the right thing for my needs, so apologies for wasting time if not!