This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement ranges::mismatch
ClosedPublic

Authored by philnik on Jan 20 2022, 11:08 AM.

Details

Summary

Implement ranges::mismatch

Diff Detail

Event Timeline

philnik created this revision.Jan 20 2022, 11:08 AM
philnik requested review of this revision.Jan 20 2022, 11:08 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 20 2022, 11:08 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript

Drive-by comment: can you also update Status/RangesPaper.csv and Status/RangesAlgorithms.csv?

libcxx/include/module.modulemap
291

Drive-by comment: s/rnages/ranges/

philnik updated this revision to Diff 401791.Jan 20 2022, 2:56 PM
philnik marked an inline comment as done.
  • Address comments and fix CI
Quuxplusone requested changes to this revision.Jan 22 2022, 6:25 PM

Thanks for working on this!

libcxx/include/__algorithm/ranges_mismatch.h
39–46
48

_VSTD::invoke throughout; and please add a regression test involving Holder<Incomplete>*.
https://quuxplusone.github.io/blog/2019/09/26/uglification-doesnt-stop-adl/

59–60
65–67

Here, either std::move(__foo) or, better, rejigger this so that we can use references (or our __comp_ref trick) with all of these callables. The Standard permits us to copy these callables as much as we like (AFAIK); but as a quality-of-implementation thing, we want to make zero copies and ideally (IMHO) zero moves as well.

I think it's easy to make this work; you just have to pull out the algorithm itself into a helper

template<class _I1, class _S1, class _I2, class _S2,
         class _Pred, class _Proj1, class _Proj2>
static _LIBCPP_HIDE_FROM_ABI constexpr
mismatch_result<_I1, _I2>
__go(_I1 __first1, _S1 __last1, _I2 __first2, _S2 __last2,
     _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) const {
  while (~~~
  return {__first1, __first2};
}

and then call __go from both overloads of operator(), e.g.:

~~~
mismatch_result<_I1, _I2>
operator()(_I1 __first1, _S1 __last1, _I2 __first2, _S2 __last2,
           _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
  return __go(_VSTD::move(__first1), __last1, _VSTD::move(__first2), __last2,
               __pred, __proj1, __proj2);
}
libcxx/test/std/algorithms/alg.nonmodifying/mismatch/ranges_mismatch.pass.cpp
2

Please uncomment the relevant line in std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp.
Consider adding explicit test coverage here for C arrays, e.g.

int a[] = {1, 2, 3, 4};
int b[] = {1, 2, 4, 8, 16};
auto [ai, bi] = std::ranges::mismatch(a, b);
assert(ai == a + 2);
assert(bi == b + 2);
auto [aj, bj] = std::ranges::mismatch(a, a+4, b, b+5);
assert(aj == a + 2);
assert(bj == b + 2);

This is on my mind tonight because of D117940; but I don't think there's anything specific to mismatch that would bite us here, and niebloid.compile.pass.cpp already (by a happy accident) tests the C-array case.

17–31

I think this layer of indirection is more confusing than helpful. Strongly recommend inlining these assertions directly into test_iters, test_different_lengths, and test_borrowed_range — I think that will probably even shorten the code!

76

mismatch's constraint says input_iterator, so you need to test with both cpp17_input_iterator and (especially) cpp20_input_iterator, as well as all these.
Please also throw in contiguous_iterator<int*>, since there's no good reason to leave it out.

This revision now requires changes to proceed.Jan 22 2022, 6:25 PM
philnik updated this revision to Diff 402315.Jan 23 2022, 5:34 AM
philnik marked 5 inline comments as done.Jan 23 2022, 5:34 AM
  • Rebased
  • Address comments
libcxx/include/__algorithm/ranges_mismatch.h
48

Using Holder<Incomplete>* currently errors in input_range, so I won't put a regression test in since fixing input_range is out of scope for this PR.

libcxx/test/std/algorithms/alg.nonmodifying/mismatch/ranges_mismatch.pass.cpp
17–31

Veto on doing this for test_ranges. For that I would either have to inline the return type check as well or explicitly name the template parameters. Both of which make the code definitely less readable.

Just test nits at this point (probably all related to inlining test_ranges :))

libcxx/include/__algorithm/ranges_mismatch.h
37

Here and line 39, consider linebreaking after _S2,. These lines are just barely too long for Phabricator, so this is a pretty minor nit; but it's also super easy to fix.

39–46

Just a note to say this implementation LGTM now, and awesome, I see that testing with cpp20_input_iterator caught a bug :)

48

Yikes, I see this now: https://godbolt.org/z/WPzrhda1f Is that the problem you mean? If so, OK, no-regression-test is fine.

libcxx/test/std/algorithms/alg.nonmodifying/mismatch/ranges_mismatch.pass.cpp
24–28

And change the signature on line 19 to take int *expected1, int *expected2.

89

You can replace this call to test_ranges with simply

using Expected = std::ranges::mismatch_result<Iter, Iter>;
std::same_as<Expected> auto ret = std::ranges::mismatch(b1, b2);
assert(base(ret.in1) == r1 + 3);
assert(base(ret.in2) == r2 + 3);

(leaving off the base() if you want, since here Iter is hardcoded to int* already).
However, this doesn't seem to match the name of the test case... it's supposed to be testing a borrowed range, right? The thing that's special about borrowed ranges is that they work as rvalues. So what you should be testing here is rvalues. I continue to recommend views::all(r1) because it's easy to type.

constexpr void test_borrowed_range() {
  int r1[] = {1, 2, 3, 4, 5, 6};
  int r2[] = {1, 2, 3, 5, 4};
  {
    // non-borrowed lvalue vs. borrowed rvalue
    std::same_as<std::ranges::mismatch_result<int*, int*>> auto ret =
      std::ranges::mismatch(r1, std::views::all(r2));
    assert(ret.in1 == r1 + 3);
    assert(ret.in2 == r2 + 3);
  }
  {
    // borrowed rvalue vs. non-borrowed lvalue
    std::same_as<std::ranges::mismatch_result<int*, int*>> auto ret =
      std::ranges::mismatch(std::views::all(r1), r2);
    assert(ret.in1 == r1 + 3);
    assert(ret.in2 == r2 + 3);
  }
  {
    // borrowed rvalue vs. borrowed rvalue
    std::same_as<std::ranges::mismatch_result<int*, int*>> auto ret =
      std::ranges::mismatch(std::views::all(r1), std::views::all(r2));
    assert(ret.in1 == r1 + 3);
    assert(ret.in2 == r2 + 3);
  }
}

(the // comments are optional)

I'm hoping that seeing this example changes your mind about the utility of inlining test_ranges everywhere else. I haven't dug into those call-sites yet myself, and am hoping you will.

philnik updated this revision to Diff 402807.Jan 25 2022, 2:15 AM
philnik marked 7 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_mismatch.h
48

Yes.

libcxx/test/std/algorithms/alg.nonmodifying/mismatch/ranges_mismatch.pass.cpp
89

std::views::all seems to not be a borrowed_range. At least it's not a borrowed range in libc++ and I couldn't find anything in the standard.

libcxx/include/__algorithm/ranges_mismatch.h
48

This is now D118213, so hopefully by end-of-week you can add that regression test after all. :)

Holder<Incomplete> *a[3] = {};
Holder<Incomplete> *b[4] = {};
auto [ai, bi] = std::ranges::mismatch(a, b);
assert(ai == a+3);
assert(bi == b+3);
philnik updated this revision to Diff 403378.Jan 26 2022, 12:48 PM
  • Rebased
  • IWYU
libcxx/include/__algorithm/ranges_mismatch.h
48

D118213 is landed! So you should be able to add the above test now.

libcxx/test/std/algorithms/alg.nonmodifying/mismatch/ranges_mismatch.pass.cpp
89

D118164 fixed the borrowed-ness of views::all(r), so you can do this now too.

philnik updated this revision to Diff 405463.Feb 2 2022, 2:52 PM
philnik marked an inline comment as done.
  • Updates
libcxx/include/__algorithm/ranges_mismatch.h
48

Now it fails in iterator_traits.h:150. I don't really understand why and I also don't feel like fixing all the concepts before landing this.

LGTM % nits.

libcxx/include/__algorithm/ranges_mismatch.h
31

This will need merge-conflict resolution. I suggest just this for now:

#if !defined(_LIBCPP_HAS_NO_CONCEPTS)

although if we wait long enough, D118736 might change it again.

48

Discussed offline, and discovered that Ranges algorithms are fundamentally not ADL-proof, so we actively cannot add the test I was asking for.

https://godbolt.org/z/P9fhhYWvW

I actually now have a suggested fix to ADL-firewall std::projected, but it will require a paper.

libcxx/test/std/algorithms/alg.nonmodifying/mismatch/ranges_mismatch.pass.cpp
66

a.begin() + 3 is a funny way to spell a.end().
How about changing a and b to C arrays, and then you can just say test_iterators(a, a + 3, b, b + 2, a + 2, b + 2)?

Please also test when the first range is shorter, i.e. add test_iterators(b, b + 2, a, a + 3, b + 2, a + 2).

168

I claim that we traditionally put a blank line before the return 0;.

philnik updated this revision to Diff 406093.Feb 4 2022, 1:14 PM
philnik marked 6 inline comments as done.
  • Address comments
ldionne requested changes to this revision.Feb 10 2022, 8:10 AM
ldionne added inline comments.
libcxx/test/std/algorithms/alg.nonmodifying/mismatch/ranges_mismatch.pass.cpp
13

Please document what you're testing by adding the synopsis here. That's what we do everywhere else.

22

You could easily inline that function into the only place where it's called (unless I missed a second usage?).

38

Please inline those test_foo() functions into the body below, and separate them with scopes like we've started doing:

// meaningful comment
{
  <...>
}

Using a comment allows for something more descriptive than just test_sentinel.

This revision now requires changes to proceed.Feb 10 2022, 8:10 AM
philnik updated this revision to Diff 407572.Feb 10 2022, 9:25 AM
philnik marked 3 inline comments as done.
  • Rebased
  • Address comments
libcxx/test/std/algorithms/alg.nonmodifying/mismatch/ranges_mismatch.pass.cpp
22

It's also used in test_different_lengths().

philnik updated this revision to Diff 412819.Mar 3 2022, 1:17 PM
  • Rebased
  • Fix spelling

ping @ldionne

Herald added a project: Restricted Project. · View Herald TranscriptMar 3 2022, 1:17 PM
ldionne requested changes to this revision.Mar 7 2022, 10:00 AM
ldionne added inline comments.
libcxx/include/__algorithm/ranges_mismatch.h
61

Any reason why we don't implement the algorithm here and then call *this in the range version immediately below?

libcxx/include/algorithm
47–58

This is strangely formatted. Also, we need to say // since C++20.

libcxx/test/std/algorithms/alg.nonmodifying/mismatch/ranges_mismatch.pass.cpp
106

We should add test with non-default projections and predicate for the range overload.

Edit: And for the iterator overload too, since it appears we don't have such tests.

This revision now requires changes to proceed.Mar 7 2022, 10:00 AM
philnik updated this revision to Diff 413767.Mar 8 2022, 4:49 AM
philnik marked 3 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_mismatch.h
61

With the current implementation the predicates and projections are never moved. using *this() would mean we have to move them at least once.

ldionne accepted this revision.Mar 8 2022, 1:53 PM

LGTM with my comments addressed. Thanks!

libcxx/include/__algorithm/ranges_mismatch.h
61

Oh, I see. Clever. Can you please add a libc++ specific test for that? I know it's nitpicky, but that seems like a useful guarantee to test if we're providing it. I suggest finding a simple way to test this because I'll be requesting the same kind of test for other algorithms as well (e.g. find_if).

libcxx/test/std/algorithms/alg.nonmodifying/mismatch/ranges_mismatch.pass.cpp
129
This revision is now accepted and ready to land.Mar 8 2022, 1:53 PM

By the way, I know CI is flaky right now with failures around installing cxxabi_config.h -- I'm getting there but there's a couple pre-requisites to fix this. For now, please ignore.

Quuxplusone added inline comments.Mar 8 2022, 2:06 PM
libcxx/include/__algorithm/ranges_mismatch.h
61

I'd be happy to tackle this in a different PR; it'd basically be a Ranges version of libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp.

This revision was landed with ongoing or failed builds.Mar 8 2022, 2:21 PM
This revision was automatically updated to reflect the committed changes.
philnik marked an inline comment as done.
var-const added inline comments.Mar 8 2022, 4:15 PM
libcxx/docs/Status/RangesAlgorithms.csv
10

Ultranit: can you use the checkmark emoji instead? It would be consistent with other completed entries (and I think stands out better visually).

libcxx/include/__algorithm/ranges_mismatch.h
31

Since D118736 has landed, does this need to change again?

82

This comment looks like it doesn't match the #if condition.

libcxx/include/algorithm
51

Do you need to also add mismatch_result to the synopsis?

libcxx/test/std/algorithms/alg.nonmodifying/mismatch/ranges_mismatch.pass.cpp
36

Ultranit: include <utility>?

43

Nit: it's not obvious from names alone how test_iters is different from test_iterators. Feel free to ignore because the scope is small enough. (For a concrete suggestion, I'd use test_iters and test_iters_impl, though it's certainly not perfect)

108

Very optional: you could use CTAD here to avoid providing an element count.

124

Question: is wrapping in Iter necessary? It seems like array-to-pointer decay would work.

129

Nit: s/sized/size/?

172

Optional: this seems like a test of std::ranges::in_in_result?

290

I think this patch also needs to test the constraints to make sure that parameters that don't satisfy input_iterator, indirectly_comparable, etc. SFINAE away properly.

@philnik Sorry, looks like I'm a little late with my review. Can you please address some of the comments in a follow-up? You can definitely ignore the nits and optionals -- I'm mostly concerned about the potentially missing tests for SFINAE and missing mismatch_result from the synopsis. Thanks!

One more suggestion -- how about testing with empty range(s)?