# HG changeset patch
# User Luke Dashjr <luke-jr+git@utopios.org>
# Date 1338159969 0
# Node ID a0faaa0a6f523627d8dd4260d6169de44c0b2ade
# Parent  2eaf5522a4e89b8ac51a1c3d81955b3115b1ebde
Store a fixed order of transactions (and accounting) in the wallet

For backward compatibility, new accounting data is stored after a \0 in the comment string.
This way, old versions and third-party software should load and store them, but all actual use (listtransactions, for example) ignores it.

diff --git a/src/rpcwallet.cpp b/src/rpcwallet.cpp
--- a/src/rpcwallet.cpp
+++ b/src/rpcwallet.cpp
@@ -542,6 +542,7 @@
 
     // Debit
     CAccountingEntry debit;
+    debit.nOrderPos = pwalletMain->nOrderPosNext++;
     debit.strAccount = strFrom;
     debit.nCreditDebit = -nAmount;
     debit.nTime = nNow;
@@ -551,6 +552,7 @@
 
     // Credit
     CAccountingEntry credit;
+    credit.nOrderPos = pwalletMain->nOrderPosNext++;
     credit.strAccount = strTo;
     credit.nCreditDebit = nAmount;
     credit.nTime = nNow;
@@ -984,27 +986,27 @@
     Array ret;
     CWalletDB walletdb(pwalletMain->strWalletFile);
 
-    // First: get all CWalletTx and CAccountingEntry into a sorted-by-time multimap.
+    // First: get all CWalletTx and CAccountingEntry into a sorted-by-order multimap.
     typedef pair<CWalletTx*, CAccountingEntry*> TxPair;
     typedef multimap<int64, TxPair > TxItems;
-    TxItems txByTime;
+    TxItems txOrdered;
 
     // Note: maintaining indices in the database of (account,time) --> txid and (account, time) --> acentry
     // would make this much faster for applications that do this a lot.
     for (map<uint256, CWalletTx>::iterator it = pwalletMain->mapWallet.begin(); it != pwalletMain->mapWallet.end(); ++it)
     {
         CWalletTx* wtx = &((*it).second);
-        txByTime.insert(make_pair(wtx->GetTxTime(), TxPair(wtx, (CAccountingEntry*)0)));
+        txOrdered.insert(make_pair(wtx->nOrderPos, TxPair(wtx, (CAccountingEntry*)0)));
     }
     list<CAccountingEntry> acentries;
     walletdb.ListAccountCreditDebit(strAccount, acentries);
     BOOST_FOREACH(CAccountingEntry& entry, acentries)
     {
-        txByTime.insert(make_pair(entry.nTime, TxPair((CWalletTx*)0, &entry)));
+        txOrdered.insert(make_pair(entry.nOrderPos, TxPair((CWalletTx*)0, &entry)));
     }
 
     // iterate backwards until we have nCount items to return:
-    for (TxItems::reverse_iterator it = txByTime.rbegin(); it != txByTime.rend(); ++it)
+    for (TxItems::reverse_iterator it = txOrdered.rbegin(); it != txOrdered.rend(); ++it)
     {
         CWalletTx *const pwtx = (*it).second.first;
         if (pwtx != 0)
diff --git a/src/test/accounting_tests.cpp b/src/test/accounting_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/test/accounting_tests.cpp
@@ -0,0 +1,123 @@
+#include <boost/test/unit_test.hpp>
+
+#include <boost/foreach.hpp>
+
+#include "init.h"
+#include "wallet.h"
+#include "walletdb.h"
+
+BOOST_AUTO_TEST_SUITE(accounting_tests)
+
+static void
+GetResults(CWalletDB& walletdb, std::map<int64, CAccountingEntry>& results)
+{
+    std::list<CAccountingEntry> aes;
+
+    results.clear();
+    BOOST_CHECK(walletdb.ReorderTransactions(pwalletMain) == DB_LOAD_OK);
+    walletdb.ListAccountCreditDebit("", aes);
+    BOOST_FOREACH(CAccountingEntry& ae, aes)
+    {
+        results[ae.nOrderPos] = ae;
+    }
+}
+
+BOOST_AUTO_TEST_CASE(acc_orderupgrade)
+{
+    CWalletDB walletdb(pwalletMain->strWalletFile);
+    std::vector<CWalletTx*> vpwtx;
+    CWalletTx wtx;
+    CAccountingEntry ae;
+    std::map<int64, CAccountingEntry> results;
+
+    ae.strAccount = "";
+    ae.nCreditDebit = 1;
+    ae.nTime = 1333333333;
+    ae.strOtherAccount = "b";
+    ae.strComment = "";
+    walletdb.WriteAccountingEntry(ae);
+
+    wtx.mapValue["comment"] = "z";
+    pwalletMain->AddToWallet(wtx);
+    vpwtx.push_back(&pwalletMain->mapWallet[wtx.GetHash()]);
+    vpwtx[0]->nTimeReceived = (unsigned int)1333333335;
+    vpwtx[0]->nOrderPos = -1;
+
+    ae.nTime = 1333333336;
+    ae.strOtherAccount = "c";
+    walletdb.WriteAccountingEntry(ae);
+
+    GetResults(walletdb, results);
+
+    BOOST_CHECK(pwalletMain->nOrderPosNext == 3);
+    BOOST_CHECK(2 == results.size());
+    BOOST_CHECK(results[0].nTime == 1333333333);
+    BOOST_CHECK(results[0].strComment.empty());
+    BOOST_CHECK(1 == vpwtx[0]->nOrderPos);
+    BOOST_CHECK(results[2].nTime == 1333333336);
+    BOOST_CHECK(results[2].strOtherAccount == "c");
+
+
+    ae.nTime = 1333333330;
+    ae.strOtherAccount = "d";
+    ae.nOrderPos = pwalletMain->nOrderPosNext++;
+    walletdb.WriteAccountingEntry(ae);
+
+    GetResults(walletdb, results);
+
+    BOOST_CHECK(results.size() == 3);
+    BOOST_CHECK(pwalletMain->nOrderPosNext == 4);
+    BOOST_CHECK(results[0].nTime == 1333333333);
+    BOOST_CHECK(1 == vpwtx[0]->nOrderPos);
+    BOOST_CHECK(results[2].nTime == 1333333336);
+    BOOST_CHECK(results[3].nTime == 1333333330);
+    BOOST_CHECK(results[3].strComment.empty());
+
+
+    wtx.mapValue["comment"] = "y";
+    --wtx.nLockTime;  // Just to change the hash :)
+    pwalletMain->AddToWallet(wtx);
+    vpwtx.push_back(&pwalletMain->mapWallet[wtx.GetHash()]);
+    vpwtx[1]->nTimeReceived = (unsigned int)1333333336;
+
+    wtx.mapValue["comment"] = "x";
+    --wtx.nLockTime;  // Just to change the hash :)
+    pwalletMain->AddToWallet(wtx);
+    vpwtx.push_back(&pwalletMain->mapWallet[wtx.GetHash()]);
+    vpwtx[2]->nTimeReceived = (unsigned int)1333333329;
+    vpwtx[2]->nOrderPos = -1;
+
+    GetResults(walletdb, results);
+
+    BOOST_CHECK(results.size() == 3);
+    BOOST_CHECK(pwalletMain->nOrderPosNext == 6);
+    BOOST_CHECK(0 == vpwtx[2]->nOrderPos);
+    BOOST_CHECK(results[1].nTime == 1333333333);
+    BOOST_CHECK(2 == vpwtx[0]->nOrderPos);
+    BOOST_CHECK(results[3].nTime == 1333333336);
+    BOOST_CHECK(results[4].nTime == 1333333330);
+    BOOST_CHECK(results[4].strComment.empty());
+    BOOST_CHECK(5 == vpwtx[1]->nOrderPos);
+
+
+    ae.nTime = 1333333334;
+    ae.strOtherAccount = "e";
+    ae.nOrderPos = -1;
+    walletdb.WriteAccountingEntry(ae);
+
+    GetResults(walletdb, results);
+
+    BOOST_CHECK(results.size() == 4);
+    BOOST_CHECK(pwalletMain->nOrderPosNext == 7);
+    BOOST_CHECK(0 == vpwtx[2]->nOrderPos);
+    BOOST_CHECK(results[1].nTime == 1333333333);
+    BOOST_CHECK(2 == vpwtx[0]->nOrderPos);
+    BOOST_CHECK(results[3].nTime == 1333333336);
+    BOOST_CHECK(results[3].strComment.empty());
+    BOOST_CHECK(results[4].nTime == 1333333330);
+    BOOST_CHECK(results[4].strComment.empty());
+    BOOST_CHECK(results[5].nTime == 1333333334);
+    BOOST_CHECK(6 == vpwtx[1]->nOrderPos);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/wallet.cpp b/src/wallet.cpp
--- a/src/wallet.cpp
+++ b/src/wallet.cpp
@@ -336,7 +336,10 @@
         wtx.BindWallet(this);
         bool fInsertedNew = ret.second;
         if (fInsertedNew)
+        {
             wtx.nTimeReceived = GetAdjustedTime();
+            wtx.nOrderPos = nOrderPosNext++;
+        }
 
         bool fUpdated = false;
         if (!fInsertedNew)
diff --git a/src/wallet.h b/src/wallet.h
--- a/src/wallet.h
+++ b/src/wallet.h
@@ -5,11 +5,17 @@
 #ifndef BITCOIN_WALLET_H
 #define BITCOIN_WALLET_H
 
+#include <string>
+#include <vector>
+
+#include <stdlib.h>
+
 #include "main.h"
 #include "key.h"
 #include "keystore.h"
 #include "script.h"
 #include "ui_interface.h"
+#include "util.h"
 
 class CWalletTx;
 class CReserveKey;
@@ -103,6 +109,7 @@
     }
 
     std::map<uint256, CWalletTx> mapWallet;
+    int64 nOrderPosNext;
     std::map<uint256, int> mapRequestCount;
 
     std::map<CTxDestination, std::string> mapAddressBook;
@@ -304,6 +311,32 @@
 };
 
 
+typedef std::map<std::string, std::string> mapValue_t;
+
+
+static
+void
+ReadOrderPos(int64& nOrderPos, mapValue_t& mapValue)
+{
+    if (!mapValue.count("n"))
+    {
+        nOrderPos = -1; // TODO: calculate elsewhere
+        return;
+    }
+    nOrderPos = atoi64(mapValue["n"].c_str());
+}
+
+
+static
+void
+WriteOrderPos(const int64& nOrderPos, mapValue_t& mapValue)
+{
+    if (nOrderPos == -1)
+        return;
+    mapValue["n"] = i64tostr(nOrderPos);
+}
+
+
 /** A transaction with a bunch of additional info that only the owner cares about. 
  * It includes any unrecorded transactions needed to link it back to the block chain.
  */
@@ -314,13 +347,14 @@
 
 public:
     std::vector<CMerkleTx> vtxPrev;
-    std::map<std::string, std::string> mapValue;
+    mapValue_t mapValue;
     std::vector<std::pair<std::string, std::string> > vOrderForm;
     unsigned int fTimeReceivedIsTxTime;
     unsigned int nTimeReceived;  // time received by this node
     char fFromMe;
     std::string strFromAccount;
     std::vector<char> vfSpent; // which outputs are already spent
+    int64 nOrderPos;  // position in ordered transaction list
 
     // memory only
     mutable bool fDebitCached;
@@ -371,6 +405,7 @@
         nCreditCached = 0;
         nAvailableCreditCached = 0;
         nChangeCached = 0;
+        nOrderPos = -1;
     }
 
     IMPLEMENT_SERIALIZE
@@ -392,6 +427,8 @@
                     fSpent = true;
             }
             pthis->mapValue["spent"] = str;
+
+            WriteOrderPos(pthis->nOrderPos, pthis->mapValue);
         }
 
         nSerSize += SerReadWrite(s, *(CMerkleTx*)this, nType, nVersion,ser_action);
@@ -414,9 +451,13 @@
                 pthis->vfSpent.assign(vout.size(), fSpent);
         }
 
+        if (fRead)
+            ReadOrderPos(pthis->nOrderPos, pthis->mapValue);
+
         pthis->mapValue.erase("fromaccount");
         pthis->mapValue.erase("version");
         pthis->mapValue.erase("spent");
+        pthis->mapValue.erase("n");
     )
 
     // marks certain txout's as spent
@@ -705,6 +746,9 @@
     int64 nTime;
     std::string strOtherAccount;
     std::string strComment;
+    mapValue_t mapValue;
+    int64 nOrderPos;  // position in ordered transaction list
+    uint64 nEntryNo;
 
     CAccountingEntry()
     {
@@ -718,18 +762,55 @@
         strAccount.clear();
         strOtherAccount.clear();
         strComment.clear();
+        nOrderPos = -1;
     }
 
     IMPLEMENT_SERIALIZE
     (
+        CAccountingEntry& me = *const_cast<CAccountingEntry*>(this);
         if (!(nType & SER_GETHASH))
             READWRITE(nVersion);
         // Note: strAccount is serialized as part of the key, not here.
         READWRITE(nCreditDebit);
         READWRITE(nTime);
         READWRITE(strOtherAccount);
+
+        if (!fRead)
+        {
+            WriteOrderPos(nOrderPos, me.mapValue);
+
+            if (!(mapValue.empty() && _ssExtra.empty()))
+            {
+                CDataStream ss(nType, nVersion);
+                ss.insert(ss.begin(), '\0');
+                ss << mapValue;
+                ss.insert(ss.end(), _ssExtra.begin(), _ssExtra.end());
+                me.strComment.append(ss.str());
+            }
+        }
+
         READWRITE(strComment);
+
+        size_t nSepPos = strComment.find("\0", 0, 1);
+        if (fRead)
+        {
+            me.mapValue.clear();
+            if (std::string::npos != nSepPos)
+            {
+                CDataStream ss(std::vector<char>(strComment.begin() + nSepPos + 1, strComment.end()), nType, nVersion);
+                ss >> me.mapValue;
+                me._ssExtra = std::vector<char>(ss.begin(), ss.end());
+            }
+            ReadOrderPos(me.nOrderPos, me.mapValue);
+        }
+        if (std::string::npos != nSepPos)
+            me.strComment.erase(nSepPos);
+
+        me.mapValue.erase("n");
     )
+
+private:
+    std::vector<char> _ssExtra;
 };
 
 bool GetWalletFile(CWallet* pwallet, std::string &strWalletFileOut);
diff --git a/src/walletdb.cpp b/src/walletdb.cpp
--- a/src/walletdb.cpp
+++ b/src/walletdb.cpp
@@ -42,9 +42,14 @@
     return Write(make_pair(string("acc"), strAccount), account);
 }
 
+bool CWalletDB::WriteAccountingEntry(const uint64 nAccEntryNum, const CAccountingEntry& acentry)
+{
+    return Write(boost::make_tuple(string("acentry"), acentry.strAccount, nAccEntryNum), acentry);
+}
+
 bool CWalletDB::WriteAccountingEntry(const CAccountingEntry& acentry)
 {
-    return Write(boost::make_tuple(string("acentry"), acentry.strAccount, ++nAccountingEntryNumber), acentry);
+    return WriteAccountingEntry(++nAccountingEntryNumber, acentry);
 }
 
 int64 CWalletDB::GetAccountCreditDebit(const string& strAccount)
@@ -95,6 +100,7 @@
             break;
 
         ssValue >> acentry;
+        ssKey >> acentry.nEntryNo;
         entries.push_back(acentry);
     }
 
@@ -102,12 +108,86 @@
 }
 
 
+int
+CWalletDB::ReorderTransactions(CWallet* pwallet)
+{
+    LOCK(pwallet->cs_wallet);
+    // Old wallets didn't have any defined order for transactions
+    // Probably a bad idea to change the output of this
+
+    // First: get all CWalletTx and CAccountingEntry into a sorted-by-time multimap.
+    typedef pair<CWalletTx*, CAccountingEntry*> TxPair;
+    typedef multimap<int64, TxPair > TxItems;
+    TxItems txByTime;
+
+    for (map<uint256, CWalletTx>::iterator it = pwallet->mapWallet.begin(); it != pwallet->mapWallet.end(); ++it)
+    {
+        CWalletTx* wtx = &((*it).second);
+        txByTime.insert(make_pair(wtx->nTimeReceived, TxPair(wtx, (CAccountingEntry*)0)));
+    }
+    list<CAccountingEntry> acentries;
+    ListAccountCreditDebit("", acentries);
+    BOOST_FOREACH(CAccountingEntry& entry, acentries)
+    {
+        txByTime.insert(make_pair(entry.nTime, TxPair((CWalletTx*)0, &entry)));
+    }
+
+    int64& nOrderPosNext = pwallet->nOrderPosNext;
+    nOrderPosNext = 0;
+    std::vector<int64> nOrderPosOffsets;
+    for (TxItems::iterator it = txByTime.begin(); it != txByTime.end(); ++it)
+    {
+        CWalletTx *const pwtx = (*it).second.first;
+        CAccountingEntry *const pacentry = (*it).second.second;
+        int64& nOrderPos = (pwtx != 0) ? pwtx->nOrderPos : pacentry->nOrderPos;
+
+        if (nOrderPos == -1)
+        {
+            nOrderPos = nOrderPosNext++;
+            nOrderPosOffsets.push_back(nOrderPos);
+
+            if (pacentry)
+                // Have to write accounting regardless, since we don't keep it in memory
+                if (!WriteAccountingEntry(pacentry->nEntryNo, *pacentry))
+                    return DB_LOAD_FAIL;
+        }
+        else
+        {
+            int64 nOrderPosOff = 0;
+            BOOST_FOREACH(const int64& nOffsetStart, nOrderPosOffsets)
+            {
+                if (nOrderPos >= nOffsetStart)
+                    ++nOrderPosOff;
+            }
+            nOrderPos += nOrderPosOff;
+            nOrderPosNext = std::max(nOrderPosNext, nOrderPos + 1);
+
+            if (!nOrderPosOff)
+                continue;
+
+            // Since we're changing the order, write it back
+            if (pwtx)
+            {
+                if (!WriteTx(pwtx->GetHash(), *pwtx))
+                    return DB_LOAD_FAIL;
+            }
+            else
+                if (!WriteAccountingEntry(pacentry->nEntryNo, *pacentry))
+                    return DB_LOAD_FAIL;
+        }
+    }
+
+    return DB_LOAD_OK;
+}
+
+
 int CWalletDB::LoadWallet(CWallet* pwallet)
 {
     pwallet->vchDefaultKey = CPubKey();
     int nFileVersion = 0;
     vector<uint256> vWalletUpgrade;
     bool fIsEncrypted = false;
+    bool fAnyUnordered = false;
 
     //// todo: shouldn't we catch exceptions and try to recover and continue?
     {
@@ -183,6 +263,9 @@
                     vWalletUpgrade.push_back(hash);
                 }
 
+                if (wtx.nOrderPos == -1)
+                    fAnyUnordered = true;
+
                 //// debug print
                 //printf("LoadWallet  %s\n", wtx.GetHash().ToString().c_str());
                 //printf(" %12"PRI64d"  %s  %s  %s\n",
@@ -199,6 +282,14 @@
                 ssKey >> nNumber;
                 if (nNumber > nAccountingEntryNumber)
                     nAccountingEntryNumber = nNumber;
+
+                if (!fAnyUnordered)
+                {
+                    CAccountingEntry acentry;
+                    ssValue >> acentry;
+                    if (acentry.nOrderPos == -1)
+                        fAnyUnordered = true;
+                }
             }
             else if (strType == "key" || strType == "wkey")
             {
@@ -318,6 +409,10 @@
     if (nFileVersion < CLIENT_VERSION) // Update
         WriteVersion(CLIENT_VERSION);
 
+    if (fAnyUnordered)
+        return ReorderTransactions(pwallet);
+
+    // If you add anything else here... be sure to do it if ReorderTransactions returns DB_LOAD_OK too!
     return DB_LOAD_OK;
 }
 
diff --git a/src/walletdb.h b/src/walletdb.h
--- a/src/walletdb.h
+++ b/src/walletdb.h
@@ -170,10 +170,14 @@
 
     bool ReadAccount(const std::string& strAccount, CAccount& account);
     bool WriteAccount(const std::string& strAccount, const CAccount& account);
+private:
+    bool WriteAccountingEntry(const uint64 nAccEntryNum, const CAccountingEntry& acentry);
+public:
     bool WriteAccountingEntry(const CAccountingEntry& acentry);
     int64 GetAccountCreditDebit(const std::string& strAccount);
     void ListAccountCreditDebit(const std::string& strAccount, std::list<CAccountingEntry>& acentries);
 
+    int ReorderTransactions(CWallet*);
     int LoadWallet(CWallet* pwallet);
 };