15237506489

Committed 25 May 2025 11:43AM UTC coverage: 72.85% (+0.2%) from 72.638%

Build # 15237506489

Build Type

Pull #258

github

Committed by

web-flow

Commit Message

Merge 25a6692b9 into 6ff867199

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

Run Details

79 of 92 new or added lines in 5 files covered. (85.87%)

2 existing lines in 1 file now uncovered.

3295 of 4523 relevant lines covered (72.85%)

2236.75 hits per line

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

95.08

/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 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 {
                    evaluate_type_at_compile_time(&checked.expression)
                } 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,
            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 EnvironmentBuilder {
137	pub fn new() -> Self {	45✔
138	Self {
139	lambda_layers: Vec::new(),	45✔
140	}
141	}
142
143	pub fn is_empty(&self) -> bool {	24✔
144	self.lambda_layers.is_empty()	24✔
145	}
146
147	pub fn enter_lambda_body(&mut self, parameters: &[TypeCheckedLambdaParameter]) {	30✔
148	self.lambda_layers.push(LambdaScope::new(parameters));	30✔
149	}
150
151	pub fn leave_lambda_body(&mut self) -> Vec<TypedExpression> {	30✔
152	let top_scope = self.lambda_layers.pop().unwrap();	30✔
153	top_scope.leave()	30✔
154	}
155
156	pub fn read(&mut self, identifier: &Name, location: &SourceLocation) -> CompilerOutput {	21✔
157	Self::read_down(&mut self.lambda_layers, identifier, location)	21✔
158	}
159
160	fn read_down(	29✔
161	layers: &mut [LambdaScope],
162	identifier: &Name,
163	location: &SourceLocation,
164	) -> CompilerOutput {
165	let layer_count = layers.len();	29✔
166	if let Some(last) = layers.last_mut() {	56✔
167	if let Some((parameter_index, parameter_type)) = last.find_parameter_index(identifier) {	19✔
168	return CompilerOutput::new(
169	Some(TypedExpression::new(
170	lambda::expressions::DeepExpression(
171	lambda::expressions::Expression::make_get_child(
172	Arc::new(lambda::expressions::DeepExpression(
173	lambda::expressions::Expression::make_argument(),
174	)),
175	parameter_index,
176	),
177	),
178	parameter_type,
179	)),
180	Vec::new(),
181	);
182	} else if layer_count > 1 {	8✔
183	let result = Self::read_down(&mut layers[..layer_count - 1], identifier, location);	8✔
184	if result.entry_point.is_some() {	8✔
185	return layers	8✔
186	.last_mut()	8✔
187	.unwrap()	8✔
188	.capture(result.entry_point.unwrap());	8✔
189	}
UNCOV 190	return result;	×
191	}
192	}
193	CompilerOutput::new(
194	None,	2✔
195	vec![crate::compilation::CompilerError::new(	2✔
196	format!("Identifier {identifier} not found"),	2✔
197	*location,	2✔
198	)],
199	)
200	}
201	}
202
UNCOV 203	pub fn evaluate_type_at_compile_time(_expression: &DeepExpression) -> Type {	×
204	todo!()
205	}
206
207	pub struct TypeCheckedLambdaParameter {
208	pub name: Name,
209	pub source_location: SourceLocation,
210	pub type_: Type,
211	}
212
213	pub fn check_lambda_parameters(	30✔
214	parameters: &[LambdaParameter],
215	) -> Result<Vec<TypeCheckedLambdaParameter>, StoreError> {
216	let mut checked_parameters = Vec::new();	30✔
217	for parameter in parameters {	72✔
218	let mut environment_builder = EnvironmentBuilder::new();	21✔
219	let parameter_type: Type = match &parameter.type_annotation {	42✔
NEW 220	Some(type_annotation) => {	×
NEW 221	let checked_type = check_types(type_annotation, &mut environment_builder)?;	×
222	assert!(environment_builder.is_empty());
NEW 223	if let Some(checked) = checked_type.entry_point {	×
224	evaluate_type_at_compile_time(&checked.expression)
225	} else {
226	todo!()
227	}
228	}
229	None => {
230	// If no type annotation is provided, we assume the type is `Any`.
231	Type::Any	21✔
232	}
233	};
234	checked_parameters.push(TypeCheckedLambdaParameter {
235	name: parameter.name.clone(),
236	source_location: parameter.source_location,
237	type_: parameter_type,
238	});
239	}
240	Ok(checked_parameters)	30✔
241	}
242
243	pub fn check_lambda(	30✔
244	parameters: &[LambdaParameter],
245	body: &ast::Expression,
246	environment_builder: &mut EnvironmentBuilder,
247	) -> Result<CompilerOutput, StoreError> {
248	let checked_parameters = check_lambda_parameters(parameters)?;	60✔
249	environment_builder.enter_lambda_body(&checked_parameters[..]);
250	let body_result = check_types(body, environment_builder);
251	// TODO: use RAII or something?
252	let environment = environment_builder.leave_lambda_body();
253	let environment_expressions = environment
254	.into_iter()
255	.map(\|typed_expression\| Arc::new(typed_expression.expression))	8✔
256	.collect();
257	let body_output = body_result?;	30✔
258	match body_output.entry_point {
259	Some(body_checked) => Ok(CompilerOutput {	29✔
260	entry_point: Some(TypedExpression::new(	29✔
261	lambda::expressions::DeepExpression(lambda::expressions::Expression::Lambda {	29✔
262	environment: Arc::new(DeepExpression(Expression::make_construct_tree(	29✔
263	environment_expressions,	29✔
264	))),
265	body: Arc::new(body_checked.expression),	29✔
266	}),
267	Type::Function {	29✔
268	parameters: checked_parameters	29✔
269	.into_iter()	29✔
270	.map(\|parameter\| parameter.type_)	49✔
271	.collect(),	29✔
272	return_type: Box::new(body_checked.type_),	29✔
273	},
274	)),
275	errors: body_output.errors,	29✔
276	}),
277	None => Ok(CompilerOutput::new(None, body_output.errors)),	1✔
278	}
279	}
280
281	pub fn check_types(	84✔
282	syntax_tree: &ast::Expression,
283	environment_builder: &mut EnvironmentBuilder,
284	) -> Result<CompilerOutput, StoreError> {
285	match syntax_tree {	84✔
286	ast::Expression::Identifier(name, location) => Ok(environment_builder.read(name, location)),	21✔
287	ast::Expression::StringLiteral(value) => Ok(CompilerOutput::new(	11✔
288	Some(TypedExpression::new(	11✔
289	lambda::expressions::DeepExpression(lambda::expressions::Expression::Literal(	11✔
290	Tree::from_string(value).unwrap(/TODO/),	11✔
291	)),
292	Type::String,	11✔
293	)),
294	Vec::new(),	11✔
295	)),
296	ast::Expression::Apply { callee, arguments } => {	6✔
297	let callee_output = check_types(callee, environment_builder)?;	12✔
298	let argument_output = if arguments.len() == 1 {	6✔
299	// For N=1 we don't need an indirection.
300	check_types(&arguments[0], environment_builder)?	3✔
301	} else {
302	check_tree_construction_or_argument_list(&arguments[..], environment_builder)?	3✔
303	};
304	let errors = callee_output
305	.errors
306	.into_iter()
307	.chain(argument_output.errors)
308	.collect();
309	match (callee_output.entry_point, argument_output.entry_point) {
310	(Some(callee_checked), Some(argument_checked)) => {	5✔
311	let return_type = match &callee_checked.type_ {	9✔
312	Type::Function { return_type, .. } => return_type.as_ref().clone(),
313	_ => {
314	return Ok(CompilerOutput::new(	1✔
315	None,	1✔
316	vec![crate::compilation::CompilerError::new(	1✔
317	"Callee is not a function".to_string(),	1✔
318	callee.source_location(),	1✔
319	)],
320	))
321	}
322	};
323	// TODO: check argument types against callee parameter types
324	Ok(CompilerOutput {
325	entry_point: Some(TypedExpression::new(
326	lambda::expressions::DeepExpression(
327	lambda::expressions::Expression::Apply {
328	callee: Arc::new(callee_checked.expression),
329	argument: Arc::new(argument_checked.expression),
330	},
331	),
332	return_type,
333	)),
334	errors,
335	})
336	}
337	(None, _) \| (_, None) => Ok(CompilerOutput::new(None, errors)),	1✔
338	}
339	}
340	ast::Expression::Lambda { parameters, body } => {	30✔
341	check_lambda(&parameters[..], body, environment_builder)	30✔
342	}
343	ast::Expression::ConstructTree(arguments) => {	12✔
344	check_tree_construction_or_argument_list(&arguments[..], environment_builder)	12✔
345	}
346	ast::Expression::Braces(expression) => {	4✔
347	let output = check_types(expression, environment_builder)?;	8✔
348	Ok(output)
349	}
350	}
351	}

TyRoXx / NonlocalityOS / 15237506489

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