Also implement in_out_result which is a prerequisite.
Details
- Reviewers
• Quuxplusone ldionne - Group Reviewers
Restricted Project - Commits
- rG8d23b7420c92: [libc++][ranges] Implement `uninitialized_copy{,_n}` and `uninitialized_move{…
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
libcxx/include/__memory/uninitialized_algorithms.h | ||
---|---|---|
28 | This class is to allow the non-ranges versions of algorithms operating on two sequences to use the same internal implementation (because the non-ranges versions only provide the beginning of the output range, so some placeholder is necessary for the end of the output range). | |
39 | Note: __compressed_pair cannot be used here because it doesn't support its two types being the same type. tuple, which supports EBO, also cannot be used here because uninitialized_copy must be available in the C++03 mode. | |
41 | I made some refactorings throughout to make the implementations in this file to be more similar to each other (using same names and similar code flow). | |
45–46 | From a quick look at the Standard's definition of unreachable_sentinel, it only defines operator== (not !=) and the sentinel is the first argument. I didn't want to expand the interface, hence the somewhat convoluted comparison here. However, maybe I'm missing something and other forms of comparison are synthesized somehow for unreachable_sentinel? | |
282 | There is an important implementation difference between the ranges- and non-ranges versions of uninitialized_move: the old version simply calls std::move on each element, while the ranges version calls std::ranges::iter_move, which is a customization point. To avoid maintaining two parallel implementations, use a functor. | |
283 | Note: I could use tuple here to get EBO (suggested by @ldionne). I'm a little concerned about consistency with the very similar uninitialized_copy algorithm (though it can be argues that uninitialized_move already diverges quite a bit). Happy to change to tuple if other people feel it's appropriate here. | |
libcxx/include/memory | ||
185 | For entities in the nested ranges namespace, is it preferable to specify them like this: template <class A, class B> ranges::foo_result ranges::foo(A a, B b); or like this: namespace ranges { template <class A, class B> foo_result foo(A a, B b); } ? |
libcxx/include/__memory/uninitialized_algorithms.h | ||
---|---|---|
45–46 | Yes, C++20's operator-spaceship feature includes the ability to create "rewritten candidates," so that a < b might actually call (a <=> b) < 0 or 0 < (b <=> a), and a != b might actually call !(a == b) or !(b == a). My first impression here is that the benefits of sharing this code between C++11 and C++20 are outweighed by the costs, and we should just write a new file <__memory/ranges_uninitialized_algorithms.h> without trying to share code at all. Actually, didn't we already do that? <__memory/ranges_uninitialized_algorithms.h> seems to exist! Can you double-check how this PR interacts with whatever PR introduced <__memory/ranges_uninitialized_algorithms.h> already? However, you can at least simplify the C++11 codepath by making your new C++11-friendly __unreachable_sentinel provide friend bool operator!=(const _Iter&, __unreachable_sentinel) (and nothing else), because that's the unwritten syntactic requirement implied by the body of the (old) C++11 function template __uninitialized_copy. The template does require (it != sent) to compile, so your sentinel type should provide that operator. The template does not require (sent == it) to compile, so (to keep things simple) your sentinel type should not provide that operator. | |
libcxx/include/memory | ||
185 | The precedent here is "do as https://eel.is/c++draft/memory.syn does" (which means reopen namespace ranges). | |
libcxx/include/module.modulemap | ||
223 | (1, moot) Inconsistent pluralization here. | |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.copy/ranges_uninitialized_copy.pass.cpp | ||
34–37 | FWIW, ultimately we'll probably want to move all these assertions into one centralized place similar to what @jloser did with the "customization point" CPOs and as I did with ADL-proofing and predicate-copying. Otherwise ultimately you're spending 4 lines in each of 100 different test files, and you probably end up missing a few dozen without noticing. | |
61 | Style nit: I'd prefer auto it = forward_iterator<Counted*>(in); for readability. ( https://quuxplusone.github.io/blog/2019/02/18/knightmare-of-initialization/#simple-guidelines-for-variable-i ) | |
175–176 | IIUC, these two lines could be just auto view = in | std::views::reverse; except that in has 5 elements when it probably was intended to have only 3? The last 2 of in's elements aren't being used in this test. | |
255–285 | These two tests seem backwards to me. The important thing about "works with const iterators" is that it needs to work when the destination range has const iterators. Making the elements of the source range const — that also ought to work, sure, but it's significantly less interesting than making the elements of the destination range const. |
libcxx/include/__memory/uninitialized_algorithms.h | ||
---|---|---|
45–46 | __memory/ranges_uninitialized_algorithms.h was introduced by my first patch in this series. It deliberately delegates most of the work to the internal functions contained in __memory/uninitialized_algorithms.h. I have considered maintaining separate implementations before starting on this path. The amount of code duplication would be significant, with all the associated drawbacks. Already in uninitialized_algorithms.h before these changes there was a lot of inconsistency between very similar functions, this would only grow worse with twice the duplication and code being split among two different files.
Done. | |
libcxx/include/memory | ||
185 | Done (throughout the file). Another question on this topic -- I've seen a few instances where lines in the synopsis run longer than even 120 characters. Is this intentional or just an oversight? | |
libcxx/include/module.modulemap | ||
223 |
There are a plenty of very similar closely-related types: in_fun_result in_in_result in_out_result in_in_out_result in_out_out_result min_max_result in_found_result Given how small and similar they are, it seemed to me like consolidating them in a single file makes sense. Do you feel these should be separated? | |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.copy/ranges_uninitialized_copy.pass.cpp | ||
34–37 | I would prefer having a single test file devoted to this as well. Added a TODO throughout. | |
61 | Thank you for the link. While I can see the benefit described there, this form also makes me wonder whether forward_iterator is a type or a function, and if it's the latter, then what kind of a return type it might have. This makes me hesitant to make this change. | |
175–176 |
I wanted to have a test case where only a part of the output buffer is used (here and in similar recently-committed tests). If you feel it doesn't add value, I can reduce the size of the buffer to 3. | |
255–285 | Thanks for spotting this! |
Left some comments -- I don't need to see this again if you agree with my suggestions. I don't want to block you since I'll be out for the holidays soon.
libcxx/include/__algorithm/algorithms_results.h | ||
---|---|---|
34 ↗ | (On Diff #395559) | _LIBCPP_HIDE_FROM_ABI |
libcxx/include/__memory/ranges_uninitialized_algorithms.h | ||
401–402 | Suggestion, we often have the return type above the rest of the function. I'm not a big fan of that convention, but here it might help. | |
libcxx/include/__memory/uninitialized_algorithms.h | ||
45–46 | Note from our discussion: you noticed you are missing a test case in the ranges version when __idx reaches __olast before __ifirst reaches __ilast. | |
283 | I am not utterly concerned by using pair and not doing EBO. I believe these algorithms will be used with stateful iterators where EBO wouldn't help most of the time anyway. | |
libcxx/include/memory | ||
185 | I don't think anyone has ever asked the question. I think we should just copy-paste the formatting of the Standard, as you seem to be doing already. | |
libcxx/test/std/algorithms/algorithms.results/algorithms.results.compile.pass.cpp | ||
9 ↗ | (On Diff #395559) | I suspect this test is going to have to be XFAILed for Clang on Windows, because I don't think the Clang emulation of MSVC supports [[no_unique_address]]. You can see whether that's correct once CI runs. |
23 ↗ | (On Diff #395559) | You seem to be missing a test case for when the members of in_out_result are move constructible vs copy constructible, i.e. the const& vs && variant. Also, there should be runtime tests actually running those conversion operators to make sure they are implemented correctly, even though I know it's an almost trivial class. (This means you'll need to move from .compile.pass.cpp to .pass.cpp) |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.copy/ranges_uninitialized_copy.pass.cpp | ||
216–217 | This comment should clarify what "existing objects" means. Are we talking about the objects in the source range? | |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.move/ranges_uninitialized_move.pass.cpp | ||
87–92 | Suggestion. It helps clarify that the test cases are 100% unrelated, and also allows skipping the numbering. All that for just two spaces of indentation! | |
250–251 | What http://eel.is/c++draft/specialized.algorithms#uninitialized.move-5 says is basically that if one of the move constructor throws, the objects in the source range (that have been moved-from) will now be left in a moved-from state (aka the valid-but-unspecified-state wording used in the spec). Instead, IMO we should be asserting that the moved-from objects (i.e. in[0], in[1], in[2]) are indeed moved-from after the exception has been thrown. | |
349 | Here and elsewhere. | |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.move/ranges_uninitialized_move_n.pass.cpp | ||
100 | I don't think I've seen tests that the various std::ranges:: algorithms are returning exactly the type specified in the standard. If that's right, we should add some. In other words, it's not sufficient to be returning some type that happens to have .in and .out, they need to be exactly what the spec says. |
libcxx/include/__memory/uninitialized_algorithms.h | ||
---|---|---|
283 | EBO is only a concern when ABI is a concern. Here, if you're thinking about ABI, you've already lost. If this return value is ever materialized into memory, your perf is already shot to heck. (This is a general complaint of mine about C++20 Ranges and refactorings-to-use-more-helper-functions: the optimizer can paper over a lot of sins, but the flip side of that is that the library gradually becomes even less usable at -O0.) | |
libcxx/include/module.modulemap | ||
223 |
I feel that there are two things to consider, and right now both of them militate in favor of in_out_result.h: | |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.copy/ranges_uninitialized_copy.pass.cpp | ||
61 |
True. Of course this isn't unique to forward_iterator<int*>; we see that kind of ambiguity with std::ranges::subrange (type) on line 68 versus std::ranges::uninitialized_copy (function) on line 69. Btw, if you're implying "Someone working on this file might not instantly understand that forward_iterator<It> is one of our test iterators from test_iterators.h," well, I would disagree with that implication. :) The test iterators are used in enough places that we should expect people to be at least as familiar with that vocabulary as with the std::ranges vocabulary (and hopefully more so!). I grant that auto it = mary_poppins<int*>(in) would be legitimately mysterious as to what kind of entity mary_poppins is; but auto it = forward_iterator<int*>(in) in this codebase shouldn't have quite that same level of mystery. No action needed here, but if I've reduced your hesitancy, consider un-hesitating. ;) | |
216–217 | I assume it means "any of the existing objects in the destination range (which have not yet been overwritten)." Line 224 says "the fourth object," but N is actually 3 and there's also a 5 involved, so I don't know which direction the off-by-one math is happening. IIUC, that comment could just say Throw when constructing out[3]. Line 226 should be followed by an assert(false) (inside the try, but never hit because we expect to throw an exception). And then circa line 229, we should do what the comment says we're doing: we should check that the value of out[4].value remains 5. Without that check, I don't think this test is doing anything. | |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.copy/ranges_uninitialized_copy_n.pass.cpp | ||
39–40 | clang-format strikes again. I suggest static_assert(!std::is_invocable_v<decltype(std::ranges::uninitialized_copy_n), int*, size_t, NotConvertibleFromInt*, NotConvertibleFromInt*>); or even better, just static_assert(!std::is_invocable_v<decltype(std::ranges::uninitialized_copy_n), int**, size_t, int*, int*>); since IIUC the point of this assertion is to test that it SFINAEs away when the source element type isn't convertible to the dest element type (e.g. int isn't convertible to int*). | |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.move/ranges_uninitialized_move.pass.cpp | ||
72–76 | I'd feel better if this were a non-template hidden friend: friend T&& iter_move(Iterator it) { ++iter_move_invocations; return std::move(*it); } Also, in writing that, I noticed that you were passing it by mutable reference on line 72. That's because https://eel.is/c++draft/specialized.algorithms#uninitialized.move-4 is overspecified, right? Personally I think we shouldn't bother to test that, and should file yet another LWG issue about the overspecification. This is the same overspecification problem as in resize_and_overwrite; and I hadn't noticed it before. Intuition tells me that for the programmer to provide an ADL iter_move that works only with lvalues, might actually be IFNDR for some reason related to https://github.com/cplusplus/nbballot/issues/183 "implicit expression variations." But I certainly don't know for sure. | |
87–92 | +1... and note that in many existing tests, we don't even bother to pay the 2 spaces of indentation. ;) | |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.move/ranges_uninitialized_move_n.pass.cpp | ||
100 | Pro tip: in tests that already require Concepts, this can be as simple as std::same_as<std::ranges::in_out_result> auto result = std::ranges::uninitialized_move_n(in, N, out.begin(), out.end()); although I guess that syntax works better for shorter types/expressions. :) Here it's not saving you much (if anything) over the old-school auto result = std::ranges::uninitialized_move_n(in, N, out.begin(), out.end()); ASSERT_SAME_TYPE(decltype(result), std::ranges::in_out_result); |
- Use a different branch which is correctly based on main. The previous branch's history was unfortunately broken;
- address feedback.
libcxx/include/__memory/uninitialized_algorithms.h | ||
---|---|---|
45–46 | Added. | |
283 |
It's a very valid concern, but I don't see a great way around it without a lot of code duplication (or code generation, which comes with its own set of problems). | |
libcxx/include/module.modulemap | ||
223 | Renamed to in_out_result.h. Regarding whether they're used together -- I don't think they're ever used within the same function, but I'm also pretty sure that including <algorithm> will drag in all of them. That was part of my thinking when I decided to define them in a single file. However, having them in separate files would mean we "import" less stuff internally. | |
libcxx/test/std/algorithms/algorithms.results/algorithms.results.compile.pass.cpp | ||
23 ↗ | (On Diff #395559) | Done. |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.copy/ranges_uninitialized_copy.pass.cpp | ||
61 | The problem with initialization styles is that their main benefits happen when they are used consistently. Personally, I always use the old T foo(x, y) unless there's a reason not to -- this is why when I see auto foo = T(x, y), my thought process goes something like "I _think_ T is a class, but if it were, why wouldn't they just write T foo(x, y)? Am I missing something? Is it actually some T2 class with a very similar name? Or perhaps it comes from some different namespace? Oh, I see, it is in fact T, they just prefer to use auto initialization for some reason". This would be less of an issue if auto foo = ... form was used consistently, but to a certain extent the issue is unavoidable -- it's inherent in the fact that this form of initialization invokes regular functions just as happily as constructors. The fact that current code sometimes uses the same naming convention for functions as for types doesn't help, either. I generally prefer to use the most restricted form that achieves the necessary result, and in this case the T foo(x, y) form seems more restricted (T can only be a type, and thus this can only be a constructor call). It's true that the reader can be expected to know the commonly-used types, but I think it poses new questions. At which point can a type be considered a commonly-used type within a file? It's an additional judgment call for the writer, and I don't think using two different forms of initialization makes things easier for the reader either. The fact that I'm using the auto = form with subrange is actually a mistake on my part -- I did presume subrange was a function. Yes, it is my fault for not checking, but I wouldn't _need_ to check if a different form of initialization was used. | |
216–217 | Thanks for calling it out. Should be in a better shape now, PTAL.
Yes (because it uses copying, the fact that objects in the source range are unchanged seems like a given, but please let me know if you disagree and I can add checks). However, now that I think of it, I'm not sure this is a valid use case -- this algorithm is supposed to be used on uninitialized memory. I'm also not 100% sure that calling placement new on an object without calling its destructor first isn't undefined behavior for trivially-destructible types (though I would think so).
Your rephrasing is much better, thanks. The original comment meant "fourth" if using "natural" counting order (counting from one). | |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.copy/ranges_uninitialized_copy_n.pass.cpp | ||
39–40 | I don't feel too strongly about it, but my current preference is to keep it as-is. The class name, verbose as it is, makes the purpose of the test obvious, whereas the distinction between one asterisk vs. two asterisks requires a closer look. In my experience, manually changing the output of a formatting tool largely defeats the purpose of using one. While I agree that the proposed formatting is better, I wouldn't say that what clang-format produced is broken to justify manual editing. | |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.move/ranges_uninitialized_move.pass.cpp | ||
72–76 | Done. | |
87–92 | Done. I'd prefer to use consistent indentation everywhere. | |
250–251 | Done, thanks! | |
libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.move/ranges_uninitialized_move_n.pass.cpp | ||
100 | Added, will add similar tests to the already-committed algorithms in a follow-up. @Quuxplusone Thanks for providing two versions! I agree that Concepts don't seem to have a huge advantage, so I went with ASSERT_SAME_TYPE. Happy to change, though. |
libcxx/include/__memory/ranges_uninitialized_algorithms.h | ||
---|---|---|
182 | Does this just need to be rebased? I think I remember fixing that fil to fill as a drive-by, too. | |
398 | Please remove all clang-format comments. | |
432–433 | Readability nit. ("Semantic linebreaks") | |
libcxx/include/__memory/uninitialized_algorithms.h | ||
30 | I suspect the _NOEXCEPT is useless and thus should be removed; but I'm not sure. (Which is why I'd rather it hadn't been there at all! Frost's corollary to Chesterton's Fence: it's going to take more work to remove a fence [keyword] than to erect one unnecessarily, so let's make sure we're only erecting the necessary ones.) | |
37–39 | and so on throughout — let's not go out of our way to fit everything in 80 columns, but let's not go out of our way to shove everything onto one line either :) | |
libcxx/test/std/algorithms/algorithms.results/in_out_result.pass.cpp | ||
24–31 | I remember a similar issue in the in_in_result review. Is this consistent with what we landed on there? (I don't think it is...?) |
Address feedback.
libcxx/include/__memory/ranges_uninitialized_algorithms.h | ||
---|---|---|
182 | Done. After some thinking, I still feel that having special rules for special cases adds more complexity than it's worth. Would a new programmer starting on the code base be able to figure out the reason for the inconsistency? Are we realistically going to document the rationale for all the special cases? I feel the answer to both is more likely no than yes. | |
398 | I'd rather leave these in. clang-format doesn't format requires clauses well. I understand you're not a big fan of clang-format, but removing those statements after they're already added seems a little overkill. | |
libcxx/include/__memory/uninitialized_algorithms.h | ||
30 | This class mimics std::unreachable_sentinel_t which does define its operator== as noexcept. I'd rather be consistent with the standard class, for simplicity if nothing else. | |
37–39 | Done, but I'm not very happy with the change. If we say that we're using 120 columns width, we should be using it. | |
libcxx/test/std/algorithms/algorithms.results/in_out_result.pass.cpp | ||
24–31 | Made it consistent and copied a group of tests from that patch. Thanks for bringing this up! |
This patch seems to break the Fuchsia builds.
Failed Tests (1): libc++ :: std/algorithms/algorithms.results/in_out_result.pass.cpp
This is the link to the cmake commands:
https://logs.chromium.org/logs/fuchsia/buildbucket/cr-buildbucket/8825352420796900577/+/u/clang/configure/execution_details
I don't see any details on what is failing in the logs. If I were to guess, I'd presume that the [[no_unique_address]] attribute doesn't work on Fuchsia.
@gulfem The test should be disabled on Fuchsia by commit 9e634b35ff51d0eb2b38013111491e88bdbae388.
I would need a log that indicates the exact failure in the test (I don't see that in the log you provided) or a way to reproduce in order to fix this properly. Can you help me with that?
The libc++::in_out_result.pass.cpp test gets failed to build with the following error:
C:/buildbot/as-builder-1/x-armv7l/build/include/c++/v1\__algorithm/in_out_result.h:36:13: error: non-constant-expression cannot be narrowed from type 'int' to 'double' in initializer list [-Wc++11-narrowing] return {in, out}; ^~ C:\buildbot\as-builder-1\x-armv7l\llvm-project\libcxx\test\std\algorithms\algorithms.results\in_out_result.pass.cpp:49:50: note: in instantiation of function template specialization 'std::ranges::in_out_result<int, bool>::operator in_out_result<double, char>' requested here std::ranges::in_out_result<double, char> y = x; ^ C:/buildbot/as-builder-1/x-armv7l/build/include/c++/v1\__algorithm/in_out_result.h:36:13: note: insert an explicit cast to silence this issue return {in, out}; ^~ static_cast<double>( ) 1 error generated. error: command failed with exit status: 1
I suspect the same problem for Fuchsia also.
I see this error too in our downstream tests:
In file included from /repo/uabelho/master-github/libcxx/test/std/algorithms/algorithms.results/in_out_result.pass.cpp:19: In file included from /repo/uabelho/master-github/llvm/build-all-builtins/include/c++/v1/algorithm:659: In file included from /repo/uabelho/master-github/llvm/build-all-builtins/include/c++/v1/functional:506: In file included from /repo/uabelho/master-github/llvm/build-all-builtins/include/c++/v1/__functional/function.h:24: In file included from /repo/uabelho/master-github/llvm/build-all-builtins/include/c++/v1/memory:793: In file included from /repo/uabelho/master-github/llvm/build-all-builtins/include/c++/v1/__memory/ranges_uninitialized_algorithms.h:13: /repo/uabelho/master-github/llvm/build-all-builtins/include/c++/v1/__algorithm/in_out_result.h:36:13: error: non-constant-expression cannot be narrowed from type 'int' to 'double' in initializer list [-Wc++11-narrowing] return {in, out}; ^~ /repo/uabelho/master-github/libcxx/test/std/algorithms/algorithms.results/in_out_result.pass.cpp:49:50: note: in instantiation of function template specialization 'std::ranges::in_out_result<int, bool>::operator in_out_result<double, char>' requested here std::ranges::in_out_result<double, char> y = x; ^ /repo/uabelho/master-github/llvm/build-all-builtins/include/c++/v1/__algorithm/in_out_result.h:36:13: note: insert an explicit cast to silence this issue return {in, out}; ^~ static_cast<double>( ) 1 error generated. error: command failed with exit status: 1
I'm on RHEL7 compiling with clang 8.
@vvereschaka @uabelho I'll submit a quick fix today after https://reviews.llvm.org/D117089 passes CI.
That test isn't failing on Fuchsia (we don't run libc++ tests on Fuchsia yet), it's failing on Fuchsia toolchain bots which are building and running tests on Linux, but in this particular case it's an arm64 machine.
Thank you @var-const, fe958b140ab37acf316f5b98318e75ba2119d5a2 fixed the issue that we were seeing in the Fuchsia toolchain bots.
I think you can also revert 9e634b35ff51d0eb2b38013111491e88bdbae388 as there is no need for that.
clang-format not found in user’s local PATH; not linting file.