1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
// Copyright 2016 Joe Neeman.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
use dfa::{Dfa, RetTrait};
use nfa::{Nfa, NoLooks, StateIdx};
use num::traits::PrimInt;
use std::collections::HashSet;
use std::fmt::Debug;
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum DfsInstruction {
Continue,
#[allow(dead_code)]
TurnBack,
Stop,
}
pub trait Graph {
fn num_states(&self) -> usize;
fn neighbors<'a>(&'a self, i: StateIdx) -> Box<Iterator<Item=StateIdx> + 'a>;
/// Does a depth-first search of this graph.
///
/// Every time the search visits a new state, `visit` will be called. Every time the search
/// detects a loop, `cycle` will be called. These return value of these callbacks tell the
/// search how to proceed:
/// - on `Continue`, the search will proceed normally
/// - on `TurnBack`, the search will stop searching the current branch
/// - on `Stop`, the search will terminate early.
fn dfs<Inits, Visit, Cycle>(&self, init: Inits, mut visit: Visit, mut cycle: Cycle)
where
Visit: FnMut(&[StateIdx]) -> DfsInstruction,
Cycle: FnMut(&[StateIdx]) -> DfsInstruction,
Inits: Iterator<Item=StateIdx>,
{
// Pairs of (state, children_left_to_explore).
let mut stack: Vec<StateIdx> = Vec::with_capacity(self.num_states());
let mut remaining_children_stack: Vec<Box<Iterator<Item=StateIdx>>>
= Vec::with_capacity(self.num_states());
let mut visiting: Vec<bool> = vec![false; self.num_states()];
let mut done: Vec<bool> = vec![false; self.num_states()];
// For nodes that we are currently visiting, this is their position on the stack.
let mut stack_pos: Vec<usize> = vec![0; self.num_states()];
let start_states: Vec<StateIdx> = init.collect();
for &start_idx in &start_states {
if !done[start_idx] {
match visit(&[start_idx][..]) {
DfsInstruction::Continue => {},
DfsInstruction::TurnBack => {
done[start_idx] = true;
continue;
},
DfsInstruction::Stop => { return; },
}
visiting[start_idx] = true;
stack.push(start_idx);
remaining_children_stack.push(self.neighbors(start_idx));
stack_pos[start_idx] = 0;
while !stack.is_empty() {
// We keep stack and remaining_children_stack synchronized.
debug_assert!(!remaining_children_stack.is_empty());
let cur = *stack.last().unwrap();
let next_child = remaining_children_stack.last_mut().unwrap().next();
if let Some(child) = next_child {
if visiting[child] {
// We found a cycle: report it (and maybe terminate early).
// Since we turn back on finding a cycle anyway, we treat Continue
// and TurnBack the same (i.e. we don't need to handle either one
// explicitly).
if cycle(&stack[stack_pos[child]..]) == DfsInstruction::Stop {
return;
}
} else if !done[child] {
// This is a new state: report it and push it onto the stack.
stack.push(child);
match visit(&stack[stack_pos[child]..]) {
DfsInstruction::Stop => { return; },
DfsInstruction::TurnBack => {
stack.pop();
done[child] = true;
},
DfsInstruction::Continue => {
remaining_children_stack.push(self.neighbors(child));
visiting[child] = true;
stack_pos[child] = stack.len() - 1;
},
}
}
continue;
}
// If we got this far, the current node is out of children. Pop it from the
// stack.
visiting[cur] = false;
done[cur] = true;
stack.pop();
remaining_children_stack.pop();
}
}
}
}
/// The same as `dfs`, but runs on a graph with cuts in it.
///
/// Instead of running on the full graph, runs on the graph where pairs in `cuts` are
/// disconnected.
fn dfs_with_cut<Inits, Cuts, Visit, Cycle>(
&self,
init: Inits,
cuts: &HashSet<(StateIdx, StateIdx)>,
mut visit: Visit,
mut cycle: Cycle)
where
Visit: FnMut(&[StateIdx]) -> DfsInstruction,
Cycle: FnMut(&[StateIdx]) -> DfsInstruction,
Inits: Iterator<Item=StateIdx>,
{
let should_cut = |s: &[StateIdx]| {
let len = s.len();
len >= 2 && cuts.contains(&(s[len-2], s[len-1]))
};
let my_visit = |s: &[StateIdx]|
if should_cut(s) { DfsInstruction::TurnBack } else { visit(s) };
let my_cycle = |s: &[StateIdx]|
if should_cut(s) { DfsInstruction::TurnBack } else { cycle(s) };
self.dfs(init, my_visit, my_cycle);
}
/// Returns a list of states, visited in depth-first order.
fn dfs_order<I: Iterator<Item=StateIdx>>(&self, init: I) -> Vec<StateIdx> {
use self::DfsInstruction::*;
let mut ret: Vec<StateIdx> = Vec::new();
// The unwrap is ok because dfa guarantees never to pass an empty slice.
self.dfs(init, |st| { ret.push(*st.last().unwrap()); Continue }, |_| Continue);
ret
}
/// Checks whether this graph has any cycles.
#[allow(unused)]
fn has_cycles(&self) -> bool {
use self::DfsInstruction::*;
let mut found = false;
self.dfs(0..self.num_states(), |_| Continue, |_| { found = true; Stop });
found
}
}
impl<T: RetTrait> Graph for Dfa<T> {
fn num_states(&self) -> usize {
Dfa::num_states(self)
}
fn neighbors<'a>(&'a self, i: StateIdx) -> Box<Iterator<Item=StateIdx> + 'a> {
Box::new(self.transitions(i).ranges_values().map(|x| x.1))
}
}
impl<Tok: Debug + PrimInt> Graph for Nfa<Tok, NoLooks> {
fn num_states(&self) -> usize {
Nfa::num_states(self)
}
fn neighbors<'a>(&'a self, i: usize) -> Box<Iterator<Item=usize> + 'a> {
Box::new(self.consuming(i).ranges_values().map(|x| x.1))
}
}
#[cfg(test)]
mod tests {
use dfa::tests::make_dfa;
use graph::Graph;
#[test]
fn cycles() {
macro_rules! cyc {
($re:expr, $res:expr) => {
{
let dfa = make_dfa($re).unwrap();
println!("{:?}", dfa);
assert_eq!(dfa.has_cycles(), $res);
}
};
}
cyc!("abcde", false);
cyc!("ab*d", true);
cyc!("ab*", true);
cyc!("ab*?", false);
cyc!("ab+", true);
cyc!("ab+?", false);
cyc!("(ab*?|cde)", false);
cyc!("(ab*?|cde)f", true);
cyc!("(abc)*?", false);
cyc!("(abc)*?def", true);
}
}