vendor/globset-0.2.1/src/lib.rs

   1 /*!
   2 The globset crate provides cross platform single glob and glob set matching.
   3
   4 Glob set matching is the process of matching one or more glob patterns against
   5 a single candidate path simultaneously, and returning all of the globs that
   6 matched. For example, given this set of globs:
   7
   8 ```ignore
   9 *.rs
  10 src/lib.rs
  11 src/**/foo.rs
  12 ```
  13
  14 and a path `src/bar/baz/foo.rs`, then the set would report the first and third
  15 globs as matching.
  16
  17 # Example: one glob
  18
  19 This example shows how to match a single glob against a single file path.
  20
  21 ```
  22 # fn example() -> Result<(), globset::Error> {
  23 use globset::Glob;
  24
  25 let glob = try!(Glob::new("*.rs")).compile_matcher();
  26
  27 assert!(glob.is_match("foo.rs"));
  28 assert!(glob.is_match("foo/bar.rs"));
  29 assert!(!glob.is_match("Cargo.toml"));
  30 # Ok(()) } example().unwrap();
  31 ```
  32
  33 # Example: configuring a glob matcher
  34
  35 This example shows how to use a `GlobBuilder` to configure aspects of match
  36 semantics. In this example, we prevent wildcards from matching path separators.
  37
  38 ```
  39 # fn example() -> Result<(), globset::Error> {
  40 use globset::GlobBuilder;
  41
  42 let glob = try!(GlobBuilder::new("*.rs")
  43     .literal_separator(true).build()).compile_matcher();
  44
  45 assert!(glob.is_match("foo.rs"));
  46 assert!(!glob.is_match("foo/bar.rs")); // no longer matches
  47 assert!(!glob.is_match("Cargo.toml"));
  48 # Ok(()) } example().unwrap();
  49 ```
  50
  51 # Example: match multiple globs at once
  52
  53 This example shows how to match multiple glob patterns at once.
  54
  55 ```
  56 # fn example() -> Result<(), globset::Error> {
  57 use globset::{Glob, GlobSetBuilder};
  58
  59 let mut builder = GlobSetBuilder::new();
  60 // A GlobBuilder can be used to configure each glob's match semantics
  61 // independently.
  62 builder.add(try!(Glob::new("*.rs")));
  63 builder.add(try!(Glob::new("src/lib.rs")));
  64 builder.add(try!(Glob::new("src/**/foo.rs")));
  65 let set = try!(builder.build());
  66
  67 assert_eq!(set.matches("src/bar/baz/foo.rs"), vec![0, 2]);
  68 # Ok(()) } example().unwrap();
  69 ```
  70
  71 # Syntax
  72
  73 Standard Unix-style glob syntax is supported:
  74
  75 * `?` matches any single character. (If the `literal_separator` option is
  76   enabled, then `?` can never match a path separator.)
  77 * `*` matches zero or more characters. (If the `literal_separator` option is
  78   enabled, then `*` can never match a path separator.)
  79 * `**` recursively matches directories but are only legal in three situations.
  80   First, if the glob starts with <code>\*\*&#x2F;</code>, then it matches
  81   all directories. For example, <code>\*\*&#x2F;foo</code> matches `foo`
  82   and `bar/foo` but not `foo/bar`. Secondly, if the glob ends with
  83   <code>&#x2F;\*\*</code>, then it matches all sub-entries. For example,
  84   <code>foo&#x2F;\*\*</code> matches `foo/a` and `foo/a/b`, but not `foo`.
  85   Thirdly, if the glob contains <code>&#x2F;\*\*&#x2F;</code> anywhere within
  86   the pattern, then it matches zero or more directories. Using `**` anywhere
  87   else is illegal (N.B. the glob `**` is allowed and means "match everything").
  88 * `{a,b}` matches `a` or `b` where `a` and `b` are arbitrary glob patterns.
  89   (N.B. Nesting `{...}` is not currently allowed.)
  90 * `[ab]` matches `a` or `b` where `a` and `b` are characters. Use
  91   `[!ab]` to match any character except for `a` and `b`.
  92 * Metacharacters such as `*` and `?` can be escaped with character class
  93   notation. e.g., `[*]` matches `*`.
  94
  95 A `GlobBuilder` can be used to prevent wildcards from matching path separators,
  96 or to enable case insensitive matching.
  97 */
  98
  99 #![deny(missing_docs)]
 100
 101 extern crate aho_corasick;
 102 extern crate fnv;
 103 #[macro_use]
 104 extern crate log;
 105 extern crate memchr;
 106 extern crate regex;
 107
 108 use std::borrow::Cow;
 109 use std::collections::{BTreeMap, HashMap};
 110 use std::error::Error as StdError;
 111 use std::ffi::{OsStr, OsString};
 112 use std::fmt;
 113 use std::hash;
 114 use std::path::Path;
 115 use std::str;
 116
 117 use aho_corasick::{Automaton, AcAutomaton, FullAcAutomaton};
 118 use regex::bytes::{Regex, RegexBuilder, RegexSet};
 119
 120 use pathutil::{
 121     file_name, file_name_ext, normalize_path, os_str_bytes, path_bytes,
 122 };
 123 use glob::MatchStrategy;
 124 pub use glob::{Glob, GlobBuilder, GlobMatcher};
 125
 126 mod glob;
 127 mod pathutil;
 128
 129 /// Represents an error that can occur when parsing a glob pattern.
 130 #[derive(Clone, Debug, Eq, PartialEq)]
 131 pub struct Error {
 132     /// The original glob provided by the caller.
 133     glob: Option<String>,
 134     /// The kind of error.
 135     kind: ErrorKind,
 136 }
 137
 138 /// The kind of error that can occur when parsing a glob pattern.
 139 #[derive(Clone, Debug, Eq, PartialEq)]
 140 pub enum ErrorKind {
 141     /// Occurs when a use of `**` is invalid. Namely, `**` can only appear
 142     /// adjacent to a path separator, or the beginning/end of a glob.
 143     InvalidRecursive,
 144     /// Occurs when a character class (e.g., `[abc]`) is not closed.
 145     UnclosedClass,
 146     /// Occurs when a range in a character (e.g., `[a-z]`) is invalid. For
 147     /// example, if the range starts with a lexicographically larger character
 148     /// than it ends with.
 149     InvalidRange(char, char),
 150     /// Occurs when a `}` is found without a matching `{`.
 151     UnopenedAlternates,
 152     /// Occurs when a `{` is found without a matching `}`.
 153     UnclosedAlternates,
 154     /// Occurs when an alternating group is nested inside another alternating
 155     /// group, e.g., `{{a,b},{c,d}}`.
 156     NestedAlternates,
 157     /// An error associated with parsing or compiling a regex.
 158     Regex(String),
 159 }
 160
 161 impl StdError for Error {
 162     fn description(&self) -> &str {
 163         self.kind.description()
 164     }
 165 }
 166
 167 impl Error {
 168     /// Return the glob that caused this error, if one exists.
 169     pub fn glob(&self) -> Option<&str> {
 170         self.glob.as_ref().map(|s| &**s)
 171     }
 172
 173     /// Return the kind of this error.
 174     pub fn kind(&self) -> &ErrorKind {
 175         &self.kind
 176     }
 177 }
 178
 179 impl ErrorKind {
 180     fn description(&self) -> &str {
 181         match *self {
 182             ErrorKind::InvalidRecursive => {
 183                 "invalid use of **; must be one path component"
 184             }
 185             ErrorKind::UnclosedClass => {
 186                 "unclosed character class; missing ']'"
 187             }
 188             ErrorKind::InvalidRange(_, _) => {
 189                 "invalid character range"
 190             }
 191             ErrorKind::UnopenedAlternates => {
 192                 "unopened alternate group; missing '{' \
 193                 (maybe escape '}' with '[}]'?)"
 194             }
 195             ErrorKind::UnclosedAlternates => {
 196                 "unclosed alternate group; missing '}' \
 197                 (maybe escape '{' with '[{]'?)"
 198             }
 199             ErrorKind::NestedAlternates => {
 200                 "nested alternate groups are not allowed"
 201             }
 202             ErrorKind::Regex(ref err) => err,
 203         }
 204     }
 205 }
 206
 207 impl fmt::Display for Error {
 208     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 209         match self.glob {
 210             None => self.kind.fmt(f),
 211             Some(ref glob) => {
 212                 write!(f, "error parsing glob '{}': {}", glob, self.kind)
 213             }
 214         }
 215     }
 216 }
 217
 218 impl fmt::Display for ErrorKind {
 219     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 220         match *self {
 221             ErrorKind::InvalidRecursive
 222             | ErrorKind::UnclosedClass
 223             | ErrorKind::UnopenedAlternates
 224             | ErrorKind::UnclosedAlternates
 225             | ErrorKind::NestedAlternates
 226             | ErrorKind::Regex(_) => {
 227                 write!(f, "{}", self.description())
 228             }
 229             ErrorKind::InvalidRange(s, e) => {
 230                 write!(f, "invalid range; '{}' > '{}'", s, e)
 231             }
 232         }
 233     }
 234 }
 235
 236 fn new_regex(pat: &str) -> Result<Regex, Error> {
 237     RegexBuilder::new(pat)
 238         .dot_matches_new_line(true)
 239         .size_limit(10 * (1 << 20))
 240         .dfa_size_limit(10 * (1 << 20))
 241         .build()
 242         .map_err(|err| {
 243             Error {
 244                 glob: Some(pat.to_string()),
 245                 kind: ErrorKind::Regex(err.to_string()),
 246             }
 247         })
 248 }
 249
 250 fn new_regex_set<I, S>(pats: I) -> Result<RegexSet, Error>
 251         where S: AsRef<str>, I: IntoIterator<Item=S> {
 252     RegexSet::new(pats).map_err(|err| {
 253         Error {
 254             glob: None,
 255             kind: ErrorKind::Regex(err.to_string()),
 256         }
 257     })
 258 }
 259
 260 type Fnv = hash::BuildHasherDefault<fnv::FnvHasher>;
 261
 262 /// GlobSet represents a group of globs that can be matched together in a
 263 /// single pass.
 264 #[derive(Clone, Debug)]
 265 pub struct GlobSet {
 266     len: usize,
 267     strats: Vec<GlobSetMatchStrategy>,
 268 }
 269
 270 impl GlobSet {
 271     /// Returns true if this set is empty, and therefore matches nothing.
 272     pub fn is_empty(&self) -> bool {
 273         self.len == 0
 274     }
 275
 276     /// Returns the number of globs in this set.
 277     pub fn len(&self) -> usize {
 278         self.len
 279     }
 280
 281     /// Returns true if any glob in this set matches the path given.
 282     pub fn is_match<P: AsRef<Path>>(&self, path: P) -> bool {
 283         self.is_match_candidate(&Candidate::new(path.as_ref()))
 284     }
 285
 286     /// Returns true if any glob in this set matches the path given.
 287     ///
 288     /// This takes a Candidate as input, which can be used to amortize the
 289     /// cost of preparing a path for matching.
 290     pub fn is_match_candidate(&self, path: &Candidate) -> bool {
 291         if self.is_empty() {
 292             return false;
 293         }
 294         for strat in &self.strats {
 295             if strat.is_match(path) {
 296                 return true;
 297             }
 298         }
 299         false
 300     }
 301
 302     /// Returns the sequence number of every glob pattern that matches the
 303     /// given path.
 304     pub fn matches<P: AsRef<Path>>(&self, path: P) -> Vec<usize> {
 305         self.matches_candidate(&Candidate::new(path.as_ref()))
 306     }
 307
 308     /// Returns the sequence number of every glob pattern that matches the
 309     /// given path.
 310     ///
 311     /// This takes a Candidate as input, which can be used to amortize the
 312     /// cost of preparing a path for matching.
 313     pub fn matches_candidate(&self, path: &Candidate) -> Vec<usize> {
 314         let mut into = vec![];
 315         if self.is_empty() {
 316             return into;
 317         }
 318         self.matches_candidate_into(path, &mut into);
 319         into
 320     }
 321
 322     /// Adds the sequence number of every glob pattern that matches the given
 323     /// path to the vec given.
 324     ///
 325     /// `into` is is cleared before matching begins, and contains the set of
 326     /// sequence numbers (in ascending order) after matching ends. If no globs
 327     /// were matched, then `into` will be empty.
 328     pub fn matches_into<P: AsRef<Path>>(
 329         &self,
 330         path: P,
 331         into: &mut Vec<usize>,
 332     ) {
 333         self.matches_candidate_into(&Candidate::new(path.as_ref()), into);
 334     }
 335
 336     /// Adds the sequence number of every glob pattern that matches the given
 337     /// path to the vec given.
 338     ///
 339     /// `into` is is cleared before matching begins, and contains the set of
 340     /// sequence numbers (in ascending order) after matching ends. If no globs
 341     /// were matched, then `into` will be empty.
 342     ///
 343     /// This takes a Candidate as input, which can be used to amortize the
 344     /// cost of preparing a path for matching.
 345     pub fn matches_candidate_into(
 346         &self,
 347         path: &Candidate,
 348         into: &mut Vec<usize>,
 349     ) {
 350         into.clear();
 351         if self.is_empty() {
 352             return;
 353         }
 354         for strat in &self.strats {
 355             strat.matches_into(path, into);
 356         }
 357         into.sort();
 358         into.dedup();
 359     }
 360
 361     fn new(pats: &[Glob]) -> Result<GlobSet, Error> {
 362         if pats.is_empty() {
 363             return Ok(GlobSet { len: 0, strats: vec![] });
 364         }
 365         let mut lits = LiteralStrategy::new();
 366         let mut base_lits = BasenameLiteralStrategy::new();
 367         let mut exts = ExtensionStrategy::new();
 368         let mut prefixes = MultiStrategyBuilder::new();
 369         let mut suffixes = MultiStrategyBuilder::new();
 370         let mut required_exts = RequiredExtensionStrategyBuilder::new();
 371         let mut regexes = MultiStrategyBuilder::new();
 372         for (i, p) in pats.iter().enumerate() {
 373             match MatchStrategy::new(p) {
 374                 MatchStrategy::Literal(lit) => {
 375                     lits.add(i, lit);
 376                 }
 377                 MatchStrategy::BasenameLiteral(lit) => {
 378                     base_lits.add(i, lit);
 379                 }
 380                 MatchStrategy::Extension(ext) => {
 381                     exts.add(i, ext);
 382                 }
 383                 MatchStrategy::Prefix(prefix) => {
 384                     prefixes.add(i, prefix);
 385                 }
 386                 MatchStrategy::Suffix { suffix, component } => {
 387                     if component {
 388                         lits.add(i, suffix[1..].to_string());
 389                     }
 390                     suffixes.add(i, suffix);
 391                 }
 392                 MatchStrategy::RequiredExtension(ext) => {
 393                     required_exts.add(i, ext, p.regex().to_owned());
 394                 }
 395                 MatchStrategy::Regex => {
 396                     debug!("glob converted to regex: {:?}", p);
 397                     regexes.add(i, p.regex().to_owned());
 398                 }
 399             }
 400         }
 401         debug!("built glob set; {} literals, {} basenames, {} extensions, \
 402                 {} prefixes, {} suffixes, {} required extensions, {} regexes",
 403                 lits.0.len(), base_lits.0.len(), exts.0.len(),
 404                 prefixes.literals.len(), suffixes.literals.len(),
 405                 required_exts.0.len(), regexes.literals.len());
 406         Ok(GlobSet {
 407             len: pats.len(),
 408             strats: vec![
 409                 GlobSetMatchStrategy::Extension(exts),
 410                 GlobSetMatchStrategy::BasenameLiteral(base_lits),
 411                 GlobSetMatchStrategy::Literal(lits),
 412                 GlobSetMatchStrategy::Suffix(suffixes.suffix()),
 413                 GlobSetMatchStrategy::Prefix(prefixes.prefix()),
 414                 GlobSetMatchStrategy::RequiredExtension(
 415                     try!(required_exts.build())),
 416                 GlobSetMatchStrategy::Regex(try!(regexes.regex_set())),
 417             ],
 418         })
 419     }
 420 }
 421
 422 /// GlobSetBuilder builds a group of patterns that can be used to
 423 /// simultaneously match a file path.
 424 pub struct GlobSetBuilder {
 425     pats: Vec<Glob>,
 426 }
 427
 428 impl GlobSetBuilder {
 429     /// Create a new GlobSetBuilder. A GlobSetBuilder can be used to add new
 430     /// patterns. Once all patterns have been added, `build` should be called
 431     /// to produce a `GlobSet`, which can then be used for matching.
 432     pub fn new() -> GlobSetBuilder {
 433         GlobSetBuilder { pats: vec![] }
 434     }
 435
 436     /// Builds a new matcher from all of the glob patterns added so far.
 437     ///
 438     /// Once a matcher is built, no new patterns can be added to it.
 439     pub fn build(&self) -> Result<GlobSet, Error> {
 440         GlobSet::new(&self.pats)
 441     }
 442
 443     /// Add a new pattern to this set.
 444     #[allow(dead_code)]
 445     pub fn add(&mut self, pat: Glob) -> &mut GlobSetBuilder {
 446         self.pats.push(pat);
 447         self
 448     }
 449 }
 450
 451 /// A candidate path for matching.
 452 ///
 453 /// All glob matching in this crate operates on `Candidate` values.
 454 /// Constructing candidates has a very small cost associated with it, so
 455 /// callers may find it beneficial to amortize that cost when matching a single
 456 /// path against multiple globs or sets of globs.
 457 #[derive(Clone, Debug)]
 458 pub struct Candidate<'a> {
 459     path: Cow<'a, [u8]>,
 460     basename: Cow<'a, [u8]>,
 461     ext: &'a OsStr,
 462 }
 463
 464 impl<'a> Candidate<'a> {
 465     /// Create a new candidate for matching from the given path.
 466     pub fn new<P: AsRef<Path> + ?Sized>(path: &'a P) -> Candidate<'a> {
 467         let path = path.as_ref();
 468         let basename = file_name(path).unwrap_or(OsStr::new(""));
 469         Candidate {
 470             path: normalize_path(path_bytes(path)),
 471             basename: os_str_bytes(basename),
 472             ext: file_name_ext(basename).unwrap_or(OsStr::new("")),
 473         }
 474     }
 475
 476     fn path_prefix(&self, max: usize) -> &[u8] {
 477         if self.path.len() <= max {
 478             &*self.path
 479         } else {
 480             &self.path[..max]
 481         }
 482     }
 483
 484     fn path_suffix(&self, max: usize) -> &[u8] {
 485         if self.path.len() <= max {
 486             &*self.path
 487         } else {
 488             &self.path[self.path.len() - max..]
 489         }
 490     }
 491 }
 492
 493 #[derive(Clone, Debug)]
 494 enum GlobSetMatchStrategy {
 495     Literal(LiteralStrategy),
 496     BasenameLiteral(BasenameLiteralStrategy),
 497     Extension(ExtensionStrategy),
 498     Prefix(PrefixStrategy),
 499     Suffix(SuffixStrategy),
 500     RequiredExtension(RequiredExtensionStrategy),
 501     Regex(RegexSetStrategy),
 502 }
 503
 504 impl GlobSetMatchStrategy {
 505     fn is_match(&self, candidate: &Candidate) -> bool {
 506         use self::GlobSetMatchStrategy::*;
 507         match *self {
 508             Literal(ref s) => s.is_match(candidate),
 509             BasenameLiteral(ref s) => s.is_match(candidate),
 510             Extension(ref s) => s.is_match(candidate),
 511             Prefix(ref s) => s.is_match(candidate),
 512             Suffix(ref s) => s.is_match(candidate),
 513             RequiredExtension(ref s) => s.is_match(candidate),
 514             Regex(ref s) => s.is_match(candidate),
 515         }
 516     }
 517
 518     fn matches_into(&self, candidate: &Candidate, matches: &mut Vec<usize>) {
 519         use self::GlobSetMatchStrategy::*;
 520         match *self {
 521             Literal(ref s) => s.matches_into(candidate, matches),
 522             BasenameLiteral(ref s) => s.matches_into(candidate, matches),
 523             Extension(ref s) => s.matches_into(candidate, matches),
 524             Prefix(ref s) => s.matches_into(candidate, matches),
 525             Suffix(ref s) => s.matches_into(candidate, matches),
 526             RequiredExtension(ref s) => s.matches_into(candidate, matches),
 527             Regex(ref s) => s.matches_into(candidate, matches),
 528         }
 529     }
 530 }
 531
 532 #[derive(Clone, Debug)]
 533 struct LiteralStrategy(BTreeMap<Vec<u8>, Vec<usize>>);
 534
 535 impl LiteralStrategy {
 536     fn new() -> LiteralStrategy {
 537         LiteralStrategy(BTreeMap::new())
 538     }
 539
 540     fn add(&mut self, global_index: usize, lit: String) {
 541         self.0.entry(lit.into_bytes()).or_insert(vec![]).push(global_index);
 542     }
 543
 544     fn is_match(&self, candidate: &Candidate) -> bool {
 545         self.0.contains_key(&*candidate.path)
 546     }
 547
 548     #[inline(never)]
 549     fn matches_into(&self, candidate: &Candidate, matches: &mut Vec<usize>) {
 550         if let Some(hits) = self.0.get(&*candidate.path) {
 551             matches.extend(hits);
 552         }
 553     }
 554 }
 555
 556 #[derive(Clone, Debug)]
 557 struct BasenameLiteralStrategy(BTreeMap<Vec<u8>, Vec<usize>>);
 558
 559 impl BasenameLiteralStrategy {
 560     fn new() -> BasenameLiteralStrategy {
 561         BasenameLiteralStrategy(BTreeMap::new())
 562     }
 563
 564     fn add(&mut self, global_index: usize, lit: String) {
 565         self.0.entry(lit.into_bytes()).or_insert(vec![]).push(global_index);
 566     }
 567
 568     fn is_match(&self, candidate: &Candidate) -> bool {
 569         if candidate.basename.is_empty() {
 570             return false;
 571         }
 572         self.0.contains_key(&*candidate.basename)
 573     }
 574
 575     #[inline(never)]
 576     fn matches_into(&self, candidate: &Candidate, matches: &mut Vec<usize>) {
 577         if candidate.basename.is_empty() {
 578             return;
 579         }
 580         if let Some(hits) = self.0.get(&*candidate.basename) {
 581             matches.extend(hits);
 582         }
 583     }
 584 }
 585
 586 #[derive(Clone, Debug)]
 587 struct ExtensionStrategy(HashMap<OsString, Vec<usize>, Fnv>);
 588
 589 impl ExtensionStrategy {
 590     fn new() -> ExtensionStrategy {
 591         ExtensionStrategy(HashMap::with_hasher(Fnv::default()))
 592     }
 593
 594     fn add(&mut self, global_index: usize, ext: OsString) {
 595         self.0.entry(ext).or_insert(vec![]).push(global_index);
 596     }
 597
 598     fn is_match(&self, candidate: &Candidate) -> bool {
 599         if candidate.ext.is_empty() {
 600             return false;
 601         }
 602         self.0.contains_key(candidate.ext)
 603     }
 604
 605     #[inline(never)]
 606     fn matches_into(&self, candidate: &Candidate, matches: &mut Vec<usize>) {
 607         if candidate.ext.is_empty() {
 608             return;
 609         }
 610         if let Some(hits) = self.0.get(candidate.ext) {
 611             matches.extend(hits);
 612         }
 613     }
 614 }
 615
 616 #[derive(Clone, Debug)]
 617 struct PrefixStrategy {
 618     matcher: FullAcAutomaton<Vec<u8>>,
 619     map: Vec<usize>,
 620     longest: usize,
 621 }
 622
 623 impl PrefixStrategy {
 624     fn is_match(&self, candidate: &Candidate) -> bool {
 625         let path = candidate.path_prefix(self.longest);
 626         for m in self.matcher.find_overlapping(path) {
 627             if m.start == 0 {
 628                 return true;
 629             }
 630         }
 631         false
 632     }
 633
 634     fn matches_into(&self, candidate: &Candidate, matches: &mut Vec<usize>) {
 635         let path = candidate.path_prefix(self.longest);
 636         for m in self.matcher.find_overlapping(path) {
 637             if m.start == 0 {
 638                 matches.push(self.map[m.pati]);
 639             }
 640         }
 641     }
 642 }
 643
 644 #[derive(Clone, Debug)]
 645 struct SuffixStrategy {
 646     matcher: FullAcAutomaton<Vec<u8>>,
 647     map: Vec<usize>,
 648     longest: usize,
 649 }
 650
 651 impl SuffixStrategy {
 652     fn is_match(&self, candidate: &Candidate) -> bool {
 653         let path = candidate.path_suffix(self.longest);
 654         for m in self.matcher.find_overlapping(path) {
 655             if m.end == path.len() {
 656                 return true;
 657             }
 658         }
 659         false
 660     }
 661
 662     fn matches_into(&self, candidate: &Candidate, matches: &mut Vec<usize>) {
 663         let path = candidate.path_suffix(self.longest);
 664         for m in self.matcher.find_overlapping(path) {
 665             if m.end == path.len() {
 666                 matches.push(self.map[m.pati]);
 667             }
 668         }
 669     }
 670 }
 671
 672 #[derive(Clone, Debug)]
 673 struct RequiredExtensionStrategy(HashMap<OsString, Vec<(usize, Regex)>, Fnv>);
 674
 675 impl RequiredExtensionStrategy {
 676     fn is_match(&self, candidate: &Candidate) -> bool {
 677         if candidate.ext.is_empty() {
 678             return false;
 679         }
 680         match self.0.get(candidate.ext) {
 681             None => false,
 682             Some(regexes) => {
 683                 for &(_, ref re) in regexes {
 684                     if re.is_match(&*candidate.path) {
 685                         return true;
 686                     }
 687                 }
 688                 false
 689             }
 690         }
 691     }
 692
 693     #[inline(never)]
 694     fn matches_into(&self, candidate: &Candidate, matches: &mut Vec<usize>) {
 695         if candidate.ext.is_empty() {
 696             return;
 697         }
 698         if let Some(regexes) = self.0.get(candidate.ext) {
 699             for &(global_index, ref re) in regexes {
 700                 if re.is_match(&*candidate.path) {
 701                     matches.push(global_index);
 702                 }
 703             }
 704         }
 705     }
 706 }
 707
 708 #[derive(Clone, Debug)]
 709 struct RegexSetStrategy {
 710     matcher: RegexSet,
 711     map: Vec<usize>,
 712 }
 713
 714 impl RegexSetStrategy {
 715     fn is_match(&self, candidate: &Candidate) -> bool {
 716         self.matcher.is_match(&*candidate.path)
 717     }
 718
 719     fn matches_into(&self, candidate: &Candidate, matches: &mut Vec<usize>) {
 720         for i in self.matcher.matches(&*candidate.path) {
 721             matches.push(self.map[i]);
 722         }
 723     }
 724 }
 725
 726 #[derive(Clone, Debug)]
 727 struct MultiStrategyBuilder {
 728     literals: Vec<String>,
 729     map: Vec<usize>,
 730     longest: usize,
 731 }
 732
 733 impl MultiStrategyBuilder {
 734     fn new() -> MultiStrategyBuilder {
 735         MultiStrategyBuilder {
 736             literals: vec![],
 737             map: vec![],
 738             longest: 0,
 739         }
 740     }
 741
 742     fn add(&mut self, global_index: usize, literal: String) {
 743         if literal.len() > self.longest {
 744             self.longest = literal.len();
 745         }
 746         self.map.push(global_index);
 747         self.literals.push(literal);
 748     }
 749
 750     fn prefix(self) -> PrefixStrategy {
 751         let it = self.literals.into_iter().map(|s| s.into_bytes());
 752         PrefixStrategy {
 753             matcher: AcAutomaton::new(it).into_full(),
 754             map: self.map,
 755             longest: self.longest,
 756         }
 757     }
 758
 759     fn suffix(self) -> SuffixStrategy {
 760         let it = self.literals.into_iter().map(|s| s.into_bytes());
 761         SuffixStrategy {
 762             matcher: AcAutomaton::new(it).into_full(),
 763             map: self.map,
 764             longest: self.longest,
 765         }
 766     }
 767
 768     fn regex_set(self) -> Result<RegexSetStrategy, Error> {
 769         Ok(RegexSetStrategy {
 770             matcher: try!(new_regex_set(self.literals)),
 771             map: self.map,
 772         })
 773     }
 774 }
 775
 776 #[derive(Clone, Debug)]
 777 struct RequiredExtensionStrategyBuilder(
 778     HashMap<OsString, Vec<(usize, String)>>,
 779 );
 780
 781 impl RequiredExtensionStrategyBuilder {
 782     fn new() -> RequiredExtensionStrategyBuilder {
 783         RequiredExtensionStrategyBuilder(HashMap::new())
 784     }
 785
 786     fn add(&mut self, global_index: usize, ext: OsString, regex: String) {
 787         self.0.entry(ext).or_insert(vec![]).push((global_index, regex));
 788     }
 789
 790     fn build(self) -> Result<RequiredExtensionStrategy, Error> {
 791         let mut exts = HashMap::with_hasher(Fnv::default());
 792         for (ext, regexes) in self.0.into_iter() {
 793             exts.insert(ext.clone(), vec![]);
 794             for (global_index, regex) in regexes {
 795                 let compiled = try!(new_regex(&regex));
 796                 exts.get_mut(&ext).unwrap().push((global_index, compiled));
 797             }
 798         }
 799         Ok(RequiredExtensionStrategy(exts))
 800     }
 801 }
 802
 803 #[cfg(test)]
 804 mod tests {
 805     use super::GlobSetBuilder;
 806     use glob::Glob;
 807
 808     #[test]
 809     fn set_works() {
 810         let mut builder = GlobSetBuilder::new();
 811         builder.add(Glob::new("src/**/*.rs").unwrap());
 812         builder.add(Glob::new("*.c").unwrap());
 813         builder.add(Glob::new("src/lib.rs").unwrap());
 814         let set = builder.build().unwrap();
 815
 816         assert!(set.is_match("foo.c"));
 817         assert!(set.is_match("src/foo.c"));
 818         assert!(!set.is_match("foo.rs"));
 819         assert!(!set.is_match("tests/foo.rs"));
 820         assert!(set.is_match("src/foo.rs"));
 821         assert!(set.is_match("src/grep/src/main.rs"));
 822
 823         let matches = set.matches("src/lib.rs");
 824         assert_eq!(2, matches.len());
 825         assert_eq!(0, matches[0]);
 826         assert_eq!(2, matches[1]);
 827     }
 828
 829     #[test]
 830     fn empty_set_works() {
 831         let set = GlobSetBuilder::new().build().unwrap();
 832         assert!(!set.is_match(""));
 833         assert!(!set.is_match("a"));
 834     }
 835 }