src/libregex/compile.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // Enable this to squash warnings due to exporting pieces of the representation
  12 // for use with the regex! macro. See lib.rs for explanation.
  13
  14 pub use self::Inst::*;
  15
  16 use std::cmp;
  17 use std::iter::repeat;
  18 use parse;
  19 use parse::{
  20     Flags, FLAG_EMPTY,
  21     Nothing, Literal, Dot, AstClass, Begin, End, WordBoundary, Capture, Cat, Alt,
  22     Rep,
  23     ZeroOne, ZeroMore, OneMore,
  24 };
  25
  26 type InstIdx = uint;
  27
  28 #[deriving(Show, Clone)]
  29 pub enum Inst {
  30     // When a Match instruction is executed, the current thread is successful.
  31     Match,
  32
  33     // The OneChar instruction matches a literal character.
  34     // The flags indicate whether to do a case insensitive match.
  35     OneChar(char, Flags),
  36
  37     // The CharClass instruction tries to match one input character against
  38     // the range of characters given.
  39     // The flags indicate whether to do a case insensitive match and whether
  40     // the character class is negated or not.
  41     CharClass(Vec<(char, char)>, Flags),
  42
  43     // Matches any character except new lines.
  44     // The flags indicate whether to include the '\n' character.
  45     Any(Flags),
  46
  47     // Matches the beginning of the string, consumes no characters.
  48     // The flags indicate whether it matches if the preceding character
  49     // is a new line.
  50     EmptyBegin(Flags),
  51
  52     // Matches the end of the string, consumes no characters.
  53     // The flags indicate whether it matches if the proceeding character
  54     // is a new line.
  55     EmptyEnd(Flags),
  56
  57     // Matches a word boundary (\w on one side and \W \A or \z on the other),
  58     // and consumes no character.
  59     // The flags indicate whether this matches a word boundary or something
  60     // that isn't a word boundary.
  61     EmptyWordBoundary(Flags),
  62
  63     // Saves the current position in the input string to the Nth save slot.
  64     Save(uint),
  65
  66     // Jumps to the instruction at the index given.
  67     Jump(InstIdx),
  68
  69     // Jumps to the instruction at the first index given. If that leads to
  70     // a panic state, then the instruction at the second index given is
  71     // tried.
  72     Split(InstIdx, InstIdx),
  73 }
  74
  75 /// Program represents a compiled regular expression. Once an expression is
  76 /// compiled, its representation is immutable and will never change.
  77 ///
  78 /// All of the data in a compiled expression is wrapped in "MaybeStatic" or
  79 /// "MaybeOwned" types so that a `Program` can be represented as static data.
  80 /// (This makes it convenient and efficient for use with the `regex!` macro.)
  81 #[deriving(Clone)]
  82 pub struct Program {
  83     /// A sequence of instructions.
  84     pub insts: Vec<Inst>,
  85     /// If the regular expression requires a literal prefix in order to have a
  86     /// match, that prefix is stored here. (It's used in the VM to implement
  87     /// an optimization.)
  88     pub prefix: String,
  89 }
  90
  91 impl Program {
  92     /// Compiles a Regex given its AST.
  93     pub fn new(ast: parse::Ast) -> (Program, Vec<Option<String>>) {
  94         let mut c = Compiler {
  95             insts: Vec::with_capacity(100),
  96             names: Vec::with_capacity(10),
  97         };
  98
  99         c.insts.push(Save(0));
 100         c.compile(ast);
 101         c.insts.push(Save(1));
 102         c.insts.push(Match);
 103
 104         // Try to discover a literal string prefix.
 105         // This is a bit hacky since we have to skip over the initial
 106         // 'Save' instruction.
 107         let mut pre = String::with_capacity(5);
 108         for inst in c.insts[1..].iter() {
 109             match *inst {
 110                 OneChar(c, FLAG_EMPTY) => pre.push(c),
 111                 _ => break
 112             }
 113         }
 114
 115         let Compiler { insts, names } = c;
 116         let prog = Program {
 117             insts: insts,
 118             prefix: pre,
 119         };
 120         (prog, names)
 121     }
 122
 123     /// Returns the total number of capture groups in the regular expression.
 124     /// This includes the zeroth capture.
 125     pub fn num_captures(&self) -> uint {
 126         let mut n = 0;
 127         for inst in self.insts.iter() {
 128             match *inst {
 129                 Save(c) => n = cmp::max(n, c+1),
 130                 _ => {}
 131             }
 132         }
 133         // There's exactly 2 Save slots for every capture.
 134         n / 2
 135     }
 136 }
 137
 138 struct Compiler<'r> {
 139     insts: Vec<Inst>,
 140     names: Vec<Option<String>>,
 141 }
 142
 143 // The compiler implemented here is extremely simple. Most of the complexity
 144 // in this crate is in the parser or the VM.
 145 // The only tricky thing here is patching jump/split instructions to point to
 146 // the right instruction.
 147 impl<'r> Compiler<'r> {
 148     fn compile(&mut self, ast: parse::Ast) {
 149         match ast {
 150             Nothing => {},
 151             Literal(c, flags) => self.push(OneChar(c, flags)),
 152             Dot(nl) => self.push(Any(nl)),
 153             AstClass(ranges, flags) =>
 154                 self.push(CharClass(ranges, flags)),
 155             Begin(flags) => self.push(EmptyBegin(flags)),
 156             End(flags) => self.push(EmptyEnd(flags)),
 157             WordBoundary(flags) => self.push(EmptyWordBoundary(flags)),
 158             Capture(cap, name, x) => {
 159                 let len = self.names.len();
 160                 if cap >= len {
 161                     self.names.extend(repeat(None).take(10 + cap - len))
 162                 }
 163                 self.names[cap] = name;
 164
 165                 self.push(Save(2 * cap));
 166                 self.compile(*x);
 167                 self.push(Save(2 * cap + 1));
 168             }
 169             Cat(xs) => {
 170                 for x in xs.into_iter() {
 171                     self.compile(x)
 172                 }
 173             }
 174             Alt(x, y) => {
 175                 let split = self.empty_split(); // push: split 0, 0
 176                 let j1 = self.insts.len();
 177                 self.compile(*x);                // push: insts for x
 178                 let jmp = self.empty_jump();    // push: jmp 0
 179                 let j2 = self.insts.len();
 180                 self.compile(*y);                // push: insts for y
 181                 let j3 = self.insts.len();
 182
 183                 self.set_split(split, j1, j2);  // split 0, 0 -> split j1, j2
 184                 self.set_jump(jmp, j3);         // jmp 0      -> jmp j3
 185             }
 186             Rep(x, ZeroOne, g) => {
 187                 let split = self.empty_split();
 188                 let j1 = self.insts.len();
 189                 self.compile(*x);
 190                 let j2 = self.insts.len();
 191
 192                 if g.is_greedy() {
 193                     self.set_split(split, j1, j2);
 194                 } else {
 195                     self.set_split(split, j2, j1);
 196                 }
 197             }
 198             Rep(x, ZeroMore, g) => {
 199                 let j1 = self.insts.len();
 200                 let split = self.empty_split();
 201                 let j2 = self.insts.len();
 202                 self.compile(*x);
 203                 let jmp = self.empty_jump();
 204                 let j3 = self.insts.len();
 205
 206                 self.set_jump(jmp, j1);
 207                 if g.is_greedy() {
 208                     self.set_split(split, j2, j3);
 209                 } else {
 210                     self.set_split(split, j3, j2);
 211                 }
 212             }
 213             Rep(x, OneMore, g) => {
 214                 let j1 = self.insts.len();
 215                 self.compile(*x);
 216                 let split = self.empty_split();
 217                 let j2 = self.insts.len();
 218
 219                 if g.is_greedy() {
 220                     self.set_split(split, j1, j2);
 221                 } else {
 222                     self.set_split(split, j2, j1);
 223                 }
 224             }
 225         }
 226     }
 227
 228     /// Appends the given instruction to the program.
 229     #[inline]
 230     fn push(&mut self, x: Inst) {
 231         self.insts.push(x)
 232     }
 233
 234     /// Appends an *empty* `Split` instruction to the program and returns
 235     /// the index of that instruction. (The index can then be used to "patch"
 236     /// the actual locations of the split in later.)
 237     #[inline]
 238     fn empty_split(&mut self) -> InstIdx {
 239         self.insts.push(Split(0, 0));
 240         self.insts.len() - 1
 241     }
 242
 243     /// Sets the left and right locations of a `Split` instruction at index
 244     /// `i` to `pc1` and `pc2`, respectively.
 245     /// If the instruction at index `i` isn't a `Split` instruction, then
 246     /// `panic!` is called.
 247     #[inline]
 248     fn set_split(&mut self, i: InstIdx, pc1: InstIdx, pc2: InstIdx) {
 249         let split = &mut self.insts[i];
 250         match *split {
 251             Split(_, _) => *split = Split(pc1, pc2),
 252             _ => panic!("BUG: Invalid split index."),
 253         }
 254     }
 255
 256     /// Appends an *empty* `Jump` instruction to the program and returns the
 257     /// index of that instruction.
 258     #[inline]
 259     fn empty_jump(&mut self) -> InstIdx {
 260         self.insts.push(Jump(0));
 261         self.insts.len() - 1
 262     }
 263
 264     /// Sets the location of a `Jump` instruction at index `i` to `pc`.
 265     /// If the instruction at index `i` isn't a `Jump` instruction, then
 266     /// `panic!` is called.
 267     #[inline]
 268     fn set_jump(&mut self, i: InstIdx, pc: InstIdx) {
 269         let jmp = &mut self.insts[i];
 270         match *jmp {
 271             Jump(_) => *jmp = Jump(pc),
 272             _ => panic!("BUG: Invalid jump index."),
 273         }
 274     }
 275 }