export function fromJsonSchemaMultiDocument(document: JsonSchema.MultiDocument<"draft-2020-12">, options?: {
  readonly onEnter?: ((js: JsonSchema.JsonSchema) => JsonSchema.JsonSchema) | undefined
}): MultiDocument {
  let definitionIdentifier: string | undefined
  const references: Record<string, Representation> = {}

  type ResolvedReference = Exclude<Representation, { _tag: "Reference" }>
  const resolvedReferences = new Map<string, ResolvedReference | null>()

  function resolveReference($ref: string): ResolvedReference {
    const definition = document.definitions[$ref]
    if (definition === undefined) {
      throw new Error(`Reference ${$ref} not found`)
    }

    const resolved = resolvedReferences.get($ref)
    if (resolved === null) {
      throw new Error(`Circular reference detected: ${$ref}`)
    }
    if (resolved !== undefined) return resolved

    resolvedReferences.set($ref, null)
    const value = recur(definition)
    const out = value._tag === "Reference" ? resolveReference(value.$ref) : value
    resolvedReferences.set($ref, out)
    return out
  }

  for (const [identifier, definition] of Object.entries(document.definitions)) {
    definitionIdentifier = identifier
    references[identifier] = unknownToJson(recur(definition))
  }

  definitionIdentifier = undefined
  const representations = Arr.map(document.schemas, (schema) => unknownToJson(recur(schema)))
  return {
    representations,
    references
  }

  function recur(u: unknown): Representation {
    if (u === false) return never
    if (!Predicate.isObject(u)) return unknown

    let js: JsonSchema.JsonSchema = options?.onEnter?.(u) ?? u
    if (Array.isArray(js.type)) {
      if (js.type.every(isType)) {
        const { type, ...rest } = js
        js = {
          anyOf: type.map((type) => ({ type })),
          ...rest
        }
      } else {
        js = {}
      }
    }

    let out = on(js)

    const annotations = collectAnnotations(js)
    if (annotations !== undefined) {
      out = combine(out, { _tag: "Unknown", annotations })
    }

    if (Array.isArray(js.allOf)) {
      out = js.allOf.reduce((acc, curr) => combine(acc, recur(curr)), out)
    }
    if (Array.isArray(js.anyOf)) {
      out = combine({ _tag: "Union", types: js.anyOf.map((type) => recur(type)), mode: "anyOf" }, out)
    }
    if (Array.isArray(js.oneOf)) {
      out = combine({ _tag: "Union", types: js.oneOf.map((type) => recur(type)), mode: "oneOf" }, out)
    }

    return out
  }

  function on(js: JsonSchema.JsonSchema): Representation {
    if (typeof js.$ref === "string") {
      const $ref = js.$ref.slice(2).split("/").at(-1)
      if ($ref !== undefined) {
        const reference: Reference = { _tag: "Reference", $ref: unescapeToken($ref) }
        if (definitionIdentifier === $ref) {
          return { _tag: "Suspend", thunk: reference, checks: [] }
        } else {
          return reference
        }
      }
    } else if ("const" in js) {
      if (isLiteralValue(js.const)) {
        return { _tag: "Literal", literal: js.const }
      } else if (js.const === null) {
        return null_
      }
    } else if (Array.isArray(js.enum)) {
      const types: Array<Representation> = []
      for (const e of js.enum) {
        if (isLiteralValue(e)) {
          types.push({ _tag: "Literal", literal: e })
        } else if (e === null) {
          types.push(null_)
        } else {
          types.push(recur(e))
        }
      }
      if (types.length === 1) {
        return types[0]
      } else {
        return { _tag: "Union", types, mode: "anyOf" }
      }
    }

    const type = isType(js.type) ? js.type : getType(js)
    if (type !== undefined) {
      switch (type) {
        case "null":
          return null_
        case "string": {
          const checks = collectStringChecks(js)
          if (checks.length > 0) {
            return { ...string, checks }
          }
          return string
        }
        case "number":
          return {
            _tag: "Number",
            checks: [{ _tag: "Filter", meta: { _tag: "isFinite" } }, ...collectNumberChecks(js)]
          }
        case "integer":
          return {
            _tag: "Number",
            checks: [{ _tag: "Filter", meta: { _tag: "isInt" } }, ...collectNumberChecks(js)]
          }
        case "boolean":
          return boolean
        case "array": {
          const minItems = typeof js.minItems === "number" ? js.minItems : 0

          const elements: Array<Element> = (Array.isArray(js.prefixItems) ? js.prefixItems : []).map((e, i) => ({
            isOptional: i + 1 > minItems,
            type: recur(e)
          }))

          const rest: Array<Representation> = js.items !== undefined ?
            [recur(js.items)]
            : js.prefixItems !== undefined && typeof js.maxItems === "number"
            ? []
            : [unknown]

          return { _tag: "Arrays", elements, rest, checks: collectArraysChecks(js) }
        }
        case "object": {
          return {
            _tag: "Objects",
            propertySignatures: collectProperties(js),
            indexSignatures: collectIndexSignatures(js),
            checks: collectObjectsChecks(js)
          }
        }
      }
    }

    return { _tag: "Unknown" }
  }

  function collectObjectsChecks(js: JsonSchema.JsonSchema): Array<Check<ObjectsMeta>> {
    const checks: Array<Check<ObjectsMeta>> = []
    if (typeof js.minProperties === "number") {
      checks.push({ _tag: "Filter", meta: { _tag: "isMinProperties", minProperties: js.minProperties } })
    }
    if (typeof js.maxProperties === "number") {
      checks.push({ _tag: "Filter", meta: { _tag: "isMaxProperties", maxProperties: js.maxProperties } })
    }
    if (js.propertyNames !== undefined) {
      const propertyNames = recur(js.propertyNames)
      checks.push({ _tag: "Filter", meta: { _tag: "isPropertyNames", propertyNames } })
    }
    return checks
  }

  function combine(a: Representation, b: Representation): Representation {
    switch (a._tag) {
      default:
        return never
      case "Reference":
        return combine(resolveReference(a.$ref), b)
      case "Never":
        return a
      case "Unknown": {
        const resolved = b._tag === "Reference" ? resolveReference(b.$ref) : b
        return { ...resolved, ...combineAnnotations(a.annotations, resolved.annotations) }
      }
      case "Null":
      case "String":
      case "Number":
      case "Boolean":
      case "Literal":
      case "Arrays":
      case "Objects":
      case "Union":
        break
    }

    if (b._tag === "Reference") {
      return combine(a, resolveReference(b.$ref))
    }
    if (b._tag === "Unknown") {
      return { ...a, ...combineAnnotations(a.annotations, b.annotations) }
    }
    if (a._tag === "Union") {
      const types = a.types.map((s) => combine(s, b)).filter((s) => s !== never)
      if (types.length === 0) return never
      return {
        _tag: "Union",
        types,
        mode: a.mode,
        ...makeAnnotations(a.annotations)
      }
    }
    if (b._tag === "Union") {
      return combine(b, a)
    }

    switch (a._tag) {
      case "Null":
        return b._tag === "Null" ? { ...a, ...combineAnnotations(a.annotations, b.annotations) } : never
      case "String": {
        if (b._tag === "Literal") {
          return satisfiesLiteral(a, b) ? { ...b, ...combineAnnotations(a.annotations, b.annotations) } : never
        }
        if (b._tag !== "String") return never
        const checks = combineChecks(a.checks, b.checks, b.annotations)
        return {
          _tag: "String",
          checks: checks ?? a.checks,
          ...combineAnnotations(a.annotations, checks ? undefined : b.annotations)
        }
      }
      case "Number": {
        if (b._tag === "Literal") {
          return satisfiesLiteral(a, b) ? { ...b, ...combineAnnotations(a.annotations, b.annotations) } : never
        }
        if (b._tag !== "Number") return never
        const checks = combineNumberChecks(a.checks, b.checks, b.annotations)
        return {
          _tag: "Number",
          checks: checks ?? a.checks,
          ...combineAnnotations(a.annotations, checks ? undefined : b.annotations)
        }
      }
      case "Boolean":
        if (b._tag === "Boolean") {
          return { _tag: "Boolean", ...combineAnnotations(a.annotations, b.annotations) }
        }
        return b._tag === "Literal" && typeof b.literal === "boolean"
          ? { ...b, ...combineAnnotations(a.annotations, b.annotations) }
          : never
      case "Literal":
        switch (b._tag) {
          case "Literal":
            return a.literal === b.literal
              ? { ...a, ...combineAnnotations(a.annotations, b.annotations) }
              : never
          case "String":
          case "Number":
            return satisfiesLiteral(b, a) ? { ...a, ...combineAnnotations(a.annotations, b.annotations) } : never
          case "Boolean":
            return typeof a.literal === "boolean"
              ? { ...a, ...combineAnnotations(a.annotations, b.annotations) }
              : never
          default:
            return never
        }
      case "Arrays": {
        if (b._tag !== "Arrays") return never
        const arrays = combineArrays(a, b)
        if (arrays === undefined) return never
        const checks = combineArraysChecks(a.checks, b.checks, b.annotations)
        return {
          _tag: "Arrays",
          elements: arrays.elements,
          rest: arrays.rest,
          checks: checks ?? a.checks,
          ...combineAnnotations(a.annotations, checks ? undefined : b.annotations)
        }
      }
      case "Objects": {
        if (b._tag !== "Objects") return never
        const checks = combineChecks(a.checks, b.checks, b.annotations)
        return {
          _tag: "Objects",
          propertySignatures: combinePropertySignatures(a.propertySignatures, b.propertySignatures),
          indexSignatures: combineIndexSignatures(a.indexSignatures, b.indexSignatures),
          checks: checks ?? a.checks,
          ...combineAnnotations(a.annotations, checks ? undefined : b.annotations)
        }
      }
      default:
        return never
    }
  }

  function satisfiesPrimitiveCheck(check: Check<Meta>, value: unknown): boolean {
    if (check._tag === "FilterGroup") {
      return check.checks.every((check) => satisfiesPrimitiveCheck(check, value))
    }
    const meta = check.meta
    switch (meta._tag) {
      case "isMinLength":
        return typeof value === "string" && value.length >= meta.minLength
      case "isMaxLength":
        return typeof value === "string" && value.length <= meta.maxLength
      case "isPattern":
        return typeof value === "string" && meta.regExp.test(value)
      case "isFinite":
        return typeof value === "number" && globalThis.Number.isFinite(value)
      case "isInt":
        return typeof value === "number" && globalThis.Number.isSafeInteger(value)
      case "isMultipleOf":
        return typeof value === "number" && remainder(value, meta.divisor) === 0
      case "isGreaterThan":
        return typeof value === "number" && value > meta.exclusiveMinimum
      case "isGreaterThanOrEqualTo":
        return typeof value === "number" && value >= meta.minimum
      case "isLessThan":
        return typeof value === "number" && value < meta.exclusiveMaximum
      case "isLessThanOrEqualTo":
        return typeof value === "number" && value <= meta.maximum
      default:
        return false
    }
  }

  function satisfiesLiteral(type: String | Number, literal: Literal): boolean {
    const value = literal.literal
    if (type._tag === "String" ? typeof value !== "string" : typeof value !== "number") {
      return false
    }
    return type.checks.every((check) => satisfiesPrimitiveCheck(check, value))
  }

  function collectProperties(js: JsonSchema.JsonSchema): Array<PropertySignature> {
    const properties: Record<string, unknown> = Predicate.isObject(js.properties) ? js.properties : {}
    const required = Array.isArray(js.required) ? js.required : []
    required.forEach((key) => {
      if (!Object.hasOwn(properties, key)) {
        properties[key] = {}
      }
    })
    return Object.entries(properties).map(([key, v]) => ({
      name: key,
      type: recur(v),
      isOptional: !required.includes(key),
      isMutable: false
    }))
  }

  function collectIndexSignatures(js: JsonSchema.JsonSchema): Array<IndexSignature> {
    const out: Array<IndexSignature> = []

    if (Predicate.isObject(js.patternProperties)) {
      for (const [pattern, value] of Object.entries(js.patternProperties)) {
        out.push({ parameter: recur({ pattern }), type: recur(value) })
      }
    }

    if (js.additionalProperties === undefined || js.additionalProperties === true) {
      out.push({ parameter: string, type: unknown })
    } else if (Predicate.isObject(js.additionalProperties)) {
      out.push({ parameter: string, type: recur(js.additionalProperties) })
    }

    return out
  }

  function combineArrays(a: Arrays, b: Arrays): Pick<Arrays, "elements" | "rest"> | undefined {
    const elements: Array<Element> = []
    const len = Math.max(a.elements.length, b.elements.length)
    for (let i = 0; i < len; i++) {
      const ae = a.elements[i]
      const be = b.elements[i]
      const isOptional = ae?.isOptional !== false && be?.isOptional !== false
      const at = ae?.type ?? a.rest[0]
      const bt = be?.type ?? b.rest[0]
      if (at === undefined || bt === undefined) {
        return isOptional ? { elements, rest: [] } : undefined
      }
      const type = combine(at, bt)
      if (type === never) {
        return isOptional ? { elements, rest: [] } : undefined
      }
      elements.push({ isOptional, type })
    }

    const ar = a.rest[0]
    const br = b.rest[0]
    if (ar === undefined || br === undefined) {
      return { elements, rest: [] }
    }
    const rest = combine(ar, br)
    return { elements, rest: rest === never ? [] : [rest] }
  }

  function combinePropertySignatures(
    a: ReadonlyArray<PropertySignature>,
    b: ReadonlyArray<PropertySignature>
  ): Array<PropertySignature> {
    const propertySignatures: Array<PropertySignature> = []
    const thatPropertiesMap: Record<PropertyKey, PropertySignature> = {}
    for (const p of b) {
      thatPropertiesMap[p.name] = p
    }
    const keys = new Set<PropertyKey>()
    for (const p of a) {
      keys.add(p.name)
      const thatp = thatPropertiesMap[p.name]
      if (thatp) {
        propertySignatures.push(
          {
            name: p.name,
            type: combine(p.type, thatp.type),
            isOptional: p.isOptional && thatp.isOptional,
            isMutable: p.isMutable
          }
        )
      } else {
        propertySignatures.push(p)
      }
    }
    for (const p of b) {
      if (!keys.has(p.name)) propertySignatures.push(p)
    }
    return propertySignatures
  }

  function combineIndexSignatures(
    a: ReadonlyArray<IndexSignature>,
    b: ReadonlyArray<IndexSignature>
  ): Array<IndexSignature> {
    if (a.length === 0 || b.length === 0) return []
    const out: Array<IndexSignature> = [...a]
    for (const is of b) {
      if (is.parameter === string) {
        const i = a.findIndex((is) => is.parameter === string)
        if (i !== -1) {
          out[i] = { parameter: string, type: combine(a[i].type, is.type) }
        } else {
          out.push(is)
        }
      } else {
        out.push(is)
      }
    }
    return out
  }

  function unknownToJson(representation: Representation): Representation {
    switch (representation._tag) {
      case "Unknown":
        return representation.annotations === undefined ?
          json :
          {
            ...json,
            annotations: {
              ...json.annotations,
              ...representation.annotations
            }
          }
      case "Suspend": {
        const thunk = unknownToJson(representation.thunk)
        return thunk === representation.thunk ? representation : { ...representation, thunk }
      }
      case "String": {
        if (representation.contentSchema === undefined) return representation
        const contentSchema = unknownToJson(representation.contentSchema)
        return contentSchema === representation.contentSchema ? representation : { ...representation, contentSchema }
      }
      case "Arrays": {
        const elements = SchemaAST.mapOrSame(representation.elements, (element) => {
          const type = unknownToJson(element.type)
          return type === element.type ? element : { ...element, type }
        })
        const rest = SchemaAST.mapOrSame(representation.rest, unknownToJson)
        return elements === representation.elements && rest === representation.rest ?
          representation :
          { ...representation, elements, rest }
      }
      case "Objects": {
        const propertySignatures = SchemaAST.mapOrSame(representation.propertySignatures, (propertySignature) => {
          const type = unknownToJson(propertySignature.type)
          return type === propertySignature.type ? propertySignature : { ...propertySignature, type }
        })
        const indexSignatures = SchemaAST.mapOrSame(representation.indexSignatures, (indexSignature) => {
          const type = unknownToJson(indexSignature.type)
          return type === indexSignature.type ? indexSignature : { ...indexSignature, type }
        })
        return propertySignatures === representation.propertySignatures &&
            indexSignatures === representation.indexSignatures ?
          representation :
          { ...representation, propertySignatures, indexSignatures }
      }
      case "Union": {
        const types = SchemaAST.mapOrSame(representation.types, unknownToJson)
        return types === representation.types ? representation : { ...representation, types }
      }
      default:
        return representation
    }
  }
}