@devries-cameron20 / composio Mirror · read-only
Fork 0

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

Mirrored from https://github.com/Camo67/composio.git

Synced Nov 21, 04:45 UTC

next
ts 371 lines 12.3 KB
Raw
1 import fc from 'fast-check';
2 import { describe, expect, it, vi } from 'vitest';
3
4 import { InvalidPatternError } from '../src/index';
5 import type { JsonSchema } from '../src/types';
6 import { compilePattern } from '../src/utils/compile-pattern';
7 import {
8 MAX_BACKTRACKING_INPUT_LENGTH,
9 compileLinearPattern,
10 createPatternMatcher,
11 isSafeForBacktracking,
12 } from '../src/utils/linear-pattern';
13 import { toUnicodePattern } from '../src/utils/unicode-pattern';
14 import { builders } from './support/builders';
15
16 /** Patterns whose RE2 translation must agree with the native Unicode engine. */
17 const TRANSLATED_PATTERNS = [
18 '^\\s+$',
19 '^\\S+$',
20 '^[\\s\\S]$',
21 '^[^\\s]+$',
22 '^[^\\S]$',
23 '^.$',
24 '^..$',
25 '^a.b$',
26 '\\u00e9',
27 '^\\ud83d\\ude00$',
28 '^\\u{1F600}$',
29 '^[]$',
30 '^[^]$',
31 '^[\\b]$',
32 '^\\cJ$',
33 '^\\0$',
34 '^(?<word>a)\\d$',
35 '\\bfoo\\b',
36 '\\Bo',
37 '^[\\[^]+$',
38 '^a{2,3}$',
39 '^\\x41$',
40 '^[\\w-]+$',
41 '^\\D\\W$',
42 '^$',
43 '^(?:ab|a)b?$',
44 '^[a-z\\-\\]]$',
45 '^\\/\\.\\*$',
46 ] as const;
47
48 const UNITS = [
49 ' ',
50 '\t',
51 '\n',
52 '\r',
53 '\v',
54 '\u00a0',
55 '\u1680',
56 '\u2028',
57 '\u2029',
58 '\ufeff',
59 '\u0085',
60 'a',
61 'b',
62 'A',
63 '0',
64 '_',
65 '\b',
66 '\u0000',
67 '\u{1F600}',
68 '\ud83d',
69 '\u00e9',
70 '-',
71 '[',
72 ']',
73 '^',
74 'f',
75 'o',
76 '/',
77 '.',
78 '*',
79 ];
80
81 describe('unicodePatternToRe2', () => {
82 it.each(TRANSLATED_PATTERNS)('matches %s exactly like the native Unicode engine', pattern => {
83 const unicodePattern = toUnicodePattern(pattern) ?? pattern;
84 const linear = compileLinearPattern(unicodePattern);
85 expect(linear).toBeDefined();
86 const native = new RegExp(unicodePattern, 'u');
87
88 fc.assert(
89 fc.property(fc.string({ unit: fc.constantFrom(...UNITS), maxLength: 4 }), input => {
90 expect(linear!.test(input)).toBe(native.test(input));
91 }),
92 { numRuns: 300 }
93 );
94 });
95
96 it.each(['^(?=a)a$', '(?<=a)b', '(?<!a)b', '^(a)\\1$', '^(?<n>a)\\k<n>$'])(
97 'leaves %s to the backtracking engine',
98 pattern => {
99 expect(compileLinearPattern(pattern)).toBeUndefined();
100 }
101 );
102 });
103
104 describe('isSafeForBacktracking', () => {
105 it.each([
106 '^(?=.*[a-y])a',
107 '^(?=.*[a-z])(?=.*[A-Z])(?=.*\\d)[A-Za-z\\d]{8,}$',
108 '^(?=a){2}ab$',
109 '^(?!admin$)[a-z]+$',
110 '^(?:jpg|png|gif)(?=\\.)',
111 ])('accepts %s', pattern => {
112 expect(isSafeForBacktracking(pattern)).toBe(true);
113 });
114
115 it.each([
116 ['nested quantifiers', '^(?=(a+)+$)'],
117 ['a quantified alternation', '^(?=x)(a|aa)*$'],
118 ['a backreference', '^(a)\\1$'],
119 ['a named backreference', '^(?<n>a)\\k<n>$'],
120 ['polynomial quantifiers', '(?=x).*.*y'],
121 ['two unbounded quantifiers in one lookaround', '(?=.*a.*b)x'],
122 ['a nested lookaround', '^(?=(?=a)a)'],
123 ['an unquantified alternation chain', `(?<=)${'(?:a|aa)'.repeat(28)}b`],
124 ['many optional atoms', `^(?=x)${'a?'.repeat(30)}${'a'.repeat(30)}$`],
125 ['huge fixed assertion repeats', '^(?=a){1000000000}a$'],
126 ['huge fixed consuming repeats', '^(?=a)a{1000000000}$'],
127 ['huge finite upper bounds', '^(?=a)a{1,1000000000}$'],
128 ['huge unbounded minimums', '^(?=a)a{1000000000,}$'],
129 ['nested fixed assertion repeats', '^((?=a){64}){64}a$'],
130 ['an unanchored alternative', '^(?=a)b|b+b+c'],
131 ['an unanchored alternative with bounded choices', `^z|(?=a)${'(?:a|aa)'.repeat(5)}a*a*b$`],
132 ])('rejects %s', (_, pattern) => {
133 expect(isSafeForBacktracking(pattern)).toBe(false);
134 });
135 });
136
137 const finishesQuickly = (run: () => void): void => {
138 const start = performance.now();
139 run();
140 expect(performance.now() - start).toBeLessThan(1000);
141 };
142
143 const ATTACK = `${'a'.repeat(40)}!`;
144
145 describe('pattern matcher selection', () => {
146 it('leaves a lookahead pattern that could backtrack catastrophically unenforced', () => {
147 // Assembled at runtime so static analysis does not flag the test input
148 // itself as an inefficient regular expression.
149 const pattern = ['^(?=(a+)+', '$)a'].join('');
150 const regex = compilePattern('pattern', pattern, { path: [] });
151 expect(regex.matcher.kind).toBe('unenforced');
152 finishesQuickly(() => expect(regex.test(ATTACK)).toBe(true));
153 // The JSON Schema shown to the model still carries the pattern.
154 expect(regex.source).toBe(pattern);
155 });
156
157 it('picks RE2 for every pattern it can express', () => {
158 expect(createPatternMatcher('^(\\d+\\.)*\\d+$').kind).toBe('linear');
159 expect(createPatternMatcher('^[a-z\\_]+$').kind).toBe('linear');
160 expect(createPatternMatcher('^(?=.*[a-y])a').kind).toBe('backtracking');
161 });
162 });
163
164 describe.each(builders)('catastrophic backtracking (SEC-1178) ($name)', builder => {
165 it.each(['^(?=a){1000000000}a$', `^z|(?=a)${'(?:a|aa)'.repeat(5)}a*a*b$`])(
166 'leaves unsafe fallback pattern %s unenforced',
167 pattern => {
168 expect(createPatternMatcher(pattern).kind).toBe('unenforced');
169 const parsed = builder.convert({ type: 'string', pattern });
170 expect(parsed.safeParse('a'.repeat(MAX_BACKTRACKING_INPUT_LENGTH)).success).toBe(true);
171 }
172 );
173
174 it.each(['x', 'components', 'escaped', '$id', '$anchor'])(
175 'protects regexes referenced through %s',
176 location => {
177 const pattern = '^(a+)+$';
178 let nativeExecutions = 0;
179 const originalExec = RegExp.prototype.exec;
180 const nativeExec = vi.spyOn(RegExp.prototype, 'exec').mockImplementation(function (
181 this: RegExp,
182 input: string
183 ) {
184 if (this.source === pattern) {
185 nativeExecutions++;
186 throw new Error('schema regex reached native matching');
187 }
188 return originalExec.call(this, input);
189 });
190 try {
191 for (const keyword of ['pattern', 'patternProperties']) {
192 const target =
193 keyword === 'pattern'
194 ? { type: 'string', pattern }
195 : {
196 type: 'object',
197 patternProperties: { [pattern]: { type: 'integer' } },
198 additionalProperties: false,
199 };
200 const { extension, ref } = {
201 x: { extension: { x: target }, ref: '#/x' },
202 components: {
203 extension: { components: { schemas: { target } } },
204 ref: '#/components/schemas/target',
205 },
206 escaped: { extension: { 'schema/~target': target }, ref: '#/schema~1~0target' },
207 // The interpreter also resolves identifiers it registers anywhere.
208 $id: {
209 extension: { x: { $id: 'https://example.com/target', ...target } },
210 ref: 'https://example.com/target',
211 },
212 $anchor: { extension: { x: { $anchor: 'target', ...target } }, ref: '#target' },
213 }[location]!;
214 const parsed = builder.convert({
215 type: 'object',
216 properties: { value: { $ref: ref } },
217 ...extension,
218 } as JsonSchema);
219 expect(
220 parsed.safeParse({ value: keyword === 'pattern' ? 'aaa' : { aaa: 1 } }).success
221 ).toBe(true);
222 expect(
223 parsed.safeParse({ value: keyword === 'pattern' ? 'a!' : { 'a!': 1 } }).success
224 ).toBe(false);
225 if (keyword === 'patternProperties') {
226 expect(parsed.safeParse({ value: { aaa: 'bad' } }).success).toBe(false);
227 }
228 }
229 expect(nativeExecutions).toBe(0);
230 } finally {
231 nativeExec.mockRestore();
232 }
233 }
234 );
235
236 it.each([
237 ['#/x', {}],
238 ['https://example.com/target', { $id: 'https://example.com/target' }],
239 ['#target', { $anchor: 'target' }],
240 ])(
241 'rejects unsupported key patterns in extension reference targets (%s) during conversion',
242 (ref, identifier) => {
243 expect(() =>
244 builder.convert({
245 type: 'object',
246 properties: { value: { $ref: ref } },
247 x: {
248 ...identifier,
249 type: 'object',
250 patternProperties: { '^(?=a)': { type: 'integer' } },
251 },
252 } as JsonSchema)
253 ).toThrow(InvalidPatternError);
254 }
255 );
256
257 it('keeps references through renamed keys in extension schemas valid', () => {
258 const parsed = builder.convert({
259 type: 'object',
260 properties: {
261 keys: { $ref: '#/x' },
262 value: { $ref: '#/x/patternProperties/^k' },
263 },
264 x: { type: 'object', patternProperties: { '^k': { type: 'integer' } } },
265 } as JsonSchema);
266 expect(parsed.safeParse({ keys: { k1: 1 }, value: 2 }).success).toBe(true);
267 expect(parsed.safeParse({ keys: { k1: 1 }, value: 'bad' }).success).toBe(false);
268 });
269
270 it('follows reference cycles without rewriting instance data as schemas', () => {
271 const parsed = builder.convert({
272 type: 'object',
273 properties: { value: { $ref: '#/x' } },
274 x: {
275 type: 'object',
276 properties: { next: { $ref: '#/x' } },
277 default: { patternProperties: { '^(?=a)': {} } },
278 },
279 } as JsonSchema);
280 expect(parsed.safeParse({ value: { next: {} } }).success).toBe(true);
281 });
282
283 it('runs a nested-quantifier pattern in linear time', () => {
284 const parsed = builder.convert({ type: 'string', pattern: '^(a+)+$' });
285 finishesQuickly(() => expect(parsed.safeParse(ATTACK).success).toBe(false));
286 expect(parsed.safeParse('aaa').success).toBe(true);
287 });
288
289 it('runs a backtracking patternProperties key in linear time', () => {
290 const parsed = builder.convert({
291 type: 'object',
292 patternProperties: { '^(a|a)*$': { type: 'integer' } },
293 additionalProperties: false,
294 });
295 finishesQuickly(() => expect(parsed.safeParse({ [ATTACK]: 1 }).success).toBe(false));
296 expect(parsed.safeParse({ aaa: 1 }).success).toBe(true);
297 expect(parsed.safeParse({ aaa: 'x' }).success).toBe(false);
298 });
299
300 it('runs patterns that only the whole-schema guard sees in linear time', () => {
301 const schema: JsonSchema = {
302 type: 'object',
303 properties: { handle: { $ref: '#/$defs/handle' }, tags: { $ref: '#/$defs/tags' } },
304 $defs: {
305 handle: { type: 'string', pattern: '^(a+)+$' },
306 tags: {
307 type: 'object',
308 patternProperties: { '^(a|a)*$': { type: 'integer' } },
309 additionalProperties: false,
310 },
311 },
312 };
313 const parsed = builder.convert(schema);
314
315 finishesQuickly(() => {
316 expect(parsed.safeParse({ handle: ATTACK }).success).toBe(false);
317 expect(parsed.safeParse({ tags: { [ATTACK]: 1 } }).success).toBe(false);
318 });
319 expect(parsed.safeParse({ handle: 'aa', tags: { aa: 1 } }).success).toBe(true);
320 expect(parsed.safeParse({ tags: { aa: 'x' } }).success).toBe(false);
321 });
322
323 it('runs a backtracking propertyNames pattern in linear time', () => {
324 const parsed = builder.convert({
325 type: 'object',
326 propertyNames: { pattern: '^(a+)+$' },
327 });
328 finishesQuickly(() => expect(parsed.safeParse({ [ATTACK]: 1 }).success).toBe(false));
329 expect(parsed.safeParse({ aa: 1 }).success).toBe(true);
330 });
331
332 it('reports the schema pattern, not its per-value spelling, in guard errors', () => {
333 const parsed = builder.convert({
334 type: 'object',
335 properties: { tags: { $ref: '#/$defs/tags' } },
336 $defs: { tags: { type: 'object', patternProperties: { '^t_': { type: 'integer' } } } },
337 });
338 const result = parsed.safeParse({ tags: { t_1: 'x' } });
339 expect(result.success).toBe(false);
340 expect(JSON.stringify(result.success ? [] : result.error.issues)).not.toContain('t_1$');
341 });
342
343 it('keeps enforcing a lookahead pattern that is safe to backtrack', () => {
344 const parsed = builder.convert({
345 type: 'string',
346 pattern: '^(?=.*[a-z])(?=.*\\d)[a-z\\d]{8,}$',
347 });
348 expect(parsed.safeParse('abcd1234').success).toBe(true);
349 expect(parsed.safeParse('abcdefgh').success).toBe(false);
350 // Past the input bound the fallback is skipped rather than risked.
351 expect(parsed.safeParse('a'.repeat(MAX_BACKTRACKING_INPUT_LENGTH + 1)).success).toBe(true);
352 });
353
354 it('rejects a patternProperties key that needs a backtracking engine', () => {
355 for (const schema of [
356 { type: 'object', patternProperties: { '^(?!x)': { type: 'string' } } },
357 {
358 type: 'object',
359 properties: { v: { $ref: '#/$defs/v' } },
360 $defs: { v: { type: 'object', patternProperties: { '^(?!x)': { type: 'string' } } } },
361 },
362 ] as JsonSchema[]) {
363 expect(() => builder.convert(schema)).toThrow(InvalidPatternError);
364 }
365 try {
366 compilePattern('patternProperties', '^(?!x)', { path: [] });
367 } catch (error) {
368 expect((error as InvalidPatternError).reason).toBe('unsupported');
369 }
370 });
371 });