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)