Make coding doctests ready for random seeds
Closed this issue · 40 comments
This ticket makes
sage -t --long --random-seed=n src/sage/coding/
pass for different values n than just 0.
Depends on #29962
Depends on #30045
CC: @sagetrac-dlucas @johanrosenkilde @orlitzky
Component: doctest framework
Keywords: linear code syndrome decoder
Work Issues: mark the doctest as fixed again after #30045 is done
Author: Jonathan Kliem
Branch/Commit: 9493347
Reviewer: Michael Orlitzky
Issue created by migration from https://trac.sagemath.org/ticket/29945
Changed keywords from none to linear code syndrom decoder
That code has minimum distance 3 so it can't correct two errors: it's not supposed to work. If you want to fuzz the generated code, say, you need to guard against the code having minimum distance less than 5.
Note that the existing doctest is already fuzzy in that it injects a random error of weight two.
How could r = Chan(c) have injected an error of 3?
That is a bug, isn't it?
The existing doctest has only been tested for set_random_seed(0). This is how the doctesting framework is currently set up, see #29935.
Sorry, I think I understand now.
This can be fixed in #29935 I guess. What fix do you suggest?
-D = codes.decoders.LinearCodeSyndromeDecoder(C, maximum_error_weight = 2)
+D = codes.decoders.LinearCodeSyndromeDecoder(C, maximum_error_weight = 1)Or do you want the last line of the test to be random?
This is a strange test for the method, because it really is only applied in a situation, where it might or might not work.
Or is it just testing that the result of D.decode_to_code is well-defined?
Replying to @johanrosenkilde:
That code has minimum distance 3 so it can't correct two errors: it's not supposed to work.
The real question is: Why is it a doctest, if it is not supposed to work.
There is the doctest
sage: G = Matrix(GF(3),[
....: [1, 0, 0, 0, 2, 2, 1, 1],
....: [0, 1, 0, 0, 0, 0, 1, 1],
....: [0, 0, 1, 0, 2, 0, 0, 2],
....: [0, 0, 0, 1, 0, 2, 0, 1]])
sage: C = LinearCode(G)
sage: D = codes.decoders.LinearCodeSyndromeDecoder(C, maximum_error_weight = 2)
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), 2)
sage: c = C.random_element()
sage: r = Chan(c)
sage: c == D.decode_to_code(r)
True
in src/sage/coding/linear_code.py. Why is it there? What is supposed to illustrate?
Ah, you're right, that's a bug in the doctest! I had not looked up the doctest (you hadn't given me a file/linenumber), so I incorrectly assumed that you had fuzzied the code matrix.
Indeed, the code can only correct one error. One fix would be
sage: D = codes.decoders.LinearCodeSyndromeDecoder(C, maximum_error_weight = 1)
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), 1)
Then the channel always creates only one error, which is uniquely correctable with the code.
Best,
Johan
Changed keywords from linear code syndrom decoder to linear code syndrome decoder
Description changed:
---
+++
@@ -15,3 +15,5 @@
sage: c == D.decode_to_code(r)
False
```
+
+The doctest is wrong, as the code can only correct errors of weight 1. It will be fixed in #29935.I figured you probably misunderstood what I wrote.
Not until actually thinking about your comment did I realize that I learnt this in linear algebra. Until then I just figured this is something I don't understand and I was only guessing what is going on.
Just to remark that this should be fixed and the ticket shouldn't be closed unless this is the case.
Description changed:
---
+++
@@ -1,19 +1,6 @@
-This failure was discovered with fuzzing the doctest with #29935.
+This ticket makes
```
-sage: set_random_seed(2)
-sage: G = Matrix(GF(3),[
-....: [1, 0, 0, 0, 2, 2, 1, 1],
-....: [0, 1, 0, 0, 0, 0, 1, 1],
-....: [0, 0, 1, 0, 2, 0, 0, 2],
-....: [0, 0, 0, 1, 0, 2, 0, 1]])
-sage: C = LinearCode(G)
-sage: D = codes.decoders.LinearCodeSyndromeDecoder(C, maximum_error_weight = 2)
-sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), 2)
-sage: c = C.random_element()
-sage: r = Chan(c)
-sage: c == D.decode_to_code(r)
-False
+sage -t --long --random-seed=n src/sage/coding/
```
-
-The doctest is wrong, as the code can only correct errors of weight 1. It will be fixed in #29935.
+pass for different values `n` than just `0`.One more bug or wrong doctest:
This is a doctest in src/sage/coding/grs_code.py and it fails (for some reason in the doctest environment one needs a different random seed, but that shouldn't matter here):
sage: set_random_seed(164)
sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSErrorErasureDecoder(C)
sage: c = C.random_element()
sage: n_era = randint(0, C.minimum_distance() - 2)
sage: Chan = channels.ErrorErasureChannel(C.ambient_space(), D.decoding_radius(n_era), n_era)
sage: y = Chan(c)
sage: D.connected_encoder().unencode(c) == D.decode_to_message(y)
For convenience:
sage: y
((0, 0, 37, 0, 0, 0, 46, 0, 0, 31, 0, 47, 0, 20, 50, 0, 0, 0, 0, 0, 0, 0, 32, 0, 40, 0, 0, 41, 0, 19, 0, 0, 0, 0, 16, 0, 12, 4, 0, 0),
(1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1))
sage: c
(43, 6, 37, 9, 34, 4, 46, 0, 40, 31, 26, 47, 10, 20, 50, 3, 24, 42, 6, 50, 18, 46, 32, 45, 40, 53, 19, 41, 22, 19, 47, 27, 54, 46, 16, 15, 12, 4, 15, 58)
sage: n_era
27
One more.
sage -t --long --random-seed=1231123241434789 src/sage/coding/punctured_code.py
**********************************************************************
File "src/sage/coding/punctured_code.py", line 628, in sage.coding.punctured_code.PuncturedCodeOriginalCodeDecoder.decode_to_code
Failed example:
D.decode_to_code(y) == c
Exception raised:
Traceback (most recent call last):
File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, in _run
self.compile_and_execute(example, compiler, test.globs)
File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1104, in compile_and_execute
exec(compiled, globs)
File "<doctest sage.coding.punctured_code.PuncturedCodeOriginalCodeDecoder.decode_to_code[7]>", line 1, in <module>
D.decode_to_code(y) == c
File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/coding/punctured_code.py", line 649, in decode_to_code
return _puncture(D.decode_to_code((y, e)), pts)
File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/coding/decoder.py", line 257, in decode_to_code
return self.connected_encoder().encode(word)
File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/coding/encoder.py", line 163, in encode
raise ValueError("The value to encode must be in %s" % M)
ValueError: The value to encode must be in Vector space of dimension 7 over Finite Field in a of size 2^4
**********************************************************************
1 item had failures:
1 of 9 in sage.coding.punctured_code.PuncturedCodeOriginalCodeDecoder.decode_to_code
[111 tests, 1 failure, 0.22 s]
Branch: public/29962
It's very cool you're finding these bugs! I will look at them when I get time (unfortunately probably not before next week), if someone else doesn't handle them first.
Changed branch from public/29962 to public/29945
Branch pushed to git repo; I updated commit sha1. New commits:
af5a330 | use _random_nonzero_element |
So now I've (somewhat redundantly) created #30045 which documents what the problem exactly was and posted a fix for that. I intend to merge this ticket into it (doctests running as I write). As you added "known bug"-flag, I guess this ticket can be positively reviewed (I hereby positively review it), after which you can perhaps positively review #30045?
Changed branch from public/29945 to public/29945-reb
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
ce176ef | make coding fuzz ready |
9dcd35c | fix doctest in sage/coding/linear_code |
f259cea | remove known bug flag |
b57d709 | marking bugs |
af5a330 | use _random_nonzero_element |
f6b09ea | Merge branch 'public/29945' of git://trac.sagemath.org/sage into public/29945-reb |
18428ed | Remove unnecessary decode_to_message in GeneralizedReedSolomonCode |
36cff4a | Add doc-test for 30045 |
4d76948 | Merge branch 'u/jsrn/30045_bugs_in_grs' of git://trac.sagemath.org/sage into public/29945-reb |
347e286 | remove known bug tags for fixed bugs |
Commit: 347e286
Changed branch from public/29945-reb to public/29945-reb2
Author: Jonathan Kliem
Reviewer: Michael Orlitzky
LGTM. I'll track down where _random_nonzero_element() comes from in the example you fixed and see if we can't make it a public method, since it will be needed more often when things are really random.
Thank you.
Changed branch from public/29945-reb2 to 9493347