15096182297

Committed 18 May 2025 12:58PM UTC coverage: 72.468% (+0.4%) from 72.054%

Build # 15096182297

Build Type

Pull #245

github

Committed by

web-flow

Commit Message

Merge c677cd285 into 4e7b17925

Pull Request Pull Request #245: GH-244: multiple parameters actually work

Run Details

169 of 192 new or added lines in 7 files covered. (88.02%)

1 existing line in 1 file now uncovered.

3206 of 4424 relevant lines covered (72.47%)

2243.02 hits per line

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

93.62

/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: usize,
}

impl LocalVariable {
    pub fn new(parameter_index: usize) -> 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() {
            names.insert(name.clone(), LocalVariable::new(index));
        }
        Self {
            names,
            captures: Vec::new(),
        }
    }

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

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

TyRoXx / NonlocalityOS / 15096182297

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