concepts.nim 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354
  1. #
  2. #
  3. # The Nim Compiler
  4. # (c) Copyright 2020 Andreas Rumpf
  5. #
  6. # See the file "copying.txt", included in this
  7. # distribution, for details about the copyright.
  8. #
  9. ## New styled concepts for Nim. See https://github.com/nim-lang/RFCs/issues/168
  10. ## for details. Note this is a first implementation and only the "Concept matching"
  11. ## section has been implemented.
  12. import ast, astalgo, semdata, lookups, lineinfos, idents, msgs, renderer, types, intsets
  13. from magicsys import addSonSkipIntLit
  14. when defined(nimPreviewSlimSystem):
  15. import std/assertions
  16. const
  17. logBindings = false
  18. ## Code dealing with Concept declarations
  19. ## --------------------------------------
  20. proc declareSelf(c: PContext; info: TLineInfo) =
  21. ## Adds the magical 'Self' symbols to the current scope.
  22. let ow = getCurrOwner(c)
  23. let s = newSym(skType, getIdent(c.cache, "Self"), c.idgen, ow, info)
  24. s.typ = newType(tyTypeDesc, nextTypeId(c.idgen), ow)
  25. s.typ.flags.incl {tfUnresolved, tfPacked}
  26. s.typ.add newType(tyEmpty, nextTypeId(c.idgen), ow)
  27. addDecl(c, s, info)
  28. proc isSelf*(t: PType): bool {.inline.} =
  29. ## Is this the magical 'Self' type?
  30. t.kind == tyTypeDesc and tfPacked in t.flags
  31. proc makeTypeDesc*(c: PContext, typ: PType): PType =
  32. if typ.kind == tyTypeDesc and not isSelf(typ):
  33. result = typ
  34. else:
  35. result = newTypeS(tyTypeDesc, c)
  36. incl result.flags, tfCheckedForDestructor
  37. result.addSonSkipIntLit(typ, c.idgen)
  38. proc semConceptDecl(c: PContext; n: PNode): PNode =
  39. ## Recursive helper for semantic checking for the concept declaration.
  40. ## Currently we only support (possibly empty) lists of statements
  41. ## containing 'proc' declarations and the like.
  42. case n.kind
  43. of nkStmtList, nkStmtListExpr:
  44. result = shallowCopy(n)
  45. for i in 0..<n.len:
  46. result[i] = semConceptDecl(c, n[i])
  47. of nkProcDef..nkIteratorDef, nkFuncDef:
  48. result = c.semExpr(c, n, {efWantStmt})
  49. of nkTypeClassTy:
  50. result = shallowCopy(n)
  51. for i in 0..<n.len-1:
  52. result[i] = n[i]
  53. result[^1] = semConceptDecl(c, n[^1])
  54. of nkCommentStmt:
  55. result = n
  56. else:
  57. localError(c.config, n.info, "unexpected construct in the new-styled concept: " & renderTree(n))
  58. result = n
  59. proc semConceptDeclaration*(c: PContext; n: PNode): PNode =
  60. ## Semantic checking for the concept declaration. Runs
  61. ## when we process the concept itself, not its matching process.
  62. assert n.kind == nkTypeClassTy
  63. inc c.inConceptDecl
  64. openScope(c)
  65. declareSelf(c, n.info)
  66. result = semConceptDecl(c, n)
  67. rawCloseScope(c)
  68. dec c.inConceptDecl
  69. ## Concept matching
  70. ## ----------------
  71. type
  72. MatchCon = object ## Context we pass around during concept matching.
  73. inferred: seq[(PType, PType)] ## we need a seq here so that we can easily undo inferences \
  74. ## that turned out to be wrong.
  75. marker: IntSet ## Some protection against wild runaway recursions.
  76. potentialImplementation: PType ## the concrete type that might match the concept we try to match.
  77. magic: TMagic ## mArrGet and mArrPut is wrong in system.nim and
  78. ## cannot be fixed that easily.
  79. ## Thus we special case it here.
  80. proc existingBinding(m: MatchCon; key: PType): PType =
  81. ## checks if we bound the type variable 'key' already to some
  82. ## concrete type.
  83. for i in 0..<m.inferred.len:
  84. if m.inferred[i][0] == key: return m.inferred[i][1]
  85. return nil
  86. proc conceptMatchNode(c: PContext; n: PNode; m: var MatchCon): bool
  87. proc matchType(c: PContext; f, a: PType; m: var MatchCon): bool =
  88. ## The heart of the concept matching process. 'f' is the formal parameter of some
  89. ## routine inside the concept that we're looking for. 'a' is the formal parameter
  90. ## of a routine that might match.
  91. const
  92. ignorableForArgType = {tyVar, tySink, tyLent, tyOwned, tyGenericInst, tyAlias, tyInferred}
  93. case f.kind
  94. of tyAlias:
  95. result = matchType(c, f.lastSon, a, m)
  96. of tyTypeDesc:
  97. if isSelf(f):
  98. #let oldLen = m.inferred.len
  99. result = matchType(c, a, m.potentialImplementation, m)
  100. #echo "self is? ", result, " ", a.kind, " ", a, " ", m.potentialImplementation, " ", m.potentialImplementation.kind
  101. #m.inferred.setLen oldLen
  102. #echo "A for ", result, " to ", typeToString(a), " to ", typeToString(m.potentialImplementation)
  103. else:
  104. if a.kind == tyTypeDesc and f.len == a.len:
  105. for i in 0..<a.len:
  106. if not matchType(c, f[i], a[i], m): return false
  107. return true
  108. else:
  109. result = false
  110. of tyGenericInvocation:
  111. result = false
  112. if a.kind == tyGenericInst and a[0].kind == tyGenericBody:
  113. if sameType(f[0], a[0]) and f.len == a.len-1:
  114. for i in 1 ..< f.len:
  115. if not matchType(c, f[i], a[i], m): return false
  116. return true
  117. of tyGenericParam:
  118. let ak = a.skipTypes({tyVar, tySink, tyLent, tyOwned})
  119. if ak.kind in {tyTypeDesc, tyStatic} and not isSelf(ak):
  120. result = false
  121. else:
  122. let old = existingBinding(m, f)
  123. if old == nil:
  124. if f.len > 0 and f[0].kind != tyNone:
  125. # also check the generic's constraints:
  126. let oldLen = m.inferred.len
  127. result = matchType(c, f[0], a, m)
  128. m.inferred.setLen oldLen
  129. if result:
  130. when logBindings: echo "A adding ", f, " ", ak
  131. m.inferred.add((f, ak))
  132. elif m.magic == mArrGet and ak.kind in {tyArray, tyOpenArray, tySequence, tyVarargs, tyCstring, tyString}:
  133. when logBindings: echo "B adding ", f, " ", lastSon ak
  134. m.inferred.add((f, lastSon ak))
  135. result = true
  136. else:
  137. when logBindings: echo "C adding ", f, " ", ak
  138. m.inferred.add((f, ak))
  139. #echo "binding ", typeToString(ak), " to ", typeToString(f)
  140. result = true
  141. elif not m.marker.containsOrIncl(old.id):
  142. result = matchType(c, old, ak, m)
  143. if m.magic == mArrPut and ak.kind == tyGenericParam:
  144. result = true
  145. else:
  146. result = false
  147. #echo "B for ", result, " to ", typeToString(a), " to ", typeToString(m.potentialImplementation)
  148. of tyVar, tySink, tyLent, tyOwned:
  149. # modifiers in the concept must be there in the actual implementation
  150. # too but not vice versa.
  151. if a.kind == f.kind:
  152. result = matchType(c, f[0], a[0], m)
  153. elif m.magic == mArrPut:
  154. result = matchType(c, f[0], a, m)
  155. else:
  156. result = false
  157. of tyEnum, tyObject, tyDistinct:
  158. result = sameType(f, a)
  159. of tyEmpty, tyString, tyCstring, tyPointer, tyNil, tyUntyped, tyTyped, tyVoid:
  160. result = a.skipTypes(ignorableForArgType).kind == f.kind
  161. of tyBool, tyChar, tyInt..tyUInt64:
  162. let ak = a.skipTypes(ignorableForArgType)
  163. result = ak.kind == f.kind or ak.kind == tyOrdinal or
  164. (ak.kind == tyGenericParam and ak.len > 0 and ak[0].kind == tyOrdinal)
  165. of tyConcept:
  166. let oldLen = m.inferred.len
  167. let oldPotentialImplementation = m.potentialImplementation
  168. m.potentialImplementation = a
  169. result = conceptMatchNode(c, f.n.lastSon, m)
  170. m.potentialImplementation = oldPotentialImplementation
  171. if not result:
  172. m.inferred.setLen oldLen
  173. of tyArray, tyTuple, tyVarargs, tyOpenArray, tyRange, tySequence, tyRef, tyPtr,
  174. tyGenericInst:
  175. result = false
  176. let ak = a.skipTypes(ignorableForArgType - {f.kind})
  177. if ak.kind == f.kind and f.len == ak.len:
  178. for i in 0..<ak.len:
  179. if not matchType(c, f[i], ak[i], m): return false
  180. return true
  181. of tyOr:
  182. let oldLen = m.inferred.len
  183. if a.kind == tyOr:
  184. # say the concept requires 'int|float|string' if the potentialImplementation
  185. # says 'int|string' that is good enough.
  186. var covered = 0
  187. for i in 0..<f.len:
  188. for j in 0..<a.len:
  189. let oldLenB = m.inferred.len
  190. let r = matchType(c, f[i], a[j], m)
  191. if r:
  192. inc covered
  193. break
  194. m.inferred.setLen oldLenB
  195. result = covered >= a.len
  196. if not result:
  197. m.inferred.setLen oldLen
  198. else:
  199. result = false
  200. for i in 0..<f.len:
  201. result = matchType(c, f[i], a, m)
  202. if result: break # and remember the binding!
  203. m.inferred.setLen oldLen
  204. of tyNot:
  205. if a.kind == tyNot:
  206. result = matchType(c, f[0], a[0], m)
  207. else:
  208. let oldLen = m.inferred.len
  209. result = not matchType(c, f[0], a, m)
  210. m.inferred.setLen oldLen
  211. of tyAnything:
  212. result = true
  213. of tyOrdinal:
  214. result = isOrdinalType(a, allowEnumWithHoles = false) or a.kind == tyGenericParam
  215. else:
  216. result = false
  217. proc matchReturnType(c: PContext; f, a: PType; m: var MatchCon): bool =
  218. ## Like 'matchType' but with extra logic dealing with proc return types
  219. ## which can be nil or the 'void' type.
  220. if f.isEmptyType:
  221. result = a.isEmptyType
  222. elif a == nil:
  223. result = false
  224. else:
  225. result = matchType(c, f, a, m)
  226. proc matchSym(c: PContext; candidate: PSym, n: PNode; m: var MatchCon): bool =
  227. ## Checks if 'candidate' matches 'n' from the concept body. 'n' is a nkProcDef
  228. ## or similar.
  229. # watch out: only add bindings after a completely successful match.
  230. let oldLen = m.inferred.len
  231. let can = candidate.typ.n
  232. let con = n[0].sym.typ.n
  233. if can.len < con.len:
  234. # too few arguments, cannot be a match:
  235. return false
  236. let common = min(can.len, con.len)
  237. for i in 1 ..< common:
  238. if not matchType(c, con[i].typ, can[i].typ, m):
  239. m.inferred.setLen oldLen
  240. return false
  241. if not matchReturnType(c, n[0].sym.typ[0], candidate.typ[0], m):
  242. m.inferred.setLen oldLen
  243. return false
  244. # all other parameters have to be optional parameters:
  245. for i in common ..< can.len:
  246. assert can[i].kind == nkSym
  247. if can[i].sym.ast == nil:
  248. # has too many arguments one of which is not optional:
  249. m.inferred.setLen oldLen
  250. return false
  251. return true
  252. proc matchSyms(c: PContext, n: PNode; kinds: set[TSymKind]; m: var MatchCon): bool =
  253. ## Walk the current scope, extract candidates which the same name as 'n[namePos]',
  254. ## 'n' is the nkProcDef or similar from the concept that we try to match.
  255. let candidates = searchInScopesAllCandidatesFilterBy(c, n[namePos].sym.name, kinds)
  256. for candidate in candidates:
  257. #echo "considering ", typeToString(candidate.typ), " ", candidate.magic
  258. m.magic = candidate.magic
  259. if matchSym(c, candidate, n, m): return true
  260. result = false
  261. proc conceptMatchNode(c: PContext; n: PNode; m: var MatchCon): bool =
  262. ## Traverse the concept's AST ('n') and see if every declaration inside 'n'
  263. ## can be matched with the current scope.
  264. case n.kind
  265. of nkStmtList, nkStmtListExpr:
  266. for i in 0..<n.len:
  267. if not conceptMatchNode(c, n[i], m):
  268. return false
  269. return true
  270. of nkProcDef, nkFuncDef:
  271. # procs match any of: proc, template, macro, func, method, converter.
  272. # The others are more specific.
  273. # XXX: Enforce .noSideEffect for 'nkFuncDef'? But then what are the use cases...
  274. const filter = {skProc, skTemplate, skMacro, skFunc, skMethod, skConverter}
  275. result = matchSyms(c, n, filter, m)
  276. of nkTemplateDef:
  277. result = matchSyms(c, n, {skTemplate}, m)
  278. of nkMacroDef:
  279. result = matchSyms(c, n, {skMacro}, m)
  280. of nkConverterDef:
  281. result = matchSyms(c, n, {skConverter}, m)
  282. of nkMethodDef:
  283. result = matchSyms(c, n, {skMethod}, m)
  284. of nkIteratorDef:
  285. result = matchSyms(c, n, {skIterator}, m)
  286. of nkCommentStmt:
  287. result = true
  288. else:
  289. # error was reported earlier.
  290. result = false
  291. proc conceptMatch*(c: PContext; concpt, arg: PType; bindings: var TIdTable; invocation: PType): bool =
  292. ## Entry point from sigmatch. 'concpt' is the concept we try to match (here still a PType but
  293. ## we extract its AST via 'concpt.n.lastSon'). 'arg' is the type that might fullfill the
  294. ## concept's requirements. If so, we return true and fill the 'bindings' with pairs of
  295. ## (typeVar, instance) pairs. ('typeVar' is usually simply written as a generic 'T'.)
  296. ## 'invocation' can be nil for atomic concepts. For non-atomic concepts, it contains the
  297. ## `C[S, T]` parent type that we look for. We need this because we need to store bindings
  298. ## for 'S' and 'T' inside 'bindings' on a successful match. It is very important that
  299. ## we do not add any bindings at all on an unsuccessful match!
  300. var m = MatchCon(inferred: @[], potentialImplementation: arg)
  301. result = conceptMatchNode(c, concpt.n.lastSon, m)
  302. if result:
  303. for (a, b) in m.inferred:
  304. if b.kind == tyGenericParam:
  305. var dest = b
  306. while true:
  307. dest = existingBinding(m, dest)
  308. if dest == nil or dest.kind != tyGenericParam: break
  309. if dest != nil:
  310. bindings.idTablePut(a, dest)
  311. when logBindings: echo "A bind ", a, " ", dest
  312. else:
  313. bindings.idTablePut(a, b)
  314. when logBindings: echo "B bind ", a, " ", b
  315. # we have a match, so bind 'arg' itself to 'concpt':
  316. bindings.idTablePut(concpt, arg)
  317. # invocation != nil means we have a non-atomic concept:
  318. if invocation != nil and arg.kind == tyGenericInst and invocation.len == arg.len-1:
  319. # bind even more generic parameters
  320. assert invocation.kind == tyGenericInvocation
  321. for i in 1 ..< invocation.len:
  322. bindings.idTablePut(invocation[i], arg[i])