import
  intsets, ast, idents, algorithm, renderer, parser, ospaths, strutils,
  sequtils, msgs, modulegraphs, syntaxes, options, modulepaths, tables,
  configuration

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

when not defined(release):
  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.expls = @[]

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
    when not defined(release):
      idNames[n.ident.id] = n.ident.s
  of nkSym:
    declares.incl n.sym.name.id
    when not defined(release):
      idNames[n.sym.name.id] = n.sym.name.s
  of nkAccQuoted:
    let a = accQuoted(n)
    declares.incl a.id
    when not defined(release):
      idNames[a.id] = a.s
  of nkEnumFieldDef:
    addDecl(n[0], declares)
  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, 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(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(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 <style>pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */</style><div class="highlight"><pre><span></span><span class="k">discard</span><span class="w"> </span><span class="s2">&quot;&quot;&quot;</span>
<span class="s">  output: 42</span>
<span class="s2">&quot;&quot;&quot;</span>

<span class="kn">import</span><span class="w"> </span><span class="n">asyncdispatch</span>

<span class="k">proc</span><span class="w"> </span><span class="nf">foo</span><span class="p">():</span><span class="w"> </span><span class="n">Future</span><span class="o">[</span><span class="nb">int</span><span class="o">]</span><span class="w"> </span><span class="sx">{.async.}</span><span class="w"> </span><span class="o">=</span>
<span class="w">  </span><span class="k">template</span><span class="w"> </span><span class="nf">ret</span><span class="p">()</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="mi">42</span>
<span class="w">  </span><span class="n">ret</span><span class="p">()</span>

<span class="n">echo</span><span class="w"> </span><span class="p">(</span><span class="n">waitFor</span><span class="w"> </span><span class="n">foo</span><span class="p">())</span>
</pre></div>
</code></pre></td></tr></table>
</div> <!-- class=content -->
<div class='footer'>generated by <a href='https://git.causal.agency/cgit-pink/about/'>cgit-pink 1.4.1-2-gfad0</a> (<a href='https://git-scm.com/'>git 2.36.2.497.gbbea4dcf42</a>) at 2025-07-18 00:40:32 +0000</div>
</div> <!-- id=cgit -->
</body>
</html>
ses = 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 not defined(release):
          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):
          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 not defined(release):
          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):
            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 not defined(release):
              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, cache: IdentCache): PNode =
  if n.hasForbiddenPragma:
    return n
  var includedFiles = initIntSet()
  let mpath = module.fileIdx.toFullPath
  let n = expandIncludes(graph, module, n, mpath,
                          includedFiles, cache).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)

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