LCOV - code coverage report
Current view: top level - src/test/fuzz - bitdeque.cpp (source / functions) Coverage Total Hit
Test: fuzz_coverage.info Lines: 100.0 % 427 427
Test Date: 2024-12-04 04:00:22 Functions: 100.0 % 49 49
Branches: 66.8 % 262 175

             Branch data     Line data    Source code
       1                 :             : // Copyright (c) 2022 The Bitcoin Core developers
       2                 :             : // Distributed under the MIT software license, see the accompanying
       3                 :             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4                 :             : 
       5                 :             : #include <random.h>
       6                 :             : #include <test/fuzz/FuzzedDataProvider.h>
       7                 :             : #include <test/fuzz/util.h>
       8                 :             : #include <util/bitdeque.h>
       9                 :             : 
      10                 :             : #include <deque>
      11                 :             : #include <vector>
      12                 :             : 
      13                 :             : namespace {
      14                 :             : 
      15                 :             : constexpr int LEN_BITS = 16;
      16                 :             : constexpr int RANDDATA_BITS = 20;
      17                 :             : 
      18                 :             : using bitdeque_type = bitdeque<128>;
      19                 :             : 
      20                 :             : //! Deterministic random vector of bools, for begin/end insertions to draw from.
      21                 :             : std::vector<bool> RANDDATA;
      22                 :             : 
      23                 :           1 : void InitRandData()
      24                 :             : {
      25                 :           1 :     FastRandomContext ctx(true);
      26                 :           1 :     RANDDATA.clear();
      27         [ +  + ]:     1114113 :     for (size_t i = 0; i < (1U << RANDDATA_BITS) + (1U << LEN_BITS); ++i) {
      28         [ +  - ]:     1114112 :         RANDDATA.push_back(ctx.randbool());
      29                 :             :     }
      30                 :           1 : }
      31                 :             : 
      32                 :             : } // namespace
      33                 :             : 
      34         [ +  - ]:        1134 : FUZZ_TARGET(bitdeque, .init = InitRandData)
      35                 :             : {
      36                 :         722 :     FuzzedDataProvider provider(buffer.data(), buffer.size());
      37                 :         722 :     FastRandomContext ctx(true);
      38                 :             : 
      39                 :         722 :     size_t maxlen = (1U << provider.ConsumeIntegralInRange<size_t>(0, LEN_BITS)) - 1;
      40                 :         722 :     size_t limitlen = 4 * maxlen;
      41                 :             : 
      42         [ +  - ]:         722 :     std::deque<bool> deq;
      43         [ +  - ]:         722 :     bitdeque_type bitdeq;
      44                 :             : 
      45                 :         722 :     const auto& cdeq = deq;
      46                 :         722 :     const auto& cbitdeq = bitdeq;
      47                 :             : 
      48                 :         722 :     size_t initlen = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
      49         [ +  + ]:     4912453 :     while (initlen) {
      50                 :     4911009 :         bool val = ctx.randbool();
      51         [ +  - ]:     4911009 :         deq.push_back(val);
      52         [ +  - ]:     4911009 :         bitdeq.push_back(val);
      53                 :     4911009 :         --initlen;
      54                 :             :     }
      55                 :             : 
      56         [ +  + ]:         722 :     const auto iter_limit{maxlen > 6000 ? 90U : 900U};
      57   [ +  +  +  + ]:      256746 :     LIMITED_WHILE(provider.remaining_bytes() > 0, iter_limit)
      58                 :             :     {
      59         [ +  - ]:      256024 :         CallOneOf(
      60                 :             :             provider,
      61                 :       20277 :             [&] {
      62                 :             :                 // constructor()
      63                 :       40554 :                 deq = std::deque<bool>{};
      64                 :       20277 :                 bitdeq = bitdeque_type{};
      65                 :       20277 :             },
      66                 :        4197 :             [&] {
      67                 :             :                 // clear()
      68                 :        4197 :                 deq.clear();
      69                 :        4197 :                 bitdeq.clear();
      70                 :        4197 :             },
      71                 :        5618 :             [&] {
      72                 :             :                 // resize()
      73                 :        5618 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
      74                 :        5618 :                 deq.resize(count);
      75                 :        5618 :                 bitdeq.resize(count);
      76                 :        5618 :             },
      77                 :        8211 :             [&] {
      78                 :             :                 // assign(count, val)
      79                 :        8211 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
      80                 :        8211 :                 bool val = ctx.randbool();
      81                 :        8211 :                 deq.assign(count, val);
      82                 :        8211 :                 bitdeq.assign(count, val);
      83                 :        8211 :             },
      84                 :        3103 :             [&] {
      85                 :             :                 // constructor(count, val)
      86                 :        3103 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
      87                 :        3103 :                 bool val = ctx.randbool();
      88                 :        6206 :                 deq = std::deque<bool>(count, val);
      89                 :        3103 :                 bitdeq = bitdeque_type(count, val);
      90                 :        3103 :             },
      91                 :        2285 :             [&] {
      92                 :             :                 // constructor(count)
      93                 :        2285 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
      94                 :        4570 :                 deq = std::deque<bool>(count);
      95                 :        2285 :                 bitdeq = bitdeque_type(count);
      96                 :        2285 :             },
      97                 :        4437 :             [&] {
      98                 :             :                 // construct(begin, end)
      99                 :        4437 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
     100                 :        4437 :                 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
     101                 :        4437 :                 auto rand_end = rand_begin + count;
     102                 :        8874 :                 deq = std::deque<bool>(rand_begin, rand_end);
     103                 :        4437 :                 bitdeq = bitdeque_type(rand_begin, rand_end);
     104                 :        4437 :             },
     105                 :        7745 :             [&] {
     106                 :             :                 // assign(begin, end)
     107                 :        7745 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
     108                 :        7745 :                 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
     109                 :        7745 :                 auto rand_end = rand_begin + count;
     110                 :        7745 :                 deq.assign(rand_begin, rand_end);
     111                 :        7745 :                 bitdeq.assign(rand_begin, rand_end);
     112                 :        7745 :             },
     113                 :        7229 :             [&] {
     114                 :             :                 // construct(initializer_list)
     115                 :        7229 :                 std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool()};
     116                 :       14458 :                 deq = std::deque<bool>(ilist);
     117                 :        7229 :                 bitdeq = bitdeque_type(ilist);
     118                 :        7229 :             },
     119                 :       11407 :             [&] {
     120                 :             :                 // assign(initializer_list)
     121                 :       11407 :                 std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
     122                 :       11407 :                 deq.assign(ilist);
     123                 :       11407 :                 bitdeq.assign(ilist);
     124                 :       11407 :             },
     125                 :       11413 :             [&] {
     126                 :             :                 // operator=(const&)
     127                 :       11413 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
     128                 :       11413 :                 bool val = ctx.randbool();
     129                 :       11413 :                 const std::deque<bool> deq2(count, val);
     130         [ +  - ]:       11413 :                 deq = deq2;
     131         [ +  - ]:       11413 :                 const bitdeque_type bitdeq2(count, val);
     132         [ +  - ]:       11413 :                 bitdeq = bitdeq2;
     133                 :       11413 :             },
     134                 :        3285 :             [&] {
     135                 :             :                 // operator=(&&)
     136                 :        3285 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
     137                 :        3285 :                 bool val = ctx.randbool();
     138                 :        3285 :                 std::deque<bool> deq2(count, val);
     139                 :        3285 :                 deq = std::move(deq2);
     140         [ +  - ]:        3285 :                 bitdeque_type bitdeq2(count, val);
     141                 :        3285 :                 bitdeq = std::move(bitdeq2);
     142                 :        3285 :             },
     143                 :        2915 :             [&] {
     144                 :             :                 // deque swap
     145                 :        2915 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
     146                 :        2915 :                 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
     147                 :        2915 :                 auto rand_end = rand_begin + count;
     148                 :        2915 :                 std::deque<bool> deq2(rand_begin, rand_end);
     149         [ +  - ]:        2915 :                 bitdeque_type bitdeq2(rand_begin, rand_end);
     150                 :        2915 :                 using std::swap;
     151         [ -  + ]:        2915 :                 assert(deq.size() == bitdeq.size());
     152         [ -  + ]:        2915 :                 assert(deq2.size() == bitdeq2.size());
     153                 :        2915 :                 swap(deq, deq2);
     154                 :        2915 :                 swap(bitdeq, bitdeq2);
     155         [ -  + ]:        2915 :                 assert(deq.size() == bitdeq.size());
     156         [ -  + ]:        2915 :                 assert(deq2.size() == bitdeq2.size());
     157                 :        2915 :             },
     158                 :        5607 :             [&] {
     159                 :             :                 // deque.swap
     160                 :        5607 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
     161                 :        5607 :                 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
     162                 :        5607 :                 auto rand_end = rand_begin + count;
     163                 :        5607 :                 std::deque<bool> deq2(rand_begin, rand_end);
     164         [ +  - ]:        5607 :                 bitdeque_type bitdeq2(rand_begin, rand_end);
     165         [ -  + ]:        5607 :                 assert(deq.size() == bitdeq.size());
     166         [ -  + ]:        5607 :                 assert(deq2.size() == bitdeq2.size());
     167                 :        5607 :                 deq.swap(deq2);
     168                 :        5607 :                 bitdeq.swap(bitdeq2);
     169         [ -  + ]:        5607 :                 assert(deq.size() == bitdeq.size());
     170         [ -  + ]:        5607 :                 assert(deq2.size() == bitdeq2.size());
     171                 :        5607 :             },
     172                 :        6368 :             [&] {
     173                 :             :                 // operator=(initializer_list)
     174                 :        6368 :                 std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
     175                 :        6368 :                 deq = ilist;
     176                 :        6368 :                 bitdeq = ilist;
     177                 :        6368 :             },
     178                 :        5122 :             [&] {
     179                 :             :                 // iterator arithmetic
     180                 :        5122 :                 auto pos1 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
     181                 :        5122 :                 auto pos2 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
     182                 :        5122 :                 auto it = deq.begin() + pos1;
     183                 :        5122 :                 auto bitit = bitdeq.begin() + pos1;
     184   [ +  +  -  + ]:        5122 :                 if ((size_t)pos1 != cdeq.size()) assert(*it == *bitit);
     185         [ -  + ]:        5122 :                 assert(it - deq.begin() == pos1);
     186         [ -  + ]:        5122 :                 assert(bitit - bitdeq.begin() == pos1);
     187         [ +  + ]:        5122 :                 if (provider.ConsumeBool()) {
     188                 :        3104 :                     it += pos2 - pos1;
     189                 :        3104 :                     bitit += pos2 - pos1;
     190                 :             :                 } else {
     191                 :        2018 :                     it -= pos1 - pos2;
     192                 :        2018 :                     bitit -= pos1 - pos2;
     193                 :             :                 }
     194   [ +  +  -  + ]:        5122 :                 if ((size_t)pos2 != cdeq.size()) assert(*it == *bitit);
     195         [ -  + ]:        5122 :                 assert(deq.end() - it == bitdeq.end() - bitit);
     196         [ +  + ]:        5122 :                 if (provider.ConsumeBool()) {
     197         [ +  + ]:        2889 :                     if ((size_t)pos2 != cdeq.size()) {
     198                 :        2161 :                         ++it;
     199                 :        2161 :                         ++bitit;
     200                 :             :                     }
     201                 :             :                 } else {
     202         [ +  + ]:        2233 :                     if (pos2 != 0) {
     203                 :        1620 :                         --it;
     204                 :        1620 :                         --bitit;
     205                 :             :                     }
     206                 :             :                 }
     207         [ -  + ]:        5122 :                 assert(deq.end() - it == bitdeq.end() - bitit);
     208                 :        5122 :             },
     209                 :        1822 :             [&] {
     210                 :             :                 // begin() and end()
     211         [ -  + ]:        1822 :                 assert(deq.end() - deq.begin() == bitdeq.end() - bitdeq.begin());
     212                 :        1822 :             },
     213                 :        2631 :             [&] {
     214                 :             :                 // begin() and end() (const)
     215         [ -  + ]:        2631 :                 assert(cdeq.end() - cdeq.begin() == cbitdeq.end() - cbitdeq.begin());
     216                 :        2631 :             },
     217                 :        2073 :             [&] {
     218                 :             :                 // rbegin() and rend()
     219         [ -  + ]:        2073 :                 assert(deq.rend() - deq.rbegin() == bitdeq.rend() - bitdeq.rbegin());
     220                 :        2073 :             },
     221                 :        1979 :             [&] {
     222                 :             :                 // rbegin() and rend() (const)
     223         [ -  + ]:        1979 :                 assert(cdeq.rend() - cdeq.rbegin() == cbitdeq.rend() - cbitdeq.rbegin());
     224                 :        1979 :             },
     225                 :        1462 :             [&] {
     226                 :             :                 // cbegin() and cend()
     227         [ -  + ]:        1462 :                 assert(cdeq.cend() - cdeq.cbegin() == cbitdeq.cend() - cbitdeq.cbegin());
     228                 :        1462 :             },
     229                 :        1797 :             [&] {
     230                 :             :                 // crbegin() and crend()
     231         [ -  + ]:        1797 :                 assert(cdeq.crend() - cdeq.crbegin() == cbitdeq.crend() - cbitdeq.crbegin());
     232                 :        1797 :             },
     233                 :        2633 :             [&] {
     234                 :             :                 // size() and maxsize()
     235         [ -  + ]:        2633 :                 assert(cdeq.size() == cbitdeq.size());
     236         [ -  + ]:        2633 :                 assert(cbitdeq.size() <= cbitdeq.max_size());
     237                 :        2633 :             },
     238                 :        2083 :             [&] {
     239                 :             :                 // empty
     240         [ -  + ]:        2083 :                 assert(cdeq.empty() == cbitdeq.empty());
     241                 :        2083 :             },
     242                 :        4260 :             [&] {
     243                 :             :                 // at (in range) and flip
     244         [ +  + ]:        4260 :                 if (!cdeq.empty()) {
     245                 :        3545 :                     size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
     246                 :        3545 :                     auto& ref = deq.at(pos);
     247                 :        3545 :                     auto bitref = bitdeq.at(pos);
     248         [ -  + ]:        3545 :                     assert(ref == bitref);
     249         [ +  + ]:        3545 :                     if (ctx.randbool()) {
     250                 :        1705 :                         ref = !ref;
     251                 :        1705 :                         bitref.flip();
     252                 :             :                     }
     253                 :        3545 :                 }
     254                 :        4260 :             },
     255                 :        8645 :             [&] {
     256                 :             :                 // at (maybe out of range) and bit assign
     257                 :        8645 :                 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
     258                 :        8645 :                 bool newval = ctx.randbool();
     259                 :        8645 :                 bool throw_deq{false}, throw_bitdeq{false};
     260                 :        8645 :                 bool val_deq{false}, val_bitdeq{false};
     261                 :        8645 :                 try {
     262         [ +  + ]:        8645 :                     auto& ref = deq.at(pos);
     263                 :        3026 :                     val_deq = ref;
     264                 :        3026 :                     ref = newval;
     265         [ -  + ]:        5619 :                 } catch (const std::out_of_range&) {
     266                 :        5619 :                     throw_deq = true;
     267                 :        5619 :                 }
     268                 :        8645 :                 try {
     269         [ +  + ]:        8645 :                     auto ref = bitdeq.at(pos);
     270                 :        3026 :                     val_bitdeq = ref;
     271                 :        3026 :                     ref = newval;
     272         [ -  + ]:        8645 :                 } catch (const std::out_of_range&) {
     273                 :        5619 :                     throw_bitdeq = true;
     274                 :        5619 :                 }
     275         [ -  + ]:        8645 :                 assert(throw_deq == throw_bitdeq);
     276         [ -  + ]:        8645 :                 assert(throw_bitdeq == (pos >= cdeq.size()));
     277   [ +  +  -  + ]:        8645 :                 if (!throw_deq) assert(val_deq == val_bitdeq);
     278                 :        8645 :             },
     279                 :        1633 :             [&] {
     280                 :             :                 // at (maybe out of range) (const)
     281                 :        1633 :                 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
     282                 :        1633 :                 bool throw_deq{false}, throw_bitdeq{false};
     283                 :        1633 :                 bool val_deq{false}, val_bitdeq{false};
     284                 :        1633 :                 try {
     285         [ +  + ]:        1633 :                     auto& ref = cdeq.at(pos);
     286                 :         922 :                     val_deq = ref;
     287         [ -  + ]:         711 :                 } catch (const std::out_of_range&) {
     288                 :         711 :                     throw_deq = true;
     289                 :         711 :                 }
     290                 :        1633 :                 try {
     291         [ +  + ]:        1633 :                     auto ref = cbitdeq.at(pos);
     292                 :             :                     val_bitdeq = ref;
     293         [ -  + ]:         711 :                 } catch (const std::out_of_range&) {
     294                 :         711 :                     throw_bitdeq = true;
     295                 :         711 :                 }
     296         [ -  + ]:        1633 :                 assert(throw_deq == throw_bitdeq);
     297         [ -  + ]:        1633 :                 assert(throw_bitdeq == (pos >= cdeq.size()));
     298   [ +  +  -  + ]:        1633 :                 if (!throw_deq) assert(val_deq == val_bitdeq);
     299                 :        1633 :             },
     300                 :        4729 :             [&] {
     301                 :             :                 // operator[]
     302         [ +  + ]:        4729 :                 if (!cdeq.empty()) {
     303                 :        4218 :                     size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
     304         [ -  + ]:        4218 :                     assert(deq[pos] == bitdeq[pos]);
     305         [ +  + ]:        4218 :                     if (ctx.randbool()) {
     306                 :        2119 :                         deq[pos] = !deq[pos];
     307                 :        2119 :                         bitdeq[pos].flip();
     308                 :             :                     }
     309                 :             :                 }
     310                 :        4729 :             },
     311                 :        1525 :             [&] {
     312                 :             :                 // operator[] const
     313         [ +  + ]:        1525 :                 if (!cdeq.empty()) {
     314                 :         951 :                     size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
     315         [ -  + ]:         951 :                     assert(deq[pos] == bitdeq[pos]);
     316                 :             :                 }
     317                 :        1525 :             },
     318                 :        3860 :             [&] {
     319                 :             :                 // front()
     320         [ +  + ]:        3860 :                 if (!cdeq.empty()) {
     321         [ -  + ]:        3277 :                     auto& ref = deq.front();
     322                 :        3277 :                     auto bitref = bitdeq.front();
     323         [ -  + ]:        3277 :                     assert(ref == bitref);
     324         [ +  + ]:        3277 :                     if (ctx.randbool()) {
     325                 :        1594 :                         ref = !ref;
     326                 :        1594 :                         bitref = !bitref;
     327                 :             :                     }
     328                 :        3277 :                 }
     329                 :        3860 :             },
     330                 :        1568 :             [&] {
     331                 :             :                 // front() const
     332         [ +  + ]:        1568 :                 if (!cdeq.empty()) {
     333         [ -  + ]:        1009 :                     auto& ref = cdeq.front();
     334                 :        1009 :                     auto bitref = cbitdeq.front();
     335         [ -  + ]:        1009 :                     assert(ref == bitref);
     336                 :             :                 }
     337                 :        1568 :             },
     338                 :        4164 :             [&] {
     339                 :             :                 // back() and swap(bool, ref)
     340         [ +  + ]:        4164 :                 if (!cdeq.empty()) {
     341                 :        3437 :                     auto& ref = deq.back();
     342                 :        3437 :                     auto bitref = bitdeq.back();
     343         [ -  + ]:        3437 :                     assert(ref == bitref);
     344         [ +  + ]:        3437 :                     if (ctx.randbool()) {
     345                 :        1743 :                         ref = !ref;
     346                 :        1743 :                         bitref.flip();
     347                 :             :                     }
     348                 :        3437 :                 }
     349                 :        4164 :             },
     350                 :        3005 :             [&] {
     351                 :             :                 // back() const
     352         [ +  + ]:        3005 :                 if (!cdeq.empty()) {
     353                 :        2114 :                     const auto& cdeq = deq;
     354                 :        2114 :                     const auto& cbitdeq = bitdeq;
     355                 :        2114 :                     auto& ref = cdeq.back();
     356                 :        2114 :                     auto bitref = cbitdeq.back();
     357         [ -  + ]:        2114 :                     assert(ref == bitref);
     358                 :             :                 }
     359                 :        3005 :             },
     360                 :        5675 :             [&] {
     361                 :             :                 // push_back()
     362         [ +  + ]:        5675 :                 if (cdeq.size() < limitlen) {
     363                 :        5247 :                     bool val = ctx.randbool();
     364         [ +  + ]:        5247 :                     if (cdeq.empty()) {
     365                 :        2004 :                         deq.push_back(val);
     366                 :        2004 :                         bitdeq.push_back(val);
     367                 :             :                     } else {
     368                 :        3243 :                         size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
     369                 :        3243 :                         auto& ref = deq[pos];
     370                 :        3243 :                         auto bitref = bitdeq[pos];
     371         [ -  + ]:        3243 :                         assert(ref == bitref);
     372                 :        3243 :                         deq.push_back(val);
     373                 :        3243 :                         bitdeq.push_back(val);
     374         [ -  + ]:        3243 :                         assert(ref == bitref); // references are not invalidated
     375                 :        3243 :                     }
     376                 :             :                 }
     377                 :        5675 :             },
     378                 :        8516 :             [&] {
     379                 :             :                 // push_front()
     380         [ +  + ]:        8516 :                 if (cdeq.size() < limitlen) {
     381                 :        7959 :                     bool val = ctx.randbool();
     382         [ +  + ]:        7959 :                     if (cdeq.empty()) {
     383                 :        2753 :                         deq.push_front(val);
     384                 :        2753 :                         bitdeq.push_front(val);
     385                 :             :                     } else {
     386                 :        5206 :                         size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
     387                 :        5206 :                         auto& ref = deq[pos];
     388                 :        5206 :                         auto bitref = bitdeq[pos];
     389         [ -  + ]:        5206 :                         assert(ref == bitref);
     390                 :        5206 :                         deq.push_front(val);
     391                 :        5206 :                         bitdeq.push_front(val);
     392         [ -  + ]:        5206 :                         assert(ref == bitref); // references are not invalidated
     393                 :        5206 :                     }
     394                 :             :                 }
     395                 :        8516 :             },
     396                 :        4401 :             [&] {
     397                 :             :                 // pop_back()
     398         [ +  + ]:        4401 :                 if (!cdeq.empty()) {
     399         [ +  + ]:        3605 :                     if (cdeq.size() == 1) {
     400                 :        1166 :                         deq.pop_back();
     401                 :        1166 :                         bitdeq.pop_back();
     402                 :             :                     } else {
     403                 :        2439 :                         size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 2);
     404                 :        2439 :                         auto& ref = deq[pos];
     405                 :        2439 :                         auto bitref = bitdeq[pos];
     406         [ -  + ]:        2439 :                         assert(ref == bitref);
     407                 :        2439 :                         deq.pop_back();
     408                 :        2439 :                         bitdeq.pop_back();
     409         [ -  + ]:        2439 :                         assert(ref == bitref); // references to other elements are not invalidated
     410                 :        2439 :                     }
     411                 :             :                 }
     412                 :        4401 :             },
     413                 :        5090 :             [&] {
     414                 :             :                 // pop_front()
     415         [ +  + ]:        5090 :                 if (!cdeq.empty()) {
     416         [ +  + ]:        3770 :                     if (cdeq.size() == 1) {
     417                 :        1586 :                         deq.pop_front();
     418                 :        1586 :                         bitdeq.pop_front();
     419                 :             :                     } else {
     420                 :        2184 :                         size_t pos = provider.ConsumeIntegralInRange<size_t>(1, cdeq.size() - 1);
     421                 :        2184 :                         auto& ref = deq[pos];
     422                 :        2184 :                         auto bitref = bitdeq[pos];
     423         [ -  + ]:        2184 :                         assert(ref == bitref);
     424                 :        2184 :                         deq.pop_front();
     425                 :        2184 :                         bitdeq.pop_front();
     426         [ -  + ]:        2184 :                         assert(ref == bitref); // references to other elements are not invalidated
     427                 :        2184 :                     }
     428                 :             :                 }
     429                 :        5090 :             },
     430                 :        5842 :             [&] {
     431                 :             :                 // erase (in middle, single)
     432         [ +  + ]:        5842 :                 if (!cdeq.empty()) {
     433                 :        4865 :                     size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
     434                 :        4865 :                     size_t after = cdeq.size() - 1 - before;
     435                 :        4865 :                     auto it = deq.erase(cdeq.begin() + before);
     436                 :        4865 :                     auto bitit = bitdeq.erase(cbitdeq.begin() + before);
     437   [ +  -  -  + ]:        4865 :                     assert(it == cdeq.begin() + before && it == cdeq.end() - after);
     438   [ +  -  +  - ]:        9730 :                     assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
     439                 :             :                 }
     440                 :        5842 :             },
     441                 :        6221 :             [&] {
     442                 :             :                 // erase (at front, range)
     443                 :        6221 :                 size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
     444                 :        6221 :                 auto it = deq.erase(cdeq.begin(), cdeq.begin() + count);
     445                 :        6221 :                 auto bitit = bitdeq.erase(cbitdeq.begin(), cbitdeq.begin() + count);
     446         [ -  + ]:        6221 :                 assert(it == deq.begin());
     447         [ +  - ]:        6221 :                 assert(bitit == bitdeq.begin());
     448                 :        6221 :             },
     449                 :        2648 :             [&] {
     450                 :             :                 // erase (at back, range)
     451                 :        2648 :                 size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
     452                 :        2648 :                 auto it = deq.erase(cdeq.end() - count, cdeq.end());
     453                 :        2648 :                 auto bitit = bitdeq.erase(cbitdeq.end() - count, cbitdeq.end());
     454         [ -  + ]:        2648 :                 assert(it == deq.end());
     455         [ +  - ]:        2648 :                 assert(bitit == bitdeq.end());
     456                 :        2648 :             },
     457                 :        3938 :             [&] {
     458                 :             :                 // erase (in middle, range)
     459                 :        3938 :                 size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
     460                 :        3938 :                 size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - count);
     461                 :        3938 :                 size_t after = cdeq.size() - count - before;
     462                 :        3938 :                 auto it = deq.erase(cdeq.begin() + before, cdeq.end() - after);
     463                 :        3938 :                 auto bitit = bitdeq.erase(cbitdeq.begin() + before, cbitdeq.end() - after);
     464   [ +  -  -  + ]:        3938 :                 assert(it == cdeq.begin() + before && it == cdeq.end() - after);
     465   [ +  -  +  - ]:        7876 :                 assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
     466                 :        3938 :             },
     467                 :        9228 :             [&] {
     468                 :             :                 // insert/emplace (in middle, single)
     469         [ +  + ]:        9228 :                 if (cdeq.size() < limitlen) {
     470                 :        8729 :                     size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
     471                 :        8729 :                     bool val = ctx.randbool();
     472                 :        8729 :                     bool do_emplace = provider.ConsumeBool();
     473                 :        8729 :                     auto it = deq.insert(cdeq.begin() + before, val);
     474         [ +  + ]:        8729 :                     auto bitit = do_emplace ? bitdeq.emplace(cbitdeq.begin() + before, val)
     475                 :        8729 :                                             : bitdeq.insert(cbitdeq.begin() + before, val);
     476         [ -  + ]:        8729 :                     assert(it == deq.begin() + before);
     477         [ +  - ]:        8729 :                     assert(bitit == bitdeq.begin() + before);
     478                 :             :                 }
     479                 :        9228 :             },
     480                 :        6992 :             [&] {
     481                 :             :                 // insert (at front, begin/end)
     482         [ +  + ]:        6992 :                 if (cdeq.size() < limitlen) {
     483                 :        6454 :                     size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
     484                 :        6454 :                     auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
     485                 :        6454 :                     auto rand_end = rand_begin + count;
     486                 :        6454 :                     auto it = deq.insert(cdeq.begin(), rand_begin, rand_end);
     487                 :        6454 :                     auto bitit = bitdeq.insert(cbitdeq.begin(), rand_begin, rand_end);
     488         [ -  + ]:        6454 :                     assert(it == cdeq.begin());
     489         [ +  - ]:        6454 :                     assert(bitit == cbitdeq.begin());
     490                 :             :                 }
     491                 :        6992 :             },
     492                 :        5358 :             [&] {
     493                 :             :                 // insert (at back, begin/end)
     494         [ +  + ]:        5358 :                 if (cdeq.size() < limitlen) {
     495                 :        4595 :                     size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
     496                 :        4595 :                     auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
     497                 :        4595 :                     auto rand_end = rand_begin + count;
     498                 :        4595 :                     auto it = deq.insert(cdeq.end(), rand_begin, rand_end);
     499                 :        4595 :                     auto bitit = bitdeq.insert(cbitdeq.end(), rand_begin, rand_end);
     500         [ -  + ]:        4595 :                     assert(it == cdeq.end() - count);
     501         [ +  - ]:        4595 :                     assert(bitit == cbitdeq.end() - count);
     502                 :             :                 }
     503                 :        5358 :             },
     504                 :       18041 :             [&] {
     505                 :             :                 // insert (in middle, range)
     506         [ +  + ]:       18041 :                 if (cdeq.size() < limitlen) {
     507                 :       14944 :                     size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
     508                 :       14944 :                     size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
     509                 :       14944 :                     bool val = ctx.randbool();
     510                 :       14944 :                     auto it = deq.insert(cdeq.begin() + before, count, val);
     511                 :       14944 :                     auto bitit = bitdeq.insert(cbitdeq.begin() + before, count, val);
     512         [ -  + ]:       14944 :                     assert(it == deq.begin() + before);
     513         [ +  - ]:       14944 :                     assert(bitit == bitdeq.begin() + before);
     514                 :             :                 }
     515                 :       18041 :             },
     516                 :       14986 :             [&] {
     517                 :             :                 // insert (in middle, begin/end)
     518         [ +  + ]:       14986 :                 if (cdeq.size() < limitlen) {
     519                 :       13133 :                     size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
     520                 :       13133 :                     size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
     521                 :       13133 :                     auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
     522                 :       13133 :                     auto rand_end = rand_begin + count;
     523                 :       13133 :                     auto it = deq.insert(cdeq.begin() + before, rand_begin, rand_end);
     524                 :       13133 :                     auto bitit = bitdeq.insert(cbitdeq.begin() + before, rand_begin, rand_end);
     525         [ -  + ]:       13133 :                     assert(it == deq.begin() + before);
     526         [ +  - ]:       13133 :                     assert(bitit == bitdeq.begin() + before);
     527                 :             :                 }
     528                 :       14986 :             });
     529                 :             :     }
     530                 :         722 :     {
     531         [ -  + ]:         722 :         assert(deq.size() == bitdeq.size());
     532                 :         722 :         auto it = deq.begin();
     533                 :         722 :         auto bitit = bitdeq.begin();
     534                 :         722 :         auto itend = deq.end();
     535         [ +  + ]:     7608706 :         while (it != itend) {
     536         [ -  + ]:     7607984 :             assert(*it == *bitit);
     537                 :     7607984 :             ++it;
     538                 :     7607984 :             ++bitit;
     539                 :             :         }
     540                 :             :     }
     541                 :         722 : }
        

Generated by: LCOV version 2.0-1