Code graph and memory for your coding agents, in one Rust program. For Claude Code, Codex, Cursor and any MCP client.
Rust agent-memoryai-agentsclaude-codecode-analysiscode-graphcode-intelligencecode-searchcodexcoding-agentscontext-engineeringcursordeveloper-toolsgraphragknowledge-graphlocal-firstmcpmcp-servermodel-context-protocolrusttree-sitter
// Adapted from Graphify 0.9.95 (92741d16), Apache-2.0; see NOTICE.md.
// Upstream: graphify/build.py
//! Native graph construction and conservative normalization of extraction output.
pub use crate::build_global::{distinct_repo_tags, prefix_graph_for_global, prune_repo_from_graph};
pub use crate::build_labels::is_file_node_label;
pub use crate::build_merge::{
MergeOptions, build_merge, build_merge_owned, load_existing_graph, merge_raw_extraction,
};
pub use crate::build_normalize::*;
use crate::{
Result,
dedup::{self, DedupOptions, TiebreakClient},
dedup_strings,
extractors::{
base,
resolution::{is_python_stdlib_module, map_field, map_field_mut},
},
fsutil,
graph::Graph,
hyperedge_members, ids,
python_compat::{self, scalar_key},
record::{Attributes, EdgeItem, Properties, Record, item_field},
validate,
};
use rustc_hash::{FxHashMap, FxHashSet};
use serde::{Deserialize, Serialize};
use serde_json::{Map, Value, json};
use std::{
collections::{BTreeMap, BTreeSet, HashMap},
path::{Path, PathBuf},
};
pub const GENERIC_RELATIONS: &[&str] = &["references", "uses", "mentions"];
/// Relations whose undeclared target gets a typed external stub node so every
/// edge endpoint resolves (#2873). `calls` is deliberately absent: a call to an
/// external target survives only when its module was imported too, since the
/// import edge pre-mints the stub (#3793); a call to a never-imported target is
/// still dropped as a phantom (#3156).
pub const EXTERNAL_STUB_RELATIONS: &[&str] = &["imports", "imports_from", "re_exports"];
/// Membership of a type or file (0.9.83, #4256). On an undirected graph these
/// share a node pair with a `calls` edge in the opposite direction when a
/// member calls or constructs its owner; the membership edge wins that
/// collapse, so the member stays reachable from its type. Directed graphs
/// keep both, and same-direction `contains`/`method` vs `calls` is not ranked.
pub const STRUCTURAL_MEMBER_RELATIONS: &[&str] = &["method", "contains"];
#[derive(Default, Debug, Serialize)]
pub struct Diagnostics {
pub stdout: Vec<String>,
pub stderr: Vec<String>,
}
#[derive(Clone, Debug, Serialize, Deserialize)]
#[serde(default)]
pub struct BuildOptions {
pub directed: bool,
pub dedup: bool,
pub dedup_llm_backend: Option<String>,
pub root: Option<PathBuf>,
pub protected_ids: BTreeSet<String>,
/// Keep parallel edges with different relations between the same pair,
/// keyed by relation. The parity default (`false`) folds them into one
/// edge exactly as the Python `build_graph` does.
pub multigraph: bool,
}
impl Default for BuildOptions {
fn default() -> Self {
Self {
directed: false,
dedup: true,
dedup_llm_backend: None,
root: None,
protected_ids: BTreeSet::new(),
multigraph: false,
}
}
}
pub fn edge_datas<'a>(
graph: &'a Graph,
source: &Value,
target: &Value,
) -> Result<Vec<&'a crate::record::Attributes>> {
let edges = graph.edges_between(source, target);
if edges.is_empty() {
return Err(format!(
"Missing graph edge {} → {}",
python_compat::repr(source),
python_compat::repr(target)
)
.into());
}
Ok(edges.into_iter().map(|e| &e.attributes).collect())
}
pub fn edge_data<'a>(
graph: &'a Graph,
source: &Value,
target: &Value,
) -> Result<&'a crate::record::Attributes> {
Ok(edge_datas(graph, source, target)?[0])
}
fn external_stub(nid: &str) -> Value {
json!({"id":nid,"label":nid,"file_type":"concept","type":"external","external":true,"source_file":""})
}
pub fn mint_external_stub(graph: &mut Graph, nid: &str) -> Result<()> {
if graph.node_index(&json!(nid)).is_none() {
let mut attributes = external_stub(nid).as_object().unwrap().clone();
attributes.shift_remove("id");
graph.add_node(json!(nid), attributes)?;
}
Ok(())
}
pub fn mint_external_stubs_in_data(data: &mut Value) {
let Some(nodes) = data["nodes"].as_array() else {
return;
};
let links = data["links"]
.as_array()
.or_else(|| data["edges"].as_array());
let Some(links) = links else {
return;
};
let declared: BTreeSet<_> = nodes
.iter()
.filter(|n| n.is_object())
.filter_map(|n| scalar_key(&n["id"]))
.collect();
let mut minted = BTreeSet::new();
let mut additions = Vec::new();
for edge in links {
if !edge["relation"]
.as_str()
.is_some_and(|s| EXTERNAL_STUB_RELATIONS.contains(&s))
{
continue;
}
let Some(target) = edge["target"].as_str() else {
continue;
};
if scalar_key(&edge["source"]).is_some_and(|k| declared.contains(&k))
&& !declared.contains(&scalar_key(&edge["target"]).unwrap())
&& minted.insert(target)
{
additions.push(external_stub(target));
}
}
data["nodes"].as_array_mut().unwrap().extend(additions);
}
/// `finalize_raw_graph_endpoints` (0.9.80, #4189/#4181): apply
/// [`build_from_json`]'s endpoint rules to a raw (`--no-cluster`) graph. An
/// endpoint that differs from a declared id only by normalization, or that
/// names a declared node in an old-stem spelling ([`alias_index`], Graphify
/// 0.9.95, #4670), is repointed to it first; whatever still names an
/// undeclared node is external: an import of an external module gets its
/// typed stub, every other edge without two declared endpoints is dropped,
/// and a stub no edge or hyperedge references any more is dropped, as a fresh
/// build would not have it.
pub fn finalize_raw_graph_endpoints(data: &mut Value) {
let key = if data.get("links").is_some_and(Value::is_array) {
"links"
} else {
"edges"
};
if !data.get("nodes").is_some_and(Value::is_array)
|| !data.get(key).is_some_and(Value::is_array)
{
return;
}
let declared_ids = |data: &Value| {
data["nodes"]
.as_array()
.into_iter()
.flatten()
.filter_map(|n| n.as_object()?.get("id")?.as_str())
.map(str::to_owned)
.collect::<Vec<_>>()
};
let mut declared = declared_ids(&*data);
declared.sort();
declared.dedup();
// Two ids with one normalized spelling: the later in sorted order wins,
// the same stable choice build_from_json makes (the reference iterates a set).
let mut norm_to_id: FxHashMap<String, String> = declared
.iter()
.map(|nid| (ids::normalize_id(nid), nid.clone()))
.collect();
// Only fills gaps: never overrides a real node id.
let index = alias_index(
data["nodes"]
.as_array()
.into_iter()
.flatten()
.filter_map(|n| {
let node = n.as_object()?;
Some((node.get("id")?.as_str()?, node))
}),
);
for (alias, canonical) in index {
norm_to_id.entry(alias).or_insert(canonical);
}
let declared: std::collections::HashSet<String> = declared.into_iter().collect();
// Repoint every endpoint that has a canonical form before stubbing, so an
// import that names a real file is not frozen onto a stub minted for its
// unresolved spelling.
for object in data[key]
.as_array_mut()
.unwrap()
.iter_mut()
.filter_map(Value::as_object_mut)
{
for (primary, alias) in [("source", "from"), ("target", "to")] {
let field = if object.contains_key(primary) {
primary
} else {
alias
};
if let Some(endpoint) = object.get(field).and_then(Value::as_str)
&& !declared.contains(endpoint)
&& let Some(canonical) = norm_to_id.get(&ids::normalize_id(endpoint))
{
object.insert(field.into(), json!(canonical));
}
}
}
mint_external_stubs_in_data(data);
let declared: std::collections::HashSet<String> = declared_ids(&*data).into_iter().collect();
let mut referenced = BTreeSet::new();
let links = std::mem::take(data[key].as_array_mut().unwrap());
let mut kept = Vec::with_capacity(links.len());
for mut edge in links {
let Some(object) = edge.as_object_mut() else {
kept.push(edge);
continue;
};
let mut attached = true;
for (primary, alias) in [("source", "from"), ("target", "to")] {
let field = if object.contains_key(primary) {
primary
} else {
alias
};
match object.get(field).and_then(Value::as_str) {
Some(endpoint) if declared.contains(endpoint) => {}
Some(endpoint) => match norm_to_id.get(&ids::normalize_id(endpoint)) {
Some(canonical) => {
object.insert(field.into(), json!(canonical));
}
None => {
attached = false;
break;
}
},
None => {
attached = false;
break;
}
}
}
if attached {
for (primary, alias) in [("source", "from"), ("target", "to")] {
let endpoint = object.get(primary).or_else(|| object.get(alias));
if let Some(key) = scalar_key(endpoint.unwrap_or(&Value::Null)) {
referenced.insert(key);
}
}
kept.push(edge);
}
}
data[key] = Value::Array(kept);
for hyperedge in data
.get("hyperedges")
.and_then(Value::as_array)
.into_iter()
.flatten()
.filter_map(Value::as_object)
{
let members = hyperedge
.get("nodes")
.or_else(|| hyperedge.get("members"))
.or_else(|| hyperedge.get("node_ids"));
for member in members
.and_then(Value::as_array)
.into_iter()
.flatten()
.filter_map(Value::as_str)
{
referenced.insert(python_compat::ScalarKey::Text(member.to_owned()));
}
}
if let Some(nodes) = data["nodes"].as_array_mut() {
nodes.retain(|n| {
!is_external_stub(n)
|| scalar_key(n.get("id").unwrap_or(&Value::Null))
.is_some_and(|id| referenced.contains(&id))
});
}
}
/// The normalized method name of an AST `.name()` label (#3705).
fn method_name(label: &str) -> String {
let stem = label.strip_prefix('.').unwrap_or(label);
ids::make_id([stem.strip_suffix("()").unwrap_or(stem)])
}
/// `_alias_index` (Graphify 0.9.95, #4670): every old-stem spelling of a
/// node mapped to that node's id. A file's pre-migration node id was keyed on
/// its stem (`Kit/Event/ToolEvent.h` was `toolevent`, now
/// `kit_event_toolevent`, #1504/#1509), so each node registers its old-stem
/// forms, normalized and raw. An alias is committed only when exactly one
/// node claims it: `ping.h` and `ping.php` in different folders both alias
/// to `ping`. A Python module whose bare stem is a stdlib name
/// (`scripts/logging.py`) never claims the bare-stem alias (0.9.84, #4261).
/// Shared by the clustered build and [`finalize_raw_graph_endpoints`].
fn alias_index<'a, P: Properties + 'a>(
nodes: impl IntoIterator<Item = (&'a str, &'a P)>,
) -> FxHashMap<String, String> {
let mut aliases = FxHashMap::<String, BTreeSet<String>>::default();
// A file's stem id, name and former stems, derived once per file rather
// than for each of its nodes.
let mut files = HashMap::<String, (String, String, Vec<String>, bool)>::new();
for (nid, attributes) in nodes {
let Some(sf) = attributes.get("source_file").filter(|v| truthy(v)) else {
continue;
};
let sf = python_compat::string(sf);
if crate::paths::is_absolute_any_platform(Some(&sf)) {
continue;
}
let (stem, file_name, olds, py_stdlib_stem) = files.entry(sf).or_insert_with_key(|sf| {
let rel = Path::new(sf);
let name = rel
.file_name()
.unwrap_or_default()
.to_string_lossy()
.into_owned();
// The directory-scoped alias ("scripts_logging") is still registered.
let py_stdlib_stem =
matches!(crate::detect_types::suffix(rel).as_str(), ".py" | ".pyi")
&& is_python_stdlib_module(&ids::make_id([crate::detect_types::stem(&name)]));
(
ids::make_id([base::file_stem(rel)]),
name,
old_file_stems(rel),
py_stdlib_stem,
)
});
if stem.is_empty() {
continue;
}
let py_stdlib_stem = *py_stdlib_stem;
let stem = &*stem;
let normalized_id = ids::normalize_id(nid);
let suffix = if value_string(attributes, "label") == *file_name {
""
} else {
normalized_id.strip_prefix(stem).unwrap_or("")
};
for old in olds.iter() {
if old == stem || (py_stdlib_stem && is_python_stdlib_module(old)) {
continue;
}
let alias = format!("{old}{suffix}");
aliases
.entry(ids::normalize_id(&alias))
.or_default()
.insert(nid.into());
aliases.entry(alias).or_default().insert(nid.into());
}
if attributes.get("_origin").is_some_and(|v| v == "ast") {
let label = value_string(attributes, "label");
if label.starts_with('.') {
// #3705: `<file_stem>_<method>` alias for AST `.name()` nodes.
let m_alias = format!(
"{stem}_{}",
method_name(label.trim_matches(dedup_strings::whitespace))
);
if normalized_id != ids::normalize_id(&m_alias) {
aliases
.entry(ids::normalize_id(&m_alias))
.or_default()
.insert(nid.into());
aliases.entry(m_alias).or_default().insert(nid.into());
}
}
}
}
aliases
.into_iter()
.filter(|(_, candidates)| candidates.len() == 1)
.map(|(alias, candidates)| (alias, candidates.into_iter().next().unwrap()))
.collect()
}
/// `has_parallel_links` (Graphify 0.9.92, #4500): whether two link records
/// share their endpoints, as an unordered pair when `directed` is false. Keeps
/// a serialized `multigraph` flag consistent with the links stored: readers
/// that honour the flag otherwise collapse the parallel edges on load.
pub fn has_parallel_links<'a>(links: impl IntoIterator<Item = &'a Value>, directed: bool) -> bool {
let mut seen = BTreeSet::new();
for link in links.into_iter().filter_map(Value::as_object) {
let endpoint = |k: &str| scalar_key(link.get(k).unwrap_or(&Value::Null));
let (Some(source), Some(target)) = (endpoint("source"), endpoint("target")) else {
continue;
};
let pair = if directed || source <= target {
(source, target)
} else {
(target, source)
};
if !seen.insert(pair) {
return true;
}
}
false
}
/// The load-time repair of the MCP loader (`_load_graph`, Graphify 0.9.92,
/// #4500), for every reader of a saved graph.json: a document whose `links`
/// hold two records on one pair is read as a multigraph, whatever its
/// `multigraph` flag says. Writers before 0.9.92 restored such links with the
/// flag `false`, so without this a file read the same links collapsed or kept
/// depending on the release that wrote it. Pairs compare as the document's
/// `directed` flag says; readers that force `directed` set it first.
pub fn mark_parallel_links(data: &mut Value) {
let directed = data
.get("directed")
.and_then(Value::as_bool)
.unwrap_or(false);
if data
.get("links")
.and_then(Value::as_array)
.is_some_and(|links| has_parallel_links(links, directed))
{
data["multigraph"] = json!(true);
}
}
/// `_fold_type_only` for a stored edge and an incoming one ([`execution_wins`]).
fn fold_type_only<R: Record>(prior: &mut Attributes, incoming: &mut R) {
if prior.get("type_only").is_some_and(truthy) != incoming.get("type_only").is_some_and(truthy) {
prior.shift_remove("type_only");
incoming.take_key("type_only");
}
}
pub fn disambiguate_file_node_labels(graph: &mut Graph) {
let items: Vec<_> = graph
.nodes
.iter()
.map(|n| {
(
n.id.clone(),
n.attributes.get("label").cloned().unwrap_or(Value::Null),
n.attributes
.get("source_file")
.cloned()
.unwrap_or(Value::Null),
)
})
.collect();
for (id, label) in file_label_reassignments(&items) {
if let Some(i) = graph.node_index(&id) {
graph.nodes[i]
.attributes
.insert("label".into(), json!(label));
}
}
}
fn family(extension: &str) -> Option<&'static str> {
Some(match extension {
".py" | ".pyi" => "py",
".js" | ".mjs" | ".cjs" | ".jsx" | ".ts" | ".tsx" | ".mts" | ".cts" => "js",
".go" => "go",
".rs" => "rs",
".java" | ".kt" | ".scala" | ".groovy" => "jvm",
".c" | ".h" | ".cc" | ".cpp" | ".hpp" | ".cxx" | ".hh" | ".hxx" | ".cu" | ".cuh"
| ".metal" | ".m" | ".mm" => "c",
".rb" | ".rake" => "rb",
".php" => "php",
".cs" => "cs",
".swift" => "swift",
".lua" => "lua",
_ => return None,
})
}
fn normalized_file_type(value: &Value) -> Result<Value> {
if value.is_null() || value.as_str() == Some("") {
return Ok(json!("concept"));
}
let ft = value.as_str().ok_or("Expected file_type string")?;
if validate::VALID_FILE_TYPES.contains(&ft) {
return Ok(value.clone());
}
Ok(json!(match ft {
"markdown" | "text" => "document",
"tool" | "library" => "code",
_ => "concept",
}))
}
fn numeric_field(value: &Value) -> f64 {
let number = match value {
Value::Number(v) => v.as_f64(),
Value::Bool(v) => Some(u8::from(*v) as f64),
Value::String(s) => {
let s: String = s
.trim_matches(dedup_strings::whitespace)
.chars()
.map(|c| {
let ranges = crate::decimal_data::DECIMAL;
let i = ranges.partition_point(|&(lo, _)| lo <= c as u32);
if i > 0 && c as u32 <= ranges[i - 1].1 {
char::from_u32('0' as u32 + (c as u32 - ranges[i - 1].0) % 10).unwrap()
} else {
c
}
})
.collect();
let bytes = s.as_bytes();
if bytes.iter().enumerate().any(|(i, &b)| {
b == b'_'
&& (i == 0
|| i + 1 == bytes.len()
|| !bytes[i - 1].is_ascii_digit()
|| !bytes[i + 1].is_ascii_digit())
}) {
None
} else {
s.replace('_', "").parse::<f64>().ok()
}
}
_ => None,
};
number.filter(|n| n.is_finite() && *n >= 0.0).unwrap_or(1.0)
}
fn value_string(attributes: &impl crate::record::Properties, key: &str) -> String {
attributes
.get(key)
.map(python_compat::string)
.unwrap_or_default()
}
fn remap_extraction<R: Record, E: EdgeItem<Record = R>>(
extraction: &mut Value,
edges: &mut Vec<E>,
remap: &BTreeMap<String, String>,
remove_nodes: bool,
) {
if remap.is_empty() {
return;
}
if let Some(nodes) = extraction.get_mut("nodes").and_then(Value::as_array_mut) {
if remove_nodes {
nodes.retain(|n| !n["id"].as_str().is_some_and(|s| remap.contains_key(s)));
} else {
for node in nodes {
if let Some(new) = node["id"].as_str().and_then(|s| remap.get(s)) {
node["id"] = json!(new);
}
}
}
}
edges.retain_mut(|e| {
let Some(e) = e.record_mut() else {
return true;
};
let mut changed = false;
for field in ["source", "target"] {
if let Some(new) = e
.get(field)
.and_then(Value::as_str)
.and_then(|s| remap.get(s))
{
e.put(field, json!(new));
changed = true;
}
}
let null = &Value::Null;
!(remove_nodes
&& changed
&& e.get("source").unwrap_or(null) == e.get("target").unwrap_or(null))
});
for he in extraction
.get_mut("hyperedges")
.and_then(Value::as_array_mut)
.into_iter()
.flatten()
{
for member in he
.get_mut("nodes")
.and_then(Value::as_array_mut)
.into_iter()
.flatten()
{
if let Some(new) = member.as_str().and_then(|s| remap.get(s)) {
*member = json!(new);
}
}
}
}
/// Whether a new edge with the same relation as `old` should be dropped:
/// lower confidence rank, or equal rank while losing a source location or a
/// lower confidence score.
fn same_relation_is_weaker(
old: &dyn crate::record::Properties,
new: &dyn crate::record::Properties,
) -> bool {
let rank = |attributes: &dyn crate::record::Properties| match attributes
.get("confidence")
.and_then(Value::as_str)
{
Some("EXTRACTED") => 3,
Some("INFERRED") => 2,
Some("AMBIGUOUS") => 1,
_ => 0,
};
let old_rank = rank(old);
let new_rank = rank(new);
old_rank > new_rank
|| (old_rank == new_rank
&& (old.get("source_location").is_some_and(truthy)
&& !new.get("source_location").is_some_and(truthy)
|| old
.get("confidence_score")
.and_then(Value::as_f64)
.zip(new.get("confidence_score").and_then(Value::as_f64))
.is_some_and(|(old, new)| old > new)))
}
pub fn build_from_json(
extraction: &mut Value,
directed: bool,
root: Option<&Path>,
messages: &mut Diagnostics,
) -> Result<Graph> {
build_from_json_with(extraction, directed, false, root, messages)
}
/// [`build_from_json`] of an extraction the caller no longer reads: its node
/// and edge records move into the graph instead of being copied, so the
/// graph is built without a second copy of them (the rebuild in `watch`).
/// The graph is the same; the extraction is left without its records.
pub fn build_from_json_consuming(
extraction: &mut Value,
directed: bool,
root: Option<&Path>,
messages: &mut Diagnostics,
) -> Result<Graph> {
build_from_json_core(extraction, directed, false, root, messages, true, true)
}
/// `build_from_json` with the multigraph choice explicit: when `multigraph`
/// is set, edges are keyed by relation so that distinct relations between the
/// same pair survive; same-relation duplicates still fold by confidence.
pub fn build_from_json_with(
extraction: &mut Value,
directed: bool,
multigraph: bool,
root: Option<&Path>,
messages: &mut Diagnostics,
) -> Result<Graph> {
build_from_json_dedup(extraction, directed, multigraph, true, root, messages)
}
/// `build_from_json(..., dedup=False)` (0.9.77): with `dedup` off, distinct
/// non-AST IDs that merely share a file and label are kept apart.
pub fn build_from_json_dedup(
extraction: &mut Value,
directed: bool,
multigraph: bool,
dedup: bool,
root: Option<&Path>,
messages: &mut Diagnostics,
) -> Result<Graph> {
build_from_json_core(
extraction, directed, multigraph, root, messages, false, dedup,
)
}
/// Shared body of [`build_from_json_dedup`] and [`build_owned`]. With
/// `consume`, the node and edge records are moved out of `extraction` into
/// the graph instead of cloned; callers that read the extraction afterwards
/// pass `false` and see it exactly as before. `dedup: false` (0.9.77) keeps
/// distinct non-AST IDs that merely share a file and label; AST twins and
/// document-file twins still reconcile.
fn build_from_json_core(
extraction: &mut Value,
directed: bool,
multigraph: bool,
root: Option<&Path>,
messages: &mut Diagnostics,
consume: bool,
dedup: bool,
) -> Result<Graph> {
if !extraction.is_object() {
return Err("Expected extraction object".into());
}
let root = resolve_root(root)?;
if extraction.get("edges").is_none()
&& let Some(links) = extraction.get("links").cloned()
{
extraction["edges"] = links;
}
// The passes hold the edge list beside the rest of the extraction
// ([`build_core`]); it goes back afterwards, emptied when consumed.
let mut edges = match extraction.get_mut("edges") {
Some(Value::Array(edges)) => std::mem::take(edges),
_ => Vec::new(),
};
let graph = build_core(
extraction,
&mut edges,
directed,
multigraph,
root.as_deref(),
messages,
consume,
dedup,
);
if let Some(Value::Array(slot)) = extraction.get_mut("edges") {
*slot = edges;
}
graph
}
/// A build's root, resolved; `None` for an absent or empty one.
fn resolve_root(root: Option<&Path>) -> Result<Option<PathBuf>> {
root.filter(|p| !p.as_os_str().is_empty())
.map(fsutil::resolve_missing)
.transpose()
.map_err(crate::Error::from)
}
/// The build passes over an extraction whose edge list is held beside it:
/// JSON values, or the compact records an extract assembled. Every pass reads
/// and edits an edge record exactly as it would the same edge as a JSON
/// object, so both forms build the same graph; records move into the graph
/// with no JSON copy. `extraction` holds the nodes and hyperedges, and an
/// empty `edges` array when its edges are in `edges`.
#[allow(clippy::too_many_arguments)]
fn build_core<R: Record, E: EdgeItem<Record = R>>(
extraction: &mut Value,
edges: &mut Vec<E>,
directed: bool,
multigraph: bool,
root: Option<&Path>,
messages: &mut Diagnostics,
consume: bool,
dedup: bool,
) -> Result<Graph> {
if extraction.get("hyperedges").is_none()
&& let Some(hyper) = extraction["graph"]["hyperedges"].as_array()
{
extraction["hyperedges"] = json!(hyper);
}
let profiled = crate::profile::span("build.core.prepare");
coerce_non_string_ids(extraction);
for edge in edges.iter_mut() {
if let Some(e) = edge.record_mut() {
coerce_edge_record_ids(e);
}
}
for node in extraction
.get_mut("nodes")
.and_then(Value::as_array_mut)
.into_iter()
.flatten()
{
let Some(n) = node.as_object_mut() else {
continue;
};
if n.contains_key("source") && !n.contains_key("source_file") {
let nid = n.get("id").cloned().unwrap_or(json!("?"));
let affected = edges
.iter()
.filter(|e| *item_field(*e, "source") == nid || *item_field(*e, "target") == nid)
.count();
messages.stderr.push(format!("[graphicle] WARNING: node '{}' uses field 'source' instead of 'source_file' — {affected} edge(s) may be misrouted. Rename the field to 'source_file' to silence this warning.",python_compat::string(&nid)));
let source = n.shift_remove("source").unwrap();
n.insert("source_file".into(), source);
}
fold_node_aliases(node);
node["file_type"] = normalized_file_type(&node["file_type"])?;
}
// A hyperedge carries the same confidence pair an edge does, and folds the
// same legacy or drifted values (Graphify 0.9.92, #4495).
for he in extraction
.get_mut("hyperedges")
.and_then(Value::as_array_mut)
.into_iter()
.flatten()
{
messages.stderr.extend(hyperedge_members::normalize(he));
if let Some(he) = he.as_object_mut() {
fold_confidence(he);
}
}
for edge in edges.iter_mut() {
if let Some(e) = edge.record_mut() {
fold_edge_record_aliases(e);
}
}
drop(profiled);
let profiled = crate::profile::span("build.core.validate");
// Dangling endpoints are expected here (they become external stubs or
// are dropped below), so their diagnostics are not built at all.
let errors = validate::validate_extraction_beside(extraction, edges, false)?;
drop(profiled);
let errors: Vec<_> = errors
.into_iter()
.filter(|e| !e.contains("does not match any node id"))
.collect();
if !errors.is_empty() {
let mut causes: Vec<(String, Vec<&str>)> = Vec::new();
let mut indices = HashMap::new();
for error in &errors {
let cause = error
.find("missing required field '")
.map(|i| {
let tail = &error[i..];
let end = tail[24..]
.find('\'')
.map(|j| 24 + j + 1)
.unwrap_or(tail.len());
tail[..end].to_owned()
})
.unwrap_or_else(|| "other schema issue".into());
let next = causes.len();
let i = *indices.entry(cause.clone()).or_insert_with(|| {
causes.push((cause, Vec::new()));
next
});
causes[i].1.push(error);
}
let breakdown = causes
.iter()
.map(|(cause, errs)| format!("{}x {cause} (e.g. {})", errs.len(), errs[0]))
.collect::<Vec<_>>()
.join("; ");
messages.stderr.push(format!(
"[graphicle] Extraction warning ({} issues): {breakdown}",
errors.len()
));
}
let profiled = crate::profile::span("build.core.remap");
let rekey = semantic_id_remap(
extraction["nodes"]
.as_array()
.map(Vec::as_slice)
.unwrap_or(&[]),
root,
);
remap_extraction(extraction, edges, &rekey, false);
let twins = doc_twin_remap(
extraction["nodes"]
.as_array()
.map(Vec::as_slice)
.unwrap_or(&[]),
);
remap_extraction(extraction, edges, &twins, true);
drop(profiled);
let profiled = crate::profile::span("build.core.add_nodes");
let mut graph = Graph::new(directed, multigraph);
for node in extraction
.get_mut("nodes")
.and_then(Value::as_array_mut)
.into_iter()
.flatten()
{
let n = node.as_object_mut().ok_or("Node must be an object")?;
let Some(nid) = map_field(n, "id").cloned() else {
continue;
};
if scalar_key(&nid).is_none() {
messages.stderr.push(format!(
"[graphicle] WARNING: skipping node with non-hashable id {} (must be a string).",
python_compat::repr(&nid)
));
continue;
}
for key in ["source_file", "definition_file"] {
if let Some(value) = map_field_mut(n, key) {
*value = norm_source_file(value, root)?;
}
}
let mut attrs = if consume {
std::mem::take(n)
} else {
n.clone()
};
attrs.shift_remove("id");
graph.add_node(nid, attrs)?;
}
drop(profiled);
let profiled = crate::profile::span("build.core.ghosts_aliases");
let norm_to_id = ghosts_and_aliases(&mut graph, dedup)?;
drop(profiled);
let profiled = crate::profile::span("build.core.edges");
let edges = if consume {
std::mem::take(edges)
} else {
edges.clone()
};
add_edges(
&mut graph,
edges,
&norm_to_id,
directed,
multigraph,
root,
messages,
)?;
drop(profiled);
if let Some(hyperedges) = extraction
.get_mut("hyperedges")
.and_then(Value::as_array_mut)
.filter(|h| !h.is_empty())
{
let mut kept = Vec::new();
for he in hyperedges.iter_mut() {
if let Some(sf) = he.get_mut("source_file").filter(|v| truthy(v)) {
*sf = norm_source_file(sf, root)?;
}
if let Some(members) = he["nodes"].as_array() {
let mut valid = Vec::new();
for raw in members {
if scalar_key(raw).is_none() {
continue;
}
let mut member = raw.clone();
if graph.node_index(&member).is_none()
&& let Some(s) = member.as_str()
&& let Some(id) = norm_to_id.get(&ids::normalize_id(s))
{
member = json!(id);
}
if graph.node_index(&member).is_some() {
valid.push(member);
}
}
if valid.is_empty() {
messages.stderr.push(format!("[graphicle] WARNING: dropping hyperedge {} — none of its members {} match built nodes.",python_compat::repr(he.get("id").unwrap_or(&json!("?"))),python_compat::repr(&he["nodes"])));
continue;
}
he["nodes"] = json!(valid);
}
kept.push(he.clone());
}
if kept.is_empty() {
messages.stderr.push(format!("[graphicle] WARNING: all {} hyperedge(s) were dropped by member revalidation; graph.json's hyperedge set will be emptied on the next export.",hyperedges.len()));
}
graph.attributes["hyperedges"] = json!(kept);
}
let profiled = crate::profile::span("build.core.file_labels");
disambiguate_file_node_labels(&mut graph);
drop(profiled);
Ok(graph)
}
/// Fold semantic ghosts into the AST nodes they shadow (removing them from
/// `graph`), and the table edge endpoints resolve through: normalized ids,
/// ghost ids and file-stem aliases, each to its canonical node id.
fn ghosts_and_aliases(graph: &mut Graph, dedup: bool) -> Result<FxHashMap<String, String>> {
// Node indices are stable until `remove_nodes_from` below, so the
// sorted pass can address attributes directly instead of re-hashing ids.
let mut sorted_nodes = graph
.nodes
.iter()
.enumerate()
.map(|(i, n)| {
n.id.as_str()
.map(|id| (id.to_owned(), i))
.ok_or("Graph node IDs must be strings")
})
.collect::<std::result::Result<Vec<_>, _>>()?;
sorted_nodes.sort_by(|a, b| a.0.cmp(&b.0));
// `located`, `collisions`, `ast_methods`, `norm_to_id` and `aliases` are
// only looked up (or visited where each key is handled once), so hash
// tables give the same result as ordered maps without string comparisons;
// `ghosts` stays ordered because its visiting order decides overrides.
let mut located = FxHashMap::<(String, String), String>::default();
let mut collisions = FxHashSet::default();
let mut ghosts_by_key = BTreeMap::<(String, String), String>::new();
let mut ast_files = Vec::new();
// #3705: (source_file, normalized method name) -> AST `.name()` nodes.
let mut ast_methods = FxHashMap::<(String, String), Vec<String>>::default();
let mut method_ghosts = BTreeMap::<String, String>::new();
for (nid, index) in &sorted_nodes {
let attributes = &graph.nodes[*index].attributes;
let label = value_string(attributes, "label")
.trim_matches(dedup_strings::whitespace)
.to_owned();
let sf = value_string(attributes, "source_file");
if label.is_empty() || sf.is_empty() {
continue;
}
let ast = attributes.get("_origin").is_some_and(|v| v == "ast");
if attributes.get("source_location").is_some_and(truthy) || ast {
let key = (sf.clone(), label.clone());
if ast {
if located
.get(&key)
.and_then(|id| graph.node_index(&json!(id)))
.is_some_and(|i| {
graph.nodes[i]
.attributes
.get("_origin")
.is_some_and(|v| v == "ast")
})
{
collisions.insert(key.clone());
}
located.insert(key, nid.clone());
if label.starts_with('.') && label.ends_with("()") {
ast_methods
.entry((sf.clone(), method_name(&label)))
.or_default()
.push(nid.clone());
}
if crate::build_labels::is_file_node_label_str(&label, &sf) {
ast_files.push((nid.clone(), sf));
}
} else {
located.entry(key).or_insert_with(|| nid.clone());
}
}
}
for (nid, index) in &sorted_nodes {
let attributes = &graph.nodes[*index].attributes;
if attributes.get("_origin").is_some_and(|v| v == "ast") {
continue;
}
let label = value_string(attributes, "label")
.trim_matches(dedup_strings::whitespace)
.to_owned();
let sf = value_string(attributes, "source_file");
if label.is_empty() || sf.is_empty() {
continue;
}
let key = (sf, label);
if collisions.contains(&key) {
continue;
}
if let Some(canonical) = located.get(&key).filter(|n| *n != nid) {
if !dedup
&& graph.node_index(&json!(canonical)).is_none_or(|i| {
graph.nodes[i]
.attributes
.get("_origin")
.is_none_or(|v| v != "ast")
})
{
continue;
}
ghosts_by_key.insert(key, nid.clone());
} else if !located.contains_key(&key) {
// #3705: spec-conformant method ghost that omits the class
// segment / leading dot; remap only on one unambiguous candidate.
let candidates = ast_methods.get(&(key.0.clone(), method_name(&key.1)));
if let Some([canonical]) = candidates.map(Vec::as_slice) {
method_ghosts.insert(nid.clone(), canonical.clone());
}
}
}
let mut ghosts = method_ghosts;
for (key, sem) in ghosts_by_key {
if let Some(ast) = located.get(&key) {
ghosts.insert(sem, ast.clone());
}
}
for (nid, index) in &sorted_nodes {
if ghosts.contains_key(nid) {
continue;
}
let attributes = &graph.nodes[*index].attributes;
if attributes.get("_origin").is_some_and(|v| v == "ast") {
continue;
}
let label = value_string(attributes, "label")
.trim_matches(dedup_strings::whitespace)
.to_owned();
if label.is_empty() {
continue;
}
let matches: BTreeSet<_> = ast_files
.iter()
.filter(|(_, sf)| crate::build_labels::is_file_node_label_str(&label, sf))
.map(|(n, _)| n.clone())
.collect();
if matches.len() == 1 {
ghosts.insert(nid.clone(), matches.into_iter().next().unwrap());
}
}
graph.remove_nodes_from(&ghosts.keys().map(|s| json!(s)).collect::<Vec<_>>())?;
let mut norm_to_id = FxHashMap::<String, String>::default();
// Stable order resolves the reference's hash-order ambiguity when two IDs
// have the same normalized spelling; no insertion is allowed to mint a node.
for (nid, _) in &sorted_nodes {
if graph.node_index(&json!(nid)).is_some() {
norm_to_id.insert(ids::normalize_id(nid), nid.clone());
}
}
for (ghost, canonical) in &ghosts {
norm_to_id.insert(ids::normalize_id(ghost), canonical.clone());
norm_to_id.insert(ghost.clone(), canonical.clone());
}
// The index lives in [`alias_index`] so the raw (`--no-cluster`) write
// path resolves endpoints identically (Graphify 0.9.95, #4670).
let index = alias_index(
graph
.nodes
.iter()
.filter_map(|node| Some((node.id.as_str()?, &node.attributes))),
);
for (alias, canonical) in index {
norm_to_id.entry(alias).or_insert(canonical);
}
Ok(norm_to_id)
}
/// The fields an edge is ordered by: source, target and relation, an
/// endpoint read from its alias (`from`, `to`) when absent.
const ORDER_FIELDS: [(&str, Option<&str>); 3] = [
("source", Some("from")),
("target", Some("to")),
("relation", None),
];
/// An edge's order texts as [`python_compat::string`] gives them, borrowed
/// from the edge (`""` for an absent field, and for an item that is no
/// record); `None` when one is no string, whose text is not stored.
fn order_texts<E: EdgeItem>(edge: &E) -> Option<[&str; 3]> {
let Some(record) = edge.record() else {
return Some([""; 3]);
};
let mut texts = [""; 3];
for (text, (key, alias)) in texts.iter_mut().zip(ORDER_FIELDS) {
match record
.get(key)
.or_else(|| alias.and_then(|a| record.get(a)))
{
None => {}
Some(Value::String(s)) => *text = s.as_str(),
Some(_) => return None,
}
}
Some(texts)
}
/// The indices of `edges` in the order the build adds them: stable by the
/// source, target and relation texts (`sorted(edges, key=...)`). Each key is
/// built once and borrows the edge's own strings; ties keep the list order.
fn edge_order<E: EdgeItem>(edges: &[E]) -> Vec<usize> {
let mut keyed = Vec::with_capacity(edges.len());
for (i, edge) in edges.iter().enumerate() {
let Some(texts) = order_texts(edge) else {
break;
};
keyed.push((texts, i));
}
if keyed.len() == edges.len() {
keyed.sort_unstable();
return indices(&keyed);
}
drop(keyed);
// Some text is no string: its Python spelling, built for every edge.
let mut keyed = edges
.iter()
.enumerate()
.map(|(i, edge)| {
let texts = ORDER_FIELDS.map(|(key, alias)| {
edge.record()
.and_then(|r| r.get(key).or_else(|| alias.and_then(|a| r.get(a))))
.map(python_compat::string)
.unwrap_or_default()
});
(texts, i)
})
.collect::<Vec<_>>();
keyed.sort_unstable();
indices(&keyed)
}
/// The indices of sorted `(key, index)` pairs, in a list of their own size
/// (collecting the pairs in place would keep the pairs' allocation).
fn indices<K>(keyed: &[(K, usize)]) -> Vec<usize> {
let mut order = Vec::with_capacity(keyed.len());
order.extend(keyed.iter().map(|(_, i)| *i));
order
}
/// Add `edges` in the build's order ([`edge_order`]) under the endpoint,
/// provenance and duplicate rules.
fn add_edges<R: Record, E: EdgeItem<Record = R>>(
graph: &mut Graph,
mut edges: Vec<E>,
norm_to_id: &FxHashMap<String, String>,
directed: bool,
multigraph: bool,
root: Option<&Path>,
messages: &mut Diagnostics,
) -> Result<()> {
let order = edge_order(&edges);
// Each record adds at most one edge slot, so the edge list is allocated
// once instead of doubling (each doubling copies every slot while the
// old and the new list are both live).
graph.reserve_edges(edges.len());
for i in order {
// Each edge is taken out of the list once: its attributes move into
// the graph instead of being copied.
let edge = std::mem::take(&mut edges[i]);
let mut attrs = edge.into_record().ok_or("Edge must be an object")?;
for (key, alias) in [("source", "from"), ("target", "to")] {
if attrs.get(key).is_none()
&& let Some(value) = attrs.get(alias).cloned()
{
attrs.put(key, value);
}
}
let (Some(mut src), Some(mut tgt)) =
(attrs.get("source").cloned(), attrs.get("target").cloned())
else {
continue;
};
if scalar_key(&src).is_none() || scalar_key(&tgt).is_none() {
messages.stderr.push(format!("[graphicle] WARNING: skipping edge with non-hashable endpoint (source={}, target={}).",python_compat::repr(&src),python_compat::repr(&tgt)));
continue;
}
let mut u = graph.node_index(&src);
let mut v = graph.node_index(&tgt);
for (endpoint, index) in [(&mut src, &mut u), (&mut tgt, &mut v)] {
if index.is_none() {
let id = endpoint.as_str().ok_or("Expected string edge endpoint")?;
if let Some(new) = norm_to_id.get(&ids::normalize_id(id)) {
*endpoint = json!(new);
*index = graph.node_index(endpoint);
}
}
}
let relation = attrs
.get("relation")
.and_then(Value::as_str)
.unwrap_or("")
.to_owned();
let relation = relation.as_str();
if u.is_none() || v.is_none() {
if EXTERNAL_STUB_RELATIONS.contains(&relation)
&& u.is_some()
&& v.is_none()
&& tgt.is_string()
{
mint_external_stub(graph, tgt.as_str().unwrap())?;
v = graph.node_index(&tgt);
} else {
continue;
}
}
let (Some(u), Some(v)) = (u, v) else {
continue;
};
for key in ["source", "target", "target_file", "local_alias"] {
// The last two are rare: skip hashing the key when absent.
if attrs.get(key).is_some() {
attrs.take_key(key);
}
}
for key in ["weight", "confidence_score"] {
if let Some(value) = attrs.get(key) {
let value = json!(numeric_field(value));
attrs.put(key, value);
}
}
if !attrs.get("source_file").is_some_and(truthy) {
let sf = graph.nodes[u]
.attributes
.get("source_file")
.filter(|v| truthy(v))
.or_else(|| {
graph.nodes[v]
.attributes
.get("source_file")
.filter(|v| truthy(v))
})
.cloned()
.unwrap_or(json!(""));
attrs.put("source_file", sf);
}
if let Some(sf) = attrs.get("source_file") {
let sf = norm_source_file(sf, root)?;
attrs.put("source_file", sf);
}
if let Some(sf) = attrs.get("definition_file").filter(|v| truthy(v)) {
let sf = norm_source_file(sf, root)?;
attrs.put("definition_file", sf);
}
if ["calls", "imports", "imports_from", "references"].contains(&relation) {
let ext = |i: usize| {
let path = graph.nodes[i]
.attributes
.get("source_file")
.and_then(Value::as_str)
.unwrap_or("");
crate::detect_types::suffix(Path::new(path))
};
let a = ext(u);
let b = ext(v);
let (fa, fb) = (family(&a), family(&b));
if relation == "calls" {
if attrs.get("confidence").is_some_and(|v| v == "INFERRED")
&& !a.is_empty()
&& !b.is_empty()
&& fa != fb
{
continue;
}
} else if fa.is_some() && fb.is_some() && fa != fb {
continue;
}
}
if src == tgt && EXTERNAL_STUB_RELATIONS.contains(&relation) {
continue;
}
attrs.put("_src", src.clone());
attrs.put("_tgt", tgt.clone());
// Before the drops below, so a runtime import that folds into a
// type-only edge still clears its marker (0.9.80, #3159). The reverse
// duplicate an undirected graph drops (#1061) is another file's import:
// the surviving edge keeps its own marker.
if EXTERNAL_STUB_RELATIONS.contains(&relation) {
let key = multigraph.then(|| json!(relation));
if let Some(prior) = graph.edge_attributes_mut(&src, &tgt, key.as_ref()) {
let reverse_duplicate = !directed
&& prior.get("relation") == attrs.get("relation")
&& prior.get("_src") == Some(&tgt)
&& prior.get("_tgt") == Some(&src);
if prior
.get("relation")
.and_then(Value::as_str)
.is_some_and(|r| EXTERNAL_STUB_RELATIONS.contains(&r))
&& !reverse_duplicate
{
fold_type_only(prior, &mut attrs);
}
}
}
if multigraph {
let is_generic = |edge: &&crate::graph::Edge| {
edge.attributes
.get("relation")
.and_then(Value::as_str)
.is_some_and(|r| GENERIC_RELATIONS.contains(&r))
};
let key = json!(relation);
let parallel = graph.edges_between(&src, &tgt);
// A generic relation adds nothing beside a specific one, whichever
// arrives first; same-relation duplicates fold as in the parity path.
if GENERIC_RELATIONS.contains(&relation) && parallel.iter().any(|e| !is_generic(e)) {
continue;
}
if let Some(existing) = parallel.iter().find(|e| e.key == key) {
let old = &existing.attributes;
if !directed && old.get("_src") == Some(&tgt) && old.get("_tgt") == Some(&src) {
continue;
}
if same_relation_is_weaker(old, &attrs) {
continue;
}
}
let superseded: Vec<Value> = if GENERIC_RELATIONS.contains(&relation) {
Vec::new()
} else {
parallel
.iter()
.filter(|e| is_generic(e))
.map(|e| e.key.to_value())
.collect()
};
for generic in &superseded {
graph.remove_edge(&src, &tgt, Some(generic))?;
}
graph.add_edge(src, tgt, Some(key), attrs)?;
continue;
}
if let Some(existing) = graph.edges_between(&src, &tgt).first() {
let old = &existing.attributes;
let reverse = old.get("_src") == Some(&tgt) && old.get("_tgt") == Some(&src);
if !directed && reverse && old.get("relation") == attrs.get("relation") {
continue;
}
// Different relations in opposite directions only share a pair
// because the graph is undirected: a type's `method`/`contains`
// edge beats its member's `calls` edge back (0.9.83, #4256). If
// the call is stored first, the membership edge replaces it below.
if !directed
&& reverse
&& old
.get("relation")
.and_then(Value::as_str)
.is_some_and(|r| STRUCTURAL_MEMBER_RELATIONS.contains(&r))
&& relation == "calls"
{
continue;
}
if GENERIC_RELATIONS.contains(&relation)
&& old.get("relation").is_some_and(|v| !v.is_null())
&& !old
.get("relation")
.and_then(Value::as_str)
.is_some_and(|s| GENERIC_RELATIONS.contains(&s))
{
continue;
}
if old.get("relation") == attrs.get("relation") && same_relation_is_weaker(old, &attrs)
{
continue;
}
}
graph.add_edge(src, tgt, None, attrs)?;
}
Ok(())
}
pub fn build(
extractions: &[Value],
options: &BuildOptions,
messages: &mut Diagnostics,
client: Option<&mut dyn TiebreakClient>,
) -> Result<Graph> {
build_owned(extractions.to_vec(), options, messages, client)
}
/// The lists of the extractions a build combines, in order, apart from the
/// edges ([`combine`]).
struct Combined {
nodes: Vec<Value>,
hyperedges: Vec<Value>,
/// Receiver-resolution leftovers (`ExtractOptions::receiver_resolution`)
/// ride along as a graph attribute so reports can list them; the parity
/// extraction never carries the key.
unresolved_calls: Vec<Value>,
}
/// The extractions' lists combined in order, and their edges beside them.
fn combine(extractions: Vec<Value>) -> Result<(Combined, Vec<Value>)> {
let mut nodes = Vec::new();
let mut edges = Vec::new();
let mut hyperedges = Vec::new();
let mut unresolved_calls: Vec<Value> = Vec::new();
for extraction in extractions {
let Value::Object(mut extraction) = extraction else {
continue;
};
for (key, target) in [
("nodes", &mut nodes),
("edges", &mut edges),
("hyperedges", &mut hyperedges),
] {
if let Some(values) = extraction.shift_remove(key) {
let Value::Array(values) = values else {
return Err(format!("Expected {key} array").into());
};
if target.is_empty() {
*target = values;
} else {
target.extend(values);
}
}
}
if let Some(Value::Array(values)) = extraction.shift_remove("unresolved_calls") {
unresolved_calls.extend(values);
}
}
Ok((
Combined {
nodes,
hyperedges,
unresolved_calls,
},
edges,
))
}
/// [`build`] over extractions the caller no longer needs: node and edge
/// records are moved into the graph rather than copied, which halves the peak
/// footprint of a large build. Output is identical to [`build`].
pub fn build_owned(
extractions: Vec<Value>,
options: &BuildOptions,
messages: &mut Diagnostics,
client: Option<&mut dyn TiebreakClient>,
) -> Result<Graph> {
let (combined, edges) = combine(extractions)?;
build_combined(combined, edges, options, messages, client)
}
/// [`build_owned`] of one extraction whose edges start with `records`, the
/// compact edge records an extract assembled, held beside it: the graph is
/// the one [`build_owned`] builds with those records as JSON objects in front
/// of the extraction's own edges, but they move into it with no JSON copy,
/// and the extraction's own edges convert to records too.
pub(crate) fn build_owned_records(
extraction: Value,
records: Vec<Attributes>,
options: &BuildOptions,
messages: &mut Diagnostics,
client: Option<&mut dyn TiebreakClient>,
) -> Result<Graph> {
let (combined, json_edges) = combine(vec![extraction])?;
if !json_edges.iter().all(Value::is_object) {
// Only the JSON form holds an edge that is not an object.
let mut edges = Vec::with_capacity(records.len() + json_edges.len());
edges.extend(records.into_iter().map(Value::from));
edges.extend(json_edges);
return build_combined(combined, edges, options, messages, client);
}
let mut edges = records;
edges.reserve_exact(json_edges.len());
edges.extend(
json_edges
.into_iter()
.filter_map(EdgeItem::into_record)
.map(Attributes::from),
);
build_combined(combined, edges, options, messages, client)
}
/// The body of [`build_owned`] over combined lists, with the edges in either
/// form ([`build_core`]).
fn build_combined<R: Record, E: EdgeItem<Record = R>>(
combined: Combined,
mut edges: Vec<E>,
options: &BuildOptions,
messages: &mut Diagnostics,
client: Option<&mut dyn TiebreakClient>,
) -> Result<Graph> {
let Combined {
nodes,
hyperedges,
unresolved_calls,
} = combined;
let mut combined = Map::new();
combined.insert("nodes".into(), Value::Array(nodes));
// The edges are held beside the rest (`build_core`).
combined.insert("edges".into(), Value::Array(Vec::new()));
combined.insert("hyperedges".into(), Value::Array(hyperedges));
let mut combined = Value::Object(combined);
let root = resolve_root(options.root.as_deref())?;
let mut dedup_collapsed = 0;
if options.dedup && !combined["nodes"].as_array().unwrap().is_empty() {
let profiled = crate::profile::span("build.dedup_prepare");
coerce_non_string_ids(&mut combined);
for edge in edges.iter_mut() {
if let Some(e) = edge.record_mut() {
coerce_edge_record_ids(e);
}
}
for node in combined["nodes"].as_array_mut().unwrap() {
fold_node_aliases(node);
if node.is_object() {
for key in ["source_file", "definition_file"] {
if let Some(sf) = node.get_mut(key) {
*sf = norm_source_file(sf, root.as_deref())?;
}
}
}
}
let take = |combined: &mut Value, key: &str| match combined[key].take() {
Value::Array(values) => values,
_ => vec![],
};
let mut hyperedges = take(&mut combined, "hyperedges");
let nodes = take(&mut combined, "nodes");
let before_dedup = nodes.len();
drop(profiled);
let profiled = crate::profile::span("build.dedup");
let (result, deduped) = dedup::deduplicate_records(
nodes,
std::mem::take(&mut edges),
&DedupOptions {
communities: Map::new(),
dedup_llm_backend: options.dedup_llm_backend.clone(),
root: root.clone(),
protected_ids: options.protected_ids.iter().cloned().collect(),
},
Some(&mut hyperedges),
client,
)?;
edges = deduped;
dedup_collapsed = before_dedup.saturating_sub(result.nodes.len());
combined["nodes"] = Value::Array(result.nodes);
combined["hyperedges"] = Value::Array(hyperedges);
messages.stdout.extend(result.stdout);
messages.stderr.extend(result.stderr);
drop(profiled);
}
let _profiled = crate::profile::span("build.core");
// The core resolves the root again, as `build_from_json` does.
let root = resolve_root(root.as_deref())?;
let mut graph = build_core(
&mut combined,
&mut edges,
options.directed,
options.multigraph,
root.as_deref(),
messages,
true,
options.dedup,
)?;
// The extract CLI reads this to tell a dedup shrink from a file deletion
// (#3774); `to_json` never stores it in graph.json.
if dedup_collapsed > 0 {
graph.attributes[DEDUP_COLLAPSED] = json!(dedup_collapsed);
}
if !unresolved_calls.is_empty() {
graph.attributes["unresolved_calls"] = json!(unresolved_calls);
}
Ok(graph)
}
/// Graph attribute: nodes this build's dedup merged away (Graphify #3774).
pub const DEDUP_COLLAPSED: &str = "_dedup_collapsed";
/// Graph attribute: saved nodes a `build_merge` prune removed (Graphify #3774).
pub const PRUNED_NODE_COUNT: &str = "_pruned_node_count";
/// Read and remove the #3774 shrink counters `(dedup collapsed, pruned)` that
/// [`build`] and [`build_merge`] stash on the graph for the extract CLI.
pub fn take_shrink_accounting(graph: &mut Graph) -> (u64, u64) {
let Some(attributes) = graph.attributes.as_object_mut() else {
return (0, 0);
};
let mut take = |key: &str| {
attributes
.shift_remove(key)
.and_then(|v| v.as_u64())
.unwrap_or(0)
};
(take(DEDUP_COLLAPSED), take(PRUNED_NODE_COUNT))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::extract::{self, ExtractOptions};
/// A build's graph (node-link form) and messages, or its error.
fn outcome(result: Result<Graph>, messages: &Diagnostics) -> String {
let graph = match result {
Ok(graph) => serde_json::to_string(&graph.to_node_link("links")).unwrap(),
Err(e) => format!("error: {e}"),
};
format!("{graph}\n{:?}\n{:?}", messages.stdout, messages.stderr)
}
/// Semantic-tier nodes, edges and a hyperedge beside the AST ones, which
/// reach every build pass that reads or edits an edge: endpoint and
/// relation aliases, numeric ids and confidence, a document twin, a dedup
/// merge, an extension collision and a path collision (with a reference
/// that cannot be attributed), a schema warning, a field named `source`
/// and an external stub. `code` is an AST node id they point at.
fn semantic(code: &str) -> (Vec<Value>, Vec<Value>, Vec<Value>) {
let doc = |id: &str, label: &str, file: &str| json!({"id": id, "label": label, "file_type": "document", "source_file": file});
let refs = |source: &str, target: &str, file: &str| {
json!({"source": source, "target": target, "relation": "references",
"confidence": "EXTRACTED", "source_file": file})
};
let nodes = vec![
doc("guide", "Guide", "docs/guide.md"),
doc("guide_doc", "Guide doc", "docs/guide.md"),
json!({"id": "payment_gateway", "label": "Payment Gateway Service",
"file_type": "concept", "source_file": "docs/notes.md"}),
json!({"id": "payment_gateway_2", "label": "payment gateway service",
"file_type": "concept", "source_file": "docs/notes.md", "description": "dup"}),
doc("x_overview", "Overview", "a/x.md"),
doc("x_overview", "Overview", "b/x.md"),
doc("site_page_intro", "Intro", "site/page.md"),
doc("site_page_intro", "Intro", "site/page.html"),
json!({"id": 42, "label": "Answer", "file_type": "concept", "source_file": "docs/notes.md"}),
json!({"id": "legacy", "label": "Legacy", "file_type": "concept", "source": "docs/legacy.md"}),
];
let edges = vec![
refs("guide_doc", "guide", "docs/guide.md"),
json!({"source": "payment_gateway", "target": "payment_gateway_2",
"relation": "semantically_similar_to", "confidence": "INFERRED",
"confidence_score": 0.9, "source_file": "docs/notes.md"}),
json!({"from": "payment_gateway_2", "to": code, "type": "mentions",
"confidence": 0.6, "source_file": "docs/notes.md", "weight": "2"}),
refs("x_overview", "guide", "a/x.md"),
refs("x_overview", "guide", "b/x.md"),
refs("guide", "x_overview", "docs/guide.md"),
refs("site_page_intro", "guide", "site/page.html"),
json!({"source": 42, "target": "guide", "relation": "references",
"confidence": "EXTRACTED", "source_file": "docs/notes.md"}),
json!({"source": "legacy", "target": "guide", "relation": "references",
"source_file": "docs/legacy.md"}),
json!({"source": "guide", "target": "external_mod", "relation": "imports",
"confidence": "EXTRACTED", "source_file": "docs/guide.md"}),
json!({"source": code, "target": "guide", "relation": "references",
"confidence": "INFERRED", "source_file": ""}),
];
let hyperedges = vec![
json!({"id": "flow", "label": "Flow", "relation": "participate_in",
"confidence": "INFERRED", "source_file": "docs/guide.md",
"nodes": ["guide", "x_overview", "payment_gateway_2", 42]}),
];
(nodes, edges, hyperedges)
}
fn with(extraction: &Value, key: &str, items: &[Value]) -> Value {
let mut out = extraction.clone();
let mut all = out[key].as_array().cloned().unwrap_or_default();
all.extend_from_slice(items);
out[key] = Value::Array(all);
out
}
/// The JSON build of `json` against the record build of `beside` with
/// `records` in front of its edges, under several build options.
fn assert_same_builds(json: &Value, beside: &Value, records: &[Attributes], root: &Path) {
for (dedup, directed, multigraph) in [
(true, false, false),
(false, false, false),
(true, true, false),
(true, false, true),
] {
let options = BuildOptions {
dedup,
directed,
multigraph,
root: Some(root.to_path_buf()),
..Default::default()
};
let mut old = Diagnostics::default();
let want = build_owned(vec![json.clone()], &options, &mut old, None);
let mut new = Diagnostics::default();
let got =
build_owned_records(beside.clone(), records.to_vec(), &options, &mut new, None);
assert_eq!(
outcome(got, &new),
outcome(want, &old),
"dedup {dedup}, directed {directed}, multigraph {multigraph}"
);
}
}
/// The extract command builds the edge records assembly leaves (and the
/// JSON edges after them) into exactly the graph, messages and errors
/// that the JSON build of the same edges gives.
#[test]
fn assembled_records_build_exactly_like_json_edges() {
let _serial = crate::extractors::parse_cache::test_serial();
let temp = tempfile::tempdir().unwrap();
let root = temp.path().canonicalize().unwrap();
let write = |rel: &str, text: &str| {
let path = root.join(rel);
std::fs::create_dir_all(path.parent().unwrap()).unwrap();
std::fs::write(&path, text).unwrap();
path
};
write("go.mod", "module example.com/demo\n\ngo 1.22\n");
let mut native = vec![
write(
"a/a.go",
"package a\n\nfunc Alpha() int { return 1 }\n\ntype Thing struct{}\n\nfunc (t *Thing) Do() int { return Alpha() }\n",
),
write(
"a/a2.go",
"package a\n\nfunc Beta() int { return Alpha() }\n",
),
write(
"b/b.go",
"package b\n\nimport (\n\t\"fmt\"\n\t\"example.com/demo/a\"\n)\n\nfunc Bravo() { fmt.Println(a.Alpha()); Charlie() }\n\nfunc Charlie() {}\n",
),
write(
"py/models.py",
"class Base:\n def run(self):\n return 1\n\n\nclass Child(Base):\n def go(self):\n return self.run()\n",
),
write(
"py/app.py",
"import models\nfrom models import Child\n\n\ndef main():\n c = Child()\n models.Base().run()\n return c.go()\n",
),
write("sh/run.sh", "#!/bin/bash\nsource ./lib.sh\nhelper\n"),
write("sh/lib.sh", "helper() {\n echo hi\n}\n"),
write(
"c/main.c",
"int util(void);\nint main(void) { return util(); }\n",
),
write("c/util.c", "int util(void) { return 1; }\n"),
];
native.sort();
let mut all = native.clone();
all.extend([
write(
"ts/a.ts",
"export class Greeter {\n greet(): string { return this.name(); }\n name(): string { return 'x'; }\n}\n",
),
write(
"ts/b.ts",
"import { Greeter } from './a';\n\nexport function run(): string {\n const g = new Greeter();\n return g.greet();\n}\n",
),
write(
"src/lib.rs",
"pub struct S;\n\nimpl S {\n pub fn f(&self) -> usize { self.g() }\n fn g(&self) -> usize { 1 }\n}\n",
),
write(
"java/A.java",
"package demo;\n\npublic class A {\n public int f() { return g(); }\n int g() { return 1; }\n}\n",
),
write(
"java/B.java",
"package demo;\n\nimport demo.A;\n\npublic class B {\n public int h() { return new A().f(); }\n}\n",
),
write("rb/a.rb", "class Foo\n def bar\n baz\n end\n\n def baz\n 1\n end\nend\n"),
write(
"php/a.php",
"<?php\nclass P {\n public function f() { return $this->g(); }\n public function g() { return 1; }\n}\n",
),
write(
"kt/A.kt",
"package demo\n\nclass K {\n fun f(): Int = g()\n fun g(): Int = 1\n}\n",
),
write(
"cs/A.cs",
"namespace Demo {\n public class C {\n public int F() { return G(); }\n int G() { return 1; }\n }\n}\n",
),
write(
"swift/A.swift",
"class W {\n func f() -> Int { return g() }\n func g() -> Int { return 1 }\n}\n",
),
write(
"cpp/a.cpp",
"#include \"a.hpp\"\n\nint Q::f() { return g(); }\nint Q::g() { return 1; }\n",
),
write("cpp/a.hpp", "class Q {\npublic:\n int f();\n int g();\n};\n"),
]);
all.sort();
let options = ExtractOptions {
root: Some(root.clone()),
cache_root: Some(root.join("cache")),
use_cache: false,
parallel: false,
..Default::default()
};
let code_node = |extraction: &Value| {
extraction["nodes"]
.as_array()
.unwrap()
.iter()
.find(|n| {
n["source_file"]
.as_str()
.is_some_and(|f| f.ends_with(".go"))
})
.and_then(|n| n["id"].as_str())
.unwrap()
.to_owned()
};
// Go, Python, Bash and C keep the record form through assembly; the
// other languages' JSON resolvers leave JSON edges, which convert.
for paths in [&native, &all] {
let json = extract::extract(paths, &options).unwrap();
assert_eq!(
serde_json::to_string(
&extract::extract_assembled(paths, &options)
.unwrap()
.into_value()
)
.unwrap(),
serde_json::to_string(&json).unwrap()
);
let (beside, records) = extract::extract_assembled(paths, &options)
.unwrap()
.into_parts();
assert!(!records.is_empty());
assert_eq!(beside["edges"], json!([]));
let (nodes, edges, hyperedges) = semantic(&code_node(&json));
let plain = |e: &Value| with(&with(e, "nodes", &nodes), "hyperedges", &hyperedges);
assert_same_builds(&json, &beside, &records, &root);
assert_same_builds(
&with(&plain(&json), "edges", &edges),
&with(&plain(&beside), "edges", &edges),
&records,
&root,
);
// A JSON edge that is no object fails both builds the same way.
let broken = [edges.clone(), vec![json!("not an edge")]].concat();
assert_same_builds(
&with(&plain(&json), "edges", &broken),
&with(&plain(&beside), "edges", &broken),
&records,
&root,
);
}
}
}