src/libregex/re.rs

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