14778271446

Committed 01 May 2025 03:38PM UTC coverage: 76.387% (-1.9%) from 78.257%

Build # 14778271446

Build Type

Pull #225

github

Committed by

web-flow

Commit Message

Merge 49a625bd4 into 824c46b00

Pull Request Pull Request #225: Update GitHub Actions runner to Ubuntu 24.04

Run Details

3966 of 5192 relevant lines covered (76.39%)

1812.35 hits per line

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

86.35

/lambda/src/expressions.rs

use crate::name::Name;
use astraea::tree::{BlobDigest, HashedValue, ReferenceIndex, Value, ValueDeserializationError};
use astraea::{
    storage::{LoadValue, StoreError, StoreValue},
    tree::ValueBlob,
};
use serde::{Deserialize, Serialize};
use std::fmt::Display;
use std::future::Future;
use std::hash::Hash;
use std::{
    collections::{BTreeMap, BTreeSet},
    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, V>
where
    E: Clone + Display + PrintExpression,
    V: Clone + Display,
{
    Literal(V),
    Apply { callee: E, argument: E },
    ReadVariable(Name),
    Lambda { parameter_name: Name, body: E },
    Construct(Vec<E>),
}

impl<E, V> PrintExpression for Expression<E, V>
where
    E: Clone + Display + PrintExpression,
    V: Clone + Display,
{
    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::ReadVariable(name) => {
                write!(writer, "{}", &name.key)
            }
            Expression::Lambda {
                parameter_name,
                body,
            } => {
                write!(writer, "({}) =>\n", parameter_name)?;
                let indented = level + 1;
                for _ in 0..(indented * 2) {
                    write!(writer, " ")?;
                }
                body.print(writer, indented)
            }
            Expression::Construct(arguments) => {
                write!(writer, "construct(")?;
                for argument in arguments {
                    argument.print(writer, level)?;
                    write!(writer, ", ")?;
                }
                write!(writer, ")")
            }
        }
    }
}

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

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

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

    pub fn make_construct(arguments: Vec<E>) -> Self {
        Expression::Construct(arguments)
    }

    pub fn make_read_variable(name: Name) -> Self {
        Expression::ReadVariable(name)
    }

    pub async fn map_child_expressions<
        't,
        Expr: Clone + Display + PrintExpression,
        V2: Clone + Display,
        Error,
        F,
        G,
    >(
        &self,
        transform_expression: &'t F,
        transform_value: &'t G,
    ) -> Result<Expression<Expr, V2>, Error>
    where
        F: Fn(&E) -> Pin<Box<dyn Future<Output = Result<Expr, Error>> + 't>>,
        G: Fn(&V) -> Pin<Box<dyn Future<Output = Result<V2, Error>> + 't>>,
    {
        match self {
            Expression::Literal(value) => Ok(Expression::Literal(transform_value(value).await?)),
            Expression::Apply { callee, argument } => Ok(Expression::Apply {
                callee: transform_expression(callee).await?,
                argument: transform_expression(argument).await?,
            }),
            Expression::ReadVariable(name) => Ok(Expression::ReadVariable(name.clone())),
            Expression::Lambda {
                parameter_name,
                body,
            } => Ok(Expression::Lambda {
                parameter_name: parameter_name.clone(),
                body: transform_expression(body).await?,
            }),
            Expression::Construct(items) => {
                let mut transformed_items = Vec::new();
                for item in items.iter() {
                    transformed_items.push(transform_expression(item).await?);
                }
                Ok(Expression::Construct(transformed_items))
            }
        }
    }
}

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

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

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::ReadVariable(name) => (ReferenceExpression::ReadVariable(name.clone()), vec![]),
        Expression::Lambda {
            parameter_name,
            body,
        } => (
            ReferenceExpression::Lambda {
                parameter_name: parameter_name.clone(),
                body: ReferenceIndex(0),
            },
            vec![*body],
        ),
        Expression::Construct(items) => (
            ReferenceExpression::Construct(
                (0..items.len())
                    .map(|index| ReferenceIndex(index as u64))
                    .collect(),
            ),
            // TODO: deduplicate?
            items.clone(),
        ),
    }
}

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

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

pub fn expression_to_value(expression: &ShallowExpression) -> Value {
    let (reference_expression, references) = to_reference_expression(expression);
    let blob = postcard::to_allocvec(&reference_expression).unwrap(/*TODO*/);
    Value::new(
        ValueBlob::try_from(bytes::Bytes::from_owner(blob)).unwrap(/*TODO*/),
        references,
    )
}

pub async fn serialize_shallow(
    expression: &ShallowExpression,
    storage: &(dyn StoreValue + Sync),
) -> std::result::Result<BlobDigest, StoreError> {
    let value = expression_to_value(expression);
    storage
        .store_value(&HashedValue::from(Arc::new(value)))
        .await
}

pub async fn serialize_recursively(
    expression: &DeepExpression,
    storage: &(dyn StoreValue + 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: &BlobDigest| -> Pin<
        Box<dyn Future<Output = Result<BlobDigest, StoreError>>>,
        > {
            let child = child.clone();
            Box::pin(async move {
                Ok(child)
            })
        })
        .await?;
    serialize_shallow(&shallow_expression, storage).await
}

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

#[derive(Debug, Serialize, Deserialize)]
pub struct ClosureBlob {
    parameter_name: Name,
    captured_variables: BTreeMap<Name, ReferenceIndex>,
}

impl ClosureBlob {
    pub fn new(parameter_name: Name, captured_variables: BTreeMap<Name, ReferenceIndex>) -> Self {
        Self {
            parameter_name,
            captured_variables,
        }
    }
}

impl Closure {
    pub fn new(
        parameter_name: Name,
        body: Arc<DeepExpression>,
        captured_variables: BTreeMap<Name, BlobDigest>,
    ) -> Self {
        Self {
            parameter_name,
            body,
            captured_variables,
        }
    }

    pub async fn serialize(
        &self,
        store_value: &(dyn StoreValue + Sync),
    ) -> Result<BlobDigest, StoreError> {
        let mut references = vec![serialize_recursively(&self.body, store_value).await?];
        let mut captured_variables = BTreeMap::new();
        for (name, reference) in self.captured_variables.iter() {
            let index = ReferenceIndex(references.len() as u64);
            captured_variables.insert(name.clone(), index);
            references.push(reference.clone());
        }
        let closure_blob = ClosureBlob::new(self.parameter_name.clone(), captured_variables);
        let closure_blob_bytes = postcard::to_allocvec(&closure_blob).unwrap(/*TODO*/);
        store_value
            .store_value(&HashedValue::from(Arc::new(Value::new(
                ValueBlob::try_from(bytes::Bytes::from_owner(closure_blob_bytes)).unwrap(/*TODO*/),
                references,
            ))))
            .await
    }

    pub async fn deserialize(
        root: &BlobDigest,
        load_value: &(dyn LoadValue + Sync),
    ) -> Result<Closure, ValueDeserializationError> {
        let loaded_root = match load_value.load_value(root).await {
            Some(success) => success,
            None => return Err(ValueDeserializationError::BlobUnavailable(root.clone())),
        };
        let root_value = loaded_root.hash().unwrap(/*TODO*/).value().clone();
        let closure_blob: ClosureBlob = match postcard::from_bytes(&root_value.blob().as_slice()) {
            Ok(success) => success,
            Err(error) => return Err(ValueDeserializationError::Postcard(error)),
        };
        let body_reference = &root_value.references()[0];
        let body = deserialize_recursively(body_reference, load_value).await.unwrap(/*TODO*/);
        let mut captured_variables = BTreeMap::new();
        for (name, index) in closure_blob.captured_variables {
            let reference = &root_value.references()[index.0 as usize];
            captured_variables.insert(name, reference.clone());
        }
        Ok(Closure::new(
            closure_blob.parameter_name,
            Arc::new(body),
            captured_variables,
        ))
    }
}

async fn call_method(
    parameter_name: &Name,
    captured_variables: &BTreeMap<Name, BlobDigest>,
    body: &DeepExpression,
    argument: &BlobDigest,
    load_value: &(dyn LoadValue + Sync),
    store_value: &(dyn StoreValue + Sync),
    read_variable: &Arc<ReadVariable>,
) -> std::result::Result<BlobDigest, StoreError> {
    let read_variable_in_body: Arc<ReadVariable> = Arc::new({
        let parameter_name = parameter_name.clone();
        let argument = argument.clone();
        let captured_variables = captured_variables.clone();
        let read_variable = read_variable.clone();
        move |name: &Name| -> Pin<Box<dyn core::future::Future<Output = BlobDigest> + Send>> {
            if name == &parameter_name {
                let argument = argument.clone();
                Box::pin(core::future::ready(argument))
            } else if let Some(found) = captured_variables.get(name) {
                Box::pin(core::future::ready(found.clone()))
            } else {
                read_variable(name)
            }
        }
    });
    Box::pin(evaluate(
        &body,
        load_value,
        store_value,
        &read_variable_in_body,
    ))
    .await
}

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

fn find_captured_names(expression: &DeepExpression) -> BTreeSet<Name> {
    match &expression.0 {
        Expression::Literal(_blob_digest) => BTreeSet::new(),
        Expression::Apply { callee, argument } => {
            let mut result = find_captured_names(callee);
            result.append(&mut find_captured_names(argument));
            result
        }
        Expression::ReadVariable(name) => BTreeSet::from([name.clone()]),
        Expression::Lambda {
            parameter_name,
            body,
        } => {
            let mut result = find_captured_names(body);
            result.remove(&parameter_name);
            result
        }
        Expression::Construct(arguments) => {
            let mut result = BTreeSet::new();
            for argument in arguments {
                result.append(&mut find_captured_names(argument));
            }
            result
        }
    }
}

pub async fn evaluate(
    expression: &DeepExpression,
    load_value: &(dyn LoadValue + Sync),
    store_value: &(dyn StoreValue + Sync),
    read_variable: &Arc<ReadVariable>,
) -> std::result::Result<BlobDigest, StoreError> {
    match &expression.0 {
        Expression::Literal(literal_value) => Ok(literal_value.clone()),
        Expression::Apply { callee, argument } => {
            let evaluated_callee =
                Box::pin(evaluate(callee, load_value, store_value, read_variable)).await?;
            let evaluated_argument =
                Box::pin(evaluate(argument, load_value, store_value, read_variable)).await?;
            let closure = match Closure::deserialize(&evaluated_callee, load_value).await {
                Ok(success) => success,
                Err(_) => todo!(),
            };
            call_method(
                &closure.parameter_name,
                &closure.captured_variables,
                &closure.body,
                &evaluated_argument,
                load_value,
                store_value,
                read_variable,
            )
            .await
        }
        Expression::ReadVariable(name) => Ok(read_variable(&name).await),
        Expression::Lambda {
            parameter_name,
            body,
        } => {
            let mut captured_variables = BTreeMap::new();
            for captured_name in find_captured_names(body).into_iter() {
                let captured_value = read_variable(&captured_name).await;
                captured_variables.insert(captured_name, captured_value);
            }
            let closure = Closure::new(parameter_name.clone(), body.clone(), captured_variables);
            let serialized = closure.serialize(store_value).await?;
            Ok(serialized)
        }
        Expression::Construct(arguments) => {
            let mut evaluated_arguments = Vec::new();
            for argument in arguments {
                let evaluated_argument =
                    Box::pin(evaluate(argument, load_value, store_value, read_variable)).await?;
                evaluated_arguments.push(evaluated_argument);
            }
            Ok(HashedValue::from(Arc::new(Value::new(
                ValueBlob::empty(),
                evaluated_arguments,
            )))
            .digest()
            .clone())
        }
    }
}

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

TyRoXx / NonlocalityOS / 14778271446

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