Changeset - 95db38ce6846
Parent rev.
Child rev.
[Not reviewed]
default
0 1 0
Laman - 10 months ago 2024-06-24 11:55:22

refactoring: changed the states representation from usize and u64 to i32
1 file changed with 40 insertions and 38 deletions:
src/regexp.rs
40
38
0 comments (0 inline, 0 general)
src/regexp.rs
➞
Show inline comments
 
@@ -4,26 +4,27 @@ mod token;
 
pub use token::ParsingError;
 
use token::parse;
 

			




	
	
	
		
 
const START: usize = usize::MAX;

			




	
	
	
		
 
const FAIL: usize = START-1;

			




	
	
	
		
 
const START: i32 = -1;

			




	
	
	
		
 
const FAIL: i32 = -2;

			




	
	
	
		
 

			




	
	
	
		
 
fn encode_set(set: &HashSet<usize>) -> u64 {

			




	
	
	
		
 
fn encode_set(set: &HashSet<i32>) -> i32 {

			




	
	
	
		
 
	let mut res = 0;

			




	
	
	
		
 
	for x in set.iter() {

			




	
	
	
		
 
		assert!(*x >= 0);

			




	
	
	
		
 
		res ^= 1<<x;

			




	
	
	
		
 
	}

			




	
	
	
		
 
	return res;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
fn decode_set(x: u64) ->HashSet<usize> {

			




	
	
	
		
 
	if x == START as u64 {return HashSet::from([START]);}

			




	
	
	
		
 
fn decode_set(x: i32) -> HashSet<i32> {

			




	
	
	
		
 
	if x == START {return HashSet::from([START]);}

			




	
	
	
		
 

			




	
	
	
		
 
	let mut x = x;

			




	
	
	
		
 
	let mut res: HashSet<usize> = HashSet::new();

			




	
	
	
		
 
	let mut res: HashSet<i32> = HashSet::new();

			




	
	
	
		
 
	

			




	
	
	
		
 
	while x > 0 {

			




	
	
	
		
 
		let y = x.trailing_zeros();

			




	
	
	
		
 
		res.insert(y as usize);

			




	
	
	
		
 
		res.insert(y as i32);

			




	
	
	
		
 
		x ^= 1 << y;

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
		
 
@@ -32,35 +33,35 @@ fn decode_set(x: u64) ->HashSet<usize> {

			




	
	
	
		
 

			




	
	
	
		
 
#[derive(Debug)]

			




	
	
	
		
 
pub struct Regexp {

			




	
	
	
		
 
	rules: HashMap<(usize, char), HashSet<usize>>,

			




	
	
	
		
 
	end_states: HashSet<usize>

			




	
	
	
		
 
	rules: HashMap<(i32, char), HashSet<i32>>,

			




	
	
	
		
 
	end_states: HashSet<i32>

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
impl Regexp {

			




	
	
	
		
 
	pub fn new(pattern: &String) -> Result<Regexp, ParsingError> {

			




	
	
	
		
 
		let r = parse(pattern, 0)?;

			




	
	
	
		
 
		let pattern_chars = Vec::from_iter(pattern.chars());

			




	
	
	
		
 
		let mut rules: HashMap<(usize, char), HashSet<usize>> = HashMap::new();

			




	
	
	
		
 
		let mut rules: HashMap<(i32, char), HashSet<i32>> = HashMap::new();

			




	
	
	
		
 
		

			




	
	
	
		
 
		for i in r.list_first() {

			




	
	
	
		
 
			let c = pattern_chars[i];

			




	
	
	
		
 
			let key = (START, c);

			




	
	
	
		
 
			match rules.get_mut(&key) {

			




	
	
	
		
 
				Some(set) => {set.insert(i);},

			




	
	
	
		
 
				None => {rules.insert(key, HashSet::from([i]));}

			




	
	
	
		
 
				Some(set) => {set.insert(i as i32);},

			




	
	
	
		
 
				None => {rules.insert(key, HashSet::from([i as i32]));}

			




	
	
	
		
 
			};

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		for (i, j) in r.list_neighbours() {

			




	
	
	
		
 
			let c = pattern_chars[j];

			




	
	
	
		
 
			let key = (i, c);

			




	
	
	
		
 
			let key = (i as i32, c);

			




	
	
	
		
 
			match rules.get_mut(&key) {

			




	
	
	
		
 
				Some(set) => {set.insert(j);},

			




	
	
	
		
 
				None => {rules.insert(key, HashSet::from([j]));}

			




	
	
	
		
 
				Some(set) => {set.insert(j as i32);},

			




	
	
	
		
 
				None => {rules.insert(key, HashSet::from([j as i32]));}

			




	
	
	
		
 
			};

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		let mut end_states = HashSet::from_iter(r.list_last().into_iter());

			




	
	
	
		
 
		let mut end_states = HashSet::from_iter(r.list_last().into_iter().map(|i| i as i32));

			




	
	
	
		
 
		if r.is_skippable() {

			




	
	
	
		
 
			end_states.insert(START);

			




	
	
	
		
 
		}

			




	
	
		
 
@@ -88,16 +89,16 @@ impl Regexp {

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	pub fn determinize(&self) -> RegexpDFA {

			




	
	
	
		
 
		let mut rules: HashMap<(u64, char), u64> = HashMap::new();

			




	
	
	
		
 
		let mut end_states: HashSet<u64> = HashSet::new();

			




	
	
	
		
 
		if self.end_states.contains(&START) {end_states.insert(START as u64);}

			




	
	
	
		
 
		let mut rules: HashMap<(i32, char), i32> = HashMap::new();

			




	
	
	
		
 
		let mut end_states: HashSet<i32> = HashSet::new();

			




	
	
	
		
 
		if self.end_states.contains(&START) {end_states.insert(START);}

			




	
	
	
		
 

			




	
	
	
		
 
		let mut stack = Vec::from([START as u64]);

			




	
	
	
		
 
		let mut stack = Vec::from([START]);

			




	
	
	
		
 
		let mut processed_states = HashSet::new();

			




	
	
	
		
 
		while !stack.is_empty() {

			




	
	
	
		
 
			let state = stack.pop().unwrap();

			




	
	
	
		
 
			let multistate = decode_set(state);

			




	
	
	
		
 
			let mut new_rules: HashMap<char, HashSet<usize>> = HashMap::new();

			




	
	
	
		
 
			let mut new_rules: HashMap<char, HashSet<i32>> = HashMap::new();

			




	
	
	
		
 

			




	
	
	
		
 
			for key in self.rules.keys().filter(|key| multistate.contains(&key.0)) {

			




	
	
	
		
 
				let (_st, c) = key;

			




	
	
		
 
@@ -127,13 +128,13 @@ impl Regexp {

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
pub struct RegexpDFA {

			




	
	
	
		
 
	rules: HashMap<(u64, char), u64>,

			




	
	
	
		
 
	end_states: HashSet<u64>

			




	
	
	
		
 
	rules: HashMap<(i32, char), i32>,

			




	
	
	
		
 
	end_states: HashSet<i32>

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
impl RegexpDFA {

			




	
	
	
		
 
	pub fn eval(&self, s: String) -> bool {

			




	
	
	
		
 
		let mut state = START as u64;

			




	
	
	
		
 
		let mut state = START;

			




	
	
	
		
 

			




	
	
	
		
 
		for c in s.chars() {

			




	
	
	
		
 
			if let Some(x) = self.rules.get(&(state, c)) {

			




	
	
		
 
@@ -152,34 +153,35 @@ impl RegexpDFA {

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	pub fn normalize(&self) -> RegexpDFA {

			




	
	
	
		
 
		let mut index = HashMap::from([(START as u64, START as u64)]);

			




	
	
	
		
 
		let mut queue = VecDeque::from([START as u64]);

			




	
	
	
		
 
		let mut index = HashMap::from([(START, START)]);

			




	
	
	
		
 
		let mut queue = VecDeque::from([START]);

			




	
	
	
		
 

			




	
	
	
		
 
		while !queue.is_empty() {

			




	
	
	
		
 
			let state = queue.pop_front().unwrap();

			




	
	
	
		
 
			let mut edges: Vec<((u64, char), u64)> = self.rules.iter().filter(|((st, c), t)| *st == state).map(|((st, c), t)| ((*st, *c), *t)).collect();

			




	
	
	
		
 
			let mut edges: Vec<((i32, char), i32)> = self.rules.iter()

			




	
	
	
		
 
				.filter(|((st, c), t)| *st == state)

			




	
	
	
		
 
				.map(|((st, c), t)| ((*st, *c), *t)).collect();

			




	
	
	
		
 
			edges.sort();

			




	
	
	
		
 
			for ((_st, _c), t) in edges {

			




	
	
	
		
 
				if !index.contains_key(&t) {

			




	
	
	
		
 
					index.insert(t, index.len() as u64);

			




	
	
	
		
 
					index.insert(t, index.len() as i32);

			




	
	
	
		
 
					queue.push_back(t);

			




	
	
	
		
 
				}

			




	
	
	
		
 
			}

			




	
	
	
		
 
		}

			




	
	
	
		
 

			




	
	
	
		
 
		let rules = self.rules.iter().map(|((st, c), t)| ((index[st as &u64], *c), index[t as &u64])).collect();

			




	
	
	
		
 
		let rules = self.rules.iter().map(|((st, c), t)| ((index[st], *c), index[t])).collect();

			




	
	
	
		
 
		let end_states = self.end_states.iter().map(|st| index[st]).collect();

			




	
	
	
		
 
		

			




	
	
	
		
 
		return RegexpDFA{rules, end_states};

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	fn find_equivalent_states(&self) -> Vec<(u64, u64)> {

			




	
	
	
		
 
		let state_set: HashSet<u64> = HashSet::from_iter(self.rules.values().copied());

			




	
	
	
		
 
		let mut state_vec: Vec<u64> = Vec::from_iter(state_set.into_iter());

			




	
	
	
		
 
		state_vec.push(START as u64);

			




	
	
	
		
 
		state_vec.push(FAIL as u64);

			




	
	
	
		
 
	fn find_equivalent_states(&self) -> Vec<(i32, i32)> {

			




	
	
	
		
 
		let state_set: HashSet<i32> = HashSet::from_iter(self.rules.values().copied());

			




	
	
	
		
 
		let mut state_vec: Vec<i32> = Vec::from_iter(state_set.into_iter());

			




	
	
	
		
 
		state_vec.push(START);

			




	
	
	
		
 
		state_vec.push(FAIL);

			




	
	
	
		
 
		state_vec.sort();

			




	
	
	
		
 
		state_vec.reverse();

			




	
	
	
		
 
		let alphabet: HashSet<char> = self.rules.keys().map(|(_st, c)| c).copied().collect();

			




	
	
	
		
 

			




	
	
	
		
 
		let mut equivalents = HashSet::new();

			




	
	
		
 
@@ -196,8 +198,8 @@ impl RegexpDFA {

			




	
	
	
		
 
			n = equivalents.len();

			




	
	
	
		
 
			equivalents = equivalents.iter().filter(|(s1, s2)| {

			




	
	
	
		
 
				!alphabet.iter().any(|c| {

			




	
	
	
		
 
					let t1 = self.rules.get(&(*s1, *c)).unwrap_or(&(FAIL as u64));

			




	
	
	
		
 
					let t2 = self.rules.get(&(*s2, *c)).unwrap_or(&(FAIL as u64));

			




	
	
	
		
 
					let t1 = self.rules.get(&(*s1, *c)).unwrap_or(&FAIL);

			




	
	
	
		
 
					let t2 = self.rules.get(&(*s2, *c)).unwrap_or(&FAIL);

			




	
	
	
		
 
					let key = (*t1.min(t2), *t1.max(t2));

			




	
	
	
		
 
					return t1 != t2 && !equivalents.contains(&key);

			




	
	
	
		
 
				})

			




	
	
		
 
@@ -207,7 +209,7 @@ impl RegexpDFA {

			




	
	
	
		
 
		return Vec::from_iter(equivalents.into_iter());

			




	
	
	
		
 
	}

			




	
	
	
		
 

			




	
	
	
		
 
	fn collapse_states(&self, mut equivalents: Vec<(u64, u64)>) -> RegexpDFA {

			




	
	
	
		
 
	fn collapse_states(&self, mut equivalents: Vec<(i32, i32)>) -> RegexpDFA {

			




	
	
	
		
 
		let mut rules = self.rules.clone();

			




	
	
	
		
 
		let mut end_states = self.end_states.clone();

			




	
	
	
		
 
		equivalents.sort();

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: Sirius-560
    
    
        This site is powered by
            Kallithea 0.7.0,
        which is
        © 2010–2023 by various authors & licensed under GPLv3.
            – Support