sapio_miniscript/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 bitcoin::blockdata::{opcodes, script};
21
22use std::fmt;
23
24use super::Error;
25
26/// Atom of a tokenized version of a script
27#[derive(Debug, Copy, Clone, PartialEq, Eq)]
28#[allow(missing_docs)]
29pub enum Token<'s> {
30    BoolAnd,
31    BoolOr,
32    Add,
33    Equal,
34    NumEqual,
35    CheckSig,
36    CheckSigAdd,
37    CheckMultiSig,
38    CheckSequenceVerify,
39    CheckLockTimeVerify,
40    CheckTemplateVerify,
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
108impl<'s> Iterator for TokenIter<'s> {
109    type Item = Token<'s>;
110
111    fn next(&mut self) -> Option<Token<'s>> {
112        self.0.pop()
113    }
114}
115
116/// Tokenize a script
117pub fn lex<'s>(script: &'s script::Script) -> Result<Vec<Token<'s>>, Error> {
118    let mut ret = Vec::with_capacity(script.len());
119
120    for ins in script.instructions_minimal() {
121        match ins.map_err(Error::Script)? {
122            script::Instruction::Op(opcodes::all::OP_BOOLAND) => {
123                ret.push(Token::BoolAnd);
124            }
125            script::Instruction::Op(opcodes::all::OP_BOOLOR) => {
126                ret.push(Token::BoolOr);
127            }
128            script::Instruction::Op(opcodes::all::OP_EQUAL) => {
129                ret.push(Token::Equal);
130            }
131            script::Instruction::Op(opcodes::all::OP_EQUALVERIFY) => {
132                ret.push(Token::Equal);
133                ret.push(Token::Verify);
134            }
135            script::Instruction::Op(opcodes::all::OP_NUMEQUAL) => {
136                ret.push(Token::NumEqual);
137            }
138            script::Instruction::Op(opcodes::all::OP_NUMEQUALVERIFY) => {
139                ret.push(Token::NumEqual);
140                ret.push(Token::Verify);
141            }
142            script::Instruction::Op(opcodes::all::OP_CHECKSIG) => {
143                ret.push(Token::CheckSig);
144            }
145            script::Instruction::Op(opcodes::all::OP_CHECKSIGVERIFY) => {
146                ret.push(Token::CheckSig);
147                ret.push(Token::Verify);
148            }
149            // Change once the opcode name is updated
150            script::Instruction::Op(opcodes::all::OP_CHECKSIGADD) => {
151                ret.push(Token::CheckSigAdd);
152            }
153            script::Instruction::Op(opcodes::all::OP_CHECKMULTISIG) => {
154                ret.push(Token::CheckMultiSig);
155            }
156            script::Instruction::Op(opcodes::all::OP_CHECKMULTISIGVERIFY) => {
157                ret.push(Token::CheckMultiSig);
158                ret.push(Token::Verify);
159            }
160            script::Instruction::Op(op) if op == opcodes::all::OP_CSV => {
161                ret.push(Token::CheckSequenceVerify);
162            }
163            script::Instruction::Op(op) if op == opcodes::all::OP_CLTV => {
164                ret.push(Token::CheckLockTimeVerify);
165            }
166            script::Instruction::Op(op) if op == opcodes::all::OP_NOP4 => {
167                ret.push(Token::CheckTemplateVerify);
168            }
169            script::Instruction::Op(opcodes::all::OP_FROMALTSTACK) => {
170                ret.push(Token::FromAltStack);
171            }
172            script::Instruction::Op(opcodes::all::OP_TOALTSTACK) => {
173                ret.push(Token::ToAltStack);
174            }
175            script::Instruction::Op(opcodes::all::OP_DROP) => {
176                ret.push(Token::Drop);
177            }
178            script::Instruction::Op(opcodes::all::OP_DUP) => {
179                ret.push(Token::Dup);
180            }
181            script::Instruction::Op(opcodes::all::OP_ADD) => {
182                ret.push(Token::Add);
183            }
184            script::Instruction::Op(opcodes::all::OP_IF) => {
185                ret.push(Token::If);
186            }
187            script::Instruction::Op(opcodes::all::OP_IFDUP) => {
188                ret.push(Token::IfDup);
189            }
190            script::Instruction::Op(opcodes::all::OP_NOTIF) => {
191                ret.push(Token::NotIf);
192            }
193            script::Instruction::Op(opcodes::all::OP_ELSE) => {
194                ret.push(Token::Else);
195            }
196            script::Instruction::Op(opcodes::all::OP_ENDIF) => {
197                ret.push(Token::EndIf);
198            }
199            script::Instruction::Op(opcodes::all::OP_0NOTEQUAL) => {
200                ret.push(Token::ZeroNotEqual);
201            }
202            script::Instruction::Op(opcodes::all::OP_SIZE) => {
203                ret.push(Token::Size);
204            }
205            script::Instruction::Op(opcodes::all::OP_SWAP) => {
206                ret.push(Token::Swap);
207            }
208            script::Instruction::Op(opcodes::all::OP_VERIFY) => {
209                match ret.last() {
210                    Some(op @ &Token::Equal)
211                    | Some(op @ &Token::CheckSig)
212                    | Some(op @ &Token::CheckMultiSig) => {
213                        return Err(Error::NonMinimalVerify(String::from(format!("{:?}", op))))
214                    }
215                    _ => {}
216                }
217                ret.push(Token::Verify);
218            }
219            script::Instruction::Op(opcodes::all::OP_RIPEMD160) => {
220                ret.push(Token::Ripemd160);
221            }
222            script::Instruction::Op(opcodes::all::OP_HASH160) => {
223                ret.push(Token::Hash160);
224            }
225            script::Instruction::Op(opcodes::all::OP_SHA256) => {
226                ret.push(Token::Sha256);
227            }
228            script::Instruction::Op(opcodes::all::OP_HASH256) => {
229                ret.push(Token::Hash256);
230            }
231            script::Instruction::PushBytes(bytes) => {
232                match bytes.len() {
233                    20 => ret.push(Token::Hash20(&bytes)),
234                    32 => ret.push(Token::Bytes32(&bytes)),
235                    33 => ret.push(Token::Bytes33(&bytes)),
236                    65 => ret.push(Token::Bytes65(&bytes)),
237                    _ => {
238                        match script::read_scriptint(bytes) {
239                            Ok(v) if v >= 0 => {
240                                // check minimality of the number
241                                if &script::Builder::new().push_int(v).into_script()[1..] != bytes {
242                                    return Err(Error::InvalidPush(bytes.to_owned()));
243                                }
244                                ret.push(Token::Num(v as u32));
245                            }
246                            Ok(_) => return Err(Error::InvalidPush(bytes.to_owned())),
247                            Err(e) => return Err(Error::Script(e)),
248                        }
249                    }
250                }
251            }
252            script::Instruction::Op(opcodes::all::OP_PUSHBYTES_0) => {
253                ret.push(Token::Num(0));
254            }
255            script::Instruction::Op(opcodes::all::OP_PUSHNUM_1) => {
256                ret.push(Token::Num(1));
257            }
258            script::Instruction::Op(opcodes::all::OP_PUSHNUM_2) => {
259                ret.push(Token::Num(2));
260            }
261            script::Instruction::Op(opcodes::all::OP_PUSHNUM_3) => {
262                ret.push(Token::Num(3));
263            }
264            script::Instruction::Op(opcodes::all::OP_PUSHNUM_4) => {
265                ret.push(Token::Num(4));
266            }
267            script::Instruction::Op(opcodes::all::OP_PUSHNUM_5) => {
268                ret.push(Token::Num(5));
269            }
270            script::Instruction::Op(opcodes::all::OP_PUSHNUM_6) => {
271                ret.push(Token::Num(6));
272            }
273            script::Instruction::Op(opcodes::all::OP_PUSHNUM_7) => {
274                ret.push(Token::Num(7));
275            }
276            script::Instruction::Op(opcodes::all::OP_PUSHNUM_8) => {
277                ret.push(Token::Num(8));
278            }
279            script::Instruction::Op(opcodes::all::OP_PUSHNUM_9) => {
280                ret.push(Token::Num(9));
281            }
282            script::Instruction::Op(opcodes::all::OP_PUSHNUM_10) => {
283                ret.push(Token::Num(10));
284            }
285            script::Instruction::Op(opcodes::all::OP_PUSHNUM_11) => {
286                ret.push(Token::Num(11));
287            }
288            script::Instruction::Op(opcodes::all::OP_PUSHNUM_12) => {
289                ret.push(Token::Num(12));
290            }
291            script::Instruction::Op(opcodes::all::OP_PUSHNUM_13) => {
292                ret.push(Token::Num(13));
293            }
294            script::Instruction::Op(opcodes::all::OP_PUSHNUM_14) => {
295                ret.push(Token::Num(14));
296            }
297            script::Instruction::Op(opcodes::all::OP_PUSHNUM_15) => {
298                ret.push(Token::Num(15));
299            }
300            script::Instruction::Op(opcodes::all::OP_PUSHNUM_16) => {
301                ret.push(Token::Num(16));
302            }
303            script::Instruction::Op(op) => return Err(Error::InvalidOpcode(op)),
304        };
305    }
306    Ok(ret)
307}
sapio_miniscript/miniscript/lex.rs

sapio_miniscript/miniscript/
lex.rs
