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
125
126
127

// Wallet-level libraries for bitcoin protocol by LNP/BP Association
//
// Written in 2020-2022 by
//     Dr. Maxim Orlovsky <orlovsky@lnp-bp.org>
//
// This software is distributed without any warranty.
//
// You should have received a copy of the Apache-2.0 License
// along with this software.
// If not, see <https://opensource.org/licenses/Apache-2.0>.

//! Lexicographic sorting functions.

use std::cmp::Ordering;

use bitcoin::{secp256k1, Transaction, TxIn, TxOut};

use crate::v0::PsbtV0;
use crate::{Input, Output, Psbt};

pub trait LexOrder {
    fn lex_order(&mut self);

    fn lex_ordered(mut self) -> Self
    where
        Self: Sized,
    {
        self.lex_order();
        self
    }
}

impl LexOrder for Vec<secp256k1::PublicKey> {
    fn lex_order(&mut self) { self.sort() }
}

impl LexOrder for Vec<bitcoin::PublicKey> {
    fn lex_order(&mut self) { self.sort() }
}

impl LexOrder for Vec<TxIn> {
    fn lex_order(&mut self) { self.sort_by_key(|txin| txin.previous_output) }
}

impl LexOrder for Vec<TxOut> {
    fn lex_order(&mut self) { self.sort_by(txout_cmp) }
}

impl LexOrder for Transaction {
    fn lex_order(&mut self) {
        self.input.lex_order();
        self.output.lex_order();
    }
}

impl LexOrder for Vec<(TxOut, crate::v0::OutputV0)> {
    fn lex_order(&mut self) { self.sort_by(|(a, _), (b, _)| txout_cmp(a, b)); }
}

impl LexOrder for PsbtV0 {
    fn lex_order(&mut self) {
        let tx = &mut self.unsigned_tx;
        let mut inputs = tx
            .input
            .clone()
            .into_iter()
            .zip(self.inputs.clone())
            .collect::<Vec<(_, _)>>();
        inputs.sort_by_key(|(k, _)| k.previous_output);

        let mut outputs = tx
            .output
            .clone()
            .into_iter()
            .zip(self.outputs.clone())
            .collect::<Vec<(_, _)>>();
        outputs.lex_order();

        let (in_tx, in_map): (Vec<_>, Vec<_>) = inputs.into_iter().unzip();
        let (out_tx, out_map): (Vec<_>, Vec<_>) = outputs.into_iter().unzip();
        tx.input = in_tx;
        tx.output = out_tx;
        self.inputs = in_map;
        self.outputs = out_map;
    }
}

impl LexOrder for Vec<Input> {
    fn lex_order(&mut self) {
        self.sort_by_key(|input| input.previous_outpoint);
        for (index, input) in self.iter_mut().enumerate() {
            input.index = index;
        }
    }
}

impl LexOrder for Vec<Output> {
    fn lex_order(&mut self) {
        self.sort_by(psbtout_cmp);
        for (index, output) in self.iter_mut().enumerate() {
            output.index = index;
        }
    }
}

impl LexOrder for Psbt {
    fn lex_order(&mut self) {
        self.inputs.lex_order();
        self.outputs.lex_order();
    }
}

fn txout_cmp(left: &TxOut, right: &TxOut) -> Ordering {
    match (left.value, right.value) {
        (l, r) if l < r => Ordering::Less,
        (l, r) if l > r => Ordering::Greater,
        _ => left.script_pubkey.cmp(&right.script_pubkey),
    }
}

fn psbtout_cmp(left: &Output, right: &Output) -> Ordering {
    match (left.amount, right.amount) {
        (l, r) if l < r => Ordering::Less,
        (l, r) if l > r => Ordering::Greater,
        _ => left.script.cmp(&right.script),
    }
}