C++20 std::views::reverse

stickies-v commented at 12:37 pm on October 19, 2023: contributor

C++20 introduces std::ranges::views::reverse, which allows us to drop our own reverse_iterator.h implementation and also makes it easier to chain views (even though I think we currently don’t use this).

DrahtBot commented at 12:37 pm on October 19, 2023: 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	achow101, maflcko

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:

#29700 (kernel, refactor: return error status on all fatal errors by ryanofsky)

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.

fanquake commented at 12:39 pm on October 19, 2023: member

cc @sipa you might have some insight here in regards to prevector.

DrahtBot added the label CI failed on Oct 19, 2023

DrahtBot added the label Needs rebase on Nov 22, 2023

stickies-v force-pushed on Nov 22, 2023

DrahtBot removed the label Needs rebase on Nov 22, 2023

DrahtBot added the label Needs rebase on Dec 1, 2023

stickies-v force-pushed on Dec 2, 2023

DrahtBot removed the label Needs rebase on Dec 2, 2023

maflcko commented at 5:49 pm on December 11, 2023: member

WIP: our prevector implementation requires modification for std::ranges::views::reverse to work. More specifically: it needs to implement the bidirectional_range concept, which currently it seems not to (see static_assert(std::ranges::bidirectional_range<prevector>) output below) as we’re not satisfying range. Once that’s done, we can update the last usage of reverse_iterator.h here and here and remove the header entirely.

That is also required by std::span.

stickies-v force-pushed on Dec 11, 2023

stickies-v renamed this:
~~[POC][WIP] C++20 std::views::reverse~~
[WIP] C++20 std::views::reverse
on Dec 11, 2023

stickies-v commented at 6:51 pm on December 11, 2023: contributor

Needs rebase

Thx, rebased to include #28349 & updated PR description

fanquake commented at 11:21 am on December 12, 2023: member

https://github.com/bitcoin/bitcoin/pull/28687/checks?check_run_id=19528202548

0/usr/bin/ccache clang++-13 -stdlib=libc++ -std=c++20 -DHAVE_CONFIG_H -I. -I../src/config  -fmacro-prefix-map=/ci_container_base/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu=. -U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=3 -DHAVE_BUILD_INFO -DPROVIDE_FUZZ_MAIN_FUNCTION -I. -I./minisketch/include -I./secp256k1/include -I./univalue/include -I./leveldb/include -isystem /ci_container_base/depends/x86_64-pc-linux-gnu/include -DBOOST_MULTI_INDEX_DISABLE_SERIALIZATION -DBOOST_NO_CXX98_FUNCTION_BASE   -isystem /ci_container_base/depends/x86_64-pc-linux-gnu/include -pthread -I/ci_container_base/depends/x86_64-pc-linux-gnu/include  -I/ci_container_base/depends/x86_64-pc-linux-gnu/include/  -fdebug-prefix-map=/ci_container_base/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu=. -Wstack-protector -fstack-protector-all -fcf-protection=full -fstack-clash-protection   -Werror    -fvisibility=hidden -fPIE -pipe -std=c++20 -O2  -c -o libbitcoin_node_a-net_processing.o `test -f 'net_processing.cpp' || echo './'`net_processing.cpp
1net_processing.cpp:2074:62: error: no member named 'reverse' in namespace 'std::views'
2            for (const uint256& hash : vHashes | std::views::reverse) {
3                                                 ~~~~~~~~~~~~^
4net_processing.cpp:2760:69: error: no member named 'reverse' in namespace 'std::views'
5            for (const CBlockIndex *pindex : vToFetch | std::views::reverse) {
6                                                        ~~~~~~~~~~~~^
72 errors generated.

Looks like ranges didn’t become complete / non-experimental in LLVM until version 16: https://releases.llvm.org/16.0.0/projects/libcxx/docs/ReleaseNotes.html

The C++20 ranges library has been completed and is no longer experimental (with the exception of ranges::join_view which is still marked as experimental because it is about to undergo an ABI-breaking change in the Standard due to D2770). Work on C++23 ranges has started.

Note that prior versions of LLVM required distros/venders to compile with special flags, so I assume it’s just not going to be generally available until 16? i.e from the LLVM 14 release notes:

More parts of ranges have been implemented. Since we still expect to make some API and ABI breaking changes, those are disabled by default. However, vendors that wish to enable in their distribution may do so by defining -DLIBCXX_ENABLE_INCOMPLETE_FEATURES=ON when configuring their build.

maflcko commented at 12:03 pm on December 12, 2023: member

Hmm, there’s no clang-16 in the current LTS release of Ubuntu, so I guess this will have to wait for some time.

https://packages.ubuntu.com/jammy/clang-16

I wonder whether std::span will be usable, given that it internally assumes ranges?

maflcko added the label DrahtBot Guix build requested on Dec 13, 2023

DrahtBot commented at 10:23 pm on December 13, 2023: contributor

Guix builds (on x86_64)

File	commit f0e829022a415c7c9513e715c532079ec7756306(master)	commit 2a92fac6906073cf9344d192c0c67b3072a86815(master and this pull)
SHA256SUMS.part	`7997d8e0220138cc...`	`3e66821911a14934...`
*-aarch64-linux-gnu-debug.tar.gz	`c2d1d518af6b6690...`	`71cd2844ef1594e9...`
*-aarch64-linux-gnu.tar.gz	`24b6219549eb167f...`	`62103870da8375e6...`
*-arm-linux-gnueabihf-debug.tar.gz	`43d2f9e984064b30...`	`95c903521454832f...`
*-arm-linux-gnueabihf.tar.gz	`62029d495b06ae94...`	`2bec136fd3d597e5...`
*-arm64-apple-darwin-unsigned.tar.gz	`5940ccb123abcb6f...`	`80071654801bc8bb...`
*-arm64-apple-darwin-unsigned.zip	`5f9ad735e43975c2...`	`cadd46af1fd698b9...`
*-arm64-apple-darwin.tar.gz	`4fb329d17e653ace...`	`09bc2dd4f449aaa0...`
*-powerpc64-linux-gnu-debug.tar.gz	`b89080b50e79f418...`	`1e1c09db73cbc3cf...`
*-powerpc64-linux-gnu.tar.gz	`958122ba55627d09...`	`71e4c7cea959d564...`
*-powerpc64le-linux-gnu-debug.tar.gz	`3b193a6facbfaca1...`	`55c83a7292bcdef5...`
*-powerpc64le-linux-gnu.tar.gz	`133288419542c1bc...`	`c1987c5dc27c19a0...`
*-riscv64-linux-gnu-debug.tar.gz	`497e98ac63114289...`	`6ec70782d4801883...`
*-riscv64-linux-gnu.tar.gz	`46bbcb20a8f21119...`	`7d0da4d25a6f60c5...`
*-x86_64-apple-darwin-unsigned.tar.gz	`ab343d4c4677f67c...`	`64c41cb674a66651...`
*-x86_64-apple-darwin-unsigned.zip	`ac24b8017268700b...`	`99a2559f0b3845b0...`
*-x86_64-apple-darwin.tar.gz	`eb8a6f37e0bb38de...`	`0b2972137b3a2a6b...`
*-x86_64-linux-gnu-debug.tar.gz	`6b25557dcc1c1ac2...`	`31655748d794c403...`
*-x86_64-linux-gnu.tar.gz	`7edcc22d840d9362...`	`9d6ba3a813312f33...`
*.tar.gz	`846962d7c9f05011...`	`d351b109a6580b69...`
guix_build.log	`7c8dff6c68055a73...`	`79e8210da9e68cc4...`
guix_build.log.diff		`1520c94a16f066b4...`

DrahtBot removed the label DrahtBot Guix build requested on Dec 13, 2023

maflcko commented at 8:41 am on December 14, 2023: member

Interesting that the guix macOS build passed, given that it is on clang-15, no?

fanquake commented at 9:51 am on December 14, 2023: member

Interesting that the guix macOS build passed, given that it is on clang-15, no?

I’d guess this is because our macOS SDK (libc++) is from Xcode 15, which is based on LLVM ~16, and includes support for ranges. So as long as clang-15 can compile it, which it should given vanilla LLVM supports the use of ranges (experimentally) in 15, it probably works.

maflcko commented at 10:19 am on December 14, 2023: member

Oh, I guess clang-15 can use libc++-16, but not libstdc++, according to https://godbolt.org/z/dbKWeE8Te and https://github.com/llvm/llvm-project/commit/babdef27c503c0bbbcc017e9f88affddda90ea4e ?

maflcko commented at 10:04 am on December 20, 2023: member

Though, on GHA it says XCode 14.3, see https://github.com/bitcoin/bitcoin/actions/runs/7171999335/job/19528203033?pr=28687#step:3:14

0clang --version
1Apple clang version 14.0.3 (clang-1403.0.22.14.1)
2Target: x86_64-apple-darwin22.6.0
3Thread model: posix
4InstalledDir: /Applications/Xcode_14.3.1.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

fanquake commented at 10:09 am on December 20, 2023: member

Though, on GHA it says XCode 14.3

According to https://developer.apple.com/xcode/cpp/#c++20, “Ranges” have been available on macOS since Xcode 14.3.

maflcko commented at 7:50 am on January 23, 2024: member

WIP: our prevector implementation requires modification for std::ranges::views::reverse to work. More specifically: it needs to implement the bidirectional_range concept, which currently it seems not to (see static_assert(std::ranges::bidirectional_range<prevector>) output below) as we’re not satisfying range. Once that’s done, we can update the last usage of reverse_iterator.h here and here and remove the header entirely.

That is also required by std::span.

(Possibly?) fixed in https://github.com/bitcoin/bitcoin/pull/29275

fanquake commented at 3:05 pm on January 24, 2024: member

(Possibly?) fixed in #29275

Looks like it does, this compiles for me locally atleast: https://github.com/fanquake/bitcoin/tree/28687_29275. @stickies-v can you rebase this branch on top of #29275.

stickies-v force-pushed on Jan 30, 2024

fanquake commented at 4:46 pm on February 1, 2024: member

Could rebase, and update the PR description? Ideally this is now just blocked on our supported compiler versions.

stickies-v force-pushed on Feb 2, 2024

stickies-v commented at 2:16 pm on February 2, 2024: contributor

Force pushed to rebase, added a commit to bump compilers of failing CI tasks (see OP), not too sure what I’m doing here though.

stickies-v force-pushed on Feb 2, 2024

DrahtBot removed the label CI failed on Feb 2, 2024

fanquake renamed this:
~~[WIP] C++20 std::views::reverse~~
C++20 std::views::reverse
on Mar 6, 2024

fanquake added this to the milestone 28.0 on Mar 6, 2024

DrahtBot added the label Needs rebase on Mar 11, 2024

stickies-v force-pushed on Mar 11, 2024

stickies-v commented at 2:45 pm on March 11, 2024: contributor

Force pushed to address merge conflict from #29483

DrahtBot removed the label Needs rebase on Mar 11, 2024

DrahtBot added the label Needs rebase on Mar 18, 2024

stickies-v force-pushed on Mar 18, 2024

DrahtBot removed the label Needs rebase on Mar 18, 2024

stickies-v force-pushed on Mar 18, 2024

DrahtBot added the label CI failed on Mar 18, 2024

DrahtBot commented at 11:47 pm on March 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/22798928866

stickies-v commented at 11:53 pm on March 18, 2024: contributor

Force pushed to:

rebase after #29091 got merged, which now makes the previous releases, depends DEBUG task pass
rebase on top of #29165 (e95d88b197cd49040b693f33367e055dbf90b276), which will make multiprocess, i686, DEBUG pass when merged

no wallet, libbitcoinkernel is now the only remaining unadressed failing CI task, afaict requiring a bump to clang-16 too

DrahtBot removed the label CI failed on Mar 19, 2024

DrahtBot added the label Needs rebase on Apr 1, 2024

stickies-v force-pushed on Apr 1, 2024

stickies-v commented at 4:17 pm on April 1, 2024: contributor

Rebased on top of #29765. One more task to go 🤞

DrahtBot removed the label Needs rebase on Apr 1, 2024

DrahtBot added the label CI failed on Apr 1, 2024

DrahtBot removed the label CI failed on Apr 5, 2024

stickies-v force-pushed on Apr 5, 2024

DrahtBot added the label Needs rebase on Apr 29, 2024

stickies-v force-pushed on Apr 29, 2024

DrahtBot removed the label Needs rebase on Apr 29, 2024

DrahtBot added the label Needs rebase on Jun 11, 2024

stickies-v force-pushed on Jun 12, 2024

stickies-v commented at 10:40 am on June 12, 2024: contributor

Force pushed to address merge conflict from #28830 and rebase on top of #30263

DrahtBot removed the label Needs rebase on Jun 12, 2024

stickies-v force-pushed on Jul 8, 2024

stickies-v marked this as ready for review on Jul 8, 2024

stickies-v commented at 5:27 pm on July 8, 2024: contributor

With #30263 merged, this PR is now ready for review 🥳

DrahtBot added the label Needs rebase on Aug 5, 2024

refactor: use c++20 std::views::reverse instead of reverse_iterator.h

Use std::ranges::views::reverse instead of the implementation in
reverse_iterator.h, and remove it as it is no longer used.

2925bd537c

stickies-v force-pushed on Aug 5, 2024

stickies-v commented at 11:25 pm on August 5, 2024: contributor

Force pushed to address merge conflict from https://github.com/bitcoin/bitcoin/pull/28052/

DrahtBot removed the label Needs rebase on Aug 6, 2024

achow101 commented at 6:54 pm on August 8, 2024: member

ACK 2925bd537cbd8c70594e23f6c4298b7101f7f73d

maflcko commented at 6:52 am on August 9, 2024: member

ACK 2925bd537cbd8c70594e23f6c4298b7101f7f73d 🎷

Signature:

0untrusted comment: signature from minisign secret key on empty file; verify via: minisign -Vm "${path_to_any_empty_file}" -P RWTRmVTMeKV5noAMqVlsMugDDCyyTSbA3Re5AkUrhvLVln0tSaFWglOw -x "${path_to_this_whole_four_line_signature_blob}"
1RUTRmVTMeKV5npGrKx1nqXCw5zeVHdtdYURB/KlyA/LMFgpNCs+SkW9a8N95d+U4AP1RJMi+krxU1A3Yux4bpwZNLvVBKy0wLgM=
2trusted comment: ACK 2925bd537cbd8c70594e23f6c4298b7101f7f73d 🎷
3hdWxKaQlmycdmMRya28H4AKptHOQLgq//CDoWCwS6QAA5hcnhTRD1nkFbYpGtK6moizOMjisBVHALD8qIuYNAA==

fanquake merged this on Aug 9, 2024

fanquake closed this on Aug 9, 2024

TheCharlatan commented at 8:56 am on August 9, 2024: contributor

Post-merge ACK 2925bd537cbd8c70594e23f6c4298b7101f7f73d

stickies-v deleted the branch on Aug 9, 2024

C++20 std::views::reverse #28687

Code Coverage

Reviews

Conflicts

Guix builds (on x86_64)