etk_dasm/blocks/
annotated.rs

1//! Representation of EVM instruction blocks as expressions applied to inputs
2//! (ie. stack/memory/storage).
3use crate::sym::{Expr, Var};
4
5use etk_ops::shanghai::*;
6
7use std::collections::VecDeque;
8
9use super::BasicBlock;
10
11/// Possible ways for an [`AnnotatedBlock`] to exit.
12#[derive(Debug, Clone)]
13pub enum Exit<T = Expr> {
14    /// Unconditional program halt.
15    ///
16    /// Includes `stop` (`0x00`), `return` (`0xF3`), `revert` (`0xfd`), etc.
17    Terminate,
18
19    /// Unconditionally continue to the subsequent block, which has the given
20    /// offset.
21    ///
22    /// Commonly occurs when the next block begins with a `jumpdest` (`0x5b`).
23    FallThrough(usize),
24
25    /// Unconditionally jump to the given offset.
26    Unconditional(T),
27
28    /// Conditionally jump to one of the given offsets.
29    Branch {
30        /// Expression that determines whether to fall through to the next block
31        /// or jump.
32        condition: T,
33
34        /// Offset to jump to if `condition` is truthy.
35        when_true: T,
36
37        /// Offset of block to fall through to if `condition` is not truthy.
38        when_false: usize,
39    },
40}
41
42impl<T> Exit<T> {
43    /// Get the offset of the fall through block, or `None` if this block can
44    /// never fall through.
45    ///
46    /// Both [`Exit::FallThrough`] and [`Exit::Branch`] have fall through
47    /// offsets.
48    pub fn fall_through(&self) -> Option<usize> {
49        match self {
50            Self::FallThrough(f) => Some(*f),
51            Self::Branch { when_false, .. } => Some(*when_false),
52            _ => None,
53        }
54    }
55
56    /// Return `true` if this block is an [`Exit::FallThrough`], or `false`
57    /// otherwise.
58    pub fn is_fall_through(&self) -> bool {
59        matches!(self, Self::FallThrough(_))
60    }
61
62    /// Return `true` if this block is an [`Exit::Terminate`], or `false`
63    /// otherwise.
64    pub fn is_terminate(&self) -> bool {
65        matches!(self, Self::Terminate)
66    }
67
68    /// Return `true` if this block is an [`Exit::Unconditional`], or `false`
69    /// otherwise.
70    pub fn is_unconditional(&self) -> bool {
71        matches!(self, Self::Unconditional(_))
72    }
73
74    /// Return `true` if this block is an [`Exit::Branch`], or `false`
75    /// otherwise.
76    pub fn is_branch(&self) -> bool {
77        matches!(self, Self::Branch { .. })
78    }
79}
80
81/// Represents values that are accessed during execution of an
82/// [`AnnotatedBlock`].
83#[derive(Debug, Clone)]
84#[non_exhaustive]
85pub struct Inputs {
86    /// Ordered list of inputs that are required to be on the EVM stack when
87    /// entering this block.
88    pub stack: Vec<Var>,
89}
90
91/// Represents values that are modified during execution of an
92/// [`AnnotatedBlock`].
93#[derive(Debug, Clone)]
94#[non_exhaustive]
95pub struct Outputs {
96    /// Ordered list of expressions pushed to the stack after exiting this
97    /// block.
98    pub stack: Vec<Expr>,
99}
100
101/// Represents a block of EVM instructions as a set of expressions.
102#[derive(Debug, Clone)]
103#[non_exhaustive]
104pub struct AnnotatedBlock {
105    /// Position of the first instruction in the block.
106    pub offset: usize,
107
108    /// Values which are accessed during execution of this block.
109    pub inputs: Inputs,
110
111    /// Values which are created/modified during execution of this block.
112    pub outputs: Outputs,
113
114    /// Describes how execution continues after the last instruction of this
115    /// block.
116    pub exit: Exit,
117
118    /// Whether this block begins with a `jumpdest` (`0x5b`).
119    pub jump_target: bool,
120
121    /// Length of this block.
122    pub size: usize,
123}
124
125impl AnnotatedBlock {
126    /// Construct an [`AnnotatedBlock`] from a [`BasicBlock`].
127    pub fn annotate(basic: &BasicBlock) -> Self {
128        let jump_target = basic
129            .ops
130            .get(0)
131            .map(Operation::is_jump_target)
132            .unwrap_or_default();
133
134        let mut annotator = Annotator::new(basic);
135        let exit = annotator.annotate();
136
137        let mut stacks = annotator.stacks.into_iter();
138        let stack_inputs = stacks
139            .next()
140            .unwrap()
141            .into_iter()
142            .map(|i| i.as_var().unwrap())
143            .collect();
144        let stack_outputs = stacks.last().unwrap();
145
146        Self {
147            jump_target,
148            size: basic.size(),
149            offset: basic.offset,
150            outputs: Outputs {
151                stack: stack_outputs.into(),
152            },
153            inputs: Inputs {
154                stack: stack_inputs,
155            },
156            exit,
157        }
158    }
159}
160
161struct StackWindow<'s> {
162    vars: &'s mut u16,
163    stacks: &'s mut Vec<VecDeque<Expr>>,
164    pops: usize,
165    pushes: usize,
166}
167
168impl<'s> Drop for StackWindow<'s> {
169    fn drop(&mut self) {
170        if !std::thread::panicking() {
171            assert_eq!(self.pops, 0);
172            assert_eq!(self.pushes, 0);
173        }
174    }
175}
176
177impl<'s> StackWindow<'s> {
178    fn new(vars: &'s mut u16, stacks: &'s mut Vec<VecDeque<Expr>>, op: &Op<[u8]>) -> Self {
179        Self {
180            vars,
181            stacks,
182            pops: op.pops(),
183            pushes: op.pushes(),
184        }
185    }
186
187    fn count_pops(&mut self, count: usize) {
188        assert!(self.pops >= count);
189        self.pops -= count;
190    }
191
192    fn count_pushes(&mut self, count: usize) {
193        assert_eq!(self.pops, 0);
194        assert!(self.pushes >= count);
195        self.pushes -= count;
196    }
197
198    fn expand_stack(&mut self, by: usize) {
199        for _ in 0..by {
200            *self.vars += 1;
201            let var = Var::with_id(*self.vars);
202            for stack in self.stacks.iter_mut() {
203                stack.push_back(var.into());
204            }
205        }
206    }
207
208    fn current_stack(&mut self) -> &mut VecDeque<Expr> {
209        self.stacks.last_mut().unwrap()
210    }
211
212    fn pop(&mut self) -> Expr {
213        self.count_pops(1);
214
215        if self.current_stack().is_empty() {
216            self.expand_stack(1);
217        }
218
219        self.current_stack().pop_front().unwrap()
220    }
221
222    fn peek(&mut self, depth: usize) -> &Expr {
223        // A peek is basically N pops followed by N pushes.
224        self.count_pops(depth + 1);
225        self.count_pushes(depth + 1);
226
227        let len = self.current_stack().len();
228        if len < depth + 1 {
229            self.expand_stack(1 + depth - len);
230        }
231
232        self.current_stack().get(depth).unwrap()
233    }
234
235    fn swap(&mut self, depth: usize) {
236        // A swap is basically N pops followed by N pushes.
237        self.count_pops(depth + 1);
238        self.count_pushes(depth + 1);
239
240        let len = self.current_stack().len();
241        if len < depth + 1 {
242            self.expand_stack(1 + depth - len);
243        }
244
245        let deep = self.current_stack().swap_remove_front(depth).unwrap();
246        self.current_stack().push_front(deep);
247    }
248
249    fn push(&mut self, expr: Expr) {
250        self.count_pushes(1);
251        self.current_stack().push_front(expr);
252    }
253
254    fn push_const<A: AsRef<[u8]>>(&mut self, imm: &A) {
255        self.push(Expr::constant(imm))
256    }
257}
258
259#[derive(Debug)]
260struct Annotator<'a> {
261    basic: &'a BasicBlock,
262    vars: u16,
263    stacks: Vec<VecDeque<Expr>>, // TODO: I don't think we actually need to keep the
264                                 //       intermediary stacks. Probably only need the
265                                 //       current, previous, and first.
266}
267
268impl<'a> Annotator<'a> {
269    fn new(basic: &'a BasicBlock) -> Self {
270        let mut stacks = Vec::with_capacity(basic.ops.len() + 1);
271        stacks.push(VecDeque::new());
272
273        Self {
274            stacks,
275            basic,
276            vars: 0,
277        }
278    }
279
280    fn advance(&mut self) {
281        let last = self.stacks.last().cloned().unwrap_or_default();
282        self.stacks.push(last);
283    }
284
285    fn annotate_one(pc: usize, stack: &mut StackWindow, op: &Op<[u8]>) -> Option<Exit> {
286        match op {
287            Op::Stop(_) => {
288                return Some(Exit::Terminate);
289            }
290
291            Op::Add(_) => {
292                let lhs = stack.pop();
293                let rhs = stack.pop();
294                stack.push(lhs.add(&rhs));
295            }
296
297            Op::Mul(_) => {
298                let lhs = stack.pop();
299                let rhs = stack.pop();
300                stack.push(lhs.mul(&rhs));
301            }
302
303            Op::Sub(_) => {
304                let lhs = stack.pop();
305                let rhs = stack.pop();
306                stack.push(lhs.sub(&rhs));
307            }
308
309            Op::Div(_) => {
310                let lhs = stack.pop();
311                let rhs = stack.pop();
312                stack.push(lhs.div(&rhs));
313            }
314            Op::SDiv(_) => {
315                let lhs = stack.pop();
316                let rhs = stack.pop();
317                stack.push(lhs.s_div(&rhs));
318            }
319            Op::Mod(_) => {
320                let lhs = stack.pop();
321                let rhs = stack.pop();
322                stack.push(lhs.modulo(&rhs));
323            }
324            Op::SMod(_) => {
325                let lhs = stack.pop();
326                let rhs = stack.pop();
327                stack.push(lhs.s_modulo(&rhs));
328            }
329            Op::AddMod(_) => {
330                let add0 = stack.pop();
331                let add1 = stack.pop();
332                let mod_ = stack.pop();
333                stack.push(add0.add_mod(&add1, &mod_))
334            }
335            Op::MulMod(_) => {
336                let add0 = stack.pop();
337                let add1 = stack.pop();
338                let mod_ = stack.pop();
339                stack.push(add0.mul_mod(&add1, &mod_))
340            }
341            Op::Exp(_) => {
342                let lhs = stack.pop();
343                let rhs = stack.pop();
344                stack.push(lhs.exp(&rhs));
345            }
346            Op::SignExtend(_) => {
347                let lhs = stack.pop();
348                let rhs = stack.pop();
349                stack.push(lhs.sign_extend(&rhs));
350            }
351
352            Op::Lt(_) => {
353                let lhs = stack.pop();
354                let rhs = stack.pop();
355                stack.push(lhs.lt(&rhs));
356            }
357            Op::Gt(_) => {
358                let lhs = stack.pop();
359                let rhs = stack.pop();
360                stack.push(lhs.gt(&rhs));
361            }
362            Op::SLt(_) => {
363                let lhs = stack.pop();
364                let rhs = stack.pop();
365                stack.push(lhs.s_lt(&rhs));
366            }
367            Op::SGt(_) => {
368                let lhs = stack.pop();
369                let rhs = stack.pop();
370                stack.push(lhs.s_gt(&rhs));
371            }
372            Op::Eq(_) => {
373                let lhs = stack.pop();
374                let rhs = stack.pop();
375                stack.push(lhs.is_eq(&rhs));
376            }
377            Op::IsZero(_) => {
378                let arg = stack.pop().is_zero();
379                stack.push(arg);
380            }
381            Op::And(_) => {
382                let lhs = stack.pop();
383                let rhs = stack.pop();
384                stack.push(lhs.and(&rhs));
385            }
386            Op::Or(_) => {
387                let lhs = stack.pop();
388                let rhs = stack.pop();
389                stack.push(lhs.or(&rhs));
390            }
391            Op::Xor(_) => {
392                let lhs = stack.pop();
393                let rhs = stack.pop();
394                stack.push(lhs.xor(&rhs));
395            }
396            Op::Not(_) => {
397                let arg = stack.pop().not();
398                stack.push(arg);
399            }
400            Op::Byte(_) => {
401                let lhs = stack.pop();
402                let rhs = stack.pop();
403                stack.push(lhs.byte(&rhs));
404            }
405            Op::Shl(_) => {
406                let lhs = stack.pop();
407                let rhs = stack.pop();
408                stack.push(lhs.shl(&rhs));
409            }
410            Op::Shr(_) => {
411                let lhs = stack.pop();
412                let rhs = stack.pop();
413                stack.push(lhs.shr(&rhs));
414            }
415            Op::Sar(_) => {
416                let lhs = stack.pop();
417                let rhs = stack.pop();
418                stack.push(lhs.sar(&rhs));
419            }
420            Op::Keccak256(_) => {
421                let offset = stack.pop();
422                let length = stack.pop();
423                stack.push(Expr::keccak256(&offset, &length));
424            }
425
426            Op::Address(_) => stack.push(Expr::address()),
427            Op::Balance(_) => {
428                let address = stack.pop();
429                stack.push(Expr::balance(&address));
430            }
431            Op::Origin(_) => stack.push(Expr::origin()),
432            Op::Caller(_) => stack.push(Expr::caller()),
433            Op::CallValue(_) => stack.push(Expr::call_value()),
434            Op::CallDataLoad(_) => {
435                let offset = stack.pop();
436                stack.push(Expr::call_data_load(&offset));
437            }
438            Op::CodeSize(_) => stack.push(Expr::code_size()),
439            Op::GasPrice(_) => stack.push(Expr::gas_price()),
440            Op::ExtCodeSize(_) => {
441                let address = stack.pop();
442                stack.push(Expr::ext_code_size(&address));
443            }
444            Op::BlockHash(_) => {
445                let address = stack.pop();
446                stack.push(Expr::block_hash(&address));
447            }
448            Op::Coinbase(_) => stack.push(Expr::coinbase()),
449            Op::Timestamp(_) => stack.push(Expr::timestamp()),
450            Op::Number(_) => stack.push(Expr::number()),
451            Op::Difficulty(_) => stack.push(Expr::difficulty()),
452            Op::GasLimit(_) => stack.push(Expr::gas_limit()),
453            Op::ChainId(_) => stack.push(Expr::chain_id()),
454            Op::SelfBalance(_) => stack.push(Expr::self_balance()),
455            Op::BaseFee(_) => stack.push(Expr::base_fee()),
456
457            Op::MSize(_) => stack.push(Expr::m_size()),
458            Op::Gas(_) => stack.push(Expr::gas()),
459
460            Op::Pop(_) => {
461                stack.pop();
462            }
463
464            Op::CallDataSize(_) => stack.push(Expr::call_data_size()),
465            Op::CallDataCopy(_) => {
466                let _dest_offset = stack.pop();
467                let _offset = stack.pop();
468                let _len = stack.pop();
469                // TODO: Set memory
470            }
471
472            Op::CodeCopy(_) => {
473                let _dest_offset = stack.pop();
474                let _offset = stack.pop();
475                let _len = stack.pop();
476                // TODO: Set memory
477            }
478
479            Op::ExtCodeCopy(_) => {
480                let _addr = stack.pop();
481                let _dest_offset = stack.pop();
482                let _offset = stack.pop();
483                let _len = stack.pop();
484                // TODO: Set memory
485            }
486            Op::ReturnDataSize(_) => stack.push(Expr::return_data_size()),
487            Op::ReturnDataCopy(_) => {
488                let _dest_offset = stack.pop();
489                let _offset = stack.pop();
490                let _len = stack.pop();
491                // TODO: Set memory
492            }
493            Op::ExtCodeHash(_) => {
494                let addr = stack.pop();
495                stack.push(Expr::ext_code_hash(&addr));
496            }
497            Op::MLoad(_) => {
498                let addr = stack.pop();
499                stack.push(addr.m_load());
500            }
501            Op::MStore(_) => {
502                let _addr = stack.pop();
503                let _value = stack.pop();
504                // TODO: set memory
505            }
506            Op::MStore8(_) => {
507                let _addr = stack.pop();
508                let _value = stack.pop();
509                // TODO: set memory
510            }
511            Op::SLoad(_) => {
512                let addr = stack.pop();
513                stack.push(addr.s_load());
514            }
515            Op::SStore(_) => {
516                let _key = stack.pop();
517                let _value = stack.pop();
518                // TODO: set storage
519            }
520            Op::GetPc(_) => stack.push(Expr::pc(pc as u16)),
521
522            Op::JumpDest(_) => {
523                // No-op
524            }
525
526            Op::Push0(_) => stack.push_const(&[0; 1]),
527            Op::Push1(Push1(imm)) => stack.push_const(imm),
528            Op::Push2(Push2(imm)) => stack.push_const(imm),
529            Op::Push3(Push3(imm)) => stack.push_const(imm),
530            Op::Push4(Push4(imm)) => stack.push_const(imm),
531            Op::Push5(Push5(imm)) => stack.push_const(imm),
532            Op::Push6(Push6(imm)) => stack.push_const(imm),
533            Op::Push7(Push7(imm)) => stack.push_const(imm),
534            Op::Push8(Push8(imm)) => stack.push_const(imm),
535            Op::Push9(Push9(imm)) => stack.push_const(imm),
536            Op::Push10(Push10(imm)) => stack.push_const(imm),
537            Op::Push11(Push11(imm)) => stack.push_const(imm),
538            Op::Push12(Push12(imm)) => stack.push_const(imm),
539            Op::Push13(Push13(imm)) => stack.push_const(imm),
540            Op::Push14(Push14(imm)) => stack.push_const(imm),
541            Op::Push15(Push15(imm)) => stack.push_const(imm),
542            Op::Push16(Push16(imm)) => stack.push_const(imm),
543            Op::Push17(Push17(imm)) => stack.push_const(imm),
544            Op::Push18(Push18(imm)) => stack.push_const(imm),
545            Op::Push19(Push19(imm)) => stack.push_const(imm),
546            Op::Push20(Push20(imm)) => stack.push_const(imm),
547            Op::Push21(Push21(imm)) => stack.push_const(imm),
548            Op::Push22(Push22(imm)) => stack.push_const(imm),
549            Op::Push23(Push23(imm)) => stack.push_const(imm),
550            Op::Push24(Push24(imm)) => stack.push_const(imm),
551            Op::Push25(Push25(imm)) => stack.push_const(imm),
552            Op::Push26(Push26(imm)) => stack.push_const(imm),
553            Op::Push27(Push27(imm)) => stack.push_const(imm),
554            Op::Push28(Push28(imm)) => stack.push_const(imm),
555            Op::Push29(Push29(imm)) => stack.push_const(imm),
556            Op::Push30(Push30(imm)) => stack.push_const(imm),
557            Op::Push31(Push31(imm)) => stack.push_const(imm),
558            Op::Push32(Push32(imm)) => stack.push_const(imm),
559
560            Op::Dup1(_) => {
561                let arg = stack.peek(0).clone();
562                stack.push(arg)
563            }
564            Op::Dup2(_) => {
565                let arg = stack.peek(1).clone();
566                stack.push(arg)
567            }
568            Op::Dup3(_) => {
569                let arg = stack.peek(2).clone();
570                stack.push(arg)
571            }
572            Op::Dup4(_) => {
573                let arg = stack.peek(3).clone();
574                stack.push(arg)
575            }
576            Op::Dup5(_) => {
577                let arg = stack.peek(4).clone();
578                stack.push(arg)
579            }
580            Op::Dup6(_) => {
581                let arg = stack.peek(5).clone();
582                stack.push(arg)
583            }
584            Op::Dup7(_) => {
585                let arg = stack.peek(6).clone();
586                stack.push(arg)
587            }
588            Op::Dup8(_) => {
589                let arg = stack.peek(7).clone();
590                stack.push(arg)
591            }
592            Op::Dup9(_) => {
593                let arg = stack.peek(8).clone();
594                stack.push(arg)
595            }
596            Op::Dup10(_) => {
597                let arg = stack.peek(9).clone();
598                stack.push(arg)
599            }
600            Op::Dup11(_) => {
601                let arg = stack.peek(10).clone();
602                stack.push(arg)
603            }
604            Op::Dup12(_) => {
605                let arg = stack.peek(11).clone();
606                stack.push(arg)
607            }
608            Op::Dup13(_) => {
609                let arg = stack.peek(12).clone();
610                stack.push(arg)
611            }
612            Op::Dup14(_) => {
613                let arg = stack.peek(13).clone();
614                stack.push(arg)
615            }
616            Op::Dup15(_) => {
617                let arg = stack.peek(14).clone();
618                stack.push(arg)
619            }
620            Op::Dup16(_) => {
621                let arg = stack.peek(15).clone();
622                stack.push(arg)
623            }
624
625            Op::Log0(_) => {
626                let _offset = stack.pop();
627                let _length = stack.pop();
628            }
629            Op::Log1(_) => {
630                let _offset = stack.pop();
631                let _length = stack.pop();
632                let _topic0 = stack.pop();
633            }
634            Op::Log2(_) => {
635                let _offset = stack.pop();
636                let _length = stack.pop();
637                let _topic0 = stack.pop();
638                let _topic1 = stack.pop();
639            }
640            Op::Log3(_) => {
641                let _offset = stack.pop();
642                let _length = stack.pop();
643                let _topic0 = stack.pop();
644                let _topic1 = stack.pop();
645                let _topic2 = stack.pop();
646            }
647            Op::Log4(_) => {
648                let _offset = stack.pop();
649                let _length = stack.pop();
650                let _topic0 = stack.pop();
651                let _topic1 = stack.pop();
652                let _topic2 = stack.pop();
653                let _topic3 = stack.pop();
654            }
655
656            Op::Swap1(_) => stack.swap(1),
657            Op::Swap2(_) => stack.swap(2),
658            Op::Swap3(_) => stack.swap(3),
659            Op::Swap4(_) => stack.swap(4),
660            Op::Swap5(_) => stack.swap(5),
661            Op::Swap6(_) => stack.swap(6),
662            Op::Swap7(_) => stack.swap(7),
663            Op::Swap8(_) => stack.swap(8),
664            Op::Swap9(_) => stack.swap(9),
665            Op::Swap10(_) => stack.swap(10),
666            Op::Swap11(_) => stack.swap(11),
667            Op::Swap12(_) => stack.swap(12),
668            Op::Swap13(_) => stack.swap(13),
669            Op::Swap14(_) => stack.swap(14),
670            Op::Swap15(_) => stack.swap(15),
671            Op::Swap16(_) => stack.swap(16),
672
673            Op::Revert(_) | Op::Return(_) => {
674                let _offset = stack.pop();
675                let _length = stack.pop();
676                return Some(Exit::Terminate);
677            }
678
679            Op::SelfDestruct(_) => {
680                let _addr = stack.pop();
681                return Some(Exit::Terminate);
682            }
683
684            Op::Jump(_) => {
685                let dest = stack.pop();
686                return Some(Exit::Unconditional(dest));
687            }
688
689            Op::JumpI(_) => {
690                let when_false = pc + 1;
691                let when_true = stack.pop();
692                let condition = stack.pop();
693                return Some(Exit::Branch {
694                    when_false,
695                    when_true,
696                    condition,
697                });
698            }
699
700            Op::Create(_) => {
701                let value = stack.pop();
702                let offset = stack.pop();
703                let length = stack.pop();
704                stack.push(Expr::create(&value, &offset, &length))
705            }
706
707            Op::Call(_) => {
708                let gas = stack.pop();
709                let addr = stack.pop();
710                let value = stack.pop();
711                let args_offset = stack.pop();
712                let args_len = stack.pop();
713                let ret_offset = stack.pop();
714                let ret_len = stack.pop();
715                stack.push(Expr::call(
716                    &gas,
717                    &addr,
718                    &value,
719                    &args_offset,
720                    &args_len,
721                    &ret_offset,
722                    &ret_len,
723                ))
724            }
725
726            Op::CallCode(_) => {
727                let gas = stack.pop();
728                let addr = stack.pop();
729                let value = stack.pop();
730                let args_offset = stack.pop();
731                let args_len = stack.pop();
732                let ret_offset = stack.pop();
733                let ret_len = stack.pop();
734                stack.push(Expr::call_code(
735                    &gas,
736                    &addr,
737                    &value,
738                    &args_offset,
739                    &args_len,
740                    &ret_offset,
741                    &ret_len,
742                ))
743            }
744
745            Op::DelegateCall(_) => {
746                let gas = stack.pop();
747                let addr = stack.pop();
748                let args_offset = stack.pop();
749                let args_len = stack.pop();
750                let ret_offset = stack.pop();
751                let ret_len = stack.pop();
752                stack.push(Expr::delegate_call(
753                    &gas,
754                    &addr,
755                    &args_offset,
756                    &args_len,
757                    &ret_offset,
758                    &ret_len,
759                ))
760            }
761
762            Op::Create2(_) => {
763                let value = stack.pop();
764                let offset = stack.pop();
765                let length = stack.pop();
766                let salt = stack.pop();
767                stack.push(Expr::create2(&value, &offset, &length, &salt))
768            }
769
770            Op::StaticCall(_) => {
771                let gas = stack.pop();
772                let addr = stack.pop();
773                let args_offset = stack.pop();
774                let args_len = stack.pop();
775                let ret_offset = stack.pop();
776                let ret_len = stack.pop();
777                stack.push(Expr::static_call(
778                    &gas,
779                    &addr,
780                    &args_offset,
781                    &args_len,
782                    &ret_offset,
783                    &ret_len,
784                ))
785            }
786
787            Op::Invalid(_)
788            | Op::Invalid0c(_)
789            | Op::Invalid0d(_)
790            | Op::Invalid0e(_)
791            | Op::Invalid0f(_)
792            | Op::Invalid1e(_)
793            | Op::Invalid1f(_)
794            | Op::Invalid21(_)
795            | Op::Invalid22(_)
796            | Op::Invalid23(_)
797            | Op::Invalid24(_)
798            | Op::Invalid25(_)
799            | Op::Invalid26(_)
800            | Op::Invalid27(_)
801            | Op::Invalid28(_)
802            | Op::Invalid29(_)
803            | Op::Invalid2a(_)
804            | Op::Invalid2b(_)
805            | Op::Invalid2c(_)
806            | Op::Invalid2d(_)
807            | Op::Invalid2e(_)
808            | Op::Invalid2f(_)
809            | Op::Invalid49(_)
810            | Op::Invalid4a(_)
811            | Op::Invalid4b(_)
812            | Op::Invalid4c(_)
813            | Op::Invalid4d(_)
814            | Op::Invalid4e(_)
815            | Op::Invalid4f(_)
816            | Op::Invalid5c(_)
817            | Op::Invalid5d(_)
818            | Op::Invalid5e(_)
819            | Op::InvalidA5(_)
820            | Op::InvalidA6(_)
821            | Op::InvalidA7(_)
822            | Op::InvalidA8(_)
823            | Op::InvalidA9(_)
824            | Op::InvalidAa(_)
825            | Op::InvalidAb(_)
826            | Op::InvalidAc(_)
827            | Op::InvalidAd(_)
828            | Op::InvalidAe(_)
829            | Op::InvalidAf(_)
830            | Op::InvalidB0(_)
831            | Op::InvalidB1(_)
832            | Op::InvalidB2(_)
833            | Op::InvalidB3(_)
834            | Op::InvalidB4(_)
835            | Op::InvalidB5(_)
836            | Op::InvalidB6(_)
837            | Op::InvalidB7(_)
838            | Op::InvalidB8(_)
839            | Op::InvalidB9(_)
840            | Op::InvalidBa(_)
841            | Op::InvalidBb(_)
842            | Op::InvalidBc(_)
843            | Op::InvalidBd(_)
844            | Op::InvalidBe(_)
845            | Op::InvalidBf(_)
846            | Op::InvalidC0(_)
847            | Op::InvalidC1(_)
848            | Op::InvalidC2(_)
849            | Op::InvalidC3(_)
850            | Op::InvalidC4(_)
851            | Op::InvalidC5(_)
852            | Op::InvalidC6(_)
853            | Op::InvalidC7(_)
854            | Op::InvalidC8(_)
855            | Op::InvalidC9(_)
856            | Op::InvalidCa(_)
857            | Op::InvalidCb(_)
858            | Op::InvalidCc(_)
859            | Op::InvalidCd(_)
860            | Op::InvalidCe(_)
861            | Op::InvalidCf(_)
862            | Op::InvalidD0(_)
863            | Op::InvalidD1(_)
864            | Op::InvalidD2(_)
865            | Op::InvalidD3(_)
866            | Op::InvalidD4(_)
867            | Op::InvalidD5(_)
868            | Op::InvalidD6(_)
869            | Op::InvalidD7(_)
870            | Op::InvalidD8(_)
871            | Op::InvalidD9(_)
872            | Op::InvalidDa(_)
873            | Op::InvalidDb(_)
874            | Op::InvalidDc(_)
875            | Op::InvalidDd(_)
876            | Op::InvalidDe(_)
877            | Op::InvalidDf(_)
878            | Op::InvalidE0(_)
879            | Op::InvalidE1(_)
880            | Op::InvalidE2(_)
881            | Op::InvalidE3(_)
882            | Op::InvalidE4(_)
883            | Op::InvalidE5(_)
884            | Op::InvalidE6(_)
885            | Op::InvalidE7(_)
886            | Op::InvalidE8(_)
887            | Op::InvalidE9(_)
888            | Op::InvalidEa(_)
889            | Op::InvalidEb(_)
890            | Op::InvalidEc(_)
891            | Op::InvalidEd(_)
892            | Op::InvalidEe(_)
893            | Op::InvalidEf(_)
894            | Op::InvalidF6(_)
895            | Op::InvalidF7(_)
896            | Op::InvalidF8(_)
897            | Op::InvalidF9(_)
898            | Op::InvalidFb(_)
899            | Op::InvalidFc(_) => {
900                return Some(Exit::Terminate);
901            }
902        }
903
904        None
905    }
906
907    fn annotate(&mut self) -> Exit {
908        let mut pc = self.basic.offset;
909
910        for (idx, op) in self.basic.ops.iter().enumerate() {
911            self.advance();
912            let is_last = idx == self.basic.ops.len() - 1;
913
914            let mut window = StackWindow::new(&mut self.vars, &mut self.stacks, op);
915
916            if let Some(exit) = Self::annotate_one(pc, &mut window, op) {
917                assert!(is_last);
918
919                let exit_matches = match exit {
920                    Exit::Terminate => op.is_exit(),
921                    Exit::Branch { .. } => op.is_jump(),
922                    Exit::Unconditional(_) => op.is_jump(),
923                    Exit::FallThrough(_) => unreachable!(),
924                };
925
926                assert!(exit_matches, "bug: exit type doesn't match metadata");
927
928                return exit;
929            }
930
931            assert!(!op.is_exit());
932
933            pc += op.size();
934        }
935
936        Exit::FallThrough(pc)
937    }
938}
939
940#[cfg(test)]
941mod tests {
942    use super::*;
943
944    trait CheckExit {
945        fn check(&self, actual: &Exit);
946    }
947
948    struct ExitTerminate;
949    impl CheckExit for ExitTerminate {
950        fn check(&self, actual: &Exit) {
951            match actual {
952                Exit::Terminate => (),
953                wrong => panic!("expected {:?}, got {:?}", Exit::<()>::Terminate, wrong),
954            }
955        }
956    }
957
958    struct ExitFallThrough(usize);
959
960    impl CheckExit for ExitFallThrough {
961        fn check(&self, actual: &Exit) {
962            let exit = match actual {
963                Exit::FallThrough(f) => f,
964                wrong => panic!(
965                    "expected {:?}, got {:?}",
966                    Exit::<()>::FallThrough(self.0),
967                    wrong
968                ),
969            };
970
971            assert_eq!(&self.0, exit);
972        }
973    }
974
975    struct ExitUnconditional(Expr);
976
977    impl CheckExit for ExitUnconditional {
978        fn check(&self, actual: &Exit) {
979            let exit = match actual {
980                Exit::Unconditional(expr) => expr,
981                wrong => panic!("expected Exit::Unconditional(...), got {:?}", wrong),
982            };
983
984            assert_eq!(&self.0, exit);
985        }
986    }
987
988    #[must_use]
989    struct AnnotateTest<O, E, I, P> {
990        ops: O,
991        expected_exit: E,
992        expected_input_stack: I,
993        expected_output_stack: P,
994    }
995
996    impl<O, Oi, E, I, Ii, P, Pi> AnnotateTest<O, E, I, P>
997    where
998        O: IntoIterator<Item = Oi>,
999        Oi: Into<Op<[u8]>>,
1000        E: CheckExit,
1001        I: IntoIterator<Item = Ii>,
1002        Ii: Into<Expr>,
1003        P: IntoIterator<Item = Pi>,
1004        Pi: Into<Expr>,
1005    {
1006        fn check(self) {
1007            let basic = BasicBlock {
1008                offset: 0x1234,
1009                ops: self.ops.into_iter().map(Into::into).collect(),
1010            };
1011
1012            let mut annotator = Annotator::new(&basic);
1013            let exit = annotator.annotate();
1014            self.expected_exit.check(&exit);
1015
1016            let input_stack = annotator.stacks.first().unwrap();
1017            let expected_input_stack: Vec<_> = self
1018                .expected_input_stack
1019                .into_iter()
1020                .map(Into::into)
1021                .collect();
1022            assert_eq!(input_stack, &expected_input_stack, "input stack incorrect");
1023
1024            let output_stack = annotator.stacks.last().unwrap();
1025            let expected_output_stack: Vec<_> = self
1026                .expected_output_stack
1027                .into_iter()
1028                .map(Into::into)
1029                .collect();
1030            assert_eq!(
1031                output_stack, &expected_output_stack,
1032                "output stack incorrect"
1033            );
1034        }
1035    }
1036
1037    #[test]
1038    fn annotate_stop() {
1039        AnnotateTest {
1040            ops: vec![Stop],
1041            expected_exit: ExitTerminate,
1042            expected_input_stack: Vec::<Expr>::new(),
1043            expected_output_stack: Vec::<Expr>::new(),
1044        }
1045        .check();
1046    }
1047
1048    #[test]
1049    fn annotate_add() {
1050        AnnotateTest {
1051            ops: vec![Add],
1052            expected_exit: ExitFallThrough(0x1235),
1053            expected_input_stack: vec![Var::with_id(1), Var::with_id(2)],
1054            expected_output_stack: vec![Expr::add(
1055                &Var::with_id(1).into(),
1056                &Var::with_id(2).into(),
1057            )],
1058        }
1059        .check();
1060    }
1061
1062    #[test]
1063    fn annotate_mul() {
1064        AnnotateTest {
1065            ops: vec![Mul],
1066            expected_exit: ExitFallThrough(0x1235),
1067            expected_input_stack: vec![Var::with_id(1), Var::with_id(2)],
1068            expected_output_stack: vec![Expr::mul(
1069                &Var::with_id(1).into(),
1070                &Var::with_id(2).into(),
1071            )],
1072        }
1073        .check();
1074    }
1075
1076    #[test]
1077    fn annotate_sub() {
1078        AnnotateTest {
1079            ops: vec![Sub],
1080            expected_exit: ExitFallThrough(0x1235),
1081            expected_input_stack: vec![Var::with_id(1), Var::with_id(2)],
1082            expected_output_stack: vec![Expr::sub(
1083                &Var::with_id(1).into(),
1084                &Var::with_id(2).into(),
1085            )],
1086        }
1087        .check();
1088    }
1089
1090    // TODO: Test the rest of the opcodes.
1091
1092    #[test]
1093    fn annotate_swap1() {
1094        AnnotateTest {
1095            ops: vec![Swap1],
1096            expected_exit: ExitFallThrough(0x1235),
1097            expected_input_stack: vec![Var::with_id(1), Var::with_id(2)],
1098            expected_output_stack: vec![Var::with_id(2), Var::with_id(1)],
1099        }
1100        .check();
1101    }
1102
1103    #[test]
1104    fn annotate_swap2() {
1105        AnnotateTest {
1106            ops: vec![Swap2],
1107            expected_exit: ExitFallThrough(0x1235),
1108            expected_input_stack: vec![Var::with_id(1), Var::with_id(2), Var::with_id(3)],
1109            expected_output_stack: vec![Var::with_id(3), Var::with_id(2), Var::with_id(1)],
1110        }
1111        .check();
1112    }
1113
1114    #[test]
1115    fn annotate_swap3() {
1116        AnnotateTest {
1117            ops: vec![Swap3],
1118            expected_exit: ExitFallThrough(0x1235),
1119            expected_input_stack: (1..5).map(Var::with_id),
1120            expected_output_stack: vec![
1121                Var::with_id(4),
1122                Var::with_id(2),
1123                Var::with_id(3),
1124                Var::with_id(1),
1125            ],
1126        }
1127        .check();
1128    }
1129
1130    #[test]
1131    fn annotate_dup1() {
1132        AnnotateTest {
1133            ops: vec![Dup1],
1134            expected_exit: ExitFallThrough(0x1235),
1135            expected_input_stack: vec![Var::with_id(1)],
1136            expected_output_stack: vec![Var::with_id(1), Var::with_id(1)],
1137        }
1138        .check();
1139    }
1140
1141    #[test]
1142    fn annotate_dup2() {
1143        AnnotateTest {
1144            ops: vec![Dup2],
1145            expected_exit: ExitFallThrough(0x1235),
1146            expected_input_stack: vec![Var::with_id(1), Var::with_id(2)],
1147            expected_output_stack: vec![Var::with_id(2), Var::with_id(1), Var::with_id(2)],
1148        }
1149        .check();
1150    }
1151
1152    #[test]
1153    fn annotate_dup3() {
1154        AnnotateTest {
1155            ops: vec![Dup3],
1156            expected_exit: ExitFallThrough(0x1235),
1157            expected_input_stack: vec![Var::with_id(1), Var::with_id(2), Var::with_id(3)],
1158            expected_output_stack: vec![
1159                Var::with_id(3),
1160                Var::with_id(1),
1161                Var::with_id(2),
1162                Var::with_id(3),
1163            ],
1164        }
1165        .check();
1166    }
1167
1168    #[test]
1169    fn annotate_push1() {
1170        AnnotateTest {
1171            ops: vec![Push1([77])],
1172            expected_exit: ExitFallThrough(0x1236),
1173            expected_input_stack: Vec::<Expr>::new(),
1174            expected_output_stack: vec![Expr::constant_offset(77u8)],
1175        }
1176        .check();
1177    }
1178
1179    #[test]
1180    fn annotate_push2() {
1181        AnnotateTest {
1182            ops: vec![Push2([0x12, 0x34])],
1183            expected_exit: ExitFallThrough(0x1237),
1184            expected_input_stack: Vec::<Expr>::new(),
1185            expected_output_stack: vec![Expr::constant_offset(0x1234u64)],
1186        }
1187        .check();
1188    }
1189
1190    #[test]
1191    fn annotate_jump() {
1192        AnnotateTest {
1193            ops: vec![
1194                Op::from(Push1([0xbb])),
1195                Op::from(Push1([0xaa])),
1196                Op::from(Jump),
1197            ],
1198            expected_exit: ExitUnconditional(Expr::constant_offset(0xaau64)),
1199            expected_input_stack: Vec::<Expr>::new(),
1200            expected_output_stack: vec![Expr::constant_offset(0xbbu64)],
1201        }
1202        .check();
1203    }
1204}
etk_dasm/blocks/annotated.rs

etk_dasm/blocks/
annotated.rs
