summary refs log tree commit diff stats
path: root/compiler/concepts.nim
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/concepts.nim')
-rw-r--r--compiler/concepts.nim343
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])