Repository: JuliaLang/julia
File: JuliaSyntax/src/porcelain/syntax_graph.jl (Julia)

Code before:

    unalias_nodes(sl::SyntaxList)

If a `SyntaxList` is given, every resulting tree will be unique with respect to
each other as well as internally.  A duplicate entry will produce a copied tree.
"""
unalias_nodes(st::SyntaxTree) = SyntaxTree(
    syntax_graph(st),
    _unalias_nodes(syntax_graph(st), st._id, Set{NodeId}(), Set{Int}()))

function unalias_nodes(sl::SyntaxList)
    seen = Set{NodeId}()
    seen_edges = Set{Int}()
    SyntaxList(syntax_graph(sl),
               map(id->_unalias_nodes(syntax_graph(sl), id, seen, seen_edges),
                   sl.ids))
end

# Note that `seen_edges` is only needed for when edge ranges overlap, which is a
# situation we don't produce yet.
function _unalias_nodes(graph::SyntaxGraph, id::NodeId,
                        seen::Set{NodeId}, seen_edges::Set{Int})
    if id in seen
        id = copy_ast(graph, SyntaxTree(graph, id); copy_source=false)._id
    end
    if !isempty(intersect(seen_edges, graph.edge_ranges[id]))
        # someone is referencing our edges; run away so we can modify them
        # (we don't produce this situation.  delete if we decide we never will)
        next_edge = length(graph.edges) + 1
        append!(graph.edges, children(graph, id))
        graph.edge_ranges[id] = next_edge:lastindex(graph.edges)
    end
    union!(seen_edges, graph.edge_ranges[id])
    push!(seen, id)

    for (c, i) in zip(children(graph, id), graph.edge_ranges[id])
        c2 = _unalias_nodes(graph, c, seen, seen_edges)
        # the new child should be the same in every way to the old one, so
        # modify the edge instead of triggering copies with `mapchildren`
        c !== c2 && (graph.edges[i] = c2)
    end
    return id
end

"""
Return a tree where unreachable nodes (non-descendents of `st`) in its graph
have been deleted, and where provenance data has been minimized.

If `keep` is not nothing, also consider descendents of it reachable.  It's
usually useful to provide `keep=your_parser_output` (so we have expression
provenance back to the original parsed nodes, but no lowering-internal

Review comment (suggestion):
I'd be OK with turning this into an `@assert` (or just deleting it)

Trying to compress edge ranges to overlap as a micro-optimization is kind of out there IMO.

Code after:
    unalias_nodes(sl::SyntaxList)

If a `SyntaxList` is given, every resulting tree will be unique with respect to
each other as well as internally.  A duplicate entry will produce a copied tree.
"""
unalias_nodes(st::SyntaxTree) = SyntaxTree(
    syntax_graph(st),
    _unalias_nodes(syntax_graph(st), st._id, Set{NodeId}(), Set{Int}()))

function unalias_nodes(sl::SyntaxList)
    seen = Set{NodeId}()
    seen_edges = Set{Int}()
    SyntaxList(syntax_graph(sl),
               map(id->_unalias_nodes(syntax_graph(sl), id, seen, seen_edges),
                   sl.ids))
end

# Note that `seen_edges` is only needed for when edge ranges overlap, which is a
# situation we don't produce yet.
function _unalias_nodes(graph::SyntaxGraph, id::NodeId,
                        seen::Set{NodeId}, seen_edges::Set{Int})
    if id in seen
        id = copy_ast(graph, SyntaxTree(graph, id); copy_source=false)._id
    end
    # nodes may not share edges (SyntaxGraph invariant)
    @assert isempty(intersect(seen_edges, graph.edge_ranges[id]))
    union!(seen_edges, graph.edge_ranges[id])
    push!(seen, id)

    for (c, i) in zip(children(graph, id), graph.edge_ranges[id])
        c2 = _unalias_nodes(graph, c, seen, seen_edges)
        # the new child should be the same in every way to the old one, so
        # modify the edge instead of triggering copies with `mapchildren`
        c !== c2 && (graph.edges[i] = c2)
    end
    return id
end

"""
Return a tree where unreachable nodes (non-descendents of `st`) in its graph
have been deleted, and where provenance data has been minimized.

If `keep` is not nothing, also consider descendents of it reachable.  It's
usually useful to provide `keep=your_parser_output` (so we have expression
provenance back to the original parsed nodes, but no lowering-internal
provenance.)  In any case, we still retain byte (or, from old macros,
LineNumberNode) provenance.

Provenance shrinkage: The green tree will be deleted unless specified in `keep`.
If node A references node B as its `.source` and B is unreachable, A adopts the
source of B.