tests: Make descriptor tests deterministic

davereikher commented at 12:05 pm on August 8, 2019: contributor

This is an improvement to a test, inspired by #14343 - removing non determinism from a test.

The test descriptor_test is non-deterministic, as it relies on the MaybeUseHInsteadOfApostrophy function which randomly either swaps all apostrophes with ‘h’ or doesn’t at all in a descriptor. This fix makes both cases always run, if an apostrophe is found in a test descriptor. This does not reduce test coverage but removes the non-determinism.

Additionally, the MaybeUseHInsteadOfApostrophy function removed the checksum if found at the end of a descriptor when the apostrophes are swapped by ‘h’s, since after being swapped the checksum is no longer correct. I instead added re-calculation of the checksum using the DescriptorChecksum function, which adds coverage for the case of a descriptors having ‘h’s instead of apostrophes and a checksum. This was previously lacking. To achieve this I had to move DescriptorChecksum and PolyMod out of the anonymous namespace in descriptor.cpp to make DescriptorChecksum accessible in descriptor_tests.cpp.

All tests complete successfully (functional as well as unit tests).

fanquake added the label Descriptors on Aug 8, 2019

fanquake added the label Tests on Aug 8, 2019

fanquake requested review from achow101 on Aug 8, 2019

fanquake requested review from meshcollider on Aug 8, 2019

davereikher commented at 12:37 pm on August 8, 2019: contributor

Woops, lint failed.. Is there an easy way to reproduce a Travis job locally? I’m a newb to Travis. I tried following https://stackoverflow.com/questions/21053657/how-to-run-travis-ci-locally/49019950 but I don’t understand the instance field that is displayed in the Travis build logs (there is more than one instance there?)

fanquake commented at 12:41 pm on August 8, 2019: member

@davereikher The linter is just complaining about trailing whitespace:

 0This diff appears to have added new lines with trailing whitespace.
 1
 2The following changes were suspected:
 3
 4diff --git a/src/test/descriptor_tests.cpp b/src/test/descriptor_tests.cpp
 5
 6@@ -55,0 +63 @@ std::string MaybeUseHInsteadOfApostrophy(std::string ret)
 7
 8+
 9
10@@ -61 +69,2 @@ const std::set<std::vector<uint32_t>> ONLY_EMPTY{{}};
11
12+void DoCheck(const std::string& prv, const std::string& pub, int flags, const std::vector<std::vector<std::string>>& scripts, const std::set<std::vector<uint32_t>>& paths = ONLY_EMPTY,
13
14^---- failure generated from test/lint/lint-whitespace.sh

You should be able to run the test/lint/lint-whitespace.sh script (as well as the other linters) locally.

DrahtBot commented at 12:52 pm on August 8, 2019: member

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

Conflicts

No conflicts as of last run.

davereikher commented at 12:54 pm on August 8, 2019: contributor

The test/lint/lint-whitespace.sh script finishes without errors locally. I would like to reproduce the Travis environment to avoid fixing and pushing multiple times. If not, I can just remove the trailing whitespace and try again.

in src/script/descriptor.cpp:116 in f86cf3ab9b outdated

108@@ -137,6 +109,36 @@ std::string DescriptorChecksum(const Span<const char>& span)
109     return ret;
110 }
111 
112+
113+namespace {
114+
115+////////////////////////////////////////////////////////////////////////////
116+// Checksum                                                               //

achow101 commented at 6:06 pm on August 8, 2019:

This comment shouldn’t be moved.

davereikher commented at 9:24 am on August 9, 2019:

I’m not sure I understand. It’s not quite clear in the diff, but the // Checksum comment was not moved. It remains after namespace {. The only comment that was moved is the one above PolyMod, describing the operation of that function, along with the function.

MarcoFalke commented at 12:16 pm on August 9, 2019:

In other words: The function does not need to move, only the namespace {

davereikher commented at 1:24 pm on August 9, 2019:

Thanks, fixed in commit 6819fbd741891081b2679e4b763bb88dc997ffe7. Is there a way to re-run AppVeyor? Looks like it timed out.

MarcoFalke commented at 1:31 pm on August 9, 2019:

You can re-run the ci by squashing your commits according to https://github.com/bitcoin/bitcoin/blob/master/CONTRIBUTING.md#squashing-commits

davereikher commented at 3:05 pm on August 9, 2019:

Ok, done in commit 0fc46f5b9262f016c42d2abe68d5125833f55416.

in src/test/descriptor_tests.cpp:34 in f86cf3ab9b outdated

30@@ -28,6 +31,8 @@ constexpr int HARDENED = 2; // Derivation needs access to private keys
31 constexpr int UNSOLVABLE = 4; // This descriptor is not expected to be solvable
32 constexpr int SIGNABLE = 8; // We can sign with this descriptor (this is not true when actual BIP32 derivation is used, as that's not integrated in our signing code)
33 
34+

achow101 commented at 6:06 pm on August 8, 2019:

Unnecessary whitespace change.

davereikher commented at 10:44 am on August 9, 2019:

Thanks, fixed in commit d3e2d08a3be92cecb50c89c69871e61e0618e10b.

in src/test/descriptor_tests.cpp:75 in f86cf3ab9b outdated

84+    std::unique_ptr<Descriptor> parse_priv;
85+    std::unique_ptr<Descriptor> parse_pub;
86     // Check that parsing succeeds.
87-    auto parse_priv = Parse(MaybeUseHInsteadOfApostrophy(prv), keys_priv);
88-    auto parse_pub = Parse(MaybeUseHInsteadOfApostrophy(pub), keys_pub);
89+    if (replace_apostrophe_with_h)

achow101 commented at 6:14 pm on August 8, 2019:

I think it would make more sense to largely leave this function untouched and instead do the ' to h change in your new Check function below. The only change here would be to remove MaybeUseHInsteadOfApostrophy

davereikher commented at 9:55 am on August 9, 2019:

I agree and I did it that way initially but then, for example, this check failed:

0std::string pub1 = parse_priv->ToString();
1BOOST_CHECK(EqualDescriptor(pub, pub1));

since Descriptor::ToString returns a descriptor formatted with ', while pub has h, if I do it the way you suggest. I had to work around this by passing pub and prv without modification and introducing a boolean argument of whether to swap ' with h only when passing them to the Parse function.

achow101 commented at 6:17 pm on August 8, 2019: member

Concept ACK. I’ve left a few comments.

I think it makes sense to test the parsing of both the ' and h key origin forms for all descriptors.

davereikher force-pushed on Aug 9, 2019

in src/test/descriptor_tests.cpp:74 in 0fc46f5b92 outdated

90+        parse_pub = Parse(pub, keys_pub);
91+    }
92+    else
93+    {
94+        parse_priv = Parse(UseHInsteadOfApostrophe(prv), keys_priv);
95+        parse_pub = Parse(UseHInsteadOfApostrophe(pub), keys_pub);

achow101 commented at 5:18 pm on August 9, 2019:

This is actually backwards. When replace_apostrophe_with_h is false, we’re swapping. I think it’s supposed to be the other way around.

davereikher commented at 6:16 am on August 10, 2019:

Thanks, you’re absolutely right. Fixed in a8f49b7d53d33aeba8bd0965c21878795b36f99b.

in src/test/descriptor_tests.cpp:52 in 0fc46f5b92 outdated

56-                break;
57+    while (true) {
58+        auto it = ret.find("'");
59+        if (it != std::string::npos) {
60+            ret[it] = 'h';
61+            if (ret.size() > 9 && ret[ret.size() - 9] == '#') {

meshcollider commented at 2:38 am on August 10, 2019:

This will recalculate the checksum after every replacement, it would be better to just recalculate it at the end

davereikher commented at 6:15 am on August 10, 2019:

Thanks! Fixed in 9f9afcf1355e48d2b39ad9119415d658f5770ec5.

meshcollider commented at 2:38 am on August 10, 2019: contributor

Concept ACK

in src/test/descriptor_tests.cpp:43 in 9f9afcf135 outdated

42@@ -40,32 +43,49 @@ bool EqualDescriptor(std::string a, std::string b)
43     return a == b;
44 }
45 
46-std::string MaybeUseHInsteadOfApostrophy(std::string ret)
47+std::string UseHInsteadOfApostrophe(std::string ret)

promag commented at 9:54 am on August 10, 2019:

nit, static function.

davereikher commented at 10:29 am on August 10, 2019:

It’s in an anonymous namespace, or am I missing something?

promag commented at 0:11 am on August 16, 2019:

True, sorry.

promag commented at 0:13 am on August 16, 2019:

But make it std::string UseHInsteadOfApostrophe(const std::string& ret). ~~Also could avoid ret argument, sounds like it’s an output/return argument.~~ (rename is unrelated here).

davereikher commented at 11:44 am on August 16, 2019:

I believe that this line would fail should ret be made a const reference: https://github.com/bitcoin/bitcoin/blob/0b90954416767f6213094f1f282e708c3e8a710b/src/test/descriptor_tests.cpp#L50 I guess I could change the signature to what you suggest and then assign ret to a local variable. Then there would still be a single copy operation so it’s not less efficient or anything, but that would introduce an extra line of code. Do you think I should do it? I agree that ret is not an indicative name. I think desc is better?

in src/test/descriptor_tests.cpp:15 in 9f9afcf135 outdated

10@@ -11,6 +11,9 @@
11 #include <script/descriptor.h>
12 #include <util/strencodings.h>
13 
14+
15+std::string DescriptorChecksum(const Span<const char>& span);

promag commented at 9:55 am on August 10, 2019:

IMO it would be fine to declare in src/script/descriptor.h

davereikher commented at 10:59 am on August 10, 2019:

Done in commit 07c079a2fb49dca58a1d7e5e185a1cbc430381df.

in src/test/descriptor_tests.cpp:51 in 9f9afcf135 outdated

56-                break;
57-            }
58+    bool ret_changed = false;
59+    while (true) {
60+        auto it = ret.find("'");
61+        if (it != std::string::npos) {

promag commented at 9:57 am on August 10, 2019:

nit, if (it == std::string::npos) break;

davereikher commented at 10:59 am on August 10, 2019:

Done in commit 07c079a2fb49dca58a1d7e5e185a1cbc430381df.

in src/test/descriptor_tests.cpp:193 in 9f9afcf135 outdated

188+{
189+    DoCheck(prv, pub, flags, scripts, paths); // Check original (with apostrophes)
190+
191+    if ((prv.find("'") != std::string::npos) || (pub.find("'") != std::string::npos))
192+    {
193+        DoCheck(prv, pub, flags, scripts, paths, true); // Check with apostrophes replaced by 'h'

promag commented at 9:58 am on August 10, 2019:

Add a comment like /* replace_apostrophe_with_h = */ true instead.

davereikher commented at 11:04 am on August 10, 2019:

Done in commit 07c079a.

in src/test/descriptor_tests.cpp:191 in 9f9afcf135 outdated

183@@ -164,6 +184,16 @@ void Check(const std::string& prv, const std::string& pub, int flags, const std:
184     BOOST_CHECK_MESSAGE(left_paths.empty(), "Not all expected key paths found: " + prv);
185 }
186 
187+void Check(const std::string& prv, const std::string& pub, int flags, const std::vector<std::vector<std::string>>& scripts, const std::set<std::vector<uint32_t>>& paths = ONLY_EMPTY)
188+{
189+    DoCheck(prv, pub, flags, scripts, paths); // Check original (with apostrophes)
190+
191+    if ((prv.find("'") != std::string::npos) || (pub.find("'") != std::string::npos))

promag commented at 9:59 am on August 10, 2019:

Use std::string::find(char, ...) like find('\'').

nit, { here.

nit, remove unnecessary ( ).

davereikher commented at 11:03 am on August 10, 2019:

Done in commit 07c079a2fb49dca58a1d7e5e185a1cbc430381df. Also, applied the same change (find("'")->find('\'')) here:https://github.com/bitcoin/bitcoin/blob/07c079a2fb49dca58a1d7e5e185a1cbc430381df/src/test/descriptor_tests.cpp#L47

in src/test/descriptor_tests.cpp:79 in 9f9afcf135 outdated

90-    auto parse_pub = Parse(MaybeUseHInsteadOfApostrophy(pub), keys_pub);
91+    if (replace_apostrophe_with_h)
92+    {
93+        parse_priv = Parse(UseHInsteadOfApostrophe(prv), keys_priv);
94+        parse_pub = Parse(UseHInsteadOfApostrophe(pub), keys_pub);
95+    }

promag commented at 9:59 am on August 10, 2019:

nit } else {

davereikher commented at 10:59 am on August 10, 2019:

Done in commit 07c079a2fb49dca58a1d7e5e185a1cbc430381df.

in src/test/descriptor_tests.cpp:78 in 9f9afcf135 outdated

86+    std::unique_ptr<Descriptor> parse_priv;
87+    std::unique_ptr<Descriptor> parse_pub;
88     // Check that parsing succeeds.
89-    auto parse_priv = Parse(MaybeUseHInsteadOfApostrophy(prv), keys_priv);
90-    auto parse_pub = Parse(MaybeUseHInsteadOfApostrophy(pub), keys_pub);
91+    if (replace_apostrophe_with_h)

promag commented at 9:59 am on August 10, 2019:

nit, { here

davereikher commented at 10:59 am on August 10, 2019:

Done in commit 07c079a2fb49dca58a1d7e5e185a1cbc430381df.

promag commented at 10:02 am on August 10, 2019: member

Concept ACK.

PolyMod linkage changed, make it static?

davereikher commented at 11:06 am on August 10, 2019: contributor

Concept ACK.

PolyMod linkage changed, make it static?

Thanks! Done in commit 07c079a.

davereikher force-pushed on Aug 13, 2019

davereikher commented at 9:05 am on August 13, 2019: contributor

Squashed commits.

meshcollider commented at 9:27 pm on August 16, 2019: contributor

I believe this will be a lot simpler change now if you use GetDescriptorChecksum from #15986

Concept ACK anyhow

davereikher force-pushed on Aug 18, 2019

DrahtBot added the label Needs rebase on Aug 18, 2019

davereikher force-pushed on Aug 19, 2019

DrahtBot removed the label Needs rebase on Aug 19, 2019

davereikher commented at 7:38 am on August 19, 2019: contributor

I believe this will be a lot simpler change now if you use GetDescriptorChecksum from #15986

Concept ACK anyhow

Great! Now that GetDescriptorChecksum is available I moved DescriptorChecksum and PolyMod back into the anonymous namespace and instead used GetDescriptorChecksum to calculate the checksum. This also introduces an indirect test to GetDescriptorChecksum and the underlying functions. My branch seems to have failed an unrelated test on Travis while passing all tests (unit and functional, including the test that fails on Travis) locally. Is sporadic failure a known issue perhaps? Is there a way to re-run Travis?

fanquake commented at 7:41 am on August 19, 2019: member

@davereikher Travis tests can occasionally fail sporadically. I’ve rebooted the two failing instances for you.

fanquake renamed this:
~~Make descriptor tests deterministic~~
tests: Make descriptor tests deterministic
on Aug 19, 2019

in src/test/descriptor_tests.cpp:58 in d0e54ff552 outdated

64+
65+    // GetDescriptorChecksum returns "" if the checksum exists but is bad.
66+    // Switching apostrophes with 'h' breaks the checksum if it exists - recalculate it and replace the broken one.
67+    if (GetDescriptorChecksum(ret) == "") {
68+      ret = ret.substr(0, desc.size() - 9);
69+      ret += std::string("#") + GetDescriptorChecksum(ret);

meshcollider commented at 3:19 am on August 20, 2019:

nit: indentation

in src/test/descriptor_tests.cpp:75 in d0e54ff552 outdated

84+    std::unique_ptr<Descriptor> parse_priv;
85+    std::unique_ptr<Descriptor> parse_pub;
86     // Check that parsing succeeds.
87-    auto parse_priv = Parse(MaybeUseHInsteadOfApostrophy(prv), keys_priv, error);
88-    auto parse_pub = Parse(MaybeUseHInsteadOfApostrophy(pub), keys_pub, error);
89+    if (replace_apostrophe_with_h) {

meshcollider commented at 3:21 am on August 20, 2019:

There is actually a test case which used to be covered which is no longer ever covered - the use of h in the pub and ' in the prv and vice versa (because there was a 50% chance of each being changed independently)

davereikher commented at 5:30 am on August 21, 2019:

Thanks for your review. You are right, I completely missed this. I added code to cover all four test cases (no replacement, prv only, pub only and prv+pub) in b9ee63c71b751fd67da777774ea8c0b27e7db2f8.

davereikher force-pushed on Aug 21, 2019

Make descriptor test deterministic

Changed MaybeUseHInsteadOfApostrophy to UseHInsteadOfApostrophe.
This function now always replaces apostrophes with 'h'.
The original Check function was renamed to DoCheck and it's
called with an additional parameter which tells it to either
leave the prv and pub arguments as is or replace the apostrophes
with 'h'. The test runs with apostrophes replaced in prv only,
pub only, prv and pub and without replacement at all. Replacement
of apostrophes in a descriptor and then running DoCheck is conditional
on whether apostrophes are found in that descriptor.

Additionally, instead of dropping the checksum recalculate it
after replacing apostrophes with 'h' in the function UseHInsteadOfApostrophe
using the GetDescriptorChecksum function. That way, this also
introduces an indirect unit test to GetDescriptoChecksum.

b9ee63c71b

davereikher force-pushed on Aug 21, 2019

davereikher commented at 6:14 am on August 21, 2019: contributor

@davereikher Travis tests can occasionally fail sporadically. I’ve rebooted the two failing instances for you. @fanquake Travis failed again, could you please reboot the failing instance here?

meshcollider commented at 9:28 am on August 21, 2019: contributor

utACK

fanquake requested review from achow101 on Aug 21, 2019

achow101 approved

achow101 commented at 5:41 pm on August 22, 2019: member

Code Review ACK b9ee63c71b751fd67da777774ea8c0b27e7db2f8

fanquake commented at 0:01 am on August 23, 2019: member

@davereikher Thanks for sticking with this, nice first time contribution.

fanquake referenced this in commit 12f7147c89 on Aug 23, 2019

fanquake merged this on Aug 23, 2019

fanquake closed this on Aug 23, 2019

davereikher commented at 3:51 pm on August 23, 2019: contributor

Thanks a lot! I learned so much from just this small contribution and your reviews. Looking forward for more! :)

practicalswift commented at 5:49 am on August 24, 2019: contributor

@davereikher Very nice to have you onboard and thanks for this first contribution! Hope to see more contributions from you.

If you want to take on non-determinism in tests you might want to take a look at contrib/devtools/test_deterministic_coverage.sh.

The following unit tests are known to have non-deterministic line coverage:

https://github.com/bitcoin/bitcoin/blob/3ca514ddb77253042877d1a72dfd3021c3de2812/contrib/devtools/test_deterministic_coverage.sh#L16-L36

Getting them deterministic in terms of line coverage would be great! More specifically that would allow us to reason about how a proposed change alters unit tests line coverage. Currently line coverage is a stochastic process :-)

davereikher commented at 10:24 am on August 24, 2019: contributor

@davereikher Very nice to have you onboard and thanks for this first contribution! Hope to see more contributions from you.

If you want to take on non-determinism in tests you might want to take a look at contrib/devtools/test_deterministic_coverage.sh.

The following unit tests are known to have non-deterministic line coverage:

https://github.com/bitcoin/bitcoin/blob/3ca514ddb77253042877d1a72dfd3021c3de2812/contrib/devtools/test_deterministic_coverage.sh#L16-L36

Getting them deterministic in terms of line coverage would be great! More specifically that would allow us to reason about how a proposed change alters unit tests line coverage. Currently line coverage is a stochastic process :-)

Thanks! Sounds great, I’ll look into the non-determinism of those tests and I guess I will start with the low hanging fruit first :)

jasonbcox referenced this in commit 833f4496bb on Aug 18, 2020

kittywhiskers referenced this in commit 1f8a7bad4f on Nov 6, 2021

kittywhiskers referenced this in commit 16b2591e77 on Dec 5, 2021

DrahtBot locked this on Dec 16, 2021

tests: Make descriptor tests deterministic #16570

Conflicts