15236678782

Committed 25 May 2025 09:59AM UTC coverage: 72.675% (+0.04%) from 72.638%

Build # 15236678782

Build Type

Pull #258

github

Committed by

web-flow

Commit Message

Merge 750305c8d into 6ff867199

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

Run Details

24 of 31 new or added lines in 3 files covered. (77.42%)

3 existing lines in 1 file now uncovered.

3266 of 4494 relevant lines covered (72.67%)

2233.66 hits per line

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

94.95

/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};

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();
    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));
        } else {
            return Ok(CompilerOutput::new(None, errors));
        }
    }
    Ok(CompilerOutput {
        entry_point: Some(lambda::expressions::DeepExpression(
            lambda::expressions::Expression::ConstructTree(checked_arguments),
        )),
        errors,
    })
}

pub struct LocalVariable {
    parameter_index: u16,
}

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

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

impl LambdaScope {
    pub fn new(parameters: &[LambdaParameter]) -> 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));
        }
        Self {
            names,
            captures: Vec::new(),
        }
    }

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

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

    pub fn leave(self) -> Vec<Arc<DeepExpression>> {
        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()
    }

    // TODO: only take the parameter names?
    pub fn enter_lambda_body(&mut self, parameters: &[LambdaParameter]) {
        self.lambda_layers.push(LambdaScope::new(parameters));
    }

    pub fn leave_lambda_body(&mut self) -> Vec<Arc<DeepExpression>> {
        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) = last.find_parameter_index(identifier) {
                return CompilerOutput::new(
                    Some(lambda::expressions::DeepExpression(
                        lambda::expressions::Expression::make_get_child(
                            Arc::new(lambda::expressions::DeepExpression(
                                lambda::expressions::Expression::make_argument(),
                            )),
                            parameter_index,
                        ),
                    )),
                    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(Arc::new(result.entry_point.unwrap()));
                }
                return result;
            }
        }
        CompilerOutput::new(
            None,
            vec![crate::compilation::CompilerError::new(
                format!("Identifier {identifier} not found"),
                *location,
            )],
        )
    }
}

pub fn check_lambda(
    parameters: &[LambdaParameter],
    body: &ast::Expression,
    environment_builder: &mut EnvironmentBuilder,
) -> Result<CompilerOutput, StoreError> {
    environment_builder.enter_lambda_body(parameters);
    let body_result = check_types(body, environment_builder);
    // TODO: use RAII or something?
    let environment = environment_builder.leave_lambda_body();
    let body_output = body_result?;
    match body_output.entry_point {
        Some(body_checked) => Ok(CompilerOutput {
            entry_point: Some(lambda::expressions::DeepExpression(
                lambda::expressions::Expression::Lambda {
                    environment: Arc::new(DeepExpression(Expression::make_construct_tree(
                        environment,
                    ))),
                    body: Arc::new(body_checked),
                },
            )),
            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(lambda::expressions::DeepExpression(
                lambda::expressions::Expression::Literal(Tree::from_string(value).unwrap(/*TODO*/)),
            )),
            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)) => Ok(CompilerOutput {
                    entry_point: Some(lambda::expressions::DeepExpression(
                        lambda::expressions::Expression::Apply {
                            callee: Arc::new(callee_checked),
                            argument: Arc::new(argument_checked),
                        },
                    )),
                    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	fn check_tree_construction_or_argument_list(	15✔
13	arguments: &[ast::Expression],
14	environment_builder: &mut EnvironmentBuilder,
15	) -> Result<CompilerOutput, StoreError> {
16	let mut errors = Vec::new();	15✔
17	let mut checked_arguments = Vec::new();	15✔
18	for argument in arguments {	51✔
19	let output = check_types(argument, environment_builder)?;	36✔
20	errors.extend(output.errors);
21	if let Some(checked) = output.entry_point {	18✔
22	checked_arguments.push(Arc::new(checked));
23	} else {
24	return Ok(CompilerOutput::new(None, errors));	×
25	}
26	}
27	Ok(CompilerOutput {	15✔
28	entry_point: Some(lambda::expressions::DeepExpression(	15✔
29	lambda::expressions::Expression::ConstructTree(checked_arguments),	15✔
30	)),
31	errors,	15✔
32	})
33	}
34
35	pub struct LocalVariable {
36	parameter_index: u16,
37	}
38
39	impl LocalVariable {
40	pub fn new(parameter_index: u16) -> Self {	19✔
41	Self { parameter_index }
42	}
43	}
44
45	pub struct LambdaScope {
46	names: BTreeMap<Name, LocalVariable>,
47	captures: Vec<Arc<DeepExpression>>,
48	}
49
50	impl LambdaScope {
51	pub fn new(parameters: &[LambdaParameter]) -> Self {	27✔
52	let mut names = BTreeMap::new();	27✔
53	for (index, parameter) in parameters.iter().enumerate() {	46✔
54	let checked_index: u16 = index.try_into().expect("TODO handle too many parameters");
55	names.insert(parameter.name.clone(), LocalVariable::new(checked_index));
56	}
57	Self {
58	names,
59	captures: Vec::new(),	27✔
60	}
61	}
62
63	pub fn find_parameter_index(&self, parameter_name: &Name) -> Option<u16> {	26✔
64	self.names	26✔
65	.get(parameter_name)	26✔
66	.map(\|variable\| variable.parameter_index)	44✔
67	}
68
69	pub fn capture(&mut self, expression: Arc<DeepExpression>) -> CompilerOutput {	8✔
70	let index = self	8✔
71	.captures	8✔
72	.len()
73	.try_into()
74	.expect("TODO handle too many captures");
75	self.captures.push(expression);	8✔
76	CompilerOutput::new(
77	Some(lambda::expressions::DeepExpression(	8✔
78	lambda::expressions::Expression::make_get_child(	8✔
79	Arc::new(DeepExpression(	8✔
80	lambda::expressions::Expression::make_environment(),	8✔
81	)),
82	index,	8✔
83	),
84	)),
85	Vec::new(),	8✔
86	)
87	}
88
89	pub fn leave(self) -> Vec<Arc<DeepExpression>> {	27✔
90	self.captures	27✔
91	}
92	}
93
94	pub struct EnvironmentBuilder {
95	lambda_layers: Vec<LambdaScope>,
96	}
97
98	impl Default for EnvironmentBuilder {
UNCOV 99	fn default() -> Self {	×
UNCOV 100	Self::new()	×
101	}
102	}
103
104	impl EnvironmentBuilder {
105	pub fn new() -> Self {	22✔
106	Self {
107	lambda_layers: Vec::new(),	22✔
108	}
109	}
110
111	pub fn is_empty(&self) -> bool {	22✔
112	self.lambda_layers.is_empty()	22✔
113	}
114
115	// TODO: only take the parameter names?
116	pub fn enter_lambda_body(&mut self, parameters: &[LambdaParameter]) {	27✔
117	self.lambda_layers.push(LambdaScope::new(parameters));	27✔
118	}
119
120	pub fn leave_lambda_body(&mut self) -> Vec<Arc<DeepExpression>> {	27✔
121	let top_scope = self.lambda_layers.pop().unwrap();	27✔
122
123	top_scope.leave()	27✔
124	}
125
126	pub fn read(&mut self, identifier: &Name, location: &SourceLocation) -> CompilerOutput {	20✔
127	Self::read_down(&mut self.lambda_layers, identifier, location)	20✔
128	}
129
130	fn read_down(	28✔
131	layers: &mut [LambdaScope],
132	identifier: &Name,
133	location: &SourceLocation,
134	) -> CompilerOutput {
135	let layer_count = layers.len();	28✔
136	if let Some(last) = layers.last_mut() {	54✔
137	if let Some(parameter_index) = last.find_parameter_index(identifier) {	18✔
138	return CompilerOutput::new(
139	Some(lambda::expressions::DeepExpression(
140	lambda::expressions::Expression::make_get_child(
141	Arc::new(lambda::expressions::DeepExpression(
142	lambda::expressions::Expression::make_argument(),
143	)),
144	parameter_index,
145	),
146	)),
147	Vec::new(),
148	);
149	} else if layer_count > 1 {	8✔
150	let result = Self::read_down(&mut layers[..layer_count - 1], identifier, location);	8✔
151	if result.entry_point.is_some() {	8✔
152	return layers	8✔
153	.last_mut()	8✔
154	.unwrap()	8✔
155	.capture(Arc::new(result.entry_point.unwrap()));	8✔
156	}
157	return result;	×
158	}
159	}
160	CompilerOutput::new(
161	None,	2✔
162	vec![crate::compilation::CompilerError::new(	2✔
163	format!("Identifier {identifier} not found"),	2✔
164	*location,	2✔
165	)],
166	)
167	}
168	}
169
170	pub fn check_lambda(	27✔
171	parameters: &[LambdaParameter],
172	body: &ast::Expression,
173	environment_builder: &mut EnvironmentBuilder,
174	) -> Result<CompilerOutput, StoreError> {
175	environment_builder.enter_lambda_body(parameters);	27✔
176	let body_result = check_types(body, environment_builder);	27✔
177	// TODO: use RAII or something?
178	let environment = environment_builder.leave_lambda_body();	27✔
179	let body_output = body_result?;	54✔
180	match body_output.entry_point {
181	Some(body_checked) => Ok(CompilerOutput {	27✔
182	entry_point: Some(lambda::expressions::DeepExpression(	27✔
183	lambda::expressions::Expression::Lambda {	27✔
184	environment: Arc::new(DeepExpression(Expression::make_construct_tree(	27✔
185	environment,	27✔
186	))),
187	body: Arc::new(body_checked),	27✔
188	},
189	)),
190	errors: body_output.errors,	27✔
191	}),
UNCOV 192	None => Ok(CompilerOutput::new(None, body_output.errors)),	×
193	}
194	}
195
196	pub fn check_types(	78✔
197	syntax_tree: &ast::Expression,
198	environment_builder: &mut EnvironmentBuilder,
199	) -> Result<CompilerOutput, StoreError> {
200	match syntax_tree {	78✔
201	ast::Expression::Identifier(name, location) => Ok(environment_builder.read(name, location)),	20✔
202	ast::Expression::StringLiteral(value) => Ok(CompilerOutput::new(	10✔
203	Some(lambda::expressions::DeepExpression(	10✔
204	lambda::expressions::Expression::Literal(Tree::from_string(value).unwrap(/TODO/)),	10✔
205	)),
206	Vec::new(),	10✔
207	)),
208	ast::Expression::Apply { callee, arguments } => {	6✔
209	let callee_output = check_types(callee, environment_builder)?;	12✔
210	let argument_output = if arguments.len() == 1 {	6✔
211	// For N=1 we don't need an indirection.
212	check_types(&arguments[0], environment_builder)?	3✔
213	} else {
214	check_tree_construction_or_argument_list(&arguments[..], environment_builder)?	3✔
215	};
216	let errors = callee_output
217	.errors
218	.into_iter()
219	.chain(argument_output.errors)
220	.collect();
221	match (callee_output.entry_point, argument_output.entry_point) {
222	(Some(callee_checked), Some(argument_checked)) => Ok(CompilerOutput {	5✔
223	entry_point: Some(lambda::expressions::DeepExpression(	5✔
224	lambda::expressions::Expression::Apply {	5✔
225	callee: Arc::new(callee_checked),	5✔
226	argument: Arc::new(argument_checked),	5✔
227	},
228	)),
229	errors,	5✔
230	}),
231	(None, _) \| (_, None) => Ok(CompilerOutput::new(None, errors)),	1✔
232	}
233	}
234	ast::Expression::Lambda { parameters, body } => {	27✔
235	check_lambda(&parameters[..], body, environment_builder)	27✔
236	}
237	ast::Expression::ConstructTree(arguments) => {	12✔
238	check_tree_construction_or_argument_list(&arguments[..], environment_builder)	12✔
239	}
240	ast::Expression::Braces(expression) => {	3✔
241	let output = check_types(expression, environment_builder)?;	6✔
242	Ok(output)
243	}
244	}
245	}

TyRoXx / NonlocalityOS / 15236678782

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