import
intsets, ast, idents, algorithm, renderer, parser, os, strutils,
sequtils, msgs, modulegraphs, syntaxes, options, modulepaths, tables,
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 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(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 countup(0, a.len-3): decl(a[j])
for j in a.len-2..a.len-1: 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.sons[0].sym.name.id
of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse, nkStaticStmt:
for i in 0..<len(n): 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])
else:
for i in 0..<safeLen(n): deps(n[i])
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 =
for a in n:
if a.kind == nkIncludeStmt:
return true
proc includeModule*(graph: ModuleGraph; s: PSym, fileIdx: FileIndex): PNode {.procvar.} =
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.sons[i])
if f != InvalidFileIDX:
if containsOrIncl(includedFiles, f.int):
localError(graph.config, a.info, "recursive dependency: '$1'" %
toFilename(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.sons[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 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 extandedProcDefs = 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:
result = n[0].hasAccQuoted
of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse, nkStaticStmt:
for a in n:
if a.hasAccQuotedDef:
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 extandedProcDefs:
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.sons[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.
result = newSeq[seq[DepN]]()
var s = newSeq[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)