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::collections::HashMap;
  15 use std::fmt;
  16 use std::str::{MaybeOwned, Owned, Slice};
  17
  18 use compile::Program;
  19 use parse;
  20 use vm;
  21 use vm::{CaptureLocs, MatchKind, Exists, Location, Submatches};
  22
  23 /// Escapes all regular expression meta characters in `text`.
  24 ///
  25 /// The string returned may be safely used as a literal in a regular
  26 /// expression.
  27 pub fn quote(text: &str) -> String {
  28     let mut quoted = String::with_capacity(text.len());
  29     for c in text.chars() {
  30         if parse::is_punct(c) {
  31             quoted.push('\\')
  32         }
  33         quoted.push(c);
  34     }
  35     quoted
  36 }
  37
  38 /// Tests if the given regular expression matches somewhere in the text given.
  39 ///
  40 /// If there was a problem compiling the regular expression, an error is
  41 /// returned.
  42 ///
  43 /// To find submatches, split or replace text, you'll need to compile an
  44 /// expression first.
  45 ///
  46 /// Note that you should prefer the `regex!` macro when possible. For example,
  47 /// `regex!("...").is_match("...")`.
  48 pub fn is_match(regex: &str, text: &str) -> Result<bool, parse::Error> {
  49     Regex::new(regex).map(|r| r.is_match(text))
  50 }
  51
  52 /// A compiled regular expression
  53 ///
  54 /// It is represented as either a sequence of bytecode instructions (dynamic)
  55 /// or as a specialized Rust function (native). It can be used to search, split
  56 /// or replace text. All searching is done with an implicit `.*?` at the
  57 /// beginning and end of an expression. To force an expression to match the
  58 /// whole string (or a prefix or a suffix), you must use an anchor like `^` or
  59 /// `$` (or `\A` and `\z`).
  60 ///
  61 /// While this crate will handle Unicode strings (whether in the regular
  62 /// expression or in the search text), all positions returned are **byte
  63 /// indices**. Every byte index is guaranteed to be at a Unicode code point
  64 /// boundary.
  65 ///
  66 /// The lifetimes `'r` and `'t` in this crate correspond to the lifetime of a
  67 /// compiled regular expression and text to search, respectively.
  68 ///
  69 /// The only methods that allocate new strings are the string replacement
  70 /// methods. All other methods (searching and splitting) return borrowed
  71 /// pointers into the string given.
  72 ///
  73 /// # Examples
  74 ///
  75 /// Find the location of a US phone number:
  76 ///
  77 /// ```rust
  78 /// # use regex::Regex;
  79 /// let re = match Regex::new("[0-9]{3}-[0-9]{3}-[0-9]{4}") {
  80 ///     Ok(re) => re,
  81 ///     Err(err) => panic!("{}", err),
  82 /// };
  83 /// assert_eq!(re.find("phone: 111-222-3333"), Some((7, 19)));
  84 /// ```
  85 ///
  86 /// You can also use the `regex!` macro to compile a regular expression when
  87 /// you compile your program:
  88 ///
  89 /// ```rust
  90 /// #![feature(phase)]
  91 /// extern crate regex;
  92 /// #[phase(plugin)] extern crate regex_macros;
  93 ///
  94 /// fn main() {
  95 ///     let re = regex!(r"\d+");
  96 ///     assert_eq!(re.find("123 abc"), Some((0, 3)));
  97 /// }
  98 /// ```
  99 ///
 100 /// Given an incorrect regular expression, `regex!` will cause the Rust
 101 /// compiler to produce a compile time error.
 102 /// Note that `regex!` will compile the expression to native Rust code, which
 103 /// makes it much faster when searching text.
 104 /// More details about the `regex!` macro can be found in the `regex` crate
 105 /// documentation.
 106 #[deriving(Clone)]
 107 pub enum Regex {
 108     // The representation of `Regex` is exported to support the `regex!`
 109     // syntax extension. Do not rely on it.
 110     //
 111     // See the comments for the `program` module in `lib.rs` for a more
 112     // detailed explanation for what `regex!` requires.
 113     #[doc(hidden)]
 114     Dynamic(ExDynamic),
 115     #[doc(hidden)]
 116     Native(ExNative),
 117 }
 118
 119 #[deriving(Clone)]
 120 #[doc(hidden)]
 121 pub struct ExDynamic {
 122     original: String,
 123     names: Vec<Option<String>>,
 124     #[doc(hidden)]
 125     pub prog: Program
 126 }
 127
 128 #[doc(hidden)]
 129 pub struct ExNative {
 130     #[doc(hidden)]
 131     pub original: &'static str,
 132     #[doc(hidden)]
 133     pub names: &'static &'static [Option<&'static str>],
 134     #[doc(hidden)]
 135     pub prog: fn(MatchKind, &str, uint, uint) -> Vec<Option<uint>>
 136 }
 137
 138 impl Clone for ExNative {
 139     fn clone(&self) -> ExNative { *self }
 140 }
 141
 142 impl fmt::Show for Regex {
 143     /// Shows the original regular expression.
 144     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 145         write!(f, "{}", self.as_str())
 146     }
 147 }
 148
 149 impl Regex {
 150     /// Compiles a dynamic regular expression. Once compiled, it can be
 151     /// used repeatedly to search, split or replace text in a string.
 152     ///
 153     /// When possible, you should prefer the `regex!` macro since it is
 154     /// safer and always faster.
 155     ///
 156     /// If an invalid expression is given, then an error is returned.
 157     pub fn new(re: &str) -> Result<Regex, parse::Error> {
 158         let ast = try!(parse::parse(re));
 159         let (prog, names) = Program::new(ast);
 160         Ok(Dynamic(ExDynamic {
 161             original: re.to_string(),
 162             names: names,
 163             prog: prog,
 164         }))
 165     }
 166
 167     /// Returns true if and only if the regex matches the string given.
 168     ///
 169     /// # Example
 170     ///
 171     /// Test if some text contains at least one word with exactly 13
 172     /// characters:
 173     ///
 174     /// ```rust
 175     /// # #![feature(phase)]
 176     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 177     /// # fn main() {
 178     /// let text = "I categorically deny having triskaidekaphobia.";
 179     /// let matched = regex!(r"\b\w{13}\b").is_match(text);
 180     /// assert!(matched);
 181     /// # }
 182     /// ```
 183     pub fn is_match(&self, text: &str) -> bool {
 184         has_match(&exec(self, Exists, text))
 185     }
 186
 187     /// Returns the start and end byte range of the leftmost-first match in
 188     /// `text`. If no match exists, then `None` is returned.
 189     ///
 190     /// Note that this should only be used if you want to discover the position
 191     /// of the match. Testing the existence of a match is faster if you use
 192     /// `is_match`.
 193     ///
 194     /// # Example
 195     ///
 196     /// Find the start and end location of the first word with exactly 13
 197     /// characters:
 198     ///
 199     /// ```rust
 200     /// # #![feature(phase)]
 201     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 202     /// # fn main() {
 203     /// let text = "I categorically deny having triskaidekaphobia.";
 204     /// let pos = regex!(r"\b\w{13}\b").find(text);
 205     /// assert_eq!(pos, Some((2, 15)));
 206     /// # }
 207     /// ```
 208     pub fn find(&self, text: &str) -> Option<(uint, uint)> {
 209         let caps = exec(self, Location, text);
 210         if has_match(&caps) {
 211             Some((caps[0].unwrap(), caps[1].unwrap()))
 212         } else {
 213             None
 214         }
 215     }
 216
 217     /// Returns an iterator for each successive non-overlapping match in
 218     /// `text`, returning the start and end byte indices with respect to
 219     /// `text`.
 220     ///
 221     /// # Example
 222     ///
 223     /// Find the start and end location of every word with exactly 13
 224     /// characters:
 225     ///
 226     /// ```rust
 227     /// # #![feature(phase)]
 228     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 229     /// # fn main() {
 230     /// let text = "Retroactively relinquishing remunerations is reprehensible.";
 231     /// for pos in regex!(r"\b\w{13}\b").find_iter(text) {
 232     ///     println!("{}", pos);
 233     /// }
 234     /// // Output:
 235     /// // (0, 13)
 236     /// // (14, 27)
 237     /// // (28, 41)
 238     /// // (45, 58)
 239     /// # }
 240     /// ```
 241     pub fn find_iter<'r, 't>(&'r self, text: &'t str) -> FindMatches<'r, 't> {
 242         FindMatches {
 243             re: self,
 244             search: text,
 245             last_end: 0,
 246             last_match: None,
 247         }
 248     }
 249
 250     /// Returns the capture groups corresponding to the leftmost-first
 251     /// match in `text`. Capture group `0` always corresponds to the entire
 252     /// match. If no match is found, then `None` is returned.
 253     ///
 254     /// You should only use `captures` if you need access to submatches.
 255     /// Otherwise, `find` is faster for discovering the location of the overall
 256     /// match.
 257     ///
 258     /// # Examples
 259     ///
 260     /// Say you have some text with movie names and their release years,
 261     /// like "'Citizen Kane' (1941)". It'd be nice if we could search for text
 262     /// looking like that, while also extracting the movie name and its release
 263     /// year separately.
 264     ///
 265     /// ```rust
 266     /// # #![feature(phase)]
 267     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 268     /// # fn main() {
 269     /// let re = regex!(r"'([^']+)'\s+\((\d{4})\)");
 270     /// let text = "Not my favorite movie: 'Citizen Kane' (1941).";
 271     /// let caps = re.captures(text).unwrap();
 272     /// assert_eq!(caps.at(1), "Citizen Kane");
 273     /// assert_eq!(caps.at(2), "1941");
 274     /// assert_eq!(caps.at(0), "'Citizen Kane' (1941)");
 275     /// # }
 276     /// ```
 277     ///
 278     /// Note that the full match is at capture group `0`. Each subsequent
 279     /// capture group is indexed by the order of its opening `(`.
 280     ///
 281     /// We can make this example a bit clearer by using *named* capture groups:
 282     ///
 283     /// ```rust
 284     /// # #![feature(phase)]
 285     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 286     /// # fn main() {
 287     /// let re = regex!(r"'(?P<title>[^']+)'\s+\((?P<year>\d{4})\)");
 288     /// let text = "Not my favorite movie: 'Citizen Kane' (1941).";
 289     /// let caps = re.captures(text).unwrap();
 290     /// assert_eq!(caps.name("title"), "Citizen Kane");
 291     /// assert_eq!(caps.name("year"), "1941");
 292     /// assert_eq!(caps.at(0), "'Citizen Kane' (1941)");
 293     /// # }
 294     /// ```
 295     ///
 296     /// Here we name the capture groups, which we can access with the `name`
 297     /// method. Note that the named capture groups are still accessible with
 298     /// `at`.
 299     ///
 300     /// The `0`th capture group is always unnamed, so it must always be
 301     /// accessed with `at(0)`.
 302     pub fn captures<'t>(&self, text: &'t str) -> Option<Captures<'t>> {
 303         let caps = exec(self, Submatches, text);
 304         Captures::new(self, text, caps)
 305     }
 306
 307     /// Returns an iterator over all the non-overlapping capture groups matched
 308     /// in `text`. This is operationally the same as `find_iter` (except it
 309     /// yields information about submatches).
 310     ///
 311     /// # Example
 312     ///
 313     /// We can use this to find all movie titles and their release years in
 314     /// some text, where the movie is formatted like "'Title' (xxxx)":
 315     ///
 316     /// ```rust
 317     /// # #![feature(phase)]
 318     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 319     /// # fn main() {
 320     /// let re = regex!(r"'(?P<title>[^']+)'\s+\((?P<year>\d{4})\)");
 321     /// let text = "'Citizen Kane' (1941), 'The Wizard of Oz' (1939), 'M' (1931).";
 322     /// for caps in re.captures_iter(text) {
 323     ///     println!("Movie: {}, Released: {}", caps.name("title"), caps.name("year"));
 324     /// }
 325     /// // Output:
 326     /// // Movie: Citizen Kane, Released: 1941
 327     /// // Movie: The Wizard of Oz, Released: 1939
 328     /// // Movie: M, Released: 1931
 329     /// # }
 330     /// ```
 331     pub fn captures_iter<'r, 't>(&'r self, text: &'t str)
 332                                 -> FindCaptures<'r, 't> {
 333         FindCaptures {
 334             re: self,
 335             search: text,
 336             last_match: None,
 337             last_end: 0,
 338         }
 339     }
 340
 341     /// Returns an iterator of substrings of `text` delimited by a match
 342     /// of the regular expression.
 343     /// Namely, each element of the iterator corresponds to text that *isn't*
 344     /// matched by the regular expression.
 345     ///
 346     /// This method will *not* copy the text given.
 347     ///
 348     /// # Example
 349     ///
 350     /// To split a string delimited by arbitrary amounts of spaces or tabs:
 351     ///
 352     /// ```rust
 353     /// # #![feature(phase)]
 354     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 355     /// # fn main() {
 356     /// let re = regex!(r"[ \t]+");
 357     /// let fields: Vec<&str> = re.split("a b \t  c\td    e").collect();
 358     /// assert_eq!(fields, vec!("a", "b", "c", "d", "e"));
 359     /// # }
 360     /// ```
 361     pub fn split<'r, 't>(&'r self, text: &'t str) -> RegexSplits<'r, 't> {
 362         RegexSplits {
 363             finder: self.find_iter(text),
 364             last: 0,
 365         }
 366     }
 367
 368     /// Returns an iterator of at most `limit` substrings of `text` delimited
 369     /// by a match of the regular expression. (A `limit` of `0` will return no
 370     /// substrings.)
 371     /// Namely, each element of the iterator corresponds to text that *isn't*
 372     /// matched by the regular expression.
 373     /// The remainder of the string that is not split will be the last element
 374     /// in the iterator.
 375     ///
 376     /// This method will *not* copy the text given.
 377     ///
 378     /// # Example
 379     ///
 380     /// Get the first two words in some text:
 381     ///
 382     /// ```rust
 383     /// # #![feature(phase)]
 384     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 385     /// # fn main() {
 386     /// let re = regex!(r"\W+");
 387     /// let fields: Vec<&str> = re.splitn("Hey! How are you?", 3).collect();
 388     /// assert_eq!(fields, vec!("Hey", "How", "are you?"));
 389     /// # }
 390     /// ```
 391     pub fn splitn<'r, 't>(&'r self, text: &'t str, limit: uint)
 392                          -> RegexSplitsN<'r, 't> {
 393         RegexSplitsN {
 394             splits: self.split(text),
 395             cur: 0,
 396             limit: limit,
 397         }
 398     }
 399
 400     /// Replaces the leftmost-first match with the replacement provided.
 401     /// The replacement can be a regular string (where `$N` and `$name` are
 402     /// expanded to match capture groups) or a function that takes the matches'
 403     /// `Captures` and returns the replaced string.
 404     ///
 405     /// If no match is found, then a copy of the string is returned unchanged.
 406     ///
 407     /// # Examples
 408     ///
 409     /// Note that this function is polymorphic with respect to the replacement.
 410     /// In typical usage, this can just be a normal string:
 411     ///
 412     /// ```rust
 413     /// # #![feature(phase)]
 414     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 415     /// # fn main() {
 416     /// let re = regex!("[^01]+");
 417     /// assert_eq!(re.replace("1078910", "").as_slice(), "1010");
 418     /// # }
 419     /// ```
 420     ///
 421     /// But anything satisfying the `Replacer` trait will work. For example,
 422     /// a closure of type `|&Captures| -> String` provides direct access to the
 423     /// captures corresponding to a match. This allows one to access
 424     /// submatches easily:
 425     ///
 426     /// ```rust
 427     /// # #![feature(phase)]
 428     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 429     /// # use regex::Captures; fn main() {
 430     /// let re = regex!(r"([^,\s]+),\s+(\S+)");
 431     /// let result = re.replace("Springsteen, Bruce", |caps: &Captures| {
 432     ///     format!("{} {}", caps.at(2), caps.at(1))
 433     /// });
 434     /// assert_eq!(result.as_slice(), "Bruce Springsteen");
 435     /// # }
 436     /// ```
 437     ///
 438     /// But this is a bit cumbersome to use all the time. Instead, a simple
 439     /// syntax is supported that expands `$name` into the corresponding capture
 440     /// group. Here's the last example, but using this expansion technique
 441     /// with named capture groups:
 442     ///
 443     /// ```rust
 444     /// # #![feature(phase)]
 445     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 446     /// # fn main() {
 447     /// let re = regex!(r"(?P<last>[^,\s]+),\s+(?P<first>\S+)");
 448     /// let result = re.replace("Springsteen, Bruce", "$first $last");
 449     /// assert_eq!(result.as_slice(), "Bruce Springsteen");
 450     /// # }
 451     /// ```
 452     ///
 453     /// Note that using `$2` instead of `$first` or `$1` instead of `$last`
 454     /// would produce the same result. To write a literal `$` use `$$`.
 455     ///
 456     /// Finally, sometimes you just want to replace a literal string with no
 457     /// submatch expansion. This can be done by wrapping a string with
 458     /// `NoExpand`:
 459     ///
 460     /// ```rust
 461     /// # #![feature(phase)]
 462     /// # extern crate regex; #[phase(plugin)] extern crate regex_macros;
 463     /// # fn main() {
 464     /// use regex::NoExpand;
 465     ///
 466     /// let re = regex!(r"(?P<last>[^,\s]+),\s+(\S+)");
 467     /// let result = re.replace("Springsteen, Bruce", NoExpand("$2 $last"));
 468     /// assert_eq!(result.as_slice(), "$2 $last");
 469     /// # }
 470     /// ```
 471     pub fn replace<R: Replacer>(&self, text: &str, rep: R) -> String {
 472         self.replacen(text, 1, rep)
 473     }
 474
 475     /// Replaces all non-overlapping matches in `text` with the
 476     /// replacement provided. This is the same as calling `replacen` with
 477     /// `limit` set to `0`.
 478     ///
 479     /// See the documentation for `replace` for details on how to access
 480     /// submatches in the replacement string.
 481     pub fn replace_all<R: Replacer>(&self, text: &str, rep: R) -> String {
 482         self.replacen(text, 0, rep)
 483     }
 484
 485     /// Replaces at most `limit` non-overlapping matches in `text` with the
 486     /// replacement provided. If `limit` is 0, then all non-overlapping matches
 487     /// are replaced.
 488     ///
 489     /// See the documentation for `replace` for details on how to access
 490     /// submatches in the replacement string.
 491     pub fn replacen<R: Replacer>
 492                    (&self, text: &str, limit: uint, mut rep: R) -> String {
 493         let mut new = String::with_capacity(text.len());
 494         let mut last_match = 0u;
 495
 496         for (i, cap) in self.captures_iter(text).enumerate() {
 497             // It'd be nicer to use the 'take' iterator instead, but it seemed
 498             // awkward given that '0' => no limit.
 499             if limit > 0 && i >= limit {
 500                 break
 501             }
 502
 503             let (s, e) = cap.pos(0).unwrap(); // captures only reports matches
 504             new.push_str(text.slice(last_match, s));
 505             new.push_str(rep.reg_replace(&cap).as_slice());
 506             last_match = e;
 507         }
 508         new.push_str(text.slice(last_match, text.len()));
 509         return new;
 510     }
 511
 512     /// Returns the original string of this regex.
 513     pub fn as_str<'a>(&'a self) -> &'a str {
 514         match *self {
 515             Dynamic(ExDynamic { ref original, .. }) => original.as_slice(),
 516             Native(ExNative { ref original, .. }) => original.as_slice(),
 517         }
 518     }
 519
 520     #[doc(hidden)]
 521     #[experimental]
 522     pub fn names_iter<'a>(&'a self) -> NamesIter<'a> {
 523         match *self {
 524             Native(ref n) => NamesIterNative(n.names.iter()),
 525             Dynamic(ref d) => NamesIterDynamic(d.names.iter())
 526         }
 527     }
 528
 529     fn names_len(&self) -> uint {
 530         match *self {
 531             Native(ref n) => n.names.len(),
 532             Dynamic(ref d) => d.names.len()
 533         }
 534     }
 535
 536 }
 537
 538 pub enum NamesIter<'a> {
 539     NamesIterNative(::std::slice::Items<'a, Option<&'static str>>),
 540     NamesIterDynamic(::std::slice::Items<'a, Option<String>>)
 541 }
 542
 543 impl<'a> Iterator<Option<String>> for NamesIter<'a> {
 544     fn next(&mut self) -> Option<Option<String>> {
 545         match *self {
 546             NamesIterNative(ref mut i) => i.next().map(|x| x.map(|s| s.to_string())),
 547             NamesIterDynamic(ref mut i) => i.next().map(|x| x.as_ref().map(|s| s.to_string())),
 548         }
 549     }
 550 }
 551
 552 /// NoExpand indicates literal string replacement.
 553 ///
 554 /// It can be used with `replace` and `replace_all` to do a literal
 555 /// string replacement without expanding `$name` to their corresponding
 556 /// capture groups.
 557 ///
 558 /// `'r` is the lifetime of the literal text.
 559 pub struct NoExpand<'t>(pub &'t str);
 560
 561 /// Replacer describes types that can be used to replace matches in a string.
 562 pub trait Replacer {
 563     /// Returns a possibly owned string that is used to replace the match
 564     /// corresponding to the `caps` capture group.
 565     ///
 566     /// The `'a` lifetime refers to the lifetime of a borrowed string when
 567     /// a new owned string isn't needed (e.g., for `NoExpand`).
 568     fn reg_replace<'a>(&'a mut self, caps: &Captures) -> MaybeOwned<'a>;
 569 }
 570
 571 impl<'t> Replacer for NoExpand<'t> {
 572     fn reg_replace<'a>(&'a mut self, _: &Captures) -> MaybeOwned<'a> {
 573         let NoExpand(s) = *self;
 574         Slice(s)
 575     }
 576 }
 577
 578 impl<'t> Replacer for &'t str {
 579     fn reg_replace<'a>(&'a mut self, caps: &Captures) -> MaybeOwned<'a> {
 580         Owned(caps.expand(*self))
 581     }
 582 }
 583
 584 impl<'t> Replacer for |&Captures|: 't -> String {
 585     fn reg_replace<'a>(&'a mut self, caps: &Captures) -> MaybeOwned<'a> {
 586         Owned((*self)(caps))
 587     }
 588 }
 589
 590 /// Yields all substrings delimited by a regular expression match.
 591 ///
 592 /// `'r` is the lifetime of the compiled expression and `'t` is the lifetime
 593 /// of the string being split.
 594 pub struct RegexSplits<'r, 't> {
 595     finder: FindMatches<'r, 't>,
 596     last: uint,
 597 }
 598
 599 impl<'r, 't> Iterator<&'t str> for RegexSplits<'r, 't> {
 600     fn next(&mut self) -> Option<&'t str> {
 601         let text = self.finder.search;
 602         match self.finder.next() {
 603             None => {
 604                 if self.last >= text.len() {
 605                     None
 606                 } else {
 607                     let s = text.slice(self.last, text.len());
 608                     self.last = text.len();
 609                     Some(s)
 610                 }
 611             }
 612             Some((s, e)) => {
 613                 let matched = text.slice(self.last, s);
 614                 self.last = e;
 615                 Some(matched)
 616             }
 617         }
 618     }
 619 }
 620
 621 /// Yields at most `N` substrings delimited by a regular expression match.
 622 ///
 623 /// The last substring will be whatever remains after splitting.
 624 ///
 625 /// `'r` is the lifetime of the compiled expression and `'t` is the lifetime
 626 /// of the string being split.
 627 pub struct RegexSplitsN<'r, 't> {
 628     splits: RegexSplits<'r, 't>,
 629     cur: uint,
 630     limit: uint,
 631 }
 632
 633 impl<'r, 't> Iterator<&'t str> for RegexSplitsN<'r, 't> {
 634     fn next(&mut self) -> Option<&'t str> {
 635         let text = self.splits.finder.search;
 636         if self.cur >= self.limit {
 637             None
 638         } else {
 639             self.cur += 1;
 640             if self.cur >= self.limit {
 641                 Some(text.slice(self.splits.last, text.len()))
 642             } else {
 643                 self.splits.next()
 644             }
 645         }
 646     }
 647 }
 648
 649 /// Captures represents a group of captured strings for a single match.
 650 ///
 651 /// The 0th capture always corresponds to the entire match. Each subsequent
 652 /// index corresponds to the next capture group in the regex.
 653 /// If a capture group is named, then the matched string is *also* available
 654 /// via the `name` method. (Note that the 0th capture is always unnamed and so
 655 /// must be accessed with the `at` method.)
 656 ///
 657 /// Positions returned from a capture group are always byte indices.
 658 ///
 659 /// `'t` is the lifetime of the matched text.
 660 pub struct Captures<'t> {
 661     text: &'t str,
 662     locs: CaptureLocs,
 663     named: Option<HashMap<String, uint>>,
 664 }
 665
 666 impl<'t> Captures<'t> {
 667     #[allow(experimental)]
 668     fn new(re: &Regex, search: &'t str, locs: CaptureLocs)
 669           -> Option<Captures<'t>> {
 670         if !has_match(&locs) {
 671             return None
 672         }
 673
 674         let named =
 675             if re.names_len() == 0 {
 676                 None
 677             } else {
 678                 let mut named = HashMap::new();
 679                 for (i, name) in re.names_iter().enumerate() {
 680                     match name {
 681                         None => {},
 682                         Some(name) => {
 683                             named.insert(name, i);
 684                         }
 685                     }
 686                 }
 687                 Some(named)
 688             };
 689         Some(Captures {
 690             text: search,
 691             locs: locs,
 692             named: named,
 693         })
 694     }
 695
 696     /// Returns the start and end positions of the Nth capture group.
 697     /// Returns `None` if `i` is not a valid capture group or if the capture
 698     /// group did not match anything.
 699     /// The positions returned are *always* byte indices with respect to the
 700     /// original string matched.
 701     pub fn pos(&self, i: uint) -> Option<(uint, uint)> {
 702         let (s, e) = (i * 2, i * 2 + 1);
 703         if e >= self.locs.len() || self.locs[s].is_none() {
 704             // VM guarantees that each pair of locations are both Some or None.
 705             return None
 706         }
 707         Some((self.locs[s].unwrap(), self.locs[e].unwrap()))
 708     }
 709
 710     /// Returns the matched string for the capture group `i`.
 711     /// If `i` isn't a valid capture group or didn't match anything, then the
 712     /// empty string is returned.
 713     pub fn at(&self, i: uint) -> &'t str {
 714         match self.pos(i) {
 715             None => "",
 716             Some((s, e)) => {
 717                 self.text.slice(s, e)
 718             }
 719         }
 720     }
 721
 722     /// Returns the matched string for the capture group named `name`.
 723     /// If `name` isn't a valid capture group or didn't match anything, then
 724     /// the empty string is returned.
 725     pub fn name(&self, name: &str) -> &'t str {
 726         match self.named {
 727             None => "",
 728             Some(ref h) => {
 729                 match h.get(name) {
 730                     None => "",
 731                     Some(i) => self.at(*i),
 732                 }
 733             }
 734         }
 735     }
 736
 737     /// Creates an iterator of all the capture groups in order of appearance
 738     /// in the regular expression.
 739     pub fn iter(&'t self) -> SubCaptures<'t> {
 740         SubCaptures { idx: 0, caps: self, }
 741     }
 742
 743     /// Creates an iterator of all the capture group positions in order of
 744     /// appearance in the regular expression. Positions are byte indices
 745     /// in terms of the original string matched.
 746     pub fn iter_pos(&'t self) -> SubCapturesPos<'t> {
 747         SubCapturesPos { idx: 0, caps: self, }
 748     }
 749
 750     /// Expands all instances of `$name` in `text` to the corresponding capture
 751     /// group `name`.
 752     ///
 753     /// `name` may be an integer corresponding to the index of the
 754     /// capture group (counted by order of opening parenthesis where `0` is the
 755     /// entire match) or it can be a name (consisting of letters, digits or
 756     /// underscores) corresponding to a named capture group.
 757     ///
 758     /// If `name` isn't a valid capture group (whether the name doesn't exist or
 759     /// isn't a valid index), then it is replaced with the empty string.
 760     ///
 761     /// To write a literal `$` use `$$`.
 762     pub fn expand(&self, text: &str) -> String {
 763         // How evil can you get?
 764         // FIXME: Don't use regexes for this. It's completely unnecessary.
 765         let re = Regex::new(r"(^|[^$]|\b)\$(\w+)").unwrap();
 766         let text = re.replace_all(text, |refs: &Captures| -> String {
 767             let (pre, name) = (refs.at(1), refs.at(2));
 768             format!("{}{}", pre,
 769                     match from_str::<uint>(name.as_slice()) {
 770                 None => self.name(name).to_string(),
 771                 Some(i) => self.at(i).to_string(),
 772             })
 773         });
 774         let re = Regex::new(r"\$\$").unwrap();
 775         re.replace_all(text.as_slice(), NoExpand("$"))
 776     }
 777
 778     /// Returns the number of captured groups.
 779     #[inline]
 780     pub fn len(&self) -> uint { self.locs.len() / 2 }
 781
 782     /// Returns if there are no captured groups.
 783     #[inline]
 784     pub fn is_empty(&self) -> bool { self.len() == 0 }
 785 }
 786
 787 /// An iterator over capture groups for a particular match of a regular
 788 /// expression.
 789 ///
 790 /// `'t` is the lifetime of the matched text.
 791 pub struct SubCaptures<'t> {
 792     idx: uint,
 793     caps: &'t Captures<'t>,
 794 }
 795
 796 impl<'t> Iterator<&'t str> for SubCaptures<'t> {
 797     fn next(&mut self) -> Option<&'t str> {
 798         if self.idx < self.caps.len() {
 799             self.idx += 1;
 800             Some(self.caps.at(self.idx - 1))
 801         } else {
 802             None
 803         }
 804     }
 805 }
 806
 807 /// An iterator over capture group positions for a particular match of a
 808 /// regular expression.
 809 ///
 810 /// Positions are byte indices in terms of the original string matched.
 811 ///
 812 /// `'t` is the lifetime of the matched text.
 813 pub struct SubCapturesPos<'t> {
 814     idx: uint,
 815     caps: &'t Captures<'t>,
 816 }
 817
 818 impl<'t> Iterator<Option<(uint, uint)>> for SubCapturesPos<'t> {
 819     fn next(&mut self) -> Option<Option<(uint, uint)>> {
 820         if self.idx < self.caps.len() {
 821             self.idx += 1;
 822             Some(self.caps.pos(self.idx - 1))
 823         } else {
 824             None
 825         }
 826     }
 827 }
 828
 829 /// An iterator that yields all non-overlapping capture groups matching a
 830 /// particular regular expression.
 831 ///
 832 /// The iterator stops when no more matches can be found.
 833 ///
 834 /// `'r` is the lifetime of the compiled expression and `'t` is the lifetime
 835 /// of the matched string.
 836 pub struct FindCaptures<'r, 't> {
 837     re: &'r Regex,
 838     search: &'t str,
 839     last_match: Option<uint>,
 840     last_end: uint,
 841 }
 842
 843 impl<'r, 't> Iterator<Captures<'t>> for FindCaptures<'r, 't> {
 844     fn next(&mut self) -> Option<Captures<'t>> {
 845         if self.last_end > self.search.len() {
 846             return None
 847         }
 848
 849         let caps = exec_slice(self.re, Submatches, self.search,
 850                               self.last_end, self.search.len());
 851         let (s, e) =
 852             if !has_match(&caps) {
 853                 return None
 854             } else {
 855                 (caps[0].unwrap(), caps[1].unwrap())
 856             };
 857
 858         // Don't accept empty matches immediately following a match.
 859         // i.e., no infinite loops please.
 860         if e == s && Some(self.last_end) == self.last_match {
 861             self.last_end += 1;
 862             return self.next()
 863         }
 864         self.last_end = e;
 865         self.last_match = Some(self.last_end);
 866         Captures::new(self.re, self.search, caps)
 867     }
 868 }
 869
 870 /// An iterator over all non-overlapping matches for a particular string.
 871 ///
 872 /// The iterator yields a tuple of integers corresponding to the start and end
 873 /// of the match. The indices are byte offsets. The iterator stops when no more
 874 /// matches can be found.
 875 ///
 876 /// `'r` is the lifetime of the compiled expression and `'t` is the lifetime
 877 /// of the matched string.
 878 pub struct FindMatches<'r, 't> {
 879     re: &'r Regex,
 880     search: &'t str,
 881     last_match: Option<uint>,
 882     last_end: uint,
 883 }
 884
 885 impl<'r, 't> Iterator<(uint, uint)> for FindMatches<'r, 't> {
 886     fn next(&mut self) -> Option<(uint, uint)> {
 887         if self.last_end > self.search.len() {
 888             return None
 889         }
 890
 891         let caps = exec_slice(self.re, Location, self.search,
 892                               self.last_end, self.search.len());
 893         let (s, e) =
 894             if !has_match(&caps) {
 895                 return None
 896             } else {
 897                 (caps[0].unwrap(), caps[1].unwrap())
 898             };
 899
 900         // Don't accept empty matches immediately following a match.
 901         // i.e., no infinite loops please.
 902         if e == s && Some(self.last_end) == self.last_match {
 903             self.last_end += 1;
 904             return self.next()
 905         }
 906         self.last_end = e;
 907         self.last_match = Some(self.last_end);
 908         Some((s, e))
 909     }
 910 }
 911
 912 fn exec(re: &Regex, which: MatchKind, input: &str) -> CaptureLocs {
 913     exec_slice(re, which, input, 0, input.len())
 914 }
 915
 916 fn exec_slice(re: &Regex, which: MatchKind,
 917               input: &str, s: uint, e: uint) -> CaptureLocs {
 918     match *re {
 919         Dynamic(ExDynamic { ref prog, .. }) => vm::run(which, prog, input, s, e),
 920         Native(ExNative { prog, .. }) => prog(which, input, s, e),
 921     }
 922 }
 923
 924 #[inline]
 925 fn has_match(caps: &CaptureLocs) -> bool {
 926     caps.len() >= 2 && caps[0].is_some() && caps[1].is_some()
 927 }