Title
Incorrect usages of "models" versus "satisfies"
Status
new
Section
[concept.swappable][iterator.cust.swap][range.iter.op.advance] [range.iter.op.distance][reverse.iterator][move.iterator] [move.iter.nav][common.iter.types][common.iter.nav] [range.access][range.iota.iterator][range.adaptors] [algorithms]
Submitter
Daniel Krügler

Created on 2019-11-23.00:00:00 last changed 2 months ago

Messages

Date: 2020-02-15.00:00:00

[ 2020-02-10, Prague; Daniel comments ]

I expect that P2101R0 (See D2101R0) is going to resolve this issue.

This proposal should also resolve the corresponding NB comments US-298 and US-300.

Date: 2019-12-15.00:00:00

[ 2019-12-15; Daniel synchronizes wording with N4842 ]

Previous resolution [SUPERSEDED]:

This wording is relative to N4842.

[Drafting note: The proposed wording does intentionally not touch the definition of enable_view, whose definition is radically changed by LWG 3326 in a manner that does no longer need similar adjustments.]

  1. Modify [concept.swappable] as indicated:

    -2- The name ranges::swap denotes a customization point object ([customization.point.object]). The expression ranges::swap(E1, E2) for some subexpressions E1 and E2 is expression-equivalent to an expression S determined as follows:

    1. (2.1) — […]

    2. (2.2) — […]

    3. (2.3) — Otherwise, if E1 and E2 are lvalues of the same type T that modelssatisfies move_constructible<T> and assignable_from<T&, T>, S is an expression that exchanges the denoted values. S is a constant expression if […]

    4. (2.4) — […]

  2. Modify [iterator.cust.swap] as indicated:

    -4- The expression ranges::iter_swap(E1, E2) for some subexpressions E1 and E2 is expression-equivalent to:

    1. (4.1) — […]

    2. (4.2) — Otherwise, if the types of E1 and E2 each modelsatisfy indirectly_readable, and if the reference types of E1 and E2 modelsatisfy swappable_with ([concept.swappable]), then ranges::swap(*E1, *E2).

    3. (4.3) — Otherwise, if the types T1 and T2 of E1 and E2 modelsatisfy indirectly_movable_storable<T1, T2> and indirectly_movable_storable<T2, T1>, then (void)(*E1 = iter-exchange-move(E2, E1)), except that E1 is evaluated only once.

    4. (4.4) — […]

  3. Modify [range.iter.ops] as indicated:

    -1- The library includes the function templates ranges::advance, ranges::distance, ranges::next, and ranges::prev to manipulate iterators. These operations adapt to the set of operators provided by each iterator category to provide the most efficient implementation possible for a concrete iterator type. [Example: ranges::advance uses the + operator to move a random_access_iterator forward n steps in constant time. For an iterator type that does not modelsatisfy random_access_iterator, ranges::advance instead performs n individual increments with the ++ operator. — end example]

  4. Modify [range.iter.op.advance] as indicated:

    template<input_or_output_iterator I>
      constexpr void ranges::advance(I& i, iter_difference_t<I> n);
    

    -1- Preconditions: […]

    -2- Effects:

    1. (2.1) — If I modelssatisfies random_access_iterator, equivalent to i += n.

    2. (2.2) — […]

    3. (2.3) — […]

    template<input_or_output_iterator I, sentinel_for<I> S>
      constexpr void ranges::advance(I& i, S bound);
    

    -3- Preconditions: […]

    -4- Effects:

    1. (4.1) — If I and S modelsatisfy assignable_from<I&, S>, equivalent to i = std::move(bound).

    2. (4.2) — Otherwise, if S and I modelsatisfy sized_sentinel_for<S, I>, equivalent to ranges::advance(i, bound - i).

    3. (4.3) — […]

    template<input_or_output_iterator I, sentinel_for<I> S>
      constexpr iter_difference_t<I> ranges::advance(I& i, iter_difference_t<I> n, S bound);
    

    -5- Preconditions: […]

    -6- Effects:

    1. (6.1) — If S and I modelsatisfy sized_sentinel_for<S, I>: […]

    2. (6.2) — […]

  5. Modify [range.iter.op.distance] as indicated:

    template<input_or_output_iterator I, sentinel_for<I> S>
      constexpr iter_difference_t<I> ranges::distance(I first, S last);
    

    -1- Preconditions: […]

    -2- Effects: If S and I modelsatisfy sized_sentinel_for<S, I>, returns (last - first); otherwise, returns the number of increments needed to get from first to last.

    template<range R>
      range_difference_t<R> ranges::distance(R&& r);
    

    -3- Effects: If R modelssatisfies sized_range, equivalent to:

    return static_cast<range_difference_t<R>>(ranges::size(r)); // [range.prim.size]
    

    Otherwise, equivalent to:

    return ranges::distance(ranges::begin(r), ranges::end(r)); // [range.access]
    
  6. Modify [reverse.iterator] as indicated:

    -1- The member typedef-name iterator_concept denotes

    1. (1.1) — random_access_iterator_tag if Iterator modelssatisfies random_access_iterator, and

    2. (1.2) — bidirectional_iterator_tag otherwise.

    -2- The member typedef-name iterator_category denotes

    1. (2.1) — random_access_iterator_tag if the type iterator_traits<Iterator>::iterator_category modelssatisfies derived_from<random_access_iterator_tag>, and

    2. (2.2) — iterator_traits<Iterator>::iterator_category otherwise.

  7. Modify [move.iterator] as indicated:

    -1- The member typedef-name iterator_category denotes

    1. (1.1) — random_access_iterator_tag if the type iterator_traits<Iterator>::iterator_category modelssatisfies derived_from<random_access_iterator_tag>, and

    2. (1.2) — iterator_traits<Iterator>::iterator_category otherwise.

  8. Modify [move.iter.nav] as indicated:

    constexpr auto operator++(int);
    

    -3- Effects: Iterator modelssatisfies forward_iterator, equivalent to:

    move_iterator tmp = *this;
    ++current;
    return tmp;
    

    Otherwise, equivalent to ++current.

  9. Modify [common.iter.types] as indicated:

    -1- The nested typedef-names of the specialization of iterator_traits for common_iterator<I, S> are defined as follows.

    1. (1.1) — iterator_concept denotes forward_iterator_tag if I modelssatisfies forward_iterator; otherwise it denotes input_iterator_tag.

    2. (1.2) — iterator_category denotes forward_iterator_tag if iterator_traits<I>::iterator_category modelssatisfies derived_from<forward_iterator_tag>; otherwise it denotes input_iterator_tag.

    3. (1.3) — […]

  10. Modify [common.iter.nav] as indicated:

    decltype(auto) operator++(int);
    

    -4- Preconditions: […]

    -5- Effects: If I modelssatisfies forward_iterator, equivalent to:

    common_iterator tmp = *this;
    ++*this;
    return tmp;
    

    Otherwise, equivalent to return get<I>(v_)++;

  11. Modify [range.access.begin] as indicated:

    -1- The name ranges::begin denotes a customization point object ([customization.point.object]). Given a subexpression E and an lvalue t that denotes the same object as E, if E is an rvalue and enable_safe_range<remove_cvref_t<decltype((E))>> is false, ranges::begin(E) is ill-formed. Otherwise, ranges::begin(E) is expression-equivalent to:

    1. (1.1) — […]

    2. (1.2) — Otherwise, decay-copy(t.begin()) if it is a valid expression and its type I modelssatisfies input_or_output_iterator.

    3. (1.3) — Otherwise, decay-copy(begin(t)) if it is a valid expression and its type I modelssatisfies input_or_output_iterator with overload resolution performed in a context that includes the declarations:

      template<class T> void begin(T&&) = delete;
      template<class T> void begin(initializer_list<T>&&) = delete;
      

      and does not include a declaration of ranges::begin.

    4. (1.4) — […]

  12. Modify [range.access.end] as indicated:

    -1- The name ranges::end denotes a customization point object ([customization.point.object]). Given a subexpression E and an lvalue t that denotes the same object as E, if E is an rvalue and enable_safe_range<remove_cvref_t<decltype((E))>> is false, ranges::end(E) is ill-formed. Otherwise, ranges::end(E) is expression-equivalent to:

    1. (1.1) — […]

    2. (1.2) — Otherwise, decay-copy(t.end()) if it is a valid expression and its type S modelssatisfies sentinel_for<decltype(ranges::begin(E))>.

    3. (1.3) — Otherwise, decay-copy(end(t)) if it is a valid expression and its type S modelssatisfies sentinel_for<decltype(ranges::begin(E))> with overload resolution performed in a context that includes the declarations:

      template<class T> void end(T&&) = delete;
      template<class T> void end(initializer_list<T>&&) = delete;
      
      and does not include a declaration of ranges::end.

    4. (1.4) — […]

  13. Modify [range.access.rbegin] as indicated:

    -1- The name ranges::rbegin denotes a customization point object ([customization.point.object]). Given a subexpression E and an lvalue t that denotes the same object as E, if E is an rvalue and enable_safe_range<remove_cvref_t<decltype((E))>> is false, ranges::rbegin(E) is ill-formed. Otherwise, ranges::rbegin(E) is expression-equivalent to:

    1. (1.1) — decay-copy(t.rbegin()) if it is a valid expression and its type I modelssatisfies input_or_output_iterator.

    2. (1.2) — Otherwise, decay-copy(rbegin(t)) if it is a valid expression and its type I modelssatisfies input_or_output_iterator with overload resolution performed in a context that includes the declaration:

      template<class T> void rbegin(T&&) = delete;
      
      and does not include a declaration of ranges::rbegin.

    3. (1.3) — Otherwise, make_reverse_iterator(ranges::end(t)) if both ranges::begin(t) and ranges::end(t) are valid expressions of the same type I which modelssatisfies bidirectional_iterator ([iterator.concept.bidir]).

    4. (1.4) — […]

  14. Modify [range.access.rend] as indicated:

    -1- The name ranges::rend denotes a customization point object ([customization.point.object]). Given a subexpression E and an lvalue t that denotes the same object as E, if E is an rvalue and enable_safe_range<remove_cvref_t<decltype((E))>> is false, ranges::rend(E) is ill-formed. Otherwise, ranges::rend(E) is expression-equivalent to:

    1. (1.1) — decay-copy(t.rend()) if it is a valid expression and its type S modelssatisfies sentinel_for<decltype(ranges::rbegin(E))>.

    2. (1.2) — Otherwise, decay-copy(rend(t)) if it is a valid expression and its type S modelssatisfies sentinel_for<decltype(ranges::rbegin(E))> with overload resolution performed in a context that includes the declaration:

      template<class T> void rend(T&&) = delete;
      
      and does not include a declaration of ranges::rend.

    3. (1.3) — Otherwise, make_reverse_iterator(ranges::begin(t)) if both ranges::begin(t) and ranges::end(t) are valid expressions of the same type I which modelssatisfies bidirectional_iterator ([iterator.concept.bidir]).

    4. (1.4) — […]

  15. Modify [range.prim.size] as indicated:

    [Drafting note: The term "is integer-like" is very specifically defined to be related to semantic requirements as well, and the term "satisfy integer-like" seems to be undefined. Fortunately, [iterator.concept.winc] also introduces the exposition-only variable template is-integer-like which we use as predicate below to describe the syntactic constraints of "integer-like" alone. This wording change regarding "is integer-like" is strictly speaking not required because of the "if and only if" definition provided in [iterator.concept.winc] p12, but it has been made nonetheless to improve the consistency between discriminating compile-time tests from potentially semantic requirements]

    -1- The name size denotes a customization point object ([customization.point.object]). The expression ranges::size(E) for some subexpression E with type T is expression-equivalent to:

    1. (1.1) — […]

    2. (1.2) — Otherwise, if disable_sized_range<remove_cv_t<T>> ([range.sized]) is false:

      1. (1.2.1) — decay-copy(E.size()) if it is a valid expression and its type I is integer-likeis-integer-like<I> is true ([iterator.concept.winc]).

      2. (1.2.2) — Otherwise, decay-copy(size(E)) if it is a valid expression and its type I is integer-likeis-integer-like<I> is true with overload resolution performed in a context that includes the declaration:

        template<class T> void size(T&&) = delete;
        
        and does not include a declaration of ranges::size.

    3. (1.3) — Otherwise, make-unsigned-like(ranges::end(E) - ranges::begin(E)) ([range.subrange]) if it is a valid expression and the types I and S of ranges::begin(E) and ranges::end(E) (respectively) modelsatisfy both sized_sentinel_for<S, I> ([iterator.concept.sizedsentinel]) and forward_iterator<I>. However, E is evaluated only once.

    4. (1.4) — […]

  16. Modify [range.prim.empty] as indicated:

    -1- The name empty denotes a customization point object ([customization.point.object]). The expression ranges::empty(E) for some subexpression E is expression-equivalent to:

    1. (1.1) — […]

    2. (1.2) — […]

    3. (1.3) — Otherwise, EQ, where EQ is bool(ranges::begin(E) == ranges::end(E)) except that E is only evaluated once, if EQ is a valid expression and the type of ranges::begin(E) modelssatisfies forward_iterator.

    4. (1.4) — […]

  17. Modify [range.prim.data] as indicated:

    -1- The name data denotes a customization point object ([customization.point.object]). The expression ranges::data(E) for some subexpression E is expression-equivalent to:

    1. (1.1) — […]

    2. (1.2) — Otherwise, if ranges::begin(E) is a valid expression whose type modelssatisfies contiguous_iterator, to_address(ranges::begin(E)).

    3. (1.3) — […]

  18. Modify [range.dangling] as indicated:

    -1- The tag type dangling is used together with the template aliases safe_iterator_t and safe_subrange_t to indicate that an algorithm that typically returns an iterator into or subrange of a range argument does not return an iterator or subrange which could potentially reference a range whose lifetime has ended for a particular rvalue range argument which does not modelsatisfy forwarding-range ([range.range]).

    […]

    -2- [Example:

    vector<int> f();
    auto result1 = ranges::find(f(), 42); // #1
    static_assert(same_as<decltype(result1), ranges::dangling>);
    auto vec = f();
    auto result2 = ranges::find(vec, 42); // #2
    static_assert(same_as<decltype(result2), vector<int>::iterator>);
    auto result3 = ranges::find(subrange{vec}, 42); // #3
    static_assert(same_as<decltype(result3), vector<int>::iterator>);
    

    The call to ranges::find at #1 returns ranges::dangling since f() is an rvalue vector; the vector could potentially be destroyed before a returned iterator is dereferenced. However, the calls at #2 and #3 both return iterators since the lvalue vec and specializations of subrange modelsatisfy forwarding-range. — end example]

  19. Modify [range.iota.iterator] as indicated:

    -1- iterator::iterator_category is defined as follows:

    1. (1.1) — If W modelssatisfies advanceable, then iterator_category is random_access_iterator_tag.

    2. (1.2) — Otherwise, if W modelssatisfies decrementable, then iterator_category is bidirectional_iterator_tag.

    3. (1.3) — Otherwise, if W modelssatisfies incrementable, then iterator_category is forward_iterator_tag.

    4. (1.4) — Otherwise, iterator_category is input_iterator_tag.

  20. Modify [range.semi.wrap] as indicated:

    -1- Many types in this subclause are specified in terms of an exposition-only class template semiregular-box. semiregular-box<T> behaves exactly like optional<T> with the following differences:

    1. (1.1) — […]

    2. (1.2) — If T modelssatisfies default_constructible, the default constructor of semiregular-box<T> is equivalent to: […]

    3. (1.3) — If assignable_from<T&, const T&> is not modeledsatisfied, the copy assignment operator is equivalent to: […]

    4. (1.4) — If assignable_from<T&, T> is not modeledsatisfied, the move assignment operator is equivalent to: […]

  21. Modify [range.all] as indicated:

    -2- The name views::all denotes a range adaptor object ([range.adaptor.object]). For some subexpression E, the expression views::all(E) is expression-equivalent to:

    1. (2.1) — decay-copy(E) if the decayed type of E modelssatisfies view.

    2. (2.2) — […]

    3. (2.3) — […]

  22. Modify [range.filter.iterator] as indicated:

    -2- iterator::iterator_concept is defined as follows:

    1. (2.1) — If V modelssatisfies bidirectional_range, then iterator_concept denotes bidirectional_iterator_tag.

    2. (2.2) — Otherwise, if V modelssatisfies forward_range, then iterator_concept denotes forward_iterator_tag.

    3. (2.3) — […]

    -3- iterator::iterator_category is defined as follows:

    1. (3.1) — Let C denote the type iterator_traits<iterator_t<V>>::iterator_category.

    2. (3.2) — If C modelssatisfies derived_from<bidirectional_iterator_tag>, then iterator_category denotes bidirectional_iterator_tag.

    3. (3.3) — Otherwise, if C modelssatisfies derived_from<forward_iterator_tag>, then iterator_category denotes forward_iterator_tag.

    4. (3.4) — […]

  23. Modify [range.transform.iterator] as indicated:

    -1- iterator::iterator_concept is defined as follows:

    1. (1.1) — If V modelssatisfies random_access_range, then iterator_concept denotes random_access_iterator_tag.

    2. (1.2) — Otherwise, if V modelssatisfies bidirectional_range, then iterator_concept denotes bidirectional_iterator_tag.

    3. (1.3) — Otherwise, if V modelssatisfies forward_range, then iterator_concept denotes forward_iterator_tag.

    4. (1.4) — […]

    -2- Let C denote the type iterator_traits<iterator_t<Base>>::iterator_category. If C modelssatisfies derived_from<contiguous_iterator_tag>, then iterator_category denotes random_access_iterator_tag; otherwise, iterator_category denotes C.

  24. Modify [range.join.iterator] as indicated:

    -1- iterator::iterator_concept is defined as follows:

    1. (1.1) — If ref_is_glvalue is true and Base and range_reference_t<Base> each modelsatisfy bidirectional_range, then iterator_concept denotes bidirectional_iterator_tag.

    2. (1.2) — Otherwise, if ref_is_glvalue is true and Base and range_reference_t<Base> each modelsatisfy forward_range, then iterator_concept denotes forward_iterator_tag.

    3. (1.3) — […]

    -2- iterator::iterator_category is defined as follows:

    1. (2.1) — Let […]

    2. (2.2) — If ref_is_glvalue is true and OUTERC and INNERC each modelsatisfy derived_from<bidirectional_iterator_tag>, iterator_category denotes bidirectional_iterator_tag.

    3. (2.3) — Otherwise, if ref_is_glvalue is true and OUTERC and INNERC each modelsatisfy derived_from<forward_iterator_tag>, iterator_category denotes forward_iterator_tag.

    4. (2.4) — Otherwise, if OUTERC and INNERC each modelsatisfy derived_from<input_iterator_tag>, iterator_category denotes input_iterator_tag.

    5. (2.5) — […]

  25. Modify [range.split.outer] as indicated:

    […]
    Parent* parent_ = nullptr; // exposition only
    iterator_t<Base> current_ = // exposition only, present only if V modelssatisfies forward_range
      iterator_t<Base>();
    […]
    

    -1- Many of the following specifications refer to the notional member current of outer_iterator. current is equivalent to current_ if V modelssatisfies forward_range, and parent_->current_ otherwise.

  26. Modify [range.split.inner] as indicated:

    -1- The typedef-name iterator_category denotes

    1. (1.1) — forward_iterator_tag if iterator_traits<iterator_t<Base>>::iterator_category modelssatisfies derived_from<forward_iterator_tag>;

    2. (1.2) — otherwise, iterator_traits<iterator_t<Base>>::iterator_category.

  27. Modify [range.counted] as indicated:

    -2- The name views::counted denotes a customization point object ([customization.point.object]). Let E and F be expressions, and let T be decay_t<decltype((E))>. Then the expression views::counted(E, F) is expression-equivalent to:

    1. (2.1) — If T modelssatisfies input_or_output_iterator and decltype((F)) modelssatisfies convertible_to<iter_difference_t<T>>,

      1. (2.1.1) — subrange{E, E + static_cast<iter_difference_t<T>>(F)} if T modelssatisfies random_access_iterator.

      2. (2.1.2) — […]

    2. (2.2) — […]

  28. Modify [range.common.adaptor] as indicated:

    -1- The name views::common denotes a range adaptor object ([range.adaptor.object]). For some subexpression E, the expression views::common(E) is expression-equivalent to:

    1. (1.1) — views::all(E), if decltype((E)) modelssatisfies common_range and views::all(E) is a well-formed expression.

    2. (1.2) — […]

  29. Modify [alg.equal] as indicated:

    template<class InputIterator1, class InputIterator2>
      constexpr bool equal(InputIterator1 first1, InputIterator1 last1,
                           InputIterator2 first2);
    […]
    template<input_range R1, input_range R2, class Pred = ranges::equal_to,
              class Proj1 = identity, class Proj2 = identity>
      requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
      constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},
                                   Proj1 proj1 = {}, Proj2 proj2 = {});
    

    […]

    -3- Complexity: If the types of first1, last1, first2, and last2:

    1. (3.1) — meet the Cpp17RandomAccessIterator requirements ([random.access.iterators]) for the overloads in namespace std, or

    2. (3.2) — pairwise modelsatisfy sized_sentinel_for ([iterator.concept.sizedsentinel]) for the overloads in namespace ranges, and last1 - first1 != last2 - first2, then no applications of the corresponding predicate and each projection; otherwise,

    3. (3.3) — […]

    4. (3.4) — […]

  30. Modify [alg.is.permutation] as indicated:

    template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
             sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity,
             class Proj2 = identity>
      requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
      constexpr bool ranges::is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
                                            Pred pred = {},
                                            Proj1 proj1 = {}, Proj2 proj2 = {});
    template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
             class Proj1 = identity, class Proj2 = identity>
      requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
      constexpr bool ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {},
                                            Proj1 proj1 = {}, Proj2 proj2 = {});
    

    […]

    -7- Complexity: No applications of the corresponding predicate and projections if:

    1. (7.1) — S1 and I1 modelsatisfy sized_sentinel_for<S1, I1>,

    2. (7.2) — S2 and I2 modelsatisfy sized_sentinel_for<S2, I2>, and

    3. (7.3) — […]

  31. Modify [alg.partitions] as indicated:

    template<class ForwardIterator, class Predicate>
      constexpr ForwardIterator
        partition(ForwardIterator first, ForwardIterator last, Predicate pred);
    […]
    template<forward_range R, class Proj = identity,
             indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
      requires permutable<iterator_t<R>>
      constexpr safe_subrange_t<R>
        ranges::partition(R&& r, Pred pred, Proj proj = {});
    

    […]

    -8- Complexity: Let N = last - first:

    1. (8.1) — For the overload with no ExecutionPolicy, exactly N applications of the predicate and projection. At most N/2 swaps if the type of first meets the Cpp17BidirectionalIterator requirements for the overloads in namespace std or modelssatisfies bidirectional_iterator for the overloads in namespace ranges, and at most N swaps otherwise.

    2. (8.2) […]

Date: 2019-12-08.00:00:00

[ 2019-12-08 Issue Prioritization ]

Priority to 2 after reflector discussion.

Date: 2019-11-23.00:00:00

The current working draft uses at several places within normative wording the term "models" instead of "satisfies" even though it is clear from the context that these are conditions to be tested by the implementation. Since "models" includes both syntactic requirements as well as semantic requirements, such wording would require (at least in general) heroic efforts for an implementation. Just to name a few examples for such misusage:

  • The specification of the customization objects in [concept.swappable], [iterator.cust.swap], [range.access]

  • The algorithmic decision logic for the effects of the functions specified in [range.iter.op.advance], [range.iter.op.distance]

The correct way to fix these presumably unintended extra requirements is to use the term "satisfies" at the places where it is clear that an implementation has to test them.

Note: There exists similar misusage in regard to wording for types that "meet Cpp17XX requirements, but those are not meant to be covered as part of this issue. This additional wording problem should be handled by a separate issue.

History
Date User Action Args
2019-12-15 11:55:48adminsetmessages: + msg10890
2019-12-08 18:50:22adminsetmessages: + msg10876
2019-11-30 13:34:19adminsetmessages: + msg10849
2019-11-23 00:00:00admincreate