15327202569

Committed 29 May 2025 03:17PM UTC coverage: 72.802% (-0.2%) from 72.983%

Build # 15327202569

Build Type

push

github

Committed by

TyRoXx

Commit Message

GH-267: begin to compile time evaluate lambda parameter types

Run Details

139 of 185 new or added lines in 7 files covered. (75.14%)

2 existing lines in 1 file now uncovered.

3445 of 4732 relevant lines covered (72.8%)

2177.62 hits per line

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

81.49

/lambda_compiler/src/type_checking.rs

use crate::{
    ast::{self, LambdaParameter},
    compilation::{CompilerOutput, SourceLocation},
};
use astraea::{
    deep_tree::DeepTree,
    storage::StoreError,
    tree::{ReferenceIndex, TreeBlob},
};
use lambda::{
    expressions::{evaluate, DeepExpression, Expression},
    name::Name,
};
use serde::{Deserialize, Serialize};
use std::{collections::BTreeMap, sync::Arc};

#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash, Clone, Serialize, Deserialize)]
pub enum GenericType<T>
where
    T: Clone,
{
    Any,
    String,
    TreeWithKnownChildTypes(Vec<T>),
    Function {
        parameters: Vec<T>,
        return_type: Box<T>,
    },
    Type,
}

#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash, Clone)]
pub struct DeepType(pub GenericType<DeepType>);

pub fn to_reference_type(deep_type: &DeepType) -> (GenericType<ReferenceIndex>, Vec<DeepType>) {
    match deep_type.0 {
        GenericType::Any => (GenericType::Any, Vec::new()),
        GenericType::String => (GenericType::String, Vec::new()),
        GenericType::TreeWithKnownChildTypes(ref children) => (
            GenericType::TreeWithKnownChildTypes(
                (0u64..(children.len() as u64))
                    .map(ReferenceIndex)
                    .collect(),
            ),
            children.clone(),
        ),
        GenericType::Function {
            ref parameters,
            ref return_type,
        } => {
            let mut parameters_references = Vec::new();
            let mut children = Vec::new();
            for (index, parameter) in parameters.iter().enumerate() {
                parameters_references.push(ReferenceIndex(index as u64));
                children.push(parameter.clone());
            }
            let return_type_reference = ReferenceIndex(children.len() as u64);
            children.push(return_type.as_ref().clone());
            (
                GenericType::Function {
                    parameters: parameters_references,
                    return_type: Box::new(return_type_reference),
                },
                children,
            )
        }
        GenericType::Type => (GenericType::Type, Vec::new()),
    }
}

pub fn type_to_deep_tree(deep_type: &DeepType) -> DeepTree {
    let (body, children) = to_reference_type(deep_type);
    let body_serialized = postcard::to_allocvec(&body).unwrap(/*TODO*/);
    DeepTree::new(
        TreeBlob::try_from(bytes::Bytes::from( body_serialized)).unwrap(/*TODO*/),
        children.iter().map(type_to_deep_tree).collect(),
    )
}

pub fn from_reference_type(body: &GenericType<ReferenceIndex>, children: &[DeepType]) -> DeepType {
    match body {
        GenericType::Any => DeepType(GenericType::Any),
        GenericType::String => DeepType(GenericType::String),
        GenericType::TreeWithKnownChildTypes(ref children_references) => {
            let mut resulting_children = Vec::new();
            for reference in children_references {
                let index = reference.0 as usize;
                if index < children.len() {
                    resulting_children.push(children[index].clone());
                } else {
                    // TODO error handling
                    // This should not happen if the tree is well-formed.
                    panic!("Reference index out of bounds: {index}");
                }
            }
            DeepType(GenericType::TreeWithKnownChildTypes(resulting_children))
        }
        GenericType::Function {
            ref parameters,
            ref return_type,
        } => {
            let mut resulting_parameters = Vec::new();
            for reference in parameters {
                let index: usize = reference.0.try_into().expect("TODO");
                if index < children.len() {
                    resulting_parameters.push(children[index].clone());
                } else {
                    // TODO error handling
                    // This should not happen if the tree is well-formed.
                    panic!("Reference index out of bounds: {index}");
                }
            }
            let resulting_return_type = {
                let index: usize = return_type.0.try_into().expect("TODO");
                if index < children.len() {
                    children[index].clone()
                } else {
                    // TODO error handling
                    panic!("Reference index out of bounds: {index}");
                }
            };
            DeepType(GenericType::Function {
                parameters: resulting_parameters,
                return_type: Box::new(resulting_return_type),
            })
        }
        GenericType::Type => DeepType(GenericType::Type),
    }
}

pub fn type_from_deep_tree(deep_tree: &DeepTree) -> DeepType {
    let body: GenericType<ReferenceIndex> =
        postcard::from_bytes(deep_tree.blob().as_slice()).unwrap(/*TODO*/);
    let children: Vec<_> = deep_tree
        .references()
        .iter()
        .map(type_from_deep_tree)
        .collect();
    from_reference_type(&body, &children)
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
pub struct TypedExpression {
    pub expression: DeepExpression,
    pub type_: DeepType,
}

impl TypedExpression {
    pub fn new(expression: DeepExpression, type_: DeepType) -> Self {
        Self { expression, type_ }
    }
}

async 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).await?;
        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,
            )),
            DeepType(GenericType::TreeWithKnownChildTypes(argument_types)),
        )),
        errors,
    })
}

#[derive(Debug, Clone, Copy)]
enum ParameterIndex {
    SingleParameter,
    GetChild(u16),
}

impl ParameterIndex {
    pub fn create_deep_expression(&self) -> lambda::expressions::DeepExpression {
        match self {
            ParameterIndex::SingleParameter => {
                lambda::expressions::DeepExpression(lambda::expressions::Expression::make_argument())
            }
            ParameterIndex::GetChild(index) => lambda::expressions::DeepExpression(
                lambda::expressions::Expression::make_get_child(
                    Arc::new(lambda::expressions::DeepExpression(
                        lambda::expressions::Expression::make_argument(),
                    )),
                    *index,
                ),
            ),
        }
    }
}

struct LocalVariable {
    parameter_index: ParameterIndex,
    type_: DeepType,
    compile_time_value: Option<DeepTree>,
}

impl LocalVariable {
    pub fn new(
        parameter_index: ParameterIndex,
        type_: DeepType,
        compile_time_value: Option<DeepTree>,
    ) -> Self {
        Self {
            parameter_index,
            type_,
            compile_time_value,
        }
    }
}

struct LambdaScope {
    names: BTreeMap<Name, LocalVariable>,
    captures: BTreeMap<TypedExpression, u16>,
}

impl LambdaScope {
    pub fn new_lambda_scope(parameters: &[TypeCheckedLambdaParameter]) -> Self {
        let mut names = BTreeMap::new();
        if parameters.len() == 1 {
            names.insert(
                parameters[0].name.clone(),
                LocalVariable::new(
                    ParameterIndex::SingleParameter,
                    parameters[0].type_.clone(),
                    parameters[0].compile_time_value.clone(),
                ),
            );
        } else {
            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(
                        ParameterIndex::GetChild(checked_index),
                        parameter.type_.clone(),
                        parameter.compile_time_value.clone(),
                    ),
                );
            }
        }
        Self {
            names,
            captures: BTreeMap::new(),
        }
    }

    pub fn new_constant_scope(name: Name, type_: DeepType, compile_time_value: DeepTree) -> Self {
        let mut names = BTreeMap::new();
        names.insert(
            name,
            LocalVariable::new(
                ParameterIndex::SingleParameter,
                type_.clone(),
                Some(compile_time_value),
            ),
        );
        Self {
            names,
            captures: BTreeMap::new(),
        }
    }

    pub fn find_parameter_index(
        &self,
        parameter_name: &Name,
    ) -> Option<(ParameterIndex, DeepType, Option<DeepTree>)> {
        self.names.get(parameter_name).map(|variable| {
            (
                variable.parameter_index,
                variable.type_.clone(),
                variable.compile_time_value.clone(),
            )
        })
    }

    pub fn capture(&mut self, expression: TypedExpression) -> CompilerOutput {
        let type_ = expression.type_.clone();
        let index = match self.captures.get(&expression) {
            Some(&already_exists) => already_exists,
            None => {
                let new_index = self
                    .captures
                    .len()
                    .try_into()
                    .expect("TODO handle too many captures");
                self.captures.insert(expression, new_index);
                new_index
            }
        };
        CompilerOutput::new(
            Some(TypedExpression::new(
                lambda::expressions::DeepExpression(
                    lambda::expressions::Expression::make_get_child(
                        Arc::new(DeepExpression(
                            lambda::expressions::Expression::make_environment(),
                        )),
                        index,
                    ),
                ),
                type_,
            )),
            Vec::new(),
        )
    }

    pub fn leave(self) -> Vec<TypedExpression> {
        let mut as_vec: Vec<(TypedExpression, u16)> = self.captures.into_iter().collect();
        as_vec.sort_by_key(|(_, index)| *index);
        // sanity check:
        for (expected_index, (_, actual_index)) in as_vec.iter().enumerate() {
            assert_eq!(expected_index, *actual_index as usize);
        }
        as_vec
            .into_iter()
            .map(|(expression, _)| expression)
            .collect()
    }
}

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, parameters: &[TypeCheckedLambdaParameter]) {
        self.lambda_layers
            .push(LambdaScope::new_lambda_scope(parameters));
    }

    pub fn leave_lambda_body(&mut self) -> Vec<TypedExpression> {
        let top_scope = self.lambda_layers.pop().unwrap();
        top_scope.leave()
    }

    pub fn define_constant(&mut self, name: Name, type_: DeepType, compile_time_value: DeepTree) {
        self.lambda_layers.push(LambdaScope::new_constant_scope(
            name,
            type_,
            compile_time_value,
        ));
    }

    pub fn undefine_constant(&mut self) {
        let captures = self.leave_lambda_body();
        if !captures.is_empty() {
            todo!()
        }
    }

    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, compile_time_value)) =
                last.find_parameter_index(identifier)
            {
                return match compile_time_value {
                    Some(value) => CompilerOutput::new(
                        Some(TypedExpression::new(
                            DeepExpression(lambda::expressions::Expression::make_literal(value)),
                            parameter_type,
                        )),
                        Vec::new(),
                    ),
                    None => CompilerOutput::new(
                        Some(TypedExpression::new(
                            parameter_index.create_deep_expression(),
                            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 async fn evaluate_type_at_compile_time(expression: &DeepExpression) -> DeepType {
    let storage = astraea::storage::InMemoryTreeStorage::empty();
    let digest = evaluate(expression, &storage, &storage, &None, &None).await.unwrap(/*TODO*/);
    let deep_tree = DeepTree::deserialize(&digest, &storage).await.unwrap(/*TODO*/);
    type_from_deep_tree(&deep_tree)
}

pub struct TypeCheckedLambdaParameter {
    pub name: Name,
    pub source_location: SourceLocation,
    pub type_: DeepType,
    pub compile_time_value: Option<DeepTree>,
}

impl TypeCheckedLambdaParameter {
    pub fn new(
        name: Name,
        source_location: SourceLocation,
        type_: DeepType,
        compile_time_value: Option<DeepTree>,
    ) -> Self {
        Self {
            name,
            source_location,
            type_,
            compile_time_value,
        }
    }
}

pub async fn check_lambda_parameters(
    parameters: &[LambdaParameter],
    environment_builder: &mut EnvironmentBuilder,
) -> Result<Vec<TypeCheckedLambdaParameter>, StoreError> {
    let mut checked_parameters = Vec::new();
    for parameter in parameters {
        let parameter_type: DeepType = match &parameter.type_annotation {
            Some(type_annotation) => {
                let checked_type = check_types(type_annotation, environment_builder).await?;
                if let Some(checked) = checked_type.entry_point {
                    evaluate_type_at_compile_time(&checked.expression).await
                } else {
                    todo!()
                }
            }
            None => {
                // If no type annotation is provided, we assume the type is `Any`.
                DeepType(GenericType::Any)
            }
        };
        checked_parameters.push(TypeCheckedLambdaParameter {
            name: parameter.name.clone(),
            source_location: parameter.source_location,
            type_: parameter_type,
            compile_time_value: None, // TODO?
        });
    }
    Ok(checked_parameters)
}

pub async fn check_lambda(
    parameters: &[LambdaParameter],
    body: &ast::Expression,
    environment_builder: &mut EnvironmentBuilder,
) -> Result<CompilerOutput, StoreError> {
    let checked_parameters = check_lambda_parameters(parameters, environment_builder).await?;
    environment_builder.enter_lambda_body(&checked_parameters[..]);
    let body_result = check_types(body, environment_builder).await;
    // 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),
                }),
                DeepType(GenericType::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 async fn check_braces(
    expression: &[ast::Expression],
    environment_builder: &mut EnvironmentBuilder,
) -> Result<CompilerOutput, StoreError> {
    if expression.len() != 1 {
        todo!()
    }
    check_types(&expression[0], environment_builder).await
}

pub async fn check_let(
    name: &Name,
    location: &SourceLocation,
    value: &ast::Expression,
    body: &ast::Expression,
    environment_builder: &mut EnvironmentBuilder,
) -> Result<CompilerOutput, StoreError> {
    let value_checked = check_types(value, environment_builder).await?;
    if !value_checked.errors.is_empty() {
        todo!()
    }
    let value_checked_unwrapped = value_checked.entry_point.unwrap();
    let checked_parameters = [TypeCheckedLambdaParameter::new(
        name.clone(),
        *location,
        value_checked_unwrapped.type_.clone(),
        // TODO: add const keyword or something
        None,
    )];
    environment_builder.enter_lambda_body(&checked_parameters[..]);
    let body_result = check_types(body, environment_builder).await;
    // 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::make_apply(
                    Arc::new(lambda::expressions::DeepExpression(
                        lambda::expressions::Expression::Lambda {
                            environment: Arc::new(DeepExpression(Expression::make_construct_tree(
                                environment_expressions,
                            ))),
                            body: Arc::new(body_checked.expression),
                        },
                    )),
                    Arc::new(value_checked_unwrapped.expression),
                )),
                body_checked.type_,
            )),
            errors: body_output.errors,
        }),
        None => Ok(CompilerOutput::new(None, body_output.errors)),
    }
}

pub async fn check_types(
    syntax_tree: &ast::Expression,
    environment_builder: &mut EnvironmentBuilder,
) -> Result<CompilerOutput, StoreError> {
    Box::pin(async move {
        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(
                        DeepTree::try_from_string(value).unwrap(/*TODO*/),
                    )),
                    DeepType(GenericType::String),
                )),
                Vec::new(),
            )),
            ast::Expression::Apply { callee, arguments } => {
                let callee_output = check_types(callee, environment_builder).await?;
                let argument_output = if arguments.len() == 1 {
                    // For N=1 we don't need an indirection.
                    check_types(&arguments[0], environment_builder).await?
                } else {
                    check_tree_construction_or_argument_list(&arguments[..], environment_builder)
                        .await?
                };
                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_.0 {
                            GenericType::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).await
            }
            ast::Expression::ConstructTree(arguments) => {
                check_tree_construction_or_argument_list(&arguments[..], environment_builder).await
            }
            ast::Expression::Braces(expression) => {
                check_types(expression, environment_builder).await
            }
            ast::Expression::Let {
                name,
                location,
                value,
                body,
            } => check_let(name, location, value, body, environment_builder).await,
        }
    })
    .await
}

1	use crate::{
2	ast::{self, LambdaParameter},
3	compilation::{CompilerOutput, SourceLocation},
4	};
5	use astraea::{
6	deep_tree::DeepTree,
7	storage::StoreError,
8	tree::{ReferenceIndex, TreeBlob},
9	};
10	use lambda::{
11	expressions::{evaluate, DeepExpression, Expression},
12	name::Name,
13	};
14	use serde::{Deserialize, Serialize};
15	use std::{collections::BTreeMap, sync::Arc};
16
17	#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash, Clone, Serialize, Deserialize)]
18	pub enum GenericType<T>
19	where
20	T: Clone,
21	{
22	Any,
23	String,
24	TreeWithKnownChildTypes(Vec<T>),
25	Function {
26	parameters: Vec<T>,
27	return_type: Box<T>,
28	},
29	Type,
30	}
31
32	#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash, Clone)]
33	pub struct DeepType(pub GenericType<DeepType>);
34
35	pub fn to_reference_type(deep_type: &DeepType) -> (GenericType<ReferenceIndex>, Vec<DeepType>) {	1✔
36	match deep_type.0 {	1✔
NEW 37	GenericType::Any => (GenericType::Any, Vec::new()),	×
38	GenericType::String => (GenericType::String, Vec::new()),	1✔
NEW 39	GenericType::TreeWithKnownChildTypes(ref children) => (	×
NEW 40	GenericType::TreeWithKnownChildTypes(	×
NEW 41	(0u64..(children.len() as u64))	×
NEW 42	.map(ReferenceIndex)	×
NEW 43	.collect(),	×
44	),
NEW 45	children.clone(),	×
46	),
47	GenericType::Function {
NEW 48	ref parameters,	×
NEW 49	ref return_type,	×
NEW 50	} => {	×
NEW 51	let mut parameters_references = Vec::new();	×
NEW 52	let mut children = Vec::new();	×
NEW 53	for (index, parameter) in parameters.iter().enumerate() {	×
54	parameters_references.push(ReferenceIndex(index as u64));
55	children.push(parameter.clone());
56	}
NEW 57	let return_type_reference = ReferenceIndex(children.len() as u64);	×
NEW 58	children.push(return_type.as_ref().clone());	×
59	(
NEW 60	GenericType::Function {	×
NEW 61	parameters: parameters_references,	×
NEW 62	return_type: Box::new(return_type_reference),	×
63	},
NEW 64	children,	×
65	)
66	}
NEW 67	GenericType::Type => (GenericType::Type, Vec::new()),	×
68	}
69	}
70
71	pub fn type_to_deep_tree(deep_type: &DeepType) -> DeepTree {	1✔
72	let (body, children) = to_reference_type(deep_type);	1✔
73	let body_serialized = postcard::to_allocvec(&body).unwrap(/TODO/);	1✔
74	DeepTree::new(
75	TreeBlob::try_from(bytes::Bytes::from( body_serialized)).unwrap(/TODO/),	1✔
76	children.iter().map(type_to_deep_tree).collect(),	1✔
77	)
78	}
79
80	pub fn from_reference_type(body: &GenericType<ReferenceIndex>, children: &[DeepType]) -> DeepType {	1✔
81	match body {	1✔
NEW 82	GenericType::Any => DeepType(GenericType::Any),	×
83	GenericType::String => DeepType(GenericType::String),	1✔
NEW 84	GenericType::TreeWithKnownChildTypes(ref children_references) => {	×
NEW 85	let mut resulting_children = Vec::new();	×
NEW 86	for reference in children_references {	×
NEW 87	let index = reference.0 as usize;	×
NEW 88	if index < children.len() {	×
NEW 89	resulting_children.push(children[index].clone());	×
90	} else {
91	// TODO error handling
92	// This should not happen if the tree is well-formed.
93	panic!("Reference index out of bounds: {index}");
94	}
95	}
NEW 96	DeepType(GenericType::TreeWithKnownChildTypes(resulting_children))	×
97	}
98	GenericType::Function {
NEW 99	ref parameters,	×
NEW 100	ref return_type,	×
NEW 101	} => {	×
NEW 102	let mut resulting_parameters = Vec::new();	×
NEW 103	for reference in parameters {	×
NEW 104	let index: usize = reference.0.try_into().expect("TODO");	×
NEW 105	if index < children.len() {	×
NEW 106	resulting_parameters.push(children[index].clone());	×
107	} else {
108	// TODO error handling
109	// This should not happen if the tree is well-formed.
110	panic!("Reference index out of bounds: {index}");
111	}
112	}
NEW 113	let resulting_return_type = {	×
NEW 114	let index: usize = return_type.0.try_into().expect("TODO");	×
NEW 115	if index < children.len() {	×
NEW 116	children[index].clone()	×
117	} else {
118	// TODO error handling
119	panic!("Reference index out of bounds: {index}");
120	}
121	};
NEW 122	DeepType(GenericType::Function {	×
NEW 123	parameters: resulting_parameters,	×
NEW 124	return_type: Box::new(resulting_return_type),	×
125	})
126	}
NEW 127	GenericType::Type => DeepType(GenericType::Type),	×
128	}
129	}
130
131	pub fn type_from_deep_tree(deep_tree: &DeepTree) -> DeepType {	1✔
132	let body: GenericType<ReferenceIndex> =	1✔
133	postcard::from_bytes(deep_tree.blob().as_slice()).unwrap(/TODO/);	1✔
134	let children: Vec<_> = deep_tree	1✔
135	.references()
136	.iter()
137	.map(type_from_deep_tree)	1✔
138	.collect();
139	from_reference_type(&body, &children)	1✔
140	}
141
142	#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
143	pub struct TypedExpression {
144	pub expression: DeepExpression,
145	pub type_: DeepType,
146	}
147
148	impl TypedExpression {
149	pub fn new(expression: DeepExpression, type_: DeepType) -> Self {	150✔
150	Self { expression, type_ }
151	}
152	}
153
154	async fn check_tree_construction_or_argument_list(	18✔
155	arguments: &[ast::Expression],
156	environment_builder: &mut EnvironmentBuilder,
157	) -> Result<CompilerOutput, StoreError> {
158	let mut errors = Vec::new();	18✔
159	let mut checked_arguments = Vec::new();	18✔
160	let mut argument_types = Vec::new();	18✔
161	for argument in arguments {	78✔
162	let output = check_types(argument, environment_builder).await?;	60✔
163	errors.extend(output.errors);
164	if let Some(checked) = output.entry_point {	30✔
165	checked_arguments.push(Arc::new(checked.expression));
166	argument_types.push(checked.type_);
167	} else {
168	return Ok(CompilerOutput::new(None, errors));	×
169	}
170	}
171	Ok(CompilerOutput {	18✔
172	entry_point: Some(TypedExpression::new(	18✔
173	lambda::expressions::DeepExpression(lambda::expressions::Expression::ConstructTree(	18✔
174	checked_arguments,	18✔
175	)),
176	DeepType(GenericType::TreeWithKnownChildTypes(argument_types)),	18✔
177	)),
178	errors,	18✔
179	})
180	}
181
182	#[derive(Debug, Clone, Copy)]
183	enum ParameterIndex {
184	SingleParameter,
185	GetChild(u16),
186	}
187
188	impl ParameterIndex {
189	pub fn create_deep_expression(&self) -> lambda::expressions::DeepExpression {	32✔
190	match self {	32✔
191	ParameterIndex::SingleParameter => {
192	lambda::expressions::DeepExpression(lambda::expressions::Expression::make_argument())	24✔
193	}
194	ParameterIndex::GetChild(index) => lambda::expressions::DeepExpression(
195	lambda::expressions::Expression::make_get_child(	8✔
196	Arc::new(lambda::expressions::DeepExpression(	8✔
197	lambda::expressions::Expression::make_argument(),	8✔
198	)),
199	*index,	8✔
200	),
201	),
202	}
203	}
204	}
205
206	struct LocalVariable {
207	parameter_index: ParameterIndex,
208	type_: DeepType,
209	compile_time_value: Option<DeepTree>,
210	}
211
212	impl LocalVariable {
213	pub fn new(	28✔
214	parameter_index: ParameterIndex,
215	type_: DeepType,
216	compile_time_value: Option<DeepTree>,
217	) -> Self {
218	Self {
219	parameter_index,
220	type_,
221	compile_time_value,
222	}
223	}
224	}
225
226	struct LambdaScope {
227	names: BTreeMap<Name, LocalVariable>,
228	captures: BTreeMap<TypedExpression, u16>,
229	}
230
231	impl LambdaScope {
232	pub fn new_lambda_scope(parameters: &[TypeCheckedLambdaParameter]) -> Self {	39✔
233	let mut names = BTreeMap::new();	39✔
234	if parameters.len() == 1 {	56✔
235	names.insert(	17✔
236	parameters[0].name.clone(),	17✔
237	LocalVariable::new(	17✔
238	ParameterIndex::SingleParameter,	17✔
239	parameters[0].type_.clone(),	17✔
240	parameters[0].compile_time_value.clone(),	17✔
241	),
242	);
243	} else {
244	for (index, parameter) in parameters.iter().enumerate() {	32✔
245	let checked_index: u16 = index.try_into().expect("TODO handle too many parameters");
246	names.insert(
247	parameter.name.clone(),
248	LocalVariable::new(
249	ParameterIndex::GetChild(checked_index),
250	parameter.type_.clone(),
251	parameter.compile_time_value.clone(),
252	),
253	);
254	}
255	}
256	Self {
257	names,
258	captures: BTreeMap::new(),	39✔
259	}
260	}
261
262	pub fn new_constant_scope(name: Name, type_: DeepType, compile_time_value: DeepTree) -> Self {	1✔
263	let mut names = BTreeMap::new();	1✔
264	names.insert(	1✔
265	name,	1✔
266	LocalVariable::new(	1✔
267	ParameterIndex::SingleParameter,	1✔
268	type_.clone(),	1✔
269	Some(compile_time_value),	1✔
270	),
271	);
272	Self {
273	names,
274	captures: BTreeMap::new(),	1✔
275	}
276	}
277
278	pub fn find_parameter_index(	56✔
279	&self,
280	parameter_name: &Name,
281	) -> Option<(ParameterIndex, DeepType, Option<DeepTree>)> {
282	self.names.get(parameter_name).map(\|variable\| {	89✔
283	(
284	variable.parameter_index,	33✔
285	variable.type_.clone(),	33✔
286	variable.compile_time_value.clone(),	33✔
287	)
288	})
289	}
290
291	pub fn capture(&mut self, expression: TypedExpression) -> CompilerOutput {	23✔
292	let type_ = expression.type_.clone();	23✔
293	let index = match self.captures.get(&expression) {	46✔
294	Some(&already_exists) => already_exists,	10✔
295	None => {
296	let new_index = self	13✔
297	.captures	13✔
298	.len()
299	.try_into()
300	.expect("TODO handle too many captures");
301	self.captures.insert(expression, new_index);	13✔
302	new_index	13✔
303	}
304	};
305	CompilerOutput::new(
306	Some(TypedExpression::new(	23✔
307	lambda::expressions::DeepExpression(	23✔
308	lambda::expressions::Expression::make_get_child(	23✔
309	Arc::new(DeepExpression(	23✔
310	lambda::expressions::Expression::make_environment(),	23✔
311	)),
312	index,	23✔
313	),
314	),
315	type_,	23✔
316	)),
317	Vec::new(),	23✔
318	)
319	}
320
321	pub fn leave(self) -> Vec<TypedExpression> {	40✔
322	let mut as_vec: Vec<(TypedExpression, u16)> = self.captures.into_iter().collect();	40✔
323	as_vec.sort_by_key(\|(_, index)\| *index);	48✔
324	// sanity check:
325	for (expected_index, (_, actual_index)) in as_vec.iter().enumerate() {	53✔
326	assert_eq!(expected_index, *actual_index as usize);
327	}
328	as_vec	40✔
329	.into_iter()
330	.map(\|(expression, _)\| expression)	53✔
331	.collect()
332	}
333	}
334
335	pub struct EnvironmentBuilder {
336	lambda_layers: Vec<LambdaScope>,
337	}
338
339	impl Default for EnvironmentBuilder {
340	fn default() -> Self {	×
341	Self::new()	×
342	}
343	}
344
345	impl EnvironmentBuilder {
346	pub fn new() -> Self {	28✔
347	Self {
348	lambda_layers: Vec::new(),	28✔
349	}
350	}
351
352	pub fn is_empty(&self) -> bool {	28✔
353	self.lambda_layers.is_empty()	28✔
354	}
355
356	pub fn enter_lambda_body(&mut self, parameters: &[TypeCheckedLambdaParameter]) {	39✔
357	self.lambda_layers	39✔
358	.push(LambdaScope::new_lambda_scope(parameters));	39✔
359	}
360
361	pub fn leave_lambda_body(&mut self) -> Vec<TypedExpression> {	40✔
362	let top_scope = self.lambda_layers.pop().unwrap();	40✔
363	top_scope.leave()	40✔
364	}
365
366	pub fn define_constant(&mut self, name: Name, type_: DeepType, compile_time_value: DeepTree) {	1✔
367	self.lambda_layers.push(LambdaScope::new_constant_scope(	1✔
368	name,	1✔
369	type_,	1✔
370	compile_time_value,	1✔
371	));
372	}
373
374	pub fn undefine_constant(&mut self) {	1✔
375	let captures = self.leave_lambda_body();	1✔
376	if !captures.is_empty() {	1✔
377	todo!()
378	}
379	}
380
381	pub fn read(&mut self, identifier: &Name, location: &SourceLocation) -> CompilerOutput {	35✔
382	Self::read_down(&mut self.lambda_layers, identifier, location)	35✔
383	}
384
385	fn read_down(	58✔
386	layers: &mut [LambdaScope],
387	identifier: &Name,
388	location: &SourceLocation,
389	) -> CompilerOutput {
390	let layer_count = layers.len();	58✔
391	if let Some(last) = layers.last_mut() {	114✔
392	if let Some((parameter_index, parameter_type, compile_time_value)) =	33✔
393	last.find_parameter_index(identifier)
394	{
395	return match compile_time_value {
396	Some(value) => CompilerOutput::new(	1✔
397	Some(TypedExpression::new(	1✔
398	DeepExpression(lambda::expressions::Expression::make_literal(value)),	1✔
399	parameter_type,	1✔
400	)),
401	Vec::new(),	1✔
402	),
403	None => CompilerOutput::new(	32✔
404	Some(TypedExpression::new(	32✔
405	parameter_index.create_deep_expression(),	32✔
406	parameter_type,	32✔
407	)),
408	Vec::new(),	32✔
409	),
410	};
411	} else if layer_count > 1 {	23✔
412	let result = Self::read_down(&mut layers[..layer_count - 1], identifier, location);	23✔
413	if result.entry_point.is_some() {	23✔
414	return layers	23✔
415	.last_mut()	23✔
416	.unwrap()	23✔
417	.capture(result.entry_point.unwrap());	23✔
418	}
419	return result;	×
420	}
421	}
422	CompilerOutput::new(
423	None,	2✔
424	vec![crate::compilation::CompilerError::new(	2✔
425	format!("Identifier {identifier} not found"),	2✔
426	*location,	2✔
427	)],
428	)
429	}
430	}
431
432	pub async fn evaluate_type_at_compile_time(expression: &DeepExpression) -> DeepType {	2✔
433	let storage = astraea::storage::InMemoryTreeStorage::empty();	1✔
434	let digest = evaluate(expression, &storage, &storage, &None, &None).await.unwrap(/TODO/);	3✔
435	let deep_tree = DeepTree::deserialize(&digest, &storage).await.unwrap(/TODO/);	2✔
436	type_from_deep_tree(&deep_tree)
437	}
438
439	pub struct TypeCheckedLambdaParameter {
440	pub name: Name,
441	pub source_location: SourceLocation,
442	pub type_: DeepType,
443	pub compile_time_value: Option<DeepTree>,
444	}
445
446	impl TypeCheckedLambdaParameter {
447	pub fn new(	3✔
448	name: Name,
449	source_location: SourceLocation,
450	type_: DeepType,
451	compile_time_value: Option<DeepTree>,
452	) -> Self {
453	Self {
454	name,
455	source_location,
456	type_,
457	compile_time_value,
458	}
459	}
460	}
461
462	pub async fn check_lambda_parameters(	36✔
463	parameters: &[LambdaParameter],
464	environment_builder: &mut EnvironmentBuilder,
465	) -> Result<Vec<TypeCheckedLambdaParameter>, StoreError> {
466	let mut checked_parameters = Vec::new();	36✔
467	for parameter in parameters {	84✔
468	let parameter_type: DeepType = match &parameter.type_annotation {	48✔
469	Some(type_annotation) => {	1✔
470	let checked_type = check_types(type_annotation, environment_builder).await?;	2✔
471	if let Some(checked) = checked_type.entry_point {	1✔
472	evaluate_type_at_compile_time(&checked.expression).await	1✔
473	} else {
474	todo!()
475	}
476	}
477	None => {
478	// If no type annotation is provided, we assume the type is `Any`.
479	DeepType(GenericType::Any)	23✔
480	}
481	};
482	checked_parameters.push(TypeCheckedLambdaParameter {
483	name: parameter.name.clone(),
484	source_location: parameter.source_location,
485	type_: parameter_type,
486	compile_time_value: None, // TODO?
487	});
488	}
489	Ok(checked_parameters)	36✔
490	}
491
492	pub async fn check_lambda(	36✔
493	parameters: &[LambdaParameter],
494	body: &ast::Expression,
495	environment_builder: &mut EnvironmentBuilder,
496	) -> Result<CompilerOutput, StoreError> {
497	let checked_parameters = check_lambda_parameters(parameters, environment_builder).await?;	72✔
498	environment_builder.enter_lambda_body(&checked_parameters[..]);
499	let body_result = check_types(body, environment_builder).await;	36✔
500	// TODO: use RAII or something?
501	let environment = environment_builder.leave_lambda_body();	36✔
502	let environment_expressions = environment	36✔
503	.into_iter()
504	.map(\|typed_expression\| Arc::new(typed_expression.expression))	48✔
505	.collect();
506	let body_output = body_result?;	72✔
507	match body_output.entry_point {
508	Some(body_checked) => Ok(CompilerOutput {	35✔
509	entry_point: Some(TypedExpression::new(	35✔
510	lambda::expressions::DeepExpression(lambda::expressions::Expression::Lambda {	35✔
511	environment: Arc::new(DeepExpression(Expression::make_construct_tree(	35✔
512	environment_expressions,	35✔
513	))),
514	body: Arc::new(body_checked.expression),	35✔
515	}),
516	DeepType(GenericType::Function {	35✔
517	parameters: checked_parameters	35✔
518	.into_iter()	35✔
519	.map(\|parameter\| parameter.type_)	58✔
520	.collect(),	35✔
521	return_type: Box::new(body_checked.type_),	35✔
522	}),
523	)),
524	errors: body_output.errors,	35✔
525	}),
526	None => Ok(CompilerOutput::new(None, body_output.errors)),	1✔
527	}
528	}
529
NEW 530	pub async fn check_braces(	×
531	expression: &[ast::Expression],
532	environment_builder: &mut EnvironmentBuilder,
533	) -> Result<CompilerOutput, StoreError> {
534	if expression.len() != 1 {	×
535	todo!()
536	}
NEW 537	check_types(&expression[0], environment_builder).await	×
538	}
539
540	pub async fn check_let(	3✔
541	name: &Name,
542	location: &SourceLocation,
543	value: &ast::Expression,
544	body: &ast::Expression,
545	environment_builder: &mut EnvironmentBuilder,
546	) -> Result<CompilerOutput, StoreError> {
547	let value_checked = check_types(value, environment_builder).await?;	6✔
548	if !value_checked.errors.is_empty() {
549	todo!()
550	}
551	let value_checked_unwrapped = value_checked.entry_point.unwrap();	3✔
552	let checked_parameters = [TypeCheckedLambdaParameter::new(	3✔
553	name.clone(),	3✔
554	*location,	3✔
555	value_checked_unwrapped.type_.clone(),	3✔
556	// TODO: add const keyword or something
557	None,	3✔
558	)];
559	environment_builder.enter_lambda_body(&checked_parameters[..]);	3✔
560	let body_result = check_types(body, environment_builder).await;	6✔
561	// TODO: use RAII or something?
562	let environment = environment_builder.leave_lambda_body();	3✔
563	let environment_expressions = environment	3✔
564	.into_iter()
565	.map(\|typed_expression\| Arc::new(typed_expression.expression))	4✔
566	.collect();
567	let body_output = body_result?;	6✔
568	match body_output.entry_point {
569	Some(body_checked) => Ok(CompilerOutput {	3✔
570	entry_point: Some(TypedExpression::new(	3✔
571	lambda::expressions::DeepExpression(lambda::expressions::Expression::make_apply(	3✔
572	Arc::new(lambda::expressions::DeepExpression(	3✔
573	lambda::expressions::Expression::Lambda {	3✔
574	environment: Arc::new(DeepExpression(Expression::make_construct_tree(	3✔
575	environment_expressions,	3✔
576	))),
577	body: Arc::new(body_checked.expression),	3✔
578	},
579	)),
580	Arc::new(value_checked_unwrapped.expression),	3✔
581	)),
582	body_checked.type_,	3✔
583	)),
584	errors: body_output.errors,	3✔
585	}),
586	None => Ok(CompilerOutput::new(None, body_output.errors)),	×
587	}
588	}
589
590	pub async fn check_types(	114✔
591	syntax_tree: &ast::Expression,
592	environment_builder: &mut EnvironmentBuilder,
593	) -> Result<CompilerOutput, StoreError> {
594	Box::pin(async move {	228✔
595	match syntax_tree {	114✔
596	ast::Expression::Identifier(name, location) => {	35✔
597	Ok(environment_builder.read(name, location))	35✔
598	}
599	ast::Expression::StringLiteral(value) => Ok(CompilerOutput::new(	14✔
600	Some(TypedExpression::new(	14✔
601	lambda::expressions::DeepExpression(lambda::expressions::Expression::Literal(	14✔
602	DeepTree::try_from_string(value).unwrap(/TODO/),	14✔
603	)),
604	DeepType(GenericType::String),	14✔
605	)),
606	Vec::new(),	14✔
607	)),
608	ast::Expression::Apply { callee, arguments } => {	6✔
609	let callee_output = check_types(callee, environment_builder).await?;	12✔
610	let argument_output = if arguments.len() == 1 {	6✔
611	// For N=1 we don't need an indirection.
612	check_types(&arguments[0], environment_builder).await?	3✔
613	} else {
614	check_tree_construction_or_argument_list(&arguments[..], environment_builder)	3✔
615	.await?	3✔
616	};
617	let errors = callee_output
618	.errors
619	.into_iter()
620	.chain(argument_output.errors)
621	.collect();
622	match (callee_output.entry_point, argument_output.entry_point) {
623	(Some(callee_checked), Some(argument_checked)) => {	5✔
624	let return_type = match &callee_checked.type_.0 {	9✔
625	GenericType::Function { return_type, .. } => {
626	return_type.as_ref().clone()
627	}
628	_ => {
629	return Ok(CompilerOutput::new(	1✔
630	None,	1✔
631	vec![crate::compilation::CompilerError::new(	1✔
632	"Callee is not a function".to_string(),	1✔
633	callee.source_location(),	1✔
634	)],
635	))
636	}
637	};
638	// TODO: check argument types against callee parameter types
639	Ok(CompilerOutput {
640	entry_point: Some(TypedExpression::new(
641	lambda::expressions::DeepExpression(
642	lambda::expressions::Expression::Apply {
643	callee: Arc::new(callee_checked.expression),
644	argument: Arc::new(argument_checked.expression),
645	},
646	),
647	return_type,
648	)),
649	errors,
650	})
651	}
652	(None, _) \| (_, None) => Ok(CompilerOutput::new(None, errors)),	1✔
653	}
654	}
655	ast::Expression::Lambda { parameters, body } => {	36✔
656	check_lambda(&parameters[..], body, environment_builder).await	36✔
657	}
658	ast::Expression::ConstructTree(arguments) => {	15✔
659	check_tree_construction_or_argument_list(&arguments[..], environment_builder).await	15✔
660	}
661	ast::Expression::Braces(expression) => {	5✔
662	check_types(expression, environment_builder).await	5✔
663	}
664	ast::Expression::Let {
665	name,	3✔
666	location,	3✔
667	value,	3✔
668	body,	3✔
669	} => check_let(name, location, value, body, environment_builder).await,	3✔
670	}
671	})
672	.await	114✔
673	}

TyRoXx / NonlocalityOS / 15327202569

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