Merge pull request #11091 from f321x/fix_num_parents_perf_simple

### electrum/gui/qt/utxo_dialog.py
@@ -24,7 +24,6 @@
 # SOFTWARE.
 
 from typing import TYPE_CHECKING
-import copy
 
 from PyQt6.QtCore import Qt, QUrl
 from PyQt6.QtGui import QTextCharFormat, QFont
@@ -78,15 +77,16 @@ def __init__(self, window: 'ElectrumWindow', utxo: 'PartialTxInput'):
         vbox.addLayout(legend_hbox)
         vbox.addLayout(Buttons(CloseButton(self)))
         self.setLayout(vbox)
+        self.parents = self.wallet.get_tx_parents(self.utxo.prevout.txid.hex())
         self.update()
         self.main_window.labels_changed_signal.connect(self.update)
 
     def update(self):
 
         txid = self.utxo.prevout.txid.hex()
-        parents = self.wallet.get_tx_parents(txid)
+        parents = self.parents
         num_parents = len(parents)
-        parents_copy = copy.deepcopy(parents)
+        parents_copy = dict(parents)
         cursor = self.parents_list.textCursor()
         ext = QTextCharFormat()
 

### electrum/wallet.py
@@ -27,6 +27,7 @@
 #   - Multisig_Wallet: several HD keystores, M-of-N OP_CHECKMULTISIG scripts
 
 import os
+import bisect
 import random
 import time
 import copy
@@ -435,7 +436,6 @@ def __init__(self, db: WalletDB, *, config: SimpleConfig):
             self.adb.add_address(addr)
         self.lock = self.adb.lock
         self._last_full_history = None
-        self._tx_parents_cache = {}
         self._paid_invoice_keys_cache = set()  # type: Set[str]
         self._coin_price_cache = {}
         self._default_labels = {}
@@ -641,7 +641,6 @@ def tx_is_related(self, tx):
 
     def clear_tx_parents_cache(self):
         with self.lock:
-            self._tx_parents_cache.clear()
             self._num_parents.clear()
             self._last_full_history = None
 
@@ -1091,51 +1090,55 @@ def get_num_parents(self, txid: str) -> Optional[int]:
 
     def get_tx_parents(self, txid: str) -> Dict[str, Tuple[List[str], List[str]]]:
         """
-        returns a flat dict:
-        txid -> list of parent txids
+        returns a flat dict, for txid and its ancestors in the wallet history:
+        txid -> (list of parent txids, list of uncle txids)
+        uncles are the txs that funded other coins of an input address,
+        if those coins were spent by a mined tx before txid (address reuse)
         """
+
+        def _get_spent_coins(addr_: str) -> Tuple[List[Tuple[int, int]], List[str]]:
+            """Returns the coins of addr that were spent by a mined tx, in the order they were spent:
+            the (height, txpos) of the spending txs, and the txids that funded the coins.
+            """
+            received, sent = self.adb.get_addr_io(addr_)
+            spends = sorted(
+                ((height, txpos), prevout_str.split(':')[0])
+                for prevout_str, (spending_txid, height, txpos) in sent.items()
+                if height > 0
+            )
+            return [key_ for key_, _ in spends], [txid_ for _, txid_ in spends]
+
         with self.lock:
             if self._last_full_history is None:
                 self._last_full_history = self.get_onchain_history()
-                # populate cache in chronological order (confirmed tx only)
-                # todo: get_full_history should return unconfirmed tx topologically sorted
-                for _txid, tx_item in self._last_full_history.items():
-                    if tx_item.tx_mined_status.height() > 0:
-                        self.get_tx_parents(_txid)
-
-            result = self._tx_parents_cache.get(txid, None)
-            if result is not None:
-                return result
-            result = {}   # type: Dict[str, Tuple[List[str], List[str]]]
-            parents = []  # type: List[str]
-            uncles = []   # type: List[str]
-            tx = self.adb.get_transaction(txid)
-            assert tx, f"cannot find {txid} in db"
-            for i, txin in enumerate(tx.inputs()):
-                _txid = txin.prevout.txid.hex()
-                parents.append(_txid)
-                # detect address reuse
-                addr = self.adb.get_txin_address(txin)
-                if addr is None:
+            result = {}  # type: Dict[str, Tuple[List[str], List[str]]]
+            spent_coins = {}  # addr -> _get_spent_coins(addr)
+            num_uncles = defaultdict(int)  # addr -> number of funding txs of spent_coins[addr] added to todo
+            todo = [txid]
+            while todo:
+                _txid = todo.pop()
+                if _txid in result:
                     continue
-                received, sent = self.adb.get_addr_io(addr)
-                if len(sent) > 1:
-                    my_txid, my_height, my_pos = sent[txin.prevout.to_str()]
-                    assert my_txid == txid
-                    for k, v in sent.items():
-                        if k != txin.prevout.to_str():
-                            reuse_txid, reuse_height, reuse_pos = v
-                            if reuse_height <= 0:  # exclude not-yet-mined (we need topological ordering)
-                                continue
-                            if (reuse_height, reuse_pos) < (my_height, my_pos):
-                                uncle_txid, uncle_index = k.split(':')
-                                uncles.append(uncle_txid)
-
-            for _txid in parents + uncles:
-                if _txid in self._last_full_history.keys():
-                    result.update(self.get_tx_parents(_txid))
-            result[txid] = parents, uncles
-            self._tx_parents_cache[txid] = result
+                tx = self.db.get_transaction(_txid)
+                assert tx, f"cannot find {_txid} in db"
+                tx_mined_info = self.adb.get_tx_height(_txid)
+                key = tx_mined_info.height(), tx_mined_info.txpos if tx_mined_info.txpos is not None else -1
+                parents = [txin.prevout.txid.hex() for txin in tx.inputs()]
+                uncles = []  # type: List[str]
+                for txin in tx.inputs():
+                    addr = self.adb.get_txin_address(txin)
+                    if addr is None:
+                        continue
+                    if addr not in spent_coins:
+                        spent_coins[addr] = _get_spent_coins(addr)
+                    keys, funding_txids = spent_coins[addr]
+                    n = bisect.bisect_left(keys, key)  # number of coins spent before _txid (0 if unmined)
+                    uncles += funding_txids[:n]
+                    # the uncles of earlier spends from addr are a prefix of these, add them to todo only once
+                    todo.extend(x for x in funding_txids[num_uncles[addr]:n] if x in self._last_full_history)
+                    num_uncles[addr] = max(num_uncles[addr], n)
+                result[_txid] = parents, uncles
+                todo.extend(x for x in parents if x in self._last_full_history and x not in result)
             return result
 
     def get_balance(self, **kwargs):

### tests/test_wallet.py
@@ -22,8 +22,9 @@
 from electrum import util, storage
 from electrum.daemon import Daemon
 from electrum.invoices import PR_UNPAID, PR_PAID, PR_UNCONFIRMED
-from electrum.transaction import tx_from_any
+from electrum.transaction import tx_from_any, Transaction, PartialTransaction, PartialTxInput, PartialTxOutput, TxOutpoint
 from electrum.address_synchronizer import TX_HEIGHT_UNCONFIRMED
+from electrum import bitcoin
 
 from . import ElectrumTestCase
 from . import restore_wallet_from_text__for_unittest
@@ -482,3 +483,35 @@ async def test_update_password_with_app_restarts(self):
         with self.assertRaises(InvalidPassword):
             wallet.check_password("wrong password")
         wallet.check_password("1234")
+
+
+class TestTxParents(WalletTestCase):
+
+    async def test_num_parents_with_address_reuse(self):
+        a, b, c, d, external = [bitcoin.hash160_to_p2pkh(bytes([i]) * 20) for i in range(1, 6)]
+        wallet = restore_wallet_from_text__for_unittest(f'{a} {b} {c} {d}', path=None, config=self.config)['wallet']
+        wallet.db.put('stored_height', 1000)
+
+        def add_tx(prevouts, outputs, height=TX_HEIGHT_UNCONFIRMED, txpos=None) -> str:
+            inputs = [PartialTxInput(prevout=TxOutpoint.from_str(prevout)) for prevout in prevouts]
+            outputs = [PartialTxOutput.from_address_and_value(addr, value) for addr, value in outputs]
+            tx = Transaction(PartialTransaction.from_io(inputs, outputs, BIP69_sort=False).serialize_to_network(include_sigs=False))
+            wallet.adb.receive_tx_callback(tx, tx_height=height)
+            if height > 0:
+                wallet.adb.add_verified_tx(tx.txid(), TxMinedInfo(_height=height, timestamp=0, txpos=txpos, header_hash='00' * 32))
+            return tx.txid()
+
+        f1 = add_tx(['01' * 32 + ':0'], [(a, 1000)], height=100, txpos=1)
+        f2 = add_tx(['02' * 32 + ':0'], [(a, 2000), (b, 3000)], height=100, txpos=2)
+        s1 = add_tx([f1 + ':0'], [(external, 500), (c, 400)], height=101, txpos=1)
+        s2 = add_tx([f2 + ':0'], [(external, 1900)], height=102, txpos=1)  # reuses a: f1 is an uncle
+        s3 = add_tx([f2 + ':1', s1 + ':1'], [(d, 3300)], height=102, txpos=2)
+        u1 = add_tx([s3 + ':0'], [(c, 3200)])
+        u2 = add_tx([u1 + ':0'], [(external, 3100)])  # reuses c, but unmined: no uncles
+
+        self.assertEqual(([f1], []), wallet.get_tx_parents(s1)[s1])  # s2 spent from a later
+        self.assertEqual(([f2], [f1]), wallet.get_tx_parents(s2)[s2])
+        self.assertEqual(([u1], []), wallet.get_tx_parents(u2)[u2])
+        expected = {f1: 1, f2: 1, s1: 2, s2: 3, s3: 4, u1: 5, u2: 6}
+        for txid, num_parents in expected.items():
+            self.assertEqual(num_parents, len(wallet.get_tx_parents(txid)))