sailfork / t3code-github / .repos/ effect/ packages/ tools/ graphql-generator/ src/ internal/ Emitter.ts

/**
 * Emits per-document and shared modules from validated documents. Paths and
 * import specifiers are supplied by the caller; output needs no formatter.
 * Generated class names that can't be made unique produce diagnostics instead
 * of output.
 *
 * @internal
 */
import * as Arr from "effect/Array"
import type { GraphQL } from "effect/graphql"
import type { GeneratedFile } from "../Generator.ts"
import type * as Ast from "./Ast.ts"
import { type Diagnostic, make } from "./Diagnostic.ts"
import { print, template } from "./Printer.ts"
import * as SchemaModel from "./SchemaModel.ts"
import { type File, fragmentSpreads, inclusion } from "./Validate.ts"

/** One parsed document file holding only executable definitions. */
export interface DocumentFile extends File {
  /** Absolute path of the `.graphql.ts` emitted for this file. */
  readonly outputPath: string
  /** The source file's base name, used in the header. */
  readonly sourceName: string
}

/** A custom or built-in scalar mapped to a codec export. */
export interface ScalarMapping {
  /** The import specifier as written in the shared module. */
  readonly specifier: string
  readonly exportName: string
}

export interface Options {
  readonly schema: SchemaModel.Schema
  readonly files: ReadonlyArray<DocumentFile>
  /** Absolute path of the shared module. */
  readonly sharedPath: string
  readonly scalars: ReadonlyMap<string, ScalarMapping>
  /** The import specifier one generated file uses for another, from absolute paths. */
  readonly importSpecifier: (from: string, to: string) => string
}

export interface Output {
  readonly files: ReadonlyArray<GeneratedFile>
  readonly errors: ReadonlyArray<Diagnostic>
  /** Custom scalars the operations reach that have no mapping, sorted by name. */
  readonly unmappedScalars: ReadonlyArray<string>
}

export const emit = (options: Options): Output => {
  const emitter = new Emitter(options)
  const errors = emitter.check()
  if (errors.length > 0) return { files: [], errors, unmappedScalars: [] }
  const emitted = options.files.map((file) => emitter.emitFile(file))
  const emitErrors = emitted.flatMap((result) => result.errors)
  if (emitErrors.length > 0) return { files: [], errors: emitErrors, unmappedScalars: [] }
  const shared = emitter.emitShared()
  return { files: [shared.file, ...emitted.map((result) => result.file)], errors: [], unmappedScalars: shared.unmapped }
}

// -----------------------------------------------------------------------------
// Text helpers
// -----------------------------------------------------------------------------

export const header = (sourceName: string | undefined): string =>
  `// Generated by @effect/graphql-generator${sourceName === undefined ? "" : ` from ${sourceName}`}. Do not edit.`

/** A private-use character marking class references in rendered structs (see `classRef`). */
const classMarker = "\uE000"

/**
 * Escapes `*\/` so text can't end the JSDoc comment it is written into, and
 * the class reference marker so it can't be mistaken for one.
 */
const escapeComment = (text: string): string => text.replace(/\*\//g, "*\\/").replace(/\uE000/g, "\\uE000")

const deprecation = (reason: string): string => escapeComment(reason.replace(/\s*\r?\n\s*/g, " "))

const descriptionLines = (description: string | undefined): Array<string> => {
  if (description === undefined) return []
  const lines = description.split(/\r\n|\r|\n/).map((line) => escapeComment(line.trimEnd()))
  while (lines.length > 0 && lines[0] === "") lines.shift()
  while (lines.length > 0 && lines[lines.length - 1] === "") lines.pop()
  return lines
}

const docLines = (body: ReadonlyArray<string>, tags: ReadonlyArray<string>): Array<string> =>
  body.length > 0 && tags.length > 0 ? [...body, "", ...tags] : [...body, ...tags]

const jsdoc = (lines: ReadonlyArray<string>, indent: string): string => {
  if (lines.length === 0) return ""
  if (lines.length === 1) return `${indent}/** ${lines[0]} */\n`
  return `${indent}/**\n${
    lines.map((line) => line === "" ? `${indent} *` : `${indent} * ${line}`).join("\n")
  }\n${indent} */\n`
}

const deprecatedTag = (reason: string | undefined): Array<string> =>
  reason === undefined ? [] : [`@deprecated ${deprecation(reason)}`]

const defaultTag = (value: SchemaModel.ConstValue | undefined): Array<string> =>
  value === undefined ? [] : [`@default ${escapeComment(printConstValue(value))}`]

/** A const value in GraphQL syntax, for `@default` tags. */
const printConstValue = (value: SchemaModel.ConstValue): string => {
  switch (value._tag) {
    case "IntValue":
    case "FloatValue":
    case "EnumValue":
      return value.value
    case "StringValue":
      return JSON.stringify(value.value)
    case "BooleanValue":
      return String(value.value)
    case "NullValue":
      return "null"
    case "ListValue":
      return `[${value.values.map(printConstValue).join(", ")}]`
    case "ObjectValue":
      return value.fields.length === 0
        ? "{}"
        : `{ ${value.fields.map((field) => `${field.name}: ${printConstValue(field.value)}`).join(", ")} }`
  }
}

const struct = (members: ReadonlyArray<string>, indent: string, schema = "Schema"): string =>
  members.length === 0 ? `${schema}.Struct({})` : `${schema}.Struct({\n${members.join(",\n")}\n${indent}})`

/** Writes out a type reference: `leaf` for its named type, `list` around list types, `nullable` around types without `!`. */
const typeRef = (
  type: SchemaModel.TypeRef,
  leaf: (name: string) => string,
  list: (element: string) => string,
  nullable: (inner: string) => string
): string => {
  const nonNull = (type: SchemaModel.NamedTypeRef | SchemaModel.ListTypeRef): string =>
    type._tag === "ListTypeRef" ? list(typeRef(type.ofType, leaf, list, nullable)) : leaf(type.name)
  return type._tag === "NonNullTypeRef" ? nonNull(type.ofType) : nullable(nonNull(type))
}

const typeSchema = (type: SchemaModel.TypeRef, leaf: (name: string) => string, schema = "Schema"): string =>
  typeRef(type, leaf, (element) => `${schema}.Array(${element})`, (inner) => `${schema}.NullOr(${inner})`)

/**
 * The Schema for a variable or input field: a nullable one, or a non-null one
 * with a default, is `optional`.
 */
const inputSchema = (
  type: SchemaModel.TypeRef,
  hasDefault: boolean,
  ref: (name: string) => string,
  schema = "Schema"
): string => {
  const expression = typeSchema(
    type,
    (name) => name === "String" || name === "Boolean" ? `${schema}.${name}` : ref(name),
    schema
  )
  return hasDefault || type._tag !== "NonNullTypeRef" ? `${schema}.optional(${expression})` : expression
}

/**
 * A struct key. `__proto__` is written as a computed key, because in an
 * object literal the plain form sets the prototype instead of a field.
 */
const propertyKey = (key: string): string => key === "__proto__" ? `["__proto__"]` : key

/** `issue-timeline` → `IssueTimeline`. */
const pascalCase = (text: string): string =>
  text.split(/[^A-Za-z0-9]+/).map((word) => word.slice(0, 1).toUpperCase() + word.slice(1)).join("")

/** `issue-timeline.graphql` or `issue-timeline.gql` → `IssueTimelineGraphQLGroup`. */
const groupName = (sourceName: string): string => {
  const name = pascalCase(sourceName.replace(/\.(?:graphql|gql)$/, ""))
  return `${/^[0-9]/.test(name) ? `_${name}` : name}GraphQLGroup`
}

const reservedWords: ReadonlySet<string> = new Set([
  "await break case catch class const continue debugger default delete do else enum export extends",
  "false finally for function if implements import in instanceof interface let new null package private",
  "protected public return static super switch this throw true try typeof var void while with yield",
  "any bigint boolean never number object string symbol undefined unknown"
].flatMap((line) => line.split(" ")))

/** Names unavailable for generated bindings or TypeScript type declarations. */
const unbindable = (name: string): boolean => reservedWords.has(name) || name === "arguments" || name === "eval"

/**
 * An alias for each of `names` that can't be bound: `name_`, then more `_`
 * while `taken`. Reserved words hold no `_`, so aliases never collide.
 */
const underscoreAliases = (names: Iterable<string>, taken: ReadonlySet<string>): Map<string, string> => {
  const aliases = new Map<string, string>()
  for (const name of names) {
    if (!unbindable(name)) continue
    let alias = `${name}_`
    while (taken.has(alias)) alias = `${alias}_`
    aliases.set(name, alias)
  }
  return aliases
}

/** Names every per-file module imports, which operations and fragments can't take. */
const importedNames: ReadonlySet<string> = new Set(["Schema", "Shared", "GraphQL", "GraphQLGroup"])

interface BuiltInScalar {
  readonly codec: (schema: string) => string
  /** Whether the codec's Encoded type differs from its Type. */
  readonly transforms: boolean
}

/** The scalars with a default codec in the shared module, in declaration order. */
const builtInSharedScalars: ReadonlyMap<string, BuiltInScalar> = new Map([
  ["Int", { codec: (schema) => `${schema}.Number.check(${schema}.isInt32())`, transforms: false }],
  ["Float", { codec: (schema) => `${schema}.Finite`, transforms: false }],
  ["ID", { codec: (schema) => `${schema}.String`, transforms: false }],
  ["DateTime", { codec: (schema) => `${schema}.DateTimeUtcFromString`, transforms: true }],
  ["URI", { codec: (schema) => `${schema}.String`, transforms: false }]
])

/**
 * Tarjan's strongly connected components of the graph reached from `roots`,
 * in dependency order. Each component's nodes are in the order they were
 * reached.
 */
const stronglyConnectedComponents = (
  roots: Iterable<string>,
  successors: (node: string) => Iterable<string>
): Array<ReadonlyArray<string>> => {
  const index = new Map<string, number>()
  const low = new Map<string, number>()
  const stack: Array<string> = []
  const onStack = new Set<string>()
  const components: Array<ReadonlyArray<string>> = []
  const visit = (node: string): void => {
    const nodeIndex = index.size
    index.set(node, nodeIndex)
    low.set(node, nodeIndex)
    stack.push(node)
    onStack.add(node)
    for (const next of successors(node)) {
      if (!index.has(next)) {
        visit(next)
        low.set(node, Math.min(low.get(node)!, low.get(next)!))
      } else if (onStack.has(next)) {
        low.set(node, Math.min(low.get(node)!, index.get(next)!))
      }
    }
    if (low.get(node) !== nodeIndex) return
    const component = stack.splice(stack.lastIndexOf(node))
    for (const member of component) onStack.delete(member)
    components.push(component)
  }
  for (const root of roots) {
    if (!index.has(root)) visit(root)
  }
  return components
}

// -----------------------------------------------------------------------------
// Emitter
// -----------------------------------------------------------------------------

interface FragmentEntry {
  readonly definition: Ast.FragmentDefinition
  readonly file: DocumentFile
}

/**
 * A selection together with where it came from. `via` is undefined when the
 * selection is written in the file being emitted; otherwise it is the spread
 * in that file through which a fragment from another file was written out
 * inline. `conditional` is set when the selection, or a fragment it came
 * through, has a `@skip` / `@include` with a variable condition.
 */
interface Sourced<S extends Ast.Selection> {
  readonly selection: S
  readonly via: Ast.FragmentSpread | undefined
  readonly conditional: boolean
  /**
   * The selection's index in each enclosing selection set, from the
   * definition's root, with fragments expanded where they are spread.
   * Comparing two orders tells which selection comes first in the document.
   */
  readonly order: ReadonlyArray<number>
}

/** A selection after inline fragments are flattened into their parent. */
type FlatSelection = Sourced<Ast.Field | Ast.FragmentSpread>

interface SpreadItem {
  readonly _tag: "Spread"
  readonly name: string
  readonly spread: Ast.FragmentSpread
  readonly via: Ast.FragmentSpread | undefined
}

type Item = { readonly _tag: "Field"; readonly key: string; readonly fields: Array<Sourced<Ast.Field>> } | SpreadItem

const written = (selections: ReadonlyArray<Ast.Selection>): Array<Sourced<Ast.Selection>> =>
  selections.map((selection, i) => ({ selection, via: undefined, conditional: false, order: [i] }))

const isAbstract = (type: SchemaModel.NamedType): type is SchemaModel.InterfaceType | SchemaModel.UnionType =>
  type._tag === "InterfaceType" || type._tag === "UnionType"

/** `prefix` followed by `"A" | "B"`, wrapped onto `|` lines when it doesn't fit in 120 columns. */
const literalUnion = (prefix: string, names: ReadonlyArray<string>, indent: string): string => {
  if (names.length === 0) return `${prefix}never`
  const literals = names.map((name) => JSON.stringify(name))
  const single = `${prefix}${literals.join(" | ")}`
  if (single.length <= 120) return single
  const lines: Array<string> = []
  let line = ""
  for (const literal of literals) {
    const next = line === "" ? `${indent}  | ${literal}` : `${line} | ${literal}`
    if (next.length > 120 && line !== "") {
      lines.push(line)
      line = `${indent}  | ${literal}`
    } else {
      line = next
    }
  }
  lines.push(line)
  return `${prefix.trimEnd()}\n${lines.join("\n")}`
}

/**
 * Identical nested selections share a schema and interface within a file,
 * using the first occurrence's path for naming.
 */
interface ExtractedClass {
  readonly id: number
  /** The type's name, or `<AbstractType>Other` for a catch-all member. */
  readonly typeName: string
  readonly description: string | undefined
  /** The operation or fragment holding the selection. */
  definition: string
  /** Response keys from the definition's root down to the field holding the selection. */
  path: ReadonlyArray<string>
  /** Where the selection is written in the file being emitted. */
  offset: number
  /** The definition's index in the file, then the selection's place in it (see `Sourced.order`). */
  order: ReadonlyArray<number>
  /** The struct, with `classRef(id)` standing for each class it uses. */
  readonly body: string
  /** Fragments of this file the struct uses. */
  readonly refs: ReadonlySet<string>
}

/**
 * A rendered struct or struct member. `identity` stands for the selection
 * that produced it: response keys, the fields they select, optionality and
 * nested classes and fragments, independent of the order keys are written in.
 */
interface Struct {
  readonly code: string
  readonly identity: string
}

/** A reference to a fragment or an extracted class, standing for its own selection. */
const refStruct = (ref: string): Struct => ({ code: ref, identity: ref })

/** Which of two `Sourced.order`s comes first in the document. */
const compareOrder = (a: ReadonlyArray<number>, b: ReadonlyArray<number>): number => {
  for (let i = 0; i < Math.min(a.length, b.length); i++) {
    if (a[i] !== b[i]) return a[i]! - b[i]!
  }
  return a.length - b.length
}

interface EmittedFile {
  readonly file: GeneratedFile
  readonly errors: ReadonlyArray<Diagnostic>
}

/**
 * Stands for an extracted class until the file's classes are named.
 * `escapeComment` escapes the marker in the only text from documents that
 * structs carry.
 */
const classRef = (id: number): string => `${classMarker}${id}${classMarker}`

const classRefPattern = /\uE000(\d+)\uE000/g

/** `author` → `Author`, for response keys in class names. */
const capitalize = (key: string): string => key.slice(0, 1).toUpperCase() + key.slice(1)

interface FileContext {
  readonly file: DocumentFile
  usesSchema: boolean
  usesGraphQL: boolean
  usesShared: boolean
  /** Fragments imported from other files, each with the first spread in this file that led to the import. */
  readonly imports: Map<string, Ast.FragmentSpread>
  /** Fragments of this file referenced by the code being rendered. */
  localRefs: Set<string>
  /** The classes extracted so far, in order of extraction. */
  readonly classes: Array<ExtractedClass>
  readonly byShape: Map<string, ExtractedClass>
  /** The name and index of the definition being rendered. */
  definition: { readonly name: string; readonly index: number }
  /** Response keys from the definition's root to the selection being rendered. */
  readonly path: Array<string>
  /** Where the field holding the selection being rendered is written. */
  offset: number
  /** The document order of the field holding the selection being rendered. */
  order: ReadonlyArray<number>
  readonly errors: Array<Diagnostic>
}

class Emitter {
  readonly fragments = new Map<string, FragmentEntry>()
  /** Named types the per-file modules reference through `Shared`. */
  readonly reached = new Set<string>()
  /** Interfaces and unions the per-file modules reference through `Shared.Typename`. */
  readonly reachedAbstract = new Set<string>()
  /** The `Shared.Typename` members whose abstract type's name can't be bound. */
  readonly typenameAliases: ReadonlyMap<string, string>
  readonly fragmentKeyCache = new Map<string, ReadonlyArray<string>>()

  readonly options: Options

  constructor(options: Options) {
    this.options = options
    const abstractNames = Array.from(options.schema.types.values()).filter(isAbstract).map((type) => type.name).sort()
    this.typenameAliases = underscoreAliases(abstractNames, new Set(abstractNames))
    for (const file of options.files) {
      for (const definition of file.document.definitions) {
        if (definition._tag === "FragmentDefinition") {
          this.fragments.set(definition.name.value, { definition, file })
        }
      }
    }
  }

  type(name: string): SchemaModel.NamedType {
    const type = this.options.schema.types.get(name)
    if (type === undefined) throw new Error(`@effect/graphql-generator: unknown type ${name} after validation`)
    return type
  }

  fieldDefinition(parent: SchemaModel.NamedType, name: string): SchemaModel.Field {
    const fields = parent._tag === "ObjectType" || parent._tag === "InterfaceType" ? parent.fields : []
    const field = fields.find((field) => field.name === name)
    if (field === undefined) {
      throw new Error(`@effect/graphql-generator: unknown field ${parent.name}.${name} after validation`)
    }
    return field
  }

  /** The object types a type stands for: itself, or an abstract type's possible types. */
  possibleTypes(name: string): ReadonlyArray<string> {
    const type = this.type(name)
    return isAbstract(type) ? type.possibleTypes : [name]
  }

  rootType(operation: Ast.OperationDefinition): string {
    return SchemaModel.rootTypeName(this.options.schema, operation.operation)!
  }

  // ---------------------------------------------------------------------------
  // Checks
  // ---------------------------------------------------------------------------

  /** Names generated code can't use and import cycles, sorted by file and position. */
  check(): ReadonlyArray<Diagnostic> {
    const errors: Array<{ readonly file: number; readonly offset: number; readonly message: string }> = []
    this.options.files.forEach((file, fileIndex) => {
      const report = (offset: number, message: string) => errors.push({ file: fileIndex, offset, message })
      const group = groupName(file.sourceName)
      const exportsGroup = file.document.definitions.some((definition) => definition._tag === "OperationDefinition")
      if (exportsGroup && importedNames.has(group)) {
        report(0, `The group name "${group}" is reserved in generated code; rename this file.`)
      }
      for (const definition of file.document.definitions) {
        if (definition._tag !== "OperationDefinition" && definition._tag !== "FragmentDefinition") continue
        const name = definition.name
        if (name !== undefined) {
          if (importedNames.has(name.value) || unbindable(name.value)) {
            report(name.loc.start, `The name "${name.value}" is reserved in generated code; rename this definition.`)
          } else if (name.value === group && exportsGroup) {
            report(name.loc.start, `The name "${name.value}" is taken by the group this file exports.`)
          }
        }
      }
    })
    errors.push(...this.importCycles())
    return errors
      .sort((a, b) => a.file - b.file || a.offset - b.offset)
      .map((error) => make(this.options.files[error.file]!.source, error.offset, error.message))
  }

  /**
   * Cycles in the imports between generated files. Every fragment reference
   * is read while its module initializes, so any cycle throws for some entry
   * point. Each cycle is reported once, at its first cross-file spread by file
   * order and then position. Every cross-file spread counts, including ones
   * the emitter would write out inline, so the rule doesn't depend on how a
   * selection set is merged.
   */
  importCycles(): Array<{ readonly file: number; readonly offset: number; readonly message: string }> {
    const files = this.options.files
    const indexOf = new Map(files.map((file, i) => [file, i] as const))
    const edges: Array<{ readonly from: number; readonly to: number; readonly spread: Ast.FragmentSpread }> = []
    const adjacent = files.map(() => new Set<number>())
    files.forEach((file, from) => {
      for (const definition of file.document.definitions) {
        if (definition._tag !== "OperationDefinition" && definition._tag !== "FragmentDefinition") continue
        for (const spread of fragmentSpreads(definition.selectionSet)) {
          const entry = this.fragments.get(spread.name.value)
          if (entry === undefined || entry.file === file) continue
          const to = indexOf.get(entry.file)!
          edges.push({ from, to, spread })
          adjacent[from]!.add(to)
        }
      }
    })

    // Tarjan's strongly connected components.
    const index: Array<number | undefined> = files.map(() => undefined)
    const low: Array<number> = files.map(() => 0)
    const onStack = files.map(() => false)
    const stack: Array<number> = []
    const components: Array<ReadonlySet<number>> = []
    let next = 0
    const connect = (v: number): void => {
      index[v] = low[v] = next++
      stack.push(v)
      onStack[v] = true
      for (const w of adjacent[v]!) {
        if (index[w] === undefined) {
          connect(w)
          low[v] = Math.min(low[v]!, low[w]!)
        } else if (onStack[w]) {
          low[v] = Math.min(low[v]!, index[w]!)
        }
      }
      if (low[v] === index[v]) {
        const component = new Set<number>()
        let w: number
        do {
          w = stack.pop()!
          onStack[w] = false
          component.add(w)
        } while (w !== v)
        if (component.size > 1) components.push(component)
      }
    }
    files.forEach((_, v) => {
      if (index[v] === undefined) connect(v)
    })

    return components.map((component) => {
      const first = edges
        .filter((edge) => component.has(edge.from) && component.has(edge.to))
        .sort((a, b) => a.from - b.from || a.spread.loc.start - b.spread.loc.start)[0]!
      // The shortest way back from the spread's target to the spreading file.
      const previous = new Map<number, number>([[first.to, -1]])
      const queue = [first.to]
      while (!previous.has(first.from)) {
        const v = queue.shift()!
        for (const w of adjacent[v]!) {
          if (component.has(w) && !previous.has(w)) {
            previous.set(w, v)
            queue.push(w)
          }
        }
      }
      const path: Array<number> = []
      for (let v = first.from; v !== -1; v = previous.get(v)!) path.unshift(v)
      const names = [first.from, ...path].map((i) => files[i]!.source.path)
      return {
        file: first.from,
        offset: first.spread.loc.start,
        message:
          `Fragment spread "...${first.spread.name.value}" makes the generated modules import each other in a cycle: ${
            names.join(" -> ")
          }. Move fragments between files so the imports don't form a cycle.`
      }
    })
  }

  // ---------------------------------------------------------------------------
  // Result selections
  // ---------------------------------------------------------------------------

  /**
   * Whether a fragment on `condition` applies to `target`. A target that is an
   * object type is one concrete type. A target that is an interface or union
   * stands for the possible types no fragment names, so only a fragment
   * covering every one of its possible types applies.
   */
  applies(condition: string | undefined, target: string): boolean {
    if (condition === undefined || condition === target) return true
    const type = this.type(target)
    if (type._tag === "ObjectType") {
      const fragmentType = this.type(condition)
      return isAbstract(fragmentType) && fragmentType.possibleTypes.includes(target)
    }
    // Only an interface the target declares contributes fields the target has.
    return type._tag === "InterfaceType" && type.interfaces.includes(condition)
  }

  /**
   * Flattens a selection set for `target`: inline fragments and spreads that
   * apply to it are written into their parent and the rest are dropped,
   * excluded selections are dropped, and variable conditions are carried down.
   * A spread of a fragment on exactly the object type `target` is kept, unless
   * it is conditional, since `...Frag.fields` can't make its keys optional.
   */
  narrow(file: DocumentFile, selections: ReadonlyArray<Sourced<Ast.Selection>>, target: string): Array<FlatSelection> {
    const out: Array<FlatSelection> = []
    for (const { conditional: outer, order, selection, via } of selections) {
      const included = inclusion(selection.directives)
      if (included === "exclude") continue
      const conditional = outer || included === "conditional"
      switch (selection._tag) {
        case "Field":
          out.push({ selection, via, conditional, order })
          break
        case "InlineFragment":
          if (this.applies(selection.typeCondition?.name.value, target)) {
            out.push(...this.narrow(
              file,
              selection.selectionSet.selections.map((selection, i) => ({
                selection,
                via,
                conditional,
                order: [...order, i]
              })),
              target
            ))
          }
          break
        case "FragmentSpread": {
          const fragment = this.fragment(selection.name.value)
          const condition = fragment.definition.typeCondition.name.value
          if (condition === target && this.type(target)._tag === "ObjectType" && !conditional) {
            out.push({ selection, via, conditional, order })
          } else if (this.applies(condition, target)) {
            out.push(...this.narrow(file, this.expand(file, fragment, selection, via, conditional, order), target))
          }
          break
        }
      }
    }
    return out
  }

  /** A fragment's selections, written out inline through `spread`. */
  expand(
    file: DocumentFile,
    fragment: FragmentEntry,
    spread: Ast.FragmentSpread,
    via: Ast.FragmentSpread | undefined,
    conditional: boolean,
    order: ReadonlyArray<number>
  ): Array<Sourced<Ast.Selection>> {
    // A local fragment's selections are written in this file; another file's come in through this spread.
    const through = fragment.file === file ? undefined : via ?? spread
    return fragment.definition.selectionSet.selections.map((selection, i) => ({
      selection,
      via: through,
      conditional,
      order: [...order, i]
    }))
  }

  group(flat: ReadonlyArray<FlatSelection>): Array<Item> {
    const items: Array<Item> = []
    const fields = new Map<string, Array<Sourced<Ast.Field>>>()
    const spreads = new Set<string>()
    for (const entry of flat) {
      const selection = entry.selection
      if (selection._tag === "Field") {
        const key = (selection.alias ?? selection.name).value
        const existing = fields.get(key)
        const sourced = { selection, via: entry.via, conditional: entry.conditional, order: entry.order }
        if (existing === undefined) {
          const merged = [sourced]
          fields.set(key, merged)
          items.push({ _tag: "Field", key, fields: merged })
        } else {
          existing.push(sourced)
        }
      } else if (!spreads.has(selection.name.value)) {
        spreads.add(selection.name.value)
        items.push({ _tag: "Spread", name: selection.name.value, spread: selection, via: entry.via })
      }
    }
    return items
  }

  fragment(name: string): FragmentEntry {
    const entry = this.fragments.get(name)
    if (entry === undefined) throw new Error(`@effect/graphql-generator: unknown fragment ${name} after validation`)
    return entry
  }

  /** Every response key a fragment on an object type contributes, through nested spreads. */
  fragmentKeys(name: string): ReadonlyArray<string> {
    const cached = this.fragmentKeyCache.get(name)
    if (cached !== undefined) return cached
    const entry = this.fragment(name)
    const keys = new Set<string>()
    const flat = this.narrow(
      entry.file,
      written(entry.definition.selectionSet.selections),
      entry.definition.typeCondition.name.value
    )
    for (const item of this.group(flat)) {
      if (item._tag === "Field") keys.add(item.key)
      else for (const key of this.fragmentKeys(item.name)) keys.add(key)
    }
    const result = Array.from(keys)
    this.fragmentKeyCache.set(name, result)
    return result
  }

  /**
   * Groups a selection set for `target`, writing out inline every spread
   * whose keys overlap a sibling's or one of `reserved`.
   * The remaining spreads become `...Frag.fields`.
   */
  resolveItems(
    file: DocumentFile,
    selections: ReadonlyArray<Sourced<Ast.Selection>>,
    target: string,
    reserved: ReadonlyArray<string> = []
  ): Array<Item> {
    let flat = this.narrow(file, selections, target)
    for (;;) {
      const items = this.group(flat)
      const overlapping = items.find((item) => {
        if (item._tag !== "Spread") return false
        const others = new Set<string>(reserved)
        for (const other of items) {
          if (other === item) continue
          if (other._tag === "Field") others.add(other.key)
          else for (const key of this.fragmentKeys(other.name)) others.add(key)
        }
        return this.fragmentKeys(item.name).some((key) => others.has(key))
      })
      if (overlapping === undefined || overlapping._tag !== "Spread") return items
      const fragment = this.fragment(overlapping.name)
      flat = flat.flatMap((entry) => {
        const selection = entry.selection
        if (selection._tag !== "FragmentSpread" || selection.name.value !== overlapping.name) return [entry]
        return this.narrow(
          file,
          this.expand(file, fragment, selection, entry.via, entry.conditional, entry.order),
          target
        )
      })
    }
  }

  fragmentRef(ctx: FileContext, item: SpreadItem): string {
    const name = item.name
    if (this.fragment(name).file === ctx.file) ctx.localRefs.add(name)
    else if (!ctx.imports.has(name)) ctx.imports.set(name, item.via ?? item.spread)
    return name
  }

  shared(ctx: FileContext, name: string): string {
    ctx.usesShared = true
    this.reached.add(name)
    return `Shared.${name}`
  }

  typename(ctx: FileContext, name: string): string {
    ctx.usesShared = true
    this.reachedAbstract.add(name)
    return `Shared.Typename.${this.typenameAliases.get(name) ?? name}`
  }

  /**
   * The Schema for a selection set on `parentName`, starting on a line
   * indented by `indent`. A selection that is only one spread of a fragment
   * on exactly that type references the fragment unless `alwaysStruct` is
   * set. With `nested` set, a struct with members is extracted as a class.
   */
  selection(
    ctx: FileContext,
    parentName: string,
    selections: ReadonlyArray<Sourced<Ast.Selection>>,
    indent: string,
    alwaysStruct = false,
    nested = false
  ): Struct {
    const parent = this.type(parentName)
    if (isAbstract(parent)) {
      const only = alwaysStruct ? undefined : this.onlySpread(selections, parentName)
      return only !== undefined
        ? refStruct(this.fragmentRef(ctx, only))
        : this.abstractSelection(ctx, parent, selections, indent, nested)
    }
    const items = this.resolveItems(ctx.file, selections, parentName)
    const only = items[0]
    if (!alwaysStruct && items.length === 1 && only!._tag === "Spread") {
      return refStruct(this.fragmentRef(ctx, only!))
    }
    const typename = `Schema.Literal(${JSON.stringify(parent.name)})`
    return nested && items.length > 0
      ? refStruct(
        this.extract(ctx, parent.name, parent.description, () => this.structOf(ctx, parent, items, "", typename, false))
      )
      : this.structOf(ctx, parent, items, indent, typename, false)
  }

  /**
   * Renders a struct written at the top level as a class of the file and
   * refers to it. A struct with the same identity reuses the class, which
   * keeps the path of whichever occurrence comes first in the document.
   */
  extract(ctx: FileContext, typeName: string, description: string | undefined, render: () => Struct): string {
    const outer = ctx.localRefs
    ctx.localRefs = new Set()
    const struct = render()
    const refs = ctx.localRefs
    ctx.localRefs = outer
    for (const ref of refs) outer.add(ref)
    const order = [ctx.definition.index, ...ctx.order]
    const shape = `${typeName}\u0001${struct.identity}`
    const existing = ctx.byShape.get(shape)
    if (existing !== undefined) {
      if (compareOrder(order, existing.order) < 0) {
        existing.definition = ctx.definition.name
        existing.path = ctx.path.slice()
        existing.offset = ctx.offset
        existing.order = order
      }
      return classRef(existing.id)
    }
    const extracted: ExtractedClass = {
      id: ctx.classes.length,
      typeName,
      description,
      definition: ctx.definition.name,
      path: ctx.path.slice(),
      offset: ctx.offset,
      order,
      body: struct.code,
      refs
    }
    ctx.classes.push(extracted)
    ctx.byShape.set(shape, extracted)
    return classRef(extracted.id)
  }

  /** The one spread a selection set consists of, when it is an unconditional spread of a fragment on `parentName`. */
  onlySpread(selections: ReadonlyArray<Sourced<Ast.Selection>>, parentName: string): SpreadItem | undefined {
    const kept = selections.filter(({ selection }) => inclusion(selection.directives) !== "exclude")
    const only = kept[0]
    if (kept.length !== 1 || only!.selection._tag !== "FragmentSpread") return undefined
    const spread = only!.selection
    if (only!.conditional || inclusion(spread.directives) !== "include") return undefined
    if (this.fragment(spread.name.value).definition.typeCondition.name.value !== parentName) return undefined
    return { _tag: "Spread", name: spread.name.value, spread, via: only!.via }
  }

  /**
   * The object types a selection on an abstract type names through fragments
   * that don't apply to the type itself (see `applies`), in order of first
   * mention. Each gets its own member of the union, even when it is the only
   * possible type.
   */
  selectedTypes(
    parent: SchemaModel.InterfaceType | SchemaModel.UnionType,
    selections: ReadonlyArray<Sourced<Ast.Selection>>
  ): Array<string> {
    const all = parent.possibleTypes
    const selected: Array<string> = []
    const walk = (selections: ReadonlyArray<Ast.Selection>, scope: ReadonlyArray<string>): void => {
      for (const selection of selections) {
        if (selection._tag === "Field" || inclusion(selection.directives) === "exclude") continue
        const definition = selection._tag === "FragmentSpread"
          ? this.fragment(selection.name.value).definition
          : selection
        const condition = definition.typeCondition?.name.value
        let next = scope
        if (!this.applies(condition, parent.name)) {
          const inScope = new Set(scope)
          next = this.possibleTypes(condition!).filter((name) => inScope.has(name))
          for (const name of next) if (!selected.includes(name)) selected.push(name)
        }
        walk(definition.selectionSet.selections, next)
      }
    }
    walk(selections.map(({ selection }) => selection), all)
    return selected
  }

  /**
   * A selection on an interface or union: one struct per
   * selected object type with `__typename: Schema.Literal("T")`, and one for
   * every other possible type with `GraphQL.otherTypename`. Each member of
   * the union is extracted as a class; without selected types the one struct
   * is extracted only when `nested` is set. The identity ignores the order the
   * types are mentioned in, which only decides the order members are written.
   */
  abstractSelection(
    ctx: FileContext,
    parent: SchemaModel.InterfaceType | SchemaModel.UnionType,
    selections: ReadonlyArray<Sourced<Ast.Selection>>,
    indent: string,
    nested: boolean
  ): Struct {
    ctx.usesGraphQL = true
    const selected = this.selectedTypes(parent, selections)
    const others = `GraphQL.otherTypename<${this.typename(ctx, parent.name)}>()([${
      selected.map((name) => JSON.stringify(name)).join(", ")
    }])`
    const othersIdentity = `GraphQL.otherTypename(${selected.slice().sort().join(",")})`
    const member = (type: SchemaModel.NamedType, typename: string, indent: string, typenameIdentity = typename) =>
      this.structOf(
        ctx,
        type,
        this.resolveItems(ctx.file, selections, type.name, ["__typename"]),
        indent,
        typename,
        true,
        typenameIdentity
      )
    if (selected.length === 0) {
      return nested
        ? refStruct(
          this.extract(ctx, parent.name, parent.description, () => member(parent, others, "", othersIdentity))
        )
        : member(parent, others, indent, othersIdentity)
    }
    const members = [
      ...selected.map((name) => {
        const type = this.type(name)
        return this.extract(
          ctx,
          name,
          type.description,
          () => member(type, `Schema.Literal(${JSON.stringify(name)})`, "")
        )
      }),
      this.extract(ctx, `${parent.name}Other`, parent.description, () => member(parent, others, "", othersIdentity))
    ]
    const memberIndent = `${indent}  `
    return {
      code: `Schema.Union([\n${members.map((member) => `${memberIndent}${member}`).join(",\n")}\n${indent}])`,
      identity: `Schema.Union(${members.slice().sort().join(",")})`
    }
  }

  /**
   * A struct for `items` on `parent`. `typename` is the Schema for a
   * selected `__typename`; with `discriminated` set, `__typename` comes first
   * whether or not it was selected. `typenameIdentity` stands for `typename`
   * in the identity.
   */
  structOf(
    ctx: FileContext,
    parent: SchemaModel.NamedType,
    items: ReadonlyArray<Item>,
    indent: string,
    typename: string,
    discriminated: boolean,
    typenameIdentity = typename
  ): Struct {
    ctx.usesSchema = true
    const memberIndent = `${indent}  `
    const members: Array<string> = discriminated ? [`${memberIndent}__typename: ${typename}`] : []
    const identities: Array<string> = []
    for (const item of items) {
      if (item._tag === "Spread") {
        const name = this.fragmentRef(ctx, item)
        members.push(`${memberIndent}...${name}.fields`)
        identities.push(`...${name}`)
      } else if (!(discriminated && item.key === "__typename")) {
        const member = this.resultMember(ctx, parent, item.key, item.fields, memberIndent, typename, typenameIdentity)
        members.push(member.code)
        identities.push(member.identity)
      }
    }
    return {
      code: struct(members, indent),
      identity: [discriminated ? typenameIdentity : "", ...identities.sort()].join("\u0002")
    }
  }

  resultMember(
    ctx: FileContext,
    parent: SchemaModel.NamedType,
    key: string,
    fields: ReadonlyArray<Sourced<Ast.Field>>,
    indent: string,
    typename: string,
    typenameIdentity: string
  ): Struct {
    const name = fields[0]!.selection.name.value
    const isOptional = fields.every((field) => field.conditional)
    const optional = (expression: string): string => isOptional ? `Schema.optionalKey(${expression})` : expression
    const identity = (inner: string) => [key, name, isOptional ? "?" : "", inner].join("\u0003")
    if (name === "__typename") {
      return { code: `${indent}${propertyKey(key)}: ${optional(typename)}`, identity: identity(typenameIdentity) }
    }
    const definition = this.fieldDefinition(parent, name)
    const typeName = SchemaModel.namedTypeOf(definition.type)
    const type = this.type(typeName)
    const inner = type._tag === "ObjectType" || isAbstract(type)
      ? this.nestedSelection(
        ctx,
        key,
        fields[0]!,
        typeName,
        indent,
        // The parent's key covers its only occurrence's condition. With several
        // occurrences, the parent can be present because of another one, so
        // each occurrence's condition carries over to the children it adds.
        fields.flatMap(({ conditional, order, selection: field, via }) =>
          (field.selectionSet?.selections ?? []).map((selection, i) => ({
            selection,
            via,
            conditional: conditional && fields.length > 1,
            order: [...order, i]
          }))
        )
      )
      : undefined
    const doc = docLines(descriptionLines(definition.description), deprecatedTag(definition.deprecationReason))
    const expression = optional(typeSchema(definition.type, () => inner?.code ?? this.resultLeaf(ctx, type)))
    return {
      code: `${jsdoc(doc, indent)}${indent}${propertyKey(key)}: ${expression}`,
      // A leaf's Schema follows from the field.
      identity: identity(inner?.identity ?? "")
    }
  }

  /** The selection under the field `key`, with `key` added to the path of the classes it extracts. */
  nestedSelection(
    ctx: FileContext,
    key: string,
    first: Sourced<Ast.Field>,
    typeName: string,
    indent: string,
    selections: ReadonlyArray<Sourced<Ast.Selection>>
  ): Struct {
    const { offset, order } = ctx
    ctx.path.push(key)
    ctx.offset = (first.via ?? first.selection).loc.start
    ctx.order = first.order
    const expression = this.selection(ctx, typeName, selections, indent, false, true)
    ctx.path.pop()
    ctx.offset = offset
    ctx.order = order
    return expression
  }

  resultLeaf(ctx: FileContext, type: SchemaModel.NamedType): string {
    if (type.name === "String" || type.name === "Boolean") return `Schema.${type.name}`
    if (type._tag === "EnumType") {
      ctx.usesGraphQL = true
      return `GraphQL.enumLiterals(${this.shared(ctx, type.name)}.literals)`
    }
    return this.shared(ctx, type.name)
  }

  // ---------------------------------------------------------------------------
  // Per-file modules
  // ---------------------------------------------------------------------------

  /**
   * Emits one per-file module. Fails with a located error when the module
   * would import a fragment named like the group it exports, or when a
   * class can't be given a name of its own; the import is found from the
   * code actually emitted, so a spread written out inline counts only for
   * the fragments it really brings in.
   */
  emitFile(file: DocumentFile): EmittedFile {
    const ctx: FileContext = {
      file,
      usesSchema: false,
      usesGraphQL: false,
      usesShared: false,
      imports: new Map(),
      localRefs: new Set(),
      classes: [],
      byShape: new Map(),
      definition: { name: "", index: 0 },
      path: [],
      offset: 0,
      order: [],
      errors: []
    }

    const fragments = new Map<string, { readonly code: string; readonly refs: ReadonlySet<string> }>()
    const operations: Array<string> = []
    const operationNames: Array<string> = []
    file.document.definitions.forEach((definition, index) => {
      if (definition._tag !== "FragmentDefinition" && definition._tag !== "OperationDefinition") return
      const name = definition.name!
      ctx.localRefs = new Set()
      ctx.definition = { name: name.value, index }
      ctx.offset = name.loc.start
      ctx.order = []
      if (definition._tag === "FragmentDefinition") {
        fragments.set(name.value, { code: this.emitFragment(ctx, definition), refs: ctx.localRefs })
      } else {
        operations.push(this.emitOperation(ctx, definition))
        operationNames.push(name.value)
      }
    })

    const group = groupName(file.sourceName)
    const errors = ctx.errors
    const taken = new Map<string, string>()
    for (const name of importedNames) taken.set(name, "is reserved in generated code")
    for (const name of [...fragments.keys(), ...operationNames]) {
      taken.set(name, "is taken by a definition in this file")
    }
    for (const name of ctx.imports.keys()) taken.set(name, "is taken by a fragment this file imports")
    if (operationNames.length > 0) taken.set(group, "is taken by the group this file exports")
    const names = this.nameClasses(ctx, taken)
    const fill = (text: string) => text.replace(classRefPattern, (_, id: string) => names[Number(id)]!)

    // Fragments and classes are declared before the code that uses them: each
    // fragment after the fragments it uses, and each class after the
    // fragments and classes it uses.
    const blocks: Array<string> = []
    const placedClasses = new Set<number>()
    const placedFragments = new Set<string>()
    const placeClasses = (code: string): void => {
      // A class only uses classes extracted before it.
      const used = new Set<number>()
      const visit = (text: string): void => {
        for (const match of text.matchAll(classRefPattern)) {
          const id = Number(match[1])
          if (used.has(id)) continue
          used.add(id)
          visit(ctx.classes[id]!.body)
        }
      }
      visit(code)
      for (const id of Array.from(used).sort((a, b) => a - b)) {
        if (placedClasses.has(id)) continue
        placedClasses.add(id)
        const extracted = ctx.classes[id]!
        for (const ref of extracted.refs) placeFragment(ref)
        const name = names[id]!
        blocks.push(
          `${jsdoc(descriptionLines(extracted.description), "")}export const ${name} = ${
            fill(extracted.body)
          }\nexport interface ${name} extends Schema.Struct.Type<typeof ${name}.fields> {}`
        )
      }
    }
    const placeFragment = (name: string): void => {
      if (placedFragments.has(name)) return
      placedFragments.add(name)
      const fragment = fragments.get(name)!
      for (const ref of fragment.refs) placeFragment(ref)
      placeClasses(fragment.code)
      blocks.push(fill(fragment.code))
    }
    for (const name of fragments.keys()) placeFragment(name)
    for (const operation of operations) {
      placeClasses(operation)
      blocks.push(fill(operation))
    }

    if (operationNames.length > 0) {
      blocks.push(
        `/** Every operation in ${file.sourceName}. */\nexport const ${group} = GraphQLGroup.make(${
          operationNames.join(", ")
        })`
      )
      const via = ctx.imports.get(group)
      if (via !== undefined) {
        errors.push(make(
          file.source,
          via.loc.start,
          `Fragment "${group}" from ${
            this.fragment(group).file.source.path
          } can't be imported here: the name is taken by the group this file exports.`
        ))
      }
    }

    const imports: Array<string> = []
    const graphql = [...(ctx.usesGraphQL ? ["GraphQL"] : []), ...(operationNames.length > 0 ? ["GraphQLGroup"] : [])]
    if (graphql.length > 0) imports.push(`import { ${graphql.join(", ")} } from "effect/graphql"`)
    if (ctx.usesSchema) imports.push(`import * as Schema from "effect/Schema"`)
    const bySpecifier = Arr.groupBy(
      Array.from(ctx.imports.keys()).sort(),
      (name) => this.options.importSpecifier(file.outputPath, this.fragment(name).file.outputPath)
    )
    for (const specifier of Object.keys(bySpecifier).sort()) {
      imports.push(`import { ${bySpecifier[specifier].join(", ")} } from ${JSON.stringify(specifier)}`)
    }
    if (ctx.usesShared) {
      imports.push(
        `import * as Shared from ${
          JSON.stringify(this.options.importSpecifier(file.outputPath, this.options.sharedPath))
        }`
      )
    }

    return {
      file: {
        path: file.outputPath,
        contents: `${[header(file.sourceName), ...imports].join("\n")}\n\n${blocks.join("\n\n")}\n`
      },
      errors
    }
  }

  /**
   * Names the file's classes after their types. Classes that would share a
   * name, and ones whose name is `taken` or can't be bound, all add their
   * field's response key, then parent response keys one at a time, then
   * their definition's name, until the names are free. Ones that run out
   * are reported.
   */
  nameClasses(ctx: FileContext, taken: ReadonlyMap<string, string>): Array<string> {
    const classes = ctx.classes
    const levels = classes.map(() => 0)
    const nameAt = (extracted: ExtractedClass, level: number): string => {
      const keys = extracted.path.slice(Math.max(0, extracted.path.length - level)).map(capitalize).join("")
      return `${level > extracted.path.length ? extracted.definition : ""}${keys}${extracted.typeName}`
    }
    let names: Array<string>
    let counts: Map<string, number>
    let conflicts: Array<number>
    for (;;) {
      names = classes.map((extracted, i) => nameAt(extracted, levels[i]!))
      counts = new Map()
      for (const name of names) counts.set(name, (counts.get(name) ?? 0) + 1)
      conflicts = names.flatMap((name, i) => counts.get(name)! > 1 || taken.has(name) || unbindable(name) ? [i] : [])
      let advanced = false
      for (const i of conflicts) {
        if (levels[i]! <= classes[i]!.path.length) {
          levels[i]!++
          advanced = true
        }
      }
      if (!advanced) break
    }
    for (const i of conflicts.sort((a, b) => classes[a]!.offset - classes[b]!.offset)) {
      const name = names[i]!
      ctx.errors.push(make(
        ctx.file.source,
        classes[i]!.offset,
        counts.get(name)! > 1
          ? `Different selections here would all generate the class "${name}"; alias one of the fields.`
          : `The generated class name "${name}" ${taken.get(name) ?? "is reserved in generated code"}; alias the field.`
      ))
    }
    return names
  }

  emitFragment(ctx: FileContext, definition: Ast.FragmentDefinition): string {
    const name = definition.name.value
    const type = this.type(definition.typeCondition.name.value)
    ctx.usesSchema = true
    const description = definition.description?.value ?? type.description
    const doc = docLines([`\`fragment ${name} on ${type.name}\``], descriptionLines(description))
    const selections = written(definition.selectionSet.selections)
    if (isAbstract(type)) {
      const body = this.abstractSelection(ctx, type, selections, "", false).code
      return `${jsdoc(doc, "")}export const ${name} = ${body}\nexport type ${name} = typeof ${name}.Type`
    }
    const body = this.selection(ctx, type.name, selections, "", true).code
    return `${
      jsdoc(doc, "")
    }export const ${name} = ${body}\nexport interface ${name} extends Schema.Struct.Type<typeof ${name}.fields> {}`
  }

  emitOperation(ctx: FileContext, definition: Ast.OperationDefinition): string {
    const name = definition.name!.value
    const root = this.rootType(definition)
    ctx.usesGraphQL = true
    const doc = docLines(
      [`\`${definition.operation} ${name}\``],
      descriptionLines(definition.description?.value)
    )
    const lines = [`  document: ${this.document(definition)},`]
    if (definition.variableDefinitions.length > 0) {
      const members = definition.variableDefinitions.map((variable) => {
        const defaultValue = variable.defaultValue === undefined
          ? undefined
          : SchemaModel.fromAstConstValue(variable.defaultValue)
        const type = SchemaModel.fromAstType(variable.type)
        const expression = inputSchema(type, defaultValue !== undefined, (name) => this.shared(ctx, name))
        ctx.usesSchema ||= expression.includes("Schema.")
        const variableDoc = docLines(descriptionLines(variable.description?.value), defaultTag(defaultValue))
        return `${jsdoc(variableDoc, "    ")}    ${propertyKey(variable.variable.name.value)}: ${expression}`
      })
      lines.push(`  variables: {\n${members.join(",\n")}\n  },`)
    }
    lines.push(`  result: ${this.selection(ctx, root, written(definition.selectionSet.selections), "  ").code}`)
    return [
      `${jsdoc(doc, "")}export const ${name} = GraphQL.${definition.operation}(${JSON.stringify(name)}, {`,
      ...lines,
      "})",
      `export declare namespace ${name} {`,
      `  export type Variables = typeof ${name}.variables.Type`,
      `  export type Result = typeof ${name}.result.Type`,
      "}"
    ].join("\n")
  }

  /**
   * The `document` expression: the operation printed compactly, followed by
   * every fragment it uses in order of first use, with `__typename` added to
   * every selection on an interface or union that doesn't already select it.
   * Queries and mutations get a `DocumentTemplate` of that text, subscriptions
   * the text itself.
   */
  document(operation: Ast.OperationDefinition): string {
    const names = new Set(fragmentSpreads(operation.selectionSet).map((spread) => spread.name.value))
    for (const name of names) {
      for (const spread of fragmentSpreads(this.fragment(name).definition.selectionSet)) names.add(spread.name.value)
    }
    const root = {
      ...operation,
      selectionSet: this.withTypename(operation.selectionSet, this.rootType(operation))
    }
    const fragments = Array.from(names, (name) => {
      const fragment = this.fragment(name).definition
      return { ...fragment, selectionSet: this.withTypename(fragment.selectionSet, fragment.typeCondition.name.value) }
    })
    if (operation.operation === "subscription") {
      return JSON.stringify(print({ _tag: "Document", definitions: [root, ...fragments], loc: operation.loc }))
    }
    return emitTemplate(template(root, fragments))
  }

  /**
   * Adds `__typename` to a selection set on an interface or union. Inline
   * fragments share their parent's response object, so the one added there
   * covers them (`inline`).
   */
  withTypename(selectionSet: Ast.SelectionSet, parentName: string, inline = false): Ast.SelectionSet {
    const parent = this.type(parentName)
    const selections = selectionSet.selections.map((selection): Ast.Selection => {
      switch (selection._tag) {
        case "Field": {
          if (selection.selectionSet === undefined) return selection
          const definition = this.fieldDefinition(parent, selection.name.value)
          return {
            ...selection,
            selectionSet: this.withTypename(selection.selectionSet, SchemaModel.namedTypeOf(definition.type))
          }
        }
        case "InlineFragment":
          return {
            ...selection,
            selectionSet: this.withTypename(
              selection.selectionSet,
              selection.typeCondition?.name.value ?? parentName,
              true
            )
          }
        case "FragmentSpread":
          return selection
      }
    })
    const selectsTypename = selections.some((selection) =>
      selection._tag === "Field" && selection.alias === undefined && selection.name.value === "__typename" &&
      selection.directives.length === 0
    )
    if (inline || !isAbstract(parent) || selectsTypename) return { ...selectionSet, selections }
    const loc = selectionSet.loc
    const typename: Ast.Field = {
      _tag: "Field",
      alias: undefined,
      name: { _tag: "Name", value: "__typename", loc },
      arguments: [],
      directives: [],
      selectionSet: undefined,
      loc
    }
    return { ...selectionSet, selections: [typename, ...selections] }
  }

  // ---------------------------------------------------------------------------
  // Shared module
  // ---------------------------------------------------------------------------

  /** The shared module, and the custom scalars it holds without a mapping. */
  emitShared(): { readonly file: GeneratedFile; readonly unmapped: ReadonlyArray<string> } {
    // Close over input objects in dependency order, keeping each cycle's
    // members together.
    const fieldTypes = (name: string): ReadonlyArray<string> => {
      const type = this.type(name)
      return type._tag === "InputObjectType" ? type.fields.map((field) => SchemaModel.namedTypeOf(field.type)) : []
    }
    const components = stronglyConnectedComponents(Array.from(this.reached).sort(), fieldTypes)
    const order = components.flat()
    const all = new Set(order)
    const inputs = order.flatMap((name) => {
      const type = this.type(name)
      return type._tag === "InputObjectType" ? [type] : []
    })
    /** Each recursive input object's cycle. */
    const cycles = new Map<string, ReadonlySet<string>>()
    /** The input objects whose Encoded type differs from their Type. */
    const transforms = new Set<string>()
    // A mapped scalar codec may transform; an unmapped custom scalar is `Schema.Json`.
    const transformsLeaf = (name: string): boolean =>
      this.type(name)._tag === "ScalarType"
        ? this.options.scalars.has(name) || builtInSharedScalars.get(name)?.transforms === true
        : transforms.has(name)
    for (const component of components) {
      const members = new Set(component)
      const leaves = component.flatMap(fieldTypes)
      if (members.size > 1 || leaves.includes(component[0])) {
        for (const name of component) cycles.set(name, members)
      }
      if (leaves.some((leaf) => !members.has(leaf) && transformsLeaf(leaf))) {
        for (const name of component) transforms.add(name)
      }
    }
    all.delete("String")
    all.delete("Boolean")

    const byName = Array.from(all).sort()
    const builtIns = Array.from(builtInSharedScalars.keys()).filter((name) =>
      all.has(name) && this.type(name)._tag === "ScalarType"
    )
    const scalars = byName.filter((name) => this.type(name)._tag === "ScalarType" && !builtInSharedScalars.has(name))
    const enums = byName.flatMap((name) => {
      const type = this.type(name)
      return type._tag === "EnumType" ? [type] : []
    })

    // Each type is exported under its GraphQL name, which per-file modules read
    // as `Shared.<name>`. A name the module can't bind gets a local alias,
    // and the module's own imports take names no type uses.
    const taken = new Set<string>([...byName, "Typename"])
    const allocate = (candidate: string): string => {
      let name = candidate
      for (let i = 2; taken.has(name) || unbindable(name); i++) name = `${candidate}${i}`
      taken.add(name)
      return name
    }
    const aliases = underscoreAliases(byName, taken)
    const alias = (name: string): string => aliases.get(name) ?? name
    const schema = allocate("Schema")

    let usesSchema = enums.length > 0 || inputs.length > 0
    const modules = new Map<string, string>()
    const moduleName = (specifier: string): string => {
      if (specifier === "effect/Schema") {
        usesSchema = true
        return schema
      }
      const existing = modules.get(specifier)
      if (existing !== undefined) return existing
      const candidate = pascalCase(specifier.split("/").pop()!.replace(/\.[^.]*$/, ""))
      const name = allocate(candidate === "" || /^[0-9]/.test(candidate) ? "Scalars" : candidate)
      modules.set(specifier, name)
      return name
    }
    const scalarCodec = (name: string, fallback: string): string => {
      const mapping = this.options.scalars.get(name)
      if (mapping === undefined) {
        usesSchema = true
        return fallback
      }
      return `${moduleName(mapping.specifier)}.${mapping.exportName}`
    }
    /**
     * A documented declaration, exported under the GraphQL name: directly, or
     * through `export { alias as Name }` when the name can't be bound.
     * `declaration` puts `exported` before each statement it writes.
     */
    const declare = (
      name: string,
      doc: ReadonlyArray<string>,
      declaration: (binding: string, exported: string) => string
    ): string => {
      const binding = alias(name)
      return binding === name
        ? `${jsdoc(doc, "")}${declaration(name, "export ")}`
        : `${jsdoc(doc, "")}${declaration(binding, "")}\nexport { ${binding} as ${name} }`
    }

    const blocks: Array<string> = []
    for (const name of [...builtIns, ...scalars]) {
      const codec = scalarCodec(name, builtInSharedScalars.get(name)?.codec(schema) ?? `${schema}.Json`)
      blocks.push(declare(name, descriptionLines(this.type(name).description), (b, e) => `${e}const ${b} = ${codec}`))
    }
    for (const type of enums) {
      const values = type.values.map((value) => {
        const description = descriptionLines(value.description).join(" ")
        const deprecated = value.deprecationReason === undefined
          ? ""
          : ` Deprecated: ${deprecation(value.deprecationReason)}`
        return `- \`${value.name}\`${description === "" ? "" : `: ${description}`}${deprecated}`
      })
      const literals = type.values.map((value) => JSON.stringify(value.name)).join(", ")
      blocks.push(declare(
        type.name,
        docLines(descriptionLines(type.description), values),
        (b, e) => `${e}const ${b} = ${schema}.Literals([${literals}])\n${e}type ${b} = typeof ${b}.Type`
      ))
    }
    // Recursive input objects whose Encoded type differs from their Type.
    const encodedNames = new Map<string, string>()
    for (const type of inputs) {
      if (cycles.has(type.name) && transforms.has(type.name)) {
        encodedNames.set(type.name, allocate(`${type.name}Encoded`))
      }
    }
    // Enums and input objects declare a type under their name; scalars don't.
    const typeLeaf = (name: string): string =>
      this.type(name)._tag === "ScalarType" ? `typeof ${alias(name)}.Type` : alias(name)
    const encodedLeaf = (name: string): string =>
      cycles.has(name) ? encodedNames.get(name) ?? alias(name) : `typeof ${alias(name)}.Encoded`
    for (const type of inputs) {
      const doc = descriptionLines(type.description)
      const cycle = cycles.get(type.name)
      if (cycle !== undefined) {
        const recursion: Recursion = {
          encoded: encodedNames.get(type.name),
          ref: (name) => cycle.has(name) ? `${schema}.suspend(() => ${alias(name)})` : alias(name),
          typeLeaf,
          encodedLeaf
        }
        blocks.push(declare(type.name, doc, (b, e) => recursiveDeclaration(type, b, e, schema, recursion)))
        continue
      }
      if (type.oneOf) {
        blocks.push(declare(type.name, doc, (b, e) => oneOfDeclaration(type, b, e, schema, alias, typeLeaf)))
        continue
      }
      const members = type.fields.map((field) => {
        const fieldDoc = docLines(
          descriptionLines(field.description),
          [...deprecatedTag(field.deprecationReason), ...defaultTag(field.defaultValue)]
        )
        return `${jsdoc(fieldDoc, "  ")}  ${propertyKey(field.name)}: ${
          inputSchema(field.type, field.defaultValue !== undefined, alias, schema)
        }`
      })
      const body = struct(members, "", schema)
      blocks.push(declare(
        type.name,
        doc,
        (b, e) => `${e}const ${b} = ${body}\n${e}interface ${b} extends ${schema}.Struct.Type<typeof ${b}.fields> {}`
      ))
    }

    if (this.reachedAbstract.size > 0) {
      const members = Array.from(this.reachedAbstract).sort().map((name) => {
        const kind = this.type(name)._tag === "InterfaceType" ? "interface" : "union"
        const doc = `  /** Every possible \`__typename\` of ${kind} \`${name}\`. */\n`
        return `${doc}${
          literalUnion(`  export type ${this.typenameAliases.get(name) ?? name} = `, this.possibleTypes(name), "  ")
        }`
      })
      blocks.push(
        `/** The possible \`__typename\` values of each interface and union the operations select from. */\n` +
          `export declare namespace Typename {\n${members.join("\n")}\n}`
      )
    }

    const imports: Array<string> = []
    if (usesSchema) imports.push(`import * as ${schema} from "effect/Schema"`)
    for (const [specifier, name] of modules) {
      imports.push(`import * as ${name} from ${JSON.stringify(specifier)}`)
    }
    const body = blocks.length === 0 ? "export {}" : blocks.join("\n\n")
    return {
      file: { path: this.options.sharedPath, contents: `${[header(undefined), ...imports].join("\n")}\n\n${body}\n` },
      unmapped: scalars.filter((name) => !this.options.scalars.has(name))
    }
  }
}

/**
 * A `@oneOf` input object: a `Schema.Union` with one
 * struct per field, each with that field required and non-null and every
 * other field `optionalKey(Never)`, so an input with two keys or none fails to