Brunobkr/llama.cpp_AlgMor24_github

1import { expand } from 'brace-expansion';2import { assertValidPattern } from './assert-valid-pattern.js';3import { AST } from './ast.js';4import { escape } from './escape.js';5import { unescape } from './unescape.js';6export const minimatch = (p, pattern, options = {}) => {7    assertValidPattern(pattern);8    // shortcut: comments match nothing.9    if (!options.nocomment && pattern.charAt(0) === '#') {10        return false;11    }12    return new Minimatch(pattern, options).match(p);13};14// Optimized checking for the most common glob patterns.15const starDotExtRE = /^\*+([^+@!?*[(]*)$/;16const starDotExtTest = (ext) => (f) => !f.startsWith('.') && f.endsWith(ext);17const starDotExtTestDot = (ext) => (f) => f.endsWith(ext);18const starDotExtTestNocase = (ext) => {19    ext = ext.toLowerCase();20    return (f) => !f.startsWith('.') && f.toLowerCase().endsWith(ext);21};22const starDotExtTestNocaseDot = (ext) => {23    ext = ext.toLowerCase();24    return (f) => f.toLowerCase().endsWith(ext);25};26const starDotStarRE = /^\*+\.\*+$/;27const starDotStarTest = (f) => !f.startsWith('.') && f.includes('.');28const starDotStarTestDot = (f) => f !== '.' && f !== '..' && f.includes('.');29const dotStarRE = /^\.\*+$/;30const dotStarTest = (f) => f !== '.' && f !== '..' && f.startsWith('.');31const starRE = /^\*+$/;32const starTest = (f) => f.length !== 0 && !f.startsWith('.');33const starTestDot = (f) => f.length !== 0 && f !== '.' && f !== '..';34const qmarksRE = /^\?+([^+@!?*[(]*)?$/;35const qmarksTestNocase = ([$0, ext = '']) => {36    const noext = qmarksTestNoExt([$0]);37    if (!ext)38        return noext;39    ext = ext.toLowerCase();40    return (f) => noext(f) && f.toLowerCase().endsWith(ext);41};42const qmarksTestNocaseDot = ([$0, ext = '']) => {43    const noext = qmarksTestNoExtDot([$0]);44    if (!ext)45        return noext;46    ext = ext.toLowerCase();47    return (f) => noext(f) && f.toLowerCase().endsWith(ext);48};49const qmarksTestDot = ([$0, ext = '']) => {50    const noext = qmarksTestNoExtDot([$0]);51    return !ext ? noext : (f) => noext(f) && f.endsWith(ext);52};53const qmarksTest = ([$0, ext = '']) => {54    const noext = qmarksTestNoExt([$0]);55    return !ext ? noext : (f) => noext(f) && f.endsWith(ext);56};57const qmarksTestNoExt = ([$0]) => {58    const len = $0.length;59    return (f) => f.length === len && !f.startsWith('.');60};61const qmarksTestNoExtDot = ([$0]) => {62    const len = $0.length;63    return (f) => f.length === len && f !== '.' && f !== '..';64};65/* c8 ignore start */66const defaultPlatform = (typeof process === 'object' && process ?67    (typeof process.env === 'object' &&68        process.env &&69        process.env.__MINIMATCH_TESTING_PLATFORM__) ||70        process.platform71    : 'posix');72const path = {73    win32: { sep: '\\' },74    posix: { sep: '/' },75};76/* c8 ignore stop */77export const sep = defaultPlatform === 'win32' ? path.win32.sep : path.posix.sep;78minimatch.sep = sep;79export const GLOBSTAR = Symbol('globstar **');80minimatch.GLOBSTAR = GLOBSTAR;81// any single thing other than /82// don't need to escape / when using new RegExp()83const qmark = '[^/]';84// * => any number of characters85const star = qmark + '*?';86// ** when dots are allowed.  Anything goes, except .. and .87// not (^ or / followed by one or two dots followed by $ or /),88// followed by anything, any number of times.89const twoStarDot = '(?:(?!(?:\\/|^)(?:\\.{1,2})($|\\/)).)*?';90// not a ^ or / followed by a dot,91// followed by anything, any number of times.92const twoStarNoDot = '(?:(?!(?:\\/|^)\\.).)*?';93export const filter = (pattern, options = {}) => (p) => minimatch(p, pattern, options);94minimatch.filter = filter;95const ext = (a, b = {}) => Object.assign({}, a, b);96export const defaults = (def) => {97    if (!def || typeof def !== 'object' || !Object.keys(def).length) {98        return minimatch;99    }100    const orig = minimatch;101    const m = (p, pattern, options = {}) => orig(p, pattern, ext(def, options));102    return Object.assign(m, {103        Minimatch: class Minimatch extends orig.Minimatch {104            constructor(pattern, options = {}) {105                super(pattern, ext(def, options));106            }107            static defaults(options) {108                return orig.defaults(ext(def, options)).Minimatch;109            }110        },111        AST: class AST extends orig.AST {112            /* c8 ignore start */113            constructor(type, parent, options = {}) {114                super(type, parent, ext(def, options));115            }116            /* c8 ignore stop */117            static fromGlob(pattern, options = {}) {118                return orig.AST.fromGlob(pattern, ext(def, options));119            }120        },121        unescape: (s, options = {}) => orig.unescape(s, ext(def, options)),122        escape: (s, options = {}) => orig.escape(s, ext(def, options)),123        filter: (pattern, options = {}) => orig.filter(pattern, ext(def, options)),124        defaults: (options) => orig.defaults(ext(def, options)),125        makeRe: (pattern, options = {}) => orig.makeRe(pattern, ext(def, options)),126        braceExpand: (pattern, options = {}) => orig.braceExpand(pattern, ext(def, options)),127        match: (list, pattern, options = {}) => orig.match(list, pattern, ext(def, options)),128        sep: orig.sep,129        GLOBSTAR: GLOBSTAR,130    });131};132minimatch.defaults = defaults;133// Brace expansion:134// a{b,c}d -> abd acd135// a{b,}c -> abc ac136// a{0..3}d -> a0d a1d a2d a3d137// a{b,c{d,e}f}g -> abg acdfg acefg138// a{b,c}d{e,f}g -> abdeg acdeg abdeg abdfg139//140// Invalid sets are not expanded.141// a{2..}b -> a{2..}b142// a{b}c -> a{b}c143export const braceExpand = (pattern, options = {}) => {144    assertValidPattern(pattern);145    // Thanks to Yeting Li <https://github.com/yetingli> for146    // improving this regexp to avoid a ReDOS vulnerability.147    if (options.nobrace || !/\{(?:(?!\{).)*\}/.test(pattern)) {148        // shortcut. no need to expand.149        return [pattern];150    }151    return expand(pattern, { max: options.braceExpandMax });152};153minimatch.braceExpand = braceExpand;154// parse a component of the expanded set.155// At this point, no pattern may contain "/" in it156// so we're going to return a 2d array, where each entry is the full157// pattern, split on '/', and then turned into a regular expression.158// A regexp is made at the end which joins each array with an159// escaped /, and another full one which joins each regexp with |.160//161// Following the lead of Bash 4.1, note that "**" only has special meaning162// when it is the *only* thing in a path portion.  Otherwise, any series163// of * is equivalent to a single *.  Globstar behavior is enabled by164// default, and can be disabled by setting options.noglobstar.165export const makeRe = (pattern, options = {}) => new Minimatch(pattern, options).makeRe();166minimatch.makeRe = makeRe;167export const match = (list, pattern, options = {}) => {168    const mm = new Minimatch(pattern, options);169    list = list.filter(f => mm.match(f));170    if (mm.options.nonull && !list.length) {171        list.push(pattern);172    }173    return list;174};175minimatch.match = match;176// replace stuff like \* with *177const globMagic = /[?*]|[+@!]\(.*?\)|\[|\]/;178const regExpEscape = (s) => s.replace(/[-[\]{}()*+?.,\\^$|#\s]/g, '\\$&');179export class Minimatch {180    options;181    set;182    pattern;183    windowsPathsNoEscape;184    nonegate;185    negate;186    comment;187    empty;188    preserveMultipleSlashes;189    partial;190    globSet;191    globParts;192    nocase;193    isWindows;194    platform;195    windowsNoMagicRoot;196    maxGlobstarRecursion;197    regexp;198    constructor(pattern, options = {}) {199        assertValidPattern(pattern);200        options = options || {};201        this.options = options;202        this.maxGlobstarRecursion = options.maxGlobstarRecursion ?? 200;203        this.pattern = pattern;204        this.platform = options.platform || defaultPlatform;205        this.isWindows = this.platform === 'win32';206        // avoid the annoying deprecation flag lol207        const awe = ('allowWindow' + 'sEscape');208        this.windowsPathsNoEscape =209            !!options.windowsPathsNoEscape || options[awe] === false;210        if (this.windowsPathsNoEscape) {211            this.pattern = this.pattern.replace(/\\/g, '/');212        }213        this.preserveMultipleSlashes = !!options.preserveMultipleSlashes;214        this.regexp = null;215        this.negate = false;216        this.nonegate = !!options.nonegate;217        this.comment = false;218        this.empty = false;219        this.partial = !!options.partial;220        this.nocase = !!this.options.nocase;221        this.windowsNoMagicRoot =222            options.windowsNoMagicRoot !== undefined ?223                options.windowsNoMagicRoot224                : !!(this.isWindows && this.nocase);225        this.globSet = [];226        this.globParts = [];227        this.set = [];228        // make the set of regexps etc.229        this.make();230    }231    hasMagic() {232        if (this.options.magicalBraces && this.set.length > 1) {233            return true;234        }235        for (const pattern of this.set) {236            for (const part of pattern) {237                if (typeof part !== 'string')238                    return true;239            }240        }241        return false;242    }243    debug(..._) { }244    make() {245        const pattern = this.pattern;246        const options = this.options;247        // empty patterns and comments match nothing.248        if (!options.nocomment && pattern.charAt(0) === '#') {249            this.comment = true;250            return;251        }252        if (!pattern) {253            this.empty = true;254            return;255        }256        // step 1: figure out negation, etc.257        this.parseNegate();258        // step 2: expand braces259        this.globSet = [...new Set(this.braceExpand())];260        if (options.debug) {261            //oxlint-disable-next-line no-console262            this.debug = (...args) => console.error(...args);263        }264        this.debug(this.pattern, this.globSet);265        // step 3: now we have a set, so turn each one into a series of266        // path-portion matching patterns.267        // These will be regexps, except in the case of "**", which is268        // set to the GLOBSTAR object for globstar behavior,269        // and will not contain any / characters270        //271        // First, we preprocess to make the glob pattern sets a bit simpler272        // and deduped.  There are some perf-killing patterns that can cause273        // problems with a glob walk, but we can simplify them down a bit.274        const rawGlobParts = this.globSet.map(s => this.slashSplit(s));275        this.globParts = this.preprocess(rawGlobParts);276        this.debug(this.pattern, this.globParts);277        // glob --> regexps278        let set = this.globParts.map((s, _, __) => {279            if (this.isWindows && this.windowsNoMagicRoot) {280                // check if it's a drive or unc path.281                const isUNC = s[0] === '' &&282                    s[1] === '' &&283                    (s[2] === '?' || !globMagic.test(s[2])) &&284                    !globMagic.test(s[3]);285                const isDrive = /^[a-z]:/i.test(s[0]);286                if (isUNC) {287                    return [288                        ...s.slice(0, 4),289                        ...s.slice(4).map(ss => this.parse(ss)),290                    ];291                }292                else if (isDrive) {293                    return [s[0], ...s.slice(1).map(ss => this.parse(ss))];294                }295            }296            return s.map(ss => this.parse(ss));297        });298        this.debug(this.pattern, set);299        // filter out everything that didn't compile properly.300        this.set = set.filter(s => s.indexOf(false) === -1);301        // do not treat the ? in UNC paths as magic302        if (this.isWindows) {303            for (let i = 0; i < this.set.length; i++) {304                const p = this.set[i];305                if (p[0] === '' &&306                    p[1] === '' &&307                    this.globParts[i][2] === '?' &&308                    typeof p[3] === 'string' &&309                    /^[a-z]:$/i.test(p[3])) {310                    p[2] = '?';311                }312            }313        }314        this.debug(this.pattern, this.set);315    }316    // various transforms to equivalent pattern sets that are317    // faster to process in a filesystem walk.  The goal is to318    // eliminate what we can, and push all ** patterns as far319    // to the right as possible, even if it increases the number320    // of patterns that we have to process.321    preprocess(globParts) {322        // if we're not in globstar mode, then turn ** into *323        if (this.options.noglobstar) {324            for (const partset of globParts) {325                for (let j = 0; j < partset.length; j++) {326                    if (partset[j] === '**') {327                        partset[j] = '*';328                    }329                }330            }331        }332        const { optimizationLevel = 1 } = this.options;333        if (optimizationLevel >= 2) {334            // aggressive optimization for the purpose of fs walking335            globParts = this.firstPhasePreProcess(globParts);336            globParts = this.secondPhasePreProcess(globParts);337        }338        else if (optimizationLevel >= 1) {339            // just basic optimizations to remove some .. parts340            globParts = this.levelOneOptimize(globParts);341        }342        else {343            // just collapse multiple ** portions into one344            globParts = this.adjascentGlobstarOptimize(globParts);345        }346        return globParts;347    }348    // just get rid of adjascent ** portions349    adjascentGlobstarOptimize(globParts) {350        return globParts.map(parts => {351            let gs = -1;352            while (-1 !== (gs = parts.indexOf('**', gs + 1))) {353                let i = gs;354                while (parts[i + 1] === '**') {355                    i++;356                }357                if (i !== gs) {358                    parts.splice(gs, i - gs);359                }360            }361            return parts;362        });363    }364    // get rid of adjascent ** and resolve .. portions365    levelOneOptimize(globParts) {366        return globParts.map(parts => {367            parts = parts.reduce((set, part) => {368                const prev = set[set.length - 1];369                if (part === '**' && prev === '**') {370                    return set;371                }372                if (part === '..') {373                    if (prev && prev !== '..' && prev !== '.' && prev !== '**') {374                        set.pop();375                        return set;376                    }377                }378                set.push(part);379                return set;380            }, []);381            return parts.length === 0 ? [''] : parts;382        });383    }384    levelTwoFileOptimize(parts) {385        if (!Array.isArray(parts)) {386            parts = this.slashSplit(parts);387        }388        let didSomething = false;389        do {390            didSomething = false;391            // <pre>/<e>/<rest> -> <pre>/<rest>392            if (!this.preserveMultipleSlashes) {393                for (let i = 1; i < parts.length - 1; i++) {394                    const p = parts[i];395                    // don't squeeze out UNC patterns396                    if (i === 1 && p === '' && parts[0] === '')397                        continue;398                    if (p === '.' || p === '') {399                        didSomething = true;400                        parts.splice(i, 1);401                        i--;402                    }403                }404                if (parts[0] === '.' &&405                    parts.length === 2 &&406                    (parts[1] === '.' || parts[1] === '')) {407                    didSomething = true;408                    parts.pop();409                }410            }411            // <pre>/<p>/../<rest> -> <pre>/<rest>412            let dd = 0;413            while (-1 !== (dd = parts.indexOf('..', dd + 1))) {414                const p = parts[dd - 1];415                if (p &&416                    p !== '.' &&417                    p !== '..' &&418                    p !== '**' &&419                    !(this.isWindows && /^[a-z]:$/i.test(p))) {420                    didSomething = true;421                    parts.splice(dd - 1, 2);422                    dd -= 2;423                }424            }425        } while (didSomething);426        return parts.length === 0 ? [''] : parts;427    }428    // First phase: single-pattern processing429    // <pre> is 1 or more portions430    // <rest> is 1 or more portions431    // <p> is any portion other than ., .., '', or **432    // <e> is . or ''433    //434    // **/.. is *brutal* for filesystem walking performance, because435    // it effectively resets the recursive walk each time it occurs,436    // and ** cannot be reduced out by a .. pattern part like a regexp437    // or most strings (other than .., ., and '') can be.438    //439    // <pre>/**/../<p>/<p>/<rest> -> {<pre>/../<p>/<p>/<rest>,<pre>/**/<p>/<p>/<rest>}440    // <pre>/<e>/<rest> -> <pre>/<rest>441    // <pre>/<p>/../<rest> -> <pre>/<rest>442    // **/**/<rest> -> **/<rest>443    //444    // **/*/<rest> -> */**/<rest> <== not valid because ** doesn't follow445    // this WOULD be allowed if ** did follow symlinks, or * didn't446    firstPhasePreProcess(globParts) {447        let didSomething = false;448        do {449            didSomething = false;450            // <pre>/**/../<p>/<p>/<rest> -> {<pre>/../<p>/<p>/<rest>,<pre>/**/<p>/<p>/<rest>}451            for (let parts of globParts) {452                let gs = -1;453                while (-1 !== (gs = parts.indexOf('**', gs + 1))) {454                    let gss = gs;455                    while (parts[gss + 1] === '**') {456                        // <pre>/**/**/<rest> -> <pre>/**/<rest>457                        gss++;458                    }459                    // eg, if gs is 2 and gss is 4, that means we have 3 **460                    // parts, and can remove 2 of them.461                    if (gss > gs) {462                        parts.splice(gs + 1, gss - gs);463                    }464                    let next = parts[gs + 1];465                    const p = parts[gs + 2];466                    const p2 = parts[gs + 3];467                    if (next !== '..')468                        continue;469                    if (!p ||470                        p === '.' ||471                        p === '..' ||472                        !p2 ||473                        p2 === '.' ||474                        p2 === '..') {475                        continue;476                    }477                    didSomething = true;478                    // edit parts in place, and push the new one479                    parts.splice(gs, 1);480                    const other = parts.slice(0);481                    other[gs] = '**';482                    globParts.push(other);483                    gs--;484                }485                // <pre>/<e>/<rest> -> <pre>/<rest>486                if (!this.preserveMultipleSlashes) {487                    for (let i = 1; i < parts.length - 1; i++) {488                        const p = parts[i];489                        // don't squeeze out UNC patterns490                        if (i === 1 && p === '' && parts[0] === '')491                            continue;492                        if (p === '.' || p === '') {493                            didSomething = true;494                            parts.splice(i, 1);495                            i--;496                        }497                    }498                    if (parts[0] === '.' &&499                        parts.length === 2 &&500                        (parts[1] === '.' || parts[1] === '')) {501                        didSomething = true;502                        parts.pop();503                    }504                }505                // <pre>/<p>/../<rest> -> <pre>/<rest>506                let dd = 0;507                while (-1 !== (dd = parts.indexOf('..', dd + 1))) {508                    const p = parts[dd - 1];509                    if (p && p !== '.' && p !== '..' && p !== '**') {510                        didSomething = true;511                        const needDot = dd === 1 && parts[dd + 1] === '**';512                        const splin = needDot ? ['.'] : [];513                        parts.splice(dd - 1, 2, ...splin);514                        if (parts.length === 0)515                            parts.push('');516                        dd -= 2;517                    }518                }519            }520        } while (didSomething);521        return globParts;522    }523    // second phase: multi-pattern dedupes524    // {<pre>/*/<rest>,<pre>/<p>/<rest>} -> <pre>/*/<rest>525    // {<pre>/<rest>,<pre>/<rest>} -> <pre>/<rest>526    // {<pre>/**/<rest>,<pre>/<rest>} -> <pre>/**/<rest>527    //528    // {<pre>/**/<rest>,<pre>/**/<p>/<rest>} -> <pre>/**/<rest>529    // ^-- not valid because ** doens't follow symlinks530    secondPhasePreProcess(globParts) {531        for (let i = 0; i < globParts.length - 1; i++) {532            for (let j = i + 1; j < globParts.length; j++) {533                const matched = this.partsMatch(globParts[i], globParts[j], !this.preserveMultipleSlashes);534                if (matched) {535                    globParts[i] = [];536                    globParts[j] = matched;537                    break;538                }539            }540        }541        return globParts.filter(gs => gs.length);542    }543    partsMatch(a, b, emptyGSMatch = false) {544        let ai = 0;545        let bi = 0;546        let result = [];547        let which = '';548        while (ai < a.length && bi < b.length) {549            if (a[ai] === b[bi]) {550                result.push(which === 'b' ? b[bi] : a[ai]);551                ai++;552                bi++;553            }554            else if (emptyGSMatch && a[ai] === '**' && b[bi] === a[ai + 1]) {555                result.push(a[ai]);556                ai++;557            }558            else if (emptyGSMatch && b[bi] === '**' && a[ai] === b[bi + 1]) {559                result.push(b[bi]);560                bi++;561            }562            else if (a[ai] === '*' &&563                b[bi] &&564                (this.options.dot || !b[bi].startsWith('.')) &&565                b[bi] !== '**') {566                if (which === 'b')567                    return false;568                which = 'a';569                result.push(a[ai]);570                ai++;571                bi++;572            }573            else if (b[bi] === '*' &&574                a[ai] &&575                (this.options.dot || !a[ai].startsWith('.')) &&576                a[ai] !== '**') {577                if (which === 'a')578                    return false;579                which = 'b';580                result.push(b[bi]);581                ai++;582                bi++;583            }584            else {585                return false;586            }587        }588        // if we fall out of the loop, it means they two are identical589        // as long as their lengths match590        return a.length === b.length && result;591    }592    parseNegate() {593        if (this.nonegate)594            return;595        const pattern = this.pattern;596        let negate = false;597        let negateOffset = 0;598        for (let i = 0; i < pattern.length && pattern.charAt(i) === '!'; i++) {599            negate = !negate;600            negateOffset++;601        }602        if (negateOffset)603            this.pattern = pattern.slice(negateOffset);604        this.negate = negate;605    }606    // set partial to true to test if, for example,607    // "/a/b" matches the start of "/*/b/*/d"608    // Partial means, if you run out of file before you run609    // out of pattern, then that's fine, as long as all610    // the parts match.611    matchOne(file, pattern, partial = false) {612        let fileStartIndex = 0;613        let patternStartIndex = 0;614        // UNC paths like //?/X:/... can match X:/... and vice versa615        // Drive letters in absolute drive or unc paths are always compared616        // case-insensitively.617        if (this.isWindows) {618            const fileDrive = typeof file[0] === 'string' && /^[a-z]:$/i.test(file[0]);619            const fileUNC = !fileDrive &&620                file[0] === '' &&621                file[1] === '' &&622                file[2] === '?' &&623                /^[a-z]:$/i.test(file[3]);624            const patternDrive = typeof pattern[0] === 'string' && /^[a-z]:$/i.test(pattern[0]);625            const patternUNC = !patternDrive &&626                pattern[0] === '' &&627                pattern[1] === '' &&628                pattern[2] === '?' &&629                typeof pattern[3] === 'string' &&630                /^[a-z]:$/i.test(pattern[3]);631            const fdi = fileUNC ? 3632                : fileDrive ? 0633                    : undefined;634            const pdi = patternUNC ? 3635                : patternDrive ? 0636                    : undefined;637            if (typeof fdi === 'number' && typeof pdi === 'number') {638                const [fd, pd] = [639                    file[fdi],640                    pattern[pdi],641                ];642                // start matching at the drive letter index of each643                if (fd.toLowerCase() === pd.toLowerCase()) {644                    pattern[pdi] = fd;645                    patternStartIndex = pdi;646                    fileStartIndex = fdi;647                }648            }649        }650        // resolve and reduce . and .. portions in the file as well.651        // don't need to do the second phase, because it's only one string[]652        const { optimizationLevel = 1 } = this.options;653        if (optimizationLevel >= 2) {654            file = this.levelTwoFileOptimize(file);655        }656        if (pattern.includes(GLOBSTAR)) {657            return this.#matchGlobstar(file, pattern, partial, fileStartIndex, patternStartIndex);658        }659        return this.#matchOne(file, pattern, partial, fileStartIndex, patternStartIndex);660    }661    #matchGlobstar(file, pattern, partial, fileIndex, patternIndex) {662        // split the pattern into head, tail, and middle of ** delimited parts663        const firstgs = pattern.indexOf(GLOBSTAR, patternIndex);664        const lastgs = pattern.lastIndexOf(GLOBSTAR);665        // split the pattern up into globstar-delimited sections666        // the tail has to be at the end, and the others just have667        // to be found in order from the head.668        const [head, body, tail] = partial ?669            [670                pattern.slice(patternIndex, firstgs),671                pattern.slice(firstgs + 1),672                [],673            ]674            : [675                pattern.slice(patternIndex, firstgs),676                pattern.slice(firstgs + 1, lastgs),677                pattern.slice(lastgs + 1),678            ];679        // check the head, from the current file/pattern index.680        if (head.length) {681            const fileHead = file.slice(fileIndex, fileIndex + head.length);682            if (!this.#matchOne(fileHead, head, partial, 0, 0)) {683                return false;684            }685            fileIndex += head.length;686            patternIndex += head.length;687        }688        // now we know the head matches!689        // if the last portion is not empty, it MUST match the end690        // check the tail691        let fileTailMatch = 0;692        if (tail.length) {693            // if head + tail > file, then we cannot possibly match694            if (tail.length + fileIndex > file.length)695                return false;696            // try to match the tail697            let tailStart = file.length - tail.length;698            if (this.#matchOne(file, tail, partial, tailStart, 0)) {699                fileTailMatch = tail.length;700            }701            else {702                // affordance for stuff like a/**/* matching a/b/703                // if the last file portion is '', and there's more to the pattern704                // then try without the '' bit.705                if (file[file.length - 1] !== '' ||706                    fileIndex + tail.length === file.length) {707                    return false;708                }709                tailStart--;710                if (!this.#matchOne(file, tail, partial, tailStart, 0)) {711                    return false;712                }713                fileTailMatch = tail.length + 1;714            }715        }716        // now we know the tail matches!717        // the middle is zero or more portions wrapped in **, possibly718        // containing more ** sections.719        // so a/**/b/**/c/**/d has become **/b/**/c/**720        // if it's empty, it means a/**/b, just verify we have no bad dots721        // if there's no tail, so it ends on /**, then we must have *something*722        // after the head, or it's not a matc723        if (!body.length) {724            let sawSome = !!fileTailMatch;725            for (let i = fileIndex; i < file.length - fileTailMatch; i++) {726                const f = String(file[i]);727                sawSome = true;728                if (f === '.' ||729                    f === '..' ||730                    (!this.options.dot && f.startsWith('.'))) {731                    return false;732                }733            }734            // in partial mode, we just need to get past all file parts735            return partial || sawSome;736        }737        // now we know that there's one or more body sections, which can738        // be matched anywhere from the 0 index (because the head was pruned)739        // through to the length-fileTailMatch index.740        // split the body up into sections, and note the minimum index it can741        // be found at (start with the length of all previous segments)742        // [section, before, after]743        const bodySegments = [[[], 0]];744        let currentBody = bodySegments[0];745        let nonGsParts = 0;746        const nonGsPartsSums = [0];747        for (const b of body) {748            if (b === GLOBSTAR) {749                nonGsPartsSums.push(nonGsParts);750                currentBody = [[], 0];751                bodySegments.push(currentBody);752            }753            else {754                currentBody[0].push(b);755                nonGsParts++;756            }757        }758        let i = bodySegments.length - 1;759        const fileLength = file.length - fileTailMatch;760        for (const b of bodySegments) {761            b[1] = fileLength - (nonGsPartsSums[i--] + b[0].length);762        }763        return !!this.#matchGlobStarBodySections(file, bodySegments, fileIndex, 0, partial, 0, !!fileTailMatch);764    }765    // return false for "nope, not matching"766    // return null for "not matching, cannot keep trying"767    #matchGlobStarBodySections(file, 768    // pattern section, last possible position for it769    bodySegments, fileIndex, bodyIndex, partial, globStarDepth, sawTail) {770        // take the first body segment, and walk from fileIndex to its "after"771        // value at the end772        // If it doesn't match at that position, we increment, until we hit773        // that final possible position, and give up.774        // If it does match, then advance and try to rest.775        // If any of them fail we keep walking forward.776        // this is still a bit recursively painful, but it's more constrained777        // than previous implementations, because we never test something that778        // can't possibly be a valid matching condition.779        const bs = bodySegments[bodyIndex];780        if (!bs) {781            // just make sure that there's no bad dots782            for (let i = fileIndex; i < file.length; i++) {783                sawTail = true;784                const f = file[i];785                if (f === '.' ||786                    f === '..' ||787                    (!this.options.dot && f.startsWith('.'))) {788                    return false;789                }790            }791            return sawTail;792        }793        // have a non-globstar body section to test794        const [body, after] = bs;795        while (fileIndex <= after) {796            const m = this.#matchOne(file.slice(0, fileIndex + body.length), body, partial, fileIndex, 0);797            // if limit exceeded, no match. intentional false negative,798            // acceptable break in correctness for security.799            if (m && globStarDepth < this.maxGlobstarRecursion) {800                // match! see if the rest match. if so, we're done!801                const sub = this.#matchGlobStarBodySections(file, bodySegments, fileIndex + body.length, bodyIndex + 1, partial, globStarDepth + 1, sawTail);802                if (sub !== false) {803                    return sub;804                }805            }806            const f = file[fileIndex];807            if (f === '.' ||808                f === '..' ||809                (!this.options.dot && f.startsWith('.'))) {810                return false;811            }812            fileIndex++;813        }814        // walked off. no point continuing815        return partial || null;816    }817    #matchOne(file, pattern, partial, fileIndex, patternIndex) {818        let fi;819        let pi;820        let pl;821        let fl;822        for (fi = fileIndex,823            pi = patternIndex,824            fl = file.length,825            pl = pattern.length; fi < fl && pi < pl; fi++, pi++) {826            this.debug('matchOne loop');827            let p = pattern[pi];828            let f = file[fi];829            this.debug(pattern, p, f);830            // should be impossible.831            // some invalid regexp stuff in the set.832            /* c8 ignore start */833            if (p === false || p === GLOBSTAR) {834                return false;835            }836            /* c8 ignore stop */837            // something other than **838            // non-magic patterns just have to match exactly839            // patterns with magic have been turned into regexps.840            let hit;841            if (typeof p === 'string') {842                hit = f === p;843                this.debug('string match', p, f, hit);844            }845            else {846                hit = p.test(f);847                this.debug('pattern match', p, f, hit);848            }849            if (!hit)850                return false;851        }852        // Note: ending in / means that we'll get a final ""853        // at the end of the pattern.  This can only match a854        // corresponding "" at the end of the file.855        // If the file ends in /, then it can only match a856        // a pattern that ends in /, unless the pattern just857        // doesn't have any more for it. But, a/b/ should *not*858        // match "a/b/*", even though "" matches against the859        // [^/]*? pattern, except in partial mode, where it might860        // simply not be reached yet.861        // However, a/b/ should still satisfy a/*862        // now either we fell off the end of the pattern, or we're done.863        if (fi === fl && pi === pl) {864            // ran out of pattern and filename at the same time.865            // an exact hit!866            return true;867        }868        else if (fi === fl) {869            // ran out of file, but still had pattern left.870            // this is ok if we're doing the match as part of871            // a glob fs traversal.872            return partial;873        }874        else if (pi === pl) {875            // ran out of pattern, still have file left.876            // this is only acceptable if we're on the very last877            // empty segment of a file with a trailing slash.878            // a/* should match a/b/879            return fi === fl - 1 && file[fi] === '';880            /* c8 ignore start */881        }882        else {883            // should be unreachable.884            throw new Error('wtf?');885        }886        /* c8 ignore stop */887    }888    braceExpand() {889        return braceExpand(this.pattern, this.options);890    }891    parse(pattern) {892        assertValidPattern(pattern);893        const options = this.options;894        // shortcuts895        if (pattern === '**')896            return GLOBSTAR;897        if (pattern === '')898            return '';899        // far and away, the most common glob pattern parts are900        // *, *.*, and *.<ext>  Add a fast check method for those.901        let m;902        let fastTest = null;903        if ((m = pattern.match(starRE))) {904            fastTest = options.dot ? starTestDot : starTest;905        }906        else if ((m = pattern.match(starDotExtRE))) {907            fastTest = (options.nocase ?908                options.dot ?909                    starDotExtTestNocaseDot910                    : starDotExtTestNocase911                : options.dot ? starDotExtTestDot912                    : starDotExtTest)(m[1]);913        }914        else if ((m = pattern.match(qmarksRE))) {915            fastTest = (options.nocase ?916                options.dot ?917                    qmarksTestNocaseDot918                    : qmarksTestNocase919                : options.dot ? qmarksTestDot920                    : qmarksTest)(m);921        }922        else if ((m = pattern.match(starDotStarRE))) {923            fastTest = options.dot ? starDotStarTestDot : starDotStarTest;924        }925        else if ((m = pattern.match(dotStarRE))) {926            fastTest = dotStarTest;927        }928        const re = AST.fromGlob(pattern, this.options).toMMPattern();929        if (fastTest && typeof re === 'object') {930            // Avoids overriding in frozen environments931            Reflect.defineProperty(re, 'test', { value: fastTest });932        }933        return re;934    }935    makeRe() {936        if (this.regexp || this.regexp === false)937            return this.regexp;938        // at this point, this.set is a 2d array of partial939        // pattern strings, or "**".940        //941        // It's better to use .match().  This function shouldn't942        // be used, really, but it's pretty convenient sometimes,943        // when you just want to work with a regex.944        const set = this.set;945        if (!set.length) {946            this.regexp = false;947            return this.regexp;948        }949        const options = this.options;950        const twoStar = options.noglobstar ? star951            : options.dot ? twoStarDot952                : twoStarNoDot;953        const flags = new Set(options.nocase ? ['i'] : []);954        // regexpify non-globstar patterns955        // if ** is only item, then we just do one twoStar956        // if ** is first, and there are more, prepend (\/|twoStar\/)? to next957        // if ** is last, append (\/twoStar|) to previous958        // if ** is in the middle, append (\/|\/twoStar\/) to previous959        // then filter out GLOBSTAR symbols960        let re = set961            .map(pattern => {962            const pp = pattern.map(p => {963                if (p instanceof RegExp) {964                    for (const f of p.flags.split(''))965                        flags.add(f);966                }967                return (typeof p === 'string' ? regExpEscape(p)968                    : p === GLOBSTAR ? GLOBSTAR969                        : p._src);970            });971            pp.forEach((p, i) => {972                const next = pp[i + 1];973                const prev = pp[i - 1];974                if (p !== GLOBSTAR || prev === GLOBSTAR) {975                    return;976                }977                if (prev === undefined) {978                    if (next !== undefined && next !== GLOBSTAR) {979                        pp[i + 1] = '(?:\\/|' + twoStar + '\\/)?' + next;980                    }981                    else {982                        pp[i] = twoStar;983                    }984                }985                else if (next === undefined) {986                    pp[i - 1] = prev + '(?:\\/|\\/' + twoStar + ')?';987                }988                else if (next !== GLOBSTAR) {989                    pp[i - 1] = prev + '(?:\\/|\\/' + twoStar + '\\/)' + next;990                    pp[i + 1] = GLOBSTAR;991                }992            });993            const filtered = pp.filter(p => p !== GLOBSTAR);994            // For partial matches, we need to make the pattern match995            // any prefix of the full path. We do this by generating996            // alternative patterns that match progressively longer prefixes.997            if (this.partial && filtered.length >= 1) {998                const prefixes = [];999                for (let i = 1; i <= filtered.length; i++) {1000                    prefixes.push(filtered.slice(0, i).join('/'));1001                }1002                return '(?:' + prefixes.join('|') + ')';1003            }1004            return filtered.join('/');1005        })1006            .join('|');1007        // need to wrap in parens if we had more than one thing with |,1008        // otherwise only the first will be anchored to ^ and the last to $1009        const [open, close] = set.length > 1 ? ['(?:', ')'] : ['', ''];1010        // must match entire pattern1011        // ending in a * or ** will make it less strict.1012        re = '^' + open + re + close + '$';1013        // In partial mode, '/' should always match as it's a valid prefix for any pattern1014        if (this.partial) {1015            re = '^(?:\\/|' + open + re.slice(1, -1) + close + ')$';1016        }1017        // can match anything, as long as it's not this.1018        if (this.negate)1019            re = '^(?!' + re + ').+$';1020        try {1021            this.regexp = new RegExp(re, [...flags].join(''));1022            /* c8 ignore start */1023        }1024        catch {1025            // should be impossible1026            this.regexp = false;1027        }1028        /* c8 ignore stop */1029        return this.regexp;1030    }1031    slashSplit(p) {1032        // if p starts with // on windows, we preserve that1033        // so that UNC paths aren't broken.  Otherwise, any number of1034        // / characters are coalesced into one, unless1035        // preserveMultipleSlashes is set to true.1036        if (this.preserveMultipleSlashes) {1037            return p.split('/');1038        }1039        else if (this.isWindows && /^\/\/[^/]+/.test(p)) {1040            // add an extra '' for the one we lose1041            return ['', ...p.split(/\/+/)];1042        }1043        else {1044            return p.split(/\/+/);1045        }1046    }1047    match(f, partial = this.partial) {1048        this.debug('match', f, this.pattern);1049        // short-circuit in the case of busted things.1050        // comments, etc.1051        if (this.comment) {1052            return false;1053        }1054        if (this.empty) {1055            return f === '';1056        }1057        if (f === '/' && partial) {1058            return true;1059        }1060        const options = this.options;1061        // windows: need to use /, not \1062        if (this.isWindows) {1063            f = f.split('\\').join('/');1064        }1065        // treat the test path as a set of pathparts.1066        const ff = this.slashSplit(f);1067        this.debug(this.pattern, 'split', ff);1068        // just ONE of the pattern sets in this.set needs to match1069        // in order for it to be valid.  If negating, then just one1070        // match means that we have failed.1071        // Either way, return on the first hit.1072        const set = this.set;1073        this.debug(this.pattern, 'set', set);1074        // Find the basename of the path by looking for the last non-empty segment1075        let filename = ff[ff.length - 1];1076        if (!filename) {1077            for (let i = ff.length - 2; !filename && i >= 0; i--) {1078                filename = ff[i];1079            }1080        }1081        for (const pattern of set) {1082            let file = ff;1083            if (options.matchBase && pattern.length === 1) {1084                file = [filename];1085            }1086            const hit = this.matchOne(file, pattern, partial);1087            if (hit) {1088                if (options.flipNegate) {1089                    return true;1090                }1091                return !this.negate;1092            }1093        }1094        // didn't get any hits.  this is success if it's a negative1095        // pattern, failure otherwise.1096        if (options.flipNegate) {1097            return false;1098        }1099        return this.negate;1100    }1101    static defaults(def) {1102        return minimatch.defaults(def).Minimatch;1103    }1104}1105/* c8 ignore start */1106export { AST } from './ast.js';1107export { escape } from './escape.js';1108export { unescape } from './unescape.js';1109/* c8 ignore stop */1110minimatch.AST = AST;1111minimatch.Minimatch = Minimatch;1112minimatch.escape = escape;1113minimatch.unescape = unescape;1114//# sourceMappingURL=index.js.map