Make Parma Polyhedra Library a standard library

[vbraun]

The Parma Polyhedra Library (ppl) is for many workloads the fastest library for polyhedral computations. It is also high-quality code, for example GCC uses it (optionally) to optimize loops.

• ppl has already been widely tested on a multitude of platforms.
• Native C++ with a pure C interface.
• Contains a huge testsuite _and_ passes its own testsuite (in contrast to some other polydedral library that shall remain unnamed)

Official webpage: http://www.cs.unipr.it/ppl/

My plan is to

1. Create a PPL spkg.
2. Write a Cython interface.
3. Base sage.geometry.cone.Cone on PPL instead of Polyhedron/cddlib
4. Split sage.geometry.polyhedra.Polyhedron into an abstract base class and derived classes that use different polyhedral computation libraries.

Current status:

1. My cython wrapper for PPL is attached. It has full doctest coverage and any invalid input is caught and raises ValueError.
2. Is split off into trac #10140.

For convenience I mirrored the reference manual page here: http://www.stp.dias.ie/~vbraun/Sage/html/en/reference/sage/libs/ppl.html

To apply this ticket:

• download the new spkg http://boxen.math.washington.edu/home/jdemeyer/spkg/ppl-0.11.2.spkg
• copy the spkg to $SAGE_ROOT/spkg/standard
• apply attachment: trac_10039_parma_polyhedra_library.patch to the Sage library
• apply attachment: trac_10039_ppl_fix_extremize.patch to the Sage library
• apply attachment: 10039_manifest.patch to the Sage library
• apply attachment: trac_10039_root_repo.patch the sage root repository
• apply attachment: trac_10039_SAGE_LOCAL_bin_repo.patch to the $SAGE_LOCAL/bin repository

CC: @novoselt @jdemeyer @kiwifb

Component: geometry

Keywords: ppl spkg

Author: Volker Braun

Reviewer: Marshall Hampton, Jeroen Demeyer

Merged: sage-4.7.alpha4

Issue created by migration from https://trac.sagemath.org/ticket/10039

[vbraun]

comment:45

Here is the PPL configuration:

./configure --prefix="$SAGE_LOCAL" --with-gmp-prefix="$SAGE_LOCAL" --enable-fpmath=no --enable-coefficients=mpz --enable-interfaces=c++ 

I need the GMP/MPIR based coefficients and C++ interface. PPL supports some tricks to work with floating point numbers as coefficients, but I'm not using that as it obviously comes with restrictions on the allowed coefficients. Also, the PPL Cython wrapper turns off the FPU rounding mode that PPL's floating point arithmetic relies on.

[kiwifb]

comment:46

I still get

**********************************************************************
File "/usr/share/sage/devel/sage/sage/libs/ppl.pyx", line 1271:
    sage: p.maximize( +x )
Expected:
    {'sup_d': 0, 'sup_n': 0, 'bounded': False, 'maximum': False, 'generator': None}
Got:
    {'sup_d': 0, 'sup_n': 0, 'bounded': False, 'maximum': True, 'generator': None}
**********************************************************************
File "/usr/share/sage/devel/sage/sage/libs/ppl.pyx", line 1340:
    sage: p.minimize( -x )
Expected:
    {'minimum': False, 'bounded': False, 'inf_d': 0, 'generator': None, 'inf_n': 0}
Got:
    {'minimum': True, 'bounded': False, 'inf_d': 0, 'generator': None, 'inf_n': 0}

On x86 but not on amd64. I am guessing from the configuration log on my amd64 machine and the configure.ac file that --enable-fpmath=no is the same as the default and enable use of 387 and sse instructions. --enable-coefficients also currently default to mpz, and we enable c++ by default. So it seems all good configuration wise.

[kiwifb]

comment:47

more upsetting. The test pass on my x86-macos set up. I'll will have to check that's not limited to my own old home computer.

[vbraun]

comment:48

387 and SSE instructions are floating point math. Which versions of PPL are you using? Am I right in the assumption that this is only with Gentoo's ppl library and not with my ppl spkg? If yes, can you open a separate ticket for Gentoo overlay bugs?

[kiwifb]

comment:49

ppl is 0.11, same as yours unless you patched it. We don't. For all intent and purpose I am the co-maintainer of sage-on-gentoo by the way. You just asked me to open a bug with myself :) Yes this is not with your ppl spkg, I will have to create a set up to compare results with vanilla sage and see what's different on x86. But just to make my point, we leave enable-fpmath and enable-coefficients to their defaults which happens to be what you choose (unless you can point to something subbtle somewhere else), from configure.ac:

enableval=default
fpmath_may_use_387=yes
fpmath_may_use_sse=yes
AC_MSG_CHECKING([whether to select specific floating point arithmetics])
AC_ARG_ENABLE(fpmath,
  AS_HELP_STRING([--enable-fpmath=INSTRUCTION_SET],
                 [select floating point arithmetics]))
case "${enableval}" in
sse)
  AC_MSG_RESULT(sse)
  OPT_FLAGS="$OPT_FLAGS -msse -mfpmath=sse"
  # The SSE instruction set only supports single precision arithmetics:
  # double and extended precision arithmetics is still done using 387.
  ;;
sse2)
  AC_MSG_RESULT(sse2)
  OPT_FLAGS="$OPT_FLAGS -msse2 -mfpmath=sse"
  # SSE2 still does not support extended precision arithmetics.
  ;;
387)
  AC_MSG_RESULT(387)
  OPT_FLAGS="$OPT_FLAGS -mno-sse -mno-sse2 -mfpmath=387"
  # Note that the -mno-sse* and -mfpmath options are only guaranteed
  # to work with GCC.
  if test x"$GCC" = xyes
  then
    fpmath_may_use_sse=no
  fi
  ;;
sse+387)
  AC_MSG_RESULT(sse+387)
  OPT_FLAGS="$OPT_FLAGS -msse -mfpmath=sse,387"
  ;;
sse2+387)
  AC_MSG_RESULT(sse2+387)
  OPT_FLAGS="$OPT_FLAGS -msse2 -mfpmath=sse,387"
  ;;
default)
  AC_MSG_RESULT(default)
  ;;
no)
  AC_MSG_RESULT(default)
  ;;
*)
  AC_MSG_ERROR([bad value ${enableval} for --enable-fpmath, needs sse, sse2, 387, sse+387, sse2+387, default or no])
  ;;
esac

As you can see just saying "no" leaves you with the same thing as "default" and that is 387 and sse. Same thing for coefficient:

enableval=mpz
AC_MSG_CHECKING([the type of integral values to use as coefficients])
AC_ARG_ENABLE(coefficients,
  AS_HELP_STRING([--enable-coefficients=TYPE],
                 [select the type of the coefficients]))
case "${enableval}" in
native-int8)
  AC_MSG_RESULT([native 8 bits integers])
  coefficient_kind=native
  coefficient_bits=8
  coefficient_mnemonic=nint8
  ;;
native-int16)
  AC_MSG_RESULT([native 16 bits integers])
  coefficient_kind=native
  coefficient_bits=16
  coefficient_mnemonic=nint16
  ;;
native-int32)
  AC_MSG_RESULT([native 32 bits integers])
  coefficient_kind=native
  coefficient_bits=32
  coefficient_mnemonic=nint32
  ;;
native-int64)
  AC_MSG_RESULT([native 64 bits integers])
  coefficient_kind=native
  coefficient_bits=64
  coefficient_mnemonic=nint64
  ;;
checked-int8)
  AC_MSG_RESULT([checked 8 bits integers])
  coefficient_kind=checked
  coefficient_bits=8
  coefficient_mnemonic=int8
  ;;
checked-int16)
  AC_MSG_RESULT([checked 16 bits integers])
  coefficient_kind=checked
  coefficient_bits=16
  coefficient_mnemonic=int16
  ;;
checked-int32)
  AC_MSG_RESULT([checked 32 bits integers])
  coefficient_kind=checked
  coefficient_bits=32
  coefficient_mnemonic=int32
  ;;
checked-int64)
  AC_MSG_RESULT([checked 64 bits integers])
  coefficient_kind=checked
  coefficient_bits=64
  coefficient_mnemonic=int64
  ;;
mpz)
  AC_MSG_RESULT([GMP mpz])
  coefficient_kind=unbounded
  coefficient_bits=0
  coefficient_mnemonic=mpz
  ;;
*)
  AC_MSG_ERROR([bad value ${enableval} for --enable-coefficients, checked-int32, checked-int64, checked-int16, checked-int8, mpz, native-int32, native-int64, native-int16 or native-int8])
  ;;
esac

Again mpz is the default if you don't pass anything.

So unless you have patched these behaviors - and you didn't, we have very similar configurations, we pass

--disable-debugging --disable-optimization --enable-ppl_lpsol --disable-pch --disable-watchdog

Since I have a different result for two different x86 setup I am wondering if the great age of my home machine (close to 8 years) is a factor.

[vbraun]

comment:50

I know that you are doing the sage-on-gentoo, I'm asking you to open a different ticket on the Sage track for the gentoo ebuild issues and stop hijacking this ticket :-P

As far as I know, I'm not using any floating point code in ppl. So your configuration seems to be fine. But clearly your ppl returns a wrong result. Is your compiler/toolchain up to date on your antique computer?

[kiwifb]

comment:51

Replying to @vbraun:

I know that you are doing the sage-on-gentoo, I'm asking you to open a different ticket on the Sage track for the gentoo ebuild issues and stop hijacking this ticket :-P

As far as I know, I'm not using any floating point code in ppl. So your configuration seems to be fine. But clearly your ppl returns a wrong result. Is your compiler/toolchain up to date on your antique computer?

Yes it is (gcc-4.5.2/binutils-2.20.1/glibc-2.11.2). But I will abide to your requests and stop spamming this ticket. I will only abuse it again to post positive reviews (I hope).

[vbraun]

comment:52

I had some sig_on without corresponding sig_off's when exceptions were raised, the updated patch fixes that. Now everything plays nicely with Jeroen' sigon/off debugging patch at #10030.

Marshall, considering that it now builds on t2, how about a positive review? ;-)

[kiwifb]

comment:53

I unfortunately not give a positive review. I tested this again on a vanilla sage-4.6.2.alpha4 (as in _NOT_ sage-on-gentoo) with the latest version of the patch, spkg, install and deps and I still get the same doctest failures. sage -testall didn't report any broken tests before applying the patch. My opinion is that if this gets merged in an alpha release we will see this failure more on 32bit linux.

[vbraun]

comment:54

Can you give more details? Which hardware is it failing on, what is the result of the PPL testsuite (build with SAGE_CHECK=yes), is your gcc configured to use ppl (how is that working out for you), can you reproduce the issue with a supported linux distribution, ...

[vbraun]

comment:55

I've updated the PPL spkg to the new upstream version 0.11.1 and tested it on Fedora 14 i386. It passes all tests on my system, so I'm pretty confident that it works fine on 32bit.

[vbraun]

Description changed:

--- 
+++ 
@@ -12,7 +12,7 @@
 4. Split `sage.geometry.polyhedra.Polyhedron` into an abstract base class and derived classes that use different polyhedral computation libraries.

 Current status:
-1. Spkg can be found here: http://www.stp.dias.ie/~vbraun/Sage/spkg/ppl-0.11.spkg
+1. Spkg can be found here: http://www.stp.dias.ie/~vbraun/Sage/spkg/ppl-0.11.1.spkg
 2. My cython wrapper for PPL is attached. It has full doctest coverage and any invalid input is caught and raises `ValueError`.
 3. Is split off into trac #10140.

[5d2aaf09-c963-473a-bf79-1f742a72700f]

comment:56

Volker - I still can't get this to work on t2, but I think that's because of my Solaris ignorance. How did you build and test on Solaris - in particular, did you ever change your environment variables somehow?

[vbraun]

comment:57

Oops, I accidentally dropped the fix for the newest_version check that is required on t2, see comment:41. Sorry about that.

Updated spkg fixes it and builds on t2.

Marshall: Are you asking about building all of Sage on t2? I don't remember any specific problem there, just source the t2-setup:

. /usr/local/bin/t2-setup
make

If you put stuff into your .profile and it is not picked up you are using a different shell with different initalization files. You can also use a binary distribution, sage-4.6.1-sunos-32bit-5.10-sun4v-SunOS.tar.gz works.

[kiwifb]

comment:58

I noticed that 0.11.2 is out and from the release notes it sounds like you had some wish granted:

Bugfixes
========

o  Fixed the semantics of the `--disable-fpmath' configure option
   (which is equivalent to `--enable-fpmath=no').  It now disables all
   floating point computations and, consequently, all numerical
   abstractions based on floating point numbers.

o  The PPL no longer overwrites the SIGILL signal handler.

o  Minor documentation fixes.

o  Portability improved.

[vbraun]

Description changed:

--- 
+++ 
@@ -12,7 +12,7 @@
 4. Split `sage.geometry.polyhedra.Polyhedron` into an abstract base class and derived classes that use different polyhedral computation libraries.

 Current status:
-1. Spkg can be found here: http://www.stp.dias.ie/~vbraun/Sage/spkg/ppl-0.11.1.spkg
+1. Spkg can be found here: http://www.stp.dias.ie/~vbraun/Sage/spkg/ppl-0.11.2.spkg
 2. My cython wrapper for PPL is attached. It has full doctest coverage and any invalid input is caught and raises `ValueError`.
 3. Is split off into trac #10140.

[vbraun]

comment:59

I updated my ppl spkg to 0.11.2, see the link in the ticket description. Builds and tests correctly on F14 x86_64, i384, and on t2.math.

[5d2aaf09-c963-473a-bf79-1f742a72700f]

comment:60

I'm going to look at this again this week, hopefully can give a positive review soon. I'm going to try to install on some of the skynet machines and do a little more testing. It would be great to get this into sage-4.7.

I just tested on a mac, with your latest package, and I think an error message might have changed. I get the following doctest "failure" (test is expected to fail, just not with this message):

File "/Users/mh/sagestuff/sage-4.7.alpha2/devel/sage-t1/sage/libs/ppl.pyx", line 4124:
    sage: line.divisor()
Expected:
    Traceback (most recent call last):
    ...
    ValueError: Only points and closure points have a divisor.
Got:
    Traceback (most recent call last):
      File "/Users/mh/sagestuff/sage-4.7.alpha2/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/mh/sagestuff/sage-4.7.alpha2/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/mh/sagestuff/sage-4.7.alpha2/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_108[8]>", line 1, in <module>
        line.divisor()###line 4124:
    sage: line.divisor()
      File "ppl.pyx", line 4131, in sage.libs.ppl.Generator.divisor (sage/libs/ppl.cpp:13949)
        mpz_set(c.value, self.thisptr.divisor().get_mpz_t())
    ValueError: PPL::Generator::divisor():
    *this is neither a point nor a closure point.

[vbraun]

comment:62

Hi Marshall,

Sage-4.7.alpha2 hasn't been released yet, you are cheating :-P

It seems like Cython-0.14.1 got smarter and now translates the C++ std::invalid_argument exception into a Python ValueError, while the older Cython only threw a nondescript RuntimeError. So I don't have to catch the exception any more, perfect. Attached patch fixes the doctest, I only removed the try/except block in divisor().

For anybody who is still using Sage-4.6.x: You will encounter one doctest failure but that is harmless.

[vbraun]

Attachment: trac_10039_parma_polyhedra_library.patch.gz

Updated patch

[5d2aaf09-c963-473a-bf79-1f742a72700f]

comment:63

OK, this looks good on OS X, linux, and solaris. I built and tested on the skynet machine "mark", and everything seemed fine except for some doctest errors which all seem related to timeout issues - not surprising perhaps since mark is quite slow and has a load of other processes on it right now. So I'm not sure I would consider those failures blockers for this ticket. The failures for mark are at: http://sage.math.washington.edu/home/mhampton/ppltest2.txt

[5d2aaf09-c963-473a-bf79-1f742a72700f]

comment:64

Sorry, I needed to read the test_executable docs. Clearly these are just timeout issues, and running those doctests with longer values works fine on mark.

I've tested this on a variety of OS X 10.6, linux, and solaris machines now. Hopefully this can be included in an alpha or rc0 of sage-4.7 for wider testing.

[novoselt]

comment:65

Can someone please post step-by-step instructions how to apply it? I tried to install the package (it went fine) and apply the last patch, but when I build I get the error

----------------------------------------------------------
sage: Building and installing modified Sage library files.

Installing c_lib
scons: `install' is up to date.
Updating Cython code....
Traceback (most recent call last):
  File "setup.py", line 859, in <module>
    queue = compile_command_list(ext_modules, deps)
  File "setup.py", line 819, in compile_command_list
    dep_file, dep_time = deps.newest_dep(f)
  File "setup.py", line 726, in newest_dep
    for f in self.all_deps(filename):
  File "setup.py", line 707, in all_deps
    for f in self.immediate_deps(filename):
  File "setup.py", line 689, in immediate_deps
    self._deps[filename] = self.parse_deps(filename)
  File "setup.py", line 679, in parse_deps
    raise IOError, "could not find dependency %s included in %s."%(path, filename)
IOError: could not find dependency ppl.hh included in sage/libs/ppl.pyx.
sage: There was an error installing modified sage library code.

[5d2aaf09-c963-473a-bf79-1f742a72700f]

comment:66

Andrey - that should have worked. Installing the package should put ppl.hh in $SAGE_ROOT/local/include/ - is it there? If the spkg installed OK, I don't know what would be wrong except the error that I sometimes make of working on two different copies of sage.

[novoselt]

comment:67

It is, but I have realized that I didn't install dependencies. I guess I'll install 4.7.alpha1 and try again.

[novoselt]

comment:68

Everything applies smooth now, sorry for the false alarm!

[jdemeyer]

Description changed:

--- 
+++ 
@@ -17,8 +17,3 @@
 3. Is split off into trac #10140.

 For convenience I mirrored the reference manual page here: http://www.stp.dias.ie/~vbraun/Sage/html/en/reference/sage/libs/ppl.html
-
-Dependencies:
-* #10094: cython and c++
-* #9828: Upgrade to Cython 0.13
-* #10233: Incomplete cython search path in `setup.py`

[jdemeyer]

comment:69

Some administrative issues:

1. Now that #9433 is merged, changes to spkg/install and spkg/standard/deps should be made using hg export tip (producing an actual HG changeset for the sage_root repository).
2. Please state clearly which patches have to be applied where.

[vbraun]

Patch to SAGE_ROOT repo

[vbraun]

Attachment: trac_10039_root_repo.patch.gz

Attachment: trac_10039_SAGE_LOCAL_bin_repo.patch.gz

patch to SAGE_LOCAL/bin repo

[vbraun]

Description changed:

--- 
+++ 
@@ -17,3 +17,10 @@
 3. Is split off into trac #10140.

 For convenience I mirrored the reference manual page here: http://www.stp.dias.ie/~vbraun/Sage/html/en/reference/sage/libs/ppl.html
+
+To apply this ticket
+* copy the ppl spkg to `$SAGE_ROOT/spkg/standard`
+* apply `trac_10039_parma_polyhedra_library.patch` to the Sage library
+* apply `trac_10039_root_repo.patch` the sage root repository
+* apply `trac_10039_SAGE_LOCAL_bin_repo.patch` to the `$SAGE_LOCAL/bin` repository
+

[vbraun]

comment:71

The patches are explained in the ticket description.

[vbraun]

comment:72

back to positive review since I only repackaged existing changes.

[jdemeyer]

comment:73

This ticket will also be an interesting test for #9433: adding a new spkg has not been tested before.

[jdemeyer]

Merged: sage-4.7.alpha3

[jdemeyer]

Attachment: 10039_manifest.patch.gz

Patch to MANIFEST.in

[jdemeyer]

Description changed:

--- 
+++ 
@@ -20,7 +20,8 @@

 To apply this ticket
 * copy the ppl spkg to `$SAGE_ROOT/spkg/standard`
-* apply `trac_10039_parma_polyhedra_library.patch` to the Sage library
-* apply `trac_10039_root_repo.patch` the sage root repository
-* apply `trac_10039_SAGE_LOCAL_bin_repo.patch` to the `$SAGE_LOCAL/bin` repository
-
+* apply [attachment: trac_10039_parma_polyhedra_library.patch](https://github.com/sagemath/sage-prod/files/10651046/trac_10039_parma_polyhedra_library.patch.gz) to the Sage library
+* apply [attachment: 10039_manifest.patch](https://github.com/sagemath/sage-prod/files/10651049/10039_manifest.patch.gz) to the Sage library
+* apply [attachment: trac_10039_root_repo.patch](https://github.com/sagemath/sage-prod/files/10651047/trac_10039_root_repo.patch.gz) the sage root repository
+* apply [attachment: trac_10039_SAGE_LOCAL_bin_repo.patch](https://github.com/sagemath/sage-prod/files/10651048/trac_10039_SAGE_LOCAL_bin_repo.patch.gz) to the `$SAGE_LOCAL/bin` repository
+ 

[jdemeyer]

comment:77

On OS X 10.6 (both 32-bit and 64-bit):

sage -t -long  -force_lib devel/sage/sage/libs/ppl.pyx
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 4178:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_110[8]>", line 1, in <module>
        (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest###line 4178:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/lib/python/site-packages/sage/tests/cmdline.py", line 366, in test_executable
        raise RuntimeError("timeout in test_executable()")
    RuntimeError: timeout in test_executable()
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 4179:
    sage: print err
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_110[9]>", line 1, in <module>
        print err###line 4179:
    sage: print err
    NameError: name 'err' is not defined
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 4444:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_124[8]>", line 1, in <module>
        (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest###line 4444:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/lib/python/site-packages/sage/tests/cmdline.py", line 366, in test_executable
        raise RuntimeError("timeout in test_executable()")
    RuntimeError: timeout in test_executable()
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 4445:
    sage: print err
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_124[9]>", line 1, in <module>
        print err###line 4445:
    sage: print err
    NameError: name 'err' is not defined
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 5056:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_149[8]>", line 1, in <module>
        (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest###line 5056:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/lib/python/site-packages/sage/tests/cmdline.py", line 366, in test_executable
        raise RuntimeError("timeout in test_executable()")
    RuntimeError: timeout in test_executable()
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 5057:
    sage: print err
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_149[9]>", line 1, in <module>
        print err###line 5057:
    sage: print err
    NameError: name 'err' is not defined
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 5293:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_161[8]>", line 1, in <module>
        (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest###line 5293:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/lib/python/site-packages/sage/tests/cmdline.py", line 366, in test_executable
        raise RuntimeError("timeout in test_executable()")
    RuntimeError: timeout in test_executable()
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 5294:
    sage: print err
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_161[9]>", line 1, in <module>
        print err###line 5294:
    sage: print err
    NameError: name 'err' is not defined
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 5572:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_176[5]>", line 1, in <module>
        (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest###line 5572:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/lib/python/site-packages/sage/tests/cmdline.py", line 366, in test_executable
        raise RuntimeError("timeout in test_executable()")
    RuntimeError: timeout in test_executable()
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 5573:
    sage: print err
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_176[6]>", line 1, in <module>
        print err###line 5573:
    sage: print err
    NameError: name 'err' is not defined
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 5822:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_189[5]>", line 1, in <module>
        (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest###line 5822:
    sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd]);   # indirect doctest
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/lib/python/site-packages/sage/tests/cmdline.py", line 366, in test_executable
        raise RuntimeError("timeout in test_executable()")
    RuntimeError: timeout in test_executable()
**********************************************************************
File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 5823:
    sage: print err
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/buildbot/build/sage/bsd-1/bsd_full/build/sage-4.7.alpha3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_189[6]>", line 1, in <module>
        print err###line 5823:
    sage: print err
    NameError: name 'err' is not defined
**********************************************************************

Note the default timeout of test_executable() is 10 seconds, which might simply be too short.

[jdemeyer]

Changed merged from sage-4.7.alpha3 to none

[jdemeyer]

comment:78

On RHEL 5.3-64 (cleo), SUSE ES10-64 (iras), OpenSolaris 06.2009-32 (hawk), SunOS 5.10-32 (t2):

File "/scratch/buildbot/sage/t2-1/t2_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 1413:
    sage: p.minimize( -x )
Expected:
    {'minimum': False, 'bounded': False, 'inf_d': 0, 'generator': None, 'inf_n': 0}
Got:
    {'minimum': True, 'bounded': False, 'inf_d': 0, 'generator': None, 'inf_n': 0}

[jdemeyer]

comment:79

On SunOS 5.10-32 (t2), OpenSolaris 06.2009-32 (hawk):

File "/scratch/buildbot/sage/t2-1/t2_full/build/sage-4.7.alpha3/devel/sage-main/sage/libs/ppl.pyx", line 1342:
    sage: p.maximize( +x )
Expected:
    {'sup_d': 0, 'sup_n': 0, 'bounded': False, 'maximum': False, 'generator': None}
Got:
    {'sup_d': 0, 'sup_n': 0, 'bounded': False, 'maximum': True, 'generator': None}

[jdemeyer]

comment:80

See #11100 for the timeout problem.

[vbraun]

Description changed:

--- 
+++ 
@@ -21,6 +21,7 @@
 To apply this ticket
 * copy the ppl spkg to `$SAGE_ROOT/spkg/standard`
 * apply [attachment: trac_10039_parma_polyhedra_library.patch](https://github.com/sagemath/sage-prod/files/10651046/trac_10039_parma_polyhedra_library.patch.gz) to the Sage library
+* apply [attachment: trac_10039_ppl_fix_extremize.patch](https://github.com/sagemath/sage-prod/files/10651051/trac_10039_ppl_fix_extremize.patch.gz) to the Sage library
 * apply [attachment: 10039_manifest.patch](https://github.com/sagemath/sage-prod/files/10651049/10039_manifest.patch.gz) to the Sage library
 * apply [attachment: trac_10039_root_repo.patch](https://github.com/sagemath/sage-prod/files/10651047/trac_10039_root_repo.patch.gz) the sage root repository
 * apply [attachment: trac_10039_SAGE_LOCAL_bin_repo.patch](https://github.com/sagemath/sage-prod/files/10651048/trac_10039_SAGE_LOCAL_bin_repo.patch.gz) to the `$SAGE_LOCAL/bin` repository

[vbraun]

comment:81

I finally got the problem with the maximize/minimize doctest failure. If the linear function is not bounded on the polyhedron then it doesn't make sense to ask for whether its a maximum or minimum. And PPL then does not return a consistent value for the corresponding field.

In the attached patch I changed return value of the maximize/minimize methods to only return {'bounded':False} if the linear program is unbounded, since all other dictionary entries are not well-defined in that case. If the linear program is bounded then the returned dictionary is the same as before and contains information about the sup/inf value, whether it is a maximum, and where it is attained.

The new patch trac_10039_ppl_fix_extremize.patch needs to be applied on top of trac_10039_parma_polyhedra_library.patch, see also the ticket description. The new patch needs review.

[kiwifb]

comment:82

That's good news and that wasn't just me then! I have my hands full at the moment so I won't be able to review it quickly but I am sure you have another reviewer around :)

[jdemeyer]

Changed reviewer from Marshall Hampton to Marshall Hampton, Jeroen Demeyer

[jdemeyer]

comment:83

New patch looks good to me. Still needs to be tested on the buildbots, but positive review in the hope that everything works fine.

[jdemeyer]

comment:84

Volker, you just need to put a proper commit message on your patch...

[vbraun]

Attachment: trac_10039_ppl_fix_extremize.2.patch.gz

Updated patch

[vbraun]

Attachment: trac_10039_ppl_fix_extremize.patch.gz

Updated patch