diff options
Diffstat (limited to 'compiler/semtypinst.nim')
| -rw-r--r-- | compiler/semtypinst.nim | 834 |
1 files changed, 550 insertions, 284 deletions
diff --git a/compiler/semtypinst.nim b/compiler/semtypinst.nim index 0f49398f2..759e8e6ab 100644 --- a/compiler/semtypinst.nim +++ b/compiler/semtypinst.nim @@ -9,110 +9,104 @@ # This module does the instantiation of generic types. -import ast, astalgo, msgs, types, magicsys, semdata, renderer, options +import std / tables -const - tfInstClearedFlags = {tfHasMeta, tfUnresolved} +import ast, astalgo, msgs, types, magicsys, semdata, renderer, options, + lineinfos, modulegraphs -proc checkPartialConstructedType(info: TLineInfo, t: PType) = - if tfAcyclic in t.flags and skipTypes(t, abstractInst).kind != tyObject: - localError(info, errInvalidPragmaX, "acyclic") - elif t.kind == tyVar and t.sons[0].kind == tyVar: - localError(info, errVarVarTypeNotAllowed) +when defined(nimPreviewSlimSystem): + import std/assertions -proc checkConstructedType*(info: TLineInfo, typ: PType) = - var t = typ.skipTypes({tyDistinct}) - if t.kind in tyTypeClasses: discard - elif tfAcyclic in t.flags and skipTypes(t, abstractInst).kind != tyObject: - localError(info, errInvalidPragmaX, "acyclic") - elif t.kind == tyVar and t.sons[0].kind == tyVar: - localError(info, errVarVarTypeNotAllowed) - elif computeSize(t) == szIllegalRecursion: - localError(info, errIllegalRecursionInTypeX, typeToString(t)) - when false: - if t.kind == tyObject and t.sons[0] != nil: - if t.sons[0].kind != tyObject or tfFinal in t.sons[0].flags: - localError(info, errInheritanceOnlyWithNonFinalObjects) +const tfInstClearedFlags = {tfHasMeta, tfUnresolved} -proc searchInstTypes*(key: PType): PType = - let genericTyp = key.sons[0] - internalAssert genericTyp.kind == tyGenericBody and - key.sons[0] == genericTyp and - genericTyp.sym != nil - - if genericTyp.sym.typeInstCache == nil: - return +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") - for inst in genericTyp.sym.typeInstCache: +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.sons.len < key.sons.len: + if inst.kidsLen < key.kidsLen: # XXX: This happens for prematurely cached # types such as Channel[empty]. Why? # See the notes for PActor in handleGenericInvocation - return + # 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 1 .. high(key.sons): + for j in FirstGenericParamAt..<key.kidsLen: # XXX sameType is not really correct for nested generics? - if not compareTypes(inst.sons[j], key.sons[j], - flags = {ExactGenericParams}): + if not compareTypes(inst[j], key[j], + flags = {ExactGenericParams, PickyCAliases}): break matchType return inst -proc cacheTypeInst*(inst: PType) = - # XXX: add to module's generics - # update the refcount - let gt = inst.sons[0] - let t = if gt.kind == tyGenericBody: gt.lastSon else: gt - if t.kind in {tyStatic, tyGenericParam} + tyTypeClasses: +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 - gt.sym.typeInstCache.safeAdd(inst) - + addToGenericCache(c, gt.sym, inst) type - LayeredIdTable* = object - topLayer*: TIdTable - nextLayer*: ptr LayeredIdTable + LayeredIdTable* {.acyclic.} = ref object + topLayer*: TypeMapping + nextLayer*: LayeredIdTable TReplTypeVars* = object c*: PContext - typeMap*: ptr LayeredIdTable # map PType to PType - symMap*: TIdTable # map PSym to PSym - localCache*: TIdTable # local cache for remembering alraedy replaced + 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 # wether we should skip typeDescs + 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): PSym -proc replaceTypeVarsN*(cl: var TReplTypeVars, n: PNode; start=0): PNode +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: TIdTable): LayeredIdTable = - copyIdTable(result.topLayer, pt) +proc initLayeredTypeMap*(pt: sink TypeMapping): LayeredIdTable = + result = LayeredIdTable() + result.topLayer = pt proc newTypeMapLayer*(cl: var TReplTypeVars): LayeredIdTable = - result.nextLayer = cl.typeMap - initIdTable(result.topLayer) + result = LayeredIdTable(nextLayer: cl.typeMap, topLayer: initTable[ItemId, PType]()) -proc lookup(typeMap: ptr LayeredIdTable, key: PType): PType = +proc lookup(typeMap: LayeredIdTable, key: PType): PType = + result = nil var tm = typeMap while tm != nil: - result = PType(idTableGet(tm.topLayer, key)) + result = getOrDefault(tm.topLayer, key.itemId) if result != nil: return tm = tm.nextLayer -template put(typeMap: ptr LayeredIdTable, key, value: PType) = - idTablePut(typeMap.topLayer, key, value) +template put(typeMap: LayeredIdTable, key, value: PType) = + typeMap.topLayer[key.itemId] = value -template checkMetaInvariants(cl: TReplTypeVars, t: PType) = +template checkMetaInvariants(cl: TReplTypeVars, t: PType) = # noop code when false: if t != nil and tfHasMeta in t.flags and cl.allowMetaTypes == false: @@ -124,19 +118,86 @@ proc replaceTypeVarsT*(cl: var TReplTypeVars, t: PType): PType = result = replaceTypeVarsTAux(cl, t) checkMetaInvariants(cl, result) -proc prepareNode(cl: var TReplTypeVars, n: PNode): PNode = +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 = replaceTypeVarsS(cl, n.sym) - let isCall = result.kind in nkCallKinds - for i in 0 .. <n.safeLen: - # XXX HACK: ``f(a, b)``, avoid to instantiate `f` - if isCall and i == 0: result.add(n[i]) - else: result.add(prepareNode(cl, n[i])) + 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 @@ -144,200 +205,297 @@ proc isTypeParam(n: PNode): bool = (n.sym.kind == skGenericParam or (n.sym.kind == skType and sfFromGeneric in n.sym.flags)) -proc hasGenericArguments*(n: PNode): bool = - if n.kind == nkSym: - return n.sym.kind == skGenericParam or - tfInferrableStatic in n.sym.typ.flags or - (n.sym.kind == skType and - n.sym.typ.flags * {tfGenericTypeParam, tfImplicitTypeParam} != {}) +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.safeLen: - if hasGenericArguments(n.sons[i]): return true - return false - -proc reResolveCallsWithTypedescParams(cl: var TReplTypeVars, n: PNode): PNode = - # This is needed for tgenericshardcases - # 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.sons[0] = newSymNode(n.sons[0].sym.owner) - return cl.c.semOverloadedCall(cl.c, n, n, {skProc, skFunc}, {}) - - for i in 0 .. <n.safeLen: - n.sons[i] = reResolveCallsWithTypedescParams(cl, n[i]) - - return n - -proc replaceTypeVarsN(cl: var TReplTypeVars, n: PNode; start=0): PNode = + 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 = replaceTypeVarsS(cl, n.sym) - if result.sym.typ.kind == tyVoid: + 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 = newNode(nkRecList, n.info) + result = newNodeI(nkRecList, n.info) of nkRecWhen: var branch: PNode = nil # the branch to take - for i in countup(0, sonsLen(n) - 1): - var it = n.sons[i] - if it == nil: illFormedAst(n) + 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) - var cond = prepareNode(cl, it.sons[0]) - var e = cl.c.semConstExpr(cl.c, cond) - if e.kind != nkIntLit: - internalError(e.info, "ReplaceTypeVarsN: when condition not a bool") - if e.intVal != 0 and branch == nil: branch = it.sons[1] + 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) - if branch == nil: branch = it.sons[0] - else: illFormedAst(n) + 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) - n = reResolveCallsWithTypedescParams(cl, n) + when false: + n = reResolveCallsWithTypedescParams(cl, n) result = if cl.allowMetaTypes: n - else: cl.c.semExpr(cl.c, n) + else: cl.c.semExpr(cl.c, n, {}, expectedType) + if not cl.allowMetaTypes and expectedType != nil: + assert result.kind notin nkCallKinds else: - var length = sonsLen(n) - if length > 0: - newSons(result, length) + if n.len > 0: + newSons(result, n.len) if start > 0: - result.sons[0] = n.sons[0] - for i in countup(start, length - 1): - result.sons[i] = replaceTypeVarsN(cl, n.sons[i]) + result[0] = n[0] + for i in start..<n.len: + result[i] = replaceTypeVarsN(cl, n[i]) -proc replaceTypeVarsS(cl: var TReplTypeVars, s: PSym): PSym = +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: - result = copySym(s, false) + #[ + + 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 = replaceTypeVarsT(cl, s.typ) - result.ast = replaceTypeVarsN(cl, s.ast) + 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(t.sym.info, errCannotInstantiateX, typeToString(t)) + 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.info, "substitution with generic parameter") + 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 - result = copyType(t, t.owner, cl.allowMetaTypes) + 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.destructor = nil result.sink = nil -template typeBound(c, newty, oldty, field, info) = - let opr = newty.field - if opr != nil and sfFromGeneric notin opr.flags: - # '=' needs to be instantiated for generics when the type is constructed: - newty.field = c.instTypeBoundOp(c, opr, oldty, info, attachedAsgn, 1) - proc handleGenericInvocation(cl: var TReplTypeVars, t: PType): PType = # tyGenericInvocation[A, tyGenericInvocation[A, B]] # is difficult to handle: - const eqFlags = eqTypeFlags + {tfGcSafe} - var body = t.sons[0] - if body.kind != tyGenericBody: internalError(cl.info, "no generic body") - var header: PType = t + 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 = PType(idTableGet(cl.localCache, t)) + result = getOrDefault(cl.localCache, t.itemId) else: - result = searchInstTypes(t) + result = searchInstTypes(cl.c.graph, t) - if result != nil and eqFlags*result.flags == eqFlags*t.flags: return - for i in countup(1, sonsLen(t) - 1): - var x = t.sons[i] + 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.sons[i] = x + header[i] = x propagateToOwner(header, x) else: propagateToOwner(header, x) if header != t: # search again after first pass: - result = searchInstTypes(header) - if result != nil and eqFlags*result.flags == eqFlags*t.flags: return + 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, t.sons[0].owner) + 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) - result.sons = @[header.sons[0]] # 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(result) + cacheTypeInst(cl.c, result) else: - idTablePut(cl.localCache, t, result) + cl.localCache[t.itemId] = result let oldSkipTypedesc = cl.skipTypedesc cl.skipTypedesc = true - var typeMapLayer = newTypeMapLayer(cl) - cl.typeMap = addr(typeMapLayer) + cl.typeMap = newTypeMapLayer(cl) - for i in countup(1, sonsLen(t) - 1): - var x = replaceTypeVarsT(cl, t.sons[i]) + 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.sons[i] = x + header[i] = x propagateToOwner(header, x) - cl.typeMap.put(body.sons[i-1], x) + cl.typeMap.put(body[i-1], x) - for i in countup(1, sonsLen(t) - 1): + 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.sons[i]) + rawAddSon(result, header[i], propagateHasAsgn = false) - let bbody = lastSon body + if body.kind == tyError: + return + + let bbody = last body var newbody = replaceTypeVarsT(cl, bbody) - let bodyIsNew = newbody != bbody cl.skipTypedesc = oldSkipTypedesc newbody.flags = newbody.flags + (t.flags + body.flags - tfInstClearedFlags) result.flags = result.flags + newbody.flags - tfInstClearedFlags @@ -350,74 +508,82 @@ proc handleGenericInvocation(cl: var TReplTypeVars, t: PType): PType = # 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.info, newbody) - let dc = newbody.deepCopy - if cl.allowMetaTypes == false: - if dc != nil and sfFromGeneric notin newbody.deepCopy.flags: + 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*: - newbody.deepCopy = cl.c.instTypeBoundOp(cl.c, dc, result, cl.info, - attachedDeepCopy, 1) - if bodyIsNew and newbody.typeInst == nil: - #doassert newbody.typeInst == nil + 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} - assert newbody.lastSon.typeInst == nil - newbody.lastSon.typeInst = result - if newDestructors: - cl.c.typesWithOps.add((newbody, result)) - else: - typeBound(cl.c, newbody, result, assignment, cl.info) - let methods = skipTypes(bbody, abstractPtrs).methods - for col, meth in items(methods): - # 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) + 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.sons[0] != nil and t.sons[0].kind == tyVoid: - t.sons[0] = nil + if t.returnType != nil and t.returnType.kind == tyVoid: + t.setReturnType nil - for i in 1 .. <t.sonsLen: + for i in FirstParamAt..<t.signatureLen: # don't touch any memory unless necessary - if t.sons[i].kind == tyVoid: + if t[i].kind == tyVoid: var pos = i - for j in i+1 .. <t.sonsLen: - if t.sons[j].kind != tyVoid: - t.sons[pos] = t.sons[j] - t.n.sons[pos] = t.n.sons[j] + for j in i+1..<t.signatureLen: + if t[j].kind != tyVoid: + t[pos] = t[j] + t.n[pos] = t.n[j] inc pos - setLen t.sons, pos + newSons t, pos setLen t.n.sons, pos - return + break -proc skipIntLiteralParams*(t: PType) = - for i in 0 .. <t.sonsLen: - let p = t.sons[i] +proc skipIntLiteralParams*(t: PType; idgen: IdGenerator) = + for i, p in t.ikids: if p == nil: continue - let skipped = p.skipIntLit + let skipped = p.skipIntLit(idgen) if skipped != p: - t.sons[i] = skipped - if i > 0: t.n.sons[i].sym.typ = skipped + 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.sons[0] != nil and t.sons[0].kind == tyStatic: - t.sons[0] = t.sons[0].base + 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 + #internalAssert n.kind != nkRecWhen case n.kind of nkSym: propagateToOwner(t, n.sym.typ) @@ -428,81 +594,136 @@ proc propagateFieldFlags(t: PType, n: PNode) = proc replaceTypeVarsTAux(cl: var TReplTypeVars, t: PType): PType = template bailout = - 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 = PType(idTableGet(cl.localCache, t)) - if result != nil: return result - inc cl.recursionLimit + 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 - if t.kind in {tyStatic, tyGenericParam} + tyTypeClasses: + 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.lastSon.kind == tyUserTypeClass: + if result.last.kind == tyUserTypeClass: result.kind = tyUserTypeClassInst of tyGenericBody: - localError(cl.info, errCannotInstantiateX, typeToString(t)) + 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: - n = cl.c.semConstExpr(cl.c, n) + 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: + 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) - result.sons = @[n.typ] + result = newTypeS(tyStatic, cl.c, son = n.typ) result.n = n else: result = n.typ of tyInt, tyFloat: - result = skipIntLit(t) + result = skipIntLit(t, cl.c.idgen) of tyTypeDesc: let lookup = cl.typeMap.lookup(t) if lookup != nil: result = lookup - if tfUnresolved in t.flags or cl.skipTypedesc: result = result.base - elif t.sons[0].kind != tyNone: - result = makeTypeDesc(cl.c, replaceTypeVarsT(cl, t.sons[0])) - - of tyUserTypeClass, tyStatic: + 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) - idTablePut(cl.localCache, t, result) - for i in 1 .. <result.sonsLen: - result.sons[i] = replaceTypeVarsT(cl, result.sons[i]) - propagateToOwner(result, result.lastSon) + 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): @@ -511,90 +732,135 @@ proc replaceTypeVarsTAux(cl: var TReplTypeVars, t: PType): PType = result = instCopyType(cl, t) result.size = -1 # needs to be recomputed #if not cl.allowMetaTypes: - idTablePut(cl.localCache, t, result) - - for i in countup(0, sonsLen(result) - 1): - if result.sons[i] != nil: - var r = replaceTypeVarsT(cl, result.sons[i]) + 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}) + let r2 = r.skipTypes({tyAlias, tySink, tyOwned}) if r2.kind in {tyPtr, tyRef}: r = skipTypes(r2, {tyPtr, tyRef}) - result.sons[i] = r - propagateToOwner(result, r) + 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.sons[0] - internalAssert idx.kind != tyStatic + 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) + 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) -proc instAllTypeBoundOp*(c: PContext, info: TLineInfo) = - if not newDestructors: return - var i = 0 - while i < c.typesWithOps.len: - let (newty, oldty) = c.typesWithOps[i] - typeBound(c, newty, oldty, destructor, info) - typeBound(c, newty, oldty, sink, info) - typeBound(c, newty, oldty, assignment, info) - inc i - setLen(c.typesWithOps, 0) - -proc initTypeVars*(p: PContext, typeMap: ptr LayeredIdTable, info: TLineInfo; + 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 = - initIdTable(result.symMap) - initIdTable(result.localCache) - result.typeMap = typeMap - result.info = info - result.c = p - result.owner = owner - -proc replaceTypesInBody*(p: PContext, pt: TIdTable, n: PNode; - owner: PSym, allowMetaTypes = false): PNode = + 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, addr(typeMap), n.info, owner) + var cl = initTypeVars(p, typeMap, n.info, owner) cl.allowMetaTypes = allowMetaTypes - pushInfoContext(n.info) - result = replaceTypeVarsN(cl, n) - popInfoContext() + pushInfoContext(p.config, n.info) + result = replaceTypeVarsN(cl, n, expectedType = expectedType) + popInfoContext(p.config) -proc replaceTypesForLambda*(p: PContext, pt: TIdTable, n: PNode; - original, new: PSym): PNode = +proc prepareTypesInBody*(p: PContext, pt: TypeMapping, n: PNode; + owner: PSym = nil): PNode = var typeMap = initLayeredTypeMap(pt) - var cl = initTypeVars(p, addr(typeMap), n.info, original) - idTablePut(cl.symMap, original, new) - pushInfoContext(n.info) - result = replaceTypeVarsN(cl, n) - popInfoContext() + 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: TIdTable, info: TLineInfo, +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, addr(typeMap), info, nil) - pushInfoContext(info) + var cl = initTypeVars(p, typeMap, info, nil) + pushInfoContext(p.config, info) result = replaceTypeVarsT(cl, t) - popInfoContext() + 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: TIdTable, info: TLineInfo, +proc prepareMetatypeForSigmatch*(p: PContext, pt: TypeMapping, info: TLineInfo, t: PType): PType = var typeMap = initLayeredTypeMap(pt) - var cl = initTypeVars(p, addr(typeMap), info, nil) + var cl = initTypeVars(p, typeMap, info, nil) cl.allowMetaTypes = true - pushInfoContext(info) + pushInfoContext(p.config, info) result = replaceTypeVarsT(cl, t) - popInfoContext() + popInfoContext(p.config) -template generateTypeInstance*(p: PContext, pt: TIdTable, arg: PNode, +template generateTypeInstance*(p: PContext, pt: TypeMapping, arg: PNode, t: PType): untyped = generateTypeInstance(p, pt, arg.info, t) - |