search

ericniebler / stl2

LaTeX and Markdown source for the Ranges TS/STL2 and associated proposals
88 stars 8 forks source link

Unimplementable requirements for advance and distance #107

Closed CaseyCarter closed 8 years ago

CaseyCarter commented 9 years ago

Describing:

template <Iterator I, Sentinel<I> S>
void advance(I& i, S bound);

[iterator.operations]/7 says:

If SizedIteratorRange<I,S>() is satisfied, this function shall dispatch to advance(i, bound - i).

Paragraph 10 similarly requires of:

template <Iterator I, Sentinel<I> S>
DifferenceType<I> advance(I& i, DifferenceType<I> n, S bound);

If SizedIteratorRange<I,S>() is satisfied: ... Otherwise, ...

Paragraph 12 provides a similar requirement for

template <Iterator I, Sentinel<I> S>
DifferenceType<I> distance(I first, S last);

If SizedIteratorRange<I,S>() is satisfied, returns (last - first); otherwise, ...

Since it is not possible for a library implementation to determine if a set of parameters satisfies the non-syntactic requirements of a concept, these requirements are not implementable.

CaseyCarter commented 9 years ago

Possible solutions:

The "introduce additional overloads" solution is going to have scalability issues when we get into the algorithms. Any feature like SizedIteratorRange / SizedRange of which we want to allow algorithm implementors to take advantage will require the introduction of an additional set of permuted declarations. For example, search:

template<ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2,
  class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>()
I1 search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{},
         Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template<ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
  class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyComparable<IteratorType<Rng1>, IteratorType<Rng2>, Pred, Proj1, Proj2>()
safe_iterator_t<Rng1>
search(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
       Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

needs additional declarations:

template<ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2,
  class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>() &&
      SizedIteratorRange<I1, S1>()
I1 search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{},
         Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template<ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2,
  class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>() &&
      SizedIteratorRange<I2, S2>()
I1 search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{},
         Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template<ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2,
  class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity>
    requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>() &&
      SizedIteratorRange<I1, S1>() && SizedIteratorRange<I2, S2>()
I1 search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{},
         Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template<ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
  class Proj1 = identity, class Proj2 = identity>
    requires SizedRange<Rng1>() &&
      IndirectlyComparable<IteratorType<Rng1>, IteratorType<Rng2>, Pred, Proj1, Proj2>()
safe_iterator_t<Rng1>
search(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
       Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template<ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
  class Proj1 = identity, class Proj2 = identity>
    requires SizedRange<Rng2>() &&
      IndirectlyComparable<IteratorType<Rng1>, IteratorType<Rng2>, Pred, Proj1, Proj2>()
safe_iterator_t<Rng1>
search(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
       Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

template<ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>,
  class Proj1 = identity, class Proj2 = identity>
    requires SizedRange<Rng1>() && SizedRange<Rng2>() &&
      IndirectlyComparable<IteratorType<Rng1>, IteratorType<Rng2>, Pred, Proj1, Proj2>()
safe_iterator_t<Rng1>
search(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{},
       Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

and since the Range overloads dispatch to the Iterator overloads, and it's possible for a range that doesn't satisfy SizedRange to have an IteratorType and SentinelType that satisfy SizedIteratorRange, all of those Range overload variants also need additional !SizedRange<R>() && SizedIteratorRange<IteratorType<R>, SentinelType<R>>() variants as well.

When we added SizedRange{R} DistanceType<IteratorType<R>> distance(R&&); to solve this problem for Range{R} DistanceType<IteratorType<R>> distance(R&&); it seemed like a good idea, but I don't think the approach is tenable for the algorithms.

ericniebler commented 9 years ago

I don't think the approach is tenable for the algorithms.

I think the correct approach here is to have some text in the library introduction describing what happens when instantiating a template on a type that does not satisfy the requirements: undefined behavior. We would also need to extend this blanket wording to function templates that are specified to use concepts internally to dispatch to optimal implementations.

CaseyCarter commented 9 years ago

I greatly prefer a single consistent library-wide requirement for SizedRange and SizedIteratorRange. Your suggestion implies that we decide at specification time to partition the library into components that may used SizedRange / SizedIteratorRange in their implementations, and components that may not - restricting implementor freedom. We either specify the partitioning explicitly - increasing specification size and thus cognitive load on readers - or leave it implicit so users must recursively trace requirements through the standard to determine the partitioning.

I think it would save everyone time and trouble if we rename disable_sized_range to disable_sized, and require users who pass Ranges or Sentinels to the library that do not satisfy SizedRange / SizedIteratorRange but do meet the syntactic requirements to specialize disable_sized to false.

ericniebler commented 9 years ago

I think it would save everyone time and trouble if we rename disable_sized_range to disable_sized, and require users who pass Ranges or Sentinels to the library that do not satisfy SizedRange / SizedIteratorRange bit do meet the syntactic requirements to specialize disable_sized to false.

What would the definition of such a disable_sized trait look like?

CaseyCarter commented 9 years ago

The trait itself would be the same except for the name change; when we made it a pure opt-out trait it became agnostic to the type of the parameter. It's now simply a mapping from type to bool that defaults to false (which may as well be a variable template, now that I think about it). What would be different is the definition of SizedIteratorRange to allow opt-out:

template <class I, class S>
concept bool SizedIteratorRange() {
  return Sentinel<S, I>() &&
    !disable_sized<S>::value &&
    requires (const I i, const S j) {
      { i - i } -> DifferenceType<I>;
      { j - j } -> DifferenceType<I>;
      { i - j } -> DifferenceType<I>;
      { j - i } -> DifferenceType<I>;
    };
}

Although it seems a bit hackish that only the sentinel type participates in the determination. I'm convinced that we need a single library-wide requirement, but I'm not certain at this time exactly what that requirement should be. I need to let this gel some more.

ericniebler commented 9 years ago

Obviously, sized-ness is not a property of the sentinel only, but of the iterator/sentinel pair. Pressing a single trait into service for this will require a fairly contrived and confusing interface. It requires more thought.