use input::{Input, InputAt};
use params::Params;
use prog::{Program, InstPtr};
pub fn should_exec(num_insts: usize, text_len: usize) -> bool {
num_insts <= MAX_PROG_SIZE && text_len <= MAX_INPUT_SIZE
}
type Bits = u32;
const BIT_SIZE: usize = 32;
const MAX_PROG_SIZE: usize = 100;
const MAX_INPUT_SIZE: usize = 128 * (1 << 10);
#[derive(Debug)]
pub struct Backtrack<'a, 'r, 'p, 'c: 'p, 'm: 'p, I> {
prog: &'r Program,
input: I,
params: &'p mut Params<'c, 'm>,
m: &'a mut BacktrackCache,
}
#[derive(Debug)]
pub struct BacktrackCache {
jobs: Vec<Job>,
visited: Vec<Bits>,
}
impl BacktrackCache {
pub fn new() -> Self {
BacktrackCache { jobs: vec![], visited: vec![] }
}
}
#[derive(Clone, Copy, Debug)]
enum Job {
Inst { ip: InstPtr, at: InputAt },
SaveRestore { slot: usize, old_pos: Option<usize> },
}
impl<'a, 'r, 'p, 'c, 'm, I: Input> Backtrack<'a, 'r, 'p, 'c, 'm, I> {
pub fn exec(
prog: &'r Program,
cache: &mut BacktrackCache,
params: &'p mut Params<'c, 'm>,
input: I,
start: usize,
) -> bool {
let start = input.at(start);
let mut b = Backtrack {
prog: prog,
input: input,
params: params,
m: cache,
};
b.exec_(start)
}
fn clear(&mut self) {
self.m.jobs.clear();
let visited_len =
(self.prog.len() * (self.input.len() + 1) + BIT_SIZE - 1)
/
BIT_SIZE;
self.m.visited.truncate(visited_len);
for v in &mut self.m.visited {
*v = 0;
}
if visited_len > self.m.visited.len() {
let len = self.m.visited.len();
self.m.visited.reserve_exact(visited_len - len);
for _ in 0..(visited_len - len) {
self.m.visited.push(0);
}
}
}
fn exec_(&mut self, mut at: InputAt) -> bool {
self.clear();
if self.prog.is_anchored_start {
return if !at.is_start() {
false
} else {
self.backtrack(at)
};
}
loop {
if !self.prog.prefixes.is_empty() {
at = match self.input.prefix_at(&self.prog.prefixes, at) {
None => break,
Some(at) => at,
};
}
if self.backtrack(at) && self.prog.matches.len() == 1 {
return true;
}
if at.is_end() {
break;
}
at = self.input.at(at.next_pos());
}
self.params.is_match()
}
#[inline(always)]
fn backtrack(&mut self, start: InputAt) -> bool {
self.m.jobs.push(Job::Inst { ip: 0, at: start });
while let Some(job) = self.m.jobs.pop() {
match job {
Job::Inst { ip, at } => {
if self.step(ip, at) {
if self.prog.matches.len() == 1 {
return true;
}
}
}
Job::SaveRestore { slot, old_pos } => {
self.params.set_capture(slot, old_pos);
}
}
}
self.params.is_match()
}
fn step(&mut self, mut ip: InstPtr, mut at: InputAt) -> bool {
use prog::Inst::*;
loop {
match self.prog[ip] {
Match(slot) => {
self.params.set_match(slot);
return true;
}
Save(ref inst) => {
if let Some(&old_pos) = self.params.captures().get(inst.slot) {
self.m.jobs.push(Job::SaveRestore {
slot: inst.slot,
old_pos: old_pos,
});
self.params.set_capture(inst.slot, Some(at.pos()));
}
ip = inst.goto;
}
Split(ref inst) => {
self.m.jobs.push(Job::Inst { ip: inst.goto2, at: at });
ip = inst.goto1;
}
EmptyLook(ref inst) => {
let prev = self.input.previous_char(at);
let next = self.input.next_char(at);
if inst.matches(prev, next) {
ip = inst.goto;
} else {
return false;
}
}
Char(ref inst) => {
if inst.c == at.char() {
ip = inst.goto;
at = self.input.at(at.next_pos());
} else {
return false;
}
}
Ranges(ref inst) => {
if inst.matches(at.char()) {
ip = inst.goto;
at = self.input.at(at.next_pos());
} else {
return false;
}
}
Bytes(ref inst) => {
if let Some(b) = at.byte() {
if inst.matches(b) {
ip = inst.goto;
at = self.input.at(at.next_pos());
continue;
}
}
return false;
}
}
if self.has_visited(ip, at) {
return false;
}
}
}
fn has_visited(&mut self, ip: InstPtr, at: InputAt) -> bool {
let k = ip * (self.input.len() + 1) + at.pos();
let k1 = k / BIT_SIZE;
let k2 = usize_to_u32(1 << (k & (BIT_SIZE - 1)));
if self.m.visited[k1] & k2 == 0 {
self.m.visited[k1] |= k2;
false
} else {
true
}
}
}
fn usize_to_u32(n: usize) -> u32 {
if (n as u64) > (::std::u32::MAX as u64) {
panic!("BUG: {} is too big to fit into u32", n)
}
n as u32
}