miniscript_debug/miniscript/
lex.rs

1// Miniscript
2// Written in 2018 by
3//     Andrew Poelstra <apoelstra@wpsoftware.net>
4//
5// To the extent possible under law, the author(s) have dedicated all
6// copyright and related and neighboring rights to this software to
7// the public domain worldwide. This software is distributed without
8// any warranty.
9//
10// You should have received a copy of the CC0 Public Domain Dedication
11// along with this software.
12// If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
13//
14
15//! Lexer
16//!
17//! Translates a script into a reversed sequence of tokens
18//!
19
20use core::fmt;
21
22use bitcoin::blockdata::{opcodes, script};
23
24use super::Error;
25use crate::prelude::*;
26
27/// Atom of a tokenized version of a script
28#[derive(Debug, Copy, Clone, PartialEq, Eq)]
29#[allow(missing_docs)]
30pub enum Token<'s> {
31    BoolAnd,
32    BoolOr,
33    Add,
34    Equal,
35    NumEqual,
36    CheckSig,
37    CheckSigAdd,
38    CheckMultiSig,
39    CheckSequenceVerify,
40    CheckLockTimeVerify,
41    FromAltStack,
42    ToAltStack,
43    Drop,
44    Dup,
45    If,
46    IfDup,
47    NotIf,
48    Else,
49    EndIf,
50    ZeroNotEqual,
51    Size,
52    Swap,
53    Verify,
54    Ripemd160,
55    Hash160,
56    Sha256,
57    Hash256,
58    Num(u32),
59    Hash20(&'s [u8]),
60    Bytes32(&'s [u8]),
61    Bytes33(&'s [u8]),
62    Bytes65(&'s [u8]),
63}
64
65impl<'s> fmt::Display for Token<'s> {
66    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
67        match *self {
68            Token::Num(n) => write!(f, "#{}", n),
69            Token::Hash20(b) | Token::Bytes33(b) | Token::Bytes32(b) | Token::Bytes65(b) => {
70                for ch in b {
71                    write!(f, "{:02x}", *ch)?;
72                }
73                Ok(())
74            }
75            x => write!(f, "{:?}", x),
76        }
77    }
78}
79
80#[derive(Debug, Clone)]
81/// Iterator that goes through a vector of tokens backward (our parser wants to read
82/// backward and this is more efficient anyway since we can use `Vec::pop()`).
83pub struct TokenIter<'s>(Vec<Token<'s>>);
84
85impl<'s> TokenIter<'s> {
86    /// Create a new TokenIter
87    pub fn new(v: Vec<Token<'s>>) -> TokenIter<'s> {
88        TokenIter(v)
89    }
90
91    /// Look at the top at Iterator
92    pub fn peek(&self) -> Option<&'s Token> {
93        self.0.last()
94    }
95
96    /// Push a value to the iterator
97    /// This will be first value consumed by popun_
98    pub fn un_next(&mut self, tok: Token<'s>) {
99        self.0.push(tok)
100    }
101
102    /// The len of the iterator
103    pub fn len(&self) -> usize {
104        self.0.len()
105    }
106
107    /// Returns true if iterator is empty.
108    pub fn is_empty(&self) -> bool {
109        self.0.is_empty()
110    }
111}
112
113impl<'s> Iterator for TokenIter<'s> {
114    type Item = Token<'s>;
115
116    fn next(&mut self) -> Option<Token<'s>> {
117        self.0.pop()
118    }
119}
120
121/// Tokenize a script
122pub fn lex(script: &'_ script::Script) -> Result<Vec<Token<'_>>, Error> {
123    let mut ret = Vec::with_capacity(script.len());
124
125    for ins in script.instructions_minimal() {
126        match ins.map_err(Error::Script)? {
127            script::Instruction::Op(opcodes::all::OP_BOOLAND) => {
128                ret.push(Token::BoolAnd);
129            }
130            script::Instruction::Op(opcodes::all::OP_BOOLOR) => {
131                ret.push(Token::BoolOr);
132            }
133            script::Instruction::Op(opcodes::all::OP_EQUAL) => {
134                ret.push(Token::Equal);
135            }
136            script::Instruction::Op(opcodes::all::OP_EQUALVERIFY) => {
137                ret.push(Token::Equal);
138                ret.push(Token::Verify);
139            }
140            script::Instruction::Op(opcodes::all::OP_NUMEQUAL) => {
141                ret.push(Token::NumEqual);
142            }
143            script::Instruction::Op(opcodes::all::OP_NUMEQUALVERIFY) => {
144                ret.push(Token::NumEqual);
145                ret.push(Token::Verify);
146            }
147            script::Instruction::Op(opcodes::all::OP_CHECKSIG) => {
148                ret.push(Token::CheckSig);
149            }
150            script::Instruction::Op(opcodes::all::OP_CHECKSIGVERIFY) => {
151                ret.push(Token::CheckSig);
152                ret.push(Token::Verify);
153            }
154            // Change once the opcode name is updated
155            script::Instruction::Op(opcodes::all::OP_CHECKSIGADD) => {
156                ret.push(Token::CheckSigAdd);
157            }
158            script::Instruction::Op(opcodes::all::OP_CHECKMULTISIG) => {
159                ret.push(Token::CheckMultiSig);
160            }
161            script::Instruction::Op(opcodes::all::OP_CHECKMULTISIGVERIFY) => {
162                ret.push(Token::CheckMultiSig);
163                ret.push(Token::Verify);
164            }
165            script::Instruction::Op(op) if op == opcodes::all::OP_CSV => {
166                ret.push(Token::CheckSequenceVerify);
167            }
168            script::Instruction::Op(op) if op == opcodes::all::OP_CLTV => {
169                ret.push(Token::CheckLockTimeVerify);
170            }
171            script::Instruction::Op(opcodes::all::OP_FROMALTSTACK) => {
172                ret.push(Token::FromAltStack);
173            }
174            script::Instruction::Op(opcodes::all::OP_TOALTSTACK) => {
175                ret.push(Token::ToAltStack);
176            }
177            script::Instruction::Op(opcodes::all::OP_DROP) => {
178                ret.push(Token::Drop);
179            }
180            script::Instruction::Op(opcodes::all::OP_DUP) => {
181                ret.push(Token::Dup);
182            }
183            script::Instruction::Op(opcodes::all::OP_ADD) => {
184                ret.push(Token::Add);
185            }
186            script::Instruction::Op(opcodes::all::OP_IF) => {
187                ret.push(Token::If);
188            }
189            script::Instruction::Op(opcodes::all::OP_IFDUP) => {
190                ret.push(Token::IfDup);
191            }
192            script::Instruction::Op(opcodes::all::OP_NOTIF) => {
193                ret.push(Token::NotIf);
194            }
195            script::Instruction::Op(opcodes::all::OP_ELSE) => {
196                ret.push(Token::Else);
197            }
198            script::Instruction::Op(opcodes::all::OP_ENDIF) => {
199                ret.push(Token::EndIf);
200            }
201            script::Instruction::Op(opcodes::all::OP_0NOTEQUAL) => {
202                ret.push(Token::ZeroNotEqual);
203            }
204            script::Instruction::Op(opcodes::all::OP_SIZE) => {
205                ret.push(Token::Size);
206            }
207            script::Instruction::Op(opcodes::all::OP_SWAP) => {
208                ret.push(Token::Swap);
209            }
210            script::Instruction::Op(opcodes::all::OP_VERIFY) => {
211                match ret.last() {
212                    Some(op @ &Token::Equal)
213                    | Some(op @ &Token::CheckSig)
214                    | Some(op @ &Token::CheckMultiSig) => {
215                        return Err(Error::NonMinimalVerify(format!("{:?}", op)))
216                    }
217                    _ => {}
218                }
219                ret.push(Token::Verify);
220            }
221            script::Instruction::Op(opcodes::all::OP_RIPEMD160) => {
222                ret.push(Token::Ripemd160);
223            }
224            script::Instruction::Op(opcodes::all::OP_HASH160) => {
225                ret.push(Token::Hash160);
226            }
227            script::Instruction::Op(opcodes::all::OP_SHA256) => {
228                ret.push(Token::Sha256);
229            }
230            script::Instruction::Op(opcodes::all::OP_HASH256) => {
231                ret.push(Token::Hash256);
232            }
233            script::Instruction::PushBytes(bytes) => {
234                match bytes.len() {
235                    20 => ret.push(Token::Hash20(bytes)),
236                    32 => ret.push(Token::Bytes32(bytes)),
237                    33 => ret.push(Token::Bytes33(bytes)),
238                    65 => ret.push(Token::Bytes65(bytes)),
239                    _ => {
240                        match script::read_scriptint(bytes) {
241                            Ok(v) if v >= 0 => {
242                                // check minimality of the number
243                                if &script::Builder::new().push_int(v).into_script()[1..] != bytes {
244                                    return Err(Error::InvalidPush(bytes.to_owned()));
245                                }
246                                ret.push(Token::Num(v as u32));
247                            }
248                            Ok(_) => return Err(Error::InvalidPush(bytes.to_owned())),
249                            Err(e) => return Err(Error::Script(e)),
250                        }
251                    }
252                }
253            }
254            script::Instruction::Op(opcodes::all::OP_PUSHBYTES_0) => {
255                ret.push(Token::Num(0));
256            }
257            script::Instruction::Op(opcodes::all::OP_PUSHNUM_1) => {
258                ret.push(Token::Num(1));
259            }
260            script::Instruction::Op(opcodes::all::OP_PUSHNUM_2) => {
261                ret.push(Token::Num(2));
262            }
263            script::Instruction::Op(opcodes::all::OP_PUSHNUM_3) => {
264                ret.push(Token::Num(3));
265            }
266            script::Instruction::Op(opcodes::all::OP_PUSHNUM_4) => {
267                ret.push(Token::Num(4));
268            }
269            script::Instruction::Op(opcodes::all::OP_PUSHNUM_5) => {
270                ret.push(Token::Num(5));
271            }
272            script::Instruction::Op(opcodes::all::OP_PUSHNUM_6) => {
273                ret.push(Token::Num(6));
274            }
275            script::Instruction::Op(opcodes::all::OP_PUSHNUM_7) => {
276                ret.push(Token::Num(7));
277            }
278            script::Instruction::Op(opcodes::all::OP_PUSHNUM_8) => {
279                ret.push(Token::Num(8));
280            }
281            script::Instruction::Op(opcodes::all::OP_PUSHNUM_9) => {
282                ret.push(Token::Num(9));
283            }
284            script::Instruction::Op(opcodes::all::OP_PUSHNUM_10) => {
285                ret.push(Token::Num(10));
286            }
287            script::Instruction::Op(opcodes::all::OP_PUSHNUM_11) => {
288                ret.push(Token::Num(11));
289            }
290            script::Instruction::Op(opcodes::all::OP_PUSHNUM_12) => {
291                ret.push(Token::Num(12));
292            }
293            script::Instruction::Op(opcodes::all::OP_PUSHNUM_13) => {
294                ret.push(Token::Num(13));
295            }
296            script::Instruction::Op(opcodes::all::OP_PUSHNUM_14) => {
297                ret.push(Token::Num(14));
298            }
299            script::Instruction::Op(opcodes::all::OP_PUSHNUM_15) => {
300                ret.push(Token::Num(15));
301            }
302            script::Instruction::Op(opcodes::all::OP_PUSHNUM_16) => {
303                ret.push(Token::Num(16));
304            }
305            script::Instruction::Op(op) => return Err(Error::InvalidOpcode(op)),
306        };
307    }
308    Ok(ret)
309}
miniscript_debug/miniscript/lex.rs

miniscript_debug/miniscript/
lex.rs
