20205683691

Committed 14 Dec 2025 09:06AM UTC coverage: 80.811% (+0.03%) from 80.786%

Build # 20205683691

Build Type

push

github

Committed by

TyRoXx

Commit Message

Prevent Trees with too many children being created

Run Details

131 of 148 new or added lines in 11 files covered. (88.51%)

2 existing lines in 1 file now uncovered.

5441 of 6733 relevant lines covered (80.81%)

33569.52 hits per line

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

93.88

/lambda/src/expressions.rs

use crate::name::Name;
use astraea::deep_tree::DeepTree;
use astraea::tree::{
    BlobDigest, HashedTree, ReferenceIndex, Tree, TreeChildren, TreeDeserializationError,
    TreeSerializationError,
};
use astraea::{
    storage::{LoadTree, StoreError, StoreTree},
    tree::TreeBlob,
};
use serde::{Deserialize, Serialize};
use std::fmt::Display;
use std::future::Future;
use std::hash::Hash;
use std::{pin::Pin, sync::Arc};

pub trait PrintExpression {
    fn print(&self, writer: &mut dyn std::fmt::Write, level: usize) -> std::fmt::Result;
}

#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash, Clone, Serialize, Deserialize)]
pub enum Expression<E, TreeLike>
where
    E: Clone + Display + PrintExpression,
    TreeLike: Clone + std::fmt::Debug,
{
    Literal(TreeLike),
    Apply { callee: E, argument: E },
    Argument,
    Environment,
    Lambda { environment: E, body: E },
    ConstructTree(Vec<E>),
    GetChild { parent: E, index: u16 },
}

impl<E, V> PrintExpression for Expression<E, V>
where
    E: Clone + Display + PrintExpression,
    V: Clone + std::fmt::Debug,
{
    fn print(&self, writer: &mut dyn std::fmt::Write, level: usize) -> std::fmt::Result {
        match self {
            Expression::Literal(literal_value) => {
                write!(writer, "literal({literal_value:?})")
            }
            Expression::Apply { callee, argument } => {
                callee.print(writer, level)?;
                write!(writer, "(")?;
                argument.print(writer, level)?;
                write!(writer, ")")
            }
            Expression::Argument => {
                write!(writer, "$arg")
            }
            Expression::Environment => {
                write!(writer, "$env")
            }
            Expression::Lambda { environment, body } => {
                write!(writer, "$env={{")?;
                let indented = level + 1;
                environment.print(writer, indented)?;
                writeln!(writer, "}}($arg) =>")?;
                for _ in 0..(indented * 2) {
                    write!(writer, " ")?;
                }
                body.print(writer, indented)
            }
            Expression::ConstructTree(arguments) => {
                write!(writer, "[")?;
                for argument in arguments {
                    argument.print(writer, level)?;
                    write!(writer, ", ")?;
                }
                write!(writer, "]")
            }
            Expression::GetChild { parent, index } => {
                parent.print(writer, level)?;
                write!(writer, ".{index}")
            }
        }
    }
}

impl<E, TreeLike> Expression<E, TreeLike>
where
    E: Clone + Display + PrintExpression,
    TreeLike: Clone + std::fmt::Debug,
{
    pub fn make_literal(value: TreeLike) -> Self {
        Expression::Literal(value)
    }

    pub fn make_apply(callee: E, argument: E) -> Self {
        Expression::Apply { callee, argument }
    }

    pub fn make_argument() -> Self {
        Expression::Argument
    }

    pub fn make_environment() -> Self {
        Expression::Environment
    }

    pub fn make_lambda(environment: E, body: E) -> Self {
        Expression::Lambda { environment, body }
    }

    pub fn make_construct_tree(arguments: Vec<E>) -> Self {
        Expression::ConstructTree(arguments)
    }

    pub fn make_get_child(parent: E, index: u16) -> Self {
        Expression::GetChild { parent, index }
    }

    pub async fn map_child_expressions<
        't,
        Expr: Clone + Display + PrintExpression,
        TreeLike2: Clone + std::fmt::Debug,
        Error,
        F,
        G,
    >(
        &self,
        transform_expression: &'t F,
        transform_tree: &'t G,
    ) -> Result<Expression<Expr, TreeLike2>, Error>
    where
        F: Fn(&E) -> Pin<Box<dyn Future<Output = Result<Expr, Error>> + 't>>,
        G: Fn(&TreeLike) -> Pin<Box<dyn Future<Output = Result<TreeLike2, Error>> + 't>>,
    {
        match self {
            Expression::Literal(value) => Ok(Expression::Literal(transform_tree(value).await?)),
            Expression::Apply { callee, argument } => Ok(Expression::Apply {
                callee: transform_expression(callee).await?,
                argument: transform_expression(argument).await?,
            }),
            Expression::Argument => Ok(Expression::Argument),
            Expression::Environment => Ok(Expression::Environment),
            Expression::Lambda { environment, body } => Ok(Expression::Lambda {
                environment: transform_expression(environment).await?,
                body: transform_expression(body).await?,
            }),
            Expression::ConstructTree(items) => {
                let mut transformed_items = Vec::new();
                for item in items.iter() {
                    transformed_items.push(transform_expression(item).await?);
                }
                Ok(Expression::ConstructTree(transformed_items))
            }
            Expression::GetChild { parent, index } => Ok(Expression::GetChild {
                parent: transform_expression(parent).await?,
                index: *index,
            }),
        }
    }
}

impl<E, V> Display for Expression<E, V>
where
    E: Clone + Display + PrintExpression,
    V: Clone + std::fmt::Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        self.print(f, 0)
    }
}

#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Clone)]
pub struct DeepExpression(pub Expression<Arc<DeepExpression>, DeepTree>);

impl PrintExpression for DeepExpression {
    fn print(&self, writer: &mut dyn std::fmt::Write, level: usize) -> std::fmt::Result {
        self.0.print(writer, level)
    }
}

impl PrintExpression for Arc<DeepExpression> {
    fn print(&self, writer: &mut dyn std::fmt::Write, level: usize) -> std::fmt::Result {
        self.0.print(writer, level)
    }
}

impl Display for DeepExpression {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

pub type ShallowExpression = Expression<BlobDigest, BlobDigest>;

impl PrintExpression for BlobDigest {
    fn print(&self, writer: &mut dyn std::fmt::Write, _level: usize) -> std::fmt::Result {
        write!(writer, "{self}")
    }
}

pub type ReferenceExpression = Expression<ReferenceIndex, ReferenceIndex>;

impl PrintExpression for ReferenceIndex {
    fn print(&self, writer: &mut dyn std::fmt::Write, _level: usize) -> std::fmt::Result {
        write!(writer, "{self}")
    }
}

pub fn to_reference_expression(
    expression: &ShallowExpression,
) -> (ReferenceExpression, Vec<BlobDigest>) {
    match expression {
        Expression::Literal(value) => (
            ReferenceExpression::Literal(ReferenceIndex(0)),
            vec![*value],
        ),
        Expression::Apply { callee, argument } => (
            ReferenceExpression::Apply {
                callee: ReferenceIndex(0),
                argument: ReferenceIndex(1),
            },
            // TODO: deduplicate?
            vec![*callee, *argument],
        ),
        Expression::Argument => (ReferenceExpression::Argument, vec![]),
        Expression::Environment => (ReferenceExpression::Environment, vec![]),
        Expression::Lambda { environment, body } => (
            ReferenceExpression::Lambda {
                environment: ReferenceIndex(0),
                body: ReferenceIndex(1),
            },
            vec![*environment, *body],
        ),
        Expression::ConstructTree(items) => (
            ReferenceExpression::ConstructTree(
                (0..items.len())
                    .map(|index| ReferenceIndex(index as u64))
                    .collect(),
            ),
            // TODO: deduplicate?
            items.clone(),
        ),
        Expression::GetChild { parent, index } => (
            ReferenceExpression::GetChild {
                parent: ReferenceIndex(0),
                index: *index,
            },
            vec![*parent],
        ),
    }
}

pub async fn deserialize_shallow(tree: &Tree) -> Result<ShallowExpression, ()> {
    let reference_expression: ReferenceExpression = postcard::from_bytes(tree.blob().as_slice())
        .unwrap(/*TODO*/);
    reference_expression
        .map_child_expressions(
            &|child: &ReferenceIndex| -> Pin<Box<dyn Future<Output = Result<BlobDigest, ()>>>> {
                let child = tree.children().references()[child.0 as usize];
                Box::pin(async move { Ok(child) })
            },
            &|child: &ReferenceIndex| -> Pin<Box<dyn Future<Output = Result<BlobDigest, ()>>>> {
                let child = tree.children().references()[child.0 as usize];
                Box::pin(async move { Ok(child) })
            },
        )
        .await
}

pub async fn deserialize_recursively(
    root: &BlobDigest,
    load_tree: &(dyn LoadTree + Sync),
) -> Result<DeepExpression, ()> {
    let root_loaded = load_tree.load_tree(root).await.unwrap(/*TODO*/).hash().unwrap(/*TODO*/);
    let shallow = deserialize_shallow(root_loaded.tree()).await?;
    let deep = shallow
        .map_child_expressions(
            &|child: &BlobDigest| -> Pin<Box<dyn Future<Output = Result<Arc<DeepExpression>, ()>>>> {
                let child = *child;
                Box::pin(async move { deserialize_recursively(&child, load_tree)
                    .await
                    .map(Arc::new) })
            },
            &|child: &BlobDigest| -> Pin<Box<dyn Future<Output = Result<DeepTree, ()>>>> {
                let child = *child;
                Box::pin(async move { Ok(DeepTree::deserialize(&child, load_tree).await.unwrap(/*TODO*/)) })
            },
        )
        .await?;
    Ok(DeepExpression(deep))
}

pub fn expression_to_tree(expression: &ShallowExpression) -> Result<Tree, TreeSerializationError> {
    let (reference_expression, references) = to_reference_expression(expression);
    let children = match TreeChildren::try_from(references) {
        Some(success) => success,
        None => return Err(TreeSerializationError::TooManyChildren),
    };
    let blob = postcard::to_allocvec(&reference_expression).unwrap(/*TODO*/);
    Ok(Tree::new(
        TreeBlob::try_from(bytes::Bytes::from_owner(blob)).unwrap(/*TODO*/),
        children,
    ))
}

pub async fn serialize_shallow(
    expression: &ShallowExpression,
    storage: &(dyn StoreTree + Sync),
) -> std::result::Result<BlobDigest, StoreError> {
    let tree = match expression_to_tree(expression) {
        Ok(success) => success,
        Err(error) => return Err(StoreError::TreeSerializationError(error)),
    };
    storage.store_tree(&HashedTree::from(Arc::new(tree))).await
}

pub async fn serialize_recursively(
    expression: &DeepExpression,
    storage: &(dyn StoreTree + Sync),
) -> std::result::Result<BlobDigest, StoreError> {
    let shallow_expression: ShallowExpression = expression
        .0
        .map_child_expressions(&|child: &Arc<DeepExpression>| -> Pin<
            Box<dyn Future<Output = Result<BlobDigest, StoreError>>>,
        > {
            let child = child.clone();
            Box::pin(async move {
                serialize_recursively(&child, storage)
                    .await
            })
        },&|child: &DeepTree| -> Pin<
        Box<dyn Future<Output = Result<BlobDigest, StoreError>>>,
        > {
            let child = child.clone();
            Box::pin(async move {
                child.serialize(storage).await
            })
        })
        .await?;
    serialize_shallow(&shallow_expression, storage).await
}

#[derive(Debug)]
pub struct Closure {
    environment: BlobDigest,
    body: Arc<DeepExpression>,
}

#[derive(Debug, Serialize, Deserialize)]
pub struct ClosureBlob {}

impl Default for ClosureBlob {
    fn default() -> Self {
        Self::new()
    }
}

impl ClosureBlob {
    pub fn new() -> Self {
        Self {}
    }
}

impl Closure {
    pub fn new(environment: BlobDigest, body: Arc<DeepExpression>) -> Self {
        Self { environment, body }
    }

    pub async fn serialize(
        &self,
        store_tree: &(dyn StoreTree + Sync),
    ) -> Result<BlobDigest, StoreError> {
        let children = TreeChildren::try_from(vec![
            self.environment,
            serialize_recursively(&self.body, store_tree).await?,
        ])
        .expect("Two children always fit");
        let closure_blob = ClosureBlob::new();
        let closure_blob_bytes = postcard::to_allocvec(&closure_blob).unwrap(/*TODO*/);
        store_tree
            .store_tree(&HashedTree::from(Arc::new(Tree::new(
                TreeBlob::try_from(bytes::Bytes::from_owner(closure_blob_bytes)).unwrap(/*TODO*/),
                children,
            ))))
            .await
    }

    pub async fn deserialize(
        root: &BlobDigest,
        load_tree: &(dyn LoadTree + Sync),
    ) -> Result<Closure, TreeDeserializationError> {
        let loaded_root = match load_tree.load_tree(root).await {
            Some(success) => success,
            None => return Err(TreeDeserializationError::BlobUnavailable(*root)),
        };
        let root_tree = loaded_root.hash().unwrap(/*TODO*/).tree().clone();
        let _closure_blob: ClosureBlob = match postcard::from_bytes(root_tree.blob().as_slice()) {
            Ok(success) => success,
            Err(error) => return Err(TreeDeserializationError::Postcard(error)),
        };
        let environment_reference = &root_tree.children().references()[0];
        let body_reference = &root_tree.children().references()[1];
        let body = deserialize_recursively(body_reference, load_tree).await.unwrap(/*TODO*/);
        Ok(Closure::new(*environment_reference, Arc::new(body)))
    }
}

async fn call_method(
    body: &DeepExpression,
    argument: &BlobDigest,
    environment: &BlobDigest,
    load_tree: &(dyn LoadTree + Sync),
    store_tree: &(dyn StoreTree + Sync),
) -> std::result::Result<BlobDigest, StoreError> {
    Box::pin(evaluate(
        body,
        load_tree,
        store_tree,
        &Some(*argument),
        &Some(*environment),
    ))
    .await
}

pub type ReadVariable =
    dyn Fn(&Name) -> Pin<Box<dyn core::future::Future<Output = BlobDigest> + Send>> + Send + Sync;

pub async fn apply_evaluated_argument(
    callee: &DeepExpression,
    evaluated_argument: &BlobDigest,
    load_tree: &(dyn LoadTree + Sync),
    store_tree: &(dyn StoreTree + Sync),
    current_lambda_argument: &Option<BlobDigest>,
    current_lambda_environment: &Option<BlobDigest>,
) -> std::result::Result<BlobDigest, StoreError> {
    let evaluated_callee = Box::pin(evaluate(
        callee,
        load_tree,
        store_tree,
        current_lambda_argument,
        current_lambda_environment,
    ))
    .await?;
    let closure = match Closure::deserialize(&evaluated_callee, load_tree).await {
        Ok(success) => success,
        Err(_) => todo!(),
    };
    call_method(
        &closure.body,
        evaluated_argument,
        &closure.environment,
        load_tree,
        store_tree,
    )
    .await
}

pub async fn evaluate_apply(
    callee: &DeepExpression,
    argument: &DeepExpression,
    load_tree: &(dyn LoadTree + Sync),
    store_tree: &(dyn StoreTree + Sync),
    current_lambda_argument: &Option<BlobDigest>,
    current_lambda_environment: &Option<BlobDigest>,
) -> std::result::Result<BlobDigest, StoreError> {
    let evaluated_argument = Box::pin(evaluate(
        argument,
        load_tree,
        store_tree,
        current_lambda_argument,
        current_lambda_environment,
    ))
    .await?;
    apply_evaluated_argument(
        callee,
        &evaluated_argument,
        load_tree,
        store_tree,
        current_lambda_argument,
        current_lambda_environment,
    )
    .await
}

pub async fn evaluate(
    expression: &DeepExpression,
    load_tree: &(dyn LoadTree + Sync),
    store_tree: &(dyn StoreTree + Sync),
    current_lambda_argument: &Option<BlobDigest>,
    current_lambda_environment: &Option<BlobDigest>,
) -> std::result::Result<BlobDigest, StoreError> {
    match &expression.0 {
        Expression::Literal(literal_value) => literal_value.serialize(store_tree).await,
        Expression::Apply { callee, argument } => {
            evaluate_apply(
                callee,
                argument,
                load_tree,
                store_tree,
                current_lambda_argument,
                current_lambda_environment,
            )
            .await
        }
        Expression::Argument => {
            if let Some(argument) = current_lambda_argument {
                Ok(*argument)
            } else {
                todo!("We are not in a lambda context; argument is not available")
            }
        }
        Expression::Environment => {
            if let Some(environment) = current_lambda_environment {
                Ok(*environment)
            } else {
                todo!("We are not in a lambda context; environment is not available")
            }
        }
        Expression::Lambda { environment, body } => {
            let evaluated_environment = Box::pin(evaluate(
                environment,
                load_tree,
                store_tree,
                current_lambda_argument,
                current_lambda_environment,
            ))
            .await?;
            let closure = Closure::new(evaluated_environment, body.clone());
            let serialized = closure.serialize(store_tree).await?;
            Ok(serialized)
        }
        Expression::ConstructTree(arguments) => {
            let mut evaluated_arguments = Vec::new();
            for argument in arguments {
                let evaluated_argument = Box::pin(evaluate(
                    argument,
                    load_tree,
                    store_tree,
                    current_lambda_argument,
                    current_lambda_environment,
                ))
                .await?;
                evaluated_arguments.push(evaluated_argument);
            }
            let children = match TreeChildren::try_from(evaluated_arguments) {
                Some(success) => success,
                None => {
                    return Err(StoreError::TreeSerializationError(
                        TreeSerializationError::TooManyChildren,
                    ))
                }
            };
            store_tree
                .store_tree(&HashedTree::from(Arc::new(Tree::new(
                    TreeBlob::empty(),
                    children,
                ))))
                .await
        }
        Expression::GetChild { parent, index } => {
            let evaluated_parent = Box::pin(evaluate(
                parent,
                load_tree,
                store_tree,
                current_lambda_argument,
                current_lambda_environment,
            ))
            .await?;
            let loaded_parent = load_tree.load_tree(&evaluated_parent).await.unwrap(/*TODO*/);
            let hashed_tree = loaded_parent
                .hash()
                .unwrap(/*TODO*/);
            let child = hashed_tree
                .tree()
                .children()
                .references()
                .get(*index as usize)
                .expect("TODO handle out of range error");
            Ok(*child)
        }
    }
}

1	use crate::name::Name;
2	use astraea::deep_tree::DeepTree;
3	use astraea::tree::{
4	BlobDigest, HashedTree, ReferenceIndex, Tree, TreeChildren, TreeDeserializationError,
5	TreeSerializationError,
6	};
7	use astraea::{
8	storage::{LoadTree, StoreError, StoreTree},
9	tree::TreeBlob,
10	};
11	use serde::{Deserialize, Serialize};
12	use std::fmt::Display;
13	use std::future::Future;
14	use std::hash::Hash;
15	use std::{pin::Pin, sync::Arc};
16
17	pub trait PrintExpression {
18	fn print(&self, writer: &mut dyn std::fmt::Write, level: usize) -> std::fmt::Result;
19	}
20
21	#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Hash, Clone, Serialize, Deserialize)]
22	pub enum Expression<E, TreeLike>
23	where
24	E: Clone + Display + PrintExpression,
25	TreeLike: Clone + std::fmt::Debug,
26	{
27	Literal(TreeLike),
28	Apply { callee: E, argument: E },
29	Argument,
30	Environment,
31	Lambda { environment: E, body: E },
32	ConstructTree(Vec<E>),
33	GetChild { parent: E, index: u16 },
34	}
35
36	impl<E, V> PrintExpression for Expression<E, V>
37	where
38	E: Clone + Display + PrintExpression,
39	V: Clone + std::fmt::Debug,
40	{
41	fn print(&self, writer: &mut dyn std::fmt::Write, level: usize) -> std::fmt::Result {	19✔
42	match self {	19✔
43	Expression::Literal(literal_value) => {	8✔
44	write!(writer, "literal({literal_value:?})")	16✔
45	}
46	Expression::Apply { callee, argument } => {	2✔
47	callee.print(writer, level)?;	4✔
48	write!(writer, "(")?;	2✔
49	argument.print(writer, level)?;	4✔
50	write!(writer, ")")	2✔
51	}
52	Expression::Argument => {	×
53	write!(writer, "$arg")	2✔
54	}
55	Expression::Environment => {	×
56	write!(writer, "$env")	4✔
57	}
58	Expression::Lambda { environment, body } => {	8✔
59	write!(writer, "$env={{")?;	8✔
60	let indented = level + 1;	8✔
61	environment.print(writer, indented)?;	16✔
62	writeln!(writer, "}}($arg) =>")?;	8✔
63	for _ in 0..(indented * 2) {	4✔
64	write!(writer, " ")?;	20✔
65	}
66	body.print(writer, indented)	16✔
67	}
68	Expression::ConstructTree(arguments) => {	3✔
69	write!(writer, "[")?;	6✔
70	for argument in arguments {	8✔
71	argument.print(writer, level)?;	20✔
72	write!(writer, ", ")?;	10✔
73	}
74	write!(writer, "]")	6✔
75	}
76	Expression::GetChild { parent, index } => {	×
77	parent.print(writer, level)?;	×
78	write!(writer, ".{index}")	×
79	}
80	}
81	}
82	}
83
84	impl<E, TreeLike> Expression<E, TreeLike>
85	where
86	E: Clone + Display + PrintExpression,
87	TreeLike: Clone + std::fmt::Debug,
88	{
89	pub fn make_literal(value: TreeLike) -> Self {	54✔
90	Expression::Literal(value)	54✔
91	}
92
93	pub fn make_apply(callee: E, argument: E) -> Self {	23✔
94	Expression::Apply { callee, argument }
95	}
96
97	pub fn make_argument() -> Self {	91✔
98	Expression::Argument	91✔
99	}
100
101	pub fn make_environment() -> Self {	49✔
102	Expression::Environment	49✔
103	}
104
105	pub fn make_lambda(environment: E, body: E) -> Self {	25✔
106	Expression::Lambda { environment, body }
107	}
108
109	pub fn make_construct_tree(arguments: Vec<E>) -> Self {	128✔
110	Expression::ConstructTree(arguments)	128✔
111	}
112
113	pub fn make_get_child(parent: E, index: u16) -> Self {	70✔
114	Expression::GetChild { parent, index }
115	}
116
117	pub async fn map_child_expressions<	1,715✔
118	't,
119	Expr: Clone + Display + PrintExpression,
120	TreeLike2: Clone + std::fmt::Debug,
121	Error,
122	F,
123	G,
124	>(
125	&self,
126	transform_expression: &'t F,
127	transform_tree: &'t G,
128	) -> Result<Expression<Expr, TreeLike2>, Error>
129	where
130	F: Fn(&E) -> Pin<Box<dyn Future<Output = Result<Expr, Error>> + 't>>,
131	G: Fn(&TreeLike) -> Pin<Box<dyn Future<Output = Result<TreeLike2, Error>> + 't>>,
132	{
133	match self {	1,715✔
134	Expression::Literal(value) => Ok(Expression::Literal(transform_tree(value).await?)),	384✔
135	Expression::Apply { callee, argument } => Ok(Expression::Apply {	468✔
136	callee: transform_expression(callee).await?,	234✔
137	argument: transform_expression(argument).await?,	234✔
138	}),
139	Expression::Argument => Ok(Expression::Argument),	291✔
140	Expression::Environment => Ok(Expression::Environment),	136✔
141	Expression::Lambda { environment, body } => Ok(Expression::Lambda {	456✔
142	environment: transform_expression(environment).await?,	228✔
143	body: transform_expression(body).await?,	228✔
144	}),
145	Expression::ConstructTree(items) => {	361✔
146	let mut transformed_items = Vec::new();	722✔
147	for item in items.iter() {	773✔
148	transformed_items.push(transform_expression(item).await?);	1,236✔
149	}
150	Ok(Expression::ConstructTree(transformed_items))	361✔
151	}
152	Expression::GetChild { parent, index } => Ok(Expression::GetChild {	546✔
153	parent: transform_expression(parent).await?,	273✔
154	index: *index,	273✔
155	}),
156	}
157	}
158	}
159
160	impl<E, V> Display for Expression<E, V>
161	where
162	E: Clone + Display + PrintExpression,
163	V: Clone + std::fmt::Debug,
164	{
165	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {	×
166	self.print(f, 0)	×
167	}
168	}
169
170	#[derive(Debug, PartialEq, Eq, Ord, PartialOrd, Clone)]
171	pub struct DeepExpression(pub Expression<Arc<DeepExpression>, DeepTree>);
172
173	impl PrintExpression for DeepExpression {
174	fn print(&self, writer: &mut dyn std::fmt::Write, level: usize) -> std::fmt::Result {	1✔
175	self.0.print(writer, level)	4✔
176	}
177	}
178
179	impl PrintExpression for Arc<DeepExpression> {
180	fn print(&self, writer: &mut dyn std::fmt::Write, level: usize) -> std::fmt::Result {	15✔
181	self.0.print(writer, level)	60✔
182	}
183	}
184
185	impl Display for DeepExpression {
186	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {	×
187	write!(f, "{}", self.0)	×
188	}
189	}
190
191	pub type ShallowExpression = Expression<BlobDigest, BlobDigest>;
192
193	impl PrintExpression for BlobDigest {
194	fn print(&self, writer: &mut dyn std::fmt::Write, _level: usize) -> std::fmt::Result {	1✔
195	write!(writer, "{self}")	2✔
196	}
197	}
198
199	pub type ReferenceExpression = Expression<ReferenceIndex, ReferenceIndex>;
200
201	impl PrintExpression for ReferenceIndex {
202	fn print(&self, writer: &mut dyn std::fmt::Write, _level: usize) -> std::fmt::Result {	1✔
203	write!(writer, "{self}")	2✔
204	}
205	}
206
207	pub fn to_reference_expression(	574✔
208	expression: &ShallowExpression,
209	) -> (ReferenceExpression, Vec<BlobDigest>) {
210	match expression {	574✔
211	Expression::Literal(value) => (	128✔
212	ReferenceExpression::Literal(ReferenceIndex(0)),	128✔
213	vec![*value],	64✔
214	),
215	Expression::Apply { callee, argument } => (	234✔
216	ReferenceExpression::Apply {	156✔
217	callee: ReferenceIndex(0),	156✔
218	argument: ReferenceIndex(1),	156✔
219	},
220	// TODO: deduplicate?
221	vec![callee, argument],	156✔
222	),
223	Expression::Argument => (ReferenceExpression::Argument, vec![]),	98✔
224	Expression::Environment => (ReferenceExpression::Environment, vec![]),	46✔
225	Expression::Lambda { environment, body } => (	228✔
226	ReferenceExpression::Lambda {	152✔
227	environment: ReferenceIndex(0),	152✔
228	body: ReferenceIndex(1),	152✔
229	},
230	vec![environment, body],	152✔
231	),
232	Expression::ConstructTree(items) => (	121✔
233	ReferenceExpression::ConstructTree(
234	(0..items.len())	121✔
235	.map(\|index\| ReferenceIndex(index as u64))	259✔
236	.collect(),	121✔
237	),
238	// TODO: deduplicate?
239	items.clone(),	242✔
240	),
241	Expression::GetChild { parent, index } => (	273✔
242	ReferenceExpression::GetChild {	182✔
243	parent: ReferenceIndex(0),	182✔
244	index: *index,	182✔
245	},
246	vec![*parent],	91✔
247	),
248	}
249	}
250
251	pub async fn deserialize_shallow(tree: &Tree) -> Result<ShallowExpression, ()> {	1,142✔
252	let reference_expression: ReferenceExpression = postcard::from_bytes(tree.blob().as_slice())	2,284✔
253	.unwrap(/TODO/);
254	reference_expression	571✔
255	.map_child_expressions(
256	&\|child: &ReferenceIndex\| -> Pin<Box<dyn Future<Output = Result<BlobDigest, ()>>>> {	536✔
257	let child = tree.children().references()[child.0 as usize];	1,608✔
258	Box::pin(async move { Ok(child) })	2,144✔
259	},
260	&\|child: &ReferenceIndex\| -> Pin<Box<dyn Future<Output = Result<BlobDigest, ()>>>> {	64✔
261	let child = tree.children().references()[child.0 as usize];	192✔
262	Box::pin(async move { Ok(child) })	256✔
263	},
264	)
265	.await	571✔
266	}
267
268	pub async fn deserialize_recursively(	571✔
269	root: &BlobDigest,
270	load_tree: &(dyn LoadTree + Sync),
271	) -> Result<DeepExpression, ()> {
272	let root_loaded = load_tree.load_tree(root).await.unwrap(/TODO/).hash().unwrap(/TODO/);	3,997✔
273	let shallow = deserialize_shallow(root_loaded.tree()).await?;	1,713✔
274	let deep = shallow	1,142✔
275	.map_child_expressions(
276	&\|child: &BlobDigest\| -> Pin<Box<dyn Future<Output = Result<Arc<DeepExpression>, ()>>>> {	536✔
277	let child = *child;	1,072✔
278	Box::pin(async move { deserialize_recursively(&child, load_tree)	2,680✔
279	.await	536✔
280	.map(Arc::new) })	1,072✔
281	},
282	&\|child: &BlobDigest\| -> Pin<Box<dyn Future<Output = Result<DeepTree, ()>>>> {	64✔
283	let child = *child;	128✔
284	Box::pin(async move { Ok(DeepTree::deserialize(&child, load_tree).await.unwrap(/TODO/)) })	448✔
285	},
286	)
287	.await?;	571✔
288	Ok(DeepExpression(deep))	571✔
289	}
290
291	pub fn expression_to_tree(expression: &ShallowExpression) -> Result<Tree, TreeSerializationError> {	573✔
292	let (reference_expression, references) = to_reference_expression(expression);	1,719✔
293	let children = match TreeChildren::try_from(references) {	1,146✔
294	Some(success) => success,	1,146✔
NEW 295	None => return Err(TreeSerializationError::TooManyChildren),	×
296	};
297	let blob = postcard::to_allocvec(&reference_expression).unwrap(/TODO/);	2,292✔
298	Ok(Tree::new(	1,146✔
299	TreeBlob::try_from(bytes::Bytes::from_owner(blob)).unwrap(/TODO/),	2,292✔
300	children,	573✔
301	))
302	}
303
304	pub async fn serialize_shallow(	573✔
305	expression: &ShallowExpression,
306	storage: &(dyn StoreTree + Sync),
307	) -> std::result::Result<BlobDigest, StoreError> {
308	let tree = match expression_to_tree(expression) {	1,146✔
309	Ok(success) => success,	1,146✔
NEW 310	Err(error) => return Err(StoreError::TreeSerializationError(error)),	×
311	};
312	storage.store_tree(&HashedTree::from(Arc::new(tree))).await	2,292✔
313	}
314
315	pub async fn serialize_recursively(	573✔
316	expression: &DeepExpression,
317	storage: &(dyn StoreTree + Sync),
318	) -> std::result::Result<BlobDigest, StoreError> {
319	let shallow_expression: ShallowExpression = expression	1,719✔
320	.0	573✔
321	.map_child_expressions(&\|child: &Arc<DeepExpression>\| -> Pin<	573✔
322	Box<dyn Future<Output = Result<BlobDigest, StoreError>>>,
323	> {	537✔
324	let child = child.clone();	1,611✔
325	Box::pin(async move {	1,074✔
326	serialize_recursively(&child, storage)	1,611✔
327	.await	537✔
328	})
329	},&\|child: &DeepTree\| -> Pin<	537✔
330	Box<dyn Future<Output = Result<BlobDigest, StoreError>>>,
331	> {	64✔
332	let child = child.clone();	192✔
333	Box::pin(async move {	128✔
334	child.serialize(storage).await	192✔
335	})
336	})
337	.await?;	573✔
338	serialize_shallow(&shallow_expression, storage).await	1,719✔
339	}
340
341	#[derive(Debug)]
342	pub struct Closure {
343	environment: BlobDigest,
344	body: Arc<DeepExpression>,
345	}
346
347	#[derive(Debug, Serialize, Deserialize)]
348	pub struct ClosureBlob {}
349
350	impl Default for ClosureBlob {
351	fn default() -> Self {	×
352	Self::new()	×
353	}
354	}
355
356	impl ClosureBlob {
357	pub fn new() -> Self {	35✔
358	Self {}
359	}
360	}
361
362	impl Closure {
363	pub fn new(environment: BlobDigest, body: Arc<DeepExpression>) -> Self {	69✔
364	Self { environment, body }
365	}
366
367	pub async fn serialize(	35✔
368	&self,
369	store_tree: &(dyn StoreTree + Sync),
370	) -> Result<BlobDigest, StoreError> {
371	let children = TreeChildren::try_from(vec![	105✔
372	self.environment,	35✔
373	serialize_recursively(&self.body, store_tree).await?,	105✔
374	])
375	.expect("Two children always fit");
376	let closure_blob = ClosureBlob::new();	70✔
377	let closure_blob_bytes = postcard::to_allocvec(&closure_blob).unwrap(/TODO/);	140✔
378	store_tree	70✔
379	.store_tree(&HashedTree::from(Arc::new(Tree::new(	175✔
380	TreeBlob::try_from(bytes::Bytes::from_owner(closure_blob_bytes)).unwrap(/TODO/),	140✔
381	children,	35✔
382	))))
383	.await	35✔
384	}
385
386	pub async fn deserialize(	34✔
387	root: &BlobDigest,
388	load_tree: &(dyn LoadTree + Sync),
389	) -> Result<Closure, TreeDeserializationError> {
390	let loaded_root = match load_tree.load_tree(root).await {	170✔
391	Some(success) => success,	68✔
392	None => return Err(TreeDeserializationError::BlobUnavailable(*root)),	×
393	};
394	let root_tree = loaded_root.hash().unwrap(/TODO/).tree().clone();	136✔
395	let _closure_blob: ClosureBlob = match postcard::from_bytes(root_tree.blob().as_slice()) {	136✔
396	Ok(success) => success,	68✔
397	Err(error) => return Err(TreeDeserializationError::Postcard(error)),	×
398	};
399	let environment_reference = &root_tree.children().references()[0];	102✔
400	let body_reference = &root_tree.children().references()[1];	102✔
401	let body = deserialize_recursively(body_reference, load_tree).await.unwrap(/TODO/);	170✔
402	Ok(Closure::new(*environment_reference, Arc::new(body)))	102✔
403	}
404	}
405
406	async fn call_method(	34✔
407	body: &DeepExpression,
408	argument: &BlobDigest,
409	environment: &BlobDigest,
410	load_tree: &(dyn LoadTree + Sync),
411	store_tree: &(dyn StoreTree + Sync),
412	) -> std::result::Result<BlobDigest, StoreError> {
413	Box::pin(evaluate(	102✔
414	body,	68✔
415	load_tree,	68✔
416	store_tree,	68✔
417	&Some(*argument),	68✔
418	&Some(*environment),	34✔
419	))
420	.await	34✔
421	}
422
423	pub type ReadVariable =
424	dyn Fn(&Name) -> Pin<Box<dyn core::future::Future<Output = BlobDigest> + Send>> + Send + Sync;
425
426	pub async fn apply_evaluated_argument(	34✔
427	callee: &DeepExpression,
428	evaluated_argument: &BlobDigest,
429	load_tree: &(dyn LoadTree + Sync),
430	store_tree: &(dyn StoreTree + Sync),
431	current_lambda_argument: &Option<BlobDigest>,
432	current_lambda_environment: &Option<BlobDigest>,
433	) -> std::result::Result<BlobDigest, StoreError> {
434	let evaluated_callee = Box::pin(evaluate(	136✔
435	callee,	68✔
436	load_tree,	68✔
437	store_tree,	68✔
438	current_lambda_argument,	68✔
439	current_lambda_environment,	34✔
440	))
441	.await?;	34✔
442	let closure = match Closure::deserialize(&evaluated_callee, load_tree).await {	170✔
443	Ok(success) => success,	68✔
444	Err(_) => todo!(),
445	};
446	call_method(
447	&closure.body,	68✔
448	evaluated_argument,	68✔
449	&closure.environment,	68✔
450	load_tree,	68✔
451	store_tree,	34✔
452	)
453	.await	34✔
454	}
455
456	pub async fn evaluate_apply(	28✔
457	callee: &DeepExpression,
458	argument: &DeepExpression,
459	load_tree: &(dyn LoadTree + Sync),
460	store_tree: &(dyn StoreTree + Sync),
461	current_lambda_argument: &Option<BlobDigest>,
462	current_lambda_environment: &Option<BlobDigest>,
463	) -> std::result::Result<BlobDigest, StoreError> {
464	let evaluated_argument = Box::pin(evaluate(	112✔
465	argument,	56✔
466	load_tree,	56✔
467	store_tree,	56✔
468	current_lambda_argument,	56✔
469	current_lambda_environment,	28✔
470	))
471	.await?;	28✔
472	apply_evaluated_argument(
473	callee,	56✔
474	&evaluated_argument,	56✔
475	load_tree,	56✔
476	store_tree,	56✔
477	current_lambda_argument,	56✔
478	current_lambda_environment,	28✔
479	)
480	.await	28✔
481	}
482
483	pub async fn evaluate(	191✔
484	expression: &DeepExpression,
485	load_tree: &(dyn LoadTree + Sync),
486	store_tree: &(dyn StoreTree + Sync),
487	current_lambda_argument: &Option<BlobDigest>,
488	current_lambda_environment: &Option<BlobDigest>,
489	) -> std::result::Result<BlobDigest, StoreError> {
490	match &expression.0 {	191✔
491	Expression::Literal(literal_value) => literal_value.serialize(store_tree).await,	132✔
492	Expression::Apply { callee, argument } => {	56✔
493	evaluate_apply(
494	callee,	56✔
495	argument,	56✔
496	load_tree,	56✔
497	store_tree,	56✔
498	current_lambda_argument,	56✔
499	current_lambda_environment,	28✔
500	)
501	.await	28✔
502	}
503	Expression::Argument => {
504	if let Some(argument) = current_lambda_argument {	44✔
505	Ok(*argument)	22✔
506	} else {
507	todo!("We are not in a lambda context; argument is not available")
508	}
509	}
510	Expression::Environment => {
511	if let Some(environment) = current_lambda_environment {	16✔
512	Ok(*environment)	8✔
513	} else {
514	todo!("We are not in a lambda context; environment is not available")
515	}
516	}
517	Expression::Lambda { environment, body } => {	70✔
518	let evaluated_environment = Box::pin(evaluate(	140✔
519	environment,	70✔
520	load_tree,	70✔
521	store_tree,	70✔
522	current_lambda_argument,	70✔
523	current_lambda_environment,	35✔
524	))
525	.await?;	35✔
526	let closure = Closure::new(evaluated_environment, body.clone());	175✔
527	let serialized = closure.serialize(store_tree).await?;	140✔
528	Ok(serialized)	35✔
529	}
530	Expression::ConstructTree(arguments) => {	45✔
531	let mut evaluated_arguments = Vec::new();	90✔
532	for argument in arguments {	80✔
533	let evaluated_argument = Box::pin(evaluate(	140✔
534	argument,	70✔
535	load_tree,	70✔
536	store_tree,	70✔
537	current_lambda_argument,	70✔
538	current_lambda_environment,	35✔
539	))
540	.await?;	35✔
541	evaluated_arguments.push(evaluated_argument);	105✔
542	}
543	let children = match TreeChildren::try_from(evaluated_arguments) {	90✔
544	Some(success) => success,	90✔
545	None => {
NEW 546	return Err(StoreError::TreeSerializationError(	×
NEW 547	TreeSerializationError::TooManyChildren,	×
548	))
549	}
550	};
551	store_tree	90✔
552	.store_tree(&HashedTree::from(Arc::new(Tree::new(	225✔
553	TreeBlob::empty(),	45✔
554	children,	45✔
555	))))
556	.await	45✔
557	}
558	Expression::GetChild { parent, index } => {	40✔
559	let evaluated_parent = Box::pin(evaluate(	80✔
560	parent,	40✔
561	load_tree,	40✔
562	store_tree,	40✔
563	current_lambda_argument,	40✔
564	current_lambda_environment,	20✔
565	))
566	.await?;	20✔
567	let loaded_parent = load_tree.load_tree(&evaluated_parent).await.unwrap(/TODO/);	100✔
568	let hashed_tree = loaded_parent	40✔
569	.hash()
570	.unwrap(/TODO/);
571	let child = hashed_tree	40✔
572	.tree()
573	.children()
574	.references()
575	.get(*index as usize)	40✔
576	.expect("TODO handle out of range error");
577	Ok(*child)	20✔
578	}
579	}
580	}

TyRoXx / NonlocalityOS / 20205683691

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