Nondeterministic automaton thing. Type-checks only with the commented-out ascription.

nfa.rs

enum pc = u32;

struct state<S: copy> {
    let state: S;
    let pc: pc;
    let idx: uint;
}

trait success<S: copy, R> {
    fn succeed(state: &S) -> R;
}

trait action<S: copy> {
    fn act(state: &mut S, pc: pc, idx: uint) -> pc;
}

trait atom<S: copy> {
    fn consume(state: &S, l: lexbuf) -> option<uint>;
}

enum insn<S: copy, R, Su: copy success<S,R>, Ac: action<S>, At: atom<S>> 
{
    success(Su),
    action(Ac),
    atom(At),
    split(pc, pc),
    jmp(pc)
}

type prog<S: copy, R, Su: copy success<S,R>, Ac: action<S>, At: atom<S>> 
    = ~[insn<S,R,Su,Ac,At>];

enum lexbuf = ~[u8];

enum outcome<S: copy, R> {
    succeeded(fn(&S) -> R),
    proceeded,
    failed,
    divided(pc)
}

enum mode {
    first,
    longest,
    shortest
}

fn run_depth<S: copy, R, Su:copy success<S,R>, Ac:action<S>, At:atom<S>>
    (lexbuf: lexbuf, prog: prog<S,R,Su,Ac,At>, s0: S, mode: mode) 
    -> option<R> {
    let mut threads = ~[];
    let mut here = state { state: s0, pc: pc(0), idx: 0 };
    let mut best /* : option<(state<S>, Su)> */ = none;
    loop {
        let mut removeme = false;
        let insn = &prog[*here.pc];
        here.pc = pc(*here.pc + 1);
        match *insn {
          jmp(npc) => here.pc = npc,
          action(ac) => {
            here.pc = ac.act(&mut here.state, here.pc, here.idx)
          }
          split(npc0, npc1) => {
            vec::push(threads, state { pc: npc1 with here });
            here.pc = npc0;
          }
          atom(at) => match at.consume(&here.state, lexbuf) {
            some(skip) => here.idx += skip,
            none => removeme = true
          },
          success(su) => {
            match mode {
              first => return some(su.succeed(&here.state)),
              longest => match best {
                none =>
                    best = some((here, su)),
                some((copy there, _)) if here.idx > there.idx =>
                    best = some((here, su)),
                _ => { }
              },
              shortest => match best {
                none => 
                    best = some((here, su)),
                some((copy there, _)) if here.idx < there.idx =>
                    best = some((here, su)),
                _ => { }
              }
            }
            removeme = true;
          }
        }
        if removeme {
            if threads.len() == 0 {
                break;
            } else {
                here = vec::pop(threads);
            }
        }
    }
    do best.map |hs| { let (here,s) = hs; s.succeed(&here.state) }
}