bells_miniscript/miniscript/
lex.rs

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

bells_miniscript/miniscript/
lex.rs
