summary refs log tree commit diff stats
path: root/compiler/semtypinst.nim
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/semtypinst.nim')
-rw-r--r--compiler/semtypinst.nim866
1 files changed, 866 insertions, 0 deletions
diff --git a/compiler/semtypinst.nim b/compiler/semtypinst.nim
new file mode 100644
index 000000000..759e8e6ab
--- /dev/null
+++ b/compiler/semtypinst.nim
@@ -0,0 +1,866 @@
+#
+#
+#           The Nim Compiler
+#        (c) Copyright 2015 Andreas Rumpf
+#
+#    See the file "copying.txt", included in this
+#    distribution, for details about the copyright.
+#
+
+# This module does the instantiation of generic types.
+
+import std / tables
+
+import ast, astalgo, msgs, types, magicsys, semdata, renderer, options,
+  lineinfos, modulegraphs
+
+when defined(nimPreviewSlimSystem):
+  import std/assertions
+
+const tfInstClearedFlags = {tfHasMeta, tfUnresolved}
+
+proc checkPartialConstructedType(conf: ConfigRef; info: TLineInfo, t: PType) =
+  if t.kind in {tyVar, tyLent} and t.elementType.kind in {tyVar, tyLent}:
+    localError(conf, info, "type 'var var' is not allowed")
+
+proc checkConstructedType*(conf: ConfigRef; info: TLineInfo, typ: PType) =
+  var t = typ.skipTypes({tyDistinct})
+  if t.kind in tyTypeClasses: discard
+  elif t.kind in {tyVar, tyLent} and t.elementType.kind in {tyVar, tyLent}:
+    localError(conf, info, "type 'var var' is not allowed")
+  elif computeSize(conf, t) == szIllegalRecursion or isTupleRecursive(t):
+    localError(conf, info, "illegal recursion in type '" & typeToString(t) & "'")
+
+proc searchInstTypes*(g: ModuleGraph; key: PType): PType =
+  result = nil
+  let genericTyp = key[0]
+  if not (genericTyp.kind == tyGenericBody and
+      genericTyp.sym != nil): return
+
+  for inst in typeInstCacheItems(g, genericTyp.sym):
+    if inst.id == key.id: return inst
+    if inst.kidsLen < key.kidsLen:
+      # XXX: This happens for prematurely cached
+      # types such as Channel[empty]. Why?
+      # See the notes for PActor in handleGenericInvocation
+      # if this is return the same type gets cached more than it needs to
+      continue
+    if not sameFlags(inst, key):
+      continue
+
+    block matchType:
+      for j in FirstGenericParamAt..<key.kidsLen:
+        # XXX sameType is not really correct for nested generics?
+        if not compareTypes(inst[j], key[j],
+                            flags = {ExactGenericParams, PickyCAliases}):
+          break matchType
+
+      return inst
+
+proc cacheTypeInst(c: PContext; inst: PType) =
+  let gt = inst[0]
+  let t = if gt.kind == tyGenericBody: gt.typeBodyImpl else: gt
+  if t.kind in {tyStatic, tyError, tyGenericParam} + tyTypeClasses:
+    return
+  addToGenericCache(c, gt.sym, inst)
+
+type
+  LayeredIdTable* {.acyclic.} = ref object
+    topLayer*: TypeMapping
+    nextLayer*: LayeredIdTable
+
+  TReplTypeVars* = object
+    c*: PContext
+    typeMap*: LayeredIdTable  # map PType to PType
+    symMap*: SymMapping         # map PSym to PSym
+    localCache*: TypeMapping     # local cache for remembering already replaced
+                              # types during instantiation of meta types
+                              # (they are not stored in the global cache)
+    info*: TLineInfo
+    allowMetaTypes*: bool     # allow types such as seq[Number]
+                              # i.e. the result contains unresolved generics
+    skipTypedesc*: bool       # whether we should skip typeDescs
+    isReturnType*: bool
+    owner*: PSym              # where this instantiation comes from
+    recursionLimit: int
+
+proc replaceTypeVarsTAux(cl: var TReplTypeVars, t: PType): PType
+proc replaceTypeVarsS(cl: var TReplTypeVars, s: PSym, t: PType): PSym
+proc replaceTypeVarsN*(cl: var TReplTypeVars, n: PNode; start=0; expectedType: PType = nil): PNode
+
+proc initLayeredTypeMap*(pt: sink TypeMapping): LayeredIdTable =
+  result = LayeredIdTable()
+  result.topLayer = pt
+
+proc newTypeMapLayer*(cl: var TReplTypeVars): LayeredIdTable =
+  result = LayeredIdTable(nextLayer: cl.typeMap, topLayer: initTable[ItemId, PType]())
+
+proc lookup(typeMap: LayeredIdTable, key: PType): PType =
+  result = nil
+  var tm = typeMap
+  while tm != nil:
+    result = getOrDefault(tm.topLayer, key.itemId)
+    if result != nil: return
+    tm = tm.nextLayer
+
+template put(typeMap: LayeredIdTable, key, value: PType) =
+  typeMap.topLayer[key.itemId] = value
+
+template checkMetaInvariants(cl: TReplTypeVars, t: PType) = # noop code
+  when false:
+    if t != nil and tfHasMeta in t.flags and
+       cl.allowMetaTypes == false:
+      echo "UNEXPECTED META ", t.id, " ", instantiationInfo(-1)
+      debug t
+      writeStackTrace()
+
+proc replaceTypeVarsT*(cl: var TReplTypeVars, t: PType): PType =
+  result = replaceTypeVarsTAux(cl, t)
+  checkMetaInvariants(cl, result)
+
+proc prepareNode*(cl: var TReplTypeVars, n: PNode): PNode =
+  ## instantiates a given generic expression, not a type node
+  if n.kind == nkSym and n.sym.kind == skType and
+      n.sym.typ != nil and n.sym.typ.kind == tyGenericBody:
+    # generic body types are allowed as user expressions, see #24090
+    return n
+  let t = replaceTypeVarsT(cl, n.typ)
+  if t != nil and t.kind == tyStatic and t.n != nil:
+    return if tfUnresolved in t.flags: prepareNode(cl, t.n)
+           else: t.n
+  result = copyNode(n)
+  result.typ = t
+  if result.kind == nkSym:
+    result.sym =
+      if n.typ != nil and n.typ == n.sym.typ:
+        replaceTypeVarsS(cl, n.sym, result.typ)
+      else:
+        replaceTypeVarsS(cl, n.sym, replaceTypeVarsT(cl, n.sym.typ))
+  # we need to avoid trying to instantiate nodes that can have uninstantiated
+  # types, like generic proc symbols or raw generic type symbols
+  case n.kind
+  of nkSymChoices:
+    # don't try to instantiate symchoice symbols, they can be
+    # generic procs which the compiler will think are uninstantiated
+    # because their type will contain uninstantiated params
+    for i in 0..<n.len:
+      result.add(n[i])
+  of nkCallKinds:
+    # don't try to instantiate call names since they may be generic proc syms
+    # also bracket expressions can turn into calls with symchoice [] and
+    # we need to not instantiate the Generic in Generic[int]
+    # exception exists for the call name being a dot expression since
+    # dot expressions need their LHS instantiated
+    assert n.len != 0
+    # avoid instantiating generic proc symbols, refine condition if needed:
+    let ignoreFirst = n[0].kind notin {nkDotExpr, nkBracketExpr} + nkCallKinds
+    let name = n[0].getPIdent
+    let ignoreSecond = name != nil and name.s == "[]" and n.len > 1 and
+      # generic type instantiation:
+      ((n[1].typ != nil and n[1].typ.kind == tyTypeDesc) or
+        # generic proc instantiation:
+        (n[1].kind == nkSym and n[1].sym.isGenericRoutineStrict))
+    if ignoreFirst:
+      result.add(n[0])
+    else:
+      result.add(prepareNode(cl, n[0]))
+    if n.len > 1:
+      if ignoreSecond:
+        result.add(n[1])
+      else:
+        result.add(prepareNode(cl, n[1]))
+    for i in 2..<n.len:
+      result.add(prepareNode(cl, n[i]))
+  of nkBracketExpr:
+    # don't instantiate Generic body type in expression like Generic[T]
+    # exception exists for the call name being a dot expression since
+    # dot expressions need their LHS instantiated
+    assert n.len != 0
+    let ignoreFirst = n[0].kind != nkDotExpr and
+      # generic type instantiation:
+      ((n[0].typ != nil and n[0].typ.kind == tyTypeDesc) or
+        # generic proc instantiation:
+        (n[0].kind == nkSym and n[0].sym.isGenericRoutineStrict))
+    if ignoreFirst:
+      result.add(n[0])
+    else:
+      result.add(prepareNode(cl, n[0]))
+    for i in 1..<n.len:
+      result.add(prepareNode(cl, n[i]))
+  of nkDotExpr:
+    # don't try to instantiate RHS of dot expression, it can outright be
+    # undeclared, but definitely instantiate LHS
+    assert n.len >= 2
+    result.add(prepareNode(cl, n[0]))
+    result.add(n[1])
+    for i in 2..<n.len:
+      result.add(prepareNode(cl, n[i]))
+  else:
+    for i in 0..<n.safeLen:
+      result.add(prepareNode(cl, n[i]))
+
+proc isTypeParam(n: PNode): bool =
+  # XXX: generic params should use skGenericParam instead of skType
+  return n.kind == nkSym and
+         (n.sym.kind == skGenericParam or
+           (n.sym.kind == skType and sfFromGeneric in n.sym.flags))
+
+when false: # old workaround
+  proc reResolveCallsWithTypedescParams(cl: var TReplTypeVars, n: PNode): PNode =
+    # This is needed for tuninstantiatedgenericcalls
+    # It's possible that a generic param will be used in a proc call to a
+    # typedesc accepting proc. After generic param substitution, such procs
+    # should be optionally instantiated with the correct type. In order to
+    # perform this instantiation, we need to re-run the generateInstance path
+    # in the compiler, but it's quite complicated to do so at the moment so we
+    # resort to a mild hack; the head symbol of the call is temporary reset and
+    # overload resolution is executed again (which may trigger generateInstance).
+    if n.kind in nkCallKinds and sfFromGeneric in n[0].sym.flags:
+      var needsFixing = false
+      for i in 1..<n.safeLen:
+        if isTypeParam(n[i]): needsFixing = true
+      if needsFixing:
+        n[0] = newSymNode(n[0].sym.owner)
+        return cl.c.semOverloadedCall(cl.c, n, n, {skProc, skFunc}, {})
+
+    for i in 0..<n.safeLen:
+      n[i] = reResolveCallsWithTypedescParams(cl, n[i])
+
+    return n
+
+proc replaceObjBranches(cl: TReplTypeVars, n: PNode): PNode =
+  result = n
+  case n.kind
+  of nkNone..nkNilLit:
+    discard
+  of nkRecWhen:
+    var branch: PNode = nil              # the branch to take
+    for i in 0..<n.len:
+      var it = n[i]
+      if it == nil: illFormedAst(n, cl.c.config)
+      case it.kind
+      of nkElifBranch:
+        checkSonsLen(it, 2, cl.c.config)
+        var cond = it[0]
+        var e = cl.c.semConstExpr(cl.c, cond)
+        if e.kind != nkIntLit:
+          internalError(cl.c.config, e.info, "ReplaceTypeVarsN: when condition not a bool")
+        if e.intVal != 0 and branch == nil: branch = it[1]
+      of nkElse:
+        checkSonsLen(it, 1, cl.c.config)
+        if branch == nil: branch = it[0]
+      else: illFormedAst(n, cl.c.config)
+    if branch != nil:
+      result = replaceObjBranches(cl, branch)
+    else:
+      result = newNodeI(nkRecList, n.info)
+  else:
+    for i in 0..<n.len:
+      n[i] = replaceObjBranches(cl, n[i])
+
+proc hasValuelessStatics(n: PNode): bool =
+  # We should only attempt to call an expression that has no tyStatics
+  # As those are unresolved generic parameters, which means in the following
+  # The compiler attempts to do `T == 300` which errors since the typeclass `MyThing` lacks a parameter
+  #[
+    type MyThing[T: static int] = object
+      when T == 300:
+        a
+    proc doThing(_: MyThing)
+  ]#
+  if n.safeLen == 0 and n.kind != nkEmpty: # Some empty nodes can get in here
+    n.typ == nil or n.typ.kind == tyStatic
+  else:
+    for x in n:
+      if hasValuelessStatics(x):
+        return true
+    false
+
+proc replaceTypeVarsN(cl: var TReplTypeVars, n: PNode; start=0; expectedType: PType = nil): PNode =
+  if n == nil: return
+  result = copyNode(n)
+  if n.typ != nil:
+    if n.typ.kind == tyFromExpr:
+      # type of node should not be evaluated as a static value
+      n.typ.flags.incl tfNonConstExpr
+    result.typ = replaceTypeVarsT(cl, n.typ)
+    checkMetaInvariants(cl, result.typ)
+  case n.kind
+  of nkNone..pred(nkSym), succ(nkSym)..nkNilLit:
+    discard
+  of nkOpenSymChoice, nkClosedSymChoice: result = n
+  of nkSym:
+    result.sym =
+      if n.typ != nil and n.typ == n.sym.typ:
+        replaceTypeVarsS(cl, n.sym, result.typ)
+      else:
+        replaceTypeVarsS(cl, n.sym, replaceTypeVarsT(cl, n.sym.typ))
+    # sym type can be nil if was gensym created by macro, see #24048
+    if result.sym.typ != nil and result.sym.typ.kind == tyVoid:
+      # don't add the 'void' field
+      result = newNodeI(nkRecList, n.info)
+  of nkRecWhen:
+    var branch: PNode = nil              # the branch to take
+    for i in 0..<n.len:
+      var it = n[i]
+      if it == nil: illFormedAst(n, cl.c.config)
+      case it.kind
+      of nkElifBranch:
+        checkSonsLen(it, 2, cl.c.config)
+        var cond = prepareNode(cl, it[0])
+        if not cond.hasValuelessStatics:
+          var e = cl.c.semConstExpr(cl.c, cond)
+          if e.kind != nkIntLit:
+            internalError(cl.c.config, e.info, "ReplaceTypeVarsN: when condition not a bool")
+          if e.intVal != 0 and branch == nil: branch = it[1]
+      of nkElse:
+        checkSonsLen(it, 1, cl.c.config)
+        if branch == nil: branch = it[0]
+      else: illFormedAst(n, cl.c.config)
+    if branch != nil:
+      result = replaceTypeVarsN(cl, branch)
+    else:
+      result = newNodeI(nkRecList, n.info)
+  of nkStaticExpr:
+    var n = prepareNode(cl, n)
+    when false:
+      n = reResolveCallsWithTypedescParams(cl, n)
+    result = if cl.allowMetaTypes: n
+             else: cl.c.semExpr(cl.c, n, {}, expectedType)
+    if not cl.allowMetaTypes and expectedType != nil:
+      assert result.kind notin nkCallKinds
+  else:
+    if n.len > 0:
+      newSons(result, n.len)
+      if start > 0:
+        result[0] = n[0]
+      for i in start..<n.len:
+        result[i] = replaceTypeVarsN(cl, n[i])
+
+proc replaceTypeVarsS(cl: var TReplTypeVars, s: PSym, t: PType): PSym =
+  if s == nil: return nil
+  # symbol is not our business:
+  if cl.owner != nil and s.owner != cl.owner:
+    return s
+
+  # XXX: Bound symbols in default parameter expressions may reach here.
+  # We cannot process them, because `sym.n` may point to a proc body with
+  # cyclic references that will lead to an infinite recursion.
+  # Perhaps we should not use a black-list here, but a whitelist instead
+  # (e.g. skGenericParam and skType).
+  # Note: `s.magic` may be `mType` in an example such as:
+  # proc foo[T](a: T, b = myDefault(type(a)))
+  if s.kind in routineKinds+{skLet, skConst, skVar} or s.magic != mNone:
+    return s
+
+  #result = PSym(idTableGet(cl.symMap, s))
+  #if result == nil:
+  #[
+
+  We cannot naively check for symbol recursions, because otherwise
+  object types A, B whould share their fields!
+
+      import tables
+
+      type
+        Table[S, T] = object
+          x: S
+          y: T
+
+        G[T] = object
+          inodes: Table[int, T] # A
+          rnodes: Table[T, int] # B
+
+      var g: G[string]
+
+  ]#
+  result = copySym(s, cl.c.idgen)
+  incl(result.flags, sfFromGeneric)
+  #idTablePut(cl.symMap, s, result)
+  result.owner = s.owner
+  result.typ = t
+  if result.kind != skType:
+    result.ast = replaceTypeVarsN(cl, s.ast)
+
+proc lookupTypeVar(cl: var TReplTypeVars, t: PType): PType =
+  if tfRetType in t.flags and t.kind == tyAnything:
+    # don't bind `auto` return type to a previous binding of `auto`
+    return nil
+  result = cl.typeMap.lookup(t)
+  if result == nil:
+    if cl.allowMetaTypes or tfRetType in t.flags: return
+    localError(cl.c.config, t.sym.info, "cannot instantiate: '" & typeToString(t) & "'")
+    result = errorType(cl.c)
+    # In order to prevent endless recursions, we must remember
+    # this bad lookup and replace it with errorType everywhere.
+    # These code paths are only active in "nim check"
+    cl.typeMap.put(t, result)
+  elif result.kind == tyGenericParam and not cl.allowMetaTypes:
+    internalError(cl.c.config, cl.info, "substitution with generic parameter")
+
+proc instCopyType*(cl: var TReplTypeVars, t: PType): PType =
+  # XXX: relying on allowMetaTypes is a kludge
+  if cl.allowMetaTypes:
+    result = t.exactReplica
+  else:
+    result = copyType(t, cl.c.idgen, t.owner)
+    copyTypeProps(cl.c.graph, cl.c.idgen.module, result, t)
+    #cl.typeMap.topLayer.idTablePut(result, t)
+
+  if cl.allowMetaTypes: return
+  result.flags.incl tfFromGeneric
+  if not (t.kind in tyMetaTypes or
+         (t.kind == tyStatic and t.n == nil)):
+    result.flags.excl tfInstClearedFlags
+  else:
+    result.flags.excl tfHasAsgn
+  when false:
+    if newDestructors:
+      result.assignment = nil
+      result.destructor = nil
+      result.sink = nil
+
+proc handleGenericInvocation(cl: var TReplTypeVars, t: PType): PType =
+  # tyGenericInvocation[A, tyGenericInvocation[A, B]]
+  # is difficult to handle:
+  var body = t.genericHead
+  if body.kind != tyGenericBody:
+    internalError(cl.c.config, cl.info, "no generic body")
+  var header = t
+  # search for some instantiation here:
+  if cl.allowMetaTypes:
+    result = getOrDefault(cl.localCache, t.itemId)
+  else:
+    result = searchInstTypes(cl.c.graph, t)
+
+  if result != nil and sameFlags(result, t):
+    when defined(reportCacheHits):
+      echo "Generic instantiation cached ", typeToString(result), " for ", typeToString(t)
+    return
+  for i in FirstGenericParamAt..<t.kidsLen:
+    var x = t[i]
+    if x.kind in {tyGenericParam}:
+      x = lookupTypeVar(cl, x)
+      if x != nil:
+        if header == t: header = instCopyType(cl, t)
+        header[i] = x
+        propagateToOwner(header, x)
+    else:
+      propagateToOwner(header, x)
+
+  if header != t:
+    # search again after first pass:
+    result = searchInstTypes(cl.c.graph, header)
+    if result != nil and sameFlags(result, t):
+      when defined(reportCacheHits):
+        echo "Generic instantiation cached ", typeToString(result), " for ",
+          typeToString(t), " header ", typeToString(header)
+      return
+  else:
+    header = instCopyType(cl, t)
+
+  result = newType(tyGenericInst, cl.c.idgen, t.genericHead.owner, son = header.genericHead)
+  result.flags = header.flags
+  # be careful not to propagate unnecessary flags here (don't use rawAddSon)
+  # ugh need another pass for deeply recursive generic types (e.g. PActor)
+  # we need to add the candidate here, before it's fully instantiated for
+  # recursive instantions:
+  if not cl.allowMetaTypes:
+    cacheTypeInst(cl.c, result)
+  else:
+    cl.localCache[t.itemId] = result
+
+  let oldSkipTypedesc = cl.skipTypedesc
+  cl.skipTypedesc = true
+
+  cl.typeMap = newTypeMapLayer(cl)
+
+  for i in FirstGenericParamAt..<t.kidsLen:
+    var x = replaceTypeVarsT(cl):
+      if header[i].kind == tyGenericInst:
+        t[i]
+      else:
+        header[i]
+    assert x.kind != tyGenericInvocation
+    header[i] = x
+    propagateToOwner(header, x)
+    cl.typeMap.put(body[i-1], x)
+
+  for i in FirstGenericParamAt..<t.kidsLen:
+    # if one of the params is not concrete, we cannot do anything
+    # but we already raised an error!
+    rawAddSon(result, header[i], propagateHasAsgn = false)
+
+  if body.kind == tyError:
+    return
+
+  let bbody = last body
+  var newbody = replaceTypeVarsT(cl, bbody)
+  cl.skipTypedesc = oldSkipTypedesc
+  newbody.flags = newbody.flags + (t.flags + body.flags - tfInstClearedFlags)
+  result.flags = result.flags + newbody.flags - tfInstClearedFlags
+
+  cl.typeMap = cl.typeMap.nextLayer
+
+  # This is actually wrong: tgeneric_closure fails with this line:
+  #newbody.callConv = body.callConv
+  # This type may be a generic alias and we want to resolve it here.
+  # One step is enough, because the recursive nature of
+  # handleGenericInvocation will handle the alias-to-alias-to-alias case
+  if newbody.isGenericAlias: newbody = newbody.skipGenericAlias
+
+  rawAddSon(result, newbody)
+  checkPartialConstructedType(cl.c.config, cl.info, newbody)
+  if not cl.allowMetaTypes:
+    let dc = cl.c.graph.getAttachedOp(newbody, attachedDeepCopy)
+    if dc != nil and sfFromGeneric notin dc.flags:
+      # 'deepCopy' needs to be instantiated for
+      # generics *when the type is constructed*:
+      cl.c.graph.setAttachedOp(cl.c.module.position, newbody, attachedDeepCopy,
+          cl.c.instTypeBoundOp(cl.c, dc, result, cl.info, attachedDeepCopy, 1))
+    if newbody.typeInst == nil:
+      # doAssert newbody.typeInst == nil
+      newbody.typeInst = result
+      if tfRefsAnonObj in newbody.flags and newbody.kind != tyGenericInst:
+        # can come here for tyGenericInst too, see tests/metatype/ttypeor.nim
+        # need to look into this issue later
+        assert newbody.kind in {tyRef, tyPtr}
+        if newbody.last.typeInst != nil:
+          #internalError(cl.c.config, cl.info, "ref already has a 'typeInst' field")
+          discard
+        else:
+          newbody.last.typeInst = result
+    # DESTROY: adding object|opt for opt[topttree.Tree]
+    # sigmatch: Formal opt[=destroy.T] real opt[topttree.Tree]
+    # adding myseq for myseq[system.int]
+    # sigmatch: Formal myseq[=destroy.T] real myseq[system.int]
+    #echo "DESTROY: adding ", typeToString(newbody), " for ", typeToString(result, preferDesc)
+    let mm = skipTypes(bbody, abstractPtrs)
+    if tfFromGeneric notin mm.flags:
+      # bug #5479, prevent endless recursions here:
+      incl mm.flags, tfFromGeneric
+      for col, meth in methodsForGeneric(cl.c.graph, mm):
+        # we instantiate the known methods belonging to that type, this causes
+        # them to be registered and that's enough, so we 'discard' the result.
+        discard cl.c.instTypeBoundOp(cl.c, meth, result, cl.info,
+          attachedAsgn, col)
+      excl mm.flags, tfFromGeneric
+
+proc eraseVoidParams*(t: PType) =
+  # transform '(): void' into '()' because old parts of the compiler really
+  # don't deal with '(): void':
+  if t.returnType != nil and t.returnType.kind == tyVoid:
+    t.setReturnType nil
+
+  for i in FirstParamAt..<t.signatureLen:
+    # don't touch any memory unless necessary
+    if t[i].kind == tyVoid:
+      var pos = i
+      for j in i+1..<t.signatureLen:
+        if t[j].kind != tyVoid:
+          t[pos] = t[j]
+          t.n[pos] = t.n[j]
+          inc pos
+      newSons t, pos
+      setLen t.n.sons, pos
+      break
+
+proc skipIntLiteralParams*(t: PType; idgen: IdGenerator) =
+  for i, p in t.ikids:
+    if p == nil: continue
+    let skipped = p.skipIntLit(idgen)
+    if skipped != p:
+      t[i] = skipped
+      if i > 0: t.n[i].sym.typ = skipped
+
+  # when the typeof operator is used on a static input
+  # param, the results gets infected with static as well:
+  if t.returnType != nil and t.returnType.kind == tyStatic:
+    t.setReturnType t.returnType.skipModifier
+
+proc propagateFieldFlags(t: PType, n: PNode) =
+  # This is meant for objects and tuples
+  # The type must be fully instantiated!
+  if n.isNil:
+    return
+  #internalAssert n.kind != nkRecWhen
+  case n.kind
+  of nkSym:
+    propagateToOwner(t, n.sym.typ)
+  of nkRecList, nkRecCase, nkOfBranch, nkElse:
+    for son in n:
+      propagateFieldFlags(t, son)
+  else: discard
+
+proc replaceTypeVarsTAux(cl: var TReplTypeVars, t: PType): PType =
+  template bailout =
+    if (t.sym == nil) or (t.sym != nil and sfGeneratedType in t.sym.flags):
+      # In the first case 't.sym' can be 'nil' if the type is a ref/ptr, see
+      # issue https://github.com/nim-lang/Nim/issues/20416 for more details.
+      # Fortunately for us this works for now because partial ref/ptr types are
+      # not allowed in object construction, eg.
+      #   type
+      #     Container[T] = ...
+      #     O = object
+      #      val: ref Container
+      #
+      # In the second case only consider the recursion limit if the symbol is a
+      # type with generic parameters that have not been explicitly supplied,
+      # typechecking should terminate when generic parameters are explicitly
+      # supplied.
+      if cl.recursionLimit > 100:
+        # bail out, see bug #2509. But note this caching is in general wrong,
+        # look at this example where TwoVectors should not share the generic
+        # instantiations (bug #3112):
+        # type
+        #   Vector[N: static[int]] = array[N, float64]
+        #   TwoVectors[Na, Nb: static[int]] = (Vector[Na], Vector[Nb])
+        result = getOrDefault(cl.localCache, t.itemId)
+        if result != nil: return result
+      inc cl.recursionLimit
+
+  result = t
+  if t == nil: return
+
+  const lookupMetas = {tyStatic, tyGenericParam, tyConcept} + tyTypeClasses - {tyAnything}
+  if t.kind in lookupMetas or
+      (t.kind == tyAnything and tfRetType notin t.flags):
+    let lookup = cl.typeMap.lookup(t)
+    if lookup != nil: return lookup
+
+  case t.kind
+  of tyGenericInvocation:
+    result = handleGenericInvocation(cl, t)
+    if result.last.kind == tyUserTypeClass:
+      result.kind = tyUserTypeClassInst
+
+  of tyGenericBody:
+    if cl.allowMetaTypes: return
+    localError(
+      cl.c.config,
+      cl.info,
+      "cannot instantiate: '" &
+      typeToString(t, preferDesc) &
+      "'; Maybe generic arguments are missing?")
+    result = errorType(cl.c)
+    #result = replaceTypeVarsT(cl, lastSon(t))
+
+  of tyFromExpr:
+    if cl.allowMetaTypes: return
+    # This assert is triggered when a tyFromExpr was created in a cyclic
+    # way. You should break the cycle at the point of creation by introducing
+    # a call such as: `n.typ = makeTypeFromExpr(c, n.copyTree)`
+    # Otherwise, the cycle will be fatal for the prepareNode call below
+    assert t.n.typ != t
+    var n = prepareNode(cl, t.n)
+    if n.kind != nkEmpty:
+      if tfNonConstExpr in t.flags:
+        n = cl.c.semExprWithType(cl.c, n, flags = {efInTypeof})
+      else:
+        n = cl.c.semConstExpr(cl.c, n)
+    if n.typ.kind == tyTypeDesc:
+      # XXX: sometimes, chained typedescs enter here.
+      # It may be worth investigating why this is happening,
+      # because it may cause other bugs elsewhere.
+      result = n.typ.skipTypes({tyTypeDesc})
+      # result = n.typ.base
+    elif tfNonConstExpr in t.flags:
+      result = n.typ
+    else:
+      if n.typ.kind != tyStatic and n.kind != nkType:
+        # XXX: In the future, semConstExpr should
+        # return tyStatic values to let anyone make
+        # use of this knowledge. The patching here
+        # won't be necessary then.
+        result = newTypeS(tyStatic, cl.c, son = n.typ)
+        result.n = n
+      else:
+        result = n.typ
+
+  of tyInt, tyFloat:
+    result = skipIntLit(t, cl.c.idgen)
+
+  of tyTypeDesc:
+    let lookup = cl.typeMap.lookup(t)
+    if lookup != nil:
+      result = lookup
+      if result.kind != tyTypeDesc:
+        result = makeTypeDesc(cl.c, result)
+      elif tfUnresolved in t.flags or cl.skipTypedesc:
+        result = result.base
+    elif t.elementType.kind != tyNone:
+      result = makeTypeDesc(cl.c, replaceTypeVarsT(cl, t.elementType))
+
+  of tyUserTypeClass:
+    result = t
+  
+  of tyStatic:
+    if cl.c.matchedConcept != nil:
+      # allow concepts to not instantiate statics for now
+      # they can't always infer them
+      return
+    if not containsGenericType(t) and (t.n == nil or t.n.kind in nkLiterals):
+      # no need to instantiate
+      return
+    bailout()
+    result = instCopyType(cl, t)
+    cl.localCache[t.itemId] = result
+    for i in FirstGenericParamAt..<result.kidsLen:
+      var r = result[i]
+      if r != nil:
+        r = replaceTypeVarsT(cl, r)
+        result[i] = r
+        propagateToOwner(result, r)
+    result.n = replaceTypeVarsN(cl, result.n)
+    if not cl.allowMetaTypes and result.n != nil and
+        result.base.kind != tyNone:
+      result.n = cl.c.semConstExpr(cl.c, result.n)
+      result.n.typ = result.base
+
+  of tyGenericInst, tyUserTypeClassInst:
+    bailout()
+    result = instCopyType(cl, t)
+    cl.localCache[t.itemId] = result
+    for i in FirstGenericParamAt..<result.kidsLen:
+      result[i] = replaceTypeVarsT(cl, result[i])
+    propagateToOwner(result, result.last)
+
+  else:
+    if containsGenericType(t):
+      #if not cl.allowMetaTypes:
+      bailout()
+      result = instCopyType(cl, t)
+      result.size = -1 # needs to be recomputed
+      #if not cl.allowMetaTypes:
+      cl.localCache[t.itemId] = result
+
+      for i, resulti in result.ikids:
+        if resulti != nil:
+          if resulti.kind == tyGenericBody and not cl.allowMetaTypes:
+            localError(cl.c.config, if t.sym != nil: t.sym.info else: cl.info,
+              "cannot instantiate '" &
+              typeToString(result[i], preferDesc) &
+              "' inside of type definition: '" &
+              t.owner.name.s & "'; Maybe generic arguments are missing?")
+          var r = replaceTypeVarsT(cl, resulti)
+          if result.kind == tyObject:
+            # carefully coded to not skip the precious tyGenericInst:
+            let r2 = r.skipTypes({tyAlias, tySink, tyOwned})
+            if r2.kind in {tyPtr, tyRef}:
+              r = skipTypes(r2, {tyPtr, tyRef})
+          result[i] = r
+          if result.kind != tyArray or i != 0:
+            propagateToOwner(result, r)
+      # bug #4677: Do not instantiate effect lists
+      result.n = replaceTypeVarsN(cl, result.n, ord(result.kind==tyProc))
+      case result.kind
+      of tyArray:
+        let idx = result.indexType
+        internalAssert cl.c.config, idx.kind != tyStatic
+
+      of tyObject, tyTuple:
+        propagateFieldFlags(result, result.n)
+        if result.kind == tyObject and cl.c.computeRequiresInit(cl.c, result):
+          result.flags.incl tfRequiresInit
+
+      of tyProc:
+        eraseVoidParams(result)
+        skipIntLiteralParams(result, cl.c.idgen)
+
+      of tyRange:
+        result.setIndexType result.indexType.skipTypes({tyStatic, tyDistinct})
+
+      else: discard
+    else:
+      # If this type doesn't refer to a generic type we may still want to run it
+      # trough replaceObjBranches in order to resolve any pending nkRecWhen nodes
+      result = t
+
+      # Slow path, we have some work to do
+      if t.kind == tyRef and t.hasElementType and t.elementType.kind == tyObject and t.elementType.n != nil:
+        discard replaceObjBranches(cl, t.elementType.n)
+
+      elif result.n != nil and t.kind == tyObject:
+        # Invalidate the type size as we may alter its structure
+        result.size = -1
+        result.n = replaceObjBranches(cl, result.n)
+
+proc initTypeVars*(p: PContext, typeMap: LayeredIdTable, info: TLineInfo;
+                   owner: PSym): TReplTypeVars =
+  result = TReplTypeVars(symMap: initSymMapping(),
+            localCache: initTypeMapping(), typeMap: typeMap,
+            info: info, c: p, owner: owner)
+
+proc replaceTypesInBody*(p: PContext, pt: TypeMapping, n: PNode;
+                         owner: PSym, allowMetaTypes = false,
+                         fromStaticExpr = false, expectedType: PType = nil): PNode =
+  var typeMap = initLayeredTypeMap(pt)
+  var cl = initTypeVars(p, typeMap, n.info, owner)
+  cl.allowMetaTypes = allowMetaTypes
+  pushInfoContext(p.config, n.info)
+  result = replaceTypeVarsN(cl, n, expectedType = expectedType)
+  popInfoContext(p.config)
+
+proc prepareTypesInBody*(p: PContext, pt: TypeMapping, n: PNode;
+                         owner: PSym = nil): PNode =
+  var typeMap = initLayeredTypeMap(pt)
+  var cl = initTypeVars(p, typeMap, n.info, owner)
+  pushInfoContext(p.config, n.info)
+  result = prepareNode(cl, n)
+  popInfoContext(p.config)
+
+when false:
+  # deadcode
+  proc replaceTypesForLambda*(p: PContext, pt: TIdTable, n: PNode;
+                              original, new: PSym): PNode =
+    var typeMap = initLayeredTypeMap(pt)
+    var cl = initTypeVars(p, typeMap, n.info, original)
+    idTablePut(cl.symMap, original, new)
+    pushInfoContext(p.config, n.info)
+    result = replaceTypeVarsN(cl, n)
+    popInfoContext(p.config)
+
+proc recomputeFieldPositions*(t: PType; obj: PNode; currPosition: var int) =
+  if t != nil and t.baseClass != nil:
+    let b = skipTypes(t.baseClass, skipPtrs)
+    recomputeFieldPositions(b, b.n, currPosition)
+  case obj.kind
+  of nkRecList:
+    for i in 0..<obj.len: recomputeFieldPositions(nil, obj[i], currPosition)
+  of nkRecCase:
+    recomputeFieldPositions(nil, obj[0], currPosition)
+    for i in 1..<obj.len:
+      recomputeFieldPositions(nil, lastSon(obj[i]), currPosition)
+  of nkSym:
+    obj.sym.position = currPosition
+    inc currPosition
+  else: discard "cannot happen"
+
+proc generateTypeInstance*(p: PContext, pt: TypeMapping, info: TLineInfo,
+                           t: PType): PType =
+  # Given `t` like Foo[T]
+  # pt: Table with type mappings: T -> int
+  # Desired result: Foo[int]
+  # proc (x: T = 0); T -> int ---->  proc (x: int = 0)
+  var typeMap = initLayeredTypeMap(pt)
+  var cl = initTypeVars(p, typeMap, info, nil)
+  pushInfoContext(p.config, info)
+  result = replaceTypeVarsT(cl, t)
+  popInfoContext(p.config)
+  let objType = result.skipTypes(abstractInst)
+  if objType.kind == tyObject:
+    var position = 0
+    recomputeFieldPositions(objType, objType.n, position)
+
+proc prepareMetatypeForSigmatch*(p: PContext, pt: TypeMapping, info: TLineInfo,
+                                 t: PType): PType =
+  var typeMap = initLayeredTypeMap(pt)
+  var cl = initTypeVars(p, typeMap, info, nil)
+  cl.allowMetaTypes = true
+  pushInfoContext(p.config, info)
+  result = replaceTypeVarsT(cl, t)
+  popInfoContext(p.config)
+
+template generateTypeInstance*(p: PContext, pt: TypeMapping, arg: PNode,
+                               t: PType): untyped =
+  generateTypeInstance(p, pt, arg.info, t)