elements_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 std::fmt;
10
11use elements::{opcodes, script};
12
13use super::Error;
14use crate::util::{build_scriptint, slice_to_u32_le};
15/// Atom of a tokenized version of a script
16#[derive(Debug, Clone, PartialEq, Eq)]
17#[allow(missing_docs)]
18pub enum Token<'s> {
19    BoolAnd,
20    BoolOr,
21    Add,
22    Sub,
23    Equal,
24    NumEqual,
25    CheckSig,
26    CheckSigFromStack,
27    CheckSigAdd,
28    CheckSigFromStackVerify,
29    CheckMultiSig,
30    CheckSequenceVerify,
31    CheckLockTimeVerify,
32    FromAltStack,
33    ToAltStack,
34    Left,
35    Cat,
36    CodeSep,
37    Over,
38    Pick,
39    Depth,
40    Drop,
41    Dup,
42    If,
43    IfDup,
44    NotIf,
45    Else,
46    EndIf,
47    ZeroNotEqual,
48    Size,
49    Swap,
50    Verify,
51    Ripemd160,
52    Hash160,
53    Sha256,
54    Hash256,
55    Num(u32),
56    Hash20(&'s [u8]),
57    Bytes8(&'s [u8]),
58    Bytes32(&'s [u8]),
59    Bytes33(&'s [u8]),
60    Bytes65(&'s [u8]),
61    Push(Vec<u8>),        // Num or a
62    PickPush4(u32),       // Pick followed by a 4 byte push
63    PickPush32([u8; 32]), // Pick followed by a 32 byte push
64    PickPush(Vec<u8>),    // Pick followed by a push
65    InpValue,
66    OutValue,
67    InpIssue,
68    Leq64,
69    Le64,
70    Geq64,
71    Ge64,
72    Neg64,
73    Div64,
74    Mul64,
75    Sub64,
76    Add64,
77    Nip,
78    And,
79    Or,
80    Xor,
81    Invert,
82    CurrInp,
83    InpAsset,
84    OutAsset,
85    OutSpk,
86    InpSpk,
87    NumNeg1,
88    ScriptNumToLe64,
89    Le64ToScriptNum,
90    Dup2,
91}
92
93impl<'s> fmt::Display for Token<'s> {
94    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
95        match self {
96            Token::Num(n) => write!(f, "#{}", n),
97            Token::Hash20(b) | Token::Bytes33(b) | Token::Bytes32(b) | Token::Bytes65(b) => {
98                for ch in &b[..] {
99                    write!(f, "{:02x}", *ch)?;
100                }
101                Ok(())
102            }
103            x => write!(f, "{:?}", x),
104        }
105    }
106}
107
108#[derive(Debug, Clone)]
109/// Iterator that goes through a vector of tokens backward (our parser wants to read
110/// backward and this is more efficient anyway since we can use `Vec::pop()`).
111// This really does not need to be an iterator because the way we are using it, we are
112// actually collecting lexed symbols into a vector. If that is the case, might as well
113// use the inner vector directly
114pub struct TokenIter<'s>(Vec<Token<'s>>);
115
116impl<'s> TokenIter<'s> {
117    /// Create a new TokenIter
118    pub fn new(v: Vec<Token<'s>>) -> TokenIter<'s> {
119        TokenIter(v)
120    }
121
122    /// Look at the top at Iterator
123    pub fn peek(&self) -> Option<&'s Token<'_>> {
124        self.0.last()
125    }
126
127    /// Look at the slice with the last n elements
128    pub fn peek_slice(&self, n: usize) -> Option<&[Token<'_>]> {
129        if n <= self.len() {
130            Some(self.0[self.len() - n..].as_ref())
131        } else {
132            None
133        }
134    }
135
136    /// Advance the iterator n times
137    /// Returns Some(()) if the iterator can be advanced n times
138    pub fn advance(&mut self, n: usize) -> Option<()> {
139        if n <= self.len() {
140            for _ in 0..n {
141                self.next();
142            }
143            Some(())
144        } else {
145            None
146        }
147    }
148
149    /// Push a value to the iterator
150    /// This will be first value consumed by popun_
151    pub fn un_next(&mut self, tok: Token<'s>) {
152        self.0.push(tok)
153    }
154
155    /// The len of the iterator
156    pub fn len(&self) -> usize {
157        self.0.len()
158    }
159
160    /// Check if the iterator is empty
161    pub fn is_empty(&self) -> bool {
162        self.0.is_empty()
163    }
164
165    /// Get the inner mutable vector
166    pub fn as_inner_mut(&mut self) -> &mut Vec<Token<'s>> {
167        &mut self.0
168    }
169}
170
171impl<'s> Iterator for TokenIter<'s> {
172    type Item = Token<'s>;
173
174    fn next(&mut self) -> Option<Token<'s>> {
175        self.0.pop()
176    }
177}
178
179/// Tokenize a script
180pub fn lex(script: &script::Script) -> Result<Vec<Token<'_>>, Error> {
181    let mut ret = Vec::with_capacity(script.len());
182
183    fn process_candidate_push(ret: &mut [Token<'_>]) {
184        let ret_len = ret.len();
185
186        if ret_len < 2 || ret[ret_len - 1] != Token::Swap {
187            return;
188        }
189        let token = match &ret[ret_len - 2] {
190            Token::Hash20(x) => Token::Push(x.to_vec()),
191            Token::Bytes32(x) | Token::Bytes33(x) | Token::Bytes65(x) => Token::Push(x.to_vec()),
192            Token::Num(k) => Token::Push(build_scriptint(i64::from(*k))),
193            _x => return, // no change required
194        };
195        ret[ret_len - 2] = token;
196    }
197
198    for ins in script.instructions_minimal() {
199        match ins.map_err(Error::Script)? {
200            script::Instruction::Op(opcodes::all::OP_BOOLAND) => {
201                ret.push(Token::BoolAnd);
202            }
203            script::Instruction::Op(opcodes::all::OP_BOOLOR) => {
204                ret.push(Token::BoolOr);
205            }
206            script::Instruction::Op(opcodes::all::OP_EQUAL) => {
207                ret.push(Token::Equal);
208            }
209            script::Instruction::Op(opcodes::all::OP_EQUALVERIFY) => {
210                ret.push(Token::Equal);
211                ret.push(Token::Verify);
212            }
213            script::Instruction::Op(opcodes::all::OP_NUMEQUAL) => {
214                ret.push(Token::NumEqual);
215            }
216            script::Instruction::Op(opcodes::all::OP_NUMEQUALVERIFY) => {
217                ret.push(Token::NumEqual);
218                ret.push(Token::Verify);
219            }
220            script::Instruction::Op(opcodes::all::OP_CHECKSIG) => {
221                ret.push(Token::CheckSig);
222            }
223            script::Instruction::Op(opcodes::all::OP_CHECKSIGFROMSTACK) => {
224                ret.push(Token::CheckSigFromStack);
225            }
226            script::Instruction::Op(opcodes::all::OP_CHECKSIGFROMSTACKVERIFY) => {
227                ret.push(Token::CheckSigFromStackVerify);
228            }
229            script::Instruction::Op(opcodes::all::OP_CHECKSIGVERIFY) => {
230                ret.push(Token::CheckSig);
231                ret.push(Token::Verify);
232            }
233            script::Instruction::Op(opcodes::all::OP_CHECKSIGADD) => {
234                ret.push(Token::CheckSigAdd);
235            }
236            script::Instruction::Op(opcodes::all::OP_INSPECTINPUTVALUE) => {
237                ret.push(Token::InpValue);
238            }
239            script::Instruction::Op(opcodes::all::OP_INSPECTOUTPUTVALUE) => {
240                ret.push(Token::OutValue);
241            }
242            script::Instruction::Op(opcodes::all::OP_INSPECTINPUTASSET) => {
243                ret.push(Token::InpAsset);
244            }
245            script::Instruction::Op(opcodes::all::OP_INSPECTOUTPUTASSET) => {
246                ret.push(Token::OutAsset);
247            }
248            script::Instruction::Op(opcodes::all::OP_INSPECTINPUTSCRIPTPUBKEY) => {
249                ret.push(Token::InpSpk);
250            }
251            script::Instruction::Op(opcodes::all::OP_INSPECTOUTPUTSCRIPTPUBKEY) => {
252                ret.push(Token::OutSpk);
253            }
254            script::Instruction::Op(opcodes::all::OP_INSPECTINPUTISSUANCE) => {
255                ret.push(Token::InpIssue);
256            }
257            script::Instruction::Op(opcodes::all::OP_PUSHCURRENTINPUTINDEX) => {
258                ret.push(Token::CurrInp);
259            }
260            script::Instruction::Op(opcodes::all::OP_ADD64) => {
261                ret.push(Token::Add64);
262            }
263            script::Instruction::Op(opcodes::all::OP_SUB64) => {
264                ret.push(Token::Sub64);
265            }
266            script::Instruction::Op(opcodes::all::OP_MUL64) => {
267                ret.push(Token::Mul64);
268            }
269            script::Instruction::Op(opcodes::all::OP_DIV64) => {
270                ret.push(Token::Div64);
271            }
272            script::Instruction::Op(opcodes::all::OP_NEG64) => {
273                ret.push(Token::Neg64);
274            }
275            script::Instruction::Op(opcodes::all::OP_GREATERTHAN64) => {
276                ret.push(Token::Ge64);
277            }
278            script::Instruction::Op(opcodes::all::OP_GREATERTHANOREQUAL64) => {
279                ret.push(Token::Geq64);
280            }
281            script::Instruction::Op(opcodes::all::OP_LESSTHAN64) => {
282                ret.push(Token::Le64);
283            }
284            script::Instruction::Op(opcodes::all::OP_LESSTHANOREQUAL64) => {
285                ret.push(Token::Leq64);
286            }
287            script::Instruction::Op(opcodes::all::OP_AND) => {
288                ret.push(Token::And);
289            }
290            script::Instruction::Op(opcodes::all::OP_OR) => {
291                ret.push(Token::Or);
292            }
293            script::Instruction::Op(opcodes::all::OP_XOR) => {
294                ret.push(Token::Xor);
295            }
296            script::Instruction::Op(opcodes::all::OP_INVERT) => {
297                ret.push(Token::Invert);
298            }
299            script::Instruction::Op(opcodes::all::OP_SCRIPTNUMTOLE64) => {
300                ret.push(Token::ScriptNumToLe64);
301            }
302            script::Instruction::Op(opcodes::all::OP_LE64TOSCRIPTNUM) => {
303                ret.push(Token::Le64ToScriptNum);
304            }
305            script::Instruction::Op(opcodes::all::OP_CHECKMULTISIG) => {
306                ret.push(Token::CheckMultiSig);
307            }
308            script::Instruction::Op(opcodes::all::OP_CHECKMULTISIGVERIFY) => {
309                ret.push(Token::CheckMultiSig);
310                ret.push(Token::Verify);
311            }
312            script::Instruction::Op(op) if op == opcodes::all::OP_CSV => {
313                ret.push(Token::CheckSequenceVerify);
314            }
315            script::Instruction::Op(op) if op == opcodes::all::OP_CLTV => {
316                ret.push(Token::CheckLockTimeVerify);
317            }
318            script::Instruction::Op(opcodes::all::OP_FROMALTSTACK) => {
319                ret.push(Token::FromAltStack);
320            }
321            script::Instruction::Op(opcodes::all::OP_TOALTSTACK) => {
322                ret.push(Token::ToAltStack);
323            }
324            script::Instruction::Op(opcodes::all::OP_LEFT) => {
325                ret.push(Token::Left);
326            }
327            script::Instruction::Op(opcodes::all::OP_2DUP) => {
328                ret.push(Token::Dup2);
329            }
330            script::Instruction::Op(opcodes::all::OP_CAT) => {
331                process_candidate_push(&mut ret);
332                ret.push(Token::Cat);
333            }
334            script::Instruction::Op(opcodes::all::OP_CODESEPARATOR) => {
335                ret.push(Token::CodeSep);
336            }
337            script::Instruction::Op(opcodes::all::OP_OVER) => {
338                ret.push(Token::Over);
339            }
340            script::Instruction::Op(opcodes::all::OP_NIP) => {
341                ret.push(Token::Nip);
342            }
343            script::Instruction::Op(opcodes::all::OP_PICK) => {
344                ret.push(Token::Pick);
345            }
346            script::Instruction::Op(opcodes::all::OP_DROP) => {
347                ret.push(Token::Drop);
348            }
349            script::Instruction::Op(opcodes::all::OP_DEPTH) => {
350                ret.push(Token::Depth);
351            }
352            script::Instruction::Op(opcodes::all::OP_DUP) => {
353                ret.push(Token::Dup);
354            }
355            script::Instruction::Op(opcodes::all::OP_ADD) => {
356                ret.push(Token::Add);
357            }
358            script::Instruction::Op(opcodes::all::OP_SUB) => {
359                ret.push(Token::Sub);
360            }
361            script::Instruction::Op(opcodes::all::OP_IF) => {
362                ret.push(Token::If);
363            }
364            script::Instruction::Op(opcodes::all::OP_IFDUP) => {
365                ret.push(Token::IfDup);
366            }
367            script::Instruction::Op(opcodes::all::OP_NOTIF) => {
368                ret.push(Token::NotIf);
369            }
370            script::Instruction::Op(opcodes::all::OP_ELSE) => {
371                ret.push(Token::Else);
372            }
373            script::Instruction::Op(opcodes::all::OP_ENDIF) => {
374                ret.push(Token::EndIf);
375            }
376            script::Instruction::Op(opcodes::all::OP_0NOTEQUAL) => {
377                ret.push(Token::ZeroNotEqual);
378            }
379            script::Instruction::Op(opcodes::all::OP_SIZE) => {
380                ret.push(Token::Size);
381            }
382            script::Instruction::Op(opcodes::all::OP_SWAP) => {
383                ret.push(Token::Swap);
384            }
385            script::Instruction::Op(opcodes::all::OP_VERIFY) => {
386                match ret.last() {
387                    Some(op @ &Token::Equal)
388                    | Some(op @ &Token::CheckSig)
389                    | Some(op @ &Token::CheckMultiSig) => {
390                        return Err(Error::NonMinimalVerify(format!("{:?}", op)))
391                    }
392                    _ => {}
393                }
394                ret.push(Token::Verify);
395            }
396            script::Instruction::Op(opcodes::all::OP_RIPEMD160) => {
397                ret.push(Token::Ripemd160);
398            }
399            script::Instruction::Op(opcodes::all::OP_HASH160) => {
400                ret.push(Token::Hash160);
401            }
402            script::Instruction::Op(opcodes::all::OP_SHA256) => {
403                ret.push(Token::Sha256);
404            }
405            script::Instruction::Op(opcodes::all::OP_HASH256) => {
406                ret.push(Token::Hash256);
407            }
408            script::Instruction::PushBytes(bytes) => {
409                // Check for Pick Push
410                // Special handling of tokens for Covenants
411                // To determine whether some Token is actually
412                // 4 bytes push or a script int of 4 bytes,
413                // we need additional script context
414                if ret.last() == Some(&Token::Pick) {
415                    ret.pop().unwrap();
416                    match bytes.len() {
417                        // All other sighash elements are 32 bytes. And the script code
418                        // is 24 bytes
419                        4 => ret.push(Token::PickPush4(slice_to_u32_le(bytes))),
420                        32 => {
421                            let mut x = [0u8; 32];
422                            x.copy_from_slice(bytes);
423                            ret.push(Token::PickPush32(x));
424                        }
425                        // Other pushes should be err. This will change
426                        // once we add script introspection
427                        _ => return Err(Error::InvalidPush(bytes.to_owned())),
428                    }
429                } else {
430                    // Create the most specific type possible out of the
431                    // Push. When we later encounter CAT, revisit and
432                    // reconvert these to pushes.
433                    // See [process_candidate_push]
434                    match bytes.len() {
435                        8 => ret.push(Token::Bytes8(bytes)),
436                        20 => ret.push(Token::Hash20(bytes)),
437                        32 => ret.push(Token::Bytes32(bytes)),
438                        33 => ret.push(Token::Bytes33(bytes)),
439                        65 => ret.push(Token::Bytes65(bytes)),
440                        _ => {
441                            match script::read_scriptint(bytes) {
442                                Ok(v) if v >= 0 => {
443                                    // check minimality of the number
444                                    if &script::Builder::new().push_int(v).into_script()[1..]
445                                        != bytes
446                                    {
447                                        return Err(Error::InvalidPush(bytes.to_owned()));
448                                    }
449                                    ret.push(Token::Num(v as u32));
450                                }
451                                _ => ret.push(Token::Push(bytes.to_owned())),
452                            }
453                        }
454                    }
455                }
456            }
457            script::Instruction::Op(opcodes::all::OP_PUSHNUM_NEG1) => {
458                ret.push(Token::NumNeg1);
459            }
460            script::Instruction::Op(opcodes::all::OP_PUSHBYTES_0) => {
461                ret.push(Token::Num(0));
462            }
463            script::Instruction::Op(opcodes::all::OP_PUSHNUM_1) => {
464                ret.push(Token::Num(1));
465            }
466            script::Instruction::Op(opcodes::all::OP_PUSHNUM_2) => {
467                ret.push(Token::Num(2));
468            }
469            script::Instruction::Op(opcodes::all::OP_PUSHNUM_3) => {
470                ret.push(Token::Num(3));
471            }
472            script::Instruction::Op(opcodes::all::OP_PUSHNUM_4) => {
473                ret.push(Token::Num(4));
474            }
475            script::Instruction::Op(opcodes::all::OP_PUSHNUM_5) => {
476                ret.push(Token::Num(5));
477            }
478            script::Instruction::Op(opcodes::all::OP_PUSHNUM_6) => {
479                ret.push(Token::Num(6));
480            }
481            script::Instruction::Op(opcodes::all::OP_PUSHNUM_7) => {
482                ret.push(Token::Num(7));
483            }
484            script::Instruction::Op(opcodes::all::OP_PUSHNUM_8) => {
485                ret.push(Token::Num(8));
486            }
487            script::Instruction::Op(opcodes::all::OP_PUSHNUM_9) => {
488                ret.push(Token::Num(9));
489            }
490            script::Instruction::Op(opcodes::all::OP_PUSHNUM_10) => {
491                ret.push(Token::Num(10));
492            }
493            script::Instruction::Op(opcodes::all::OP_PUSHNUM_11) => {
494                ret.push(Token::Num(11));
495            }
496            script::Instruction::Op(opcodes::all::OP_PUSHNUM_12) => {
497                ret.push(Token::Num(12));
498            }
499            script::Instruction::Op(opcodes::all::OP_PUSHNUM_13) => {
500                ret.push(Token::Num(13));
501            }
502            script::Instruction::Op(opcodes::all::OP_PUSHNUM_14) => {
503                ret.push(Token::Num(14));
504            }
505            script::Instruction::Op(opcodes::all::OP_PUSHNUM_15) => {
506                ret.push(Token::Num(15));
507            }
508            script::Instruction::Op(opcodes::all::OP_PUSHNUM_16) => {
509                ret.push(Token::Num(16));
510            }
511            script::Instruction::Op(op) => return Err(Error::InvalidOpcode(op)),
512        };
513    }
514    Ok(ret)
515}
elements_miniscript/miniscript/lex.rs

elements_miniscript/miniscript/
lex.rs
