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

Code before:
        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
provenance.)  In any case, we still retain byte (or, from old macros,
LineNumberNode) provenance.

Provenance shrinkage: The green tree will be delete unless specified in `keep`.
If node A references node B as its `.source` and B is unreachable, A adopts the
source of B.
"""
function prune(st::SyntaxTree;
               keep::Union{SyntaxTree, SyntaxList, Nothing}=nothing)
    entrypoints = NodeId[st._id]
    keep isa SyntaxList && append!(entrypoints, keep.ids)
    keep isa SyntaxTree && push!(entrypoints, keep._id)
    prune(syntax_graph(st), unique(entrypoints))[1]
end

# This implementation unaliases nodes, which undoes a small amount of space
# savings from the DAG representation, but it allows us to (1) omit the whole
# `edges` array (TODO), and (2) make the pruning algorithm simpler.  The
# invariant we win is having `edge_ranges` be one or more interleaved
# level-order traversals where every node's set of children is contiguous, so
# its entries can refer to itself instead of an external `edges` vector.
function prune(graph1_a::SyntaxGraph, entrypoints_a::Vector{NodeId})
    @assert length(entrypoints_a) === length(unique(entrypoints_a))
    unaliased = unalias_nodes(SyntaxList(graph1_a, entrypoints_a))
    (graph1, entrypoints) = (unaliased.graph, unaliased.ids)

    nodes1 = copy(entrypoints)      # Current reachable subset of graph1
    map12 = Dict{NodeId, Int}()     # graph1 => graph2 mapping
    graph2 = ensure_attributes!(SyntaxGraph(); attrdefs(graph1)...)

Review comment (suggestion):
```suggestion
Provenance shrinkage: The green tree will be deleted unless specified in `keep`.
```

Code after:
    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.
"""
function prune(st::SyntaxTree;
               keep::Union{SyntaxTree, SyntaxList, Nothing}=nothing)
    entrypoints = NodeId[st._id]
    keep isa SyntaxList && append!(entrypoints, keep.ids)
    keep isa SyntaxTree && push!(entrypoints, keep._id)
    prune(syntax_graph(st), unique(entrypoints))[1]
end

# This implementation unaliases nodes, which undoes a small amount of space
# savings from the DAG representation, but it allows us to (1) omit the whole
# `edges` array (TODO), and (2) make the pruning algorithm simpler.  The
# invariant we win is having `edge_ranges` be one or more interleaved
# level-order traversals where every node's set of children is contiguous, so
# its entries can refer to itself instead of an external `edges` vector.
function prune(graph1_a::SyntaxGraph, entrypoints_a::Vector{NodeId})
    @assert length(entrypoints_a) === length(unique(entrypoints_a))
    unaliased = unalias_nodes(SyntaxList(graph1_a, entrypoints_a))
    (graph1, entrypoints) = (unaliased.graph, unaliased.ids)

    nodes1 = copy(entrypoints)      # Current reachable subset of graph1
    map12 = Dict{NodeId, Int}()     # graph1 => graph2 mapping
    graph2 = ensure_attributes!(SyntaxGraph(); attrdefs(graph1)...)
    while length(graph2.edge_ranges) < length(nodes1)
        n2 = length(graph2.edge_ranges) + 1
        n1 = nodes1[n2]
        map12[n1] = n2
        push!(graph2.edge_ranges, is_leaf(graph1, n1) ?
            (0:-1) : (1:numchildren(graph1, n1)) .+ length(nodes1))