Loading

Paste #pipkovoqt

  1. use std::collections::*;
  2. use std::io;
  3.  
  4. // Machine
  5. struct MachineSpec<T: Copy + Eq + std::hash::Hash> {
  6.     start: T,
  7.     end: T,
  8.     rules: HashMap<(T, Option<char>), HashSet<T>>
  9. }
  10.  
  11. struct Machine<'a, T: 'a + Copy + Eq + std::hash::Hash> {
  12.     spec: &'a MachineSpec<T>, // ' fuck syntax coloring
  13.     states: HashSet<T>
  14. }
  15.  
  16. impl<'a, T> Machine<'a, T> where T: 'a + Copy + Eq + std::hash::Hash { // ' fuck syntax coloring
  17.     fn new(spec: &'a MachineSpec<T>) -> Self { // ' fuck syntax coloring
  18.         let mut states = HashSet::new();
  19.         states.insert(spec.start);
  20.         Machine { spec: spec, states: states }
  21.     }
  22.  
  23.     fn make_closure(&mut self) {
  24.         // I failed to implement (recursive) DFS in Rust
  25.         // so here's non-recursive BFS
  26.         let mut q: VecDeque<T> = self.states.iter().cloned().collect();
  27.         while let Some(v) = q.pop_front() {
  28.             if let Some(ns) = self.spec.rules.get(&(v, None)) {
  29.                 for &n in ns {
  30.                     if !self.states.contains(&n) {
  31.                         q.push_back(n);
  32.                         self.states.insert(n);
  33.                     }
  34.                 }
  35.             }
  36.         }
  37.     }
  38.  
  39.     fn step(&mut self, c: char) {
  40.         self.make_closure();
  41.         let mut res = HashSet::new();
  42.         for &old_state in &self.states {
  43.             if let Some(new_states) = self.spec.rules.get(&(old_state, Some(c))) {
  44.                 for &new_state in new_states {
  45.                     res.insert(new_state);
  46.                 }
  47.             }
  48.         }
  49.         self.states = res;
  50.     }
  51.  
  52.     fn is_final(&mut self) -> bool {
  53.         self.make_closure();
  54.         self.states.contains(&self.spec.end)
  55.     }
  56. }
  57.  
  58. // Lexer
  59.  
  60. #[derive(Copy, Clone)]
  61. enum Token {
  62.     Char(char),
  63.     LParen, RParen,
  64.     LBracket, RBracket,
  65.     Not,
  66.     Pipe,
  67.     Star,
  68.     Plus,
  69.     Minus,
  70.     Question
  71. }
  72.  
  73. struct Lexer<I> where I: Iterator<Item = char> {
  74.     s: I
  75. }
  76.  
  77. impl<I> Iterator for Lexer<I> where I: Iterator<Item = char> {
  78.     type Item = Result<Token, &'static str>; // ' fuck syntax coloring
  79.  
  80.     fn next(&mut self) -> Option<Self::Item> {
  81.         self.s.next().map(|c| match c {
  82.             '(' => Ok(Token::LParen),
  83.             ')' => Ok(Token::RParen),
  84.             '[' => Ok(Token::LBracket),
  85.             ']' => Ok(Token::RBracket),
  86.             '^' => Ok(Token::Not),
  87.             '|' => Ok(Token::Pipe),
  88.             '*' => Ok(Token::Star),
  89.             '+' => Ok(Token::Plus),
  90.             '-' => Ok(Token::Minus),
  91.             '?' => Ok(Token::Question),
  92.             '\\' => match self.s.next() {
  93.                 None => Err("Can't escape EOF"),
  94.                 // TODO: add some more checks,
  95.                 // Err on chars that do not need to be escaped
  96.                 Some(c) => Ok(Token::Char(c))
  97.             },
  98.             _ => Ok(Token::Char(c))
  99.         })
  100.     }
  101. }
  102.  
  103. // Parser
  104.  
  105.  
  106. struct Parser<I> where I: Iterator<Item = char> {
  107.     s: std::iter::Peekable<Lexer<I>>,
  108.     c: u32  // node count, aka new node index
  109. }
  110.  
  111. impl<I> Parser<I> where I: Iterator<Item = char> {
  112.     fn new(l: Lexer<I>) -> Self {
  113.         Parser { s: l.peekable(), c: 0 }
  114.     }
  115.  
  116.     fn parse_s(&mut self) -> Result<MachineSpec<u32>, &'static str> { // ' fuck syntax coloring
  117.         let mut res = try!(self.parse_r());
  118.         while let Some(&Ok(Token::Pipe)) = self.s.peek() {
  119.             self.s.next();
  120.             let t = try!(self.parse_r());
  121.             for (k, v) in t.rules {
  122.                 res.rules.insert(k, v);
  123.             }
  124.             res.rules.insert((self.c, None), [res.start, t.start].iter().cloned().collect());
  125.             res.start = self.c;
  126.             self.c += 1;
  127.             res.rules.insert((res.end, None), [self.c].iter().cloned().collect());
  128.             res.rules.insert((t.end, None), [self.c].iter().cloned().collect());
  129.             res.end = self.c;
  130.             self.c += 1;
  131.         }
  132.         Ok(res)
  133.     }
  134.  
  135.     fn parse_r(&mut self) -> Result<MachineSpec<u32>, &'static str> {
  136.        let mut res = match try!(try!(self.s.next().ok_or("Unexpected EOF"))) {
  137.            Token::LParen => {
  138.                let r = try!(self.parse_s());
  139.                match self.s.next() {
  140.                    None => return Err("Missing ')', reached EOF"),
  141.                    Some(Err(e)) => return Err(e),
  142.                    Some(Ok(Token::RParen)) => r,
  143.                    Some(Ok(_)) => return Err("Missing ')'")
  144.                }
  145.            },
  146.            // TODO: handle[c*]
  147.            Token::Char(c) => {
  148.                self.c += 2;
  149.                let mut tmp1 = HashSet::new();
  150.                tmp1.insert(self.c - 1);
  151.                let mut tmp2 = HashMap::new();
  152.                tmp2.insert((self.c - 2, Some(c)), tmp1);
  153.                MachineSpec {
  154.                    start: self.c - 2,
  155.                    end: self.c - 1,
  156.                    rules: tmp2
  157.                }
  158.            }
  159.            _ => return Err("Unexpected token")
  160.        };
  161.        loop {
  162.            match self.s.peek() {
  163.                None => return Ok(res),
  164.                Some(&v) => match try!(v) {
  165.                    Token::Question => {
  166.                        self.s.next();
  167.                        res.rules.insert((self.c, None), [res.start, self.c + 1].iter().cloned().collect());
  168.                        res.rules.insert((res.end, None), [self.c + 1].iter().cloned().collect());
  169.                        res.start = self.c;
  170.                        res.end = self.c + 1;
  171.                        self.c += 2;
  172.                    },
  173.                    Token::Plus => {
  174.                        self.s.next();
  175.                        res.rules.insert((self.c, None), [res.start].iter().cloned().collect());
  176.                        res.rules.insert((res.end, None), [self.c + 1].iter().cloned().collect());
  177.                        res.rules.insert((self.c + 1, None), [res.start].iter().cloned().collect());
  178.                        res.start = self.c;
  179.                        res.end = self.c + 1;
  180.                        self.c += 2;
  181.                    },
  182.                    Token::Star => {
  183.                        self.s.next();
  184.                        res.rules.insert((self.c, None), [res.start].iter().cloned().collect());
  185.                        res.rules.insert((res.end, None), [self.c].iter().cloned().collect());
  186.                        res.start = self.c;
  187.                        res.end = self.c;
  188.                        self.c += 1;
  189.                    },
  190.                    Token::Char(_) | Token::LParen | Token::LBracket => {
  191.                        let t = try!(self.parse_r());
  192.                        for (k, v) in t.rules {
  193.                            res.rules.insert(k, v);
  194.                        }
  195.                        res.rules.insert((res.end, None), [t.start].iter().cloned().collect());
  196.                        res.end = t.end;
  197.                    }
  198.                    _ => return Ok(res)
  199.                }
  200.            }
  201.        }
  202.    }
  203.  
  204.    fn parse(&mut self) -> Result<MachineSpec<u32>, &'static str> { // ' fuck syntax coloring
  205.         match self.s.peek() {
  206.             None => Ok(MachineSpec { start: 0, end: 0, rules: HashMap::new() }),
  207.             Some(_) => {
  208.                 let res = try!(self.parse_s());
  209.                 match self.s.next() {
  210.                     None => Ok(res),
  211.                     Some(Err(e)) => Err(e),
  212.                     // no idea how we can expect EOF in a RE, but nevertheless
  213.                     Some(Ok(_)) => Err("EOF expected")
  214.                 }
  215.             }
  216.         }
  217.     }
  218. }
  219.  
  220. fn check_regex(regex: &str, s: &str) -> Result<bool, &'static str> { // ' fuck syntax coloring
  221.     let mut parser = Parser::new(Lexer { s: regex.chars() });
  222.     let spec = try!(parser.parse());
  223.  
  224.     println!("Debug: {} {}", spec.start, spec.end);
  225.     for (&(s, c), v) in &spec.rules {
  226.         print!("{} > {} >", s, c.unwrap_or('_'));
  227.         for ss in v {
  228.             print!(" {}", ss);
  229.         }
  230.         println!("");
  231.     }
  232.  
  233.     let mut machine = Machine::new(&spec);
  234.     for c in s.chars() {
  235.         machine.step(c);
  236.     }
  237.     Ok(machine.is_final())
  238. }
  239.  
  240. fn main() {
  241.     let mut regex = String::new();
  242.     println!("Enter the regex:");
  243.     io::stdin().read_line(&mut regex).expect("Failed to read line");
  244.     let mut s = String::new();
  245.     loop {
  246.         s.clear();
  247.         println!("Enter the string:");
  248.         io::stdin().read_line(&mut s).expect("Failed to read line");
  249.         if s.is_empty() { break }
  250.         match check_regex(regex.trim_right(), s.trim_right()) {
  251.             Err(e) => println!("Error: {}", e),
  252.             Ok(true) => println!("Pass"),
  253.             Ok(false) => println!("Nope")
  254.         }
  255.     }
  256. }