Loading

Simple grep in Rust

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