use std::collections::HashMap;
use crate::nodes::*;
use crate::{AstNodeArena, NodeId, StringInterner, TypedNodeRef};
#[derive(Debug, Clone)]
pub struct SymbolInfo {
pub decl_node_id: NodeId,
pub kind: SymbolKind,
pub scope_depth: usize,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SymbolKind {
Variable,
Parameter,
Function,
Class,
Field,
Module,
}
#[derive(Debug, Default, Clone)]
pub struct SymbolTable {
resolutions: HashMap<NodeId, SymbolInfo>,
}
impl SymbolTable {
pub fn new() -> Self {
Self {
resolutions: HashMap::new(),
}
}
pub fn record_resolution(&mut self, identifier_id: NodeId, info: SymbolInfo) {
self.resolutions.insert(identifier_id, info);
}
pub fn resolve(&self, identifier_id: NodeId) -> Option<&SymbolInfo> {
self.resolutions.get(&identifier_id)
}
pub fn all_resolutions(&self) -> &HashMap<NodeId, SymbolInfo> {
&self.resolutions
}
}
pub struct SymbolResolver<'a> {
nodes: &'a AstNodeArena,
#[allow(dead_code)] strings: &'a StringInterner,
symbol_table: SymbolTable,
scopes: Vec<HashMap<u32, SymbolInfo>>, scope_depth: usize,
}
impl<'a> SymbolResolver<'a> {
pub fn new(nodes: &'a AstNodeArena, strings: &'a StringInterner) -> Self {
Self {
nodes,
strings,
symbol_table: SymbolTable::new(),
scopes: vec![HashMap::new()], scope_depth: 0,
}
}
pub fn resolve_module(mut self, module: TypedNodeRef<Module>) -> SymbolTable {
self.declare_hoisted_symbols(module);
self.visit_module(module);
self.symbol_table
}
fn declare_hoisted_symbols(&mut self, module: TypedNodeRef<Module>) {
let length = self.nodes.array.size(module.node.decls);
for i in 0..length {
if let Some(node_id) = self.nodes.array.get_node_id_at(module.node.decls, i) {
let decl = self.nodes.get_decl_node(node_id);
match decl.node {
DeclNode::Class(class) => {
let name_node = self.nodes.get_identifier_node(class.name);
self.declare_symbol(
name_node.node.name,
SymbolInfo {
decl_node_id: decl.id,
kind: SymbolKind::Class,
scope_depth: self.scope_depth,
},
);
}
DeclNode::Function(func) => {
let func_expr = self.nodes.get_func_expr_node(func.function);
let name_node = self.nodes.get_identifier_node(func_expr.node.name);
self.declare_symbol(
name_node.node.name,
SymbolInfo {
decl_node_id: decl.id,
kind: SymbolKind::Function,
scope_depth: self.scope_depth,
},
);
}
DeclNode::Module(module_decl) => {
let name_node = self.nodes.get_identifier_node(module_decl.name);
self.declare_symbol(
name_node.node.name,
SymbolInfo {
decl_node_id: decl.id,
kind: SymbolKind::Module,
scope_depth: self.scope_depth,
},
);
}
_ => {
}
}
}
}
}
fn begin_scope(&mut self) {
self.scope_depth += 1;
self.scopes.push(HashMap::new());
}
fn end_scope(&mut self) {
self.scopes.pop();
self.scope_depth -= 1;
}
fn declare_symbol(&mut self, name: u32, info: SymbolInfo) {
if let Some(current_scope) = self.scopes.last_mut() {
current_scope.insert(name, info);
}
}
fn resolve_identifier(&mut self, identifier: TypedNodeRef<IdentifierNode>) {
let name = identifier.node.name;
for scope in self.scopes.iter().rev() {
if let Some(info) = scope.get(&name) {
self.symbol_table
.record_resolution(identifier.id, info.clone());
return;
}
}
}
fn visit_module(&mut self, module: TypedNodeRef<Module>) {
let length = self.nodes.array.size(module.node.decls);
for i in 0..length {
if let Some(node_id) = self.nodes.array.get_node_id_at(module.node.decls, i) {
let decl = self.nodes.get_decl_node(node_id);
self.visit_decl(decl);
}
}
}
fn visit_decl(&mut self, decl: TypedNodeRef<DeclNode>) {
match decl.node {
DeclNode::Class(class) => self.visit_class(TypedNodeRef::new(decl.id, class)),
DeclNode::Function(func) => self.visit_function(TypedNodeRef::new(decl.id, func)),
DeclNode::Variable(var) => self.visit_variable(TypedNodeRef::new(decl.id, var)),
DeclNode::Lambda(lambda) => self.visit_lambda_decl(TypedNodeRef::new(decl.id, lambda)),
DeclNode::Stmt(stmt) => self.visit_statement(TypedNodeRef::new(decl.id, stmt)),
DeclNode::Module(_module_decl) => {
}
}
}
fn visit_class(&mut self, class: TypedNodeRef<ClassDeclNode>) {
if let Some(superclass_id) = class.node.superclass {
let superclass_node = self.nodes.get_identifier_node(superclass_id);
self.resolve_identifier(superclass_node);
}
let length = self.nodes.array.size(class.node.members);
for i in 0..length {
if let Some(member_id) = self.nodes.array.get_node_id_at(class.node.members, i) {
let member = self.nodes.get_class_member_node(member_id);
self.visit_class_member(member);
}
}
}
fn visit_class_member(&mut self, member: TypedNodeRef<ClassMemberNode>) {
match member.node {
ClassMemberNode::Method(method) => {
self.visit_method(TypedNodeRef::new(member.id, method))
}
ClassMemberNode::Field(field) => self.visit_field(TypedNodeRef::new(member.id, field)),
}
}
fn visit_method(&mut self, method: TypedNodeRef<FunctionExprNode>) {
self.begin_scope();
let params_length = self.nodes.array.size(method.node.parameters);
for i in 0..params_length {
if let Some(param_id) = self.nodes.array.get_node_id_at(method.node.parameters, i) {
let param = self.nodes.get_identifier_node(param_id);
self.declare_symbol(
param.node.name,
SymbolInfo {
decl_node_id: param.id,
kind: SymbolKind::Parameter,
scope_depth: self.scope_depth,
},
);
}
}
let body = self.nodes.get_block_stmt_node(method.node.body);
self.visit_block(body);
self.end_scope();
}
fn visit_field(&mut self, field: TypedNodeRef<FieldDeclNode>) {
if let Some(init_id) = field.node.initializer {
let init_expr = self.nodes.get_expr_node(init_id);
self.visit_expression(init_expr);
}
}
fn visit_function(&mut self, func: TypedNodeRef<FunctionDeclNode>) {
let func_expr = self.nodes.get_func_expr_node(func.node.function);
self.begin_scope();
let params_length = self.nodes.array.size(func_expr.node.parameters);
for i in 0..params_length {
if let Some(param_id) = self
.nodes
.array
.get_node_id_at(func_expr.node.parameters, i)
{
let param = self.nodes.get_identifier_node(param_id);
self.declare_symbol(
param.node.name,
SymbolInfo {
decl_node_id: param.id,
kind: SymbolKind::Parameter,
scope_depth: self.scope_depth,
},
);
}
}
let body = self.nodes.get_block_stmt_node(func_expr.node.body);
self.visit_block(body);
self.end_scope();
}
fn visit_lambda_decl(&mut self, lambda: TypedNodeRef<LambdaDeclNode>) {
let name_node = self.nodes.get_identifier_node(lambda.node.name);
self.declare_symbol(
name_node.node.name,
SymbolInfo {
decl_node_id: lambda.id,
kind: SymbolKind::Function,
scope_depth: self.scope_depth,
},
);
let lambda_expr = self.nodes.get_lambda_expr_node(lambda.node.lambda);
self.visit_lambda_expr(lambda_expr);
}
fn visit_lambda_expr(&mut self, lambda: TypedNodeRef<LambdaExprNode>) {
self.begin_scope();
let params_length = self.nodes.array.size(lambda.node.parameters);
for i in 0..params_length {
if let Some(param_id) = self.nodes.array.get_node_id_at(lambda.node.parameters, i) {
let param = self.nodes.get_identifier_node(param_id);
self.declare_symbol(
param.node.name,
SymbolInfo {
decl_node_id: param.id,
kind: SymbolKind::Parameter,
scope_depth: self.scope_depth,
},
);
}
}
let node = self.nodes.get_node(lambda.node.body);
if matches!(node, AstNode::BlockStmt(_)) {
let block = self.nodes.get_block_stmt_node(lambda.node.body);
self.visit_block(block);
} else {
let expr = self.nodes.get_expr_node(lambda.node.body);
self.visit_expression(expr);
}
self.end_scope();
}
fn visit_variable(&mut self, var: TypedNodeRef<VariableDeclNode>) {
let name_node = self.nodes.get_identifier_node(var.node.target);
if let Some(init_id) = var.node.initializer {
let init_expr = self.nodes.get_expr_node(init_id);
self.visit_expression(init_expr);
}
self.declare_symbol(
name_node.node.name,
SymbolInfo {
decl_node_id: var.id,
kind: SymbolKind::Variable,
scope_depth: self.scope_depth,
},
);
}
fn visit_block(&mut self, block: TypedNodeRef<BlockStmtNode>) {
self.begin_scope();
let length = self.nodes.array.size(block.node.decls);
for i in 0..length {
if let Some(decl_id) = self.nodes.array.get_node_id_at(block.node.decls, i) {
let decl = self.nodes.get_decl_node(decl_id);
match decl.node {
DeclNode::Class(class) => {
let name_node = self.nodes.get_identifier_node(class.name);
self.declare_symbol(
name_node.node.name,
SymbolInfo {
decl_node_id: decl.id,
kind: SymbolKind::Class,
scope_depth: self.scope_depth,
},
);
}
DeclNode::Function(func) => {
let func_expr = self.nodes.get_func_expr_node(func.function);
let name_node = self.nodes.get_identifier_node(func_expr.node.name);
self.declare_symbol(
name_node.node.name,
SymbolInfo {
decl_node_id: decl.id,
kind: SymbolKind::Function,
scope_depth: self.scope_depth,
},
);
}
DeclNode::Module(module_decl) => {
let name_node = self.nodes.get_identifier_node(module_decl.name);
self.declare_symbol(
name_node.node.name,
SymbolInfo {
decl_node_id: decl.id,
kind: SymbolKind::Module,
scope_depth: self.scope_depth,
},
);
}
_ => {
}
}
}
}
for i in 0..length {
if let Some(decl_id) = self.nodes.array.get_node_id_at(block.node.decls, i) {
let decl = self.nodes.get_decl_node(decl_id);
self.visit_decl(decl);
}
}
self.end_scope();
}
fn visit_statement(&mut self, stmt: TypedNodeRef<StmtNode>) {
match stmt.node {
StmtNode::Expr(expr_stmt) => {
let expr = self.nodes.get_expr_node(expr_stmt.expr);
self.visit_expression(expr);
}
StmtNode::Block(block) => {
self.visit_block(TypedNodeRef::new(stmt.id, block));
}
StmtNode::If(if_stmt) => {
let cond = self.nodes.get_expr_node(if_stmt.condition);
self.visit_expression(cond);
let then_branch = self.nodes.get_stmt_node(if_stmt.then_branch);
self.visit_statement(then_branch);
if let Some(else_id) = if_stmt.else_branch {
let else_branch = self.nodes.get_stmt_node(else_id);
self.visit_statement(else_branch);
}
}
StmtNode::While(while_stmt) => {
let cond = self.nodes.get_expr_node(while_stmt.condition);
self.visit_expression(cond);
let body = self.nodes.get_stmt_node(while_stmt.body);
self.visit_statement(body);
}
StmtNode::For(for_stmt) => {
self.begin_scope();
if let Some(init_id) = for_stmt.initializer {
self.visit_for_initializer(init_id);
}
if let Some(cond_id) = for_stmt.condition {
let cond = self.nodes.get_expr_node(cond_id);
self.visit_expression(cond);
}
if let Some(after_id) = for_stmt.afterthought {
let after = self.nodes.get_expr_node(after_id);
self.visit_expression(after);
}
let body = self.nodes.get_stmt_node(for_stmt.body);
self.visit_statement(body);
self.end_scope();
}
StmtNode::Return(ret_stmt) => {
if let Some(value_id) = ret_stmt.value {
let value = self.nodes.get_expr_node(value_id);
self.visit_expression(value);
}
}
StmtNode::Break(_) | StmtNode::Continue(_) => {
}
}
}
fn visit_for_initializer(&mut self, init_id: NodeId) {
let node = self.nodes.get_node(init_id);
if matches!(node, AstNode::VariableDecl(_)) {
let var_decl = self.nodes.get_var_decl_node(init_id);
self.visit_variable(var_decl);
} else {
let expr = self.nodes.get_expr_node(init_id);
self.visit_expression(expr);
}
}
fn visit_expression(&mut self, expr: TypedNodeRef<ExprNode>) {
match expr.node {
ExprNode::Primary(primary) => {
self.visit_primary(TypedNodeRef::new(expr.id, primary));
}
ExprNode::Call(call) => {
let callee = self.nodes.get_expr_node(call.callee);
self.visit_expression(callee);
let op = self.nodes.get_call_operation_node(call.operation);
self.visit_call_operation(op);
}
ExprNode::Assignment(assign) => {
let target = self.nodes.get_assignment_target_node(assign.target);
self.visit_assignment_target(target);
let value = self.nodes.get_expr_node(assign.value);
self.visit_expression(value);
}
ExprNode::Unary(unary) => {
let operand = self.nodes.get_expr_node(unary.operand);
self.visit_expression(operand);
}
ExprNode::Equality(equality) => {
let left = self.nodes.get_expr_node(equality.left);
self.visit_expression(left);
let right = self.nodes.get_expr_node(equality.right);
self.visit_expression(right);
}
ExprNode::Comparison(comparison) => {
let left = self.nodes.get_expr_node(comparison.left);
self.visit_expression(left);
let right = self.nodes.get_expr_node(comparison.right);
self.visit_expression(right);
}
ExprNode::Term(term) => {
let left = self.nodes.get_expr_node(term.left);
self.visit_expression(left);
let right = self.nodes.get_expr_node(term.right);
self.visit_expression(right);
}
ExprNode::Factor(factor) => {
let left = self.nodes.get_expr_node(factor.left);
self.visit_expression(left);
let right = self.nodes.get_expr_node(factor.right);
self.visit_expression(right);
}
ExprNode::Pipe(pipe) => {
let left = self.nodes.get_expr_node(pipe.left);
self.visit_expression(left);
let right = self.nodes.get_expr_node(pipe.right);
self.visit_expression(right);
}
ExprNode::LogicalOr(logical) => {
let left = self.nodes.get_expr_node(logical.left);
self.visit_expression(left);
let right = self.nodes.get_expr_node(logical.right);
self.visit_expression(right);
}
ExprNode::LogicalAnd(logical) => {
let left = self.nodes.get_expr_node(logical.left);
self.visit_expression(left);
let right = self.nodes.get_expr_node(logical.right);
self.visit_expression(right);
}
ExprNode::Ternary(ternary) => {
let condition = self.nodes.get_expr_node(ternary.condition);
self.visit_expression(condition);
let then_expr = self.nodes.get_expr_node(ternary.then_expr);
self.visit_expression(then_expr);
let else_expr = self.nodes.get_expr_node(ternary.else_expr);
self.visit_expression(else_expr);
}
}
}
fn visit_call_operation(&mut self, op: TypedNodeRef<CallOperationNode>) {
match op.node {
CallOperationNode::Call(call_node) => {
let length = self.nodes.array.size(call_node.args);
for i in 0..length {
if let Some(arg_id) = self.nodes.array.get_node_id_at(call_node.args, i) {
let arg = self.nodes.get_expr_node(arg_id);
self.visit_expression(arg);
}
}
}
CallOperationNode::Property(_prop) => {
}
CallOperationNode::Index(index) => {
let index_expr = self.nodes.get_expr_node(index.index);
self.visit_expression(index_expr);
}
CallOperationNode::OptionalProperty(_)
| CallOperationNode::Map(_)
| CallOperationNode::OptionalMap(_) => {
}
}
}
fn visit_assignment_target(&mut self, target: TypedNodeRef<AssignmentTargetNode>) {
match target.node {
AssignmentTargetNode::Identifier(ident) => {
self.resolve_identifier(TypedNodeRef::new(target.id, ident));
}
AssignmentTargetNode::Property(prop) => {
let object = self.nodes.get_expr_node(prop.object);
self.visit_expression(object);
}
AssignmentTargetNode::Index(index) => {
let object = self.nodes.get_expr_node(index.object);
self.visit_expression(object);
let index_expr = self.nodes.get_expr_node(index.index);
self.visit_expression(index_expr);
}
}
}
fn visit_primary(&mut self, primary: TypedNodeRef<PrimaryNode>) {
match primary.node {
PrimaryNode::Identifier(ident) => {
self.resolve_identifier(TypedNodeRef::new(primary.id, ident));
}
PrimaryNode::Array(arr) => {
let length = self.nodes.array.size(arr.elements);
for i in 0..length {
if let Some(elem_id) = self.nodes.array.get_node_id_at(arr.elements, i) {
let elem = self.nodes.get_expr_node(elem_id);
self.visit_expression(elem);
}
}
}
PrimaryNode::Object(obj) => {
let length = self.nodes.array.size(obj.entries);
for i in 0..length {
if let Some(entry_id) = self.nodes.array.get_node_id_at(obj.entries, i) {
let entry = self.nodes.get_obj_entry_node(entry_id);
let value = self.nodes.get_expr_node(entry.node.value);
self.visit_expression(value);
}
}
}
PrimaryNode::Grouping(group) => {
let inner = self.nodes.get_expr_node(group.expr);
self.visit_expression(inner);
}
PrimaryNode::Lambda(lambda) => {
self.visit_lambda_expr(TypedNodeRef::new(primary.id, lambda));
}
PrimaryNode::When(when) => {
if let Some(value_id) = when.value {
let subject = self.nodes.get_expr_node(value_id);
self.visit_expression(subject);
}
let branch_length = self.nodes.array.size(when.branches);
for i in 0..branch_length {
if let Some(branch_id) = self.nodes.array.get_node_id_at(when.branches, i) {
let branch = self.nodes.get_when_branch_node(branch_id);
self.visit_when_branch(branch);
}
}
if let Some(else_id) = when.else_branch {
let else_expr = self.nodes.get_expr_node(else_id);
self.visit_expression(else_expr);
}
}
PrimaryNode::Number(_)
| PrimaryNode::String(_)
| PrimaryNode::Boolean(_)
| PrimaryNode::Nil(_)
| PrimaryNode::This(_)
| PrimaryNode::Super(_) => {}
}
}
fn visit_when_branch(&mut self, branch: TypedNodeRef<WhenBranchNode>) {
let cond = self.nodes.get_expr_node(branch.node.condition);
self.visit_expression(cond);
let body = self.nodes.get_expr_node(branch.node.body);
self.visit_expression(body);
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{AnalysisPipeline, Parser, ParserConfig, SourceMap};
use std::sync::Arc;
#[test]
fn test_basic_symbol_resolution() {
let source = r#"
var x = 10;
print(x);
"#;
let source_map = Arc::new(SourceMap::from_source(source.to_string()));
let mut strings = StringInterner::new();
let mut nodes = AstNodeArena::new();
let mut parser = Parser::new(source_map.clone(), &mut nodes, &mut strings)
.with_config(ParserConfig { skip_modules: true });
let modules = parser.parse();
let mut errors = parser.into_errors();
let mut modules = modules;
AnalysisPipeline::new(&mut strings)
.analyze(&mut modules, &mut nodes, &mut errors)
.unwrap();
let root_module_id = modules.get_main().unwrap().node;
let module_node = nodes.get_program_node(root_module_id);
let resolver = SymbolResolver::new(&nodes, &strings);
let symbol_table = resolver.resolve_module(module_node);
let resolutions = symbol_table.all_resolutions();
println!("Number of resolutions: {}", resolutions.len());
for (node_id, symbol_info) in resolutions {
println!("NodeId {:?} resolves to {:?}", node_id, symbol_info);
}
assert!(
resolutions.len() > 0,
"Symbol table should have at least one resolution for the identifier 'x' in print(x)"
);
}
}