Skip to content

Commit b8740d6

Browse files
laanwjlaanwj
committed
Merge #18468: Span improvements
26acc8d Add sanity check asserts to span when -DDEBUG (Pieter Wuille) 2676aea Simplify usage of Span in several places (Pieter Wuille) ab303a1 Add Span constructors for arrays and vectors (Pieter Wuille) bb3d38f Make pointer-based Span construction safer (Pieter Wuille) 1f790a1 Make Span size type unsigned (Pieter Wuille) Pull request description: This improves our Span class by making it closer to the C++20 `std::span` one: * ~~Support conversion between compatible Spans (e.g. `Span<char>` to `Span<const char>`).~~ (done in #18591) * Make the size type `std::size_t` rather than `std::ptrdiff_t` (the C++20 one underwent the same change). * Support construction of Spans directly from arrays, `std::string`s, `std::array`s, `std::vector`s, `prevector`s, ... (for all but arrays, this only works for const containers to prevent surprises). And then make use of those improvements in various call sites. I realize the template magic used looks scary, but it's only needed to make overload resultion make the right choices. Note that the operations done on values are all extremely simple: no casts, explicit conversions, or warning-silencing constructions. That should hopefully make it simpler to review. ACKs for top commit: laanwj: Code review ACK 26acc8d promag: Code review ACK 26acc8d. Tree-SHA512: 5a5bd346a140edf782b5b3b3f04d9160c7b9e9def35159814a07780ab1dd352545b88d3cc491e0f80d161f829c49ebfb952fddc9180f1a56f1257aa51f38788a
2 parents 343c0bf + 26acc8d commit b8740d6

File tree

6 files changed

+104
-44
lines changed

6 files changed

+104
-44
lines changed

‎src/script/descriptor.cpp‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -139,7 +139,7 @@ std::string DescriptorChecksum(const Span<const char>& span)
139139
return ret;
140140
}
141141

142-
std::string AddChecksum(const std::string& str) { return str + "#" + DescriptorChecksum(MakeSpan(str)); }
142+
std::string AddChecksum(const std::string& str) { return str + "#" + DescriptorChecksum(str); }
143143

144144
////////////////////////////////////////////////////////////////////////////
145145
// Internal representation //
@@ -1087,7 +1087,7 @@ bool CheckChecksum(Span<const char>& sp, bool require_checksum, std::string& err
10871087

10881088
std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum)
10891089
{
1090-
Span<const char> sp(descriptor.data(), descriptor.size());
1090+
Span<const char> sp{descriptor};
10911091
if (!CheckChecksum(sp, require_checksum, error)) return nullptr;
10921092
auto ret = ParseScript(0, sp, ParseScriptContext::TOP, out, error);
10931093
if (sp.size() == 0 && ret) return std::unique_ptr<Descriptor>(std::move(ret));
@@ -1098,7 +1098,7 @@ std::string GetDescriptorChecksum(const std::string& descriptor)
10981098
{
10991099
std::string ret;
11001100
std::string error;
1101-
Span<const char> sp(descriptor.data(), descriptor.size());
1101+
Span<const char> sp{descriptor};
11021102
if (!CheckChecksum(sp, false, error, &ret)) return "";
11031103
return ret;
11041104
}

‎src/script/interpreter.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1522,7 +1522,7 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
15221522
static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
15231523
{
15241524
CScript scriptPubKey;
1525-
Span<const valtype> stack = MakeSpan(witness.stack);
1525+
Span<const valtype> stack{witness.stack};
15261526

15271527
if (witversion == 0) {
15281528
if (program.size() == WITNESS_V0_SCRIPTHASH_SIZE) {

‎src/span.h‎

Lines changed: 86 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,14 @@
1010
#include <algorithm>
1111
#include <assert.h>
1212

13+
#ifdef DEBUG
14+
#define CONSTEXPR_IF_NOT_DEBUG
15+
#define ASSERT_IF_DEBUG(x) assert((x))
16+
#else
17+
#define CONSTEXPR_IF_NOT_DEBUG constexpr
18+
#define ASSERT_IF_DEBUG(x)
19+
#endif
20+
1321
/** A Span is an object that can refer to a contiguous sequence of objects.
1422
*
1523
* It implements a subset of C++20's std::span.
@@ -18,12 +26,29 @@ template<typename C>
1826
class Span
1927
{
2028
C* m_data;
21-
std::ptrdiff_t m_size;
29+
std::size_t m_size;
2230

2331
public:
2432
constexpr Span() noexcept : m_data(nullptr), m_size(0) {}
25-
constexpr Span(C* data, std::ptrdiff_t size) noexcept : m_data(data), m_size(size) {}
26-
constexpr Span(C* data, C* end) noexcept : m_data(data), m_size(end - data) {}
33+
34+
/** Construct a span from a begin pointer and a size.
35+
*
36+
* This implements a subset of the iterator-based std::span constructor in C++20,
37+
* which is hard to implement without std::address_of.
38+
*/
39+
template <typename T, typename std::enable_if<std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0>
40+
constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
41+
42+
/** Construct a span from a begin and end pointer.
43+
*
44+
* This implements a subset of the iterator-based std::span constructor in C++20,
45+
* which is hard to implement without std::address_of.
46+
*/
47+
template <typename T, typename std::enable_if<std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0>
48+
CONSTEXPR_IF_NOT_DEBUG Span(T* begin, T* end) noexcept : m_data(begin), m_size(end - begin)
49+
{
50+
ASSERT_IF_DEBUG(end >= begin);
51+
}
2752

2853
/** Implicit conversion of spans between compatible types.
2954
*
@@ -42,18 +67,59 @@ class Span
4267
/** Default assignment operator. */
4368
Span& operator=(const Span& other) noexcept = default;
4469

70+
/** Construct a Span from an array. This matches the corresponding C++20 std::span constructor. */
71+
template <int N>
72+
constexpr Span(C (&a)[N]) noexcept : m_data(a), m_size(N) {}
73+
74+
/** Construct a Span for objects with .data() and .size() (std::string, std::array, std::vector, ...).
75+
*
76+
* This implements a subset of the functionality provided by the C++20 std::span range-based constructor.
77+
*
78+
* To prevent surprises, only Spans for constant value types are supported when passing in temporaries.
79+
* Note that this restriction does not exist when converting arrays or other Spans (see above).
80+
*/
81+
template <typename V, typename std::enable_if<(std::is_const<C>::value || std::is_lvalue_reference<V>::value) && std::is_convertible<typename std::remove_pointer<decltype(std::declval<V&>().data())>::type (*)[], C (*)[]>::value && std::is_convertible<decltype(std::declval<V&>().size()), std::size_t>::value, int>::type = 0>
82+
constexpr Span(V&& v) noexcept : m_data(v.data()), m_size(v.size()) {}
83+
4584
constexpr C* data() const noexcept { return m_data; }
4685
constexpr C* begin() const noexcept { return m_data; }
4786
constexpr C* end() const noexcept { return m_data + m_size; }
48-
constexpr C& front() const noexcept { return m_data[0]; }
49-
constexpr C& back() const noexcept { return m_data[m_size - 1]; }
50-
constexpr std::ptrdiff_t size() const noexcept { return m_size; }
51-
constexpr C& operator[](std::ptrdiff_t pos) const noexcept { return m_data[pos]; }
52-
53-
constexpr Span<C> subspan(std::ptrdiff_t offset) const noexcept { return Span<C>(m_data + offset, m_size - offset); }
54-
constexpr Span<C> subspan(std::ptrdiff_t offset, std::ptrdiff_t count) const noexcept { return Span<C>(m_data + offset, count); }
55-
constexpr Span<C> first(std::ptrdiff_t count) const noexcept { return Span<C>(m_data, count); }
56-
constexpr Span<C> last(std::ptrdiff_t count) const noexcept { return Span<C>(m_data + m_size - count, count); }
87+
CONSTEXPR_IF_NOT_DEBUG C& front() const noexcept
88+
{
89+
ASSERT_IF_DEBUG(size() > 0);
90+
return m_data[0];
91+
}
92+
CONSTEXPR_IF_NOT_DEBUG C& back() const noexcept
93+
{
94+
ASSERT_IF_DEBUG(size() > 0);
95+
return m_data[m_size - 1];
96+
}
97+
constexpr std::size_t size() const noexcept { return m_size; }
98+
CONSTEXPR_IF_NOT_DEBUG C& operator[](std::size_t pos) const noexcept
99+
{
100+
ASSERT_IF_DEBUG(size() > pos);
101+
return m_data[pos];
102+
}
103+
CONSTEXPR_IF_NOT_DEBUG Span<C> subspan(std::size_t offset) const noexcept
104+
{
105+
ASSERT_IF_DEBUG(size() >= offset);
106+
return Span<C>(m_data + offset, m_size - offset);
107+
}
108+
CONSTEXPR_IF_NOT_DEBUG Span<C> subspan(std::size_t offset, std::size_t count) const noexcept
109+
{
110+
ASSERT_IF_DEBUG(size() >= offset + count);
111+
return Span<C>(m_data + offset, count);
112+
}
113+
CONSTEXPR_IF_NOT_DEBUG Span<C> first(std::size_t count) const noexcept
114+
{
115+
ASSERT_IF_DEBUG(size() >= count);
116+
return Span<C>(m_data, count);
117+
}
118+
CONSTEXPR_IF_NOT_DEBUG Span<C> last(std::size_t count) const noexcept
119+
{
120+
ASSERT_IF_DEBUG(size() >= count);
121+
return Span<C>(m_data + m_size - count, count);
122+
}
57123

58124
friend constexpr bool operator==(const Span& a, const Span& b) noexcept { return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()); }
59125
friend constexpr bool operator!=(const Span& a, const Span& b) noexcept { return !(a == b); }
@@ -65,26 +131,20 @@ class Span
65131
template <typename O> friend class Span;
66132
};
67133

68-
/** Create a span to a container exposing data() and size().
69-
*
70-
* This correctly deals with constness: the returned Span's element type will be
71-
* whatever data() returns a pointer to. If either the passed container is const,
72-
* or its element type is const, the resulting span will have a const element type.
73-
*
74-
* std::span will have a constructor that implements this functionality directly.
75-
*/
76-
template<typename A, int N>
77-
constexpr Span<A> MakeSpan(A (&a)[N]) { return Span<A>(a, N); }
78-
79-
template<typename V>
80-
constexpr Span<typename std::remove_pointer<decltype(std::declval<V>().data())>::type> MakeSpan(V& v) { return Span<typename std::remove_pointer<decltype(std::declval<V>().data())>::type>(v.data(), v.size()); }
134+
// MakeSpan helps constructing a Span of the right type automatically.
135+
/** MakeSpan for arrays: */
136+
template <typename A, int N> Span<A> constexpr MakeSpan(A (&a)[N]) { return Span<A>(a, N); }
137+
/** MakeSpan for temporaries / rvalue references, only supporting const output. */
138+
template <typename V> constexpr auto MakeSpan(V&& v) -> typename std::enable_if<!std::is_lvalue_reference<V>::value, Span<const typename std::remove_pointer<decltype(v.data())>::type>>::type { return std::forward<V>(v); }
139+
/** MakeSpan for (lvalue) references, supporting mutable output. */
140+
template <typename V> constexpr auto MakeSpan(V& v) -> Span<typename std::remove_pointer<decltype(v.data())>::type> { return v; }
81141

82142
/** Pop the last element off a span, and return a reference to that element. */
83143
template <typename T>
84144
T& SpanPopBack(Span<T>& span)
85145
{
86146
size_t size = span.size();
87-
assert(size > 0);
147+
ASSERT_IF_DEBUG(size > 0);
88148
T& back = span[size - 1];
89149
span = Span<T>(span.data(), size - 1);
90150
return back;

‎src/test/fuzz/span.cpp‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@ void test_one_input(const std::vector<uint8_t>& buffer)
1818
FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
1919

2020
std::string str = fuzzed_data_provider.ConsumeBytesAsString(32);
21-
const Span<const char> span = MakeSpan(str);
21+
const Span<const char> span{str};
2222
(void)span.data();
2323
(void)span.begin();
2424
(void)span.end();
@@ -32,7 +32,7 @@ void test_one_input(const std::vector<uint8_t>& buffer)
3232
}
3333

3434
std::string another_str = fuzzed_data_provider.ConsumeBytesAsString(32);
35-
const Span<const char> another_span = MakeSpan(another_str);
35+
const Span<const char> another_span{another_str};
3636
assert((span <= another_span) != (span > another_span));
3737
assert((span == another_span) != (span != another_span));
3838
assert((span >= another_span) != (span < another_span));

‎src/test/fuzz/spanparsing.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@ void test_one_input(const std::vector<uint8_t>& buffer)
1212
const size_t query_size = fuzzed_data_provider.ConsumeIntegral<size_t>();
1313
const std::string query = fuzzed_data_provider.ConsumeBytesAsString(std::min<size_t>(query_size, 1024 * 1024));
1414
const std::string span_str = fuzzed_data_provider.ConsumeRemainingBytesAsString();
15-
const Span<const char> const_span = MakeSpan(span_str);
15+
const Span<const char> const_span{span_str};
1616

1717
Span<const char> mut_span = const_span;
1818
(void)spanparsing::Const(query, mut_span);

‎src/test/util_tests.cpp‎

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1829,7 +1829,7 @@ BOOST_AUTO_TEST_CASE(test_spanparsing)
18291829

18301830
// Const(...): parse a constant, update span to skip it if successful
18311831
input = "MilkToastHoney";
1832-
sp = MakeSpan(input);
1832+
sp = input;
18331833
success = Const("", sp); // empty
18341834
BOOST_CHECK(success);
18351835
BOOST_CHECK_EQUAL(SpanToStr(sp), "MilkToastHoney");
@@ -1854,7 +1854,7 @@ BOOST_AUTO_TEST_CASE(test_spanparsing)
18541854

18551855
// Func(...): parse a function call, update span to argument if successful
18561856
input = "Foo(Bar(xy,z()))";
1857-
sp = MakeSpan(input);
1857+
sp = input;
18581858

18591859
success = Func("FooBar", sp);
18601860
BOOST_CHECK(!success);
@@ -1877,31 +1877,31 @@ BOOST_AUTO_TEST_CASE(test_spanparsing)
18771877
Span<const char> result;
18781878

18791879
input = "(n*(n-1))/2";
1880-
sp = MakeSpan(input);
1880+
sp = input;
18811881
result = Expr(sp);
18821882
BOOST_CHECK_EQUAL(SpanToStr(result), "(n*(n-1))/2");
18831883
BOOST_CHECK_EQUAL(SpanToStr(sp), "");
18841884

18851885
input = "foo,bar";
1886-
sp = MakeSpan(input);
1886+
sp = input;
18871887
result = Expr(sp);
18881888
BOOST_CHECK_EQUAL(SpanToStr(result), "foo");
18891889
BOOST_CHECK_EQUAL(SpanToStr(sp), ",bar");
18901890

18911891
input = "(aaaaa,bbbbb()),c";
1892-
sp = MakeSpan(input);
1892+
sp = input;
18931893
result = Expr(sp);
18941894
BOOST_CHECK_EQUAL(SpanToStr(result), "(aaaaa,bbbbb())");
18951895
BOOST_CHECK_EQUAL(SpanToStr(sp), ",c");
18961896

18971897
input = "xyz)foo";
1898-
sp = MakeSpan(input);
1898+
sp = input;
18991899
result = Expr(sp);
19001900
BOOST_CHECK_EQUAL(SpanToStr(result), "xyz");
19011901
BOOST_CHECK_EQUAL(SpanToStr(sp), ")foo");
19021902

19031903
input = "((a),(b),(c)),xxx";
1904-
sp = MakeSpan(input);
1904+
sp = input;
19051905
result = Expr(sp);
19061906
BOOST_CHECK_EQUAL(SpanToStr(result), "((a),(b),(c))");
19071907
BOOST_CHECK_EQUAL(SpanToStr(sp), ",xxx");
@@ -1910,27 +1910,27 @@ BOOST_AUTO_TEST_CASE(test_spanparsing)
19101910
std::vector<Span<const char>> results;
19111911

19121912
input = "xxx";
1913-
results = Split(MakeSpan(input), 'x');
1913+
results = Split(input, 'x');
19141914
BOOST_CHECK_EQUAL(results.size(), 4U);
19151915
BOOST_CHECK_EQUAL(SpanToStr(results[0]), "");
19161916
BOOST_CHECK_EQUAL(SpanToStr(results[1]), "");
19171917
BOOST_CHECK_EQUAL(SpanToStr(results[2]), "");
19181918
BOOST_CHECK_EQUAL(SpanToStr(results[3]), "");
19191919

19201920
input = "one#two#three";
1921-
results = Split(MakeSpan(input), '-');
1921+
results = Split(input, '-');
19221922
BOOST_CHECK_EQUAL(results.size(), 1U);
19231923
BOOST_CHECK_EQUAL(SpanToStr(results[0]), "one#two#three");
19241924

19251925
input = "one#two#three";
1926-
results = Split(MakeSpan(input), '#');
1926+
results = Split(input, '#');
19271927
BOOST_CHECK_EQUAL(results.size(), 3U);
19281928
BOOST_CHECK_EQUAL(SpanToStr(results[0]), "one");
19291929
BOOST_CHECK_EQUAL(SpanToStr(results[1]), "two");
19301930
BOOST_CHECK_EQUAL(SpanToStr(results[2]), "three");
19311931

19321932
input = "*foo*bar*";
1933-
results = Split(MakeSpan(input), '*');
1933+
results = Split(input, '*');
19341934
BOOST_CHECK_EQUAL(results.size(), 4U);
19351935
BOOST_CHECK_EQUAL(SpanToStr(results[0]), "");
19361936
BOOST_CHECK_EQUAL(SpanToStr(results[1]), "foo");

0 commit comments

Comments
 (0)