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