Nim/compiler/reorder.nim

import
  intsets, ast, idents, algorithm, renderer, strutils,
  msgs, modulegraphs, syntaxes, options, modulepaths,
  lineinfos

type
  DepN = ref object
    pnode: PNode
    id, idx, lowLink: int
    onStack: bool
    kids: seq[DepN]
    hAQ, hIS, hB, hCmd: int
    when defined(debugReorder):
      expls: seq[string]
  DepG = seq[DepN]

when defined(debugReorder):
  var idNames = newTable[int, string]()

proc newDepN(id: int, pnode: PNode): DepN =
  new(result)
  result.id = id
  result.pnode = pnode
  result.idx = -1
  result.lowLink = -1
  result.onStack = false
  result.kids = @[]
  result.hAQ = -1
  result.hIS = -1
  result.hB = -1
  result.hCmd = -1
  when defined(debugReorder):
    result.expls = @[]

proc accQuoted(cache: IdentCache; n: PNode): PIdent =
  var id = ""
  for i in 0..<n.len:
    let ident = n[i].getPIdent
    if ident != nil: id.add(ident.s)
  result = getIdent(cache, id)

proc addDecl(cache: IdentCache; n: PNode; declares: var IntSet) =
  case n.kind
  of nkPostfix: addDecl(cache, n[1], declares)
  of nkPragmaExpr: addDecl(cache, n[0], declares)
  of nkIdent:
    declares.incl n.ident.id
    when defined(debugReorder):
      idNames[n.ident.id] = n.ident.s
  of nkSym:
    declares.incl n.sym.name.id
    when defined(debugReorder):
      idNames[n.sym.name.id] = n.sym.name.s
  of nkAccQuoted:
    let a = accQuoted(cache, n)
    declares.incl a.id
    when defined(debugReorder):
      idNames[a.id] = a.s
  of nkEnumFieldDef:
    addDecl(cache, n[0], declares)
  else: discard

proc computeDeps(cache: IdentCache; n: PNode, declares, uses: var IntSet; topLevel: bool) =
  template deps(n) = computeDeps(cache, n, declares, uses, false)
  template decl(n) =
    if topLevel: addDecl(cache, n, declares)
  case n.kind
  of procDefs, nkMacroDef, nkTemplateDef:
    decl(n[0])
    for i in 1..bodyPos: deps(n[i])
  of nkLetSection, nkVarSection, nkUsingStmt:
    for a in n:
      if a.kind in {nkIdentDefs, nkVarTuple}:
        for j in 0..<a.len-2: decl(a[j])
        for j in a.len-2..<a.len: deps(a[j])
  of nkConstSection, nkTypeSection:
    for a in n:
      if a.len >= 3:
        decl(a[0])
        for i in 1..<a.len:
          if a[i].kind == nkEnumTy:
            # declare enum members
            for b in a[i]:
              decl(b)
          else:
            deps(a[i])
  of nkIdentDefs:
    for i in 1..<n.len: # avoid members identifiers in object definition
      deps(n[i])
  of nkIdent: uses.incl n.ident.id
  of nkSym: uses.incl n.sym.name.id
  of nkAccQuoted: uses.incl accQuoted(cache, n).id
  of nkOpenSymChoice, nkClosedSymChoice:
    uses.incl n[0].sym.name.id
  of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse, nkStaticStmt:
    for i in 0..<n.len: computeDeps(cache, n[i], declares, uses, topLevel)
  of nkPragma:
    let a = n[0]
    if a.kind == nkExprColonExpr and a[0].kind == nkIdent and a[0].ident.s == "pragma":
      # user defined pragma
      decl(a[1])
    else:
      for i in 0..<n.safeLen: deps(n[i])
  of nkMixinStmt, nkBindStmt: discard
  else:
    # XXX: for callables, this technically adds the return type dep before args
    for i in 0..<n.safeLen: deps(n[i])

proc hasIncludes(n:PNode): bool =
  for a in n:
    if a.kind == nkIncludeStmt:
      return true

proc includeModule*(graph: ModuleGraph; s: PSym, fileIdx: FileIndex): PNode =
  result = syntaxes.parseFile(fileIdx, graph.cache, graph.config)
  graph.addDep(s, fileIdx)
  graph.addIncludeDep(FileIndex s.position, fileIdx)

proc expandIncludes(graph: ModuleGraph, module: PSym, n: PNode,
                    modulePath: string, includedFiles: var IntSet): PNode =
  # Parses includes and injects them in the current tree
  if not n.hasIncludes:
    return n
  result = newNodeI(nkStmtList, n.info)
  for a in n:
    if a.kind == nkIncludeStmt:
      for i in 0..<a.len:
        var f = checkModuleName(graph.config, a[i])
        if f != InvalidFileIdx:
          if containsOrIncl(includedFiles, f.int):
            localError(graph.config, a.info, "recursive dependency: '$1'" %
              toMsgFilename(graph.config, f))
          else:
            let nn = includeModule(graph, module, f)
            let nnn = expandIncludes(graph, module, nn, modulePath,
                                      includedFiles)
            excl(includedFiles, f.int)
            for b in nnn:
              result.add b
    else:
      result.add a

proc splitSections(n: PNode): PNode =
  # Split typeSections and ConstSections into
  # sections that contain only one definition
  assert n.kind == nkStmtList
  result = newNodeI(nkStmtList, n.info)
  for a in n:
    if a.kind in {nkTypeSection, nkConstSection} and a.len > 1:
      for b in a:
        var s = newNode(a.kind)
        s.info = b.info
        s.add b
        result.add s
    else:
      result.add a

proc haveSameKind(dns: seq[DepN]): bool =
  # Check if all the nodes in a strongly connected
  # component have the same kind
  result = true
  let kind = dns[0].pnode.kind
  for dn in dns:
    if dn.pnode.kind != kind:
      return false

proc mergeSections(conf: ConfigRef; comps: seq[seq[DepN]], res: PNode) =
  # Merges typeSections and ConstSections when they form
  # a strong component (ex: circular type definition)
  for c in comps:
    assert c.len > 0
    if c.len == 1:
      res.add c[0].pnode
    else:
      let fstn = c[0].pnode
      let kind = fstn.kind
      # always return to the original order when we got circular dependencies
      let cs = c.sortedByIt(it.id)
      if kind in {nkTypeSection, nkConstSection} and haveSameKind(cs):
        # Circular dependency between type or const sections, we just
        # need to merge them
        var sn = newNode(kind)
        for dn in cs:
          sn.add dn.pnode[0]
        res.add sn
      else:
        # Problematic circular dependency, we arrange the nodes into
        # their original relative order and make sure to re-merge
        # consecutive type and const sections
        var wmsg = "Circular dependency detected. `codeReordering` pragma may not be able to" &
          " reorder some nodes properly"
        when defined(debugReorder):
          wmsg &= ":\n"
          for i in 0..<cs.len-1:
            for j in i..<cs.len:
              for ci in 0..<cs[i].kids.len:
                if cs[i].kids[ci].id == cs[j].id:
                  wmsg &= "line " & $cs[i].pnode.info.line &
                    " depends on line " & $cs[j].pnode.info.line &
                    ": " & cs[i].expls[ci] & "\n"
          for j in 0..<cs.len-1:
            for ci in 0..<cs[^1].kids.len:
              if cs[^1].kids[ci].id == cs[j].id:
                wmsg &= "line " & $cs[^1].pnode.info.line &
                  " depends on line " & $cs[j].pnode.info.line &
                  ": " & cs[^1].expls[ci] & "\n"
        message(conf, cs[0].pnode.info, warnUser, wmsg)

        var i = 0
        while i < cs.len:
          if cs[i].pnode.kind in {nkTypeSection, nkConstSection}:
            let ckind = cs[i].pnode.kind
            var sn = newNode(ckind)
            sn.add cs[i].pnode[0]
            inc i
            while i < cs.len and cs[i].pnode.kind == ckind:
              sn.add cs[i].pnode[0]
              inc i
            res.add sn
          else:
            res.add cs[i].pnode
            inc i

proc hasImportStmt(n: PNode): bool =
  # Checks if the node is an import statement or
  # i it contains one
  case n.kind
  of nkImportStmt, nkFromStmt, nkImportExceptStmt:
    return true
  of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse, nkStaticStmt:
    for a in n:
      if a.hasImportStmt:
        return true
  else:
    result = false

proc hasImportStmt(n: DepN): bool =
  if n.hIS < 0:
    n.hIS = ord(n.pnode.hasImportStmt)
  result = bool(n.hIS)

proc hasCommand(n: PNode): bool =
  # Checks if the node is a command or a call
  # or if it contains one
  case n.kind
  of nkCommand, nkCall:
    result = true
  of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse,
      nkStaticStmt, nkLetSection, nkConstSection, nkVarSection,
      nkIdentDefs:
    for a in n:
      if a.hasCommand:
        return true
  else:
    return false

proc hasCommand(n: DepN): bool =
  if n.hCmd < 0:
    n.hCmd = ord(n.pnode.hasCommand)
  result = bool(n.hCmd)

proc hasAccQuoted(n: PNode): bool =
  if n.kind == nkAccQuoted:
    return true
  for a in n:
    if hasAccQuoted(a):
      return true

const extendedProcDefs = procDefs + {nkMacroDef, nkTemplateDef}

proc hasAccQuotedDef(n: PNode): bool =
  # Checks if the node is a function, macro, template ...
  # with a quoted name or if it contains one
  case n.kind
  of extendedProcDefs:
    result = n[0].hasAccQuoted
  of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse, nkStaticStmt:
    for a in n:
      if hasAccQuotedDef(a):
        return true
  else:
    result = false

proc hasAccQuotedDef(n: DepN): bool =
  if n.hAQ < 0:
    n.hAQ = ord(n.pnode.hasAccQuotedDef)
  result = bool(n.hAQ)

proc hasBody(n: PNode): bool =
  # Checks if the node is a function, macro, template ...
  # with a body or if it contains one
  case n.kind
  of nkCommand, nkCall:
    result = true
  of extendedProcDefs:
    result = n[^1].kind == nkStmtList
  of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse, nkStaticStmt:
    for a in n:
      if a.hasBody:
        return true
  else:
    result = false

proc hasBody(n: DepN): bool =
  if n.hB < 0:
    n.hB = ord(n.pnode.hasBody)
  result = bool(n.hB)

proc intersects(s1, s2: IntSet): bool =
  for a in s1:
    if s2.contains(a):
      return true

proc buildGraph(n: PNode, deps: seq[(IntSet, IntSet)]): DepG =
  # Build a dependency graph
  result = newSeqOfCap[DepN](deps.len)
  for i in 0..<deps.len:
    result.add newDepN(i, n[i])
  for i in 0..<deps.len:
    var ni = result[i]
    let uses = deps[i][1]
    let niHasBody = ni.hasBody
    let niHasCmd = ni.hasCommand
    for j in 0..<deps.len:
      if i == j: continue
      var nj = result[j]
      let declares = deps[j][0]
      if j < i and nj.hasCommand and niHasCmd:
        # Preserve order for commands and calls
        ni.kids.add nj
        when defined(debugReorder):
          ni.expls.add "both have commands and one comes after the other"
      elif j < i and nj.hasImportStmt:
        # Every node that comes after an import statement must
        # depend on that import
        ni.kids.add nj
        when defined(debugReorder):
          ni.expls.add "parent is, or contains, an import statement and child comes after it"
      elif j < i and niHasBody and nj.hasAccQuotedDef:
        # Every function, macro, template... with a body depends
        # on precedent function declarations that have quoted names.
        # That's because it is hard to detect the use of functions
        # like "[]=", "[]", "or" ... in their bodies.
        ni.kids.add nj
        when defined(debugReorder):
          ni.expls.add "one declares a quoted identifier and the other has a body and comes after it"
      elif j < i and niHasBody and not nj.hasBody and
        intersects(deps[i][0], declares):
          # Keep function declaration before function definition
          ni.kids.add nj
          when defined(debugReorder):
            for dep in deps[i][0]:
              if dep in declares:
                ni.expls.add "one declares \"" & idNames[dep] & "\" and the other defines it"
      else:
        for d in declares:
          if uses.contains(d):
            ni.kids.add nj
            when defined(debugReorder):
              ni.expls.add "one declares \"" & idNames[d] & "\" and the other uses it"

proc strongConnect(v: var DepN, idx: var int, s: var seq[DepN],
                   res: var seq[seq[DepN]]) =
  # Recursive part of trajan's algorithm
  v.idx = idx
  v.lowLink = idx
  inc idx
  s.add v
  v.onStack = true
  for w in v.kids.mitems:
    if w.idx < 0:
      strongConnect(w, idx, s, res)
      v.lowLink = min(v.lowLink, w.lowLink)
    elif w.onStack:
      v.lowLink = min(v.lowLink, w.idx)
  if v.lowLink == v.idx:
    var comp = newSeq[DepN]()
    while true:
      var w = s.pop
      w.onStack = false
      comp.add w
      if w.id == v.id: break
    res.add comp

proc getStrongComponents(g: var DepG): seq[seq[DepN]] =
  ## Tarjan's algorithm. Performs a topological sort
  ## and detects strongly connected components.
  var s: seq[DepN]
  var idx = 0
  for v in g.mitems:
    if v.idx < 0:
      strongConnect(v, idx, s, result)

proc hasForbiddenPragma(n: PNode): bool =
  # Checks if the tree node has some pragmas that do not
  # play well with reordering, like the push/pop pragma
  for a in n:
    if a.kind == nkPragma and a[0].kind == nkIdent and
        a[0].ident.s == "push":
      return true

proc reorder*(graph: ModuleGraph, n: PNode, module: PSym): PNode =
  if n.hasForbiddenPragma:
    return n
  var includedFiles = initIntSet()
  let mpath = toFullPath(graph.config, module.fileIdx)
  let n = expandIncludes(graph, module, n, mpath,
                          includedFiles).splitSections
  result = newNodeI(nkStmtList, n.info)
  var deps = newSeq[(IntSet, IntSet)](n.len)
  for i in 0..<n.len:
    deps[i][0] = initIntSet()
    deps[i][1] = initIntSet()
    computeDeps(graph.cache, n[i], deps[i][0], deps[i][1], true)

  var g = buildGraph(n, deps)
  let comps = getStrongComponents(g)
  mergeSections(graph.config, comps, result)