Use MemoryAllocator in generic graphs; fixes crash

[rws]

Sage on OpenSuSE 42.2 (built from scratch with internal gcc-4.9 and 5.4) crashes on the command Poset().is_incomparable_chain_free(1,1). Reason is there is no check in the SubgraphSearch member functions for an empty graph, so happily unallocated memory is changed in _initialization().

This was discovered because of several failing doctests on OpenSuSE, presumably because of the system's more stringent memory model.

[rws]

New commits:

​6b74031

21828: check for empty graph before de/allocating

[jdemeyer]

It's not really clear to me if adding if self.ng == 0: return in those places is the right thing to do. Why in __cinit__ and __dealloc__ for example? I don't see the problem there. And in _initialize, why should self.stack and self.active not be initialized? If you do the initialization correctly, it should also be possible to remove the if self.ng == 0: return from __next__.

[rws]

Deallocation of tmp_array is also missing.

[rws]

Let's try again differently.

---

New commits:

​5a14f4d

21828: Crash in SubgraphSearch of empty graph

[vdelecroix]

doctest?

[jmantysalo]

Good to fix this. For larger context see #21741.

[jdemeyer]

This seems overly complicated to me...

This looks like the only place where you really need to do something:

self.busy[0] = 1

[jdemeyer]

You may also want to look at src/sage/ext/memory_allocator.pyx to simplify the memory allocations.

[rws]

My Python understanding does not suffice for this. Please someone take over.

[jdemeyer]

What exactly is the problem here? What would be the minimal code to exhibit the problem?

[Konrad127123]

Replying to rws:

Deallocation of tmp_array is also missing.

I've added a fix for this part in #24660 .

[rws]

You mean #24660? As said in comment:15 that is only part of it.

[rws]

Finally I got the handle on this. I'm inserting/leaving some checks for efficiency reasons. Please review, as this makes patchbot fail on OpenSuSE.

---

New commits:

​5def5f4

21828: use MemoryAllocator in generic graphs; fixes crash

[dcoudert]

I don't have OpenSuSE, so I cannot fully test the patch (working for me on OSX).

Could you add a doctest for Poset().is_incomparable_chain_free(1,1) ?

[jdemeyer]

1. MemoryAllocator raises exceptions when out of memory, so the NULL checks are no longer needed.

2. I'm surprised that for 0 < i < self.ng is legal Cython syntax. Cython understands for i in range(1, self.ng) though. To be safe, you may want to add cdef int i.

3. My impression is that self.ng is constant. So I don't understand code of the form

   if self.ng == 0:
      raise StopIteration
   ....
   if self.ng > 0: ...
   

Isn't the latter trivially true?

[git]

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

​8fa9ec7

21828: improvements, doctest

[jdemeyer]

I think that you should still fix the for 0 < i < self.ng: syntax (sorry if my previous comment was not clear on this).

[git]

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

​6612f1e

21828: cosmetics

[dcoudert]

For me this patch is perfectly working, so I give it positive review.

[rws]

Thanks!