diff options
Diffstat (limited to 'compiler/concepts.nim')
| -rw-r--r-- | compiler/concepts.nim | 343 |
1 files changed, 343 insertions, 0 deletions
diff --git a/compiler/concepts.nim b/compiler/concepts.nim new file mode 100644 index 000000000..d48bacdc5 --- /dev/null +++ b/compiler/concepts.nim @@ -0,0 +1,343 @@ +# +# +# The Nim Compiler +# (c) Copyright 2020 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## New styled concepts for Nim. See https://github.com/nim-lang/RFCs/issues/168 +## for details. Note this is a first implementation and only the "Concept matching" +## section has been implemented. + +import ast, astalgo, semdata, lookups, lineinfos, idents, msgs, renderer, types + +import std/intsets + +when defined(nimPreviewSlimSystem): + import std/assertions + +const + logBindings = false + +## Code dealing with Concept declarations +## -------------------------------------- + +proc declareSelf(c: PContext; info: TLineInfo) = + ## Adds the magical 'Self' symbols to the current scope. + let ow = getCurrOwner(c) + let s = newSym(skType, getIdent(c.cache, "Self"), c.idgen, ow, info) + s.typ = newType(tyTypeDesc, c.idgen, ow) + s.typ.flags.incl {tfUnresolved, tfPacked} + s.typ.add newType(tyEmpty, c.idgen, ow) + addDecl(c, s, info) + +proc semConceptDecl(c: PContext; n: PNode): PNode = + ## Recursive helper for semantic checking for the concept declaration. + ## Currently we only support (possibly empty) lists of statements + ## containing 'proc' declarations and the like. + case n.kind + of nkStmtList, nkStmtListExpr: + result = shallowCopy(n) + for i in 0..<n.len: + result[i] = semConceptDecl(c, n[i]) + of nkProcDef..nkIteratorDef, nkFuncDef: + result = c.semExpr(c, n, {efWantStmt}) + of nkTypeClassTy: + result = shallowCopy(n) + for i in 0..<n.len-1: + result[i] = n[i] + result[^1] = semConceptDecl(c, n[^1]) + of nkCommentStmt: + result = n + else: + localError(c.config, n.info, "unexpected construct in the new-styled concept: " & renderTree(n)) + result = n + +proc semConceptDeclaration*(c: PContext; n: PNode): PNode = + ## Semantic checking for the concept declaration. Runs + ## when we process the concept itself, not its matching process. + assert n.kind == nkTypeClassTy + inc c.inConceptDecl + openScope(c) + declareSelf(c, n.info) + result = semConceptDecl(c, n) + rawCloseScope(c) + dec c.inConceptDecl + +## Concept matching +## ---------------- + +type + MatchCon = object ## Context we pass around during concept matching. + inferred: seq[(PType, PType)] ## we need a seq here so that we can easily undo inferences \ + ## that turned out to be wrong. + marker: IntSet ## Some protection against wild runaway recursions. + potentialImplementation: PType ## the concrete type that might match the concept we try to match. + magic: TMagic ## mArrGet and mArrPut is wrong in system.nim and + ## cannot be fixed that easily. + ## Thus we special case it here. + +proc existingBinding(m: MatchCon; key: PType): PType = + ## checks if we bound the type variable 'key' already to some + ## concrete type. + for i in 0..<m.inferred.len: + if m.inferred[i][0] == key: return m.inferred[i][1] + return nil + +proc conceptMatchNode(c: PContext; n: PNode; m: var MatchCon): bool + +proc matchType(c: PContext; f, a: PType; m: var MatchCon): bool = + ## The heart of the concept matching process. 'f' is the formal parameter of some + ## routine inside the concept that we're looking for. 'a' is the formal parameter + ## of a routine that might match. + const + ignorableForArgType = {tyVar, tySink, tyLent, tyOwned, tyGenericInst, tyAlias, tyInferred} + case f.kind + of tyAlias: + result = matchType(c, f.skipModifier, a, m) + of tyTypeDesc: + if isSelf(f): + #let oldLen = m.inferred.len + result = matchType(c, a, m.potentialImplementation, m) + #echo "self is? ", result, " ", a.kind, " ", a, " ", m.potentialImplementation, " ", m.potentialImplementation.kind + #m.inferred.setLen oldLen + #echo "A for ", result, " to ", typeToString(a), " to ", typeToString(m.potentialImplementation) + else: + if a.kind == tyTypeDesc and f.hasElementType == a.hasElementType: + if f.hasElementType: + result = matchType(c, f.elementType, a.elementType, m) + else: + result = true # both lack it + else: + result = false + + of tyGenericInvocation: + result = false + if a.kind == tyGenericInst and a.genericHead.kind == tyGenericBody: + if sameType(f.genericHead, a.genericHead) and f.kidsLen == a.kidsLen-1: + for i in FirstGenericParamAt ..< f.kidsLen: + if not matchType(c, f[i], a[i], m): return false + return true + of tyGenericParam: + let ak = a.skipTypes({tyVar, tySink, tyLent, tyOwned}) + if ak.kind in {tyTypeDesc, tyStatic} and not isSelf(ak): + result = false + else: + let old = existingBinding(m, f) + if old == nil: + if f.hasElementType and f.elementType.kind != tyNone: + # also check the generic's constraints: + let oldLen = m.inferred.len + result = matchType(c, f.elementType, a, m) + m.inferred.setLen oldLen + if result: + when logBindings: echo "A adding ", f, " ", ak + m.inferred.add((f, ak)) + elif m.magic == mArrGet and ak.kind in {tyArray, tyOpenArray, tySequence, tyVarargs, tyCstring, tyString}: + when logBindings: echo "B adding ", f, " ", lastSon ak + m.inferred.add((f, last ak)) + result = true + else: + when logBindings: echo "C adding ", f, " ", ak + m.inferred.add((f, ak)) + #echo "binding ", typeToString(ak), " to ", typeToString(f) + result = true + elif not m.marker.containsOrIncl(old.id): + result = matchType(c, old, ak, m) + if m.magic == mArrPut and ak.kind == tyGenericParam: + result = true + else: + result = false + #echo "B for ", result, " to ", typeToString(a), " to ", typeToString(m.potentialImplementation) + + of tyVar, tySink, tyLent, tyOwned: + # modifiers in the concept must be there in the actual implementation + # too but not vice versa. + if a.kind == f.kind: + result = matchType(c, f.elementType, a.elementType, m) + elif m.magic == mArrPut: + result = matchType(c, f.elementType, a, m) + else: + result = false + of tyEnum, tyObject, tyDistinct: + result = sameType(f, a) + of tyEmpty, tyString, tyCstring, tyPointer, tyNil, tyUntyped, tyTyped, tyVoid: + result = a.skipTypes(ignorableForArgType).kind == f.kind + of tyBool, tyChar, tyInt..tyUInt64: + let ak = a.skipTypes(ignorableForArgType) + result = ak.kind == f.kind or ak.kind == tyOrdinal or + (ak.kind == tyGenericParam and ak.hasElementType and ak.elementType.kind == tyOrdinal) + of tyConcept: + let oldLen = m.inferred.len + let oldPotentialImplementation = m.potentialImplementation + m.potentialImplementation = a + result = conceptMatchNode(c, f.n.lastSon, m) + m.potentialImplementation = oldPotentialImplementation + if not result: + m.inferred.setLen oldLen + of tyArray, tyTuple, tyVarargs, tyOpenArray, tyRange, tySequence, tyRef, tyPtr, + tyGenericInst: + # ^ XXX Rewrite this logic, it's more complex than it needs to be. + result = false + let ak = a.skipTypes(ignorableForArgType - {f.kind}) + if ak.kind == f.kind and f.kidsLen == ak.kidsLen: + for i in 0..<ak.kidsLen: + if not matchType(c, f[i], ak[i], m): return false + return true + of tyOr: + let oldLen = m.inferred.len + if a.kind == tyOr: + # say the concept requires 'int|float|string' if the potentialImplementation + # says 'int|string' that is good enough. + var covered = 0 + for ff in f.kids: + for aa in a.kids: + let oldLenB = m.inferred.len + let r = matchType(c, ff, aa, m) + if r: + inc covered + break + m.inferred.setLen oldLenB + + result = covered >= a.kidsLen + if not result: + m.inferred.setLen oldLen + else: + result = false + for ff in f.kids: + result = matchType(c, ff, a, m) + if result: break # and remember the binding! + m.inferred.setLen oldLen + of tyNot: + if a.kind == tyNot: + result = matchType(c, f.elementType, a.elementType, m) + else: + let oldLen = m.inferred.len + result = not matchType(c, f.elementType, a, m) + m.inferred.setLen oldLen + of tyAnything: + result = true + of tyOrdinal: + result = isOrdinalType(a, allowEnumWithHoles = false) or a.kind == tyGenericParam + else: + result = false + +proc matchReturnType(c: PContext; f, a: PType; m: var MatchCon): bool = + ## Like 'matchType' but with extra logic dealing with proc return types + ## which can be nil or the 'void' type. + if f.isEmptyType: + result = a.isEmptyType + elif a == nil: + result = false + else: + result = matchType(c, f, a, m) + +proc matchSym(c: PContext; candidate: PSym, n: PNode; m: var MatchCon): bool = + ## Checks if 'candidate' matches 'n' from the concept body. 'n' is a nkProcDef + ## or similar. + + # watch out: only add bindings after a completely successful match. + let oldLen = m.inferred.len + + let can = candidate.typ.n + let con = n[0].sym.typ.n + + if can.len < con.len: + # too few arguments, cannot be a match: + return false + + let common = min(can.len, con.len) + for i in 1 ..< common: + if not matchType(c, con[i].typ, can[i].typ, m): + m.inferred.setLen oldLen + return false + + if not matchReturnType(c, n[0].sym.typ.returnType, candidate.typ.returnType, m): + m.inferred.setLen oldLen + return false + + # all other parameters have to be optional parameters: + for i in common ..< can.len: + assert can[i].kind == nkSym + if can[i].sym.ast == nil: + # has too many arguments one of which is not optional: + m.inferred.setLen oldLen + return false + + return true + +proc matchSyms(c: PContext, n: PNode; kinds: set[TSymKind]; m: var MatchCon): bool = + ## Walk the current scope, extract candidates which the same name as 'n[namePos]', + ## 'n' is the nkProcDef or similar from the concept that we try to match. + let candidates = searchInScopesAllCandidatesFilterBy(c, n[namePos].sym.name, kinds) + for candidate in candidates: + #echo "considering ", typeToString(candidate.typ), " ", candidate.magic + m.magic = candidate.magic + if matchSym(c, candidate, n, m): return true + result = false + +proc conceptMatchNode(c: PContext; n: PNode; m: var MatchCon): bool = + ## Traverse the concept's AST ('n') and see if every declaration inside 'n' + ## can be matched with the current scope. + case n.kind + of nkStmtList, nkStmtListExpr: + for i in 0..<n.len: + if not conceptMatchNode(c, n[i], m): + return false + return true + of nkProcDef, nkFuncDef: + # procs match any of: proc, template, macro, func, method, converter. + # The others are more specific. + # XXX: Enforce .noSideEffect for 'nkFuncDef'? But then what are the use cases... + const filter = {skProc, skTemplate, skMacro, skFunc, skMethod, skConverter} + result = matchSyms(c, n, filter, m) + of nkTemplateDef: + result = matchSyms(c, n, {skTemplate}, m) + of nkMacroDef: + result = matchSyms(c, n, {skMacro}, m) + of nkConverterDef: + result = matchSyms(c, n, {skConverter}, m) + of nkMethodDef: + result = matchSyms(c, n, {skMethod}, m) + of nkIteratorDef: + result = matchSyms(c, n, {skIterator}, m) + of nkCommentStmt: + result = true + else: + # error was reported earlier. + result = false + +proc conceptMatch*(c: PContext; concpt, arg: PType; bindings: var TypeMapping; invocation: PType): bool = + ## Entry point from sigmatch. 'concpt' is the concept we try to match (here still a PType but + ## we extract its AST via 'concpt.n.lastSon'). 'arg' is the type that might fulfill the + ## concept's requirements. If so, we return true and fill the 'bindings' with pairs of + ## (typeVar, instance) pairs. ('typeVar' is usually simply written as a generic 'T'.) + ## 'invocation' can be nil for atomic concepts. For non-atomic concepts, it contains the + ## `C[S, T]` parent type that we look for. We need this because we need to store bindings + ## for 'S' and 'T' inside 'bindings' on a successful match. It is very important that + ## we do not add any bindings at all on an unsuccessful match! + var m = MatchCon(inferred: @[], potentialImplementation: arg) + result = conceptMatchNode(c, concpt.n.lastSon, m) + if result: + for (a, b) in m.inferred: + if b.kind == tyGenericParam: + var dest = b + while true: + dest = existingBinding(m, dest) + if dest == nil or dest.kind != tyGenericParam: break + if dest != nil: + bindings.idTablePut(a, dest) + when logBindings: echo "A bind ", a, " ", dest + else: + bindings.idTablePut(a, b) + when logBindings: echo "B bind ", a, " ", b + # we have a match, so bind 'arg' itself to 'concpt': + bindings.idTablePut(concpt, arg) + # invocation != nil means we have a non-atomic concept: + if invocation != nil and arg.kind == tyGenericInst and invocation.kidsLen == arg.kidsLen-1: + # bind even more generic parameters + assert invocation.kind == tyGenericInvocation + for i in FirstGenericParamAt ..< invocation.kidsLen: + bindings.idTablePut(invocation[i], arg[i]) |