///|
/// Possible last-definition blocks for a use before the block's local defs.
/// requires_entry_value records a possible caller-supplied incoming value;
/// it does not establish a source-language missing-initialization error.
#derive(Eq, Debug)
pub(all) struct UseOrigins {
node : Int32
variable : Int32
definitions : Array[Int32]
requires_entry_value : Bool
}
///|
pub extend UseOrigins with Eq::{equal, not_equal}
///|
pub extend UseOrigins with Debug::{to_repr}
///|
/// Privately owned input and complete per-use results. Inspection methods
/// return defensive copies so later caller edits cannot alter saved answers.
struct ValueOrigins {
program : FlowProgram
reachable : Array[Bool]
origins : Array[UseOrigins]
}
///|
let max_value_origin_relations : Int32 = 65536
///|
/// Explain each entry-reachable use over all finite entry-to-use paths,
/// including uses in permanent loops. Uses precede local definitions; a block's
/// own definition can reach its use through a previous loop iteration.
/// Results are ordered by node then variable, with definition blocks sorted by
/// node index. At most 65,536 source/use relations are returned, counting each
/// incoming-value flag as one source. Oversized complete results raise an error
/// rather than returning a partial list. Each reverse search uses O(n) scratch
/// space and O(n + e) work, without a block/variable/source state matrix.
pub fn trace_values(input : FlowProgram) -> ValueOrigins raise GraphError {
validate_program(input)
let program : FlowProgram = {
graph: snapshot_graph(input.graph),
variables: input.variables.copy(),
definitions: input.definitions.map(row => row.copy()),
uses: input.uses.map(row => row.copy()),
}
let graph = program.graph
let n = graph.nodes.length()
let (succ, pred) = adjacency(graph)
let reachable = Array::make(n, false)
let visit = [graph.entry]
reachable[graph.entry] = true
let mut next = 0
while next < visit.length() {
let node = visit[next]
next += 1
for child in succ[node] {
if !reachable[child] {
reachable[child] = true
visit.push(child)
}
}
}
let use_sites : Array[Array[Int32]] = Array::makei(
program.variables.length(),
_ => [],
)
for node in 0.. {
reachable[node] && program.definitions[node].contains(variable)
})
for node in sites {
let seen = Array::make(n, false)
let sources = Array::make(n, false)
let work = [node]
seen[node] = true
let mut cursor = 0
let mut requires_entry_value = false
while cursor < work.length() {
let current = work[cursor]
cursor += 1
if current == graph.entry && !requires_entry_value {
if relations == max_value_origin_relations {
raise Invalid("value-origin relation limit of 65536 exceeded")
}
relations += 1
requires_entry_value = true
}
for previous in pred[current] {
if !reachable[previous] {
continue
}
// Test definitions before seen: an already visited use block can
// supply its local definition through a self-edge or another cycle.
if defined[previous] {
if !sources[previous] {
if relations == max_value_origin_relations {
raise Invalid("value-origin relation limit of 65536 exceeded")
}
relations += 1
sources[previous] = true
}
} else if !seen[previous] {
seen[previous] = true
work.push(previous)
}
}
}
let definitions = []
for source, yes in sources {
if yes {
definitions.push(source)
}
}
origins.push({ node, variable, definitions, requires_entry_value, })
}
}
origins.sort_by(fn(left, right) {
if left.node != right.node {
left.node.compare(right.node)
} else {
left.variable.compare(right.variable)
}
})
{ program, reachable, origins, }
}
///|
/// Return an independently mutable input snapshot, including all graph arrays
/// and nested definition/use rows. Editing it cannot change these origins.
pub fn ValueOrigins::program(self : Self) -> FlowProgram {
let program = self.program
let graph = program.graph
{
graph: {
nodes: graph.nodes.copy(),
edges: graph.edges.copy(),
entry: graph.entry,
exits: graph.exits.copy(),
},
variables: program.variables.copy(),
definitions: program.definitions.map(row => row.copy()),
uses: program.uses.map(row => row.copy()),
}
}
///|
/// Return complete origins in node/variable order, copying each definitions
/// array as well as the outer list. Unreachable uses are absent.
pub fn ValueOrigins::uses(self : Self) -> Array[UseOrigins] {
self.origins.map(origin => {
..origin,
definitions: origin.definitions.copy(),
})
}
///|
/// Entry reachability, independent of declared exits or eventual termination.
pub fn ValueOrigins::is_reachable(
self : Self,
node : Int32,
) -> Bool raise GraphError {
if node < 0 || node >= self.reachable.length() {
raise Invalid("value-origin node index is outside the graph")
}
self.reachable[node]
}