1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

//! Representation of mempool transactions' dependencies on other transactions in the mempool.

use std::collections::{HashMap, HashSet};

use zebra_chain::{transaction, transparent};

/// Representation of mempool transactions' dependencies on other transactions in the mempool.
#[derive(Default, Debug, Clone)]
pub struct TransactionDependencies {
    /// Lists of mempool transaction ids that create UTXOs spent by
    /// a mempool transaction. Used during block template construction
    /// to exclude transactions from block templates unless all of the
    /// transactions they depend on have been included.
    dependencies: HashMap<transaction::Hash, HashSet<transaction::Hash>>,

    /// Lists of transaction ids in the mempool that spend UTXOs created
    /// by a transaction in the mempool, e.g. tx1 -> set(tx2, tx3, tx4) where
    /// tx2, tx3, and tx4 spend outputs created by tx1.
    dependents: HashMap<transaction::Hash, HashSet<transaction::Hash>>,
}

impl TransactionDependencies {
    /// Adds a transaction that spends outputs created by other transactions in the mempool
    /// as a dependent of those transactions, and adds the transactions that created the outputs
    /// spent by the dependent transaction as dependencies of the dependent transaction.
    ///
    /// # Correctness
    ///
    /// It's the caller's responsibility to ensure that there are no cyclical dependencies.
    ///
    /// The transaction verifier will wait until the spent output of a transaction has been added to the verified set,
    /// so its `AwaitOutput` requests will timeout if there is a cyclical dependency.
    pub fn add(
        &mut self,
        dependent: transaction::Hash,
        spent_mempool_outpoints: Vec<transparent::OutPoint>,
    ) {
        for &spent_mempool_outpoint in &spent_mempool_outpoints {
            self.dependents
                .entry(spent_mempool_outpoint.hash)
                .or_default()
                .insert(dependent);
        }

        // Only add an entries to `dependencies` for transactions that spend unmined outputs so it
        // can be used to handle transactions with dependencies differently during block production.
        if !spent_mempool_outpoints.is_empty() {
            self.dependencies.insert(
                dependent,
                spent_mempool_outpoints
                    .into_iter()
                    .map(|outpoint| outpoint.hash)
                    .collect(),
            );
        }
    }

    /// Removes all dependents for a list of mined transaction ids and removes the mined transaction ids
    /// from the dependencies of their dependents.
    pub fn clear_mined_dependencies(&mut self, mined_ids: &HashSet<transaction::Hash>) {
        for mined_tx_id in mined_ids {
            for dependent_id in self.dependents.remove(mined_tx_id).unwrap_or_default() {
                let Some(dependencies) = self.dependencies.get_mut(&dependent_id) else {
                    // TODO: Move this struct to zebra-chain and log a warning here.
                    continue;
                };

                // TODO: Move this struct to zebra-chain and log a warning here if the dependency was not found.
                let _ = dependencies.remove(&dependent_id);
            }
        }
    }

    /// Removes the hash of a transaction in the mempool and the hashes of any transactions
    /// that are tracked as being directly or indirectly dependent on that transaction from
    /// this [`TransactionDependencies`].
    ///
    /// Returns a list of transaction hashes that were being tracked as dependents of the
    /// provided transaction hash.
    pub fn remove_all(&mut self, &tx_hash: &transaction::Hash) -> HashSet<transaction::Hash> {
        let mut all_dependents = HashSet::new();
        let mut current_level_dependents: HashSet<_> = [tx_hash].into();

        while !current_level_dependents.is_empty() {
            current_level_dependents = current_level_dependents
                .iter()
                .flat_map(|dep| {
                    self.dependencies.remove(dep);
                    self.dependents.remove(dep).unwrap_or_default()
                })
                .collect();

            all_dependents.extend(&current_level_dependents);
        }

        all_dependents
    }

    /// Returns a list of hashes of transactions that directly depend on the transaction for `tx_hash`.
    pub fn direct_dependents(&self, tx_hash: &transaction::Hash) -> HashSet<transaction::Hash> {
        self.dependents.get(tx_hash).cloned().unwrap_or_default()
    }

    /// Returns a list of hashes of transactions that are direct dependencies of the transaction for `tx_hash`.
    pub fn direct_dependencies(&self, tx_hash: &transaction::Hash) -> HashSet<transaction::Hash> {
        self.dependencies.get(tx_hash).cloned().unwrap_or_default()
    }

    /// Clear the maps of transaction dependencies.
    pub fn clear(&mut self) {
        self.dependencies.clear();
        self.dependents.clear();
    }

    /// Returns the map of transaction's dependencies
    pub fn dependencies(&self) -> &HashMap<transaction::Hash, HashSet<transaction::Hash>> {
        &self.dependencies
    }

    /// Returns the map of transaction's dependents
    pub fn dependents(&self) -> &HashMap<transaction::Hash, HashSet<transaction::Hash>> {
        &self.dependents
    }
}