# # # The Nim 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, nimfix.pretty when not defined(noDocgen): import docgen type TCandidateState* = enum csEmpty, csMatch, csNoMatch CandidateError* = object sym*: PSym unmatchedVarParam*: int diagnostics*: seq[string] CandidateErrors* = seq[CandidateError] TCandidate* = 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 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. # this is used 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 isNoCall*: bool # misused for generic type instantiations C[T] inferredTypes: seq[PType] # inferred types during the current signature # matching. they will be reset if the matching # is not successful. may replace the bindings # table in the future. diagnostics*: seq[string] # when this is not nil, the matching process # will collect extra diagnostics that will be # displayed to the user. # triggered when overload resolution fails # or when the explain pragma is used. may be # triggered with an idetools command in the # future. mutabilityProblem*: uint8 # tyVar mismatch inheritancePenalty: int # to prefer closest father object type 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? proc markUsed*(info: TLineInfo, s: PSym; usageSym: var PSym) template hasFauxMatch*(c: TCandidate): bool = c.fauxMatch != tyNone 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(c: var TCandidate, key, val: PType) {.inline.} = idTablePut(c.bindings, key, val.skipIntLit) proc initCandidate*(ctx: PContext, c: var TCandidate, callee: PSym, binding: PNode, calleeScope = -1, diagnostics = false) = initCandidateAux(ctx, c, callee.typ) c.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 else: c.calleeScope = calleeScope c.diagnostics = if diagnostics: @[] else: nil c.magic = c.calleeSym.magic initIdTable(c.bindings) 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 internalAssert bound != nil if formalTypeParam.kind == tyTypeDesc: if bound.kind != tyTypeDesc: bound = makeTypeDesc(ctx, bound) else: bound = bound.skipTypes({tyTypeDesc}) put(c, 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 var isvar = 1 while true: case t.kind of tyGenericInst, tyArray, tyRef, tyPtr, tyDistinct, tyOpenArray, tyVarargs, tySet, tyRange, tySequence, tyGenericBody: t = t.lastSon inc result of tyVar: t = t.sons[0] inc result inc isvar of tyTypeDesc: t = t.lastSon if t.kind == tyEmpty: break inc result of tyGenericInvocation, tyTuple, tyProc: result += ord(t.kind == tyGenericInvocation) for i in 0 .. y: winner = 1 else: winner = -1 elif x > y: if winner != 1: # contradiction return 0 else: if winner != -1: return 0 result = winner when false: var x, y: int for i in 1 .. = 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 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]) proc isObjectSubtype(c: var TCandidate; a, f, fGenericOrigin: PType): int = var t = a assert t.kind == tyObject var depth = 0 var last = a while t != nil and not sameObjectTypes(f, t): assert t.kind == tyObject t = t.sons[0] if t == nil: break last = t t = skipTypes(t, skipPtrs) inc depth if t != nil: genericParamPut(c, last, fGenericOrigin) result = depth else: result = -1 type SkippedPtr = enum skippedNone, skippedRef, skippedPtr proc skipToObject(t: PType; skipped: var SkippedPtr): PType = var r = t # we're allowed to skip one level of ptr/ref: var ptrs = 0 while r != nil: case r.kind of tyGenericInvocation: r = r.sons[0] of tyRef: inc ptrs skipped = skippedRef r = r.lastSon of tyPtr: inc ptrs skipped = skippedPtr r = r.lastSon of tyGenericBody, tyGenericInst, tyAlias: r = r.lastSon else: break if r.kind == tyObject and ptrs <= 1: result = r proc isGenericSubtype(c: var TCandidate; a, f: PType, d: var int, fGenericOrigin: PType = nil): bool = assert f.kind in {tyGenericInst, tyGenericInvocation, tyGenericBody} var askip = skippedNone var fskip = skippedNone var t = a.skipToObject(askip) let r = f.skipToObject(fskip) if r == nil: return false var depth = 0 var last = a # 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] if t == nil: break last = t t = t.skipToObject(askip) inc depth if t != nil and askip == fskip: genericParamPut(c, last, fGenericOrigin) d = depth result = true 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 = ## For example we have: ## .. code-block:: 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: ## - matches f=T to a=Q. Since f is metatype, we resolve it ## to int (which is already known at this point). So in this case ## Q=int mapping will be saved to c.bindings. ## - matches f=S to a=W. Both of these metatypes are unknown, so we ## return with isBothMetaConvertible to ask for rerun. ## - matches f=S to a=W. At this point the return type of innerProc ## is known (we get it from c.bindings). We can use that value ## to match with f, and save back to c.bindings. var f = f a = a if a.isMetaType: let aResolved = PType(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 # 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 isBothMetaConvertible # Note that this typeRel call will save a's resolved type into c.bindings let reverseRel = typeRel(c, a, f) if reverseRel >= isGeneric: result = isInferred #inc c.genericMatches 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): 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): PType = var typeClass = ff.skipTypes({tyUserTypeClassInst}) body = typeClass.n[3] if c.inTypeClass > 4: localError(body.info, $body & " too nested for type matching") return nil openScope(c) inc c.inTypeClass defer: dec c.inTypeClass closeScope(c) var typeParams: seq[(PSym, PType)] 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: PSym template paramSym(kind): untyped = newSym(kind, typeParamName, typeClass.sym, typeClass.sym.info) block addTypeParam: for prev in typeParams: if prev[1].id == typ.id: param = paramSym prev[0].kind param.typ = prev[0].typ break addTypeParam case typ.kind of tyStatic: param = paramSym skConst param.typ = typ.exactReplica if typ.n == nil: param.typ.flags.incl tfInferrableStatic else: param.ast = typ.n of tyUnknown: param = paramSym skVar param.typ = typ.exactReplica else: param = paramSym skType param.typ = if typ.isMetaType: c.newTypeWithSons(tyInferred, @[typ]) else: makeTypeDesc(c, typ) typeParams.safeAdd((param, typ)) addDecl(c, param) for param in typeClass.n[0]: var dummyName: PNode dummyType: PType let modifier = case param.kind of nkVarTy: tyVar of nkRefTy: tyRef of nkPtrTy: tyPtr of nkStaticTy: tyStatic of nkTypeOfExpr: tyTypeDesc else: tyNone if modifier != tyNone: dummyName = param[0] dummyType = c.makeTypeWithModifier(modifier, a) if modifier == tyTypeDesc: dummyType.flags.incl tfExplicit else: dummyName = param dummyType = a internalAssert dummyName.kind == nkIdent var dummyParam = newSym(if modifier == tyTypeDesc: skType else: skVar, dummyName.ident, typeClass.sym, typeClass.sym.info) dummyParam.typ = dummyType addDecl(c, dummyParam) var oldWriteHook: type(writelnHook) diagnostics: seq[string] errorPrefix: string flags: TExprFlags = {} collectDiagnostics = m.diagnostics != nil or sfExplain in typeClass.sym.flags if collectDiagnostics: oldWriteHook = writelnHook # XXX: we can't write to m.diagnostics directly, because # Nim doesn't support capturing var params in closures diagnostics = @[] flags = {efExplain} writelnHook = proc (s: string) = if errorPrefix == nil: errorPrefix = typeClass.sym.name.s & ":" let msg = s.replace("Error:", errorPrefix) if oldWriteHook != nil: oldWriteHook msg diagnostics.add msg var checkedBody = c.semTryExpr(c, body.copyTree, flags) if collectDiagnostics: writelnHook = oldWriteHook for msg in diagnostics: m.diagnostics.safeAdd msg if checkedBody == nil: return nil # The inferrable type params have been identified during the semTryExpr above. # We need to put them in the current sigmatch's binding table in order for them # to be resolvable while matching the rest of the parameters for p in typeParams: put(m, p[1], p[0].typ) if ff.kind == tyUserTypeClassInst: result = generateTypeInstance(c, m.bindings, typeClass.sym.info, ff) else: result = copyType(ff, ff.owner, true) result.n = checkedBody proc shouldSkipDistinct(rules: PNode, callIdent: PIdent): bool = if rules.kind == nkWith: for r in rules: if r.considerQuotedIdent == callIdent: return true return false else: for r in rules: if r.considerQuotedIdent == 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 tryResolvingStaticExpr(c: var TCandidate, n: PNode, allowUnresolved = false): PNode = # Consider this example: # type Value[N: static[int]] = object # proc foo[N](a: Value[N], r: range[0..(N-1)]) # Here, N-1 will be initially nkStaticExpr that can be evaluated only after # N is bound to a concrete value during the matching of the first param. # This proc is used to evaluate such static expressions. let instantiated = replaceTypesInBody(c.c, c.bindings, n, nil, allowMetaTypes = allowUnresolved) result = c.c.semExpr(c.c, instantiated) proc inferStaticParam*(lhs: PNode, rhs: BiggestInt): PType = # This is a simple integer arithimetic equation solver, # capable of deriving the value of a static parameter in # expressions such as (N + 5) / 2 = rhs # # Preconditions: # # * The input of this proc must be semantized # - all templates should be expanded # - aby constant folding possible should already be performed # # * There must be exactly one unresolved static parameter # # Result: # # The proc will return the inferred static type with the `n` field # populated with the inferred value. # # `nil` will be returned if the inference was not possible # if lhs.kind in nkCallKinds and lhs[0].kind == nkSym: case lhs[0].sym.magic of mUnaryLt: return inferStaticParam(lhs[1], rhs + 1) of mAddI, mAddU, mInc, mSucc: if lhs[1].kind == nkIntLit: return inferStaticParam(lhs[2], rhs - lhs[1].intVal) elif lhs[2].kind == nkIntLit: return inferStaticParam(lhs[1], rhs - lhs[2].intVal) of mDec, mSubI, mSubU, mPred: if lhs[1].kind == nkIntLit: return inferStaticParam(lhs[2], lhs[1].intVal - rhs) elif lhs[2].kind == nkIntLit: return inferStaticParam(lhs[1], rhs + lhs[2].intVal) of mMulI, mMulU: if lhs[1].kind == nkIntLit: if rhs mod lhs[1].intVal == 0: return inferStaticParam(lhs[2], rhs div lhs[1].intVal) elif lhs[2].kind == nkIntLit: if rhs mod lhs[2].intVal == 0: return inferStaticParam(lhs[1], rhs div lhs[2].intVal) of mDivI, mDivU: if lhs[1].kind == nkIntLit: if lhs[1].intVal mod rhs == 0: return inferStaticParam(lhs[2], lhs[1].intVal div rhs) elif lhs[2].kind == nkIntLit: return inferStaticParam(lhs[1], lhs[2].intVal * rhs) of mShlI: if lhs[2].kind == nkIntLit: return inferStaticParam(lhs[1], rhs shr lhs[2].intVal) of mShrI: if lhs[2].kind == nkIntLit: return inferStaticParam(lhs[1], rhs shl lhs[2].intVal) of mUnaryMinusI: return inferStaticParam(lhs[1], -rhs) of mUnaryPlusI, mToInt, mToBiggestInt: return inferStaticParam(lhs[1], rhs) else: discard elif lhs.kind == nkSym and lhs.typ.kind == tyStatic and lhs.typ.n == nil: lhs.typ.n = newIntNode(nkIntLit, rhs) return lhs.typ return nil proc failureToInferStaticParam(n: PNode) = let staticParam = n.findUnresolvedStatic let name = if staticParam != nil: staticParam.sym.name.s else: "unknown" localError(n.info, errCannotInferStaticParam, name) proc inferStaticsInRange(c: var TCandidate, inferred, concrete: PType): TTypeRelation = let lowerBound = tryResolvingStaticExpr(c, inferred.n[0], allowUnresolved = true) let upperBound = tryResolvingStaticExpr(c, inferred.n[1], allowUnresolved = true) template doInferStatic(c: var TCandidate, e: PNode, r: BiggestInt) = var exp = e var rhs = r var inferred = inferStaticParam(exp, rhs) if inferred != nil: put(c, inferred, inferred) return isGeneric else: failureToInferStaticParam exp if lowerBound.kind == nkIntLit: if upperBound.kind == nkIntLit: if lengthOrd(concrete) == upperBound.intVal - lowerBound.intVal + 1: return isGeneric else: return isNone doInferStatic(c, upperBound, lengthOrd(concrete) + lowerBound.intVal - 1) elif upperBound.kind == nkIntLit: doInferStatic(c, lowerBound, upperBound.intVal + 1 - lengthOrd(concrete)) template subtypeCheck() = if result <= isSubrange and f.lastSon.skipTypes(abstractInst).kind in {tyRef, tyPtr, tyVar}: result = isNone 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: if aOrig != nil: put(c, f, aOrig) return isGeneric assert(aOrig != nil) var useTypeLoweringRuleInTypeClass = c.c.inTypeClass > 0 and not c.isNoCall and f.kind != tyTypeDesc and tfExplicit notin aOrig.flags aOrig = if useTypeLoweringRuleInTypeClass: aOrig.skipTypes({tyTypeDesc, tyFieldAccessor}) else: aOrig if aOrig.kind == tyInferred: let prev = aOrig.previouslyInferred if prev != nil: return typeRel(c, f, prev) else: var candidate = f case f.kind of tyGenericParam: var prev = PType(idTableGet(c.bindings, f)) if prev != nil: candidate = prev of tyFromExpr: let computedType = tryResolvingStaticExpr(c, f.n).typ case computedType.kind of tyTypeDesc: candidate = computedType.base of tyStatic: candidate = computedType else: localError(f.n.info, errTypeExpected) else: discard result = typeRel(c, aOrig.base, candidate) if result != isNone: c.inferredTypes.safeAdd aOrig aOrig.sons.add candidate result = isEqual return # var and static arguments match regular modifier-free types var 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 in {tyGenericInst, tyAlias} and skipTypes(f, {tyVar}).kind notin { tyGenericBody, tyGenericInvocation, tyGenericInst, tyGenericParam} + tyTypeClasses: return typeRel(c, f, lastSon(a)) if a.isResolvedUserTypeClass: return typeRel(c, f, a.lastSon) template bindingRet(res) = if doBind: let bound = aOrig.skipTypes({tyRange}).skipIntLit put(c, f, bound) return res template considerPreviousT(body: untyped) = 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 # but ensure that '[T: A|A]' matches as good as '[T: A]' (bug #2219): result = isGeneric for branch in a.sons: let x = typeRel(c, f, branch, false) if x == isNone: return isNone if x < result: result = x of tyAnd: # seq[Sortable and Iterable] vs seq[Sortable] # only one match is enough for branch in a.sons: let x = typeRel(c, f, branch, false) if x != isNone: return if x >= isGeneric: isGeneric else: x result = 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 of tyUserTypeClass, tyUserTypeClassInst: # consider this: 'var g: Node' *within* a concept where 'Node' # is a concept too (tgraph) let x = typeRel(c, a, f, false) if x >= isGeneric: return isGeneric 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: if f.base.kind == tyNone: return isGeneric result = typeRel(c, base(f), base(a)) # 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: for i in 0..1: if f.n[i].kind == nkStaticExpr: f.n.sons[i] = tryResolvingStaticExpr(c, f.n[i]) 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) 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)) if prev == nil: put(c, fRange, a.sons[0]) fRange = a else: fRange = prev result = typeRel(c, f.sons[1].skipTypes({tyTypeDesc}), a.sons[1].skipTypes({tyTypeDesc})) if result < isGeneric: return isNone if fRange.rangeHasUnresolvedStatic: return inferStaticsInRange(c, fRange, a) elif c.c.inTypeClass > 0 and aRange.rangeHasUnresolvedStatic: return inferStaticsInRange(c, aRange, f) elif lengthOrd(fRange) != lengthOrd(a): 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]: if f.kind == tyVarargs: if tfOldSchoolExprStmt in f.sons[0].flags: if f.sons[0].kind == tyExpr: return elif f.sons[0].kind == tyStmt: return case a.kind of tyOpenArray, tyVarargs: result = typeRel(c, base(f), base(a)) if result < isGeneric: result = isNone 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 of tyString: if f.kind == tyOpenArray: if f.sons[0].kind == tyChar: result = isConvertible elif f.sons[0].kind == tyGenericParam and a.len > 0 and typeRel(c, base(f), base(a)) >= 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(c, a, f, nil) if depth > 0: inc(c.inheritancePenalty, depth) result = isSubtype of tyDistinct: 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) 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) subtypeC
#
#
#            Nim's Runtime Library
#        (c) Copyright 2012 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

## This module contains helpers for parsing tokens, numbers, integers, floats,
## identifiers, etc.
##
## To unpack raw bytes look at the `streams <streams.html>`_ module.
##
##   ```nim test
##   let logs = @["2019-01-10: OK_", "2019-01-11: FAIL_", "2019-01: aaaa"]
##   var outp: seq[string]
##
##   for log in logs:
##     var res: string
##     if parseUntil(log, res, ':') == 10: # YYYY-MM-DD == 10
##       outp.add(res & " - " & captureBetween(log, ' ', '_'))
##   doAssert outp == @["2019-01-10 - OK", "2019-01-11 - FAIL"]
##   ```
##
##   ```nim test
##   from std/strutils import Digits, parseInt
##
##   let
##     input1 = "2019 school start"
##     input2 = "3 years back"
##     startYear = input1[0 .. skipWhile(input1, Digits)-1] # 2019
##     yearsBack = input2[0 .. skipWhile(input2, Digits)-1] # 3
##     examYear = parseInt(startYear) + parseInt(yearsBack)
##   doAssert "Examination is in " & $examYear == "Examination is in 2022"
##   ```
##
## **See also:**
## * `strutils module<strutils.html>`_ for combined and identical parsing proc's
## * `json module<json.html>`_ for a JSON parser
## * `parsecfg module<parsecfg.html>`_ for a configuration file parser
## * `parsecsv module<parsecsv.html>`_ for a simple CSV (comma separated value) parser
## * `parseopt module<parseopt.html>`_ for a command line parser
## * `parsexml module<parsexml.html>`_ for a XML / HTML parser
## * `other parsers<lib.html#pure-libraries-parsers>`_ for other parsers

{.push debugger: off.} # the user does not want to trace a part
                       # of the standard library!

include "system/inclrtl"

template toOa(s: string): openArray[char] = openArray[char](s)

const
  Whitespace = {' ', '\t', '\v', '\r', '\l', '\f'}
  IdentChars = {'a'..'z', 'A'..'Z', '0'..'9', '_'}
  IdentStartChars = {'a'..'z', 'A'..'Z', '_'}
    ## copied from strutils

proc toLower(c: char): char {.inline.} =
  result = if c in {'A'..'Z'}: chr(ord(c)-ord('A')+ord('a')) else: c

proc parseBin*[T: SomeInteger](s: openArray[char], number: var T, maxLen = 0): int {.noSideEffect.} =
  ## Parses a binary number and stores its value in ``number``.
  ##
  ## Returns the number of the parsed characters or 0 in case of an error.
  ## If error, the value of ``number`` is not changed.
  ##
  ## If ``maxLen == 0``, the parsing continues until the first non-bin character
  ## or to the end of the string. Otherwise, no more than ``maxLen`` characters
  ## are parsed starting from the ``start`` position.
  ##
  ## It does not check for overflow. If the value represented by the string is
  ## too big to fit into ``number``, only the value of last fitting characters
  ## will be stored in ``number`` without producing an error.
  runnableExamples:
    var num: int
    doAssert parseBin("0100_1110_0110_1001_1110_1101", num) == 29
    doAssert num == 5138925
    doAssert parseBin("3", num) == 0
    var num8: int8
    doAssert parseBin("0b_0100_1110_0110_1001_1110_1101", num8) == 32
    doAssert num8 == 0b1110_1101'i8
    doAssert parseBin("0b_0100_1110_0110_1001_1110_1101", num8, 3, 9) == 9
    doAssert num8 == 0b0100_1110'i8
    var num8u: uint8
    doAssert parseBin("0b_0100_1110_0110_1001_1110_1101", num8u) == 32
    doAssert num8u == 237
    var num64: int64
    doAssert parseBin("0100111001101001111011010100111001101001", num64) == 40
    doAssert num64 == 336784608873
  var i = 0
  var output = T(0)
  var foundDigit = false
  let last = min(s.len, if maxLen == 0: s.len else: i + maxLen)
  if i + 1 < last and s[i] == '0' and (s[i+1] in {'b', 'B'}): inc(i, 2)
  while i < last:
    case s[i]
    of '_': discard
    of '0'..'1':
      output = output shl 1 or T(ord(s[i]) - ord('0'))
      foundDigit = true
    else: break
    inc(i)
  if foundDigit:
    number = output
    result = i

proc parseOct*[T: SomeInteger](s: openArray[char], number: var T, maxLen = 0): int {.noSideEffect.} =
  ## Parses an octal number and stores its value in ``number``.
  ##
  ## Returns the number of the parsed characters or 0 in case of an error.
  ## If error, the value of ``number`` is not changed.
  ##
  ## If ``maxLen == 0``, the parsing continues until the first non-oct character
  ## or to the end of the string. Otherwise, no more than ``maxLen`` characters
  ## are parsed starting from the ``start`` position.
  ##
  ## It does not check for overflow. If the value represented by the string is
  ## too big to fit into ``number``, only the value of last fitting characters
  ## will be stored in ``number`` without producing an error.
  runnableExamples:
    var num: int
    doAssert parseOct("0o23464755", num) == 10
    doAssert num == 5138925
    doAssert parseOct("8", num) == 0
    var num8: int8
    doAssert parseOct("0o_1464_755", num8) == 11
    doAssert num8 == -19
    doAssert parseOct("0o_1464_755", num8, 3, 3) == 3
    doAssert num8 == 102
    var num8u: uint8
    doAssert parseOct("1464755", num8u) == 7
    doAssert num8u == 237
    var num64: int64
    doAssert parseOct("2346475523464755", num64) == 16
    doAssert num64 == 86216859871725
  var i = 0
  var output = T(0)
  var foundDigit = false
  let last = min(s.len, if maxLen == 0: s.len else: i + maxLen)
  if i + 1 < last and s[i] == '0' and (s[i+1] in {'o', 'O'}): inc(i, 2)
  while i < last:
    case s[i]
    of '_': discard
    of '0'..'7':
      output = output shl 3 or T(ord(s[i]) - ord('0'))
      foundDigit = true
    else: break
    inc(i)
  if foundDigit:
    number = output
    result = i

proc parseHex*[T: SomeInteger](s: openArray[char], number: var T, maxLen = 0): int {.noSideEffect.} =
  ## Pars