// Lowering a typed module to the binary form.
//
// Ported from wax/src/lib-conversion/to_wasm.ml, folding in the index
// resolution of wax/src/lib-wasm/text_to_binary.ml.
//
// The interface to the checker is narrower than its size suggests: every
// instruction node carries the types it produced, and that annotation is what
// selects an opcode. `i32.add` and `i64.add` are one `+` in the source and two
// instructions here, and the only thing that tells them apart is the cell the
// checker left behind.
//
// Anything not yet lowered RAISES rather than emitting something plausible. The
// vendored encoder shipped with a `_ => 0x00` fallback that turned every
// unhandled instruction into `unreachable`, which is a valid-looking module that
// does the wrong thing; removing it is what made the compiler name the gaps, and
// the same discipline applies here.

///|
pub suberror LowerError {
  /// A construct the lowering does not handle yet, named so the gap is legible.
  NotLowered(String, @basic.Location)
  /// A name or type the checker accepted but that did not survive to here.
  Unresolved(String, @basic.Location)
  /// A construct that is not a gap in this port at all: the binary format has
  /// no way to hold it, and the reference refuses it too. Named separately so
  /// the burn-down is not padded with work that will never be done.
  Unemittable(String, @basic.Location)
  /// Two bindings in one function whose names were written at the same
  /// position. A local's slot is keyed by that position -- see
  /// `Lowering::binding_slots` -- so the second binding would take the first
  /// one's slot and every use of either name would reach one of them.
  ///
  /// Parsed input cannot produce this: two identifiers in one file are two byte
  /// offsets. A GENERATED tree can, by building every identifier at
  /// `@basic.dummy_loc`, and the result would be a module that is wrong rather
  /// than one that fails -- so it fails here instead.
  AmbiguousBinding(String, @basic.Location)
}

///|
/// A one-line description, for the CLI's report.
///
/// The location is named as `file:line:col` rather than rendered as a caret
/// diagram: this is a gap in the port, not a fault in the user's module, and
/// the two should not look alike.
pub impl Show for LowerError with fn output(self, logger) {
  match self {
    // The one error here that is the CALLER's to fix rather than this port's,
    // so it says what to do about it. Its reader is whoever generated the tree.
    AmbiguousBinding(name, loc) =>
      logger.write_string(
        "\{loc.start.fname}:\{loc.start.lnum}:\{loc.start.column1()}: local `\{name}` was written at the same position as an earlier binding in this function; every generated identifier needs a distinct location",
      )
    Unemittable(what, loc) =>
      logger.write_string(
        "\{loc.start.fname}:\{loc.start.lnum}:\{loc.start.column1()}: \{what} cannot be emitted to the WebAssembly binary format",
      )
    NotLowered(what, loc) | Unresolved(what, loc) => {
      let kind = if self is NotLowered(_, _) {
        "not lowered yet"
      } else {
        "did not resolve"
      }
      logger.write_string(
        "\{loc.start.fname}:\{loc.start.lnum}:\{loc.start.column1()}: \{what} \{kind}",
      )
    }
  }
}

///|
/// What the lowering needs to know while walking one module.
struct Lowering {
  ctx : @typing_env.ModuleContext
  store : @type_store.TypeStore
  indices : Indices
  /// Where each type lands in the emitted type section, which is not where the
  /// store put it.
  layout : TypeLayout
  /// Local name to index, rebuilt per function: parameters first, in order,
  /// then each `let` as it is declared. Wasm numbers them in exactly that
  /// order, so the map is built by walking the same way.
  mut locals : Map[String, Int]
  mut local_types : Array[@wasm_types.ValType[Int]]
  /// The slot each `let` binding took, keyed by where its NAME was written.
  ///
  /// Slots are assigned in one pass up front, but a name comes into scope only
  /// after its own initializer -- `let x = x + 1` reads the OUTER `x` -- so the
  /// two cannot both be carried by the name-to-slot map.
  /// Where each lowered node's instructions START and END in the body being
  /// built, recorded as the node COMPLETES -- so a node's span always follows
  /// its children's.
  ///
  /// A wax instruction lowers to its operands and then itself, which is the
  /// post-order flattening of a folded tree. The spans are what let that tree
  /// be read back: the text format writes it folded, and re-deriving the
  /// nesting from an arity table would be a second answer to a question the
  /// lowering has already answered.
  /// Where a field-order entry stands, when that is not where its field does.
  /// A guarded export stands at its attribute; everything else at its field.
  entry_locs : Map[Int, @basic.Location]
  /// The conditional groups the source wrote, for resolving a name from the
  /// branch that asks.
  conditionals : Array[@wasm_bin.CondGroup]
  /// Whether an unresolved `#[if(..)]` may be lowered at all.
  ///
  /// The binary format has nowhere to put one, so `-f wasm` refuses a module
  /// that still has one. The TEXT format writes it, and then both branches are
  /// lowered side by side and told apart afterwards by where they were
  /// written -- which is not a module anyone could run, and is never encoded.
  keep_conditionals : Bool
  /// A `#[start]` an import named, waiting for the import's own field entry.
  mut pending_start : (Int, @ast.Attribute)?
  /// The `#[if(..)]` groups written inside the body being lowered.
  mut body_conditionals : Array[@wasm_bin.CondGroup]
  mut spans : Array[@wasm_bin.Span]
  /// The spans of every NESTED body -- a block's, a loop's, each arm of an
  /// `if` -- in the order those bodies COMPLETE, which is deepest-first and
  /// then left to right. A nested body is a separate array with its own
  /// indices, so its spans cannot live in the enclosing body's list; the
  /// completion order is what pairs them up again, because folding walks the
  /// same tree the lowering built.
  mut nested_spans : Array[Array[@wasm_bin.Span]]
  mut binding_slots : Map[Int, Int]
  /// The wasm-level names already claimed in this function, each with the
  /// number its next duplicate takes. Wasm has one flat namespace per
  /// function, so a shadowing `let` needs a name of its own.
  mut claimed : Map[String, Int]
  /// Local slot to the name the source gave it, for the name section.
  mut local_names : Map[Int, Bytes]
  /// Block label names, keyed by the order the blocks OPEN in.
  ///
  /// The name section numbers labels per function in that order, which is not
  /// the order a `br` counts them in -- depth is relative to where the branch
  /// stands, while a name belongs to the block itself.
  mut label_names : Map[Int, Bytes]
  mut label_counter : Int
  /// The handlers an enclosing `on` clause wrote, waiting for the resume they
  /// belong to. Empty everywhere else.
  mut pending_handlers : Array[@ast.OnClause]
  /// Functions a `ref.func` named from INSIDE a function body, in first-use
  /// order, and those named from outside one.
  ///
  /// A `ref.func` is only valid on a function the module has DECLARED. A
  /// reference in a global initializer or an element segment declares it
  /// already; one inside a body declares nothing, so those need a declarative
  /// element segment minted for them. The two lists are kept apart because a
  /// function in both needs no segment entry.
  func_refs_in_body : Array[String]
  func_refs_outside : Array[String]
  /// Whether a function body is currently being lowered.
  mut in_body : Bool
  /// The labels in scope, innermost last. A `br` names one; the binary counts
  /// outward from the innermost, so the depth is the distance from the end.
  mut labels : Array[String?]
  /// Type index back to the SOURCE definition.
  ///
  /// The store erases field names, because wasm has none -- so a `s.x` needs
  /// the declaration the author wrote to know which slot `x` is. This is the
  /// only place the two views of a type are joined, and it is built once.
  source_types : Map[Int, @ast.SubType]
  /// Function signature back to the type index that interned it.
  ///
  /// A block with parameters or several results is spelled as a reference into
  /// the type section, so its signature has to be findable BY SHAPE -- the
  /// block wrote no name, and the store interned it structurally.
  functypes : Map[
    (Array[@wasm_types.ValType[Int]], Array[@wasm_types.ValType[Int]]),
    Int,
  ]
}

///|
/// Index every function type in the store by its shape.
fn functype_index(
  store : @type_store.TypeStore,
  layout : TypeLayout,
) -> Map[
  (Array[@wasm_types.ValType[Int]], Array[@wasm_types.ValType[Int]]),
  Int,
] {
  let out : Map[
    (Array[@wasm_types.ValType[Int]], Array[@wasm_types.ValType[Int]]),
    Int,
  ] = Map([])
  // Read off the EMITTED section, not the store. Two declarations that
  // interned together can still be different types once their own inner
  // references are resolved -- `fn(&t1)` and `fn(&t2)` are the same shape in
  // the store and two shapes here -- and it is this section a signature is
  // matched against. First match wins, which is the order a search finds.
  ignore(store)
  for emitted, sub in layout.types {
    if sub.composite is Func(ft) {
      let key = (ft.params, ft.results)
      if !out.contains(key) {
        out[key] = emitted
      }
    }
  }
  out
}

///|
/// Index every source type definition by the index it interned to.
fn source_type_index(
  ctx : @typing_env.ModuleContext,
  layout : TypeLayout,
) -> Map[Int, @ast.SubType] {
  let out : Map[Int, @ast.SubType] = Map([])
  for entry in ctx.type_context.types.iter_entries() {
    let (name, (idx, sub)) = entry
    // By NAME where the layout gave the name an entry of its own: two
    // declarations that interned together are one store id and two emitted
    // ones, and only the name says which definition is at which.
    match layout.by_name.get(name) {
      Some(emitted) => out[emitted] = sub
      None =>
        if idx is Def(id) {
          let emitted = emitted_type_index(id.to_int_for_tests_only())
          if !out.contains(emitted) {
            out[emitted] = sub
          }
        }
    }
  }
  out
}

///|
/// The branch depth of a label, counting outward from the innermost.
fn Lowering::depth_of(self : Lowering, name : String) -> Int? {
  let n = self.labels.length()
  for k = n - 1; k >= 0; k = k - 1 {
    if self.labels[k] is Some(l) && l == name {
      return Some(n - 1 - k)
    }
  }
  None
}

///|
/// The reference type of the LAST value this node produces, when it is one a
/// branching cast can name as its SOURCE.
///
/// A `br_on_cast` tests the top of the stack, but a decompiled operand carries
/// every value its label's arity needs, so the last is the one being tested.
///
/// A BOTTOM heap type -- `none`, `nofunc` and their siblings, which is what wax
/// gives a polymorphic operand such as a hole in dead code -- is a subtype of
/// every reference and a supertype of none, so it cannot serve: the `rt2 <:
/// rt1` check the instruction carries would fail whenever the target is in
/// another hierarchy. `None` here means "no determinable source", and the
/// caller falls back to the target, which is always valid against itself.
fn node_last_reftype(
  i : @ast.Instr[@typing_env.InferredAnnotation],
) -> @wasm_types.RefType[Int]? {
  let tys = i.info.0
  guard tys.length() > 0 else { return None }
  guard @typing_env.standalone_valtype(tys[tys.length() - 1]) is Some(v) else {
    return None
  }
  match lower_valtype(v.internal) {
    Ref({ typ: None_ | NoFunc | NoExtern | NoExn | NoCont, .. }) => None
    Ref(r) => Some(r)
    _ => None
  }
}

///|
/// Whether the last value this node produces is a NULLABLE reference.
///
/// A bottom-heap operand has no usable heap type, so the cast target stands in
/// for it -- but a nullable such operand is not a subtype of a non-null target,
/// so its nullability has to carry over or the module is rejected.
fn node_last_nullable(i : @ast.Instr[@typing_env.InferredAnnotation]) -> Bool {
  let tys = i.info.0
  guard tys.length() > 0 else { return false }
  guard @typing_env.standalone_valtype(tys[tys.length() - 1]) is Some(v) else {
    return false
  }
  lower_valtype(v.internal) is Ref({ nullable: true, .. })
}

///|
/// The value type a checked node produced, as an index-form value type.
///
/// `None` when the node produced no single value, or one that never resolved --
/// the caller then raises, because an opcode cannot be chosen without it.
fn node_valtype(
  i : @ast.Instr[@typing_env.InferredAnnotation],
) -> @wasm_types.ValType[Int]? {
  guard i.info.0.length() == 1 else { return None }
  guard @typing_env.standalone_valtype(i.info.0[0]) is Some(v) else {
    return None
  }
  Some(inferred_valtype(v))
}

///|
/// An inferred type as an emitted value type.
///
/// The annotation carries the type twice: the NAME the source form kept and
/// the interned id. The name is the better answer where there is one, because
/// interning collapses distinct declarations and the emitted section does not.
fn inferred_valtype(v : @infer.InferredValType) -> @wasm_types.ValType[Int] {
  match (v.typ, v.internal) {
    (Ref({ typ: Type(n), .. }), Ref(r)) =>
      Ref({
        nullable: r.nullable,
        typ: Type(emitted_named_index(n.name, store_id_of(r.typ))),
      })
    (Ref({ typ: Exact(n), .. }), Ref(r)) =>
      Ref({
        nullable: r.nullable,
        typ: Exact(emitted_named_index(n.name, store_id_of(r.typ))),
      })
    _ => lower_valtype(v.internal)
  }
}

///|
/// The store index a heap type carries, or -1 when it carries none.
fn store_id_of(h : @wasm_types.HeapType[@type_store.Id]) -> Int {
  match h {
    Type(i) | Exact(i) => i.to_int_for_tests_only()
    _ => -1
  }
}

///|
/// Every label name written anywhere inside these instructions.
///
/// The synthetic labels a lowering invents have to avoid these as well as the
/// enclosing ones: a nested block that already takes the name would capture a
/// branch meant for the synthetic one, and the two are only told apart by name.
fn labels_within(
  instrs : Array[@ast.Instr[@typing_env.InferredAnnotation]],
) -> Array[String] {
  let out : Array[String] = []
  fn add(l : @ast.Label?) -> Unit {
    if l is Some(name) {
      out.push(name.name)
    }
  }

  for top in instrs {
    top.iter_instr(i => {
      match i.desc {
        Block(label~, ..)
        | Loop(label~, ..)
        | While(label~, ..)
        | If(label~, ..)
        | TryTable(label~, ..)
        | Try(label~, ..)
        | TryCatch(label~, ..) => add(label)
        _ => ()
      }
    })
  }
  out
}

///|
/// The first name of this series not already taken.
///
/// The reference numbers from the BARE name -- `loop`, then `loop2` -- so the
/// common case reads as the author would have written it, and only a genuine
/// collision gets a suffix.
/// `first` is the number whose name is the BARE base -- 1 for the loop series,
/// where the reference counts from one, and 0 for the arm and catch series.
fn fresh_name(taken : Array[String], base : String, first : Int) -> String {
  let mut k = first
  while true {
    let name = if k == first { base } else { base + k.to_string() }
    if !taken.contains(name) {
      return name
    }
    k = k + 1
  }
  base
}

///|
/// Every label name currently in scope, innermost last.
fn Lowering::enclosing_labels(self : Lowering) -> Array[String] {
  let out : Array[String] = []
  for l in self.labels {
    if l is Some(name) {
      out.push(name)
    }
  }
  out
}