source: node_modules/minimatch/dist/esm/ast.js@ 81bc7da

finki-main main
Last change on this file since 81bc7da was 81bc7da, checked in by Klimentina Efremova <klimentina08642@…>, 3 months ago

Initial commit
  • Property mode set to 100644
File size: 22.3 KB
RevLine 
[81bc7da]1// parse a single path portion
2import { parseClass } from './brace-expressions.js';
3import { unescape } from './unescape.js';
4const types = new Set(['!', '?', '+', '*', '@']);
5const isExtglobType = (c) => types.has(c);
6// Patterns that get prepended to bind to the start of either the
7// entire string, or just a single path portion, to prevent dots
8// and/or traversal patterns, when needed.
9// Exts don't need the ^ or / bit, because the root binds that already.
10const startNoTraversal = '(?!(?:^|/)\\.\\.?(?:$|/))';
11const startNoDot = '(?!\\.)';
12// characters that indicate a start of pattern needs the "no dots" bit,
13// because a dot *might* be matched. ( is not in the list, because in
14// the case of a child extglob, it will handle the prevention itself.
15const addPatternStart = new Set(['[', '.']);
16// cases where traversal is A-OK, no dot prevention needed
17const justDots = new Set(['..', '.']);
18const reSpecials = new Set('().*{}+?[]^$\\!');
19const regExpEscape = (s) => s.replace(/[-[\]{}()*+?.,\\^$|#\s]/g, '\\$&');
20// any single thing other than /
21const qmark = '[^/]';
22// * => any number of characters
23const star = qmark + '*?';
24// use + when we need to ensure that *something* matches, because the * is
25// the only thing in the path portion.
26const starNoEmpty = qmark + '+?';
27// remove the \ chars that we added if we end up doing a nonmagic compare
28// const deslash = (s: string) => s.replace(/\\(.)/g, '$1')
29export class AST {
30 type;
31 #root;
32 #hasMagic;
33 #uflag = false;
34 #parts = [];
35 #parent;
36 #parentIndex;
37 #negs;
38 #filledNegs = false;
39 #options;
40 #toString;
41 // set to true if it's an extglob with no children
42 // (which really means one child of '')
43 #emptyExt = false;
44 constructor(type, parent, options = {}) {
45 this.type = type;
46 // extglobs are inherently magical
47 if (type)
48 this.#hasMagic = true;
49 this.#parent = parent;
50 this.#root = this.#parent ? this.#parent.#root : this;
51 this.#options = this.#root === this ? options : this.#root.#options;
52 this.#negs = this.#root === this ? [] : this.#root.#negs;
53 if (type === '!' && !this.#root.#filledNegs)
54 this.#negs.push(this);
55 this.#parentIndex = this.#parent ? this.#parent.#parts.length : 0;
56 }
57 get hasMagic() {
58 /* c8 ignore start */
59 if (this.#hasMagic !== undefined)
60 return this.#hasMagic;
61 /* c8 ignore stop */
62 for (const p of this.#parts) {
63 if (typeof p === 'string')
64 continue;
65 if (p.type || p.hasMagic)
66 return (this.#hasMagic = true);
67 }
68 // note: will be undefined until we generate the regexp src and find out
69 return this.#hasMagic;
70 }
71 // reconstructs the pattern
72 toString() {
73 if (this.#toString !== undefined)
74 return this.#toString;
75 if (!this.type) {
76 return (this.#toString = this.#parts.map(p => String(p)).join(''));
77 }
78 else {
79 return (this.#toString =
80 this.type + '(' + this.#parts.map(p => String(p)).join('|') + ')');
81 }
82 }
83 #fillNegs() {
84 /* c8 ignore start */
85 if (this !== this.#root)
86 throw new Error('should only call on root');
87 if (this.#filledNegs)
88 return this;
89 /* c8 ignore stop */
90 // call toString() once to fill this out
91 this.toString();
92 this.#filledNegs = true;
93 let n;
94 while ((n = this.#negs.pop())) {
95 if (n.type !== '!')
96 continue;
97 // walk up the tree, appending everthing that comes AFTER parentIndex
98 let p = n;
99 let pp = p.#parent;
100 while (pp) {
101 for (let i = p.#parentIndex + 1; !pp.type && i < pp.#parts.length; i++) {
102 for (const part of n.#parts) {
103 /* c8 ignore start */
104 if (typeof part === 'string') {
105 throw new Error('string part in extglob AST??');
106 }
107 /* c8 ignore stop */
108 part.copyIn(pp.#parts[i]);
109 }
110 }
111 p = pp;
112 pp = p.#parent;
113 }
114 }
115 return this;
116 }
117 push(...parts) {
118 for (const p of parts) {
119 if (p === '')
120 continue;
121 /* c8 ignore start */
122 if (typeof p !== 'string' &&
123 !(p instanceof AST && p.#parent === this)) {
124 throw new Error('invalid part: ' + p);
125 }
126 /* c8 ignore stop */
127 this.#parts.push(p);
128 }
129 }
130 toJSON() {
131 const ret = this.type === null ?
132 this.#parts
133 .slice()
134 .map(p => (typeof p === 'string' ? p : p.toJSON()))
135 : [this.type, ...this.#parts.map(p => p.toJSON())];
136 if (this.isStart() && !this.type)
137 ret.unshift([]);
138 if (this.isEnd() &&
139 (this === this.#root ||
140 (this.#root.#filledNegs && this.#parent?.type === '!'))) {
141 ret.push({});
142 }
143 return ret;
144 }
145 isStart() {
146 if (this.#root === this)
147 return true;
148 // if (this.type) return !!this.#parent?.isStart()
149 if (!this.#parent?.isStart())
150 return false;
151 if (this.#parentIndex === 0)
152 return true;
153 // if everything AHEAD of this is a negation, then it's still the "start"
154 const p = this.#parent;
155 for (let i = 0; i < this.#parentIndex; i++) {
156 const pp = p.#parts[i];
157 if (!(pp instanceof AST && pp.type === '!')) {
158 return false;
159 }
160 }
161 return true;
162 }
163 isEnd() {
164 if (this.#root === this)
165 return true;
166 if (this.#parent?.type === '!')
167 return true;
168 if (!this.#parent?.isEnd())
169 return false;
170 if (!this.type)
171 return this.#parent?.isEnd();
172 // if not root, it'll always have a parent
173 /* c8 ignore start */
174 const pl = this.#parent ? this.#parent.#parts.length : 0;
175 /* c8 ignore stop */
176 return this.#parentIndex === pl - 1;
177 }
178 copyIn(part) {
179 if (typeof part === 'string')
180 this.push(part);
181 else
182 this.push(part.clone(this));
183 }
184 clone(parent) {
185 const c = new AST(this.type, parent);
186 for (const p of this.#parts) {
187 c.copyIn(p);
188 }
189 return c;
190 }
191 static #parseAST(str, ast, pos, opt) {
192 let escaping = false;
193 let inBrace = false;
194 let braceStart = -1;
195 let braceNeg = false;
196 if (ast.type === null) {
197 // outside of a extglob, append until we find a start
198 let i = pos;
199 let acc = '';
200 while (i < str.length) {
201 const c = str.charAt(i++);
202 // still accumulate escapes at this point, but we do ignore
203 // starts that are escaped
204 if (escaping || c === '\\') {
205 escaping = !escaping;
206 acc += c;
207 continue;
208 }
209 if (inBrace) {
210 if (i === braceStart + 1) {
211 if (c === '^' || c === '!') {
212 braceNeg = true;
213 }
214 }
215 else if (c === ']' && !(i === braceStart + 2 && braceNeg)) {
216 inBrace = false;
217 }
218 acc += c;
219 continue;
220 }
221 else if (c === '[') {
222 inBrace = true;
223 braceStart = i;
224 braceNeg = false;
225 acc += c;
226 continue;
227 }
228 if (!opt.noext && isExtglobType(c) && str.charAt(i) === '(') {
229 ast.push(acc);
230 acc = '';
231 const ext = new AST(c, ast);
232 i = AST.#parseAST(str, ext, i, opt);
233 ast.push(ext);
234 continue;
235 }
236 acc += c;
237 }
238 ast.push(acc);
239 return i;
240 }
241 // some kind of extglob, pos is at the (
242 // find the next | or )
243 let i = pos + 1;
244 let part = new AST(null, ast);
245 const parts = [];
246 let acc = '';
247 while (i < str.length) {
248 const c = str.charAt(i++);
249 // still accumulate escapes at this point, but we do ignore
250 // starts that are escaped
251 if (escaping || c === '\\') {
252 escaping = !escaping;
253 acc += c;
254 continue;
255 }
256 if (inBrace) {
257 if (i === braceStart + 1) {
258 if (c === '^' || c === '!') {
259 braceNeg = true;
260 }
261 }
262 else if (c === ']' && !(i === braceStart + 2 && braceNeg)) {
263 inBrace = false;
264 }
265 acc += c;
266 continue;
267 }
268 else if (c === '[') {
269 inBrace = true;
270 braceStart = i;
271 braceNeg = false;
272 acc += c;
273 continue;
274 }
275 if (isExtglobType(c) && str.charAt(i) === '(') {
276 part.push(acc);
277 acc = '';
278 const ext = new AST(c, part);
279 part.push(ext);
280 i = AST.#parseAST(str, ext, i, opt);
281 continue;
282 }
283 if (c === '|') {
284 part.push(acc);
285 acc = '';
286 parts.push(part);
287 part = new AST(null, ast);
288 continue;
289 }
290 if (c === ')') {
291 if (acc === '' && ast.#parts.length === 0) {
292 ast.#emptyExt = true;
293 }
294 part.push(acc);
295 acc = '';
296 ast.push(...parts, part);
297 return i;
298 }
299 acc += c;
300 }
301 // unfinished extglob
302 // if we got here, it was a malformed extglob! not an extglob, but
303 // maybe something else in there.
304 ast.type = null;
305 ast.#hasMagic = undefined;
306 ast.#parts = [str.substring(pos - 1)];
307 return i;
308 }
309 static fromGlob(pattern, options = {}) {
310 const ast = new AST(null, undefined, options);
311 AST.#parseAST(pattern, ast, 0, options);
312 return ast;
313 }
314 // returns the regular expression if there's magic, or the unescaped
315 // string if not.
316 toMMPattern() {
317 // should only be called on root
318 /* c8 ignore start */
319 if (this !== this.#root)
320 return this.#root.toMMPattern();
321 /* c8 ignore stop */
322 const glob = this.toString();
323 const [re, body, hasMagic, uflag] = this.toRegExpSource();
324 // if we're in nocase mode, and not nocaseMagicOnly, then we do
325 // still need a regular expression if we have to case-insensitively
326 // match capital/lowercase characters.
327 const anyMagic = hasMagic ||
328 this.#hasMagic ||
329 (this.#options.nocase &&
330 !this.#options.nocaseMagicOnly &&
331 glob.toUpperCase() !== glob.toLowerCase());
332 if (!anyMagic) {
333 return body;
334 }
335 const flags = (this.#options.nocase ? 'i' : '') + (uflag ? 'u' : '');
336 return Object.assign(new RegExp(`^${re}$`, flags), {
337 _src: re,
338 _glob: glob,
339 });
340 }
341 get options() {
342 return this.#options;
343 }
344 // returns the string match, the regexp source, whether there's magic
345 // in the regexp (so a regular expression is required) and whether or
346 // not the uflag is needed for the regular expression (for posix classes)
347 // TODO: instead of injecting the start/end at this point, just return
348 // the BODY of the regexp, along with the start/end portions suitable
349 // for binding the start/end in either a joined full-path makeRe context
350 // (where we bind to (^|/), or a standalone matchPart context (where
351 // we bind to ^, and not /). Otherwise slashes get duped!
352 //
353 // In part-matching mode, the start is:
354 // - if not isStart: nothing
355 // - if traversal possible, but not allowed: ^(?!\.\.?$)
356 // - if dots allowed or not possible: ^
357 // - if dots possible and not allowed: ^(?!\.)
358 // end is:
359 // - if not isEnd(): nothing
360 // - else: $
361 //
362 // In full-path matching mode, we put the slash at the START of the
363 // pattern, so start is:
364 // - if first pattern: same as part-matching mode
365 // - if not isStart(): nothing
366 // - if traversal possible, but not allowed: /(?!\.\.?(?:$|/))
367 // - if dots allowed or not possible: /
368 // - if dots possible and not allowed: /(?!\.)
369 // end is:
370 // - if last pattern, same as part-matching mode
371 // - else nothing
372 //
373 // Always put the (?:$|/) on negated tails, though, because that has to be
374 // there to bind the end of the negated pattern portion, and it's easier to
375 // just stick it in now rather than try to inject it later in the middle of
376 // the pattern.
377 //
378 // We can just always return the same end, and leave it up to the caller
379 // to know whether it's going to be used joined or in parts.
380 // And, if the start is adjusted slightly, can do the same there:
381 // - if not isStart: nothing
382 // - if traversal possible, but not allowed: (?:/|^)(?!\.\.?$)
383 // - if dots allowed or not possible: (?:/|^)
384 // - if dots possible and not allowed: (?:/|^)(?!\.)
385 //
386 // But it's better to have a simpler binding without a conditional, for
387 // performance, so probably better to return both start options.
388 //
389 // Then the caller just ignores the end if it's not the first pattern,
390 // and the start always gets applied.
391 //
392 // But that's always going to be $ if it's the ending pattern, or nothing,
393 // so the caller can just attach $ at the end of the pattern when building.
394 //
395 // So the todo is:
396 // - better detect what kind of start is needed
397 // - return both flavors of starting pattern
398 // - attach $ at the end of the pattern when creating the actual RegExp
399 //
400 // Ah, but wait, no, that all only applies to the root when the first pattern
401 // is not an extglob. If the first pattern IS an extglob, then we need all
402 // that dot prevention biz to live in the extglob portions, because eg
403 // +(*|.x*) can match .xy but not .yx.
404 //
405 // So, return the two flavors if it's #root and the first child is not an
406 // AST, otherwise leave it to the child AST to handle it, and there,
407 // use the (?:^|/) style of start binding.
408 //
409 // Even simplified further:
410 // - Since the start for a join is eg /(?!\.) and the start for a part
411 // is ^(?!\.), we can just prepend (?!\.) to the pattern (either root
412 // or start or whatever) and prepend ^ or / at the Regexp construction.
413 toRegExpSource(allowDot) {
414 const dot = allowDot ?? !!this.#options.dot;
415 if (this.#root === this)
416 this.#fillNegs();
417 if (!this.type) {
418 const noEmpty = this.isStart() &&
419 this.isEnd() &&
420 !this.#parts.some(s => typeof s !== 'string');
421 const src = this.#parts
422 .map(p => {
423 const [re, _, hasMagic, uflag] = typeof p === 'string' ?
424 AST.#parseGlob(p, this.#hasMagic, noEmpty)
425 : p.toRegExpSource(allowDot);
426 this.#hasMagic = this.#hasMagic || hasMagic;
427 this.#uflag = this.#uflag || uflag;
428 return re;
429 })
430 .join('');
431 let start = '';
432 if (this.isStart()) {
433 if (typeof this.#parts[0] === 'string') {
434 // this is the string that will match the start of the pattern,
435 // so we need to protect against dots and such.
436 // '.' and '..' cannot match unless the pattern is that exactly,
437 // even if it starts with . or dot:true is set.
438 const dotTravAllowed = this.#parts.length === 1 && justDots.has(this.#parts[0]);
439 if (!dotTravAllowed) {
440 const aps = addPatternStart;
441 // check if we have a possibility of matching . or ..,
442 // and prevent that.
443 const needNoTrav =
444 // dots are allowed, and the pattern starts with [ or .
445 (dot && aps.has(src.charAt(0))) ||
446 // the pattern starts with \., and then [ or .
447 (src.startsWith('\\.') && aps.has(src.charAt(2))) ||
448 // the pattern starts with \.\., and then [ or .
449 (src.startsWith('\\.\\.') && aps.has(src.charAt(4)));
450 // no need to prevent dots if it can't match a dot, or if a
451 // sub-pattern will be preventing it anyway.
452 const needNoDot = !dot && !allowDot && aps.has(src.charAt(0));
453 start =
454 needNoTrav ? startNoTraversal
455 : needNoDot ? startNoDot
456 : '';
457 }
458 }
459 }
460 // append the "end of path portion" pattern to negation tails
461 let end = '';
462 if (this.isEnd() &&
463 this.#root.#filledNegs &&
464 this.#parent?.type === '!') {
465 end = '(?:$|\\/)';
466 }
467 const final = start + src + end;
468 return [
469 final,
470 unescape(src),
471 (this.#hasMagic = !!this.#hasMagic),
472 this.#uflag,
473 ];
474 }
475 // We need to calculate the body *twice* if it's a repeat pattern
476 // at the start, once in nodot mode, then again in dot mode, so a
477 // pattern like *(?) can match 'x.y'
478 const repeated = this.type === '*' || this.type === '+';
479 // some kind of extglob
480 const start = this.type === '!' ? '(?:(?!(?:' : '(?:';
481 let body = this.#partsToRegExp(dot);
482 if (this.isStart() && this.isEnd() && !body && this.type !== '!') {
483 // invalid extglob, has to at least be *something* present, if it's
484 // the entire path portion.
485 const s = this.toString();
486 this.#parts = [s];
487 this.type = null;
488 this.#hasMagic = undefined;
489 return [s, unescape(this.toString()), false, false];
490 }
491 // XXX abstract out this map method
492 let bodyDotAllowed = !repeated || allowDot || dot || !startNoDot ?
493 ''
494 : this.#partsToRegExp(true);
495 if (bodyDotAllowed === body) {
496 bodyDotAllowed = '';
497 }
498 if (bodyDotAllowed) {
499 body = `(?:${body})(?:${bodyDotAllowed})*?`;
500 }
501 // an empty !() is exactly equivalent to a starNoEmpty
502 let final = '';
503 if (this.type === '!' && this.#emptyExt) {
504 final = (this.isStart() && !dot ? startNoDot : '') + starNoEmpty;
505 }
506 else {
507 const close = this.type === '!' ?
508 // !() must match something,but !(x) can match ''
509 '))' +
510 (this.isStart() && !dot && !allowDot ? startNoDot : '') +
511 star +
512 ')'
513 : this.type === '@' ? ')'
514 : this.type === '?' ? ')?'
515 : this.type === '+' && bodyDotAllowed ? ')'
516 : this.type === '*' && bodyDotAllowed ? `)?`
517 : `)${this.type}`;
518 final = start + body + close;
519 }
520 return [
521 final,
522 unescape(body),
523 (this.#hasMagic = !!this.#hasMagic),
524 this.#uflag,
525 ];
526 }
527 #partsToRegExp(dot) {
528 return this.#parts
529 .map(p => {
530 // extglob ASTs should only contain parent ASTs
531 /* c8 ignore start */
532 if (typeof p === 'string') {
533 throw new Error('string type in extglob ast??');
534 }
535 /* c8 ignore stop */
536 // can ignore hasMagic, because extglobs are already always magic
537 const [re, _, _hasMagic, uflag] = p.toRegExpSource(dot);
538 this.#uflag = this.#uflag || uflag;
539 return re;
540 })
541 .filter(p => !(this.isStart() && this.isEnd()) || !!p)
542 .join('|');
543 }
544 static #parseGlob(glob, hasMagic, noEmpty = false) {
545 let escaping = false;
546 let re = '';
547 let uflag = false;
548 // multiple stars that aren't globstars coalesce into one *
549 let inStar = false;
550 for (let i = 0; i < glob.length; i++) {
551 const c = glob.charAt(i);
552 if (escaping) {
553 escaping = false;
554 re += (reSpecials.has(c) ? '\\' : '') + c;
555 continue;
556 }
557 if (c === '*') {
558 if (inStar)
559 continue;
560 inStar = true;
561 re += noEmpty && /^[*]+$/.test(glob) ? starNoEmpty : star;
562 hasMagic = true;
563 continue;
564 }
565 else {
566 inStar = false;
567 }
568 if (c === '\\') {
569 if (i === glob.length - 1) {
570 re += '\\\\';
571 }
572 else {
573 escaping = true;
574 }
575 continue;
576 }
577 if (c === '[') {
578 const [src, needUflag, consumed, magic] = parseClass(glob, i);
579 if (consumed) {
580 re += src;
581 uflag = uflag || needUflag;
582 i += consumed - 1;
583 hasMagic = hasMagic || magic;
584 continue;
585 }
586 }
587 if (c === '?') {
588 re += qmark;
589 hasMagic = true;
590 continue;
591 }
592 re += regExpEscape(c);
593 }
594 return [re, unescape(glob), !!hasMagic, uflag];
595 }
596}
597//# sourceMappingURL=ast.js.map
Note: See TracBrowser for help on using the repository browser.