LCOV - code coverage report
Current view: top level - src/test/fuzz - bitdeque.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 2 451 0.4 %
Date: 2023-11-06 23:13:05 Functions: 1 51 2.0 %
Branches: 1 294 0.3 %

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

Generated by: LCOV version 1.14