rpc: improve get_output_distribution

It can now handle small reorgs without having to rescan the
whole blockchain.

Also add a test for it.

3 files changed, 236 insertions, 12 deletions

diff --git a/tests/functional_tests/functional_tests_rpc.py b/tests/functional_tests/functional_tests_rpc.py
index 83b75a088..f080176dc 100755
--- a/tests/functional_tests/functional_tests_rpc.py
+++ b/tests/functional_tests/functional_tests_rpc.py
@@ -10,7 +10,7 @@ import string
 import os
 
 USAGE = 'usage: functional_tests_rpc.py <python> <srcdir> <builddir> [<tests-to-run> | all]'
-DEFAULT_TESTS = ['daemon_info', 'blockchain', 'wallet_address', 'integrated_address', 'mining', 'transfer', 'txpool', 'multisig', 'cold_signing', 'sign_message', 'proofs']
+DEFAULT_TESTS = ['daemon_info', 'blockchain', 'wallet_address', 'integrated_address', 'mining', 'transfer', 'txpool', 'multisig', 'cold_signing', 'sign_message', 'proofs', 'get_output_distribution']
 try:
   python = sys.argv[1]
   srcdir = sys.argv[2]
diff --git a/tests/functional_tests/get_output_distribution.py b/tests/functional_tests/get_output_distribution.py
new file mode 100755
index 000000000..2a0762d5e
--- /dev/null
+++ b/tests/functional_tests/get_output_distribution.py
@@ -0,0 +1,217 @@
+#!/usr/bin/env python3
+
+# Copyright (c) 2019 The Monero Project
+# 
+# All rights reserved.
+# 
+# Redistribution and use in source and binary forms, with or without modification, are
+# permitted provided that the following conditions are met:
+# 
+# 1. Redistributions of source code must retain the above copyright notice, this list of
+#    conditions and the following disclaimer.
+# 
+# 2. Redistributions in binary form must reproduce the above copyright notice, this list
+#    of conditions and the following disclaimer in the documentation and/or other
+#    materials provided with the distribution.
+# 
+# 3. Neither the name of the copyright holder nor the names of its contributors may be
+#    used to endorse or promote products derived from this software without specific
+#    prior written permission.
+# 
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
+# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+# THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+# STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+# THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+import time
+
+"""Test get_output_distribution RPC
+"""
+
+from framework.daemon import Daemon
+from framework.wallet import Wallet
+
+class GetOutputDistributionTest():
+    def run_test(self):
+        self.reset()
+        self.create()
+        self.test_get_output_distribution()
+
+    def reset(self):
+        print 'Resetting blockchain'
+        daemon = Daemon()
+        daemon.pop_blocks(1000)
+        daemon.flush_txpool()
+
+    def create(self):
+        self.wallet = Wallet()
+        # close the wallet if any, will throw if none is loaded
+        try: self.wallet.close_wallet()
+        except: pass
+        res = self.wallet.restore_deterministic_wallet(seed = 'velvet lymph giddy number token physics poetry unquoted nibs useful sabotage limits benches lifestyle eden nitrogen anvil fewest avoid batch vials washing fences goat unquoted')
+
+    def test_get_output_distribution(self):
+        print "Test get_output_distribution"
+
+        daemon = Daemon()
+
+        res = daemon.get_output_distribution([0], 0, 0)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 0
+        assert d.base == 0
+        assert d.binary == False
+        assert len(d.distribution) == 1
+        assert d.distribution[0] == 0
+
+        res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 1)
+
+        res = daemon.get_output_distribution([0], 0, 0)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 0
+        assert d.base == 0
+        assert d.binary == False
+        assert len(d.distribution) == 2
+        assert d.distribution[0] == 0
+        assert d.distribution[1] == 1
+
+        res = daemon.pop_blocks(1)
+
+        res = daemon.get_output_distribution([0], 0, 0)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 0
+        assert d.base == 0
+        assert d.binary == False
+        assert len(d.distribution) == 1
+        assert d.distribution[0] == 0
+
+        res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 3)
+
+        res = daemon.get_output_distribution([0], 0, 0, cumulative = True)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 0
+        assert d.base == 0
+        assert d.binary == False
+        assert len(d.distribution) == 4
+        assert d.distribution[0] == 0
+        assert d.distribution[1] == 1
+        assert d.distribution[2] == 2
+        assert d.distribution[3] == 3
+
+        # extend
+        res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 80)
+
+        res = daemon.get_output_distribution([0], 0, 0, cumulative = True)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 0
+        assert d.base == 0
+        assert d.binary == False
+        assert len(d.distribution) == 84
+        for h in range(len(d.distribution)):
+            assert d.distribution[h] == h
+
+        # pop and replace, this will do through the "trim and extend" path
+        res = daemon.pop_blocks(2)
+        self.wallet.refresh()
+        dst = {'address': '42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 'amount': 1000000000000}
+        self.wallet.transfer([dst])
+        res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 1)
+        for step in range(3): # the second will be cached, the third will also be cached, but we get it in non-cumulative mode
+            res = daemon.get_output_distribution([0], 0, 0, cumulative = step < 3)
+            assert len(res.distributions) == 1
+            d = res.distributions[0]
+            assert d.amount == 0
+            assert d.base == 0
+            assert d.binary == False
+            assert len(d.distribution) == 83
+            for h in range(len(d.distribution)):
+                assert d.distribution[h] == (h if step < 3 else 1) + (2 if h == len(d.distribution) - 1 else 0)
+
+        # start at 0, end earlier
+        res = daemon.get_output_distribution([0], 0, 40, cumulative = True)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 0
+        assert d.base == 0
+        assert d.binary == False
+        assert len(d.distribution) == 41
+        for h in range(len(d.distribution)):
+            assert d.distribution[h] == h
+
+        # start after 0, end earlier
+        res = daemon.get_output_distribution([0], 10, 20, cumulative = True)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 0
+        assert d.base == 9
+        assert d.binary == False
+        assert len(d.distribution) == 11
+        for h in range(len(d.distribution)):
+            assert d.distribution[h] == 10 + h
+
+        # straddling up
+        res = daemon.get_output_distribution([0], 15, 25, cumulative = True)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 0
+        assert d.base == 14
+        assert d.binary == False
+        assert len(d.distribution) == 11
+        for h in range(len(d.distribution)):
+            assert d.distribution[h] == 15 + h
+
+        # straddling down
+        res = daemon.get_output_distribution([0], 8, 18, cumulative = True)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 0
+        assert d.base == 7
+        assert d.binary == False
+        assert len(d.distribution) == 11
+        for h in range(len(d.distribution)):
+            assert d.distribution[h] == 8 + h
+
+        # encompassing
+        res = daemon.get_output_distribution([0], 5, 20, cumulative = True)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 0
+        assert d.base == 4
+        assert d.binary == False
+        assert len(d.distribution) == 16
+        for h in range(len(d.distribution)):
+            assert d.distribution[h] == 5 + h
+
+        # single
+        res = daemon.get_output_distribution([0], 2, 2, cumulative = True)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 0
+        assert d.base == 1
+        assert d.binary == False
+        assert len(d.distribution) == 1
+        assert d.distribution[0] == 2
+
+        # a non existent amount
+        res = daemon.get_output_distribution([1], 0, 0)
+        assert len(res.distributions) == 1
+        d = res.distributions[0]
+        assert d.amount == 1
+        assert d.base == 0
+        assert d.binary == False
+        assert len(d.distribution) == 83
+        for h in range(len(d.distribution)):
+            assert d.distribution[h] == 0
+
+
+if __name__ == '__main__':
+    GetOutputDistributionTest().run_test()
diff --git a/tests/unit_tests/output_distribution.cpp b/tests/unit_tests/output_distribution.cpp
index 45f2c135b..196fc949c 100644
--- a/tests/unit_tests/output_distribution.cpp
+++ b/tests/unit_tests/output_distribution.cpp
@@ -84,36 +84,43 @@ bool get_output_distribution(uint64_t amount, uint64_t from, uint64_t to, uint64
   return r && bc->get_output_distribution(amount, from, to, start_height, distribution, base);
 }
 
+crypto::hash get_block_hash(uint64_t height)
+{
+  crypto::hash hash;
+  *((uint64_t*)&hash) = height;
+  return hash;
+}
+
 TEST(output_distribution, extend)
 {
   boost::optional<cryptonote::rpc::output_distribution_data> res;
 
-  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, false);
+  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, ::get_block_hash, false, test_distribution_size);
   ASSERT_TRUE(res != boost::none);
   ASSERT_EQ(res->distribution.size(), 2);
   ASSERT_EQ(res->distribution, std::vector<uint64_t>({5, 0}));
 
-  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, true);
+  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, ::get_block_hash, true, test_distribution_size);
   ASSERT_TRUE(res != boost::none);
   ASSERT_EQ(res->distribution.size(), 2);
   ASSERT_EQ(res->distribution, std::vector<uint64_t>({55, 55}));
 
-  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, false);
+  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, ::get_block_hash, false, test_distribution_size);
   ASSERT_TRUE(res != boost::none);
   ASSERT_EQ(res->distribution.size(), 3);
   ASSERT_EQ(res->distribution, std::vector<uint64_t>({5, 0, 2}));
 
-  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, true);
+  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, ::get_block_hash, true, test_distribution_size);
   ASSERT_TRUE(res != boost::none);
   ASSERT_EQ(res->distribution.size(), 3);
   ASSERT_EQ(res->distribution, std::vector<uint64_t>({55, 55, 57}));
 
-  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, false);
+  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, ::get_block_hash, false, test_distribution_size);
   ASSERT_TRUE(res != boost::none);
   ASSERT_EQ(res->distribution.size(), 4);
   ASSERT_EQ(res->distribution, std::vector<uint64_t>({5, 0, 2, 3}));
 
-  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, true);
+  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, ::get_block_hash, true, test_distribution_size);
   ASSERT_TRUE(res != boost::none);
   ASSERT_EQ(res->distribution.size(), 4);
   ASSERT_EQ(res->distribution, std::vector<uint64_t>({55, 55, 57, 60}));
@@ -123,7 +130,7 @@ TEST(output_distribution, one)
 {
   boost::optional<cryptonote::rpc::output_distribution_data> res;
 
-  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 0, false);
+  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 0, ::get_block_hash, false, test_distribution_size);
   ASSERT_TRUE(res != boost::none);
   ASSERT_EQ(res->distribution.size(), 1);
   ASSERT_EQ(res->distribution.back(), 0);
@@ -133,7 +140,7 @@ TEST(output_distribution, full_cumulative)
 {
   boost::optional<cryptonote::rpc::output_distribution_data> res;
 
-  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, true);
+  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, ::get_block_hash, true, test_distribution_size);
   ASSERT_TRUE(res != boost::none);
   ASSERT_EQ(res->distribution.size(), 32);
   ASSERT_EQ(res->distribution.back(), 60);
@@ -143,7 +150,7 @@ TEST(output_distribution, full_noncumulative)
 {
   boost::optional<cryptonote::rpc::output_distribution_data> res;
 
-  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, false);
+  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, ::get_block_hash, false, test_distribution_size);
   ASSERT_TRUE(res != boost::none);
   ASSERT_EQ(res->distribution.size(), 32);
   for (size_t i = 0; i < 32; ++i)
@@ -154,7 +161,7 @@ TEST(output_distribution, part_cumulative)
 {
   boost::optional<cryptonote::rpc::output_distribution_data> res;
 
-  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, true);
+  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, ::get_block_hash, true, test_distribution_size);
   ASSERT_TRUE(res != boost::none);
   ASSERT_EQ(res->distribution.size(), 5);
   ASSERT_EQ(res->distribution, std::vector<uint64_t>({0, 1, 6, 7, 11}));
@@ -164,7 +171,7 @@ TEST(output_distribution, part_noncumulative)
 {
   boost::optional<cryptonote::rpc::output_distribution_data> res;
 
-  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, false);
+  res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, ::get_block_hash, false, test_distribution_size);
   ASSERT_TRUE(res != boost::none);
   ASSERT_EQ(res->distribution.size(), 5);
   ASSERT_EQ(res->distribution, std::vector<uint64_t>({0, 1, 5, 1, 4}));