///|
fn fields(
value : Json,
allowed : Array[String],
) -> Map[String, Json] raise GraphError {
let object = match value {
Object(object) => object
_ => raise Invalid("expected a JSON object")
}
for key, _ in object {
if !allowed.contains(key) {
raise Invalid("unknown field: " + key)
}
}
object
}
///|
fn text(value : Json) -> String raise GraphError {
match value {
String(value) => value
_ => raise Invalid("expected a node ID string")
}
}
///|
fn required(object : Map[String, Json], name : String) -> Json raise GraphError {
match object.get(name) {
Some(value) => value
None => raise Invalid("missing field: " + name)
}
}
///|
fn items(value : Json, limit : Int32) -> Array[Json] raise GraphError {
match value {
Array(values) if values.length() <= limit => values
_ => raise Invalid("expected a bounded JSON array")
}
}
///|
fn node_index(
names : Map[String, Int32],
value : Json,
) -> Int32 raise GraphError {
let name = text(value)
match names.get(name) {
Some(index) => index
None => raise Invalid("unknown node: " + name)
}
}
///|
/// Parse cairndom.graph.v1 with string node IDs and strict JSON keys.
pub fn parse_graph(input : String) -> Graph raise GraphError {
if input.length() > 2_097_152 {
raise Invalid("graph JSON exceeds 2 MiB")
}
let value = @json.parse(
input,
max_nesting_depth=8,
reject_duplicate_keys=true,
) catch {
_ => raise Invalid("invalid JSON, repeated key or excessive nesting")
}
let object = fields(value, ["schema", "nodes", "edges", "entry", "exits"])
if text(required(object, "schema")) != "cairndom.graph.v1" {
raise Invalid("schema must be cairndom.graph.v1")
}
let nodes = []
let names : Map[String, Int32] = Map([])
for value in items(required(object, "nodes"), max_nodes) {
let name = text(value)
if !valid_id(name) || names.contains(name) {
raise Invalid("invalid or duplicate node ID: " + name)
}
names[name] = nodes.length()
nodes.push(name)
}
let edges = []
for value in items(required(object, "edges"), max_edges) {
let edge = items(value, 2)
if edge.length() != 2 {
raise Invalid("each edge must contain two node IDs")
}
edges.push((node_index(names, edge[0]), node_index(names, edge[1])))
}
let exits = []
for value in items(required(object, "exits"), max_nodes) {
exits.push(node_index(names, value))
}
snapshot_graph({
nodes,
edges,
exits,
entry: node_index(names, required(object, "entry")),
})
}
///|
fn names_json(graph : Graph, nodes : Array[Int32]) -> Json {
Json::array(nodes.map(index => Json::string(graph.nodes[index])))
}
///|
fn parent_json(graph : Graph, parent : Int32?) -> Json {
match parent {
Some(node) if node < graph.nodes.length() => Json::string(graph.nodes[node])
_ => Json::null()
}
}
///|
fn analysis_node_value(result : Analysis, index : Int32) -> Json {
let graph = result.graph
let post_parent = result.post.immediate[index]
Json::object(
Map([
("id", Json::string(graph.nodes[index])),
("reachable", Json::boolean(result.forward.reachable[index])),
("can_reach_exit", Json::boolean(result.post.reachable[index])),
(
"immediate_dominator",
parent_json(graph, result.forward.immediate[index]),
),
("dominance_frontier", names_json(graph, result.forward.frontiers[index])),
("immediate_postdominator", parent_json(graph, post_parent)),
(
"postdominator_is_virtual_exit",
Json::boolean(post_parent == Some(graph.nodes.length())),
),
(
"control_dependencies",
names_json(graph, result.control_dependencies[index]),
),
]),
)
}
///|
fn analysis_loop_value(result : Analysis, index : Int32) -> Json {
let graph = result.graph
let natural_loop = result.loops[index]
Json::object(
Map([
("header", Json::string(graph.nodes[natural_loop.header])),
("latches", names_json(graph, natural_loop.latches)),
("members", names_json(graph, natural_loop.members)),
(
"parent_header",
match natural_loop.parent {
Some(parent) => Json::string(graph.nodes[result.loops[parent].header])
None => Json::null()
},
),
]),
)
}
///|
fn analysis_component_value(result : Analysis, index : Int32) -> Json {
let graph = result.graph
let component = result.components[index]
Json::object(
Map([
("members", names_json(graph, component.members)),
("entry_nodes", names_json(graph, component.entry_nodes)),
("cyclic", Json::boolean(component.cyclic)),
("multiple_entries", Json::boolean(component.multiple_entries)),
]),
)
}
///|
fn analysis_report_fields(
result : Analysis,
schema : String,
) -> Array[(String, Json)] {
[
("schema", Json::string(schema)),
("entry", Json::string(result.graph.nodes[result.graph.entry])),
("exits", names_json(result.graph, result.graph.exits)),
(
"postdominator_scope",
Json::string("finite_paths_reaching_declared_exits"),
),
]
}
///|
fn analysis_report_sections(
result : Analysis,
) -> Array[(String, Int32, (Int32) -> Json)] {
[
(
"nodes",
result.graph.nodes.length(),
index => analysis_node_value(result, index),
),
(
"natural_loops",
result.loops.length(),
index => analysis_loop_value(result, index),
),
(
"components",
result.components.length(),
index => analysis_component_value(result, index),
),
]
}
///|
fn analysis_witness_value(graph : Graph, witness : ControlWitness) -> Json {
Json::object(
Map([
("controller", Json::string(graph.nodes[witness.controller])),
("successor", Json::string(graph.nodes[witness.successor])),
("dependent", Json::string(graph.nodes[witness.dependent])),
]),
)
}
///|
fn analysis_report_value(result : Analysis, include_witnesses : Bool) -> Json {
let schema = if include_witnesses {
"cairndom.analysis.v1"
} else {
"cairndom.analysis-summary.v1"
}
let report = Map(analysis_report_fields(result, schema))
for (name, count, row) in analysis_report_sections(result) {
report[name] = Json::array(Array::makei(count, row))
}
if include_witnesses {
let (witnesses, complete) = bounded_control_witnesses_of(result)
report["control_witnesses_complete"] = Json::boolean(complete)
report["control_witness_limit"] = Json::number(
max_control_witnesses.to_double(),
)
report["control_witnesses"] = Json::array(
witnesses.map(witness => analysis_witness_value(result.graph, witness)),
)
}
Json::object(report)
}
///|
/// Report indices as original string IDs, with explicit reachability and exit
/// scope. A virtual postdominator parent is distinguished from no exit path.
pub fn analysis_json_text(result : Analysis) -> String {
analysis_report_value(result, true).stringify(indent=2)
}
///|
/// A DOT graph showing original edges and dashed immediate-dominator edges.
/// Node IDs use the validated ASCII identifier grammar.
pub fn analysis_dot(result : Analysis) -> String {
let graph = result.graph
let out = StringBuilder()
out.write_string("digraph CairnDom {\n rankdir=TB;\n")
for index, name in graph.nodes {
let style = if result.forward.reachable[index] { "solid" } else { "dotted" }
out.write_string(" \"\{name}\" [style=\{style}];\n")
}
for (from, to) in graph.edges {
out.write_string(" \"\{graph.nodes[from]}\" -> \"\{graph.nodes[to]}\";\n")
}
for index, parent in result.forward.immediate {
if parent is Some(dominator) {
out.write_string(
" \"\{graph.nodes[dominator]}\" -> \"\{graph.nodes[index]}\" [style=dashed,color=blue,label=\"idom\"];\n",
)
}
}
out.write_string("}\n")
out.to_string()
}