canonicalize segfaulting

[kylematoba]

In the below, good functions run cleanly and prob functions signal 11: SIGSEGV. The same happens with for rational arithmetic. Python 3.7.4 on OSX, pip installed with GMP. pycddlib 2.1.0.

import numpy as np

import cdd

def prob1():
    h = np.array([[1, 0, 1],
                  [1, 1, 0]])

    h_eq = np.array([[1, .5, 0]])
    f_cdd = cdd.Matrix(h, number_type="float")
    f_cdd.rep_type = cdd.RepType.INEQUALITY
    p = cdd.Polyhedron(f_cdd)
    g = p.get_generators()
    g.canonicalize()

    f_cdd.extend(h_eq, True)

    p = cdd.Polyhedron(f_cdd)
    g = p.get_generators()
    g.canonicalize()

def good1():
    h = np.array([[1, 0, 1],
                  [1, 1, 0]])

    f_cdd = cdd.Matrix(h, number_type="float")
    f_cdd.rep_type = cdd.RepType.INEQUALITY
    p = cdd.Polyhedron(f_cdd)
    g = p.get_generators()
    g.canonicalize()

    p = cdd.Polyhedron(f_cdd)
    g = p.get_generators()
    g.canonicalize()

def prob2():
    v_one_side = np.array([[1, 1, 1],
                           [1, 0, 1],
                           [1, 1, 0]])
    v = np.vstack([v_one_side, -1 * v_one_side])
    f_cdd = cdd.Matrix(v, number_type="float")
    f_cdd.rep_type = cdd.RepType.GENERATOR

    p = cdd.Polyhedron(f_cdd)
    i = p.get_inequalities()
    i.canonicalize()

def good2():
    v_one_side = np.array([[1, 1, 1],
                           [1, 0, 1],
                           [1, 1, 0]])
    v = v_one_side
    f_cdd = cdd.Matrix(v, number_type="float")
    f_cdd.rep_type = cdd.RepType.GENERATOR

    p = cdd.Polyhedron(f_cdd)
    i = p.get_inequalities()
    i.canonicalize()

if __name__ == "__main__":
    # prob1()
    # prob2()
    good1()
    # good2()

[mcmtroffaes]

Thanks for reporting. It looks like you might be triggering a bug in cddlib since it only segfaults on particular inputs. Do you get segfaults as well if you use cddlib directly (rather than via Python)?

[kylematoba]

Sorry for not better recognising what was going on -- in both of the prob functions above, the problem is that the thing you are trying to canonicalise is R^n. Here is much more minimal example:

import numpy as np

import cdd

def prob1():
    a = np.zeros((0, 3))
    f_cdd = cdd.Matrix(a, number_type="float")
    f_cdd.rep_type = cdd.RepType.INEQUALITY
    f_cdd.canonicalize()

if __name__ == "__main__":
    prob1()

The principle of least astonishment would say that canonicalising vacuous system of inequalities would deliver the input unchanged, and indeed this is what cdd seems to be doing. If I run

#include <assert.h>
#include <stdio.h>

#include <setoper.h>
#include <cdd.h>

int main(int argc, char *argv[]){
    dd_MatrixPtr h;

    dd_rowset impl_linset;
    dd_rowset redset;
    dd_rowindex newpos;
    dd_ErrorType error = dd_NoError;
    dd_boolean success_h;

    dd_set_global_constants();

    h=dd_CreateMatrix(0, 3);
    h->representation=dd_Inequality;

    dd_WriteMatrix(stdout, h);

    success_h = dd_MatrixCanonicalize(&h, &impl_linset, &redset, &newpos, &error);
    assert(success_h);

    dd_WriteMatrix(stdout, h);

    dd_FreeMatrix(h);
    dd_free_global_constants();
    return 0;
}

I get:

/Users/kylematoba/Documents/cddlib/cmake-build-debug/test_canonicalize
H-representation
begin
 0 3 real
end
H-representation
begin
 0 3 real
end

Process finished with exit code 0

[mcmtroffaes]

Thanks for minimizing the test case and for confirming that the problem is indeed on pycddlib's end. I'll see if I can figure out what's causing this...

[mcmtroffaes]

Can I ask you if you get a segfault in C if you also properly free the sets allocated by dd_MatrixCanonicalize, i.e. with

set_free(impl_linset)
set_free(redset)
free(newpos)

[kylematoba]

No, freeing everything with

    dd_FreeMatrix(h);
    set_free(impl_linset);
    set_free(redset);
    free(newpos);

    dd_free_global_constants();

does not segfault for me.

I'm on a recent mac, FWIW, using /Library/Developer/CommandLineTools/usr/bin/cc.

[mcmtroffaes]

Ok, thanks for testing. I'll try to put this through valgrind and gdb to see where the problem is.

[mcmtroffaes]

It's been a long time but I do have an update: oddly, the canonicalization functions for implicit linearities and redundant inequalities (which are now wrapped as well in the develop branch), when run by themselves, don't crash when the space is R^n. So, I've been looking hard through the code due and cannot rule out that cddlib itself is doing something that causes a random crash, likely an non-initialized pointer somewhere which only triggers on some systems/compilers/situations/... I've addressed one obvious culprit (there's a PR for it on cddlib upstream) but there are likely others.

The biggest problem I have now is that I cannot reproduce this anymore on my current linux system. It still pops up on continuous integration testing... but only if I build pycddlib against the system cddlib libraries, which I cannot patch... Very frustrating!