Page MenuHomePhabricator

[libc++][ranges] Implement `uninitialized_copy{,_n}` and `uninitialized_move{,_n}`.
ClosedPublic

Authored by var-const on Dec 20 2021, 2:21 AM.

Details

Summary

Also implement in_out_result which is a prerequisite.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
var-const marked an inline comment as done.Dec 20 2021, 5:09 PM
var-const added inline comments.
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.

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)

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

If there are more types that need to be rolled into this same header, we can always rename it later if needed.

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

except that in has 5 elements when it probably was intended to have only 3?

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!

var-const updated this revision to Diff 395559.Dec 20 2021, 5:45 PM
var-const marked an inline comment as done.

Rebase on main.

ldionne accepted this revision.Dec 21 2021, 11:35 AM

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.

Quuxplusone added inline comments.Dec 21 2021, 7:02 PM
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

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?

I feel that there are two things to consider, and right now both of them militate in favor of in_out_result.h:
(1) .h files should be named for what's in them. What's in this file right now is in_out_result. Maybe that'll change in a few weeks; if it does, then we can change the file's name to match its new contents.
(2) Minimize dependencies: things should be combined if they're often used together, and split up if they're basically never used together. My ill-informed impression is that these *_result types are (2a) literally never used together, and (2b) in some cases, single-purpose types which really belong in their appropriate algorithm .h file; e.g. min_max_result probably belongs in __algorithm/ranges_min_max.h (and nowhere else).

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.copy/ranges_uninitialized_copy.pass.cpp
61

While I can see the benefit described there, this form also makes me wonder whether forward_iterator is a type or a function

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.
Anyway, I think in this case it reads better with = instead of (); but I definitely can't claim that we use = 100% consistently.

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);
var-const updated this revision to Diff 396999.Sun, Jan 2, 10:31 PM
var-const marked 19 inline comments as done.
  • 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

but the flip side of that is that the library gradually becomes even less usable at -O0.

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.

I assume it means "any of the existing objects in the destination range (which have not yet been overwritten)."

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).

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].

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.

var-const updated this revision to Diff 397213.Tue, Jan 4, 12:22 AM

Run libcxx-generate-files.

var-const updated this revision to Diff 397328.Tue, Jan 4, 9:48 AM

Rebase on main.

var-const updated this revision to Diff 397450.Tue, Jan 4, 8:05 PM

Fix CI on Windows.

Quuxplusone added inline comments.Mon, Jan 10, 11:22 AM
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.
Ditto throughout: I believe we agreed (at least for now) not to indent the big namespace but to leave the one-liner indented. Anyway, please look at the existing code (as it is now in main, not how it was last month ;)) and let's be consistent with whatever it looks like.

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...?)

var-const updated this revision to Diff 398833.Mon, Jan 10, 9:17 PM
var-const marked 3 inline comments as done.

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 revision was not accepted when it landed; it landed in state Needs Review.Mon, Jan 10, 10:50 PM
This revision was automatically updated to reflect the committed changes.
gulfem added a subscriber: gulfem.Tue, Jan 11, 10:37 AM

This patch seems to break the Fuchsia builds.

Failed Tests (1):
  libc++ :: std/algorithms/algorithms.results/in_out_result.pass.cpp

https://logs.chromium.org/logs/fuchsia/buildbucket/cr-buildbucket/8825352420796900577/+/u/clang/test/stdout

This is the link to the cmake commands:
https://logs.chromium.org/logs/fuchsia/buildbucket/cr-buildbucket/8825352420796900577/+/u/clang/configure/execution_details

Would you mind reverting it unless the issue can be fixed quickly?

This patch seems to break the Fuchsia builds.

Failed Tests (1):
  libc++ :: std/algorithms/algorithms.results/in_out_result.pass.cpp

https://logs.chromium.org/logs/fuchsia/buildbucket/cr-buildbucket/8825352420796900577/+/u/clang/test/stdout

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.

Would you mind reverting it unless the issue can be fixed quickly?

I'll see if I can mark the test as XFAIL on Fuchsia. If not, I'll change the test.

@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?

@var-const, @gulfem

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.

@var-const, @gulfem

The libc++::in_out_result.pass.cpp test gets failed to build with the following error:

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 Thanks for the error messages! I'll prepare a fix ASAP.

@vvereschaka @uabelho I'll submit a quick fix today after https://reviews.llvm.org/D117089 passes CI.

phosek added a subscriber: phosek.Tue, Jan 11, 10:51 PM

@vvereschaka, @uabelho Thanks for the error messages! I'll prepare a fix ASAP.

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.

Hopefully fixed by commit fe958b140ab37acf316f5b98318e75ba2119d5a2.

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.