20191186094

Committed 13 Dec 2025 11:07AM UTC coverage: 80.154% (-0.06%) from 80.214%

Build # 20191186094

Build Type

Pull #368

github

Committed by

web-flow

Commit Message

Merge 7123f0716 into 306950449

Pull Request Pull Request #368: Prolly tree polishing

Run Details

100 of 107 new or added lines in 12 files covered. (93.46%)

4 existing lines in 2 files now uncovered.

5396 of 6732 relevant lines covered (80.15%)

33555.01 hits per line

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

95.15

/lambda/src/expressions.rs

use crate::name::Name;
use astraea::deep_tree::DeepTree;
use astraea::tree::{BlobDigest, HashedTree, ReferenceIndex, Tree, TreeDeserializationError};
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.references()[child.0 as usize];
                Box::pin(async move { Ok(child) })
            },
            &|child: &ReferenceIndex| -> Pin<Box<dyn Future<Output = Result<BlobDigest, ()>>>> {
                let child = tree.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) -> Tree {
    let (reference_expression, references) = to_reference_expression(expression);
    let blob = postcard::to_allocvec(&reference_expression).unwrap(/*TODO*/);
    Tree::new(
        TreeBlob::try_from(bytes::Bytes::from_owner(blob)).unwrap(/*TODO*/),
        references,
    )
}

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

TyRoXx / NonlocalityOS / 20191186094

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