# # # The Nimrod Compiler # (c) Copyright 2013 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. # ## This module implements the signature matching for resolving ## 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 when not defined(noDocgen): import docgen type TCandidateState* = enum csEmpty, csMatch, csNoMatch TCandidate* {.final.} = object c*: PContext exactMatches*: int # also misused to prefer iters over procs genericMatches: int # also misused to prefer constraints subtypeMatches: int intConvMatches: int # conversions to int are not as expensive convMatches: int state*: TCandidateState callee*: PType # may not be nil! calleeSym*: PSym # may be nil calleeScope*: int # scope depth: # is this a top-level symbol or a nested proc? call*: PNode # modified call bindings*: TIdTable # maps types to types baseTypeMatch: bool # needed for conversions from T to openarray[T] # for example proxyMatch*: bool # to prevent instantiations genericConverter*: bool # true if a generic converter needs to # be instantiated coerceDistincts*: bool # this is an explicit coercion that can strip away # a distrinct type typedescMatched: bool inheritancePenalty: int # to prefer closest father object type errors*: seq[string] # additional clarifications to be displayed to the # user if overload resolution fails 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`` 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? proc markUsed*(n: PNode, 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) proc put(t: var TIdTable, key, val: PType) {.inline.} = idTablePut(t, key, val) proc initCandidate*(ctx: PContext, c: var TCandidate, callee: PSym, binding: PNode, calleeScope = -1) = initCandidateAux(ctx, c, callee.typ) c.calleeSym = callee if callee.kind in skProcKinds and calleeScope == -1: if callee.originatingModule == ctx.module: let rootSym = if sfFromGeneric notin callee.flags: callee else: callee.owner c.calleeScope = rootSym.scope.depthLevel else: c.calleeScope = 1 else: c.calleeScope = calleeScope initIdTable(c.bindings) c.errors = nil 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 and formalTypeParam.kind != tyTypeDesc: bound = bound.skipTypes({tyTypeDesc}) assert bound != nil put(c.bindings, formalTypeParam, bound) proc newCandidate*(ctx: PContext, callee: PSym, binding: PNode, calleeScope = -1): TCandidate = initCandidate(ctx, result, 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) proc sumGeneric(t: PType): int = var t = t while true: case t.kind of tyGenericInst, tyArray, tyRef, tyPtr, tyDistinct, tyArrayConstr, tyOpenArray, tyVarargs, tySet, tyRange, tySequence, tyGenericBody: t = t.lastSon inc result of tyVar: # but do not make 'var T' more specific than 'T'! t = t.sons[0] of tyGenericInvokation, tyTuple: result = ord(t.kind == tyGenericInvokation) for i in 0 .. b.sumGeneric if a.len > 1 and b.len > 1: let aa = a.sons[1].sumGeneric let bb = b.sons[1].sumGeneric var a = a var b = b if aa < bb: swap(a, b) # all must be better for i in 2 .. = firstOrd(f) and ab.n.intVal <= lastOrd(f): # 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}: 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(f) and a.n[1].intVal <= lastOrd(f): 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: if f.kind in {tyInt..tyInt64, tyUInt..tyUInt64} and a.kind in {tyInt..tyInt64, tyUInt..tyUInt64}: result = true elif f.kind in {tyFloat..tyFloat128} and a.kind in {tyFloat..tyFloat128}: result = true proc handleFloatRange(f, a: PType): TTypeRelation = if a.kind == f.kind: result = isEqual else: let ab = skipTypes(a, {tyRange}) var k = ab.kind if k == f.kind: result = isSubrange elif isFloatLit(ab): result = isFromIntLit elif isIntLit(ab): result = isConvertible elif k >= tyFloat and k <= tyFloat128: # conversion to "float32" is not as good: if f.kind == tyFloat32: result = isConvertible else: result = isIntConv else: result = isNone proc isObjectSubtype(a, f: PType): int = var t = a assert t.kind == tyObject var depth = 0 while t != nil and not sameObjectTypes(f, t): assert t.kind == tyObject t = t.sons[0] if t == nil: break t = skipTypes(t, {tyGenericInst}) inc depth if t != nil: result = depth proc minRel(a, b: TTypeRelation): TTypeRelation = if a <= b: result = a else: result = b proc recordRel(c: var TCandidate, f, a: PType): TTypeRelation = result = isNone if sameType(f, a): result = isEqual elif sonsLen(a) == sonsLen(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]) if m < isSubtype: return isNone result = minRel(result, m) if f.n != nil and a.n != nil: for i in countup(0, sonsLen(f.n) - 1): # check field names: if f.n.sons[i].kind != nkSym: internalError(f.n.info, "recordRel") elif a.n.sons[i].kind != nkSym: internalError(a.n.info, "recordRel") 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: return isNone if x.name.id != y.name.id: return isNone 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 == tyVar or a.kind == tyVar) proc procParamTypeRel(c: var TCandidate, f, a: PType): TTypeRelation = var f = f 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 # type is already fully-determined, so we are # going to try resolve it f = generateTypeInstance(c.c, c.bindings, c.call.info, f) if f == nil or f.isMetaType: # no luck resolving the type, so the inference fails return isNone let reverseRel = typeRel(c, a, f) if reverseRel == isGeneric: result = isInferred inc c.genericMatches else: result = typeRel(c, f, a) if result <= isSubtype or inconsistentVarTypes(f, a): result = isNone if result == isEqual: inc c.exactMatches proc procTypeRel(c: var TCandidate, f, a: PType): TTypeRelation = case a.kind of tyProc: if sonsLen(f) != sonsLen(a): return result = isEqual # start with maximum; also correct for no # params at all 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 .. = 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 else: result = isNone proc matchUserTypeClass*(c: PContext, m: var TCandidate, ff, a: PType): TTypeRelation = var body = ff.skipTypes({tyUserTypeClassInst}) openScope(c) inc c.inTypeClass finally: dec c.inTypeClass closeScope(c) if ff.kind == tyUserTypeClassInst: for i in 1 .. <(ff.len - 1): var typeParamName = ff.base.sons[i-1].sym.name typ = ff.sons[i] param = newSym(skType, typeParamName, body.sym, body.sym.info) param.typ = makeTypeDesc(c, typ) addDecl(c, param) for param in body.n[0]: var dummyName: PNode dummyType: PType if param.kind == nkVarTy: dummyName = param[0] dummyType = if a.kind != tyVar: makeVarType(c, a) else: a else: dummyName = param dummyType = a internalAssert dummyName.kind == nkIdent var dummyParam = newSym(skType, dummyName.ident, body.sym, body.sym.info) dummyParam.typ = dummyType addDecl(c, dummyParam) var checkedBody = c.semTryExpr(c, body.n[3].copyTree, bufferErrors = false) m.errors = bufferedMsgs clearBufferedMsgs() if checkedBody == nil: return isNone if checkedBody.kind == nkStmtList: for stmt in checkedBody: case stmt.kind of nkReturnStmt: discard of nkTypeSection: discard of nkConstDef: discard else: discard return isGeneric proc shouldSkipDistinct(rules: PNode, callIdent: PIdent): bool = if rules.kind == nkWith: for r in rules: if r.considerAcc == callIdent: return true return false else: for r in rules: if r.considerAcc == callIdent: return false return true proc maybeSkipDistinct(t: PType, callee: PSym): PType = if t != nil and t.kind == tyDistinct and t.n != nil and shouldSkipDistinct(t.n, callee.name): result = t.base else: result = t proc typeRel(c: var TCandidate, f, aOrig: PType, doBind = true): TTypeRelation = # typeRel can be used to establish various relationships between types: # # 1) When used with concrete types, it will check for type equivalence # or a subtype relationship. # # 2) When used with a concrete type against a type class (such as generic # signature of a proc), it will check whether the concrete type is a member # 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 # order to give preferrence to the most specific one: # # seq[seq[any]] is a strict subset of seq[any] and hence more specific. result = isNone assert(f != nil) if f.kind == tyExpr: put(c.bindings, f, aOrig) return isGeneric assert(aOrig != nil) # var and static arguments match regular modifier-free types let a = aOrig.skipTypes({tyStatic, tyVar}).maybeSkipDistinct(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 a.kind == tyGenericInst and skipTypes(f, {tyVar}).kind notin { tyGenericBody, tyGenericInvokation, tyGenericInst, tyGenericParam} + tyTypeClasses: return typeRel(c, f, lastSon(a)) template bindingRet(res) = when res == isGeneric: if doBind: let bound = aOrig.skipTypes({tyRange}).skipIntLit if doBind: put(c.bindings, f, bound) return res template considerPreviousT(body: stmt) {.immediate.} = var prev = PType(idTableGet(c.bindings, f)) if prev == nil: body else: return typeRel(c, prev, a) case a.kind of tyOr: # seq[int|string] vs seq[number] # both int and string must match against number for branch in a.sons: if typeRel(c, f, branch, false) == isNone: return isNone return isGeneric of tyAnd: # seq[Sortable and Iterable] vs seq[Sortable] # only one match is enough for branch in a.sons: if typeRel(c, f, branch, false) != isNone: return isGeneric return isNone of tyNot: case f.kind of tyNot: # seq[!int] vs seq[!number] # 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) 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 else: discard case f.kind of tyEnum: if a.kind == f.kind and sameEnumTypes(f, a): result = isEqual elif sameEnumTypes(f, skipTypes(a, {tyRange})): result = isSubtype of tyBool, tyChar: if a.kind == f.kind: result = isEqual elif skipTypes(a, {tyRange}).kind == f.kind: result = isSubtype of tyRange: if a.kind == f.kind: result = typeRel(c, base(f), base(a)) # bugfix: accept integer conversions here #if result < isGeneric: result = isNone if result notin {isNone, isGeneric}: result = typeRangeRel(f, a) else: if skipTypes(f, {tyRange}).kind == a.kind: result = isIntConv elif isConvertibleToRange(skipTypes(f, {tyRange}), 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 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: if aOrig.kind == tyVar: result = typeRel(c, f.base, aOrig.base) else: result = typeRel(c, f.base, aOrig) of tyArray, tyArrayConstr: # tyArrayConstr cannot happen really, but # we wanna be safe here case a.kind of tyArray, tyArrayConstr: var fRange = f.sons[0] if fRange.kind == tyGenericParam: var prev = PType(idTableGet(c.bindings, fRange)) if prev == nil: put(c.bindings, fRange, a.sons[0]) fRange = a else: fRange = prev result = typeRel(c, f.sons[1], a.sons[1]) if result < isGeneric: result = isNone elif tfUnresolved in fRange.flags and rangeHasStaticIf(fRange): # This is a range from an array instantiated with a generic # static param. We must extract the static param here and bind # it to the size of the currently supplied array. var rangeStaticT = fRange.getStaticTypeFromRange replacementT = newTypeWithSons(c.c, tyStatic, @[tyInt.getSysType]) inputUpperBound = a.sons[0].n[1].intVal # we must correct for the off-by-one discrepancy between # ranges and static params: replacementT.n = newIntNode(nkIntLit, inputUpperBound + 1) put(c.bindings, rangeStaticT, replacementT) result = isGeneric elif lengthOrd(fRange) != lengthOrd(a): result = isNone else: discard of tyOpenArray, tyVarargs: # varargs[expr] is special if f.kind == tyVarargs and f.sons[0].kind == tyExpr: return case a.kind of tyOpenArray, tyVarargs: result = typeRel(c, base(f), base(a)) if result < isGeneric: result = isNone of tyArrayConstr: if (f.sons[0].kind != tyGenericParam) and (a.sons[1].kind == tyEmpty): result = isSubtype # [] is allowed here elif typeRel(c, base(f), a.sons[1]) >= isGeneric: result = isSubtype of tyArray: if (f.sons[0].kind != tyGenericParam) and (a.sons[1].kind == tyEmpty): result = isSubtype elif typeRel(c, base(f), a.sons[1]) >= isGeneric: result = isConvertible of tySequence: if (f.sons[0].kind != tyGenericParam) and (a.sons[0].kind == tyEmpty): result = isConvertible elif typeRel(c, base(f), a.sons[0]) >= isGeneric: result = isConvertible else: discard of tySequence: case a.kind of tySequence: if (f.sons[0].kind != tyGenericParam) and (a.sons[0].kind == tyEmpty): result = isSubtype else: result = typeRel(c, f.sons[0], a.sons[0]) if result < isGeneric: result = isNone elif tfNotNil in f.flags and tfNotNil notin a.flags: result = isNilConversion of tyNil: result = f.allowsNil else: discard of tyOrdinal: if isOrdinalType(a): var x = if a.kind == tyOrdinal: a.sons[0] else: a if f.sons[0].kind == tyNone: result = isGeneric else: result = typeRel(c, f.sons[0], x) if result < isGeneric: result = isNone elif a.kind == tyGenericParam: result = isGeneric of tyForward: internalError("forward type in typeRel()") of tyNil: if a.kind == f.kind: result = isEqual of tyTuple: if a.kind == tyTuple: result = recordRel(c, f, a) of tyObject: if a.kind == tyObject: if sameObjectTypes(f, a): result = isEqual # elif tfHasMeta in f.flags: result = recordRel(c, f, a) else: var depth = isObjectSubtype(a, f) if depth > 0: inc(c.inheritancePenalty, depth) result = isSubtype of tyDistinct: if (a.kind == tyDistinct) and sameDistinctTypes(f, a): result = isEqual elif c.coerceDistincts: result = typeRel(c, f.base, a) of tySet: if a.kind == tySet: if (f.sons[0].kind != tyGenericParam) and (a.sons[0].kind == tyEmpty): result = isSubtype else: result = typeRel(c, f.sons[0], a.sons[0]) if result <= isConvertible: result = isNone # BUGFIX! of tyPtr, tyRef: 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) if result <= isConvertible: 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: result = procTypeRel(c, f, a) if result != isNone and tfNotNil in f.flags and tfNotNil notin a.flags: result = isNilConversion of tyPointer: case a.kind of tyPointer: if tfNotNil in f.flags and tfNotNil notin a.flags: result = isNilConversion else: result = isEqual of tyNil: result = f.allowsNil of tyProc: 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 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 else: discard of tyCString: # conversion from string to cstring is automatic: case a.kind of tyCString: if tfNotNil in f.flags and tfNotNil notin a.flags: result = isNilConversion else: result = isEqual 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 and a.sons[0].kind == tyChar: result = isConvertible of tyArray: if (firstOrd(a.sons[0]) == 0) and (skipTypes(a.sons[0], {tyRange}).kind in {tyInt..tyInt64}) and (a.sons[1].kind == tyChar): result = isConvertible else: discard of tyEmpty: if a.kind == tyEmpty: result = isEqual of tyGenericInst: let roota = a.skipGenericAlias let rootf = f.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) if result == isNone: return if ff.kind == tyRange and result != isEqual: return isNone result = isGeneric else: result = typeRel(c, lastSon(f), a) of tyGenericBody: considerPreviousT: if a.kind == tyGenericInst and a.sons[0] == f: bindingRet isGeneric let ff = lastSon(f) if ff != nil: result = typeRel(c, ff, a) of tyGenericInvokation: var x = a.skipGenericAlias if x.kind == tyGenericInvokation or f.sons[0].kind != tyGenericBody: #InternalError("typeRel: tyGenericInvokation -> tyGenericInvokation") # simply no match for now: discard elif x.kind == tyGenericInst and (f.sons[0] == x.sons[0]) and (sonsLen(x) - 1 == sonsLen(f)): for i in countup(1, sonsLen(f) - 1): if x.sons[i].kind == tyGenericParam: internalError("wrong instantiated type!") elif typeRel(c, f.sons[i], x.sons[i]) <= isSubtype: return result = isGeneric else: result = typeRel(c, f.sons[0], x) if result != isNone: # we steal the generic parameters from the tyGenericBody: for i in countup(1, sonsLen(f) - 1): var x = PType(idTableGet(c.bindings, f.sons[0].sons[i - 1])) if x == nil or x.kind in {tyGenericInvokation, tyGenericParam}: internalError("wrong instantiated type!") put(c.bindings, f.sons[i], x) of tyAnd: considerPreviousT: for branch in f.sons: if typeRel(c, branch, aOrig) < isSubtype: return isNone bindingRet isGeneric of tyOr: considerPreviousT: for branch in f.sons: if typeRel(c, branch, aOrig) >= isSubtype: bindingRet isGeneric return isNone of tyNot: considerPreviousT: for branch in f.sons: if typeRel(c, branch, aOrig) != isNone: return isNone bindingRet isGeneric of tyAnything: considerPreviousT: var concrete = concreteType(c, a) if concrete != nil and doBind: put(c.bindings, f, concrete) return isGeneric of tyBuiltInTypeClass: considerPreviousT: let targetKind = f.sons[0].kind if targetKind == a.skipTypes({tyRange, tyGenericInst}).kind or (targetKind in {tyProc, tyPointer} and a.kind == tyNil): put(c.bindings, f, a) return isGeneric else: return isNone of tyUserTypeClass, tyUserTypeClassInst: considerPreviousT: result = matchUserTypeClass(c.c, c, f, aOrig) if result == isGeneric: put(c.bindings, f, a) of tyCompositeTypeClass: considerPreviousT: if typeRel(c, f.sons[1], a) != isNone: put(c.bindings, f, a) return isGeneric else: return isNone of tyGenericParam: var x = PType(idTableGet(c.bindings, f)) if x == nil: if c.callee.kind == tyGenericBody and f.kind == tyGenericParam 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 # by a tyTypeDesc params. Unfortunately, this requires more substantial # changes in semtypinst and elsewhere. if tfWildcard in a.flags: result = isGeneric elif a.kind == tyTypeDesc: if f.sonsLen == 0: result = isGeneric else: internalAssert a.sons != nil and a.sons.len > 0 c.typedescMatched = true result = typeRel(c, f.base, a.base) else: result = isNone else: if f.sonsLen > 0 and f.sons[0].kind != tyNone: result = typeRel(c, f.lastSon, a) else: result = isGeneric if result == isGeneric: var concrete = a if tfWildcard in a.flags: a.sym.kind = skType a.flags.excl tfWildcard else: concrete = concreteType(c, a) if concrete == nil: return isNone if doBind: put(c.bindings, f, concrete) elif a.kind == tyEmpty: result = isGeneric elif x.kind == tyGenericParam: result = isGeneric else: result = typeRel(c, x, a) # check if it fits of tyStatic: if aOrig.kind == tyStatic: result = typeRel(c, f.lastSon, a) if result != isNone: put(c.bindings, f, aOrig) else: result = isNone of tyTypeDesc: var prev = PType(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: result = isGeneric else: result = typeRel(c, f.base, a.base) if result != isNone: put(c.bindings, f, a) else: if tfUnresolved in f.flags: result = typeRel(c, prev.base, a) elif a.kind == tyTypeDesc: result = typeRel(c, prev.base, a.base) else: result = isNone of tyIter: if a.kind == tyIter or (a.kind == tyProc and tfIterator in a.flags): result = typeRel(c, f.base, a.base) else: result = isNone of tyStmt: result = isGeneric of tyProxy: result = isEqual of tyFromExpr: # fix the expression, so it contains the already instantiated types let instantiated = replaceTypesInBody(c.c, c.bindings, f.n) let reevaluted = c.c.semExpr(c.c, instantiated) case reevaluted.typ.kind of tyTypeDesc: result = typeRel(c, a, reevaluted.typ.base) of tyStatic: result = typeRel(c, a, reevaluted.typ.base) if result != isNone and reevaluted.typ.n != nil: if not exprStructuralEquivalent(aOrig.n, reevaluted.typ.n): result = isNone else: localError(f.n.info, errTypeExpected) result = isNone else: internalAssert false proc cmpTypes*(c: PContext, f, a: PType): TTypeRelation = var m: TCandidate initCandidate(c, m, f) result = typeRel(m, f, a) proc getInstantiatedType(c: PContext, arg: PNode, m: TCandidate, f: PType): PType = result = PType(idTableGet(m.bindings, f)) if result == nil: result = generateTypeInstance(c, m.bindings, arg, f) if result == nil: internalError(arg.info, "getInstantiatedType") result = errorType(c) proc implicitConv(kind: TNodeKind, f: PType, arg: PNode, m: TCandidate, c: PContext): PNode = result = newNodeI(kind, arg.info) if containsGenericType(f): if not m.proxyMatch: result.typ = getInstantiatedType(c, arg, m, f) else: result.typ = errorType(c) else: result.typ = f if result.typ == nil: internalError(arg.info, "implicitConv") addSon(result, ast.emptyNode) addSon(result, arg) 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 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 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(arg, 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)) inc(m.convMatches) m.genericConverter = srca == isGeneric or destIsGeneric return result proc localConvMatch(c: PContext, m: var TCandidate, f, a: PType, arg: PNode): PNode = # arg.typ can be nil in 'suggest': if isNil(arg.typ): return nil var call = newNodeI(nkCall, arg.info) call.add(f.n.copyTree) call.add(arg.copyTree) result = c.semOverloadedCall(c, call, call, routineKinds) if result != nil: # resulting type must be consistent with the other arguments: var r = typeRel(m, f.sons[0], result.typ) if r < isGeneric: return nil if result.kind == nkCall: result.kind = nkHiddenCallConv inc(m.convMatches) if r == isGeneric: result.typ = getInstantiatedType(c, arg, m, base(f)) m.baseTypeMatch = true proc isInlineIterator*(t: PType): bool = result = t.kind == tyIter or (t.kind == tyBuiltInTypeClass and t.base.kind == tyIter) proc paramTypesMatchAux(m: var TCandidate, f, argType: PType, argSemantized, argOrig: PNode): PNode = var fMaybeStatic = f.skipTypes({tyDistinct}) arg = argSemantized argType = argType 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 # and finally start using tyTypedesc for generic types properly. if argType.kind == tyGenericParam and tfWildcard in argType.flags: argType.assignType(f) # put(m.bindings, f, argType) return argSemantized if argType.kind == tyStatic: if m.callee.kind == tyGenericBody: result = newNodeI(nkType, argOrig.info) result.typ = makeTypeFromExpr(c, arg) return else: var evaluated = c.semTryConstExpr(c, arg) if evaluated != nil: arg.typ = newTypeS(tyStatic, c) arg.typ.sons = @[evaluated.typ] arg.typ.n = evaluated argType = arg.typ var a = if c.inTypeClass > 0: argType.skipTypes({tyTypeDesc, tyFieldAccessor}) else: argType r = typeRel(m, f, a) if r != isNone and m.calleeSym != nil and m.calleeSym.kind in {skMacro, skTemplate}: # XXX: duplicating this is ugly, maybe we should move this # directly into typeRel using return-like templates case r of isConvertible, isIntConv: inc(m.convMatches) of isSubtype, isSubrange: inc(m.subtypeMatches) of isGeneric, isInferred: inc(m.genericMatches) of isInferredConvertible: inc(m.genericMatches); inc(m.convMatches) of isFromIntLit: inc(m.intConvMatches, 256) of isEqual: inc(m.exactMatches) of isNone: discard if f.kind == tyStmt and argOrig.kind == nkDo: return argOrig[bodyPos] elif f.kind == tyTypeDesc: return arg elif f.kind == tyStatic: return arg.typ.n else: return argOrig if r != isNone and f.isInlineIterator: var inlined = newTypeS(tyStatic, c) inlined.sons = @[argType] inlined.n = argSemantized put(m.bindings, f, inlined) return argSemantized case r of isConvertible: inc(m.convMatches) result = implicitConv(nkHiddenStdConv, f, copyTree(arg), m, c) of isIntConv: # I'm too lazy to introduce another ``*matches`` field, so we conflate # ``isIntConv`` and ``isIntLit`` here: inc(m.intConvMatches) result = implicitConv(nkHiddenStdConv, f, copyTree(arg), m, c) of isSubtype: inc(m.subtypeMatches) result = implicitConv(nkHiddenSubConv, f, copyTree(arg), m, c) of isSubrange: inc(m.subtypeMatches) #result = copyTree(arg) result = implicitConv(nkHiddenStdConv, f, copyTree(arg), m, c) of isInferred, isInferredConvertible: inc(m.genericMatches) if arg.kind in {nkProcDef, nkIteratorDef} + nkLambdaKinds: result = c.semInferredLambda(c, m.bindings, arg) 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) of isGeneric: inc(m.genericMatches) result = copyTree(arg) result.typ = getInstantiatedType(c, arg, m, f) # BUG: f may not be the right key! if skipTypes(result.typ, abstractVar-{tyTypeDesc}).kind in {tyTuple}: result = implicitConv(nkHiddenStdConv, f, copyTree(arg), m, c) # BUGFIX: use ``result.typ`` and not `f` here of isFromIntLit: # too lazy to introduce another ``*matches`` field, so we conflate # ``isIntConv`` and ``isIntLit`` here: inc(m.intConvMatches, 256) result = implicitConv(nkHiddenStdConv, f, copyTree(arg), m, c) of isEqual: inc(m.exactMatches) result = copyTree(arg) if skipTypes(f, abstractVar-{tyTypeDesc}).kind in {tyTuple}: result = implicitConv(nkHiddenStdConv, f, copyTree(arg), m, c) of isNone: # do not do this in ``typeRel`` as it then can't infere T in ``ref T``: if a.kind == tyProxy: inc(m.genericMatches) m.proxyMatch = true return copyTree(arg) result = userConvMatch(c, m, f, a, arg) # check for a base type match, which supports varargs[T] without [] # constructor in a call: if result == nil and f.kind == tyVarargs: if f.n != nil: result = localConvMatch(c, m, f, a, arg) else: r = typeRel(m, base(f), a) if r >= isGeneric: inc(m.convMatches) result = copyTree(arg) if r == isGeneric: result.typ = getInstantiatedType(c, arg, m, base(f)) m.baseTypeMatch = true else: result = userConvMatch(c, m, base(f), a, arg) 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 var best = -1 for i in countup(0, sonsLen(arg) - 1): if arg.sons[i].sym.kind in {skProc, skMethod, skConverter}+skIterators: copyCandidate(z, m) var r = typeRel(z, f, arg.sons[i].typ) if r != isNone: case x.state of csEmpty, csNoMatch: x = z best = i x.state = csMatch of csMatch: var 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(arg.info, "x.state is not csMatch") # ambiguous: more than one symbol fits result = nil else: # only one valid interpretation found: markUsed(arg, arg.sons[best].sym) result = paramTypesMatchAux(m, f, arg.sons[best].typ, arg.sons[best], argOrig) proc setSon(father: PNode, at: int, son: PNode) = if sonsLen(father) <= at: setLen(father.sons, at + 1) father.sons[at] = son # 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}: # a.typ == nil is valid result = a elif a.typ.isNil: let flags = if formal.kind == tyIter: {efDetermineType, efWantIterator} elif formal.kind == tyStmt: {efDetermineType, efWantStmt} else: {efDetermineType} result = c.semOperand(c, a, flags) else: result = a proc prepareOperand(c: PContext; a: PNode): PNode = if a.typ.isNil: result = c.semOperand(c, a, {efDetermineType}) else: result = a proc prepareNamedParam(a: PNode) = if a.sons[0].kind != nkIdent: var info = a.sons[0].info a.sons[0] = newIdentNode(considerAcc(a.sons[0]), info) proc arrayConstr(c: PContext, n: PNode): PType = result = newTypeS(tyArrayConstr, c) rawAddSon(result, makeRangeType(c, 0, 0, n.info)) addSonSkipIntLit(result, skipTypes(n.typ, {tyGenericInst, tyVar, tyOrdinal})) proc arrayConstr(c: PContext, info: TLineInfo): PType = result = newTypeS(tyArrayConstr, c) rawAddSon(result, makeRangeType(c, 0, -1, info)) rawAddSon(result, newTypeS(tyEmpty, c)) # needs an empty basetype! proc incrIndexType(t: PType) = assert t.kind == tyArrayConstr inc t.sons[0].n.sons[1].intVal proc matchesAux(c: PContext, n, nOrig: PNode, m: var TCandidate, marker: var TIntSet) = template checkConstraint(n: expr) {.immediate, dirty.} = if not formal.constraint.isNil: if matchNodeKinds(formal.constraint, n): # better match over other routines with no such restriction: inc(m.genericMatches, 100) else: m.state = csNoMatch return var # iterates over formal parameters f = if m.callee.kind != tyGenericBody: 1 else: 0 # iterates over the actual given arguments a = 1 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 = nil while a < n.len: if n.sons[a].kind == nkExprEqExpr: # named param # check if m.callee has such a param: prepareNamedParam(n.sons[a]) if n.sons[a].sons[0].kind != nkIdent: localError(n.sons[a].info, errNamedParamHasToBeIdent) m.state = csNoMatch return formal = getSymFromList(m.callee.n, n.sons[a].sons[0].ident, 1) if formal == nil: # no error message! m.state = csNoMatch return if containsOrIncl(marker, formal.position): # already in namedParams: localError(n.sons[a].info, errCannotBindXTwice, formal.name.s) m.state = csNoMatch return 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], nOrig.sons[a].sons[1]) if arg == nil: m.state = csNoMatch return checkConstraint(n.sons[a].sons[1]) if m.baseTypeMatch: assert(container == nil) container = newNodeIT(nkBracket, n.sons[a].info, arrayConstr(c, arg)) addSon(container, arg) setSon(m.call, formal.position + 1, container) if f != formalLen - 1: container = nil else: setSon(m.call, formal.position + 1, arg) else: # unnamed param if f >= formalLen: # too many arguments? 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(tyCString), copyTree(n.sons[a]), m, c)) else: addSon(m.call, copyTree(n.sons[a])) elif formal != nil: 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]) if (arg != nil) and m.baseTypeMatch and (container != nil): addSon(container, arg) incrIndexType(container.typ) else: m.state = csNoMatch return else: m.state = csNoMatch return else: if m.callee.n.sons[f].kind != nkSym: internalError(n.sons[a].info, "matches") return formal = m.callee.n.sons[f].sym if containsOrIncl(marker, formal.position): # already in namedParams: localError(n.sons[a].info, errCannotBindXTwice, formal.name.s) m.state = csNoMatch return 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]) if arg == nil: m.state = csNoMatch return if m.baseTypeMatch: assert(container == nil) container = newNodeIT(nkBracket, n.sons[a].info, arrayConstr(c, arg)) addSon(container, arg) setSon(m.call, formal.position + 1, implicitConv(nkHiddenStdConv, formal.typ, container, m, c)) if f != formalLen - 1: container = nil else: setSon(m.call, formal.position + 1, arg) checkConstraint(n.sons[a]) inc(a) inc(f) 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 ..