Composio powers 1000+ toolkits, tool search, context management, authentication, and a sandboxed workbench to help you build AI agents that turn intent into action.

next
ts 392 lines 13.5 KB
Raw
1 import { RE2JS } from 're2js';
2 import { toUnicodePattern } from './unicode-pattern';
3
4 /**
5 * ECMAScript `\s`: the characters it matches, spelled for an RE2 class body.
6 * RE2's own `\s` is ASCII-only, so both `\s` and `\S` are spelled out.
7 */
8 const WHITESPACE =
9 '\\t\\n\\x{B}\\f\\r\\x{20}\\x{A0}\\x{1680}\\x{2000}-\\x{200A}\\x{2028}\\x{2029}\\x{202F}\\x{205F}\\x{3000}\\x{FEFF}';
10 /** The complement of {@link WHITESPACE}, usable inside another class. */
11 const NON_WHITESPACE =
12 '\\x{0}-\\x{8}\\x{E}-\\x{1F}\\x{21}-\\x{9F}\\x{A1}-\\x{167F}\\x{1681}-\\x{1FFF}\\x{200B}-\\x{2027}\\x{202A}-\\x{202E}\\x{2030}-\\x{205E}\\x{2060}-\\x{2FFF}\\x{3001}-\\x{FEFE}\\x{FF00}-\\x{10FFFF}';
13 const ANY_CHARACTER = '\\x{0}-\\x{10FFFF}';
14 /** ECMAScript `.` without the `s` flag excludes every line terminator, not just `\n`. */
15 const DOT = '[^\\n\\r\\x{2028}\\x{2029}]';
16 const SYNTAX_CHARACTERS = new Set('^$\\.*+?()[]{}|/-');
17 const CONTROL_ESCAPES = new Set('fnrtv');
18 const PASSTHROUGH_CLASS_ESCAPES = new Set('dDwW');
19
20 const codePoint = (code: number): string => `\\x{${code.toString(16).toUpperCase()}}`;
21
22 /** Thrown inside the translator for constructs RE2 cannot express. */
23 class Unsupported extends Error {}
24
25 /**
26 * Reads one escape at `pattern[index] === '\\'` that is valid in both a class
27 * and the top level, returning its RE2 spelling and the index after it.
28 */
29 const readEscape = (pattern: string, index: number, inClass: boolean): [string, number] => {
30 const escaped = pattern[index + 1] ?? '';
31
32 if (PASSTHROUGH_CLASS_ESCAPES.has(escaped) || CONTROL_ESCAPES.has(escaped)) {
33 return [`\\${escaped}`, index + 2];
34 }
35 if (escaped === 's') {
36 return [inClass ? WHITESPACE : `[${WHITESPACE}]`, index + 2];
37 }
38 if (escaped === 'S') {
39 return [inClass ? NON_WHITESPACE : `[^${WHITESPACE}]`, index + 2];
40 }
41 if (escaped === 'b' || escaped === 'B') {
42 // Inside a class `\b` is a backspace; `\B` is not allowed there.
43 return [inClass ? codePoint(8) : `\\${escaped}`, index + 2];
44 }
45 if (escaped === '0') {
46 return [codePoint(0), index + 2];
47 }
48 if (escaped === 'c') {
49 return [codePoint(pattern.charCodeAt(index + 2) % 32), index + 3];
50 }
51 if (escaped === 'x') {
52 return [codePoint(parseInt(pattern.slice(index + 2, index + 4), 16)), index + 4];
53 }
54 if (escaped === 'u') {
55 if (pattern[index + 2] === '{') {
56 const end = pattern.indexOf('}', index + 3);
57 return [codePoint(parseInt(pattern.slice(index + 3, end), 16)), end + 1];
58 }
59 const unit = parseInt(pattern.slice(index + 2, index + 6), 16);
60 const low = /^\\u([Dd][C-Fc-f][0-9A-Fa-f]{2})/.exec(pattern.slice(index + 6));
61 if (unit >= 0xd800 && unit <= 0xdbff && low) {
62 // The Unicode grammar reads an escaped surrogate pair as one code point.
63 const combined = (unit - 0xd800) * 0x400 + (parseInt(low[1], 16) - 0xdc00) + 0x10000;
64 return [codePoint(combined), index + 12];
65 }
66 return [codePoint(unit), index + 6];
67 }
68 if (SYNTAX_CHARACTERS.has(escaped)) {
69 return [`\\${escaped}`, index + 2];
70 }
71 // Backreferences have no linear-time implementation, and RE2 names Unicode
72 // properties differently.
73 throw new Unsupported();
74 };
75
76 /** Translates a class starting at `pattern[index] === '['`. */
77 const readClass = (pattern: string, index: number): [string, number] => {
78 let cursor = index + 1;
79 const negated = pattern[cursor] === '^';
80 if (negated) {
81 cursor++;
82 }
83 if (pattern[cursor] === ']') {
84 // `[]` matches nothing and `[^]` matches everything; RE2 reads a leading
85 // `]` as a literal instead.
86 return [negated ? `[${ANY_CHARACTER}]` : `[^${ANY_CHARACTER}]`, cursor + 1];
87 }
88
89 let body = '';
90 while (pattern[cursor] !== ']') {
91 const char = pattern[cursor];
92 if (char === '\\') {
93 const [spelled, next] = readEscape(pattern, cursor, true);
94 body += spelled;
95 cursor = next;
96 } else {
97 // `[` and `^` are literals here but could start a POSIX class or a
98 // negation in RE2.
99 body += char === '[' || char === '^' ? `\\${char}` : char;
100 cursor += char.length;
101 }
102 }
103 return [`[${negated ? '^' : ''}${body}]`, cursor + 1];
104 };
105
106 /**
107 * Translates a pattern written in the ECMAScript Unicode (`u` flag) grammar
108 * into RE2 syntax with the same meaning. The input must already compile with
109 * the `u` flag. Returns `undefined` for constructs that need a backtracking
110 * engine (lookaround, backreferences) or that RE2 spells differently.
111 */
112 export const unicodePatternToRe2 = (pattern: string): string | undefined => {
113 let result = '';
114 let index = 0;
115 try {
116 while (index < pattern.length) {
117 const char = pattern[index];
118 if (char === '\\') {
119 const [spelled, next] = readEscape(pattern, index, false);
120 result += spelled;
121 index = next;
122 } else if (char === '[') {
123 const [spelled, next] = readClass(pattern, index);
124 result += spelled;
125 index = next;
126 } else if (char === '.') {
127 result += DOT;
128 index++;
129 } else if (char === '(' && pattern[index + 1] === '?') {
130 if (pattern[index + 2] === ':') {
131 result += '(?:';
132 index += 3;
133 } else if (pattern[index + 2] === '<' && !'=!'.includes(pattern[index + 3] ?? '')) {
134 // A named group keeps its number; the name is irrelevant to matching.
135 result += '(';
136 index = pattern.indexOf('>', index) + 1;
137 } else {
138 throw new Unsupported();
139 }
140 } else {
141 result += char;
142 index++;
143 }
144 }
145 } catch (error) {
146 if (error instanceof Unsupported) {
147 return undefined;
148 }
149 throw error;
150 }
151 return result;
152 };
153
154 /**
155 * Compiles a Unicode-grammar pattern for RE2JS, whose matching time is linear
156 * in the input for every pattern. Returns `undefined` when RE2 cannot express
157 * the pattern.
158 */
159 export const compileLinearPattern = (unicodePattern: string): RE2JS | undefined => {
160 const re2 = unicodePatternToRe2(unicodePattern);
161 if (re2 === undefined) {
162 return undefined;
163 }
164 try {
165 return RE2JS.compile(re2);
166 } catch {
167 return undefined;
168 }
169 };
170
171 /** A quantifier whose range (maximum minus minimum) exceeds this counts as unbounded. */
172 const LARGE_QUANTIFIER_RANGE = 16;
173 /** Bound on the product of the ranges of all small variable quantifiers. */
174 const MAX_SMALL_QUANTIFIER_PRODUCT = 64;
175 /** Absolute explicit repeat bounds, including repetitions of zero-width assertions. */
176 const MAX_FALLBACK_REPEAT_COUNT = 64;
177 /** Bound on the polynomial degree of the backtracking search in the input length. */
178 const MAX_BACKTRACKING_DEGREE = 2;
179 const BRACE_QUANTIFIER = /^\{(\d+)(,(\d*))?\}/;
180
181 type Group = {
182 lookaround: boolean;
183 quantified: boolean;
184 alternation: boolean;
185 branches: number;
186 };
187
188 /**
189 * Whether a pattern that RE2 cannot run (it needs lookaround or a
190 * backreference) is still safe for the native backtracking engine on short
191 * input. Deliberately conservative, since only such patterns reach it:
192 *
193 * - no backreferences;
194 * - no quantified group that contains a quantifier or an alternation, the
195 * shapes behind exponential backtracking (`(a+)+`, `(a|a)*`);
196 * - no lookaround nested in another lookaround;
197 * - explicit repetition bounds are capped, including fixed assertions;
198 * - the search is at most quadratic: one degree for an unanchored start, plus
199 * the number of unbounded quantifiers at the top level, plus the largest
200 * number inside a single lookaround (lookarounds are atomic, so they add
201 * rather than multiply);
202 * - small variable quantifiers (`?`, `{1,3}`) and alternations multiply the
203 * work by a bounded constant (`(?:a|aa)(?:a|aa)...b` is exponential without
204 * any quantifier).
205 * A leading anchor removes search work only without a top-level alternative.
206 *
207 * Callers still bound the input length, which keeps the quadratic case cheap.
208 */
209 export const isSafeForBacktracking = (pattern: string): boolean => {
210 const hasNamedGroup = /\(\?<(?![=!])/.test(pattern);
211 const newGroup = (lookaround: boolean): Group => ({
212 lookaround,
213 quantified: false,
214 alternation: false,
215 branches: 1,
216 });
217 const stack: Group[] = [newGroup(false)];
218 let topLevelLarge = 0;
219 let lookaroundLarge = 0;
220 let maxLookaroundLarge = 0;
221 let smallProduct = 1;
222 let lastAtomGroup: Group | undefined;
223 let index = 0;
224
225 const insideLookaround = () => stack.some(group => group.lookaround);
226 const multiply = (factor: number): boolean => {
227 smallProduct *= factor;
228 return smallProduct <= MAX_SMALL_QUANTIFIER_PRODUCT;
229 };
230
231 while (index < pattern.length) {
232 const char = pattern[index];
233 const current = stack[stack.length - 1];
234
235 let quantifierLength = 0;
236 let range = 0;
237 if (char === '*' || char === '+') {
238 quantifierLength = 1;
239 range = Infinity;
240 } else if (char === '?') {
241 quantifierLength = 1;
242 range = 1;
243 } else if (char === '{') {
244 const brace = BRACE_QUANTIFIER.exec(pattern.slice(index));
245 if (brace) {
246 quantifierLength = brace[0].length;
247 const minimum = Number(brace[1]);
248 const maximum = brace[2] === undefined ? minimum : Number(brace[3]);
249 if (
250 minimum > MAX_FALLBACK_REPEAT_COUNT ||
251 (brace[3] !== '' && maximum > MAX_FALLBACK_REPEAT_COUNT)
252 ) {
253 return false;
254 }
255 if (brace[2] !== undefined) {
256 range = brace[3] === '' ? Infinity : Number(brace[3]) - Number(brace[1]);
257 }
258 }
259 }
260
261 if (quantifierLength > 0) {
262 if (lastAtomGroup && (lastAtomGroup.quantified || lastAtomGroup.alternation)) {
263 return false;
264 }
265 if (range > LARGE_QUANTIFIER_RANGE) {
266 if (insideLookaround()) {
267 maxLookaroundLarge = Math.max(maxLookaroundLarge, ++lookaroundLarge);
268 } else {
269 topLevelLarge++;
270 }
271 } else if (range > 0 && !multiply(range + 1)) {
272 return false;
273 }
274 current.quantified = true;
275 index += quantifierLength;
276 if (pattern[index] === '?') {
277 index++;
278 }
279 lastAtomGroup = undefined;
280 continue;
281 }
282
283 lastAtomGroup = undefined;
284 if (char === '\\') {
285 const escaped = pattern[index + 1] ?? '';
286 if (/^[1-9]$/.test(escaped) || (escaped === 'k' && hasNamedGroup)) {
287 return false;
288 }
289 index += 2;
290 } else if (char === '[') {
291 index++;
292 while (index < pattern.length && pattern[index] !== ']') {
293 index += pattern[index] === '\\' ? 2 : 1;
294 }
295 index++;
296 } else if (char === '(') {
297 const lookaround =
298 pattern[index + 1] === '?' &&
299 ('=!'.includes(pattern[index + 2] ?? '') ||
300 (pattern[index + 2] === '<' && '=!'.includes(pattern[index + 3] ?? '')));
301 if (lookaround) {
302 if (insideLookaround()) {
303 return false;
304 }
305 lookaroundLarge = 0;
306 }
307 stack.push(newGroup(lookaround));
308 index++;
309 if (pattern[index] === '?') {
310 // Skip the group prefix so its `?` is not read as a quantifier.
311 index += lookaround && pattern[index + 1] === '<' ? 3 : 2;
312 }
313 } else if (char === ')') {
314 const closed = stack.length > 1 ? stack.pop()! : current;
315 if (!multiply(closed.branches)) {
316 return false;
317 }
318 const parent = stack[stack.length - 1];
319 parent.quantified ||= closed.quantified;
320 parent.alternation ||= closed.alternation;
321 lastAtomGroup = closed;
322 index++;
323 } else {
324 if (char === '|') {
325 current.alternation = true;
326 current.branches++;
327 }
328 index++;
329 }
330 }
331 if (!multiply(stack[0].branches)) {
332 return false;
333 }
334
335 const unanchored = pattern.startsWith('^') && stack[0].branches === 1 ? 0 : 1;
336 return unanchored + topLevelLarge + maxLookaroundLarge <= MAX_BACKTRACKING_DEGREE;
337 };
338
339 /**
340 * Longest input the backtracking fallback runs on. Longer input is treated as
341 * matching: skipping a constraint only widens what the schema accepts, which
342 * a hostile schema could do anyway by omitting the pattern.
343 */
344 export const MAX_BACKTRACKING_INPUT_LENGTH = 1000;
345
346 /**
347 * How a schema pattern is evaluated:
348 *
349 * - `linear`: RE2JS runs it, in time linear in the input.
350 * - `backtracking`: the pattern needs lookaround, but passes
351 * {@link isSafeForBacktracking}; the native engine runs it on input up to
352 * {@link MAX_BACKTRACKING_INPUT_LENGTH} characters.
353 * - `unenforced`: neither applies, so the constraint is not checked rather
354 * than exposing validation to catastrophic backtracking.
355 */
356 export type PatternMatcher =
357 | { readonly kind: 'linear'; readonly regex: RE2JS }
358 | { readonly kind: 'backtracking'; readonly regex: RegExp }
359 | { readonly kind: 'unenforced' };
360
361 /**
362 * Builds the matcher for a schema pattern in the legacy (no `u` flag) grammar
363 * the rest of this package accepts. `pattern` must already compile as a
364 * `RegExp`.
365 */
366 export const createPatternMatcher = (pattern: string): PatternMatcher => {
367 const unicodePattern = toUnicodePattern(pattern);
368 const linear = unicodePattern === undefined ? undefined : compileLinearPattern(unicodePattern);
369 if (linear !== undefined) {
370 return { kind: 'linear', regex: linear };
371 }
372 if (isSafeForBacktracking(pattern)) {
373 return { kind: 'backtracking', regex: new RegExp(pattern) };
374 }
375 return { kind: 'unenforced' };
376 };
377
378 /** Whether `input` satisfies the pattern behind `matcher`. */
379 export const patternMatches = (matcher: PatternMatcher, input: string): boolean => {
380 switch (matcher.kind) {
381 case 'linear':
382 return matcher.regex.test(input);
383 case 'backtracking':
384 if (input.length > MAX_BACKTRACKING_INPUT_LENGTH) {
385 return true;
386 }
387 matcher.regex.lastIndex = 0;
388 return matcher.regex.test(input);
389 case 'unenforced':
390 return true;
391 }
392 };