Context Navigation

source: node_modules/minimatch/dist/commonjs/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.6 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: