astalgo.nim 32 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075
  1. #
  2. #
  3. # The Nim Compiler
  4. # (c) Copyright 2012 Andreas Rumpf
  5. #
  6. # See the file "copying.txt", included in this
  7. # distribution, for details about the copyright.
  8. #
  9. # Algorithms for the abstract syntax tree: hash tables, lists
  10. # and sets of nodes are supported. Efficiency is important as
  11. # the data structures here are used in various places of the compiler.
  12. import
  13. ast, hashes, intsets, options, lineinfos, ropes, idents, rodutils,
  14. msgs
  15. import strutils except addf
  16. when defined(nimPreviewSlimSystem):
  17. import std/assertions
  18. proc hashNode*(p: RootRef): Hash
  19. proc treeToYaml*(conf: ConfigRef; n: PNode, indent: int = 0, maxRecDepth: int = - 1): Rope
  20. # Convert a tree into its YAML representation; this is used by the
  21. # YAML code generator and it is invaluable for debugging purposes.
  22. # If maxRecDepht <> -1 then it won't print the whole graph.
  23. proc typeToYaml*(conf: ConfigRef; n: PType, indent: int = 0, maxRecDepth: int = - 1): Rope
  24. proc symToYaml*(conf: ConfigRef; n: PSym, indent: int = 0, maxRecDepth: int = - 1): Rope
  25. proc lineInfoToStr*(conf: ConfigRef; info: TLineInfo): Rope
  26. # these are for debugging only: They are not really deprecated, but I want
  27. # the warning so that release versions do not contain debugging statements:
  28. proc debug*(n: PSym; conf: ConfigRef = nil) {.exportc: "debugSym", deprecated.}
  29. proc debug*(n: PType; conf: ConfigRef = nil) {.exportc: "debugType", deprecated.}
  30. proc debug*(n: PNode; conf: ConfigRef = nil) {.exportc: "debugNode", deprecated.}
  31. proc typekinds*(t: PType) {.deprecated.} =
  32. var t = t
  33. var s = ""
  34. while t != nil and t.len > 0:
  35. s.add $t.kind
  36. s.add " "
  37. t = t.lastSon
  38. echo s
  39. template debug*(x: PSym|PType|PNode) {.deprecated.} =
  40. when compiles(c.config):
  41. debug(c.config, x)
  42. elif compiles(c.graph.config):
  43. debug(c.graph.config, x)
  44. else:
  45. error()
  46. template debug*(x: auto) {.deprecated.} =
  47. echo x
  48. template mdbg*: bool {.deprecated.} =
  49. when compiles(c.graph):
  50. c.module.fileIdx == c.graph.config.projectMainIdx
  51. elif compiles(c.module):
  52. c.module.fileIdx == c.config.projectMainIdx
  53. elif compiles(c.c.module):
  54. c.c.module.fileIdx == c.c.config.projectMainIdx
  55. elif compiles(m.c.module):
  56. m.c.module.fileIdx == m.c.config.projectMainIdx
  57. elif compiles(cl.c.module):
  58. cl.c.module.fileIdx == cl.c.config.projectMainIdx
  59. elif compiles(p):
  60. when compiles(p.lex):
  61. p.lex.fileIdx == p.lex.config.projectMainIdx
  62. else:
  63. p.module.module.fileIdx == p.config.projectMainIdx
  64. elif compiles(m.module.fileIdx):
  65. m.module.fileIdx == m.config.projectMainIdx
  66. elif compiles(L.fileIdx):
  67. L.fileIdx == L.config.projectMainIdx
  68. else:
  69. error()
  70. # --------------------------- ident tables ----------------------------------
  71. proc idTableGet*(t: TIdTable, key: PIdObj): RootRef
  72. proc idTableGet*(t: TIdTable, key: int): RootRef
  73. proc idTablePut*(t: var TIdTable, key: PIdObj, val: RootRef)
  74. proc idTableHasObjectAsKey*(t: TIdTable, key: PIdObj): bool
  75. # checks if `t` contains the `key` (compared by the pointer value, not only
  76. # `key`'s id)
  77. proc idNodeTableGet*(t: TIdNodeTable, key: PIdObj): PNode
  78. proc idNodeTablePut*(t: var TIdNodeTable, key: PIdObj, val: PNode)
  79. # ---------------------------------------------------------------------------
  80. proc lookupInRecord*(n: PNode, field: PIdent): PSym
  81. proc mustRehash*(length, counter: int): bool
  82. proc nextTry*(h, maxHash: Hash): Hash {.inline.}
  83. # ------------- table[int, int] ---------------------------------------------
  84. const
  85. InvalidKey* = low(int)
  86. type
  87. TIIPair*{.final.} = object
  88. key*, val*: int
  89. TIIPairSeq* = seq[TIIPair]
  90. TIITable*{.final.} = object # table[int, int]
  91. counter*: int
  92. data*: TIIPairSeq
  93. proc initIiTable*(x: var TIITable)
  94. proc iiTableGet*(t: TIITable, key: int): int
  95. proc iiTablePut*(t: var TIITable, key, val: int)
  96. # implementation
  97. proc skipConvCastAndClosure*(n: PNode): PNode =
  98. result = n
  99. while true:
  100. case result.kind
  101. of nkObjUpConv, nkObjDownConv, nkChckRange, nkChckRangeF, nkChckRange64,
  102. nkClosure:
  103. result = result[0]
  104. of nkHiddenStdConv, nkHiddenSubConv, nkConv, nkCast:
  105. result = result[1]
  106. else: break
  107. proc sameValue*(a, b: PNode): bool =
  108. result = false
  109. case a.kind
  110. of nkCharLit..nkUInt64Lit:
  111. if b.kind in {nkCharLit..nkUInt64Lit}: result = getInt(a) == getInt(b)
  112. of nkFloatLit..nkFloat64Lit:
  113. if b.kind in {nkFloatLit..nkFloat64Lit}: result = a.floatVal == b.floatVal
  114. of nkStrLit..nkTripleStrLit:
  115. if b.kind in {nkStrLit..nkTripleStrLit}: result = a.strVal == b.strVal
  116. else:
  117. # don't raise an internal error for 'nim check':
  118. #InternalError(a.info, "SameValue")
  119. discard
  120. proc leValue*(a, b: PNode): bool =
  121. # a <= b?
  122. result = false
  123. case a.kind
  124. of nkCharLit..nkUInt64Lit:
  125. if b.kind in {nkCharLit..nkUInt64Lit}: result = getInt(a) <= getInt(b)
  126. of nkFloatLit..nkFloat64Lit:
  127. if b.kind in {nkFloatLit..nkFloat64Lit}: result = a.floatVal <= b.floatVal
  128. of nkStrLit..nkTripleStrLit:
  129. if b.kind in {nkStrLit..nkTripleStrLit}: result = a.strVal <= b.strVal
  130. else:
  131. # don't raise an internal error for 'nim check':
  132. #InternalError(a.info, "leValue")
  133. discard
  134. proc weakLeValue*(a, b: PNode): TImplication =
  135. if a.kind notin nkLiterals or b.kind notin nkLiterals:
  136. result = impUnknown
  137. else:
  138. result = if leValue(a, b): impYes else: impNo
  139. proc lookupInRecord(n: PNode, field: PIdent): PSym =
  140. result = nil
  141. case n.kind
  142. of nkRecList:
  143. for i in 0..<n.len:
  144. result = lookupInRecord(n[i], field)
  145. if result != nil: return
  146. of nkRecCase:
  147. if (n[0].kind != nkSym): return nil
  148. result = lookupInRecord(n[0], field)
  149. if result != nil: return
  150. for i in 1..<n.len:
  151. case n[i].kind
  152. of nkOfBranch, nkElse:
  153. result = lookupInRecord(lastSon(n[i]), field)
  154. if result != nil: return
  155. else: return nil
  156. of nkSym:
  157. if n.sym.name.id == field.id: result = n.sym
  158. else: return nil
  159. proc getModule*(s: PSym): PSym =
  160. result = s
  161. assert((result.kind == skModule) or (result.owner != result))
  162. while result != nil and result.kind != skModule: result = result.owner
  163. proc fromSystem*(op: PSym): bool {.inline.} = sfSystemModule in getModule(op).flags
  164. proc getSymFromList*(list: PNode, ident: PIdent, start: int = 0): PSym =
  165. for i in start..<list.len:
  166. if list[i].kind == nkSym:
  167. result = list[i].sym
  168. if result.name.id == ident.id: return
  169. else: return nil
  170. result = nil
  171. proc sameIgnoreBacktickGensymInfo(a, b: string): bool =
  172. if a[0] != b[0]: return false
  173. var alen = a.len - 1
  174. while alen > 0 and a[alen] != '`': dec(alen)
  175. if alen <= 0: alen = a.len
  176. var i = 1
  177. var j = 1
  178. while true:
  179. while i < alen and a[i] == '_': inc i
  180. while j < b.len and b[j] == '_': inc j
  181. var aa = if i < alen: toLowerAscii(a[i]) else: '\0'
  182. var bb = if j < b.len: toLowerAscii(b[j]) else: '\0'
  183. if aa != bb: return false
  184. # the characters are identical:
  185. if i >= alen:
  186. # both cursors at the end:
  187. if j >= b.len: return true
  188. # not yet at the end of 'b':
  189. return false
  190. elif j >= b.len:
  191. return false
  192. inc i
  193. inc j
  194. proc getNamedParamFromList*(list: PNode, ident: PIdent): PSym =
  195. ## Named parameters are special because a named parameter can be
  196. ## gensym'ed and then they have '\`<number>' suffix that we need to
  197. ## ignore, see compiler / evaltempl.nim, snippet:
  198. ## ```
  199. ## result.add newIdentNode(getIdent(c.ic, x.name.s & "\`gensym" & $x.id),
  200. ## if c.instLines: actual.info else: templ.info)
  201. ## ```
  202. for i in 1..<list.len:
  203. let it = list[i].sym
  204. if it.name.id == ident.id or
  205. sameIgnoreBacktickGensymInfo(it.name.s, ident.s): return it
  206. proc hashNode(p: RootRef): Hash =
  207. result = hash(cast[pointer](p))
  208. proc mustRehash(length, counter: int): bool =
  209. assert(length > counter)
  210. result = (length * 2 < counter * 3) or (length - counter < 4)
  211. proc rspaces(x: int): Rope =
  212. # returns x spaces
  213. result = rope(spaces(x))
  214. proc toYamlChar(c: char): string =
  215. case c
  216. of '\0'..'\x1F', '\x7F'..'\xFF': result = "\\u" & strutils.toHex(ord(c), 4)
  217. of '\'', '\"', '\\': result = '\\' & c
  218. else: result = $c
  219. proc makeYamlString*(s: string): Rope =
  220. # We have to split long strings into many ropes. Otherwise
  221. # this could trigger InternalError(111). See the ropes module for
  222. # further information.
  223. const MaxLineLength = 64
  224. result = ""
  225. var res = "\""
  226. for i in 0..<s.len:
  227. if (i + 1) mod MaxLineLength == 0:
  228. res.add('\"')
  229. res.add("\n")
  230. result.add(rope(res))
  231. res = "\"" # reset
  232. res.add(toYamlChar(s[i]))
  233. res.add('\"')
  234. result.add(rope(res))
  235. proc flagsToStr[T](flags: set[T]): Rope =
  236. if flags == {}:
  237. result = rope("[]")
  238. else:
  239. result = ""
  240. for x in items(flags):
  241. if result != "": result.add(", ")
  242. result.add(makeYamlString($x))
  243. result = "[" & result & "]"
  244. proc lineInfoToStr(conf: ConfigRef; info: TLineInfo): Rope =
  245. result = "[$1, $2, $3]" % [makeYamlString(toFilename(conf, info)),
  246. rope(toLinenumber(info)),
  247. rope(toColumn(info))]
  248. proc treeToYamlAux(conf: ConfigRef; n: PNode, marker: var IntSet,
  249. indent, maxRecDepth: int): Rope
  250. proc symToYamlAux(conf: ConfigRef; n: PSym, marker: var IntSet,
  251. indent, maxRecDepth: int): Rope
  252. proc typeToYamlAux(conf: ConfigRef; n: PType, marker: var IntSet,
  253. indent, maxRecDepth: int): Rope
  254. proc symToYamlAux(conf: ConfigRef; n: PSym, marker: var IntSet, indent: int,
  255. maxRecDepth: int): Rope =
  256. if n == nil:
  257. result = rope("null")
  258. elif containsOrIncl(marker, n.id):
  259. result = "\"$1\"" % [rope(n.name.s)]
  260. else:
  261. var ast = treeToYamlAux(conf, n.ast, marker, indent + 2, maxRecDepth - 1)
  262. #rope("typ"), typeToYamlAux(conf, n.typ, marker,
  263. # indent + 2, maxRecDepth - 1),
  264. let istr = rspaces(indent + 2)
  265. result = rope("{")
  266. result.addf("$N$1\"kind\": $2", [istr, makeYamlString($n.kind)])
  267. result.addf("$N$1\"name\": $2", [istr, makeYamlString(n.name.s)])
  268. result.addf("$N$1\"typ\": $2", [istr, typeToYamlAux(conf, n.typ, marker, indent + 2, maxRecDepth - 1)])
  269. if conf != nil:
  270. # if we don't pass the config, we probably don't care about the line info
  271. result.addf("$N$1\"info\": $2", [istr, lineInfoToStr(conf, n.info)])
  272. if card(n.flags) > 0:
  273. result.addf("$N$1\"flags\": $2", [istr, flagsToStr(n.flags)])
  274. result.addf("$N$1\"magic\": $2", [istr, makeYamlString($n.magic)])
  275. result.addf("$N$1\"ast\": $2", [istr, ast])
  276. result.addf("$N$1\"options\": $2", [istr, flagsToStr(n.options)])
  277. result.addf("$N$1\"position\": $2", [istr, rope(n.position)])
  278. result.addf("$N$1\"k\": $2", [istr, makeYamlString($n.loc.k)])
  279. result.addf("$N$1\"storage\": $2", [istr, makeYamlString($n.loc.storage)])
  280. if card(n.loc.flags) > 0:
  281. result.addf("$N$1\"flags\": $2", [istr, makeYamlString($n.loc.flags)])
  282. result.addf("$N$1\"r\": $2", [istr, n.loc.r])
  283. result.addf("$N$1\"lode\": $2", [istr, treeToYamlAux(conf, n.loc.lode, marker, indent + 2, maxRecDepth - 1)])
  284. result.addf("$N$1}", [rspaces(indent)])
  285. proc typeToYamlAux(conf: ConfigRef; n: PType, marker: var IntSet, indent: int,
  286. maxRecDepth: int): Rope =
  287. var sonsRope: Rope
  288. if n == nil:
  289. sonsRope = rope("null")
  290. elif containsOrIncl(marker, n.id):
  291. sonsRope = "\"$1 @$2\"" % [rope($n.kind), rope(
  292. strutils.toHex(cast[int](n), sizeof(n) * 2))]
  293. else:
  294. if n.len > 0:
  295. sonsRope = rope("[")
  296. for i in 0..<n.len:
  297. if i > 0: sonsRope.add(",")
  298. sonsRope.addf("$N$1$2", [rspaces(indent + 4), typeToYamlAux(conf, n[i],
  299. marker, indent + 4, maxRecDepth - 1)])
  300. sonsRope.addf("$N$1]", [rspaces(indent + 2)])
  301. else:
  302. sonsRope = rope("null")
  303. let istr = rspaces(indent + 2)
  304. result = rope("{")
  305. result.addf("$N$1\"kind\": $2", [istr, makeYamlString($n.kind)])
  306. result.addf("$N$1\"sym\": $2", [istr, symToYamlAux(conf, n.sym, marker, indent + 2, maxRecDepth - 1)])
  307. result.addf("$N$1\"n\": $2", [istr, treeToYamlAux(conf, n.n, marker, indent + 2, maxRecDepth - 1)])
  308. if card(n.flags) > 0:
  309. result.addf("$N$1\"flags\": $2", [istr, flagsToStr(n.flags)])
  310. result.addf("$N$1\"callconv\": $2", [istr, makeYamlString($n.callConv)])
  311. result.addf("$N$1\"size\": $2", [istr, rope(n.size)])
  312. result.addf("$N$1\"align\": $2", [istr, rope(n.align)])
  313. result.addf("$N$1\"sons\": $2", [istr, sonsRope])
  314. proc treeToYamlAux(conf: ConfigRef; n: PNode, marker: var IntSet, indent: int,
  315. maxRecDepth: int): Rope =
  316. if n == nil:
  317. result = rope("null")
  318. else:
  319. var istr = rspaces(indent + 2)
  320. result = "{$N$1\"kind\": $2" % [istr, makeYamlString($n.kind)]
  321. if maxRecDepth != 0:
  322. if conf != nil:
  323. result.addf(",$N$1\"info\": $2", [istr, lineInfoToStr(conf, n.info)])
  324. case n.kind
  325. of nkCharLit..nkInt64Lit:
  326. result.addf(",$N$1\"intVal\": $2", [istr, rope(n.intVal)])
  327. of nkFloatLit, nkFloat32Lit, nkFloat64Lit:
  328. result.addf(",$N$1\"floatVal\": $2",
  329. [istr, rope(n.floatVal.toStrMaxPrecision)])
  330. of nkStrLit..nkTripleStrLit:
  331. result.addf(",$N$1\"strVal\": $2", [istr, makeYamlString(n.strVal)])
  332. of nkSym:
  333. result.addf(",$N$1\"sym\": $2",
  334. [istr, symToYamlAux(conf, n.sym, marker, indent + 2, maxRecDepth)])
  335. of nkIdent:
  336. if n.ident != nil:
  337. result.addf(",$N$1\"ident\": $2", [istr, makeYamlString(n.ident.s)])
  338. else:
  339. result.addf(",$N$1\"ident\": null", [istr])
  340. else:
  341. if n.len > 0:
  342. result.addf(",$N$1\"sons\": [", [istr])
  343. for i in 0..<n.len:
  344. if i > 0: result.add(",")
  345. result.addf("$N$1$2", [rspaces(indent + 4), treeToYamlAux(conf, n[i],
  346. marker, indent + 4, maxRecDepth - 1)])
  347. result.addf("$N$1]", [istr])
  348. result.addf(",$N$1\"typ\": $2",
  349. [istr, typeToYamlAux(conf, n.typ, marker, indent + 2, maxRecDepth)])
  350. result.addf("$N$1}", [rspaces(indent)])
  351. proc treeToYaml(conf: ConfigRef; n: PNode, indent: int = 0, maxRecDepth: int = - 1): Rope =
  352. var marker = initIntSet()
  353. result = treeToYamlAux(conf, n, marker, indent, maxRecDepth)
  354. proc typeToYaml(conf: ConfigRef; n: PType, indent: int = 0, maxRecDepth: int = - 1): Rope =
  355. var marker = initIntSet()
  356. result = typeToYamlAux(conf, n, marker, indent, maxRecDepth)
  357. proc symToYaml(conf: ConfigRef; n: PSym, indent: int = 0, maxRecDepth: int = - 1): Rope =
  358. var marker = initIntSet()
  359. result = symToYamlAux(conf, n, marker, indent, maxRecDepth)
  360. import tables
  361. const backrefStyle = "\e[90m"
  362. const enumStyle = "\e[34m"
  363. const numberStyle = "\e[33m"
  364. const stringStyle = "\e[32m"
  365. const resetStyle = "\e[0m"
  366. type
  367. DebugPrinter = object
  368. conf: ConfigRef
  369. visited: Table[pointer, int]
  370. renderSymType: bool
  371. indent: int
  372. currentLine: int
  373. firstItem: bool
  374. useColor: bool
  375. res: string
  376. proc indentMore(this: var DebugPrinter) =
  377. this.indent += 2
  378. proc indentLess(this: var DebugPrinter) =
  379. this.indent -= 2
  380. proc newlineAndIndent(this: var DebugPrinter) =
  381. this.res.add "\n"
  382. this.currentLine += 1
  383. for i in 0..<this.indent:
  384. this.res.add ' '
  385. proc openCurly(this: var DebugPrinter) =
  386. this.res.add "{"
  387. this.indentMore
  388. this.firstItem = true
  389. proc closeCurly(this: var DebugPrinter) =
  390. this.indentLess
  391. this.newlineAndIndent
  392. this.res.add "}"
  393. proc comma(this: var DebugPrinter) =
  394. this.res.add ", "
  395. proc openBracket(this: var DebugPrinter) =
  396. this.res.add "["
  397. #this.indentMore
  398. proc closeBracket(this: var DebugPrinter) =
  399. #this.indentLess
  400. this.res.add "]"
  401. proc key(this: var DebugPrinter; key: string) =
  402. if not this.firstItem:
  403. this.res.add ","
  404. this.firstItem = false
  405. this.newlineAndIndent
  406. this.res.add "\""
  407. this.res.add key
  408. this.res.add "\": "
  409. proc value(this: var DebugPrinter; value: string) =
  410. if this.useColor:
  411. this.res.add stringStyle
  412. this.res.add "\""
  413. this.res.add value
  414. this.res.add "\""
  415. if this.useColor:
  416. this.res.add resetStyle
  417. proc value(this: var DebugPrinter; value: BiggestInt) =
  418. if this.useColor:
  419. this.res.add numberStyle
  420. this.res.addInt value
  421. if this.useColor:
  422. this.res.add resetStyle
  423. proc value[T: enum](this: var DebugPrinter; value: T) =
  424. if this.useColor:
  425. this.res.add enumStyle
  426. this.res.add "\""
  427. this.res.add $value
  428. this.res.add "\""
  429. if this.useColor:
  430. this.res.add resetStyle
  431. proc value[T: enum](this: var DebugPrinter; value: set[T]) =
  432. this.openBracket
  433. let high = card(value)-1
  434. var i = 0
  435. for v in value:
  436. this.value v
  437. if i != high:
  438. this.comma
  439. inc i
  440. this.closeBracket
  441. template earlyExit(this: var DebugPrinter; n: PType | PNode | PSym) =
  442. if n == nil:
  443. this.res.add "null"
  444. return
  445. let index = this.visited.getOrDefault(cast[pointer](n), -1)
  446. if index < 0:
  447. this.visited[cast[pointer](n)] = this.currentLine
  448. else:
  449. if this.useColor:
  450. this.res.add backrefStyle
  451. this.res.add "<defined "
  452. this.res.addInt(this.currentLine - index)
  453. this.res.add " lines upwards>"
  454. if this.useColor:
  455. this.res.add resetStyle
  456. return
  457. proc value(this: var DebugPrinter; value: PType)
  458. proc value(this: var DebugPrinter; value: PNode)
  459. proc value(this: var DebugPrinter; value: PSym) =
  460. earlyExit(this, value)
  461. this.openCurly
  462. this.key("kind")
  463. this.value(value.kind)
  464. this.key("name")
  465. this.value(value.name.s)
  466. this.key("id")
  467. this.value(value.id)
  468. if value.kind in {skField, skEnumField, skParam}:
  469. this.key("position")
  470. this.value(value.position)
  471. if card(value.flags) > 0:
  472. this.key("flags")
  473. this.value(value.flags)
  474. if this.renderSymType and value.typ != nil:
  475. this.key "typ"
  476. this.value(value.typ)
  477. this.closeCurly
  478. proc value(this: var DebugPrinter; value: PType) =
  479. earlyExit(this, value)
  480. this.openCurly
  481. this.key "kind"
  482. this.value value.kind
  483. this.key "id"
  484. this.value value.id
  485. if value.sym != nil:
  486. this.key "sym"
  487. this.value value.sym
  488. #this.value value.sym.name.s
  489. if card(value.flags) > 0:
  490. this.key "flags"
  491. this.value value.flags
  492. if value.kind in IntegralTypes and value.n != nil:
  493. this.key "n"
  494. this.value value.n
  495. if value.len > 0:
  496. this.key "sons"
  497. this.openBracket
  498. for i in 0..<value.len:
  499. this.value value[i]
  500. if i != value.len - 1:
  501. this.comma
  502. this.closeBracket
  503. if value.n != nil:
  504. this.key "n"
  505. this.value value.n
  506. this.closeCurly
  507. proc value(this: var DebugPrinter; value: PNode) =
  508. earlyExit(this, value)
  509. this.openCurly
  510. this.key "kind"
  511. this.value value.kind
  512. if value.comment.len > 0:
  513. this.key "comment"
  514. this.value value.comment
  515. when defined(useNodeIds):
  516. this.key "id"
  517. this.value value.id
  518. if this.conf != nil:
  519. this.key "info"
  520. this.value $lineInfoToStr(this.conf, value.info)
  521. if value.flags != {}:
  522. this.key "flags"
  523. this.value value.flags
  524. if value.typ != nil:
  525. this.key "typ"
  526. this.value value.typ.kind
  527. else:
  528. this.key "typ"
  529. this.value "nil"
  530. case value.kind
  531. of nkCharLit..nkUInt64Lit:
  532. this.key "intVal"
  533. this.value value.intVal
  534. of nkFloatLit, nkFloat32Lit, nkFloat64Lit:
  535. this.key "floatVal"
  536. this.value value.floatVal.toStrMaxPrecision
  537. of nkStrLit..nkTripleStrLit:
  538. this.key "strVal"
  539. this.value value.strVal
  540. of nkSym:
  541. this.key "sym"
  542. this.value value.sym
  543. #this.value value.sym.name.s
  544. of nkIdent:
  545. if value.ident != nil:
  546. this.key "ident"
  547. this.value value.ident.s
  548. else:
  549. if this.renderSymType and value.typ != nil:
  550. this.key "typ"
  551. this.value value.typ
  552. if value.len > 0:
  553. this.key "sons"
  554. this.openBracket
  555. for i in 0..<value.len:
  556. this.value value[i]
  557. if i != value.len - 1:
  558. this.comma
  559. this.closeBracket
  560. this.closeCurly
  561. proc debug(n: PSym; conf: ConfigRef) =
  562. var this: DebugPrinter
  563. this.visited = initTable[pointer, int]()
  564. this.renderSymType = true
  565. this.useColor = not defined(windows)
  566. this.value(n)
  567. echo($this.res)
  568. proc debug(n: PType; conf: ConfigRef) =
  569. var this: DebugPrinter
  570. this.visited = initTable[pointer, int]()
  571. this.renderSymType = true
  572. this.useColor = not defined(windows)
  573. this.value(n)
  574. echo($this.res)
  575. proc debug(n: PNode; conf: ConfigRef) =
  576. var this: DebugPrinter
  577. this.visited = initTable[pointer, int]()
  578. #this.renderSymType = true
  579. this.useColor = not defined(windows)
  580. this.value(n)
  581. echo($this.res)
  582. proc nextTry(h, maxHash: Hash): Hash =
  583. result = ((5 * h) + 1) and maxHash
  584. # For any initial h in range(maxHash), repeating that maxHash times
  585. # generates each int in range(maxHash) exactly once (see any text on
  586. # random-number generation for proof).
  587. proc objectSetContains*(t: TObjectSet, obj: RootRef): bool =
  588. # returns true whether n is in t
  589. var h: Hash = hashNode(obj) and high(t.data) # start with real hash value
  590. while t.data[h] != nil:
  591. if t.data[h] == obj:
  592. return true
  593. h = nextTry(h, high(t.data))
  594. result = false
  595. proc objectSetRawInsert(data: var TObjectSeq, obj: RootRef) =
  596. var h: Hash = hashNode(obj) and high(data)
  597. while data[h] != nil:
  598. assert(data[h] != obj)
  599. h = nextTry(h, high(data))
  600. assert(data[h] == nil)
  601. data[h] = obj
  602. proc objectSetEnlarge(t: var TObjectSet) =
  603. var n: TObjectSeq
  604. newSeq(n, t.data.len * GrowthFactor)
  605. for i in 0..high(t.data):
  606. if t.data[i] != nil: objectSetRawInsert(n, t.data[i])
  607. swap(t.data, n)
  608. proc objectSetIncl*(t: var TObjectSet, obj: RootRef) =
  609. if mustRehash(t.data.len, t.counter): objectSetEnlarge(t)
  610. objectSetRawInsert(t.data, obj)
  611. inc(t.counter)
  612. proc objectSetContainsOrIncl*(t: var TObjectSet, obj: RootRef): bool =
  613. # returns true if obj is already in the string table:
  614. var h: Hash = hashNode(obj) and high(t.data)
  615. while true:
  616. var it = t.data[h]
  617. if it == nil: break
  618. if it == obj:
  619. return true # found it
  620. h = nextTry(h, high(t.data))
  621. if mustRehash(t.data.len, t.counter):
  622. objectSetEnlarge(t)
  623. objectSetRawInsert(t.data, obj)
  624. else:
  625. assert(t.data[h] == nil)
  626. t.data[h] = obj
  627. inc(t.counter)
  628. result = false
  629. proc strTableContains*(t: TStrTable, n: PSym): bool =
  630. var h: Hash = n.name.h and high(t.data) # start with real hash value
  631. while t.data[h] != nil:
  632. if (t.data[h] == n):
  633. return true
  634. h = nextTry(h, high(t.data))
  635. result = false
  636. proc strTableRawInsert(data: var seq[PSym], n: PSym) =
  637. var h: Hash = n.name.h and high(data)
  638. while data[h] != nil:
  639. if data[h] == n:
  640. # allowed for 'export' feature:
  641. #InternalError(n.info, "StrTableRawInsert: " & n.name.s)
  642. return
  643. h = nextTry(h, high(data))
  644. assert(data[h] == nil)
  645. data[h] = n
  646. proc symTabReplaceRaw(data: var seq[PSym], prevSym: PSym, newSym: PSym) =
  647. assert prevSym.name.h == newSym.name.h
  648. var h: Hash = prevSym.name.h and high(data)
  649. while data[h] != nil:
  650. if data[h] == prevSym:
  651. data[h] = newSym
  652. return
  653. h = nextTry(h, high(data))
  654. assert false
  655. proc symTabReplace*(t: var TStrTable, prevSym: PSym, newSym: PSym) =
  656. symTabReplaceRaw(t.data, prevSym, newSym)
  657. proc strTableEnlarge(t: var TStrTable) =
  658. var n: seq[PSym]
  659. newSeq(n, t.data.len * GrowthFactor)
  660. for i in 0..high(t.data):
  661. if t.data[i] != nil: strTableRawInsert(n, t.data[i])
  662. swap(t.data, n)
  663. proc strTableAdd*(t: var TStrTable, n: PSym) =
  664. if mustRehash(t.data.len, t.counter): strTableEnlarge(t)
  665. strTableRawInsert(t.data, n)
  666. inc(t.counter)
  667. proc strTableInclReportConflict*(t: var TStrTable, n: PSym;
  668. onConflictKeepOld = false): PSym =
  669. # if `t` has a conflicting symbol (same identifier as `n`), return it
  670. # otherwise return `nil`. Incl `n` to `t` unless `onConflictKeepOld = true`
  671. # and a conflict was found.
  672. assert n.name != nil
  673. var h: Hash = n.name.h and high(t.data)
  674. var replaceSlot = -1
  675. while true:
  676. var it = t.data[h]
  677. if it == nil: break
  678. # Semantic checking can happen multiple times thanks to templates
  679. # and overloading: (var x=@[]; x).mapIt(it).
  680. # So it is possible the very same sym is added multiple
  681. # times to the symbol table which we allow here with the 'it == n' check.
  682. if it.name.id == n.name.id:
  683. if it == n: return nil
  684. replaceSlot = h
  685. h = nextTry(h, high(t.data))
  686. if replaceSlot >= 0:
  687. result = t.data[replaceSlot] # found it
  688. if not onConflictKeepOld:
  689. t.data[replaceSlot] = n # overwrite it with newer definition!
  690. return result # but return the old one
  691. elif mustRehash(t.data.len, t.counter):
  692. strTableEnlarge(t)
  693. strTableRawInsert(t.data, n)
  694. else:
  695. assert(t.data[h] == nil)
  696. t.data[h] = n
  697. inc(t.counter)
  698. result = nil
  699. proc strTableIncl*(t: var TStrTable, n: PSym;
  700. onConflictKeepOld = false): bool {.discardable.} =
  701. result = strTableInclReportConflict(t, n, onConflictKeepOld) != nil
  702. proc strTableGet*(t: TStrTable, name: PIdent): PSym =
  703. var h: Hash = name.h and high(t.data)
  704. while true:
  705. result = t.data[h]
  706. if result == nil: break
  707. if result.name.id == name.id: break
  708. h = nextTry(h, high(t.data))
  709. type
  710. TIdentIter* = object # iterator over all syms with same identifier
  711. h*: Hash # current hash
  712. name*: PIdent
  713. proc nextIdentIter*(ti: var TIdentIter, tab: TStrTable): PSym =
  714. # hot spots
  715. var h = ti.h and high(tab.data)
  716. var start = h
  717. var p {.cursor.} = tab.data[h]
  718. while p != nil:
  719. if p.name.id == ti.name.id: break
  720. h = nextTry(h, high(tab.data))
  721. if h == start:
  722. p = nil
  723. break
  724. p = tab.data[h]
  725. if p != nil:
  726. result = p # increase the count
  727. else:
  728. result = nil
  729. ti.h = nextTry(h, high(tab.data))
  730. proc initIdentIter*(ti: var TIdentIter, tab: TStrTable, s: PIdent): PSym =
  731. ti.h = s.h
  732. ti.name = s
  733. if tab.counter == 0: result = nil
  734. else: result = nextIdentIter(ti, tab)
  735. proc nextIdentExcluding*(ti: var TIdentIter, tab: TStrTable,
  736. excluding: IntSet): PSym =
  737. var h: Hash = ti.h and high(tab.data)
  738. var start = h
  739. result = tab.data[h]
  740. while result != nil:
  741. if result.name.id == ti.name.id and not contains(excluding, result.id):
  742. break
  743. h = nextTry(h, high(tab.data))
  744. if h == start:
  745. result = nil
  746. break
  747. result = tab.data[h]
  748. ti.h = nextTry(h, high(tab.data))
  749. if result != nil and contains(excluding, result.id): result = nil
  750. proc firstIdentExcluding*(ti: var TIdentIter, tab: TStrTable, s: PIdent,
  751. excluding: IntSet): PSym =
  752. ti.h = s.h
  753. ti.name = s
  754. if tab.counter == 0: result = nil
  755. else: result = nextIdentExcluding(ti, tab, excluding)
  756. type
  757. TTabIter* = object
  758. h: Hash
  759. proc nextIter*(ti: var TTabIter, tab: TStrTable): PSym =
  760. # usage:
  761. # var
  762. # i: TTabIter
  763. # s: PSym
  764. # s = InitTabIter(i, table)
  765. # while s != nil:
  766. # ...
  767. # s = NextIter(i, table)
  768. #
  769. result = nil
  770. while (ti.h <= high(tab.data)):
  771. result = tab.data[ti.h]
  772. inc(ti.h) # ... and increment by one always
  773. if result != nil: break
  774. proc initTabIter*(ti: var TTabIter, tab: TStrTable): PSym =
  775. ti.h = 0
  776. if tab.counter == 0:
  777. result = nil
  778. else:
  779. result = nextIter(ti, tab)
  780. iterator items*(tab: TStrTable): PSym =
  781. var it: TTabIter
  782. var s = initTabIter(it, tab)
  783. while s != nil:
  784. yield s
  785. s = nextIter(it, tab)
  786. proc hasEmptySlot(data: TIdPairSeq): bool =
  787. for h in 0..high(data):
  788. if data[h].key == nil:
  789. return true
  790. result = false
  791. proc idTableRawGet(t: TIdTable, key: int): int =
  792. var h: Hash
  793. h = key and high(t.data) # start with real hash value
  794. while t.data[h].key != nil:
  795. if t.data[h].key.id == key:
  796. return h
  797. h = nextTry(h, high(t.data))
  798. result = - 1
  799. proc idTableHasObjectAsKey(t: TIdTable, key: PIdObj): bool =
  800. var index = idTableRawGet(t, key.id)
  801. if index >= 0: result = t.data[index].key == key
  802. else: result = false
  803. proc idTableGet(t: TIdTable, key: PIdObj): RootRef =
  804. var index = idTableRawGet(t, key.id)
  805. if index >= 0: result = t.data[index].val
  806. else: result = nil
  807. proc idTableGet(t: TIdTable, key: int): RootRef =
  808. var index = idTableRawGet(t, key)
  809. if index >= 0: result = t.data[index].val
  810. else: result = nil
  811. iterator pairs*(t: TIdTable): tuple[key: int, value: RootRef] =
  812. for i in 0..high(t.data):
  813. if t.data[i].key != nil:
  814. yield (t.data[i].key.id, t.data[i].val)
  815. proc idTableRawInsert(data: var TIdPairSeq, key: PIdObj, val: RootRef) =
  816. var h: Hash
  817. h = key.id and high(data)
  818. while data[h].key != nil:
  819. assert(data[h].key.id != key.id)
  820. h = nextTry(h, high(data))
  821. assert(data[h].key == nil)
  822. data[h].key = key
  823. data[h].val = val
  824. proc idTablePut(t: var TIdTable, key: PIdObj, val: RootRef) =
  825. var
  826. index: int
  827. n: TIdPairSeq
  828. index = idTableRawGet(t, key.id)
  829. if index >= 0:
  830. assert(t.data[index].key != nil)
  831. t.data[index].val = val
  832. else:
  833. if mustRehash(t.data.len, t.counter):
  834. newSeq(n, t.data.len * GrowthFactor)
  835. for i in 0..high(t.data):
  836. if t.data[i].key != nil:
  837. idTableRawInsert(n, t.data[i].key, t.data[i].val)
  838. assert(hasEmptySlot(n))
  839. swap(t.data, n)
  840. idTableRawInsert(t.data, key, val)
  841. inc(t.counter)
  842. iterator idTablePairs*(t: TIdTable): tuple[key: PIdObj, val: RootRef] =
  843. for i in 0..high(t.data):
  844. if not isNil(t.data[i].key): yield (t.data[i].key, t.data[i].val)
  845. proc idNodeTableRawGet(t: TIdNodeTable, key: PIdObj): int =
  846. var h: Hash
  847. h = key.id and high(t.data) # start with real hash value
  848. while t.data[h].key != nil:
  849. if t.data[h].key.id == key.id:
  850. return h
  851. h = nextTry(h, high(t.data))
  852. result = - 1
  853. proc idNodeTableGet(t: TIdNodeTable, key: PIdObj): PNode =
  854. var index: int
  855. index = idNodeTableRawGet(t, key)
  856. if index >= 0: result = t.data[index].val
  857. else: result = nil
  858. proc idNodeTableRawInsert(data: var TIdNodePairSeq, key: PIdObj, val: PNode) =
  859. var h: Hash
  860. h = key.id and high(data)
  861. while data[h].key != nil:
  862. assert(data[h].key.id != key.id)
  863. h = nextTry(h, high(data))
  864. assert(data[h].key == nil)
  865. data[h].key = key
  866. data[h].val = val
  867. proc idNodeTablePut(t: var TIdNodeTable, key: PIdObj, val: PNode) =
  868. var index = idNodeTableRawGet(t, key)
  869. if index >= 0:
  870. assert(t.data[index].key != nil)
  871. t.data[index].val = val
  872. else:
  873. if mustRehash(t.data.len, t.counter):
  874. var n: TIdNodePairSeq
  875. newSeq(n, t.data.len * GrowthFactor)
  876. for i in 0..high(t.data):
  877. if t.data[i].key != nil:
  878. idNodeTableRawInsert(n, t.data[i].key, t.data[i].val)
  879. swap(t.data, n)
  880. idNodeTableRawInsert(t.data, key, val)
  881. inc(t.counter)
  882. iterator pairs*(t: TIdNodeTable): tuple[key: PIdObj, val: PNode] =
  883. for i in 0..high(t.data):
  884. if not isNil(t.data[i].key): yield (t.data[i].key, t.data[i].val)
  885. proc initIITable(x: var TIITable) =
  886. x.counter = 0
  887. newSeq(x.data, StartSize)
  888. for i in 0..<StartSize: x.data[i].key = InvalidKey
  889. proc iiTableRawGet(t: TIITable, key: int): int =
  890. var h: Hash
  891. h = key and high(t.data) # start with real hash value
  892. while t.data[h].key != InvalidKey:
  893. if t.data[h].key == key: return h
  894. h = nextTry(h, high(t.data))
  895. result = -1
  896. proc iiTableGet(t: TIITable, key: int): int =
  897. var index = iiTableRawGet(t, key)
  898. if index >= 0: result = t.data[index].val
  899. else: result = InvalidKey
  900. proc iiTableRawInsert(data: var TIIPairSeq, key, val: int) =
  901. var h: Hash
  902. h = key and high(data)
  903. while data[h].key != InvalidKey:
  904. assert(data[h].key != key)
  905. h = nextTry(h, high(data))
  906. assert(data[h].key == InvalidKey)
  907. data[h].key = key
  908. data[h].val = val
  909. proc iiTablePut(t: var TIITable, key, val: int) =
  910. var index = iiTableRawGet(t, key)
  911. if index >= 0:
  912. assert(t.data[index].key != InvalidKey)
  913. t.data[index].val = val
  914. else:
  915. if mustRehash(t.data.len, t.counter):
  916. var n: TIIPairSeq
  917. newSeq(n, t.data.len * GrowthFactor)
  918. for i in 0..high(n): n[i].key = InvalidKey
  919. for i in 0..high(t.data):
  920. if t.data[i].key != InvalidKey:
  921. iiTableRawInsert(n, t.data[i].key, t.data[i].val)
  922. swap(t.data, n)
  923. iiTableRawInsert(t.data, key, val)
  924. inc(t.counter)
  925. proc isAddrNode*(n: PNode): bool =
  926. case n.kind
  927. of nkAddr, nkHiddenAddr: true
  928. of nkCallKinds:
  929. if n[0].kind == nkSym and n[0].sym.magic == mAddr: true
  930. else: false
  931. else: false
  932. proc listSymbolNames*(symbols: openArray[PSym]): string =
  933. for sym in symbols:
  934. if result.len > 0:
  935. result.add ", "
  936. result.add sym.name.s
  937. proc isDiscriminantField*(n: PNode): bool =
  938. if n.kind == nkCheckedFieldExpr: sfDiscriminant in n[0][1].sym.flags
  939. elif n.kind == nkDotExpr: sfDiscriminant in n[1].sym.flags
  940. else: false