diff options
Diffstat (limited to 'compiler/sigmatch.nim')
| -rw-r--r-- | compiler/sigmatch.nim | 2496 |
1 files changed, 1594 insertions, 902 deletions
diff --git a/compiler/sigmatch.nim b/compiler/sigmatch.nim index 9a3c75261..6ea2c7bb5 100644 --- a/compiler/sigmatch.nim +++ b/compiler/sigmatch.nim @@ -11,20 +11,33 @@ ## the call to overloaded procs, generic procs and operators. import - intsets, ast, astalgo, semdata, types, msgs, renderer, lookups, semtypinst, - magicsys, condsyms, idents, lexer, options, parampatterns, strutils, trees, - linter, lineinfos + ast, astalgo, semdata, types, msgs, renderer, lookups, semtypinst, + magicsys, idents, lexer, options, parampatterns, trees, + linter, lineinfos, lowerings, modulegraphs, concepts -when defined(booting) or defined(nimsuggest): - import docgen +import std/[intsets, strutils, tables] + +when defined(nimPreviewSlimSystem): + import std/assertions type + MismatchKind* = enum + kUnknown, kAlreadyGiven, kUnknownNamedParam, kTypeMismatch, kVarNeeded, + kMissingParam, kExtraArg, kPositionalAlreadyGiven, + kGenericParamTypeMismatch, kMissingGenericParam, kExtraGenericParam + + MismatchInfo* = object + kind*: MismatchKind # reason for mismatch + arg*: int # position of provided arguments that mismatches + formal*: PSym # parameter that mismatches against provided argument + # its position can differ from `arg` because of varargs + TCandidateState* = enum csEmpty, csMatch, csNoMatch CandidateError* = object sym*: PSym - unmatchedVarParam*, firstMismatch*: int + firstMismatch*: MismatchInfo diagnostics*: seq[string] enabled*: bool @@ -43,12 +56,12 @@ type calleeScope*: int # scope depth: # is this a top-level symbol or a nested proc? call*: PNode # modified call - bindings*: TIdTable # maps types to types + bindings*: TypeMapping # maps types to types magic*: TMagic # magic of operation baseTypeMatch: bool # needed for conversions from T to openarray[T] # for example - fauxMatch*: TTypeKind # the match was successful only due to the use - # of error or wildcard (unknown) types. + matchedErrorType*: bool # match is considered successful after matching + # error type to avoid cascading errors # this is used to prevent instantiations. genericConverter*: bool # true if a generic converter needs to # be instantiated @@ -56,7 +69,6 @@ type # a distrinct type typedescMatched*: bool isNoCall*: bool # misused for generic type instantiations C[T] - mutabilityProblem*: uint8 # tyVar mismatch inferredTypes: seq[PType] # inferred types during the current signature # matching. they will be reset if the matching # is not successful. may replace the bindings @@ -69,171 +81,290 @@ type # or when the explain pragma is used. may be # triggered with an idetools command in the # future. - inheritancePenalty: int # to prefer closest father object type - firstMismatch*: int # position of the first type mismatch for - # better error messages + # to prefer closest father object type + inheritancePenalty: int + firstMismatch*: MismatchInfo # mismatch info for better error messages diagnosticsEnabled*: bool TTypeRelFlag* = enum trDontBind trNoCovariance + trBindGenericParam # bind tyGenericParam even with trDontBind + trIsOutParam TTypeRelFlags* = set[TTypeRelFlag] - TTypeRelation* = enum # order is important! - isNone, isConvertible, - isIntConv, - isSubtype, - isSubrange, # subrange of the wanted type; no type conversion - # but apart from that counts as ``isSubtype`` - isBothMetaConvertible # generic proc parameter was matched against - # generic type, e.g., map(mySeq, x=>x+1), - # maybe recoverable by rerun if the parameter is - # the proc's return value - isInferred, # generic proc was matched against a concrete type - isInferredConvertible, # same as above, but requiring proc CC conversion - isGeneric, - isFromIntLit, # conversion *from* int literal; proven safe - isEqual const isNilConversion = isConvertible # maybe 'isIntConv' fits better? + maxInheritancePenalty = high(int) div 2 -proc markUsed*(conf: ConfigRef; info: TLineInfo, s: PSym; usageSym: var PSym) - -template hasFauxMatch*(c: TCandidate): bool = c.fauxMatch != tyNone +proc markUsed*(c: PContext; info: TLineInfo, s: PSym; checkStyle = true) +proc markOwnerModuleAsUsed*(c: PContext; s: PSym) proc initCandidateAux(ctx: PContext, - c: var TCandidate, callee: PType) {.inline.} = - c.c = ctx - c.exactMatches = 0 - c.subtypeMatches = 0 - c.convMatches = 0 - c.intConvMatches = 0 - c.genericMatches = 0 - c.state = csEmpty - c.callee = callee - c.call = nil - c.baseTypeMatch = false - c.genericConverter = false - c.inheritancePenalty = 0 - -proc initCandidate*(ctx: PContext, c: var TCandidate, callee: PType) = - initCandidateAux(ctx, c, callee) - c.calleeSym = nil - initIdTable(c.bindings) + callee: PType): TCandidate {.inline.} = + result = TCandidate(c: ctx, exactMatches: 0, subtypeMatches: 0, + convMatches: 0, intConvMatches: 0, genericMatches: 0, + state: csEmpty, firstMismatch: MismatchInfo(), + callee: callee, call: nil, baseTypeMatch: false, + genericConverter: false, inheritancePenalty: -1 + ) + +proc initCandidate*(ctx: PContext, callee: PType): TCandidate = + result = initCandidateAux(ctx, callee) + result.calleeSym = nil + result.bindings = initTypeMapping() proc put(c: var TCandidate, key, val: PType) {.inline.} = - idTablePut(c.bindings, key, val.skipIntLit) + ## Given: proc foo[T](x: T); foo(4) + ## key: 'T' + ## val: 'int' (typeof(4)) + when false: + let old = idTableGet(c.bindings, key) + if old != nil: + echo "Putting ", typeToString(key), " ", typeToString(val), " and old is ", typeToString(old) + if typeToString(old) == "float32": + writeStackTrace() + if c.c.module.name.s == "temp3": + echo "binding ", key, " -> ", val + idTablePut(c.bindings, key, val.skipIntLit(c.c.idgen)) + +proc typeRel*(c: var TCandidate, f, aOrig: PType, + flags: TTypeRelFlags = {}): TTypeRelation + +proc matchGenericParam(m: var TCandidate, formal: PType, n: PNode) = + var arg = n.typ + if m.c.inGenericContext > 0: + # don't match yet-unresolved generic instantiations + while arg != nil and arg.kind == tyGenericParam: + arg = idTableGet(m.bindings, arg) + if arg == nil or arg.containsUnresolvedType: + m.state = csNoMatch + return + # fix up the type to get ready to match formal: + var formalBase = formal + while formalBase.kind == tyGenericParam and + formalBase.genericParamHasConstraints: + formalBase = formalBase.genericConstraint + if formalBase.kind == tyStatic and arg.kind != tyStatic: + # maybe call `paramTypesMatch` here, for now be conservative + if n.kind in nkSymChoices: n.flags.excl nfSem + let evaluated = m.c.semTryConstExpr(m.c, n, formalBase.skipTypes({tyStatic})) + if evaluated != nil: + arg = newTypeS(tyStatic, m.c, son = evaluated.typ) + arg.n = evaluated + elif formalBase.kind == tyTypeDesc: + if arg.kind != tyTypeDesc: + arg = makeTypeDesc(m.c, arg) + else: + arg = arg.skipTypes({tyTypeDesc}) + let tm = typeRel(m, formal, arg) + if tm in {isNone, isConvertible}: + m.state = csNoMatch + m.firstMismatch.kind = kGenericParamTypeMismatch + return -proc initCandidate*(ctx: PContext, c: var TCandidate, callee: PSym, +proc matchGenericParams*(m: var TCandidate, binding: PNode, callee: PSym) = + ## matches explicit generic instantiation `binding` against generic params of + ## proc symbol `callee` + ## state is set to `csMatch` if all generic params match, `csEmpty` if + ## implicit generic parameters are missing (matches but cannot instantiate), + ## `csNoMatch` if a constraint fails or param count doesn't match + let c = m.c + let typeParams = callee.ast[genericParamsPos] + let paramCount = typeParams.len + let bindingCount = binding.len-1 + if bindingCount > paramCount: + m.state = csNoMatch + m.firstMismatch.kind = kExtraGenericParam + m.firstMismatch.arg = paramCount + 1 + return + for i in 1..bindingCount: + matchGenericParam(m, typeParams[i-1].typ, binding[i]) + if m.state == csNoMatch: + m.firstMismatch.arg = i + m.firstMismatch.formal = typeParams[i-1].sym + return + # not enough generic params given, check if remaining have defaults: + for i in bindingCount ..< paramCount: + let param = typeParams[i] + assert param.kind == nkSym + let paramSym = param.sym + if paramSym.ast != nil: + matchGenericParam(m, param.typ, paramSym.ast) + if m.state == csNoMatch: + m.firstMismatch.arg = i + 1 + m.firstMismatch.formal = paramSym + return + elif tfImplicitTypeParam in paramSym.typ.flags: + # not a mismatch, but can't create sym + m.state = csEmpty + return + else: + m.state = csNoMatch + m.firstMismatch.kind = kMissingGenericParam + m.firstMismatch.arg = i + 1 + m.firstMismatch.formal = paramSym + return + m.state = csMatch + +proc copyingEraseVoidParams(m: TCandidate, t: var PType) = + ## if `t` is a proc type with void parameters, copies it and erases them + assert t.kind == tyProc + let original = t + var copied = false + for i in 1 ..< original.len: + var f = original[i] + var isVoidParam = f.kind == tyVoid + if not isVoidParam: + let prev = idTableGet(m.bindings, f) + if prev != nil: f = prev + isVoidParam = f.kind == tyVoid + if isVoidParam: + if not copied: + # keep first i children + t = copyType(original, m.c.idgen, t.owner) + t.setSonsLen(i) + t.n = copyNode(original.n) + t.n.sons = original.n.sons + t.n.sons.setLen(i) + copied = true + elif copied: + t.add(f) + t.n.add(original.n[i]) + +proc initCandidate*(ctx: PContext, callee: PSym, binding: PNode, calleeScope = -1, - diagnosticsEnabled = false) = - initCandidateAux(ctx, c, callee.typ) - c.calleeSym = callee + diagnosticsEnabled = false): TCandidate = + result = initCandidateAux(ctx, callee.typ) + result.calleeSym = callee if callee.kind in skProcKinds and calleeScope == -1: - if callee.originatingModule == ctx.module: - c.calleeScope = 2 - var owner = callee - while true: - owner = owner.skipGenericOwner - if owner.kind == skModule: break - inc c.calleeScope - else: - c.calleeScope = 1 + result.calleeScope = cmpScopes(ctx, callee) else: - c.calleeScope = calleeScope - c.diagnostics = if diagnosticsEnabled: @[] else: nil - c.diagnosticsEnabled = diagnosticsEnabled - c.magic = c.calleeSym.magic - initIdTable(c.bindings) + result.calleeScope = calleeScope + result.diagnostics = @[] # if diagnosticsEnabled: @[] else: nil + result.diagnosticsEnabled = diagnosticsEnabled + result.magic = result.calleeSym.magic + result.bindings = initTypeMapping() if binding != nil and callee.kind in routineKinds: - var typeParams = callee.ast[genericParamsPos] - for i in 1..min(sonsLen(typeParams), sonsLen(binding)-1): - var formalTypeParam = typeParams.sons[i-1].typ - var bound = binding[i].typ - if bound != nil: - if formalTypeParam.kind == tyTypeDesc: - if bound.kind != tyTypeDesc: - bound = makeTypeDesc(ctx, bound) - else: - bound = bound.skipTypes({tyTypeDesc}) - put(c, formalTypeParam, bound) + matchGenericParams(result, binding, callee) + let genericMatch = result.state + if genericMatch != csNoMatch: + result.state = csEmpty + if genericMatch == csMatch: # csEmpty if not fully instantiated + # instantiate the type, emulates old compiler behavior + # wouldn't be needed if sigmatch could handle complex cases, + # examples are in texplicitgenerics + # might be buggy, see rest of generateInstance if problems occur + let typ = ctx.instantiateOnlyProcType(ctx, result.bindings, callee, binding.info) + result.callee = typ + else: + # createThread[void] requires this if the above branch is removed: + copyingEraseVoidParams(result, result.callee) proc newCandidate*(ctx: PContext, callee: PSym, binding: PNode, calleeScope = -1): TCandidate = - initCandidate(ctx, result, callee, binding, calleeScope) + result = initCandidate(ctx, callee, binding, calleeScope) proc newCandidate*(ctx: PContext, callee: PType): TCandidate = - initCandidate(ctx, result, callee) - -proc copyCandidate(a: var TCandidate, b: TCandidate) = - a.c = b.c - a.exactMatches = b.exactMatches - a.subtypeMatches = b.subtypeMatches - a.convMatches = b.convMatches - a.intConvMatches = b.intConvMatches - a.genericMatches = b.genericMatches - a.state = b.state - a.callee = b.callee - a.calleeSym = b.calleeSym - a.call = copyTree(b.call) - a.baseTypeMatch = b.baseTypeMatch - copyIdTable(a.bindings, b.bindings) + result = initCandidate(ctx, callee) + +proc copyCandidate(dest: var TCandidate, src: TCandidate) = + dest.c = src.c + dest.exactMatches = src.exactMatches + dest.subtypeMatches = src.subtypeMatches + dest.convMatches = src.convMatches + dest.intConvMatches = src.intConvMatches + dest.genericMatches = src.genericMatches + dest.state = src.state + dest.callee = src.callee + dest.calleeSym = src.calleeSym + dest.call = copyTree(src.call) + dest.baseTypeMatch = src.baseTypeMatch + dest.bindings = src.bindings + +proc checkGeneric(a, b: TCandidate): int = + let c = a.c + let aa = a.callee + let bb = b.callee + var winner = 0 + for aai, bbi in underspecifiedPairs(aa, bb, 1): + var ma = newCandidate(c, bbi) + let tra = typeRel(ma, bbi, aai, {trDontBind}) + var mb = newCandidate(c, aai) + let trb = typeRel(mb, aai, bbi, {trDontBind}) + if tra == isGeneric and trb in {isNone, isInferred, isInferredConvertible}: + if winner == -1: return 0 + winner = 1 + if trb == isGeneric and tra in {isNone, isInferred, isInferredConvertible}: + if winner == 1: return 0 + winner = -1 + result = winner proc sumGeneric(t: PType): int = + # count the "genericness" so that Foo[Foo[T]] has the value 3 + # and Foo[T] has the value 2 so that we know Foo[Foo[T]] is more + # specific than Foo[T]. + result = 0 var t = t - var isvar = 1 while true: case t.kind - of tyGenericInst, tyArray, tyRef, tyPtr, tyDistinct, - tyOpenArray, tyVarargs, tySet, tyRange, tySequence, tyGenericBody, - tyLent: - t = t.lastSon + of tyAlias, tySink, tyNot: t = t.skipModifier + of tyArray, tyRef, tyPtr, tyDistinct, tyUncheckedArray, + tyOpenArray, tyVarargs, tySet, tyRange, tySequence, + tyLent, tyOwned, tyVar: + t = t.elementType + inc result + of tyBool, tyChar, tyEnum, tyObject, tyPointer, tyVoid, + tyString, tyCstring, tyInt..tyInt64, tyFloat..tyFloat128, + tyUInt..tyUInt64, tyCompositeTypeClass, tyBuiltInTypeClass: + inc result + break + of tyGenericBody: + t = t.typeBodyImpl + of tyGenericInst, tyStatic: + t = t.skipModifier inc result of tyOr: var maxBranch = 0 - for branch in t.sons: - let branchSum = branch.sumGeneric + for branch in t.kids: + let branchSum = sumGeneric(branch) if branchSum > maxBranch: maxBranch = branchSum - inc result, maxBranch + 1 + inc result, maxBranch break - of tyVar: - t = t.sons[0] - inc result - inc isvar of tyTypeDesc: - t = t.lastSon + t = t.elementType if t.kind == tyEmpty: break inc result - of tyGenericInvocation, tyTuple, tyProc, tyAnd: - result += ord(t.kind in {tyGenericInvocation, tyAnd}) - for i in 0 ..< t.len: - if t.sons[i] != nil: - result += t.sons[i].sumGeneric + of tyGenericParam: + if t.len > 0: + t = t.skipModifier + else: + inc result + break + of tyUntyped, tyTyped: break + of tyGenericInvocation, tyTuple, tyAnd: + result += ord(t.kind == tyAnd) + for a in t.kids: + if a != nil: + result += sumGeneric(a) + break + of tyProc: + if t.returnType != nil: + result += sumGeneric(t.returnType) + for _, a in t.paramTypes: + result += sumGeneric(a) break - of tyStatic: - return t.sons[0].sumGeneric + 1 - of tyGenericParam, tyExpr, tyStmt: break - of tyAlias, tySink: t = t.lastSon - of tyBool, tyChar, tyEnum, tyObject, tyPointer, - tyString, tyCString, tyInt..tyInt64, tyFloat..tyFloat128, - tyUInt..tyUInt64, tyCompositeTypeClass: - return isvar else: - return 0 - -#var ggDebug: bool + break proc complexDisambiguation(a, b: PType): int = # 'a' matches better if *every* argument matches better or equal than 'b'. var winner = 0 - for i in 1 ..< min(a.len, b.len): - let x = a.sons[i].sumGeneric - let y = b.sons[i].sumGeneric - #if ggDebug: - #echo "came herA ", typeToString(a.sons[i]), " ", x - #echo "came herB ", typeToString(b.sons[i]), " ", y + for ai, bi in underspecifiedPairs(a, b, 1): + let x = ai.sumGeneric + let y = bi.sumGeneric if x != y: if winner == 0: if x > y: winner = 1 @@ -248,8 +379,8 @@ proc complexDisambiguation(a, b: PType): int = result = winner when false: var x, y: int - for i in 1 ..< a.len: x += a.sons[i].sumGeneric - for i in 1 ..< b.len: y += b.sons[i].sumGeneric + for i in 1..<a.len: x += ai.sumGeneric + for i in 1..<b.len: y += bi.sumGeneric result = x - y proc writeMatches*(c: TCandidate) = @@ -261,7 +392,16 @@ proc writeMatches*(c: TCandidate) = echo " conv matches: ", c.convMatches echo " inheritance: ", c.inheritancePenalty -proc cmpCandidates*(a, b: TCandidate): int = +proc cmpInheritancePenalty(a, b: int): int = + var eb = b + var ea = a + if b < 0: + eb = maxInheritancePenalty # defacto max penalty + if a < 0: + ea = maxInheritancePenalty + eb - ea + +proc cmpCandidates*(a, b: TCandidate, isFormal=true): int = result = a.exactMatches - b.exactMatches if result != 0: return result = a.genericMatches - b.genericMatches @@ -272,19 +412,22 @@ proc cmpCandidates*(a, b: TCandidate): int = if result != 0: return result = a.convMatches - b.convMatches if result != 0: return - # the other way round because of other semantics: - result = b.inheritancePenalty - a.inheritancePenalty + result = cmpInheritancePenalty(a.inheritancePenalty, b.inheritancePenalty) if result != 0: return - # prefer more specialized generic over more general generic: - result = complexDisambiguation(a.callee, b.callee) - # only as a last resort, consider scoping: + if isFormal: + # check for generic subclass relation + result = checkGeneric(a, b) + if result != 0: return + # prefer more specialized generic over more general generic: + result = complexDisambiguation(a.callee, b.callee) if result != 0: return + # only as a last resort, consider scoping: result = a.calleeScope - b.calleeScope proc argTypeToString(arg: PNode; prefer: TPreferedDesc): string = if arg.kind in nkSymChoices: result = typeToString(arg[0].typ, prefer) - for i in 1 ..< arg.len: + for i in 1..<arg.len: result.add(" | ") result.add typeToString(arg[i].typ, prefer) elif arg.typ == nil: @@ -292,129 +435,144 @@ proc argTypeToString(arg: PNode; prefer: TPreferedDesc): string = else: result = arg.typ.typeToString(prefer) -proc describeArgs*(c: PContext, n: PNode, startIdx = 1; - prefer: TPreferedDesc = preferName): string = +template describeArgImpl(c: PContext, n: PNode, i: int, startIdx = 1; prefer = preferName) = + var arg = n[i] + if n[i].kind == nkExprEqExpr: + result.add renderTree(n[i][0]) + result.add ": " + if arg.typ.isNil and arg.kind notin {nkStmtList, nkDo}: + arg = c.semTryExpr(c, n[i][1]) + if arg == nil: + arg = n[i][1] + arg.typ = newTypeS(tyUntyped, c) + else: + if arg.typ == nil: + arg.typ = newTypeS(tyVoid, c) + n[i].typ = arg.typ + n[i][1] = arg + else: + if arg.typ.isNil and arg.kind notin {nkStmtList, nkDo, nkElse, + nkOfBranch, nkElifBranch, + nkExceptBranch}: + arg = c.semTryExpr(c, n[i]) + if arg == nil: + arg = n[i] + arg.typ = newTypeS(tyUntyped, c) + else: + if arg.typ == nil: + arg.typ = newTypeS(tyVoid, c) + n[i] = arg + if arg.typ != nil and arg.typ.kind == tyError: return + result.add argTypeToString(arg, prefer) + +proc describeArg*(c: PContext, n: PNode, i: int, startIdx = 1; prefer = preferName): string = result = "" - for i in countup(startIdx, n.len - 1): - var arg = n.sons[i] - if n.sons[i].kind == nkExprEqExpr: - add(result, renderTree(n.sons[i].sons[0])) - add(result, ": ") - if arg.typ.isNil and arg.kind notin {nkStmtList, nkDo}: - # XXX we really need to 'tryExpr' here! - arg = c.semOperand(c, n.sons[i].sons[1]) - n.sons[i].typ = arg.typ - n.sons[i].sons[1] = arg - else: - if arg.typ.isNil and arg.kind notin {nkStmtList, nkDo, nkElse, - nkOfBranch, nkElifBranch, - nkExceptBranch}: - arg = c.semOperand(c, n.sons[i]) - n.sons[i] = arg - if arg.typ != nil and arg.typ.kind == tyError: return - add(result, argTypeToString(arg, prefer)) - if i != sonsLen(n) - 1: add(result, ", ") - -proc typeRelImpl*(c: var TCandidate, f, aOrig: PType, - flags: TTypeRelFlags = {}): TTypeRelation - -const traceTypeRel = false - -when traceTypeRel: - var nextTypeRel = 0 - -template typeRel*(c: var TCandidate, f, aOrig: PType, - flags: TTypeRelFlags = {}): TTypeRelation = - when traceTypeRel: - var enteringAt = nextTypeRel - if mdbg: - inc nextTypeRel - echo "----- TYPE REL ", enteringAt - debug f - debug aOrig - # writeStackTrace() - - let r = typeRelImpl(c, f, aOrig, flags) - - when traceTypeRel: - if enteringAt != nextTypeRel: - echo "----- TYPE REL ", enteringAt, " RESULT: ", r - - r - -proc concreteType(c: TCandidate, t: PType): PType = + describeArgImpl(c, n, i, startIdx, prefer) + +proc describeArgs*(c: PContext, n: PNode, startIdx = 1; prefer = preferName): string = + result = "" + for i in startIdx..<n.len: + describeArgImpl(c, n, i, startIdx, prefer) + if i != n.len - 1: result.add ", " + +proc concreteType(c: TCandidate, t: PType; f: PType = nil): PType = case t.kind - of tyNil: - result = nil # what should it be? of tyTypeDesc: if c.isNoCall: result = t else: result = nil of tySequence, tySet: - if t.sons[0].kind == tyEmpty: result = nil + if t.elementType.kind == tyEmpty: result = nil else: result = t - of tyGenericParam, tyAnything: + of tyGenericParam, tyAnything, tyConcept: result = t + if c.isNoCall: return while true: - result = PType(idTableGet(c.bindings, t)) + result = idTableGet(c.bindings, t) if result == nil: break # it's ok, no match # example code that triggers it: # proc sort[T](cmp: proc(a, b: T): int = cmp) if result.kind != tyGenericParam: break of tyGenericInvocation: - result = t - doAssert(false, "cannot resolve type: " & typeToString(t)) + result = nil + of tyOwned: + # bug #11257: the comparison system.`==`[T: proc](x, y: T) works + # better without the 'owned' type: + if f != nil and f.hasElementType and f.elementType.skipTypes({tyBuiltInTypeClass, tyOr}).kind == tyProc: + result = t.skipModifier + else: + result = t else: result = t # Note: empty is valid here -proc handleRange(f, a: PType, min, max: TTypeKind): TTypeRelation = +proc handleRange(c: PContext, f, a: PType, min, max: TTypeKind): TTypeRelation = if a.kind == f.kind: result = isEqual else: let ab = skipTypes(a, {tyRange}) let k = ab.kind - if k == f.kind: result = isSubrange - elif k == tyInt and f.kind in {tyRange, tyInt8..tyInt64, - tyUInt..tyUInt64} and - isIntLit(ab) and ab.n.intVal >= firstOrd(nil, f) and - ab.n.intVal <= lastOrd(nil, f): + let nf = c.config.normalizeKind(f.kind) + let na = c.config.normalizeKind(k) + if k == f.kind: + # `a` is a range type matching its base type + # see very bottom for range types matching different types + if isIntLit(ab): + # range type can only give isFromIntLit for base type + result = isFromIntLit + else: + result = isSubrange + elif a.kind == tyInt and f.kind in {tyRange, tyInt..tyInt64, + tyUInt..tyUInt64} and + isIntLit(ab) and getInt(ab.n) >= firstOrd(nil, f) and + getInt(ab.n) <= lastOrd(nil, f): # passing 'nil' to firstOrd/lastOrd here as type checking rules should - # not depent on the target integer size configurations! + # not depend on the target integer size configurations! # integer literal in the proper range; we want ``i16 + 4`` to stay an # ``int16`` operation so we declare the ``4`` pseudo-equal to int16 result = isFromIntLit - elif f.kind == tyInt and k in {tyInt8..tyInt32}: + elif a.kind == tyInt and nf == c.config.targetSizeSignedToKind: + result = isIntConv + elif a.kind == tyUInt and nf == c.config.targetSizeUnsignedToKind: + result = isIntConv + elif f.kind == tyInt and na in {tyInt8 .. pred(c.config.targetSizeSignedToKind)}: + result = isIntConv + elif f.kind == tyUInt and na in {tyUInt8 .. pred(c.config.targetSizeUnsignedToKind)}: result = isIntConv elif k >= min and k <= max: result = isConvertible - elif a.kind == tyRange and a.sons[0].kind in {tyInt..tyInt64, - tyUInt8..tyUInt32} and - a.n[0].intVal >= firstOrd(nil, f) and - a.n[1].intVal <= lastOrd(nil, f): + elif a.kind == tyRange and + # Make sure the conversion happens between types w/ same signedness + (f.kind in {tyInt..tyInt64} and a[0].kind in {tyInt..tyInt64} or + f.kind in {tyUInt8..tyUInt32} and a[0].kind in {tyUInt8..tyUInt32}) and + a.n[0].intVal >= firstOrd(nil, f) and a.n[1].intVal <= lastOrd(nil, f): # passing 'nil' to firstOrd/lastOrd here as type checking rules should - # not depent on the target integer size configurations! + # not depend on the target integer size configurations! result = isConvertible else: result = isNone - #elif f.kind == tyInt and k in {tyInt..tyInt32}: result = isIntConv - #elif f.kind == tyUInt and k in {tyUInt..tyUInt32}: result = isIntConv -proc isConvertibleToRange(f, a: PType): bool = - # be less picky for tyRange, as that it is used for array indexing: +proc isConvertibleToRange(c: PContext, f, a: PType): bool = if f.kind in {tyInt..tyInt64, tyUInt..tyUInt64} and a.kind in {tyInt..tyInt64, tyUInt..tyUInt64}: case f.kind - of tyInt, tyInt64: result = true - of tyInt8: result = a.kind in {tyInt8, tyInt} - of tyInt16: result = a.kind in {tyInt8, tyInt16, tyInt} - of tyInt32: result = a.kind in {tyInt8, tyInt16, tyInt32, tyInt} - of tyUInt, tyUInt64: result = true - of tyUInt8: result = a.kind in {tyUInt8, tyUInt} - of tyUInt16: result = a.kind in {tyUInt8, tyUInt16, tyUInt} - of tyUInt32: result = a.kind in {tyUInt8, tyUInt16, tyUInt32, tyUInt} + of tyInt8: result = isIntLit(a) or a.kind in {tyInt8} + of tyInt16: result = isIntLit(a) or a.kind in {tyInt8, tyInt16} + of tyInt32: result = isIntLit(a) or a.kind in {tyInt8, tyInt16, tyInt32} + # This is wrong, but seems like there's a lot of code that relies on it :( + of tyInt, tyUInt: result = true + # of tyInt: result = isIntLit(a) or a.kind in {tyInt8 .. c.config.targetSizeSignedToKind} + of tyInt64: result = isIntLit(a) or a.kind in {tyInt8, tyInt16, tyInt32, tyInt, tyInt64} + of tyUInt8: result = isIntLit(a) or a.kind in {tyUInt8} + of tyUInt16: result = isIntLit(a) or a.kind in {tyUInt8, tyUInt16} + of tyUInt32: result = isIntLit(a) or a.kind in {tyUInt8, tyUInt16, tyUInt32} + # of tyUInt: result = isIntLit(a) or a.kind in {tyUInt8 .. c.config.targetSizeUnsignedToKind} + of tyUInt64: result = isIntLit(a) or a.kind in {tyUInt8, tyUInt16, tyUInt32, tyUInt64} else: result = false - elif f.kind in {tyFloat..tyFloat128} and - a.kind in {tyFloat..tyFloat128}: - result = true + elif f.kind in {tyFloat..tyFloat128}: + # `isIntLit` is correct and should be used above as well, see PR: + # https://github.com/nim-lang/Nim/pull/11197 + result = isIntLit(a) or a.kind in {tyFloat..tyFloat128} + else: + result = false proc handleFloatRange(f, a: PType): TTypeRelation = if a.kind == f.kind: @@ -431,13 +589,52 @@ proc handleFloatRange(f, a: PType): TTypeRelation = else: result = isIntConv else: result = isNone +proc reduceToBase(f: PType): PType = + #[ + Returns the lowest order (most general) type that that is compatible with the input. + E.g. + A[T] = ptr object ... A -> ptr object + A[N: static[int]] = array[N, int] ... A -> array + ]# + case f.kind: + of tyGenericParam: + if f.len <= 0 or f.skipModifier == nil: + result = f + else: + result = reduceToBase(f.skipModifier) + of tyGenericInvocation: + result = reduceToBase(f.baseClass) + of tyCompositeTypeClass, tyAlias: + if not f.hasElementType or f.elementType == nil: + result = f + else: + result = reduceToBase(f.elementType) + of tyGenericInst: + result = reduceToBase(f.skipModifier) + of tyGenericBody: + result = reduceToBase(f.typeBodyImpl) + of tyUserTypeClass: + if f.isResolvedUserTypeClass: + result = f.base # ?? idk if this is right + else: + result = f.skipModifier + of tyStatic, tyOwned, tyVar, tyLent, tySink: + result = reduceToBase(f.base) + of tyInferred: + # This is not true "After a candidate type is selected" + result = reduceToBase(f.base) + of tyRange: + result = f.elementType + else: + result = f + proc genericParamPut(c: var TCandidate; last, fGenericOrigin: PType) = - if fGenericOrigin != nil and last.kind == tyGenericInst and - last.len-1 == fGenericOrigin.len: - for i in countup(1, sonsLen(fGenericOrigin) - 1): - let x = PType(idTableGet(c.bindings, fGenericOrigin.sons[i])) - if x == nil: - put(c, fGenericOrigin.sons[i], last.sons[i]) + if fGenericOrigin != nil and last.kind == tyGenericInst and + last.kidsLen-1 == fGenericOrigin.kidsLen: + for i in FirstGenericParamAt..<fGenericOrigin.kidsLen: + let x = idTableGet(c.bindings, fGenericOrigin[i]) + if x == nil: + put(c, fGenericOrigin[i], last[i]) proc isObjectSubtype(c: var TCandidate; a, f, fGenericOrigin: PType): int = var t = a @@ -445,8 +642,9 @@ proc isObjectSubtype(c: var TCandidate; a, f, fGenericOrigin: PType): int = var depth = 0 var last = a while t != nil and not sameObjectTypes(f, t): - assert t.kind == tyObject - t = t.sons[0] + if t.kind != tyObject: # avoid entering generic params etc + return -1 + t = t.baseClass if t == nil: break last = t t = skipTypes(t, skipPtrs) @@ -467,22 +665,25 @@ proc skipToObject(t: PType; skipped: var SkippedPtr): PType = while r != nil: case r.kind of tyGenericInvocation: - r = r.sons[0] + r = r.genericHead of tyRef: inc ptrs skipped = skippedRef - r = r.lastSon + r = r.elementType of tyPtr: inc ptrs skipped = skippedPtr - r = r.lastSon - of tyGenericBody, tyGenericInst, tyAlias, tySink: - r = r.lastSon + r = r.elementType + of tyGenericInst, tyAlias, tySink, tyOwned: + r = r.elementType + of tyGenericBody: + r = r.typeBodyImpl else: break if r.kind == tyObject and ptrs <= 1: result = r + else: result = nil -proc isGenericSubtype(c: var TCandidate; a, f: PType, d: var int, fGenericOrigin: PType = nil): bool = +proc isGenericSubtype(c: var TCandidate; a, f: PType, d: var int, fGenericOrigin: PType): bool = assert f.kind in {tyGenericInst, tyGenericInvocation, tyGenericBody} var askip = skippedNone var fskip = skippedNone @@ -494,7 +695,7 @@ proc isGenericSubtype(c: var TCandidate; a, f: PType, d: var int, fGenericOrigin # XXX sameObjectType can return false here. Need to investigate # why that is but sameObjectType does way too much work here anyway. while t != nil and r.sym != t.sym and askip == fskip: - t = t.sons[0] + t = t.baseClass if t == nil: break last = t t = t.skipToObject(askip) @@ -503,32 +704,39 @@ proc isGenericSubtype(c: var TCandidate; a, f: PType, d: var int, fGenericOrigin genericParamPut(c, last, fGenericOrigin) d = depth result = true + else: + result = false proc minRel(a, b: TTypeRelation): TTypeRelation = if a <= b: result = a else: result = b -proc recordRel(c: var TCandidate, f, a: PType): TTypeRelation = +proc recordRel(c: var TCandidate, f, a: PType, flags: TTypeRelFlags): TTypeRelation = result = isNone if sameType(f, a): result = isEqual - elif sonsLen(a) == sonsLen(f): + elif sameTupleLengths(a, f): result = isEqual let firstField = if f.kind == tyTuple: 0 else: 1 - for i in countup(firstField, sonsLen(f) - 1): - var m = typeRel(c, f.sons[i], a.sons[i]) + for _, ff, aa in tupleTypePairs(f, a): + var m = typeRel(c, ff, aa, flags) if m < isSubtype: return isNone + if m == isSubtype and aa.kind != tyNil and c.inheritancePenalty > -1: + # we can't process individual element type conversions from a + # type conversion for the whole tuple + # subtype relations need type conversions when inheritance is used + return isNone result = minRel(result, m) if f.n != nil and a.n != nil: - for i in countup(0, sonsLen(f.n) - 1): + for i in 0..<f.n.len: # check field names: - if f.n.sons[i].kind != nkSym: return isNone - elif a.n.sons[i].kind != nkSym: return isNone + if f.n[i].kind != nkSym: return isNone + elif a.n[i].kind != nkSym: return isNone else: - var x = f.n.sons[i].sym - var y = a.n.sons[i].sym - if f.kind == tyObject and typeRel(c, x.typ, y.typ) < isSubtype: + var x = f.n[i].sym + var y = a.n[i].sym + if f.kind == tyObject and typeRel(c, x.typ, y.typ, flags) < isSubtype: return isNone if x.name.id != y.name.id: return isNone @@ -536,13 +744,16 @@ proc allowsNil(f: PType): TTypeRelation {.inline.} = result = if tfNotNil notin f.flags: isSubtype else: isNone proc inconsistentVarTypes(f, a: PType): bool {.inline.} = - result = f.kind != a.kind and (f.kind in {tyVar, tyLent} or a.kind in {tyVar, tyLent}) + result = (f.kind != a.kind and + (f.kind in {tyVar, tyLent, tySink} or a.kind in {tyVar, tyLent, tySink})) or + isOutParam(f) != isOutParam(a) -proc procParamTypeRel(c: var TCandidate, f, a: PType): TTypeRelation = +proc procParamTypeRel(c: var TCandidate; f, a: PType): TTypeRelation = ## For example we have: - ## .. code-block:: nim + ## ```nim ## proc myMap[T,S](sIn: seq[T], f: proc(x: T): S): seq[S] = ... ## proc innerProc[Q,W](q: Q): W = ... + ## ``` ## And we want to match: myMap(@[1,2,3], innerProc) ## This proc (procParamTypeRel) will do the following steps in ## three different calls: @@ -559,17 +770,20 @@ proc procParamTypeRel(c: var TCandidate, f, a: PType): TTypeRelation = a = a if a.isMetaType: - let aResolved = PType(idTableGet(c.bindings, a)) + let aResolved = idTableGet(c.bindings, a) if aResolved != nil: a = aResolved if a.isMetaType: if f.isMetaType: # We are matching a generic proc (as proc param) # to another generic type appearing in the proc - # signature. There is a change that the target + # signature. There is a chance that the target # type is already fully-determined, so we are # going to try resolve it - f = generateTypeInstance(c.c, c.bindings, c.call.info, f) + if c.call != nil: + f = generateTypeInstance(c.c, c.bindings, c.call.info, f) + else: + f = nil if f == nil or f.isMetaType: # no luck resolving the type, so the inference fails return isBothMetaConvertible @@ -578,12 +792,14 @@ proc procParamTypeRel(c: var TCandidate, f, a: PType): TTypeRelation = if reverseRel >= isGeneric: result = isInferred #inc c.genericMatches + else: + result = isNone else: # Note that this typeRel call will save f's resolved type into c.bindings # if f is metatype. result = typeRel(c, f, a) - if result <= isSubtype or inconsistentVarTypes(f, a): + if result <= isSubrange or inconsistentVarTypes(f, a): result = isNone #if result == isEqual: @@ -592,72 +808,67 @@ proc procParamTypeRel(c: var TCandidate, f, a: PType): TTypeRelation = proc procTypeRel(c: var TCandidate, f, a: PType): TTypeRelation = case a.kind of tyProc: - if sonsLen(f) != sonsLen(a): return + var f = f + copyingEraseVoidParams(c, f) + if f.signatureLen != a.signatureLen: return result = isEqual # start with maximum; also correct for no # params at all + if f.flags * {tfIterator} != a.flags * {tfIterator}: + return isNone + template checkParam(f, a) = result = minRel(result, procParamTypeRel(c, f, a)) if result == isNone: return # Note: We have to do unification for the parameters before the # return type! - for i in 1 ..< f.sonsLen: - checkParam(f.sons[i], a.sons[i]) + for i in 1..<f.len: + checkParam(f[i], a[i]) - if f.sons[0] != nil: - if a.sons[0] != nil: - checkParam(f.sons[0], a.sons[0]) + if f[0] != nil: + if a[0] != nil: + checkParam(f[0], a[0]) else: return isNone - elif a.sons[0] != nil: + elif a[0] != nil: return isNone - if tfNoSideEffect in f.flags and tfNoSideEffect notin a.flags: - return isNone - elif tfThread in f.flags and a.flags * {tfThread, tfNoSideEffect} == {} and - optThreadAnalysis in c.c.config.globalOptions: - # noSideEffect implies ``tfThread``! - return isNone - elif f.flags * {tfIterator} != a.flags * {tfIterator}: - return isNone - elif f.callConv != a.callConv: - # valid to pass a 'nimcall' thingie to 'closure': - if f.callConv == ccClosure and a.callConv == ccDefault: - result = if result == isInferred: isInferredConvertible - elif result == isBothMetaConvertible: isBothMetaConvertible - else: isConvertible - else: - return isNone + result = getProcConvMismatch(c.c.config, f, a, result)[1] + when useEffectSystem: if compatibleEffects(f, a) != efCompat: return isNone + when defined(drnim): + if not c.c.graph.compatibleProps(c.c.graph, f, a): return isNone of tyNil: result = f.allowsNil - else: discard + else: result = isNone proc typeRangeRel(f, a: PType): TTypeRelation {.noinline.} = - let - a0 = firstOrd(nil, a) - a1 = lastOrd(nil, a) - f0 = firstOrd(nil, f) - f1 = lastOrd(nil, f) - if a0 == f0 and a1 == f1: - result = isEqual - elif a0 >= f0 and a1 <= f1: - result = isConvertible - elif a0 <= f1 and f0 <= a1: - # X..Y and C..D overlap iff (X <= D and C <= Y) - result = isConvertible + template checkRange[T](a0, a1, f0, f1: T): TTypeRelation = + if a0 == f0 and a1 == f1: + isEqual + elif a0 >= f0 and a1 <= f1: + isConvertible + elif a0 <= f1 and f0 <= a1: + # X..Y and C..D overlap iff (X <= D and C <= Y) + isConvertible + else: + isNone + + if f.isOrdinalType: + checkRange(firstOrd(nil, a), lastOrd(nil, a), firstOrd(nil, f), lastOrd(nil, f)) else: - result = isNone + checkRange(firstFloat(a), lastFloat(a), firstFloat(f), lastFloat(f)) + proc matchUserTypeClass*(m: var TCandidate; ff, a: PType): PType = var c = m.c typeClass = ff.skipTypes({tyUserTypeClassInst}) body = typeClass.n[3] - matchedConceptContext: TMatchedConcept + matchedConceptContext = TMatchedConcept() prevMatchedConcept = c.matchedConcept prevCandidateType = typeClass[0][0] @@ -670,27 +881,27 @@ proc matchUserTypeClass*(m: var TCandidate; ff, a: PType): PType = openScope(c) matchedConceptContext.candidateType = a - typeClass[0].sons[0] = a + typeClass[0][0] = a c.matchedConcept = addr(matchedConceptContext) defer: c.matchedConcept = prevMatchedConcept - typeClass[0].sons[0] = prevCandidateType + typeClass[0][0] = prevCandidateType closeScope(c) - var typeParams: seq[(PSym, PType)] + var typeParams: seq[(PSym, PType)] = @[] if ff.kind == tyUserTypeClassInst: - for i in 1 ..< (ff.len - 1): + for i in 1..<(ff.len - 1): var - typeParamName = ff.base.sons[i-1].sym.name - typ = ff.sons[i] - param: PSym - alreadyBound = PType(idTableGet(m.bindings, typ)) + typeParamName = ff.base[i-1].sym.name + typ = ff[i] + param: PSym = nil + alreadyBound = idTableGet(m.bindings, typ) if alreadyBound != nil: typ = alreadyBound template paramSym(kind): untyped = - newSym(kind, typeParamName, typeClass.sym, typeClass.sym.info, {}) + newSym(kind, typeParamName, c.idgen, typeClass.sym, typeClass.sym.info, {}) block addTypeParam: for prev in typeParams: @@ -703,27 +914,29 @@ proc matchUserTypeClass*(m: var TCandidate; ff, a: PType): PType = of tyStatic: param = paramSym skConst param.typ = typ.exactReplica + #copyType(typ, c.idgen, typ.owner) if typ.n == nil: param.typ.flags.incl tfInferrableStatic else: param.ast = typ.n - of tyUnknown: + of tyFromExpr: param = paramSym skVar param.typ = typ.exactReplica + #copyType(typ, c.idgen, typ.owner) else: param = paramSym skType param.typ = if typ.isMetaType: - c.newTypeWithSons(tyInferred, @[typ]) + newTypeS(tyInferred, c, typ) else: makeTypeDesc(c, typ) - typeParams.safeAdd((param, typ)) + typeParams.add((param, typ)) addDecl(c, param) var - oldWriteHook: type(m.c.config.writelnHook) - diagnostics: seq[string] + oldWriteHook = default typeof(m.c.config.writelnHook) + diagnostics: seq[string] = @[] errorPrefix: string flags: TExprFlags = {} collectDiagnostics = m.diagnosticsEnabled or @@ -736,7 +949,7 @@ proc matchUserTypeClass*(m: var TCandidate; ff, a: PType): PType = diagnostics = @[] flags = {efExplain} m.c.config.writelnHook = proc (s: string) = - if errorPrefix == nil: errorPrefix = typeClass.sym.name.s & ":" + if errorPrefix.len == 0: errorPrefix = typeClass.sym.name.s & ":" let msg = s.replace("Error:", errorPrefix) if oldWriteHook != nil: oldWriteHook msg diagnostics.add msg @@ -746,7 +959,7 @@ proc matchUserTypeClass*(m: var TCandidate; ff, a: PType): PType = if collectDiagnostics: m.c.config.writelnHook = oldWriteHook for msg in diagnostics: - m.diagnostics.safeAdd msg + m.diagnostics.add msg m.diagnosticsEnabled = true if checkedBody == nil: return nil @@ -760,7 +973,8 @@ proc matchUserTypeClass*(m: var TCandidate; ff, a: PType): PType = if ff.kind == tyUserTypeClassInst: result = generateTypeInstance(c, m.bindings, typeClass.sym.info, ff) else: - result = copyType(ff, ff.owner, true) + result = ff.exactReplica + #copyType(ff, c.idgen, ff.owner) result.n = checkedBody @@ -783,7 +997,9 @@ proc maybeSkipDistinct(m: TCandidate; t: PType, callee: PSym): PType = result = t proc tryResolvingStaticExpr(c: var TCandidate, n: PNode, - allowUnresolved = false): PNode = + allowUnresolved = false, + allowCalls = false, + expectedType: PType = nil): PNode = # Consider this example: # type Value[N: static[int]] = object # proc foo[N](a: Value[N], r: range[0..(N-1)]) @@ -792,6 +1008,8 @@ proc tryResolvingStaticExpr(c: var TCandidate, n: PNode, # This proc is used to evaluate such static expressions. let instantiated = replaceTypesInBody(c.c, c.bindings, n, nil, allowMetaTypes = allowUnresolved) + if not allowCalls and instantiated.kind in nkCallKinds: + return nil result = c.c.semExpr(c.c, instantiated) proc inferStaticParam*(c: var TCandidate, lhs: PNode, rhs: BiggestInt): bool = @@ -815,9 +1033,6 @@ proc inferStaticParam*(c: var TCandidate, lhs: PNode, rhs: BiggestInt): bool = # if lhs.kind in nkCallKinds and lhs[0].kind == nkSym: case lhs[0].sym.magic - of mUnaryLt: - return inferStaticParam(c, lhs[1], rhs + 1) - of mAddI, mAddU, mInc, mSucc: if lhs[1].kind == nkIntLit: return inferStaticParam(c, lhs[2], rhs - lhs[1].intVal) @@ -853,16 +1068,21 @@ proc inferStaticParam*(c: var TCandidate, lhs: PNode, rhs: BiggestInt): bool = if lhs[2].kind == nkIntLit: return inferStaticParam(c, lhs[1], rhs shl lhs[2].intVal) + of mAshrI: + if lhs[2].kind == nkIntLit: + return inferStaticParam(c, lhs[1], ashr(rhs, lhs[2].intVal)) + of mUnaryMinusI: return inferStaticParam(c, lhs[1], -rhs) - of mUnaryPlusI, mToInt, mToBiggestInt: + of mUnaryPlusI: return inferStaticParam(c, lhs[1], rhs) else: discard - elif lhs.kind == nkSym and lhs.typ.kind == tyStatic and lhs.typ.n == nil: - var inferred = newTypeWithSons(c.c, tyStatic, lhs.typ.sons) + elif lhs.kind == nkSym and lhs.typ.kind == tyStatic and + (lhs.typ.n == nil or idTableGet(c.bindings, lhs.typ) == nil): + var inferred = newTypeS(tyStatic, c.c, lhs.typ.elementType) inferred.n = newIntNode(nkIntLit, rhs) put(c, lhs.typ, inferred) if c.c.matchedConcept != nil: @@ -885,14 +1105,15 @@ proc inferStaticsInRange(c: var TCandidate, allowUnresolved = true) let upperBound = tryResolvingStaticExpr(c, inferred.n[1], allowUnresolved = true) - template doInferStatic(e: PNode, r: BiggestInt) = + template doInferStatic(e: PNode, r: Int128) = var exp = e var rhs = r - if inferStaticParam(c, exp, rhs): + if inferStaticParam(c, exp, toInt64(rhs)): return isGeneric else: failureToInferStaticParam(c.c.config, exp) + result = isNone if lowerBound.kind == nkIntLit: if upperBound.kind == nkIntLit: if lengthOrd(c.c.config, concrete) == upperBound.intVal - lowerBound.intVal + 1: @@ -901,29 +1122,42 @@ proc inferStaticsInRange(c: var TCandidate, return isNone doInferStatic(upperBound, lengthOrd(c.c.config, concrete) + lowerBound.intVal - 1) elif upperBound.kind == nkIntLit: - doInferStatic(lowerBound, upperBound.intVal + 1 - lengthOrd(c.c.config, concrete)) + doInferStatic(lowerBound, getInt(upperBound) + 1 - lengthOrd(c.c.config, concrete)) template subtypeCheck() = - if result <= isSubrange and f.lastSon.skipTypes(abstractInst).kind in {tyRef, tyPtr, tyVar, tyLent}: + case result + of isIntConv: result = isNone + of isSubrange: + discard # XXX should be isNone with preview define, warnings + of isConvertible: + if f.last.skipTypes(abstractInst).kind != tyOpenArray: + # exclude var openarray which compiler supports + result = isNone + of isSubtype: + if f.last.skipTypes(abstractInst).kind in { + tyRef, tyPtr, tyVar, tyLent, tyOwned}: + # compiler can't handle subtype conversions with pointer indirection + result = isNone + else: discard proc isCovariantPtr(c: var TCandidate, f, a: PType): bool = # this proc is always called for a pair of matching types assert f.kind == a.kind template baseTypesCheck(lhs, rhs: PType): bool = - lhs.kind notin {tyPtr, tyRef, tyVar, tyLent} and + lhs.kind notin {tyPtr, tyRef, tyVar, tyLent, tyOwned} and typeRel(c, lhs, rhs, {trNoCovariance}) == isSubtype case f.kind - of tyRef, tyPtr: + of tyRef, tyPtr, tyOwned: return baseTypesCheck(f.base, a.base) of tyGenericInst: let body = f.base return body == a.base and - a.sonsLen == 3 and - tfWeakCovariant notin body.sons[0].flags and - baseTypesCheck(f.sons[1], a.sons[1]) + a.len == 3 and + tfWeakCovariant notin body[0].flags and + baseTypesCheck(f[1], a[1]) else: return false @@ -947,8 +1181,11 @@ when false: of tyFloat64: greater({tyFloat128}) else: discard -proc typeRelImpl(c: var TCandidate, f, aOrig: PType, - flags: TTypeRelFlags = {}): TTypeRelation = +template skipOwned(a) = + if a.kind == tyOwned: a = a.skipTypes({tyOwned, tyGenericInst}) + +proc typeRel(c: var TCandidate, f, aOrig: PType, + flags: TTypeRelFlags = {}): TTypeRelation = # typeRel can be used to establish various relationships between types: # # 1) When used with concrete types, it will check for type equivalence @@ -959,8 +1196,8 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, # of the designated type class. # # 3) When used with two type classes, it will check whether the types - # matching the first type class are a strict subset of the types matching - # the other. This allows us to compare the signatures of generic procs in + # matching the first type class (aOrig) are a strict subset of the types matching + # the other (f). This allows us to compare the signatures of generic procs in # order to give preferrence to the most specific one: # # seq[seq[any]] is a strict subset of seq[any] and hence more specific. @@ -968,7 +1205,12 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, result = isNone assert(f != nil) - if f.kind == tyExpr: + when declared(deallocatedRefId): + let corrupt = deallocatedRefId(cast[pointer](f)) + if corrupt != 0: + c.c.config.quitOrRaise "it's corrupt " & $corrupt + + if f.kind == tyUntyped: if aOrig != nil: put(c, f, aOrig) return isGeneric @@ -978,7 +1220,8 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, useTypeLoweringRuleInTypeClass = c.c.matchedConcept != nil and not c.isNoCall and f.kind != tyTypeDesc and - tfExplicit notin aOrig.flags + tfExplicit notin aOrig.flags and + tfConceptMatchedTypeSym notin aOrig.flags aOrig = if useTypeLoweringRuleInTypeClass: aOrig.skipTypes({tyTypeDesc}) @@ -988,13 +1231,13 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, if aOrig.kind == tyInferred: let prev = aOrig.previouslyInferred if prev != nil: - return typeRel(c, f, prev) + return typeRel(c, f, prev, flags) else: var candidate = f case f.kind of tyGenericParam: - var prev = PType(idTableGet(c.bindings, f)) + var prev = idTableGet(c.bindings, f) if prev != nil: candidate = prev of tyFromExpr: let computedType = tryResolvingStaticExpr(c, f.n).typ @@ -1009,44 +1252,49 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, else: discard - result = typeRel(c, aOrig.base, candidate) + result = typeRel(c, aOrig.base, candidate, flags) if result != isNone: - c.inferredTypes.safeAdd aOrig - aOrig.sons.add candidate + c.inferredTypes.add aOrig + aOrig.add candidate result = isEqual return template doBind: bool = trDontBind notin flags - # var and static arguments match regular modifier-free types - var a = maybeSkipDistinct(c, aOrig.skipTypes({tyStatic, tyVar, tyLent}), c.calleeSym) + # var, sink and static arguments match regular modifier-free types + var a = maybeSkipDistinct(c, aOrig.skipTypes({tyStatic, tyVar, tyLent, tySink}), c.calleeSym) # XXX: Theoretically, maybeSkipDistinct could be called before we even # start the param matching process. This could be done in `prepareOperand` # for example, but unfortunately `prepareOperand` is not called in certain # situation when nkDotExpr are rotated to nkDotCalls if aOrig.kind in {tyAlias, tySink}: - return typeRel(c, f, lastSon(aOrig)) + return typeRel(c, f, skipModifier(aOrig), flags) if a.kind == tyGenericInst and - skipTypes(f, {tyVar, tyLent}).kind notin { + skipTypes(f, {tyStatic, tyVar, tyLent, tySink}).kind notin { tyGenericBody, tyGenericInvocation, tyGenericInst, tyGenericParam} + tyTypeClasses: - return typeRel(c, f, lastSon(a)) + return typeRel(c, f, skipModifier(a), flags) if a.isResolvedUserTypeClass: - return typeRel(c, f, a.lastSon) + return typeRel(c, f, a.skipModifier, flags) template bindingRet(res) = if doBind: - let bound = aOrig.skipTypes({tyRange}).skipIntLit + let bound = aOrig.skipTypes({tyRange}).skipIntLit(c.c.idgen) put(c, f, bound) return res template considerPreviousT(body: untyped) = - var prev = PType(idTableGet(c.bindings, f)) + var prev = idTableGet(c.bindings, f) if prev == nil: body - else: return typeRel(c, prev, a) + else: return typeRel(c, prev, a, flags) + + if c.c.inGenericContext > 0 and not c.isNoCall and + (tfUnresolved in a.flags or a.kind in tyTypeClasses): + # cheap check for unresolved arg, not nested + return isNone case a.kind of tyOr: @@ -1056,23 +1304,23 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, # both int and string must match against number # but ensure that '[T: A|A]' matches as good as '[T: A]' (bug #2219): result = isGeneric - for branch in a.sons: + for branch in a.kids: let x = typeRel(c, f, branch, flags + {trDontBind}) if x == isNone: return isNone if x < result: result = x - return - + return result of tyAnd: # XXX: deal with the current dual meaning of tyGenericParam c.typedescMatched = true # seq[Sortable and Iterable] vs seq[Sortable] # only one match is enough - for branch in a.sons: + for branch in a.kids: let x = typeRel(c, f, branch, flags + {trDontBind}) if x != isNone: return if x >= isGeneric: isGeneric else: x return isNone - + of tyIterable: + if f.kind != tyIterable: return isNone of tyNot: case f.kind of tyNot: @@ -1080,18 +1328,16 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, # seq[float] matches the first, but not the second # we must turn the problem around: # is number a subset of int? - return typeRel(c, a.lastSon, f.lastSon) + return typeRel(c, a.elementType, f.elementType, flags) else: # negative type classes are essentially infinite, # so only the `any` type class is their superset return if f.kind == tyAnything: isGeneric else: isNone - of tyAnything: - return if f.kind == tyAnything: isGeneric - else: isNone - + if f.kind == tyAnything: return isGeneric + else: return isNone of tyUserTypeClass, tyUserTypeClassInst: if c.c.matchedConcept != nil and c.c.matchedConcept.depth <= 4: # consider this: 'var g: Node' *within* a concept where 'Node' @@ -1100,6 +1346,17 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, let x = typeRel(c, a, f, flags + {trDontBind}) if x >= isGeneric: return isGeneric + of tyFromExpr: + if c.c.inGenericContext > 0: + if not c.isNoCall: + # generic type bodies can sometimes compile call expressions + # prevent expressions with unresolved types from + # being passed as parameters + return isNone + else: + # Foo[templateCall(T)] shouldn't fail early if Foo has a constraint + # and we can't evaluate `templateCall(T)` yet + return isGeneric else: discard case f.kind @@ -1112,60 +1369,74 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, of tyRange: if a.kind == f.kind: if f.base.kind == tyNone: return isGeneric - result = typeRel(c, base(f), base(a)) + result = typeRel(c, base(f), base(a), flags) # bugfix: accept integer conversions here #if result < isGeneric: result = isNone if result notin {isNone, isGeneric}: # resolve any late-bound static expressions # that may appear in the range: + let expectedType = base(f) for i in 0..1: if f.n[i].kind == nkStaticExpr: - f.n.sons[i] = tryResolvingStaticExpr(c, f.n[i]) + let r = tryResolvingStaticExpr(c, f.n[i], expectedType = expectedType) + if r != nil: + f.n[i] = r result = typeRangeRel(f, a) else: - if skipTypes(f, {tyRange}).kind == a.kind: + let f = skipTypes(f, {tyRange}) + if f.kind == a.kind and (f.kind != tyEnum or sameEnumTypes(f, a)): result = isIntConv - elif isConvertibleToRange(skipTypes(f, {tyRange}), a): + elif isConvertibleToRange(c.c, f, a): result = isConvertible # a convertible to f - of tyInt: result = handleRange(f, a, tyInt8, tyInt32) - of tyInt8: result = handleRange(f, a, tyInt8, tyInt8) - of tyInt16: result = handleRange(f, a, tyInt8, tyInt16) - of tyInt32: result = handleRange(f, a, tyInt8, tyInt32) - of tyInt64: result = handleRange(f, a, tyInt, tyInt64) - of tyUInt: result = handleRange(f, a, tyUInt8, tyUInt32) - of tyUInt8: result = handleRange(f, a, tyUInt8, tyUInt8) - of tyUInt16: result = handleRange(f, a, tyUInt8, tyUInt16) - of tyUInt32: result = handleRange(f, a, tyUInt8, tyUInt32) - of tyUInt64: result = handleRange(f, a, tyUInt, tyUInt64) + of tyInt: result = handleRange(c.c, f, a, tyInt8, c.c.config.targetSizeSignedToKind) + of tyInt8: result = handleRange(c.c, f, a, tyInt8, tyInt8) + of tyInt16: result = handleRange(c.c, f, a, tyInt8, tyInt16) + of tyInt32: result = handleRange(c.c, f, a, tyInt8, tyInt32) + of tyInt64: result = handleRange(c.c, f, a, tyInt, tyInt64) + of tyUInt: result = handleRange(c.c, f, a, tyUInt8, c.c.config.targetSizeUnsignedToKind) + of tyUInt8: result = handleRange(c.c, f, a, tyUInt8, tyUInt8) + of tyUInt16: result = handleRange(c.c, f, a, tyUInt8, tyUInt16) + of tyUInt32: result = handleRange(c.c, f, a, tyUInt8, tyUInt32) + of tyUInt64: result = handleRange(c.c, f, a, tyUInt, tyUInt64) of tyFloat: result = handleFloatRange(f, a) of tyFloat32: result = handleFloatRange(f, a) of tyFloat64: result = handleFloatRange(f, a) of tyFloat128: result = handleFloatRange(f, a) - of tyVar, tyLent: - if aOrig.kind == f.kind: result = typeRel(c, f.base, aOrig.base) - else: result = typeRel(c, f.base, aOrig, flags + {trNoCovariance}) + of tyVar: + let flags = if isOutParam(f): flags + {trIsOutParam} else: flags + if aOrig.kind == f.kind and (isOutParam(aOrig) == isOutParam(f)): + result = typeRel(c, f.base, aOrig.base, flags) + else: + result = typeRel(c, f.base, aOrig, flags + {trNoCovariance}) + subtypeCheck() + of tyLent: + if aOrig.kind == f.kind: + result = typeRel(c, f.base, aOrig.base, flags) + else: + result = typeRel(c, f.base, aOrig, flags + {trNoCovariance}) subtypeCheck() of tyArray: - case a.kind - of tyArray: - var fRange = f.sons[0] - var aRange = a.sons[0] - if fRange.kind == tyGenericParam: - var prev = PType(idTableGet(c.bindings, fRange)) + a = reduceToBase(a) + if a.kind == tyArray: + var fRange = f.indexType + var aRange = a.indexType + if fRange.kind in {tyGenericParam, tyAnything}: + var prev = idTableGet(c.bindings, fRange) if prev == nil: - put(c, fRange, a.sons[0]) + if typeRel(c, fRange, aRange) == isNone: + return isNone + put(c, fRange, a.indexType) fRange = a else: fRange = prev - let ff = f.sons[1].skipTypes({tyTypeDesc}) + let ff = f[1].skipTypes({tyTypeDesc}) # This typeDesc rule is wrong, see bug #7331 - let aa = a.sons[1] #.skipTypes({tyTypeDesc}) + let aa = a[1] #.skipTypes({tyTypeDesc}) - if f.sons[0].kind != tyGenericParam and aa.kind == tyEmpty: + if f.indexType.kind != tyGenericParam and aa.kind == tyEmpty: result = isGeneric else: - result = typeRel(c, ff, aa) - + result = typeRel(c, ff, aa, flags) if result < isGeneric: if nimEnableCovariance and trNoCovariance notin flags and @@ -1176,27 +1447,28 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, return isNone if fRange.rangeHasUnresolvedStatic: + if aRange.kind in {tyGenericParam} and aRange.reduceToBase() == aRange: + return return inferStaticsInRange(c, fRange, a) elif c.c.matchedConcept != nil and aRange.rangeHasUnresolvedStatic: return inferStaticsInRange(c, aRange, f) + elif result == isGeneric and concreteType(c, aa, ff) == nil: + return isNone else: if lengthOrd(c.c.config, fRange) != lengthOrd(c.c.config, aRange): result = isNone - else: discard of tyOpenArray, tyVarargs: - # varargs[expr] is special too but handled earlier. So we only need to - # handle varargs[stmt] which is the same as varargs[typed]: + # varargs[untyped] is special too but handled earlier. So we only need to + # handle varargs[typed]: if f.kind == tyVarargs: if tfVarargs in a.flags: - return typeRel(c, f.base, a.lastSon) - if tfOldSchoolExprStmt in f.sons[0].flags: - if f.sons[0].kind == tyExpr: return - elif f.sons[0].kind == tyStmt: return + return typeRel(c, f.base, a.elementType, flags) + if f[0].kind == tyTyped: return template matchArrayOrSeq(aBase: PType) = let ff = f.base let aa = aBase - let baseRel = typeRel(c, ff, aa) + let baseRel = typeRel(c, ff, aa, flags) if baseRel >= isGeneric: result = isConvertible elif nimEnableCovariance and @@ -1207,33 +1479,32 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, case a.kind of tyOpenArray, tyVarargs: - result = typeRel(c, base(f), base(a)) + result = typeRel(c, base(f), base(a), flags) if result < isGeneric: result = isNone of tyArray: - if (f.sons[0].kind != tyGenericParam) and (a.sons[1].kind == tyEmpty): + if (f[0].kind != tyGenericParam) and (a.elementType.kind == tyEmpty): return isSubtype - matchArrayOrSeq(a.sons[1]) + matchArrayOrSeq(a.elementType) of tySequence: - if (f.sons[0].kind != tyGenericParam) and (a.sons[0].kind == tyEmpty): + if (f[0].kind != tyGenericParam) and (a.elementType.kind == tyEmpty): return isConvertible - matchArrayOrSeq(a.sons[0]) + matchArrayOrSeq(a.elementType) of tyString: if f.kind == tyOpenArray: - if f.sons[0].kind == tyChar: + if f[0].kind == tyChar: result = isConvertible - elif f.sons[0].kind == tyGenericParam and a.len > 0 and - typeRel(c, base(f), base(a)) >= isGeneric: + elif f[0].kind == tyGenericParam and a.len > 0 and + typeRel(c, base(f), base(a), flags) >= isGeneric: result = isConvertible else: discard - of tySequence: - case a.kind - of tySequence: - if (f.sons[0].kind != tyGenericParam) and (a.sons[0].kind == tyEmpty): + of tySequence, tyUncheckedArray: + if a.kind == f.kind: + if (f[0].kind != tyGenericParam) and (a.elementType.kind == tyEmpty): result = isSubtype else: - let ff = f.sons[0] - let aa = a.sons[0] - result = typeRel(c, ff, aa) + let ff = f[0] + let aa = a.elementType + result = typeRel(c, ff, aa, flags) if result < isGeneric: if nimEnableCovariance and trNoCovariance notin flags and @@ -1242,17 +1513,15 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, result = isSubtype else: result = isNone - elif tfNotNil in f.flags and tfNotNil notin a.flags: - result = isNilConversion - of tyNil: result = f.allowsNil - else: discard + elif a.kind == tyNil: + result = isNone of tyOrdinal: if isOrdinalType(a): - var x = if a.kind == tyOrdinal: a.sons[0] else: a - if f.sons[0].kind == tyNone: + var x = if a.kind == tyOrdinal: a.elementType else: a + if f[0].kind == tyNone: result = isGeneric else: - result = typeRel(c, f.sons[0], x) + result = typeRel(c, f[0], x, flags) if result < isGeneric: result = isNone elif a.kind == tyGenericParam: result = isGeneric @@ -1260,53 +1529,71 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, #internalError("forward type in typeRel()") result = isNone of tyNil: + skipOwned(a) if a.kind == f.kind: result = isEqual of tyTuple: - if a.kind == tyTuple: result = recordRel(c, f, a) + if a.kind == tyTuple: result = recordRel(c, f, a, flags) of tyObject: - if a.kind == tyObject: - if sameObjectTypes(f, a): + let effectiveArgType = if useTypeLoweringRuleInTypeClass: + a + else: + reduceToBase(a) + if effectiveArgType.kind == tyObject: + if sameObjectTypes(f, effectiveArgType): + c.inheritancePenalty = if tfFinal in f.flags: -1 else: 0 result = isEqual # elif tfHasMeta in f.flags: result = recordRel(c, f, a) - else: - var depth = isObjectSubtype(c, a, f, nil) - if depth > 0: - inc(c.inheritancePenalty, depth) + elif trIsOutParam notin flags: + c.inheritancePenalty = isObjectSubtype(c, effectiveArgType, f, nil) + if c.inheritancePenalty > 0: result = isSubtype of tyDistinct: + a = a.skipTypes({tyOwned, tyGenericInst, tyRange}) if a.kind == tyDistinct: if sameDistinctTypes(f, a): result = isEqual - elif f.base.kind == tyAnything: result = isGeneric - elif c.coerceDistincts: result = typeRel(c, f.base, a) - elif a.kind == tyNil and f.base.kind in NilableTypes: - result = f.allowsNil - elif c.coerceDistincts: result = typeRel(c, f.base, a) + #elif f.base.kind == tyAnything: result = isGeneric # issue 4435 + elif c.coerceDistincts: result = typeRel(c, f.base, a, flags) + elif c.coerceDistincts: result = typeRel(c, f.base, a, flags) of tySet: if a.kind == tySet: - if f.sons[0].kind != tyGenericParam and a.sons[0].kind == tyEmpty: + if f[0].kind != tyGenericParam and a[0].kind == tyEmpty: result = isSubtype else: - result = typeRel(c, f.sons[0], a.sons[0]) - if result <= isConvertible: - result = isNone # BUGFIX! + result = typeRel(c, f[0], a[0], flags) + if result < isGeneric: + if tfIsConstructor notin a.flags: + # set['a'..'z'] and set[char] have different representations + result = isNone + else: + # but we can convert individual elements of the constructor + result = isConvertible of tyPtr, tyRef: + a = reduceToBase(a) if a.kind == f.kind: # ptr[R, T] can be passed to ptr[T], but not the other way round: if a.len < f.len: return isNone - for i in 0..f.len-2: - if typeRel(c, f.sons[i], a.sons[i]) == isNone: return isNone - result = typeRel(c, f.lastSon, a.lastSon, flags + {trNoCovariance}) + for i in 0..<f.len-1: + if typeRel(c, f[i], a[i], flags) == isNone: return isNone + result = typeRel(c, f.elementType, a.elementType, flags + {trNoCovariance}) subtypeCheck() - if result <= isConvertible: result = isNone + if result <= isIntConv: result = isNone elif tfNotNil in f.flags and tfNotNil notin a.flags: result = isNilConversion elif a.kind == tyNil: result = f.allowsNil else: discard of tyProc: + skipOwned(a) result = procTypeRel(c, f, a) if result != isNone and tfNotNil in f.flags and tfNotNil notin a.flags: result = isNilConversion + of tyOwned: + case a.kind + of tyOwned: + result = typeRel(c, skipModifier(f), skipModifier(a), flags) + of tyNil: result = f.allowsNil + else: discard of tyPointer: + skipOwned(a) case a.kind of tyPointer: if tfNotNil in f.flags and tfNotNil notin a.flags: @@ -1315,26 +1602,25 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, result = isEqual of tyNil: result = f.allowsNil of tyProc: - if a.callConv != ccClosure: result = isConvertible + if isDefined(c.c.config, "nimPreviewProcConversion"): + result = isNone + else: + if a.callConv != ccClosure: result = isConvertible of tyPtr: # 'pointer' is NOT compatible to regionized pointers # so 'dealloc(regionPtr)' fails: if a.len == 1: result = isConvertible - of tyCString: result = isConvertible + of tyCstring: result = isConvertible else: discard of tyString: case a.kind - of tyString: - if tfNotNil in f.flags and tfNotNil notin a.flags: - result = isNilConversion - else: - result = isEqual - of tyNil: result = f.allowsNil + of tyString: result = isEqual + of tyNil: result = isNone else: discard - of tyCString: + of tyCstring: # conversion from string to cstring is automatic: case a.kind - of tyCString: + of tyCstring: if tfNotNil in f.flags and tfNotNil notin a.flags: result = isNilConversion else: @@ -1342,64 +1628,81 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, of tyNil: result = f.allowsNil of tyString: result = isConvertible of tyPtr: - # ptr[Tag, char] is not convertible to 'cstring' for now: - if a.len == 1: - let pointsTo = a.sons[0].skipTypes(abstractInst) - if pointsTo.kind == tyChar: result = isConvertible - elif pointsTo.kind == tyArray and firstOrd(nil, pointsTo.sons[0]) == 0 and - skipTypes(pointsTo.sons[0], {tyRange}).kind in {tyInt..tyInt64} and - pointsTo.sons[1].kind == tyChar: - result = isConvertible + if isDefined(c.c.config, "nimPreviewCstringConversion"): + result = isNone + else: + if a.len == 1: + let pointsTo = a[0].skipTypes(abstractInst) + if pointsTo.kind == tyChar: result = isConvertible + elif pointsTo.kind == tyUncheckedArray and pointsTo[0].kind == tyChar: + result = isConvertible + elif pointsTo.kind == tyArray and firstOrd(nil, pointsTo[0]) == 0 and + skipTypes(pointsTo[0], {tyRange}).kind in {tyInt..tyInt64} and + pointsTo[1].kind == tyChar: + result = isConvertible else: discard - of tyEmpty, tyVoid: if a.kind == f.kind: result = isEqual - of tyAlias, tySink: - result = typeRel(c, lastSon(f), a) - + result = typeRel(c, skipModifier(f), a, flags) + of tyIterable: + if a.kind == tyIterable: + if f.len == 1: + result = typeRel(c, skipModifier(f), skipModifier(a), flags) + else: + # f.len = 3, for some reason + result = isGeneric + else: + result = isNone of tyGenericInst: - var prev = PType(idTableGet(c.bindings, f)) + var prev = idTableGet(c.bindings, f) + let origF = f var f = if prev == nil: f else: prev - let roota = a.skipGenericAlias - let rootf = f.skipGenericAlias + let deptha = a.genericAliasDepth() + let depthf = f.genericAliasDepth() + let skipBoth = deptha == depthf and (a.len > 0 and f.len > 0 and a.base != f.base) + + let roota = if skipBoth or deptha > depthf: a.skipGenericAlias else: a + let rootf = if skipBoth or depthf > deptha: f.skipGenericAlias else: f - var m = c if a.kind == tyGenericInst: if roota.base == rootf.base: let nextFlags = flags + {trNoCovariance} var hasCovariance = false - for i in 1 .. rootf.sonsLen-2: - let ff = rootf.sons[i] - let aa = roota.sons[i] - result = typeRel(c, ff, aa, nextFlags) - if result notin {isEqual, isGeneric}: + # YYYY + result = isEqual + + for i in 1..<rootf.len-1: + let ff = rootf[i] + let aa = roota[i] + let res = typeRel(c, ff, aa, nextFlags) + if res != isNone and res != isEqual: result = isGeneric + if res notin {isEqual, isGeneric}: if trNoCovariance notin flags and ff.kind == aa.kind: - let paramFlags = rootf.base.sons[i-1].flags + let paramFlags = rootf.base[i-1].flags hasCovariance = if tfCovariant in paramFlags: if tfWeakCovariant in paramFlags: isCovariantPtr(c, ff, aa) else: - ff.kind notin {tyRef, tyPtr} and result == isSubtype + ff.kind notin {tyRef, tyPtr} and res == isSubtype else: tfContravariant in paramFlags and - typeRel(c, aa, ff) == isSubtype + typeRel(c, aa, ff, flags) == isSubtype if hasCovariance: continue return isNone if prev == nil: put(c, f, a) - result = isGeneric else: - let fKind = rootf.lastSon.kind + let fKind = rootf.last.kind if fKind in {tyAnd, tyOr}: - result = typeRel(c, lastSon(f), a) + result = typeRel(c, last(f), a, flags) if result != isNone: put(c, f, a) return - var aAsObject = roota.lastSon + var aAsObject = roota.last if fKind in {tyRef, tyPtr}: if aAsObject.kind == tyObject: @@ -1409,61 +1712,69 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, elif aAsObject.kind == fKind: aAsObject = aAsObject.base - if aAsObject.kind == tyObject: + if aAsObject.kind == tyObject and trIsOutParam notin flags: let baseType = aAsObject.base if baseType != nil: - c.inheritancePenalty += 1 - return typeRel(c, f, baseType) + inc c.inheritancePenalty, 1 + int(c.inheritancePenalty < 0) + let ret = typeRel(c, f, baseType, flags) + return if ret in {isEqual,isGeneric}: isSubtype else: ret result = isNone else: - result = typeRel(c, lastSon(f), a) + assert last(origF) != nil + result = typeRel(c, last(origF), a, flags) if result != isNone and a.kind != tyNil: put(c, f, a) - of tyGenericBody: considerPreviousT: - if a.kind == tyGenericInst and a.sons[0] == f: + if a == f or a.kind == tyGenericInst and a.skipGenericAlias[0] == f: bindingRet isGeneric - let ff = lastSon(f) + let ff = last(f) if ff != nil: - result = typeRel(c, ff, a) - + result = typeRel(c, ff, a, flags) of tyGenericInvocation: var x = a.skipGenericAlias + if x.kind == tyGenericParam and x.len > 0: + x = x.last + let concpt = f[0].skipTypes({tyGenericBody}) + var preventHack = concpt.kind == tyConcept + if x.kind == tyOwned and f[0].kind != tyOwned: + preventHack = true + x = x.last # XXX: This is very hacky. It should be moved back into liftTypeParam if x.kind in {tyGenericInst, tyArray} and - c.calleeSym != nil and - c.calleeSym.kind in {skProc, skFunc} and c.call != nil: + c.calleeSym != nil and + c.calleeSym.kind in {skProc, skFunc} and c.call != nil and not preventHack: let inst = prepareMetatypeForSigmatch(c.c, c.bindings, c.call.info, f) - return typeRel(c, inst, a) - - var depth = 0 - if x.kind == tyGenericInvocation or f.sons[0].kind != tyGenericBody: - #InternalError("typeRel: tyGenericInvocation -> tyGenericInvocation") - # simply no match for now: - discard - elif x.kind == tyGenericInst and - ((f.sons[0] == x.sons[0]) or isGenericSubType(c, x, f, depth)) and - (sonsLen(x) - 1 == sonsLen(f)): - for i in countup(1, sonsLen(f) - 1): - if x.sons[i].kind == tyGenericParam: + return typeRel(c, inst, a, flags) + + if x.kind == tyGenericInvocation: + if f[0] == x[0]: + for i in 1..<f.len: + # Handle when checking against a generic that isn't fully instantiated + if i >= x.len: return + let tr = typeRel(c, f[i], x[i], flags) + if tr <= isSubtype: return + result = isGeneric + elif x.kind == tyGenericInst and f[0] == x[0] and + x.len - 1 == f.len: + for i in 1..<f.len: + if x[i].kind == tyGenericParam: internalError(c.c.graph.config, "wrong instantiated type!") - elif typeRel(c, f.sons[i], x.sons[i]) <= isSubtype: + elif typeRel(c, f[i], x[i], flags) <= isSubtype: # Workaround for regression #4589 - if f.sons[i].kind != tyTypeDesc: return - c.inheritancePenalty += depth + if f[i].kind != tyTypeDesc: return result = isGeneric + elif x.kind == tyGenericInst and concpt.kind == tyConcept: + result = if concepts.conceptMatch(c.c, concpt, x, c.bindings, f): isGeneric + else: isNone else: - let genericBody = f.sons[0] + let genericBody = f[0] var askip = skippedNone var fskip = skippedNone let aobj = x.skipToObject(askip) - let fobj = genericBody.lastSon.skipToObject(fskip) - var depth = -1 - if fobj != nil and aobj != nil and askip == fskip: - depth = isObjectSubtype(c, aobj, fobj, f) - result = typeRel(c, genericBody, x) + let fobj = genericBody.last.skipToObject(fskip) + result = typeRel(c, genericBody, x, flags) if result != isNone: # see tests/generics/tgeneric3.nim for an example that triggers this # piece of code: @@ -1475,90 +1786,99 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, # var it1 = internalFind(root, 312) # cannot instantiate: 'D' # # we steal the generic parameters from the tyGenericBody: - for i in countup(1, sonsLen(f) - 1): - let x = PType(idTableGet(c.bindings, genericBody.sons[i-1])) + for i in 1..<f.len: + let x = idTableGet(c.bindings, genericBody[i-1]) if x == nil: - discard "maybe fine (for eg. a==tyNil)" + discard "maybe fine (for e.g. a==tyNil)" elif x.kind in {tyGenericInvocation, tyGenericParam}: internalError(c.c.graph.config, "wrong instantiated type!") else: - put(c, f.sons[i], x) + let key = f[i] + let old = idTableGet(c.bindings, key) + if old == nil: + put(c, key, x) + elif typeRel(c, old, x, flags + {trDontBind}) == isNone: + return isNone + var depth = -1 + if fobj != nil and aobj != nil and askip == fskip: + depth = isObjectSubtype(c, aobj, fobj, f) if result == isNone: # Here object inheriting from generic/specialized generic object # crossing path with metatypes/aliases, so we need to separate them # by checking sym.id - let genericSubtype = isGenericSubType(c, x, f, depth, f) + let genericSubtype = isGenericSubtype(c, x, f, depth, f) if not (genericSubtype and aobj.sym.id != fobj.sym.id) and aOrig.kind != tyGenericBody: depth = -1 if depth >= 0: - c.inheritancePenalty += depth + inc c.inheritancePenalty, depth + int(c.inheritancePenalty < 0) # bug #4863: We still need to bind generic alias crap, so # we cannot return immediately: result = if depth == 0: isGeneric else: isSubtype of tyAnd: considerPreviousT: result = isEqual - for branch in f.sons: - let x = typeRel(c, branch, aOrig) + for branch in f.kids: + let x = typeRel(c, branch, aOrig, flags) if x < isSubtype: return isNone # 'and' implies minimum matching result: if x < result: result = x if result > isGeneric: result = isGeneric bindingRet result - of tyOr: considerPreviousT: result = isNone let oldInheritancePenalty = c.inheritancePenalty - var maxInheritance = 0 - for branch in f.sons: - c.inheritancePenalty = 0 - let x = typeRel(c, branch, aOrig) - maxInheritance = max(maxInheritance, c.inheritancePenalty) - - # 'or' implies maximum matching result: - if x > result: result = x - if result >= isSubtype: + var minInheritance = maxInheritancePenalty + for branch in f.kids: + c.inheritancePenalty = -1 + let x = typeRel(c, branch, aOrig, flags) + if x >= result: + if c.inheritancePenalty > -1: + minInheritance = min(minInheritance, c.inheritancePenalty) + result = x + if result >= isIntConv: + if minInheritance < maxInheritancePenalty: + c.inheritancePenalty = oldInheritancePenalty + minInheritance if result > isGeneric: result = isGeneric bindingRet result else: result = isNone - c.inheritancePenalty = oldInheritancePenalty + maxInheritance - of tyNot: considerPreviousT: - for branch in f.sons: - if typeRel(c, branch, aOrig) != isNone: - return isNone + if typeRel(c, f.elementType, aOrig, flags) != isNone: + return isNone bindingRet isGeneric - of tyAnything: considerPreviousT: var concrete = concreteType(c, a) if concrete != nil and doBind: put(c, f, concrete) return isGeneric - of tyBuiltInTypeClass: considerPreviousT: - let targetKind = f.sons[0].kind - let effectiveArgType = a.skipTypes({tyRange, tyGenericInst, - tyBuiltInTypeClass, tyAlias, tySink}) - let typeClassMatches = targetKind == effectiveArgType.kind and - not effectiveArgType.isEmptyContainer - if typeClassMatches or - (targetKind in {tyProc, tyPointer} and effectiveArgType.kind == tyNil): - put(c, f, a) + let target = f.genericHead + let targetKind = target.kind + var effectiveArgType = reduceToBase(a) + effectiveArgType = effectiveArgType.skipTypes({tyBuiltInTypeClass}) + if targetKind == effectiveArgType.kind: + if effectiveArgType.isEmptyContainer: + return isNone + if targetKind == tyProc: + if target.flags * {tfIterator} != effectiveArgType.flags * {tfIterator}: + return isNone + if tfExplicitCallConv in target.flags and + target.callConv != effectiveArgType.callConv: + return isNone + if doBind: put(c, f, a) return isGeneric else: return isNone - of tyUserTypeClassInst, tyUserTypeClass: if f.isResolvedUserTypeClass: - result = typeRel(c, f.lastSon, a) + result = typeRel(c, f.last, a, flags) else: considerPreviousT: if aOrig == f: return isEqual @@ -1567,31 +1887,41 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, bindConcreteTypeToUserTypeClass(matched, a) if doBind: put(c, f, matched) result = isGeneric + elif a.len > 0 and a.last == f: + # Needed for checking `Y` == `Addable` in the following + #[ + type + Addable = concept a, type A + a + a is A + MyType[T: Addable; Y: static T] = object + ]# + result = isGeneric else: result = isNone - + of tyConcept: + result = if concepts.conceptMatch(c.c, f, a, c.bindings, nil): isGeneric + else: isNone of tyCompositeTypeClass: considerPreviousT: let roota = a.skipGenericAlias - let rootf = f.lastSon.skipGenericAlias + let rootf = f.last.skipGenericAlias if a.kind == tyGenericInst and roota.base == rootf.base: - for i in 1 .. rootf.sonsLen-2: - let ff = rootf.sons[i] - let aa = roota.sons[i] - result = typeRel(c, ff, aa) + for i in 1..<rootf.len-1: + let ff = rootf[i] + let aa = roota[i] + result = typeRel(c, ff, aa, flags) if result == isNone: return if ff.kind == tyRange and result != isEqual: return isNone else: - result = typeRel(c, rootf.lastSon, a) + result = typeRel(c, rootf.last, a, flags) if result != isNone: put(c, f, a) result = isGeneric - of tyGenericParam: - var x = PType(idTableGet(c.bindings, f)) + let doBindGP = doBind or trBindGenericParam in flags + var x = idTableGet(c.bindings, f) if x == nil: - if c.callee.kind == tyGenericBody and - f.kind == tyGenericParam and not c.typedescMatched: + if c.callee.kind == tyGenericBody and not c.typedescMatched: # XXX: The fact that generic types currently use tyGenericParam for # their parameters is really a misnomer. tyGenericParam means "match # any value" and what we need is "match any type", which can be encoded @@ -1600,48 +1930,60 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, if tfWildcard in a.flags: result = isGeneric elif a.kind == tyTypeDesc: - if f.sonsLen == 0: + if f.len == 0: result = isGeneric else: - internalAssert c.c.graph.config, a.sons != nil and a.sons.len > 0 + internalAssert c.c.graph.config, a.len > 0 c.typedescMatched = true var aa = a while aa.kind in {tyTypeDesc, tyGenericParam} and aa.len > 0: - aa = lastSon(aa) - if aa.kind == tyGenericParam: + aa = last(aa) + if aa.kind in {tyGenericParam} + tyTypeClasses: + # If the constraint is a genericParam or typeClass this isGeneric return isGeneric - result = typeRel(c, f.base, aa) + result = typeRel(c, f.base, aa, flags) if result > isGeneric: result = isGeneric + elif c.isNoCall: + if doBindGP: + let concrete = concreteType(c, a, f) + if concrete == nil: return isNone + put(c, f, concrete) + result = isGeneric else: result = isNone else: - if f.sonsLen > 0 and f.sons[0].kind != tyNone: - let oldInheritancePenalty = c.inheritancePenalty - result = typeRel(c, f.lastSon, a, flags + {trDontBind}) - if doBind and result notin {isNone, isGeneric}: - let concrete = concreteType(c, a) + # check if 'T' has a constraint as in 'proc p[T: Constraint](x: T)' + if f.len > 0 and f[0].kind != tyNone: + result = typeRel(c, f[0], a, flags + {trDontBind, trBindGenericParam}) + if doBindGP and result notin {isNone, isGeneric}: + let concrete = concreteType(c, a, f) if concrete == nil: return isNone put(c, f, concrete) - # bug #6526 if result in {isEqual, isSubtype}: - # 'T: Class' is a *better* match than just 'T' - # but 'T: Subclass' is even better: - c.inheritancePenalty = oldInheritancePenalty - c.inheritancePenalty - - 100 * ord(result == isEqual) result = isGeneric + elif a.kind == tyTypeDesc: + # somewhat special typing rule, the following is illegal: + # proc p[T](x: T) + # p(int) + result = isNone else: result = isGeneric if result == isGeneric: var concrete = a if tfWildcard in a.flags: - a.sym.kind = skType + a.sym.transitionGenericParamToType() a.flags.excl tfWildcard - else: - concrete = concreteType(c, a) + elif doBind: + # careful: `trDontDont` (set by `checkGeneric`) is not always respected in this call graph. + # typRel having two different modes (binding and non-binding) can make things harder to + # reason about and maintain. Refactoring typeRel to not be responsible for setting, or + # at least validating, bindings can have multiple benefits. This is debatable. I'm not 100% sure. + # A design that allows a proper complexity analysis of types like `tyOr` would be ideal. + concrete = concreteType(c, a, f) if concrete == nil: return isNone - if doBind: + if doBindGP: put(c, f, concrete) elif result > isGeneric: result = isGeneric @@ -1650,117 +1992,167 @@ proc typeRelImpl(c: var TCandidate, f, aOrig: PType, elif x.kind == tyGenericParam: result = isGeneric else: - # Special type binding rule for numeric types. - # See section "Generic type inference for numeric types" of the - # manual for further details: - when false: - let rebinding = maxNumericType(x.skipTypes({tyRange}), a) - if rebinding != nil: - put(c, f, rebinding) - result = isGeneric - else: - discard - result = typeRel(c, x, a) # check if it fits + # This is the bound type - can't benifit from these tallies + let + inheritancePenaltyOld = c.inheritancePenalty + result = typeRel(c, x, a, flags) # check if it fits + c.inheritancePenalty = inheritancePenaltyOld if result > isGeneric: result = isGeneric of tyStatic: - let prev = PType(idTableGet(c.bindings, f)) + let prev = idTableGet(c.bindings, f) if prev == nil: if aOrig.kind == tyStatic: - result = typeRel(c, f.lastSon, a) - if result != isNone and f.n != nil: - if not exprStructuralEquivalent(f.n, aOrig.n): - result = isNone + if c.c.inGenericContext > 0 and aOrig.n == nil and not c.isNoCall: + # don't match unresolved static value to static param to avoid + # faulty instantiations in calls in generic bodies + # but not for generic invocations as they only check constraints + result = isNone + elif f.base.kind notin {tyNone, tyGenericParam}: + result = typeRel(c, f.base, a, flags) + if result != isNone and f.n != nil: + var r = tryResolvingStaticExpr(c, f.n) + if r == nil: r = f.n + if not exprStructuralEquivalent(r, aOrig.n) and + not (aOrig.n != nil and aOrig.n.kind == nkIntLit and + inferStaticParam(c, r, aOrig.n.intVal)): + result = isNone + elif f.base.kind == tyGenericParam: + # Handling things like `type A[T; Y: static T] = object` + if f.base.len > 0: # There is a constraint, handle it + result = typeRel(c, f.base.last, a, flags) + else: + # No constraint + if tfGenericTypeParam in f.flags: + result = isGeneric + else: + # for things like `proc fun[T](a: static[T])` + result = typeRel(c, f.base, a, flags) + else: + result = isGeneric if result != isNone: put(c, f, aOrig) elif aOrig.n != nil and aOrig.n.typ != nil: - result = typeRel(c, f.lastSon, aOrig.n.typ) + result = if f.base.kind != tyNone: + typeRel(c, f.last, aOrig.n.typ, flags) + else: isGeneric if result != isNone: - var boundType = newTypeWithSons(c.c, tyStatic, @[aOrig.n.typ]) + var boundType = newTypeS(tyStatic, c.c, aOrig.n.typ) boundType.n = aOrig.n put(c, f, boundType) else: result = isNone elif prev.kind == tyStatic: if aOrig.kind == tyStatic: - result = typeRel(c, prev.lastSon, a) + result = typeRel(c, prev.last, a, flags) if result != isNone and prev.n != nil: if not exprStructuralEquivalent(prev.n, aOrig.n): result = isNone else: result = isNone else: # XXX endless recursion? - #result = typeRel(c, prev, aOrig) + #result = typeRel(c, prev, aOrig, flags) result = isNone - of tyInferred: let prev = f.previouslyInferred if prev != nil: - result = typeRel(c, prev, a) + result = typeRel(c, prev, a, flags) else: - result = typeRel(c, f.base, a) + result = typeRel(c, f.base, a, flags) if result != isNone: - c.inferredTypes.safeAdd f - f.sons.add a - + c.inferredTypes.add f + f.add a of tyTypeDesc: - var prev = PType(idTableGet(c.bindings, f)) + var prev = idTableGet(c.bindings, f) if prev == nil: # proc foo(T: typedesc, x: T) # when `f` is an unresolved typedesc, `a` could be any # type, so we should not perform this check earlier - if a.kind != tyTypeDesc: return isNone - - if f.base.kind == tyNone: + if c.c.inGenericContext > 0 and a.containsUnresolvedType: + # generic type bodies can sometimes compile call expressions + # prevent unresolved generic parameters from being passed to procs as + # typedesc parameters + result = isNone + elif a.kind != tyTypeDesc: + if a.kind == tyGenericParam and tfWildcard in a.flags: + # TODO: prevent `a` from matching as a wildcard again + result = isGeneric + else: + result = isNone + elif f.base.kind == tyNone: result = isGeneric else: - result = typeRel(c, f.base, a.base) + result = typeRel(c, f.base, a.base, flags) if result != isNone: put(c, f, a) else: if tfUnresolved in f.flags: - result = typeRel(c, prev.base, a) + result = typeRel(c, prev.base, a, flags) elif a.kind == tyTypeDesc: - result = typeRel(c, prev.base, a.base) + result = typeRel(c, prev.base, a.base, flags) else: result = isNone - - of tyStmt: - if aOrig != nil and tfOldSchoolExprStmt notin f.flags: + of tyTyped: + if aOrig != nil: put(c, f, aOrig) result = isGeneric - - of tyProxy: + of tyError: result = isEqual - of tyFromExpr: # fix the expression, so it contains the already instantiated types if f.n == nil or f.n.kind == nkEmpty: return isGeneric - let reevaluated = tryResolvingStaticExpr(c, f.n) - case reevaluated.typ.kind + if c.c.inGenericContext > 0: + # need to delay until instantiation + # also prevent infinite recursion below + return isNone + inc c.c.inGenericContext # to generate tyFromExpr again if unresolved + # use prepareNode for consistency with other tyFromExpr in semtypinst: + let instantiated = prepareTypesInBody(c.c, c.bindings, f.n) + let reevaluated = c.c.semExpr(c.c, instantiated).typ + dec c.c.inGenericContext + case reevaluated.kind + of tyFromExpr: + # not resolved + result = isNone of tyTypeDesc: - result = typeRel(c, a, reevaluated.typ.base) + result = typeRel(c, reevaluated.base, a, flags) of tyStatic: - result = typeRel(c, a, reevaluated.typ.base) - if result != isNone and reevaluated.typ.n != nil: - if not exprStructuralEquivalent(aOrig.n, reevaluated.typ.n): + result = typeRel(c, reevaluated.base, a, flags) + if result != isNone and reevaluated.n != nil: + if not exprStructuralEquivalent(aOrig.n, reevaluated.n): result = isNone else: - localError(c.c.graph.config, f.n.info, "type expected") - result = isNone - + # bug #14136: other types are just like 'tyStatic' here: + result = typeRel(c, reevaluated, a, flags) + if result != isNone and reevaluated.n != nil: + if not exprStructuralEquivalent(aOrig.n, reevaluated.n): + result = isNone of tyNone: if a.kind == tyNone: result = isEqual else: internalError c.c.graph.config, " unknown type kind " & $f.kind +when false: + var nowDebug = false + var dbgCount = 0 + + proc typeRel(c: var TCandidate, f, aOrig: PType, + flags: TTypeRelFlags = {}): TTypeRelation = + if nowDebug: + echo f, " <- ", aOrig + inc dbgCount + if dbgCount == 2: + writeStackTrace() + result = typeRelImpl(c, f, aOrig, flags) + if nowDebug: + echo f, " <- ", aOrig, " res ", result + proc cmpTypes*(c: PContext, f, a: PType): TTypeRelation = - var m: TCandidate - initCandidate(c, m, f) + var m = newCandidate(c, f) result = typeRel(m, f, a) proc getInstantiatedType(c: PContext, arg: PNode, m: TCandidate, f: PType): PType = - result = PType(idTableGet(m.bindings, f)) + result = idTableGet(m.bindings, f) if result == nil: result = generateTypeInstance(c, m.bindings, arg, f) if result == nil: @@ -1771,42 +2163,166 @@ proc implicitConv(kind: TNodeKind, f: PType, arg: PNode, m: TCandidate, c: PContext): PNode = result = newNodeI(kind, arg.info) if containsGenericType(f): - if not m.hasFauxMatch: - result.typ = getInstantiatedType(c, arg, m, f) + if not m.matchedErrorType: + result.typ = getInstantiatedType(c, arg, m, f).skipTypes({tySink}) else: result.typ = errorType(c) else: - result.typ = f + result.typ = f.skipTypes({tySink}) + # keep varness + if arg.typ != nil and arg.typ.kind == tyVar: + result.typ = toVar(result.typ, tyVar, c.idgen) + else: + result.typ = result.typ.skipTypes({tyVar}) + if result.typ == nil: internalError(c.graph.config, arg.info, "implicitConv") - addSon(result, c.graph.emptyNode) - addSon(result, arg) + result.add c.graph.emptyNode + if arg.typ != nil and arg.typ.kind == tyLent: + let a = newNodeIT(nkHiddenDeref, arg.info, arg.typ.elementType) + a.add arg + result.add a + else: + result.add arg + +proc convertLiteral(kind: TNodeKind, c: PContext, m: TCandidate; n: PNode, newType: PType): PNode = + # based off changeType but generates implicit conversions instead + template addConsiderNil(s, node) = + let val = node + if val.isNil: return nil + s.add(val) + case n.kind + of nkCurly: + result = copyNode(n) + for i in 0..<n.len: + if n[i].kind == nkRange: + var x = copyNode(n[i]) + x.addConsiderNil convertLiteral(kind, c, m, n[i][0], elemType(newType)) + x.addConsiderNil convertLiteral(kind, c, m, n[i][1], elemType(newType)) + result.add x + else: + result.addConsiderNil convertLiteral(kind, c, m, n[i], elemType(newType)) + result.typ = newType + return + of nkBracket: + result = copyNode(n) + for i in 0..<n.len: + result.addConsiderNil convertLiteral(kind, c, m, n[i], elemType(newType)) + result.typ = newType + return + of nkPar, nkTupleConstr: + let tup = newType.skipTypes({tyGenericInst, tyAlias, tySink, tyDistinct}) + if tup.kind == tyTuple: + result = copyNode(n) + if n.len > 0 and n[0].kind == nkExprColonExpr: + # named tuple? + for i in 0..<n.len: + var name = n[i][0] + if name.kind != nkSym: + #globalError(c.config, name.info, "invalid tuple constructor") + return nil + if tup.n != nil: + var f = getSymFromList(tup.n, name.sym.name) + if f == nil: + #globalError(c.config, name.info, "unknown identifier: " & name.sym.name.s) + return nil + result.addConsiderNil convertLiteral(kind, c, m, n[i][1], f.typ) + else: + result.addConsiderNil convertLiteral(kind, c, m, n[i][1], tup[i]) + else: + for i in 0..<n.len: + result.addConsiderNil convertLiteral(kind, c, m, n[i], tup[i]) + result.typ = newType + return + of nkCharLit..nkUInt64Lit: + if n.kind != nkUInt64Lit and not sameTypeOrNil(n.typ, newType) and isOrdinalType(newType): + let value = n.intVal + if value < firstOrd(c.config, newType) or value > lastOrd(c.config, newType): + return nil + result = copyNode(n) + result.typ = newType + return + of nkFloatLit..nkFloat64Lit: + if newType.skipTypes(abstractVarRange-{tyTypeDesc}).kind == tyFloat: + if not floatRangeCheck(n.floatVal, newType): + return nil + result = copyNode(n) + result.typ = newType + return + of nkSym: + if n.sym.kind == skEnumField and not sameTypeOrNil(n.sym.typ, newType) and isOrdinalType(newType): + let value = n.sym.position + if value < firstOrd(c.config, newType) or value > lastOrd(c.config, newType): + return nil + result = copyNode(n) + result.typ = newType + return + else: discard + return implicitConv(kind, newType, n, m, c) + +proc isLValue(c: PContext; n: PNode, isOutParam = false): bool {.inline.} = + let aa = isAssignable(nil, n) + case aa + of arLValue, arLocalLValue, arStrange: + result = true + of arDiscriminant: + result = c.inUncheckedAssignSection > 0 + of arAddressableConst: + let sym = getRoot(n) + result = strictDefs in c.features and sym != nil and sym.kind == skLet and isOutParam + else: + result = false proc userConvMatch(c: PContext, m: var TCandidate, f, a: PType, arg: PNode): PNode = result = nil - for i in countup(0, len(c.converters) - 1): - var src = c.converters[i].typ.sons[1] - var dest = c.converters[i].typ.sons[0] + for i in 0..<c.converters.len: + var src = c.converters[i].typ.firstParamType + var dest = c.converters[i].typ.returnType # for generic type converters we need to check 'src <- a' before # 'f <- dest' in order to not break the unification: # see tests/tgenericconverter: let srca = typeRel(m, src, a) - if srca notin {isEqual, isGeneric}: continue + if srca notin {isEqual, isGeneric, isSubtype}: continue + + # What's done below matches the logic in ``matchesAux`` + let constraint = c.converters[i].typ.n[1].sym.constraint + if not constraint.isNil and not matchNodeKinds(constraint, arg): + continue + if src.kind in {tyVar, tyLent} and not isLValue(c, arg): + continue let destIsGeneric = containsGenericType(dest) if destIsGeneric: dest = generateTypeInstance(c, m.bindings, arg, dest) let fdest = typeRel(m, f, dest) - if fdest in {isEqual, isGeneric}: - markUsed(c.config, arg.info, c.converters[i], c.graph.usageSym) + if fdest in {isEqual, isGeneric} and not (dest.kind == tyLent and f.kind in {tyVar}): + markUsed(c, arg.info, c.converters[i]) var s = newSymNode(c.converters[i]) s.typ = c.converters[i].typ s.info = arg.info result = newNodeIT(nkHiddenCallConv, arg.info, dest) - addSon(result, s) - addSon(result, copyTree(arg)) + result.add s + # We build the call expression by ourselves in order to avoid passing this + # expression trough the semantic check phase once again so let's make sure + # it is correct + var param: PNode = nil + if srca == isSubtype: + param = implicitConv(nkHiddenSubConv, src, copyTree(arg), m, c) + elif src.kind in {tyVar}: + # Analyse the converter return type. + param = newNodeIT(nkHiddenAddr, arg.info, s.typ.firstParamType) + param.add copyTree(arg) + else: + param = copyTree(arg) + result.add param + + if dest.kind in {tyVar, tyLent}: + dest.flags.incl tfVarIsPtr + result = newDeref(result) + inc(m.convMatches) - m.genericConverter = srca == isGeneric or destIsGeneric + if not m.genericConverter: + m.genericConverter = srca == isGeneric or destIsGeneric return result proc localConvMatch(c: PContext, m: var TCandidate, f, a: PType, @@ -1821,13 +2337,18 @@ proc localConvMatch(c: PContext, m: var TCandidate, f, a: PType, var call = newNodeI(nkCall, arg.info) call.add(f.n.copyTree) call.add(arg.copyTree) - result = c.semExpr(c, call) + # XXX: This would be much nicer if we don't use `semTryExpr` and + # instead we directly search for overloads with `resolveOverloads`: + result = c.semTryExpr(c, call, {efNoSem2Check}) + if result != nil: if result.typ == nil: return nil + # bug #13378, ensure we produce a real generic instantiation: + result = c.semExpr(c, call, {efNoSem2Check}) # resulting type must be consistent with the other arguments: - var r = typeRel(m, f.sons[0], result.typ) + var r = typeRel(m, f[0], result.typ) if r < isGeneric: return nil - if result.kind == nkCall: result.kind = nkHiddenCallConv + if result.kind == nkCall: result.transitionSonsKind(nkHiddenCallConv) inc(m.convMatches) if r == isGeneric: result.typ = getInstantiatedType(c, arg, m, base(f)) @@ -1845,24 +2366,26 @@ proc incMatches(m: var TCandidate; r: TTypeRelation; convMatch = 1) = of isNone: discard template matchesVoidProc(t: PType): bool = - (t.kind == tyProc and t.len == 1 and t.sons[0] == nil) or - (t.kind == tyBuiltInTypeClass and t.sons[0].kind == tyProc) + (t.kind == tyProc and t.len == 1 and t.returnType == nil) or + (t.kind == tyBuiltInTypeClass and t.elementType.kind == tyProc) proc paramTypesMatchAux(m: var TCandidate, f, a: PType, argSemantized, argOrig: PNode): PNode = + result = nil var fMaybeStatic = f.skipTypes({tyDistinct}) arg = argSemantized a = a c = m.c - if tfHasStatic in fMaybeStatic.flags: # XXX: When implicit statics are the default # this will be done earlier - we just have to # make sure that static types enter here - # XXX: weaken tyGenericParam and call it tyGenericPlaceholder + # Zahary: weaken tyGenericParam and call it tyGenericPlaceholder # and finally start using tyTypedesc for generic types properly. + # Araq: This would only shift the problems around, in 'proc p[T](x: T)' + # the T is NOT a typedesc. if a.kind == tyGenericParam and tfWildcard in a.flags: a.assignType(f) # put(m.bindings, f, a) @@ -1873,13 +2396,19 @@ proc paramTypesMatchAux(m: var TCandidate, f, a: PType, a.n == nil and tfGenericTypeParam notin a.flags: return newNodeIT(nkType, argOrig.info, makeTypeFromExpr(c, arg)) - else: + elif a.kind == tyFromExpr and c.inGenericContext > 0: + # don't try to evaluate + discard + elif arg.kind != nkEmpty: var evaluated = c.semTryConstExpr(c, arg) if evaluated != nil: - arg.typ = newTypeS(tyStatic, c) - arg.typ.sons = @[evaluated.typ] - arg.typ.n = evaluated - a = arg.typ + # Don't build the type in-place because `evaluated` and `arg` may point + # to the same object and we'd end up creating recursive types (#9255) + let typ = newTypeS(tyStatic, c, son = evaluated.typ) + typ.n = evaluated + arg = copyTree(arg) # fix #12864 + arg.typ = typ + a = typ else: if m.callee.kind == tyGenericBody: if f.kind == tyStatic and typeRel(m, f.base, a) != isNone: @@ -1888,6 +2417,7 @@ proc paramTypesMatchAux(m: var TCandidate, f, a: PType, result.typ.n = arg return + let oldInheritancePenalty = m.inheritancePenalty var r = typeRel(m, f, a) # This special typing rule for macros and templates is not documented @@ -1898,7 +2428,7 @@ proc paramTypesMatchAux(m: var TCandidate, f, a: PType, # XXX: duplicating this is ugly, but we cannot (!) move this # directly into typeRel using return-like templates incMatches(m, r) - if f.kind == tyStmt: + if f.kind == tyTyped: return arg elif f.kind == tyTypeDesc: return arg @@ -1907,36 +2437,58 @@ proc paramTypesMatchAux(m: var TCandidate, f, a: PType, else: return argSemantized # argOrig - # If r == isBothMetaConvertible then we rerun typeRel. - # bothMetaCounter is for safety to avoid any infinite loop, - # I don't have any example when it is needed. - # lastBindingsLenth is used to check whether m.bindings remains the same, - # because in that case there is no point in continuing. - var bothMetaCounter = 0 - var lastBindingsLength = -1 - while r == isBothMetaConvertible and - lastBindingsLength != m.bindings.counter and - bothMetaCounter < 100: - lastBindingsLength = m.bindings.counter - inc(bothMetaCounter) - if arg.kind in {nkProcDef, nkFuncDef, nkIteratorDef} + nkLambdaKinds: - result = c.semInferredLambda(c, m.bindings, arg) - elif arg.kind != nkSym: - return nil - else: - let inferred = c.semGenerateInstance(c, arg.sym, m.bindings, arg.info) - result = newSymNode(inferred, arg.info) - inc(m.convMatches) - arg = result - r = typeRel(m, f, arg.typ) + block instantiateGenericRoutine: + # In the case where the matched value is a generic proc, we need to + # fully instantiate it and then rerun typeRel to make sure it matches. + # instantiationCounter is for safety to avoid any infinite loop, + # I don't have any example when it is needed. + # lastBindingCount is used to check whether m.bindings remains the same, + # because in that case there is no point in continuing. + var instantiationCounter = 0 + var lastBindingCount = -1 + while r in {isBothMetaConvertible, isInferred, isInferredConvertible} and + lastBindingCount != m.bindings.len and + instantiationCounter < 100: + lastBindingCount = m.bindings.len + inc(instantiationCounter) + if arg.kind in {nkProcDef, nkFuncDef, nkIteratorDef} + nkLambdaKinds: + result = c.semInferredLambda(c, m.bindings, arg) + elif arg.kind != nkSym: + return nil + elif arg.sym.kind in {skMacro, skTemplate}: + return nil + else: + if arg.sym.ast == nil: + return nil + let inferred = c.semGenerateInstance(c, arg.sym, m.bindings, arg.info) + result = newSymNode(inferred, arg.info) + arg = result + r = typeRel(m, f, arg.typ) case r of isConvertible: + if f.skipTypes({tyRange}).kind in {tyInt, tyUInt}: + inc(m.convMatches) inc(m.convMatches) - result = implicitConv(nkHiddenStdConv, f, arg, m, c) + if skipTypes(f, abstractVar-{tyTypeDesc}).kind == tySet: + if tfIsConstructor in a.flags and arg.kind == nkCurly: + # we marked the set as convertible only because the arg is a literal + # in which case we individually convert each element + let t = + if containsGenericType(f): + getInstantiatedType(c, arg, m, f).skipTypes({tySink}) + else: + f.skipTypes({tySink}) + result = convertLiteral(nkHiddenStdConv, c, m, arg, t) + else: + result = nil + else: + result = implicitConv(nkHiddenStdConv, f, arg, m, c) of isIntConv: # I'm too lazy to introduce another ``*matches`` field, so we conflate # ``isIntConv`` and ``isIntLit`` here: + if f.skipTypes({tyRange}).kind notin {tyInt, tyUInt}: + inc(m.intConvMatches) inc(m.intConvMatches) result = implicitConv(nkHiddenStdConv, f, arg, m, c) of isSubtype: @@ -1947,29 +2499,24 @@ proc paramTypesMatchAux(m: var TCandidate, f, a: PType, result = implicitConv(nkHiddenSubConv, f, arg, m, c) of isSubrange: inc(m.subtypeMatches) - if f.kind == tyVar: + if f.kind in {tyVar}: result = arg else: result = implicitConv(nkHiddenStdConv, f, arg, m, c) - of isInferred, isInferredConvertible: - if arg.kind in {nkProcDef, nkFuncDef, nkIteratorDef} + nkLambdaKinds: - result = c.semInferredLambda(c, m.bindings, arg) - elif arg.kind != nkSym: - return nil - else: - let inferred = c.semGenerateInstance(c, arg.sym, m.bindings, arg.info) - result = newSymNode(inferred, arg.info) - if r == isInferredConvertible: - inc(m.convMatches) - result = implicitConv(nkHiddenStdConv, f, result, m, c) - else: - inc(m.genericMatches) + of isInferred: + # result should be set in above while loop: + assert result != nil + inc(m.genericMatches) + of isInferredConvertible: + # result should be set in above while loop: + assert result != nil + inc(m.convMatches) + result = implicitConv(nkHiddenStdConv, f, result, m, c) of isGeneric: inc(m.genericMatches) if arg.typ == nil: result = arg - elif skipTypes(arg.typ, abstractVar-{tyTypeDesc}).kind == tyTuple or - m.inheritancePenalty > 0: + elif skipTypes(arg.typ, abstractVar-{tyTypeDesc}).kind == tyTuple or cmpInheritancePenalty(oldInheritancePenalty, m.inheritancePenalty) > 0: result = implicitConv(nkHiddenSubConv, f, arg, m, c) elif arg.typ.isEmptyContainer: result = arg.copyTree @@ -1977,8 +2524,10 @@ proc paramTypesMatchAux(m: var TCandidate, f, a: PType, else: result = arg of isBothMetaConvertible: - # This is the result for the 101th time. - result = nil + # result should be set in above while loop: + assert result != nil + inc(m.convMatches) + result = arg of isFromIntLit: # too lazy to introduce another ``*matches`` field, so we conflate # ``isIntConv`` and ``isIntLit`` here: @@ -1987,19 +2536,24 @@ proc paramTypesMatchAux(m: var TCandidate, f, a: PType, of isEqual: inc(m.exactMatches) result = arg - if skipTypes(f, abstractVar-{tyTypeDesc}).kind in {tyTuple}: + let ff = skipTypes(f, abstractVar-{tyTypeDesc}) + if ff.kind == tyTuple or + (arg.typ != nil and skipTypes(arg.typ, abstractVar-{tyTypeDesc}).kind == tyTuple): result = implicitConv(nkHiddenSubConv, f, arg, m, c) of isNone: # do not do this in ``typeRel`` as it then can't infer T in ``ref T``: - if a.kind in {tyProxy, tyUnknown}: + if a.kind == tyFromExpr: return nil + elif a.kind == tyError: inc(m.genericMatches) - m.fauxMatch = a.kind + m.matchedErrorType = true return arg elif a.kind == tyVoid and f.matchesVoidProc and argOrig.kind == nkStmtList: # lift do blocks without params to lambdas + # now deprecated + message(c.config, argOrig.info, warnStmtListLambda) let p = c.graph let lifted = c.semExpr(c, newProcNode(nkDo, argOrig.info, body = argOrig, - params = p.emptyNode, name = p.emptyNode, pattern = p.emptyNode, + params = nkFormalParams.newTree(p.emptyNode), name = p.emptyNode, pattern = p.emptyNode, genericParams = p.emptyNode, pragmas = p.emptyNode, exceptions = p.emptyNode), {}) if f.kind == tyBuiltInTypeClass: inc m.genericMatches @@ -2011,121 +2565,177 @@ proc paramTypesMatchAux(m: var TCandidate, f, a: PType, # constructor in a call: if result == nil and f.kind == tyVarargs: if f.n != nil: + # Forward to the varargs converter result = localConvMatch(c, m, f, a, arg) + elif f[0].kind == tyTyped: + inc m.genericMatches + result = arg else: r = typeRel(m, base(f), a) - if r >= isGeneric: + case r + of isGeneric: + inc(m.convMatches) + result = copyTree(arg) + result.typ = getInstantiatedType(c, arg, m, base(f)) + m.baseTypeMatch = true + of isFromIntLit: + inc(m.intConvMatches, 256) + result = implicitConv(nkHiddenStdConv, f[0], arg, m, c) + m.baseTypeMatch = true + of isEqual: inc(m.convMatches) result = copyTree(arg) - if r == isGeneric: - result.typ = getInstantiatedType(c, arg, m, base(f)) m.baseTypeMatch = true - # bug #4799, varargs accepting subtype relation object - elif r == isSubtype: + of isSubtype: # bug #4799, varargs accepting subtype relation object inc(m.subtypeMatches) - if f.kind == tyTypeDesc: + if base(f).kind == tyTypeDesc: result = arg else: - result = implicitConv(nkHiddenSubConv, f, arg, m, c) + result = implicitConv(nkHiddenSubConv, base(f), arg, m, c) m.baseTypeMatch = true else: result = userConvMatch(c, m, base(f), a, arg) if result != nil: m.baseTypeMatch = true +proc staticAwareTypeRel(m: var TCandidate, f: PType, arg: var PNode): TTypeRelation = + if f.kind == tyStatic and f.base.kind == tyProc: + # The ast of the type does not point to the symbol. + # Without this we will never resolve a `static proc` with overloads + let copiedNode = copyNode(arg) + copiedNode.typ = exactReplica(copiedNode.typ) + copiedNode.typ.n = arg + arg = copiedNode + typeRel(m, f, arg.typ) + + proc paramTypesMatch*(m: var TCandidate, f, a: PType, arg, argOrig: PNode): PNode = if arg == nil or arg.kind notin nkSymChoices: result = paramTypesMatchAux(m, f, a, arg, argOrig) else: - # CAUTION: The order depends on the used hashing scheme. Thus it is - # incorrect to simply use the first fitting match. However, to implement - # this correctly is inefficient. We have to copy `m` here to be able to - # roll back the side effects of the unification algorithm. - let c = m.c - var x, y, z: TCandidate - initCandidate(c, x, m.callee) - initCandidate(c, y, m.callee) - initCandidate(c, z, m.callee) - x.calleeSym = m.calleeSym - y.calleeSym = m.calleeSym - z.calleeSym = m.calleeSym + # symbol kinds that don't participate in symchoice type disambiguation: + let matchSet = {low(TSymKind)..high(TSymKind)} - {skModule, skPackage} + var best = -1 - for i in 0 ..< arg.len: - if arg.sons[i].sym.kind in {skProc, skFunc, skMethod, skConverter, - skIterator, skMacro, skTemplate}: - copyCandidate(z, m) - z.callee = arg.sons[i].typ - if tfUnresolved in z.callee.flags: continue - z.calleeSym = arg.sons[i].sym - #if arg.sons[i].sym.name.s == "cmp": - # ggDebug = true - # echo "CALLLEEEEEEEE A ", typeToString(z.callee) - # XXX this is still all wrong: (T, T) should be 2 generic matches - # and (int, int) 2 exact matches, etc. Essentially you cannot call - # typeRel here and expect things to work! - let r = typeRel(z, f, arg.sons[i].typ) - incMatches(z, r, 2) - #if arg.sons[i].sym.name.s == "cmp": # and arg.info.line == 606: - # echo "M ", r, " ", arg.info, " ", typeToString(arg.sons[i].sym.typ) - # writeMatches(z) - if r != isNone: - z.state = csMatch - case x.state - of csEmpty, csNoMatch: - x = z + result = arg + + var actingF = f + if f.kind == tyVarargs: + if m.calleeSym.kind in {skTemplate, skMacro}: + actingF = f[0] + if actingF.kind in {tyTyped, tyUntyped}: + var + bestScope = -1 + counts = 0 + for i in 0..<arg.len: + if arg[i].sym.kind in matchSet: + let thisScope = cmpScopes(m.c, arg[i].sym) + if thisScope > bestScope: best = i - of csMatch: - let cmp = cmpCandidates(x, z) - if cmp < 0: - best = i - x = z - elif cmp == 0: - y = z # z is as good as x - - if x.state == csEmpty: - result = nil - elif y.state == csMatch and cmpCandidates(x, y) == 0: - if x.state != csMatch: - internalError(m.c.graph.config, arg.info, "x.state is not csMatch") - # ambiguous: more than one symbol fits! - # See tsymchoice_for_expr as an example. 'f.kind == tyExpr' should match - # anyway: - if f.kind in {tyExpr, tyStmt}: result = arg - else: result = nil + bestScope = thisScope + counts = 0 + elif thisScope == bestScope: + inc counts + if best == -1: + result = nil + elif counts > 0: + m.genericMatches = 1 + best = -1 else: + # CAUTION: The order depends on the used hashing scheme. Thus it is + # incorrect to simply use the first fitting match. However, to implement + # this correctly is inefficient. We have to copy `m` here to be able to + # roll back the side effects of the unification algorithm. + let c = m.c + var + x = newCandidate(c, m.callee) # potential "best" + y = newCandidate(c, m.callee) # potential competitor with x + z = newCandidate(c, m.callee) # buffer for copies of m + x.calleeSym = m.calleeSym + y.calleeSym = m.calleeSym + z.calleeSym = m.calleeSym + + for i in 0..<arg.len: + if arg[i].sym.kind in matchSet: + copyCandidate(z, m) + z.callee = arg[i].typ + if arg[i].sym.kind == skType and z.callee.kind != tyTypeDesc: + # creating the symchoice with the type sym having typedesc type + # breaks a lot of stuff, so we make the typedesc type here + # mirrored from `newSymNodeTypeDesc` + z.callee = newType(tyTypeDesc, c.idgen, arg[i].sym.owner) + z.callee.addSonSkipIntLit(arg[i].sym.typ, c.idgen) + if tfUnresolved in z.callee.flags: continue + z.calleeSym = arg[i].sym + z.calleeScope = cmpScopes(m.c, arg[i].sym) + # XXX this is still all wrong: (T, T) should be 2 generic matches + # and (int, int) 2 exact matches, etc. Essentially you cannot call + # typeRel here and expect things to work! + let r = staticAwareTypeRel(z, f, arg[i]) + incMatches(z, r, 2) + if r != isNone: + z.state = csMatch + case x.state + of csEmpty, csNoMatch: + x = z + best = i + of csMatch: + let cmp = cmpCandidates(x, z, isFormal=false) + if cmp < 0: + best = i + x = z + elif cmp == 0: + y = z # z is as good as x + + if x.state == csEmpty: + result = nil + elif y.state == csMatch and cmpCandidates(x, y, isFormal=false) == 0: + if x.state != csMatch: + internalError(m.c.graph.config, arg.info, "x.state is not csMatch") + result = nil + if best > -1 and result != nil: # only one valid interpretation found: - markUsed(m.c.config, arg.info, arg.sons[best].sym, m.c.graph.usageSym) - styleCheckUse(arg.info, arg.sons[best].sym) - result = paramTypesMatchAux(m, f, arg.sons[best].typ, arg.sons[best], - argOrig) + markUsed(m.c, arg.info, arg[best].sym) + onUse(arg.info, arg[best].sym) + result = paramTypesMatchAux(m, f, arg[best].typ, arg[best], argOrig) + when false: + if m.calleeSym != nil and m.calleeSym.name.s == "[]": + echo m.c.config $ arg.info, " for ", m.calleeSym.name.s, " ", m.c.config $ m.calleeSym.info + writeMatches(m) proc setSon(father: PNode, at: int, son: PNode) = let oldLen = father.len if oldLen <= at: setLen(father.sons, at + 1) - father.sons[at] = son + father[at] = son # insert potential 'void' parameters: - #for i in oldLen ..< at: - # father.sons[i] = newNodeIT(nkEmpty, son.info, getSysType(tyVoid)) + #for i in oldLen..<at: + # father[i] = newNodeIT(nkEmpty, son.info, getSysType(tyVoid)) # we are allowed to modify the calling node in the 'prepare*' procs: proc prepareOperand(c: PContext; formal: PType; a: PNode): PNode = - if formal.kind == tyExpr and formal.len != 1: - # {tyTypeDesc, tyExpr, tyStmt, tyProxy}: + if formal.kind == tyUntyped and formal.len != 1: + # {tyTypeDesc, tyUntyped, tyTyped, tyError}: # a.typ == nil is valid result = a elif a.typ.isNil: - # XXX This is unsound! 'formal' can differ from overloaded routine to - # overloaded routine! - let flags = {efDetermineType, efAllowStmt} - #if formal.kind == tyIter: {efDetermineType, efWantIterator} - #else: {efDetermineType, efAllowStmt} - #elif formal.kind == tyStmt: {efDetermineType, efWantStmt} - #else: {efDetermineType} - result = c.semOperand(c, a, flags) + if formal.kind == tyIterable: + let flags = {efDetermineType, efAllowStmt, efWantIterator, efWantIterable} + result = c.semOperand(c, a, flags) + else: + # XXX This is unsound! 'formal' can differ from overloaded routine to + # overloaded routine! + let flags = {efDetermineType, efAllowStmt} + #if formal.kind == tyIterable: {efDetermineType, efWantIterator} + #else: {efDetermineType, efAllowStmt} + #elif formal.kind == tyTyped: {efDetermineType, efWantStmt} + #else: {efDetermineType} + result = c.semOperand(c, a, flags) else: result = a considerGenSyms(c, result) + if result.kind != nkHiddenDeref and result.typ.kind in {tyVar, tyLent} and c.matchedConcept == nil: + result = newDeref(result) proc prepareOperand(c: PContext; a: PNode): PNode = if a.typ.isNil: @@ -2135,15 +2745,15 @@ proc prepareOperand(c: PContext; a: PNode): PNode = considerGenSyms(c, result) proc prepareNamedParam(a: PNode; c: PContext) = - if a.sons[0].kind != nkIdent: - var info = a.sons[0].info - a.sons[0] = newIdentNode(considerQuotedIdent(c, a.sons[0]), info) + if a[0].kind != nkIdent: + var info = a[0].info + a[0] = newIdentNode(considerQuotedIdent(c, a[0]), info) proc arrayConstr(c: PContext, n: PNode): PType = result = newTypeS(tyArray, c) rawAddSon(result, makeRangeType(c, 0, 0, n.info)) addSonSkipIntLit(result, skipTypes(n.typ, - {tyGenericInst, tyVar, tyLent, tyOrdinal})) + {tyVar, tyLent, tyOrdinal}), c.idgen) proc arrayConstr(c: PContext, info: TLineInfo): PType = result = newTypeS(tyArray, c) @@ -2152,87 +2762,121 @@ proc arrayConstr(c: PContext, info: TLineInfo): PType = proc incrIndexType(t: PType) = assert t.kind == tyArray - inc t.sons[0].n.sons[1].intVal + inc t.indexType.n[1].intVal template isVarargsUntyped(x): untyped = - x.kind == tyVarargs and x.sons[0].kind == tyExpr and - tfOldSchoolExprStmt notin x.sons[0].flags + x.kind == tyVarargs and x[0].kind == tyUntyped + +template isVarargsTyped(x): untyped = + x.kind == tyVarargs and x[0].kind == tyTyped + +proc findFirstArgBlock(m: var TCandidate, n: PNode): int = + # see https://github.com/nim-lang/RFCs/issues/405 + result = int.high + for a2 in countdown(n.len-1, 0): + # checking `nfBlockArg in n[a2].flags` wouldn't work inside templates + if n[a2].kind != nkStmtList: break + let formalLast = m.callee.n[m.callee.n.len - (n.len - a2)] + # parameter has to occupy space (no default value, not void or varargs) + if formalLast.kind == nkSym and formalLast.sym.ast == nil and + formalLast.sym.typ.kind notin {tyVoid, tyVarargs}: + result = a2 + else: break + +proc matchesAux(c: PContext, n, nOrig: PNode, m: var TCandidate, marker: var IntSet) = + + template noMatch() = + c.mergeShadowScope #merge so that we don't have to resem for later overloads + m.state = csNoMatch + m.firstMismatch.arg = a + m.firstMismatch.formal = formal + return -proc matchesAux(c: PContext, n, nOrig: PNode, - m: var TCandidate, marker: var IntSet) = template checkConstraint(n: untyped) {.dirty.} = - if not formal.constraint.isNil: + if not formal.constraint.isNil and sfCodegenDecl notin formal.flags: if matchNodeKinds(formal.constraint, n): # better match over other routines with no such restriction: inc(m.genericMatches, 100) else: - m.state = csNoMatch - return - if formal.typ.kind == tyVar: - if not n.isLValue: - m.state = csNoMatch - m.mutabilityProblem = uint8(f-1) - return - - var - # iterates over formal parameters - f = if m.callee.kind != tyGenericBody: 1 - else: 0 - # iterates over the actual given arguments - a = 1 + noMatch() + + if formal.typ.kind in {tyVar}: + let argConverter = if arg.kind == nkHiddenDeref: arg[0] else: arg + if argConverter.kind == nkHiddenCallConv: + if argConverter.typ.kind notin {tyVar}: + m.firstMismatch.kind = kVarNeeded + noMatch() + elif not (isLValue(c, n, isOutParam(formal.typ))): + m.firstMismatch.kind = kVarNeeded + noMatch() m.state = csMatch # until proven otherwise - m.call = newNodeI(n.kind, n.info) - m.call.typ = base(m.callee) # may be nil - var formalLen = m.callee.n.len - addSon(m.call, copyTree(n.sons[0])) - var container: PNode = nil # constructed container - var formal: PSym = if formalLen > 1: m.callee.n.sons[1].sym else: nil + m.firstMismatch = MismatchInfo() + m.call = newNodeIT(n.kind, n.info, m.callee.base) + m.call.add n[0] + var + a = 1 # iterates over the actual given arguments + f = if m.callee.kind != tyGenericBody: 1 + else: 0 # iterates over formal parameters + arg: PNode = nil # current prepared argument + formalLen = m.callee.n.len + formal = if formalLen > 1: m.callee.n[1].sym else: nil # current routine parameter + container: PNode = nil # constructed container + let firstArgBlock = findFirstArgBlock(m, n) while a < n.len: + c.openShadowScope + if a >= formalLen-1 and f < formalLen and m.callee.n[f].typ.isVarargsUntyped: - formal = m.callee.n.sons[f].sym + formal = m.callee.n[f].sym incl(marker, formal.position) - if container.isNil: - container = newNodeIT(nkArgList, n.sons[a].info, arrayConstr(c, n.info)) - setSon(m.call, formal.position + 1, container) + + if n[a].kind == nkHiddenStdConv: + doAssert n[a][0].kind == nkEmpty and + n[a][1].kind in {nkBracket, nkArgList} + # Steal the container and pass it along + setSon(m.call, formal.position + 1, n[a][1]) else: - incrIndexType(container.typ) - addSon(container, n.sons[a]) - elif n.sons[a].kind == nkExprEqExpr: + if container.isNil: + container = newNodeIT(nkArgList, n[a].info, arrayConstr(c, n.info)) + setSon(m.call, formal.position + 1, container) + else: + incrIndexType(container.typ) + container.add n[a] + elif n[a].kind == nkExprEqExpr: # named param + m.firstMismatch.kind = kUnknownNamedParam # check if m.callee has such a param: - prepareNamedParam(n.sons[a], c) - if n.sons[a].sons[0].kind != nkIdent: - localError(c.config, n.sons[a].info, "named parameter has to be an identifier") - m.state = csNoMatch - return - formal = getSymFromList(m.callee.n, n.sons[a].sons[0].ident, 1) + prepareNamedParam(n[a], c) + if n[a][0].kind != nkIdent: + localError(c.config, n[a].info, "named parameter has to be an identifier") + noMatch() + formal = getNamedParamFromList(m.callee.n, n[a][0].ident) if formal == nil: # no error message! - m.state = csNoMatch - return + noMatch() if containsOrIncl(marker, formal.position): + m.firstMismatch.kind = kAlreadyGiven # already in namedParams, so no match # we used to produce 'errCannotBindXTwice' here but see # bug #3836 of why that is not sound (other overload with # different parameter names could match later on): - when false: localError(n.sons[a].info, errCannotBindXTwice, formal.name.s) - m.state = csNoMatch - return + when false: localError(n[a].info, errCannotBindXTwice, formal.name.s) + noMatch() m.baseTypeMatch = false - n.sons[a].sons[1] = prepareOperand(c, formal.typ, n.sons[a].sons[1]) - n.sons[a].typ = n.sons[a].sons[1].typ - var arg = paramTypesMatch(m, formal.typ, n.sons[a].typ, - n.sons[a].sons[1], n.sons[a].sons[1]) + m.typedescMatched = false + n[a][1] = prepareOperand(c, formal.typ, n[a][1]) + n[a].typ = n[a][1].typ + arg = paramTypesMatch(m, formal.typ, n[a].typ, + n[a][1], n[a][1]) + m.firstMismatch.kind = kTypeMismatch if arg == nil: - m.state = csNoMatch - return - checkConstraint(n.sons[a].sons[1]) + noMatch() + checkConstraint(n[a][1]) if m.baseTypeMatch: #assert(container == nil) - container = newNodeIT(nkBracket, n.sons[a].info, arrayConstr(c, arg)) - addSon(container, arg) + container = newNodeIT(nkBracket, n[a].info, arrayConstr(c, arg)) + container.add arg setSon(m.call, formal.position + 1, container) if f != formalLen - 1: container = nil else: @@ -2245,84 +2889,108 @@ proc matchesAux(c: PContext, n, nOrig: PNode, if tfVarargs in m.callee.flags: # is ok... but don't increment any counters... # we have no formal here to snoop at: - n.sons[a] = prepareOperand(c, n.sons[a]) - if skipTypes(n.sons[a].typ, abstractVar-{tyTypeDesc}).kind==tyString: - addSon(m.call, implicitConv(nkHiddenStdConv, - getSysType(c.graph, n.sons[a].info, tyCString), - copyTree(n.sons[a]), m, c)) + n[a] = prepareOperand(c, n[a]) + if skipTypes(n[a].typ, abstractVar-{tyTypeDesc}).kind==tyString: + m.call.add implicitConv(nkHiddenStdConv, + getSysType(c.graph, n[a].info, tyCstring), + copyTree(n[a]), m, c) else: - addSon(m.call, copyTree(n.sons[a])) + m.call.add copyTree(n[a]) elif formal != nil and formal.typ.kind == tyVarargs: + m.firstMismatch.kind = kTypeMismatch # beware of the side-effects in 'prepareOperand'! So only do it for # varargs matching. See tests/metatype/tstatic_overloading. m.baseTypeMatch = false + m.typedescMatched = false incl(marker, formal.position) - n.sons[a] = prepareOperand(c, formal.typ, n.sons[a]) - var arg = paramTypesMatch(m, formal.typ, n.sons[a].typ, - n.sons[a], nOrig.sons[a]) + n[a] = prepareOperand(c, formal.typ, n[a]) + arg = paramTypesMatch(m, formal.typ, n[a].typ, + n[a], nOrig[a]) if arg != nil and m.baseTypeMatch and container != nil: - addSon(container, arg) + container.add arg incrIndexType(container.typ) - checkConstraint(n.sons[a]) + checkConstraint(n[a]) else: - m.state = csNoMatch - return + noMatch() else: - m.state = csNoMatch - return + m.firstMismatch.kind = kExtraArg + noMatch() else: - if m.callee.n.sons[f].kind != nkSym: - internalError(c.config, n.sons[a].info, "matches") - return - formal = m.callee.n.sons[f].sym + if m.callee.n[f].kind != nkSym: + internalError(c.config, n[a].info, "matches") + noMatch() + if flexibleOptionalParams in c.features and a >= firstArgBlock: + f = max(f, m.callee.n.len - (n.len - a)) + formal = m.callee.n[f].sym + m.firstMismatch.kind = kTypeMismatch if containsOrIncl(marker, formal.position) and container.isNil: - # already in namedParams: (see above remark) - when false: localError(n.sons[a].info, errCannotBindXTwice, formal.name.s) - m.state = csNoMatch - return + m.firstMismatch.kind = kPositionalAlreadyGiven + # positional param already in namedParams: (see above remark) + when false: localError(n[a].info, errCannotBindXTwice, formal.name.s) + noMatch() if formal.typ.isVarargsUntyped: if container.isNil: - container = newNodeIT(nkArgList, n.sons[a].info, arrayConstr(c, n.info)) + container = newNodeIT(nkArgList, n[a].info, arrayConstr(c, n.info)) setSon(m.call, formal.position + 1, container) else: incrIndexType(container.typ) - addSon(container, n.sons[a]) + container.add n[a] else: m.baseTypeMatch = false - n.sons[a] = prepareOperand(c, formal.typ, n.sons[a]) - var arg = paramTypesMatch(m, formal.typ, n.sons[a].typ, - n.sons[a], nOrig.sons[a]) + m.typedescMatched = false + n[a] = prepareOperand(c, formal.typ, n[a]) + arg = paramTypesMatch(m, formal.typ, n[a].typ, + n[a], nOrig[a]) if arg == nil: - m.state = csNoMatch - m.firstMismatch = f - return - if m.baseTypeMatch: + noMatch() + if formal.typ.isVarargsTyped and m.calleeSym.kind in {skTemplate, skMacro}: + if container.isNil: + container = newNodeIT(nkBracket, n[a].info, arrayConstr(c, n.info)) + setSon(m.call, formal.position + 1, implicitConv(nkHiddenStdConv, formal.typ, container, m, c)) + else: + incrIndexType(container.typ) + container.add n[a] + f = max(f, formalLen - n.len + a + 1) + elif m.baseTypeMatch: + assert formal.typ.kind == tyVarargs #assert(container == nil) if container.isNil: - container = newNodeIT(nkBracket, n.sons[a].info, arrayConstr(c, arg)) + container = newNodeIT(nkBracket, n[a].info, arrayConstr(c, arg)) container.typ.flags.incl tfVarargs else: incrIndexType(container.typ) - addSon(container, arg) + container.add arg setSon(m.call, formal.position + 1, implicitConv(nkHiddenStdConv, formal.typ, container, m, c)) #if f != formalLen - 1: container = nil # pick the formal from the end, so that 'x, y, varargs, z' works: f = max(f, formalLen - n.len + a + 1) - else: + elif formal.typ.kind != tyVarargs or container == nil: setSon(m.call, formal.position + 1, arg) - inc(f) + inc f container = nil - checkConstraint(n.sons[a]) - inc(a) + else: + # we end up here if the argument can be converted into the varargs + # formal (e.g. seq[T] -> varargs[T]) but we have already instantiated + # a container + #assert arg.kind == nkHiddenStdConv # for 'nim check' + # this assertion can be off + localError(c.config, n[a].info, "cannot convert $1 to $2" % [ + typeToString(n[a].typ), typeToString(formal.typ) ]) + noMatch() + checkConstraint(n[a]) + + if m.state == csMatch and not (m.calleeSym != nil and m.calleeSym.kind in {skTemplate, skMacro}): + c.mergeShadowScope + else: + c.closeShadowScope -proc semFinishOperands*(c: PContext, n: PNode) = - # this needs to be called to ensure that after overloading resolution every - # argument has been sem'checked: - for i in 1 ..< n.len: - n.sons[i] = prepareOperand(c, n.sons[i]) + inc a + # for some edge cases (see tdont_return_unowned_from_owned test case) + m.firstMismatch.arg = a + m.firstMismatch.formal = formal proc partialMatch*(c: PContext, n, nOrig: PNode, m: var TCandidate) = # for 'suggest' support: @@ -2333,42 +3001,67 @@ proc matches*(c: PContext, n, nOrig: PNode, m: var TCandidate) = if m.magic in {mArrGet, mArrPut}: m.state = csMatch m.call = n + # Note the following doesn't work as it would produce ambiguities. + # Instead we patch system.nim, see bug #8049. + when false: + inc m.genericMatches + inc m.exactMatches return + # initCandidate may have given csNoMatch if generic params didn't match: + if m.state == csNoMatch: return var marker = initIntSet() matchesAux(c, n, nOrig, m, marker) if m.state == csNoMatch: return # check that every formal parameter got a value: - var f = 1 - while f < sonsLen(m.callee.n): - var formal = m.callee.n.sons[f].sym + for f in 1..<m.callee.n.len: + let formal = m.callee.n[f].sym if not containsOrIncl(marker, formal.position): if formal.ast == nil: if formal.typ.kind == tyVarargs: - var container = newNodeIT(nkBracket, n.info, arrayConstr(c, n.info)) + # For consistency with what happens in `matchesAux` select the + # container node kind accordingly + let cnKind = if formal.typ.isVarargsUntyped: nkArgList else: nkBracket + var container = newNodeIT(cnKind, n.info, arrayConstr(c, n.info)) setSon(m.call, formal.position + 1, implicitConv(nkHiddenStdConv, formal.typ, container, m, c)) else: # no default value m.state = csNoMatch - m.firstMismatch = f + m.firstMismatch.kind = kMissingParam + m.firstMismatch.formal = formal break else: - # use default value: - var def = copyTree(formal.ast) - if def.kind == nkNilLit: - def = implicitConv(nkHiddenStdConv, formal.typ, def, m, c) + # mirrored with updateDefaultParams: + if formal.ast.kind == nkEmpty: + # The default param value is set to empty in `instantiateProcType` + # when the type of the default expression doesn't match the type + # of the instantiated proc param: + pushInfoContext(c.config, m.call.info, + if m.calleeSym != nil: m.calleeSym.detailedInfo else: "") + typeMismatch(c.config, formal.ast.info, formal.typ, formal.ast.typ, formal.ast) + popInfoContext(c.config) + formal.ast.typ = errorType(c) + if nfDefaultRefsParam in formal.ast.flags: + m.call.flags.incl nfDefaultRefsParam + var defaultValue = copyTree(formal.ast) + if defaultValue.kind == nkNilLit: + defaultValue = implicitConv(nkHiddenStdConv, formal.typ, defaultValue, m, c) + # proc foo(x: T = 0.0) + # foo() if {tfImplicitTypeParam, tfGenericTypeParam} * formal.typ.flags != {}: - put(m, formal.typ, def.typ) - setSon(m.call, formal.position + 1, def) - inc(f) + let existing = idTableGet(m.bindings, formal.typ) + if existing == nil or existing.kind == tyTypeDesc: + # see bug #11600: + put(m, formal.typ, defaultValue.typ) + defaultValue.flags.incl nfDefaultParam + setSon(m.call, formal.position + 1, defaultValue) # forget all inferred types if the overload matching failed if m.state == csNoMatch: for t in m.inferredTypes: - if t.sonsLen > 1: t.sons.setLen 1 + if t.len > 1: t.newSons 1 proc argtypeMatches*(c: PContext, f, a: PType, fromHlo = false): bool = - var m: TCandidate - initCandidate(c, m, f) + var m = newCandidate(c, f) let res = paramTypesMatch(m, f, a, c.graph.emptyNode, nil) #instantiateGenericConverters(c, res, m) # XXX this is used by patterns.nim too; I think it's better to not @@ -2379,20 +3072,21 @@ proc argtypeMatches*(c: PContext, f, a: PType, fromHlo = false): bool = # pattern templates do not allow for conversions except from int literal res != nil and m.convMatches == 0 and m.intConvMatches in [0, 256] + proc instTypeBoundOp*(c: PContext; dc: PSym; t: PType; info: TLineInfo; - op: TTypeAttachedOp; col: int): PSym {.procvar.} = - var m: TCandidate - initCandidate(c, m, dc.typ) + op: TTypeAttachedOp; col: int): PSym = + var m = newCandidate(c, dc.typ) if col >= dc.typ.len: localError(c.config, info, "cannot instantiate: '" & dc.name.s & "'") return nil - var f = dc.typ.sons[col] + var f = dc.typ[col] if op == attachedDeepCopy: - if f.kind in {tyRef, tyPtr}: f = f.lastSon + if f.kind in {tyRef, tyPtr}: f = f.elementType else: - if f.kind == tyVar: f = f.lastSon + if f.kind in {tyVar}: f = f.elementType if typeRel(m, f, t) == isNone: + result = nil localError(c.config, info, "cannot instantiate: '" & dc.name.s & "'") else: result = c.semGenerateInstance(c, dc, m.bindings, info) @@ -2405,7 +3099,7 @@ when not declared(tests): template tests(s: untyped) = discard tests: - var dummyOwner = newSym(skModule, getIdent("test_module"), nil, UnknownLineInfo()) + var dummyOwner = newSym(skModule, getIdent("test_module"), nil, unknownLineInfo) proc `|` (t1, t2: PType): PType = result = newType(tyOr, dummyOwner) @@ -2428,9 +3122,9 @@ tests: proc array(x: int, t: PType): PType = result = newType(tyArray, dummyOwner) - var n = newNodeI(nkRange, UnknownLineInfo()) - addSon(n, newIntNode(nkIntLit, 0)) - addSon(n, newIntNode(nkIntLit, x)) + var n = newNodeI(nkRange, unknownLineInfo) + n.add newIntNode(nkIntLit, 0) + n.add newIntNode(nkIntLit, x) let range = newType(tyRange, dummyOwner) result.rawAddSon(range) @@ -2446,19 +3140,18 @@ tests: number = int | float var TFoo = newType(tyObject, dummyOwner) - TFoo.sym = newSym(skType, getIdent"TFoo", dummyOwner, UnknownLineInfo()) + TFoo.sym = newSym(skType, getIdent"TFoo", dummyOwner, unknownLineInfo) var T1 = newType(tyGenericParam, dummyOwner) - T1.sym = newSym(skType, getIdent"T1", dummyOwner, UnknownLineInfo()) + T1.sym = newSym(skType, getIdent"T1", dummyOwner, unknownLineInfo) T1.sym.position = 0 var T2 = newType(tyGenericParam, dummyOwner) - T2.sym = newSym(skType, getIdent"T2", dummyOwner, UnknownLineInfo()) + T2.sym = newSym(skType, getIdent"T2", dummyOwner, unknownLineInfo) T2.sym.position = 1 setup: - var c: TCandidate - initCandidate(nil, c, nil) + var c = newCandidate(nil, nil) template yes(x, y) = test astToStr(x) & " is " & astToStr(y): @@ -2520,4 +3213,3 @@ tests: yes int, ordinal no string, ordinal - |