15095516410

Committed 18 May 2025 11:34AM UTC coverage: 72.417% (+0.4%) from 72.054%

Build # 15095516410

Build Type

Pull #245

github

Committed by

web-flow

Commit Message

Merge 226c7229f into 4e7b17925

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

Run Details

170 of 189 new or added lines in 7 files covered. (89.95%)

1 existing line in 1 file now uncovered.

3203 of 4423 relevant lines covered (72.42%)

2242.86 hits per line

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

95.74

/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> {
        match self.names.get(parameter_name) {
            Some(variable) => Some(variable.parameter_index),
            None => None,
        }
    }

    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 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();
        let environment = top_scope.leave();
        environment
    }

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

TyRoXx / NonlocalityOS / 15095516410

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