Guard against possible overflow in span.subpan

[miscco]

Summary

There is a possible overflow in span.subspan as described here https://github.com/microsoft/STL/issues/159

Interestingly the other three overloads are already correct.

While we are there use element_type rather than _Tp

[miscco]

As a side note we could also simplify the non templated subspan method

constexpr span<element_type, dynamic_extent>
_LIBCPP_INLINE_VISIBILITY
subspan(index_type __offset, index_type __count = dynamic_extent) const noexcept
{
    _LIBCPP_ASSERT(__offset <= size(), "Offset out of range in span::subspan(offset, count)");
    _LIBCPP_ASSERT(__count  <= size() || __count == dynamic_extent, "count out of range in span::subspan(offset, count)");
    if (__count == dynamic_extent)
        return {data() + __offset, size() - __offset};
    _LIBCPP_ASSERT(__offset <= size() - __count, "Offset + count out of range in span::subspan(offset, count)");
    return {data() + __offset, __count};
}

To the equivalent

constexpr span<element_type, dynamic_extent>
_LIBCPP_INLINE_VISIBILITY
subspan(index_type __offset, index_type __count = dynamic_extent) const noexcept
{
    _LIBCPP_ASSERT(__offset <= size(), "Offset out of range in span::subspan(offset, count)");
    _LIBCPP_ASSERT(__count == dynamic_extent || __offset <= size() - __count, "Offset + count out of range in span::subspan(offset, count)");
    return {data() + __offset, __count == dynamic_extent ? size() - __offset : __count };
}

If __count == dynamic_extent then the second assert is never tested. If __count != dynamic_extent then __count <= size() follows from conjunction of __offset <= size() and __offset <= size() - __count

However, I wasn't too sure whether it should go into the same revision

[mclow.lists]

This looks fine to me, except that there's no test to show that it works.

[mclow.lists]

In D68952#1708360, @miscco wrote:

As a side note we could also simplify the non templated subspan method

[snip]

I don't find that code to be simpler.
It's shorter, but harder to understand.

[CaseyCarter]

include/span

449

Pre-existing bug: The return type should be span<element_type, _Count>.

452

_Offset <= size() - _Count should be _Count <= size() - _Offset per the P/R of LWG-3103. _Offset <= size() - _Count admits span("Hello").subspan<4, -size_t{2}>() and returns an enormous invalid span.

[miscco]

When implementing span for MS STL I locally used the libcx tests against my implementation, i found that there are some instances where libcxx is not fully conforming (due to rapidly shifting span specification). Should I prepare one big patch or go on incrementally.

[snip]

I don't find that code to be simpler.
It's shorter, but harder to understand.

What I find better about that code is that it is equivalent to the other subspan methods. I will definitely add a test against the error cases

[mclow.lists]

In D68952#1716195, @miscco wrote:

When implementing span for MS STL I locally used the libcx tests against my implementation, i found that there are some instances where libcxx is not fully conforming (due to rapidly shifting span specification). Should I prepare one big patch or go on incrementally.

How many cases are we talking about?
In general, I would say incrementally.
Smaller patches are easier to review.

[miscco]

Fixed preexisting bug and added necessary static_assert in another case

Also added (untested) Unit tests

[miscco]

I have to appologize, but my linux distribution needs to be reset. I havent had time for that so I only wrote some logical tests and will expand once I find time to setup linux again

[CaseyCarter]

test/std/containers/views/span.sub/subspan.fail.cpp

35

These template disambiguators should all be unnecessary since none of the object expressions have dependent type. In other words, span<int>().subspan<0, 0>() doesn't need a disambiguator since the compiler knows that span<int>() has type span<int> and it can see that subspan is a member template. This:

template<class T>
auto f() {
  return span<T>.template subspan<0, 0>();

on the other hand *does* need a disambiguator: span<T> has dependent type since T has dependent type. span<T> could be a specialization of span that the compiler hasn't even seen yet, so it can only guess what span<T>.subspan is.

[CaseyCarter]

(I'm not sure how to withdraw my "Request Changes" without approving - I'm not an authorized approver for libc++ - so I'll "Resign as Reviewer" and see if my red X goes away.)

[smeenai]

In D68952#1718235, @CaseyCarter wrote:

(I'm not sure how to withdraw my "Request Changes" without approving - I'm not an authorized approver for libc++ - so I'll "Resign as Reviewer" and see if my red X goes away.)

Phabricator clears a request changes status when you upload a new version, so in this case you didn't need to do anything. In the general case though, I've found that the only way to clear an active request changes is to approve and then resign as reviewer. Resigning as reviewer clears your approval, but doesn't clear a request changes.

[miscco]

I messed with arcanist and created a new revision so I am going to close this one

include/span

//  ~span() noexcept = default;
     }
 
     template <size_t _Offset, size_t _Count = dynamic_extent>
     _LIBCPP_INLINE_VISIBILITY
     constexpr auto subspan() const noexcept
         -> span<element_type, _Count != dynamic_extent ? _Count : _Extent - _Offset>
     {
         static_assert(_Offset <= _Extent, "Offset out of range in span::subspan()");
+    static_assert(_Count == dynamic_extent || _Count <= _Extent - _Offset, "Offset + count out of range in span::subspan()");
         return {data() + _Offset, _Count == dynamic_extent ? size() - _Offset : _Count};
     }
 
 
     _LIBCPP_INLINE_VISIBILITY
     constexpr span<element_type, dynamic_extent>
        subspan(index_type __offset, index_type __count = dynamic_extent) const noexcept
     {
         _LIBCPP_ASSERT(__offset <= size(), "Offset out of range in span::subspan(offset, count)");
         _LIBCPP_ASSERT(__count  <= size() || __count == dynamic_extent, "Count out of range in span::subspan(offset, count)");
         if (__count == dynamic_extent)
             return {data() + __offset, size() - __offset};
-        _LIBCPP_ASSERT(__offset <= size() - __count, "count + offset out of range in span::subspan(offset, count)");
+        _LIBCPP_ASSERT(__count <= size() - __offset, "Offset + count out of range in span::subspan(offset, count)");
         return {data() + __offset, __count};
     }
 
     _LIBCPP_INLINE_VISIBILITY constexpr index_type size()       const noexcept { return _Extent; }
     _LIBCPP_INLINE_VISIBILITY constexpr index_type size_bytes() const noexcept { return _Extent * sizeof(element_type); }
     _LIBCPP_INLINE_VISIBILITY constexpr bool empty()            const noexcept { return _Extent == 0; }
 
     _LIBCPP_INLINE_VISIBILITY constexpr reference operator[](index_type __idx) const noexcept
//    ~span() noexcept = default;
     constexpr span<element_type, dynamic_extent> last (index_type __count) const noexcept
     {
         _LIBCPP_ASSERT(__count <= size(), "Count out of range in span::last(count)");
         return {data() + size() - __count, __count};
     }
 
     template <size_t _Offset, size_t _Count = dynamic_extent>
     _LIBCPP_INLINE_VISIBILITY
-    constexpr span<_Tp, dynamic_extent> subspan() const noexcept
+    constexpr span<element_type, _Count> subspan() const noexcept
     {
         _LIBCPP_ASSERT(_Offset <= size(), "Offset out of range in span::subspan()");
-        _LIBCPP_ASSERT(_Count == dynamic_extent || _Offset + _Count <= size(), "Count out of range in span::subspan()");
+        _LIBCPP_ASSERT(_Count == dynamic_extent || _Count <= size() - _Offset, "Offset + count out of range in span::subspan()");
         return {data() + _Offset, _Count == dynamic_extent ? size() - _Offset : _Count};
     }
 
     constexpr span<element_type, dynamic_extent>
     _LIBCPP_INLINE_VISIBILITY
     subspan(index_type __offset, index_type __count = dynamic_extent) const noexcept
     {
         _LIBCPP_ASSERT(__offset <= size(), "Offset out of range in span::subspan(offset, count)");
         _LIBCPP_ASSERT(__count  <= size() || __count == dynamic_extent, "count out of range in span::subspan(offset, count)");
         if (__count == dynamic_extent)
             return {data() + __offset, size() - __offset};
-        _LIBCPP_ASSERT(__offset <= size() - __count, "Offset + count out of range in span::subspan(offset, count)");
+        _LIBCPP_ASSERT(__count <= size() - __offset, "Offset + count out of range in span::subspan(offset, count)");
         return {data() + __offset, __count};
     }
 
     _LIBCPP_INLINE_VISIBILITY constexpr index_type size()       const noexcept { return __size; }
     _LIBCPP_INLINE_VISIBILITY constexpr index_type size_bytes() const noexcept { return __size * sizeof(element_type); }
     _LIBCPP_INLINE_VISIBILITY constexpr bool empty()            const noexcept { return __size == 0; }
 
     _LIBCPP_INLINE_VISIBILITY constexpr reference operator[](index_type __idx) const noexcept

test/std/containers/views/span.sub/subspan.fail.cpp

+// -*- C++ -*-
+//===------------------------------ span ---------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===---------------------------------------------------------------------===//
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+
+// <span>
+
+// template<size_t Offset, size_t Count = dynamic_extent>
+//   constexpr span<element_type, see below> subspan() const;
+//
+// constexpr span<element_type, dynamic_extent> subspan(
+//   index_type offset, index_type count = dynamic_extent) const;
+//
+//  Requires: offset <= size() && 
+//            (count == dynamic_extent || count <= size() - offset)
+
+#include <span>
+
+#include "test_macros.h"
+
+constexpr int carr1[] = { 1,2,3,4 };
+
+int main(int, char**)
+{
+  span<int, 4> sp_static{ carr1 };
+  span<int> sp_dynamic{ carr1 };
+  
+  //  Offset too large templatized
+  {
+    auto s1 = sp_static.template subspan<5>(); // expected-error {{Offset out of range in span::subspan()}}
+    auto s2 = sp_dynamic.template subspan<5>(); // expected-error {{Offset out of range in span::subspan()}}
+  }
+
+  //  Count too large templatized
+  {
+    auto s1 = sp_static.template subspan<0, 5>(); // expected-error {{Offset + count out of range in span::subspan()}}
+    auto s2 = sp_dynamic.template subspan<0, 5>(); // expected-error {{Offset + count out of range in span::subspan()}}
+  }
+
+  //  Offset + Count too large templatized
+  {
+    auto s1 = sp_static.template subspan<2, 3>(); // expected-error {{Offset + count out of range in span::subspan()}}
+    auto s2 = sp_dynamic.template subspan<2, 3>(); // expected-error {{Offset + count out of range in span::subspan()}}
+  }
+  
+  //  Offset + Count overflow templatized
+  {
+    auto s1 = sp_static.template subspan<3, std::size_t(-2)>(); // expected-error {{Offset + count out of range in span::subspan()}}
+    auto s2 = sp_dynamic.template subspan<3, std::size_t(-2)>(); // expected-error {{Offset + count out of range in span::subspan()}}
+  }
+
+  //  Offset too large dynamic
+  {
+    auto s1 = sp_static.subspan(5); // expected-error {{Offset out of range in span::subspan(offset, count)}}
+    auto s2 = sp_dynamic.subspan(5); // expected-error {{Offset out of range in span::subspan(offset, count)}}
+  }
+
+  //  Count too large dynamic
+  {
+    auto s1 = sp_static.subspan(0, 5); // expected-error {{Count out of range in span::subspan(offset, count)}}
+    auto s2 = sp_dynamic.subspan(0, 5); // expected-error {{Count out of range in span::subspan(offset, count)}}
+  }
+
+  //  Offset + Count too large dynamic
+  {
+    auto s1 = sp_static.subspan(2, 3); // expected-error {{Offset + count out of range in span::subspan(offset, count)}}
+    auto s2 = sp_dynamic.subspan(2, 3); // expected-error {{Offset + count out of range in span::subspan(offset, count)}}
+  }
+
+  //  Offset + Count overflow dynamic
+  {
+    auto s1 = sp_static.subspan(3, std::size_t(-2)); // expected-error {{Count out of range in span::subspan(offset, count)}}
+    auto s2 = sp_dynamic.subspan(3, std::size_t(-2)); // expected-error {{Count out of range in span::subspan(offset, count)}}
+  }
+  return 0;
+}