1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
import intsets, tables, ast, idents, renderer
const
nfTempMark = nfTransf
nfPermMark = nfNoRewrite
proc accQuoted(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) =
case n.kind
of nkPostfix: addDecl(n[1], declares)
of nkPragmaExpr: addDecl(n[0], declares)
of nkIdent:
declares.incl n.ident.id
of nkSym:
declares.incl n.sym.name.id
of nkAccQuoted:
declares.incl accQuoted(n).id
else: discard
proc computeDeps(n: PNode, declares, uses: var IntSet; topLevel: bool) =
template deps(n) = computeDeps(n, declares, uses, false)
template decl(n) =
if topLevel: addDecl(n, declares)
case n.kind
of procDefs:
decl(n[0])
for i in 1..bodyPos: deps(n[i])
of nkLetSection, nkVarSection:
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: deps(a[i])
of nkIdent: uses.incl n.ident.id
of nkSym: uses.incl n.sym.name.id
of nkAccQuoted: uses.incl accQuoted(n).id
of nkOpenSymChoice, nkClosedSymChoice:
uses.incl n.sons[0].sym.name.id
of nkStmtList, nkStmtListExpr, nkWhenStmt, nkElifBranch, nkElse:
for i in 0..<len(n): computeDeps(n[i], declares, uses, topLevel)
else:
for i in 0..<safeLen(n): deps(n[i])
proc visit(i: int; all, res: PNode; deps: var seq[(IntSet, IntSet)]): bool =
let n = all[i]
if nfTempMark in n.flags:
# not a DAG!
return true
if nfPermMark notin n.flags:
incl n.flags, nfTempMark
var uses = deps[i][1]
for j in 0..<all.len:
if j != i:
let declares = deps[j][0]
for d in declares:
if uses.contains(d):
let oldLen = res.len
if visit(j, all, res, deps):
result = true
# rollback what we did, it turned out to be a dependency that caused
# trouble:
for k in oldLen..<res.len:
res.sons[k].flags = res.sons[k].flags - {nfPermMark, nfTempMark}
res.sons.setLen oldLen
break
n.flags = n.flags + {nfPermMark} - {nfTempMark}
res.add n
proc reorder*(n: PNode): PNode =
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)
for i in 0 .. n.len-1:
discard visit(i, n, result, deps)
for i in 0..<result.len:
result.sons[i].flags = result.sons[i].flags - {nfTempMark, nfPermMark}
when false:
# reverse the result:
let L = result.len-1
for i in 0 .. result.len div 2:
result.sons[i].flags = result.sons[i].flags - {nfTempMark, nfPermMark}
result.sons[L - i].flags = result.sons[L - i].flags - {nfTempMark, nfPermMark}
swap(result.sons[i], result.sons[L - i])
echo result
|