src/libglob/lib.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 /*!
  12  * Support for matching file paths against Unix shell style patterns.
  13  *
  14  * The `glob` and `glob_with` functions, in concert with the `Paths`
  15  * type, allow querying the filesystem for all files that match a particular
  16  * pattern - just like the libc `glob` function (for an example see the `glob`
  17  * documentation). The methods on the `Pattern` type provide functionality
  18  * for checking if individual paths match a particular pattern - in a similar
  19  * manner to the libc `fnmatch` function
  20  *
  21  * For consistency across platforms, and for Windows support, this module
  22  * is implemented entirely in Rust rather than deferring to the libc
  23  * `glob`/`fnmatch` functions.
  24  */
  25
  26 #![crate_id = "glob#0.11-pre"]
  27 #![crate_type = "rlib"]
  28 #![crate_type = "dylib"]
  29 #![license = "MIT/ASL2"]
  30 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  31        html_favicon_url = "http://www.rust-lang.org/favicon.ico",
  32        html_root_url = "http://static.rust-lang.org/doc/master")]
  33
  34 #![deny(deprecated_owned_vector)]
  35
  36 use std::cell::Cell;
  37 use std::{cmp, os, path};
  38 use std::io::fs;
  39 use std::path::is_sep;
  40 use std::strbuf::StrBuf;
  41
  42 /**
  43  * An iterator that yields Paths from the filesystem that match a particular
  44  * pattern - see the `glob` function for more details.
  45  */
  46 pub struct Paths {
  47     root: Path,
  48     dir_patterns: Vec<Pattern>,
  49     require_dir: bool,
  50     options: MatchOptions,
  51     todo: Vec<(Path,uint)>,
  52 }
  53
  54 ///
  55 /// Return an iterator that produces all the Paths that match the given pattern,
  56 /// which may be absolute or relative to the current working directory.
  57 ///
  58 /// This method uses the default match options and is equivalent to calling
  59 /// `glob_with(pattern, MatchOptions::new())`. Use `glob_with` directly if you
  60 /// want to use non-default match options.
  61 ///
  62 /// # Example
  63 ///
  64 /// Consider a directory `/media/pictures` containing only the files `kittens.jpg`,
  65 /// `puppies.jpg` and `hamsters.gif`:
  66 ///
  67 /// ```rust
  68 /// use glob::glob;
  69 ///
  70 /// for path in glob("/media/pictures/*.jpg") {
  71 ///     println!("{}", path.display());
  72 /// }
  73 /// ```
  74 ///
  75 /// The above code will print:
  76 ///
  77 /// ```ignore
  78 /// /media/pictures/kittens.jpg
  79 /// /media/pictures/puppies.jpg
  80 /// ```
  81 ///
  82 pub fn glob(pattern: &str) -> Paths {
  83     glob_with(pattern, MatchOptions::new())
  84 }
  85
  86 /**
  87  * Return an iterator that produces all the Paths that match the given pattern,
  88  * which may be absolute or relative to the current working directory.
  89  *
  90  * This function accepts Unix shell style patterns as described by `Pattern::new(..)`.
  91  * The options given are passed through unchanged to `Pattern::matches_with(..)` with
  92  * the exception that `require_literal_separator` is always set to `true` regardless of the
  93  * value passed to this function.
  94  *
  95  * Paths are yielded in alphabetical order, as absolute paths.
  96  */
  97 pub fn glob_with(pattern: &str, options: MatchOptions) -> Paths {
  98     #[cfg(windows)]
  99     fn check_windows_verbatim(p: &Path) -> bool { path::windows::is_verbatim(p) }
 100     #[cfg(not(windows))]
 101     fn check_windows_verbatim(_: &Path) -> bool { false }
 102
 103     // calculate root this way to handle volume-relative Windows paths correctly
 104     let mut root = os::getcwd();
 105     let pat_root = Path::new(pattern).root_path();
 106     if pat_root.is_some() {
 107         if check_windows_verbatim(pat_root.get_ref()) {
 108             // FIXME: How do we want to handle verbatim paths? I'm inclined to return nothing,
 109             // since we can't very well find all UNC shares with a 1-letter server name.
 110             return Paths {
 111                 root: root,
 112                 dir_patterns: Vec::new(),
 113                 require_dir: false,
 114                 options: options,
 115                 todo: Vec::new(),
 116             };
 117         }
 118         root.push(pat_root.get_ref());
 119     }
 120
 121     let root_len = pat_root.map_or(0u, |p| p.as_vec().len());
 122     let dir_patterns = pattern.slice_from(cmp::min(root_len, pattern.len()))
 123                        .split_terminator(is_sep)
 124                        .map(|s| Pattern::new(s))
 125                        .collect::<Vec<Pattern>>();
 126     let require_dir = pattern.chars().next_back().map(is_sep) == Some(true);
 127
 128     let mut todo = Vec::new();
 129     if dir_patterns.len() > 0 {
 130         // Shouldn't happen, but we're using -1 as a special index.
 131         assert!(dir_patterns.len() < -1 as uint);
 132
 133         fill_todo(&mut todo, dir_patterns.as_slice(), 0, &root, options);
 134     }
 135
 136     Paths {
 137         root: root,
 138         dir_patterns: dir_patterns,
 139         require_dir: require_dir,
 140         options: options,
 141         todo: todo,
 142     }
 143 }
 144
 145 impl Iterator<Path> for Paths {
 146
 147     fn next(&mut self) -> Option<Path> {
 148         loop {
 149             if self.dir_patterns.is_empty() || self.todo.is_empty() {
 150                 return None;
 151             }
 152
 153             let (path,idx) = self.todo.pop().unwrap();
 154             // idx -1: was already checked by fill_todo, maybe path was '.' or
 155             // '..' that we can't match here because of normalization.
 156             if idx == -1 as uint {
 157                 if self.require_dir && !path.is_dir() { continue; }
 158                 return Some(path);
 159             }
 160             let ref pattern = *self.dir_patterns.get(idx);
 161
 162             if pattern.matches_with(match path.filename_str() {
 163                 // this ugly match needs to go here to avoid a borrowck error
 164                 None => {
 165                     // FIXME (#9639): How do we handle non-utf8 filenames? Ignore them for now
 166                     // Ideally we'd still match them against a *
 167                     continue;
 168                 }
 169                 Some(x) => x
 170             }, self.options) {
 171                 if idx == self.dir_patterns.len() - 1 {
 172                     // it is not possible for a pattern to match a directory *AND* its children
 173                     // so we don't need to check the children
 174
 175                     if !self.require_dir || path.is_dir() {
 176                         return Some(path);
 177                     }
 178                 } else {
 179                     fill_todo(&mut self.todo, self.dir_patterns.as_slice(),
 180                               idx + 1, &path, self.options);
 181                 }
 182             }
 183         }
 184     }
 185
 186 }
 187
 188 fn list_dir_sorted(path: &Path) -> Option<Vec<Path>> {
 189     match fs::readdir(path) {
 190         Ok(mut children) => {
 191             children.sort_by(|p1, p2| p2.filename().cmp(&p1.filename()));
 192             Some(children.move_iter().collect())
 193         }
 194         Err(..) => None
 195     }
 196 }
 197
 198 /**
 199  * A compiled Unix shell style pattern.
 200  */
 201 #[deriving(Clone, Eq, TotalEq, Ord, TotalOrd, Hash, Default)]
 202 pub struct Pattern {
 203     tokens: Vec<PatternToken>,
 204 }
 205
 206 #[deriving(Clone, Eq, TotalEq, Ord, TotalOrd, Hash)]
 207 enum PatternToken {
 208     Char(char),
 209     AnyChar,
 210     AnySequence,
 211     AnyWithin(Vec<CharSpecifier> ),
 212     AnyExcept(Vec<CharSpecifier> )
 213 }
 214
 215 #[deriving(Clone, Eq, TotalEq, Ord, TotalOrd, Hash)]
 216 enum CharSpecifier {
 217     SingleChar(char),
 218     CharRange(char, char)
 219 }
 220
 221 #[deriving(Eq)]
 222 enum MatchResult {
 223     Match,
 224     SubPatternDoesntMatch,
 225     EntirePatternDoesntMatch
 226 }
 227
 228 impl Pattern {
 229
 230     /**
 231      * This function compiles Unix shell style patterns: `?` matches any single
 232      * character, `*` matches any (possibly empty) sequence of characters and
 233      * `[...]` matches any character inside the brackets, unless the first
 234      * character is `!` in which case it matches any character except those
 235      * between the `!` and the `]`. Character sequences can also specify ranges
 236      * of characters, as ordered by Unicode, so e.g. `[0-9]` specifies any
 237      * character between 0 and 9 inclusive.
 238      *
 239      * The metacharacters `?`, `*`, `[`, `]` can be matched by using brackets
 240      * (e.g. `[?]`).  When a `]` occurs immediately following `[` or `[!` then
 241      * it is interpreted as being part of, rather then ending, the character
 242      * set, so `]` and NOT `]` can be matched by `[]]` and `[!]]` respectively.
 243      * The `-` character can be specified inside a character sequence pattern by
 244      * placing it at the start or the end, e.g. `[abc-]`.
 245      *
 246      * When a `[` does not have a closing `]` before the end of the string then
 247      * the `[` will be treated literally.
 248      */
 249     pub fn new(pattern: &str) -> Pattern {
 250
 251         let chars = pattern.chars().collect::<Vec<_>>();
 252         let mut tokens = Vec::new();
 253         let mut i = 0;
 254
 255         while i < chars.len() {
 256             match *chars.get(i) {
 257                 '?' => {
 258                     tokens.push(AnyChar);
 259                     i += 1;
 260                 }
 261                 '*' => {
 262                     // *, **, ***, ****, ... are all equivalent
 263                     while i < chars.len() && *chars.get(i) == '*' {
 264                         i += 1;
 265                     }
 266                     tokens.push(AnySequence);
 267                 }
 268                 '[' => {
 269
 270                     if i <= chars.len() - 4 && *chars.get(i + 1) == '!' {
 271                         match chars.slice_from(i + 3).position_elem(&']') {
 272                             None => (),
 273                             Some(j) => {
 274                                 let chars = chars.slice(i + 2, i + 3 + j);
 275                                 let cs = parse_char_specifiers(chars);
 276                                 tokens.push(AnyExcept(cs));
 277                                 i += j + 4;
 278                                 continue;
 279                             }
 280                         }
 281                     }
 282                     else if i <= chars.len() - 3 && *chars.get(i + 1) != '!' {
 283                         match chars.slice_from(i + 2).position_elem(&']') {
 284                             None => (),
 285                             Some(j) => {
 286                                 let cs = parse_char_specifiers(chars.slice(i + 1, i + 2 + j));
 287                                 tokens.push(AnyWithin(cs));
 288                                 i += j + 3;
 289                                 continue;
 290                             }
 291                         }
 292                     }
 293
 294                     // if we get here then this is not a valid range pattern
 295                     tokens.push(Char('['));
 296                     i += 1;
 297                 }
 298                 c => {
 299                     tokens.push(Char(c));
 300                     i += 1;
 301                 }
 302             }
 303         }
 304
 305         Pattern { tokens: tokens }
 306     }
 307
 308     /**
 309      * Escape metacharacters within the given string by surrounding them in
 310      * brackets. The resulting string will, when compiled into a `Pattern`,
 311      * match the input string and nothing else.
 312      */
 313     pub fn escape(s: &str) -> ~str {
 314         let mut escaped = StrBuf::new();
 315         for c in s.chars() {
 316             match c {
 317                 // note that ! does not need escaping because it is only special inside brackets
 318                 '?' | '*' | '[' | ']' => {
 319                     escaped.push_char('[');
 320                     escaped.push_char(c);
 321                     escaped.push_char(']');
 322                 }
 323                 c => {
 324                     escaped.push_char(c);
 325                 }
 326             }
 327         }
 328         escaped.into_owned()
 329     }
 330
 331     /**
 332      * Return if the given `str` matches this `Pattern` using the default
 333      * match options (i.e. `MatchOptions::new()`).
 334      *
 335      * # Example
 336      *
 337      * ```rust
 338      * use glob::Pattern;
 339      *
 340      * assert!(Pattern::new("c?t").matches("cat"));
 341      * assert!(Pattern::new("k[!e]tteh").matches("kitteh"));
 342      * assert!(Pattern::new("d*g").matches("doog"));
 343      * ```
 344      */
 345     pub fn matches(&self, str: &str) -> bool {
 346         self.matches_with(str, MatchOptions::new())
 347     }
 348
 349     /**
 350      * Return if the given `Path`, when converted to a `str`, matches this `Pattern`
 351      * using the default match options (i.e. `MatchOptions::new()`).
 352      */
 353     pub fn matches_path(&self, path: &Path) -> bool {
 354         // FIXME (#9639): This needs to handle non-utf8 paths
 355         path.as_str().map_or(false, |s| {
 356             self.matches(s)
 357         })
 358     }
 359
 360     /**
 361      * Return if the given `str` matches this `Pattern` using the specified match options.
 362      */
 363     pub fn matches_with(&self, str: &str, options: MatchOptions) -> bool {
 364         self.matches_from(None, str, 0, options) == Match
 365     }
 366
 367     /**
 368      * Return if the given `Path`, when converted to a `str`, matches this `Pattern`
 369      * using the specified match options.
 370      */
 371     pub fn matches_path_with(&self, path: &Path, options: MatchOptions) -> bool {
 372         // FIXME (#9639): This needs to handle non-utf8 paths
 373         path.as_str().map_or(false, |s| {
 374             self.matches_with(s, options)
 375         })
 376     }
 377
 378     fn matches_from(&self,
 379                     prev_char: Option<char>,
 380                     mut file: &str,
 381                     i: uint,
 382                     options: MatchOptions) -> MatchResult {
 383
 384         let prev_char = Cell::new(prev_char);
 385
 386         let require_literal = |c| {
 387             (options.require_literal_separator && is_sep(c)) ||
 388             (options.require_literal_leading_dot && c == '.'
 389              && is_sep(prev_char.get().unwrap_or('/')))
 390         };
 391
 392         for (ti, token) in self.tokens.slice_from(i).iter().enumerate() {
 393             match *token {
 394                 AnySequence => {
 395                     loop {
 396                         match self.matches_from(prev_char.get(), file, i + ti + 1, options) {
 397                             SubPatternDoesntMatch => (), // keep trying
 398                             m => return m,
 399                         }
 400
 401                         if file.is_empty() {
 402                             return EntirePatternDoesntMatch;
 403                         }
 404
 405                         let (some_c, next) = file.slice_shift_char();
 406                         if require_literal(some_c.unwrap()) {
 407                             return SubPatternDoesntMatch;
 408                         }
 409                         prev_char.set(some_c);
 410                         file = next;
 411                     }
 412                 }
 413                 _ => {
 414                     if file.is_empty() {
 415                         return EntirePatternDoesntMatch;
 416                     }
 417
 418                     let (some_c, next) = file.slice_shift_char();
 419                     let c = some_c.unwrap();
 420                     let matches = match *token {
 421                         AnyChar => {
 422                             !require_literal(c)
 423                         }
 424                         AnyWithin(ref specifiers) => {
 425                             !require_literal(c) &&
 426                                 in_char_specifiers(specifiers.as_slice(),
 427                                                    c,
 428                                                    options)
 429                         }
 430                         AnyExcept(ref specifiers) => {
 431                             !require_literal(c) &&
 432                                 !in_char_specifiers(specifiers.as_slice(),
 433                                                     c,
 434                                                     options)
 435                         }
 436                         Char(c2) => {
 437                             chars_eq(c, c2, options.case_sensitive)
 438                         }
 439                         AnySequence => {
 440                             unreachable!()
 441                         }
 442                     };
 443                     if !matches {
 444                         return SubPatternDoesntMatch;
 445                     }
 446                     prev_char.set(some_c);
 447                     file = next;
 448                 }
 449             }
 450         }
 451
 452         if file.is_empty() {
 453             Match
 454         } else {
 455             SubPatternDoesntMatch
 456         }
 457     }
 458
 459 }
 460
 461 // Fills `todo` with paths under `path` to be matched by `patterns[idx]`,
 462 // special-casing patterns to match `.` and `..`, and avoiding `readdir()`
 463 // calls when there are no metacharacters in the pattern.
 464 fn fill_todo(todo: &mut Vec<(Path, uint)>, patterns: &[Pattern], idx: uint, path: &Path,
 465              options: MatchOptions) {
 466     // convert a pattern that's just many Char(_) to a string
 467     fn pattern_as_str(pattern: &Pattern) -> Option<StrBuf> {
 468         let mut s = StrBuf::new();
 469         for token in pattern.tokens.iter() {
 470             match *token {
 471                 Char(c) => s.push_char(c),
 472                 _ => return None
 473             }
 474         }
 475         return Some(s);
 476     }
 477
 478     let add = |todo: &mut Vec<_>, next_path: Path| {
 479         if idx + 1 == patterns.len() {
 480             // We know it's good, so don't make the iterator match this path
 481             // against the pattern again. In particular, it can't match
 482             // . or .. globs since these never show up as path components.
 483             todo.push((next_path, -1 as uint));
 484         } else {
 485             fill_todo(todo, patterns, idx + 1, &next_path, options);
 486         }
 487     };
 488
 489     let pattern = &patterns[idx];
 490
 491     match pattern_as_str(pattern) {
 492         Some(s) => {
 493             // This pattern component doesn't have any metacharacters, so we
 494             // don't need to read the current directory to know where to
 495             // continue. So instead of passing control back to the iterator,
 496             // we can just check for that one entry and potentially recurse
 497             // right away.
 498             let special = "." == s.as_slice() || ".." == s.as_slice();
 499             let next_path = path.join(s.as_slice());
 500             if (special && path.is_dir()) || (!special && next_path.exists()) {
 501                 add(todo, next_path);
 502             }
 503         },
 504         None => {
 505             match list_dir_sorted(path) {
 506                 Some(entries) => {
 507                     todo.extend(entries.move_iter().map(|x|(x, idx)));
 508
 509                     // Matching the special directory entries . and .. that refer to
 510                     // the current and parent directory respectively requires that
 511                     // the pattern has a leading dot, even if the `MatchOptions` field
 512                     // `require_literal_leading_dot` is not set.
 513                     if pattern.tokens.len() > 0 && pattern.tokens.get(0) == &Char('.') {
 514                         for &special in [".", ".."].iter() {
 515                             if pattern.matches_with(special, options) {
 516                                 add(todo, path.join(special));
 517                             }
 518                         }
 519                     }
 520                 }
 521                 None => {}
 522             }
 523         }
 524     }
 525 }
 526
 527 fn parse_char_specifiers(s: &[char]) -> Vec<CharSpecifier> {
 528     let mut cs = Vec::new();
 529     let mut i = 0;
 530     while i < s.len() {
 531         if i + 3 <= s.len() && s[i + 1] == '-' {
 532             cs.push(CharRange(s[i], s[i + 2]));
 533             i += 3;
 534         } else {
 535             cs.push(SingleChar(s[i]));
 536             i += 1;
 537         }
 538     }
 539     cs
 540 }
 541
 542 fn in_char_specifiers(specifiers: &[CharSpecifier], c: char, options: MatchOptions) -> bool {
 543
 544     for &specifier in specifiers.iter() {
 545         match specifier {
 546             SingleChar(sc) => {
 547                 if chars_eq(c, sc, options.case_sensitive) {
 548                     return true;
 549                 }
 550             }
 551             CharRange(start, end) => {
 552
 553                 // FIXME: work with non-ascii chars properly (issue #1347)
 554                 if !options.case_sensitive && c.is_ascii() && start.is_ascii() && end.is_ascii() {
 555
 556                     let start = start.to_ascii().to_lower();
 557                     let end = end.to_ascii().to_lower();
 558
 559                     let start_up = start.to_upper();
 560                     let end_up = end.to_upper();
 561
 562                     // only allow case insensitive matching when
 563                     // both start and end are within a-z or A-Z
 564                     if start != start_up && end != end_up {
 565                         let start = start.to_char();
 566                         let end = end.to_char();
 567                         let c = c.to_ascii().to_lower().to_char();
 568                         if c >= start && c <= end {
 569                             return true;
 570                         }
 571                     }
 572                 }
 573
 574                 if c >= start && c <= end {
 575                     return true;
 576                 }
 577             }
 578         }
 579     }
 580
 581     false
 582 }
 583
 584 /// A helper function to determine if two chars are (possibly case-insensitively) equal.
 585 fn chars_eq(a: char, b: char, case_sensitive: bool) -> bool {
 586     if cfg!(windows) && path::windows::is_sep(a) && path::windows::is_sep(b) {
 587         true
 588     } else if !case_sensitive && a.is_ascii() && b.is_ascii() {
 589         // FIXME: work with non-ascii chars properly (issue #1347)
 590         a.to_ascii().eq_ignore_case(b.to_ascii())
 591     } else {
 592         a == b
 593     }
 594 }
 595
 596 /**
 597  * Configuration options to modify the behaviour of `Pattern::matches_with(..)`
 598  */
 599 #[deriving(Clone, Eq, TotalEq, Ord, TotalOrd, Hash, Default)]
 600 pub struct MatchOptions {
 601
 602     /**
 603      * Whether or not patterns should be matched in a case-sensitive manner. This
 604      * currently only considers upper/lower case relationships between ASCII characters,
 605      * but in future this might be extended to work with Unicode.
 606      */
 607     case_sensitive: bool,
 608
 609     /**
 610      * If this is true then path-component separator characters (e.g. `/` on Posix)
 611      * must be matched by a literal `/`, rather than by `*` or `?` or `[...]`
 612      */
 613     require_literal_separator: bool,
 614
 615     /**
 616      * If this is true then paths that contain components that start with a `.` will
 617      * not match unless the `.` appears literally in the pattern: `*`, `?` or `[...]`
 618      * will not match. This is useful because such files are conventionally considered
 619      * hidden on Unix systems and it might be desirable to skip them when listing files.
 620      */
 621     require_literal_leading_dot: bool
 622 }
 623
 624 impl MatchOptions {
 625
 626     /**
 627      * Constructs a new `MatchOptions` with default field values. This is used
 628      * when calling functions that do not take an explicit `MatchOptions` parameter.
 629      *
 630      * This function always returns this value:
 631      *
 632      * ```rust,ignore
 633      * MatchOptions {
 634      *     case_sensitive: true,
 635      *     require_literal_separator: false.
 636      *     require_literal_leading_dot: false
 637      * }
 638      * ```
 639      */
 640     pub fn new() -> MatchOptions {
 641         MatchOptions {
 642             case_sensitive: true,
 643             require_literal_separator: false,
 644             require_literal_leading_dot: false
 645         }
 646     }
 647
 648 }
 649
 650 #[cfg(test)]
 651 mod test {
 652     use std::os;
 653     use super::{glob, Pattern, MatchOptions};
 654
 655     #[test]
 656     fn test_absolute_pattern() {
 657         // assume that the filesystem is not empty!
 658         assert!(glob("/*").next().is_some());
 659         assert!(glob("//").next().is_some());
 660
 661         // check windows absolute paths with host/device components
 662         let root_with_device = os::getcwd().root_path().unwrap().join("*");
 663         // FIXME (#9639): This needs to handle non-utf8 paths
 664         assert!(glob(root_with_device.as_str().unwrap()).next().is_some());
 665     }
 666
 667     #[test]
 668     fn test_wildcard_optimizations() {
 669         assert!(Pattern::new("a*b").matches("a___b"));
 670         assert!(Pattern::new("a**b").matches("a___b"));
 671         assert!(Pattern::new("a***b").matches("a___b"));
 672         assert!(Pattern::new("a*b*c").matches("abc"));
 673         assert!(!Pattern::new("a*b*c").matches("abcd"));
 674         assert!(Pattern::new("a*b*c").matches("a_b_c"));
 675         assert!(Pattern::new("a*b*c").matches("a___b___c"));
 676         assert!(Pattern::new("abc*abc*abc").matches("abcabcabcabcabcabcabc"));
 677         assert!(!Pattern::new("abc*abc*abc").matches("abcabcabcabcabcabcabca"));
 678         assert!(Pattern::new("a*a*a*a*a*a*a*a*a").matches("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
 679         assert!(Pattern::new("a*b[xyz]c*d").matches("abxcdbxcddd"));
 680     }
 681
 682     #[test]
 683     fn test_lots_of_files() {
 684         // this is a good test because it touches lots of differently named files
 685         glob("/*/*/*/*").skip(10000).next();
 686     }
 687
 688     #[test]
 689     fn test_range_pattern() {
 690
 691         let pat = Pattern::new("a[0-9]b");
 692         for i in range(0, 10) {
 693             assert!(pat.matches(format!("a{}b", i)));
 694         }
 695         assert!(!pat.matches("a_b"));
 696
 697         let pat = Pattern::new("a[!0-9]b");
 698         for i in range(0, 10) {
 699             assert!(!pat.matches(format!("a{}b", i)));
 700         }
 701         assert!(pat.matches("a_b"));
 702
 703         let pats = ["[a-z123]", "[1a-z23]", "[123a-z]"];
 704         for &p in pats.iter() {
 705             let pat = Pattern::new(p);
 706             for c in "abcdefghijklmnopqrstuvwxyz".chars() {
 707                 assert!(pat.matches(c.to_str()));
 708             }
 709             for c in "ABCDEFGHIJKLMNOPQRSTUVWXYZ".chars() {
 710                 let options = MatchOptions {case_sensitive: false, .. MatchOptions::new()};
 711                 assert!(pat.matches_with(c.to_str(), options));
 712             }
 713             assert!(pat.matches("1"));
 714             assert!(pat.matches("2"));
 715             assert!(pat.matches("3"));
 716         }
 717
 718         let pats = ["[abc-]", "[-abc]", "[a-c-]"];
 719         for &p in pats.iter() {
 720             let pat = Pattern::new(p);
 721             assert!(pat.matches("a"));
 722             assert!(pat.matches("b"));
 723             assert!(pat.matches("c"));
 724             assert!(pat.matches("-"));
 725             assert!(!pat.matches("d"));
 726         }
 727
 728         let pat = Pattern::new("[2-1]");
 729         assert!(!pat.matches("1"));
 730         assert!(!pat.matches("2"));
 731
 732         assert!(Pattern::new("[-]").matches("-"));
 733         assert!(!Pattern::new("[!-]").matches("-"));
 734     }
 735
 736     #[test]
 737     fn test_unclosed_bracket() {
 738         // unclosed `[` should be treated literally
 739         assert!(Pattern::new("abc[def").matches("abc[def"));
 740         assert!(Pattern::new("abc[!def").matches("abc[!def"));
 741         assert!(Pattern::new("abc[").matches("abc["));
 742         assert!(Pattern::new("abc[!").matches("abc[!"));
 743         assert!(Pattern::new("abc[d").matches("abc[d"));
 744         assert!(Pattern::new("abc[!d").matches("abc[!d"));
 745         assert!(Pattern::new("abc[]").matches("abc[]"));
 746         assert!(Pattern::new("abc[!]").matches("abc[!]"));
 747     }
 748
 749     #[test]
 750     fn test_pattern_matches() {
 751         let txt_pat = Pattern::new("*hello.txt");
 752         assert!(txt_pat.matches("hello.txt"));
 753         assert!(txt_pat.matches("gareth_says_hello.txt"));
 754         assert!(txt_pat.matches("some/path/to/hello.txt"));
 755         assert!(txt_pat.matches("some\\path\\to\\hello.txt"));
 756         assert!(txt_pat.matches("/an/absolute/path/to/hello.txt"));
 757         assert!(!txt_pat.matches("hello.txt-and-then-some"));
 758         assert!(!txt_pat.matches("goodbye.txt"));
 759
 760         let dir_pat = Pattern::new("*some/path/to/hello.txt");
 761         assert!(dir_pat.matches("some/path/to/hello.txt"));
 762         assert!(dir_pat.matches("a/bigger/some/path/to/hello.txt"));
 763         assert!(!dir_pat.matches("some/path/to/hello.txt-and-then-some"));
 764         assert!(!dir_pat.matches("some/other/path/to/hello.txt"));
 765     }
 766
 767     #[test]
 768     fn test_pattern_escape() {
 769         let s = "_[_]_?_*_!_";
 770         assert_eq!(Pattern::escape(s), ~"_[[]_[]]_[?]_[*]_!_");
 771         assert!(Pattern::new(Pattern::escape(s)).matches(s));
 772     }
 773
 774     #[test]
 775     fn test_pattern_matches_case_insensitive() {
 776
 777         let pat = Pattern::new("aBcDeFg");
 778         let options = MatchOptions {
 779             case_sensitive: false,
 780             require_literal_separator: false,
 781             require_literal_leading_dot: false
 782         };
 783
 784         assert!(pat.matches_with("aBcDeFg", options));
 785         assert!(pat.matches_with("abcdefg", options));
 786         assert!(pat.matches_with("ABCDEFG", options));
 787         assert!(pat.matches_with("AbCdEfG", options));
 788     }
 789
 790     #[test]
 791     fn test_pattern_matches_case_insensitive_range() {
 792
 793         let pat_within = Pattern::new("[a]");
 794         let pat_except = Pattern::new("[!a]");
 795
 796         let options_case_insensitive = MatchOptions {
 797             case_sensitive: false,
 798             require_literal_separator: false,
 799             require_literal_leading_dot: false
 800         };
 801         let options_case_sensitive = MatchOptions {
 802             case_sensitive: true,
 803             require_literal_separator: false,
 804             require_literal_leading_dot: false
 805         };
 806
 807         assert!(pat_within.matches_with("a", options_case_insensitive));
 808         assert!(pat_within.matches_with("A", options_case_insensitive));
 809         assert!(!pat_within.matches_with("A", options_case_sensitive));
 810
 811         assert!(!pat_except.matches_with("a", options_case_insensitive));
 812         assert!(!pat_except.matches_with("A", options_case_insensitive));
 813         assert!(pat_except.matches_with("A", options_case_sensitive));
 814     }
 815
 816     #[test]
 817     fn test_pattern_matches_require_literal_separator() {
 818
 819         let options_require_literal = MatchOptions {
 820             case_sensitive: true,
 821             require_literal_separator: true,
 822             require_literal_leading_dot: false
 823         };
 824         let options_not_require_literal = MatchOptions {
 825             case_sensitive: true,
 826             require_literal_separator: false,
 827             require_literal_leading_dot: false
 828         };
 829
 830         assert!(Pattern::new("abc/def").matches_with("abc/def", options_require_literal));
 831         assert!(!Pattern::new("abc?def").matches_with("abc/def", options_require_literal));
 832         assert!(!Pattern::new("abc*def").matches_with("abc/def", options_require_literal));
 833         assert!(!Pattern::new("abc[/]def").matches_with("abc/def", options_require_literal));
 834
 835         assert!(Pattern::new("abc/def").matches_with("abc/def", options_not_require_literal));
 836         assert!(Pattern::new("abc?def").matches_with("abc/def", options_not_require_literal));
 837         assert!(Pattern::new("abc*def").matches_with("abc/def", options_not_require_literal));
 838         assert!(Pattern::new("abc[/]def").matches_with("abc/def", options_not_require_literal));
 839     }
 840
 841     #[test]
 842     fn test_pattern_matches_require_literal_leading_dot() {
 843
 844         let options_require_literal_leading_dot = MatchOptions {
 845             case_sensitive: true,
 846             require_literal_separator: false,
 847             require_literal_leading_dot: true
 848         };
 849         let options_not_require_literal_leading_dot = MatchOptions {
 850             case_sensitive: true,
 851             require_literal_separator: false,
 852             require_literal_leading_dot: false
 853         };
 854
 855         let f = |options| Pattern::new("*.txt").matches_with(".hello.txt", options);
 856         assert!(f(options_not_require_literal_leading_dot));
 857         assert!(!f(options_require_literal_leading_dot));
 858
 859         let f = |options| Pattern::new(".*.*").matches_with(".hello.txt", options);
 860         assert!(f(options_not_require_literal_leading_dot));
 861         assert!(f(options_require_literal_leading_dot));
 862
 863         let f = |options| Pattern::new("aaa/bbb/*").matches_with("aaa/bbb/.ccc", options);
 864         assert!(f(options_not_require_literal_leading_dot));
 865         assert!(!f(options_require_literal_leading_dot));
 866
 867         let f = |options| Pattern::new("aaa/bbb/*").matches_with("aaa/bbb/c.c.c.", options);
 868         assert!(f(options_not_require_literal_leading_dot));
 869         assert!(f(options_require_literal_leading_dot));
 870
 871         let f = |options| Pattern::new("aaa/bbb/.*").matches_with("aaa/bbb/.ccc", options);
 872         assert!(f(options_not_require_literal_leading_dot));
 873         assert!(f(options_require_literal_leading_dot));
 874
 875         let f = |options| Pattern::new("aaa/?bbb").matches_with("aaa/.bbb", options);
 876         assert!(f(options_not_require_literal_leading_dot));
 877         assert!(!f(options_require_literal_leading_dot));
 878
 879         let f = |options| Pattern::new("aaa/[.]bbb").matches_with("aaa/.bbb", options);
 880         assert!(f(options_not_require_literal_leading_dot));
 881         assert!(!f(options_require_literal_leading_dot));
 882     }
 883
 884     #[test]
 885     fn test_matches_path() {
 886         // on windows, (Path::new("a/b").as_str().unwrap() == "a\\b"), so this
 887         // tests that / and \ are considered equivalent on windows
 888         assert!(Pattern::new("a/b").matches_path(&Path::new("a/b")));
 889     }
 890 }