Brunobkr/llama.cpp_AlgMor24_github

1# minimatch2 3A minimal matching utility.4 5This is the matching library used internally by npm.6 7It works by converting glob expressions into JavaScript `RegExp`8objects.9 10## Important Security Consideration!11 12> [!WARNING]  13> This library uses JavaScript regular expressions. Please read14> the following warning carefully, and be thoughtful about what15> you provide to this library in production systems.16 17_Any_ library in JavaScript that deals with matching string18patterns using regular expressions will be subject to19[ReDoS](https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS)20if the pattern is generated using untrusted input.21 22Efforts have been made to mitigate risk as much as is feasible in23such a library, providing maximum recursion depths and so forth,24but these measures can only ultimately protect against accidents,25not malice. A dedicated attacker can _always_ find patterns that26cannot be defended against by a bash-compatible glob pattern27matching system that uses JavaScript regular expressions.28 29To be extremely clear:30 31> [!WARNING]  32> **If you create a system where you take user input, and use33> that input as the source of a Regular Expression pattern, in34> this or any extant glob matcher in JavaScript, you will be35> pwned.**36 37A future version of this library _may_ use a different matching38algorithm which does not exhibit backtracking problems. If and39when that happens, it will likely be a sweeping change, and those40improvements will **not** be backported to legacy versions.41 42In the near term, it is not reasonable to continue to play43whack-a-mole with security advisories, and so any future ReDoS44reports will be considered "working as intended", and resolved45entirely by this warning.46 47## Usage48 49```js50// hybrid module, load with require() or import51import { minimatch } from 'minimatch'52// or:53const { minimatch } = require('minimatch')54 55minimatch('bar.foo', '*.foo') // true!56minimatch('bar.foo', '*.bar') // false!57minimatch('bar.foo', '*.+(bar|foo)', { debug: true }) // true, and noisy!58```59 60## Features61 62Supports these glob features:63 64- Brace Expansion65- Extended glob matching66- "Globstar" `**` matching67- [Posix character68  classes](https://www.gnu.org/software/bash/manual/html_node/Pattern-Matching.html),69  like `[[:alpha:]]`, supporting the full range of Unicode70  characters. For example, `[[:alpha:]]` will match against71  `'é'`, though `[a-zA-Z]` will not. Collating symbol and set72  matching is not supported, so `[[=e=]]` will _not_ match `'é'`73  and `[[.ch.]]` will not match `'ch'` in locales where `ch` is74  considered a single character.75 76See:77 78- `man sh`79- `man bash` [Pattern80  Matching](https://www.gnu.org/software/bash/manual/html_node/Pattern-Matching.html)81- `man 3 fnmatch`82- `man 5 gitignore`83 84## Windows85 86**Please only use forward-slashes in glob expressions.**87 88Though windows uses either `/` or `\` as its path separator, only `/`89characters are used by this glob implementation. You must use90forward-slashes **only** in glob expressions. Back-slashes in patterns91will always be interpreted as escape characters, not path separators.92 93Note that `\` or `/` _will_ be interpreted as path separators in paths on94Windows, and will match against `/` in glob expressions.95 96So just always use `/` in patterns.97 98### UNC Paths99 100On Windows, UNC paths like `//?/c:/...` or101`//ComputerName/Share/...` are handled specially.102 103- Patterns starting with a double-slash followed by some104  non-slash characters will preserve their double-slash. As a105  result, a pattern like `//*` will match `//x`, but not `/x`.106- Patterns staring with `//?/<drive letter>:` will _not_ treat107  the `?` as a wildcard character. Instead, it will be treated108  as a normal string.109- Patterns starting with `//?/<drive letter>:/...` will match110  file paths starting with `<drive letter>:/...`, and vice versa,111  as if the `//?/` was not present. This behavior only is112  present when the drive letters are a case-insensitive match to113  one another. The remaining portions of the path/pattern are114  compared case sensitively, unless `nocase:true` is set.115 116Note that specifying a UNC path using `\` characters as path117separators is always allowed in the file path argument, but only118allowed in the pattern argument when `windowsPathsNoEscape: true`119is set in the options.120 121## Minimatch Class122 123Create a minimatch object by instantiating the `minimatch.Minimatch` class.124 125```javascript126var Minimatch = require('minimatch').Minimatch127var mm = new Minimatch(pattern, options)128```129 130### Properties131 132- `pattern` The original pattern the minimatch object represents.133- `options` The options supplied to the constructor.134- `set` A 2-dimensional array of regexp or string expressions.135  Each row in the136  array corresponds to a brace-expanded pattern. Each item in the row137  corresponds to a single path-part. For example, the pattern138  `{a,b/c}/d` would expand to a set of patterns like:139 140        [ [ a, d ]141        , [ b, c, d ] ]142 143  If a portion of the pattern doesn't have any "magic" in it144  (that is, it's something like `"foo"` rather than `fo*o?`), then it145  will be left as a string rather than converted to a regular146  expression.147 148- `regexp` Created by the `makeRe` method. A single regular expression149  expressing the entire pattern. This is useful in cases where you wish150  to use the pattern somewhat like `fnmatch(3)` with `FNM_PATH` enabled.151- `negate` True if the pattern is negated.152- `comment` True if the pattern is a comment.153- `empty` True if the pattern is `""`.154 155### Methods156 157- `makeRe()` Generate the `regexp` member if necessary, and return it.158  Will return `false` if the pattern is invalid.159- `match(fname)` Return true if the filename matches the pattern, or160  false otherwise.161- `matchOne(fileArray, patternArray, partial)` Take a `/`-split162  filename, and match it against a single row in the `regExpSet`. This163  method is mainly for internal use, but is exposed so that it can be164  used by a glob-walker that needs to avoid excessive filesystem calls.165- `hasMagic()` Returns true if the parsed pattern contains any166  magic characters. Returns false if all comparator parts are167  string literals. If the `magicalBraces` option is set on the168  constructor, then it will consider brace expansions which are169  not otherwise magical to be magic. If not set, then a pattern170  like `a{b,c}d` will return `false`, because neither `abd` nor171  `acd` contain any special glob characters.172 173  This does **not** mean that the pattern string can be used as a174  literal filename, as it may contain magic glob characters that175  are escaped. For example, the pattern `\\*` or `[*]` would not176  be considered to have magic, as the matching portion parses to177  the literal string `'*'` and would match a path named `'*'`,178  not `'\\*'` or `'[*]'`. The `minimatch.unescape()` method may179  be used to remove escape characters.180 181All other methods are internal, and will be called as necessary.182 183### minimatch(path, pattern, options)184 185Main export. Tests a path against the pattern using the options.186 187```javascript188var isJS = minimatch(file, '*.js', { matchBase: true })189```190 191### minimatch.filter(pattern, options)192 193Returns a function that tests its194supplied argument, suitable for use with `Array.filter`. Example:195 196```javascript197var javascripts = fileList.filter(198  minimatch.filter('*.js', { matchBase: true }),199)200```201 202### minimatch.escape(pattern, options = {})203 204Escape all magic characters in a glob pattern, so that it will205only ever match literal strings.206 207If the `windowsPathsNoEscape` option is used, then characters are208escaped by wrapping in `[]`, because a magic character wrapped in209a character class can only be satisfied by that exact character.210 211Slashes (and backslashes in `windowsPathsNoEscape` mode) cannot212be escaped or unescaped.213 214### minimatch.unescape(pattern, options = {})215 216Un-escape a glob string that may contain some escaped characters.217 218If the `windowsPathsNoEscape` option is used, then square-brace219escapes are removed, but not backslash escapes. For example, it220will turn the string `'[*]'` into `*`, but it will not turn221`'\\*'` into `'*'`, because `\` is a path separator in222`windowsPathsNoEscape` mode.223 224When `windowsPathsNoEscape` is not set, then both brace escapes225and backslash escapes are removed.226 227Slashes (and backslashes in `windowsPathsNoEscape` mode) cannot228be escaped or unescaped.229 230### minimatch.match(list, pattern, options)231 232Match against the list of233files, in the style of fnmatch or glob. If nothing is matched, and234options.nonull is set, then return a list containing the pattern itself.235 236```javascript237var javascripts = minimatch.match(fileList, '*.js', { matchBase: true })238```239 240### minimatch.makeRe(pattern, options)241 242Make a regular expression object from the pattern.243 244## Options245 246All options are `false` by default.247 248### debug249 250Dump a ton of stuff to stderr.251 252### nobrace253 254Do not expand `{a,b}` and `{1..3}` brace sets.255 256### noglobstar257 258Disable `**` matching against multiple folder names.259 260### dot261 262Allow patterns to match filenames starting with a period, even if263the pattern does not explicitly have a period in that spot.264 265Note that by default, `a/**/b` will **not** match `a/.d/b`, unless `dot`266is set.267 268### noext269 270Disable "extglob" style patterns like `+(a|b)`.271 272### nocase273 274Perform a case-insensitive match.275 276### nocaseMagicOnly277 278When used with `{nocase: true}`, create regular expressions that279are case-insensitive, but leave string match portions untouched.280Has no effect when used without `{nocase: true}`.281 282Useful when some other form of case-insensitive matching is used,283or if the original string representation is useful in some other284way.285 286### nonull287 288When a match is not found by `minimatch.match`, return a list containing289the pattern itself if this option is set. When not set, an empty list290is returned if there are no matches.291 292### magicalBraces293 294This only affects the results of the `Minimatch.hasMagic` method.295 296If the pattern contains brace expansions, such as `a{b,c}d`, but297no other magic characters, then the `Minimatch.hasMagic()` method298will return `false` by default. When this option set, it will299return `true` for brace expansion as well as other magic glob300characters.301 302### matchBase303 304If set, then patterns without slashes will be matched305against the basename of the path if it contains slashes. For example,306`a?b` would match the path `/xyz/123/acb`, but not `/xyz/acb/123`.307 308### nocomment309 310Suppress the behavior of treating `#` at the start of a pattern as a311comment.312 313### nonegate314 315Suppress the behavior of treating a leading `!` character as negation.316 317### flipNegate318 319Returns from negate expressions the same as if they were not negated.320(Ie, true on a hit, false on a miss.)321 322### partial323 324Compare a partial path to a pattern. As long as the parts of the path that325are present are not contradicted by the pattern, it will be treated as a326match. This is useful in applications where you're walking through a327folder structure, and don't yet have the full path, but want to ensure that328you do not walk down paths that can never be a match.329 330For example,331 332```js333minimatch('/a/b', '/a/*/c/d', { partial: true }) // true, might be /a/b/c/d334minimatch('/a/b', '/**/d', { partial: true }) // true, might be /a/b/.../d335minimatch('/x/y/z', '/a/**/z', { partial: true }) // false, because x !== a336```337 338### windowsPathsNoEscape339 340Use `\\` as a path separator _only_, and _never_ as an escape341character. If set, all `\\` characters are replaced with `/` in342the pattern. Note that this makes it **impossible** to match343against paths containing literal glob pattern characters, but344allows matching with patterns constructed using `path.join()` and345`path.resolve()` on Windows platforms, mimicking the (buggy!)346behavior of earlier versions on Windows. Please use with347caution, and be mindful of [the caveat about Windows348paths](#windows).349 350For legacy reasons, this is also set if351`options.allowWindowsEscape` is set to the exact value `false`.352 353### windowsNoMagicRoot354 355When a pattern starts with a UNC path or drive letter, and in356`nocase:true` mode, do not convert the root portions of the357pattern into a case-insensitive regular expression, and instead358leave them as strings.359 360This is the default when the platform is `win32` and361`nocase:true` is set.362 363### preserveMultipleSlashes364 365By default, multiple `/` characters (other than the leading `//`366in a UNC path, see "UNC Paths" above) are treated as a single367`/`.368 369That is, a pattern like `a///b` will match the file path `a/b`.370 371Set `preserveMultipleSlashes: true` to suppress this behavior.372 373### optimizationLevel374 375A number indicating the level of optimization that should be done376to the pattern prior to parsing and using it for matches.377 378Globstar parts `**` are always converted to `*` when `noglobstar`379is set, and multiple adjacent `**` parts are converted into a380single `**` (ie, `a/**/**/b` will be treated as `a/**/b`, as this381is equivalent in all cases).382 383- `0` - Make no further changes. In this mode, `.` and `..` are384  maintained in the pattern, meaning that they must also appear385  in the same position in the test path string. Eg, a pattern386  like `a/*/../c` will match the string `a/b/../c` but not the387  string `a/c`.388- `1` - (default) Remove cases where a double-dot `..` follows a389  pattern portion that is not `**`, `.`, `..`, or empty `''`. For390  example, the pattern `./a/b/../*` is converted to `./a/*`, and391  so it will match the path string `./a/c`, but not the path392  string `./a/b/../c`. Dots and empty path portions in the393  pattern are preserved.394- `2` (or higher) - Much more aggressive optimizations, suitable395  for use with file-walking cases:396  - Remove cases where a double-dot `..` follows a pattern397    portion that is not `**`, `.`, or empty `''`. Remove empty398    and `.` portions of the pattern, where safe to do so (ie,399    anywhere other than the last position, the first position, or400    the second position in a pattern starting with `/`, as this401    may indicate a UNC path on Windows).402  - Convert patterns containing `<pre>/**/../<p>/<rest>` into the403    equivalent `<pre>/{..,**}/<p>/<rest>`, where `<p>` is a404    a pattern portion other than `.`, `..`, `**`, or empty405    `''`.406  - Dedupe patterns where a `**` portion is present in one and407    omitted in another, and it is not the final path portion, and408    they are otherwise equivalent. So `{a/**/b,a/b}` becomes409    `a/**/b`, because `**` matches against an empty path portion.410  - Dedupe patterns where a `*` portion is present in one, and a411    non-dot pattern other than `**`, `.`, `..`, or `''` is in the412    same position in the other. So `a/{*,x}/b` becomes `a/*/b`,413    because `*` can match against `x`.414 415  While these optimizations improve the performance of416  file-walking use cases such as [glob](http://npm.im/glob) (ie,417  the reason this module exists), there are cases where it will418  fail to match a literal string that would have been matched in419  optimization level 1 or 0.420 421  Specifically, while the `Minimatch.match()` method will422  optimize the file path string in the same ways, resulting in423  the same matches, it will fail when tested with the regular424  expression provided by `Minimatch.makeRe()`, unless the path425  string is first processed with426  `minimatch.levelTwoFileOptimize()` or similar.427 428### platform429 430When set to `win32`, this will trigger all windows-specific431behaviors (special handling for UNC paths, and treating `\` as432separators in file paths for comparison.)433 434Defaults to the value of `process.platform`.435 436### maxGlobstarRecursion437 438Max number of non-adjacent `**` patterns to recursively walk439down.440 441The default of `200` is almost certainly high enough for most442purposes, and can handle absurdly excessive patterns.443 444If the limit is exceeded (which would require very excessively445long patterns and paths containing lots of `**` patterns!), then446it is treated as non-matching, even if the path would normally447match the pattern provided.448 449That is, this is an intentional false negative, deemed an450acceptable break in correctness for security and performance.451 452### maxExtglobRecursion453 454Max depth to traverse for nested extglobs like `*(a|b|c)`455 456Default is 2, which is quite low, but any higher value swiftly457results in punishing performance impacts. Note that this is _not_458relevant when the globstar types can be safely coalesced into a459single set.460 461For example, `*(a|@(b|c)|d)` would be flattened into462`*(a|b|c|d)`. Thus, many common extglobs will retain good463performance and never hit this limit, even if they are464excessively deep and complicated.465 466If the limit is hit, then the extglob characters are simply not467parsed, and the pattern effectively switches into `noextglob:468true` mode for the contents of that nested sub-pattern. This will469typically _not_ result in a match, but is considered a valid470trade-off for security and performance.471 472## Comparisons to other fnmatch/glob implementations473 474While strict compliance with the existing standards is a475worthwhile goal, some discrepancies exist between minimatch and476other implementations. Some are intentional, and some are477unavoidable.478 479If the pattern starts with a `!` character, then it is negated. Set the480`nonegate` flag to suppress this behavior, and treat leading `!`481characters normally. This is perhaps relevant if you wish to start the482pattern with a negative extglob pattern like `!(a|B)`. Multiple `!`483characters at the start of a pattern will negate the pattern multiple484times.485 486If a pattern starts with `#`, then it is treated as a comment, and487will not match anything. Use `\#` to match a literal `#` at the488start of a line, or set the `nocomment` flag to suppress this behavior.489 490The double-star character `**` is supported by default, unless the491`noglobstar` flag is set. This is supported in the manner of bsdglob492and bash 4.1, where `**` only has special significance if it is the only493thing in a path part. That is, `a/**/b` will match `a/x/y/b`, but494`a/**b` will not.495 496If an escaped pattern has no matches, and the `nonull` flag is set,497then minimatch.match returns the pattern as-provided, rather than498interpreting the character escapes. For example,499`minimatch.match([], "\\*a\\?")` will return `"\\*a\\?"` rather than500`"*a?"`. This is akin to setting the `nullglob` option in bash, except501that it does not resolve escaped pattern characters.502 503If brace expansion is not disabled, then it is performed before any504other interpretation of the glob pattern. Thus, a pattern like505`+(a|{b),c)}`, which would not be valid in bash or zsh, is expanded506**first** into the set of `+(a|b)` and `+(a|c)`, and those patterns are507checked for validity. Since those two are valid, matching proceeds.508 509Negated extglob patterns are handled as closely as possible to510Bash semantics, but there are some cases with negative extglobs511which are exceedingly difficult to express in a JavaScript512regular expression. In particular the negated pattern513`<start>!(<pattern>*|)*` will in bash match anything that does514not start with `<start><pattern>`. However,515`<start>!(<pattern>*)*` _will_ match paths starting with516`<start><pattern>`, because the empty string can match against517the negated portion. In this library, `<start>!(<pattern>*|)*`518will _not_ match any pattern starting with `<start>`, due to a519difference in precisely which patterns are considered "greedy" in520Regular Expressions vs bash path expansion. This may be fixable,521but not without incurring some complexity and performance costs,522and the trade-off seems to not be worth pursuing.523 524Note that `fnmatch(3)` in libc is an extremely naive string comparison525matcher, which does not do anything special for slashes. This library is526designed to be used in glob searching and file walkers, and so it does do527special things with `/`. Thus, `foo*` will not match `foo/bar` in this528library, even though it would in `fnmatch(3)`.529