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