1use std::collections::HashSet;
2use std::fmt;
3
4use lexer::token::{Span, TokenKind};
5
6use crate::ast::*;
7
8#[derive(Clone, Debug, Eq, PartialEq)]
9pub struct ValidationError {
10 pub message: String,
11 pub span: Span,
12}
13
14impl fmt::Display for ValidationError {
15 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
16 write!(f, "{}", self.message)
17 }
18}
19
20#[derive(Clone, Copy, Debug, Eq, PartialEq)]
21enum CallableKind {
22 Function,
23 Method,
24 Constructor,
25}
26
27struct Validator {
28 scopes: Vec<HashSet<String>>,
29 callable_kinds: Vec<CallableKind>,
30 receiver_available: bool,
31 context: Vec<String>,
32}
33
34pub fn validate_program(
35 program: &Program,
36 predefined_globals: &[&str],
37) -> Result<(), ValidationError> {
38 let mut globals = HashSet::new();
39 globals.extend(predefined_globals.iter().map(|name| (*name).to_string()));
40 let mut validator = Validator {
41 scopes: vec![globals],
42 callable_kinds: Vec::new(),
43 receiver_available: false,
44 context: Vec::new(),
45 };
46 validator.validate_statements(&program.body)
47}
48
49impl Validator {
50 fn validate_statements(&mut self, statements: &[Statement]) -> Result<(), ValidationError> {
51 for statement in statements {
52 self.validate_statement(statement)?;
53 }
54 Ok(())
55 }
56
57 fn validate_statement(&mut self, statement: &Statement) -> Result<(), ValidationError> {
58 match statement {
59 Statement::Let(statement) => {
60 let name = match &statement.identifier.kind {
61 TokenKind::IDENTIFIER {
62 name,
63 } => name.clone(),
64 _ => unreachable!("parser only creates let statements with identifiers"),
65 };
66 self.scopes.last_mut().unwrap().insert(name);
67 self.validate_expression(&statement.expr)
68 }
69 Statement::Return(statement) => {
70 if self.callable_kinds.last() == Some(&CallableKind::Constructor) {
71 return Err(ValidationError {
72 message: "constructor cannot return a value".to_string(),
73 span: statement.span.clone(),
74 });
75 }
76 self.validate_expression(&statement.argument)
77 }
78 Statement::Class(class) => self.validate_class(class),
79 Statement::SetProperty(statement) => {
80 self.validate_expression(&statement.object)?;
81 self.validate_expression(&statement.value)
82 }
83 Statement::Expr(expression) => self.validate_expression(expression),
84 }
85 }
86
87 fn validate_class(&mut self, class: &ClassDeclaration) -> Result<(), ValidationError> {
88 self.scopes
89 .last_mut()
90 .unwrap()
91 .insert(class.name.name.clone());
92 self.context.push(format!("class {}", class.name.name));
93 for method in &class.methods {
94 self.validate_method(method)?;
95 }
96 self.context.pop();
97 Ok(())
98 }
99
100 fn validate_method(&mut self, method: &MethodDefinition) -> Result<(), ValidationError> {
101 let callable_kind = match method.kind {
102 MethodKind::Constructor => CallableKind::Constructor,
103 MethodKind::Method => CallableKind::Method,
104 };
105 self.context.push(method.name.name.clone());
106 self.callable_kinds.push(callable_kind);
107 let old_receiver_available = self.receiver_available;
108 self.receiver_available = true;
109 self.scopes.push(
110 method
111 .params
112 .iter()
113 .map(|parameter| parameter.name.clone())
114 .collect(),
115 );
116
117 let result = self.validate_statements(&method.body.body);
118
119 self.scopes.pop();
120 self.receiver_available = old_receiver_available;
121 self.callable_kinds.pop();
122 self.context.pop();
123 result
124 }
125
126 fn validate_function(&mut self, function: &FunctionDeclaration) -> Result<(), ValidationError> {
127 self.callable_kinds.push(CallableKind::Function);
128 self.scopes.push(
129 function
130 .params
131 .iter()
132 .map(|parameter| parameter.name.clone())
133 .collect(),
134 );
135 let result = self.validate_statements(&function.body.body);
136 self.scopes.pop();
137 self.callable_kinds.pop();
138 result
139 }
140
141 fn validate_expression(&mut self, expression: &Expression) -> Result<(), ValidationError> {
142 match expression {
143 Expression::IDENTIFIER(identifier) => self.validate_identifier(identifier),
144 Expression::LITERAL(literal) => self.validate_literal(literal),
145 Expression::PREFIX(expression) => self.validate_expression(&expression.operand),
146 Expression::INFIX(expression) => {
147 self.validate_expression(&expression.left)?;
148 self.validate_expression(&expression.right)
149 }
150 Expression::IF(expression) => {
151 self.validate_expression(&expression.condition)?;
152 self.validate_statements(&expression.consequent.body)?;
153 if let Some(alternate) = &expression.alternate {
154 self.validate_statements(&alternate.body)?;
155 }
156 Ok(())
157 }
158 Expression::FUNCTION(function) => self.validate_function(function),
159 Expression::FunctionCall(call) => {
160 self.validate_expression(&call.callee)?;
161 self.validate_expressions(&call.arguments)
162 }
163 Expression::Index(index) => {
164 self.validate_expression(&index.object)?;
165 self.validate_expression(&index.index)
166 }
167 Expression::This(this) => {
168 if self.receiver_available {
169 Ok(())
170 } else {
171 Err(ValidationError {
172 message: "this is only available inside a method".to_string(),
173 span: this.span.clone(),
174 })
175 }
176 }
177 Expression::Property(property) => self.validate_expression(&property.object),
178 Expression::New(new_expression) => {
179 self.validate_identifier(&new_expression.callee)?;
180 self.validate_expressions(&new_expression.arguments)
181 }
182 }
183 }
184
185 fn validate_literal(&mut self, literal: &Literal) -> Result<(), ValidationError> {
186 match literal {
187 Literal::Array(array) => self.validate_expressions(&array.elements),
188 Literal::Hash(hash) => {
189 for (key, value) in &hash.elements {
190 self.validate_expression(key)?;
191 self.validate_expression(value)?;
192 }
193 Ok(())
194 }
195 _ => Ok(()),
196 }
197 }
198
199 fn validate_expressions(&mut self, expressions: &[Expression]) -> Result<(), ValidationError> {
200 for expression in expressions {
201 self.validate_expression(expression)?;
202 }
203 Ok(())
204 }
205
206 fn validate_identifier(&self, identifier: &IDENTIFIER) -> Result<(), ValidationError> {
207 if self
208 .scopes
209 .iter()
210 .rev()
211 .any(|scope| scope.contains(&identifier.name))
212 {
213 return Ok(());
214 }
215
216 let context = if self.context.is_empty() {
217 String::new()
218 } else {
219 format!(" in {}", self.context.join("."))
220 };
221 Err(ValidationError {
222 message: format!("undefined variable '{}'{}", identifier.name, context),
223 span: identifier.span.clone(),
224 })
225 }
226}
227
228#[cfg(test)]
229mod tests {
230 use super::*;
231 use crate::{ast::Node, parse};
232
233 fn validate(input: &str) -> Result<(), ValidationError> {
234 let Node::Program(program) = parse(input).unwrap() else { panic!("expected program") };
235 validate_program(&program, &["len"])
236 }
237
238 #[test]
239 fn validates_source_order_constructor_return_and_lexical_this() {
240 validate(
241 r#"class Box {
242 constructor(value) { this.value = value; }
243 reader() { fn() { fn() { this.value } } }
244}
245let box = new Box(1);"#,
246 )
247 .unwrap();
248
249 assert!(validate("this")
250 .unwrap_err()
251 .message
252 .contains("only available"));
253 assert!(validate("let f = fn() { this };")
254 .unwrap_err()
255 .message
256 .contains("only available"));
257 assert!(validate("class A { constructor() { return 1; } }")
258 .unwrap_err()
259 .message
260 .contains("cannot return"));
261 assert!(validate("class A { make() { new B(); } } class B {}")
262 .unwrap_err()
263 .message
264 .contains("undefined variable 'B'"));
265 validate("class A { make() { new A(); } }").unwrap();
266 validate("len([])").unwrap();
267 }
268}