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
| 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 | }); |