refactor: Fix prevector iterator concept issues #29275

1. 
   maflcko commented at 3:01 pm on January 18, 2024: member

   Currently prevector iterators have many issues:

   • Forward iterators (and stronger) must be default constructible (https://eel.is/c++draft/forward.iterators#1.2). Otherwise, some functions can not be instantiated, like std::minmax_element.
   • Various const issues with random access iterators. For example, a const iterator is different from a const_iterator, because the first one holds a mutable reference and must also return it without const. Also, operator+ must be callable regardless of the iterator object’s const-ness.
   • When adding an offset to random access iterators, both x+n and n+x must be specified, see https://eel.is/c++draft/random.access.iterators#tab:randomaccessiterator

   Fix all issues.

   Also, upgrade the std::random_access_iterator_tag (C++17) to std::contiguous_iterator_tag (C++20)

2. refactor: Add missing default constructor to prevector iterators facaa66b49
3. refactor: Fix constness for prevector iterators fa44a60b2b
4. refactor: Fix binary operator+ for prevector iterators fab8a01048
5. 
   DrahtBot commented at 3:01 pm on January 18, 2024: contributor

   The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

   Code Coverage

   For detailed information about the code coverage, see the test coverage report.

   Reviews

   See the guideline for information on the review process.

   Type	Reviewers
   ACK	TheCharlatan, stickies-v, willcl-ark

   If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

   Conflicts

   Reviewers, this pull request conflicts with the following ones:

   • #29119 (refactor: Use std::span over Span by maflcko)

   If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

6. DrahtBot added the label Refactoring on Jan 18, 2024
7. DrahtBot added the label CI failed on Jan 18, 2024
8. 
   DrahtBot commented at 4:38 pm on January 18, 2024: contributor

   🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

   Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

   Leave a comment here, if you need help tracking down a confusing failure.

   Debug: https://github.com/bitcoin/bitcoin/runs/20620445160

9. refactor: Mark prevector iterator with std::contiguous_iterator_tag fad74bbbd0
10. maflcko force-pushed on Jan 18, 2024
11. DrahtBot removed the label CI failed on Jan 18, 2024
12. 
    maflcko commented at 7:54 pm on January 18, 2024: member

    Fixed libc++ CIs
13. DrahtBot added the label CI failed on Jan 19, 2024
14. DrahtBot removed the label CI failed on Jan 19, 2024
15. 
    luke-jr commented at 4:26 am on January 23, 2024: member

    Can we split the fixes from the C++20 stuff? The latter shouldn’t be backported…
16. 
    maflcko commented at 7:48 am on January 23, 2024: member

    While it is safe to backport, I don’t anything should be backported, unless there is a reason and need. A missing (default) constructor, if it was needed, would result in a compile failure. Given that the previous releases compile, this is not needed. Similar arguments can be made for the other commits.

    In any case, every commit is already a separate commit, so it is not possible to split further. Anyone is free to backport any or all commits, or none at all.

17. TheCharlatan approved
18. 
    TheCharlatan commented at 11:39 am on January 29, 2024: contributor

    ACK fad74bbbd0ab4425573f182ebde1b31a99e80547

    Could the bitdeque iterator also get std::contiguous_iterator_tag?

19. 
    maflcko commented at 12:07 pm on January 29, 2024: member

    Could the bitdeque iterator also get std::contiguous_iterator_tag?

    No. As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector’s indexed access which performs only one. (Copied from source: https://en.cppreference.com/w/cpp/container/deque)

    Also, even if a deque was contiguous, only bitdeque::Iterator::deque_iterator would be contiguous. Not bitdeque::Iterator, because std::addressof(std::bitset::reference) is deleted.

20. fanquake requested review from willcl-ark on Jan 31, 2024
21. stickies-v approved
22. 
    stickies-v commented at 4:36 pm on January 31, 2024: contributor

    ACK fad74bbbd0ab4425573f182ebde1b31a99e80547
23. willcl-ark approved
24. 
    willcl-ark commented at 3:50 pm on February 1, 2024: contributor

    ACK fad74bbbd0ab4425573f182ebde1b31a99e80547

    Nice enhancements to safety, usability and standards.

25. fanquake merged this on Feb 1, 2024
26. fanquake closed this on Feb 1, 2024

    ---

27. maflcko deleted the branch on Feb 1, 2024

Contributors
maflcko DrahtBot luke-jr TheCharlatan stickies-v willcl-ark

Labels
Refactoring