diff options
Diffstat (limited to 'compiler/reorder.nim')
| -rw-r--r-- | compiler/reorder.nim | 303 |
1 files changed, 147 insertions, 156 deletions
diff --git a/compiler/reorder.nim b/compiler/reorder.nim index 1cf5a0217..2f7c04af1 100644 --- a/compiler/reorder.nim +++ b/compiler/reorder.nim @@ -1,7 +1,16 @@ -import - intsets, ast, idents, algorithm, renderer, parser, ospaths, strutils, - sequtils, msgs, modulegraphs, syntaxes, options, modulepaths, tables +import + ast, idents, renderer, + msgs, modulegraphs, syntaxes, options, modulepaths, + lineinfos + +import std/[algorithm, strutils, intsets] + +when defined(nimPreviewSlimSystem): + import std/assertions + +when defined(nimDebugReorder): + import std/tables type DepN = ref object @@ -10,63 +19,54 @@ type onStack: bool kids: seq[DepN] hAQ, hIS, hB, hCmd: int - when not defined(release): + when defined(nimDebugReorder): expls: seq[string] DepG = seq[DepN] -when not defined(release): +when defined(nimDebugReorder): 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 not defined(release): + result = DepN(id: id, pnode: pnode, idx: -1, + lowLink: -1, onStack: false, + kids: @[], hAQ: -1, hIS: -1, + hB: -1, hCmd: -1 + ) + when defined(nimDebugReorder): result.expls = @[] -proc accQuoted(n: PNode): PIdent = +proc accQuoted(cache: IdentCache; n: PNode): PIdent = var id = "" - for i in 0 .. <n.len: - let x = n[i] - case x.kind - of nkIdent: id.add(x.ident.s) - of nkSym: id.add(x.sym.name.s) - else: discard - result = getIdent(id) - -proc addDecl(n: PNode; declares: var IntSet) = + 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(n[1], declares) - of nkPragmaExpr: addDecl(n[0], declares) + of nkPostfix: addDecl(cache, n[1], declares) + of nkPragmaExpr: addDecl(cache, n[0], declares) of nkIdent: declares.incl n.ident.id - when not defined(release): + when defined(nimDebugReorder): idNames[n.ident.id] = n.ident.s of nkSym: declares.incl n.sym.name.id - when not defined(release): + when defined(nimDebugReorder): idNames[n.sym.name.id] = n.sym.name.s of nkAccQuoted: - let a = accQuoted(n) + let a = accQuoted(cache, n) declares.incl a.id - when not defined(release): + when defined(nimDebugReorder): idNames[a.id] = a.s of nkEnumFieldDef: - addDecl(n[0], declares) + addDecl(cache, n[0], declares) else: discard -proc computeDeps(n: PNode, declares, uses: var IntSet; topLevel: bool) = - template deps(n) = computeDeps(n, declares, uses, false) +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(n, declares) + if topLevel: addDecl(cache, n, declares) case n.kind of procDefs, nkMacroDef, nkTemplateDef: decl(n[0]) @@ -74,8 +74,8 @@ proc computeDeps(n: PNode, declares, uses: var IntSet; topLevel: bool) = of nkLetSection, nkVarSection, nkUsingStmt: for a in n: if a.kind in {nkIdentDefs, nkVarTuple}: - for j in countup(0, a.len-3): decl(a[j]) - for j in a.len-2..a.len-1: deps(a[j]) + 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: @@ -92,58 +92,37 @@ proc computeDeps(n: PNode, declares, uses: var IntSet; topLevel: bool) = deps(n[i]) of nkIdent: uses.incl n.ident.id of nkSym: uses.incl n.sym.name.id - of nkAccQuoted: uses.incl accQuoted(n).id + of nkAccQuoted: uses.incl accQuoted(cache, n).id of nkOpenSymChoice, nkClosedSymChoice: - uses.incl n.sons[0].sym.name.id + uses.incl n[0].sym.name.id of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse, nkStaticStmt: - for i in 0..<len(n): computeDeps(n[i], declares, uses, topLevel) + for i in 0..<n.len: computeDeps(cache, n[i], declares, uses, topLevel) of nkPragma: - let a = n.sons[0] - if a.kind == nkExprColonExpr and a.sons[0].kind == nkIdent and - a.sons[0].ident.s == "pragma": - # user defined pragma - decl(a.sons[1]) + 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]) + for i in 1..<n.safeLen: deps(n[i]) else: - for i in 0..<safeLen(n): deps(n[i]) + for i in 0..<n.safeLen: deps(n[i]) + of nkMixinStmt, nkBindStmt: discard else: - for i in 0..<safeLen(n): deps(n[i]) - -proc cleanPath(s: string): string = - # Here paths may have the form A / B or "A/B" - result = "" - for c in s: - if c != ' ' and c != '\"': - result.add c - -proc joinPath(parts: seq[string]): string = - let nb = parts.len - assert nb > 0 - if nb == 1: - return parts[0] - result = parts[0] / parts[1] - for i in 2..<parts.len: - result = result / parts[i] - -proc getIncludePath(n: PNode, modulePath: string): string = - let istr = n.renderTree.cleanPath - let (pdir, _) = modulePath.splitPath - let p = istr.split('/').joinPath.addFileExt("nim") - result = pdir / p - -proc hasIncludes(n:PNode): bool = + # 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 = + result = false for a in n: if a.kind == nkIncludeStmt: return true -proc includeModule*(graph: ModuleGraph; s: PSym, fileIdx: int32; - cache: IdentCache): PNode {.procvar.} = - result = syntaxes.parseFile(fileIdx, cache) +proc includeModule*(graph: ModuleGraph; s: PSym, fileIdx: FileIndex): PNode = + result = syntaxes.parseFile(fileIdx, graph.cache, graph.config) graph.addDep(s, fileIdx) - graph.addIncludeDep(s.position.int32, fileIdx) + graph.addIncludeDep(FileIndex s.position, fileIdx) -proc expandIncludes(graph: ModuleGraph, module: PSym, n: PNode, - modulePath: string, includedFiles: var IntSet, - cache: IdentCache): PNode = +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 @@ -151,15 +130,16 @@ proc expandIncludes(graph: ModuleGraph, module: PSym, n: PNode, for a in n: if a.kind == nkIncludeStmt: for i in 0..<a.len: - var f = checkModuleName(a.sons[i]) - if f != InvalidFileIDX: - if containsOrIncl(includedFiles, f): - localError(a.info, errRecursiveDependencyX, f.toFilename) + 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, cache) - let nnn = expandIncludes(graph, module, nn, modulePath, - includedFiles, cache) - excl(includedFiles, f) + 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: @@ -189,7 +169,7 @@ proc haveSameKind(dns: seq[DepN]): bool = if dn.pnode.kind != kind: return false -proc mergeSections(comps: seq[seq[DepN]], res: PNode) = +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: @@ -206,53 +186,54 @@ proc mergeSections(comps: seq[seq[DepN]], res: PNode) = # need to merge them var sn = newNode(kind) for dn in cs: - sn.add dn.pnode.sons[0] + 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. reorder pragma may not be able to" & - " reorder some nodes properely" - when not defined(release): - 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(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) + # 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(nimDebugReorder): + 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 - 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 + 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 + result = true of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse, nkStaticStmt: + result = false for a in n: if a.hasImportStmt: return true @@ -273,9 +254,10 @@ proc hasCommand(n: PNode): bool = of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse, nkStaticStmt, nkLetSection, nkConstSection, nkVarSection, nkIdentDefs: - for a in n: - if a.hasCommand: - return true + result = false + for a in n: + if a.hasCommand: + return true else: return false @@ -285,23 +267,25 @@ proc hasCommand(n: DepN): bool = result = bool(n.hCmd) proc hasAccQuoted(n: PNode): bool = + result = false if n.kind == nkAccQuoted: return true for a in n: if hasAccQuoted(a): return true -const extandedProcDefs = procDefs + {nkMacroDef, nkTemplateDef} +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 extandedProcDefs: + of extendedProcDefs: result = n[0].hasAccQuoted of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse, nkStaticStmt: + result = false for a in n: - if a.hasAccQuotedDef: + if hasAccQuotedDef(a): return true else: result = false @@ -317,9 +301,10 @@ proc hasBody(n: PNode): bool = case n.kind of nkCommand, nkCall: result = true - of extandedProcDefs: + of extendedProcDefs: result = n[^1].kind == nkStmtList of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse, nkStaticStmt: + result = false for a in n: if a.hasBody: return true @@ -332,15 +317,24 @@ proc hasBody(n: DepN): bool = result = bool(n.hB) proc intersects(s1, s2: IntSet): bool = + result = false for a in s1: if s2.contains(a): return true +proc hasPushOrPopPragma(n: DepN): bool = + # Checks if the tree node has some pragmas that do not + # play well with reordering, like the push/pop pragma + # no crossing for push/pop barrier + let a = n.pnode + result = a.kind == nkPragma and a[0].kind == nkIdent and + (a[0].ident.s == "push" or a[0].ident.s == "pop") + 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.sons[i]) + result.add newDepN(i, n[i]) for i in 0..<deps.len: var ni = result[i] let uses = deps[i][1] @@ -353,13 +347,13 @@ proc buildGraph(n: PNode, deps: seq[(IntSet, IntSet)]): DepG = if j < i and nj.hasCommand and niHasCmd: # Preserve order for commands and calls ni.kids.add nj - when not defined(release): + when defined(nimDebugReorder): 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 not defined(release): + when defined(nimDebugReorder): 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 @@ -367,21 +361,28 @@ proc buildGraph(n: PNode, deps: seq[(IntSet, IntSet)]): DepG = # That's because it is hard to detect the use of functions # like "[]=", "[]", "or" ... in their bodies. ni.kids.add nj - when not defined(release): + when defined(nimDebugReorder): 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 not defined(release): + when defined(nimDebugReorder): for dep in deps[i][0]: if dep in declares: ni.expls.add "one declares \"" & idNames[dep] & "\" and the other defines it" + elif hasPushOrPopPragma(nj): + # Every node that comes after a push/pop pragma must + # depend on it; vice versa + if j < i: + ni.kids.add nj + else: + nj.kids.add ni else: for d in declares: if uses.contains(d): ni.kids.add nj - when not defined(release): + when defined(nimDebugReorder): ni.expls.add "one declares \"" & idNames[d] & "\" and the other uses it" proc strongConnect(v: var DepN, idx: var int, s: var seq[DepN], @@ -410,35 +411,25 @@ proc strongConnect(v: var DepN, idx: var int, s: var seq[DepN], proc getStrongComponents(g: var DepG): seq[seq[DepN]] = ## Tarjan's algorithm. Performs a topological sort ## and detects strongly connected components. - result = newSeq[seq[DepN]]() - var s = newSeq[DepN]() + result = @[] + 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, cache: IdentCache): PNode = - if n.hasForbiddenPragma: - return n +proc reorder*(graph: ModuleGraph, n: PNode, module: PSym): PNode = var includedFiles = initIntSet() - let mpath = module.fileIdx.toFullPath - let n = expandIncludes(graph, module, n, mpath, - includedFiles, cache).splitSections + 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(n[i], deps[i][0], deps[i][1], true) + computeDeps(graph.cache, n[i], deps[i][0], deps[i][1], true) var g = buildGraph(n, deps) let comps = getStrongComponents(g) - mergeSections(comps, result) + mergeSections(graph.config, comps, result) |