Implement stake kernel mining as a separate function
authorCryptoManiac <balthazar@yandex.ru>
Tue, 19 Aug 2014 18:41:31 +0000 (22:41 +0400)
committerCryptoManiac <balthazar@yandex.ru>
Tue, 19 Aug 2014 18:41:31 +0000 (22:41 +0400)
This change allows us to reduce amount of intermediatte operations, such as header hashing or modifier calculation. As the result, we've got ~20x drop of CPU load and 60x boost of kernel scanning speed.

src/kernel.cpp
src/kernel.h
src/main.cpp
src/wallet.cpp

index b473249..ae686be 100644 (file)
@@ -298,6 +298,15 @@ static bool GetKernelStakeModifier(uint256 hashBlockFrom, uint64& nStakeModifier
     return true;
 }
 
+bool GetKernelStakeModifier(uint256 hashBlockFrom, uint64& nStakeModifier)
+{
+    int nStakeModifierHeight;
+    int64 nStakeModifierTime;
+
+    return GetKernelStakeModifier(hashBlockFrom, nStakeModifier, nStakeModifierHeight, nStakeModifierTime, false);
+}
+
+
 // ppcoin kernel protocol
 // coinstake must meet hash target according to the protocol:
 // kernel (input 0) must meet the formula
@@ -380,6 +389,82 @@ bool CheckStakeKernelHash(unsigned int nBits, const CBlock& blockFrom, unsigned
     return true;
 }
 
+// Scan given coins set for kernel solution
+bool ScanForStakeKernelHash(CoinsSet &setCoins, MetaMap &mapMeta, KernelSearchSettings &settings, CoinsSet::value_type &kernelcoin, unsigned int &nTimeTx, unsigned int &nBlockTime)
+{
+    uint256 hashProofOfStake = 0, targetProofOfStake = 0;
+
+    for(CoinsSet::const_iterator pcoin = setCoins.begin(); pcoin != setCoins.end(); pcoin++)
+    {
+        if (!fCoinsDataActual)
+            break;
+
+        MetaMap::const_iterator mi = mapMeta.find(pcoin->first->GetHash());
+        if (mi == mapMeta.end())
+        {
+            if (fDebug)
+                printf("Unable to find %s in mapMeta, stopping\n", pcoin->first->GetHash().GetHex().c_str());
+            fCoinsDataActual = false;
+            break;
+        }
+
+        CTxIndex txindex = (*mi).second.first;
+        CBlock block = (*mi).second.second.first;
+        uint64 nStakeModifier = (*mi).second.second.second;
+
+        static int nMaxStakeSearchInterval = 60;
+
+        // only count coins meeting min age requirement
+        if (nStakeMinAge + block.nTime > settings.nTime - nMaxStakeSearchInterval)
+            continue;
+
+        // Transaction offset inside block
+        unsigned int nTxOffset = txindex.pos.nTxPos - txindex.pos.nBlockPos;
+
+        // Current timestamp scanning interval
+        unsigned int nCurrentSearchInterval = min((int64)settings.nSearchInterval, (int64)nMaxStakeSearchInterval);
+
+        nBlockTime = block.nTime;
+        CBigNum bnTargetPerCoinDay;
+        bnTargetPerCoinDay.SetCompact(settings.nBits);
+        int64 nValueIn = pcoin->first->vout[pcoin->second].nValue;
+
+        // Search backward in time from the given timestamp 
+        // Search nSearchInterval seconds back up to nMaxStakeSearchInterval
+        // Stopping search in case of shutting down or cache invalidation
+        for (unsigned int n=0; n<nCurrentSearchInterval && fCoinsDataActual && !fShutdown; n++)
+        {
+            nTimeTx = settings.nTime - n;
+            CBigNum bnCoinDayWeight = CBigNum(nValueIn) * GetWeight((int64)pcoin->first->nTime, (int64)nTimeTx) / COIN / (24 * 60 * 60);
+            targetProofOfStake = (bnCoinDayWeight * bnTargetPerCoinDay).getuint256();
+
+            // Build kernel
+            CDataStream ss(SER_GETHASH, 0);
+            ss << nStakeModifier;
+            ss << nBlockTime << nTxOffset << pcoin->first->nTime << pcoin->second << nTimeTx;
+
+            // Calculate kernel hash
+            hashProofOfStake = Hash(ss.begin(), ss.end());
+
+            if (bnCoinDayWeight * bnTargetPerCoinDay >= CBigNum(hashProofOfStake))
+            {
+                if (fDebug)
+                    printf("nStakeModifier=0x%016"PRI64x", nBlockTime=%u nTxOffset=%u nTxPrevTime=%u nVout=%u nTimeTx=%u hashProofOfStake=%s Success=true\n",
+                        nStakeModifier, nBlockTime, nTxOffset, pcoin->first->nTime, pcoin->second, nTimeTx, hashProofOfStake.GetHex().c_str());
+
+                kernelcoin = *pcoin;
+                return true;
+            }
+
+            if (fDebug)
+                printf("nStakeModifier=0x%016"PRI64x", nBlockTime=%u nTxOffset=%u nTxPrevTime=%u nTxNumber=%u nTimeTx=%u hashProofOfStake=%s Success=false\n",
+                    nStakeModifier, nBlockTime, nTxOffset, pcoin->first->nTime, pcoin->second, nTimeTx, hashProofOfStake.GetHex().c_str());
+        }
+    }
+
+    return false;
+}
+
 // Check kernel hash target and coinstake signature
 bool CheckProofOfStake(const CTransaction& tx, unsigned int nBits, uint256& hashProofOfStake, uint256& targetProofOfStake)
 {
index a9c8a23..d24cac3 100644 (file)
@@ -5,6 +5,7 @@
 #define PPCOIN_KERNEL_H
 
 #include "main.h"
+#include "wallet.h"
 
 // ChainDB upgrade time
 extern unsigned int nModifierUpgradeTime;
@@ -12,6 +13,8 @@ extern unsigned int nModifierUpgradeTime;
 // MODIFIER_INTERVAL: time to elapse before new modifier is computed
 extern unsigned int nModifierInterval;
 
+extern bool fCoinsDataActual;
+
 // MODIFIER_INTERVAL_RATIO:
 // ratio of group interval length between the last group and the first group
 static const int MODIFIER_INTERVAL_RATIO = 3;
@@ -22,10 +25,32 @@ bool IsFixedModifierInterval(unsigned int nTimeBlock);
 // Compute the hash modifier for proof-of-stake
 bool ComputeNextStakeModifier(const CBlockIndex* pindexCurrent, uint64& nStakeModifier, bool& fGeneratedStakeModifier);
 
+// The stake modifier used to hash for a stake kernel is chosen as the stake
+// modifier about a selection interval later than the coin generating the kernel
+bool GetKernelStakeModifier(uint256 hashBlockFrom, uint64& nStakeModifier);
+
 // Check whether stake kernel meets hash target
 // Sets hashProofOfStake on success return
 bool CheckStakeKernelHash(unsigned int nBits, const CBlock& blockFrom, unsigned int nTxPrevOffset, const CTransaction& txPrev, const COutPoint& prevout, unsigned int nTimeTx, uint256& hashProofOfStake, uint256& targetProofOfStake, bool fPrintProofOfStake=false);
 
+// Preloaded coins set
+typedef set<pair<const CWalletTx*,unsigned int> > CoinsSet;
+
+// Preloaded coins metadata (block header and stake modifier)
+typedef map<uint256, pair<CTxIndex, pair<CBlock, uint64> > > MetaMap;
+
+// Coins scanning options
+typedef struct KernelSearchSettings {
+    unsigned int nBits;           // Packed difficulty
+    unsigned int nTime;           // Basic time
+    unsigned int nOffset;         // Offset inside CoinsSet (isn't used yet)
+    unsigned int nLimit;          // Coins to scan (isn't used yet)
+    unsigned int nSearchInterval; // Number of seconds allowed to go into the past
+} KernelSearchSettings;
+
+// Scan given coins set for kernel solution
+bool ScanForStakeKernelHash(CoinsSet &setCoins, MetaMap &mapMeta, KernelSearchSettings &settings, CoinsSet::value_type &kernelcoin, unsigned int &nTimeTx, unsigned int &nBlockTime);
+
 // Check kernel hash target and coinstake signature
 // Sets hashProofOfStake on success return
 bool CheckProofOfStake(const CTransaction& tx, unsigned int nBits, uint256& hashProofOfStake, uint256& targetProofOfStake);
index 9a521fe..0d2325c 100644 (file)
@@ -149,6 +149,8 @@ void SyncWithWallets(const CTransaction& tx, const CBlock* pblock, bool fUpdate,
 
     BOOST_FOREACH(CWallet* pwallet, setpwalletRegistered)
         pwallet->AddToWalletIfInvolvingMe(tx, pblock, fUpdate);
+    // Preloaded coins cache invalidation
+    fCoinsDataActual = false;
 }
 
 // notify wallets about a new best chain
@@ -1827,6 +1829,7 @@ bool CBlock::ConnectBlock(CTxDB& txdb, CBlockIndex* pindex, bool fJustCheck)
     BOOST_FOREACH(CTransaction& tx, vtx)
         SyncWithWallets(tx, this, true);
 
+
     return true;
 }
 
index 7045e3c..104b162 100644 (file)
@@ -16,6 +16,8 @@
 using namespace std;
 extern int nStakeMaxAge;
 
+bool fCoinsDataActual;
+
 //////////////////////////////////////////////////////////////////////////////
 //
 // mapWallet
@@ -1633,46 +1635,25 @@ bool CWallet::GetStakeWeight(const CKeyStore& keystore, uint64& nMinWeight, uint
 
     vector<const CWalletTx*> vwtxPrev;
 
-/*
- * TODO: performance comparison
-
     static set<pair<const CWalletTx*,unsigned int> > setCoins;
     static uint256 hashPrevBlock;
-    static int64 nValueIn = 0;
 
-    // Cache outputs unless best block changed
-    if (hashPrevBlock != pindexBest->GetBlockHash())
+    // Cache outputs unless best block or wallet transaction set changed
+    if (!fCoinsDataActual)
     {
+        int64 nValueIn = 0;
         if (!SelectCoinsSimple(nBalance - nReserveBalance, GetAdjustedTime(), nCoinbaseMaturity * 10, setCoins, nValueIn))
             return false;
 
         if (setCoins.empty())
             return false;
 
-        hashPrevBlock == pindexBest->GetBlockHash();
+        fCoinsDataActual = true;
     }
-*/
-
-    set<pair<const CWalletTx*,unsigned int> > setCoins;
-    int64 nValueIn = 0;
-
-    // Simple coins selection - no randomization
-    if (!SelectCoinsSimple(nBalance - nReserveBalance, GetTime(), nCoinbaseMaturity * 10, setCoins, nValueIn))
-        return false;
-
-    if (setCoins.empty())
-        return false;
 
     CTxDB txdb("r");
     BOOST_FOREACH(PAIRTYPE(const CWalletTx*, unsigned int) pcoin, setCoins)
     {
-        CTxIndex txindex;
-        {
-            LOCK2(cs_main, cs_wallet);
-            if (!txdb.ReadTxIndex(pcoin.first->GetHash(), txindex))
-                continue;
-        }
-
         int64 nTimeWeight = GetWeight((int64)pcoin.first->nTime, (int64)GetTime());
         CBigNum bnCoinDayWeight = CBigNum(pcoin.first->vout[pcoin.second].nValue) * nTimeWeight / COIN / (24 * 60 * 60);
 
@@ -1855,151 +1836,148 @@ bool CWallet::CreateCoinStake(const CKeyStore& keystore, unsigned int nBits, int
 
     vector<const CWalletTx*> vwtxPrev;
 
-/*
- * TODO: performance comparison
+    static CoinsSet setCoins;
+    static MetaMap mapMeta;
 
-    static set<pair<const CWalletTx*,unsigned int> > setCoins;
-    static uint256 hashPrevBlock;
-    static int64 nValueIn = 0;
-
-    // Cache outputs unless best block changed
-    if (hashPrevBlock != pindexBest->GetBlockHash())
+    CTxDB txdb("r");
     {
-        if (!SelectCoinsSimple(nBalance - nReserveBalance, txNew.nTime, nCoinbaseMaturity * 10, setCoins, nValueIn))
-            return false;
+        LOCK2(cs_main, cs_wallet);
+        // Cache outputs unless best block or wallet transaction set changed
+        if (!fCoinsDataActual)
+        {
+            setCoins.clear();
+            mapMeta.clear();
 
-        if (setCoins.empty())
-            return false;
+            int64 nValueIn = 0;
+            if (!SelectCoinsSimple(nBalance - nReserveBalance, txNew.nTime, nCoinbaseMaturity * 10, setCoins, nValueIn))
+                return false;
 
-        hashPrevBlock == pindexBest->GetBlockHash();
-    }
-*/
+            if (setCoins.empty())
+                return false;
 
-    set<pair<const CWalletTx*,unsigned int> > setCoins;
-    int64 nValueIn = 0;
+            {
+                CTxIndex txindex;
+                CBlock block;
+                for(CoinsSet::iterator pcoin = setCoins.begin(); pcoin != setCoins.end(); pcoin++)
+                {
+                    // Load transaction index item
+                    if (!txdb.ReadTxIndex(pcoin->first->GetHash(), txindex))
+                        continue;
 
-    // Select coins with suitable depth
-    if (!SelectCoinsSimple(nBalance - nReserveBalance, txNew.nTime, nCoinbaseMaturity * 10, setCoins, nValueIn))
-        return false;
+                    // Read block header
+                    if (!block.ReadFromDisk(txindex.pos.nFile, txindex.pos.nBlockPos, false))
+                        continue;
 
-    if (setCoins.empty())
-        return false;
+                    uint64 nStakeModifier = 0;
+
+                    if (!GetKernelStakeModifier(block.GetHash(), nStakeModifier))
+                        return false;
+
+                    // Add meta record
+                    mapMeta[pcoin->first->GetHash()] = make_pair(txindex, make_pair(block, nStakeModifier));
+
+                    if (fDebug)
+                        printf("Load coin: %s\n", pcoin->first->GetHash().GetHex().c_str());
+                }
+            }
+
+            if (fDebug)
+                printf("Stake miner: %zu meta items loaded for %zu coins\n", mapMeta.size(), setCoins.size());
+
+            fCoinsDataActual = true;
+        }
+    }
 
     int64 nCredit = 0;
     CScript scriptPubKeyKernel;
-    CTxDB txdb("r");
-    BOOST_FOREACH(PAIRTYPE(const CWalletTx*, unsigned int) pcoin, setCoins)
-    {
-        CTxIndex txindex;
-        {
-            LOCK2(cs_main, cs_wallet);
-            if (!txdb.ReadTxIndex(pcoin.first->GetHash(), txindex))
-                continue;
-        }
 
-        // Read block header
-        CBlock block;
+    KernelSearchSettings settings;
+    settings.nBits = nBits;
+    settings.nTime = txNew.nTime;
+    settings.nOffset = 0;
+    settings.nLimit = setCoins.size();
+    settings.nSearchInterval = nSearchInterval;
+
+    unsigned int nTimeTx, nBlockTime;
+    COutPoint prevoutStake;
+    CoinsSet::value_type kernelcoin;
+
+    if (ScanForStakeKernelHash(setCoins, mapMeta, settings, kernelcoin, nTimeTx, nBlockTime))
+    {
+        // Found a kernel
+        if (fDebug && GetBoolArg("-printcoinstake"))
+            printf("CreateCoinStake : kernel found\n");
+        vector<valtype> vSolutions;
+        txnouttype whichType;
+        CScript scriptPubKeyOut;
+        scriptPubKeyKernel = kernelcoin.first->vout[kernelcoin.second].scriptPubKey;
+        if (!Solver(scriptPubKeyKernel, whichType, vSolutions))
+        {
+            if (fDebug && GetBoolArg("-printcoinstake"))
+                printf("CreateCoinStake : failed to parse kernel\n");
+            return false;
+        }
+        if (fDebug && GetBoolArg("-printcoinstake"))
+            printf("CreateCoinStake : parsed kernel type=%d\n", whichType);
+        if (whichType != TX_PUBKEY && whichType != TX_PUBKEYHASH)
         {
-            LOCK2(cs_main, cs_wallet);
-            if (!block.ReadFromDisk(txindex.pos.nFile, txindex.pos.nBlockPos, false))
-                continue;
+            if (fDebug && GetBoolArg("-printcoinstake"))
+                printf("CreateCoinStake : no support for kernel type=%d\n", whichType);
+            return false;  // only support pay to public key and pay to address
         }
-
-        static int nMaxStakeSearchInterval = 60;
-        if (block.GetBlockTime() + nStakeMinAge > txNew.nTime - nMaxStakeSearchInterval)
-            continue; // only count coins meeting min age requirement
-
-        bool fKernelFound = false;
-        for (unsigned int n=0; n<min(nSearchInterval,(int64)nMaxStakeSearchInterval) && !fKernelFound && !fShutdown; n++)
+        if (whichType == TX_PUBKEYHASH) // pay to address type
         {
-            // Search backward in time from the given txNew timestamp 
-            // Search nSearchInterval seconds back up to nMaxStakeSearchInterval
-            uint256 hashProofOfStake = 0, targetProofOfStake = 0;
-            COutPoint prevoutStake = COutPoint(pcoin.first->GetHash(), pcoin.second);
-            if (CheckStakeKernelHash(nBits, block, txindex.pos.nTxPos - txindex.pos.nBlockPos, *pcoin.first, prevoutStake, txNew.nTime - n, hashProofOfStake, targetProofOfStake))
+            // convert to pay to public key type
+            if (!keystore.GetKey(uint160(vSolutions[0]), key))
             {
-                // Found a kernel
                 if (fDebug && GetBoolArg("-printcoinstake"))
-                    printf("CreateCoinStake : kernel found\n");
-                vector<valtype> vSolutions;
-                txnouttype whichType;
-                CScript scriptPubKeyOut;
-                scriptPubKeyKernel = pcoin.first->vout[pcoin.second].scriptPubKey;
-                if (!Solver(scriptPubKeyKernel, whichType, vSolutions))
-                {
-                    if (fDebug && GetBoolArg("-printcoinstake"))
-                        printf("CreateCoinStake : failed to parse kernel\n");
-                    break;
-                }
+                    printf("CreateCoinStake : failed to get key for kernel type=%d\n", whichType);
+                return false;  // unable to find corresponding public key
+            }
+            scriptPubKeyOut << key.GetPubKey() << OP_CHECKSIG;
+        }
+        if (whichType == TX_PUBKEY)
+        {
+            valtype& vchPubKey = vSolutions[0];
+            if (!keystore.GetKey(Hash160(vchPubKey), key))
+            {
                 if (fDebug && GetBoolArg("-printcoinstake"))
-                    printf("CreateCoinStake : parsed kernel type=%d\n", whichType);
-                if (whichType != TX_PUBKEY && whichType != TX_PUBKEYHASH)
-                {
-                    if (fDebug && GetBoolArg("-printcoinstake"))
-                        printf("CreateCoinStake : no support for kernel type=%d\n", whichType);
-                    break;  // only support pay to public key and pay to address
-                }
-                if (whichType == TX_PUBKEYHASH) // pay to address type
-                {
-                    // convert to pay to public key type
-                    if (!keystore.GetKey(uint160(vSolutions[0]), key))
-                    {
-                        if (fDebug && GetBoolArg("-printcoinstake"))
-                            printf("CreateCoinStake : failed to get key for kernel type=%d\n", whichType);
-                        break;  // unable to find corresponding public key
-                    }
-                    scriptPubKeyOut << key.GetPubKey() << OP_CHECKSIG;
-                }
-                if (whichType == TX_PUBKEY)
-                {
-                    valtype& vchPubKey = vSolutions[0];
-                    if (!keystore.GetKey(Hash160(vchPubKey), key))
-                    {
-                        if (fDebug && GetBoolArg("-printcoinstake"))
-                            printf("CreateCoinStake : failed to get key for kernel type=%d\n", whichType);
-                        break;  // unable to find corresponding public key
-                    }
-
-                if (key.GetPubKey() != vchPubKey)
-                {
-                    if (fDebug && GetBoolArg("-printcoinstake"))
-                        printf("CreateCoinStake : invalid key for kernel type=%d\n", whichType);
-                        break; // keys mismatch
-                    }
-
-                    scriptPubKeyOut = scriptPubKeyKernel;
-                }
-
-                txNew.nTime -= n;
-                txNew.vin.push_back(CTxIn(pcoin.first->GetHash(), pcoin.second));
-                nCredit += pcoin.first->vout[pcoin.second].nValue;
-                vwtxPrev.push_back(pcoin.first);
-                txNew.vout.push_back(CTxOut(0, scriptPubKeyOut));
-
-                if (GetWeight(block.GetBlockTime(), (int64)txNew.nTime) < nStakeMaxAge)
-                    txNew.vout.push_back(CTxOut(0, scriptPubKeyOut)); //split stake
+                    printf("CreateCoinStake : failed to get key for kernel type=%d\n", whichType);
+                return false;  // unable to find corresponding public key
+            }
+            if (key.GetPubKey() != vchPubKey)
+            {
                 if (fDebug && GetBoolArg("-printcoinstake"))
-                    printf("CreateCoinStake : added kernel type=%d\n", whichType);
-                fKernelFound = true;
-                break;
+                    printf("CreateCoinStake : invalid key for kernel type=%d\n", whichType);
+                return false; // keys mismatch
             }
+
+            scriptPubKeyOut = scriptPubKeyKernel;
         }
 
-        if (fKernelFound || fShutdown)
-            break; // if kernel is found stop searching
+        txNew.nTime = nTimeTx;
+        txNew.vin.push_back(CTxIn(kernelcoin.first->GetHash(), kernelcoin.second));
+        nCredit += kernelcoin.first->vout[kernelcoin.second].nValue;
+        vwtxPrev.push_back(kernelcoin.first);
+        txNew.vout.push_back(CTxOut(0, scriptPubKeyOut));
+
+        if (GetWeight((int64)nBlockTime, (int64)txNew.nTime) < nStakeMaxAge)
+            txNew.vout.push_back(CTxOut(0, scriptPubKeyOut)); //split stake
+        if (fDebug && GetBoolArg("-printcoinstake"))
+            printf("CreateCoinStake : added kernel type=%d\n", whichType);
     }
 
     if (nCredit == 0 || nCredit > nBalance - nReserveBalance)
         return false;
 
-    BOOST_FOREACH(PAIRTYPE(const CWalletTx*, unsigned int) pcoin, setCoins)
+    for(CoinsSet::const_iterator pcoin = setCoins.begin(); pcoin != setCoins.end(); pcoin++)
     {
         // Attempt to add more inputs
         // Only add coins of the same key/address as kernel
-        if (txNew.vout.size() == 2 && ((pcoin.first->vout[pcoin.second].scriptPubKey == scriptPubKeyKernel || pcoin.first->vout[pcoin.second].scriptPubKey == txNew.vout[1].scriptPubKey))
-            && pcoin.first->GetHash() != txNew.vin[0].prevout.hash)
+        if (txNew.vout.size() == 2 && ((pcoin->first->vout[pcoin->second].scriptPubKey == scriptPubKeyKernel || pcoin->first->vout[pcoin->second].scriptPubKey == txNew.vout[1].scriptPubKey))
+            && pcoin->first->GetHash() != txNew.vin[0].prevout.hash)
         {
-            int64 nTimeWeight = GetWeight((int64)pcoin.first->nTime, (int64)txNew.nTime);
+            int64 nTimeWeight = GetWeight((int64)pcoin->first->nTime, (int64)txNew.nTime);
 
             // Stop adding more inputs if already too many inputs
             if (txNew.vin.size() >= 100)
@@ -2008,18 +1986,18 @@ bool CWallet::CreateCoinStake(const CKeyStore& keystore, unsigned int nBits, int
             if (nCredit > nCombineThreshold)
                 break;
             // Stop adding inputs if reached reserve limit
-            if (nCredit + pcoin.first->vout[pcoin.second].nValue > nBalance - nReserveBalance)
+            if (nCredit + pcoin->first->vout[pcoin->second].nValue > nBalance - nReserveBalance)
                 break;
             // Do not add additional significant input
-            if (pcoin.first->vout[pcoin.second].nValue > nCombineThreshold)
+            if (pcoin->first->vout[pcoin->second].nValue > nCombineThreshold)
                 continue;
             // Do not add input that is still too young
             if (nTimeWeight < nStakeMaxAge)
                 continue;
 
-            txNew.vin.push_back(CTxIn(pcoin.first->GetHash(), pcoin.second));
-            nCredit += pcoin.first->vout[pcoin.second].nValue;
-            vwtxPrev.push_back(pcoin.first);
+            txNew.vin.push_back(CTxIn(pcoin->first->GetHash(), pcoin->second));
+            nCredit += pcoin->first->vout[pcoin->second].nValue;
+            vwtxPrev.push_back(pcoin->first);
         }
     }