src/libregex/parse/mod.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 use std::char;
  12 use std::cmp;
  13 use std::fmt;
  14 use std::iter;
  15 use std::num;
  16 use std::str;
  17
  18 /// Static data containing Unicode ranges for general categories and scripts.
  19 use self::unicode::{UNICODE_CLASSES, PERLD, PERLS, PERLW};
  20 #[allow(visible_private_types)]
  21 pub mod unicode;
  22
  23 /// The maximum number of repetitions allowed with the `{n,m}` syntax.
  24 static MAX_REPEAT: uint = 1000;
  25
  26 /// Error corresponds to something that can go wrong while parsing
  27 /// a regular expression.
  28 ///
  29 /// (Once an expression is compiled, it is not possible to produce an error
  30 /// via searching, splitting or replacing.)
  31 pub struct Error {
  32     /// The *approximate* character index of where the error occurred.
  33     pub pos: uint,
  34     /// A message describing the error.
  35     pub msg: String,
  36 }
  37
  38 impl fmt::Show for Error {
  39     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  40         write!(f, "Regex syntax error near position {}: {}",
  41                self.pos, self.msg)
  42     }
  43 }
  44
  45 /// Represents the abstract syntax of a regular expression.
  46 /// It is showable so that error messages resulting from a bug can provide
  47 /// useful information.
  48 /// It is cloneable so that expressions can be repeated for the counted
  49 /// repetition feature. (No other copying is done.)
  50 ///
  51 /// Note that this representation prevents one from reproducing the regex as
  52 /// it was typed. (But it could be used to reproduce an equivalent regex.)
  53 #[deriving(Show, Clone)]
  54 pub enum Ast {
  55     Nothing,
  56     Literal(char, Flags),
  57     Dot(Flags),
  58     Class(Vec<(char, char)>, Flags),
  59     Begin(Flags),
  60     End(Flags),
  61     WordBoundary(Flags),
  62     Capture(uint, Option<String>, Box<Ast>),
  63     // Represent concatenation as a flat vector to avoid blowing the
  64     // stack in the compiler.
  65     Cat(Vec<Ast>),
  66     Alt(Box<Ast>, Box<Ast>),
  67     Rep(Box<Ast>, Repeater, Greed),
  68 }
  69
  70 #[deriving(Show, PartialEq, Clone)]
  71 pub enum Repeater {
  72     ZeroOne,
  73     ZeroMore,
  74     OneMore,
  75 }
  76
  77 #[deriving(Show, Clone)]
  78 pub enum Greed {
  79     Greedy,
  80     Ungreedy,
  81 }
  82
  83 impl Greed {
  84     pub fn is_greedy(&self) -> bool {
  85         match *self {
  86             Greedy => true,
  87             _ => false,
  88         }
  89     }
  90
  91     fn swap(self, swapped: bool) -> Greed {
  92         if !swapped { return self }
  93         match self {
  94             Greedy => Ungreedy,
  95             Ungreedy => Greedy,
  96         }
  97     }
  98 }
  99
 100 /// BuildAst is a regrettable type that represents intermediate state for
 101 /// constructing an abstract syntax tree. Its central purpose is to facilitate
 102 /// parsing groups and alternations while also maintaining a stack of flag
 103 /// state.
 104 #[deriving(Show)]
 105 enum BuildAst {
 106     Ast(Ast),
 107     Paren(Flags, uint, String), // '('
 108     Bar, // '|'
 109 }
 110
 111 impl BuildAst {
 112     fn paren(&self) -> bool {
 113         match *self {
 114             Paren(_, _, _) => true,
 115             _ => false,
 116         }
 117     }
 118
 119     fn flags(&self) -> Flags {
 120         match *self {
 121             Paren(flags, _, _) => flags,
 122             _ => fail!("Cannot get flags from {}", self),
 123         }
 124     }
 125
 126     fn capture(&self) -> Option<uint> {
 127         match *self {
 128             Paren(_, 0, _) => None,
 129             Paren(_, c, _) => Some(c),
 130             _ => fail!("Cannot get capture group from {}", self),
 131         }
 132     }
 133
 134     fn capture_name(&self) -> Option<String> {
 135         match *self {
 136             Paren(_, 0, _) => None,
 137             Paren(_, _, ref name) => {
 138                 if name.len() == 0 {
 139                     None
 140                 } else {
 141                     Some(name.clone())
 142                 }
 143             }
 144             _ => fail!("Cannot get capture name from {}", self),
 145         }
 146     }
 147
 148     fn bar(&self) -> bool {
 149         match *self {
 150             Bar => true,
 151             _ => false,
 152         }
 153     }
 154
 155     fn unwrap(self) -> Result<Ast, Error> {
 156         match self {
 157             Ast(x) => Ok(x),
 158             _ => fail!("Tried to unwrap non-AST item: {}", self),
 159         }
 160     }
 161 }
 162
 163 /// Flags represents all options that can be twiddled by a user in an
 164 /// expression.
 165 pub type Flags = u8;
 166
 167 pub static FLAG_EMPTY:      u8 = 0;
 168 pub static FLAG_NOCASE:     u8 = 1 << 0; // i
 169 pub static FLAG_MULTI:      u8 = 1 << 1; // m
 170 pub static FLAG_DOTNL:      u8 = 1 << 2; // s
 171 pub static FLAG_SWAP_GREED: u8 = 1 << 3; // U
 172 pub static FLAG_NEGATED:    u8 = 1 << 4; // char class or not word boundary
 173
 174 struct Parser<'a> {
 175     // The input, parsed only as a sequence of UTF8 code points.
 176     chars: Vec<char>,
 177     // The index of the current character in the input.
 178     chari: uint,
 179     // The intermediate state representing the AST.
 180     stack: Vec<BuildAst>,
 181     // The current set of flags.
 182     flags: Flags,
 183     // The total number of capture groups.
 184     // Incremented each time an opening left paren is seen (assuming it is
 185     // opening a capture group).
 186     caps: uint,
 187     // A set of all capture group names used only to detect duplicates.
 188     names: Vec<String>,
 189 }
 190
 191 pub fn parse(s: &str) -> Result<Ast, Error> {
 192     Parser {
 193         chars: s.chars().collect(),
 194         chari: 0,
 195         stack: vec!(),
 196         flags: FLAG_EMPTY,
 197         caps: 0,
 198         names: vec!(),
 199     }.parse()
 200 }
 201
 202 impl<'a> Parser<'a> {
 203     fn parse(&mut self) -> Result<Ast, Error> {
 204         if self.chars.len() == 0 {
 205             return Ok(Nothing);
 206         }
 207         loop {
 208             let c = self.cur();
 209             match c {
 210                 '?' | '*' | '+' => try!(self.push_repeater(c)),
 211                 '\\' => {
 212                     let ast = try!(self.parse_escape());
 213                     self.push(ast)
 214                 }
 215                 '{' => try!(self.parse_counted()),
 216                 '[' => match self.try_parse_ascii() {
 217                     None => try!(self.parse_class()),
 218                     Some(class) => self.push(class),
 219                 },
 220                 '(' => {
 221                     if self.peek_is(1, '?') {
 222                         try!(self.expect('?'))
 223                         try!(self.parse_group_opts())
 224                     } else {
 225                         self.caps += 1;
 226                         self.stack.push(Paren(self.flags,
 227                                               self.caps,
 228                                               "".to_string()))
 229                     }
 230                 }
 231                 ')' => {
 232                     let catfrom = try!(
 233                         self.pos_last(false, |x| x.paren() || x.bar()));
 234                     try!(self.concat(catfrom));
 235
 236                     let altfrom = try!(self.pos_last(false, |x| x.paren()));
 237                     // Before we smush the alternates together and pop off the
 238                     // left paren, let's grab the old flags and see if we
 239                     // need a capture.
 240                     let (cap, cap_name, oldflags) = {
 241                         let paren = self.stack.get(altfrom-1);
 242                         (paren.capture(), paren.capture_name(), paren.flags())
 243                     };
 244                     try!(self.alternate(altfrom));
 245                     self.flags = oldflags;
 246
 247                     // If this was a capture, pop what we just pushed in
 248                     // alternate and make it a capture.
 249                     if cap.is_some() {
 250                         let ast = try!(self.pop_ast());
 251                         self.push(Capture(cap.unwrap(), cap_name, box ast));
 252                     }
 253                 }
 254                 '|' => {
 255                     let catfrom = try!(
 256                         self.pos_last(true, |x| x.paren() || x.bar()));
 257                     try!(self.concat(catfrom));
 258
 259                     self.stack.push(Bar);
 260                 }
 261                 _ => try!(self.push_literal(c)),
 262             }
 263             if !self.next_char() {
 264                 break
 265             }
 266         }
 267
 268         // Try to improve error handling. At this point, there should be
 269         // no remaining open parens.
 270         if self.stack.iter().any(|x| x.paren()) {
 271             return self.err("Unclosed parenthesis.")
 272         }
 273         let catfrom = try!(self.pos_last(true, |x| x.bar()));
 274         try!(self.concat(catfrom));
 275         try!(self.alternate(0));
 276
 277         assert!(self.stack.len() == 1);
 278         self.pop_ast()
 279     }
 280
 281     fn noteof(&mut self, expected: &str) -> Result<(), Error> {
 282         match self.next_char() {
 283             true => Ok(()),
 284             false => {
 285                 self.err(format!("Expected {} but got EOF.",
 286                                  expected).as_slice())
 287             }
 288         }
 289     }
 290
 291     fn expect(&mut self, expected: char) -> Result<(), Error> {
 292         match self.next_char() {
 293             true if self.cur() == expected => Ok(()),
 294             true => self.err(format!("Expected '{}' but got '{}'.",
 295                                      expected, self.cur()).as_slice()),
 296             false => {
 297                 self.err(format!("Expected '{}' but got EOF.",
 298                                  expected).as_slice())
 299             }
 300         }
 301     }
 302
 303     fn next_char(&mut self) -> bool {
 304         self.chari += 1;
 305         self.chari < self.chars.len()
 306     }
 307
 308     fn pop_ast(&mut self) -> Result<Ast, Error> {
 309         match self.stack.pop().unwrap().unwrap() {
 310             Err(e) => Err(e),
 311             Ok(ast) => Ok(ast),
 312         }
 313     }
 314
 315     fn push(&mut self, ast: Ast) {
 316         self.stack.push(Ast(ast))
 317     }
 318
 319     fn push_repeater(&mut self, c: char) -> Result<(), Error> {
 320         if self.stack.len() == 0 {
 321             return self.err(
 322                 "A repeat operator must be preceded by a valid expression.")
 323         }
 324         let rep: Repeater = match c {
 325             '?' => ZeroOne, '*' => ZeroMore, '+' => OneMore,
 326             _ => fail!("Not a valid repeater operator."),
 327         };
 328
 329         match self.peek(1) {
 330             Some('*') | Some('+') =>
 331                 return self.err(
 332                     "Double repeat operators are not supported."),
 333             _ => {},
 334         }
 335         let ast = try!(self.pop_ast());
 336         match ast {
 337             Begin(_) | End(_) | WordBoundary(_) =>
 338                 return self.err(
 339                     "Repeat arguments cannot be empty width assertions."),
 340             _ => {}
 341         }
 342         let greed = try!(self.get_next_greedy());
 343         self.push(Rep(box ast, rep, greed));
 344         Ok(())
 345     }
 346
 347     fn push_literal(&mut self, c: char) -> Result<(), Error> {
 348         match c {
 349             '.' => {
 350                 self.push(Dot(self.flags))
 351             }
 352             '^' => {
 353                 self.push(Begin(self.flags))
 354             }
 355             '$' => {
 356                 self.push(End(self.flags))
 357             }
 358             _ => {
 359                 self.push(Literal(c, self.flags))
 360             }
 361         }
 362         Ok(())
 363     }
 364
 365     // Parses all forms of character classes.
 366     // Assumes that '[' is the current character.
 367     fn parse_class(&mut self) -> Result<(), Error> {
 368         let negated =
 369             if self.peek_is(1, '^') {
 370                 try!(self.expect('^'))
 371                 FLAG_NEGATED
 372             } else {
 373                 FLAG_EMPTY
 374             };
 375         let mut ranges: Vec<(char, char)> = vec!();
 376         let mut alts: Vec<Ast> = vec!();
 377
 378         if self.peek_is(1, ']') {
 379             try!(self.expect(']'))
 380             ranges.push((']', ']'))
 381         }
 382         while self.peek_is(1, '-') {
 383             try!(self.expect('-'))
 384             ranges.push(('-', '-'))
 385         }
 386         loop {
 387             try!(self.noteof("a closing ']' or a non-empty character class)"))
 388             let mut c = self.cur();
 389             match c {
 390                 '[' =>
 391                     match self.try_parse_ascii() {
 392                         Some(Class(asciis, flags)) => {
 393                             alts.push(Class(asciis, flags ^ negated));
 394                             continue
 395                         }
 396                         Some(ast) =>
 397                             fail!("Expected Class AST but got '{}'", ast),
 398                         // Just drop down and try to add as a regular character.
 399                         None => {},
 400                     },
 401                 '\\' => {
 402                     match try!(self.parse_escape()) {
 403                         Class(asciis, flags) => {
 404                             alts.push(Class(asciis, flags ^ negated));
 405                             continue
 406                         }
 407                         Literal(c2, _) => c = c2, // process below
 408                         Begin(_) | End(_) | WordBoundary(_) =>
 409                             return self.err(
 410                                 "\\A, \\z, \\b and \\B are not valid escape \
 411                                  sequences inside a character class."),
 412                         ast => fail!("Unexpected AST item '{}'", ast),
 413                     }
 414                 }
 415                 _ => {},
 416             }
 417             match c {
 418                 ']' => {
 419                     if ranges.len() > 0 {
 420                         let flags = negated | (self.flags & FLAG_NOCASE);
 421                         let mut ast = Class(combine_ranges(ranges), flags);
 422                         for alt in alts.move_iter() {
 423                             ast = Alt(box alt, box ast)
 424                         }
 425                         self.push(ast);
 426                     } else if alts.len() > 0 {
 427                         let mut ast = alts.pop().unwrap();
 428                         for alt in alts.move_iter() {
 429                             ast = Alt(box alt, box ast)
 430                         }
 431                         self.push(ast);
 432                     }
 433                     return Ok(())
 434                 }
 435                 c => {
 436                     if self.peek_is(1, '-') && !self.peek_is(2, ']') {
 437                         try!(self.expect('-'))
 438                         try!(self.noteof("not a ']'"))
 439                         let c2 = self.cur();
 440                         if c2 < c {
 441                             return self.err(format!("Invalid character class \
 442                                                      range '{}-{}'",
 443                                                     c,
 444                                                     c2).as_slice())
 445                         }
 446                         ranges.push((c, self.cur()))
 447                     } else {
 448                         ranges.push((c, c))
 449                     }
 450                 }
 451             }
 452         }
 453     }
 454
 455     // Tries to parse an ASCII character class of the form [:name:].
 456     // If successful, returns an AST character class corresponding to name
 457     // and moves the parser to the final ']' character.
 458     // If unsuccessful, no state is changed and None is returned.
 459     // Assumes that '[' is the current character.
 460     fn try_parse_ascii(&mut self) -> Option<Ast> {
 461         if !self.peek_is(1, ':') {
 462             return None
 463         }
 464         let closer =
 465             match self.pos(']') {
 466                 Some(i) => i,
 467                 None => return None,
 468             };
 469         if *self.chars.get(closer-1) != ':' {
 470             return None
 471         }
 472         if closer - self.chari <= 3 {
 473             return None
 474         }
 475         let mut name_start = self.chari + 2;
 476         let negated =
 477             if self.peek_is(2, '^') {
 478                 name_start += 1;
 479                 FLAG_NEGATED
 480             } else {
 481                 FLAG_EMPTY
 482             };
 483         let name = self.slice(name_start, closer - 1);
 484         match find_class(ASCII_CLASSES, name.as_slice()) {
 485             None => None,
 486             Some(ranges) => {
 487                 self.chari = closer;
 488                 let flags = negated | (self.flags & FLAG_NOCASE);
 489                 Some(Class(combine_ranges(ranges), flags))
 490             }
 491         }
 492     }
 493
 494     // Parses counted repetition. Supports:
 495     // {n}, {n,}, {n,m}, {n}?, {n,}? and {n,m}?
 496     // Assumes that '{' is the current character.
 497     // Returns either an error or moves the parser to the final '}' character.
 498     // (Or the '?' character if not greedy.)
 499     fn parse_counted(&mut self) -> Result<(), Error> {
 500         // Scan until the closing '}' and grab the stuff in {}.
 501         let start = self.chari;
 502         let closer =
 503             match self.pos('}') {
 504                 Some(i) => i,
 505                 None => {
 506                     return self.err(format!("No closing brace for counted \
 507                                              repetition starting at position \
 508                                              {}.",
 509                                             start).as_slice())
 510                 }
 511             };
 512         self.chari = closer;
 513         let greed = try!(self.get_next_greedy());
 514         let inner = str::from_chars(
 515             self.chars.as_slice().slice(start + 1, closer));
 516
 517         // Parse the min and max values from the regex.
 518         let (mut min, mut max): (uint, Option<uint>);
 519         if !inner.as_slice().contains(",") {
 520             min = try!(self.parse_uint(inner.as_slice()));
 521             max = Some(min);
 522         } else {
 523             let pieces: Vec<&str> = inner.as_slice().splitn(',', 1).collect();
 524             let (smin, smax) = (*pieces.get(0), *pieces.get(1));
 525             if smin.len() == 0 {
 526                 return self.err("Max repetitions cannot be specified \
 527                                     without min repetitions.")
 528             }
 529             min = try!(self.parse_uint(smin));
 530             max =
 531                 if smax.len() == 0 {
 532                     None
 533                 } else {
 534                     Some(try!(self.parse_uint(smax)))
 535                 };
 536         }
 537
 538         // Do some bounds checking and make sure max >= min.
 539         if min > MAX_REPEAT {
 540             return self.err(format!(
 541                 "{} exceeds maximum allowed repetitions ({})",
 542                 min, MAX_REPEAT).as_slice());
 543         }
 544         if max.is_some() {
 545             let m = max.unwrap();
 546             if m > MAX_REPEAT {
 547                 return self.err(format!(
 548                     "{} exceeds maximum allowed repetitions ({})",
 549                     m, MAX_REPEAT).as_slice());
 550             }
 551             if m < min {
 552                 return self.err(format!(
 553                     "Max repetitions ({}) cannot be smaller than min \
 554                      repetitions ({}).", m, min).as_slice());
 555             }
 556         }
 557
 558         // Now manipulate the AST be repeating elements.
 559         if max.is_none() {
 560             // Require N copies of what's on the stack and then repeat it.
 561             let ast = try!(self.pop_ast());
 562             for _ in iter::range(0, min) {
 563                 self.push(ast.clone())
 564             }
 565             self.push(Rep(box ast, ZeroMore, greed));
 566         } else {
 567             // Require N copies of what's on the stack and then repeat it
 568             // up to M times optionally.
 569             let ast = try!(self.pop_ast());
 570             for _ in iter::range(0, min) {
 571                 self.push(ast.clone())
 572             }
 573             if max.is_some() {
 574                 for _ in iter::range(min, max.unwrap()) {
 575                     self.push(Rep(box ast.clone(), ZeroOne, greed))
 576                 }
 577             }
 578             // It's possible that we popped something off the stack but
 579             // never put anything back on it. To keep things simple, add
 580             // a no-op expression.
 581             if min == 0 && (max.is_none() || max == Some(0)) {
 582                 self.push(Nothing)
 583             }
 584         }
 585         Ok(())
 586     }
 587
 588     // Parses all escape sequences.
 589     // Assumes that '\' is the current character.
 590     fn parse_escape(&mut self) -> Result<Ast, Error> {
 591         try!(self.noteof("an escape sequence following a '\\'"))
 592
 593         let c = self.cur();
 594         if is_punct(c) {
 595             return Ok(Literal(c, FLAG_EMPTY))
 596         }
 597         match c {
 598             'a' => Ok(Literal('\x07', FLAG_EMPTY)),
 599             'f' => Ok(Literal('\x0C', FLAG_EMPTY)),
 600             't' => Ok(Literal('\t', FLAG_EMPTY)),
 601             'n' => Ok(Literal('\n', FLAG_EMPTY)),
 602             'r' => Ok(Literal('\r', FLAG_EMPTY)),
 603             'v' => Ok(Literal('\x0B', FLAG_EMPTY)),
 604             'A' => Ok(Begin(FLAG_EMPTY)),
 605             'z' => Ok(End(FLAG_EMPTY)),
 606             'b' => Ok(WordBoundary(FLAG_EMPTY)),
 607             'B' => Ok(WordBoundary(FLAG_NEGATED)),
 608             '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7' => Ok(try!(self.parse_octal())),
 609             'x' => Ok(try!(self.parse_hex())),
 610             'p' | 'P' => Ok(try!(self.parse_unicode_name())),
 611             'd' | 'D' | 's' | 'S' | 'w' | 'W' => {
 612                 let ranges = perl_unicode_class(c);
 613                 let mut flags = self.flags & FLAG_NOCASE;
 614                 if c.is_uppercase() { flags |= FLAG_NEGATED }
 615                 Ok(Class(ranges, flags))
 616             }
 617             _ => {
 618                 self.err(format!("Invalid escape sequence '\\\\{}'",
 619                                  c).as_slice())
 620             }
 621         }
 622     }
 623
 624     // Parses a unicode character class name, either of the form \pF where
 625     // F is a one letter unicode class name or of the form \p{name} where
 626     // name is the unicode class name.
 627     // Assumes that \p or \P has been read (and 'p' or 'P' is the current
 628     // character).
 629     fn parse_unicode_name(&mut self) -> Result<Ast, Error> {
 630         let negated = if self.cur() == 'P' { FLAG_NEGATED } else { FLAG_EMPTY };
 631         let mut name: String;
 632         if self.peek_is(1, '{') {
 633             try!(self.expect('{'))
 634             let closer =
 635                 match self.pos('}') {
 636                     Some(i) => i,
 637                     None => return self.err(format!(
 638                         "Missing '\\}' for unclosed '\\{' at position {}",
 639                         self.chari).as_slice()),
 640                 };
 641             if closer - self.chari + 1 == 0 {
 642                 return self.err("No Unicode class name found.")
 643             }
 644             name = self.slice(self.chari + 1, closer);
 645             self.chari = closer;
 646         } else {
 647             if self.chari + 1 >= self.chars.len() {
 648                 return self.err("No single letter Unicode class name found.")
 649             }
 650             name = self.slice(self.chari + 1, self.chari + 2);
 651             self.chari += 1;
 652         }
 653         match find_class(UNICODE_CLASSES, name.as_slice()) {
 654             None => {
 655                 return self.err(format!("Could not find Unicode class '{}'",
 656                                         name).as_slice())
 657             }
 658             Some(ranges) => {
 659                 Ok(Class(ranges, negated | (self.flags & FLAG_NOCASE)))
 660             }
 661         }
 662     }
 663
 664     // Parses an octal number, up to 3 digits.
 665     // Assumes that \n has been read, where n is the first digit.
 666     fn parse_octal(&mut self) -> Result<Ast, Error> {
 667         let start = self.chari;
 668         let mut end = start + 1;
 669         let (d2, d3) = (self.peek(1), self.peek(2));
 670         if d2 >= Some('0') && d2 <= Some('7') {
 671             try!(self.noteof("expected octal character in [0-7]"))
 672             end += 1;
 673             if d3 >= Some('0') && d3 <= Some('7') {
 674                 try!(self.noteof("expected octal character in [0-7]"))
 675                 end += 1;
 676             }
 677         }
 678         let s = self.slice(start, end);
 679         match num::from_str_radix::<u32>(s.as_slice(), 8) {
 680             Some(n) => Ok(Literal(try!(self.char_from_u32(n)), FLAG_EMPTY)),
 681             None => {
 682                 self.err(format!("Could not parse '{}' as octal number.",
 683                                  s).as_slice())
 684             }
 685         }
 686     }
 687
 688     // Parse a hex number. Either exactly two digits or anything in {}.
 689     // Assumes that \x has been read.
 690     fn parse_hex(&mut self) -> Result<Ast, Error> {
 691         if !self.peek_is(1, '{') {
 692             try!(self.expect('{'))
 693             return self.parse_hex_two()
 694         }
 695         let start = self.chari + 2;
 696         let closer =
 697             match self.pos('}') {
 698                 None => {
 699                     return self.err(format!("Missing '\\}' for unclosed \
 700                                              '\\{' at position {}",
 701                                             start).as_slice())
 702                 }
 703                 Some(i) => i,
 704             };
 705         self.chari = closer;
 706         self.parse_hex_digits(self.slice(start, closer).as_slice())
 707     }
 708
 709     // Parses a two-digit hex number.
 710     // Assumes that \xn has been read, where n is the first digit and is the
 711     // current character.
 712     // After return, parser will point at the second digit.
 713     fn parse_hex_two(&mut self) -> Result<Ast, Error> {
 714         let (start, end) = (self.chari, self.chari + 2);
 715         let bad = self.slice(start - 2, self.chars.len());
 716         try!(self.noteof(format!("Invalid hex escape sequence '{}'",
 717                                  bad).as_slice()))
 718         self.parse_hex_digits(self.slice(start, end).as_slice())
 719     }
 720
 721     // Parses `s` as a hexadecimal number.
 722     fn parse_hex_digits(&self, s: &str) -> Result<Ast, Error> {
 723         match num::from_str_radix::<u32>(s, 16) {
 724             Some(n) => Ok(Literal(try!(self.char_from_u32(n)), FLAG_EMPTY)),
 725             None => {
 726                 self.err(format!("Could not parse '{}' as hex number.",
 727                                  s).as_slice())
 728             }
 729         }
 730     }
 731
 732     // Parses a named capture.
 733     // Assumes that '(?P<' has been consumed and that the current character
 734     // is '<'.
 735     // When done, parser will be at the closing '>' character.
 736     fn parse_named_capture(&mut self) -> Result<(), Error> {
 737         try!(self.noteof("a capture name"))
 738         let closer =
 739             match self.pos('>') {
 740                 Some(i) => i,
 741                 None => return self.err("Capture name must end with '>'."),
 742             };
 743         if closer - self.chari == 0 {
 744             return self.err("Capture names must have at least 1 character.")
 745         }
 746         let name = self.slice(self.chari, closer);
 747         if !name.as_slice().chars().all(is_valid_cap) {
 748             return self.err(
 749                 "Capture names can only have underscores, letters and digits.")
 750         }
 751         if self.names.contains(&name) {
 752             return self.err(format!("Duplicate capture group name '{}'.",
 753                                     name).as_slice())
 754         }
 755         self.names.push(name.clone());
 756         self.chari = closer;
 757         self.caps += 1;
 758         self.stack.push(Paren(self.flags, self.caps, name));
 759         Ok(())
 760     }
 761
 762     // Parses non-capture groups and options.
 763     // Assumes that '(?' has already been consumed and '?' is the current
 764     // character.
 765     fn parse_group_opts(&mut self) -> Result<(), Error> {
 766         if self.peek_is(1, 'P') && self.peek_is(2, '<') {
 767             try!(self.expect('P')) try!(self.expect('<'))
 768             return self.parse_named_capture()
 769         }
 770         let start = self.chari;
 771         let mut flags = self.flags;
 772         let mut sign = 1;
 773         let mut saw_flag = false;
 774         loop {
 775             try!(self.noteof("expected non-empty set of flags or closing ')'"))
 776             match self.cur() {
 777                 'i' => { flags = flags | FLAG_NOCASE;     saw_flag = true},
 778                 'm' => { flags = flags | FLAG_MULTI;      saw_flag = true},
 779                 's' => { flags = flags | FLAG_DOTNL;      saw_flag = true},
 780                 'U' => { flags = flags | FLAG_SWAP_GREED; saw_flag = true},
 781                 '-' => {
 782                     if sign < 0 {
 783                         return self.err(format!(
 784                             "Cannot negate flags twice in '{}'.",
 785                             self.slice(start, self.chari + 1)).as_slice())
 786                     }
 787                     sign = -1;
 788                     saw_flag = false;
 789                     flags = flags ^ flags;
 790                 }
 791                 ':' | ')' => {
 792                     if sign < 0 {
 793                         if !saw_flag {
 794                             return self.err(format!(
 795                                 "A valid flag does not follow negation in '{}'",
 796                                 self.slice(start, self.chari + 1)).as_slice())
 797                         }
 798                         flags = flags ^ flags;
 799                     }
 800                     if self.cur() == ':' {
 801                         // Save the old flags with the opening paren.
 802                         self.stack.push(Paren(self.flags, 0, "".to_string()));
 803                     }
 804                     self.flags = flags;
 805                     return Ok(())
 806                 }
 807                 _ => return self.err(format!(
 808                     "Unrecognized flag '{}'.", self.cur()).as_slice()),
 809             }
 810         }
 811     }
 812
 813     // Peeks at the next character and returns whether it's ungreedy or not.
 814     // If it is, then the next character is consumed.
 815     fn get_next_greedy(&mut self) -> Result<Greed, Error> {
 816         Ok(if self.peek_is(1, '?') {
 817             try!(self.expect('?'))
 818             Ungreedy
 819         } else {
 820             Greedy
 821         }.swap(self.flags & FLAG_SWAP_GREED > 0))
 822     }
 823
 824     // Searches the stack (starting at the top) until it finds an expression
 825     // for which `pred` returns true. The index of that expression in the
 826     // stack is returned.
 827     // If there's no match, then one of two things happens depending on the
 828     // values of `allow_start`. When it's true, then `0` will be returned.
 829     // Otherwise, an error will be returned.
 830     // Generally, `allow_start` is only true when you're *not* expecting an
 831     // opening parenthesis.
 832     fn pos_last(&self, allow_start: bool, pred: |&BuildAst| -> bool)
 833                -> Result<uint, Error> {
 834         let from = match self.stack.iter().rev().position(pred) {
 835             Some(i) => i,
 836             None => {
 837                 if allow_start {
 838                     self.stack.len()
 839                 } else {
 840                     return self.err("No matching opening parenthesis.")
 841                 }
 842             }
 843         };
 844         // Adjust index since 'from' is for the reversed stack.
 845         // Also, don't include the '(' or '|'.
 846         Ok(self.stack.len() - from)
 847     }
 848
 849     // concat starts at `from` in the parser's stack and concatenates all
 850     // expressions up to the top of the stack. The resulting concatenation is
 851     // then pushed on to the stack.
 852     // Usually `from` corresponds to the position of an opening parenthesis,
 853     // a '|' (alternation) or the start of the entire expression.
 854     fn concat(&mut self, from: uint) -> Result<(), Error> {
 855         let ast = try!(self.build_from(from, concat_flatten));
 856         self.push(ast);
 857         Ok(())
 858     }
 859
 860     // concat starts at `from` in the parser's stack and alternates all
 861     // expressions up to the top of the stack. The resulting alternation is
 862     // then pushed on to the stack.
 863     // Usually `from` corresponds to the position of an opening parenthesis
 864     // or the start of the entire expression.
 865     // This will also drop any opening parens or alternation bars found in
 866     // the intermediate AST.
 867     fn alternate(&mut self, mut from: uint) -> Result<(), Error> {
 868         // Unlike in the concatenation case, we want 'build_from' to continue
 869         // all the way to the opening left paren (so it will be popped off and
 870         // thrown away). But be careful with overflow---we can't count on the
 871         // open paren to be there.
 872         if from > 0 { from = from - 1}
 873         let ast = try!(self.build_from(from, |l,r| Alt(box l, box r)));
 874         self.push(ast);
 875         Ok(())
 876     }
 877
 878     // build_from combines all AST elements starting at 'from' in the
 879     // parser's stack using 'mk' to combine them. If any such element is not an
 880     // AST then it is popped off the stack and ignored.
 881     fn build_from(&mut self, from: uint, mk: |Ast, Ast| -> Ast)
 882                  -> Result<Ast, Error> {
 883         if from >= self.stack.len() {
 884             return self.err("Empty group or alternate not allowed.")
 885         }
 886
 887         let mut combined = try!(self.pop_ast());
 888         let mut i = self.stack.len();
 889         while i > from {
 890             i = i - 1;
 891             match self.stack.pop().unwrap() {
 892                 Ast(x) => combined = mk(x, combined),
 893                 _ => {},
 894             }
 895         }
 896         Ok(combined)
 897     }
 898
 899     fn parse_uint(&self, s: &str) -> Result<uint, Error> {
 900         match from_str::<uint>(s) {
 901             Some(i) => Ok(i),
 902             None => {
 903                 self.err(format!("Expected an unsigned integer but got '{}'.",
 904                                  s).as_slice())
 905             }
 906         }
 907     }
 908
 909     fn char_from_u32(&self, n: u32) -> Result<char, Error> {
 910         match char::from_u32(n) {
 911             Some(c) => Ok(c),
 912             None => {
 913                 self.err(format!("Could not decode '{}' to unicode \
 914                                   character.",
 915                                  n).as_slice())
 916             }
 917         }
 918     }
 919
 920     fn pos(&self, c: char) -> Option<uint> {
 921         self.chars.iter()
 922             .skip(self.chari).position(|&c2| c2 == c).map(|i| self.chari + i)
 923     }
 924
 925     fn err<T>(&self, msg: &str) -> Result<T, Error> {
 926         Err(Error {
 927             pos: self.chari,
 928             msg: msg.to_string(),
 929         })
 930     }
 931
 932     fn peek(&self, offset: uint) -> Option<char> {
 933         if self.chari + offset >= self.chars.len() {
 934             return None
 935         }
 936         Some(*self.chars.get(self.chari + offset))
 937     }
 938
 939     fn peek_is(&self, offset: uint, is: char) -> bool {
 940         self.peek(offset) == Some(is)
 941     }
 942
 943     fn cur(&self) -> char {
 944         *self.chars.get(self.chari)
 945     }
 946
 947     fn slice(&self, start: uint, end: uint) -> String {
 948         str::from_chars(self.chars.as_slice().slice(start, end)).to_string()
 949     }
 950 }
 951
 952 // Given an unordered collection of character ranges, combine_ranges returns
 953 // an ordered sequence of character ranges where no two ranges overlap. They
 954 // are ordered from least to greatest (using start position).
 955 fn combine_ranges(unordered: Vec<(char, char)>) -> Vec<(char, char)> {
 956     // Returns true iff the two character classes overlap or share a boundary.
 957     // e.g., ('a', 'g') and ('h', 'm') would return true.
 958     fn should_merge((a, b): (char, char), (x, y): (char, char)) -> bool {
 959         cmp::max(a, x) as u32 <= cmp::min(b, y) as u32 + 1
 960     }
 961
 962     // This is currently O(n^2), but I think with sufficient cleverness,
 963     // it can be reduced to O(n) **if necessary**.
 964     let mut ordered: Vec<(char, char)> = Vec::with_capacity(unordered.len());
 965     for (us, ue) in unordered.move_iter() {
 966         let (mut us, mut ue) = (us, ue);
 967         assert!(us <= ue);
 968         let mut which: Option<uint> = None;
 969         for (i, &(os, oe)) in ordered.iter().enumerate() {
 970             if should_merge((us, ue), (os, oe)) {
 971                 us = cmp::min(us, os);
 972                 ue = cmp::max(ue, oe);
 973                 which = Some(i);
 974                 break
 975             }
 976         }
 977         match which {
 978             None => ordered.push((us, ue)),
 979             Some(i) => *ordered.get_mut(i) = (us, ue),
 980         }
 981     }
 982     ordered.sort();
 983     ordered
 984 }
 985
 986 // Constructs a Unicode friendly Perl character class from \d, \s or \w
 987 // (or any of their negated forms). Note that this does not handle negation.
 988 fn perl_unicode_class(which: char) -> Vec<(char, char)> {
 989     match which.to_lowercase() {
 990         'd' => Vec::from_slice(PERLD),
 991         's' => Vec::from_slice(PERLS),
 992         'w' => Vec::from_slice(PERLW),
 993         _ => unreachable!(),
 994     }
 995 }
 996
 997 // Returns a concatenation of two expressions. This also guarantees that a
 998 // `Cat` expression will never be a direct child of another `Cat` expression.
 999 fn concat_flatten(x: Ast, y: Ast) -> Ast {
1000     match (x, y) {
1001         (Cat(mut xs), Cat(ys)) => { xs.push_all_move(ys); Cat(xs) }
1002         (Cat(mut xs), ast) => { xs.push(ast); Cat(xs) }
1003         (ast, Cat(mut xs)) => { xs.unshift(ast); Cat(xs) }
1004         (ast1, ast2) => Cat(vec!(ast1, ast2)),
1005     }
1006 }
1007
1008 pub fn is_punct(c: char) -> bool {
1009     match c {
1010         '\\' | '.' | '+' | '*' | '?' | '(' | ')' | '|' |
1011         '[' | ']' | '{' | '}' | '^' | '$' => true,
1012         _ => false,
1013     }
1014 }
1015
1016 fn is_valid_cap(c: char) -> bool {
1017     c == '_' || (c >= '0' && c <= '9')
1018     || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
1019 }
1020
1021 fn find_class(classes: NamedClasses, name: &str) -> Option<Vec<(char, char)>> {
1022     match classes.bsearch(|&(s, _)| s.cmp(&name)) {
1023         Some(i) => Some(Vec::from_slice(classes[i].val1())),
1024         None => None,
1025     }
1026 }
1027
1028 type Class = &'static [(char, char)];
1029 type NamedClasses = &'static [(&'static str, Class)];
1030
1031 static ASCII_CLASSES: NamedClasses = &[
1032     // Classes must be in alphabetical order so that bsearch works.
1033     // [:alnum:]      alphanumeric (== [0-9A-Za-z])
1034     // [:alpha:]      alphabetic (== [A-Za-z])
1035     // [:ascii:]      ASCII (== [\x00-\x7F])
1036     // [:blank:]      blank (== [\t ])
1037     // [:cntrl:]      control (== [\x00-\x1F\x7F])
1038     // [:digit:]      digits (== [0-9])
1039     // [:graph:]      graphical (== [!-~])
1040     // [:lower:]      lower case (== [a-z])
1041     // [:print:]      printable (== [ -~] == [ [:graph:]])
1042     // [:punct:]      punctuation (== [!-/:-@[-`{-~])
1043     // [:space:]      whitespace (== [\t\n\v\f\r ])
1044     // [:upper:]      upper case (== [A-Z])
1045     // [:word:]       word characters (== [0-9A-Za-z_])
1046     // [:xdigit:]     hex digit (== [0-9A-Fa-f])
1047     // Taken from: http://golang.org/pkg/regex/syntax/
1048     ("alnum", &[('0', '9'), ('A', 'Z'), ('a', 'z')]),
1049     ("alpha", &[('A', 'Z'), ('a', 'z')]),
1050     ("ascii", &[('\x00', '\x7F')]),
1051     ("blank", &[(' ', ' '), ('\t', '\t')]),
1052     ("cntrl", &[('\x00', '\x1F'), ('\x7F', '\x7F')]),
1053     ("digit", &[('0', '9')]),
1054     ("graph", &[('!', '~')]),
1055     ("lower", &[('a', 'z')]),
1056     ("print", &[(' ', '~')]),
1057     ("punct", &[('!', '/'), (':', '@'), ('[', '`'), ('{', '~')]),
1058     ("space", &[('\t', '\t'), ('\n', '\n'), ('\x0B', '\x0B'), ('\x0C', '\x0C'),
1059                 ('\r', '\r'), (' ', ' ')]),
1060     ("upper", &[('A', 'Z')]),
1061     ("word", &[('0', '9'), ('A', 'Z'), ('a', 'z'), ('_', '_')]),
1062     ("xdigit", &[('0', '9'), ('A', 'F'), ('a', 'f')]),
1063 ];