bitcoin_script_analyzer/
condition_stack.rs

1// From the Bitcoin Core source code, file src/script/interpreter.cpp at commit b1a2021f78099c17360dc2179cbcb948059b5969
2// Edited for use in this software
3
4// Orignal Bitcoin Core copyright header:
5// Copyright (c) 2009-2010 Satoshi Nakamoto
6// Copyright (c) 2009-2021 The Bitcoin Core developers
7// Distributed under the MIT software license, see the accompanying
8// file COPYING or http://www.opensource.org/licenses/mit-license.php.
9
10/// A data type to abstract out the condition stack during script execution.
11///
12/// Conceptually it acts like a vector of booleans, one for each level of nested
13/// IF/THEN/ELSE, indicating whether we're in the active or inactive branch of
14/// each.
15///
16/// The elements on the stack cannot be observed individually; we only need to
17/// expose whether the stack is empty and whether or not any false values are
18/// present at all. To implement OP_ELSE, a toggle_top modifier is added, which
19/// flips the last value without returning it.
20///
21/// This uses an optimized implementation that does not materialize the
22/// actual stack. Instead, it just stores the size of the would-be stack,
23/// and the position of the first false value in it.
24#[derive(Clone)]
25pub struct ConditionStack {
26    /// The size of the implied stack.
27    m_stack_size: u32,
28    /// The position of the first false value on the implied stack, or NO_FALSE if all true.
29    m_first_false_pos: u32,
30}
31
32impl ConditionStack {
33    /// A constant for m_first_false_pos to indicate there are no falses.
34    const NO_FALSE: u32 = u32::MAX;
35
36    pub fn new() -> Self {
37        Self {
38            m_stack_size: 0,
39            m_first_false_pos: Self::NO_FALSE,
40        }
41    }
42
43    pub fn empty(&self) -> bool {
44        self.m_stack_size == 0
45    }
46
47    pub fn all_true(&self) -> bool {
48        self.m_first_false_pos == Self::NO_FALSE
49    }
50
51    pub fn push_back(&mut self, f: bool) {
52        if self.m_first_false_pos == Self::NO_FALSE && !f {
53            // The stack consists of all true values, and a false is added.
54            // The first false value will appear at the current size.
55            self.m_first_false_pos = self.m_stack_size;
56        }
57        self.m_stack_size += 1;
58    }
59
60    pub fn pop_back(&mut self) {
61        self.m_stack_size -= 1;
62        if self.m_first_false_pos == self.m_stack_size {
63            // When popping off the first false value, everything becomes true.
64            self.m_first_false_pos = Self::NO_FALSE;
65        }
66    }
67
68    pub fn toggle_top(&mut self) {
69        if self.m_first_false_pos == Self::NO_FALSE {
70            // The current stack is all true values; the first false will be the top.
71            self.m_first_false_pos = self.m_stack_size - 1;
72        } else if self.m_first_false_pos == self.m_stack_size - 1 {
73            // The top is the first false value; toggling it will make everything true.
74            self.m_first_false_pos = Self::NO_FALSE;
75        } // else {
76          // There is a false value, but not on top. No action is needed as toggling
77          // anything but the first false value is unobservable.
78          // }
79    }
80}
bitcoin_script_analyzer/condition_stack.rs

bitcoin_script_analyzer/
condition_stack.rs
