From 1f790a1147ad9a5fe06987d84b6cd71f91cbec4b Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sun, 29 Mar 2020 16:31:03 -0700 Subject: Make Span size type unsigned This matches a change in the C++20 std::span proposal. --- src/span.h | 17 +++++++++-------- 1 file changed, 9 insertions(+), 8 deletions(-) diff --git a/src/span.h b/src/span.h index 73b37e35f3..31e9fba12c 100644 --- a/src/span.h +++ b/src/span.h @@ -18,11 +18,12 @@ template class Span { C* m_data; - std::ptrdiff_t m_size; + std::size_t m_size; public: constexpr Span() noexcept : m_data(nullptr), m_size(0) {} - constexpr Span(C* data, std::ptrdiff_t size) noexcept : m_data(data), m_size(size) {} + constexpr Span(C* data, std::size_t size) noexcept : m_data(data), m_size(size) {} + constexpr Span(C* data, C* end) noexcept : m_data(data), m_size(end - data) {} /** Implicit conversion of spans between compatible types. @@ -47,13 +48,13 @@ public: constexpr C* end() const noexcept { return m_data + m_size; } constexpr C& front() const noexcept { return m_data[0]; } constexpr C& back() const noexcept { return m_data[m_size - 1]; } - constexpr std::ptrdiff_t size() const noexcept { return m_size; } - constexpr C& operator[](std::ptrdiff_t pos) const noexcept { return m_data[pos]; } + constexpr std::size_t size() const noexcept { return m_size; } + constexpr C& operator[](std::size_t pos) const noexcept { return m_data[pos]; } - constexpr Span subspan(std::ptrdiff_t offset) const noexcept { return Span(m_data + offset, m_size - offset); } - constexpr Span subspan(std::ptrdiff_t offset, std::ptrdiff_t count) const noexcept { return Span(m_data + offset, count); } - constexpr Span first(std::ptrdiff_t count) const noexcept { return Span(m_data, count); } - constexpr Span last(std::ptrdiff_t count) const noexcept { return Span(m_data + m_size - count, count); } + constexpr Span subspan(std::size_t offset) const noexcept { return Span(m_data + offset, m_size - offset); } + constexpr Span subspan(std::size_t offset, std::size_t count) const noexcept { return Span(m_data + offset, count); } + constexpr Span first(std::size_t count) const noexcept { return Span(m_data, count); } + constexpr Span last(std::size_t count) const noexcept { return Span(m_data + m_size - count, count); } friend constexpr bool operator==(const Span& a, const Span& b) noexcept { return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()); } friend constexpr bool operator!=(const Span& a, const Span& b) noexcept { return !(a == b); } -- cgit v1.2.3 From bb3d38fc061d8482e68cd335a45c9cd8bb66a475 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sun, 29 Mar 2020 16:58:04 -0700 Subject: Make pointer-based Span construction safer This prevents constructing a Span given two pointers into an array of B (where B is a subclass of A), at least without explicit cast to pointers to A. --- src/span.h | 17 +++++++++++++++-- 1 file changed, 15 insertions(+), 2 deletions(-) diff --git a/src/span.h b/src/span.h index 31e9fba12c..f83c1a5349 100644 --- a/src/span.h +++ b/src/span.h @@ -22,9 +22,22 @@ class Span public: constexpr Span() noexcept : m_data(nullptr), m_size(0) {} - constexpr Span(C* data, std::size_t size) noexcept : m_data(data), m_size(size) {} - constexpr Span(C* data, C* end) noexcept : m_data(data), m_size(end - data) {} + /** Construct a span from a begin pointer and a size. + * + * This implements a subset of the iterator-based std::span constructor in C++20, + * which is hard to implement without std::address_of. + */ + template ::value, int>::type = 0> + constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {} + + /** Construct a span from a begin and end pointer. + * + * This implements a subset of the iterator-based std::span constructor in C++20, + * which is hard to implement without std::address_of. + */ + template ::value, int>::type = 0> + constexpr Span(T* begin, T* end) noexcept : m_data(begin), m_size(end - begin) {} /** Implicit conversion of spans between compatible types. * -- cgit v1.2.3 From ab303a16d114b1e94c6cf0e4c5db5389dfa197f6 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sun, 29 Mar 2020 17:29:01 -0700 Subject: Add Span constructors for arrays and vectors --- src/span.h | 34 +++++++++++++++++++++------------- 1 file changed, 21 insertions(+), 13 deletions(-) diff --git a/src/span.h b/src/span.h index f83c1a5349..d5fec462e1 100644 --- a/src/span.h +++ b/src/span.h @@ -56,6 +56,20 @@ public: /** Default assignment operator. */ Span& operator=(const Span& other) noexcept = default; + /** Construct a Span from an array. This matches the corresponding C++20 std::span constructor. */ + template + constexpr Span(C (&a)[N]) noexcept : m_data(a), m_size(N) {} + + /** Construct a Span for objects with .data() and .size() (std::string, std::array, std::vector, ...). + * + * This implements a subset of the functionality provided by the C++20 std::span range-based constructor. + * + * To prevent surprises, only Spans for constant value types are supported when passing in temporaries. + * Note that this restriction does not exist when converting arrays or other Spans (see above). + */ + template ::value || std::is_lvalue_reference::value) && std::is_convertible().data())>::type (*)[], C (*)[]>::value && std::is_convertible().size()), std::size_t>::value, int>::type = 0> + constexpr Span(V&& v) noexcept : m_data(v.data()), m_size(v.size()) {} + constexpr C* data() const noexcept { return m_data; } constexpr C* begin() const noexcept { return m_data; } constexpr C* end() const noexcept { return m_data + m_size; } @@ -79,19 +93,13 @@ public: template friend class Span; }; -/** Create a span to a container exposing data() and size(). - * - * This correctly deals with constness: the returned Span's element type will be - * whatever data() returns a pointer to. If either the passed container is const, - * or its element type is const, the resulting span will have a const element type. - * - * std::span will have a constructor that implements this functionality directly. - */ -template -constexpr Span MakeSpan(A (&a)[N]) { return Span(a, N); } - -template -constexpr Span().data())>::type> MakeSpan(V& v) { return Span().data())>::type>(v.data(), v.size()); } +// MakeSpan helps constructing a Span of the right type automatically. +/** MakeSpan for arrays: */ +template Span constexpr MakeSpan(A (&a)[N]) { return Span(a, N); } +/** MakeSpan for temporaries / rvalue references, only supporting const output. */ +template constexpr auto MakeSpan(V&& v) -> typename std::enable_if::value, Span::type>>::type { return std::forward(v); } +/** MakeSpan for (lvalue) references, supporting mutable output. */ +template constexpr auto MakeSpan(V& v) -> Span::type> { return v; } /** Pop the last element off a span, and return a reference to that element. */ template -- cgit v1.2.3 From 2676aeadfa0e43dcaaccc4720623cdfe0beed528 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sun, 29 Mar 2020 17:42:38 -0700 Subject: Simplify usage of Span in several places --- src/script/descriptor.cpp | 6 +++--- src/script/interpreter.cpp | 2 +- src/test/fuzz/span.cpp | 4 ++-- src/test/fuzz/spanparsing.cpp | 2 +- src/test/util_tests.cpp | 22 +++++++++++----------- 5 files changed, 18 insertions(+), 18 deletions(-) diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp index ed0175bb10..7a5421ab6f 100644 --- a/src/script/descriptor.cpp +++ b/src/script/descriptor.cpp @@ -139,7 +139,7 @@ std::string DescriptorChecksum(const Span& span) return ret; } -std::string AddChecksum(const std::string& str) { return str + "#" + DescriptorChecksum(MakeSpan(str)); } +std::string AddChecksum(const std::string& str) { return str + "#" + DescriptorChecksum(str); } //////////////////////////////////////////////////////////////////////////// // Internal representation // @@ -1087,7 +1087,7 @@ bool CheckChecksum(Span& sp, bool require_checksum, std::string& err std::unique_ptr Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum) { - Span sp(descriptor.data(), descriptor.size()); + Span sp{descriptor}; if (!CheckChecksum(sp, require_checksum, error)) return nullptr; auto ret = ParseScript(0, sp, ParseScriptContext::TOP, out, error); if (sp.size() == 0 && ret) return std::unique_ptr(std::move(ret)); @@ -1098,7 +1098,7 @@ std::string GetDescriptorChecksum(const std::string& descriptor) { std::string ret; std::string error; - Span sp(descriptor.data(), descriptor.size()); + Span sp{descriptor}; if (!CheckChecksum(sp, false, error, &ret)) return ""; return ret; } diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp index 23d5b72a5c..9415bba585 100644 --- a/src/script/interpreter.cpp +++ b/src/script/interpreter.cpp @@ -1522,7 +1522,7 @@ static bool ExecuteWitnessScript(const Span& stack_span, const CS static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror) { CScript scriptPubKey; - Span stack = MakeSpan(witness.stack); + Span stack{witness.stack}; if (witversion == 0) { if (program.size() == WITNESS_V0_SCRIPTHASH_SIZE) { diff --git a/src/test/fuzz/span.cpp b/src/test/fuzz/span.cpp index 4aea530ef2..f6b6e8f6f0 100644 --- a/src/test/fuzz/span.cpp +++ b/src/test/fuzz/span.cpp @@ -18,7 +18,7 @@ void test_one_input(const std::vector& buffer) FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size()); std::string str = fuzzed_data_provider.ConsumeBytesAsString(32); - const Span span = MakeSpan(str); + const Span span{str}; (void)span.data(); (void)span.begin(); (void)span.end(); @@ -32,7 +32,7 @@ void test_one_input(const std::vector& buffer) } std::string another_str = fuzzed_data_provider.ConsumeBytesAsString(32); - const Span another_span = MakeSpan(another_str); + const Span another_span{another_str}; assert((span <= another_span) != (span > another_span)); assert((span == another_span) != (span != another_span)); assert((span >= another_span) != (span < another_span)); diff --git a/src/test/fuzz/spanparsing.cpp b/src/test/fuzz/spanparsing.cpp index 8e5e7dad11..e5bf5dd608 100644 --- a/src/test/fuzz/spanparsing.cpp +++ b/src/test/fuzz/spanparsing.cpp @@ -12,7 +12,7 @@ void test_one_input(const std::vector& buffer) const size_t query_size = fuzzed_data_provider.ConsumeIntegral(); const std::string query = fuzzed_data_provider.ConsumeBytesAsString(std::min(query_size, 1024 * 1024)); const std::string span_str = fuzzed_data_provider.ConsumeRemainingBytesAsString(); - const Span const_span = MakeSpan(span_str); + const Span const_span{span_str}; Span mut_span = const_span; (void)spanparsing::Const(query, mut_span); diff --git a/src/test/util_tests.cpp b/src/test/util_tests.cpp index cf26ca3adb..257328974b 100644 --- a/src/test/util_tests.cpp +++ b/src/test/util_tests.cpp @@ -1829,7 +1829,7 @@ BOOST_AUTO_TEST_CASE(test_spanparsing) // Const(...): parse a constant, update span to skip it if successful input = "MilkToastHoney"; - sp = MakeSpan(input); + sp = input; success = Const("", sp); // empty BOOST_CHECK(success); BOOST_CHECK_EQUAL(SpanToStr(sp), "MilkToastHoney"); @@ -1854,7 +1854,7 @@ BOOST_AUTO_TEST_CASE(test_spanparsing) // Func(...): parse a function call, update span to argument if successful input = "Foo(Bar(xy,z()))"; - sp = MakeSpan(input); + sp = input; success = Func("FooBar", sp); BOOST_CHECK(!success); @@ -1877,31 +1877,31 @@ BOOST_AUTO_TEST_CASE(test_spanparsing) Span result; input = "(n*(n-1))/2"; - sp = MakeSpan(input); + sp = input; result = Expr(sp); BOOST_CHECK_EQUAL(SpanToStr(result), "(n*(n-1))/2"); BOOST_CHECK_EQUAL(SpanToStr(sp), ""); input = "foo,bar"; - sp = MakeSpan(input); + sp = input; result = Expr(sp); BOOST_CHECK_EQUAL(SpanToStr(result), "foo"); BOOST_CHECK_EQUAL(SpanToStr(sp), ",bar"); input = "(aaaaa,bbbbb()),c"; - sp = MakeSpan(input); + sp = input; result = Expr(sp); BOOST_CHECK_EQUAL(SpanToStr(result), "(aaaaa,bbbbb())"); BOOST_CHECK_EQUAL(SpanToStr(sp), ",c"); input = "xyz)foo"; - sp = MakeSpan(input); + sp = input; result = Expr(sp); BOOST_CHECK_EQUAL(SpanToStr(result), "xyz"); BOOST_CHECK_EQUAL(SpanToStr(sp), ")foo"); input = "((a),(b),(c)),xxx"; - sp = MakeSpan(input); + sp = input; result = Expr(sp); BOOST_CHECK_EQUAL(SpanToStr(result), "((a),(b),(c))"); BOOST_CHECK_EQUAL(SpanToStr(sp), ",xxx"); @@ -1910,7 +1910,7 @@ BOOST_AUTO_TEST_CASE(test_spanparsing) std::vector> results; input = "xxx"; - results = Split(MakeSpan(input), 'x'); + results = Split(input, 'x'); BOOST_CHECK_EQUAL(results.size(), 4U); BOOST_CHECK_EQUAL(SpanToStr(results[0]), ""); BOOST_CHECK_EQUAL(SpanToStr(results[1]), ""); @@ -1918,19 +1918,19 @@ BOOST_AUTO_TEST_CASE(test_spanparsing) BOOST_CHECK_EQUAL(SpanToStr(results[3]), ""); input = "one#two#three"; - results = Split(MakeSpan(input), '-'); + results = Split(input, '-'); BOOST_CHECK_EQUAL(results.size(), 1U); BOOST_CHECK_EQUAL(SpanToStr(results[0]), "one#two#three"); input = "one#two#three"; - results = Split(MakeSpan(input), '#'); + results = Split(input, '#'); BOOST_CHECK_EQUAL(results.size(), 3U); BOOST_CHECK_EQUAL(SpanToStr(results[0]), "one"); BOOST_CHECK_EQUAL(SpanToStr(results[1]), "two"); BOOST_CHECK_EQUAL(SpanToStr(results[2]), "three"); input = "*foo*bar*"; - results = Split(MakeSpan(input), '*'); + results = Split(input, '*'); BOOST_CHECK_EQUAL(results.size(), 4U); BOOST_CHECK_EQUAL(SpanToStr(results[0]), ""); BOOST_CHECK_EQUAL(SpanToStr(results[1]), "foo"); -- cgit v1.2.3 From 26acc8dd9b512f220c1facdba2c5de7976d3c258 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 4 Jun 2020 10:46:52 -0700 Subject: Add sanity check asserts to span when -DDEBUG --- src/span.h | 58 ++++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 48 insertions(+), 10 deletions(-) diff --git a/src/span.h b/src/span.h index d5fec462e1..4931507719 100644 --- a/src/span.h +++ b/src/span.h @@ -10,6 +10,14 @@ #include #include +#ifdef DEBUG +#define CONSTEXPR_IF_NOT_DEBUG +#define ASSERT_IF_DEBUG(x) assert((x)) +#else +#define CONSTEXPR_IF_NOT_DEBUG constexpr +#define ASSERT_IF_DEBUG(x) +#endif + /** A Span is an object that can refer to a contiguous sequence of objects. * * It implements a subset of C++20's std::span. @@ -37,7 +45,10 @@ public: * which is hard to implement without std::address_of. */ template ::value, int>::type = 0> - constexpr Span(T* begin, T* end) noexcept : m_data(begin), m_size(end - begin) {} + CONSTEXPR_IF_NOT_DEBUG Span(T* begin, T* end) noexcept : m_data(begin), m_size(end - begin) + { + ASSERT_IF_DEBUG(end >= begin); + } /** Implicit conversion of spans between compatible types. * @@ -73,15 +84,42 @@ public: constexpr C* data() const noexcept { return m_data; } constexpr C* begin() const noexcept { return m_data; } constexpr C* end() const noexcept { return m_data + m_size; } - constexpr C& front() const noexcept { return m_data[0]; } - constexpr C& back() const noexcept { return m_data[m_size - 1]; } + CONSTEXPR_IF_NOT_DEBUG C& front() const noexcept + { + ASSERT_IF_DEBUG(size() > 0); + return m_data[0]; + } + CONSTEXPR_IF_NOT_DEBUG C& back() const noexcept + { + ASSERT_IF_DEBUG(size() > 0); + return m_data[m_size - 1]; + } constexpr std::size_t size() const noexcept { return m_size; } - constexpr C& operator[](std::size_t pos) const noexcept { return m_data[pos]; } - - constexpr Span subspan(std::size_t offset) const noexcept { return Span(m_data + offset, m_size - offset); } - constexpr Span subspan(std::size_t offset, std::size_t count) const noexcept { return Span(m_data + offset, count); } - constexpr Span first(std::size_t count) const noexcept { return Span(m_data, count); } - constexpr Span last(std::size_t count) const noexcept { return Span(m_data + m_size - count, count); } + CONSTEXPR_IF_NOT_DEBUG C& operator[](std::size_t pos) const noexcept + { + ASSERT_IF_DEBUG(size() > pos); + return m_data[pos]; + } + CONSTEXPR_IF_NOT_DEBUG Span subspan(std::size_t offset) const noexcept + { + ASSERT_IF_DEBUG(size() >= offset); + return Span(m_data + offset, m_size - offset); + } + CONSTEXPR_IF_NOT_DEBUG Span subspan(std::size_t offset, std::size_t count) const noexcept + { + ASSERT_IF_DEBUG(size() >= offset + count); + return Span(m_data + offset, count); + } + CONSTEXPR_IF_NOT_DEBUG Span first(std::size_t count) const noexcept + { + ASSERT_IF_DEBUG(size() >= count); + return Span(m_data, count); + } + CONSTEXPR_IF_NOT_DEBUG Span last(std::size_t count) const noexcept + { + ASSERT_IF_DEBUG(size() >= count); + return Span(m_data + m_size - count, count); + } friend constexpr bool operator==(const Span& a, const Span& b) noexcept { return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()); } friend constexpr bool operator!=(const Span& a, const Span& b) noexcept { return !(a == b); } @@ -106,7 +144,7 @@ template T& SpanPopBack(Span& span) { size_t size = span.size(); - assert(size > 0); + ASSERT_IF_DEBUG(size > 0); T& back = span[size - 1]; span = Span(span.data(), size - 1); return back; -- cgit v1.2.3