Span improvements #18468

pull sipa wants to merge 5 commits into bitcoin:master from sipa:202003_conv_span changing 6 files +104 −44
  1. sipa commented at 0:51 am on March 30, 2020: member

    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::strings, std::arrays, std::vectors, prevectors, … (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.

  2. DrahtBot added the label Consensus on Mar 30, 2020
  3. DrahtBot added the label Tests on Mar 30, 2020
  4. sipa force-pushed on Mar 30, 2020
  5. sipa force-pushed on Mar 30, 2020
  6. DrahtBot commented at 2:43 am on March 30, 2020: member

    The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

    Conflicts

    No conflicts as of last run.

  7. sipa force-pushed on Mar 30, 2020
  8. sipa force-pushed on Mar 30, 2020
  9. sipa commented at 4:48 am on March 30, 2020: member

    Here is one caveat that may not be obvious: whenever you have some iterator/pointer/object that stores objects of type B (which supertype A), it should not be possible to construct a Span<A> for it, despite B* being implicitly convertible to A*. The reason is that A and B may have different sizes, so pointer arithmetic in one may not correspond to the right operations in the other.

    This is implemented - here and in the C++20 std::span - by checking that arrays of B can be converted to arrays of A.

  10. sipa force-pushed on Mar 30, 2020
  11. sipa force-pushed on Mar 30, 2020
  12. sipa force-pushed on Mar 30, 2020
  13. sipa force-pushed on Mar 30, 2020
  14. in src/span.h:71 in 6bc07845c5 outdated 
    69+     *
70+     * To prevent surprises, this constructor is restricted to const containers. Use MakeSpan to construct
71+     * a span for mutable ones.
72+     */
73+    template <typename V, typename std::enable_if<std::is_convertible<typename std::remove_pointer<decltype(std::declval<const V&>().data())>::type (*)[], C (*)[]>::value && std::is_convertible<decltype(std::declval<const V&>().size()), std::size_t>::value, int>::type = 0>
74+    constexpr Span(const V& v) noexcept : m_data(v.data()), m_size(v.size()) {}
    aminroosta commented at 1:05 pm on April 3, 2020:

    This will cover the generic copy constructor as well, because Span<O> has both .data() & .size() methods.

    0    template <typename O, typename std::enable_if<std::is_convertible<O (*)[], C (*)[]>::value, int>::type = 0>
1    constexpr Span(const Span<O>& other) noexcept : m_data(other.m_data), m_size(other.m_size) {}
    sipa commented at 5:34 am on April 4, 2020:
    That’s true, though the specification and common other span implementations still have a default copy constructor too - I don’t know why.
  15. laanwj referenced this in commit 35ef3c15ef on Apr 30, 2020
  16. sipa force-pushed on May 1, 2020
  17. sipa commented at 6:28 pm on May 1, 2020: member
    Rebased after #18591 (which included a commit from this PR).
  18. jb55 commented at 1:36 am on May 2, 2020: member
    I was trying to MakeSpan on a prevector today and I realized I needed this PR. Concept ACK. will test and ACK soon.
  19. in src/test/fuzz/span.cpp:35 in bc32062d40 outdated 
    31@@ -32,7 +32,7 @@ void test_one_input(const std::vector<uint8_t>& buffer)
32     }
33 
34     std::string another_str = fuzzed_data_provider.ConsumeBytesAsString(32);
35-    const Span<const char> another_span = MakeSpan(another_str);
36+    const Span<const char> another_span{str};
    jb55 commented at 8:10 am on May 2, 2020:

    copy paste typo? shouldn’t this be:

    0    const Span<const char> another_span{another_str};
    sipa commented at 11:44 pm on May 2, 2020:
    Thanks, fixed!
  20. jb55 commented at 8:12 am on May 2, 2020: member

    Seems to be working well on a branch I’m testing. one spooky thing I ran into was:

    0static std::vector<unsigned char> RandomData()
1{
2    uint256 r = InsecureRand256();
3    return std::vector<unsigned char>(r.begin(), r.end());
4}
5
6auto d = MakeSpan(RandomData());
7rb1.insert(d)
8BOOST_CHECK(rb1.contains(d));

     0Running 12 test cases...
 1test/bloom_tests.cpp(519): error: in "bloom_tests/rolling_bloom": check nHits == 6 has failed [3 != 6]
 2
 3*** 1 failure is detected in the test module "Bitcoin Core Test Suite"
 4[201] jb55@monad> ./src/test/test_bitcoin -t bloom_tests                                                                                                                                                     ~/dev/github/bitcoin/bitcoin
 5Running 12 test cases...
 6test/bloom_tests.cpp(519): error: in "bloom_tests/rolling_bloom": check nHits == 6 has failed [3 != 6]
 7
 8*** 1 failure is detected in the test module "Bitcoin Core Test Suite"
 9[201] jb55@monad> ./src/test/test_bitcoin -t bloom_tests                                                                                                                                                     ~/dev/github/bitcoin/bitcoin
10Running 12 test cases...
11test/bloom_tests.cpp(519): error: in "bloom_tests/rolling_bloom": check nHits == 6 has failed [2 != 6]
12
13*** 1 failure is detected in the test module "Bitcoin Core Test Suite"
14[201] jb55@monad> ./src/test/test_bitcoin -t bloom_tests                                                                                                                                                     ~/dev/github/bitcoin/bitcoin
15Running 12 test cases...
16test/bloom_tests.cpp(519): error: in "bloom_tests/rolling_bloom": check nHits == 6 has failed [7 != 6]
17
18*** 1 failure is detected in the test module "Bitcoin Core Test Suite"
19[201] jb55@monad>                                                                                                                                                                                            ~/dev/github/bitcoin/bitcoin
20[201] jb55@monad> ./src/test/test_bitcoin -t bloom_tests                                                                                                                                                     ~/dev/github/bitcoin/bitcoin
21Running 12 test cases...
22test/bloom_tests.cpp(519): error: in "bloom_tests/rolling_bloom": check nHits == 6 has failed [4 != 6]
23
24*** 1 failure is detected in the test module "Bitcoin Core Test Suite"

    but this works fine:

    0std::vector<unsigned char> d = RandomData();
1rb1.insert(MakeSpan(d));
2BOOST_CHECK(rb1.contains(MakeSpan(d)));

    some weird rvalue voodoo going on?

  21. aminroosta commented at 8:53 am on May 2, 2020: none

    I may be wrong, but i think in your first example, the return value of RandomData() is destructed immediately.

    0auto d = MakeSpan(RandomData());
1// d contains dangling pointers by this line.
2rb1.insert(d)
3BOOST_CHECK(rb1.contains(d));

    MakeSpan takes a universal reference (V&&) in this PR.

    because the return value of RandomData() is an Rvalue, it goes out of scope on the first line and therefore is destructed immediately.

  22. jb55 commented at 9:04 am on May 2, 2020: member
    @aminroosta I understand some of those words. thanks!
  23. in src/span.h:109 in bc32062d40 outdated 
    104@@ -73,11 +105,8 @@ class Span
105  *
106  * std::span will have a constructor that implements this functionality directly.
107  */
108-template<typename A, int N>
109-constexpr Span<A> MakeSpan(A (&a)[N]) { return Span<A>(a, N); }
110-
111 template<typename V>
112-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()); }
113+constexpr auto MakeSpan(V&& v) -> Span<typename std::remove_pointer<decltype(v.data())>::type> { return Span<typename std::remove_pointer<decltype(v.data())>::type>(v.data(), v.size()); }
    aminroosta commented at 11:23 am on May 2, 2020:

    @sipa @jb55 I think passing any rvalue/temporary here will result in dangling pointers.

    I did check the docs and the c++ 20 span has a ctor that takes R&& …

    0template <class R>
1constexpr span(R&& r);

    however It says R must model borrowed_range. In other words R must be a non owning view (like basic_string_view, span, ref_view …).

    0The behavior is undefined if R does not actually model contiguous_range and
1sized_range or if R does not model borrowed_range while element_type is non-const.

    0constexpr auto MakeSpan(V& v) -> Span<typename std::remove_pointer<decltype(v.data())>::type> { return Span<typename std::remove_pointer<decltype(v.data())>::type>(v.data(), v.size()); }
    sipa commented at 11:55 pm on May 2, 2020:
    I’ve made some changes, and commented below.
  24. sipa commented at 5:20 pm on May 2, 2020: member
    Yes, exactly what @aminroosta said.
  25. sidhujag referenced this in commit c3bc34f50a on May 2, 2020
  26. sipa force-pushed on May 2, 2020
  27. sipa force-pushed on May 2, 2020
  28. sipa commented at 11:51 pm on May 2, 2020: member

    @jb55 @aminroosta Ok, interesting. I guess the reasoning is that an std::span should really be thought of a a “reference + size” thing. You can’t pass a temporary to a function that takes a non-const lvalue reference (because it would be surprising to make modifications to an input that’s going to be discarded) - similarly you shouldn’t be able to pass a temporary to a function that takes a mutable std::span.

    I’ve made changes to this PR to implement the same behaviour - both in the constructor and in MakeSpan. You can construct mutable Spans from lvalue references, but if you pass in a temporary you can only create immutable Spans.

    None of this really addresses the lifetime issue that @jb55 encountered. If you construct a Span from a temporary, you better make sure the Span doesn’t outlive the object pointed to. This is similar to the follow code, which compiles fine, but is UB:

    0const char& chr = std::string("blup")[0];
1putchar(chr);

    A string is constructed in the first line, and destroyed when the statement ends. This means chr is now a reference to a non-existing object.

    The same thing is possible with Span (and with C++20 std::span, I just checked):

    0std::span<const char> sp{std::string("blup")};
1putchar(sp[0]);
  29. in src/test/fuzz/span.cpp:35 in 88817d05a7 outdated 
    31@@ -32,7 +32,7 @@ void test_one_input(const std::vector<uint8_t>& buffer)
32     }
33 
34     std::string another_str = fuzzed_data_provider.ConsumeBytesAsString(32);
35-    const Span<const char> another_span = MakeSpan(another_str);
36+    const Span<const char> another_span{another_ptr};
    jb55 commented at 5:13 pm on May 3, 2020: 
    0    const Span<const char> another_span{another_str};

    :sweat_smile:

  30. jb55 commented at 5:13 pm on May 3, 2020: member

    None of this really addresses the lifetime issue that @jb55 encountered

    and this is completely fine of course, I’m not expecting any more from the language than what makes sense.

  31. promag commented at 10:20 pm on May 3, 2020: member
    Concept ACK. I’m curious why span constructors aren’t declared explicit - I’m aware std::span doesn’t have them - since this is the project implementation and “should” follow #11112.
  32. sipa commented at 10:39 pm on May 3, 2020: member
    @promag That would partially defeat the purpose, in my view. With std::span/Span, the point is that you can write a single function that accepts a span as input, and it will automatically work with whatever continuous container you pass it. This is safe as spans are restricted in features to be a strict subset of those containers.
  33. promag commented at 10:46 pm on May 3, 2020: member
    @sipa right, I see you have edited your comment. Don’t get me wrong, I like/prefer this way.
  34. sipa force-pushed on May 5, 2020
  35. sipa force-pushed on May 5, 2020
  36. sipa commented at 6:42 pm on May 5, 2020: member
    I added a workaround that seems necessary on CentOS 7 (GCC 4.8.5). It seems that when both a function template<typename T> F(T&) and template<typename T> F(T&&) are present, passing an lvalue rerence is treated as ambiguous there (other compilers correctly prefer the explicitly lvalue reference first version over the universal reference in the second).
  37. sipa force-pushed on May 5, 2020
  38. DrahtBot added the label Needs rebase on May 11, 2020
  39. Make Span size type unsigned 
    This matches a change in the C++20 std::span proposal.
    1f790a1147
  40. Make pointer-based Span construction safer 
    This prevents constructing a Span<A> given two pointers into an array
of B (where B is a subclass of A), at least without explicit cast to
pointers to A.
    bb3d38fc06
  41. Add Span constructors for arrays and vectors ab303a16d1
  42. Simplify usage of Span in several places 2676aeadfa
  43. sipa force-pushed on May 12, 2020
  44. DrahtBot removed the label Needs rebase on May 12, 2020
  45. jb55 commented at 1:29 am on May 16, 2020: member 
     0-----BEGIN OPENTIMESTAMPS MESSAGE-----
 1
 2- -----BEGIN PGP SIGNED MESSAGE-----
 3Hash: SHA256
 4
 5Tested ACK 1f790a1147ad9a5fe06987d84b6cd71f91cbec4b 
 6- -----BEGIN PGP SIGNATURE-----
 7
 8iHUEARYIAB0WIQTgLT/U60WFpjUxwdDhv8uQof96HAUCXr8/HwAKCRDhv8uQof96
 9HHdWAP4oLAWAFyl89rmXCkOLhabnQH0eA1WuQLms9sGQ/0ZuIAEA95NqgBdDXeNy
10LNZONShuQyUhND7sV3DFtdnwlMdwRAM=
11=eezA
12- -----END PGP SIGNATURE-----
13
14-----BEGIN OPENTIMESTAMPS PROOF-----
15
16AE9wZW5UaW1lc3RhbXBzAABQcm9vZgC/ieLohOiSlAEI0+kRFDp/91K3axlWimkSIh1Ka2PWppGJ
17YtXOXy0HOKPwEIew6IYLhpu8/iYXzfmu8MQI//AQCDnqvzdSHC6NHfUc3YlXSAjxBF6/PznwCGCt
18odmwhfKvAIPf4w0u+QyOIyJodHRwczovL2J0Yy5jYWxlbmRhci5jYXRhbGxheHkuY29t//AQJIfp
19Xbaf4HUvxkjGLaBeyQjxIK2eTRPWo7iFMz9KJAhAEQj++q+aDKHrMrU2g1OTU56WCPEEXr8/OPAI
203EyoLhEfdiQAg9/jDS75DI4sK2h0dHBzOi8vYm9iLmJ0Yy5jYWxlbmRhci5vcGVudGltZXN0YW1w
21cy5vcmfwEPLW6m0gMqdiEIgYvoB9QnYI8CA+Yd5Y9xkgXBCvNi5d4UBONxjC+nGVWiUTf+sCVk4O
22mAjxBF6/PznwCCCCbb6MkeJlAIPf4w0u+QyOKShodHRwczovL2Zpbm5leS5jYWxlbmRhci5ldGVy
23bml0eXdhbGwuY29t
24-----END OPENTIMESTAMPS PROOF-----

    otsclear xclip -o | otsclear -v | gpg --verify

  46. fanquake commented at 1:44 am on May 16, 2020: member
    @jb55 Which key did you use to sign this? I’m seeing E02D3FD4EB4585A63531C1D0E1BFCB90A1FF7A1C which doesn’t seem to match the one I have for you 1514A56A573AADFCA0EBFF908FB01059E7960F33 (from your website).
  47. jb55 commented at 1:51 am on May 16, 2020: member
    thanks for verifying :) @fanquake https://jb55.com/s/8f099795a120ae13.txt
  48. in src/script/descriptor.cpp:1101 in 2676aeadfa outdated 
    1097@@ -1098,7 +1098,7 @@ std::string GetDescriptorChecksum(const std::string& descriptor)
1098 {
1099     std::string ret;
1100     std::string error;
1101-    Span<const char> sp(descriptor.data(), descriptor.size());
1102+    Span<const char> sp{descriptor};
    Empact commented at 5:07 am on May 16, 2020:
    nit: could pass descriptor directly to CheckChecksum
    sipa commented at 8:48 pm on May 27, 2020:
    That doesn’t work; CheckChecksum needs a reference to a mutable Span<const char> (it’s an input/output argument). You can’t bind a temporary to that.
  49. in src/span.h:40 in 2676aeadfa outdated 
    38+     *
39+     * This implements a subset of the iterator-based std::span constructor in C++20,
40+     * which is hard to implement without std::address_of.
41+     */
42+    template <typename T, typename std::enable_if<std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0>
43+    constexpr Span(T* begin, T* end) noexcept : m_data(begin), m_size(end - begin) {}
    Empact commented at 5:15 am on May 16, 2020:
    nit: should we assert or otherwise check against end < data here?
    sipa commented at 8:28 pm on May 27, 2020:
    I’d rather not. This is an extremely lightweight object, so adding any kind of runtime checking may have significant performance impact.
    laanwj commented at 4:47 pm on June 4, 2020:
    You could add the check only if #ifdef DEBUG. Then at least these kind of out of bounds issues will be flagged in debug builds. No strong opinion though.
    sipa commented at 6:44 pm on June 4, 2020:
    Good idea, done.
  50. laanwj added this to the "Blockers" column in a project
  51. MarcoFalke removed the label Tests on May 29, 2020
  52. MarcoFalke added the label Refactoring on May 31, 2020
  53. MarcoFalke removed the label Consensus on May 31, 2020
  54. laanwj commented at 4:48 pm on June 4, 2020: member
    Code review ACK 2676aeadfa0e43dcaaccc4720623cdfe0beed528 Code review ACK 26acc8dd9b512f220c1facdba2c5de7976d3c258
  55. sipa commented at 6:06 pm on June 4, 2020: member
    Added a commit that adds a bunch of asserts that are enabled on -DDEBUG.
  57. practicalswift commented at 7:33 am on June 5, 2020: contributor
    Concept ACK
  58. in src/span.h:16 in 3d9ef83776 outdated 
     9@@ -10,6 +10,12 @@
10 #include <algorithm>
11 #include <assert.h>
12 
13+#ifdef DEBUG
14+#define CONSTEXPR_IF_NOT_DEBUG
15+#else
    promag commented at 9:20 pm on June 11, 2020:

    3d9ef83776f831a1f077674c16807391ec5f5d57

    #define ASSERT_IF_DEBUG ?

    sipa commented at 10:13 pm on June 17, 2020:
    Good idea, done!
  59. promag commented at 9:45 pm on June 11, 2020: member
    Code review ACK 3d9ef83776f831a1f077674c16807391ec5f5d57.
  60. Add sanity check asserts to span when -DDEBUG 26acc8dd9b
  61. sipa force-pushed on Jun 17, 2020
  62. promag commented at 11:20 pm on June 17, 2020: member

    Code review ACK 26acc8dd9b512f220c1facdba2c5de7976d3c258.

    Only changes are the new macro ASSERT_IF_DEBUG and replaced assert with ASSERT_IF_DEBUG (good catch).

  63. laanwj removed this from the "Blockers" column in a project
  64. laanwj merged this on Jun 18, 2020
  65. laanwj closed this on Jun 18, 2020
  66. in src/span.h:72 in 26acc8dd9b 
    66@@ -42,18 +67,59 @@ class Span
67     /** Default assignment operator. */
68     Span& operator=(const Span& other) noexcept = default;
69 
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) {}
    theuni commented at 6:54 pm on June 19, 2020:

    Could you help me understand the lifetime of a temporary here? It seems like you’d want this to be lvalue only. For example, this works and passes undefined/memory sanitizer checks, but I don’t understand why:

    0Span<const char> foo("bar");
1printf("foo: %s\n", foo.data());

    I would have expected the lifetime of the literal to end after the constructor, but the memory appears to remain valid afterwards.

    sipa commented at 7:01 pm on June 19, 2020:

    That’s a good question, but not the right example. String literals have static lifetime in C++, so in this specific case there is no problem.

    However, there are pitfalls around constructing a Span from a temporary, see #18468 (comment) for more discussion. It’s an inherent problem with objects that store references unfortunately, and present in std::span as well.

    sipa commented at 2:10 am on June 24, 2020:
    Follow-up: https://github.com/bitcoin/bitcoin/pull/19367
  67. in src/script/interpreter.cpp:1525 in 26acc8dd9b 
    1521@@ -1522,7 +1522,7 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
1522 static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
1523 {
1524     CScript scriptPubKey;
1525-    Span<const valtype> stack = MakeSpan(witness.stack);
1526+    Span<const valtype> stack{witness.stack};
    rajarshimaitra commented at 2:50 pm on June 22, 2020:
    Which modification in span.h exactly is allowing us to use list initialization?
    sipa commented at 2:16 am on June 24, 2020:

    This is not list initialization, but value initialization (see https://en.cppreference.com/w/cpp/language/value_initialization). In short, Type{arg1, arg2} is the preferred way in >=C++11 to invoke a type’s constructor.

    In this case, it’s effectively calling Span<const valtype>(witness.stack).

  68. in src/span.h:19 in 26acc8dd9b 
    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
    rajarshimaitra commented at 2:50 pm on June 22, 2020:
    This seemed fairly new to me. Here’s what I understood so far. Depending upon the context (weather DEBUG or not) we want to evaluate some of the methods differently. In non-debug mode we want them to be constexpr whereas in debug mode we want them to evaluate at run time. Thus we are defining some debug specific declaration here. Is that correct understanding, and can you add if there’s something more to it?
    sipa commented at 2:21 am on June 24, 2020:

    Note that constexpr for a function does not mean that the function will necessarily always be (entirely) evaluated at compile time; only that at least for some inputs, parts of the function can be evaluated at compile time (C++20 adds a consteval keyword for things that are guaranteed to be evaluated at compile time).

    The problem is that (in C++11) we can’t mark functions constexpr if they contain an assert(), as such functions are restricted to consisting of a single return statement. So we’re forced to make the constexpr keyword condition on not being in DEBUG mode.

  69. in src/span.h:78 in 26acc8dd9b 
    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.
    rajarshimaitra commented at 2:53 pm on June 22, 2020:
    Can you elaborate a little more on this specific restriction? I read your comment on #18648(comment) but was wondering what if we want to cast a span from an rvalue reference then modify its values for whatever reason? Is it something not possible or an inherently stupid thing to do?
    sipa commented at 2:23 am on June 24, 2020:

    I’ve documented this here: https://github.com/bitcoin/bitcoin/pull/19367/files#diff-9f772f6f8808fe74c65228b3a74a07c2R62-R79

    Does that explain?

  70. in src/span.h:140 in 26acc8dd9b 
    148+/** MakeSpan for arrays: */
149+template <typename A, int N> Span<A> constexpr MakeSpan(A (&a)[N]) { return Span<A>(a, N); }
150+/** MakeSpan for temporaries / rvalue references, only supporting const output. */
151+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); }
152+/** MakeSpan for (lvalue) references, supporting mutable output. */
153+template <typename V> constexpr auto MakeSpan(V& v) -> Span<typename std::remove_pointer<decltype(v.data())>::type> { return v; }
    rajarshimaitra commented at 3:00 pm on June 22, 2020:
    Can you explain why we are not returning Span<V>(v.data(), v.size()) or something like that here? More precisely, I am confused about how V v value is being automatically cast into a span?
    sipa commented at 2:29 am on June 24, 2020:

    It’s converting the argument to the return type, so this is effectively evaluating Span<typename std::remove_pointer<decltype(v.data())>::type>(v). As Span has a constructor for converting from any data type that exposes a proper size() and data() member function (the range-like object constructor), so that’s what is invoked here.

    The reason for not calling the pointer/size constructor instead (which could have been written as return {v.data(), v.size()}; btw), is that this would potentially bypass the protections that are already implemented for the range-like object constructor.

    MakeSpan’s only purpose is automatic inference of a Span’s type to construct, this way of implementing things guarantees it is not doing anything more than that (it doesn’t change what can be constructed; it only lets you write MakeSpan(...) instead of Span<...>(...)).

  71. in src/span.h:18 in 26acc8dd9b 
     9@@ -10,6 +10,14 @@
10 #include <algorithm>
11 #include <assert.h>
12 
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)
    rajarshimaitra commented at 3:10 pm on June 22, 2020:
    Why don’t we want assertions to happen in non-debug mode?
    sipa commented at 2:32 am on June 24, 2020:

    Performance.

    Span is an extreme lightweight object, which I imagine we’ll use in very tight loops or other performance critical situations. In normal production code these asserts would be an unreasonable burden. But at the same time, it’s nice to be able to verify in tests that these properties hold, so they’re enabled in DEBUG mode.

  72. in src/span.h:40 in 26acc8dd9b 
    38+     *
39+     * This implements a subset of the iterator-based std::span constructor in C++20,
40+     * which is hard to implement without std::address_of.
41+     */
42+    template <typename T, typename std::enable_if<std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0>
43+    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
    rajarshimaitra commented at 3:18 pm on June 22, 2020:
    This was wild learning curve. If I try to translate this in English it sounds like: If a T type pointer array is convertible into a C type pointer array, then only use this constructor. Does that sound correct? Then my question is if I pass in the T at the time of construction, how does the compiler know about the C in order to evaluate the above statement?
    sipa commented at 2:37 am on June 24, 2020:

    At least in C++11, because you’re telling it what C is, perhaps without knowing it.

    You could invoke this constructor like this:

    0int arr[5] = {1, 2, 3, 4, 5};
1Span<const int> sp{&arr[1], 3};

    Which is actually a conversion, as &arr[1] has type T=int, but C=const int.

    In other contexts, C may be set implicitly. For example:

    0void Foo(Span<const int> arg);
1...
2int arr[5] = {1, 2, 3, 4, 5};
3Foo({&arr[1], 3});

    where C is again const int, but it’s implied by the argument type of the called function.

  73. rajarshimaitra commented at 6:35 am on June 23, 2020: contributor

    Customary Concept ACK. I am no way qualified enough to critique this PR. But as it is merged and is an upcoming review club topic, I guess it’s ok to ask my noob questions here for educational purposes.

    Compiled without issue, All tests passing. Performed fuzzing of span and spanparser untill no new coverage path in 6 hours. No bugs reported.

    The following are some basic questions I had while reviewing the PR.

  74. sipa commented at 2:11 am on June 24, 2020: member
    @jb55 @theuni I’ve opened #19367 to document some of the pitfalls you mentioned in comments above.
  75. fjahr commented at 11:11 am on June 24, 2020: member
    post-merge code review ACK
  76. in src/span.h:97 in 26acc8dd9b 
    101+    CONSTEXPR_IF_NOT_DEBUG C& back() const noexcept
102+    {
103+        ASSERT_IF_DEBUG(size() > 0);
104+        return m_data[m_size - 1];
105+    }
106+    constexpr std::size_t size() const noexcept { return m_size; }
  77. in src/span.h:68 in 26acc8dd9b 
    66@@ -42,18 +67,59 @@ class Span
67     /** Default assignment operator. */
68     Span& operator=(const Span& other) noexcept = default;
    jnewbery commented at 4:09 pm on June 24, 2020:

    I’m pretty sure that these default declarations are unnecessary, since they’ll be generated by default anyway.

    The only place I’m aware of needing to declare default ctors/assignment operators is when you’re using a unique_ptr for an incomplete type, and you need to declare them in the header file and define them (as default) in the implementation file (eg when using a unique_ptr for a pimpl).

    They may be other situations where declaring default ctors/assiment operators is necessary, but I don’t think this is one of them.

    jonatack commented at 3:42 pm on June 25, 2020:

    I’m pretty sure that these default declarations are unnecessary, since they’ll be generated by default anyway.

    Built, tested, and fuzzed this PR and #19326 with the default copy constructor and assignment operator in span.h both removed and yes, AFAICT it seems fine.

    theuni commented at 4:01 pm on June 25, 2020:

    I believe the default declarations aren’t actually a no-op here and may be considered harmful as default move ctor/assignment is disabled when a copy/assignment oper are provided.

    See here under Implicitly-declared move constructor for reference. From a quick local test, it seems that even declaring a = default constructor/assignment operator is enough to disable the implicit moves. Please correct me if I’m wrong on that, though!

    So as a side-effect, removing these (thus implicitly creating the move ctor) is enough to eliminate the lifetimebound false-positives reported here.

    +1 for removing them unless there was a reason for disabling those moves.

    jnewbery commented at 4:15 pm on June 25, 2020:

    it seems that even declaring a = default constructor/assignment operator is enough to disable the implicit moves.

    Fascinating! I didn’t know that.

    +1 for removing them unless there was a reason for disabling those moves.

    If this is the case, presumably it’d be better to explicitly delete those move ctor/assigments than rely on this behavior.

    theuni commented at 4:24 pm on June 25, 2020:

    it seems that even declaring a = default constructor/assignment operator is enough to disable the implicit moves.

    Fascinating! I didn’t know that.

    Please double-check me on this! I’m assuming that based on my testing with lifetimebound, but I haven’t managed to track down a definitive answer.

  78. theuni commented at 5:05 pm on June 24, 2020: member

    Continuing the discussion from here: https://github.com/bitcoin/bitcoin/pull/19367/files#r445025361 because I don’t know where else to stick it.

    I believe that adding clang’s lifetimebound attribute points out a valid issue here:

    0util/spanparsing.cpp:46:28: warning: temporary whose address is used as value of local variable 'ret' will be destroyed at the end of the full-expression [-Wdangling]
1    Span<const char> ret = sp.first(it - sp.begin());

    Expr’s return value depends on the span that was passed in (sp), which may have been a temporary. In that case, I believe the span that’s returned is now referencing invalid memory.

    Edit: On second thought, I suppose that’s somewhat obvious behavior here and not really a bug. It would be really easy to miss in review, though :(

    Edit2: It does point out a dangerous pattern, though: I think any function which returns a span as a result of modifying a different input span is potentially susceptible to this issue?

  79. jnewbery commented at 6:21 pm on June 24, 2020: member
    Should any function that returns a subspan of the passed-in span be declared with non-const argument? Would that prevent temporaries from being passed in? Or is there a better way to do that?
  80. practicalswift commented at 9:57 pm on June 24, 2020: contributor

    @theuni

    It would be really easy to miss in review, though :(

    Agreed! It is very easy to get things wrong when reasoning about lifetime issues. This is really subtle topic filled with gotchas.

    The introduction of std::span and std::string_view will bring a new golden age of use-after-frees/returns to C++ :)

    Personally I’m not convinced that it is a good idea to use std::span or std::string_view as anything other than parameter types in the general case (there are exceptions obviously, but the security/stability vs performance trade-off should be considered in such cases).

    As a rule of thumb: if the median reviewer has to think more than five seconds to answer “no” to the question “might there be a life-time issue hiding in this use of std::{span,string_view}?” then it is likely not a good idea to use them :)

    Somewhat related: “std::string_view encourages use-after-free; the Core Guidelines Checker doesn’t complain”

  81. jonatack commented at 4:09 pm on June 25, 2020: member

    Thanks @sipa, this PR led me to learn more about Span and C++20 std::span via these resources, among the online ones:

    1. C++ std:span: https://en.cppreference.com/w/cpp/container/span

    2. Yesterday’s Review Club notes/questions/meeting log: https://bitcoincore.reviews/18468

    3. The C++ Core Guidelines site seems to be a source of interesting recommendations on when, why, and how to use std::span: https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines. It suggests using std::span in a fair number of places/reasons, among others:

    • expressing intent
    • improved code readability and tool support
    • avoiding range errors and array decay to a pointer (losing its size, opening the opportunity for range errors; using span preserves size information)
    • going further, avoiding passing arrays as a single pointer, as (pointer, size)-style interfaces are error-prone and a plain pointer (to array) must rely on some convention to allow the callee to determine the size
    • potentially doing more at compile time vs run time
    • potentially checking/catching run time errors earlier in the code
    • abstraction for encapsulating messy constructs, rather than spreading them throughout the code
    • reducing the number of function arguments, e.g. from pointer + size to a bounds-checked span representing a range
    • span<T> or a span_p<T> ideal for designating half-open sequences, as informal/non-explicit ranges are a source of errors
    • helpful for using abstract classes as interfaces when complete separation of interface and implementation is needed

    This PR debug-builds cleanly with gcc and clang, and the fuzzers build and run.

    ACK 26acc8dd9b512f220c1facdba2c5de7976d3c258 (AFAICT), modulo the various follow-ups suggested above.

  82. jonatack commented at 4:37 pm on June 25, 2020: member

    MakeSpan takes a universal reference (V&&) in this PR. @aminroosta Thank you – I found your link (and the downloadable presentation slides) really informative.

  83. laanwj referenced this in commit fb87f6d168 on Jun 29, 2020
  84. sidhujag referenced this in commit fe4d13dfc7 on Jul 7, 2020
  85. laanwj referenced this in commit 34eb236258 on Aug 3, 2020
  86. sidhujag referenced this in commit 49ec455bbf on Aug 4, 2020
  87. Fabcien referenced this in commit 6588bd8ef0 on Feb 2, 2021
  88. kittywhiskers referenced this in commit 8a9ddf632f on Mar 10, 2021
  89. kittywhiskers referenced this in commit de92bf69ae on Mar 10, 2021
  90. kittywhiskers referenced this in commit 109cda6f36 on Mar 10, 2021
  91. kittywhiskers referenced this in commit fee97e6668 on Mar 10, 2021
  92. kittywhiskers referenced this in commit c8642a4d3a on Mar 23, 2021
  93. kittywhiskers referenced this in commit 8f2ad9fccc on Mar 23, 2021
  94. kittywhiskers referenced this in commit 4a38f734e1 on Mar 23, 2021
  95. kittywhiskers referenced this in commit 602d18c4d9 on Mar 23, 2021
  96. kittywhiskers referenced this in commit d0c12147a8 on Mar 23, 2021
  97. kittywhiskers referenced this in commit 08fb58aa43 on Mar 23, 2021
  98. kittywhiskers referenced this in commit 077c56dcf4 on Mar 23, 2021
  99. kittywhiskers referenced this in commit 6066590bba on Mar 23, 2021
  100. kittywhiskers referenced this in commit c3f29f09db on Apr 18, 2021
  101. kittywhiskers referenced this in commit ec2eec0ccd on Apr 23, 2021
  102. UdjinM6 referenced this in commit bf01ed7881 on Apr 27, 2021
  103. random-zebra referenced this in commit 56f10aaa51 on Jul 21, 2021
  104. random-zebra referenced this in commit b4751e10ce on Aug 11, 2021
  105. DrahtBot locked this on Feb 15, 2022


sipa DrahtBot aminroosta jb55 promag fanquake Empact laanwj practicalswift theuni rajarshimaitra fjahr jnewbery jonatack

Labels
Refactoring

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-11-17 09:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me