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