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