pool.odin (18546B)
1 package jschema 2 3 import "core:encoding/json" 4 import "core:strings" 5 6 // The schema document is stored as a flat pool of nodes. All cross references 7 // are u32 indices into the pool's side arrays rather than pointers, so the 8 // entire representation lives in a handful of contiguous allocations. 9 10 Node_Index :: distinct u32 11 12 NIL_NODE :: Node_Index(0xFFFF_FFFF) 13 14 Simple_Type :: enum u8 { 15 Null, 16 Boolean, 17 Object, 18 Array, 19 Number, 20 String, 21 Integer, 22 } 23 24 Type_Set :: bit_set[Simple_Type;u8] 25 26 // Index range into one of the pool side arrays. 27 Range :: struct { 28 first: u32, 29 count: u32, 30 } 31 32 Enum_Kind :: enum u8 { 33 None, 34 Strings, // every value is a string 35 Mixed, // at least one non-string value; falls back to the base type 36 } 37 38 Bool3 :: enum u8 { 39 Unset, 40 False, 41 True, 42 } 43 44 Node :: struct { 45 types: Type_Set, 46 enum_kind: Enum_Kind, 47 additional_bool: Bool3, 48 ref: Node_Index, // resolved $ref target 49 items: Node_Index, 50 additional: Node_Index, // additionalProperties / sole patternProperties schema 51 props: Range, // into Pool.props 52 required: Range, // into Pool.names 53 enum_values: Range, // into Pool.strings (string values only) 54 all_of: Range, // into Pool.children 55 any_of: Range, // into Pool.children 56 one_of: Range, // into Pool.children 57 } 58 59 Prop :: struct { 60 name: string, 61 node: Node_Index, 62 } 63 64 // A named declaration candidate: a $defs/definitions entry or a referenced 65 // file's root schema. 66 Def :: struct { 67 name: string, 68 node: Node_Index, 69 } 70 71 Pool :: struct { 72 nodes: [dynamic]Node, 73 props: [dynamic]Prop, 74 names: [dynamic]string, 75 children: [dynamic]Node_Index, 76 strings: [dynamic]string, 77 defs: [dynamic]Def, 78 root: Node_Index, 79 } 80 81 @(private) 82 Pending_Ref :: struct { 83 node: Node_Index, // node carrying the $ref 84 ref: string, // the $ref string as written 85 file: string, // pointer-map key prefix of the file the ref appears in 86 dir: string, // directory for resolving relative file refs 87 } 88 89 @(private) 90 Builder :: struct { 91 pool: ^Pool, 92 openapi: bool, // enables if/then/else lowering and or-reference idioms 93 // "<file key>#<json pointer>" -> node, for $ref resolution. 94 pointers: map[string]Node_Index, 95 // canonical file path -> root node, so each file is parsed once. 96 files: map[string]Node_Index, 97 pending: [dynamic]Pending_Ref, 98 path: string, // display path of the file currently being parsed 99 file_key: string, // pointer-map key prefix of the current file 100 dir: string, // directory of the current file 101 } 102 103 @(private) 104 new_node :: proc(b: ^Builder, ptr: string) -> Node_Index { 105 idx := Node_Index(len(b.pool.nodes)) 106 append(&b.pool.nodes, Node{ref = NIL_NODE, items = NIL_NODE, additional = NIL_NODE}) 107 b.pointers[strings.concatenate({b.file_key, "#", ptr})] = idx 108 return idx 109 } 110 111 // RFC 6901 token encoding, so built pointer paths match the escaped form 112 // used inside $ref strings. 113 @(private) 114 pointer_append :: proc(base: string, key: string) -> string { 115 escaped, _ := strings.replace_all(key, "~", "~0") 116 escaped, _ = strings.replace_all(escaped, "/", "~1") 117 return strings.concatenate({base, "/", escaped}) 118 } 119 120 @(private) 121 parse_error :: proc(b: ^Builder, p: ^json.Parser, message: string) -> Error { 122 return Parse_Error{path = b.path, pos = p.curr_token.pos, message = message} 123 } 124 125 // Skips one JSON value without building anything. 126 @(private) 127 skip_value :: proc(p: ^json.Parser) -> json.Error { 128 depth := 0 129 for { 130 tok := p.curr_token 131 #partial switch tok.kind { 132 case .Open_Brace, .Open_Bracket: 133 depth += 1 134 case .Close_Brace, .Close_Bracket: 135 depth -= 1 136 case .EOF, .Invalid: 137 return .Unexpected_Token 138 } 139 json.advance_token(p) 140 if depth <= 0 { 141 return nil 142 } 143 } 144 } 145 146 @(private) 147 parse_string_value :: proc(b: ^Builder, p: ^json.Parser) -> (s: string, err: Error) { 148 tok := p.curr_token 149 if tok.kind != .String { 150 err = parse_error(b, p, "expected a string value") 151 return 152 } 153 value, uerr := json.unquote_string(tok, p.spec) 154 if uerr != nil { 155 err = parse_error(b, p, "invalid string literal") 156 return 157 } 158 json.advance_token(p) 159 return value, nil 160 } 161 162 @(private) 163 type_from_name :: proc(name: string) -> (Simple_Type, bool) { 164 switch name { 165 case "null": 166 return .Null, true 167 case "boolean": 168 return .Boolean, true 169 case "object": 170 return .Object, true 171 case "array": 172 return .Array, true 173 case "number": 174 return .Number, true 175 case "string": 176 return .String, true 177 case "integer": 178 return .Integer, true 179 } 180 return .Null, false 181 } 182 183 // Parses one schema (object or boolean form) into the pool. 184 @(private) 185 parse_schema :: proc(b: ^Builder, p: ^json.Parser, ptr: string) -> (idx: Node_Index, err: Error) { 186 idx = new_node(b, ptr) 187 188 #partial switch p.curr_token.kind { 189 case .True, .False: 190 // Boolean schemas constrain nothing we can express as a type. 191 json.advance_token(p) 192 return idx, nil 193 case .Open_Brace: 194 // handled below 195 case: 196 return idx, parse_error(b, p, "expected a schema (object or boolean)") 197 } 198 199 json.advance_token(p) 200 then_node: Node_Index = NIL_NODE 201 else_node: Node_Index = NIL_NODE 202 for p.curr_token.kind != .Close_Brace { 203 key, kerr := json.parse_object_key(p, context.allocator) 204 if kerr != nil { 205 return idx, parse_error(b, p, "expected an object key") 206 } 207 if jerr := json.parse_colon(p); jerr != nil { 208 return idx, parse_error(b, p, "expected ':' after object key") 209 } 210 211 switch key { 212 case "type": 213 parse_type_keyword(b, p, idx) or_return 214 case "properties": 215 parse_properties(b, p, idx, ptr) or_return 216 case "required": 217 parse_required(b, p, idx) or_return 218 case "items": 219 // Draft-07 tuple form (array of schemas) degrades to untyped items. 220 if p.curr_token.kind == .Open_Bracket { 221 parse_schema_list(b, p, pointer_append(ptr, "items")) or_return 222 } else { 223 items := parse_schema(b, p, pointer_append(ptr, "items")) or_return 224 b.pool.nodes[idx].items = items 225 } 226 case "additionalProperties": 227 #partial switch p.curr_token.kind { 228 case .True: 229 b.pool.nodes[idx].additional_bool = .True 230 json.advance_token(p) 231 case .False: 232 b.pool.nodes[idx].additional_bool = .False 233 json.advance_token(p) 234 case: 235 additional := parse_schema( 236 b, 237 p, 238 pointer_append(ptr, "additionalProperties"), 239 ) or_return 240 b.pool.nodes[idx].additional = additional 241 } 242 case "patternProperties": 243 parse_pattern_properties(b, p, idx, ptr) or_return 244 case "enum": 245 parse_enum(b, p, idx) or_return 246 case "const": 247 parse_const(b, p, idx) or_return 248 case "$ref": 249 ref := parse_string_value(b, p) or_return 250 append(&b.pending, Pending_Ref{node = idx, ref = ref, file = b.file_key, dir = b.dir}) 251 case "if": 252 // The condition cannot be evaluated at codegen time; when 253 // openapi mode is on, the then/else branches are lowered to 254 // an implicit union below. In raw JSON Schema mode if/then/else 255 // is a validation keyword with no static type effect. 256 if jerr := skip_value(p); jerr != nil { 257 return idx, parse_error(b, p, "malformed JSON value") 258 } 259 case "then": 260 if b.openapi { 261 then_node = parse_schema(b, p, pointer_append(ptr, "then")) or_return 262 } else if jerr := skip_value(p); jerr != nil { 263 return idx, parse_error(b, p, "malformed JSON value") 264 } 265 case "else": 266 if b.openapi { 267 else_node = parse_schema(b, p, pointer_append(ptr, "else")) or_return 268 } else if jerr := skip_value(p); jerr != nil { 269 return idx, parse_error(b, p, "malformed JSON value") 270 } 271 case "$defs", "definitions": 272 parse_defs(b, p, pointer_append(ptr, key)) or_return 273 case "allOf": 274 b.pool.nodes[idx].all_of = parse_schema_list( 275 b, 276 p, 277 pointer_append(ptr, "allOf"), 278 ) or_return 279 case "anyOf": 280 b.pool.nodes[idx].any_of = parse_schema_list( 281 b, 282 p, 283 pointer_append(ptr, "anyOf"), 284 ) or_return 285 case "oneOf": 286 b.pool.nodes[idx].one_of = parse_schema_list( 287 b, 288 p, 289 pointer_append(ptr, "oneOf"), 290 ) or_return 291 case: 292 if jerr := skip_value(p); jerr != nil { 293 return idx, parse_error(b, p, "malformed JSON value") 294 } 295 } 296 297 if json.parse_comma(p) { 298 break 299 } 300 } 301 if jerr := json.expect_token(p, .Close_Brace); jerr != nil { 302 return idx, parse_error(b, p, "expected '}' to close schema object") 303 } 304 // Lower if/then/else into an implicit anyOf of the then and else 305 // branches (ignoring the if condition, which is a runtime guard). 306 // Only active in openapi mode; in raw mode then_node/else_node are NIL. 307 if b.openapi && (then_node != NIL_NODE || else_node != NIL_NODE) { 308 parts := make([dynamic]Node_Index, context.temp_allocator) 309 existing := b.pool.nodes[idx].any_of 310 if existing.count > 0 { 311 append(&parts, ..b.pool.children[existing.first:][:existing.count]) 312 } 313 if then_node != NIL_NODE { 314 append(&parts, then_node) 315 } 316 if else_node != NIL_NODE { 317 append(&parts, else_node) 318 } 319 if len(parts) > 0 { 320 b.pool.nodes[idx].any_of = Range{u32(len(b.pool.children)), u32(len(parts))} 321 append(&b.pool.children, ..parts[:]) 322 } 323 } 324 return idx, nil 325 } 326 327 @(private) 328 parse_type_keyword :: proc(b: ^Builder, p: ^json.Parser, idx: Node_Index) -> Error { 329 add :: proc(b: ^Builder, p: ^json.Parser, idx: Node_Index) -> Error { 330 name, err := parse_string_value(b, p) 331 if err != nil { 332 return err 333 } 334 t, ok := type_from_name(name) 335 if !ok { 336 return parse_error(b, p, "unknown value in \"type\"") 337 } 338 b.pool.nodes[idx].types += {t} 339 return nil 340 } 341 342 if p.curr_token.kind != .Open_Bracket { 343 return add(b, p, idx) 344 } 345 json.advance_token(p) 346 for p.curr_token.kind != .Close_Bracket { 347 add(b, p, idx) or_return 348 if json.parse_comma(p) { 349 break 350 } 351 } 352 if jerr := json.expect_token(p, .Close_Bracket); jerr != nil { 353 return parse_error(b, p, "expected ']' to close \"type\" array") 354 } 355 return nil 356 } 357 358 @(private) 359 parse_properties :: proc(b: ^Builder, p: ^json.Parser, idx: Node_Index, ptr: string) -> Error { 360 if jerr := json.expect_token(p, .Open_Brace); jerr != nil { 361 return parse_error(b, p, "expected an object for \"properties\"") 362 } 363 base := pointer_append(ptr, "properties") 364 // Children are parsed first (appending nodes and their own props freely); 365 // this node's prop records are appended afterwards so they stay contiguous. 366 local := make([dynamic]Prop, context.temp_allocator) 367 for p.curr_token.kind != .Close_Brace { 368 name, kerr := json.parse_object_key(p, context.allocator) 369 if kerr != nil { 370 return parse_error(b, p, "expected a property name") 371 } 372 if jerr := json.parse_colon(p); jerr != nil { 373 return parse_error(b, p, "expected ':' after property name") 374 } 375 child, err := parse_schema(b, p, pointer_append(base, name)) 376 if err != nil { 377 return err 378 } 379 append(&local, Prop{name = name, node = child}) 380 if json.parse_comma(p) { 381 break 382 } 383 } 384 if jerr := json.expect_token(p, .Close_Brace); jerr != nil { 385 return parse_error(b, p, "expected '}' to close \"properties\"") 386 } 387 b.pool.nodes[idx].props = Range{u32(len(b.pool.props)), u32(len(local))} 388 append(&b.pool.props, ..local[:]) 389 return nil 390 } 391 392 @(private) 393 parse_required :: proc(b: ^Builder, p: ^json.Parser, idx: Node_Index) -> Error { 394 if jerr := json.expect_token(p, .Open_Bracket); jerr != nil { 395 return parse_error(b, p, "expected an array for \"required\"") 396 } 397 first := u32(len(b.pool.names)) 398 for p.curr_token.kind != .Close_Bracket { 399 name, err := parse_string_value(b, p) 400 if err != nil { 401 return err 402 } 403 append(&b.pool.names, name) 404 if json.parse_comma(p) { 405 break 406 } 407 } 408 if jerr := json.expect_token(p, .Close_Bracket); jerr != nil { 409 return parse_error(b, p, "expected ']' to close \"required\"") 410 } 411 b.pool.nodes[idx].required = Range{first, u32(len(b.pool.names)) - first} 412 return nil 413 } 414 415 @(private) 416 parse_enum :: proc(b: ^Builder, p: ^json.Parser, idx: Node_Index) -> Error { 417 if jerr := json.expect_token(p, .Open_Bracket); jerr != nil { 418 return parse_error(b, p, "expected an array for \"enum\"") 419 } 420 kind := Enum_Kind.Strings 421 local := make([dynamic]string, context.temp_allocator) 422 for p.curr_token.kind != .Close_Bracket { 423 if p.curr_token.kind == .String { 424 value, err := parse_string_value(b, p) 425 if err != nil { 426 return err 427 } 428 append(&local, value) 429 } else { 430 kind = .Mixed 431 if jerr := skip_value(p); jerr != nil { 432 return parse_error(b, p, "malformed value in \"enum\"") 433 } 434 } 435 if json.parse_comma(p) { 436 break 437 } 438 } 439 if jerr := json.expect_token(p, .Close_Bracket); jerr != nil { 440 return parse_error(b, p, "expected ']' to close \"enum\"") 441 } 442 node := &b.pool.nodes[idx] 443 node.enum_kind = kind 444 if kind == .Strings { 445 node.enum_values = Range{u32(len(b.pool.strings)), u32(len(local))} 446 append(&b.pool.strings, ..local[:]) 447 } 448 return nil 449 } 450 451 @(private) 452 parse_const :: proc(b: ^Builder, p: ^json.Parser, idx: Node_Index) -> Error { 453 if p.curr_token.kind == .String { 454 value := parse_string_value(b, p) or_return 455 node := &b.pool.nodes[idx] 456 if node.enum_kind == .None { 457 node.enum_kind = .Strings 458 node.enum_values = Range{u32(len(b.pool.strings)), 1} 459 append(&b.pool.strings, value) 460 } 461 return nil 462 } 463 if jerr := skip_value(p); jerr != nil { 464 return parse_error(b, p, "malformed value in \"const\"") 465 } 466 return nil 467 } 468 469 // A single-pattern patternProperties object is treated like 470 // additionalProperties; anything richer degrades to an untyped map. 471 @(private) 472 parse_pattern_properties :: proc( 473 b: ^Builder, 474 p: ^json.Parser, 475 idx: Node_Index, 476 ptr: string, 477 ) -> Error { 478 if jerr := json.expect_token(p, .Open_Brace); jerr != nil { 479 return parse_error(b, p, "expected an object for \"patternProperties\"") 480 } 481 base := pointer_append(ptr, "patternProperties") 482 count := 0 483 sole := NIL_NODE 484 for p.curr_token.kind != .Close_Brace { 485 pattern, kerr := json.parse_object_key(p, context.allocator) 486 if kerr != nil { 487 return parse_error(b, p, "expected a pattern key") 488 } 489 if jerr := json.parse_colon(p); jerr != nil { 490 return parse_error(b, p, "expected ':' after pattern") 491 } 492 child, err := parse_schema(b, p, pointer_append(base, pattern)) 493 if err != nil { 494 return err 495 } 496 count += 1 497 sole = child if count == 1 else NIL_NODE 498 if json.parse_comma(p) { 499 break 500 } 501 } 502 if jerr := json.expect_token(p, .Close_Brace); jerr != nil { 503 return parse_error(b, p, "expected '}' to close \"patternProperties\"") 504 } 505 if sole != NIL_NODE && b.pool.nodes[idx].additional == NIL_NODE { 506 b.pool.nodes[idx].additional = sole 507 } 508 return nil 509 } 510 511 @(private) 512 parse_defs :: proc(b: ^Builder, p: ^json.Parser, ptr: string) -> Error { 513 if jerr := json.expect_token(p, .Open_Brace); jerr != nil { 514 return parse_error(b, p, "expected an object for \"$defs\"") 515 } 516 for p.curr_token.kind != .Close_Brace { 517 name, kerr := json.parse_object_key(p, context.allocator) 518 if kerr != nil { 519 return parse_error(b, p, "expected a definition name") 520 } 521 if jerr := json.parse_colon(p); jerr != nil { 522 return parse_error(b, p, "expected ':' after definition name") 523 } 524 child, err := parse_schema(b, p, pointer_append(ptr, name)) 525 if err != nil { 526 return err 527 } 528 append(&b.pool.defs, Def{name = name, node = child}) 529 if json.parse_comma(p) { 530 break 531 } 532 } 533 if jerr := json.expect_token(p, .Close_Brace); jerr != nil { 534 return parse_error(b, p, "expected '}' to close \"$defs\"") 535 } 536 return nil 537 } 538 539 @(private) 540 parse_schema_list :: proc(b: ^Builder, p: ^json.Parser, ptr: string) -> (r: Range, err: Error) { 541 if jerr := json.expect_token(p, .Open_Bracket); jerr != nil { 542 err = parse_error(b, p, "expected an array of schemas") 543 return 544 } 545 local := make([dynamic]Node_Index, context.temp_allocator) 546 for p.curr_token.kind != .Close_Bracket { 547 child := parse_schema(b, p, pointer_append(ptr, itoa(len(local)))) or_return 548 append(&local, child) 549 if json.parse_comma(p) { 550 break 551 } 552 } 553 if jerr := json.expect_token(p, .Close_Bracket); jerr != nil { 554 err = parse_error(b, p, "expected ']' to close schema array") 555 return 556 } 557 r = Range{u32(len(b.pool.children)), u32(len(local))} 558 append(&b.pool.children, ..local[:]) 559 return r, nil 560 } 561 562 @(private) 563 itoa :: proc(n: int) -> string { 564 buf: [12]u8 565 i := len(buf) 566 n := n 567 if n == 0 { 568 return "0" 569 } 570 for n > 0 { 571 i -= 1 572 buf[i] = '0' + u8(n % 10) 573 n /= 10 574 } 575 return strings.clone(string(buf[i:])) 576 } 577 578 // Shallow-scans a schema document for signals that it uses OpenAPI 579 // idioms (if/then/else "X-or-reference" patterns). Two shapes trigger 580 // detection: 581 // 582 // 1. An OpenAPI *instance* document: a root-level "openapi" key (the 583 // version marker, e.g. {"openapi": "3.2.0", ...}). 584 // 2. The OpenAPI *meta-schema*: a root-level "properties" object that 585 // itself contains an "openapi" key (describing field 1). 586 // 587 detect_openapi :: proc(data: []u8) -> bool { 588 p := json.make_parser(data, .JSON, true, context.temp_allocator) 589 if p.curr_token.kind != .Open_Brace { 590 return false 591 } 592 json.advance_token(&p) 593 for p.curr_token.kind != .Close_Brace { 594 key, kerr := json.parse_object_key(&p, context.temp_allocator) 595 if kerr != nil { 596 return false 597 } 598 if jerr := json.parse_colon(&p); jerr != nil { 599 return false 600 } 601 // Case 1: root-level "openapi" key (instance document). 602 if key == "openapi" { 603 return true 604 } 605 // Case 2: "properties" containing an "openapi" sub-key (meta-schema). 606 if key == "properties" && p.curr_token.kind == .Open_Brace { 607 json.advance_token(&p) 608 for p.curr_token.kind != .Close_Brace { 609 prop, perr := json.parse_object_key(&p, context.temp_allocator) 610 if perr != nil { 611 return false 612 } 613 if jerr := json.parse_colon(&p); jerr != nil { 614 return false 615 } 616 if prop == "openapi" { 617 return true 618 } 619 if jerr := skip_value(&p); jerr != nil { 620 return false 621 } 622 if json.parse_comma(&p) { 623 break 624 } 625 } 626 // "properties" with no "openapi" sub-key; keep scanning the root. 627 if json.parse_comma(&p) { 628 break 629 } 630 continue 631 } 632 if jerr := skip_value(&p); jerr != nil { 633 return false 634 } 635 if json.parse_comma(&p) { 636 break 637 } 638 } 639 return false 640 } 641 642 // Parses one schema document into the pool, returning its root node. 643 @(private) 644 parse_document :: proc( 645 b: ^Builder, 646 data: []u8, 647 path: string, 648 file_key: string, 649 dir: string, 650 ) -> ( 651 root: Node_Index, 652 err: Error, 653 ) { 654 prev_path, prev_key, prev_dir := b.path, b.file_key, b.dir 655 b.path, b.file_key, b.dir = path, file_key, dir 656 defer b.path, b.file_key, b.dir = prev_path, prev_key, prev_dir 657 658 p := json.make_parser(data, .JSON, true, context.allocator) 659 root = parse_schema(b, &p, "") or_return 660 if p.curr_token.kind != .EOF { 661 return root, parse_error(b, &p, "trailing content after schema") 662 } 663 return root, nil 664 } 665