schemaexec

package
v0.13.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 18, 2026 License: MIT Imports: 22 Imported by: 0

README

schemaexec — JSON Schema Symbolic Execution for jq

Production-ready symbolic executor for jq over OpenAPI/JSON Schema. Infer the output schema from an input schema and a jq program. KLEE-style execution with allocation-site abstraction. Used in production as part of Speakeasy's Transformation Extensions.

Install

go get github.com/speakeasy-api/jq

Quick start (symbolic)

import (
  "context"
  "github.com/speakeasy-api/jq"
  "github.com/speakeasy-api/jq/schemaexec"
)

input := schemaexec.BuildObject(map[string]*oas3.Schema{
  "items": schemaexec.ArrayType(schemaexec.ObjectType()),
}, []string{"items"})
q, _ := jq.Parse(".items | map({id, total: (.price * .qty)})")
out, _ := schemaexec.RunSchema(context.Background(), q, input)
// out.Schema is the inferred output schema

Quick examples

  • Map: .items | map({id, total: (.price * .qty)})array<{id: string, total: number}>
  • Select with narrowing: .items | map(select(.qty > 0) | {id})array<{id: string}>
  • Conditionals to enum: if .score >= 90 then "gold" else "silver"enum["gold","silver"]

Symbolic capabilities

  • Property access and navigation: .foo, .[], .[0]
  • Object build/merge: {a: .x}, {a} + {b: 1}
  • Array ops: map, select, any, all, reduce, foreach
  • Conditionals and error handling: if/then/else, try/catch, alternative //
  • Arithmetic and comparisons with type propagation
  • Variables and closures: as $x | ...
  • Schema inference: required tracking, anyOf unions, enum synthesis
  • OpenAPI aware: designed for x-speakeasy-transform-from-api workflows

Why this exists

Use jq to describe JSON transformations while preserving type information. schemaexec symbolically evaluates jq to infer precise output schemas, keeping downstream codegen and tooling type-safe.

Architecture (brief)

  • KLEE-style multi-state execution with path joining
  • Allocation-site abstraction for arrays/objects; lattice-based union
  • Termination guards and memoization for fast, safe execution

Testing

Run: go test ./schemaexec/...

Thanks

  • Cristian Cadar / KLEE authors. Thanks for the research paving the golden path towards symbolic executors and teaching it to your undergrad students!
  • itchyny. Thanks for the base project!

Documentation

Overview

Package schemaexec provides symbolic execution of jq queries over JSON schemas.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AddSchemasForTest added in v0.13.0

func AddSchemasForTest(lhs, rhs *oas3.Schema, opts SchemaExecOptions) *oas3.Schema

AddSchemasForTest exposes "+" semantics for tests without requiring a VM env.

func ArrayType

func ArrayType(items *oas3.Schema) *oas3.Schema

ArrayType creates a basic array schema with the given items schema.

func BoolType

func BoolType() *oas3.Schema

BoolType creates a basic boolean schema.

func Bottom

func Bottom() *oas3.Schema

Bottom returns a schema that matches nothing (the "never" type). By convention, we use nil to represent Bottom/Never.

func BuildArray

func BuildArray(items *oas3.Schema, elements []*oas3.Schema) *oas3.Schema

BuildArray creates an array schema from element schemas.

func BuildObject

func BuildObject(props map[string]*oas3.Schema, required []string) *oas3.Schema

BuildObject creates an object schema from property map. Simplified version for Phase 1.

func ConstBool

func ConstBool(b bool) *oas3.Schema

ConstBool creates a schema for true or false.

func ConstInteger

func ConstInteger(n int64) *oas3.Schema

ConstInteger creates a schema for a specific integer.

func ConstNull

func ConstNull() *oas3.Schema

ConstNull creates a null schema.

func ConstNumber

func ConstNumber(n float64) *oas3.Schema

ConstNumber creates a schema for a specific number.

func ConstString

func ConstString(s string) *oas3.Schema

ConstString creates a schema for a specific string literal.

func FingerprintSchema added in v0.13.0

func FingerprintSchema(s *oas3.Schema) string

FingerprintSchema is a convenience function using the default fingerprinter

func GetProperty

func GetProperty(obj *oas3.Schema, key string, opts SchemaExecOptions) *oas3.Schema

GetProperty extracts the schema for a property from an object schema. Simplified version for Phase 1.

func HasProperty

func HasProperty(obj *oas3.Schema, key string, opts SchemaExecOptions) *oas3.Schema

HasProperty refines an object schema to require a property exists. Used for guards like: select(has("foo"))

func IntegerType

func IntegerType() *oas3.Schema

IntegerType creates a basic integer schema (unconstrained).

func Intersect

func Intersect(a, b *oas3.Schema, opts SchemaExecOptions) *oas3.Schema

Intersect creates a schema that matches all input schemas (allOf). This is used for narrowing and constraint combination.

func MergeObjects

func MergeObjects(a, b *oas3.Schema, opts SchemaExecOptions) *oas3.Schema

MergeObjects combines two object schemas (for the + operator on objects).

func MightBeArray

func MightBeArray(s *oas3.Schema) bool

MightBeArray checks if schema could be an array.

func MightBeNumber

func MightBeNumber(s *oas3.Schema) bool

MightBeNumber checks if schema could be a number.

func MightBeObject

func MightBeObject(s *oas3.Schema) bool

MightBeObject checks if schema could be an object.

func MightBeString

func MightBeString(s *oas3.Schema) bool

MightBeString checks if schema could be a string.

func NullType

func NullType() *oas3.Schema

NullType creates a null schema.

func NumberType

func NumberType() *oas3.Schema

NumberType creates a basic number schema (unconstrained).

func ObjectType

func ObjectType() *oas3.Schema

ObjectType creates an object schema with no declared members.

func OpenObjectType added in v0.13.0

func OpenObjectType(values *oas3.Schema) *oas3.Schema

OpenObjectType creates an object schema that admits undeclared members.

func RequireType

func RequireType(s *oas3.Schema, typ oas3.SchemaType, opts SchemaExecOptions) *oas3.Schema

RequireType narrows a schema to a specific type. Used for type guards like: select(type == "array")

func StringType

func StringType() *oas3.Schema

StringType creates a basic string schema (unconstrained).

func Top

func Top() *oas3.Schema

Top returns a schema that matches any value (union of all types).

func Union

func Union(schemas []*oas3.Schema, opts SchemaExecOptions) *oas3.Schema

Union creates a schema that matches any of the input schemas (anyOf). Implements proper flattening, deduplication, and widening when limits exceeded.

Types

type AValue

type AValue struct {
	Kind    ValueKind
	Schema  *oas3.Schema
	Closure *Closure
}

AValue is the abstract value stored on the symbolic VM stack. Phase 1a: only VSchema is used by the existing code. VClosure will be used in Phase 1b+.

func NewClosureValue

func NewClosureValue(pc, scopeIdx int) AValue

func NewSchemaValue

func NewSchemaValue(s *oas3.Schema) AValue

NewSchemaValue constructs an AValue containing a Schema.

func (AValue) AsClosure

func (v AValue) AsClosure() (*Closure, bool)

func (AValue) AsSchema

func (v AValue) AsSchema() (*oas3.Schema, bool)

type AllocOrigin added in v0.13.0

type AllocOrigin struct {
	PC       int    // Program counter where allocation occurred
	Context  string // Semantic context (e.g., "reduce_accumulator", "map_accumulator")
	CallSite int    // Return address of the enclosing call frame (-1 at top level)
}

AllocOrigin tracks where an allocID was created in the AST/execution

type Analysis added in v0.13.0

type Analysis struct {
	// Output is the inferred output schema (usable as the projected response
	// shape). Nil when the query provably produces no output (Bottom).
	Output *oas3.Schema

	// Verdict classifies the result; see the Verdict constants.
	Verdict Verdict

	// Causes holds human-readable explanations with schema locations for
	// VerdictUnverifiable and VerdictProvenBroken, e.g.
	// "property access on non-object type at $.anyOf[0]".
	Causes []string

	// Semantics records the schema interpretation mode the analysis ran
	// under. Verdicts are only meaningful relative to it: under the default
	// SchemaSemanticsSpeakeasy, "valid input" means a value as modeled by
	// Speakeasy's generators (closed objects, implied types), NOT an
	// arbitrary payload the wire could carry. Under SchemaSemanticsRaw a
	// missing property is never provably broken without an explicit
	// additionalProperties: false.
	Semantics SchemaSemantics
}

Analysis is the result of Analyze: the inferred output schema plus a classification of how trustworthy that inference is.

func Analyze added in v0.13.0

func Analyze(ctx context.Context, q *gojq.Query, input *oas3.Schema, opts ...SchemaExecOptions) (*Analysis, error)

Analyze symbolically executes a jq query against an input schema and classifies the result.

Contract for consumers (e.g. generators linting authored jq projections against response schemas):

  • VerdictProvenBroken is safe to fail a build on: the query provably produces null (or nothing) for every valid input.
  • VerdictUnverifiable is NOT a failure — the library could not decide (open schemas, oneOf, unsupported operations legitimately widen to unknown). Consumers should warn at most.
  • VerdictProven means the returned Output schema is a sound, fully concrete over-approximation of all possible outputs.

Analyze always runs in lenient mode (StrictMode is ignored): strict mode aborts on the first widening, whereas classification needs the completed output schema. The verdict is computed by deep-walking the output — including array items, object properties, and union branches — so a Top buried inside a container makes the result Unverifiable, not Proven.

jq missing-key semantics are respected: optional property access yields null UNIONED with the real types, which stays Proven. Only an output that is null for every input (or has no output at all) is ProvenBroken.

Verdicts are relative to opts.Semantics (echoed on Analysis.Semantics). Under the default SchemaSemanticsSpeakeasy, "valid input" means a value as modeled by Speakeasy's generators — objects are closed, so access to an undeclared property is provably null (typo detection). Under SchemaSemanticsRaw, objects without additionalProperties are open and such access is merely Unverifiable.

type ArrayCardinality added in v0.13.0

type ArrayCardinality struct {
	MinItems *int // Lower bound: 0 = maybe-empty, 1+ = must-be-non-empty
	MaxItems *int // Upper bound: nil = unbounded
}

ArrayCardinality tracks bounds on array size for lattice-based merging

func (*ArrayCardinality) Join added in v0.13.0

Join performs lattice join (LUB) on two cardinality bounds This is the mathematically sound merge operation for the cardinality lattice

type Closure

type Closure struct {
	PC         int
	ScopeIndex int
}

Closure abstracts a function value captured by pushpc. PC is the entry address, ScopeIndex is the captured lexical scope index.

type DSU added in v0.13.0

type DSU struct {
	// contains filtered or unexported fields
}

DSU implements Disjoint Set Union (Union-Find) for allocID equivalence classes

func NewDSU added in v0.13.0

func NewDSU() *DSU

NewDSU creates a new Disjoint Set Union structure

func (*DSU) Find added in v0.13.0

func (d *DSU) Find(allocID string) string

Find returns the canonical allocID for an equivalence class (with path compression)

func (*DSU) Union added in v0.13.0

func (d *DSU) Union(allocID1, allocID2 string)

Union merges two equivalence classes

type Fingerprinter added in v0.13.0

type Fingerprinter struct {
	// contains filtered or unexported fields
}

Fingerprinter provides schema canonicalization and hashing with caching

func NewFingerprinter added in v0.13.0

func NewFingerprinter() *Fingerprinter

NewFingerprinter creates a new fingerprinter

func (*Fingerprinter) FingerprintSchema added in v0.13.0

func (fp *Fingerprinter) FingerprintSchema(s *oas3.Schema) string

FingerprintSchema returns a deterministic hex fingerprint for a schema Uses persistent caching for performance

func (*Fingerprinter) FingerprintSchemaWithExclusions added in v0.13.0

func (fp *Fingerprinter) FingerprintSchemaWithExclusions(s *oas3.Schema, excl map[*oas3.Schema]struct{}) string

FingerprintSchemaWithExclusions computes fingerprint but skips persistent cache for schemas in the exclusion set (used for mutable schemas)

func (*Fingerprinter) Reset added in v0.13.0

func (fp *Fingerprinter) Reset()

Reset clears the persistent cache

type LogLevel

type LogLevel int

LogLevel represents the severity level for logs.

const (
	LevelError LogLevel = iota
	LevelWarn
	LevelInfo
	LevelDebug
)

func ParseLogLevel

func ParseLogLevel(s string) LogLevel

ParseLogLevel parses a string into a LogLevel.

func (LogLevel) String

func (l LogLevel) String() string

type Logger

type Logger interface {
	// Debugf, Infof, Warnf, Errorf log formatted messages at respective levels.
	Debugf(format string, args ...any)
	Infof(format string, args ...any)
	Warnf(format string, args ...any)
	Errorf(format string, args ...any)

	// With returns a child logger augmented with the provided fields.
	With(fields map[string]any) Logger
}

Logger is the interface used by the executor for logging.

func NewLogger

func NewLogger(level LogLevel, w io.Writer) Logger

NewLogger creates a default logger with the given level. If w is nil, os.Stderr is used.

type MergeMode added in v0.13.0

type MergeMode int

MergeMode determines how schemas are merged

const (
	// MergeConjunctive represents allOf semantics (intersection)
	// - Properties: union of keys, recursively merge overlapping
	// - Required: union (field required in ANY subschema)
	// - Types: intersection (must be compatible)
	MergeConjunctive MergeMode = iota

	// MergeDisjunctive represents anyOf semantics (union/LUB)
	// - Properties: union of keys, union overlapping property schemas
	// - Required: intersection (field required in ALL subschemas)
	// - Types: union (more permissive)
	MergeDisjunctive
)

type PathAllElements added in v0.13.0

type PathAllElements struct{}

PathAllElements represents every array index selected by .[] in path mode.

type PathSegment

type PathSegment struct {
	Key        interface{} // string, int, PathWildcard, or PathAllElements
	IsSymbolic bool        // True for unknown-index and all-elements segments
}

PathSegment represents one segment of a path expression

type PathWildcard

type PathWildcard struct{}

PathWildcard represents an unknown single array index or slice path.

type SValue

type SValue struct {
	Schema *oas3.Schema
	// contains filtered or unexported fields
}

SValue wraps a schema for the schema VM stack. This is the value type that flows through the schema virtual machine.

type SchemaExecOptions

type SchemaExecOptions struct {
	// Semantics selects the schema interpretation mode (see SchemaSemantics).
	// The zero value is SchemaSemanticsSpeakeasy.
	Semantics SchemaSemantics

	// Limits to prevent combinatorial explosion
	AnyOfLimit int // Max branches in anyOf before widening (default: 10)
	EnumLimit  int // Max enum values before widening to plain type (default: 50)
	MaxDepth   int // Max recursion depth (default: 100)

	// Behavior flags
	StrictMode     bool // If true, fail on unsupported ops; if false, widen to Top (default: false)
	EnableWarnings bool // If true, collect precision-loss warnings (default: true)
	EnableMemo     bool // If true, enable memoization for performance (default: true)

	// Widening level controls how aggressively we simplify schemas
	// 0 = none (keep all precision)
	// 1 = conservative (keep types, drop facets when limits exceeded)
	// 2 = aggressive (collapse to Top when limits exceeded)
	WideningLevel int // default: 1

	// Logging configuration
	LogLevel             string // Log level: "", "error", "warn", "info", "debug". Default "": no output — the library is silent on stdout/stderr unless a level is set.
	LogMaxEnumValues     int    // Max enum values to show in logs (default: 5)
	LogMaxProps          int    // Max object properties to show in logs (default: 5)
	LogStackPreviewDepth int    // Max stack depth to preview in logs (default: 3)
	LogSchemaDeltas      bool   // If true, include schema deltas in debug logs (default: true)
	// contains filtered or unexported fields
}

SchemaExecOptions configures symbolic execution behavior. Callers should start from DefaultOptions when changing individual fields. Public entry points fill zero-valued numeric limits from DefaultOptions, but boolean fields whose defaults are true (EnableWarnings, EnableMemo, and LogSchemaDeltas) remain false in a zero-value struct.

func DefaultOptions

func DefaultOptions() SchemaExecOptions

DefaultOptions returns the default configuration for schema execution.

type SchemaExecResult

type SchemaExecResult struct {
	Schema   *oas3.Schema // The resulting schema after transformation
	Warnings []string     // Warnings about precision loss or unsupported operations
}

SchemaExecResult contains the output schema and diagnostic information.

func ExecSchema

func ExecSchema(ctx context.Context, code *gojq.Code, input *oas3.Schema, opts SchemaExecOptions) (*SchemaExecResult, error)

ExecSchema executes compiled jq bytecode symbolically on an input schema. This is the core execution function - Phase 2 implementation.

func RunSchema

func RunSchema(ctx context.Context, query *gojq.Query, input *oas3.Schema, opts ...SchemaExecOptions) (*SchemaExecResult, error)

RunSchema executes a jq query symbolically on an input JSON Schema. It parses and compiles the query, then performs symbolic execution to compute the output schema.

Example:

query, _ := gojq.Parse(".foo.bar")
inputSchema := &oas3.Schema{...}
result, err := schemaexec.RunSchema(context.Background(), query, inputSchema)
if err != nil {
    log.Fatal(err)
}
fmt.Printf("Output schema: %+v\n", result.Schema)

func (*SchemaExecResult) String

func (r *SchemaExecResult) String() string

String returns a string representation of the result for debugging.

type SchemaLogOptions

type SchemaLogOptions struct {
	LogMaxEnumValues     int // default 5
	LogMaxProps          int // default 5
	LogMaxAnyOfBranches  int // default 5
	LogStackPreviewDepth int // default 3 (not used here, but kept for parity)
}

SchemaLogOptions control verbosity for schema summaries/deltas.

type SchemaSemantics added in v0.13.0

type SchemaSemantics int

SchemaSemantics selects how the executor interprets schemas that do not fully specify their shape.

const (
	// SchemaSemanticsSpeakeasy (the default) targets Speakeasy-processed
	// OpenAPI documents and mirrors the structural inference Speakeasy's
	// SDK/CLI generators apply:
	//   - untyped schemas get an implied type from structure (enum→string,
	//     const→its scalar type, properties/additionalProperties→object,
	//     items→array);
	//   - an object property that is not declared and has no
	//     additionalProperties is treated as ABSENT (closed world): access
	//     yields null. "Valid input" means a value as modeled by the
	//     generator, not an arbitrary API payload.
	SchemaSemanticsSpeakeasy SchemaSemantics = iota

	// SchemaSemanticsRaw keeps raw JSON Schema semantics at navigation:
	//   - untyped schemas are NOT implied to a single type when dispatching
	//     property access/iteration; they conservatively widen to Top;
	//   - an object property that is not declared and has no
	//     additionalProperties is treated as OPEN (additionalProperties
	//     defaults to true in JSON Schema): access yields unknown ∪ null,
	//     so nothing is ever "provably missing" without an explicit
	//     additionalProperties: false.
	// Builtins conservatively widen when an operand has only an implied type,
	// because raw JSON Schema still permits values of every other JSON type.
	SchemaSemanticsRaw
)

type ValueKind

type ValueKind uint8

ValueKind classifies entries on the abstract stack.

const (
	VSchema ValueKind = iota
	VClosure
)

type Verdict added in v0.13.0

type Verdict int

Verdict classifies the outcome of symbolically executing a jq query against an input schema. The zero value is VerdictUnverifiable. The library is best-effort: it cannot prove everything, but when it CAN prove a query is broken, consumers may hard-error.

const (
	// VerdictUnverifiable: the output contains Top (unknown) somewhere — the
	// library could not decide. This is NOT an error; consumers should warn
	// at most.
	VerdictUnverifiable Verdict = iota

	// VerdictProven: a concrete output schema was inferred; it contains no
	// Top (unknown) anywhere and is not provably empty. Safe to use as the
	// projected output shape.
	VerdictProven

	// VerdictProvenBroken: the output is provably null or empty for EVERY
	// valid input — e.g. a typo'd leaf yielding const null, or a query whose
	// execution paths are all dead (Bottom). Safe to fail a build on.
	VerdictProvenBroken
)

func (Verdict) String added in v0.13.0

func (v Verdict) String() string

String returns a human-readable name for the verdict.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL