15228202385

Committed 24 May 2025 02:53PM UTC coverage: 72.638% (+0.3%) from 72.333%

Build # 15228202385

Build Type

push

github

Committed by

TyRoXx

Commit Message

GH-244: add assertions

Run Details

4 of 4 new or added lines in 2 files covered. (100.0%)

37 existing lines in 3 files now uncovered.

3252 of 4477 relevant lines covered (72.64%)

2231.98 hits per line

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

95.0

/lambda_compiler/src/type_checking.rs

use crate::{
    ast,
    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(parameter_names: &[Name]) -> Self {
        let mut names = BTreeMap::new();
        for (index, name) in parameter_names.iter().enumerate() {
            let checked_index: u16 = index.try_into().expect("TODO handle too many parameters");
            names.insert(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()
    }

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

    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(
    parameter_names: &[Name],
    body: &ast::Expression,
    environment_builder: &mut EnvironmentBuilder,
) -> Result<CompilerOutput, StoreError> {
    environment_builder.enter_lambda_body(parameter_names);
    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 {
            parameter_names,
            body,
        } => check_lambda(&parameter_names[..], 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,
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(parameter_names: &[Name]) -> Self {	27✔
52	let mut names = BTreeMap::new();	27✔
53	for (index, name) in parameter_names.iter().enumerate() {	46✔
54	let checked_index: u16 = index.try_into().expect("TODO handle too many parameters");
55	names.insert(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	pub fn enter_lambda_body(&mut self, parameter_names: &[Name]) {	27✔
116	self.lambda_layers.push(LambdaScope::new(parameter_names));	27✔
117	}
118
119	pub fn leave_lambda_body(&mut self) -> Vec<Arc<DeepExpression>> {	27✔
120	let top_scope = self.lambda_layers.pop().unwrap();	27✔
121
122	top_scope.leave()	27✔
123	}
124
125	pub fn read(&mut self, identifier: &Name, location: &SourceLocation) -> CompilerOutput {	20✔
126	Self::read_down(&mut self.lambda_layers, identifier, location)	20✔
127	}
128
129	fn read_down(	28✔
130	layers: &mut [LambdaScope],
131	identifier: &Name,
132	location: &SourceLocation,
133	) -> CompilerOutput {
134	let layer_count = layers.len();	28✔
135	if let Some(last) = layers.last_mut() {	54✔
136	if let Some(parameter_index) = last.find_parameter_index(identifier) {	18✔
137	return CompilerOutput::new(
138	Some(lambda::expressions::DeepExpression(
139	lambda::expressions::Expression::make_get_child(
140	Arc::new(lambda::expressions::DeepExpression(
141	lambda::expressions::Expression::make_argument(),
142	)),
143	parameter_index,
144	),
145	)),
146	Vec::new(),
147	);
148	} else if layer_count > 1 {	8✔
149	let result = Self::read_down(&mut layers[..layer_count - 1], identifier, location);	8✔
150	if result.entry_point.is_some() {	8✔
151	return layers	8✔
152	.last_mut()	8✔
153	.unwrap()	8✔
154	.capture(Arc::new(result.entry_point.unwrap()));	8✔
155	}
UNCOV 156	return result;	×
157	}
158	}
159	CompilerOutput::new(
160	None,	2✔
161	vec![crate::compilation::CompilerError::new(	2✔
162	format!("Identifier {identifier} not found"),	2✔
163	*location,	2✔
164	)],
165	)
166	}
167	}
168
169	pub fn check_lambda(	27✔
170	parameter_names: &[Name],
171	body: &ast::Expression,
172	environment_builder: &mut EnvironmentBuilder,
173	) -> Result<CompilerOutput, StoreError> {
174	environment_builder.enter_lambda_body(parameter_names);	27✔
175	let body_result = check_types(body, environment_builder);	27✔
176	// TODO: use RAII or something?
177	let environment = environment_builder.leave_lambda_body();	27✔
178	let body_output = body_result?;	54✔
179	match body_output.entry_point {
180	Some(body_checked) => Ok(CompilerOutput {	27✔
181	entry_point: Some(lambda::expressions::DeepExpression(	27✔
182	lambda::expressions::Expression::Lambda {	27✔
183	environment: Arc::new(DeepExpression(Expression::make_construct_tree(	27✔
184	environment,	27✔
185	))),
186	body: Arc::new(body_checked),	27✔
187	},
188	)),
189	errors: body_output.errors,	27✔
190	}),
UNCOV 191	None => Ok(CompilerOutput::new(None, body_output.errors)),	×
192	}
193	}
194
195	pub fn check_types(	78✔
196	syntax_tree: &ast::Expression,
197	environment_builder: &mut EnvironmentBuilder,
198	) -> Result<CompilerOutput, StoreError> {
199	match syntax_tree {	78✔
200	ast::Expression::Identifier(name, location) => Ok(environment_builder.read(name, location)),	20✔
201	ast::Expression::StringLiteral(value) => Ok(CompilerOutput::new(	10✔
202	Some(lambda::expressions::DeepExpression(	10✔
203	lambda::expressions::Expression::Literal(Tree::from_string(value).unwrap(/TODO/)),	10✔
204	)),
205	Vec::new(),	10✔
206	)),
207	ast::Expression::Apply { callee, arguments } => {	6✔
208	let callee_output = check_types(callee, environment_builder)?;	12✔
209	let argument_output = if arguments.len() == 1 {	6✔
210	// For N=1 we don't need an indirection.
211	check_types(&arguments[0], environment_builder)?	3✔
212	} else {
213	check_tree_construction_or_argument_list(&arguments[..], environment_builder)?	3✔
214	};
215	let errors = callee_output
216	.errors
217	.into_iter()
218	.chain(argument_output.errors)
219	.collect();
220	match (callee_output.entry_point, argument_output.entry_point) {
221	(Some(callee_checked), Some(argument_checked)) => Ok(CompilerOutput {	5✔
222	entry_point: Some(lambda::expressions::DeepExpression(	5✔
223	lambda::expressions::Expression::Apply {	5✔
224	callee: Arc::new(callee_checked),	5✔
225	argument: Arc::new(argument_checked),	5✔
226	},
227	)),
228	errors,	5✔
229	}),
230	(None, _) \| (_, None) => Ok(CompilerOutput::new(None, errors)),	1✔
231	}
232	}
233	ast::Expression::Lambda {
234	parameter_names,	27✔
235	body,	27✔
236	} => check_lambda(&parameter_names[..], body, environment_builder),	27✔
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 / 15228202385

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