implicitly fuzz RNG-dependent doctests with a random random seed

[dimpase]

Our documentation and tests include a variety of examples and tests involving randomness.

Those depend on a randomness seed, and up to Sage 9.1 they always used the same one: 0. Thus every run of sage -t or make [p]test[all][long] would run those "random" doctests deterministically. In many cases, the output of those tests even relied on that. As a result, random examples and tests were actually testing that they were run non-randomly!

This is reminiscent of an ​xkcd comic illustration of random number generators.

Based on these considerations and the related ​sage-devel discussion, we propose to:

• allow specifying a randomness when running tests (#29962),
• adapt tests involving randomness, making sure they test mathematical functionality independent of the randomness seed used to run them (see roadmap),
• default to a random randomness seed when none is specified (present ticket),

thus making those tests more robust and more useful, by becoming more likely to reveal bugs in a variety of cases including corner cases.

The first step (see #29962, merged in Sage 9.2) adds a --random-seed flag to sage -t, allowing:

sage -t --long --random-seed=9876543210 src/sage/

Still, when no randomness seed is specified, the default seed 0 is used. This means most testers test with the same randomness seed, making "random" doctests still mostly deterministic in practice.

Here is a way to pick a random randomness seed and run tests with it (can be used to work on the tickets in the roadmap):

$ randseed() {
    sage -c "import sage.misc.randstate as randstate; \
             randstate.set_random_seed(); \
             print(randstate.initial_seed())";
    }
$ SEED=$(randseed)
$ DIR=src/sage
$ echo "$ sage -t --long --random-seed=${SEED} ${DIR}" \
  && ./sage -t --long --random-seed=${SEED} ${DIR}

Once examples and tests involving randomness have been adapted, the present ticket puts the final touch by making it so that when running tests with no seed specified, a random one will be used:

sage -t src/sage/all.py 
Running doctests with ID 2020-06-23-23-19-03-8003eea5.
...
sage -t --warn-long 89.5 --random-seed=273987373473433732996760115183658447263 src/sage/all.py
    [16 tests, 0.73 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.8 seconds
    cpu time: 0.7 seconds
    cumulative wall time: 0.7 seconds

Being displayed in the output, the seed used can be used again if needed:

sage -t --warn-long 89.5 --random-seed=273987373473433732996760115183658447263 src/sage/all.py

allowing to explore any problematic case revealed by running the tests with that seed.

Roadmap:

• Allow fuzzing: #29962
• Make all parts of sage ready for default fuzzing:
  • #29945: coding
  • #29963: geometry
  • #29964: libs
  • #29965: graphs
  • #32107: groups
  • #29967: interfaces
  • #29968: algebras
  • #29969: misc
  • #29970: arith
  • #29971: categories
  • #29972: stats
  • #29973: sets
  • #29974: combinat
  • #29975: numerical, probability
  • #29976: matrix
  • #29977: modular
  • #29978: modules
  • #29979: rings
  • #29980: crypto
  • #29981: documentation
  • #29982: dynamics
  • #29983: finance
  • #29984: symbolic
  • #29985: schemes
  • #29986: plot
  • #32188: various missed tests along the way
• #32216: Update the developers guide for implicitly fuzzing doctests
• Finally make fuzzing default with this ticket.

Follow-up:

• #32544: Meta-ticket: Fix unstable doctests detected after #29935
• Remove set_random_seed in doctests where possible.

Errors discovered by this ticket:

• #29936: Hyperbolic geometry bugs revealed by fuzzing
• #29945: Failing doctest in src/sage/coding/linear_code.py (just a wrong doctest, will be fixed here)
• #29954: Unstable plotting
• #29956: Bug in KlyachkoBundle_class.random_deformation
• #29957: Bug in ContinuedFraction rounding
• #29958: Too many strong articulation points
• #29961: Random symbolic expression is completely unstable
• #30045: Bug in Reed-Solomon encoder and error-erasure decoder
• Index error with random derangement (fixed in #29974)
• #31890: simplify_hypergeometric is unstable
• #31891: ZeroDivisonError when creating polynomial system
• #31892: Conic parametrization broken
• #32075: Polynomial generic power trunk broken
• #32083: Various errors with polybori including segmentation fault
• #32084 _nth_root_naive fails for integer mod
• #32085: Errors when computing norms of padic elements
• #32086: apply_homography unstable for continue fraction
• #32095: DiFUB algorithm fails on some random graph
• #32108: Fix random tree on one or less vertices
• #32109: Fix 0/0 in ore function field
• #32111: Unstable minimal polynomial for element of 2-adic Eisenstein Extension Field in pi defined by x^{4 - 2*a}
• #32117: Random relative number field checks only irreducibility over QQ
• #32118: AlgebraicForm? checks invariance with random matrix that can be the identity
• #32124: SL2Z.random_element unstable
• #32125: random Ore polynomials do not respect minimum degree bound
• #32126: padic QpLC.random_element is broken
• #32127: gosper_iterator of continued fractions is unstable
• #32129: sage_input is unreliable for elements of ComplexField?
• #32131: Cut width of graph with one edge incorrect
• #32132: Wrong gyration orbit length
• #32138: is_groebner fails over fraction fields
• #32141: Unstable doctest involving permutation groups
• #32169: Bug in edge disjoint spanning trees
• #32185: Failing weak order assertion on random symbolic expression
• #32186: Random bounded tolerance graph
• #32187: permutation group generated by list perms in L of degree n incorrect when compared to GAP
• #32657: plot_vector_field unstable

[gh-kliem]

Just so that we don't forget that we will have to update

​https://doc.sagemath.org/html/en/developer/coding_basics.html

[gh-kliem]

geometry/hyperbolic_space/hyperbolic_geodesic.py makes some claims on how good approximations work, which doesn't seem to work. I had this thing run 7 times now and not one time did all tests pass. E.g. there is one test that gives me absolute errors of 0.7 when running this in the shell, but the test claims it is below 10**-9.

There is also #29904. Other than that the geometry module appears to ready.

Edit: And there is some place where you need to add set_random_seed(0) now or similar.

[dimpase]

Replying to gh-kliem:

geometry/hyperbolic_space/hyperbolic_geodesic.py makes some claims on how good approximations work, which doesn't seem to work. I had this thing run 7 times now and not one time did all tests pass. E.g. there is one test that gives me absolute errors of 0.7 when running this in the shell, but the test claims it is below 10**-9.

this is a great example of fuzzing catching an apparent error, it seems.

There is also #29904. Other than that the geometry module appears to ready.

Edit: And there is some place where you need to add set_random_seed(0) now or similar.

[gh-kliem]

New commits:

​d5fc5be	start from a "random" random seed for doctesting
​5c7e562	fix double description of hypercube
​6b41bdb	Merge branch 'public/29904' of git://trac.sagemath.org/sage into public/29935
​b2954ce	fix random test in geometry/linear_expression

[gh-kliem]

Even in the developer guide there is an example, where it is confusing:

sage: M = matrix.identity(3) + random_matrix(RR,3,3)/10^3
sage: M^2 # abs tol 1e-2
[1 0 0]
[0 1 0]
[0 0 1]

There is no mentioning there that only one particular matrix is tested.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​dc49dd0

update developer guide

[dimpase]

Replying to gh-kliem:

Even in the developer guide there is an example, where it is confusing:

sage: M = matrix.identity(3) + random_matrix(RR,3,3)/10^3
sage: M^2 # abs tol 1e-2
[1 0 0]
[0 1 0]
[0 0 1]

There is no mentioning there that only one particular matrix is tested.

indeed it assumes (?) that the entries of the random matrix are small in abs value

[gh-kliem]

Nothing to assume there. random_matrix(RR,3,3) has entries between -1 and 1. After dividing we are good.

[mkoeppe]

How about making the random seed an option to sage-runtests. Then people can fuzz the doctests if they want.

[gh-kliem]

Will people do that? Especially enough to find incorrect claims. If you look into #29936 we have been claiming a preciseness that is far from true. Even if you consider the relative error instead of the absolute error. fuzzed doctests would have easily detected that. Even worse. Maybe the situation was better at some point and we never caught on about the regression.

[dimpase]

it is not a "real" (time-consuming) fuzzing, it is making the main random seed nondeterministic in tests. making it optional is akin to making tests optional.

we already found a couple of examples which show usefulness of this change in detecting bugs in Sage.

[mkoeppe]

The option that I propose to add needs to be added in any case, so that when a failure is revealed by a random random seeds, we can reproduce the failure with that seed.

[dimpase]

it is a good point - and the non-det. seed needs to be logged - if this is not yet in the branch it should get there.

[mkoeppe]

So I would suggest to use this ticket to introduce the option, not change the default.

[dimpase]

no, I don't agree, it makes no sense to test less if one can test more, and also not having it default would not force people to make their tests robust.

[mkoeppe]

By the way I don't think most doctests have the ambition to demonstrate correctness of mathematical claims. In my opinion, if a doctest intends to do that, it should run an explicit loop of several tests. Still deterministically.

[mkoeppe]

Why would creating the option and changing the default have to be done on the same ticket? I think it's best practices to separate the two steps on two tickets.

[gh-kliem]

Feel free to do with the branch whatever you think is reasonable.

[gh-kliem]

What I think would be great if running we could run each file at some "random" seed, e.g.

sage -t src/sage/all.py 
Running doctests with ID 2020-06-22-18-56-54-668a26f3.
Git branch: public/29935
Using --optional=4ti2,bliss,build,dochtml,e_antic,flask,flask_autoindex,flask_babel,flask_oldsessions,flask_openid,flask_silk,latte_int,lidia,lrslib,memlimit,normaliz,pynormaliz,python_openid,sage,speaklater,twisted
Doctesting 1 file.
sage -t --warn-long 91.5 --seed 123456 src/sage/all.py
    [16 tests, 0.76 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.8 seconds
    cpu time: 0.8 seconds
    cumulative wall time: 0.8 seconds

You can reproduce this test with

sage -t --warn-long 91.5 --seed 123456 src/sage/all.py

Is a bit annoying, as seeds can be long though. Then whenever a bot or someone discovers a failure, you can reproduce it. At least if it really was caused by the random seed.

[mjo]

Just to weigh in:

1. The default should be to use a randomly-chosen seed.
2. Failures should be reproducible:
   1. It should be possible to pass a seed to the test runner with e.g. --seed.
   2. Any test failures should log/echo the current seed so that the failing test can be reproduced easily using the option in (2.a.).

The sooner we can push this through the better. Tests that don't work due to bugs can even be deleted and replaced with trac tickets saying "this never worked" IMO.

[gh-kliem]

With #29904 (already pulled into this branch), #29936 (not yet pulled) and b2954ceea638b4510e99d90cea3f99fa9a49338 (commit from above) geometry should be ready for this.

Edit: The updated branch of #29904 (not yet pulled) doesn't have set_random_seed anymore. But there is plenty of set_random_seed for cones doctests? Should I remove those as well or do we do this somewhere else?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​bac708e

make graphs ready for fuzz doctests

[mkoeppe]

Replying to gh-kliem:

there is plenty of set_random_seed for cones doctests? Should I remove those as well or do we do this somewhere else?

Not on the same ticket.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b5e9896

make algebras fuzz ready

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​8babc2a

make arith fuzz ready

[gh-kliem]

Please tell me, if I should open seperate tickets for those or something else. I just felt like starting with those. I'm done for today.

[gh-mwageringel]

Replying to mjo:

1. The default should be to use a randomly-chosen seed.
2. Failures should be reproducible:
   1. It should be possible to pass a seed to the test runner with e.g. --seed.
   2. Any test failures should log/echo the current seed so that the failing test can be reproduced easily using the option in (2.a.).

+1.

Also note that Sage still uses a verbatim copy of the Python-2 version of the Random module during doctesting, which was necessary in order to obtain consistent results between Python 2 and 3. This is why the bug in #29550 went unnoticed, for example. Now that support for Python 2 has been removed, we should switch to the Python 3 version of Random. This will require updating lots of doctests, but I assume this ticket here will simplify this if it makes doctests less dependent on the seed/RNG.

[gh-kliem]

Apparently LinearCodeSyndromeDecoder.decode_to_code is broken.

See #29945.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​815c288	make categories fuzz ready
​c7d16e9	make coding fuzz ready

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​39edfdc	make random seed reproducible
​e5c54af	document random_seed

[gh-kliem]

I specified random_seed to distinguish from --randorder=SEED. If after --randorder=SEED the next option is --seed=SEED that sounds a bit weird to me. Although random_seed is not much better.

[gh-kliem]

Standard bracked lyndon words are set up incorrectly. I don't know if that should be consider a bug:

sage: SBLW33 = StandardBracketedLyndonWords(3,3)
sage: TestSuite(SBLW33).run()
Failure in _test_an_element:
Traceback (most recent call last):
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/misc/sage_unittest.py", line 296, in run
    test_method(tester=tester)
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/categories/sets_cat.py", line 1093, in _test_an_element
    tester.assertTrue(an_element in self, "self.an_element() is not in self")
  File "/home/jonathan/Applications/sage/local/lib/python3.7/unittest/case.py", line 692, in assertTrue
    raise self.failureException(msg)
AssertionError: self.an_element() is not in self
------------------------------------------------------------
Failure in _test_enumerated_set_contains:
Traceback (most recent call last):
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/misc/sage_unittest.py", line 296, in run
    test_method(tester=tester)
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/categories/enumerated_sets.py", line 945, in _test_enumerated_set_contains
    tester.assertIn(w, self)
  File "/home/jonathan/Applications/sage/local/lib/python3.7/unittest/case.py", line 1106, in assertIn
    self.fail(self._formatMessage(msg, standardMsg))
  File "/home/jonathan/Applications/sage/local/lib/python3.7/unittest/case.py", line 680, in fail
    raise self.failureException(msg)
AssertionError: [1, [1, 2]] not found in Standard bracketed Lyndon words from an alphabet of size 3 of length 3
------------------------------------------------------------
Failure in _test_some_elements:
Traceback (most recent call last):
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/misc/sage_unittest.py", line 296, in run
    test_method(tester=tester)
  File "/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/categories/sets_cat.py", line 1385, in _test_some_elements
    "the object %s in self.some_elements() is not in self")%(x,))
  File "/home/jonathan/Applications/sage/local/lib/python3.7/unittest/case.py", line 692, in assertTrue
    raise self.failureException(msg)
AssertionError: the object [1, [1, 2]] in self.some_elements() is not in self
------------------------------------------------------------
The following tests failed: _test_an_element, _test_enumerated_set_contains, _test_some_elements

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​93415f3

make combinat fuzz ready

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​dbd7f6c

fix doctest in sage/coding/linear_code

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​72cd0ac	make crypto fuzz ready
​00dc135	make documentation fuzz ready

[gh-kliem]

In src/sage/plot/multigraphics.py is a doctest that fails with the precicion:

1294             sage: g1 = plot(sin(x), (x, -pi, pi))
1295             sage: g2 = circle((0,1), 1.)
1296             sage: G = graphics_array([g1, g2])
1297             sage: G.position(0)  # tol 1.0e-13
1298             (0.023437500000000003,
1299              0.03415488992713045,
1300              0.4627803348994754,
1301              0.9345951100728696)
1302             sage: G.position(1)  # tol 1.0e-13
1303             (0.5136230468749999,
1304              0.19293222169724827,
1305              0.46278033489947534,
1306              0.617040446532634)

when running on set_random_seed(151058820726654196682836430928254760259). The precision is somewhere around 1e-3 then. Is this a bug?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4c540c6	make dynamics fuzz ready
​23ed583	fix doctest in hyperbolic_space/hyperbolic_point
​5283dc4	use abs tol flag
​7b244c0	modify doctests to the extend that they hold with fuzz
​84ba6d5	Merge branch 'public/29936' of git://trac.sagemath.org/sage into public/29935
​36ea095	make finance fuzz ready
​bfe9c2a	bug in connectivity
​a170927	make groups fuzz ready

[jhpalmieri]

It may be too late for this, but I would suggest a staged approach:

• ticket 1: implement optional random seed but don't make it the default
• tickets 2-n: fix doctests when using random seeds in various parts of the Sage library
• ticket n+1: make random seed standard, if that is what people think should be done

Doing everything all at once is likely to lead to a patch bomb, which will lead to merge conflicts and in general be hard to deal with.

[gh-kliem]

There is a reason that I have the fixes grouped by parts of sage. So that isn't spoiled yet.

That completely makes sense. We still need the last ticket to have the bots test everything.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​38b4557	another file for combinat
​8ec8298	make symbolix fuzz ready
​e8d4776	make schemes fuzz ready
​9b5bef8	make plot fuzz ready
​98e34d3	partially make rings fuzz ready
​6f33e4a	partially make matrix fuzz ready
​e6dc532	partially make modular fuzz ready
​18e980d	partially make modules fuzz ready

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​da1c6be	start from a "random" random seed for doctesting
​b7b836d	make random seed reproducible
​eedbe5e	document random_seed
​998b1b9	default random seed 0 for now
​0a4f42f	reanable making fuzzing default

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​fc25017

dash instead of underscore for command line options

[gh-kliem]

New commits:

​fc25017

dash instead of underscore for command line options

[gh-kliem]

We had a little discussion on #29971, how we treat doctests as

sage: C = FiniteEnumeratedSets().example()
sage: C.random_element()
1

If we tag this as # random and maybe test instead containment in C, the doctest we will essentially remove the doctest and add another. Is this what we want?

Matthias Koeppe suggested inventing a new tag maybe # random-seed=0. If we implicitly fuzz all doctests this would only be tested if we run the test block twice?!

I think we should agree on a something here. Depending on the agreement it needs to be taken care of with #29962 already.

IMO tests as C.random_element() should run at least once with fuzzing (with checking that the object is consistent). We can run it twice to obtain our old test, but I would appreciate some help with that.

[mjo]

This will do the job, and doesn't depend on the literal output of the random function:

sage: C = FiniteEnumeratedSets().example()
sage: C.random_element() in C
True

[gh-kliem]

In principal I agree.

I prefer

sage: C = FiniteEnumeratedSets().example()
sage: n = C.random_element(); n  # random
1
sage: n in C
True

as this makes it a bit easier for the user to see, what will/might happen. But that is only minor.

However, I just noticed, that there are problems with that approach. The representation of those random things will never be checked. In principal (almost) all random events should be reproducible with some random seed (doesn't work for e.g. hashing). By tagging something as # random, we might document nonsense or outdated information and no one will catch on.

E.g. in #29981 I fixed a documentation mistake along the way: Solve a linear equation system with A\v with A a random matrix. A should be non-singular of course, which was never thought of because the doctest is only tested for one matrix, which happens to be non-singular. In #29981, A is defined as A = random_matrix(QQ, 3, algorithm='unimodular'). However, I forgot to update the representation of A to some unimodular matrix and the doctests never caught on.

Now if you tag something as # random-seed=0 and we find some way to test this (both seed 0 and different), it would mean that the printed representations stay up to date and consistent and it is also tested, if those thing work for "random" input.

I found many examples where functions where tested assuming random seed 0. One could make use of the double testing framework:

def foo(y):
   r"""
   EXAMPLES::

      sage: M = random(); M  # random-seed=0
      <some random input>
      sage: N = foo(M); N  # random-seed=0
      <some random output>
      sage: check_for_consistency(M, N)
   """
   return _foo(y)

It is still checked, that foo works exactly for some example that hopefully was verified by someone. But it is also checked, that the method in principal works on "random" input and that the output appears to be correct.

[mjo]

If we want to check the printed/string representation of something, can't we just... check it? In other words, instead of

sage: C = FiniteEnumeratedSets().example()
sage: C.random_element()
1

we could do

sage: C = FiniteEnumeratedSets().example()
sage: C.random_element() in C
True
sage: C[0]
1

This has the (big, in my opinion) added benefit of actually being a runnable example. If a user runs

sage: C = FiniteEnumeratedSets().example()
sage: n = C.random_element(); n  # random

then he's not going to see what the documentation says he should see, because # random does nothing on the command-line.

[gh-mwageringel]

IMO, it is not necessary to test the printing of random elements, as the repr of those elements is already tested elsewhere. We do not make any promises about the precise elements that are returned with a seed of 0, so we should not bake that into the doctests. As we cannot test the randomness, we can only test that random_element returns an element of the parent. The following check could be used for that:

sage: C.random_element().parent() is C

Unlike __contains__, this does not implicitly coerce the element into C.

[mjo]

Replying to gh-mwageringel:

IMO, it is not necessary to test the printing of random elements, as the repr of those elements is already tested elsewhere. We do not make any promises about the precise elements that are returned with a seed of 0, so we should not bake that into the doctests. As we cannot test the randomness, we can only test that random_element returns an element of the parent. The following check could be used for that:

sage: C.random_element().parent() is C

Unlike __contains__, this does not implicitly coerce the element into C.

Sounds good to me.

[gh-kliem]

Replying to gh-kliem:

Sounds good to me. As for the documentation of random_element, I don't think a user cares about the precise value of set_random_seed(0); C.random_element().

Two more cases that I would like to discuss.

• Basically from comment:60. How do we deal with something like this:

  def foo(y):
     r"""
     EXAMPLES::
  
        sage: M = random(); M
        <some random input>
        sage: foo(M)
        <some random output>
     """
  

  It appears to me that there are many examples, where someone did not write down a concrete element to doctest. I would propose having two doctests, if possible:
  • Explicitly obtain the old test.
  • Have a "random" test with a consistency check. (Even without a consistency check, it's probably worth checking that the function terminates without an error usually.)
• The other one is a concrete example from #29981 (linear algrebra tutorial). The original test is

      sage: A=random_matrix(QQ,3)
      sage: v=vector([2,3,1])
      sage: A,v
      (
      [ 0 -1  1]
      [-1 -1 -1]
      [ 0  2  2], (2, 3, 1)
      )
      sage: x=A\v; x
      (-7/2, -3/4, 5/4)
      sage: A*x
      (2, 3, 1)
  

  As mentioned already, this does not work. I see basically two ways of fixing this. One is to explicitly write down A. The other one is similar to what I did. Use a correct random approach (e.g. random unimodular) and check that indeed A*x == v. Optionally one can print x and A and tag this as random. To be honest, I don't see how a user would profit from the printing. What a 3 by 3 matrix looks like should be clear by then.

[mjo]

Replying to gh-kliem:

• Basically from comment:60. How do we deal with something like this:

  def foo(y):
     r"""
     EXAMPLES::
  
        sage: M = random(); M
        <some random input>
        sage: foo(M)
        <some random output>
     """
  

If the point isn't to demonstrate the random() function, then the "random" element can just be replaced with whatever it winds up with now (i.e. the fixed element you get with a seed of zero). The TESTS block can contain some truly random test of a property that the output from foo() should satisfy, like

sage: foo(random()) in RR
True

• The other one is a concrete example from #29981 (linear algrebra tutorial). The original test is

      sage: A=random_matrix(QQ,3)
      sage: v=vector([2,3,1])
      sage: A,v
      (
      [ 0 -1  1]
      [-1 -1 -1]
      [ 0  2  2], (2, 3, 1)
      )
      sage: x=A\v; x
      (-7/2, -3/4, 5/4)
      sage: A*x
      (2, 3, 1)
  

How about...

sage: A = random_matrix(QQ,3)
sage: while not A.is_invertible():
....:     A = random_matrix(QQ,3)
....:     
sage: v=vector([2,3,1])
sage: x=A\v
sage: A*x - v == 0
True

[gh-kliem]

Replying to mjo:

Replying to gh-kliem:

• Basically from comment:60. How do we deal with something like this:

  def foo(y):
     r"""
     EXAMPLES::
  
        sage: M = random(); M
        <some random input>
        sage: foo(M)
        <some random output>
     """
  

If the point isn't to demonstrate the random() function, then the "random" element can just be replaced with whatever it winds up with now (i.e. the fixed element you get with a seed of zero). The TESTS block can contain some truly random test of a property that the output from foo() should satisfy, like

sage: foo(random()) in RR
True

• The other one is a concrete example from #29981 (linear algrebra tutorial). The original test is

      sage: A=random_matrix(QQ,3)
      sage: v=vector([2,3,1])
      sage: A,v
      (
      [ 0 -1  1]
      [-1 -1 -1]
      [ 0  2  2], (2, 3, 1)
      )
      sage: x=A\v; x
      (-7/2, -3/4, 5/4)
      sage: A*x
      (2, 3, 1)
  

How about...

sage: A = random_matrix(QQ,3)
sage: while not A.is_invertible():
....:     A = random_matrix(QQ,3)
....:     
sage: v=vector([2,3,1])
sage: x=A\v
sage: A*x - v == 0
True

Sounds reasonable to me. I will adhere to those suggestions.

[gh-kliem]

New commits:

​1d7b00e	dash instead of underscore for command line options
​b31e2d5	Merge branch 'public/29962' of git://trac.sagemath.org/sage into public/29962-reb
​2f30dd9	small fixes
​b62f781	doctests do not start from a random seed by default yet
​263d605	Revert "doctests do not start from a random seed by default yet"
​3636597	Revert "default random seed 0 for now"

[gh-kliem]

Maybe it makes sense to restrict the size of the random seed, so that one can still read the output of doctesting.

[dimpase]

Replying to gh-kliem:

Maybe it makes sense to restrict the size of the random seed, so that one can still read the output of doctesting.

it's not clear to me what you mean here.

[gh-kliem]

sage -t src/sage/all.py 
Running doctests with ID 2020-06-23-23-19-03-8003eea5.
...
sage -t --warn-long 89.5 --random-seed=273987373473433732996760115183658447263 src/sage/all.py
    [16 tests, 0.73 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.8 seconds
    cpu time: 0.7 seconds
    cumulative wall time: 0.7 seconds

Currently this output is the plan. This might be very annoying for patchbots and so on. If we instead restrict to fewer digits, we will still test a reasonable amount of different inputs and you can still read this line (even if working on a non-huge screen).

[dimpase]

I think it is ok - compare this with very long lists of optional packages which are there sometimes.

[gh-kliem]

See ​https://trac.sagemath.org/ticket/29962#comment:19

[mkoeppe]

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

[slelievre]

Marking this as a meta-ticket.

[slelievre]

Expanding the ticket description, adding a code snippet giving a way to set a random randomness seed, which I find useful for working on the (few remaining) dependencies of this ticket.

[gh-kliem]

A couple of new tests fail yet.

[gh-kliem]

Last 10 new commits:

​0994f0f	trac 32084 fix nth root
​226fe84	trac 32084 fix nth root
​71ab842	Merge branch 'public/32084r2' of git://trac.sagemath.org/sage into public/29935
​960ce8b	make groups ready for random seeds
​5592c58	make some_elements of affine group ready for random seeds
​dc4ed63	Merge branch 'public/32107' of git://trac.sagemath.org/sage into public/29935
​a732a3f	fix random tree on less than two vertices
​5b19d31	Merge branch 'public/32108' of git://trac.sagemath.org/sage into public/29935
​9e53965	fix 0/0 in ore function field
​453ffc8	Merge branch 'public/32109' of git://trac.sagemath.org/sage into public/29935

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7a393c2	remove bug tag from 32095
​89c210e	trac #32095: sorted is not inplace
​f16765a	Merge branch 'public/graphs/32095_fix_DiFUB_with_boost' of git://trac.sagemath.org/sage into public/29935

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​75fad77	Merge branch 'public/29979' of git://trac.sagemath.org/sage into public/29979-reb
​e280083	Merge branch 'public/32084r2' of git://trac.sagemath.org/sage into public/29979-reb
​192b564	add ticked number to test
​b20059c	Merge branch 'public/32109' of git://trac.sagemath.org/sage into public/29979-reb
​ce98d48	two more doctests
​34a233d	pull in 32117
​cfe869b	modulo n better be for n > 0
​3752b9c	some more remaining tests
​97e015c	Merge branch 'public/29979-reb' of git://trac.sagemath.org/sage into public/29935

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e6a697a	truely ignore ignored bounds for ZZ.random_element
​36c7c58	pull 32124
​0bcab06	Merge branch 'public/29979-reb' of git://trac.sagemath.org/sage into public/29935
​7f39bf0	fix orbit lenght of gyration

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​cb037ca

fix orbit lenght of gyration

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​01f98ac

fix orbit lenght of gyration

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ee49444	one more doctest in rings
​b8e9e8e	two more doctests in graphs

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​be3e05f	29979: a few more fixes
​49ddba9	merge 29979

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​aa5276a	trac #32131: fix cutwidth for single edge graph
​8488bf4	trac #32131: fix method for non connected graphs
​8d9abe0	Merge branch 'public/graphs/32131_fix_cutwidth' of git://trac.sagemath.org/sage into public/29935
​431397b	a few more tests

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ac0dca7	one more missing test from groups
​fcdc025	one more test from modular
​008c6e1	one more failing test in coding
​5f0f5dc	29979: mark failing tests as not tested
​bc1e14a	29979: minor tweaks of doctests
​692aba8	Merge branch 'public/29979-reb' of git://trac.sagemath.org/sage into public/29935

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2ca52c6

two more doctests

[gh-kliem]

This is getting more and more stable.

I can now run it on 8 random seeds without failure (or without failure that doesn't appear on random seed 0). There are probably still failing examples, but its getting to a point, where it won't prevent patchbots from working and it's not too much of a burden to report failures because of this.

[gh-mwageringel]

We should also remember to try the optional tests at some point, but I assume the majority of them does not use randomness.

[gh-kliem]

Right, I forgot about the optional packages.

I hope this helps a bit:

​https://github.com/kliem/sage/pull/48/checks

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​20336cc

various small fixes

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​836be04	remove bug tag as 32169 has been resolved
​7f082ee	a few more fixes for various doctests
​76ce723	trac #32169: new ILP formulation
​047afda	trac #32169: enforce equality in the number of incoming edges
​5f4caba	Merge branch 'public/graphs/32169_new_ILP' of git://trac.sagemath.org/sage into public/29935

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​474490e

fix ValueError when obtaining random bounded tolerance graph

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f0f9cd5

two more doctests

[gh-kliem]

I outsourced many of the small fixes to #32188, to make review here easier.

[nbruin]

Note that doctesting with a fixed seed is publicly documented behaviour in sage. Quoting from ​Developer guide:

However, most functions generating pseudorandom output do not need this tag since the doctesting framework guarantees the state of the pseudorandom number generators (PRNGs) used in Sage for a given doctest.

I would think that tests explicitly relying on this behaviour are rather weak and I wouldn't mind changing this "policy", but we shouldn't forget to update the developer guide as well.

[gh-kliem]

Replying to nbruin:

Note that doctesting with a fixed seed is publicly documented behaviour in sage. Quoting from ​Developer guide:

However, most functions generating pseudorandom output do not need this tag since the doctesting framework guarantees the state of the pseudorandom number generators (PRNGs) used in Sage for a given doctest.

I would think that tests explicitly relying on this behaviour are rather weak and I wouldn't mind changing this "policy", but we shouldn't forget to update the developer guide as well.

Thanks for the pointer. This is now #32216.

[gh-kliem]

I'll leave #32169 for later and would just like to get this in.

---

New commits:

​669a08c	implicitly fuzz RNG-dependent doctests
​84ca956	reduce vertices for edge disjoint spanning trees

[mjo]

I think this,

         ....:     n = ZZ.random_element().abs() + 5
+        ....:     if n > 5000:  # avoid timeouts
+        ....:         continue

can be simplified by passing (5,5001) as the bound to ZZ.random_element(), without abs.

And the fix for this has already been merged:

+        sage: test_symbolic_expression_order(10000)  # long time,  # not tested, known bug (see :trac:`32185`)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​180d945	do not remove fixed doctest
​5405f18	simplify doctest

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​950eaeb

fix unstable doctests

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​512a10d

fixed some doctests for disjoint spanning trees

[mjo]

Looks OK now, but there's really no way to be 100% certain. We will probably discover a few instances where e.g. a ptestlong happens to generate four relatively hard problems at once, leading to intermittent timeouts. But regardless, I think the sooner we can get this in, the better. I started some GH actions for added test cycles.

[gh-DaveWitteMorris]

Replying to mjo:

... I think the sooner we can get this in, the better. ...

+1

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​1d25525

fix unstable doctest in book_stein_ent

[gh-kliem]

I also think this is ready. It is rather stable now.

We should open a new (meta?) ticket, to collect all those failures, I think.

[mjo]

Let's just do it before beta2 happens.

Thanks for all your work on this, I never had the courage to try it myself.

[gh-kliem]

Thank you.

[gh-kliem]

I created #32544 for the errors appearing now that this is positively reviewed. There already is a ticket on it (#32543).

[vbraun]

sage -t --long --warn-long 45.3 --random-seed=58740356065403116296055203326248101103 src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 23499, in sage.graphs.generic_graph.GenericGraph.edge_polytope
Failed example:
    P.is_combinatorially_isomorphic(product(components))
Expected:
    True
Got:
    False
**********************************************************************
1 item had failures:
   1 of  24 in sage.graphs.generic_graph.GenericGraph.edge_polytope
    [3598 tests, 1 failure, 22.29 s]
----------------------------------------------------------------------
sage -t --long --warn-long 45.3 --random-seed=58740356065403116296055203326248101103 src/sage/graphs/generic_graph.py  # 1 doctest failed
----------------------------------------------------------------------

[gh-kliem]

So this ticket got rejected because it detected my own mistake in #32498. That's fair I guess.

What I claimed is complete nonsense, but it did work for seed 0 I guess. The (symmetric) edge polytope of a graph is of course the join of the (symmetric) edge polytopes of the connecting compoments.

[gh-kliem]

No, that is not the join, it is the subdirect sum. It is really worth reading the definitions once in a while...

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​36939d5	Merge branch 'develop' of git://trac.sagemath.org/sage into public/29935-reb
​7e487e5	fix mistake from #32498

[gh-kliem]

@Martin Rubey: Can you please check the fix of #32498, everything else should still be fine.

[mantepse]

I'm afraid there is a MemoryError reported by the bot. I'll check whether it is reproducible.

[mantepse]

sage -t --random-seed=306431873350217748498615142104107167501 src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 23601, in sage.graphs.generic_graph.GenericGraph.symmetric_edge_polytope
Failed example:
    P.is_combinatorially_isomorphic(P1.subdirect_sum(P2))
Exception raised:
    Traceback (most recent call last):
      File "/home/martin/sage-develop/local/lib/python3.8/site-packages/sage/doctest/forker.py", line 694, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/martin/sage-develop/local/lib/python3.8/site-packages/sage/doctest/forker.py", line 1088, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.generic_graph.GenericGraph.symmetric_edge_polytope[20]>", line 1, in <module>
        P.is_combinatorially_isomorphic(P1.subdirect_sum(P2))
      File "/home/martin/sage-develop/local/lib/python3.8/site-packages/sage/geometry/polyhedron/base.py", line 10715, in is_combinatorially_isomorphic
        return G_self.is_isomorphic(G_other)
      File "/home/martin/sage-develop/local/lib/python3.8/site-packages/sage/graphs/generic_graph.py", line 22672, in is_isomorphic
        isom = isomorphic(GC, GC2, partition, partition2, (self._directed or self.has_loops()), 1)
      File "sage/groups/perm_gps/partn_ref/refinement_graphs.pyx", line 163, in sage.groups.perm_gps.partn_ref.refinement_graphs.isomorphic (build/cythonized/sage/groups/perm_gps/partn_ref/refinement_graphs.c:6775)
        cdef bint isomorphic = double_coset(<void *>GS1, <void *>GS2, part, ordering, n, &all_children_are_equivalent, &refine_by_degree, &compare_graphs, NULL, NULL, output)
      File "sage/groups/perm_gps/partn_ref/double_coset.pyx", line 364, in sage.groups.perm_gps.partn_ref.double_coset.double_coset (build/cythonized/sage/groups/perm_gps/partn_ref/double_coset.c:5618)
        raise MemoryError
    MemoryError
**********************************************************************
1 item had failures:
   1 of  53 in sage.graphs.generic_graph.GenericGraph.symmetric_edge_polytope
    [3558 tests, 1 failure, 42.09 s]
----------------------------------------------------------------------
sage -t --random-seed=306431873350217748498615142104107167501 src/sage/graphs/generic_graph.py  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 43.1 seconds
    cpu time: 40.1 seconds
    cumulative wall time: 42.1 seconds
Pytest is not installed, skip checking tests that rely on it.

[gh-kliem]

Looks like I need to reduce the number of vertices.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​150225d

reasonable graph size for doctets

[gh-kliem]

Previously I decomposed random graphs of up to 12 vertices. Now I take the disjoint union of random graphs and need to go down with the number of vertices.

[mantepse]

timeout

[mantepse]

It seems that there is still a problem. With some seeds, testing generic_graph.py takes about 16 seconds on my computer. However,

sage -t --random-seed=236024484355828254371843550334759500607 src/sage/graphs/generic_graph.py

times out. I attached the log. The last line executed is

sage: trees = g.edge_disjoint_spanning_trees(k) ## line 6282 ##

Of course, this should not have anything to do with the SEP.

[gh-kliem]

Yes, that is #32169. I was wondering why it did not happen in this case.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2609cb5

edge disjoint spanning tree not as fast as claimed, see #32169

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​138f038

fix doctest failure for random matrix

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​8117091

one more unstable doctest

[gh-kliem]

New commits:

​8117091

one more unstable doctest

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​db8daf9	implicitly fuzz RNG-dependent doctests
​e1a487f	reduce vertices for edge disjoint spanning trees
​d311adf	do not remove fixed doctest
​accdc2b	simplify doctest
​4ad6665	fix unstable doctests
​c2326fc	fixed some doctests for disjoint spanning trees
​361b203	fix unstable doctest in book_stein_ent
​e45603f	edge disjoint spanning tree not as fast as claimed, see #32169
​eba3bc7	fix doctest failure for random matrix
​5739ef7	one more unstable doctest

[gh-kliem]

Rebased on #32498, which fixes the error with (symmetric) edge polytopes.

[gh-kliem]

Correct ticket.

[gh-kliem]

Thank you.

[mjo]

No problem, you'll have to rebase this onto the typo-fix too I think.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. Last 10 new commits:

​3cfe235	implicitly fuzz RNG-dependent doctests
​1980561	reduce vertices for edge disjoint spanning trees
​e6dd027	do not remove fixed doctest
​22c2b66	simplify doctest
​e32986c	fix unstable doctests
​7b1bd36	fixed some doctests for disjoint spanning trees
​812b555	fix unstable doctest in book_stein_ent
​74e505b	edge disjoint spanning tree not as fast as claimed, see #32169
​44cd7ae	fix doctest failure for random matrix
​2c478d1	one more unstable doctest

[gh-kliem]

Replying to mjo:

No problem, you'll have to rebase this onto the typo-fix too I think.

I don't know, if this is necessary, but it sure doesn't hurt.

[vbraun]

Merge conflict

[gh-kliem]

This is the merge conflict, which permits a trivial solution (at least trivial for a human being):

diff --cc src/bin/sage-runtests
index d1fe6567e7,4fc2062b15..0000000000
--- a/src/bin/sage-runtests
+++ b/src/bin/sage-runtests
@@@ -64,59 -55,60 +55,97 @@@ if __name__ == "__main__"
               'if "external" is listed, will also run tests for available external software; '
               'if "build" is listed, will also run tests specific to Sage\'s build/packaging system; '
               'if set to "all", then all tests will be run')
++<<<<<<< HEAD
 +    parser.add_option("--randorder", type=int, metavar="SEED", help="randomize order of tests")
 +    parser.add_option("--random-seed", dest="random_seed", type=int, metavar="SEED", help="random seed (integer) for fuzzing doctests")
 +    parser.add_option("--global-iterations", "--global_iterations", type=int, default=0, help="repeat the whole testing process this many times")
 +    parser.add_option("--file-iterations", "--file_iterations", type=int, default=0, help="repeat each file this many times, stopping on the first failure")
 +    parser.add_option("--environment", type=str, default="sage.repl.ipython_kernel.all_jupyter", help="name of a module that provides the global environment for tests")
 +
 +    parser.add_option("-i", "--initial", action="store_true", default=False, help="only show the first failure in each file")
 +    parser.add_option("--exitfirst", action="store_true", default=False, help="end the test run immediately after the first failure or unexpected exception")
 +    parser.add_option("--force_lib", "--force-lib", action="store_true", default=False, help="do not import anything from the tested file(s)")
 +    parser.add_option("--abspath", action="store_true", default=False, help="print absolute paths rather than relative paths")
 +    parser.add_option("--verbose", action="store_true", default=False, help="print debugging output during the test")
 +    parser.add_option("-d", "--debug", action="store_true", default=False, help="drop into a python debugger when an unexpected error is raised")
 +    parser.add_option("--only-errors", action="store_true", default=False, help="only output failures, not test successes")
 +
 +    parser.add_option("--gdb", action="store_true", default=False, help="run doctests under the control of gdb")
 +    parser.add_option("--valgrind", "--memcheck", action="store_true", default=False,
 +                      help="run doctests using Valgrind's memcheck tool.  The log "
 +                         "files are named sage-memcheck.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +    parser.add_option("--massif", action="store_true", default=False,
 +                      help="run doctests using Valgrind's massif tool.  The log "
 +                         "files are named sage-massif.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +    parser.add_option("--cachegrind", action="store_true", default=False,
 +                      help="run doctests using Valgrind's cachegrind tool.  The log "
 +                         "files are named sage-cachegrind.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +    parser.add_option("--omega", action="store_true", default=False,
 +                      help="run doctests using Valgrind's omega tool.  The log "
 +                         "files are named sage-omega.PID and can be found in " +
 +                         os.path.join(DOT_SAGE, "valgrind"))
 +
 +    parser.add_option("-f", "--failed", action="store_true", default=False,
++=======
+     parser.add_argument("--randorder", type=int, metavar="SEED", help="randomize order of tests")
+     parser.add_argument("--random-seed", dest="random_seed", type=int, metavar="SEED", help="random seed for fuzzing doctests")
+     parser.add_argument("--global-iterations", "--global_iterations", type=int, default=0, help="repeat the whole testing process this many times")
+     parser.add_argument("--file-iterations", "--file_iterations", type=int, default=0, help="repeat each file this many times, stopping on the first failure")
+     parser.add_argument("--environment", type=str, default="sage.repl.ipython_kernel.all_jupyter", help="name of a module that provides the global environment for tests")
+ 
+     parser.add_argument("-i", "--initial", action="store_true", default=False, help="only show the first failure in each file")
+     parser.add_argument("--exitfirst", action="store_true", default=False, help="end the test run immediately after the first failure or unexpected exception")
+     parser.add_argument("--force_lib", "--force-lib", action="store_true", default=False, help="do not import anything from the test
...

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​047379c

fix merge conflict