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
//! Opt-in precise Python call resolution (`--precise`), beyond the upstream port's.
//!
//! A flow- and context-insensitive points-to analysis over function, class,
//! instance and module values, in the spirit of PyCG (Salis et al., ICSE
//! 2021), limited to the definitions the graph already has nodes for:
//!
//! * names resolve lexically (locals, enclosing functions, module globals and
//! imports bound by the graph's own import edges), never by label guesses;
//! * values flow through assignments, parameters (positional, keyword and
//! defaults), returns (a returned parameter passes that call site's argument
//! through), instance and class attributes (`self.x = ...`), containers
//! (conflated with their elements), loops and decorators;
//! * `obj.m` binds through the class hierarchy of the instances `obj` may
//! hold, and `super().m` through the enclosing class's bases.
//!
//! Each call site inside a graph function or method gets a `calls` edge to
//! every callee found for it, unless the default engine already has that pair
//! or the site resolves to more than [`MAX_TARGETS`] callees (too ambiguous to
//! help). At a `super().m` site the default engine's edge to a same-named
//! method elsewhere is replaced. Added edges carry `resolution: points_to` or
//! `super_call`. Module-level statements feed the analysis but add no edges,
//! because Graphify has no module-level caller node. The default extraction
//! never runs this module.
use super::{parse_cache, resolution::source_key, resolution_facts};
use rustc_hash::{FxHashMap, FxHashSet};
use serde_json::{Value, json};
use std::path::{Path, PathBuf};
use tree_sitter::Node;
/// Call sites that resolve to more callees than this add no edges.
pub const MAX_TARGETS: usize = 8;
/// Values kept per variable; a larger set stops growing, which bounds the work
/// on deep hierarchies without affecting sites small enough to emit.
const MAX_VALUES: usize = 64;
/// Passes over the constraints before settling for the current solution.
const MAX_PASSES: usize = 50;
/// Syntax nesting beyond this is skipped (bounds recursion on generated code).
const MAX_DEPTH: usize = 200;
fn s<'a>(v: &'a Value, k: &str) -> &'a str {
v[k].as_str().unwrap_or("")
}
fn bare(label: &str) -> &str {
let label = label.strip_prefix('.').unwrap_or(label);
label.strip_suffix("()").unwrap_or(label)
}
fn text<'a>(n: Node<'_>, source: &'a [u8]) -> &'a str {
std::str::from_utf8(&source[n.byte_range()]).unwrap_or("")
}
fn named(n: Node<'_>) -> Vec<Node<'_>> {
let mut c = n.walk();
n.named_children(&mut c).collect()
}
fn line(n: Node<'_>) -> usize {
n.start_position().row + 1
}
fn location(v: &Value) -> Option<usize> {
s(v, "source_location").strip_prefix('L')?.parse().ok()
}
fn is_super(n: Node<'_>, source: &[u8]) -> bool {
n.kind() == "call"
&& n.child_by_field_name("function")
.is_some_and(|f| text(f, source) == "super")
}
/// The name a module file answers to (`pkg/mod.py` -> `mod`, `pkg/__init__.py` -> `pkg`).
fn module_stem(key: &str) -> &str {
let path = Path::new(key);
let file = path.file_name().and_then(|f| f.to_str()).unwrap_or("");
if file == "__init__.py" {
return path
.parent()
.and_then(Path::file_name)
.and_then(|f| f.to_str())
.unwrap_or("");
}
file.strip_suffix(".py").unwrap_or(file)
}
/// Whether file `key` is the module `dotted` (`a.b` -> `…a/b.py` or `…a/b/__init__.py`).
fn is_module(key: &str, dotted: &str) -> bool {
let rel = dotted.replace('.', "/");
[format!("{rel}.py"), format!("{rel}/__init__.py")]
.iter()
.any(|p| key == p || key.ends_with(&format!("/{p}")))
}
/// What the graph already says about definitions, files, classes and imports.
#[derive(Default)]
struct Facts {
/// (file key, definition line) -> node ids starting there.
at: FxHashMap<(String, usize), Vec<String>>,
label: FxHashMap<String, String>,
/// file key -> file node id, and back.
file_node: FxHashMap<String, String>,
file_key: FxHashMap<String, String>,
classes: FxHashSet<String>,
/// (class id, method name) -> method id.
methods: FxHashMap<(String, String), String>,
bases: FxHashMap<String, Vec<String>>,
/// (file key, line) -> targets of the import edges drawn from that line.
imports: FxHashMap<(String, usize), Vec<String>>,
}
impl Facts {
fn build(nodes: &[&Value], edges: &[&Value], root: &Path) -> Self {
let mut f = Facts::default();
for n in nodes {
let (id, sf, label) = (s(n, "id"), s(n, "source_file"), s(n, "label"));
if id.is_empty() || !sf.ends_with(".py") {
continue;
}
let key = source_key(sf, root);
f.label.insert(id.into(), label.into());
if Path::new(sf).file_name() == Path::new(label).file_name() {
f.file_node.entry(key.clone()).or_insert_with(|| id.into());
f.file_key.entry(id.into()).or_insert(key);
} else if let Some(l) = location(n) {
f.at.entry((key, l)).or_default().push(id.into());
}
}
for e in edges {
let (src, tgt) = (s(e, "source"), s(e, "target"));
match s(e, "relation") {
"method" => {
f.classes.insert(src.into());
if let Some(label) = f.label.get(tgt) {
f.methods
.entry((src.into(), bare(label).into()))
.or_insert_with(|| tgt.into());
}
}
"inherits" | "extends" => {
f.classes.insert(src.into());
f.classes.insert(tgt.into());
let bases = f.bases.entry(src.into()).or_default();
if !bases.iter().any(|b| b == tgt) {
bases.push(tgt.into());
}
}
"imports" | "imports_from" => {
if let (Some(key), Some(l)) = (f.file_key.get(src), location(e)) {
f.imports
.entry((key.clone(), l))
.or_default()
.push(tgt.into());
}
}
_ => {}
}
}
f
}
}
// ---------------------------------------------------------------------------
// Per-file intermediate form (built in parallel, names still as strings).
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Kind {
Module,
Function,
Class,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum FnKind {
Plain,
Static,
ClassMethod,
}
/// Where a name's values live.
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
enum Slot {
/// (file-local scope index, name) inside a function.
Local(usize, String),
/// (class id, attribute): class-body names and `obj.attr = ...` stores.
Field(String, String),
/// Return values of a function id.
Ret(String),
/// (file key, name) at module level.
Module(String, String),
}
#[derive(Clone, Debug)]
enum Ex {
Slot(Slot),
/// An imported graph symbol (function or class, decided once all files are known).
Sym(String),
Func(String),
Class(String),
Inst(String),
Module(String),
Attr(Box<Ex>, String),
/// `super()` in a method of the class, with the receiver's slot.
Super(String, Slot),
/// The result of the file-local call site.
Call(usize),
Many(Vec<Ex>),
/// The first operand's values, or the second's when it has none.
OrElse(Box<Ex>, Box<Ex>),
}
struct SiteB {
caller: Option<String>,
line: usize,
func: Ex,
args: Vec<Ex>,
kwargs: Vec<(String, Ex)>,
super_name: Option<String>,
}
enum ConB {
Flow(Slot, Ex),
Store(Ex, String, Ex),
Iter {
caller: Option<String>,
line: usize,
iter: Ex,
targets: Vec<Slot>,
},
}
struct FuncB {
id: String,
scope: usize,
params: Vec<String>,
/// Parameters a positional argument can bind (before `*`, `*args`, `**kw`).
positional: usize,
/// Parameters returned unchanged (`return p`).
pass: Vec<usize>,
kind: FnKind,
}
#[derive(Default)]
struct FileIr {
path: String,
key: String,
scopes: usize,
sites: Vec<SiteB>,
cons: Vec<ConB>,
funcs: Vec<FuncB>,
classes: Vec<String>,
/// Modules this file re-exports with `from m import *` (file keys).
stars: Vec<String>,
/// Names the module body binds (defs, classes, assignments, imports).
module_names: Vec<String>,
}
struct ScopeB {
kind: Kind,
parent: Option<usize>,
locals: FxHashSet<String>,
/// Names bound other than as parameters.
assigned: FxHashSet<String>,
/// Names declared `global` / `nonlocal`.
outer: FxHashSet<String>,
/// `global` bypasses all enclosing function bindings.
globals: FxHashSet<String>,
def: Option<String>,
/// The class of a class body, or of a method.
class: Option<String>,
receiver: Option<String>,
func: Option<usize>,
defaults: Vec<(usize, Ex)>,
}
impl ScopeB {
fn new(kind: Kind, parent: Option<usize>) -> Self {
ScopeB {
kind,
parent,
locals: FxHashSet::default(),
assigned: FxHashSet::default(),
outer: FxHashSet::default(),
globals: FxHashSet::default(),
def: None,
class: None,
receiver: None,
func: None,
defaults: vec![],
}
}
}
struct Builder<'a> {
src: &'a [u8],
key: String,
facts: &'a Facts,
scopes: Vec<ScopeB>,
ir: FileIr,
depth: usize,
}
impl<'a> Builder<'a> {
fn slot(&self, scope: usize, name: &str) -> Slot {
let sc = &self.scopes[scope];
match (sc.kind, &sc.class) {
(Kind::Module, _) => Slot::Module(self.key.clone(), name.into()),
(Kind::Class, Some(c)) => Slot::Field(c.clone(), name.into()),
_ => Slot::Local(scope, name.into()),
}
}
/// Lexical lookup; class bodies are visible only to their own statements.
fn lookup(&self, scope: usize, name: &str) -> Option<Slot> {
let (mut cur, mut first) = (Some(scope), true);
while let Some(i) = cur {
let sc = &self.scopes[i];
if sc.globals.contains(name) {
return Some(Slot::Module(self.key.clone(), name.into()));
}
if (first || sc.kind != Kind::Class)
&& sc.locals.contains(name)
&& !sc.outer.contains(name)
{
return Some(self.slot(i, name));
}
first = false;
cur = sc.parent;
}
None
}
/// The graph function whose body runs this scope's statements.
fn caller(&self, scope: usize) -> Option<String> {
let mut cur = Some(scope);
while let Some(i) = cur {
let sc = &self.scopes[i];
match sc.kind {
Kind::Function if sc.def.is_some() => return sc.def.clone(),
Kind::Module => return None,
_ => cur = sc.parent,
}
}
None
}
fn nearest(&self, scope: usize, method: bool) -> Option<usize> {
let mut cur = Some(scope);
while let Some(i) = cur {
let sc = &self.scopes[i];
if sc.kind == Kind::Function && (!method || sc.class.is_some()) {
return Some(i);
}
if sc.kind == Kind::Module {
return None;
}
cur = sc.parent;
}
None
}
fn def_id(&self, l: usize, name: &str, function: bool) -> Option<String> {
self.facts
.at
.get(&(self.key.clone(), l))?
.iter()
.find(|id| {
let label = self.facts.label.get(*id).map_or("", String::as_str);
if function {
label.ends_with(')') && bare(label) == name
} else {
label == name
}
})
.cloned()
}
fn push(&mut self, c: ConB) {
self.ir.cons.push(c);
}
fn targets(&self, n: Node<'_>, out: &mut Vec<String>) {
match n.kind() {
"identifier" => out.push(text(n, self.src).into()),
"pattern_list"
| "tuple_pattern"
| "list_pattern"
| "tuple"
| "list"
| "list_splat_pattern"
| "parenthesized_expression"
| "as_pattern_target" => {
for c in named(n) {
self.targets(c, out);
}
}
_ => {}
}
}
/// Names bound in a scope's body, without entering nested scopes.
fn collect(
&self,
body: Node<'_>,
assigned: &mut FxHashSet<String>,
outer: &mut FxHashSet<String>,
globals: &mut FxHashSet<String>,
) {
// Iterative: generated code can nest expressions thousands deep.
let mut stack = vec![body];
while let Some(n) = stack.pop() {
let mut names = vec![];
match n.kind() {
"function_definition" | "class_definition" => {
if let Some(name) = n.child_by_field_name("name") {
assigned.insert(text(name, self.src).into());
}
continue;
}
"lambda" => continue,
"assignment" | "augmented_assignment" | "for_statement" | "for_in_clause" => {
if let Some(l) = n.child_by_field_name("left") {
self.targets(l, &mut names);
}
}
"named_expression" => {
if let Some(l) = n.child_by_field_name("name") {
self.targets(l, &mut names);
}
}
"as_pattern" => {
if let Some(a) = n.child_by_field_name("alias") {
self.targets(a, &mut names);
}
}
"import_statement" | "import_from_statement" => {
names.extend(self.import_names(n).into_iter().map(|(_, local)| local));
}
"global_statement" | "nonlocal_statement" => {
for c in named(n).into_iter().filter(|c| c.kind() == "identifier") {
outer.insert(text(c, self.src).into());
if n.kind() == "global_statement" {
globals.insert(text(c, self.src).into());
}
}
}
_ => {}
}
assigned.extend(names);
stack.extend(named(n));
}
}
/// (imported dotted name, local binding) pairs of an import statement.
fn import_names(&self, n: Node<'_>) -> Vec<(String, String)> {
let module = n.child_by_field_name("module_name").map(|m| m.id());
let mut out = vec![];
for c in named(n) {
if Some(c.id()) == module {
continue;
}
match c.kind() {
"dotted_name" => {
let full = text(c, self.src).to_string();
let local = full.split('.').next().unwrap_or("").to_string();
out.push((full, local));
}
"aliased_import" => {
if let (Some(name), Some(alias)) = (
c.child_by_field_name("name"),
c.child_by_field_name("alias"),
) {
out.push((text(name, self.src).into(), text(alias, self.src).into()));
}
}
_ => {}
}
}
out
}
fn visit(&mut self, n: Node<'_>, scope: usize) {
match n.kind() {
"function_definition" => self.function(n, scope, &[]),
"class_definition" => self.class(n, scope, &[]),
"decorated_definition" => {
let decorators = named(n)
.into_iter()
.filter(|d| d.kind() == "decorator")
.collect::<Vec<_>>();
match n.child_by_field_name("definition") {
Some(d) if d.kind() == "function_definition" => {
self.function(d, scope, &decorators)
}
Some(d) if d.kind() == "class_definition" => self.class(d, scope, &decorators),
_ => {}
}
}
"assignment" | "augmented_assignment" => {
match (
n.child_by_field_name("left"),
n.child_by_field_name("right"),
) {
(Some(l), Some(r)) => self.assign(l, r, scope),
_ => {
for c in named(n) {
self.expr(c, scope);
}
}
}
}
"return_statement" => self.ret(n, scope),
"for_statement" => {
let (left, right) = (
n.child_by_field_name("left"),
n.child_by_field_name("right"),
);
if let Some(it) = right.and_then(|r| self.expr(r, scope)) {
self.iterate(left, it, line(n), scope);
}
let skip = [left.map(|l| l.id()), right.map(|r| r.id())];
for c in named(n) {
if !skip.contains(&Some(c.id())) {
self.visit(c, scope);
}
}
}
"import_statement" | "import_from_statement" => self.import(n, scope),
"lambda" | "global_statement" | "nonlocal_statement" | "comment" => {}
_ => {
self.expr(n, scope);
}
}
}
fn iterate(&mut self, left: Option<Node<'_>>, iter: Ex, l: usize, scope: usize) {
let Some(left) = left else { return };
let mut names = vec![];
self.targets(left, &mut names);
let targets = names.iter().filter_map(|x| self.lookup(scope, x)).collect();
let caller = self.caller(scope);
self.push(ConB::Iter {
caller,
line: l,
iter,
targets,
});
}
fn assign(&mut self, left: Node<'_>, right: Node<'_>, scope: usize) {
let seq = |k: &str| {
matches!(
k,
"pattern_list"
| "tuple_pattern"
| "list_pattern"
| "tuple"
| "list"
| "expression_list"
)
};
if seq(left.kind()) && seq(right.kind()) {
let (l, r) = (named(left), named(right));
if l.len() == r.len() {
for (a, b) in l.into_iter().zip(r) {
self.assign(a, b, scope);
}
return;
}
}
// `a = b = value` nests assignments on the right.
let (mut lefts, mut value) = (vec![left], right);
while value.kind() == "assignment" {
lefts.extend(value.child_by_field_name("left"));
match value.child_by_field_name("right") {
Some(r) => value = r,
None => break,
}
}
let v = self.expr(value, scope);
for l in lefts {
self.bind_target(l, v.clone(), scope);
}
}
fn bind_target(&mut self, target: Node<'_>, value: Option<Ex>, scope: usize) {
match target.kind() {
"identifier" => {
if let (Some(v), Some(slot)) = (value, self.lookup(scope, text(target, self.src))) {
self.push(ConB::Flow(slot, v));
}
}
"attribute" => {
let object = target
.child_by_field_name("object")
.and_then(|o| self.expr(o, scope));
if let (Some(o), Some(a), Some(v)) =
(object, target.child_by_field_name("attribute"), value)
{
let attr = text(a, self.src).to_string();
self.push(ConB::Store(o, attr, v));
}
}
"subscript" => {
// A container store: the container holds the value.
if let Some(ix) = target.child_by_field_name("subscript") {
self.expr(ix, scope);
}
if let Some(v) = target.child_by_field_name("value") {
self.bind_target(v, value, scope);
}
}
"pattern_list"
| "tuple_pattern"
| "list_pattern"
| "tuple"
| "list"
| "list_splat_pattern"
| "parenthesized_expression" => {
for c in named(target) {
self.bind_target(c, value.clone(), scope);
}
}
_ => {
self.expr(target, scope);
}
}
}
fn ret(&mut self, n: Node<'_>, scope: usize) {
let Some(value) = named(n).into_iter().next() else {
return;
};
let owner = self.nearest(scope, false).and_then(|fs| {
let sc = &self.scopes[fs];
Some((fs, sc.func?, sc.def.clone()?))
});
let Some((fs, fi, id)) = owner else {
self.expr(value, scope);
return;
};
if value.kind() == "identifier" {
let name = text(value, self.src);
if !self.scopes[fs].assigned.contains(name)
&& let Some(p) = self.ir.funcs[fi].params.iter().position(|x| x == name)
{
// `return p`: each call site gets its own argument back.
if !self.ir.funcs[fi].pass.contains(&p) {
self.ir.funcs[fi].pass.push(p);
}
let default = self.scopes[fs]
.defaults
.iter()
.find(|(i, _)| *i == p)
.map(|(_, e)| e.clone());
if let Some(d) = default {
self.push(ConB::Flow(Slot::Ret(id), d));
}
return;
}
}
if let Some(ex) = self.expr(value, scope) {
self.push(ConB::Flow(Slot::Ret(id), ex));
}
}
fn import(&mut self, n: Node<'_>, scope: usize) {
let Some(targets) = self.facts.imports.get(&(self.key.clone(), line(n))) else {
return;
};
let from = n.kind() == "import_from_statement";
let files = targets
.iter()
.filter_map(|t| self.facts.file_key.get(t))
.collect::<Vec<_>>();
// `from m import *` at module level re-exports m's names: `pkg.Name`
// then finds `Name` through the star (see `Solver::attr`).
if from
&& self.scopes[scope].kind == Kind::Module
&& named(n).iter().any(|c| c.kind() == "wildcard_import")
&& let [k] = files[..]
{
self.ir.stars.push(k.clone());
return;
}
let mut flows = vec![];
for (name, local) in self.import_names(n) {
let value = if from {
let symbol = targets.iter().find(|t| {
!self.facts.file_key.contains_key(*t)
&& self.facts.label.get(*t).is_some_and(|l| bare(l) == name)
});
if let Some(t) = symbol {
Some(Ex::Sym(t.clone()))
} else if let Some(k) = files.iter().find(|k| module_stem(k) == name) {
Some(Ex::Module((*k).clone()))
} else if let [k] = files[..] {
// A module-level name of the source module (`from m import
// handler`), read as `m.handler` so names m re-exports with
// `import *` resolve too.
Some(Ex::Attr(Box::new(Ex::Module(k.clone())), name.clone()))
} else {
None
}
} else if !name.contains('.') || name != local {
files
.iter()
.find(|k| is_module(k, &name))
.map(|k| Ex::Module((*k).clone()))
} else {
None
};
if let (Some(v), Some(slot)) = (value, self.lookup(scope, &local)) {
flows.push(ConB::Flow(slot, v));
}
}
self.ir.cons.extend(flows);
}
fn function(&mut self, n: Node<'_>, scope: usize, decorators: &[Node<'_>]) {
let Some(name) = n.child_by_field_name("name") else {
return;
};
let name = text(name, self.src).to_string();
let id = self.def_id(line(n), &name, true);
let class = match self.scopes[scope].kind {
Kind::Class => self.scopes[scope].class.clone(),
_ => None,
};
let decorated = |d: &str| {
decorators
.iter()
.any(|n| text(*n, self.src).trim_start_matches('@').trim() == d)
};
let kind = if decorated("staticmethod") {
FnKind::Static
} else if decorated("classmethod") {
FnKind::ClassMethod
} else {
FnKind::Plain
};
let (mut params, mut positional, mut default_nodes) = (vec![], usize::MAX, vec![]);
if let Some(list) = n.child_by_field_name("parameters") {
for p in named(list) {
match p.kind() {
"identifier" => params.push(text(p, self.src).to_string()),
"default_parameter" | "typed_default_parameter" => {
if let Some(nm) = p.child_by_field_name("name") {
params.push(text(nm, self.src).to_string());
if let Some(v) = p.child_by_field_name("value") {
default_nodes.push((params.len() - 1, v));
}
}
}
"typed_parameter" => {
match named(p).into_iter().find(|c| c.kind() == "identifier") {
Some(nm) => params.push(text(nm, self.src).to_string()),
None => positional = positional.min(params.len()),
}
}
"list_splat_pattern" | "dictionary_splat_pattern" | "keyword_separator" => {
positional = positional.min(params.len());
}
_ => {}
}
}
}
let positional = positional.min(params.len());
// Defaults evaluate in the defining scope.
let defaults = default_nodes
.into_iter()
.filter_map(|(i, v)| Some((i, self.expr(v, scope)?)))
.collect::<Vec<_>>();
let new = self.scopes.len();
let mut sc = ScopeB::new(Kind::Function, Some(scope));
if let Some(body) = n.child_by_field_name("body") {
self.collect(body, &mut sc.assigned, &mut sc.outer, &mut sc.globals);
}
sc.locals = params
.iter()
.cloned()
.chain(sc.assigned.iter().cloned())
.collect();
sc.def = id.clone();
sc.class = class.clone();
sc.receiver = if class.is_some() && kind != FnKind::Static {
params.first().cloned()
} else {
None
};
sc.func = id.as_ref().map(|id| {
self.ir.funcs.push(FuncB {
id: id.clone(),
scope: new,
params: params.clone(),
positional,
pass: vec![],
kind,
});
self.ir.funcs.len() - 1
});
sc.defaults = defaults.clone();
let receiver = sc.receiver.clone();
self.scopes.push(sc);
for (i, ex) in defaults {
self.push(ConB::Flow(Slot::Local(new, params[i].clone()), ex));
}
if let (Some(c), Some(r)) = (class, receiver) {
let v = match kind {
FnKind::ClassMethod => Ex::Class(c),
_ => Ex::Inst(c),
};
self.push(ConB::Flow(Slot::Local(new, r), v));
}
if let Some(body) = n.child_by_field_name("body") {
self.visit(body, new);
}
// Methods are found through the class hierarchy, not class-body names.
let value = id.map(Ex::Func);
self.bind_decorated(&name, value, decorators, scope);
}
fn class(&mut self, n: Node<'_>, scope: usize, decorators: &[Node<'_>]) {
let Some(name) = n.child_by_field_name("name") else {
return;
};
let name = text(name, self.src).to_string();
let id = self.def_id(line(n), &name, false);
if let Some(bases) = n.child_by_field_name("superclasses") {
self.expr(bases, scope);
}
let new = self.scopes.len();
let mut sc = ScopeB::new(Kind::Class, Some(scope));
if let Some(body) = n.child_by_field_name("body") {
self.collect(body, &mut sc.assigned, &mut sc.outer, &mut sc.globals);
}
sc.locals = sc.assigned.clone();
sc.class = id.clone();
self.scopes.push(sc);
if let Some(c) = &id {
self.ir.classes.push(c.clone());
}
if let Some(body) = n.child_by_field_name("body") {
self.visit(body, new);
}
self.bind_decorated(&name, id.map(Ex::Class), decorators, scope);
}
/// `@d1 @d2 def f` binds `f = d1(d2(f))`; an unknown decorator, or one
/// with no known result, is taken to return its argument.
fn bind_decorated(
&mut self,
name: &str,
value: Option<Ex>,
decorators: &[Node<'_>],
scope: usize,
) {
let mut value = value;
let caller = self.caller(scope);
for d in decorators.iter().rev() {
let Some(e) = named(*d).into_iter().next() else {
continue;
};
let Some(func) = self.expr(e, scope) else {
continue;
};
self.ir.sites.push(SiteB {
caller: caller.clone(),
line: line(*d),
func,
args: vec![value.clone().unwrap_or(Ex::Many(vec![]))],
kwargs: vec![],
super_name: None,
});
let result = Ex::Call(self.ir.sites.len() - 1);
value = Some(match value {
Some(v) => Ex::OrElse(Box::new(result), Box::new(v)),
None => result,
});
}
if self.scopes[scope].kind != Kind::Class
&& let (Some(v), Some(slot)) = (value, self.lookup(scope, name))
{
self.push(ConB::Flow(slot, v));
}
}
fn expr(&mut self, n: Node<'_>, scope: usize) -> Option<Ex> {
if self.depth > MAX_DEPTH {
return None;
}
self.depth += 1;
let out = self.expr_inner(n, scope);
self.depth -= 1;
out
}
fn many(items: Vec<Ex>) -> Option<Ex> {
(!items.is_empty()).then_some(Ex::Many(items))
}
fn expr_inner(&mut self, n: Node<'_>, scope: usize) -> Option<Ex> {
match n.kind() {
"identifier" => self.lookup(scope, text(n, self.src)).map(Ex::Slot),
"attribute" => {
let attr = text(n.child_by_field_name("attribute")?, self.src).to_string();
let object = n.child_by_field_name("object")?;
if is_super(object, self.src) {
let m = self.nearest(scope, true)?;
let sc = &self.scopes[m];
let (class, recv) = (sc.class.clone()?, sc.receiver.clone()?);
return Some(Ex::Attr(
Box::new(Ex::Super(class, Slot::Local(m, recv))),
attr,
));
}
let object = self.expr(object, scope)?;
Some(Ex::Attr(Box::new(object), attr))
}
"call" => self.call(n, scope).map(Ex::Call),
"list" | "tuple" | "set" | "expression_list" | "boolean_operator" => {
let items = named(n)
.into_iter()
.filter_map(|c| self.expr(c, scope))
.collect();
Self::many(items)
}
"dictionary" => {
let mut items = vec![];
for c in named(n) {
if c.kind() == "pair" {
if let Some(k) = c.child_by_field_name("key") {
self.expr(k, scope);
}
items.extend(
c.child_by_field_name("value")
.and_then(|v| self.expr(v, scope)),
);
} else {
items.extend(self.expr(c, scope));
}
}
Self::many(items)
}
"conditional_expression" => {
let mut items = vec![];
for (i, c) in named(n).into_iter().enumerate() {
let v = self.expr(c, scope);
if i != 1 {
items.extend(v);
}
}
Self::many(items)
}
"parenthesized_expression" | "await" | "list_splat" | "dictionary_splat" => {
let mut last = None;
for c in named(n) {
last = self.expr(c, scope);
}
last
}
"subscript" => {
let value = n.child_by_field_name("value");
for c in named(n) {
if Some(c.id()) != value.map(|v| v.id()) {
self.expr(c, scope);
}
}
value.and_then(|v| self.expr(v, scope))
}
"named_expression" => {
let v = n
.child_by_field_name("value")
.and_then(|v| self.expr(v, scope));
if let (Some(name), Some(v)) = (n.child_by_field_name("name"), v.clone())
&& let Some(slot) = self.lookup(scope, text(name, self.src))
{
self.push(ConB::Flow(slot, v));
}
v
}
"yield" => {
let v = named(n)
.into_iter()
.next()
.and_then(|c| self.expr(c, scope));
let owner = self
.nearest(scope, false)
.and_then(|fs| self.scopes[fs].def.clone());
if let (Some(v), Some(id)) = (v, owner) {
self.push(ConB::Flow(Slot::Ret(id), v));
}
None
}
"list_comprehension"
| "set_comprehension"
| "generator_expression"
| "dictionary_comprehension" => {
let body = n.child_by_field_name("body");
for c in named(n) {
if c.kind() == "for_in_clause" {
let it = c
.child_by_field_name("right")
.and_then(|r| self.expr(r, scope));
if let Some(it) = it {
self.iterate(c.child_by_field_name("left"), it, line(c), scope);
}
} else if Some(c.id()) != body.map(|b| b.id()) {
self.expr(c, scope);
}
}
let body = body?;
let value = if body.kind() == "pair" {
if let Some(k) = body.child_by_field_name("key") {
self.expr(k, scope);
}
body.child_by_field_name("value")
.and_then(|v| self.expr(v, scope))
} else {
self.expr(body, scope)
};
value.map(|v| Ex::Many(vec![v]))
}
"lambda" | "integer" | "float" | "true" | "false" | "none" | "comment" | "ellipsis" => {
None
}
_ => {
for c in named(n) {
self.visit(c, scope);
}
None
}
}
}
fn call(&mut self, n: Node<'_>, scope: usize) -> Option<usize> {
let function = n.child_by_field_name("function")?;
let func = self.expr(function, scope);
let super_name = if function.kind() == "attribute"
&& function
.child_by_field_name("object")
.is_some_and(|o| is_super(o, self.src))
{
function
.child_by_field_name("attribute")
.map(|a| text(a, self.src).to_string())
} else {
None
};
let (mut args, mut kwargs, mut splat) = (vec![], vec![], false);
if let Some(list) = n.child_by_field_name("arguments") {
if list.kind() == "argument_list" {
for a in named(list) {
match a.kind() {
"keyword_argument" => {
let v = a
.child_by_field_name("value")
.and_then(|v| self.expr(v, scope));
if let (Some(k), Some(v)) = (a.child_by_field_name("name"), v) {
kwargs.push((text(k, self.src).to_string(), v));
}
}
"list_splat" | "dictionary_splat" => {
// Positions after a splat are unknown.
splat = true;
self.expr(a, scope);
}
"comment" => {}
_ => {
let v = self.expr(a, scope);
if !splat {
args.push(v.unwrap_or(Ex::Many(vec![])));
}
}
}
}
} else {
let v = self.expr(list, scope);
args.push(v.unwrap_or(Ex::Many(vec![])));
}
}
let func = func?;
let caller = self.caller(scope);
self.ir.sites.push(SiteB {
caller,
line: line(n),
func,
args,
kwargs,
super_name,
});
Some(self.ir.sites.len() - 1)
}
}
/// Stack for the per-file builders: the same as per-file extraction, since the
/// builder recurses once per syntax level (up to `MAX_DEPTH`) and debug builds
/// use far larger frames than release.
const STACK: usize = 32 << 20;
/// Per-file IR for every file, in file order, on as many big-stack workers as
/// the current run allows (always off the caller's thread, whose stack size is
/// unknown).
fn build_all(files: &[(PathBuf, String)], facts: &Facts) -> Vec<Option<FileIr>> {
let workers = parse_cache::workers().clamp(1, files.len().max(1));
let next = std::sync::atomic::AtomicUsize::new(0);
let slots = std::sync::Mutex::new(Vec::with_capacity(files.len()));
let work = || {
loop {
let i = next.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
let Some((path, key)) = files.get(i) else {
break;
};
let ir = build_file(path, key.clone(), facts);
slots
.lock()
.unwrap_or_else(|e| e.into_inner())
.push((i, ir));
}
};
std::thread::scope(|scope| {
let spawned = (0..workers)
.filter(|_| {
std::thread::Builder::new()
.stack_size(STACK)
.spawn_scoped(scope, work)
.is_ok()
})
.count();
if spawned == 0 {
work();
}
});
let mut slots = slots.into_inner().unwrap_or_else(|e| e.into_inner());
slots.sort_by_key(|(i, _)| *i);
slots.into_iter().map(|(_, ir)| ir).collect()
}
fn build_file(path: &Path, key: String, facts: &Facts) -> Option<FileIr> {
let tree = resolution_facts::parse_python_tree(path)?;
let root = tree.tree.root_node();
let mut b = Builder {
src: &tree.source,
key: key.clone(),
facts,
scopes: vec![],
ir: FileIr {
path: path.to_string_lossy().into_owned(),
key,
..FileIr::default()
},
depth: 0,
};
let mut module = ScopeB::new(Kind::Module, None);
b.collect(
root,
&mut module.assigned,
&mut module.outer,
&mut module.globals,
);
module.locals = module.assigned.clone();
b.ir.module_names = module.assigned.iter().cloned().collect();
b.scopes.push(module);
b.visit(root, 0);
b.ir.scopes = b.scopes.len();
Some(b.ir)
}
// ---------------------------------------------------------------------------
// Whole-program solution over interned values.
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
enum Val {
Func(u32),
/// A method bound to an instance (or, for a classmethod, the class) of `.1`.
Bound(u32, u32),
Class(u32),
Inst(u32),
Module(u32),
}
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
enum Key {
Local(u32, u32),
Field(u32, u32),
Ret(u32),
Module(u32, u32),
}
enum E {
Var(u32),
Val(Val),
Attr(Box<E>, u32),
Super(u32, u32),
Call(u32),
Many(Vec<E>),
OrElse(Box<E>, Box<E>),
}
struct Site {
caller: Option<u32>,
file: usize,
line: usize,
func: E,
args: Vec<E>,
kwargs: Vec<(u32, E)>,
super_name: Option<u32>,
}
enum Con {
Flow(u32, E),
Store(E, u32, E),
Iter {
caller: Option<u32>,
file: usize,
line: usize,
iter: E,
targets: Vec<u32>,
},
}
struct Func {
params: Vec<u32>,
names: Vec<u32>,
positional: usize,
pass: Vec<usize>,
kind: FnKind,
}
#[derive(Default)]
struct Interner {
map: FxHashMap<String, u32>,
list: Vec<String>,
}
impl Interner {
fn id(&mut self, s: &str) -> u32 {
if let Some(&i) = self.map.get(s) {
return i;
}
let i = self.list.len() as u32;
self.map.insert(s.to_string(), i);
self.list.push(s.to_string());
i
}
fn name(&self, i: u32) -> &str {
&self.list[i as usize]
}
}
#[derive(Default)]
struct Solver {
ids: Interner,
syms: Interner,
files: Interner,
vars: FxHashMap<Key, u32>,
pts: Vec<Vec<Val>>,
sites: Vec<Site>,
cons: Vec<Con>,
funcs: FxHashMap<u32, Func>,
methods: FxHashMap<(u32, u32), u32>,
bases: FxHashMap<u32, Vec<u32>>,
/// Python C3 linearizations, computed once per solve. Empty means the
/// hierarchy is cyclic, inconsistent or exceeds the analysis bound.
mros: FxHashMap<u32, Vec<u32>>,
submodules: FxHashMap<(u32, u32), u32>,
/// `from m import *` re-exports: file -> source modules.
stars: FxHashMap<u32, Vec<u32>>,
/// (file, name) pairs a module body binds itself.
bound: FxHashSet<(u32, u32)>,
classes: FxHashSet<u32>,
functions: FxHashSet<u32>,
init: u32,
call: u32,
iter: u32,
next: u32,
}
impl Solver {
fn var(&mut self, k: Key) -> u32 {
if let Some(&v) = self.vars.get(&k) {
return v;
}
let v = self.pts.len() as u32;
self.pts.push(vec![]);
self.vars.insert(k, v);
v
}
fn slot(&mut self, base: u32, s: &Slot) -> u32 {
let k = match s {
Slot::Local(i, n) => Key::Local(base + *i as u32, self.syms.id(n)),
Slot::Field(c, n) => Key::Field(self.ids.id(c), self.syms.id(n)),
Slot::Ret(f) => Key::Ret(self.ids.id(f)),
Slot::Module(k, n) => Key::Module(self.files.id(k), self.syms.id(n)),
};
self.var(k)
}
fn conv(&mut self, base: u32, sites: u32, e: &Ex) -> E {
match e {
Ex::Slot(s) => E::Var(self.slot(base, s)),
Ex::Sym(id) => {
let i = self.ids.id(id);
if self.functions.contains(&i) {
E::Val(Val::Func(i))
} else if self.classes.contains(&i) {
E::Val(Val::Class(i))
} else {
E::Many(vec![])
}
}
Ex::Func(id) => E::Val(Val::Func(self.ids.id(id))),
Ex::Class(id) => E::Val(Val::Class(self.ids.id(id))),
Ex::Inst(id) => E::Val(Val::Inst(self.ids.id(id))),
Ex::Module(k) => E::Val(Val::Module(self.files.id(k))),
Ex::Attr(o, a) => {
let o = self.conv(base, sites, o);
E::Attr(Box::new(o), self.syms.id(a))
}
Ex::Super(c, recv) => {
let c = self.ids.id(c);
E::Super(c, self.slot(base, recv))
}
Ex::Call(i) => E::Call(sites + *i as u32),
Ex::Many(xs) => E::Many(xs.iter().map(|x| self.conv(base, sites, x)).collect()),
Ex::OrElse(a, b) => {
let a = self.conv(base, sites, a);
E::OrElse(Box::new(a), Box::new(self.conv(base, sites, b)))
}
}
}
fn prepare_mros(&mut self) {
fn linearize(
c: u32,
bases: &FxHashMap<u32, Vec<u32>>,
cache: &mut FxHashMap<u32, Vec<u32>>,
active: &mut FxHashSet<u32>,
) -> Option<Vec<u32>> {
if let Some(mro) = cache.get(&c) {
return (!mro.is_empty()).then(|| mro.clone());
}
if active.len() >= MAX_VALUES || !active.insert(c) {
return None;
}
let result = (|| {
let parents = bases.get(&c).cloned().unwrap_or_default();
if parents.len() >= MAX_VALUES {
return None;
}
let mut sequences = parents
.iter()
.map(|p| linearize(*p, bases, cache, active))
.collect::<Option<Vec<_>>>()?;
sequences.push(parents);
let mut out = vec![c];
while sequences.iter().any(|s| !s.is_empty()) {
let candidate =
sequences
.iter()
.filter_map(|s| s.first())
.copied()
.find(|head| {
sequences
.iter()
.all(|s| !s.get(1..).unwrap_or_default().contains(head))
})?;
if out.len() >= MAX_VALUES {
return None;
}
out.push(candidate);
for sequence in &mut sequences {
if sequence.first() == Some(&candidate) {
sequence.remove(0);
}
}
}
Some(out)
})();
active.remove(&c);
cache.insert(c, result.clone().unwrap_or_default());
result
}
self.mros.clear();
for c in &self.classes {
linearize(*c, &self.bases, &mut self.mros, &mut FxHashSet::default());
}
}
fn mro(&self, c: u32) -> &[u32] {
self.mros.get(&c).map(Vec::as_slice).unwrap_or_default()
}
fn method(&self, c: u32, name: u32) -> Option<u32> {
self.mro(c)
.iter()
.copied()
.find_map(|k| self.methods.get(&(k, name)).copied())
}
fn receiver(&self, f: u32, class: u32) -> Val {
match self.funcs.get(&f).map(|f| f.kind) {
Some(FnKind::ClassMethod) => Val::Class(class),
_ => Val::Inst(class),
}
}
fn eval(&self, e: &E, out: &mut Vec<Val>) {
match e {
E::Var(v) => out.extend_from_slice(&self.pts[*v as usize]),
E::Val(x) => out.push(*x),
E::Attr(object, a) => {
if let E::Super(class, recv) = &**object {
let found = self
.mro(*class)
.iter()
.copied()
.skip(1)
.find_map(|k| self.methods.get(&(k, *a)).copied());
if let Some(m) = found {
let mut bound = false;
for r in &self.pts[*recv as usize] {
if let Val::Inst(c) | Val::Class(c) = r {
out.push(Val::Bound(m, *c));
bound = true;
}
}
if !bound {
out.push(Val::Bound(m, *class));
}
}
return;
}
let mut objects = vec![];
self.eval(object, &mut objects);
objects.sort_unstable();
objects.dedup();
for o in objects {
self.attr(o, *a, out);
}
}
E::Super(..) => {}
E::Call(site) => self.result(*site as usize, out),
E::Many(items) => {
for i in items {
self.eval(i, out);
}
}
E::OrElse(a, b) => {
let n = out.len();
self.eval(a, out);
if out.len() == n {
self.eval(b, out);
}
}
}
}
fn values(&self, e: &E) -> Vec<Val> {
let mut out = vec![];
self.eval(e, &mut out);
out.sort_unstable();
out.dedup();
out
}
fn attr(&self, o: Val, a: u32, out: &mut Vec<Val>) {
match o {
Val::Module(f) => {
// The module's own binding and submodule, as before; a name the
// module never binds is looked up in its `import *` sources.
// Whether a module binds a name is fixed before solving, so the
// lookup stays monotone.
let (mut stack, mut seen) = (vec![f], FxHashSet::default());
while let Some(m) = stack.pop() {
if !seen.insert(m) || seen.len() > 64 {
continue;
}
let own = self.vars.get(&Key::Module(m, a));
if let Some(v) = own {
out.extend_from_slice(&self.pts[*v as usize]);
}
let sub = self.submodules.get(&(m, a));
if let Some(sub) = sub {
out.push(Val::Module(*sub));
}
if !self.bound.contains(&(m, a))
&& sub.is_none()
&& let Some(sources) = self.stars.get(&m)
{
stack.extend(sources.iter().rev());
}
}
}
Val::Class(c) | Val::Inst(c) => {
let mro = self.mro(c);
if let Some(m) = mro.iter().find_map(|k| self.methods.get(&(*k, a)).copied()) {
let kind = self.funcs.get(&m).map_or(FnKind::Plain, |f| f.kind);
out.push(match (o, kind) {
(_, FnKind::Static) => Val::Func(m),
(_, FnKind::ClassMethod) | (Val::Inst(_), FnKind::Plain) => {
Val::Bound(m, c)
}
_ => Val::Func(m),
});
}
for k in mro {
if let Some(v) = self.vars.get(&Key::Field(*k, a)) {
out.extend_from_slice(&self.pts[*v as usize]);
}
}
}
_ => {}
}
}
/// The callee a value runs when called: (function, receiver class).
fn callee(&self, v: Val) -> Option<(u32, Option<u32>)> {
match v {
Val::Func(f) => Some((f, None)),
Val::Bound(f, c) => Some((f, Some(c))),
Val::Class(c) => self.method(c, self.init).map(|m| (m, Some(c))),
Val::Inst(c) => self.method(c, self.call).map(|m| (m, Some(c))),
Val::Module(_) => None,
}
}
fn returns(
&self,
f: u32,
recv: Option<u32>,
args: &[E],
kwargs: &[(u32, E)],
out: &mut Vec<Val>,
) {
if let Some(v) = self.vars.get(&Key::Ret(f)) {
out.extend_from_slice(&self.pts[*v as usize]);
}
let Some(func) = self.funcs.get(&f) else {
return;
};
let offset = usize::from(recv.is_some());
for &p in &func.pass {
if p < offset {
out.extend(recv.map(|r| self.receiver(f, r)));
continue;
}
if p < func.positional
&& let Some(a) = args.get(p - offset)
{
self.eval(a, out);
}
if let Some((_, a)) = kwargs.iter().find(|(k, _)| Some(k) == func.names.get(p)) {
self.eval(a, out);
}
}
}
fn result(&self, site: usize, out: &mut Vec<Val>) {
let s = &self.sites[site];
for v in self.values(&s.func) {
if let Val::Class(c) = v {
out.push(Val::Inst(c));
} else if let Some((f, recv)) = self.callee(v) {
self.returns(f, recv, &s.args, &s.kwargs, out);
}
}
}
fn add(&mut self, v: u32, vals: &[Val]) -> bool {
let set = &mut self.pts[v as usize];
let mut changed = false;
for x in vals {
if set.len() >= MAX_VALUES {
break;
}
if let Err(i) = set.binary_search(x) {
set.insert(i, *x);
changed = true;
}
}
changed
}
/// Parameter flows of one call site: (parameter var, values).
fn bindings(&self, site: usize) -> Vec<(u32, Vec<Val>)> {
let s = &self.sites[site];
let mut flows = vec![];
for v in self.values(&s.func) {
let Some((f, recv)) = self.callee(v) else {
continue;
};
let Some(func) = self.funcs.get(&f) else {
continue;
};
let offset = usize::from(recv.is_some());
if let (Some(r), Some(&p0)) = (recv, func.params.first()) {
flows.push((p0, vec![self.receiver(f, r)]));
}
for (i, a) in s.args.iter().enumerate() {
if i + offset < func.positional {
flows.push((func.params[i + offset], self.values(a)));
}
}
for (k, a) in &s.kwargs {
if let Some(p) = func.names.iter().position(|n| n == k) {
flows.push((func.params[p], self.values(a)));
}
}
}
flows
}
/// Values a `for` loop over `iter` assigns, and the protocol methods it calls.
fn iteration(&self, iter: &E) -> (Vec<Val>, Vec<u32>) {
let (mut items, mut called) = (vec![], vec![]);
for v in self.values(iter) {
let Val::Inst(c) = v else {
items.push(v);
continue;
};
let Some(it) = self.method(c, self.iter) else {
continue;
};
called.push(it);
let mut iterators = vec![];
self.returns(it, Some(c), &[], &[], &mut iterators);
for i in iterators {
if let Val::Inst(k) = i
&& let Some(nx) = self.method(k, self.next)
{
called.push(nx);
self.returns(nx, Some(k), &[], &[], &mut items);
}
}
}
(items, called)
}
fn solve(&mut self) -> usize {
self.prepare_mros();
for pass in 1..=MAX_PASSES {
let mut changed = false;
for i in 0..self.cons.len() {
let flows: Vec<(u32, Vec<Val>)> = match &self.cons[i] {
Con::Flow(v, e) => vec![(*v, self.values(e))],
Con::Store(object, a, e) => {
let vals = self.values(e);
let (objects, a) = (self.values(object), *a);
let mut out = vec![];
for o in objects {
if let Val::Inst(c) | Val::Class(c) = o {
out.push((Key::Field(c, a), vals.clone()));
}
}
let mut flows = vec![];
for (k, vals) in out {
flows.push((self.var(k), vals));
}
flows
}
Con::Iter { iter, targets, .. } => {
let items = self.iteration(iter).0;
targets.iter().map(|t| (*t, items.clone())).collect()
}
};
for (v, vals) in flows {
changed |= self.add(v, &vals);
}
}
for i in 0..self.sites.len() {
for (v, vals) in self.bindings(i) {
changed |= self.add(v, &vals);
}
}
if !changed {
return pass;
}
}
MAX_PASSES
}
/// Graph ids a call site may run.
fn site_targets(&self, func: &E) -> Vec<u32> {
let mut out = vec![];
for v in self.values(func) {
match v {
Val::Func(f) | Val::Bound(f, _) => out.push(f),
Val::Class(c) => out.push(c),
Val::Inst(c) => out.extend(self.method(c, self.call)),
Val::Module(_) => {}
}
}
out.sort_unstable();
out.dedup();
out
}
}
fn edge(src: &str, tgt: &str, line: usize, file: &str, resolution: &str) -> Value {
json!({"source": src, "target": tgt, "relation": "calls", "context": "call",
"confidence": "INFERRED", "confidence_score": 0.85, "source_file": file,
"source_location": format!("L{line}"), "weight": 1.0, "_origin": "ast",
"resolution": resolution})
}
/// Add precise `calls` edges for the Python files among `paths`. `context_*`
/// is the rest of the graph when only some files are being re-extracted; its
/// Python files are analysed too, but only callers in `paths` get edges.
pub fn resolve(
paths: &[PathBuf],
nodes: &[Value],
edges: &mut Vec<Value>,
context_nodes: &[Value],
context_edges: &[Value],
root: &Path,
) {
let started = std::time::Instant::now();
let timing = std::env::var("GRAPHICLE_PRECISE_TIMING").is_ok_and(|v| v == "1");
let all_nodes = nodes.iter().chain(context_nodes).collect::<Vec<_>>();
let all_edges = edges.iter().chain(context_edges).collect::<Vec<_>>();
let facts = Facts::build(&all_nodes, &all_edges, root);
let mut files: Vec<(PathBuf, String)> = vec![];
let mut seen = FxHashSet::default();
for p in paths
.iter()
.filter(|p| p.extension().is_some_and(|e| e == "py"))
{
let key = source_key(&p.to_string_lossy(), root);
if seen.insert(key.clone()) {
files.push((p.clone(), key));
}
}
let emit = seen.clone();
for n in context_nodes {
let sf = s(n, "source_file");
if sf.ends_with(".py") && Path::new(sf).file_name() == Path::new(s(n, "label")).file_name()
{
let key = source_key(sf, root);
let path = if Path::new(sf).is_absolute() {
PathBuf::from(sf)
} else {
root.join(sf)
};
if seen.insert(key.clone()) {
files.push((path, key));
}
}
}
let irs = build_all(&files, &facts);
let parsed = started.elapsed();
let mut sv = Solver::default();
for id in facts.label.keys() {
let label = &facts.label[id];
if label.ends_with(')') {
let i = sv.ids.id(id);
sv.functions.insert(i);
}
}
for c in facts
.classes
.iter()
.chain(irs.iter().flatten().flat_map(|ir| &ir.classes))
{
let i = sv.ids.id(c);
sv.classes.insert(i);
}
for ((c, name), m) in &facts.methods {
let key = (sv.ids.id(c), sv.syms.id(name));
let m = sv.ids.id(m);
sv.methods.insert(key, m);
}
for (c, bases) in &facts.bases {
let c = sv.ids.id(c);
let bases = bases.iter().map(|b| sv.ids.id(b)).collect();
sv.bases.insert(c, bases);
}
for key in facts.file_node.keys() {
let path = Path::new(key);
let (package, name) = if path.file_name().is_some_and(|f| f == "__init__.py") {
let dir = path.parent().unwrap_or(Path::new(""));
(dir.parent().unwrap_or(Path::new("")), module_stem(key))
} else {
(path.parent().unwrap_or(Path::new("")), module_stem(key))
};
let init = package.join("__init__.py").to_string_lossy().into_owned();
if facts.file_node.contains_key(&init) {
let k = (sv.files.id(&init), sv.syms.id(name));
let m = sv.files.id(key);
sv.submodules.insert(k, m);
}
}
sv.init = sv.syms.id("__init__");
sv.call = sv.syms.id("__call__");
sv.iter = sv.syms.id("__iter__");
sv.next = sv.syms.id("__next__");
let mut file_info: Vec<(String, bool)> = vec![];
let mut scope_base = 0u32;
for ir in irs.iter().flatten() {
let file = file_info.len();
file_info.push((ir.path.clone(), emit.contains(&ir.key)));
if !ir.stars.is_empty() {
let f = sv.files.id(&ir.key);
let sources = ir.stars.iter().map(|k| sv.files.id(k)).collect();
sv.stars.insert(f, sources);
for name in &ir.module_names {
let name = sv.syms.id(name);
sv.bound.insert((f, name));
}
}
let sites = sv.sites.len() as u32;
for f in &ir.funcs {
let params = f
.params
.iter()
.map(|p| sv.slot(scope_base, &Slot::Local(f.scope, p.clone())))
.collect();
let names = f.params.iter().map(|p| sv.syms.id(p)).collect();
let id = sv.ids.id(&f.id);
sv.funcs.insert(
id,
Func {
params,
names,
positional: f.positional,
pass: f.pass.clone(),
kind: f.kind,
},
);
}
for site in &ir.sites {
let caller = site.caller.as_ref().map(|c| sv.ids.id(c));
let func = sv.conv(scope_base, sites, &site.func);
let args = site
.args
.iter()
.map(|a| sv.conv(scope_base, sites, a))
.collect();
let kwargs = site
.kwargs
.iter()
.map(|(k, a)| (sv.syms.id(k), sv.conv(scope_base, sites, a)))
.collect();
let super_name = site.super_name.as_ref().map(|n| sv.syms.id(n));
sv.sites.push(Site {
caller,
file,
line: site.line,
func,
args,
kwargs,
super_name,
});
}
for c in &ir.cons {
let con = match c {
ConB::Flow(slot, e) => {
Con::Flow(sv.slot(scope_base, slot), sv.conv(scope_base, sites, e))
}
ConB::Store(o, a, e) => {
let o = sv.conv(scope_base, sites, o);
let a = sv.syms.id(a);
Con::Store(o, a, sv.conv(scope_base, sites, e))
}
ConB::Iter {
caller,
line,
iter,
targets,
} => Con::Iter {
caller: caller.as_ref().map(|c| sv.ids.id(c)),
file,
line: *line,
iter: sv.conv(scope_base, sites, iter),
targets: targets.iter().map(|t| sv.slot(scope_base, t)).collect(),
},
};
sv.cons.push(con);
}
scope_base += ir.scopes as u32;
}
drop(irs);
let interned = started.elapsed();
let passes = sv.solve();
let solved = started.elapsed();
// A `super().m` site replaces the default engine's same-named guesses.
let mut drop_edges: FxHashSet<(String, String, String)> = FxHashSet::default();
let mut by_site: FxHashMap<(&str, usize), Vec<&Value>> = FxHashMap::default();
for e in edges.iter().filter(|e| s(e, "relation") == "calls") {
if let Some(l) = location(e) {
by_site.entry((s(e, "source"), l)).or_default().push(e);
}
}
for site in &sv.sites {
let (Some(caller), Some(name)) = (site.caller, site.super_name) else {
continue;
};
let targets = sv.site_targets(&site.func);
if targets.is_empty() || !file_info[site.file].1 {
continue;
}
let (caller, name) = (sv.ids.name(caller), sv.syms.name(name));
for e in by_site.get(&(caller, site.line)).into_iter().flatten() {
let tgt = s(e, "target");
if facts.label.get(tgt).is_some_and(|l| bare(l) == name)
&& !targets.iter().any(|t| sv.ids.name(*t) == tgt)
{
drop_edges.insert((caller.into(), tgt.into(), s(e, "source_location").into()));
}
}
}
drop(by_site);
let drop_count = drop_edges.len();
if !drop_edges.is_empty() {
edges.retain(|e| {
!(s(e, "relation") == "calls"
&& drop_edges.contains(&(
s(e, "source").into(),
s(e, "target").into(),
s(e, "source_location").into(),
)))
});
}
// Edges, in file and site order, callees sorted by id. The graph keeps one
// edge per node pair (either direction when undirected), so a pair that
// already has any edge gets no second one.
let mut have = edges
.iter()
.chain(context_edges)
.flat_map(|e| {
let (a, b) = (s(e, "source").to_string(), s(e, "target").to_string());
[(a.clone(), b.clone()), (b, a)]
})
.collect::<FxHashSet<_>>();
let mut added = vec![];
let mut emit_site =
|caller: u32, file: usize, l: usize, targets: Vec<u32>, resolution: &str| {
let (path, emit) = &file_info[file];
if !*emit || targets.is_empty() || targets.len() > MAX_TARGETS {
return;
}
let caller = sv.ids.name(caller);
let mut names = targets.iter().map(|t| sv.ids.name(*t)).collect::<Vec<_>>();
names.sort_unstable();
for t in names {
if have.insert((caller.to_string(), t.to_string())) {
have.insert((t.to_string(), caller.to_string()));
added.push(edge(caller, t, l, path, resolution));
}
}
};
for site in &sv.sites {
let Some(caller) = site.caller else { continue };
let resolution = if site.super_name.is_some() {
"super_call"
} else {
"points_to"
};
emit_site(
caller,
site.file,
site.line,
sv.site_targets(&site.func),
resolution,
);
}
for c in &sv.cons {
if let Con::Iter {
caller: Some(caller),
file,
line,
iter,
..
} = c
{
let mut called = sv.iteration(iter).1;
called.sort_unstable();
called.dedup();
emit_site(*caller, *file, *line, called, "points_to");
}
}
if timing {
eprintln!(
"[precise timing] files={} sites={} constraints={} vars={} passes={passes} \
added={} dropped={} parse+ir={:.0}ms intern={:.0}ms solve={:.0}ms emit={:.0}ms",
file_info.len(),
sv.sites.len(),
sv.cons.len(),
sv.pts.len(),
added.len(),
drop_count,
parsed.as_secs_f64() * 1e3,
(interned - parsed).as_secs_f64() * 1e3,
(solved - interned).as_secs_f64() * 1e3,
(started.elapsed() - solved).as_secs_f64() * 1e3,
);
}
edges.extend(added);
}
#[cfg(test)]
mod tests {
use crate::extract::{ExtractOptions, extract};
use serde_json::Value;
use std::path::{Path, PathBuf};
fn write(root: &Path, rel: &str, body: &str) -> PathBuf {
let p = root.join(rel);
std::fs::create_dir_all(p.parent().unwrap()).unwrap();
std::fs::write(&p, body).unwrap();
p
}
fn run(files: &[(&str, &str)], precise: bool) -> Value {
let dir = tempfile::tempdir().unwrap();
let root = dir.path().canonicalize().unwrap();
let paths = files
.iter()
.map(|(rel, body)| write(&root, rel, body))
.collect::<Vec<_>>();
let _serial = crate::extractors::parse_cache::test_serial();
extract(
&paths,
&ExtractOptions {
root: Some(root.clone()),
parallel: false,
use_cache: false,
receiver_resolution: false,
precise,
..Default::default()
},
)
.unwrap()
}
/// (source label, target label, resolution) of every `calls` edge.
fn calls(v: &Value) -> Vec<(String, String, String)> {
let label = |id: &str| {
v["nodes"]
.as_array()
.unwrap()
.iter()
.find(|n| n["id"] == id)
.map(|n| n["label"].as_str().unwrap().to_string())
.unwrap_or_default()
};
let mut out = v["edges"]
.as_array()
.unwrap()
.iter()
.filter(|e| e["relation"] == "calls")
.map(|e| {
(
label(e["source"].as_str().unwrap()),
label(e["target"].as_str().unwrap()),
e["resolution"].as_str().unwrap_or("").to_string(),
)
})
.collect::<Vec<_>>();
out.sort();
out
}
fn has(v: &Value, src: &str, tgt: &str) -> bool {
calls(v).iter().any(|(s, t, _)| s == src && t == tgt)
}
fn precise_edges(v: &Value) -> Vec<(String, String, String)> {
calls(v)
.into_iter()
.filter(|(_, _, r)| !r.is_empty())
.collect()
}
#[test]
fn default_mode_adds_nothing() {
let files = [(
"main.py",
"def g():\n pass\n\ndef f(cb):\n cb()\n\ndef h():\n f(g)\n",
)];
assert!(precise_edges(&run(&files, false)).is_empty());
assert!(has(&run(&files, true), "f()", "g()"));
}
#[test]
fn super_call_replaces_the_same_named_guess() {
let files = [(
"main.py",
"class A:\n def run(self):\n pass\n\nclass B(A):\n def run(self):\n super().run()\n\nclass C:\n def run(self):\n pass\n",
)];
let v = run(&files, true);
let from_b = calls(&v)
.into_iter()
.filter(|(s, t, _)| s == ".run()" && t == ".run()")
.collect::<Vec<_>>();
// Only the base-class edge survives; labels are shared, so check ids.
let ids = v["edges"]
.as_array()
.unwrap()
.iter()
.filter(|e| e["relation"] == "calls")
.map(|e| (e["source"].as_str().unwrap(), e["target"].as_str().unwrap()))
.collect::<Vec<_>>();
assert!(ids.contains(&("main_b_run", "main_a_run")), "{ids:?}");
assert!(!ids.contains(&("main_b_run", "main_c_run")), "{ids:?}");
assert!(!from_b.is_empty());
}
#[test]
fn values_flow_through_parameters_defaults_and_returns() {
let files = [(
"main.py",
"def a():\n pass\n\ndef b():\n pass\n\ndef pick():\n return b\n\n\
def ident(x):\n return x\n\n\
def run(cb, other=a):\n cb()\n other()\n\n\
def main():\n run(pick())\n run(cb=ident(a))\n alias = run\n alias(b)\n",
)];
let v = run(&files, true);
assert!(has(&v, "run()", "b()"));
assert!(has(&v, "run()", "a()"));
// `ident` passes its argument through per call site.
assert!(!has(&v, "main()", "b()"));
assert!(has(&v, "main()", "ident()"));
}
#[test]
fn python_dispatch_uses_module_globals_past_enclosing_locals() {
let v = run(
&[(
"main.py",
"def intended():\n pass\ndef shadow():\n pass\ncallback = intended\ndef outer():\n callback = shadow\n def inner():\n global callback\n callback()\n return inner\ndef entry():\n outer()()\n",
)],
true,
);
assert!(has(&v, "inner()", "intended()"), "{:?}", calls(&v));
assert!(!has(&v, "inner()", "shadow()"), "{:?}", calls(&v));
}
#[test]
fn python_dispatch_uses_c3_method_order_for_a_diamond() {
let v = run(
&[(
"main.py",
"class A:\n def run(self):\n pass\nclass B(A):\n pass\nclass C(A):\n def run(self):\n pass\nclass D(B, C):\n def invoke(self):\n super().run()\n",
)],
true,
);
let targets = v["edges"]
.as_array()
.unwrap()
.iter()
.filter(|e| e["source"] == "main_d_invoke" && e["relation"] == "calls")
.map(|e| e["target"].as_str().unwrap())
.collect::<Vec<_>>();
assert_eq!(targets, ["main_c_run"]);
}
#[test]
fn reassigned_names_and_unknown_callers_stay_quiet() {
let files = [(
"main.py",
"import os\n\ndef g():\n pass\n\ndef f(cb):\n cb = os.getcwd\n cb()\n\ndef h():\n f(g)\n",
)];
let v = run(&files, true);
// Flow-insensitive: the parameter still holds `g`.
assert!(has(&v, "f()", "g()"));
// Calls of names with no known value add nothing.
assert!(
precise_edges(&v)
.iter()
.all(|(s, t, _)| s == "f()" && t == "g()")
);
}
#[test]
fn instances_fields_and_dynamic_dispatch() {
let files = [(
"main.py",
"class Base:\n def go(self):\n self.step()\n def step(self):\n pass\n\n\
class Child(Base):\n def __init__(self):\n self.cb = self.done\n def step(self):\n self.cb()\n def done(self):\n pass\n\n\
class Holder:\n def __init__(self, item):\n self.item = item\n def use(self):\n self.item.go()\n\n\
def main():\n h = Holder(Child())\n h.use()\n",
)];
let v = run(&files, true);
let ids = v["edges"]
.as_array()
.unwrap()
.iter()
.filter(|e| e["relation"] == "calls")
.map(|e| (e["source"].as_str().unwrap(), e["target"].as_str().unwrap()))
.collect::<Vec<_>>();
assert!(
ids.contains(&("main_holder_use", "main_base_go")),
"{ids:?}"
);
assert!(
ids.contains(&("main_base_go", "main_child_step")),
"{ids:?}"
);
assert!(
ids.contains(&("main_child_step", "main_child_done")),
"{ids:?}"
);
}
#[test]
fn decorators_imports_and_containers() {
let files = [
(
"lib.py",
"def wrap(f):\n def inner():\n f()\n return inner\n\ndef keep(f):\n return f\n\ndef run_all(fs):\n for f in fs:\n f()\n",
),
(
"main.py",
"from lib import wrap, keep, run_all\nimport lib as L\n\n\
@wrap\ndef task():\n pass\n\n@keep\ndef other():\n pass\n\n\
def main():\n task()\n other()\n run_all([other])\n table = {'x': L.keep}\n table['x'](other)\n",
),
];
let v = run(&files, true);
assert!(has(&v, "main()", "inner()"), "{:?}", calls(&v));
assert!(has(&v, "inner()", "task()"));
assert!(has(&v, "run_all()", "other()"));
assert!(has(&v, "main()", "keep()"));
}
#[test]
fn deeply_nested_generated_code_is_bounded() {
// A long concatenation parses as a left-deep tree thousands of levels
// down; the builder must stop at MAX_DEPTH within its worker stack
// (in debug builds too) and still see the rest of the file.
let dir = tempfile::tempdir().unwrap();
let terms = vec!["'x'"; 6000].join(" + ");
let path = write(
dir.path(),
"gen.py",
&format!("def f(cb):\n s = {terms}\n cb()\n\nf(print)\n"),
);
// `build_all` runs the builders on their own big-stack workers, so the
// caller's (here: the test thread's) stack size does not matter.
let irs = super::build_all(&[(path, "gen.py".into())], &super::Facts::default());
// The deep expression is cut off; the call after it is still seen.
assert!(irs[0].as_ref().is_some_and(|ir| !ir.sites.is_empty()));
}
#[test]
fn ambiguous_sites_add_no_edges() {
let mut body = String::new();
for i in 0..(super::MAX_TARGETS + 1) {
body.push_str(&format!("def f{i}():\n pass\n\n"));
}
let names = (0..=super::MAX_TARGETS)
.map(|i| format!("f{i}"))
.collect::<Vec<_>>();
body.push_str(&format!(
"HANDLERS = [{}]\n\ndef main(k):\n HANDLERS[k]()\n",
names.join(", ")
));
let v = run(&[("main.py", &body)], true);
assert!(precise_edges(&v).is_empty(), "{:?}", precise_edges(&v));
}
}