infedges.jl

const CC = Core.Compiler
using Base: IdSet

# count total number of nodes reachable from a given point
function edgecount(G, from, counts = IdDict{Any,Int}())
    if haskey(counts, from)
        return 0
    end
    if !CC.haskey(G, from)
        return 0
    end
    next = CC.collect(CC.getindex(G, from))
    counts[from] = 0
    counts[from] = sum(x->edgecount(G, x, counts), next) + length(next)
end

# sorted list of (node, count) for all nodes
function flat_count(G)
    nodes = CC.collect(CC.keys(G))
    sort([(n, edgecount(G, n)) for n in nodes], by = x->x[2])
end

# print a tree from the given starting point
function showtree(io, G, from, level = 0, seen = IdSet{Any}())
    for i = 1:level
        print(io, "  ")
    end
    println(io, from, " ", edgecount(G, from))
    if !in(from, seen)
        push!(seen, from)
        if CC.haskey(G, from)
            next = CC.collect(CC.getindex(G, from))
            for n in next
                showtree(io, G, n, level+1, seen)
            end
        end
    end
end

# print the "worst" path through the tree from a given point; i.e. at each
# level only follow the (not-yet-seen) link with the highest count.
function badpath(io, G, from, seen = IdSet{Any}(), count = edgecount(G, from))
    println(io, from, " ", count)
    push!(seen, from)
    if CC.haskey(G, from)
        next = filter(x->!in(x,seen), CC.collect(CC.getindex(G, from)))
        counts = map(n->edgecount(G, n), next)
        m = argmax(counts)
        badpath(io, G, next[m], seen, counts[m])
    end
end

#=
Sample run:

G = CC.inference_graph;
CC.empty!(G);
CC.record_edges[] = true

using CSV; using REPL; @time precompile(Tuple{typeof(REPL.REPLCompletions.completions), String, Int64})

flat_count(G)
4351-element Array{Tuple{Type,Int64},1}:
...
 (Tuple{typeof(*),T,Char} where T<:FilePathsBase.AbstractPath, 9348)
 (Tuple{typeof(REPL.REPLCompletions.completions),String,Int64,Any}, 10429)
 (Tuple{typeof(REPL.REPLCompletions.completions),String,Int64}, 10430)
 (Tuple{typeof(REPL.REPLCompletions.completions),String,Int64,Module}, 10445)
 (Tuple{typeof(REPL.LineEdit.complete_line),REPL.REPLCompletionProvider,Any}, 11980)

f = open("inftree.txt", "w")
showtree(f, G, Tuple{typeof(REPL.LineEdit.complete_line),REPL.REPLCompletionProvider,Any})
close(f)

badpath(stdout, G, Tuple{typeof(REPL.LineEdit.complete_line),REPL.REPLCompletionProvider,Any})
Tuple{typeof(REPL.LineEdit.complete_line),REPL.REPLCompletionProvider,Any} 12003
Tuple{typeof(REPL.REPLCompletions.completions),String,Int64} 10453
Tuple{typeof(REPL.REPLCompletions.completions),String,Int64,Any} 10452
Tuple{typeof(*),T,String} where T<:FilePathsBase.AbstractPath 9368
Tuple{typeof(string),FilePathsBase.AbstractPath} 9030
...
Tuple{Type,DataFrames.SubDataFrame} 4586
Tuple{typeof(convert),Type{Union{}},DataFrames.SubDataFrame} 3
Tuple{Type{MethodError},typeof(convert),Tuple{Core.TypeofBottom,DataFrames.SubDataFrame}} 2
Tuple{Type{MethodError},typeof(convert),Tuple{Core.TypeofBottom,DataFrames.SubDataFrame},UInt64} 1
Tuple{typeof(Core.convert),Type{UInt64},UInt64} 0

=#