types.nim 65 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878
  1. #
  2. #
  3. # The Nim Compiler
  4. # (c) Copyright 2013 Andreas Rumpf
  5. #
  6. # See the file "copying.txt", included in this
  7. # distribution, for details about the copyright.
  8. #
  9. # this module contains routines for accessing and iterating over types
  10. import
  11. ast, astalgo, trees, msgs, platform, renderer, options,
  12. lineinfos, int128, modulegraphs, astmsgs, wordrecg
  13. import std/[intsets, strutils]
  14. when defined(nimPreviewSlimSystem):
  15. import std/[assertions, formatfloat]
  16. type
  17. TPreferedDesc* = enum
  18. preferName, # default
  19. preferDesc, # probably should become what preferResolved is
  20. preferExported,
  21. preferModuleInfo, # fully qualified
  22. preferGenericArg,
  23. preferTypeName,
  24. preferResolved, # fully resolved symbols
  25. preferMixed,
  26. # most useful, shows: symbol + resolved symbols if it differs, e.g.:
  27. # tuple[a: MyInt{int}, b: float]
  28. preferInlayHint,
  29. preferInferredEffects,
  30. TTypeRelation* = enum # order is important!
  31. isNone, isConvertible,
  32. isIntConv,
  33. isSubtype,
  34. isSubrange, # subrange of the wanted type; no type conversion
  35. # but apart from that counts as ``isSubtype``
  36. isBothMetaConvertible # generic proc parameter was matched against
  37. # generic type, e.g., map(mySeq, x=>x+1),
  38. # maybe recoverable by rerun if the parameter is
  39. # the proc's return value
  40. isInferred, # generic proc was matched against a concrete type
  41. isInferredConvertible, # same as above, but requiring proc CC conversion
  42. isGeneric,
  43. isFromIntLit, # conversion *from* int literal; proven safe
  44. isEqual
  45. ProcConvMismatch* = enum
  46. pcmNoSideEffect
  47. pcmNotGcSafe
  48. pcmNotIterator
  49. pcmDifferentCallConv
  50. proc typeToString*(typ: PType; prefer: TPreferedDesc = preferName): string
  51. proc addTypeDeclVerboseMaybe*(result: var string, conf: ConfigRef; typ: PType) =
  52. if optDeclaredLocs in conf.globalOptions:
  53. result.add typeToString(typ, preferMixed)
  54. result.addDeclaredLoc(conf, typ)
  55. else:
  56. result.add typeToString(typ)
  57. template `$`*(typ: PType): string = typeToString(typ)
  58. # ------------------- type iterator: ----------------------------------------
  59. type
  60. TTypeIter* = proc (t: PType, closure: RootRef): bool {.nimcall.} # true if iteration should stop
  61. TTypePredicate* = proc (t: PType): bool {.nimcall.}
  62. proc iterOverType*(t: PType, iter: TTypeIter, closure: RootRef): bool
  63. # Returns result of `iter`.
  64. type
  65. TParamsEquality* = enum # they are equal, but their
  66. # identifiers or their return
  67. # type differ (i.e. they cannot be
  68. # overloaded)
  69. # this used to provide better error messages
  70. paramsNotEqual, # parameters are not equal
  71. paramsEqual, # parameters are equal
  72. paramsIncompatible
  73. proc equalParams*(a, b: PNode): TParamsEquality
  74. # returns whether the parameter lists of the procs a, b are exactly the same
  75. const
  76. # TODO: Remove tyTypeDesc from each abstractX and (where necessary)
  77. # replace with typedescX
  78. abstractPtrs* = {tyVar, tyPtr, tyRef, tyGenericInst, tyDistinct, tyOrdinal,
  79. tyTypeDesc, tyAlias, tyInferred, tySink, tyLent, tyOwned}
  80. abstractVar* = {tyVar, tyGenericInst, tyDistinct, tyOrdinal, tyTypeDesc,
  81. tyAlias, tyInferred, tySink, tyLent, tyOwned}
  82. abstractRange* = {tyGenericInst, tyRange, tyDistinct, tyOrdinal, tyTypeDesc,
  83. tyAlias, tyInferred, tySink, tyOwned}
  84. abstractInstOwned* = abstractInst + {tyOwned}
  85. skipPtrs* = {tyVar, tyPtr, tyRef, tyGenericInst, tyTypeDesc, tyAlias,
  86. tyInferred, tySink, tyLent, tyOwned}
  87. # typedescX is used if we're sure tyTypeDesc should be included (or skipped)
  88. typedescPtrs* = abstractPtrs + {tyTypeDesc}
  89. typedescInst* = abstractInst + {tyTypeDesc, tyOwned, tyUserTypeClass}
  90. proc invalidGenericInst*(f: PType): bool =
  91. result = f.kind == tyGenericInst and skipModifier(f) == nil
  92. proc isPureObject*(typ: PType): bool =
  93. var t = typ
  94. while t.kind == tyObject and t.baseClass != nil:
  95. t = t.baseClass.skipTypes(skipPtrs)
  96. result = t.sym != nil and sfPure in t.sym.flags
  97. proc isUnsigned*(t: PType): bool =
  98. t.skipTypes(abstractInst).kind in {tyChar, tyUInt..tyUInt64}
  99. proc getOrdValueAux*(n: PNode, err: var bool): Int128 =
  100. var k = n.kind
  101. if n.typ != nil and n.typ.skipTypes(abstractInst).kind in {tyChar, tyUInt..tyUInt64}:
  102. k = nkUIntLit
  103. case k
  104. of nkCharLit, nkUIntLit..nkUInt64Lit:
  105. # XXX: enable this assert
  106. #assert n.typ == nil or isUnsigned(n.typ), $n.typ
  107. toInt128(cast[uint64](n.intVal))
  108. of nkIntLit..nkInt64Lit:
  109. # XXX: enable this assert
  110. #assert n.typ == nil or not isUnsigned(n.typ), $n.typ.kind
  111. toInt128(n.intVal)
  112. of nkNilLit:
  113. int128.Zero
  114. of nkHiddenStdConv:
  115. getOrdValueAux(n[1], err)
  116. else:
  117. err = true
  118. int128.Zero
  119. proc getOrdValue*(n: PNode): Int128 =
  120. var err: bool = false
  121. result = getOrdValueAux(n, err)
  122. #assert err == false
  123. proc getOrdValue*(n: PNode, onError: Int128): Int128 =
  124. var err = false
  125. result = getOrdValueAux(n, err)
  126. if err:
  127. result = onError
  128. proc getFloatValue*(n: PNode): BiggestFloat =
  129. case n.kind
  130. of nkFloatLiterals: n.floatVal
  131. of nkHiddenStdConv: getFloatValue(n[1])
  132. else: NaN
  133. proc isIntLit*(t: PType): bool {.inline.} =
  134. result = t.kind == tyInt and t.n != nil and t.n.kind == nkIntLit
  135. proc isFloatLit*(t: PType): bool {.inline.} =
  136. result = t.kind == tyFloat and t.n != nil and t.n.kind == nkFloatLit
  137. proc addTypeHeader*(result: var string, conf: ConfigRef; typ: PType; prefer: TPreferedDesc = preferMixed; getDeclarationPath = true) =
  138. result.add typeToString(typ, prefer)
  139. if getDeclarationPath: result.addDeclaredLoc(conf, typ.sym)
  140. proc getProcHeader*(conf: ConfigRef; sym: PSym; prefer: TPreferedDesc = preferName; getDeclarationPath = true): string =
  141. assert sym != nil
  142. # consider using `skipGenericOwner` to avoid fun2.fun2 when fun2 is generic
  143. result = sym.owner.name.s & '.' & sym.name.s
  144. if sym.kind in routineKinds:
  145. result.add '('
  146. var n = sym.typ.n
  147. for i in 1..<n.len:
  148. let p = n[i]
  149. if p.kind == nkSym:
  150. result.add(p.sym.name.s)
  151. result.add(": ")
  152. result.add(typeToString(p.sym.typ, prefer))
  153. if i != n.len-1: result.add(", ")
  154. else:
  155. result.add renderTree(p)
  156. result.add(')')
  157. if n[0].typ != nil:
  158. result.add(": " & typeToString(n[0].typ, prefer))
  159. if getDeclarationPath: result.addDeclaredLoc(conf, sym)
  160. proc elemType*(t: PType): PType =
  161. assert(t != nil)
  162. case t.kind
  163. of tyGenericInst, tyDistinct, tyAlias, tySink: result = elemType(skipModifier(t))
  164. of tyArray: result = t.elementType
  165. of tyError: result = t
  166. else: result = t.elementType
  167. assert(result != nil)
  168. proc enumHasHoles*(t: PType): bool =
  169. var b = t.skipTypes({tyRange, tyGenericInst, tyAlias, tySink})
  170. result = b.kind == tyEnum and tfEnumHasHoles in b.flags
  171. proc isOrdinalType*(t: PType, allowEnumWithHoles: bool = false): bool =
  172. assert(t != nil)
  173. const
  174. baseKinds = {tyChar, tyInt..tyInt64, tyUInt..tyUInt64, tyBool, tyEnum}
  175. parentKinds = {tyRange, tyOrdinal, tyGenericInst, tyAlias, tySink, tyDistinct}
  176. result = (t.kind in baseKinds and (not t.enumHasHoles or allowEnumWithHoles)) or
  177. (t.kind in parentKinds and isOrdinalType(t.skipModifier, allowEnumWithHoles))
  178. proc iterOverTypeAux(marker: var IntSet, t: PType, iter: TTypeIter,
  179. closure: RootRef): bool
  180. proc iterOverNode(marker: var IntSet, n: PNode, iter: TTypeIter,
  181. closure: RootRef): bool =
  182. if n != nil:
  183. case n.kind
  184. of nkNone..nkNilLit:
  185. # a leaf
  186. result = iterOverTypeAux(marker, n.typ, iter, closure)
  187. else:
  188. result = iterOverTypeAux(marker, n.typ, iter, closure)
  189. if result: return
  190. for i in 0..<n.len:
  191. result = iterOverNode(marker, n[i], iter, closure)
  192. if result: return
  193. else:
  194. result = false
  195. proc iterOverTypeAux(marker: var IntSet, t: PType, iter: TTypeIter,
  196. closure: RootRef): bool =
  197. result = false
  198. if t == nil: return
  199. result = iter(t, closure)
  200. if result: return
  201. if not containsOrIncl(marker, t.id):
  202. case t.kind
  203. of tyGenericInst, tyGenericBody, tyAlias, tySink, tyInferred:
  204. result = iterOverTypeAux(marker, skipModifier(t), iter, closure)
  205. else:
  206. for a in t.kids:
  207. result = iterOverTypeAux(marker, a, iter, closure)
  208. if result: return
  209. if t.n != nil and t.kind != tyProc: result = iterOverNode(marker, t.n, iter, closure)
  210. proc iterOverType(t: PType, iter: TTypeIter, closure: RootRef): bool =
  211. var marker = initIntSet()
  212. result = iterOverTypeAux(marker, t, iter, closure)
  213. proc searchTypeForAux(t: PType, predicate: TTypePredicate,
  214. marker: var IntSet): bool
  215. proc searchTypeNodeForAux(n: PNode, p: TTypePredicate,
  216. marker: var IntSet): bool =
  217. result = false
  218. case n.kind
  219. of nkRecList:
  220. for i in 0..<n.len:
  221. result = searchTypeNodeForAux(n[i], p, marker)
  222. if result: return
  223. of nkRecCase:
  224. assert(n[0].kind == nkSym)
  225. result = searchTypeNodeForAux(n[0], p, marker)
  226. if result: return
  227. for i in 1..<n.len:
  228. case n[i].kind
  229. of nkOfBranch, nkElse:
  230. result = searchTypeNodeForAux(lastSon(n[i]), p, marker)
  231. if result: return
  232. else: discard
  233. of nkSym:
  234. result = searchTypeForAux(n.sym.typ, p, marker)
  235. else: discard
  236. proc searchTypeForAux(t: PType, predicate: TTypePredicate,
  237. marker: var IntSet): bool =
  238. # iterates over VALUE types!
  239. result = false
  240. if t == nil: return
  241. if containsOrIncl(marker, t.id): return
  242. result = predicate(t)
  243. if result: return
  244. case t.kind
  245. of tyObject:
  246. if t.baseClass != nil:
  247. result = searchTypeForAux(t.baseClass.skipTypes(skipPtrs), predicate, marker)
  248. if not result: result = searchTypeNodeForAux(t.n, predicate, marker)
  249. of tyGenericInst, tyDistinct, tyAlias, tySink:
  250. result = searchTypeForAux(skipModifier(t), predicate, marker)
  251. of tyArray, tySet, tyTuple:
  252. for a in t.kids:
  253. result = searchTypeForAux(a, predicate, marker)
  254. if result: return
  255. else:
  256. discard
  257. proc searchTypeFor*(t: PType, predicate: TTypePredicate): bool =
  258. var marker = initIntSet()
  259. result = searchTypeForAux(t, predicate, marker)
  260. proc isObjectPredicate(t: PType): bool =
  261. result = t.kind == tyObject
  262. proc containsObject*(t: PType): bool =
  263. result = searchTypeFor(t, isObjectPredicate)
  264. proc isObjectWithTypeFieldPredicate(t: PType): bool =
  265. result = t.kind == tyObject and t.baseClass == nil and
  266. not (t.sym != nil and {sfPure, sfInfixCall} * t.sym.flags != {}) and
  267. tfFinal notin t.flags
  268. type
  269. TTypeFieldResult* = enum
  270. frNone, # type has no object type field
  271. frHeader, # type has an object type field only in the header
  272. frEmbedded # type has an object type field somewhere embedded
  273. proc analyseObjectWithTypeFieldAux(t: PType,
  274. marker: var IntSet): TTypeFieldResult =
  275. result = frNone
  276. if t == nil: return
  277. case t.kind
  278. of tyObject:
  279. if t.n != nil:
  280. if searchTypeNodeForAux(t.n, isObjectWithTypeFieldPredicate, marker):
  281. return frEmbedded
  282. var x = t.baseClass
  283. if x != nil: x = x.skipTypes(skipPtrs)
  284. let res = analyseObjectWithTypeFieldAux(x, marker)
  285. if res == frEmbedded:
  286. return frEmbedded
  287. if res == frHeader: result = frHeader
  288. if result == frNone:
  289. if isObjectWithTypeFieldPredicate(t): result = frHeader
  290. of tyGenericInst, tyDistinct, tyAlias, tySink:
  291. result = analyseObjectWithTypeFieldAux(skipModifier(t), marker)
  292. of tyArray, tyTuple:
  293. for a in t.kids:
  294. let res = analyseObjectWithTypeFieldAux(a, marker)
  295. if res != frNone:
  296. return frEmbedded
  297. else:
  298. discard
  299. proc analyseObjectWithTypeField*(t: PType): TTypeFieldResult =
  300. # this does a complex analysis whether a call to ``objectInit`` needs to be
  301. # made or initializing of the type field suffices or if there is no type field
  302. # at all in this type.
  303. var marker = initIntSet()
  304. result = analyseObjectWithTypeFieldAux(t, marker)
  305. proc isGCRef(t: PType): bool =
  306. result = t.kind in GcTypeKinds or
  307. (t.kind == tyProc and t.callConv == ccClosure)
  308. if result and t.kind in {tyString, tySequence} and tfHasAsgn in t.flags:
  309. result = false
  310. proc containsGarbageCollectedRef*(typ: PType): bool =
  311. # returns true if typ contains a reference, sequence or string (all the
  312. # things that are garbage-collected)
  313. result = searchTypeFor(typ, isGCRef)
  314. proc isManagedMemory(t: PType): bool =
  315. result = t.kind in GcTypeKinds or
  316. (t.kind == tyProc and t.callConv == ccClosure)
  317. proc containsManagedMemory*(typ: PType): bool =
  318. result = searchTypeFor(typ, isManagedMemory)
  319. proc isTyRef(t: PType): bool =
  320. result = t.kind == tyRef or (t.kind == tyProc and t.callConv == ccClosure)
  321. proc containsTyRef*(typ: PType): bool =
  322. # returns true if typ contains a 'ref'
  323. result = searchTypeFor(typ, isTyRef)
  324. proc isHiddenPointer(t: PType): bool =
  325. result = t.kind in {tyString, tySequence, tyOpenArray, tyVarargs}
  326. proc containsHiddenPointer*(typ: PType): bool =
  327. # returns true if typ contains a string, table or sequence (all the things
  328. # that need to be copied deeply)
  329. result = searchTypeFor(typ, isHiddenPointer)
  330. proc canFormAcycleAux(g: ModuleGraph; marker: var IntSet, typ: PType, orig: PType, withRef: bool, hasTrace: bool): bool
  331. proc canFormAcycleNode(g: ModuleGraph; marker: var IntSet, n: PNode, orig: PType, withRef: bool, hasTrace: bool): bool =
  332. result = false
  333. if n != nil:
  334. var hasCursor = n.kind == nkSym and sfCursor in n.sym.flags
  335. # cursor fields don't own the refs, which cannot form reference cycles
  336. if hasTrace or not hasCursor:
  337. result = canFormAcycleAux(g, marker, n.typ, orig, withRef, hasTrace)
  338. if not result:
  339. case n.kind
  340. of nkNone..nkNilLit:
  341. discard
  342. else:
  343. for i in 0..<n.len:
  344. result = canFormAcycleNode(g, marker, n[i], orig, withRef, hasTrace)
  345. if result: return
  346. proc sameBackendType*(x, y: PType): bool
  347. proc canFormAcycleAux(g: ModuleGraph, marker: var IntSet, typ: PType, orig: PType, withRef: bool, hasTrace: bool): bool =
  348. result = false
  349. if typ == nil: return
  350. if tfAcyclic in typ.flags: return
  351. var t = skipTypes(typ, abstractInst+{tyOwned}-{tyTypeDesc})
  352. if tfAcyclic in t.flags: return
  353. case t.kind
  354. of tyRef, tyPtr, tyUncheckedArray:
  355. if t.kind == tyRef or hasTrace:
  356. if withRef and sameBackendType(t, orig):
  357. result = true
  358. elif not containsOrIncl(marker, t.id):
  359. result = canFormAcycleAux(g, marker, t.elementType, orig, withRef or t.kind != tyUncheckedArray, hasTrace)
  360. of tyObject:
  361. if withRef and sameBackendType(t, orig):
  362. result = true
  363. elif not containsOrIncl(marker, t.id):
  364. var hasTrace = hasTrace
  365. let op = getAttachedOp(g, t.skipTypes({tyRef}), attachedTrace)
  366. if op != nil and sfOverridden in op.flags:
  367. hasTrace = true
  368. if t.baseClass != nil:
  369. result = canFormAcycleAux(g, marker, t.baseClass, orig, withRef, hasTrace)
  370. if result: return
  371. if t.n != nil: result = canFormAcycleNode(g, marker, t.n, orig, withRef, hasTrace)
  372. # Inheritance can introduce cyclic types, however this is not relevant
  373. # as the type that is passed to 'new' is statically known!
  374. # er but we use it also for the write barrier ...
  375. if tfFinal notin t.flags:
  376. # damn inheritance may introduce cycles:
  377. result = true
  378. of tyTuple:
  379. if withRef and sameBackendType(t, orig):
  380. result = true
  381. elif not containsOrIncl(marker, t.id):
  382. for a in t.kids:
  383. result = canFormAcycleAux(g, marker, a, orig, withRef, hasTrace)
  384. if result: return
  385. of tySequence, tyArray, tyOpenArray, tyVarargs:
  386. if withRef and sameBackendType(t, orig):
  387. result = true
  388. elif not containsOrIncl(marker, t.id):
  389. result = canFormAcycleAux(g, marker, t.elementType, orig, withRef, hasTrace)
  390. of tyProc: result = typ.callConv == ccClosure
  391. else: discard
  392. proc isFinal*(t: PType): bool =
  393. let t = t.skipTypes(abstractInst)
  394. result = t.kind != tyObject or tfFinal in t.flags or isPureObject(t)
  395. proc canFormAcycle*(g: ModuleGraph, typ: PType): bool =
  396. var marker = initIntSet()
  397. let t = skipTypes(typ, abstractInst+{tyOwned}-{tyTypeDesc})
  398. result = canFormAcycleAux(g, marker, t, t, false, false)
  399. proc valueToString(a: PNode): string =
  400. case a.kind
  401. of nkCharLit, nkUIntLit..nkUInt64Lit:
  402. result = $cast[uint64](a.intVal)
  403. of nkIntLit..nkInt64Lit:
  404. result = $a.intVal
  405. of nkFloatLit..nkFloat128Lit: result = $a.floatVal
  406. of nkStrLit..nkTripleStrLit: result = a.strVal
  407. of nkStaticExpr: result = "static(" & a[0].renderTree & ")"
  408. else: result = "<invalid value>"
  409. proc rangeToStr(n: PNode): string =
  410. assert(n.kind == nkRange)
  411. result = valueToString(n[0]) & ".." & valueToString(n[1])
  412. const
  413. typeToStr: array[TTypeKind, string] = ["None", "bool", "char", "empty",
  414. "Alias", "typeof(nil)", "untyped", "typed", "typeDesc",
  415. # xxx typeDesc=>typedesc: typedesc is declared as such, and is 10x more common.
  416. "GenericInvocation", "GenericBody", "GenericInst", "GenericParam",
  417. "distinct $1", "enum", "ordinal[$1]", "array[$1, $2]", "object", "tuple",
  418. "set[$1]", "range[$1]", "ptr ", "ref ", "var ", "seq[$1]", "proc",
  419. "pointer", "OpenArray[$1]", "string", "cstring", "Forward",
  420. "int", "int8", "int16", "int32", "int64",
  421. "float", "float32", "float64", "float128",
  422. "uint", "uint8", "uint16", "uint32", "uint64",
  423. "owned", "sink",
  424. "lent ", "varargs[$1]", "UncheckedArray[$1]", "Error Type",
  425. "BuiltInTypeClass", "UserTypeClass",
  426. "UserTypeClassInst", "CompositeTypeClass", "inferred",
  427. "and", "or", "not", "any", "static", "TypeFromExpr", "concept", # xxx bugfix
  428. "void", "iterable"]
  429. const preferToResolveSymbols = {preferName, preferTypeName, preferModuleInfo,
  430. preferGenericArg, preferResolved, preferMixed, preferInlayHint, preferInferredEffects}
  431. template bindConcreteTypeToUserTypeClass*(tc, concrete: PType) =
  432. tc.add concrete
  433. tc.flags.incl tfResolved
  434. # TODO: It would be a good idea to kill the special state of a resolved
  435. # concept by switching to tyAlias within the instantiated procs.
  436. # Currently, tyAlias is always skipped with skipModifier, which means that
  437. # we can store information about the matched concept in another position.
  438. # Then builtInFieldAccess can be modified to properly read the derived
  439. # consts and types stored within the concept.
  440. template isResolvedUserTypeClass*(t: PType): bool =
  441. tfResolved in t.flags
  442. proc addTypeFlags(name: var string, typ: PType) {.inline.} =
  443. if tfNotNil in typ.flags: name.add(" not nil")
  444. proc typeToString(typ: PType, prefer: TPreferedDesc = preferName): string =
  445. let preferToplevel = prefer
  446. proc getPrefer(prefer: TPreferedDesc): TPreferedDesc =
  447. if preferToplevel in {preferResolved, preferMixed}:
  448. preferToplevel # sticky option
  449. else:
  450. prefer
  451. proc typeToString(typ: PType, prefer: TPreferedDesc = preferName): string =
  452. result = ""
  453. let prefer = getPrefer(prefer)
  454. let t = typ
  455. if t == nil: return
  456. if prefer in preferToResolveSymbols and t.sym != nil and
  457. sfAnon notin t.sym.flags and t.kind != tySequence:
  458. if t.kind == tyInt and isIntLit(t):
  459. if prefer == preferInlayHint:
  460. result = t.sym.name.s
  461. else:
  462. result = t.sym.name.s & " literal(" & $t.n.intVal & ")"
  463. elif t.kind == tyAlias and t.elementType.kind != tyAlias:
  464. result = typeToString(t.elementType)
  465. elif prefer in {preferResolved, preferMixed}:
  466. case t.kind
  467. of IntegralTypes + {tyFloat..tyFloat128} + {tyString, tyCstring}:
  468. result = typeToStr[t.kind]
  469. of tyGenericBody:
  470. result = typeToString(t.last)
  471. of tyCompositeTypeClass:
  472. # avoids showing `A[any]` in `proc fun(a: A)` with `A = object[T]`
  473. result = typeToString(t.last.last)
  474. else:
  475. result = t.sym.name.s
  476. if prefer == preferMixed and result != t.sym.name.s:
  477. result = t.sym.name.s & "{" & result & "}"
  478. elif prefer in {preferName, preferTypeName, preferInlayHint, preferInferredEffects} or t.sym.owner.isNil:
  479. # note: should probably be: {preferName, preferTypeName, preferGenericArg}
  480. result = t.sym.name.s
  481. if t.kind == tyGenericParam and t.genericParamHasConstraints:
  482. result.add ": "
  483. result.add t.elementType.typeToString
  484. else:
  485. result = t.sym.owner.name.s & '.' & t.sym.name.s
  486. result.addTypeFlags(t)
  487. return
  488. case t.kind
  489. of tyInt:
  490. if not isIntLit(t) or prefer == preferExported:
  491. result = typeToStr[t.kind]
  492. else:
  493. case prefer:
  494. of preferGenericArg:
  495. result = $t.n.intVal
  496. of preferInlayHint:
  497. result = "int"
  498. else:
  499. result = "int literal(" & $t.n.intVal & ")"
  500. of tyGenericInst:
  501. result = typeToString(t.genericHead) & '['
  502. for needsComma, a in t.genericInstParams:
  503. if needsComma: result.add(", ")
  504. result.add(typeToString(a, preferGenericArg))
  505. result.add(']')
  506. of tyGenericInvocation:
  507. result = typeToString(t.genericHead) & '['
  508. for needsComma, a in t.genericInvocationParams:
  509. if needsComma: result.add(", ")
  510. result.add(typeToString(a, preferGenericArg))
  511. result.add(']')
  512. of tyGenericBody:
  513. result = typeToString(t.typeBodyImpl) & '['
  514. for i, a in t.genericBodyParams:
  515. if i > 0: result.add(", ")
  516. result.add(typeToString(a, preferTypeName))
  517. result.add(']')
  518. of tyTypeDesc:
  519. if t.elementType.kind == tyNone: result = "typedesc"
  520. else: result = "typedesc[" & typeToString(t.elementType) & "]"
  521. of tyStatic:
  522. if prefer == preferGenericArg and t.n != nil:
  523. result = t.n.renderTree
  524. else:
  525. result = "static[" & (if t.hasElementType: typeToString(t.skipModifier) else: "") & "]"
  526. if t.n != nil: result.add "(" & renderTree(t.n) & ")"
  527. of tyUserTypeClass:
  528. if t.sym != nil and t.sym.owner != nil:
  529. if t.isResolvedUserTypeClass: return typeToString(t.last)
  530. return t.sym.owner.name.s
  531. else:
  532. result = "<invalid tyUserTypeClass>"
  533. of tyBuiltInTypeClass:
  534. result =
  535. case t.base.kind
  536. of tyVar: "var"
  537. of tyRef: "ref"
  538. of tyPtr: "ptr"
  539. of tySequence: "seq"
  540. of tyArray: "array"
  541. of tySet: "set"
  542. of tyRange: "range"
  543. of tyDistinct: "distinct"
  544. of tyProc: "proc"
  545. of tyObject: "object"
  546. of tyTuple: "tuple"
  547. of tyOpenArray: "openArray"
  548. else: typeToStr[t.base.kind]
  549. of tyInferred:
  550. let concrete = t.previouslyInferred
  551. if concrete != nil: result = typeToString(concrete)
  552. else: result = "inferred[" & typeToString(t.base) & "]"
  553. of tyUserTypeClassInst:
  554. let body = t.base
  555. result = body.sym.name.s & "["
  556. for needsComma, a in t.userTypeClassInstParams:
  557. if needsComma: result.add(", ")
  558. result.add(typeToString(a))
  559. result.add "]"
  560. of tyAnd:
  561. for i, son in t.ikids:
  562. if i > 0: result.add(" and ")
  563. result.add(typeToString(son))
  564. of tyOr:
  565. for i, son in t.ikids:
  566. if i > 0: result.add(" or ")
  567. result.add(typeToString(son))
  568. of tyNot:
  569. result = "not " & typeToString(t.elementType)
  570. of tyUntyped:
  571. #internalAssert t.len == 0
  572. result = "untyped"
  573. of tyFromExpr:
  574. if t.n == nil:
  575. result = "unknown"
  576. else:
  577. result = "typeof(" & renderTree(t.n) & ")"
  578. of tyArray:
  579. result = "array"
  580. if t.hasElementType:
  581. if t.indexType.kind == tyRange:
  582. result &= "[" & rangeToStr(t.indexType.n) & ", " &
  583. typeToString(t.elementType) & ']'
  584. else:
  585. result &= "[" & typeToString(t.indexType) & ", " &
  586. typeToString(t.elementType) & ']'
  587. of tyUncheckedArray:
  588. result = "UncheckedArray"
  589. if t.hasElementType:
  590. result &= "[" & typeToString(t.elementType) & ']'
  591. of tySequence:
  592. if t.sym != nil and prefer != preferResolved:
  593. result = t.sym.name.s
  594. else:
  595. result = "seq"
  596. if t.hasElementType:
  597. result &= "[" & typeToString(t.elementType) & ']'
  598. of tyOrdinal:
  599. result = "ordinal"
  600. if t.hasElementType:
  601. result &= "[" & typeToString(t.skipModifier) & ']'
  602. of tySet:
  603. result = "set"
  604. if t.hasElementType:
  605. result &= "[" & typeToString(t.elementType) & ']'
  606. of tyOpenArray:
  607. result = "openArray"
  608. if t.hasElementType:
  609. result &= "[" & typeToString(t.elementType) & ']'
  610. of tyDistinct:
  611. result = "distinct " & typeToString(t.elementType,
  612. if prefer == preferModuleInfo: preferModuleInfo else: preferTypeName)
  613. of tyIterable:
  614. # xxx factor this pattern
  615. result = "iterable"
  616. if t.hasElementType:
  617. result &= "[" & typeToString(t.skipModifier) & ']'
  618. of tyTuple:
  619. # we iterate over t.sons here, because t.n may be nil
  620. if t.n != nil:
  621. result = "tuple["
  622. for i in 0..<t.n.len:
  623. assert(t.n[i].kind == nkSym)
  624. result.add(t.n[i].sym.name.s & ": " & typeToString(t.n[i].sym.typ))
  625. if i < t.n.len - 1: result.add(", ")
  626. result.add(']')
  627. elif t.isEmptyTupleType:
  628. result = "tuple[]"
  629. elif t.isSingletonTupleType:
  630. result = "("
  631. for son in t.kids:
  632. result.add(typeToString(son))
  633. result.add(",)")
  634. else:
  635. result = "("
  636. for i, son in t.ikids:
  637. if i > 0: result.add ", "
  638. result.add(typeToString(son))
  639. result.add(')')
  640. of tyPtr, tyRef, tyVar, tyLent:
  641. result = if isOutParam(t): "out " else: typeToStr[t.kind]
  642. result.add typeToString(t.elementType)
  643. of tyRange:
  644. result = "range "
  645. if t.n != nil and t.n.kind == nkRange:
  646. result.add rangeToStr(t.n)
  647. if prefer != preferExported:
  648. result.add("(" & typeToString(t.elementType) & ")")
  649. of tyProc:
  650. result = if tfIterator in t.flags: "iterator "
  651. elif t.owner != nil:
  652. case t.owner.kind
  653. of skTemplate: "template "
  654. of skMacro: "macro "
  655. of skConverter: "converter "
  656. else: "proc "
  657. else:
  658. "proc "
  659. if tfUnresolved in t.flags: result.add "[*missing parameters*]"
  660. result.add "("
  661. for i, a in t.paramTypes:
  662. if i > FirstParamAt: result.add(", ")
  663. let j = paramTypeToNodeIndex(i)
  664. if t.n != nil and j < t.n.len and t.n[j].kind == nkSym:
  665. result.add(t.n[j].sym.name.s)
  666. result.add(": ")
  667. result.add(typeToString(a))
  668. result.add(')')
  669. if t.returnType != nil: result.add(": " & typeToString(t.returnType))
  670. var prag = if t.callConv == ccNimCall and tfExplicitCallConv notin t.flags: "" else: $t.callConv
  671. var hasImplicitRaises = false
  672. if not isNil(t.owner) and not isNil(t.owner.ast) and (t.owner.ast.len - 1) >= pragmasPos:
  673. let pragmasNode = t.owner.ast[pragmasPos]
  674. let raisesSpec = effectSpec(pragmasNode, wRaises)
  675. if not isNil(raisesSpec):
  676. addSep(prag)
  677. prag.add("raises: ")
  678. prag.add($raisesSpec)
  679. hasImplicitRaises = true
  680. if tfNoSideEffect in t.flags:
  681. addSep(prag)
  682. prag.add("noSideEffect")
  683. if tfThread in t.flags:
  684. addSep(prag)
  685. prag.add("gcsafe")
  686. if not hasImplicitRaises and prefer == preferInferredEffects and not isNil(t.owner) and not isNil(t.owner.typ) and not isNil(t.owner.typ.n) and (t.owner.typ.n.len > 0):
  687. let effects = t.owner.typ.n[0]
  688. if effects.kind == nkEffectList and effects.len == effectListLen:
  689. var inferredRaisesStr = ""
  690. let effs = effects[exceptionEffects]
  691. if not isNil(effs):
  692. for eff in items(effs):
  693. if not isNil(eff):
  694. addSep(inferredRaisesStr)
  695. inferredRaisesStr.add($eff.typ)
  696. addSep(prag)
  697. prag.add("raises: <inferred> [")
  698. prag.add(inferredRaisesStr)
  699. prag.add("]")
  700. if prag.len != 0: result.add("{." & prag & ".}")
  701. of tyVarargs:
  702. result = typeToStr[t.kind] % typeToString(t.elementType)
  703. of tySink:
  704. result = "sink " & typeToString(t.skipModifier)
  705. of tyOwned:
  706. result = "owned " & typeToString(t.elementType)
  707. else:
  708. result = typeToStr[t.kind]
  709. result.addTypeFlags(t)
  710. result = typeToString(typ, prefer)
  711. proc firstOrd*(conf: ConfigRef; t: PType): Int128 =
  712. case t.kind
  713. of tyBool, tyChar, tySequence, tyOpenArray, tyString, tyVarargs, tyError:
  714. result = Zero
  715. of tySet, tyVar: result = firstOrd(conf, t.elementType)
  716. of tyArray: result = firstOrd(conf, t.indexType)
  717. of tyRange:
  718. assert(t.n != nil) # range directly given:
  719. assert(t.n.kind == nkRange)
  720. result = getOrdValue(t.n[0])
  721. of tyInt:
  722. if conf != nil:
  723. case conf.target.intSize
  724. of 8: result = toInt128(0x8000000000000000'i64)
  725. of 4: result = toInt128(-2147483648)
  726. of 2: result = toInt128(-32768)
  727. of 1: result = toInt128(-128)
  728. else: result = Zero
  729. else:
  730. result = toInt128(0x8000000000000000'i64)
  731. of tyInt8: result = toInt128(-128)
  732. of tyInt16: result = toInt128(-32768)
  733. of tyInt32: result = toInt128(-2147483648)
  734. of tyInt64: result = toInt128(0x8000000000000000'i64)
  735. of tyUInt..tyUInt64: result = Zero
  736. of tyEnum:
  737. # if basetype <> nil then return firstOrd of basetype
  738. if t.baseClass != nil:
  739. result = firstOrd(conf, t.baseClass)
  740. else:
  741. if t.n.len > 0:
  742. assert(t.n[0].kind == nkSym)
  743. result = toInt128(t.n[0].sym.position)
  744. else:
  745. result = Zero
  746. of tyGenericInst, tyDistinct, tyTypeDesc, tyAlias, tySink,
  747. tyStatic, tyInferred, tyLent:
  748. result = firstOrd(conf, skipModifier(t))
  749. of tyUserTypeClasses:
  750. result = firstOrd(conf, last(t))
  751. of tyOrdinal:
  752. if t.hasElementType: result = firstOrd(conf, skipModifier(t))
  753. else:
  754. result = Zero
  755. fatal(conf, unknownLineInfo, "invalid kind for firstOrd(" & $t.kind & ')')
  756. of tyUncheckedArray, tyCstring:
  757. result = Zero
  758. else:
  759. result = Zero
  760. fatal(conf, unknownLineInfo, "invalid kind for firstOrd(" & $t.kind & ')')
  761. proc firstFloat*(t: PType): BiggestFloat =
  762. case t.kind
  763. of tyFloat..tyFloat128: -Inf
  764. of tyRange:
  765. assert(t.n != nil) # range directly given:
  766. assert(t.n.kind == nkRange)
  767. getFloatValue(t.n[0])
  768. of tyVar: firstFloat(t.elementType)
  769. of tyGenericInst, tyDistinct, tyTypeDesc, tyAlias, tySink,
  770. tyStatic, tyInferred:
  771. firstFloat(skipModifier(t))
  772. of tyUserTypeClasses:
  773. firstFloat(last(t))
  774. else:
  775. internalError(newPartialConfigRef(), "invalid kind for firstFloat(" & $t.kind & ')')
  776. NaN
  777. proc targetSizeSignedToKind*(conf: ConfigRef): TTypeKind =
  778. case conf.target.intSize
  779. of 8: result = tyInt64
  780. of 4: result = tyInt32
  781. of 2: result = tyInt16
  782. else: result = tyNone
  783. proc targetSizeUnsignedToKind*(conf: ConfigRef): TTypeKind =
  784. case conf.target.intSize
  785. of 8: result = tyUInt64
  786. of 4: result = tyUInt32
  787. of 2: result = tyUInt16
  788. else: result = tyNone
  789. proc normalizeKind*(conf: ConfigRef, k: TTypeKind): TTypeKind =
  790. case k
  791. of tyInt:
  792. result = conf.targetSizeSignedToKind()
  793. of tyUInt:
  794. result = conf.targetSizeUnsignedToKind()
  795. else:
  796. result = k
  797. proc lastOrd*(conf: ConfigRef; t: PType): Int128 =
  798. case t.kind
  799. of tyBool: result = toInt128(1'u)
  800. of tyChar: result = toInt128(255'u)
  801. of tySet, tyVar: result = lastOrd(conf, t.elementType)
  802. of tyArray: result = lastOrd(conf, t.indexType)
  803. of tyRange:
  804. assert(t.n != nil) # range directly given:
  805. assert(t.n.kind == nkRange)
  806. result = getOrdValue(t.n[1])
  807. of tyInt:
  808. if conf != nil:
  809. case conf.target.intSize
  810. of 8: result = toInt128(0x7FFFFFFFFFFFFFFF'u64)
  811. of 4: result = toInt128(0x7FFFFFFF)
  812. of 2: result = toInt128(0x00007FFF)
  813. of 1: result = toInt128(0x0000007F)
  814. else: result = Zero
  815. else: result = toInt128(0x7FFFFFFFFFFFFFFF'u64)
  816. of tyInt8: result = toInt128(0x0000007F)
  817. of tyInt16: result = toInt128(0x00007FFF)
  818. of tyInt32: result = toInt128(0x7FFFFFFF)
  819. of tyInt64: result = toInt128(0x7FFFFFFFFFFFFFFF'u64)
  820. of tyUInt:
  821. if conf != nil and conf.target.intSize == 4:
  822. result = toInt128(0xFFFFFFFF)
  823. else:
  824. result = toInt128(0xFFFFFFFFFFFFFFFF'u64)
  825. of tyUInt8: result = toInt128(0xFF)
  826. of tyUInt16: result = toInt128(0xFFFF)
  827. of tyUInt32: result = toInt128(0xFFFFFFFF)
  828. of tyUInt64:
  829. result = toInt128(0xFFFFFFFFFFFFFFFF'u64)
  830. of tyEnum:
  831. if t.n.len > 0:
  832. assert(t.n[^1].kind == nkSym)
  833. result = toInt128(t.n[^1].sym.position)
  834. else:
  835. result = Zero
  836. of tyGenericInst, tyDistinct, tyTypeDesc, tyAlias, tySink,
  837. tyStatic, tyInferred, tyLent:
  838. result = lastOrd(conf, skipModifier(t))
  839. of tyUserTypeClasses:
  840. result = lastOrd(conf, last(t))
  841. of tyError: result = Zero
  842. of tyOrdinal:
  843. if t.hasElementType: result = lastOrd(conf, skipModifier(t))
  844. else:
  845. result = Zero
  846. fatal(conf, unknownLineInfo, "invalid kind for lastOrd(" & $t.kind & ')')
  847. of tyUncheckedArray:
  848. result = Zero
  849. else:
  850. result = Zero
  851. fatal(conf, unknownLineInfo, "invalid kind for lastOrd(" & $t.kind & ')')
  852. proc lastFloat*(t: PType): BiggestFloat =
  853. case t.kind
  854. of tyFloat..tyFloat128: Inf
  855. of tyVar: lastFloat(t.elementType)
  856. of tyRange:
  857. assert(t.n != nil) # range directly given:
  858. assert(t.n.kind == nkRange)
  859. getFloatValue(t.n[1])
  860. of tyGenericInst, tyDistinct, tyTypeDesc, tyAlias, tySink,
  861. tyStatic, tyInferred:
  862. lastFloat(skipModifier(t))
  863. of tyUserTypeClasses:
  864. lastFloat(last(t))
  865. else:
  866. internalError(newPartialConfigRef(), "invalid kind for lastFloat(" & $t.kind & ')')
  867. NaN
  868. proc floatRangeCheck*(x: BiggestFloat, t: PType): bool =
  869. case t.kind
  870. # This needs to be special cased since NaN is never
  871. # part of firstFloat(t)..lastFloat(t)
  872. of tyFloat..tyFloat128:
  873. true
  874. of tyRange:
  875. x in firstFloat(t)..lastFloat(t)
  876. of tyVar:
  877. floatRangeCheck(x, t.elementType)
  878. of tyGenericInst, tyDistinct, tyTypeDesc, tyAlias, tySink,
  879. tyStatic, tyInferred:
  880. floatRangeCheck(x, skipModifier(t))
  881. of tyUserTypeClasses:
  882. floatRangeCheck(x, last(t))
  883. else:
  884. internalError(newPartialConfigRef(), "invalid kind for floatRangeCheck:" & $t.kind)
  885. false
  886. proc lengthOrd*(conf: ConfigRef; t: PType): Int128 =
  887. if t.skipTypes(tyUserTypeClasses).kind == tyDistinct:
  888. result = lengthOrd(conf, t.skipModifier)
  889. else:
  890. let last = lastOrd(conf, t)
  891. let first = firstOrd(conf, t)
  892. result = last - first + One
  893. # -------------- type equality -----------------------------------------------
  894. type
  895. TDistinctCompare* = enum ## how distinct types are to be compared
  896. dcEq, ## a and b should be the same type
  897. dcEqIgnoreDistinct, ## compare symmetrically: (distinct a) == b, a == b
  898. ## or a == (distinct b)
  899. dcEqOrDistinctOf ## a equals b or a is distinct of b
  900. TTypeCmpFlag* = enum
  901. IgnoreTupleFields ## NOTE: Only set this flag for backends!
  902. IgnoreCC
  903. ExactTypeDescValues
  904. ExactGenericParams
  905. ExactConstraints
  906. ExactGcSafety
  907. AllowCommonBase
  908. PickyCAliases # be picky about the distinction between 'cint' and 'int32'
  909. IgnoreFlags # used for borrowed functions and methods; ignores the tfVarIsPtr flag
  910. PickyBackendAliases # be picky about different aliases
  911. TTypeCmpFlags* = set[TTypeCmpFlag]
  912. TSameTypeClosure = object
  913. cmp: TDistinctCompare
  914. recCheck: int
  915. flags: TTypeCmpFlags
  916. s: seq[tuple[a,b: int]] # seq for a set as it's hopefully faster
  917. # (few elements expected)
  918. proc initSameTypeClosure: TSameTypeClosure =
  919. # we do the initialization lazily for performance (avoids memory allocations)
  920. result = TSameTypeClosure()
  921. proc containsOrIncl(c: var TSameTypeClosure, a, b: PType): bool =
  922. result = c.s.len > 0 and c.s.contains((a.id, b.id))
  923. if not result:
  924. c.s.add((a.id, b.id))
  925. proc sameTypeAux(x, y: PType, c: var TSameTypeClosure): bool
  926. proc sameTypeOrNilAux(a, b: PType, c: var TSameTypeClosure): bool =
  927. if a == b:
  928. result = true
  929. else:
  930. if a == nil or b == nil: result = false
  931. else: result = sameTypeAux(a, b, c)
  932. proc sameType*(a, b: PType, flags: TTypeCmpFlags = {}): bool =
  933. var c = initSameTypeClosure()
  934. c.flags = flags
  935. result = sameTypeAux(a, b, c)
  936. proc sameTypeOrNil*(a, b: PType, flags: TTypeCmpFlags = {}): bool =
  937. if a == b:
  938. result = true
  939. else:
  940. if a == nil or b == nil: result = false
  941. else: result = sameType(a, b, flags)
  942. proc equalParam(a, b: PSym): TParamsEquality =
  943. if sameTypeOrNil(a.typ, b.typ, {ExactTypeDescValues}) and
  944. exprStructuralEquivalent(a.constraint, b.constraint):
  945. if a.ast == b.ast:
  946. result = paramsEqual
  947. elif a.ast != nil and b.ast != nil:
  948. if exprStructuralEquivalent(a.ast, b.ast): result = paramsEqual
  949. else: result = paramsIncompatible
  950. elif a.ast != nil:
  951. result = paramsEqual
  952. elif b.ast != nil:
  953. result = paramsIncompatible
  954. else:
  955. result = paramsNotEqual
  956. else:
  957. result = paramsNotEqual
  958. proc sameConstraints(a, b: PNode): bool =
  959. if isNil(a) and isNil(b): return true
  960. if a.len != b.len: return false
  961. for i in 1..<a.len:
  962. if not exprStructuralEquivalent(a[i].sym.constraint,
  963. b[i].sym.constraint):
  964. return false
  965. return true
  966. proc equalParams(a, b: PNode): TParamsEquality =
  967. result = paramsEqual
  968. if a.len != b.len:
  969. result = paramsNotEqual
  970. else:
  971. for i in 1..<a.len:
  972. var m = a[i].sym
  973. var n = b[i].sym
  974. assert((m.kind == skParam) and (n.kind == skParam))
  975. case equalParam(m, n)
  976. of paramsNotEqual:
  977. return paramsNotEqual
  978. of paramsEqual:
  979. discard
  980. of paramsIncompatible:
  981. result = paramsIncompatible
  982. if m.name.id != n.name.id:
  983. # BUGFIX
  984. return paramsNotEqual # paramsIncompatible;
  985. # continue traversal! If not equal, we can return immediately; else
  986. # it stays incompatible
  987. if not sameTypeOrNil(a.typ, b.typ, {ExactTypeDescValues}):
  988. if (a.typ == nil) or (b.typ == nil):
  989. result = paramsNotEqual # one proc has a result, the other not is OK
  990. else:
  991. result = paramsIncompatible # overloading by different
  992. # result types does not work
  993. proc sameTuple(a, b: PType, c: var TSameTypeClosure): bool =
  994. # two tuples are equivalent iff the names, types and positions are the same;
  995. # however, both types may not have any field names (t.n may be nil) which
  996. # complicates the matter a bit.
  997. if sameTupleLengths(a, b):
  998. result = true
  999. for i, aa, bb in tupleTypePairs(a, b):
  1000. var x = aa
  1001. var y = bb
  1002. if IgnoreTupleFields in c.flags:
  1003. x = skipTypes(x, {tyRange, tyGenericInst, tyAlias})
  1004. y = skipTypes(y, {tyRange, tyGenericInst, tyAlias})
  1005. result = sameTypeAux(x, y, c)
  1006. if not result: return
  1007. if a.n != nil and b.n != nil and IgnoreTupleFields notin c.flags:
  1008. for i in 0..<a.n.len:
  1009. # check field names:
  1010. if a.n[i].kind == nkSym and b.n[i].kind == nkSym:
  1011. var x = a.n[i].sym
  1012. var y = b.n[i].sym
  1013. result = x.name.id == y.name.id
  1014. if not result: break
  1015. else:
  1016. return false
  1017. elif a.n != b.n and (a.n == nil or b.n == nil) and IgnoreTupleFields notin c.flags:
  1018. result = false
  1019. else:
  1020. result = false
  1021. template ifFastObjectTypeCheckFailed(a, b: PType, body: untyped) =
  1022. if tfFromGeneric notin a.flags + b.flags:
  1023. # fast case: id comparison suffices:
  1024. result = a.id == b.id
  1025. else:
  1026. # expensive structural equality test; however due to the way generic and
  1027. # objects work, if one of the types does **not** contain tfFromGeneric,
  1028. # they cannot be equal. The check ``a.sym.id == b.sym.id`` checks
  1029. # for the same origin and is essential because we don't want "pure"
  1030. # structural type equivalence:
  1031. #
  1032. # type
  1033. # TA[T] = object
  1034. # TB[T] = object
  1035. # --> TA[int] != TB[int]
  1036. if tfFromGeneric in a.flags * b.flags and a.sym.id == b.sym.id:
  1037. # ok, we need the expensive structural check
  1038. body
  1039. else:
  1040. result = false
  1041. proc sameObjectTypes*(a, b: PType): bool =
  1042. # specialized for efficiency (sigmatch uses it)
  1043. ifFastObjectTypeCheckFailed(a, b):
  1044. var c = initSameTypeClosure()
  1045. result = sameTypeAux(a, b, c)
  1046. proc sameDistinctTypes*(a, b: PType): bool {.inline.} =
  1047. result = sameObjectTypes(a, b)
  1048. proc sameEnumTypes*(a, b: PType): bool {.inline.} =
  1049. result = a.id == b.id
  1050. proc sameObjectTree(a, b: PNode, c: var TSameTypeClosure): bool =
  1051. if a == b:
  1052. result = true
  1053. elif a != nil and b != nil and a.kind == b.kind:
  1054. var x = a.typ
  1055. var y = b.typ
  1056. if IgnoreTupleFields in c.flags:
  1057. if x != nil: x = skipTypes(x, {tyRange, tyGenericInst, tyAlias})
  1058. if y != nil: y = skipTypes(y, {tyRange, tyGenericInst, tyAlias})
  1059. if sameTypeOrNilAux(x, y, c):
  1060. case a.kind
  1061. of nkSym:
  1062. # same symbol as string is enough:
  1063. result = a.sym.name.id == b.sym.name.id
  1064. of nkIdent: result = a.ident.id == b.ident.id
  1065. of nkCharLit..nkInt64Lit: result = a.intVal == b.intVal
  1066. of nkFloatLit..nkFloat64Lit: result = a.floatVal == b.floatVal
  1067. of nkStrLit..nkTripleStrLit: result = a.strVal == b.strVal
  1068. of nkEmpty, nkNilLit, nkType: result = true
  1069. else:
  1070. if a.len == b.len:
  1071. for i in 0..<a.len:
  1072. if not sameObjectTree(a[i], b[i], c): return
  1073. result = true
  1074. else:
  1075. result = false
  1076. else:
  1077. result = false
  1078. else:
  1079. result = false
  1080. proc sameObjectStructures(a, b: PType, c: var TSameTypeClosure): bool =
  1081. if not sameTypeOrNilAux(a.baseClass, b.baseClass, c): return false
  1082. if not sameObjectTree(a.n, b.n, c): return false
  1083. result = true
  1084. proc sameChildrenAux(a, b: PType, c: var TSameTypeClosure): bool =
  1085. if not sameTupleLengths(a, b): return false
  1086. # XXX This is not tuple specific.
  1087. result = true
  1088. for _, x, y in tupleTypePairs(a, b):
  1089. result = sameTypeOrNilAux(x, y, c)
  1090. if not result: return
  1091. proc isGenericAlias*(t: PType): bool =
  1092. return t.kind == tyGenericInst and t.skipModifier.kind == tyGenericInst
  1093. proc genericAliasDepth*(t: PType): int =
  1094. result = 0
  1095. var it = t
  1096. while it.isGenericAlias:
  1097. it = it.skipModifier
  1098. inc result
  1099. proc skipGenericAlias*(t: PType): PType =
  1100. return if t.isGenericAlias: t.skipModifier else: t
  1101. proc sameFlags*(a, b: PType): bool {.inline.} =
  1102. result = eqTypeFlags*a.flags == eqTypeFlags*b.flags
  1103. proc sameTypeAux(x, y: PType, c: var TSameTypeClosure): bool =
  1104. result = false
  1105. template cycleCheck() =
  1106. # believe it or not, the direct check for ``containsOrIncl(c, a, b)``
  1107. # increases bootstrapping time from 2.4s to 3.3s on my laptop! So we cheat
  1108. # again: Since the recursion check is only to not get caught in an endless
  1109. # recursion, we use a counter and only if it's value is over some
  1110. # threshold we perform the expensive exact cycle check:
  1111. if c.recCheck < 3:
  1112. inc c.recCheck
  1113. else:
  1114. if containsOrIncl(c, a, b): return true
  1115. if x == y: return true
  1116. var a = skipTypes(x, {tyAlias})
  1117. while a.kind == tyUserTypeClass and tfResolved in a.flags:
  1118. a = skipTypes(a.last, {tyAlias})
  1119. var b = skipTypes(y, {tyAlias})
  1120. while b.kind == tyUserTypeClass and tfResolved in b.flags:
  1121. b = skipTypes(b.last, {tyAlias})
  1122. assert(a != nil)
  1123. assert(b != nil)
  1124. if a.kind != b.kind:
  1125. case c.cmp
  1126. of dcEq: return false
  1127. of dcEqIgnoreDistinct:
  1128. a = a.skipTypes({tyDistinct, tyGenericInst})
  1129. b = b.skipTypes({tyDistinct, tyGenericInst})
  1130. if a.kind != b.kind: return false
  1131. of dcEqOrDistinctOf:
  1132. a = a.skipTypes({tyDistinct, tyGenericInst})
  1133. if a.kind != b.kind: return false
  1134. #[
  1135. The following code should not run in the case either side is an generic alias,
  1136. but it's not presently possible to distinguish the genericinsts from aliases of
  1137. objects ie `type A[T] = SomeObject`
  1138. ]#
  1139. # this is required by tunique_type but makes no sense really:
  1140. if x.kind == tyGenericInst and IgnoreTupleFields notin c.flags and tyDistinct != y.kind:
  1141. let
  1142. lhs = x.skipGenericAlias
  1143. rhs = y.skipGenericAlias
  1144. if rhs.kind != tyGenericInst or lhs.base != rhs.base or rhs.kidsLen != lhs.kidsLen:
  1145. return false
  1146. for ff, aa in underspecifiedPairs(rhs, lhs, 1, -1):
  1147. if not sameTypeAux(ff, aa, c): return false
  1148. return true
  1149. case a.kind
  1150. of tyEmpty, tyChar, tyBool, tyNil, tyPointer, tyString, tyCstring,
  1151. tyInt..tyUInt64, tyTyped, tyUntyped, tyVoid:
  1152. result = sameFlags(a, b)
  1153. if result and {PickyCAliases, ExactTypeDescValues} <= c.flags:
  1154. # additional requirement for the caching of generics for importc'ed types:
  1155. # the symbols must be identical too:
  1156. let symFlagsA = if a.sym != nil: a.sym.flags else: {}
  1157. let symFlagsB = if b.sym != nil: b.sym.flags else: {}
  1158. if (symFlagsA+symFlagsB) * {sfImportc, sfExportc} != {}:
  1159. result = symFlagsA == symFlagsB
  1160. elif result and PickyBackendAliases in c.flags:
  1161. let symFlagsA = if a.sym != nil: a.sym.flags else: {}
  1162. let symFlagsB = if b.sym != nil: b.sym.flags else: {}
  1163. if (symFlagsA+symFlagsB) * {sfImportc, sfExportc} != {}:
  1164. result = a.id == b.id
  1165. of tyStatic, tyFromExpr:
  1166. result = exprStructuralEquivalent(a.n, b.n) and sameFlags(a, b)
  1167. if result and sameTupleLengths(a, b) and a.hasElementType:
  1168. cycleCheck()
  1169. result = sameTypeAux(a.skipModifier, b.skipModifier, c)
  1170. of tyObject:
  1171. ifFastObjectTypeCheckFailed(a, b):
  1172. cycleCheck()
  1173. result = sameObjectStructures(a, b, c) and sameFlags(a, b)
  1174. of tyDistinct:
  1175. cycleCheck()
  1176. if c.cmp == dcEq:
  1177. if sameFlags(a, b):
  1178. ifFastObjectTypeCheckFailed(a, b):
  1179. result = sameTypeAux(a.elementType, b.elementType, c)
  1180. else:
  1181. result = sameTypeAux(a.elementType, b.elementType, c) and sameFlags(a, b)
  1182. of tyEnum, tyForward:
  1183. # XXX generic enums do not make much sense, but require structural checking
  1184. result = a.id == b.id and sameFlags(a, b)
  1185. of tyError:
  1186. result = b.kind == tyError
  1187. of tyTuple:
  1188. cycleCheck()
  1189. result = sameTuple(a, b, c) and sameFlags(a, b)
  1190. of tyTypeDesc:
  1191. if c.cmp == dcEqIgnoreDistinct: result = false
  1192. elif ExactTypeDescValues in c.flags:
  1193. cycleCheck()
  1194. result = sameChildrenAux(x, y, c) and sameFlags(a, b)
  1195. else:
  1196. result = sameFlags(a, b)
  1197. of tyGenericParam:
  1198. result = sameChildrenAux(a, b, c) and sameFlags(a, b)
  1199. if result and {ExactGenericParams, ExactTypeDescValues} * c.flags != {}:
  1200. result = a.sym.position == b.sym.position
  1201. of tyBuiltInTypeClass:
  1202. result = a.elementType.kind == b.elementType.kind and sameFlags(a.elementType, b.elementType)
  1203. if result and a.elementType.kind == tyProc and IgnoreCC notin c.flags:
  1204. let ecc = a.elementType.flags * {tfExplicitCallConv}
  1205. result = ecc == b.elementType.flags * {tfExplicitCallConv} and
  1206. (ecc == {} or a.elementType.callConv == b.elementType.callConv)
  1207. of tyGenericInvocation, tyGenericBody, tySequence, tyOpenArray, tySet, tyRef,
  1208. tyPtr, tyVar, tyLent, tySink, tyUncheckedArray, tyArray, tyProc, tyVarargs,
  1209. tyOrdinal, tyCompositeTypeClass, tyUserTypeClass, tyUserTypeClassInst,
  1210. tyAnd, tyOr, tyNot, tyAnything, tyOwned:
  1211. cycleCheck()
  1212. if a.kind == tyUserTypeClass and a.n != nil: return a.n == b.n
  1213. result = sameChildrenAux(a, b, c)
  1214. if result and IgnoreFlags notin c.flags:
  1215. if IgnoreTupleFields in c.flags:
  1216. result = a.flags * {tfVarIsPtr, tfIsOutParam} == b.flags * {tfVarIsPtr, tfIsOutParam}
  1217. else:
  1218. result = sameFlags(a, b)
  1219. if result and ExactGcSafety in c.flags:
  1220. result = a.flags * {tfThread} == b.flags * {tfThread}
  1221. if result and a.kind == tyProc:
  1222. result = ((IgnoreCC in c.flags) or a.callConv == b.callConv) and
  1223. ((ExactConstraints notin c.flags) or sameConstraints(a.n, b.n))
  1224. of tyRange:
  1225. cycleCheck()
  1226. result = sameTypeOrNilAux(a.elementType, b.elementType, c) and
  1227. sameValue(a.n[0], b.n[0]) and
  1228. sameValue(a.n[1], b.n[1])
  1229. of tyAlias, tyInferred, tyIterable:
  1230. cycleCheck()
  1231. result = sameTypeAux(a.skipModifier, b.skipModifier, c)
  1232. of tyGenericInst:
  1233. # BUG #23445
  1234. # The type system must distinguish between `T[int] = object #[empty]#`
  1235. # and `T[float] = object #[empty]#`!
  1236. cycleCheck()
  1237. for ff, aa in underspecifiedPairs(a, b, 1, -1):
  1238. if not sameTypeAux(ff, aa, c): return false
  1239. result = sameTypeAux(a.skipModifier, b.skipModifier, c)
  1240. of tyNone: result = false
  1241. of tyConcept:
  1242. result = exprStructuralEquivalent(a.n, b.n)
  1243. proc sameBackendType*(x, y: PType): bool =
  1244. var c = initSameTypeClosure()
  1245. c.flags.incl IgnoreTupleFields
  1246. c.cmp = dcEqIgnoreDistinct
  1247. result = sameTypeAux(x, y, c)
  1248. proc sameBackendTypePickyAliases*(x, y: PType): bool =
  1249. var c = initSameTypeClosure()
  1250. c.flags.incl {IgnoreTupleFields, PickyCAliases, PickyBackendAliases}
  1251. c.cmp = dcEqIgnoreDistinct
  1252. result = sameTypeAux(x, y, c)
  1253. proc compareTypes*(x, y: PType,
  1254. cmp: TDistinctCompare = dcEq,
  1255. flags: TTypeCmpFlags = {}): bool =
  1256. ## compares two type for equality (modulo type distinction)
  1257. var c = initSameTypeClosure()
  1258. c.cmp = cmp
  1259. c.flags = flags
  1260. if x == y: result = true
  1261. elif x.isNil or y.isNil: result = false
  1262. else: result = sameTypeAux(x, y, c)
  1263. proc inheritanceDiff*(a, b: PType): int =
  1264. # | returns: 0 iff `a` == `b`
  1265. # | returns: -x iff `a` is the x'th direct superclass of `b`
  1266. # | returns: +x iff `a` is the x'th direct subclass of `b`
  1267. # | returns: `maxint` iff `a` and `b` are not compatible at all
  1268. if a == b or a.kind == tyError or b.kind == tyError: return 0
  1269. assert a.kind in {tyObject} + skipPtrs
  1270. assert b.kind in {tyObject} + skipPtrs
  1271. var x = a
  1272. result = 0
  1273. while x != nil:
  1274. x = skipTypes(x, skipPtrs)
  1275. if sameObjectTypes(x, b): return
  1276. x = x.baseClass
  1277. dec(result)
  1278. var y = b
  1279. result = 0
  1280. while y != nil:
  1281. y = skipTypes(y, skipPtrs)
  1282. if sameObjectTypes(y, a): return
  1283. y = y.baseClass
  1284. inc(result)
  1285. result = high(int)
  1286. proc commonSuperclass*(a, b: PType): PType =
  1287. result = nil
  1288. # quick check: are they the same?
  1289. if sameObjectTypes(a, b): return a
  1290. # simple algorithm: we store all ancestors of 'a' in a ID-set and walk 'b'
  1291. # up until the ID is found:
  1292. assert a.kind == tyObject
  1293. assert b.kind == tyObject
  1294. var x = a
  1295. var ancestors = initIntSet()
  1296. while x != nil:
  1297. x = skipTypes(x, skipPtrs)
  1298. ancestors.incl(x.id)
  1299. x = x.baseClass
  1300. var y = b
  1301. while y != nil:
  1302. var t = y # bug #7818, save type before skip
  1303. y = skipTypes(y, skipPtrs)
  1304. if ancestors.contains(y.id):
  1305. # bug #7818, defer the previous skipTypes
  1306. if t.kind != tyGenericInst: t = y
  1307. return t
  1308. y = y.baseClass
  1309. proc lacksMTypeField*(typ: PType): bool {.inline.} =
  1310. (typ.sym != nil and sfPure in typ.sym.flags) or tfFinal in typ.flags
  1311. include sizealignoffsetimpl
  1312. proc computeSize*(conf: ConfigRef; typ: PType): BiggestInt =
  1313. computeSizeAlign(conf, typ)
  1314. result = typ.size
  1315. proc getReturnType*(s: PSym): PType =
  1316. # Obtains the return type of a iterator/proc/macro/template
  1317. assert s.kind in skProcKinds
  1318. result = s.typ.returnType
  1319. proc getAlign*(conf: ConfigRef; typ: PType): BiggestInt =
  1320. computeSizeAlign(conf, typ)
  1321. result = typ.align
  1322. proc getSize*(conf: ConfigRef; typ: PType): BiggestInt =
  1323. computeSizeAlign(conf, typ)
  1324. result = typ.size
  1325. proc containsGenericTypeIter(t: PType, closure: RootRef): bool =
  1326. case t.kind
  1327. of tyStatic:
  1328. return t.n == nil
  1329. of tyTypeDesc:
  1330. if t.base.kind == tyNone: return true
  1331. if containsGenericTypeIter(t.base, closure): return true
  1332. return false
  1333. of GenericTypes + tyTypeClasses + {tyFromExpr}:
  1334. return true
  1335. else:
  1336. return false
  1337. proc containsGenericType*(t: PType): bool =
  1338. result = iterOverType(t, containsGenericTypeIter, nil)
  1339. proc baseOfDistinct*(t: PType; g: ModuleGraph; idgen: IdGenerator): PType =
  1340. if t.kind == tyDistinct:
  1341. result = t.elementType
  1342. else:
  1343. result = copyType(t, idgen, t.owner)
  1344. copyTypeProps(g, idgen.module, result, t)
  1345. var parent: PType = nil
  1346. var it = result
  1347. while it.kind in {tyPtr, tyRef, tyOwned}:
  1348. parent = it
  1349. it = it.elementType
  1350. if it.kind == tyDistinct and parent != nil:
  1351. parent[0] = it[0]
  1352. proc safeInheritanceDiff*(a, b: PType): int =
  1353. # same as inheritanceDiff but checks for tyError:
  1354. if a.kind == tyError or b.kind == tyError:
  1355. result = -1
  1356. else:
  1357. result = inheritanceDiff(a.skipTypes(skipPtrs), b.skipTypes(skipPtrs))
  1358. proc compatibleEffectsAux(se, re: PNode): bool =
  1359. if re.isNil: return false
  1360. for r in items(re):
  1361. block search:
  1362. for s in items(se):
  1363. if safeInheritanceDiff(r.typ, s.typ) <= 0:
  1364. break search
  1365. return false
  1366. result = true
  1367. proc isDefectException*(t: PType): bool
  1368. proc compatibleExceptions(se, re: PNode): bool =
  1369. if re.isNil: return false
  1370. for r in items(re):
  1371. block search:
  1372. if isDefectException(r.typ):
  1373. break search
  1374. for s in items(se):
  1375. if safeInheritanceDiff(r.typ, s.typ) <= 0:
  1376. break search
  1377. return false
  1378. result = true
  1379. proc hasIncompatibleEffect(se, re: PNode): bool =
  1380. result = false
  1381. if re.isNil: return false
  1382. for r in items(re):
  1383. for s in items(se):
  1384. if safeInheritanceDiff(r.typ, s.typ) != high(int):
  1385. return true
  1386. type
  1387. EffectsCompat* = enum
  1388. efCompat
  1389. efRaisesDiffer
  1390. efRaisesUnknown
  1391. efTagsDiffer
  1392. efTagsUnknown
  1393. efEffectsDelayed
  1394. efTagsIllegal
  1395. proc compatibleEffects*(formal, actual: PType): EffectsCompat =
  1396. # for proc type compatibility checking:
  1397. assert formal.kind == tyProc and actual.kind == tyProc
  1398. #if tfEffectSystemWorkaround in actual.flags:
  1399. # return efCompat
  1400. if formal.n[0].kind != nkEffectList or
  1401. actual.n[0].kind != nkEffectList:
  1402. return efTagsUnknown
  1403. var spec = formal.n[0]
  1404. if spec.len != 0:
  1405. var real = actual.n[0]
  1406. let se = spec[exceptionEffects]
  1407. # if 'se.kind == nkArgList' it is no formal type really, but a
  1408. # computed effect and as such no spec:
  1409. # 'r.msgHandler = if isNil(msgHandler): defaultMsgHandler else: msgHandler'
  1410. if not isNil(se) and se.kind != nkArgList:
  1411. # spec requires some exception or tag, but we don't know anything:
  1412. if real.len == 0: return efRaisesUnknown
  1413. let res = compatibleExceptions(se, real[exceptionEffects])
  1414. if not res: return efRaisesDiffer
  1415. let st = spec[tagEffects]
  1416. if not isNil(st) and st.kind != nkArgList:
  1417. # spec requires some exception or tag, but we don't know anything:
  1418. if real.len == 0: return efTagsUnknown
  1419. let res = compatibleEffectsAux(st, real[tagEffects])
  1420. if not res:
  1421. #if tfEffectSystemWorkaround notin actual.flags:
  1422. return efTagsDiffer
  1423. let sn = spec[forbiddenEffects]
  1424. if not isNil(sn) and sn.kind != nkArgList:
  1425. if 0 == real.len:
  1426. return efTagsUnknown
  1427. elif hasIncompatibleEffect(sn, real[tagEffects]):
  1428. return efTagsIllegal
  1429. for i in 1 ..< min(formal.n.len, actual.n.len):
  1430. if formal.n[i].sym.flags * {sfEffectsDelayed} != actual.n[i].sym.flags * {sfEffectsDelayed}:
  1431. result = efEffectsDelayed
  1432. break
  1433. result = efCompat
  1434. proc isCompileTimeOnly*(t: PType): bool {.inline.} =
  1435. result = t.kind in {tyTypeDesc, tyStatic, tyGenericParam}
  1436. proc containsCompileTimeOnly*(t: PType): bool =
  1437. if isCompileTimeOnly(t): return true
  1438. for a in t.kids:
  1439. if a != nil and isCompileTimeOnly(a):
  1440. return true
  1441. return false
  1442. proc safeSkipTypes*(t: PType, kinds: TTypeKinds): PType =
  1443. ## same as 'skipTypes' but with a simple cycle detector.
  1444. result = t
  1445. var seen = initIntSet()
  1446. while result.kind in kinds and not containsOrIncl(seen, result.id):
  1447. result = skipModifier(result)
  1448. type
  1449. OrdinalType* = enum
  1450. NoneLike, IntLike, FloatLike
  1451. proc classify*(t: PType): OrdinalType =
  1452. ## for convenient type checking:
  1453. if t == nil:
  1454. result = NoneLike
  1455. else:
  1456. case skipTypes(t, abstractVarRange).kind
  1457. of tyFloat..tyFloat128: result = FloatLike
  1458. of tyInt..tyInt64, tyUInt..tyUInt64, tyBool, tyChar, tyEnum:
  1459. result = IntLike
  1460. else: result = NoneLike
  1461. proc skipConv*(n: PNode): PNode =
  1462. result = n
  1463. case n.kind
  1464. of nkObjUpConv, nkObjDownConv, nkChckRange, nkChckRangeF, nkChckRange64:
  1465. # only skip the conversion if it doesn't lose too important information
  1466. # (see bug #1334)
  1467. if n[0].typ.classify == n.typ.classify:
  1468. result = n[0]
  1469. of nkHiddenStdConv, nkHiddenSubConv, nkConv:
  1470. if n[1].typ.classify == n.typ.classify:
  1471. result = n[1]
  1472. else: discard
  1473. proc skipHidden*(n: PNode): PNode =
  1474. result = n
  1475. while true:
  1476. case result.kind
  1477. of nkHiddenStdConv, nkHiddenSubConv:
  1478. if result[1].typ.classify == result.typ.classify:
  1479. result = result[1]
  1480. else: break
  1481. of nkHiddenDeref, nkHiddenAddr:
  1482. result = result[0]
  1483. else: break
  1484. proc skipConvTakeType*(n: PNode): PNode =
  1485. result = n.skipConv
  1486. result.typ = n.typ
  1487. proc isEmptyContainer*(t: PType): bool =
  1488. case t.kind
  1489. of tyUntyped, tyNil: result = true
  1490. of tyArray, tySet, tySequence, tyOpenArray, tyVarargs:
  1491. result = t.elementType.kind == tyEmpty
  1492. of tyGenericInst, tyAlias, tySink: result = isEmptyContainer(t.skipModifier)
  1493. else: result = false
  1494. proc takeType*(formal, arg: PType; g: ModuleGraph; idgen: IdGenerator): PType =
  1495. # param: openArray[string] = []
  1496. # [] is an array constructor of length 0 of type string!
  1497. if arg.kind == tyNil:
  1498. # and not (formal.kind == tyProc and formal.callConv == ccClosure):
  1499. result = formal
  1500. elif formal.kind in {tyOpenArray, tyVarargs, tySequence} and
  1501. arg.isEmptyContainer:
  1502. let a = copyType(arg.skipTypes({tyGenericInst, tyAlias}), idgen, arg.owner)
  1503. copyTypeProps(g, idgen.module, a, arg)
  1504. a[ord(arg.kind == tyArray)] = formal[0]
  1505. result = a
  1506. elif formal.kind in {tyTuple, tySet} and arg.kind == formal.kind:
  1507. result = formal
  1508. else:
  1509. result = arg
  1510. proc skipHiddenSubConv*(n: PNode; g: ModuleGraph; idgen: IdGenerator): PNode =
  1511. if n.kind == nkHiddenSubConv:
  1512. # param: openArray[string] = []
  1513. # [] is an array constructor of length 0 of type string!
  1514. let formal = n.typ
  1515. result = n[1]
  1516. let arg = result.typ
  1517. let dest = takeType(formal, arg, g, idgen)
  1518. if dest == arg and formal.kind != tyUntyped:
  1519. #echo n.info, " came here for ", formal.typeToString
  1520. result = n
  1521. else:
  1522. result = copyTree(result)
  1523. result.typ = dest
  1524. else:
  1525. result = n
  1526. proc getProcConvMismatch*(c: ConfigRef, f, a: PType, rel = isNone): (set[ProcConvMismatch], TTypeRelation) =
  1527. ## Returns a set of the reason of mismatch, and the relation for conversion.
  1528. result[1] = rel
  1529. if tfNoSideEffect in f.flags and tfNoSideEffect notin a.flags:
  1530. # Formal is pure, but actual is not
  1531. result[0].incl pcmNoSideEffect
  1532. result[1] = isNone
  1533. if tfThread in f.flags and a.flags * {tfThread, tfNoSideEffect} == {} and
  1534. optThreadAnalysis in c.globalOptions:
  1535. # noSideEffect implies ``tfThread``!
  1536. result[0].incl pcmNotGcSafe
  1537. result[1] = isNone
  1538. if f.flags * {tfIterator} != a.flags * {tfIterator}:
  1539. # One of them is an iterator so not convertible
  1540. result[0].incl pcmNotIterator
  1541. result[1] = isNone
  1542. if f.callConv != a.callConv:
  1543. # valid to pass a 'nimcall' thingie to 'closure':
  1544. if f.callConv == ccClosure and a.callConv == ccNimCall:
  1545. case result[1]
  1546. of isInferred: result[1] = isInferredConvertible
  1547. of isBothMetaConvertible: result[1] = isBothMetaConvertible
  1548. elif result[1] != isNone: result[1] = isConvertible
  1549. else: result[0].incl pcmDifferentCallConv
  1550. else:
  1551. result[1] = isNone
  1552. result[0].incl pcmDifferentCallConv
  1553. proc addPragmaAndCallConvMismatch*(message: var string, formal, actual: PType, conf: ConfigRef) =
  1554. assert formal.kind == tyProc and actual.kind == tyProc
  1555. let (convMismatch, _) = getProcConvMismatch(conf, formal, actual)
  1556. var
  1557. gotPragmas = ""
  1558. expectedPragmas = ""
  1559. for reason in convMismatch:
  1560. case reason
  1561. of pcmDifferentCallConv:
  1562. message.add "\n Calling convention mismatch: got '{.$1.}', but expected '{.$2.}'." % [$actual.callConv, $formal.callConv]
  1563. of pcmNoSideEffect:
  1564. expectedPragmas.add "noSideEffect, "
  1565. of pcmNotGcSafe:
  1566. expectedPragmas.add "gcsafe, "
  1567. of pcmNotIterator: discard
  1568. if expectedPragmas.len > 0:
  1569. gotPragmas.setLen(max(0, gotPragmas.len - 2)) # Remove ", "
  1570. expectedPragmas.setLen(max(0, expectedPragmas.len - 2)) # Remove ", "
  1571. message.add "\n Pragma mismatch: got '{.$1.}', but expected '{.$2.}'." % [gotPragmas, expectedPragmas]
  1572. proc processPragmaAndCallConvMismatch(msg: var string, formal, actual: PType, conf: ConfigRef) =
  1573. if formal.kind == tyProc and actual.kind == tyProc:
  1574. msg.addPragmaAndCallConvMismatch(formal, actual, conf)
  1575. case compatibleEffects(formal, actual)
  1576. of efCompat: discard
  1577. of efRaisesDiffer:
  1578. msg.add "\n.raise effects differ"
  1579. of efRaisesUnknown:
  1580. msg.add "\n.raise effect is 'can raise any'"
  1581. of efTagsDiffer:
  1582. msg.add "\n.tag effects differ"
  1583. of efTagsUnknown:
  1584. msg.add "\n.tag effect is 'any tag allowed'"
  1585. of efEffectsDelayed:
  1586. msg.add "\n.effectsOf annotations differ"
  1587. of efTagsIllegal:
  1588. msg.add "\n.notTag catched an illegal effect"
  1589. proc typeNameAndDesc*(t: PType): string =
  1590. result = typeToString(t)
  1591. let desc = typeToString(t, preferDesc)
  1592. if result != desc:
  1593. result.add(" = ")
  1594. result.add(desc)
  1595. proc typeMismatch*(conf: ConfigRef; info: TLineInfo, formal, actual: PType, n: PNode) =
  1596. if formal.kind != tyError and actual.kind != tyError:
  1597. let actualStr = typeToString(actual)
  1598. let formalStr = typeToString(formal)
  1599. let desc = typeToString(formal, preferDesc)
  1600. let x = if formalStr == desc: formalStr else: formalStr & " = " & desc
  1601. let verbose = actualStr == formalStr or optDeclaredLocs in conf.globalOptions
  1602. var msg = "type mismatch:"
  1603. if verbose: msg.add "\n"
  1604. if conf.isDefined("nimLegacyTypeMismatch"):
  1605. msg.add " got <$1>" % actualStr
  1606. else:
  1607. msg.add " got '$1' for '$2'" % [actualStr, n.renderTree]
  1608. if verbose:
  1609. msg.addDeclaredLoc(conf, actual)
  1610. msg.add "\n"
  1611. msg.add " but expected '$1'" % x
  1612. if verbose: msg.addDeclaredLoc(conf, formal)
  1613. var a = formal
  1614. var b = actual
  1615. if formal.kind == tyArray and actual.kind == tyArray:
  1616. a = formal[1]
  1617. b = actual[1]
  1618. processPragmaAndCallConvMismatch(msg, a, b, conf)
  1619. elif formal.kind == tySequence and actual.kind == tySequence:
  1620. a = formal[0]
  1621. b = actual[0]
  1622. processPragmaAndCallConvMismatch(msg, a, b, conf)
  1623. else:
  1624. processPragmaAndCallConvMismatch(msg, a, b, conf)
  1625. localError(conf, info, msg)
  1626. proc isTupleRecursive(t: PType, cycleDetector: var IntSet): bool =
  1627. if t == nil:
  1628. return false
  1629. if cycleDetector.containsOrIncl(t.id):
  1630. return true
  1631. case t.kind
  1632. of tyTuple:
  1633. result = false
  1634. var cycleDetectorCopy: IntSet
  1635. for a in t.kids:
  1636. cycleDetectorCopy = cycleDetector
  1637. if isTupleRecursive(a, cycleDetectorCopy):
  1638. return true
  1639. of tyRef, tyPtr, tyVar, tyLent, tySink,
  1640. tyArray, tyUncheckedArray, tySequence, tyDistinct:
  1641. return isTupleRecursive(t.elementType, cycleDetector)
  1642. of tyAlias, tyGenericInst:
  1643. return isTupleRecursive(t.skipModifier, cycleDetector)
  1644. else:
  1645. return false
  1646. proc isTupleRecursive*(t: PType): bool =
  1647. var cycleDetector = initIntSet()
  1648. isTupleRecursive(t, cycleDetector)
  1649. proc isException*(t: PType): bool =
  1650. # check if `y` is object type and it inherits from Exception
  1651. assert(t != nil)
  1652. var t = t.skipTypes(abstractInst)
  1653. while t.kind == tyObject:
  1654. if t.sym != nil and t.sym.magic == mException: return true
  1655. if t.baseClass == nil: break
  1656. t = skipTypes(t.baseClass, abstractPtrs)
  1657. return false
  1658. proc isDefectException*(t: PType): bool =
  1659. var t = t.skipTypes(abstractPtrs)
  1660. while t.kind == tyObject:
  1661. if t.sym != nil and t.sym.owner != nil and
  1662. sfSystemModule in t.sym.owner.flags and
  1663. t.sym.name.s == "Defect":
  1664. return true
  1665. if t.baseClass == nil: break
  1666. t = skipTypes(t.baseClass, abstractPtrs)
  1667. return false
  1668. proc isDefectOrCatchableError*(t: PType): bool =
  1669. var t = t.skipTypes(abstractPtrs)
  1670. while t.kind == tyObject:
  1671. if t.sym != nil and t.sym.owner != nil and
  1672. sfSystemModule in t.sym.owner.flags and
  1673. (t.sym.name.s == "Defect" or
  1674. t.sym.name.s == "CatchableError"):
  1675. return true
  1676. if t.baseClass == nil: break
  1677. t = skipTypes(t.baseClass, abstractPtrs)
  1678. return false
  1679. proc isSinkTypeForParam*(t: PType): bool =
  1680. # a parameter like 'seq[owned T]' must not be used only once, but its
  1681. # elements must, so we detect this case here:
  1682. result = t.skipTypes({tyGenericInst, tyAlias}).kind in {tySink, tyOwned}
  1683. when false:
  1684. if isSinkType(t):
  1685. if t.skipTypes({tyGenericInst, tyAlias}).kind in {tyArray, tyVarargs, tyOpenArray, tySequence}:
  1686. result = false
  1687. else:
  1688. result = true
  1689. proc lookupFieldAgain*(ty: PType; field: PSym): PSym =
  1690. result = nil
  1691. var ty = ty
  1692. while ty != nil:
  1693. ty = ty.skipTypes(skipPtrs)
  1694. assert(ty.kind in {tyTuple, tyObject})
  1695. result = lookupInRecord(ty.n, field.name)
  1696. if result != nil: break
  1697. ty = ty.baseClass
  1698. if result == nil: result = field
  1699. proc isCharArrayPtr*(t: PType; allowPointerToChar: bool): bool =
  1700. let t = t.skipTypes(abstractInst)
  1701. if t.kind == tyPtr:
  1702. let pointsTo = t.elementType.skipTypes(abstractInst)
  1703. case pointsTo.kind
  1704. of tyUncheckedArray:
  1705. result = pointsTo.elementType.kind == tyChar
  1706. of tyArray:
  1707. result = pointsTo.elementType.kind == tyChar and firstOrd(nil, pointsTo.indexType) == 0 and
  1708. skipTypes(pointsTo.indexType, {tyRange}).kind in {tyInt..tyInt64}
  1709. of tyChar:
  1710. result = allowPointerToChar
  1711. else:
  1712. result = false
  1713. else:
  1714. result = false