Skip to content

Instantly share code, notes, and snippets.

@Blei

Blei/errout

Created September 17, 2012 12:41
Show Gist options
  • Save Blei/3737071 to your computer and use it in GitHub Desktop.
Save Blei/3737071 to your computer and use it in GitHub Desktop.
Download ZIP
Failing compilation
Raw
errout
levenshtein-automata.rs:48:16: 48:34 error: multiple applicable methods in scope
levenshtein-automata.rs:48 for s.transitions.each() |c, t| {
^~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:48:16: 48:34 error: multiple applicable methods in scope
levenshtein-automata.rs:48 for s.transitions.each() |c, t| {
^~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:80:16: 80:34 error: multiple applicable methods in scope
levenshtein-automata.rs:80 for s.transitions.each() |c, t| {
^~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:80:16: 80:34 error: multiple applicable methods in scope
levenshtein-automata.rs:80 for s.transitions.each() |c, t| {
^~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:108:56: 108:63 error: multiple applicable methods in scope
levenshtein-automata.rs:108 @NState {id: id, accepting: accepting, transitions: HashMap(),
^~~~~~~
levenshtein-automata.rs:108:56: 108:63 error: multiple applicable methods in scope
levenshtein-automata.rs:108 @NState {id: id, accepting: accepting, transitions: HashMap(),
^~~~~~~
levenshtein-automata.rs:139:4: 139:27 error: multiple applicable methods in scope
levenshtein-automata.rs:139 from.transitions.insert(c, to);
^~~~~~~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:139:4: 139:27 error: multiple applicable methods in scope
levenshtein-automata.rs:139 from.transitions.insert(c, to);
^~~~~~~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:169:52: 169:59 error: multiple applicable methods in scope
levenshtein-automata.rs:169 @DState {id: id, accepting: false, transitions: HashMap(),
^~~~~~~
levenshtein-automata.rs:169:52: 169:59 error: multiple applicable methods in scope
levenshtein-automata.rs:169 @DState {id: id, accepting: false, transitions: HashMap(),
^~~~~~~
levenshtein-automata.rs:200:4: 200:27 error: multiple applicable methods in scope
levenshtein-automata.rs:200 from.transitions.insert(c, to);
^~~~~~~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:200:4: 200:27 error: multiple applicable methods in scope
levenshtein-automata.rs:200 from.transitions.insert(c, to);
^~~~~~~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:271:21: 271:28 error: multiple applicable methods in scope
levenshtein-automata.rs:271 let symbol_set = HashMap();
^~~~~~~
levenshtein-automata.rs:271:21: 271:28 error: multiple applicable methods in scope
levenshtein-automata.rs:271 let symbol_set = HashMap();
^~~~~~~
levenshtein-automata.rs:275:12: 275:29 error: multiple applicable methods in scope
levenshtein-automata.rs:275 symbol_set.insert(c, ());
^~~~~~~~~~~~~~~~~
levenshtein-automata.rs:275:12: 275:29 error: multiple applicable methods in scope
levenshtein-automata.rs:275 symbol_set.insert(c, ());
^~~~~~~~~~~~~~~~~
levenshtein-automata.rs:274:12: 274:34 error: multiple applicable methods in scope
levenshtein-automata.rs:274 for s.transitions.each_key() |c| {
^~~~~~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:274:12: 274:34 error: multiple applicable methods in scope
levenshtein-automata.rs:274 for s.transitions.each_key() |c| {
^~~~~~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:283:18: 283:36 error: multiple applicable methods in scope
levenshtein-automata.rs:283 match s.transitions.find(c) {
^~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:283:18: 283:36 error: multiple applicable methods in scope
levenshtein-automata.rs:283 match s.transitions.find(c) {
^~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:279:8: 279:27 error: multiple applicable methods in scope
levenshtein-automata.rs:279 for symbol_set.each_key() |c| {
^~~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:279:8: 279:27 error: multiple applicable methods in scope
levenshtein-automata.rs:279 for symbol_set.each_key() |c| {
^~~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:310:20: 310:38 error: multiple applicable methods in scope
levenshtein-automata.rs:310 for s.transitions.each() |c, t2| {
^~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:310:20: 310:38 error: multiple applicable methods in scope
levenshtein-automata.rs:310 for s.transitions.each() |c, t2| {
^~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:316:20: 316:40 error: multiple applicable methods in scope
levenshtein-automata.rs:316 s.transitions.remove(c);
^~~~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:316:20: 316:40 error: multiple applicable methods in scope
levenshtein-automata.rs:316 s.transitions.remove(c);
^~~~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:353:14: 353:36 error: multiple applicable methods in scope
levenshtein-automata.rs:353 match state.transitions.find(c) {
^~~~~~~~~~~~~~~~~~~~~~
levenshtein-automata.rs:353:14: 353:36 error: multiple applicable methods in scope
levenshtein-automata.rs:353 match state.transitions.find(c) {
^~~~~~~~~~~~~~~~~~~~~~
error: aborting due to 28 previous errors
Raw
levenshtein-automata.rs
extern mod std;
use dvec::DVec;
use vec::{push_all};
use option::{Option, Some, None};
use path::{Path};
use str::{slice};
use int::{range};
use cmp::{Eq, Ord};
use hash::Hash;
use to_bytes::{IterBytes, Cb, iter_bytes_2};
use io::{WriterUtil, file_writer, Create, Truncate};
use std::map::{HashMap, Set, vec_from_set};
use std::sort::{quick_sort3};
trait Graphvizable {
fn to_dot(w: WriterUtil);
}
fn write_transition(from: &str, to: &str, c: char, w: WriterUtil) {
w.write_str("\"");
w.write_str(from);
w.write_str("\" -> \"");
w.write_str(to);
w.write_str("\" [label = \"");
w.write_char(c);
w.write_str("\"];\n");
}
impl <T: Eq IterBytes Hash Copy Const ToStr> NFA<T>: Graphvizable {
fn to_dot(w: WriterUtil) {
w.write_str("digraph {\n");
for self.states.each_value() |s| {
let id = s.id.to_str();
w.write_str("\"");
w.write_str(id);
w.write_str("\"");
if (s.id == self.start_state.id) {
w.write_str(" [fontcolor = red]");
}
if (s.accepting) {
w.write_str(" [style = filled, fillcolor = green]");
}
w.write_str(";\n");
for s.transitions.each() |c, t| {
let id2 = t.id.to_str();
write_transition(id, id2, c, w);
}
for s.any_transitions.each_value() |t| {
let id2 = t.id.to_str();
write_transition(id, id2, '*', w);
}
for s.epsilon_transitions.each_value() |t| {
let id2 = t.id.to_str();
write_transition(id, id2, 'ε', w);
}
}
w.write_str("}");
}
}
impl <T: Eq IterBytes Hash Copy Const ToStr> DFA<T>: Graphvizable {
fn to_dot(w: WriterUtil) {
w.write_str("digraph {\n");
for self.states.each_value() |s| {
let id = s.id.to_str();
w.write_str("\"");
w.write_str(id);
w.write_str("\"");
if (s.id == self.start_state.id) {
w.write_str(" [fontcolor = red]");
}
if (s.accepting) {
w.write_str(" [style = filled, fillcolor = green]");
}
w.write_str(";\n");
for s.transitions.each() |c, t| {
let id2 = t.id.to_str();
write_transition(id, id2, c, w);
}
match s.default_transition {
None => {},
Some(copy t) => write_transition(id, t.id.to_str(), '*', w)
};
}
w.write_str("}");
}
}
impl char: IterBytes {
pure fn iter_bytes(lsb0: bool, f: Cb) {
(self as i32).iter_bytes(lsb0, f);
}
}
struct NState<T> {
id: T,
mut accepting: bool,
transitions: HashMap<char, @NState<T>>,
any_transitions: HashMap<T, @NState<T>>,
epsilon_transitions: HashMap<T, @NState<T>>
}
fn nstate<T: Eq IterBytes Hash Copy Const>(id: T, accepting: bool) -> @NState<T> {
@NState {id: id, accepting: accepting, transitions: HashMap(),
any_transitions: HashMap(), epsilon_transitions: HashMap()}
}
struct NFA<T> {
start_state: @NState<T>,
states: HashMap<T, @NState<T>>
}
fn nfa_get_or_add_state<T: Eq IterBytes Hash Copy Const>(nfa: @NFA<T>, id: T) -> @NState<T> {
match nfa.states.find(id) {
None => {
let state = nstate(id, false);
nfa.states.insert(id, state);
state
},
Some(state) => state
}
}
fn nfa<T: Eq IterBytes Hash Copy Const>(start_id: T) -> @NFA<T> {
let start_state = nstate(start_id, false);
let nfa = @NFA {start_state: start_state, states: HashMap()};
nfa.states.insert(start_id, start_state);
nfa
}
fn nfa_add_transition<T: Eq IterBytes Hash Copy Const>(
nfa: @NFA<T>, from_id: T, to_id: T, c: char) {
let from = nfa_get_or_add_state(nfa, from_id);
let to = nfa_get_or_add_state(nfa, to_id);
from.transitions.insert(c, to);
}
fn nfa_add_any_transition<T: Eq IterBytes Hash Copy Const>(
nfa: @NFA<T>, from_id: T, to_id: T) {
let from = nfa_get_or_add_state(nfa, from_id);
let to = nfa_get_or_add_state(nfa, to_id);
from.any_transitions.insert(to_id, to);
}
fn nfa_add_epsilon_transition<T: Eq IterBytes Hash Copy Const>(
nfa: @NFA<T>, from_id: T, to_id: T) {
let from = nfa_get_or_add_state(nfa, from_id);
let to = nfa_get_or_add_state(nfa, to_id);
from.epsilon_transitions.insert(to_id, to);
}
fn nfa_set_accepting<T: Eq IterBytes Hash Copy Const>(nfa: @NFA<T>, id: T, accepting: bool) {
let state = nfa_get_or_add_state(nfa, id);
state.accepting = accepting;
}
struct DState<T> {
id: @~[T],
mut accepting: bool,
transitions: HashMap<char, @DState<T>>,
mut default_transition: Option<@DState<T>>
}
fn dstate<T: Eq IterBytes Hash Copy Const>(id: @~[T]) -> @DState<T> {
@DState {id: id, accepting: false, transitions: HashMap(),
default_transition: None}
}
struct DFA<T> {
start_state: @DState<T>,
states: HashMap<@~[T], @DState<T>>
}
fn dfa_get_or_add_state<T: Eq IterBytes Hash Copy Const>(dfa: @DFA<T>, id: @~[T]) -> @DState<T> {
match dfa.states.find(id) {
Some(state) => state,
None => {
let state = dstate(id);
dfa.states.insert(id, state);
state
}
}
}
fn dfa<T: Eq IterBytes Hash Copy Const>(start_id: @~[T]) -> @DFA<T> {
let start_state = dstate(start_id);
let dfa = @DFA {start_state: start_state, states: HashMap()};
dfa.states.insert(start_id, start_state);
dfa
}
fn dfa_add_transition<T: Eq IterBytes Hash Copy Const>(
dfa: @DFA<T>, from_id: @~[T], to_id: @~[T], c: char) {
let from = dfa_get_or_add_state(dfa, from_id);
let to = dfa_get_or_add_state(dfa, to_id);
from.transitions.insert(c, to);
}
fn dfa_set_default_transition<T: Eq IterBytes Hash Copy Const>(
dfa: @DFA<T>, from_id: @~[T], to_id: @~[T]) {
let from = dfa_get_or_add_state(dfa, from_id);
let to = dfa_get_or_add_state(dfa, to_id);
from.default_transition = Some(to);
}
fn dfa_set_accepting<T: Eq IterBytes Hash Copy Const>(
dfa: @DFA<T>, id: @~[T], accepting: bool) {
let state = dfa_get_or_add_state(dfa, id);
state.accepting = accepting;
}
fn follow_epsilon_transitions<T: Eq IterBytes Hash Copy Const>
(state: @NState<T>, set: &HashMap<T, @NState<T>>, accepting: &mut bool) {
let stack: DVec<@NState<T>> = DVec();
set.insert(state.id, state);
stack.push(state);
while (stack.len() > 0) {
let state2 = stack.pop();
if (state2.accepting) {
*accepting = true;
}
for state2.epsilon_transitions.each_value() |t| {
if (!set.contains_key(t.id)) {
set.insert(t.id, t);
stack.push(t);
}
}
}
}
fn get_ids<T: Eq IterBytes Hash Copy Const Ord>(map: &HashMap<T, @NState<T>>) -> @~[T] {
let mut v = ~[];
vec::reserve(v, map.size());
for map.each_key() |k| {
vec::push(v, k);
}
quick_sort3(v);
@v
}
fn process_state<T: Eq IterBytes Hash Copy Const Ord>(
from_states: @HashMap<T, @NState<T>>,
from_ids: @~[T],
seen: &Set<@~[T]>,
stack: &DVec<(@HashMap<T, @NState<T>>, @~[T])>,
dfa: @DFA<T>) {
let mut default_accepting = false;
let default_states = @HashMap();
for from_states.each_value() |s| {
for s.any_transitions.each_value() |t| {
follow_epsilon_transitions(t, default_states, &mut default_accepting);
}
}
let default_ids = get_ids(default_states);
dfa_set_default_transition(dfa, from_ids, default_ids);
if (!seen.contains_key(default_ids)) {
seen.insert(default_ids, ());
stack.push((default_states, default_ids));
dfa_set_accepting(dfa, default_ids, default_accepting);
}
let symbol_set = HashMap();
for from_states.each_value() |s| {
for s.transitions.each_key() |c| {
symbol_set.insert(c, ());
}
}
for symbol_set.each_key() |c| {
let mut accepting = false;
let states = @HashMap();
for from_states.each_value() |s| {
match s.transitions.find(c) {
Some(copy target) =>
follow_epsilon_transitions(target, states, &mut accepting),
None => {}
}
for s.any_transitions.each_value |t| {
follow_epsilon_transitions(t, states, &mut accepting);
}
}
let ids = get_ids(states);
dfa_add_transition(dfa, from_ids, ids, c);
if (!seen.contains_key(ids)) {
seen.insert(ids, ());
stack.push((states, ids));
dfa_set_accepting(dfa, ids, accepting);
}
}
}
fn post_process<T: Eq IterBytes Hash Copy Const>(dfa: @DFA<T>) {
// Remove concrete transitions that are covered by default transitions
for dfa.states.each_value() |s| {
match s.default_transition {
None => {},
Some(copy t) => {
let to_remove = DVec();
for s.transitions.each() |c, t2| {
if (t2.id == t.id) {
to_remove.push(c);
}
}
for to_remove.each() |c| {
s.transitions.remove(c);
}
}
}
}
}
fn powerset_construction<T: Eq IterBytes Hash Copy Const Ord>(nfa: @NFA<T>) -> @DFA<T> {
let start_state = nfa.start_state;
let map = @HashMap();
let mut accepting = false;
follow_epsilon_transitions(start_state, map, &mut accepting);
let ids = get_ids(map);
let dfa: @DFA<T> = dfa(ids);
dfa_set_accepting(dfa, ids, accepting);
let seen = HashMap();
seen.insert(ids, ());
let stack = DVec();
stack.push((map, ids));
while (stack.len() > 0) {
match stack.pop() {
(states, ids) => {
process_state(states, ids, &seen, &stack, dfa)
}
}
}
post_process(dfa);
dfa
}
fn dfa_run<T: Eq IterBytes Hash Copy Const Ord>(dfa: @DFA<T>, s: &str) -> bool {
let mut state = dfa.start_state;
for str::each_char(s) |c| {
match state.transitions.find(c) {
Some(copy t) => state = t,
None => state = option::get(state.default_transition)
}
}
state.accepting
}
impl <T: IterBytes, U: IterBytes> (T, U): IterBytes {
pure fn iter_bytes(lsb0: bool, f:Cb) {
match self {
(a, b) => iter_bytes_2(&a, &b, lsb0, f)
}
}
}
fn copy_prefix(s: ~str, l: uint) -> @~str {
let n = str::count_bytes(s, 0, l);
let prefix = do vec::from_fn(n) |i| { s[i] };
@str::from_bytes(prefix)
}
fn make_levenshtein_nfa(s: ~str, max_errors: int) -> @NFA<(@~str, int)> {
let nfa = nfa((@~"", 0));
for s.each_chari() |i, c| {
let prefix = copy_prefix(s, i);
let prefix2 = copy_prefix(s, i+1);
for range(0, max_errors + 1) |e| {
// Correct character
nfa_add_transition(nfa, (prefix, e), (prefix2, e), c);
if (e < max_errors) {
// Deletion
nfa_add_any_transition(nfa, (prefix, e), (prefix, e + 1));
// Insertion
nfa_add_epsilon_transition(nfa, (prefix, e), (prefix2, e + 1));
// Substitution
nfa_add_any_transition(nfa, (prefix, e), (prefix2, e + 1));
}
}
}
for range(0, max_errors + 1) |e| {
if (e < max_errors) {
nfa_add_any_transition(nfa, (@copy s, e), (@copy s, e + 1));
}
nfa_set_accepting(nfa, (@copy s, e), true);
}
nfa
}
fn dot_to_file<T: Graphvizable>(fa: @T, filename: &str) {
let path = Path(filename);
let file = result::get(file_writer(&path, ~[Truncate, Create]));
fa.to_dot(file as WriterUtil);
file.flush();
}
fn make_toy_nfa() -> @NFA<(int, int)> {
let nfa = nfa((0, 0));
nfa_add_any_transition(nfa, (0, 0), (0, 1));
nfa_add_transition(nfa, (0, 0), (1, 0), 'f');
nfa_add_transition(nfa, (0, 1), (1, 1), 'f');
nfa_add_any_transition(nfa, (0, 0), (1, 1));
nfa_add_epsilon_transition(nfa, (0, 0), (1, 1));
nfa_add_any_transition(nfa, (1, 0), (1, 1));
nfa_set_accepting(nfa, (0, 1), true);
nfa_set_accepting(nfa, (1, 1), true);
nfa
}
#[test]
fn print_nfa() {
let nfa = make_toy_nfa();
dot_to_file(nfa, "nfa1.dot");
}
#[test]
fn print_dfa() {
let nfa = make_toy_nfa();
let dfa = powerset_construction(nfa);
dot_to_file(dfa, "dfa1.dot");
}
#[test]
fn print_levenshtein_nfa() {
let nfa = make_levenshtein_nfa(~"food", 1);
dot_to_file(nfa, "nfa2.dot");
}
#[test]
fn print_levenshtein_dfa() {
let nfa = make_levenshtein_nfa(~"food", 1);
let dfa = powerset_construction(nfa);
dot_to_file(dfa, "dfa2.dot");
}
#[test]
fn acceptibility_test() {
let dfa = powerset_construction(make_levenshtein_nfa(~"food", 2));
assert(dfa_run(dfa, ~"food"));
assert(dfa_run(dfa, ~"ifoodo"));
assert(dfa_run(dfa, ~"fd"));
assert(dfa_run(dfa, ~"fod"));
assert(dfa_run(dfa, ~"ifod"));
assert(dfa_run(dfa, ~"ifiod"));
assert(dfa_run(dfa, ~"12od"));
assert(!dfa_run(dfa, ~""));
assert(!dfa_run(dfa, ~"food123"));
assert(!dfa_run(dfa, ~"f"));
assert(!dfa_run(dfa, ~"123d"));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment