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 665 lines 21.8 KB
Raw
1 import {
2 encodePointer,
3 format,
4 ignoredKeyword,
5 schemaArrayKeyword,
6 schemaMapKeyword,
7 Validator,
8 } from '@cfworker/json-schema';
9 import type { Schema as InterpreterSchema } from '@cfworker/json-schema';
10
11 import type { WholeSchemaGuard } from './backend/types';
12 import type { JsonSchema, JsonSchemaObject } from './types';
13 import { InvalidPatternError } from './utils/compile-pattern';
14 import { createPatternMatcher, patternMatches, type PatternMatcher } from './utils/linear-pattern';
15 import { toUnicodePattern } from './utils/unicode-pattern';
16
17 const REQUIRES_WHOLE_SCHEMA_VALIDATION = new Set([
18 '$ref',
19 'additionalItems',
20 'allOf',
21 'anyOf',
22 'contains',
23 'dependencies',
24 'else',
25 'if',
26 'maxProperties',
27 'minProperties',
28 'not',
29 'oneOf',
30 'propertyNames',
31 'then',
32 'uniqueItems',
33 ]);
34
35 const TYPELESS_TYPE_SCOPED_KEYWORDS = new Set([
36 'properties',
37 'patternProperties',
38 'additionalProperties',
39 'propertyNames',
40 'required',
41 'dependencies',
42 'minProperties',
43 'maxProperties',
44 'items',
45 'additionalItems',
46 'contains',
47 'minItems',
48 'maxItems',
49 'uniqueItems',
50 ]);
51
52 const SCHEMA_MAP_KEYWORDS = new Set([
53 '$defs',
54 'definitions',
55 'dependencies',
56 'patternProperties',
57 'properties',
58 ]);
59
60 const SCHEMA_ARRAY_KEYWORDS = new Set(['allOf', 'anyOf', 'oneOf']);
61
62 const SCHEMA_VALUE_KEYWORDS = new Set([
63 'additionalItems',
64 'additionalProperties',
65 'contains',
66 'else',
67 'if',
68 'items',
69 'not',
70 'propertyNames',
71 'then',
72 ]);
73
74 const isObject = (value: unknown): value is Record<string, unknown> =>
75 typeof value === 'object' && value !== null && !Array.isArray(value);
76
77 type SchemaNode = { value: Record<string, unknown>; path: ReadonlyArray<string | number> };
78
79 /**
80 * Every object the interpreter registers as a schema, found with its own walk
81 * (`dereference`): each key it does not ignore, extension locations included.
82 * A `$ref` resolves only through that registry, whether it is a JSON Pointer,
83 * an `$id` or an `$anchor`, so these are all the schemas the interpreter can
84 * ever validate against.
85 */
86 function* interpreterSchemaNodes(
87 value: unknown,
88 path: ReadonlyArray<string | number> = [],
89 seen: WeakSet<object> = new WeakSet()
90 ): Generator<SchemaNode> {
91 if (!isObject(value) || seen.has(value)) {
92 return;
93 }
94 seen.add(value);
95 yield { value, path };
96
97 for (const [key, child] of Object.entries(value)) {
98 // Indexed like `dereference` does, so inherited names are skipped alike.
99 if ((ignoredKeyword as Record<string, boolean>)[key]) {
100 continue;
101 }
102 if (Array.isArray(child)) {
103 if ((schemaArrayKeyword as Record<string, boolean>)[key]) {
104 for (const [index, nested] of child.entries()) {
105 yield* interpreterSchemaNodes(nested, [...path, key, index], seen);
106 }
107 }
108 } else if ((schemaMapKeyword as Record<string, boolean>)[key]) {
109 if (isObject(child)) {
110 for (const [name, nested] of Object.entries(child)) {
111 yield* interpreterSchemaNodes(nested, [...path, key, name], seen);
112 }
113 }
114 } else {
115 yield* interpreterSchemaNodes(child, [...path, key], seen);
116 }
117 }
118 }
119
120 const hasRequiredDefault = (schema: JsonSchemaObject): boolean => {
121 if (!Array.isArray(schema.required) || !isObject(schema.properties)) {
122 return false;
123 }
124
125 return schema.required.some(name => {
126 const property = schema.properties?.[name];
127 return isObject(property) && property.default !== undefined;
128 });
129 };
130
131 const hasUnparsedRequiredProperty = (schema: JsonSchemaObject): boolean => {
132 if (!Array.isArray(schema.required)) {
133 return false;
134 }
135 const declared = new Set(Object.keys(schema.properties ?? {}));
136 return schema.required.some(name => !declared.has(name));
137 };
138
139 /**
140 * The native parsers preserve useful Zod structure and materialize defaults,
141 * but some JSON Schema assertions cannot be represented by their first-match
142 * dispatch. Only those schemas receive an authoritative Draft 7 guard.
143 */
144 export const requiresWholeSchemaValidation = (
145 schema: JsonSchema,
146 seen: WeakSet<object> = new WeakSet()
147 ): boolean => {
148 if (!isObject(schema) || seen.has(schema)) {
149 return false;
150 }
151 seen.add(schema);
152
153 if (
154 Object.keys(schema).some(key => REQUIRES_WHOLE_SCHEMA_VALIDATION.has(key)) ||
155 (schema.type === undefined &&
156 Object.keys(schema).some(key => TYPELESS_TYPE_SCOPED_KEYWORDS.has(key))) ||
157 hasUnparsedRequiredProperty(schema) ||
158 hasRequiredDefault(schema)
159 ) {
160 return true;
161 }
162
163 for (const [key, child] of Object.entries(schema)) {
164 if (SCHEMA_MAP_KEYWORDS.has(key) && isObject(child)) {
165 if (
166 Object.values(child).some(value => requiresWholeSchemaValidation(value as JsonSchema, seen))
167 ) {
168 return true;
169 }
170 } else if (SCHEMA_ARRAY_KEYWORDS.has(key) && Array.isArray(child)) {
171 if (child.some(value => requiresWholeSchemaValidation(value as JsonSchema, seen))) {
172 return true;
173 }
174 } else if (SCHEMA_VALUE_KEYWORDS.has(key)) {
175 const values = Array.isArray(child) ? child : [child];
176 if (values.some(value => requiresWholeSchemaValidation(value as JsonSchema, seen))) {
177 return true;
178 }
179 }
180 }
181
182 return false;
183 };
184
185 /**
186 * Some schemas are valid for JSON instance types that the native parser does
187 * not materialize. Such a node is parsed as `z.any()` so the Draft 7 guard
188 * that every one of these keywords also activates (see
189 * `requiresWholeSchemaValidation`) stays the acceptance authority without
190 * piping into a narrower Zod schema. The check is deliberately local: a
191 * permissive descendant must not widen its enclosing parser, or sibling
192 * defaults would stop materializing.
193 */
194 export const requiresPermissiveMaterialization = (schema: JsonSchema): boolean =>
195 isObject(schema) &&
196 ('$ref' in schema ||
197 (schema.type === undefined &&
198 (Object.keys(schema).some(key => TYPELESS_TYPE_SCOPED_KEYWORDS.has(key)) ||
199 ['if', 'then', 'else', 'not'].some(key => key in schema))));
200
201 /**
202 * The guard schema for a node nested at `path` inside `root`: the enclosing
203 * document pointed at that node, so local `$ref`s resolve exactly as they do
204 * for the document root. Draft 7 ignores the keywords next to `$ref`, which
205 * is what lets the root's own assertions be reused as the pointer carrier.
206 */
207 export const guardSchemaAt = (
208 node: JsonSchema,
209 refs: { root?: JsonSchema; path: ReadonlyArray<string | number> }
210 ): JsonSchema =>
211 isObject(refs.root) && refs.path.length > 0
212 ? // `encodePointer` is the interpreter's own key encoding, so the pointer
213 // lands on exactly the lookup entry `dereference` registered.
214 { ...refs.root, $ref: `#/${refs.path.map(part => encodePointer(String(part))).join('/')}` }
215 : node;
216
217 /** The interpreter spelling of one `patternProperties` key. */
218 type PatternKeySpelling = (pattern: string) => string;
219 /** The interpreter spelling of every key of one `patternProperties` object. */
220 type PatternKeyRenamer = (patternProperties: object) => ReadonlyMap<string, string>;
221
222 /**
223 * Spells each key of a `patternProperties` object with `spell`. Two keys that
224 * spell the same way (`^a\_b$` and `^a_b$`) stay separate entries: the later
225 * one is wrapped in a non-capturing group, which matches the same names, so
226 * neither value schema is dropped. `renamed` collects every spelling that
227 * differs from its key.
228 */
229 const patternKeyRenamer = (
230 spell: PatternKeySpelling,
231 renamed: Map<string, string> = new Map()
232 ): PatternKeyRenamer => {
233 const cache = new WeakMap<object, ReadonlyMap<string, string>>();
234 return patternProperties => {
235 const cached = cache.get(patternProperties);
236 if (cached) {
237 return cached;
238 }
239
240 const renames = new Map<string, string>();
241 const used = new Set<string>();
242 for (const key of Object.keys(patternProperties)) {
243 let spelling = spell(key);
244 while (used.has(spelling)) {
245 spelling = `(?:${spelling})`;
246 }
247 used.add(spelling);
248 renames.set(key, spelling);
249 if (spelling !== key) {
250 renamed.set(spelling, key);
251 }
252 }
253 cache.set(patternProperties, renames);
254 return renames;
255 };
256 };
257
258 /**
259 * The interpreter matches `patternProperties` keys itself, with a native
260 * backtracking `RegExp`, against object keys that come from the caller. So a
261 * key never reaches it as written. Instead, each validation spells it as the
262 * literal set of instance keys it matches under RE2 (an anchored trie, which
263 * cannot backtrack beyond the key length). Interpreter matching then agrees
264 * with RE2 on every key it can see.
265 *
266 * Returns the RE2 matcher of each key, or `undefined` for a key that does not
267 * compile in the Unicode grammar: the interpreter throws on it when reached,
268 * which fails the guard closed, as it always has. A key that compiles but
269 * needs a backtracking engine is rejected at conversion, as the native object
270 * parser does.
271 */
272 const collectPatternKeyMatchers = (
273 nodes: readonly SchemaNode[]
274 ): Map<string, PatternMatcher | undefined> => {
275 const matchers = new Map<string, PatternMatcher | undefined>();
276 for (const { value, path } of nodes) {
277 if (!isObject(value.patternProperties)) {
278 continue;
279 }
280 for (const key of Object.keys(value.patternProperties)) {
281 if (matchers.has(key)) {
282 continue;
283 }
284 let matcher: PatternMatcher | undefined;
285 try {
286 matcher = createPatternMatcher(key);
287 } catch {
288 matcher = undefined;
289 }
290 if (matcher !== undefined && matcher.kind !== 'linear') {
291 if (unicodeSpellingCompiles(key)) {
292 throw new InvalidPatternError(
293 'patternProperties',
294 key,
295 [...path, 'patternProperties', key],
296 'unsupported',
297 'patternProperties keys must not use lookaround or backreferences'
298 );
299 }
300 matcher = undefined;
301 }
302 matchers.set(key, matcher);
303 }
304 }
305
306 return matchers;
307 };
308
309 /** The Unicode spelling of a key that cannot be matched with RE2. */
310 const fallbackKeySpelling = (pattern: string): string => toUnicodePattern(pattern) ?? pattern;
311
312 const unicodeSpellingCompiles = (pattern: string): boolean => {
313 try {
314 new RegExp(fallbackKeySpelling(pattern), 'u');
315 return true;
316 } catch {
317 return false;
318 }
319 };
320
321 /** Every object key anywhere in `value`. */
322 const collectInstanceKeys = (
323 value: unknown,
324 keys: Set<string> = new Set(),
325 seen: WeakSet<object> = new WeakSet()
326 ): Set<string> => {
327 if (typeof value !== 'object' || value === null || seen.has(value)) {
328 return keys;
329 }
330 seen.add(value);
331 if (Array.isArray(value)) {
332 value.forEach(item => collectInstanceKeys(item, keys, seen));
333 } else {
334 for (const [key, child] of Object.entries(value)) {
335 keys.add(key);
336 collectInstanceKeys(child, keys, seen);
337 }
338 }
339 return keys;
340 };
341
342 const UNICODE_SYNTAX_CHARACTER = /[$()*+./?[\\\]^{|}]/g;
343
344 type KeyTrie = { end: boolean; children: Map<string, KeyTrie> };
345
346 /** Spells a trie node as a Unicode-grammar pattern over its code points. */
347 const spellKeyTrie = (node: KeyTrie): string => {
348 const branches = [...node.children].map(([char, child]) => {
349 let spelling = char.replace(UNICODE_SYNTAX_CHARACTER, '\\$&');
350 let next = child;
351 // Collapse single-path runs so nesting grows only at branch points.
352 while (!next.end && next.children.size === 1) {
353 const [[nextChar, grandchild]] = next.children;
354 spelling += nextChar.replace(UNICODE_SYNTAX_CHARACTER, '\\$&');
355 next = grandchild;
356 }
357 return spelling + spellKeyTrie(next);
358 });
359 if (branches.length === 0) {
360 return '';
361 }
362 if (branches.length === 1 && !node.end) {
363 return branches[0];
364 }
365 return `(?:${branches.join('|')}${node.end ? '|' : ''})`;
366 };
367
368 /**
369 * An anchored Unicode-grammar pattern that matches exactly `keys`. Branches of
370 * a trie start with distinct characters, so matching never backtracks further
371 * than the key being tested. No keys gives `[]`, which matches nothing.
372 */
373 const literalKeysPattern = (keys: readonly string[]): string => {
374 if (keys.length === 0) {
375 return '[]';
376 }
377 const root: KeyTrie = { end: false, children: new Map() };
378 for (const key of keys) {
379 let node = root;
380 for (const char of key) {
381 let child = node.children.get(char);
382 if (!child) {
383 child = { end: false, children: new Map() };
384 node.children.set(char, child);
385 }
386 node = child;
387 }
388 node.end = true;
389 }
390 return `^${spellKeyTrie(root)}$`;
391 };
392
393 const decodePointerSegment = (segment: string): string => {
394 try {
395 return decodeURI(segment).replace(/~1/g, '/').replace(/~0/g, '~');
396 } catch {
397 return segment;
398 }
399 };
400
401 /**
402 * What a JSON Pointer segment addresses: a keyword of a schema, a name in a
403 * keyword's map (`properties`, `$defs`, ...), a `patternProperties` key, an
404 * index into a schema array, or something that holds no schemas.
405 */
406 type PointerPosition = 'keyword' | 'name' | 'patternKey' | 'index' | 'other';
407
408 const positionAfter = (position: PointerPosition, key: string, child: unknown): PointerPosition => {
409 if (position !== 'keyword') {
410 return position === 'other' ? 'other' : 'keyword';
411 }
412 if (key === 'patternProperties') {
413 return 'patternKey';
414 }
415 if (SCHEMA_MAP_KEYWORDS.has(key)) {
416 return 'name';
417 }
418 if (SCHEMA_ARRAY_KEYWORDS.has(key) || (SCHEMA_VALUE_KEYWORDS.has(key) && Array.isArray(child))) {
419 return 'index';
420 }
421 return SCHEMA_VALUE_KEYWORDS.has(key) ? 'keyword' : 'other';
422 };
423
424 /**
425 * A local `$ref` rewritten to address the renamed `patternProperties` keys of
426 * the interpreter copy. `root` is the unrenamed document it points into. Only
427 * a segment in keyword position is a keyword, so a definition that happens to
428 * be named `patternProperties` is not mistaken for one.
429 */
430 const renameRefThroughPatternKeys = (
431 ref: string,
432 root: unknown,
433 renamePatternKeys: PatternKeyRenamer,
434 schemaObjects: WeakSet<object>
435 ): string => {
436 if (!ref.startsWith('#/')) {
437 return ref;
438 }
439
440 let node: unknown = root;
441 let position: PointerPosition = 'keyword';
442 let changed = false;
443 const renamed = ref
444 .slice(2)
445 .split('/')
446 .map(segment => {
447 if (position === 'other' && isObject(node) && schemaObjects.has(node)) {
448 position = 'keyword';
449 }
450 const key = decodePointerSegment(segment);
451 let result = segment;
452 if (position === 'patternKey' && isObject(node)) {
453 const renamedKey = renamePatternKeys(node).get(key);
454 if (renamedKey !== undefined && renamedKey !== key) {
455 result = encodePointer(renamedKey);
456 changed = true;
457 }
458 }
459 const child =
460 isObject(node) || Array.isArray(node) ? (node as Record<string, unknown>)[key] : undefined;
461 position = positionAfter(position, key, child);
462 node = child;
463 return result;
464 });
465
466 return changed ? `#/${renamed.join('/')}` : ref;
467 };
468
469 const PATTERN_FORMAT_PREFIX = 'composio-pattern:';
470
471 /** Pattern formats of one guard, installed on the interpreter only while it validates. */
472 type PatternFormats = Map<string, (value: string) => boolean>;
473
474 /**
475 * Adds `pattern` to `formats` as an interpreter format that tests it as the
476 * native string parser does (legacy grammar, RE2 with a bounded fallback; see
477 * `compilePattern`), and returns the format name. Returns `undefined` for a
478 * pattern that does not compile at all, which the interpreter then reports as
479 * it always has. `matchers` caches compiled patterns across validations.
480 */
481 const patternFormat = (
482 pattern: string,
483 formats: PatternFormats,
484 matchers: Map<string, PatternMatcher>
485 ): string | undefined => {
486 const name = `${PATTERN_FORMAT_PREFIX}${pattern}`;
487 if (!formats.has(name)) {
488 let matcher = matchers.get(pattern);
489 if (matcher === undefined) {
490 try {
491 new RegExp(pattern);
492 } catch {
493 return undefined;
494 }
495 matcher = createPatternMatcher(pattern);
496 matchers.set(pattern, matcher);
497 }
498 const compiled = matcher;
499 formats.set(name, value => patternMatches(compiled, value));
500 }
501 return name;
502 };
503
504 /**
505 * Rewrites the guard's private copy of a schema into what the Draft 7
506 * interpreter understands the way the native parsers do:
507 *
508 * - OpenAPI 3.0 / Draft 4 spell exclusive bounds as a boolean flag next to
509 * `minimum`/`maximum`. The interpreter ignores the flag, so it receives the
510 * numeric spelling the native number parser already honors.
511 * - The interpreter compiles patterns natively with the `u` flag, which
512 * refuses legacy syntax tool schemas use, such as `\_`, and backtracks. A
513 * `pattern` becomes a format that tests it exactly like the native string
514 * parser. A `patternProperties` key cannot leave the interpreter, so it is
515 * respelled by `renamePatternKeys`, and local `$ref`s through a renamed key
516 * follow the rename. `root` is the unmodified document those refs address.
517 * `formats` collects the pattern formats.
518 */
519 const prepareInterpreterSchema = (
520 value: Record<string, unknown>,
521 root: unknown,
522 formats: PatternFormats,
523 patternMatchers: Map<string, PatternMatcher>,
524 renamePatternKeys: PatternKeyRenamer,
525 schemaObjects: WeakSet<object>
526 ): void => {
527 if (value.exclusiveMinimum === true && typeof value.minimum === 'number') {
528 value.exclusiveMinimum = value.minimum;
529 delete value.minimum;
530 } else if (typeof value.exclusiveMinimum === 'boolean') {
531 delete value.exclusiveMinimum;
532 }
533 if (value.exclusiveMaximum === true && typeof value.maximum === 'number') {
534 value.exclusiveMaximum = value.maximum;
535 delete value.maximum;
536 } else if (typeof value.exclusiveMaximum === 'boolean') {
537 delete value.exclusiveMaximum;
538 }
539
540 if (typeof value.$ref === 'string') {
541 value.$ref = renameRefThroughPatternKeys(value.$ref, root, renamePatternKeys, schemaObjects);
542 }
543 const patternFormatName =
544 typeof value.pattern === 'string'
545 ? patternFormat(value.pattern, formats, patternMatchers)
546 : undefined;
547 if (patternFormatName !== undefined) {
548 delete value.pattern;
549 if (value.format === undefined) {
550 value.format = patternFormatName;
551 } else {
552 const allOf = Array.isArray(value.allOf) ? value.allOf : [];
553 value.allOf = [...allOf, { format: patternFormatName }];
554 }
555 }
556 if (isObject(value.patternProperties)) {
557 const renames = renamePatternKeys(value.patternProperties);
558 value.patternProperties = Object.fromEntries(
559 Object.entries(value.patternProperties).map(([pattern, schema]) => [
560 renames.get(pattern) ?? pattern,
561 schema,
562 ])
563 );
564 }
565 };
566
567 type PreparedInterpreter = {
568 validator: Validator;
569 formats: PatternFormats;
570 /** Interpreter spelling of each respelled `patternProperties` key, to its key. */
571 renamed: ReadonlyMap<string, string>;
572 };
573
574 /**
575 * The Draft 7 guard for `jsonSchema`: validates a source value against the
576 * complete schema with the interpreter, with patterns spelled as the native
577 * parsers match them. The backend attaches it to the parsed schema so it runs
578 * before defaults and other transforms.
579 */
580 export const createWholeSchemaGuard = (jsonSchema: JsonSchema): WholeSchemaGuard => {
581 const patternMatchers = new Map<string, PatternMatcher>();
582 const originalNodes = [...interpreterSchemaNodes(jsonSchema)];
583 const schemaObjects = new WeakSet(originalNodes.map(node => node.value));
584 const keyMatchers = collectPatternKeyMatchers(originalNodes);
585
586 const prepare = (spell: PatternKeySpelling): PreparedInterpreter => {
587 const interpreterSchema = structuredClone(jsonSchema);
588 const formats: PatternFormats = new Map();
589 const renamed = new Map<string, string>();
590 const renamePatternKeys = patternKeyRenamer(spell, renamed);
591 // Capture targets before key renaming changes the paths that address them.
592 const nodes = [...interpreterSchemaNodes(interpreterSchema)];
593 for (const { value } of nodes) {
594 prepareInterpreterSchema(
595 value,
596 jsonSchema,
597 formats,
598 patternMatchers,
599 renamePatternKeys,
600 schemaObjects
601 );
602 }
603 return {
604 validator: new Validator(interpreterSchema as InterpreterSchema, '7', false),
605 formats,
606 renamed,
607 };
608 };
609
610 // Without `patternProperties` the interpreter schema never changes. With
611 // them, it is rebuilt for each value, spelling every key as the instance
612 // keys it matches.
613 const shared = keyMatchers.size === 0 ? prepare(fallbackKeySpelling) : undefined;
614 const prepareFor = (value: unknown): PreparedInterpreter => {
615 if (shared) {
616 return shared;
617 }
618 const instanceKeys = [...collectInstanceKeys(value)];
619 const spellings = new Map<string, string>();
620 return prepare(pattern => {
621 const cached = spellings.get(pattern);
622 if (cached !== undefined) {
623 return cached;
624 }
625 const matcher = keyMatchers.get(pattern);
626 const spelling =
627 matcher === undefined
628 ? fallbackKeySpelling(pattern)
629 : literalKeysPattern(instanceKeys.filter(key => patternMatches(matcher, key)));
630 spellings.set(pattern, spelling);
631 return spelling;
632 });
633 };
634
635 return value => {
636 // The interpreter only reads formats from its process-wide table. This
637 // guard's pattern formats live there only for this synchronous call, so
638 // the table does not grow with every distinct pattern ever converted.
639 let result: ReturnType<Validator['validate']>;
640 let prepared: PreparedInterpreter | undefined;
641 try {
642 prepared = prepareFor(value);
643 prepared.formats.forEach((test, name) => {
644 format[name] = test;
645 });
646 result = prepared.validator.validate(value);
647 } catch (cause) {
648 return `JSON Schema validation failed: ${String(cause)}`;
649 } finally {
650 prepared?.formats.forEach((_, name) => {
651 delete format[name];
652 });
653 }
654
655 if (!result.valid) {
656 let error = result.errors[0]?.error ?? 'Input does not satisfy the complete JSON Schema.';
657 // Report the schema's own pattern, not its per-value spelling.
658 prepared.renamed.forEach((key, spelling) => {
659 error = error.split(`"${spelling}"`).join(`"${key}"`);
660 });
661 return error;
662 }
663 return undefined;
664 };
665 };