diff options
Diffstat (limited to 'compiler/astalgo.nim')
| -rw-r--r-- | compiler/astalgo.nim | 419 |
1 files changed, 68 insertions, 351 deletions
diff --git a/compiler/astalgo.nim b/compiler/astalgo.nim index 5e23d2284..7a9892f78 100644 --- a/compiler/astalgo.nim +++ b/compiler/astalgo.nim @@ -12,18 +12,18 @@ # the data structures here are used in various places of the compiler. import - ast, hashes, intsets, strutils, options, lineinfos, ropes, idents, rodutils, + ast, astyaml, options, lineinfos, idents, rodutils, msgs -proc hashNode*(p: RootRef): Hash -proc treeToYaml*(conf: ConfigRef; n: PNode, indent: int = 0, maxRecDepth: int = - 1): Rope - # Convert a tree into its YAML representation; this is used by the - # YAML code generator and it is invaluable for debugging purposes. - # If maxRecDepht <> -1 then it won't print the whole graph. -proc typeToYaml*(conf: ConfigRef; n: PType, indent: int = 0, maxRecDepth: int = - 1): Rope -proc symToYaml*(conf: ConfigRef; n: PSym, indent: int = 0, maxRecDepth: int = - 1): Rope -proc lineInfoToStr*(conf: ConfigRef; info: TLineInfo): Rope +import std/[hashes, intsets] +import std/strutils except addf + +export astyaml.treeToYaml, astyaml.typeToYaml, astyaml.symToYaml, astyaml.lineInfoToStr + +when defined(nimPreviewSlimSystem): + import std/assertions +proc hashNode*(p: RootRef): Hash # these are for debugging only: They are not really deprecated, but I want # the warning so that release versions do not contain debugging statements: @@ -31,15 +31,6 @@ proc debug*(n: PSym; conf: ConfigRef = nil) {.exportc: "debugSym", deprecated.} proc debug*(n: PType; conf: ConfigRef = nil) {.exportc: "debugType", deprecated.} proc debug*(n: PNode; conf: ConfigRef = nil) {.exportc: "debugNode", deprecated.} -proc typekinds*(t: PType) {.deprecated.} = - var t = t - var s = "" - while t != nil and t.len > 0: - s.add $t.kind - s.add " " - t = t.lastSon - echo s - template debug*(x: PSym|PType|PNode) {.deprecated.} = when compiles(c.config): debug(c.config, x) @@ -74,16 +65,6 @@ template mdbg*: bool {.deprecated.} = else: error() -# --------------------------- ident tables ---------------------------------- -proc idTableGet*(t: TIdTable, key: PIdObj): RootRef -proc idTableGet*(t: TIdTable, key: int): RootRef -proc idTablePut*(t: var TIdTable, key: PIdObj, val: RootRef) -proc idTableHasObjectAsKey*(t: TIdTable, key: PIdObj): bool - # checks if `t` contains the `key` (compared by the pointer value, not only - # `key`'s id) -proc idNodeTableGet*(t: TIdNodeTable, key: PIdObj): PNode -proc idNodeTablePut*(t: var TIdNodeTable, key: PIdObj, val: PNode) - # --------------------------------------------------------------------------- proc lookupInRecord*(n: PNode, field: PIdent): PSym @@ -104,20 +85,20 @@ type data*: TIIPairSeq -proc initIiTable*(x: var TIITable) +proc initIITable*(x: var TIITable) proc iiTableGet*(t: TIITable, key: int): int proc iiTablePut*(t: var TIITable, key, val: int) # implementation -proc skipConvAndClosure*(n: PNode): PNode = +proc skipConvCastAndClosure*(n: PNode): PNode = result = n while true: case result.kind of nkObjUpConv, nkObjDownConv, nkChckRange, nkChckRangeF, nkChckRange64, nkClosure: result = result[0] - of nkHiddenStdConv, nkHiddenSubConv, nkConv: + of nkHiddenStdConv, nkHiddenSubConv, nkConv, nkCast: result = result[1] else: break @@ -192,6 +173,7 @@ proc getSymFromList*(list: PNode, ident: PIdent, start: int = 0): PSym = result = nil proc sameIgnoreBacktickGensymInfo(a, b: string): bool = + result = false if a[0] != b[0]: return false var alen = a.len - 1 while alen > 0 and a[alen] != '`': dec(alen) @@ -221,11 +203,11 @@ proc getNamedParamFromList*(list: PNode, ident: PIdent): PSym = ## Named parameters are special because a named parameter can be ## gensym'ed and then they have '\`<number>' suffix that we need to ## ignore, see compiler / evaltempl.nim, snippet: - ## - ##..code-block:: nim - ## - ## result.add newIdentNode(getIdent(c.ic, x.name.s & "\`gensym" & $x.id), + ## ```nim + ## result.add newIdentNode(getIdent(c.ic, x.name.s & "\`gensym" & $x.id), ## if c.instLines: actual.info else: templ.info) + ## ``` + result = nil for i in 1..<list.len: let it = list[i].sym if it.name.id == ident.id or @@ -238,169 +220,7 @@ proc mustRehash(length, counter: int): bool = assert(length > counter) result = (length * 2 < counter * 3) or (length - counter < 4) -proc rspaces(x: int): Rope = - # returns x spaces - result = rope(spaces(x)) - -proc toYamlChar(c: char): string = - case c - of '\0'..'\x1F', '\x7F'..'\xFF': result = "\\u" & strutils.toHex(ord(c), 4) - of '\'', '\"', '\\': result = '\\' & c - else: result = $c - -proc makeYamlString*(s: string): Rope = - # We have to split long strings into many ropes. Otherwise - # this could trigger InternalError(111). See the ropes module for - # further information. - const MaxLineLength = 64 - result = nil - var res = "\"" - for i in 0..<s.len: - if (i + 1) mod MaxLineLength == 0: - res.add('\"') - res.add("\n") - result.add(rope(res)) - res = "\"" # reset - res.add(toYamlChar(s[i])) - res.add('\"') - result.add(rope(res)) - -proc flagsToStr[T](flags: set[T]): Rope = - if flags == {}: - result = rope("[]") - else: - result = nil - for x in items(flags): - if result != nil: result.add(", ") - result.add(makeYamlString($x)) - result = "[" & result & "]" - -proc lineInfoToStr(conf: ConfigRef; info: TLineInfo): Rope = - result = "[$1, $2, $3]" % [makeYamlString(toFilename(conf, info)), - rope(toLinenumber(info)), - rope(toColumn(info))] - -proc treeToYamlAux(conf: ConfigRef; n: PNode, marker: var IntSet, - indent, maxRecDepth: int): Rope -proc symToYamlAux(conf: ConfigRef; n: PSym, marker: var IntSet, - indent, maxRecDepth: int): Rope -proc typeToYamlAux(conf: ConfigRef; n: PType, marker: var IntSet, - indent, maxRecDepth: int): Rope - -proc symToYamlAux(conf: ConfigRef; n: PSym, marker: var IntSet, indent: int, - maxRecDepth: int): Rope = - if n == nil: - result = rope("null") - elif containsOrIncl(marker, n.id): - result = "\"$1\"" % [rope(n.name.s)] - else: - var ast = treeToYamlAux(conf, n.ast, marker, indent + 2, maxRecDepth - 1) - #rope("typ"), typeToYamlAux(conf, n.typ, marker, - # indent + 2, maxRecDepth - 1), - let istr = rspaces(indent + 2) - result = rope("{") - result.addf("$N$1\"kind\": $2", [istr, makeYamlString($n.kind)]) - result.addf("$N$1\"name\": $2", [istr, makeYamlString(n.name.s)]) - result.addf("$N$1\"typ\": $2", [istr, typeToYamlAux(conf, n.typ, marker, indent + 2, maxRecDepth - 1)]) - if conf != nil: - # if we don't pass the config, we probably don't care about the line info - result.addf("$N$1\"info\": $2", [istr, lineInfoToStr(conf, n.info)]) - if card(n.flags) > 0: - result.addf("$N$1\"flags\": $2", [istr, flagsToStr(n.flags)]) - result.addf("$N$1\"magic\": $2", [istr, makeYamlString($n.magic)]) - result.addf("$N$1\"ast\": $2", [istr, ast]) - result.addf("$N$1\"options\": $2", [istr, flagsToStr(n.options)]) - result.addf("$N$1\"position\": $2", [istr, rope(n.position)]) - result.addf("$N$1\"k\": $2", [istr, makeYamlString($n.loc.k)]) - result.addf("$N$1\"storage\": $2", [istr, makeYamlString($n.loc.storage)]) - if card(n.loc.flags) > 0: - result.addf("$N$1\"flags\": $2", [istr, makeYamlString($n.loc.flags)]) - result.addf("$N$1\"r\": $2", [istr, n.loc.r]) - result.addf("$N$1\"lode\": $2", [istr, treeToYamlAux(conf, n.loc.lode, marker, indent + 2, maxRecDepth - 1)]) - result.addf("$N$1}", [rspaces(indent)]) - -proc typeToYamlAux(conf: ConfigRef; n: PType, marker: var IntSet, indent: int, - maxRecDepth: int): Rope = - var sonsRope: Rope - if n == nil: - sonsRope = rope("null") - elif containsOrIncl(marker, n.id): - sonsRope = "\"$1 @$2\"" % [rope($n.kind), rope( - strutils.toHex(cast[ByteAddress](n), sizeof(n) * 2))] - else: - if n.len > 0: - sonsRope = rope("[") - for i in 0..<n.len: - if i > 0: sonsRope.add(",") - sonsRope.addf("$N$1$2", [rspaces(indent + 4), typeToYamlAux(conf, n[i], - marker, indent + 4, maxRecDepth - 1)]) - sonsRope.addf("$N$1]", [rspaces(indent + 2)]) - else: - sonsRope = rope("null") - - let istr = rspaces(indent + 2) - result = rope("{") - result.addf("$N$1\"kind\": $2", [istr, makeYamlString($n.kind)]) - result.addf("$N$1\"sym\": $2", [istr, symToYamlAux(conf, n.sym, marker, indent + 2, maxRecDepth - 1)]) - result.addf("$N$1\"n\": $2", [istr, treeToYamlAux(conf, n.n, marker, indent + 2, maxRecDepth - 1)]) - if card(n.flags) > 0: - result.addf("$N$1\"flags\": $2", [istr, flagsToStr(n.flags)]) - result.addf("$N$1\"callconv\": $2", [istr, makeYamlString(CallingConvToStr[n.callConv])]) - result.addf("$N$1\"size\": $2", [istr, rope(n.size)]) - result.addf("$N$1\"align\": $2", [istr, rope(n.align)]) - result.addf("$N$1\"sons\": $2", [istr, sonsRope]) - -proc treeToYamlAux(conf: ConfigRef; n: PNode, marker: var IntSet, indent: int, - maxRecDepth: int): Rope = - if n == nil: - result = rope("null") - else: - var istr = rspaces(indent + 2) - result = "{$N$1\"kind\": $2" % [istr, makeYamlString($n.kind)] - if maxRecDepth != 0: - if conf != nil: - result.addf(",$N$1\"info\": $2", [istr, lineInfoToStr(conf, n.info)]) - case n.kind - of nkCharLit..nkInt64Lit: - result.addf(",$N$1\"intVal\": $2", [istr, rope(n.intVal)]) - of nkFloatLit, nkFloat32Lit, nkFloat64Lit: - result.addf(",$N$1\"floatVal\": $2", - [istr, rope(n.floatVal.toStrMaxPrecision)]) - of nkStrLit..nkTripleStrLit: - result.addf(",$N$1\"strVal\": $2", [istr, makeYamlString(n.strVal)]) - of nkSym: - result.addf(",$N$1\"sym\": $2", - [istr, symToYamlAux(conf, n.sym, marker, indent + 2, maxRecDepth)]) - of nkIdent: - if n.ident != nil: - result.addf(",$N$1\"ident\": $2", [istr, makeYamlString(n.ident.s)]) - else: - result.addf(",$N$1\"ident\": null", [istr]) - else: - if n.len > 0: - result.addf(",$N$1\"sons\": [", [istr]) - for i in 0..<n.len: - if i > 0: result.add(",") - result.addf("$N$1$2", [rspaces(indent + 4), treeToYamlAux(conf, n[i], - marker, indent + 4, maxRecDepth - 1)]) - result.addf("$N$1]", [istr]) - result.addf(",$N$1\"typ\": $2", - [istr, typeToYamlAux(conf, n.typ, marker, indent + 2, maxRecDepth)]) - result.addf("$N$1}", [rspaces(indent)]) - -proc treeToYaml(conf: ConfigRef; n: PNode, indent: int = 0, maxRecDepth: int = - 1): Rope = - var marker = initIntSet() - result = treeToYamlAux(conf, n, marker, indent, maxRecDepth) - -proc typeToYaml(conf: ConfigRef; n: PType, indent: int = 0, maxRecDepth: int = - 1): Rope = - var marker = initIntSet() - result = typeToYamlAux(conf, n, marker, indent, maxRecDepth) - -proc symToYaml(conf: ConfigRef; n: PSym, indent: int = 0, maxRecDepth: int = - 1): Rope = - var marker = initIntSet() - result = symToYamlAux(conf, n, marker, indent, maxRecDepth) - -import tables +import std/tables const backrefStyle = "\e[90m" const enumStyle = "\e[34m" @@ -564,14 +384,12 @@ proc value(this: var DebugPrinter; value: PType) = this.key "n" this.value value.n - if value.len > 0: - this.key "sons" - this.openBracket - for i in 0..<value.len: - this.value value[i] - if i != value.len - 1: - this.comma - this.closeBracket + this.key "sons" + this.openBracket + for i, a in value.ikids: + if i > 0: this.comma + this.value a + this.closeBracket if value.n != nil: this.key "n" @@ -585,16 +403,26 @@ proc value(this: var DebugPrinter; value: PNode) = this.openCurly this.key "kind" this.value value.kind + if value.comment.len > 0: + this.key "comment" + this.value value.comment when defined(useNodeIds): this.key "id" this.value value.id if this.conf != nil: this.key "info" this.value $lineInfoToStr(this.conf, value.info) - if card(value.flags) > 0: + if value.flags != {}: this.key "flags" this.value value.flags + if value.typ != nil: + this.key "typ" + this.value value.typ.kind + else: + this.key "typ" + this.value "nil" + case value.kind of nkCharLit..nkUInt64Lit: this.key "intVal" @@ -630,30 +458,33 @@ proc value(this: var DebugPrinter; value: PNode) = proc debug(n: PSym; conf: ConfigRef) = - var this: DebugPrinter - this.visited = initTable[pointer, int]() - this.renderSymType = true - this.useColor = not defined(windows) + var this = DebugPrinter( + visited: initTable[pointer, int](), + renderSymType: true, + useColor: not defined(windows) + ) this.value(n) echo($this.res) proc debug(n: PType; conf: ConfigRef) = - var this: DebugPrinter - this.visited = initTable[pointer, int]() - this.renderSymType = true - this.useColor = not defined(windows) + var this = DebugPrinter( + visited: initTable[pointer, int](), + renderSymType: true, + useColor: not defined(windows) + ) this.value(n) echo($this.res) proc debug(n: PNode; conf: ConfigRef) = - var this: DebugPrinter - this.visited = initTable[pointer, int]() - #this.renderSymType = true - this.useColor = not defined(windows) + var this = DebugPrinter( + visited: initTable[pointer, int](), + renderSymType: false, + useColor: not defined(windows) + ) this.value(n) echo($this.res) -proc nextTry(h, maxHash: Hash): Hash = +proc nextTry(h, maxHash: Hash): Hash {.inline.} = result = ((5 * h) + 1) and maxHash # For any initial h in range(maxHash), repeating that maxHash times # generates each int in range(maxHash) exactly once (see any text on @@ -752,9 +583,9 @@ proc strTableAdd*(t: var TStrTable, n: PSym) = proc strTableInclReportConflict*(t: var TStrTable, n: PSym; onConflictKeepOld = false): PSym = - # returns true if n is already in the string table: - # It is essential that `n` is written nevertheless! - # This way the newest redefinition is picked by the semantic analyses! + # if `t` has a conflicting symbol (same identifier as `n`), return it + # otherwise return `nil`. Incl `n` to `t` unless `onConflictKeepOld = true` + # and a conflict was found. assert n.name != nil var h: Hash = n.name.h and high(t.data) var replaceSlot = -1 @@ -770,9 +601,10 @@ proc strTableInclReportConflict*(t: var TStrTable, n: PSym; replaceSlot = h h = nextTry(h, high(t.data)) if replaceSlot >= 0: + result = t.data[replaceSlot] # found it if not onConflictKeepOld: t.data[replaceSlot] = n # overwrite it with newer definition! - return t.data[replaceSlot] # found it + return result # but return the old one elif mustRehash(t.data.len, t.counter): strTableEnlarge(t) strTableRawInsert(t.data, n) @@ -801,16 +633,21 @@ type name*: PIdent proc nextIdentIter*(ti: var TIdentIter, tab: TStrTable): PSym = + # hot spots var h = ti.h and high(tab.data) var start = h - result = tab.data[h] - while result != nil: - if result.name.id == ti.name.id: break + var p {.cursor.} = tab.data[h] + while p != nil: + if p.name.id == ti.name.id: break h = nextTry(h, high(tab.data)) if h == start: - result = nil + p = nil break - result = tab.data[h] + p = tab.data[h] + if p != nil: + result = p # increase the count + else: + result = nil ti.h = nextTry(h, high(tab.data)) proc initIdentIter*(ti: var TIdentIter, tab: TStrTable, s: PIdent): PSym = @@ -870,125 +707,12 @@ proc initTabIter*(ti: var TTabIter, tab: TStrTable): PSym = result = nextIter(ti, tab) iterator items*(tab: TStrTable): PSym = - var it: TTabIter + var it: TTabIter = default(TTabIter) var s = initTabIter(it, tab) while s != nil: yield s s = nextIter(it, tab) -proc hasEmptySlot(data: TIdPairSeq): bool = - for h in 0..high(data): - if data[h].key == nil: - return true - result = false - -proc idTableRawGet(t: TIdTable, key: int): int = - var h: Hash - h = key and high(t.data) # start with real hash value - while t.data[h].key != nil: - if t.data[h].key.id == key: - return h - h = nextTry(h, high(t.data)) - result = - 1 - -proc idTableHasObjectAsKey(t: TIdTable, key: PIdObj): bool = - var index = idTableRawGet(t, key.id) - if index >= 0: result = t.data[index].key == key - else: result = false - -proc idTableGet(t: TIdTable, key: PIdObj): RootRef = - var index = idTableRawGet(t, key.id) - if index >= 0: result = t.data[index].val - else: result = nil - -proc idTableGet(t: TIdTable, key: int): RootRef = - var index = idTableRawGet(t, key) - if index >= 0: result = t.data[index].val - else: result = nil - -iterator pairs*(t: TIdTable): tuple[key: int, value: RootRef] = - for i in 0..high(t.data): - if t.data[i].key != nil: - yield (t.data[i].key.id, t.data[i].val) - -proc idTableRawInsert(data: var TIdPairSeq, key: PIdObj, val: RootRef) = - var h: Hash - h = key.id and high(data) - while data[h].key != nil: - assert(data[h].key.id != key.id) - h = nextTry(h, high(data)) - assert(data[h].key == nil) - data[h].key = key - data[h].val = val - -proc idTablePut(t: var TIdTable, key: PIdObj, val: RootRef) = - var - index: int - n: TIdPairSeq - index = idTableRawGet(t, key.id) - if index >= 0: - assert(t.data[index].key != nil) - t.data[index].val = val - else: - if mustRehash(t.data.len, t.counter): - newSeq(n, t.data.len * GrowthFactor) - for i in 0..high(t.data): - if t.data[i].key != nil: - idTableRawInsert(n, t.data[i].key, t.data[i].val) - assert(hasEmptySlot(n)) - swap(t.data, n) - idTableRawInsert(t.data, key, val) - inc(t.counter) - -iterator idTablePairs*(t: TIdTable): tuple[key: PIdObj, val: RootRef] = - for i in 0..high(t.data): - if not isNil(t.data[i].key): yield (t.data[i].key, t.data[i].val) - -proc idNodeTableRawGet(t: TIdNodeTable, key: PIdObj): int = - var h: Hash - h = key.id and high(t.data) # start with real hash value - while t.data[h].key != nil: - if t.data[h].key.id == key.id: - return h - h = nextTry(h, high(t.data)) - result = - 1 - -proc idNodeTableGet(t: TIdNodeTable, key: PIdObj): PNode = - var index: int - index = idNodeTableRawGet(t, key) - if index >= 0: result = t.data[index].val - else: result = nil - -proc idNodeTableRawInsert(data: var TIdNodePairSeq, key: PIdObj, val: PNode) = - var h: Hash - h = key.id and high(data) - while data[h].key != nil: - assert(data[h].key.id != key.id) - h = nextTry(h, high(data)) - assert(data[h].key == nil) - data[h].key = key - data[h].val = val - -proc idNodeTablePut(t: var TIdNodeTable, key: PIdObj, val: PNode) = - var index = idNodeTableRawGet(t, key) - if index >= 0: - assert(t.data[index].key != nil) - t.data[index].val = val - else: - if mustRehash(t.data.len, t.counter): - var n: TIdNodePairSeq - newSeq(n, t.data.len * GrowthFactor) - for i in 0..high(t.data): - if t.data[i].key != nil: - idNodeTableRawInsert(n, t.data[i].key, t.data[i].val) - swap(t.data, n) - idNodeTableRawInsert(t.data, key, val) - inc(t.counter) - -iterator pairs*(t: TIdNodeTable): tuple[key: PIdObj, val: PNode] = - for i in 0..high(t.data): - if not isNil(t.data[i].key): yield (t.data[i].key, t.data[i].val) - proc initIITable(x: var TIITable) = x.counter = 0 newSeq(x.data, StartSize) @@ -1034,15 +758,8 @@ proc iiTablePut(t: var TIITable, key, val: int) = iiTableRawInsert(t.data, key, val) inc(t.counter) -proc isAddrNode*(n: PNode): bool = - case n.kind - of nkAddr, nkHiddenAddr: true - of nkCallKinds: - if n[0].kind == nkSym and n[0].sym.magic == mAddr: true - else: false - else: false - proc listSymbolNames*(symbols: openArray[PSym]): string = + result = "" for sym in symbols: if result.len > 0: result.add ", " |