Optional package lrs-4.2b.p1.spkg needs updating

[yzh]

The current Sage optional package lrs refers to the version 4.2b released on 2006.2.14. A few bugs have been reported and fixed since then. In particular, I encountered a bug when calling the redund function provided by lrs-4.2b.p1.spkg to an H-representation input file which contains redundant linearities. The latest version lrslib-051.tar.gz available at ​http://cgm.cs.mcgill.ca/~avis/C/lrs.html solves the problem and is much faster.

package: ​http://cgm.cs.mcgill.ca/~avis/C/lrslib/lrslib-051.tar.gz

[mkoeppe]

As a first step, I have imported the old-style spkg lrs-4.2b.p1

I called the new-style spkg "lrslib" -- that's the current name of the upstream packages.

---

New commits:

​29405f6

Import old-style spkg lrs-4.2b.p1

[ncohen]

Hellooooooo,

• You cannot 'just rename' the package: there are many doctests flagged with "optional - lrs" (which are only tested if 'lrs' is installed), and if you rename the package but not those doctests then they will not be tested as they should. You will find them in three files:

  game_theory/normal_form_game.py
  game_theory/parser.py
  geometry/polyhedron/base.py
  

• A ticket that updates a package must contain a direct url toward the archive that is to be added (for the release manager who will have to merge the ticket)

• Do you know what are the differences between lrs and lrslib (if any)? It seems that the author's website still lists 'lrs' as something different from 'lrslib'.

• You can drop the "Changelog" section of SPKG.txt. That's because we now have the history in the main git tree.

Nathann

[jdemeyer]

@ncohen: note that the ticket was not set to "needs_review", so I assume that the author is just still working on it.

[ncohen]

@ncohen: note that the ticket was not set to "needs_review", so I assume that the author is just still working on it.

Yepyep. I chose to interpret as "needs_review" the fact that I was added in Cc of this ticket right after a commit was pushed.

[mkoeppe]

Thanks, Nathann, for your helpful comments.

As far as I know, lrs has, since version 4.0 (2000), only been released in the form of lrslib. Since that version, the upstream tarball has always been called lrslib-VERSION.tar.gz, where 4.0 is rendered as 040 and 4.2b as 042b etc. See ​https://web.archive.org/web/20140506162045/http://cgm.cs.mcgill.ca/~avis/C/lrslib/archive/ The website is indeed a bit unclear.

I'll update the doctests and remove the changelog.

[git]

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

​8a2e029	Complete converting old-style spkg lrs to new-style spkg lrslib
​6a7560a	Change doctests from optional - lrs' to 'optional - lrslib'

[mkoeppe]

Using historical tarball lrslib-042b; some tests fail. I will investigate.

[git]

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

​eea8d7a	Update checksum for lrslib-042b from 30-Oct-2006
​e20240a	Add spkg type

[mkoeppe]

Turns out that lrslib-042b.tar.gz was retroactively changed in 2009. The 2009 version fails Sage's doctests. The version available at ​https://web.archive.org/web/20080606032009/http://cgm.cs.mcgill.ca/~avis/C/lrslib/lrslib-042b.tar.gz (time stamp 30-Oct-2006) is better and is identical to the version used by the old spkg. This passes the doctests.

Update: lrslib-043.tar.gz has the same doctest failures.

 sage -t src/sage/game_theory/parser.py
**********************************************************************
File "src/sage/game_theory/parser.py", line 155, in sage.game_theory.parser.Parser.format_lrs
Failed example:
    lrs_output[5:-4]  # optional - lrslib
Expected:
    ['\n', '***** 4 4 rational\n', '2  0  1  2 \n', '1  1/2  1/2 -2 \n', '\n', '2  0  1  2 \n', '1  0  1 -2 \n', '\n', '*Number of equilibria found: 2\n', '*Player 1: vertices=3 bases=3 pivots=5\n', '*Player 2: vertices=2 bases=1 pivots=6\n']
Got:
    ['\n',
     '***** 4 4 rational\n',
     '2  0  1  2 \n',
     '1  1/2  1/2 -2 \n',
     '\n',
     '2  0  1  2 \n',
     '1  0  1 -2 \n',
     '\n',
     '*Number of equilibria found: 2\n',
     '*Player 1: vertices=3 bases=3 pivots=5\n']
**********************************************************************
File "src/sage/game_theory/parser.py", line 185, in sage.game_theory.parser.Parser.format_lrs
Failed example:
    print lrs_output[5:-4]  # optional - lrslib
Expected:
    ['\n', '***** 5 5 rational\n', '2  0  1/6  5/6  10/3 \n', '2  1/7  0  6/7  23/7 \n', '1  1/3  2/3  0  1 \n', '\n', '2  0  0  1  5 \n', '1  1  0  0  9 \n', '\n', '2  1  0  0  5 \n', '1  0  1  0  6 \n', '\n', '*Number of equilibria found: 4\n', '*Player 1: vertices=6 bases=7 pivots=10\n', '*Player 2: vertices=4 bases=2 pivots=14\n']
Got:
    ['\n', '***** 5 5 rational\n', '2  0  1/6  5/6  10/3 \n', '2  1/7  0  6/7  23/7 \n', '1  1/3  2/3  0  1 \n', '\n', '2  0  0  1  5 \n', '1  1  0  0  9 \n', '\n', '2  1  0  0  5 \n', '1  0  1  0  6 \n', '\n', '*Number of equilibria found: 4\n', '*Player 1: vertices=6 bases=7 pivots=10\n']
**********************************************************************
1 item had failures:
   2 of  36 in sage.game_theory.parser.Parser.format_lrs
    [58 tests, 2 failures, 0.13 s]
----------------------------------------------------------------------
sage -t src/sage/game_theory/parser.py  # 2 doctests failed
----------------------------------------------------------------------
Total time for all tests: 7.3 seconds
    cpu time: 6.4 seconds
    cumulative wall time: 6.9 seconds
egret-2:~/s/sage/sage-develop (t/18127/optional_package_lrs_4_2b_p1_spkg_needs_updating *)$ sage -t --optional=sage,lrslib src/sage/geometry/polyhedron
too few successful tests, not using stored timings
Running doctests with ID 2015-06-14-15-28-49-379c9269.
Git branch: t/18127/optional_package_lrs_4_2b_p1_spkg_needs_updating
Using --optional=lrslib,sage
Doctesting 23 files.
sage -t src/sage/geometry/polyhedron/__init__.py
    [0 tests, 0.00 s]
sage -t src/sage/geometry/polyhedron/all.py
    [0 tests, 0.00 s]
sage -t src/sage/geometry/polyhedron/backend_cdd.py
    [40 tests, 0.33 s]
sage -t src/sage/geometry/polyhedron/backend_field.py
    [37 tests, 0.58 s]
sage -t src/sage/geometry/polyhedron/backend_ppl.py
    [27 tests, 0.11 s]
sage -t src/sage/geometry/polyhedron/base.py
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 3392, in sage.geometry.polyhedron.base.Polyhedron_base.volume
Failed example:
    P5.volume(engine='lrs') #optional - lrslib
Exception raised:
    Traceback (most recent call last):
      File "/Users/mkoeppe/cvs/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/mkoeppe/cvs/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.base.Polyhedron_base.volume[8]>", line 1, in <module>
        P5.volume(engine='lrs') #optional - lrslib
      File "sage/misc/cachefunc.pyx", line 1896, in sage.misc.cachefunc.CachedMethodCaller.__call__ (/Users/mkoeppe/cvs/sage/src/build/cythonized/sage/misc/cachefunc.c:11432)
        w = self._cachedmethod._instance_call(self._instance, *args, **kwds)
      File "sage/misc/cachefunc.pyx", line 2552, in sage.misc.cachefunc.CachedMethod._instance_call (/Users/mkoeppe/cvs/sage/src/build/cythonized/sage/misc/cachefunc.c:14878)
        return self._cachedfunc.f(inst, *args, **kwds)
      File "/Users/mkoeppe/cvs/sage/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.py", line 3396, in volume
        return self._volume_lrs(**kwds)
      File "/Users/mkoeppe/cvs/sage/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.py", line 3346, in _volume_lrs
        raise ValueError("lrs did not return a volume")
    ValueError: lrs did not return a volume
**********************************************************************
1 item had failures:
   1 of  10 in sage.geometry.polyhedron.base.Polyhedron_base.volume
    [635 tests, 1 failure, 23.10 s]

[git]

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

​7e3537e	game_theory/parser.py: Make a brittle doctest a bit more robust
​b1d3405	Update doctests for volume computation with lrs.
​f8b1ab3	Update to lrslib-051

[mkoeppe]

Done with updating the package; needs review now.

[yzh]

Replying to mkoeppe:

Done with updating the package; needs review now.

Thanks a lot! The function redund from the updated package lrslib-051 succeeded on the bug example that I encountered with lrslib-042b previously.

[jdemeyer]

My experience is that a simple hand-written makefile for building libraries is not portable. It might work on one particular operating system, but almost certainly not an all.

So I think you should use autotools (autoconf + automake + libtool) to build the package (or make the package "experimental" such that it's explicit that it might not work).

[ncohen]

I just replaced the url by the 'official one', given by the software's author. The hash is the same, so no problem ahead.

He is now aware of the 404 error on his 'download' link, and should get it fixed soon.

[ncohen]

Helloooooooooo,

Instead of a full copy of the files, the patches/ folder usually contains... patches. Could you only keep .patch files in there?

I will send an email to the author in a second about an autotools versions.

Nathann

[kcrisman]

Cc:ing a few folks who will want to know about any changes in game theory tests so as to avoid conflicts during GSOC.

[vinceknight]

Adding James also.

[git]

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

​06bcecd

Use patch to patch the makefile

[ncohen]

I got several errors when installing this package. The log follows

~$ sage -f lrslib
Found local metadata for lrslib-051
Using cached file /home/ncohen/.Sage/upstream/lrslib-051.tar.gz
lrslib-051
====================================================
Setting up build directory for lrslib-051
Finished set up
****************************************************
Host system:
Linux weightless 3.16.0-4-amd64 #1 SMP Debian 3.16.7-ckt11-1 (2015-05-24) x86_64 GNU/Linux
****************************************************
C compiler: gcc
C compiler version:
Using built-in specs.
COLLECT_GCC=/home/ncohen/.Sage/local/bin/gcc
COLLECT_LTO_WRAPPER=/home/ncohen/.Sage/local/libexec/gcc/x86_64-unknown-linux-gnu/4.9.2/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ../src/configure --prefix=/home/ncohen/.Sage/local --with-local-prefix=/home/ncohen/.Sage/local --with-gmp=/home/ncohen/.Sage/local --with-mpfr=/home/ncohen/.Sage/local --with-mpc=/home/ncohen/.Sage/local --with-system-zlib --disable-multilib --disable-nls --enable-languages=c,c++,fortran --disable-libitm  
Thread model: posix
gcc version 4.9.2 (GCC) 
****************************************************
cp: cannot stat 'patches/makefile': No such file or directory
gcc -c -O3 -DLRS_QUIET -DTIMES -DSIGNALS -DGMP -o lrslib-GMP.o lrslib.c
gcc -c -O3 -DLRS_QUIET -DTIMES -DSIGNALS -DGMP -o lrsgmp-GMP.o lrsgmp.c
ar r liblrsgmp.a lrslib-GMP.o lrsgmp-GMP.o
ar: creating liblrsgmp.a
ranlib liblrsgmp.a
make -j4 LRSGMPLIB=liblrsgmp.a all
make[1]: warning: -jN forced in submake: disabling jobserver mode.
make[1]: Entering directory '/home/ncohen/.Sage/local/var/tmp/sage/build/lrslib-051/src'
gcc -c -O3 -DLRS_QUIET -DTIMES -DSIGNALS -DGMP -o 2nash-GMP.o 2nash.c
gcc -c -O3 -DLRS_QUIET -DTIMES -DSIGNALS -DGMP -o lrs-GMP.o lrs.c
gcc -O3 -DLRS_QUIET -DTIMES -DSIGNALS -DLONG -o lrs1 lrs.c lrslib.c lrslong.c
gcc -c -O3 -DLRS_QUIET -DTIMES -DSIGNALS -DGMP -o nash-GMP.o nash.c
gcc -c -O3 -DLRS_QUIET -DTIMES -DSIGNALS -DGMP -o redund-GMP.o redund.c
gcc -O3 -DLRS_QUIET -DTIMES -DSIGNALS -DLONG -o redund1 redund.c lrslib.c lrslong.c
gcc -O3 -DLRS_QUIET -DTIMES -DSIGNALS -o setnash setupnash.c lrslib.c lrsmp.c
gcc -O3 -DLRS_QUIET -DTIMES -DSIGNALS -o setnash2 setupnash2.c lrslib.c lrsmp.c
gcc 2nash-GMP.o -L. -llrsgmp -L/usr/lib  -lgmp -o 2nash
gcc lrs-GMP.o -L. -llrsgmp -L/usr/lib  -lgmp -o lrs
gcc nash-GMP.o -L. -llrsgmp -L/usr/lib  -lgmp -o nash
gcc redund-GMP.o -L. -llrsgmp -L/usr/lib  -lgmp -o redund
rm 2nash-GMP.o lrs-GMP.o nash-GMP.o redund-GMP.o
make[1]: Leaving directory '/home/ncohen/.Sage/local/var/tmp/sage/build/lrslib-051/src'
make -j4 LRSGMPLIB=liblrsgmp.a all
mkdir -p /usr/local/bin
make[1]: warning: -jN forced in submake: disabling jobserver mode.
install -t /usr/local/bin 2nash lrs lrs1 nash redund redund1 setnash setnash2
install: cannot create regular file '/usr/local/bin/2nash': Permission denied
install: cannot create regular file '/usr/local/bin/lrs': Permission denied
install: cannot create regular file '/usr/local/bin/lrs1': Permission denied
install: cannot create regular file '/usr/local/bin/nash': Permission denied
install: cannot create regular file '/usr/local/bin/redund': Permission denied
install: cannot create regular file '/usr/local/bin/redund1': Permission denied
install: cannot create regular file '/usr/local/bin/setnash': Permission denied
install: cannot create regular file '/usr/local/bin/setnash2': Permission denied
makefile:119: recipe for target 'install-common' failed
make: *** [install-common] Error 1
make: *** Waiting for unfinished jobs....
make[1]: Entering directory '/home/ncohen/.Sage/local/var/tmp/sage/build/lrslib-051/src'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/home/ncohen/.Sage/local/var/tmp/sage/build/lrslib-051/src'
Error installing lrs

real	0m3.036s
user	0m10.768s
sys	0m0.208s
************************************************************************
Error installing package lrslib-051
************************************************************************
Please email sage-devel (http://groups.google.com/group/sage-devel)
explaining the problem and including the relevant part of the log file
  /home/ncohen/.Sage/logs/pkgs/lrslib-051.log
Describe your computer, operating system, etc.
If you want to try to fix the problem yourself, *don't* just cd to
/home/ncohen/.Sage/local/var/tmp/sage/build/lrslib-051 and type 'make' or whatever is appropriate.
Instead, the following commands setup all environment variables
correctly and load a subshell for you to debug the error:
  (cd '/home/ncohen/.Sage/local/var/tmp/sage/build/lrslib-051' && '/home/ncohen/.Sage/sage' --sh)
When you are done debugging, you can type "exit" to leave the subshell.
************************************************************************

Note in particular the

cp: cannot stat 'patches/makefile': No such file or directory

[mkoeppe]

sorry, forgot to commit 1 file

[git]

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

​2552476

Fix last change

[mkoeppe]

For those interested in software archaeology, I have created a github repository that tracks the contents of the historical tarballs of lrslib since version 4.0 (040): ​https://github.com/mkoeppe/lrslib

[git]

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

​c009389

Add description to patch

[mkoeppe]

Needs review again

[ncohen]

Hello !

The package was installed correctly with this new branch, but several doctests were breaking. There are leftovet 'lrs' in the code, which you probably do not see if you have installed the former version of the 'lrs' spkg on your computer. I fixed them in a commit at public/18127.

With this commit, the branch is (in my opinion) ready to go.

For those who are not in Cc of the mail exchange with the package's author: he told us that his makefile was custom-made to work with polymake, and that it had been tested on "several OS/architecture without problem". The changes we make to their makefile are very simple:

• change harcoded paths to include SAGE_ROOT
• replace 'install' by 'cp'

About autotool: they see no point in doing it themselves, but they would not mind such a contribution.

As this package has been optional for a long while now, I believe that we can keep it as it is for the moment, and autotoolize it later if we need it.

What about you, Jeroen?

Nathann

P.S.: The 'download' link on the author's website is now fixed P.S2: One of the authors 'would not mind' an autotoolized build system, while the other would prefer to update his makefile if that's possible, whenever we meet a problem on some architecture.

[jdemeyer]

I would prefer to make minimal changes to the makefile, I think these changes can be removed:

+### modified for Sage
+

and the commenting-out of the unused targets plrs and plrsmp.

[jdemeyer]

There are still some references to a lrs package in src/sage/game_theory/normal_form_game.py:

* ``'lrs'``: Reverse search vertex enumeration for 2 player games. This
  algorithm uses the optional 'lrs' package. To install it type ``sage -i
  lrslib`` at the command line. For more information see [A2000]_.

Note that if no algorithm argument is passed then the default will be
selected according to the following order (if the corresponding package is
installed):

    1. ``'lrs'`` (requires 'lrs')

        if not algorithm:
            if is_package_installed('lrs'):
                algorithm = "lrs"
            else:
                algorithm = "enumeration"

        if algorithm == "lrs":
            if not is_package_installed('lrs'):
                raise NotImplementedError("lrs is not installed")

[ncohen]

There are still some references to a lrs package in src/sage/game_theory/normal_form_game.py:

I fixed those in public/18127 (see 32).

Nathann

[jdemeyer]

Also, don't print exceptions, but raise them:

print 'You must install the optional lrslib package ' \
    'for this function to work'

[jdemeyer]

Replying to ncohen:

I fixed those in public/18127 (see 32).

But the branch under review is u/mkoeppe/optional_package_lrs_4_2b_p1_spkg_needs_updating. If you want a different branch to be reviewed, then change the branch...

[ncohen]

But the branch under review is u/mkoeppe/optional_package_lrs_4_2b_p1_spkg_needs_updating. If you want a different branch to be reviewed, then change the branch...

I do not change the branch of somebody else's ticket. The author will do that if he agrees with the changes.

[jdemeyer]

Replying to ncohen:

it had been tested on "several OS/architecture without problem"

I see that we are only using the executable, not the library. That's acceptable for now, but I bet that there will be build problems if we ever decide to use lrslib as a library, without using libtool.

[jdemeyer]

Replying to ncohen:

The author will do that if he agrees with the changes.

Fine, but then don't set the ticket to needs_review.

[dimpase]

Well...

[jdemeyer]

See 33 and 36

[jdemeyer]

Also, replace

is_package_installed('lrslib') != True

by

not is_package_installed('lrslib')

[kcrisman]

There are still some references to a lrs package in src/sage/game_theory/normal_form_game.py:

Regardless of the branch involved, it would be nice if the folks actively developing that file could have a chance to comment. Or Dima, do you have any comments from the GSOC group as to preferred name etc.?

[vinceknight]

Hi all, thanks again for pinging us here. James, Tobenna and I have been following along and can't say that we have strong feelings either way. Depending on which branch gets merged in to develop first we should be able to adjust.

As James said:

'As long as everything gets changed and it all works'

[git]

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

​32e2f2e

fixed as requested in comments #33 and #36

[dimpase]

Replying to git:

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

​32e2f2e

fixed as requested in comments #33 and #36

and comment 43 too.

[jdemeyer]

If it passes make ptestlong (I haven't checked), this is good for me.

[dimpase]

Replying to jdemeyer:

If it passes make ptestlong (I haven't checked), this is good for me.

it does.

[mkoeppe]

Thanks, Nathann and Dima, for your fixes, Jeroen for the positive review, and everyone for their comments and their help with the ticket.

Matthias

[vbraun]

sage -t --long src/sage/geometry/polyhedron/base.py
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 3405, in sage.geometry.polyhedron.base.Polyhedron_base.volume
Failed example:
    I.volume(engine='lrs')
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.base.Polyhedron_base.volume[11]>", line 1, in <module>
        I.volume(engine='lrs')
      File "sage/misc/cachefunc.pyx", line 1896, in sage.misc.cachefunc.CachedMethodCaller.__call__ (/Users/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/misc/cachefunc.c:11437)
        w = self._cachedmethod._instance_call(self._instance, *args, **kwds)
      File "sage/misc/cachefunc.pyx", line 2552, in sage.misc.cachefunc.CachedMethod._instance_call (/Users/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/misc/cachefunc.c:14883)
        return self._cachedfunc.f(inst, *args, **kwds)
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.py", line 3409, in volume
        return self._volume_lrs(**kwds)
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.py", line 3319, in _volume_lrs
        raise NotImplementedError('You must install the optional lrslib package '
    NotImplementedError: You must install the optional lrslib package for this function to work
**********************************************************************
1 item had failures:
   1 of  13 in sage.geometry.polyhedron.base.Polyhedron_base.volume
    [637 tests, 1 failure, 28.11 s]

[git]

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

​c0ebfe6

Add a missing "#optional - lrslib"