src/libregex/re.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 pub use self::NamesIter::*;
  12 pub use self::Regex::*;
  13
  14 use std::borrow::IntoCow;
  15 use std::collections::HashMap;
  16 use std::fmt;
  17 use std::string::CowString;
  18
  19 use compile::Program;
  20 use parse;
  21 use vm;
  22 use vm::{CaptureLocs, MatchKind, Exists, Location, Submatches};
  23
  24 /// Escapes all regular expression meta characters in `text`.
  25 ///
  26 /// The string returned may be safely used as a literal in a regular
  27 /// expression.
  28 pub fn quote(text: &str) -> String {
  29     let mut quoted = String::with_capacity(text.len());
  30     for c in text.chars() {
  31         if parse::is_punct(c) {
  32             quoted.push('\\')
  33         }
  34         quoted.push(c);
  35     }
  36     quoted
  37 }
  38
  39 /// Tests if the given regular expression matches somewhere in the text given.
  40 ///
  41 /// If there was a problem compiling the regular expression, an error is
  42 /// returned.
  43 ///
  44 /// To find submatches, split or replace text, you'll need to compile an
  45 /// expression first.
  46 ///
  47 /// Note that you should prefer the `regex!` macro when possible. For example,
  48 /// `regex!("...").is_match("...")`.
  49 pub fn is_match(regex: &str, text: &str) -> Result<bool, parse::Error> {
  50     Regex::new(regex).map(|r| r.is_match(text))
  51 }
  52
  53 /// A compiled regular expression
  54 #[derive(Clone)]
  55 pub enum Regex {
  56     // The representation of `Regex` is exported to support the `regex!`
  57     // syntax extension. Do not rely on it.
  58     //
  59     // See the comments for the `program` module in `lib.rs` for a more
  60     // detailed explanation for what `regex!` requires.
  61     #[doc(hidden)]
  62     Dynamic(ExDynamic),
  63     #[doc(hidden)]
  64     Native(ExNative),
  65 }
  66
  67 #[derive(Clone)]
  68 #[doc(hidden)]
  69 pub struct ExDynamic {
  70     original: String,
  71     names: Vec<Option<String>>,
  72     #[doc(hidden)]
  73     pub prog: Program
  74 }
  75
  76 #[doc(hidden)]
  77 #[derive(Copy)]
  78 pub struct ExNative {
  79     #[doc(hidden)]
  80     pub original: &'static str,
  81     #[doc(hidden)]
  82     pub names: &'static &'static [Option<&'static str>],
  83     #[doc(hidden)]
  84     pub prog: fn(MatchKind, &str, uint, uint) -> Vec<Option<uint>>
  85 }
  86
  87 impl Clone for ExNative {
  88     fn clone(&self) -> ExNative {
  89         *self
  90     }
  91 }
  92
  93 impl fmt::Show for Regex {
  94     /// Shows the original regular expression.
  95     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  96         write!(f, "{}", self.as_str())
  97     }
  98 }
  99
 100 impl Regex {
 101     /// Compiles a dynamic regular expression. Once compiled, it can be
 102     /// used repeatedly to search, split or replace text in a string.
 103     ///
 104     /// When possible, you should prefer the `regex!` macro since it is
 105     /// safer and always faster.
 106     ///
 107     /// If an invalid expression is given, then an error is returned.
 108     pub fn new(re: &str) -> Result<Regex, parse::Error> {
 109         let ast = try!(parse::parse(re));
 110         let (prog, names) = Program::new(ast);
 111         Ok(Dynamic(ExDynamic {
 112             original: re.to_string(),
 113             names: names,
 114             prog: prog,
 115         }))
 116     }
 117
 118     /// Returns true if and only if the regex matches the string given.
 119     pub fn is_match(&self, text: &str) -> bool {
 120         has_match(&exec(self, Exists, text))
 121     }
 122
 123     /// Returns the start and end byte range of the leftmost-first match in
 124     /// `text`. If no match exists, then `None` is returned.
 125     pub fn find(&self, text: &str) -> Option<(uint, uint)> {
 126         let caps = exec(self, Location, text);
 127         if has_match(&caps) {
 128             Some((caps[0].unwrap(), caps[1].unwrap()))
 129         } else {
 130             None
 131         }
 132     }
 133
 134     /// Returns an iterator for each successive non-overlapping match in
 135     /// `text`, returning the start and end byte indices with respect to
 136     /// `text`.
 137     pub fn find_iter<'r, 't>(&'r self, text: &'t str) -> FindMatches<'r, 't> {
 138         FindMatches {
 139             re: self,
 140             search: text,
 141             last_end: 0,
 142             last_match: None,
 143         }
 144     }
 145
 146     /// Returns the capture groups corresponding to the leftmost-first
 147     /// match in `text`. Capture group `0` always corresponds to the entire
 148     /// match. If no match is found, then `None` is returned.
 149     ///
 150     /// You should only use `captures` if you need access to submatches.
 151     /// Otherwise, `find` is faster for discovering the location of the overall
 152     /// match.
 153     pub fn captures<'t>(&self, text: &'t str) -> Option<Captures<'t>> {
 154         let caps = exec(self, Submatches, text);
 155         Captures::new(self, text, caps)
 156     }
 157
 158     /// Returns an iterator over all the non-overlapping capture groups matched
 159     /// in `text`. This is operationally the same as `find_iter` (except it
 160     /// yields information about submatches).
 161     pub fn captures_iter<'r, 't>(&'r self, text: &'t str)
 162                                 -> FindCaptures<'r, 't> {
 163         FindCaptures {
 164             re: self,
 165             search: text,
 166             last_match: None,
 167             last_end: 0,
 168         }
 169     }
 170
 171     /// Returns an iterator of substrings of `text` delimited by a match
 172     /// of the regular expression.
 173     /// Namely, each element of the iterator corresponds to text that *isn't*
 174     /// matched by the regular expression.
 175     ///
 176     /// This method will *not* copy the text given.
 177     pub fn split<'r, 't>(&'r self, text: &'t str) -> RegexSplits<'r, 't> {
 178         RegexSplits {
 179             finder: self.find_iter(text),
 180             last: 0,
 181         }
 182     }
 183
 184     /// Returns an iterator of at most `limit` substrings of `text` delimited
 185     /// by a match of the regular expression. (A `limit` of `0` will return no
 186     /// substrings.)
 187     /// Namely, each element of the iterator corresponds to text that *isn't*
 188     /// matched by the regular expression.
 189     /// The remainder of the string that is not split will be the last element
 190     /// in the iterator.
 191     ///
 192     /// This method will *not* copy the text given.
 193     pub fn splitn<'r, 't>(&'r self, text: &'t str, limit: uint)
 194                          -> RegexSplitsN<'r, 't> {
 195         RegexSplitsN {
 196             splits: self.split(text),
 197             cur: 0,
 198             limit: limit,
 199         }
 200     }
 201
 202     /// Replaces the leftmost-first match with the replacement provided.
 203     /// The replacement can be a regular string (where `$N` and `$name` are
 204     /// expanded to match capture groups) or a function that takes the matches'
 205     /// `Captures` and returns the replaced string.
 206     ///
 207     /// If no match is found, then a copy of the string is returned unchanged.
 208     pub fn replace<R: Replacer>(&self, text: &str, rep: R) -> String {
 209         self.replacen(text, 1, rep)
 210     }
 211
 212     /// Replaces all non-overlapping matches in `text` with the
 213     /// replacement provided. This is the same as calling `replacen` with
 214     /// `limit` set to `0`.
 215     ///
 216     /// See the documentation for `replace` for details on how to access
 217     /// submatches in the replacement string.
 218     pub fn replace_all<R: Replacer>(&self, text: &str, rep: R) -> String {
 219         self.replacen(text, 0, rep)
 220     }
 221
 222     /// Replaces at most `limit` non-overlapping matches in `text` with the
 223     /// replacement provided. If `limit` is 0, then all non-overlapping matches
 224     /// are replaced.
 225     ///
 226     /// See the documentation for `replace` for details on how to access
 227     /// submatches in the replacement string.
 228     pub fn replacen<R: Replacer>
 229                    (&self, text: &str, limit: uint, mut rep: R) -> String {
 230         let mut new = String::with_capacity(text.len());
 231         let mut last_match = 0u;
 232
 233         for (i, cap) in self.captures_iter(text).enumerate() {
 234             // It'd be nicer to use the 'take' iterator instead, but it seemed
 235             // awkward given that '0' => no limit.
 236             if limit > 0 && i >= limit {
 237                 break
 238             }
 239
 240             let (s, e) = cap.pos(0).unwrap(); // captures only reports matches
 241             new.push_str(text[last_match..s]);
 242             new.push_str(rep.reg_replace(&cap)[]);
 243             last_match = e;
 244         }
 245         new.push_str(text[last_match..text.len()]);
 246         return new;
 247     }
 248
 249     /// Returns the original string of this regex.
 250     pub fn as_str<'a>(&'a self) -> &'a str {
 251         match *self {
 252             Dynamic(ExDynamic { ref original, .. }) => original[],
 253             Native(ExNative { ref original, .. }) => original[],
 254         }
 255     }
 256
 257     #[doc(hidden)]
 258     #[experimental]
 259     pub fn names_iter<'a>(&'a self) -> NamesIter<'a> {
 260         match *self {
 261             Native(ref n) => NamesIterNative(n.names.iter()),
 262             Dynamic(ref d) => NamesIterDynamic(d.names.iter())
 263         }
 264     }
 265
 266     fn names_len(&self) -> uint {
 267         match *self {
 268             Native(ref n) => n.names.len(),
 269             Dynamic(ref d) => d.names.len()
 270         }
 271     }
 272
 273 }
 274
 275 #[derive(Clone)]
 276 pub enum NamesIter<'a> {
 277     NamesIterNative(::std::slice::Iter<'a, Option<&'static str>>),
 278     NamesIterDynamic(::std::slice::Iter<'a, Option<String>>)
 279 }
 280
 281 impl<'a> Iterator for NamesIter<'a> {
 282     type Item = Option<String>;
 283
 284     fn next(&mut self) -> Option<Option<String>> {
 285         match *self {
 286             NamesIterNative(ref mut i) => i.next().map(|x| x.map(|s| s.to_string())),
 287             NamesIterDynamic(ref mut i) => i.next().map(|x| x.as_ref().map(|s| s.to_string())),
 288         }
 289     }
 290 }
 291
 292 /// NoExpand indicates literal string replacement.
 293 ///
 294 /// It can be used with `replace` and `replace_all` to do a literal
 295 /// string replacement without expanding `$name` to their corresponding
 296 /// capture groups.
 297 ///
 298 /// `'r` is the lifetime of the literal text.
 299 pub struct NoExpand<'t>(pub &'t str);
 300
 301 /// Replacer describes types that can be used to replace matches in a string.
 302 pub trait Replacer {
 303     /// Returns a possibly owned string that is used to replace the match
 304     /// corresponding to the `caps` capture group.
 305     ///
 306     /// The `'a` lifetime refers to the lifetime of a borrowed string when
 307     /// a new owned string isn't needed (e.g., for `NoExpand`).
 308     fn reg_replace<'a>(&'a mut self, caps: &Captures) -> CowString<'a>;
 309 }
 310
 311 impl<'t> Replacer for NoExpand<'t> {
 312     fn reg_replace<'a>(&'a mut self, _: &Captures) -> CowString<'a> {
 313         let NoExpand(s) = *self;
 314         s.into_cow()
 315     }
 316 }
 317
 318 impl<'t> Replacer for &'t str {
 319     fn reg_replace<'a>(&'a mut self, caps: &Captures) -> CowString<'a> {
 320         caps.expand(*self).into_cow()
 321     }
 322 }
 323
 324 impl<F> Replacer for F where F: FnMut(&Captures) -> String {
 325     fn reg_replace<'a>(&'a mut self, caps: &Captures) -> CowString<'a> {
 326         (*self)(caps).into_cow()
 327     }
 328 }
 329
 330 /// Yields all substrings delimited by a regular expression match.
 331 ///
 332 /// `'r` is the lifetime of the compiled expression and `'t` is the lifetime
 333 /// of the string being split.
 334 #[derive(Clone)]
 335 pub struct RegexSplits<'r, 't> {
 336     finder: FindMatches<'r, 't>,
 337     last: uint,
 338 }
 339
 340 impl<'r, 't> Iterator for RegexSplits<'r, 't> {
 341     type Item = &'t str;
 342
 343     fn next(&mut self) -> Option<&'t str> {
 344         let text = self.finder.search;
 345         match self.finder.next() {
 346             None => {
 347                 if self.last >= text.len() {
 348                     None
 349                 } else {
 350                     let s = text[self.last..text.len()];
 351                     self.last = text.len();
 352                     Some(s)
 353                 }
 354             }
 355             Some((s, e)) => {
 356                 let matched = text[self.last..s];
 357                 self.last = e;
 358                 Some(matched)
 359             }
 360         }
 361     }
 362 }
 363
 364 /// Yields at most `N` substrings delimited by a regular expression match.
 365 ///
 366 /// The last substring will be whatever remains after splitting.
 367 ///
 368 /// `'r` is the lifetime of the compiled expression and `'t` is the lifetime
 369 /// of the string being split.
 370 #[derive(Clone)]
 371 pub struct RegexSplitsN<'r, 't> {
 372     splits: RegexSplits<'r, 't>,
 373     cur: uint,
 374     limit: uint,
 375 }
 376
 377 impl<'r, 't> Iterator for RegexSplitsN<'r, 't> {
 378     type Item = &'t str;
 379
 380     fn next(&mut self) -> Option<&'t str> {
 381         let text = self.splits.finder.search;
 382         if self.cur >= self.limit {
 383             None
 384         } else {
 385             self.cur += 1;
 386             if self.cur >= self.limit {
 387                 Some(text[self.splits.last..text.len()])
 388             } else {
 389                 self.splits.next()
 390             }
 391         }
 392     }
 393 }
 394
 395 /// Captures represents a group of captured strings for a single match.
 396 ///
 397 /// The 0th capture always corresponds to the entire match. Each subsequent
 398 /// index corresponds to the next capture group in the regex.
 399 /// If a capture group is named, then the matched string is *also* available
 400 /// via the `name` method. (Note that the 0th capture is always unnamed and so
 401 /// must be accessed with the `at` method.)
 402 ///
 403 /// Positions returned from a capture group are always byte indices.
 404 ///
 405 /// `'t` is the lifetime of the matched text.
 406 pub struct Captures<'t> {
 407     text: &'t str,
 408     locs: CaptureLocs,
 409     named: Option<HashMap<String, uint>>,
 410 }
 411
 412 impl<'t> Captures<'t> {
 413     #[allow(experimental)]
 414     fn new(re: &Regex, search: &'t str, locs: CaptureLocs)
 415           -> Option<Captures<'t>> {
 416         if !has_match(&locs) {
 417             return None
 418         }
 419
 420         let named =
 421             if re.names_len() == 0 {
 422                 None
 423             } else {
 424                 let mut named = HashMap::new();
 425                 for (i, name) in re.names_iter().enumerate() {
 426                     match name {
 427                         None => {},
 428                         Some(name) => {
 429                             named.insert(name, i);
 430                         }
 431                     }
 432                 }
 433                 Some(named)
 434             };
 435         Some(Captures {
 436             text: search,
 437             locs: locs,
 438             named: named,
 439         })
 440     }
 441
 442     /// Returns the start and end positions of the Nth capture group.
 443     /// Returns `None` if `i` is not a valid capture group or if the capture
 444     /// group did not match anything.
 445     /// The positions returned are *always* byte indices with respect to the
 446     /// original string matched.
 447     pub fn pos(&self, i: uint) -> Option<(uint, uint)> {
 448         let (s, e) = (i * 2, i * 2 + 1);
 449         if e >= self.locs.len() || self.locs[s].is_none() {
 450             // VM guarantees that each pair of locations are both Some or None.
 451             return None
 452         }
 453         Some((self.locs[s].unwrap(), self.locs[e].unwrap()))
 454     }
 455
 456     /// Returns the matched string for the capture group `i`.  If `i` isn't
 457     /// a valid capture group or didn't match anything, then `None` is
 458     /// returned.
 459     pub fn at(&self, i: uint) -> Option<&'t str> {
 460         match self.pos(i) {
 461             None => None,
 462             Some((s, e)) => Some(self.text.slice(s, e))
 463         }
 464     }
 465
 466     /// Returns the matched string for the capture group named `name`.  If
 467     /// `name` isn't a valid capture group or didn't match anything, then
 468     /// `None` is returned.
 469     pub fn name(&self, name: &str) -> Option<&'t str> {
 470         match self.named {
 471             None => None,
 472             Some(ref h) => {
 473                 match h.get(name) {
 474                     None => None,
 475                     Some(i) => self.at(*i),
 476                 }
 477             }
 478         }
 479     }
 480
 481     /// Creates an iterator of all the capture groups in order of appearance
 482     /// in the regular expression.
 483     pub fn iter(&'t self) -> SubCaptures<'t> {
 484         SubCaptures { idx: 0, caps: self, }
 485     }
 486
 487     /// Creates an iterator of all the capture group positions in order of
 488     /// appearance in the regular expression. Positions are byte indices
 489     /// in terms of the original string matched.
 490     pub fn iter_pos(&'t self) -> SubCapturesPos<'t> {
 491         SubCapturesPos { idx: 0, caps: self, }
 492     }
 493
 494     /// Expands all instances of `$name` in `text` to the corresponding capture
 495     /// group `name`.
 496     ///
 497     /// `name` may be an integer corresponding to the index of the
 498     /// capture group (counted by order of opening parenthesis where `0` is the
 499     /// entire match) or it can be a name (consisting of letters, digits or
 500     /// underscores) corresponding to a named capture group.
 501     ///
 502     /// If `name` isn't a valid capture group (whether the name doesn't exist or
 503     /// isn't a valid index), then it is replaced with the empty string.
 504     ///
 505     /// To write a literal `$` use `$$`.
 506     pub fn expand(&self, text: &str) -> String {
 507         // How evil can you get?
 508         // FIXME: Don't use regexes for this. It's completely unnecessary.
 509         let re = Regex::new(r"(^|[^$]|\b)\$(\w+)").unwrap();
 510         let text = re.replace_all(text, |&mut: refs: &Captures| -> String {
 511             let pre = refs.at(1).unwrap_or("");
 512             let name = refs.at(2).unwrap_or("");
 513             format!("{}{}", pre,
 514                     match name.parse::<uint>() {
 515                 None => self.name(name).unwrap_or("").to_string(),
 516                 Some(i) => self.at(i).unwrap_or("").to_string(),
 517             })
 518         });
 519         let re = Regex::new(r"\$\$").unwrap();
 520         re.replace_all(text[], NoExpand("$"))
 521     }
 522
 523     /// Returns the number of captured groups.
 524     #[inline]
 525     pub fn len(&self) -> uint { self.locs.len() / 2 }
 526
 527     /// Returns if there are no captured groups.
 528     #[inline]
 529     pub fn is_empty(&self) -> bool { self.len() == 0 }
 530 }
 531
 532 /// An iterator over capture groups for a particular match of a regular
 533 /// expression.
 534 ///
 535 /// `'t` is the lifetime of the matched text.
 536 #[derive(Clone)]
 537 pub struct SubCaptures<'t> {
 538     idx: uint,
 539     caps: &'t Captures<'t>,
 540 }
 541
 542 impl<'t> Iterator for SubCaptures<'t> {
 543     type Item = &'t str;
 544
 545     fn next(&mut self) -> Option<&'t str> {
 546         if self.idx < self.caps.len() {
 547             self.idx += 1;
 548             Some(self.caps.at(self.idx - 1).unwrap_or(""))
 549         } else {
 550             None
 551         }
 552     }
 553 }
 554
 555 /// An iterator over capture group positions for a particular match of a
 556 /// regular expression.
 557 ///
 558 /// Positions are byte indices in terms of the original string matched.
 559 ///
 560 /// `'t` is the lifetime of the matched text.
 561 #[derive(Clone)]
 562 pub struct SubCapturesPos<'t> {
 563     idx: uint,
 564     caps: &'t Captures<'t>,
 565 }
 566
 567 impl<'t> Iterator for SubCapturesPos<'t> {
 568     type Item = Option<(uint, uint)>;
 569
 570     fn next(&mut self) -> Option<Option<(uint, uint)>> {
 571         if self.idx < self.caps.len() {
 572             self.idx += 1;
 573             Some(self.caps.pos(self.idx - 1))
 574         } else {
 575             None
 576         }
 577     }
 578 }
 579
 580 /// An iterator that yields all non-overlapping capture groups matching a
 581 /// particular regular expression.
 582 ///
 583 /// The iterator stops when no more matches can be found.
 584 ///
 585 /// `'r` is the lifetime of the compiled expression and `'t` is the lifetime
 586 /// of the matched string.
 587 #[derive(Clone)]
 588 pub struct FindCaptures<'r, 't> {
 589     re: &'r Regex,
 590     search: &'t str,
 591     last_match: Option<uint>,
 592     last_end: uint,
 593 }
 594
 595 impl<'r, 't> Iterator for FindCaptures<'r, 't> {
 596     type Item = Captures<'t>;
 597
 598     fn next(&mut self) -> Option<Captures<'t>> {
 599         if self.last_end > self.search.len() {
 600             return None
 601         }
 602
 603         let caps = exec_slice(self.re, Submatches, self.search,
 604                               self.last_end, self.search.len());
 605         let (s, e) =
 606             if !has_match(&caps) {
 607                 return None
 608             } else {
 609                 (caps[0].unwrap(), caps[1].unwrap())
 610             };
 611
 612         // Don't accept empty matches immediately following a match.
 613         // i.e., no infinite loops please.
 614         if e == s && Some(self.last_end) == self.last_match {
 615             self.last_end += 1;
 616             return self.next()
 617         }
 618         self.last_end = e;
 619         self.last_match = Some(self.last_end);
 620         Captures::new(self.re, self.search, caps)
 621     }
 622 }
 623
 624 /// An iterator over all non-overlapping matches for a particular string.
 625 ///
 626 /// The iterator yields a tuple of integers corresponding to the start and end
 627 /// of the match. The indices are byte offsets. The iterator stops when no more
 628 /// matches can be found.
 629 ///
 630 /// `'r` is the lifetime of the compiled expression and `'t` is the lifetime
 631 /// of the matched string.
 632 #[derive(Clone)]
 633 pub struct FindMatches<'r, 't> {
 634     re: &'r Regex,
 635     search: &'t str,
 636     last_match: Option<uint>,
 637     last_end: uint,
 638 }
 639
 640 impl<'r, 't> Iterator for FindMatches<'r, 't> {
 641     type Item = (uint, uint);
 642
 643     fn next(&mut self) -> Option<(uint, uint)> {
 644         if self.last_end > self.search.len() {
 645             return None
 646         }
 647
 648         let caps = exec_slice(self.re, Location, self.search,
 649                               self.last_end, self.search.len());
 650         let (s, e) =
 651             if !has_match(&caps) {
 652                 return None
 653             } else {
 654                 (caps[0].unwrap(), caps[1].unwrap())
 655             };
 656
 657         // Don't accept empty matches immediately following a match.
 658         // i.e., no infinite loops please.
 659         if e == s && Some(self.last_end) == self.last_match {
 660             self.last_end += 1;
 661             return self.next()
 662         }
 663         self.last_end = e;
 664         self.last_match = Some(self.last_end);
 665         Some((s, e))
 666     }
 667 }
 668
 669 fn exec(re: &Regex, which: MatchKind, input: &str) -> CaptureLocs {
 670     exec_slice(re, which, input, 0, input.len())
 671 }
 672
 673 fn exec_slice(re: &Regex, which: MatchKind,
 674               input: &str, s: uint, e: uint) -> CaptureLocs {
 675     match *re {
 676         Dynamic(ExDynamic { ref prog, .. }) => vm::run(which, prog, input, s, e),
 677         Native(ExNative { ref prog, .. }) => (*prog)(which, input, s, e),
 678     }
 679 }
 680
 681 #[inline]
 682 fn has_match(caps: &CaptureLocs) -> bool {
 683     caps.len() >= 2 && caps[0].is_some() && caps[1].is_some()
 684 }