1use crate::dag::{InternalSharing, PostOrderIterItem};
4use crate::jet::Jet;
5use crate::types::{self, arrow::Arrow};
6use crate::{encode, BitIter, BitWriter, Cmr, FailEntropy, FinalizeError, RedeemNode, Value, Word};
7
8use std::io;
9use std::marker::PhantomData;
10use std::sync::Arc;
11
12use super::{
13 Commit, CommitData, CommitNode, Converter, Inner, Marker, NoDisconnect, NoWitness, Node,
14 Redeem, RedeemData,
15};
16use super::{CoreConstructible, DisconnectConstructible, JetConstructible, WitnessConstructible};
17
18#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
23pub enum ConstructId {}
24
25#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
26pub struct Construct<'brand, J> {
27 never: std::convert::Infallible,
29 phantom: std::marker::PhantomData<&'brand J>,
31}
32
33impl<'brand, J: Jet> Marker for Construct<'brand, J> {
34 type CachedData = ConstructData<'brand, J>;
35 type Witness = Option<Value>;
36 type Disconnect = Option<Arc<ConstructNode<'brand, J>>>;
37 type SharingId = ConstructId;
38 type Jet = J;
39
40 fn compute_sharing_id(_: Cmr, _: &ConstructData<J>) -> Option<ConstructId> {
41 None
42 }
43}
44
45pub type ConstructNode<'brand, J> = Node<Construct<'brand, J>>;
46
47impl<'brand, J: Jet> ConstructNode<'brand, J> {
48 pub fn arrow(&self) -> &Arrow<'brand> {
50 self.data.arrow()
51 }
52
53 pub fn set_arrow_to_program(&self) -> Result<(), types::Error> {
55 let ctx = self.data.inference_context();
56 let unit_ty = types::Type::unit(ctx);
57 ctx.unify(
58 &self.arrow().source,
59 &unit_ty,
60 "setting root source to unit",
61 )?;
62 ctx.unify(
63 &self.arrow().target,
64 &unit_ty,
65 "setting root target to unit",
66 )?;
67 Ok(())
68 }
69
70 pub fn finalize_types(&self) -> Result<Arc<CommitNode<J>>, types::Error> {
77 self.set_arrow_to_program()?;
78 self.finalize_types_non_program()
79 }
80
81 pub fn finalize_types_non_program(&self) -> Result<Arc<CommitNode<J>>, types::Error> {
85 struct FinalizeTypes<J: Jet>(PhantomData<J>);
86
87 impl<'brand, J: Jet> Converter<Construct<'brand, J>, Commit<J>> for FinalizeTypes<J> {
88 type Error = types::Error;
89
90 fn convert_witness(
91 &mut self,
92 _: &PostOrderIterItem<&ConstructNode<J>>,
93 _: &Option<Value>,
94 ) -> Result<NoWitness, Self::Error> {
95 Ok(NoWitness)
96 }
97
98 fn convert_disconnect(
99 &mut self,
100 _: &PostOrderIterItem<&ConstructNode<J>>,
101 _: Option<&Arc<CommitNode<J>>>,
102 _: &Option<Arc<ConstructNode<J>>>,
103 ) -> Result<NoDisconnect, Self::Error> {
104 Ok(NoDisconnect)
105 }
106
107 fn convert_data(
108 &mut self,
109 data: &PostOrderIterItem<&ConstructNode<J>>,
110 inner: Inner<&Arc<CommitNode<J>>, J, &NoDisconnect, &NoWitness>,
111 ) -> Result<Arc<CommitData<J>>, Self::Error> {
112 let converted_data = inner.map(|node| node.cached_data());
113 CommitData::new(&data.node.data.arrow, converted_data).map(Arc::new)
114 }
115 }
116
117 self.convert::<InternalSharing, _, _>(&mut FinalizeTypes(PhantomData))
118 }
119
120 pub fn finalize_unpruned(&self) -> Result<Arc<RedeemNode<J>>, FinalizeError> {
133 struct Finalizer<J>(PhantomData<J>);
134
135 impl<'brand, J: Jet> Converter<Construct<'brand, J>, Redeem<J>> for Finalizer<J> {
136 type Error = FinalizeError;
137
138 fn convert_witness(
139 &mut self,
140 data: &PostOrderIterItem<&ConstructNode<J>>,
141 wit: &Option<Value>,
142 ) -> Result<Value, Self::Error> {
143 if let Some(ref wit) = wit {
144 Ok(wit.shallow_clone())
145 } else {
146 let ty = data
162 .node
163 .arrow()
164 .target
165 .finalize()
166 .map_err(FinalizeError::Type)?;
167 Ok(Value::zero(&ty))
168 }
169 }
170
171 fn convert_disconnect(
172 &mut self,
173 _: &PostOrderIterItem<&ConstructNode<J>>,
174 maybe_converted: Option<&Arc<RedeemNode<J>>>,
175 _: &Option<Arc<ConstructNode<J>>>,
176 ) -> Result<Arc<RedeemNode<J>>, Self::Error> {
177 if let Some(child) = maybe_converted {
178 Ok(Arc::clone(child))
179 } else {
180 Err(FinalizeError::DisconnectRedeemTime)
181 }
182 }
183
184 fn convert_data(
185 &mut self,
186 data: &PostOrderIterItem<&ConstructNode<J>>,
187 inner: Inner<&Arc<RedeemNode<J>>, J, &Arc<RedeemNode<J>>, &Value>,
188 ) -> Result<Arc<RedeemData<J>>, Self::Error> {
189 let converted_data = inner
190 .map(|node| node.cached_data())
191 .map_disconnect(|node| node.cached_data())
192 .map_witness(Value::shallow_clone);
193 Ok(Arc::new(RedeemData::new(
194 data.node.arrow().finalize().map_err(FinalizeError::Type)?,
195 converted_data,
196 )))
197 }
198 }
199
200 self.convert::<InternalSharing, _, _>(&mut Finalizer(PhantomData))
201 }
202
203 pub fn finalize_pruned(
216 &self,
217 env: &J::Environment,
218 ) -> Result<Arc<RedeemNode<J>>, FinalizeError> {
219 let unpruned = self.finalize_unpruned()?;
220 unpruned.prune(env).map_err(FinalizeError::Execution)
221 }
222
223 pub fn decode<I: Iterator<Item = u8>>(
233 context: &types::Context<'brand>,
234 mut bits: BitIter<I>,
235 ) -> Result<Arc<Self>, crate::decode::Error> {
236 let res = crate::decode::decode_expression(context, &mut bits)?;
237 bits.close()?;
238 Ok(res)
239 }
240
241 #[cfg(feature = "base64")]
242 #[allow(clippy::should_implement_trait)] pub fn from_str(
244 context: &types::Context<'brand>,
245 s: &str,
246 ) -> Result<Arc<Self>, crate::ParseError> {
247 use crate::base64::engine::general_purpose;
248 use crate::base64::Engine as _;
249
250 let v = general_purpose::STANDARD
251 .decode(s)
252 .map_err(crate::ParseError::Base64)?;
253 let iter = crate::BitIter::new(v.into_iter());
254 Self::decode(context, iter)
255 .map_err(crate::DecodeError::Decode)
256 .map_err(crate::ParseError::Decode)
257 }
258
259 #[deprecated(since = "0.5.0", note = "use Self::encode_without_witness instead")]
261 pub fn encode<W: io::Write>(&self, w: &mut BitWriter<W>) -> io::Result<usize> {
262 let program_bits = encode::encode_program(self, w)?;
263 w.flush_all()?;
264 Ok(program_bits)
265 }
266}
267
268#[derive(Clone, Debug)]
269pub struct ConstructData<'brand, J> {
270 arrow: Arrow<'brand>,
271 phantom: PhantomData<J>,
275}
276
277impl<'brand, J: Jet> ConstructData<'brand, J> {
278 pub fn new(arrow: Arrow<'brand>) -> Self {
280 ConstructData {
281 arrow,
282 phantom: PhantomData,
283 }
284 }
285
286 pub fn arrow(&self) -> &Arrow<'brand> {
288 &self.arrow
289 }
290}
291
292impl<'brand, J> CoreConstructible<'brand> for ConstructData<'brand, J> {
293 fn iden(inference_context: &types::Context<'brand>) -> Self {
294 ConstructData {
295 arrow: Arrow::iden(inference_context),
296 phantom: PhantomData,
297 }
298 }
299
300 fn unit(inference_context: &types::Context<'brand>) -> Self {
301 ConstructData {
302 arrow: Arrow::unit(inference_context),
303 phantom: PhantomData,
304 }
305 }
306
307 fn injl(child: &Self) -> Self {
308 ConstructData {
309 arrow: Arrow::injl(&child.arrow),
310 phantom: PhantomData,
311 }
312 }
313
314 fn injr(child: &Self) -> Self {
315 ConstructData {
316 arrow: Arrow::injr(&child.arrow),
317 phantom: PhantomData,
318 }
319 }
320
321 fn take(child: &Self) -> Self {
322 ConstructData {
323 arrow: Arrow::take(&child.arrow),
324 phantom: PhantomData,
325 }
326 }
327
328 fn drop_(child: &Self) -> Self {
329 ConstructData {
330 arrow: Arrow::drop_(&child.arrow),
331 phantom: PhantomData,
332 }
333 }
334
335 fn comp(left: &Self, right: &Self) -> Result<Self, types::Error> {
336 Ok(ConstructData {
337 arrow: Arrow::comp(&left.arrow, &right.arrow)?,
338 phantom: PhantomData,
339 })
340 }
341
342 fn case(left: &Self, right: &Self) -> Result<Self, types::Error> {
343 Ok(ConstructData {
344 arrow: Arrow::case(&left.arrow, &right.arrow)?,
345 phantom: PhantomData,
346 })
347 }
348
349 fn assertl(left: &Self, right: Cmr) -> Result<Self, types::Error> {
350 Ok(ConstructData {
351 arrow: Arrow::assertl(&left.arrow, right)?,
352 phantom: PhantomData,
353 })
354 }
355
356 fn assertr(left: Cmr, right: &Self) -> Result<Self, types::Error> {
357 Ok(ConstructData {
358 arrow: Arrow::assertr(left, &right.arrow)?,
359 phantom: PhantomData,
360 })
361 }
362
363 fn pair(left: &Self, right: &Self) -> Result<Self, types::Error> {
364 Ok(ConstructData {
365 arrow: Arrow::pair(&left.arrow, &right.arrow)?,
366 phantom: PhantomData,
367 })
368 }
369
370 fn fail(inference_context: &types::Context<'brand>, entropy: FailEntropy) -> Self {
371 ConstructData {
372 arrow: Arrow::fail(inference_context, entropy),
373 phantom: PhantomData,
374 }
375 }
376
377 fn const_word(inference_context: &types::Context<'brand>, word: Word) -> Self {
378 ConstructData {
379 arrow: Arrow::const_word(inference_context, word),
380 phantom: PhantomData,
381 }
382 }
383
384 fn inference_context(&self) -> &types::Context<'brand> {
385 self.arrow.inference_context()
386 }
387}
388
389impl<'brand, J: Jet> DisconnectConstructible<'brand, Option<Arc<ConstructNode<'brand, J>>>>
390 for ConstructData<'brand, J>
391{
392 fn disconnect(
393 left: &Self,
394 right: &Option<Arc<ConstructNode<'brand, J>>>,
395 ) -> Result<Self, types::Error> {
396 let right = right.as_ref();
397 Ok(ConstructData {
398 arrow: Arrow::disconnect(&left.arrow, &right.map(|n| n.arrow()))?,
399 phantom: PhantomData,
400 })
401 }
402}
403
404impl<'brand, J> WitnessConstructible<'brand, Option<Value>> for ConstructData<'brand, J> {
405 fn witness(inference_context: &types::Context<'brand>, _witness: Option<Value>) -> Self {
406 ConstructData {
407 arrow: Arrow::witness(inference_context, NoWitness),
408 phantom: PhantomData,
409 }
410 }
411}
412
413impl<'brand, J: Jet> JetConstructible<'brand, J> for ConstructData<'brand, J> {
414 fn jet(inference_context: &types::Context<'brand>, jet: J) -> Self {
415 ConstructData {
416 arrow: Arrow::jet(inference_context, jet),
417 phantom: PhantomData,
418 }
419 }
420}
421
422#[cfg(test)]
423mod tests {
424 use super::*;
425 use crate::jet::Core;
426 use crate::types::Final;
427 use crate::Value;
428
429 #[test]
430 fn occurs_check_error() {
431 types::Context::with_context(|ctx| {
432 let iden = Arc::<ConstructNode<Core>>::iden(&ctx);
433 let node =
434 Arc::<ConstructNode<Core>>::disconnect(&iden, &Some(Arc::clone(&iden))).unwrap();
435
436 assert!(matches!(
437 node.finalize_types_non_program(),
438 Err(types::Error::OccursCheck { .. }),
439 ));
440 });
441 }
442
443 #[test]
444 fn occurs_check_2() {
445 types::Context::with_context(|ctx| {
446 let iden = Arc::<ConstructNode<Core>>::iden(&ctx);
448 let injr = Arc::<ConstructNode<Core>>::injr(&iden);
449 let pair = Arc::<ConstructNode<Core>>::pair(&injr, &iden).unwrap();
450 let drop = Arc::<ConstructNode<Core>>::drop_(&pair);
451
452 let case1 = Arc::<ConstructNode<Core>>::case(&drop, &drop).unwrap();
453 let case2 = Arc::<ConstructNode<Core>>::case(&case1, &case1).unwrap();
454
455 let comp1 = Arc::<ConstructNode<Core>>::comp(&case2, &case2).unwrap();
456 let comp2 = Arc::<ConstructNode<Core>>::comp(&comp1, &case1).unwrap();
457
458 assert!(matches!(
459 comp2.finalize_types_non_program(),
460 Err(types::Error::OccursCheck { .. }),
461 ));
462 });
463 }
464
465 #[test]
466 fn occurs_check_3() {
467 types::Context::with_context(|ctx| {
468 let wit = Arc::<ConstructNode<Core>>::witness(&ctx, None);
470 let drop = Arc::<ConstructNode<Core>>::drop_(&wit);
471
472 let comp1 = Arc::<ConstructNode<Core>>::comp(&drop, &drop).unwrap();
473 let comp2 = Arc::<ConstructNode<Core>>::comp(&comp1, &comp1).unwrap();
474 let comp3 = Arc::<ConstructNode<Core>>::comp(&comp2, &comp2).unwrap();
475 let comp4 = Arc::<ConstructNode<Core>>::comp(&comp3, &comp3).unwrap();
476 let comp5 = Arc::<ConstructNode<Core>>::comp(&comp4, &comp4).unwrap();
477
478 let case = Arc::<ConstructNode<Core>>::case(&comp5, &comp4).unwrap();
479 let drop2 = Arc::<ConstructNode<Core>>::drop_(&case);
480 let case2 = Arc::<ConstructNode<Core>>::case(&drop2, &case).unwrap();
481 let comp6 = Arc::<ConstructNode<Core>>::comp(&case2, &case2).unwrap();
482 let case3 = Arc::<ConstructNode<Core>>::case(&comp6, &comp6).unwrap();
483
484 let comp7 = Arc::<ConstructNode<Core>>::comp(&case3, &case3).unwrap();
485 let comp8 = Arc::<ConstructNode<Core>>::comp(&comp7, &comp7).unwrap();
486
487 assert!(matches!(
488 comp8.finalize_types_non_program(),
489 Err(types::Error::OccursCheck { .. }),
490 ));
491 });
492 }
493
494 #[test]
495 fn type_check_error() {
496 types::Context::with_context(|ctx| {
497 let unit = Arc::<ConstructNode<Core>>::unit(&ctx);
498 let case = Arc::<ConstructNode<Core>>::case(&unit, &unit).unwrap();
499
500 assert!(matches!(
501 Arc::<ConstructNode<Core>>::disconnect(&case, &Some(unit)),
502 Err(types::Error::Bind { .. }),
503 ));
504 });
505 }
506
507 #[test]
508 fn scribe() {
509 types::Context::with_context(|ctx| {
513 let unit = Arc::<ConstructNode<Core>>::unit(&ctx);
514 let bit0 = Arc::<ConstructNode<Core>>::const_word(&ctx, Word::u1(0));
515 let bit1 = Arc::<ConstructNode<Core>>::const_word(&ctx, Word::u1(1));
516
517 assert_eq!(
518 unit.cmr(),
519 Arc::<ConstructNode<Core>>::scribe(&ctx, &Value::unit()).cmr()
520 );
521 assert_eq!(
522 bit0.cmr(),
523 Arc::<ConstructNode<Core>>::scribe(&ctx, &Value::u1(0)).cmr()
524 );
525 assert_eq!(
526 bit1.cmr(),
527 Arc::<ConstructNode<Core>>::scribe(&ctx, &Value::u1(1)).cmr()
528 );
529 assert_eq!(
530 Arc::<ConstructNode<Core>>::const_word(&ctx, Word::u2(1)).cmr(),
531 Arc::<ConstructNode<Core>>::scribe(&ctx, &Value::u2(1)).cmr()
532 );
533 assert_eq!(
534 Arc::<ConstructNode<Core>>::injl(&bit0).cmr(),
535 Arc::<ConstructNode<Core>>::scribe(&ctx, &Value::left(Value::u1(0), Final::unit()))
536 .cmr()
537 );
538 assert_eq!(
539 Arc::<ConstructNode<Core>>::injr(&bit1).cmr(),
540 Arc::<ConstructNode<Core>>::scribe(
541 &ctx,
542 &Value::right(Final::unit(), Value::u1(1))
543 )
544 .cmr()
545 );
546 assert_eq!(
547 Arc::<ConstructNode<Core>>::pair(&unit, &unit)
548 .unwrap()
549 .cmr(),
550 Arc::<ConstructNode<Core>>::scribe(
551 &ctx,
552 &Value::product(Value::unit(), Value::unit())
553 )
554 .cmr()
555 );
556 });
557 }
558
559 #[test]
560 fn regression_286_1() {
561 types::Context::with_context(|ctx| {
564 let cmr = Cmr::from_byte_array([0xde; 32]);
565
566 let u0 = Arc::<ConstructNode<Core>>::unit(&ctx);
567 let i1 = Arc::<ConstructNode<Core>>::injl(&u0);
568 let i2 = Arc::<ConstructNode<Core>>::injr(&i1);
569 let i3 = Arc::<ConstructNode<Core>>::injr(&i2);
570 let i4 = Arc::<ConstructNode<Core>>::injl(&i3);
571 let u5 = Arc::<ConstructNode<Core>>::unit(&ctx);
572 let i6 = Arc::<ConstructNode<Core>>::injl(&u5);
573 let i7 = Arc::<ConstructNode<Core>>::injr(&i6);
574 let p8 = Arc::<ConstructNode<Core>>::pair(&i4, &i7).unwrap();
575 let u9 = Arc::<ConstructNode<Core>>::unit(&ctx);
576 let a10 = Arc::<ConstructNode<Core>>::assertr(cmr, &u9).unwrap();
577 let u11 = Arc::<ConstructNode<Core>>::unit(&ctx);
578 let a12 = Arc::<ConstructNode<Core>>::assertr(cmr, &u11).unwrap();
579 let a13 = Arc::<ConstructNode<Core>>::assertl(&a12, cmr).unwrap();
580 let c14 = Arc::<ConstructNode<Core>>::case(&a10, &a13).unwrap();
581 let c15 = Arc::<ConstructNode<Core>>::comp(&p8, &c14).unwrap();
582
583 let finalized: Arc<CommitNode<_>> = c15.finalize_types().unwrap();
584 let prog = finalized.to_vec_without_witness();
585 assert_eq!(
587 hex::DisplayHex::as_hex(&prog).to_string(),
588 "dc920a28812b6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f243090e00b10e00680",
589 );
590
591 let prog = BitIter::from(prog);
592 let decode = CommitNode::<Core>::decode(prog).unwrap();
593
594 assert_eq!(finalized, decode);
596 });
597 }
598
599 #[test]
600 fn regression_286_2() {
601 types::Context::with_context(|ctx| {
609 let w0 = Arc::<ConstructNode<Core>>::witness(&ctx, None);
610 let i1 = Arc::<ConstructNode<Core>>::iden(&ctx);
611 let d2 = Arc::<ConstructNode<Core>>::drop_(&i1);
612 let i3 = Arc::<ConstructNode<Core>>::iden(&ctx);
613 let i4 = Arc::<ConstructNode<Core>>::iden(&ctx);
614 let t5 = Arc::<ConstructNode<Core>>::take(&i4);
615 let ca6 = Arc::<ConstructNode<Core>>::case(&i3, &t5).unwrap();
616 let ca7 = Arc::<ConstructNode<Core>>::case(&d2, &ca6).unwrap();
617 let c8 = Arc::<ConstructNode<Core>>::comp(&w0, &ca7).unwrap();
618 let u9 = Arc::<ConstructNode<Core>>::unit(&ctx);
619 let c10 = Arc::<ConstructNode<Core>>::comp(&c8, &u9).unwrap();
620
621 let err = c10.finalize_types().unwrap_err();
623 assert!(matches!(err, types::Error::OccursCheck { .. }));
624 });
625 }
626}