#
#
#           The Nim Compiler
#        (c) Copyright 2017 Contributors
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

import ast, renderer, strutils, msgs, options, idents, os, lineinfos,
  pathutils, nimblecmd

when false:
  const
    considerParentDirs = not defined(noParentProjects)
    considerNimbleDirs = not defined(noNimbleDirs)

  proc findInNimbleDir(pkg, subdir, dir: string): string =
    var best = ""
    var bestv = ""
    for k, p in os.walkDir(dir, relative=true):
      if k == pcDir and p.len > pkg.len+1 and
          p[pkg.len] == '-' and p.startsWith(pkg):
        let (_, a) = getPathVersion(p)
        if bestv.len == 0 or bestv < a:
          bestv = a
          best = dir / p

    if best.len > 0:
      var f: File
      if open(f, best / changeFileExt(pkg, ".nimble-link")):
        # the second line contains what we're interested in, see:
        # https://github.com/nim-lang/nimble#nimble-link
        var override = ""
        discard readLine(f, override)
        discard readLine(f, override)
        close(f)
        if not override.isAbsolute():
          best = best / override
        else:
          best = override
    let f = if subdir.len == 0: pkg else: subdir
    let res = addFileExt(best / f, "nim")
    if best.len > 0 and fileExists(res):
      result = res

when false:
  proc resolveDollar(project, source, pkg, subdir: string; info: TLineInfo): string =
    template attempt(a) =
      let x = addFileExt(a, "nim")
      if fileExists(x): return x

    case pkg
    of "stdlib":
      if subdir.len == 0:
        return options.libpath
      else:
        for candidate in stdlibDirs:
          attempt(options.libpath / candidate / subdir)
    of "root":
      let root = project.splitFile.dir
      if subdir.len == 0:
        return root
      else:
        attempt(root / subdir)
    else:
      when considerParentDirs:
        var p = parentDir(source.splitFile.dir)
        # support 'import $karax':
        let f = if subdir.len == 0: pkg else: subdir

        while p.len > 0:
          let dir = p / pkg
          if dirExists(dir):
            attempt(dir / f)
            # 2nd attempt: try to use 'karax/karax'
            attempt(dir / pkg / f)
            # 3rd attempt: try to use 'karax/src/karax'
            attempt(dir / "src" / f)
            attempt(dir / "src" / pkg / f)
          p = parentDir(p)

      when considerNimbleDirs:
        if not options.gNoNimblePath:
          var nimbleDir = getEnv("NIMBLE_DIR")
          if nimbleDir.len == 0: nimbleDir = getHomeDir() / ".nimble"
          result = findInNimbleDir(pkg, subdir, nimbleDir / "pkgs")
          if result.len > 0: return result
          when not defined(windows):
            result = findInNimbleDir(pkg, subdir, "/opt/nimble/pkgs")
            if result.len > 0: return result

  proc scriptableImport(pkg, sub: string; info: TLineInfo): string =
    result = resolveDollar(gProjectFull, info.toFullPath(), pkg, sub, info)
    if result.isNil: result = ""

  proc lookupPackage(pkg, subdir: PNode): string =
    let sub = if subdir != nil: renderTree(subdir, {renderNoComments}).replace(" ") else: pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
#
#
#           The Nim Compiler
#        (c) Copyright 2012 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

# Algorithms for the abstract syntax tree: hash tables, lists
# and sets of nodes are supported. Efficiency is important as
# the data structures here are used in various places of the compiler.

import
  ast, hashes, intsets, strutils, options, lineinfos, ropes, 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

when declared(echo):
  # these are for debugging only: They are not really deprecated, but I want
  # the warning so that release versions do not contain debugging statements:
  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)
    elif compiles(c.graph.config):
      debug(c.graph.config, x)
    else:
      error()

  template debug*(x: auto) {.deprecated.} =
    echo x

  template mdbg*: bool {.deprecated.} =
    when compiles(c.graph):
      c.module.fileIdx == c.graph.config.projectMainIdx
    elif compiles(c.module):
      c.module.fileIdx == c.config.projectMainIdx
    elif compiles(c.c.module):
      c.c.module.fileIdx == c.c.config.projectMainIdx
    elif compiles(m.c.module):
      m.c.module.fileIdx == m.c.config.projectMainIdx
    elif compiles(cl.c.module):
      cl.c.module.fileIdx == cl.c.config.projectMainIdx
    elif compiles(p):
      when compiles(p.lex):
        p.lex.fileIdx == p.lex.config.projectMainIdx
      else:
        p.module.module.fileIdx == p.config.projectMainIdx
    elif compiles(m.module.fileIdx):
      m.module.fileIdx == m.config.projectMainIdx
    elif compiles(L.fileIdx):
      L.fileIdx == L.config.projectMainIdx
    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
proc mustRehash*(length, counter: int): bool
proc nextTry*(h, maxHash: Hash): Hash {.inline.}

# ------------- table[int, int] ---------------------------------------------
const
  InvalidKey* = low(int)

type
  TIIPair*{.final.} = object
    key*, val*: int

  TIIPairSeq* = seq[TIIPair]
  TIITable*{.final.} = object # table[int, int]
    counter*: int
    data*: TIIPairSeq


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 =
  result = n
  while true:
    case result.kind
    of nkObjUpConv, nkObjDownConv, nkChckRange, nkChckRangeF, nkChckRange64,
       nkClosure:
      result = result.sons[0]
    of nkHiddenStdConv, nkHiddenSubConv, nkConv:
      result = result.sons[1]
    else: break

proc sameValue*(a, b: PNode): bool =
  result = false
  case a.kind
  of nkCharLit..nkUInt64Lit:
    if b.kind in {nkCharLit..nkUInt64Lit}: result = getInt(a) == getInt(b)
  of nkFloatLit..nkFloat64Lit:
    if b.kind in {nkFloatLit..nkFloat64Lit}: result = a.floatVal == b.floatVal
  of nkStrLit..nkTripleStrLit:
    if b.kind in {nkStrLit..nkTripleStrLit}: result = a.strVal == b.strVal
  else:
    # don't raise an internal error for 'nim check':
    #InternalError(a.info, "SameValue")
    discard

proc leValue*(a, b: PNode): bool =
  # a <= b?
  result = false
  case a.kind
  of nkCharLit..nkUInt64Lit:
    if b.kind in {nkCharLit..nkUInt64Lit}: result = getInt(a) <= getInt(b)
  of nkFloatLit..nkFloat64Lit:
    if b.kind in {nkFloatLit..nkFloat64Lit}: result = a.floatVal <= b.floatVal
  of nkStrLit..nkTripleStrLit:
    if b.kind in {nkStrLit..nkTripleStrLit}: result = a.strVal <= b.strVal
  else:
    # don't raise an internal error for 'nim check':
    #InternalError(a.info, "leValue")
    discard

proc weakLeValue*(a, b: PNode): TImplication =
  if a.kind notin nkLiterals or b.kind notin nkLiterals:
    result = impUnknown
  else:
    result = if leValue(a, b): impYes else: impNo

proc lookupInRecord(n: PNode, field: PIdent): PSym =
  result = nil
  case n.kind
  of nkRecList:
    for i in 0 ..< len(n):
      result = lookupInRecord(n.sons[i], field)
      if result != nil: return
  of nkRecCase:
    if (n.sons[0].kind != nkSym): return nil
    result = lookupInRecord(n.sons[0], field)
    if result != nil: return
    for i in 1 ..< len(n):
      case n.sons[i].kind
      of nkOfBranch, nkElse:
        result = lookupInRecord(lastSon(n.sons[i]), field)
        if result != nil: return
      else: return nil
  of nkSym:
    if n.sym.name.id == field.id: result = n.sym
  else: return nil

proc getModule*(s: PSym): PSym =
  result = s
  assert((result.kind == skModule) or (result.owner != result))
  while result != nil and result.kind != skModule: result = result.owner

proc getSymFromList*(list: PNode, ident: PIdent, start: int = 0): PSym =
  for i in start ..< len(list):
    if list.sons[i].kind == nkSym:
      result = list.sons[i].sym
      if result.name.id == ident.id: return
    else: return nil
  result = nil

proc sameIgnoreBacktickGensymInfo(a, b: string): bool =
  if a[0] != b[0]: return false
  var alen = a.len - 1
  while alen > 0 and a[alen] != '`': dec(alen)
  if alen <= 0: alen = a.len

  var i = 1
  var j = 1
  while true:
    while i < alen and a[i] == '_': inc i
    while j < b.len and b[j] == '_': inc j
    var aa = if i < alen: toLowerAscii(a[i]) else: '\0'
    var bb = if j < b.len: toLowerAscii(b[j]) else: '\0'
    if aa != bb: return false

    # the characters are identical:
    if i >= alen:
      # both cursors at the end:
      if j >= b.len: return true
      # not yet at the end of 'b':
      return false
    elif j >= b.len:
      return false
    inc i
    inc j

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),
  ##            if c.instLines: actual.info else: templ.info)
  for i in 1 ..< len(list):
    let it = list[i].sym
    if it.name.id == ident.id or
        sameIgnoreBacktickGensymInfo(it.name.s, ident.s): return it

proc hashNode(p: RootRef): Hash =
  result = hash(cast[pointer](p))

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:
      add(res, '\"')
      add(res, "\n")
      add(result, rope(res))
      res = "\""              # reset
    add(res, toYamlChar(s[i]))
  add(res, '\"')
  add(result, rope(res))

proc flagsToStr[T](flags: set[T]): Rope =
  if flags == {}:
    result = rope("[]")
  else:
    result = nil
    for x in items(flags):
      if result != nil: add(result, ", ")
      add(result, 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("{")
    addf(result, "$N$1\"kind\": $2", [istr, makeYamlString($n.kind)])
    addf(result, "$N$1\"name\": $2", [istr, makeYamlString(n.name.s)])
    addf(result, "$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
      addf(result, "$N$1\"info\": $2", [istr, lineInfoToStr(conf, n.info)])
    if card(n.flags) > 0:
      addf(result, "$N$1\"flags\": $2", [istr, flagsToStr(n.flags)])
    addf(result, "$N$1\"magic\": $2", [istr, makeYamlString($n.magic)])
    addf(result, "$N$1\"ast\": $2", [istr, ast])
    addf(result, "$N$1\"options\": $2", [istr, flagsToStr(n.options)])
    addf(result, "$N$1\"position\": $2", [istr, rope(n.position)])
    addf(result, "$N$1\"k\": $2", [istr, makeYamlString($n.loc.k)])
    addf(result, "$N$1\"storage\": $2", [istr, makeYamlString($n.loc.storage)])
    if card(n.loc.flags) > 0:
      addf(result, "$N$1\"flags\": $2", [istr, makeYamlString($n.loc.flags)])
    addf(result, "$N$1\"r\": $2", [istr, n.loc.r])
    addf(result, "$N$1\"lode\": $2", [istr, treeToYamlAux(conf, n.loc.lode, marker, indent + 2, maxRecDepth - 1)])
    addf(result, "$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 len(n) > 0:
      sonsRope = rope("[")
      for i in 0 ..< len(n):
        if i > 0: add(sonsRope, ",")
        addf(sonsRope, "$N$1$2", [rspaces(indent + 4), typeToYamlAux(conf, n.sons[i],
            marker, indent + 4, maxRecDepth - 1)])
      addf(sonsRope, "$N$1]", [rspaces(indent + 2)])
    else:
      sonsRope = rope("null")

    let istr = rspaces(indent + 2)
    result = rope("{")
    addf(result, "$N$1\"kind\": $2", [istr, makeYamlString($n.kind)])
    addf(result, "$N$1\"sym\": $2",  [istr, symToYamlAux(conf, n.sym, marker, indent + 2, maxRecDepth - 1)])
    addf(result, "$N$1\"n\": $2",     [istr, treeToYamlAux(conf, n.n, marker, indent + 2, maxRecDepth - 1)])
    if card(n.flags) > 0:
      addf(result, "$N$1\"flags\": $2", [istr, flagsToStr(n.flags)])
    addf(result, "$N$1\"callconv\": $2", [istr, makeYamlString(CallingConvToStr[n.callConv])])
    addf(result, "$N$1\"size\": $2", [istr, rope(n.size)])
    addf(result, "$N$1\"align\": $2", [istr, rope(n.align)])
    addf(result, "$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:
        addf(result, ",$N$1\"info\": $2", [istr, lineInfoToStr(conf, n.info)])
      case n.kind
      of nkCharLit..nkInt64Lit:
        addf(result, ",$N$1\"intVal\": $2", [istr, rope(n.intVal)])
      of nkFloatLit, nkFloat32Lit, nkFloat64Lit:
        addf(result, ",$N$1\"floatVal\": $2",
            [istr, rope(n.floatVal.toStrMaxPrecision)])
      of nkStrLit..nkTripleStrLit:
        addf(result, ",$N$1\"strVal\": $2", [istr, makeYamlString(n.strVal)])
      of nkSym:
        addf(result, ",$N$1\"sym\": $2",
             [istr, symToYamlAux(conf, n.sym, marker, indent + 2, maxRecDepth)])
      of nkIdent:
        if n.ident != nil:
          addf(result, ",$N$1\"ident\": $2", [istr, makeYamlString(n.ident.s)])
        else:
          addf(result, ",$N$1\"ident\": null", [istr])
      else:
        if len(n) > 0:
          addf(result, ",$N$1\"sons\": [", [istr])
          for i in 0 ..< len(n):
            if i > 0: add(result, ",")
            addf(result, "$N$1$2", [rspaces(indent + 4), treeToYamlAux(conf, n.sons[i],
                marker, indent + 4, maxRecDepth - 1)])
          addf(result, "$N$1]", [istr])
      addf(result, ",$N$1\"typ\": $2",
           [istr, typeToYamlAux(conf, n.typ, marker, indent + 2, maxRecDepth)])
    addf(result, "$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

const backrefStyle = "\e[90m"
const enumStyle = "\e[34m"
const numberStyle = "\e[33m"
const stringStyle = "\e[32m"
const resetStyle  = "\e[0m"

type
  DebugPrinter = object
    conf: ConfigRef
    visited: Table[pointer, int]
    renderSymType: bool
    indent: int
    currentLine: int
    firstItem: bool
    useColor: bool
    res: string

proc indentMore(this: var DebugPrinter) =
  this.indent += 2

proc indentLess(this: var DebugPrinter) =
  this.indent -= 2

proc newlineAndIndent(this: var DebugPrinter) =
  this.res.add "\n"
  this.currentLine += 1
  for i in 0 ..< this.indent:
    this.res.add ' '

proc openCurly(this: var DebugPrinter) =
  this.res.add "{"
  this.indentMore
  this.firstItem = true

proc closeCurly(this: var DebugPrinter) =
  this.indentLess
  this.newlineAndIndent
  this.res.add "}"

proc comma(this: var DebugPrinter) =
  this.res.add ", "

proc openBracket(this: var DebugPrinter) =
  this.res.add "["
  #this.indentMore

proc closeBracket(this: var DebugPrinter) =
  #this.indentLess
  this.res.add "]"

proc key(this: var DebugPrinter; key: string) =
  if not this.firstItem:
    this.res.add ","
  this.firstItem = false

  this.newlineAndIndent
  this.res.add "\""
  this.res.add key
  this.res.add "\": "

proc value(this: var DebugPrinter; value: string) =
  if this.useColor:
    this.res.add stringStyle
  this.res.add "\""
  this.res.add value
  this.res.add "\""
  if this.useColor:
    this.res.add resetStyle

proc value(this: var DebugPrinter; value: BiggestInt) =
  if this.useColor:
    this.res.add numberStyle
  this.res.addInt value
  if this.useColor:
    this.res.add resetStyle

proc value[T: enum](this: var DebugPrinter; value: T) =
  if this.useColor:
    this.res.add enumStyle
  this.res.add "\""
  this.res.add $value
  this.res.add "\""
  if this.useColor:
    this.res.add resetStyle

proc value[T: enum](this: var DebugPrinter; value: set[T]) =
  this.openBracket
  let high = card(value)-1
  var i = 0
  for v in value:
    this.value v
    if i != high:
      this.comma
    inc i
  this.closeBracket

template earlyExit(this: var DebugPrinter; n: PType | PNode | PSym) =
  if n == nil:
    this.res.add "null"
    return
  let index = this.visited.getOrDefault(cast[pointer](n), -1)
  if index < 0:
    this.visited[cast[pointer](n)] = this.currentLine
  else:
    if this.useColor:
      this.res.add backrefStyle
    this.res.add "<defined "
    this.res.addInt(this.currentLine - index)
    this.res.add " lines upwards>"
    if this.useColor:
      this.res.add resetStyle
    return

proc value(this: var DebugPrinter; value: PType)
proc value(this: var DebugPrinter; value: PNode)
proc value(this: var DebugPrinter; value: PSym) =
  earlyExit(this, value)

  this.openCurly
  this.key("kind")
  this.value(value.kind)
  this.key("name")
  this.value(value.name.s)
  this.key("id")
  this.value(value.id)
  if value.kind in {skField, skEnumField, skParam}:
    this.key("position")
    this.value(value.position)

  if card(value.flags) > 0:
    this.key("flags")
    this.value(value.flags)

  if this.renderSymType and value.typ != nil:
    this.key "typ"
    this.value(value.typ)

  this.closeCurly

proc value(this: var DebugPrinter; value: PType) =
  earlyExit(this, value)

  this.openCurly
  this.key "kind"
  this.value value.kind

  this.key "id"
  this.value value.id

  if value.sym != nil:
    this.key "sym"
    this.value value.sym
    #this.value value.sym.name.s

  if card(value.flags) > 0:
    this.key "flags"
    this.value value.flags

  if value.kind in IntegralTypes and value.n != nil:
    this.key "n"
    this.value value.n

  if len(value) > 0:
    this.key "sons"
    this.openBracket
    for i in 0 ..< len(value):
      this.value value.sons[i]
      if i != len(value) - 1:
        this.comma
    this.closeBracket

  if value.n != nil:
    this.key "n"
    this.value value.n

  this.closeCurly

proc value(this: var DebugPrinter; value: PNode) =
  earlyExit(this, value)

  this.openCurly
  this.key "kind"
  this.value  value.kind
  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:
    this.key "flags"
    this.value value.flags

  case value.kind
  of nkCharLit..nkUInt64Lit:
    this.key "intVal"
    this.value value.intVal
  of nkFloatLit, nkFloat32Lit, nkFloat64Lit:
    this.key "floatVal"
    this.value value.floatVal.toStrMaxPrecision
  of nkStrLit..nkTripleStrLit:
    this.key "strVal"
    this.value value.strVal
  of nkSym:
    this.key "sym"
    this.value value.sym
    #this.value value.sym.name.s
  of nkIdent:
    if value.ident != nil:
      this.key "ident"
      this.value value.ident.s
  else:
    if this.renderSymType and value.typ != nil:
      this.key "typ"
      this.value value.typ
    if len(value) > 0:
      this.key "sons"
      this.openBracket
      for i in 0 ..< len(value):
        this.value value.sons[i]
        if i != len(value) - 1:
          this.comma
      this.closeBracket

  this.closeCurly

when declared(echo):
  proc debug(n: PSym; conf: ConfigRef) =
    var this: DebugPrinter
    this.visited = initTable[pointer, int]()
    this.renderSymType = true
    this.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)
    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)
    this.value(n)
    echo($this.res)

proc nextTry(h, maxHash: Hash): Hash =
  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
  # random-number generation for proof).

proc objectSetContains*(t: TObjectSet, obj: RootRef): bool =
  # returns true whether n is in t
  var h: Hash = hashNode(obj) and high(t.data) # start with real hash value
  while t.data[h] != nil:
    if t.data[h] == obj:
      return true
    h = nextTry(h, high(t.data))
  result = false

proc objectSetRawInsert(data: var TObjectSeq, obj: RootRef) =
  var h: Hash = hashNode(obj) and high(data)
  while data[h] != nil:
    assert(data[h] != obj)
    h = nextTry(h, high(data))
  assert(data[h] == nil)
  data[h] = obj

proc objectSetEnlarge(t: var TObjectSet) =
  var n: TObjectSeq
  newSeq(n, len(t.data) * GrowthFactor)
  for i in 0 .. high(t.data):
    if t.data[i] != nil: objectSetRawInsert(n, t.data[i])
  swap(t.data, n)

proc objectSetIncl*(t: var TObjectSet, obj: RootRef) =
  if mustRehash(len(t.data), t.counter): objectSetEnlarge(t)
  objectSetRawInsert(t.data, obj)
  inc(t.counter)

proc objectSetContainsOrIncl*(t: var TObjectSet, obj: RootRef): bool =
  # returns true if obj is already in the string table:
  var h: Hash = hashNode(obj) and high(t.data)
  while true:
    var it = t.data[h]
    if it == nil: break
    if it == obj:
      return true             # found it
    h = nextTry(h, high(t.data))
  if mustRehash(len(t.data), t.counter):
    objectSetEnlarge(t)
    objectSetRawInsert(t.data, obj)
  else:
    assert(t.data[h] == nil)
    t.data[h] = obj
  inc(t.counter)
  result = false

proc strTableContains*(t: TStrTable, n: PSym): bool =
  var h: Hash = n.name.h and high(t.data) # start with real hash value
  while t.data[h] != nil:
    if (t.data[h] == n):
      return true
    h = nextTry(h, high(t.data))
  result = false

proc strTableRawInsert(data: var seq[PSym], n: PSym) =
  var h: Hash = n.name.h and high(data)
  while data[h] != nil:
    if data[h] == n:
      # allowed for 'export' feature:
      #InternalError(n.info, "StrTableRawInsert: " & n.name.s)
      return
    h = nextTry(h, high(data))
  assert(data[h] == nil)
  data[h] = n

proc symTabReplaceRaw(data: var seq[PSym], prevSym: PSym, newSym: PSym) =
  assert prevSym.name.h == newSym.name.h
  var h: Hash = prevSym.name.h and high(data)
  while data[h] != nil:
    if data[h] == prevSym:
      data[h] = newSym
      return
    h = nextTry(h, high(data))
  assert false

proc symTabReplace*(t: var TStrTable, prevSym: PSym, newSym: PSym) =
  symTabReplaceRaw(t.data, prevSym, newSym)

proc strTableEnlarge(t: var TStrTable) =
  var n: seq[PSym]
  newSeq(n, len(t.data) * GrowthFactor)
  for i in 0 .. high(t.data):
    if t.data[i] != nil: strTableRawInsert(n, t.data[i])
  swap(t.data, n)

proc strTableAdd*(t: var TStrTable, n: PSym) =
  if mustRehash(len(t.data), t.counter): strTableEnlarge(t)
  strTableRawInsert(t.data, n)
  inc(t.counter)

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!
  assert n.name != nil
  var h: Hash = n.name.h and high(t.data)
  var replaceSlot = -1
  while true:
    var it = t.data[h]
    if it == nil: break
    # Semantic checking can happen multiple times thanks to templates
    # and overloading: (var x=@[]; x).mapIt(it).
    # So it is possible the very same sym is added multiple
    # times to the symbol table which we allow here with the 'it == n' check.
    if it.name.id == n.name.id:
      if it == n: return nil
      replaceSlot = h
    h = nextTry(h, high(t.data))
  if replaceSlot >= 0:
    if not onConflictKeepOld:
      t.data[replaceSlot] = n # overwrite it with newer definition!
    return t.data[replaceSlot] # found it
  elif mustRehash(len(t.data), t.counter):
    strTableEnlarge(t)
    strTableRawInsert(t.data, n)
  else:
    assert(t.data[h] == nil)
    t.data[h] = n
  inc(t.counter)
  result = nil

proc strTableIncl*(t: var TStrTable, n: PSym;
                   onConflictKeepOld = false): bool {.discardable.} =
  result = strTableInclReportConflict(t, n, onConflictKeepOld) != nil

proc strTableGet*(t: TStrTable, name: PIdent): PSym =
  var h: Hash = name.h and high(t.data)
  while true:
    result = t.data[h]
    if result == nil: break
    if result.name.id == name.id: break
    h = nextTry(h, high(t.data))


type
  TIdentIter* = object # iterator over all syms with same identifier
    h*: Hash           # current hash
    name*: PIdent

proc nextIdentIter*(ti: var TIdentIter, tab: TStrTable): PSym =
  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
    h = nextTry(h, high(tab.data))
    if h == start:
      result = nil
      break
    result = tab.data[h]
  ti.h = nextTry(h, high(tab.data))

proc initIdentIter*(ti: var TIdentIter, tab: TStrTable, s: PIdent): PSym =
  ti.h = s.h
  ti.name = s
  if tab.counter == 0: result = nil
  else: result = nextIdentIter(ti, tab)

proc nextIdentExcluding*(ti: var TIdentIter, tab: TStrTable,
                         excluding: IntSet): PSym =
  var h: Hash = ti.h and high(tab.data)
  var start = h
  result = tab.data[h]
  while result != nil:
    if result.name.id == ti.name.id and not contains(excluding, result.id):
      break
    h = nextTry(h, high(tab.data))
    if h == start:
      result = nil
      break
    result = tab.data[h]
  ti.h = nextTry(h, high(tab.data))
  if result != nil and contains(excluding, result.id): result = nil

proc firstIdentExcluding*(ti: var TIdentIter, tab: TStrTable, s: PIdent,
                          excluding: IntSet): PSym =
  ti.h = s.h
  ti.name = s
  if tab.counter == 0: result = nil
  else: result = nextIdentExcluding(ti, tab, excluding)

type
  TTabIter* = object
    h: Hash

proc nextIter*(ti: var TTabIter, tab: TStrTable): PSym =
  # usage:
  # var
  #   i: TTabIter
  #   s: PSym
  # s = InitTabIter(i, table)
  # while s != nil:
  #   ...
  #   s = NextIter(i, table)
  #
  result = nil
  while (ti.h <= high(tab.data)):
    result = tab.data[ti.h]
    inc(ti.h)                 # ... and increment by one always
    if result != nil: break

proc initTabIter*(ti: var TTabIter, tab: TStrTable): PSym =
  ti.h = 0
  if tab.counter == 0:
    result = nil
  else:
    result = nextIter(ti, tab)

iterator items*(tab: TStrTable): PSym =
  var it: 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(len(t.data), t.counter):
      newSeq(n, len(t.data) * 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(len(t.data), t.counter):
      var n: TIdNodePairSeq
      newSeq(n, len(t.data) * 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)
  for i in 0 ..< StartSize: x.data[i].key = InvalidKey

proc iiTableRawGet(t: TIITable, key: int): int =
  var h: Hash
  h = key and high(t.data)    # start with real hash value
  while t.data[h].key != InvalidKey:
    if t.data[h].key == key: return h
    h = nextTry(h, high(t.data))
  result = -1

proc iiTableGet(t: TIITable, key: int): int =
  var index = iiTableRawGet(t, key)
  if index >= 0: result = t.data[index].val
  else: result = InvalidKey

proc iiTableRawInsert(data: var TIIPairSeq, key, val: int) =
  var h: Hash
  h = key and high(data)
  while data[h].key != InvalidKey:
    assert(data[h].key != key)
    h = nextTry(h, high(data))
  assert(data[h].key == InvalidKey)
  data[h].key = key
  data[h].val = val

proc iiTablePut(t: var TIITable, key, val: int) =
  var index = iiTableRawGet(t, key)
  if index >= 0:
    assert(t.data[index].key != InvalidKey)
    t.data[index].val = val
  else:
    if mustRehash(len(t.data), t.counter):
      var n: TIIPairSeq
      newSeq(n, len(t.data) * GrowthFactor)
      for i in 0 .. high(n): n[i].key = InvalidKey
      for i in 0 .. high(t.data):
        if t.data[i].key != InvalidKey:
          iiTableRawInsert(n, t.data[i].key, t.data[i].val)
      swap(t.data, n)
    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