dofile(getenv("HOME").."/LUA/inc50.lua")	-- (find-angg "LUA/inc50.lua")

-- dep = dependency
-- scc = strongly-connected component

node_names = {}
nodes = {}
opened_nodes = {}
closed_nodes = {}

function assert_node(name)
  if not nodes[name] then
    tinsert(node_names, name)
    nodes[name] = {name=name, status="unused", deps={}, deps_table={},
		   scc_root=name, scc_next=name}
  -- nil fields:
  --   parent, opening_time, closing_time.
  end
end

function add_dep(name1, name2)
  assert_node(name1)
  assert_node(name2)
  tinsert(nodes[name1].deps, name2)
  nodes[name1].deps_table[name2]=name2
end

function scc_root(name)
  local thisnode = nodes[name]
  if thisnode.scc_root == name then
    return name
  end
  thisnode.scc_root = scc_root(thisnode.scc_root)
  return thisnode.scc_root
end

function collapse_sccs(base, additional)
  base = scc_root(base)
  additional = scc_root(additional)
  while additional ~= base do
    nodes[base].scc_next, nodes[additional].scc_next =
      nodes[additional].scc_next, nodes[base].scc_next
    additional.scc_root = base
    additional = scc_root(additional.parent)
  end
end  

function visit_node(parent, name)
  local newnode = nodes[name]
  local i, dep
  if newnode.status == "unused" then
    newnode.parent = parent
    newnode.status = "open"
    tinsert(opened_nodes, name)
    newnode.opening_time = getn(opened_nodes)
    for dep,_ in newnode.deps_table do
      visit_node(name, dep)
    end
    newnode.status = "closed"
    tinsert(closed_nodes, name)
    newnode.closing_time = getn(closed_nodes)
  elseif newnode.status == "open" then
    collapse_sccs(name, parent)
  end
  -- nothing to do if the node is already closed
end

-- this is tuned for the syntax of makefiles
--
do
  local line, found, befores, afters, j, k
  while 1 do
    line = read()
    if not line then break end
    found, _, befores, afters = strfind(line, "^(.*):(.*)")
    befores = split(befores)
    afters = split(afters)
    for j = 1,getn(befores) do
      for k = 1,getn(afters) do
        add_dep(befores[j], afters[k])
      end
    end
  end
end

for i = 1,getn(node_names) do
  visit_node(nil, node_names[i])
end

-- p(nodes)
-- p(closed_nodes)

-- print(join(closed_nodes, "\n"))
print(join(closed_nodes, "\n",
  function(node)
    return node .. ": " .. join(nodes[node].deps)
  end))

-- for i = 1,getn(closed_nodes) do

-- cd ~/LUA/; lua toposort.lua