use alloc::vec::Vec;
use crate::stack::build::StackBuilder;
use crate::stack::{Definition, ScopeType, StackNode, StackScope, SymbolPop};
use crate::syntax::{SyntaxGraph, SyntaxKind, SyntaxNode};
use crate::{CodeGraph, Language, NodeId};
const SCOPES: [(SyntaxKind, ScopeType); 3] = [
(SyntaxKind::MethodDeclaration, ScopeType::Function),
(SyntaxKind::Class, ScopeType::Class),
(SyntaxKind::Declaration, ScopeType::Declaration),
];
impl StackBuilder {
pub(super) fn add_scopes(&mut self, syntax: &SyntaxGraph, language: Language) {
let scopes: Vec<NodeId> = SCOPES
.iter()
.flat_map(|(kind, scope_type)| {
syntax
.nodes_by_type
.get(kind)
.into_iter()
.flatten()
.map(move |id| (*id, *scope_type))
})
.map(|(id, scope_type)| {
self.graph.add_node(
id,
StackNode::Scope(StackScope {
scope_type: Some(scope_type),
}),
);
if scope_type == ScopeType::Class {
self.add_members(id);
}
id
})
.collect();
for scope in scopes {
self.link_scope(syntax, language, scope);
}
}
fn link_scope(&mut self, syntax: &SyntaxGraph, language: Language, scope: NodeId) {
let Some(parent) = self.stack_scope_parent(syntax, scope) else {
return;
};
if let Some(enclosing) = self.enclosing_scope(syntax, language, parent) {
self.graph.add_edge(scope, enclosing, 0);
}
if self.is_class(parent) {
self.add_receiver(syntax, language, parent, scope);
}
let Some(name) = statement_name(syntax, scope) else {
return;
};
if self.is_class(parent) {
self.add_member(language, parent, name, scope);
} else {
self.define(parent, name, scope);
}
}
fn stack_scope_parent(&self, syntax: &SyntaxGraph, scope: NodeId) -> Option<NodeId> {
syntax
.scope_parent
.get(&scope)
.copied()
.filter(|parent| matches!(self.graph.nodes.get(parent), Some(StackNode::Scope(_))))
}
fn enclosing_scope(
&self,
syntax: &SyntaxGraph,
language: Language,
parent: NodeId,
) -> Option<NodeId> {
let mut enclosing = parent;
while self.is_class(enclosing) && hides_class_body(language) {
enclosing = self.stack_scope_parent(syntax, enclosing)?;
}
Some(enclosing)
}
pub(super) fn define(&mut self, holder: NodeId, name: &str, target: NodeId) {
let definition = self.add(StackNode::PopSymbol(SymbolPop {
symbol: name.into(),
precedence: 1,
definition: Some(Definition::default()),
import: None,
}));
self.graph.add_edge(holder, definition, 1);
self.graph.add_edge(definition, target, 0);
if let Some(members) = self.members.get(&target) {
self.graph.add_edge(definition, members.gate, 0);
}
}
fn is_class(&self, scope: NodeId) -> bool {
matches!(
self.graph.nodes.get(&scope),
Some(StackNode::Scope(StackScope {
scope_type: Some(ScopeType::Class),
}))
)
}
}
const fn hides_class_body(language: Language) -> bool {
matches!(
language,
Language::Python | Language::JavaScript | Language::TypeScript
)
}
pub(super) fn is_statement(syntax: &SyntaxGraph, scope: NodeId) -> bool {
syntax.ast_parents(scope).iter().any(|parent| {
matches!(
syntax.nodes.get(parent),
Some(
SyntaxNode::File
| SyntaxNode::ExecutionBlock
| SyntaxNode::ClassBody
| SyntaxNode::Export { .. }
)
)
})
}
fn statement_name(syntax: &SyntaxGraph, scope: NodeId) -> Option<&str> {
syntax
.nodes
.get(&scope)
.and_then(SyntaxNode::name)
.filter(|name| !name.is_empty() && is_statement(syntax, scope))
}
#[cfg(test)]
mod tests {
use crate::stack::{build_stack_graph, ScopeType, StackGraph, StackNode, StackScope};
use crate::syntax::{SyntaxGraph, SyntaxNode};
use crate::{Language, NodeId};
use alloc::string::String;
use alloc::vec::Vec;
const FILE: NodeId = NodeId(1);
const HOLDER: NodeId = NodeId(2);
const OUTER: NodeId = NodeId(3);
const INNER: NodeId = NodeId(4);
const CLASS: NodeId = NodeId(5);
const BODY: NodeId = NodeId(6);
fn file_with(holder: SyntaxNode) -> SyntaxGraph {
let mut syntax = SyntaxGraph::new();
syntax.add_node(FILE, SyntaxNode::File);
syntax.add_node(HOLDER, holder);
syntax.add_ast_edge(FILE, HOLDER);
syntax
}
fn declare(
syntax: &mut SyntaxGraph,
function: NodeId,
name: Option<&str>,
at: (NodeId, NodeId),
) {
syntax.add_node(
function,
SyntaxNode::MethodDeclaration {
name: name.map(String::from),
access_modifiers: None,
block_id: None,
modifiers_id: None,
parameters_id: None,
},
);
syntax.add_ast_edge(at.0, function);
syntax.scope_parent.insert(function, at.1);
}
fn statement(name: &str) -> SyntaxGraph {
let mut syntax = file_with(SyntaxNode::ExecutionBlock);
declare(&mut syntax, OUTER, Some(name), (FILE, FILE));
syntax
}
fn stack(syntax: &SyntaxGraph) -> StackGraph {
build_stack_graph(syntax, Language::Python, "mod.py")
}
fn definitions_in(graph: &StackGraph, scope: NodeId) -> Vec<(&str, i64, Vec<NodeId>)> {
graph
.successors(scope)
.into_iter()
.filter_map(|(id, precedence)| {
let node = graph.nodes.get(&id).filter(|node| node.is_definition())?;
let targets = graph
.successors(id)
.into_iter()
.map(|(sink, _)| sink)
.filter(|sink| matches!(graph.nodes.get(sink), Some(StackNode::Scope(_))))
.collect();
Some((node.symbol()?, precedence, targets))
})
.collect()
}
#[test]
fn a_function_becomes_a_function_scope() {
let graph = stack(&statement("f"));
assert_eq!(
graph.nodes.get(&OUTER),
Some(&StackNode::Scope(StackScope {
scope_type: Some(ScopeType::Function),
}))
);
}
#[test]
fn a_function_scope_reaches_its_enclosing_scope() {
let graph = stack(&statement("f"));
assert_eq!(graph.successors(OUTER), [(FILE, 0)]);
}
#[test]
fn a_function_statement_defines_its_name_in_its_enclosing_scope_over_the_parent_edge() {
let graph = stack(&statement("f"));
assert_eq!(definitions_in(&graph, FILE), [("f", 1, Vec::from([OUTER]))]);
}
#[test]
fn a_nested_function_defines_its_name_in_the_outer_function() {
let mut syntax = statement("f");
syntax.add_ast_edge(OUTER, HOLDER);
declare(&mut syntax, INNER, Some("g"), (HOLDER, OUTER));
assert_eq!(
definitions_in(&stack(&syntax), OUTER),
[("g", 1, Vec::from([INNER]))]
);
}
#[test]
fn an_exported_function_defines_its_name_in_its_enclosing_scope() {
let mut syntax = file_with(SyntaxNode::Export {
expression: None,
declaration_id: Some(OUTER),
alias: None,
default_id: None,
});
declare(&mut syntax, OUTER, Some("f"), (HOLDER, FILE));
assert_eq!(
definitions_in(&stack(&syntax), FILE),
[("f", 1, Vec::from([OUTER]))]
);
}
#[test]
fn a_function_expression_does_not_define_its_name_in_the_enclosing_scope() {
let mut syntax = file_with(SyntaxNode::ArgumentList);
declare(&mut syntax, OUTER, Some("callback"), (HOLDER, FILE));
assert_eq!(definitions_in(&stack(&syntax), FILE), []);
}
#[test]
fn an_anonymous_function_defines_no_name() {
let mut syntax = file_with(SyntaxNode::ExecutionBlock);
declare(&mut syntax, OUTER, None, (FILE, FILE));
assert!(stack(&syntax)
.nodes
.values()
.all(|node| !node.is_definition()));
}
#[test]
fn a_function_whose_enclosing_scope_is_not_yet_a_stack_scope_stays_unlinked() {
let mut syntax = file_with(SyntaxNode::ExecutionBlock);
declare(&mut syntax, OUTER, Some("f"), (HOLDER, HOLDER));
let graph = stack(&syntax);
assert_eq!(graph.successors(OUTER), []);
assert!(graph.nodes.values().all(|node| !node.is_definition()));
}
fn class_named(name: &str) -> SyntaxNode {
SyntaxNode::Class {
name: String::from(name),
block_id: None,
modifiers_id: None,
inherited_class: None,
access_modifiers: None,
}
}
fn class_statement() -> SyntaxGraph {
let mut syntax = file_with(SyntaxNode::ExecutionBlock);
syntax.add_node(CLASS, class_named("C"));
syntax.add_ast_edge(FILE, CLASS);
syntax.scope_parent.insert(CLASS, FILE);
syntax.add_node(BODY, SyntaxNode::ExecutionBlock);
syntax.add_ast_edge(CLASS, BODY);
syntax
}
fn class_with_method() -> SyntaxGraph {
let mut syntax = class_statement();
declare(&mut syntax, OUTER, Some("m"), (BODY, CLASS));
syntax
}
#[test]
fn a_class_becomes_a_class_scope() {
let graph = stack(&class_statement());
assert_eq!(
graph.nodes.get(&CLASS),
Some(&StackNode::Scope(StackScope {
scope_type: Some(ScopeType::Class),
}))
);
}
#[test]
fn a_class_statement_defines_its_name_in_its_enclosing_scope_over_the_parent_edge() {
assert_eq!(
definitions_in(&stack(&class_statement()), FILE),
[("C", 1, Vec::from([CLASS]))]
);
}
#[test]
fn a_class_expression_does_not_define_its_name_in_the_enclosing_scope() {
let mut syntax = file_with(SyntaxNode::ArgumentList);
syntax.add_node(CLASS, class_named("C"));
syntax.add_ast_edge(HOLDER, CLASS);
syntax.scope_parent.insert(CLASS, FILE);
assert_eq!(definitions_in(&stack(&syntax), FILE), []);
}
#[test]
fn a_declaration_becomes_a_declaration_scope() {
let mut syntax = file_with(SyntaxNode::ExecutionBlock);
syntax.add_node(
CLASS,
SyntaxNode::Declaration {
name: String::from("Color"),
block_id: None,
access_modifiers: None,
},
);
syntax.add_ast_edge(FILE, CLASS);
syntax.scope_parent.insert(CLASS, FILE);
let graph = build_stack_graph(&syntax, Language::TypeScript, "mod.ts");
assert_eq!(
graph.nodes.get(&CLASS),
Some(&StackNode::Scope(StackScope {
scope_type: Some(ScopeType::Declaration),
}))
);
}
fn enclosing(graph: &StackGraph, scope: NodeId) -> Vec<NodeId> {
graph
.successors(scope)
.into_iter()
.map(|(sink, _)| sink)
.filter(|sink| matches!(graph.nodes.get(sink), Some(StackNode::Scope(_))))
.collect()
}
fn members_of(graph: &StackGraph, scope: NodeId, class: &str) -> Option<NodeId> {
let definition = graph
.successors(scope)
.into_iter()
.find_map(|(id, _)| (graph.nodes.get(&id)?.symbol() == Some(class)).then_some(id))?;
let gate = graph
.successors(definition)
.into_iter()
.find_map(|(id, _)| (graph.nodes.get(&id)?.symbol() == Some(".")).then_some(id))?;
match graph.successors(gate).as_slice() {
[(members, 0)] => Some(*members),
_ => None,
}
}
#[test]
fn a_class_name_leads_through_a_dot_to_a_scope_that_only_holds_its_members() {
let graph = stack(&class_with_method());
let members = members_of(&graph, FILE, "C").expect("the class opens its members");
assert_eq!(
definitions_in(&graph, members),
[("m", 1, Vec::from([OUTER]))]
);
assert_eq!(graph.successors(members).len(), 1);
}
#[test]
fn a_python_method_is_defined_in_its_class_body_too() {
assert_eq!(
definitions_in(&stack(&class_with_method()), CLASS),
[("m", 1, Vec::from([OUTER]))]
);
}
#[test]
fn a_javascript_method_is_defined_only_among_the_class_members() {
let graph = build_stack_graph(&class_with_method(), Language::JavaScript, "mod.js");
let members = members_of(&graph, FILE, "C").expect("the class opens its members");
assert_eq!(definitions_in(&graph, CLASS), []);
assert_eq!(
definitions_in(&graph, members),
[("m", 1, Vec::from([OUTER]))]
);
}
#[test]
fn a_python_method_reaches_the_scope_enclosing_its_class() {
assert_eq!(enclosing(&stack(&class_with_method()), OUTER), [FILE]);
}
#[test]
fn a_java_method_reaches_its_class_scope() {
let graph = build_stack_graph(&class_with_method(), Language::Java, "Mod.java");
assert_eq!(enclosing(&graph, OUTER), [CLASS]);
}
#[test]
fn a_class_nested_in_a_python_class_reaches_past_every_enclosing_class() {
let mut syntax = class_statement();
syntax.add_node(INNER, class_named("D"));
syntax.add_ast_edge(BODY, INNER);
syntax.scope_parent.insert(INNER, CLASS);
declare(&mut syntax, OUTER, Some("m"), (INNER, INNER));
assert_eq!(enclosing(&stack(&syntax), OUTER), [FILE]);
}
#[test]
fn a_class_inside_a_function_reaches_the_function_scope() {
let mut syntax = statement("f");
syntax.add_node(CLASS, class_named("C"));
syntax.add_ast_edge(OUTER, BODY);
syntax.add_node(BODY, SyntaxNode::ExecutionBlock);
syntax.add_ast_edge(BODY, CLASS);
syntax.scope_parent.insert(CLASS, OUTER);
assert_eq!(stack(&syntax).successors(CLASS), [(OUTER, 0)]);
}
const PARAMETERS: NodeId = NodeId(7);
const RECEIVER: NodeId = NodeId(8);
const MODIFIERS: NodeId = NodeId(9);
const DECORATOR: NodeId = NodeId(10);
fn method_taking(receiver: &str) -> SyntaxGraph {
let mut syntax = class_statement();
syntax.add_node(
OUTER,
SyntaxNode::MethodDeclaration {
name: Some(String::from("m")),
access_modifiers: None,
block_id: None,
modifiers_id: None,
parameters_id: Some(PARAMETERS),
},
);
syntax.add_ast_edge(BODY, OUTER);
syntax.scope_parent.insert(OUTER, CLASS);
syntax.add_node(PARAMETERS, SyntaxNode::ParameterList);
syntax.add_ast_edge(OUTER, PARAMETERS);
syntax.add_node(RECEIVER, lookup(receiver));
syntax.add_ast_edge(PARAMETERS, RECEIVER);
syntax
}
fn lookup(symbol: &str) -> SyntaxNode {
SyntaxNode::SymbolLookup {
symbol: String::from(symbol),
symbol_scope: Some(OUTER),
value: None,
}
}
#[test]
fn the_first_parameter_of_a_python_method_opens_the_class_members() {
let graph = stack(&method_taking("this_object"));
let members = members_of(&graph, FILE, "C");
assert!(members.is_some());
assert_eq!(members_of(&graph, OUTER, "this_object"), members);
}
#[test]
fn a_python_static_method_has_no_receiver() {
let mut syntax = method_taking("value");
syntax.add_node(MODIFIERS, SyntaxNode::Modifiers);
syntax.add_ast_edge(OUTER, MODIFIERS);
syntax.add_node(DECORATOR, lookup("staticmethod"));
syntax.add_ast_edge(MODIFIERS, DECORATOR);
assert_eq!(members_of(&stack(&syntax), OUTER, "value"), None);
}
fn java_method(access_modifiers: Option<&str>) -> SyntaxGraph {
let mut syntax = class_statement();
syntax.add_node(
OUTER,
SyntaxNode::MethodDeclaration {
name: Some(String::from("m")),
access_modifiers: access_modifiers.map(String::from),
block_id: None,
modifiers_id: None,
parameters_id: None,
},
);
syntax.add_ast_edge(BODY, OUTER);
syntax.scope_parent.insert(OUTER, CLASS);
syntax
}
#[test]
fn a_java_instance_method_binds_this_to_the_class_members() {
let graph = build_stack_graph(&java_method(Some("public")), Language::Java, "C.java");
let members = members_of(&graph, FILE, "C");
assert!(members.is_some());
assert_eq!(members_of(&graph, OUTER, "this"), members);
}
#[test]
fn a_java_static_method_has_no_this() {
let syntax = java_method(Some("public static"));
let graph = build_stack_graph(&syntax, Language::Java, "C.java");
assert_eq!(members_of(&graph, OUTER, "this"), None);
}
#[test]
fn a_javascript_method_binds_this_to_the_class_members() {
let graph = build_stack_graph(&class_with_method(), Language::JavaScript, "mod.js");
let members = members_of(&graph, FILE, "C");
assert!(members.is_some());
assert_eq!(members_of(&graph, OUTER, "this"), members);
}
}