15237436685

Committed 25 May 2025 11:33AM UTC coverage: 72.751% (+0.1%) from 72.638%

Build # 15237436685

Build Type

Pull #258

github

Committed by

web-flow

Commit Message

Merge 10a3577ca into 6ff867199

Pull Request Pull Request #258: GH-256: extend AST for optional parameter type annotations

Run Details

79 of 93 new or added lines in 5 files covered. (84.95%)

2 existing lines in 1 file now uncovered.

3292 of 4525 relevant lines covered (72.75%)

2236.02 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.55

/lambda_compiler/src/type_checking.rs

use crate::{
    ast::{self, LambdaParameter},
    compilation::{CompilerOutput, SourceLocation},
};
use astraea::{storage::StoreError, tree::Tree};
use lambda::{
    expressions::{DeepExpression, Expression},
    name::Name,
};
use std::{collections::BTreeMap, sync::Arc};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
pub enum Type {
    Any,
    String,
    TreeWithKnownChildTypes(Vec<Type>),
    Function {
        parameters: Vec<Type>,
        return_type: Box<Type>,
    },
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
pub struct TypedExpression {
    pub expression: DeepExpression,
    pub type_: Type,
}

impl TypedExpression {
    pub fn new(expression: DeepExpression, type_: Type) -> Self {
        Self { expression, type_ }
    }
}

fn check_tree_construction_or_argument_list(
    arguments: &[ast::Expression],
    environment_builder: &mut EnvironmentBuilder,
) -> Result<CompilerOutput, StoreError> {
    let mut errors = Vec::new();
    let mut checked_arguments = Vec::new();
    let mut argument_types = Vec::new();
    for argument in arguments {
        let output = check_types(argument, environment_builder)?;
        errors.extend(output.errors);
        if let Some(checked) = output.entry_point {
            checked_arguments.push(Arc::new(checked.expression));
            argument_types.push(checked.type_);
        } else {
            return Ok(CompilerOutput::new(None, errors));
        }
    }
    Ok(CompilerOutput {
        entry_point: Some(TypedExpression::new(
            lambda::expressions::DeepExpression(lambda::expressions::Expression::ConstructTree(
                checked_arguments,
            )),
            Type::TreeWithKnownChildTypes(argument_types),
        )),
        errors,
    })
}

pub struct LocalVariable {
    parameter_index: u16,
    type_: Type,
}

impl LocalVariable {
    pub fn new(parameter_index: u16, type_: Type) -> Self {
        Self {
            parameter_index,
            type_,
        }
    }
}

pub struct LambdaScope {
    names: BTreeMap<Name, LocalVariable>,
    captures: Vec<TypedExpression>,
}

impl LambdaScope {
    pub fn new(parameters: &[TypeCheckedLambdaParameter]) -> Self {
        let mut names = BTreeMap::new();
        for (index, parameter) in parameters.iter().enumerate() {
            let checked_index: u16 = index.try_into().expect("TODO handle too many parameters");
            names.insert(
                parameter.name.clone(),
                LocalVariable::new(checked_index, parameter.type_.clone()),
            );
        }
        Self {
            names,
            captures: Vec::new(),
        }
    }

    pub fn find_parameter_index(&self, parameter_name: &Name) -> Option<(u16, Type)> {
        self.names
            .get(parameter_name)
            .map(|variable| (variable.parameter_index, variable.type_.clone()))
    }

    pub fn capture(&mut self, expression: TypedExpression) -> CompilerOutput {
        let index = self
            .captures
            .len()
            .try_into()
            .expect("TODO handle too many captures");
        self.captures.push(expression);
        CompilerOutput::new(
            Some(TypedExpression::new(
                lambda::expressions::DeepExpression(
                    lambda::expressions::Expression::make_get_child(
                        Arc::new(DeepExpression(
                            lambda::expressions::Expression::make_environment(),
                        )),
                        index,
                    ),
                ),
                self.captures.last().unwrap().type_.clone(),
            )),
            Vec::new(),
        )
    }

    pub fn leave(self) -> Vec<TypedExpression> {
        self.captures
    }
}

pub struct EnvironmentBuilder {
    lambda_layers: Vec<LambdaScope>,
}

impl Default for EnvironmentBuilder {
    fn default() -> Self {
        Self::new()
    }
}

impl EnvironmentBuilder {
    pub fn new() -> Self {
        Self {
            lambda_layers: Vec::new(),
        }
    }

    pub fn is_empty(&self) -> bool {
        self.lambda_layers.is_empty()
    }

    pub fn enter_lambda_body(&mut self, parameters: &[TypeCheckedLambdaParameter]) {
        self.lambda_layers.push(LambdaScope::new(parameters));
    }

    pub fn leave_lambda_body(&mut self) -> Vec<TypedExpression> {
        let top_scope = self.lambda_layers.pop().unwrap();
        top_scope.leave()
    }

    pub fn read(&mut self, identifier: &Name, location: &SourceLocation) -> CompilerOutput {
        Self::read_down(&mut self.lambda_layers, identifier, location)
    }

    fn read_down(
        layers: &mut [LambdaScope],
        identifier: &Name,
        location: &SourceLocation,
    ) -> CompilerOutput {
        let layer_count = layers.len();
        if let Some(last) = layers.last_mut() {
            if let Some((parameter_index, parameter_type)) = last.find_parameter_index(identifier) {
                return CompilerOutput::new(
                    Some(TypedExpression::new(
                        lambda::expressions::DeepExpression(
                            lambda::expressions::Expression::make_get_child(
                                Arc::new(lambda::expressions::DeepExpression(
                                    lambda::expressions::Expression::make_argument(),
                                )),
                                parameter_index,
                            ),
                        ),
                        parameter_type,
                    )),
                    Vec::new(),
                );
            } else if layer_count > 1 {
                let result = Self::read_down(&mut layers[..layer_count - 1], identifier, location);
                if result.entry_point.is_some() {
                    return layers
                        .last_mut()
                        .unwrap()
                        .capture(result.entry_point.unwrap());
                }
                return result;
            }
        }
        CompilerOutput::new(
            None,
            vec![crate::compilation::CompilerError::new(
                format!("Identifier {identifier} not found"),
                *location,
            )],
        )
    }
}

pub fn evaluate_type_at_compile_time(_expression: &DeepExpression) -> Type {
    todo!()
}

pub struct TypeCheckedLambdaParameter {
    pub name: Name,
    pub source_location: SourceLocation,
    pub type_: Type,
}

pub fn check_lambda_parameters(
    parameters: &[LambdaParameter],
) -> Result<Vec<TypeCheckedLambdaParameter>, StoreError> {
    let mut checked_parameters = Vec::new();
    for parameter in parameters {
        let mut environment_builder = EnvironmentBuilder::new();
        let parameter_type: Type = match &parameter.type_annotation {
            Some(type_annotation) => {
                let checked_type = check_types(type_annotation, &mut environment_builder)?;
                assert!(environment_builder.is_empty());
                if let Some(checked) = checked_type.entry_point {
                    let evaluated_type = evaluate_type_at_compile_time(&checked.expression);
                    evaluated_type
                } else {
                    todo!()
                }
            }
            None => {
                // If no type annotation is provided, we assume the type is `Any`.
                Type::Any
            }
        };
        checked_parameters.push(TypeCheckedLambdaParameter {
            name: parameter.name.clone(),
            source_location: parameter.source_location.clone(),
            type_: parameter_type,
        });
    }
    Ok(checked_parameters)
}

pub fn check_lambda(
    parameters: &[LambdaParameter],
    body: &ast::Expression,
    environment_builder: &mut EnvironmentBuilder,
) -> Result<CompilerOutput, StoreError> {
    let checked_parameters = check_lambda_parameters(parameters)?;
    environment_builder.enter_lambda_body(&checked_parameters[..]);
    let body_result = check_types(body, environment_builder);
    // TODO: use RAII or something?
    let environment = environment_builder.leave_lambda_body();
    let environment_expressions = environment
        .into_iter()
        .map(|typed_expression| Arc::new(typed_expression.expression))
        .collect();
    let body_output = body_result?;
    match body_output.entry_point {
        Some(body_checked) => Ok(CompilerOutput {
            entry_point: Some(TypedExpression::new(
                lambda::expressions::DeepExpression(lambda::expressions::Expression::Lambda {
                    environment: Arc::new(DeepExpression(Expression::make_construct_tree(
                        environment_expressions,
                    ))),
                    body: Arc::new(body_checked.expression),
                }),
                Type::Function {
                    parameters: checked_parameters
                        .into_iter()
                        .map(|parameter| parameter.type_)
                        .collect(),
                    return_type: Box::new(body_checked.type_),
                },
            )),
            errors: body_output.errors,
        }),
        None => Ok(CompilerOutput::new(None, body_output.errors)),
    }
}

pub fn check_types(
    syntax_tree: &ast::Expression,
    environment_builder: &mut EnvironmentBuilder,
) -> Result<CompilerOutput, StoreError> {
    match syntax_tree {
        ast::Expression::Identifier(name, location) => Ok(environment_builder.read(name, location)),
        ast::Expression::StringLiteral(value) => Ok(CompilerOutput::new(
            Some(TypedExpression::new(
                lambda::expressions::DeepExpression(lambda::expressions::Expression::Literal(
                    Tree::from_string(value).unwrap(/*TODO*/),
                )),
                Type::String,
            )),
            Vec::new(),
        )),
        ast::Expression::Apply { callee, arguments } => {
            let callee_output = check_types(callee, environment_builder)?;
            let argument_output = if arguments.len() == 1 {
                // For N=1 we don't need an indirection.
                check_types(&arguments[0], environment_builder)?
            } else {
                check_tree_construction_or_argument_list(&arguments[..], environment_builder)?
            };
            let errors = callee_output
                .errors
                .into_iter()
                .chain(argument_output.errors)
                .collect();
            match (callee_output.entry_point, argument_output.entry_point) {
                (Some(callee_checked), Some(argument_checked)) => {
                    let return_type = match &callee_checked.type_ {
                        Type::Function { return_type, .. } => return_type.as_ref().clone(),
                        _ => {
                            return Ok(CompilerOutput::new(
                                None,
                                vec![crate::compilation::CompilerError::new(
                                    "Callee is not a function".to_string(),
                                    callee.source_location(),
                                )],
                            ))
                        }
                    };
                    // TODO: check argument types against callee parameter types
                    Ok(CompilerOutput {
                        entry_point: Some(TypedExpression::new(
                            lambda::expressions::DeepExpression(
                                lambda::expressions::Expression::Apply {
                                    callee: Arc::new(callee_checked.expression),
                                    argument: Arc::new(argument_checked.expression),
                                },
                            ),
                            return_type,
                        )),
                        errors,
                    })
                }
                (None, _) | (_, None) => Ok(CompilerOutput::new(None, errors)),
            }
        }
        ast::Expression::Lambda { parameters, body } => {
            check_lambda(&parameters[..], body, environment_builder)
        }
        ast::Expression::ConstructTree(arguments) => {
            check_tree_construction_or_argument_list(&arguments[..], environment_builder)
        }
        ast::Expression::Braces(expression) => {
            let output = check_types(expression, environment_builder)?;
            Ok(output)
        }
    }
}

1	use crate::{
2	ast::{self, LambdaParameter},
3	compilation::{CompilerOutput, SourceLocation},
4	};
5	use astraea::{storage::StoreError, tree::Tree};
6	use lambda::{
7	expressions::{DeepExpression, Expression},
8	name::Name,
9	};
10	use std::{collections::BTreeMap, sync::Arc};
11
12	#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
13	pub enum Type {
14	Any,
15	String,
16	TreeWithKnownChildTypes(Vec<Type>),
17	Function {
18	parameters: Vec<Type>,
19	return_type: Box<Type>,
20	},
21	}
22
23	#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
24	pub struct TypedExpression {
25	pub expression: DeepExpression,
26	pub type_: Type,
27	}
28
29	impl TypedExpression {
30	pub fn new(expression: DeepExpression, type_: Type) -> Self {	103✔
31	Self { expression, type_ }
32	}
33	}
34
35	fn check_tree_construction_or_argument_list(	15✔
36	arguments: &[ast::Expression],
37	environment_builder: &mut EnvironmentBuilder,
38	) -> Result<CompilerOutput, StoreError> {
39	let mut errors = Vec::new();	15✔
40	let mut checked_arguments = Vec::new();	15✔
41	let mut argument_types = Vec::new();	15✔
42	for argument in arguments {	51✔
43	let output = check_types(argument, environment_builder)?;	36✔
44	errors.extend(output.errors);
45	if let Some(checked) = output.entry_point {	18✔
46	checked_arguments.push(Arc::new(checked.expression));
47	argument_types.push(checked.type_);
48	} else {
49	return Ok(CompilerOutput::new(None, errors));	×
50	}
51	}
52	Ok(CompilerOutput {	15✔
53	entry_point: Some(TypedExpression::new(	15✔
54	lambda::expressions::DeepExpression(lambda::expressions::Expression::ConstructTree(	15✔
55	checked_arguments,	15✔
56	)),
57	Type::TreeWithKnownChildTypes(argument_types),	15✔
58	)),
59	errors,	15✔
60	})
61	}
62
63	pub struct LocalVariable {
64	parameter_index: u16,
65	type_: Type,
66	}
67
68	impl LocalVariable {
69	pub fn new(parameter_index: u16, type_: Type) -> Self {	21✔
70	Self {
71	parameter_index,
72	type_,
73	}
74	}
75	}
76
77	pub struct LambdaScope {
78	names: BTreeMap<Name, LocalVariable>,
79	captures: Vec<TypedExpression>,
80	}
81
82	impl LambdaScope {
83	pub fn new(parameters: &[TypeCheckedLambdaParameter]) -> Self {	30✔
84	let mut names = BTreeMap::new();	30✔
85	for (index, parameter) in parameters.iter().enumerate() {	51✔
86	let checked_index: u16 = index.try_into().expect("TODO handle too many parameters");
87	names.insert(
88	parameter.name.clone(),
89	LocalVariable::new(checked_index, parameter.type_.clone()),
90	);
91	}
92	Self {
93	names,
94	captures: Vec::new(),	30✔
95	}
96	}
97
98	pub fn find_parameter_index(&self, parameter_name: &Name) -> Option<(u16, Type)> {	27✔
99	self.names	27✔
100	.get(parameter_name)	27✔
101	.map(\|variable\| (variable.parameter_index, variable.type_.clone()))	46✔
102	}
103
104	pub fn capture(&mut self, expression: TypedExpression) -> CompilerOutput {	8✔
105	let index = self	8✔
106	.captures	8✔
107	.len()
108	.try_into()
109	.expect("TODO handle too many captures");
110	self.captures.push(expression);	8✔
111	CompilerOutput::new(
112	Some(TypedExpression::new(	8✔
113	lambda::expressions::DeepExpression(	8✔
114	lambda::expressions::Expression::make_get_child(	8✔
115	Arc::new(DeepExpression(	8✔
116	lambda::expressions::Expression::make_environment(),	8✔
117	)),
118	index,	8✔
119	),
120	),
121	self.captures.last().unwrap().type_.clone(),	8✔
122	)),
123	Vec::new(),	8✔
124	)
125	}
126
127	pub fn leave(self) -> Vec<TypedExpression> {	30✔
128	self.captures	30✔
129	}
130	}
131
132	pub struct EnvironmentBuilder {
133	lambda_layers: Vec<LambdaScope>,
134	}
135
136	impl Default for EnvironmentBuilder {
137	fn default() -> Self {	×
138	Self::new()	×
139	}
140	}
141
142	impl EnvironmentBuilder {
143	pub fn new() -> Self {	45✔
144	Self {
145	lambda_layers: Vec::new(),	45✔
146	}
147	}
148
149	pub fn is_empty(&self) -> bool {	24✔
150	self.lambda_layers.is_empty()	24✔
151	}
152
153	pub fn enter_lambda_body(&mut self, parameters: &[TypeCheckedLambdaParameter]) {	30✔
154	self.lambda_layers.push(LambdaScope::new(parameters));	30✔
155	}
156
157	pub fn leave_lambda_body(&mut self) -> Vec<TypedExpression> {	30✔
158	let top_scope = self.lambda_layers.pop().unwrap();	30✔
159	top_scope.leave()	30✔
160	}
161
162	pub fn read(&mut self, identifier: &Name, location: &SourceLocation) -> CompilerOutput {	21✔
163	Self::read_down(&mut self.lambda_layers, identifier, location)	21✔
164	}
165
166	fn read_down(	29✔
167	layers: &mut [LambdaScope],
168	identifier: &Name,
169	location: &SourceLocation,
170	) -> CompilerOutput {
171	let layer_count = layers.len();	29✔
172	if let Some(last) = layers.last_mut() {	56✔
173	if let Some((parameter_index, parameter_type)) = last.find_parameter_index(identifier) {	19✔
174	return CompilerOutput::new(
175	Some(TypedExpression::new(
176	lambda::expressions::DeepExpression(
177	lambda::expressions::Expression::make_get_child(
178	Arc::new(lambda::expressions::DeepExpression(
179	lambda::expressions::Expression::make_argument(),
180	)),
181	parameter_index,
182	),
183	),
184	parameter_type,
185	)),
186	Vec::new(),
187	);
188	} else if layer_count > 1 {	8✔
189	let result = Self::read_down(&mut layers[..layer_count - 1], identifier, location);	8✔
190	if result.entry_point.is_some() {	8✔
191	return layers	8✔
192	.last_mut()	8✔
193	.unwrap()	8✔
194	.capture(result.entry_point.unwrap());	8✔
195	}
196	return result;	×
197	}
198	}
199	CompilerOutput::new(
200	None,	2✔
201	vec![crate::compilation::CompilerError::new(	2✔
202	format!("Identifier {identifier} not found"),	2✔
203	*location,	2✔
204	)],
205	)
206	}
207	}
208
NEW 209	pub fn evaluate_type_at_compile_time(_expression: &DeepExpression) -> Type {	×
210	todo!()
211	}
212
213	pub struct TypeCheckedLambdaParameter {
214	pub name: Name,
215	pub source_location: SourceLocation,
216	pub type_: Type,
217	}
218
219	pub fn check_lambda_parameters(	30✔
220	parameters: &[LambdaParameter],
221	) -> Result<Vec<TypeCheckedLambdaParameter>, StoreError> {
222	let mut checked_parameters = Vec::new();	30✔
223	for parameter in parameters {	72✔
224	let mut environment_builder = EnvironmentBuilder::new();	21✔
225	let parameter_type: Type = match &parameter.type_annotation {	42✔
NEW 226	Some(type_annotation) => {	×
NEW 227	let checked_type = check_types(type_annotation, &mut environment_builder)?;	×
228	assert!(environment_builder.is_empty());
NEW 229	if let Some(checked) = checked_type.entry_point {	×
230	let evaluated_type = evaluate_type_at_compile_time(&checked.expression);
231	evaluated_type
232	} else {
233	todo!()
234	}
235	}
236	None => {
237	// If no type annotation is provided, we assume the type is `Any`.
238	Type::Any	21✔
239	}
240	};
241	checked_parameters.push(TypeCheckedLambdaParameter {
242	name: parameter.name.clone(),
243	source_location: parameter.source_location.clone(),
244	type_: parameter_type,
245	});
246	}
247	Ok(checked_parameters)	30✔
248	}
249
250	pub fn check_lambda(	30✔
251	parameters: &[LambdaParameter],
252	body: &ast::Expression,
253	environment_builder: &mut EnvironmentBuilder,
254	) -> Result<CompilerOutput, StoreError> {
255	let checked_parameters = check_lambda_parameters(parameters)?;	60✔
256	environment_builder.enter_lambda_body(&checked_parameters[..]);
257	let body_result = check_types(body, environment_builder);
258	// TODO: use RAII or something?
259	let environment = environment_builder.leave_lambda_body();
260	let environment_expressions = environment
261	.into_iter()
262	.map(\|typed_expression\| Arc::new(typed_expression.expression))	8✔
263	.collect();
264	let body_output = body_result?;	30✔
265	match body_output.entry_point {
266	Some(body_checked) => Ok(CompilerOutput {	29✔
267	entry_point: Some(TypedExpression::new(	29✔
268	lambda::expressions::DeepExpression(lambda::expressions::Expression::Lambda {	29✔
269	environment: Arc::new(DeepExpression(Expression::make_construct_tree(	29✔
270	environment_expressions,	29✔
271	))),
272	body: Arc::new(body_checked.expression),	29✔
273	}),
274	Type::Function {	29✔
275	parameters: checked_parameters	29✔
276	.into_iter()	29✔
277	.map(\|parameter\| parameter.type_)	49✔
278	.collect(),	29✔
279	return_type: Box::new(body_checked.type_),	29✔
280	},
281	)),
282	errors: body_output.errors,	29✔
283	}),
284	None => Ok(CompilerOutput::new(None, body_output.errors)),	1✔
285	}
286	}
287
288	pub fn check_types(	84✔
289	syntax_tree: &ast::Expression,
290	environment_builder: &mut EnvironmentBuilder,
291	) -> Result<CompilerOutput, StoreError> {
292	match syntax_tree {	84✔
293	ast::Expression::Identifier(name, location) => Ok(environment_builder.read(name, location)),	21✔
294	ast::Expression::StringLiteral(value) => Ok(CompilerOutput::new(	11✔
295	Some(TypedExpression::new(	11✔
296	lambda::expressions::DeepExpression(lambda::expressions::Expression::Literal(	11✔
297	Tree::from_string(value).unwrap(/TODO/),	11✔
298	)),
299	Type::String,	11✔
300	)),
301	Vec::new(),	11✔
302	)),
303	ast::Expression::Apply { callee, arguments } => {	6✔
304	let callee_output = check_types(callee, environment_builder)?;	12✔
305	let argument_output = if arguments.len() == 1 {	6✔
306	// For N=1 we don't need an indirection.
307	check_types(&arguments[0], environment_builder)?	3✔
308	} else {
309	check_tree_construction_or_argument_list(&arguments[..], environment_builder)?	3✔
310	};
311	let errors = callee_output
312	.errors
313	.into_iter()
314	.chain(argument_output.errors)
315	.collect();
316	match (callee_output.entry_point, argument_output.entry_point) {
317	(Some(callee_checked), Some(argument_checked)) => {	5✔
318	let return_type = match &callee_checked.type_ {	9✔
319	Type::Function { return_type, .. } => return_type.as_ref().clone(),
320	_ => {
321	return Ok(CompilerOutput::new(	1✔
322	None,	1✔
323	vec![crate::compilation::CompilerError::new(	1✔
324	"Callee is not a function".to_string(),	1✔
325	callee.source_location(),	1✔
326	)],
327	))
328	}
329	};
330	// TODO: check argument types against callee parameter types
331	Ok(CompilerOutput {
332	entry_point: Some(TypedExpression::new(
333	lambda::expressions::DeepExpression(
334	lambda::expressions::Expression::Apply {
335	callee: Arc::new(callee_checked.expression),
336	argument: Arc::new(argument_checked.expression),
337	},
338	),
339	return_type,
340	)),
341	errors,
342	})
343	}
344	(None, _) \| (_, None) => Ok(CompilerOutput::new(None, errors)),	1✔
345	}
346	}
347	ast::Expression::Lambda { parameters, body } => {	30✔
348	check_lambda(&parameters[..], body, environment_builder)	30✔
349	}
350	ast::Expression::ConstructTree(arguments) => {	12✔
351	check_tree_construction_or_argument_list(&arguments[..], environment_builder)	12✔
352	}
353	ast::Expression::Braces(expression) => {	4✔
354	let output = check_types(expression, environment_builder)?;	8✔
355	Ok(output)
356	}
357	}
358	}

TyRoXx / NonlocalityOS / 15237436685

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous