Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

IntegerVectorsModPermutationGroup crashes on empty domain #36681

Closed
2 tasks done
jukkakohonen opened this issue Nov 9, 2023 · 5 comments · Fixed by #36814
Closed
2 tasks done

IntegerVectorsModPermutationGroup crashes on empty domain #36681

jukkakohonen opened this issue Nov 9, 2023 · 5 comments · Fixed by #36814
Assignees
@jukkakohonen
Labels
t: bug

Comments

@jukkakohonen
Copy link
Contributor

Steps To Reproduce

In SageMath version 9.0, Release Date: 2020-01-01, run the following:

sage: P=PermutationGroup([],domain=[])                                          
sage: V=IntegerVectorsModPermutationGroup(P, sum=1)                             
sage: V.cardinality()

Expected Behavior

The cardinality should be zero.

The domain is empty, so we are counting empty integer vectors whose sum is 1. There are no such vectors.

Actual Behavior

SageMath crashes with the following dump.

------------------------------------------------------------------------
/usr/lib/python3/dist-packages/cysignals/signals.cpython-38-x86_64-linux-gnu.so(+0x8154)[0x7ff63a15a154]
/usr/lib/python3/dist-packages/cysignals/signals.cpython-38-x86_64-linux-gnu.so(+0x8329)[0x7ff63a15a329]
/usr/lib/python3/dist-packages/cysignals/signals.cpython-38-x86_64-linux-gnu.so(+0xad5f)[0x7ff63a15cd5f]
/lib/x86_64-linux-gnu/libc.so.6(+0x43090)[0x7ff63d26a090]
/usr/lib/python3/dist-packages/sage/combinat/enumeration_mod_permgroup.cpython-38-x86_64-linux-gnu.so(+0x6ffb)[0x7ff51eb7effb]
/usr/lib/python3/dist-packages/sage/combinat/enumeration_mod_permgroup.cpython-38-x86_64-linux-gnu.so(+0x884b)[0x7ff51eb8084b]
/usr/lib/python3/dist-packages/sage/combinat/enumeration_mod_permgroup.cpython-38-x86_64-linux-gnu.so(+0xcb2d)[0x7ff51eb84b2d]
python3(PyCFunction_Call+0x59)[0x5f6939]
python3(_PyObject_MakeTpCall+0x296)[0x5f7506]
python3(_PyEval_EvalFrameDefault+0x59c7)[0x570787]
python3[0x50b07e]
python3(_PyEval_EvalFrameDefault+0x5796)[0x570556]
python3[0x500e63]
python3(_PyEval_EvalFrameDefault+0xafd)[0x56b8bd]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3[0x50b1f0]
python3(_PyEval_EvalFrameDefault+0x5796)[0x570556]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3(PyEval_EvalCode+0x27)[0x68e547]
python3[0x601624]
python3[0x5c4ef0]
python3(_PyEval_EvalFrameDefault+0x72d)[0x56b4ed]
python3[0x5009c8]
python3(_PyEval_EvalFrameDefault+0x213d)[0x56cefd]
python3[0x5009c8]
python3(_PyEval_EvalFrameDefault+0x213d)[0x56cefd]
python3[0x5009c8]
python3[0x504716]
python3(_PyEval_EvalFrameDefault+0x859)[0x56b619]
python3(_PyFunction_Vectorcall+0x1b6)[0x5f6ce6]
python3(_PyEval_EvalFrameDefault+0x72d)[0x56b4ed]
python3(_PyFunction_Vectorcall+0x1b6)[0x5f6ce6]
python3(_PyEval_EvalFrameDefault+0x859)[0x56b619]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3[0x50b1f0]
python3(_PyEval_EvalFrameDefault+0x1910)[0x56c6d0]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3(_PyFunction_Vectorcall+0x393)[0x5f6ec3]
python3(_PyEval_EvalFrameDefault+0x859)[0x56b619]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3(_PyFunction_Vectorcall+0x393)[0x5f6ec3]
python3(_PyEval_EvalFrameDefault+0x859)[0x56b619]
python3(_PyFunction_Vectorcall+0x1b6)[0x5f6ce6]
python3(_PyEval_EvalFrameDefault+0x859)[0x56b619]
python3(_PyEval_EvalCodeWithName+0x26a)[0x5697da]
python3(PyEval_EvalCode+0x27)[0x68e547]
python3[0x67dbf1]
python3[0x67dc6f]
python3[0x67dd11]
python3(PyRun_SimpleFileExFlags+0x197)[0x67fe37]
python3(Py_RunMain+0x212)[0x6b7c82]
python3(Py_BytesMain+0x2d)[0x6b800d]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf3)[0x7ff63d24b083]
python3(_start+0x2e)[0x5fb85e]
------------------------------------------------------------------------

Additional Information

No response

Environment

- **OS**: Ubuntu 20.05
- **Sage Version**: 9.0, Release Date: 2020-01-01

Also tested on Sage 10.0, Release Date: 2023-05-20, with similar results.

Checklist

  • I have searched the existing issues for a bug report that matches the one I want to file, without success.
  • I have read the documentation and troubleshoot guide
@DaveWitteMorris
Copy link
Member

Thanks for reporting the bug. I think the problem is with the iterator itself, not the cardinality method, because the following also gives a segmentation fault for me.

P = PermutationGroup([], domain=[])                                          
V = IntegerVectorsModPermutationGroup(P, sum=1)                             
for _ in V:
     pass

@jukkakohonen
Copy link
Contributor Author

Pull request #36814 fixes the problem for cardinality in the finite case, because it does not call the iterator. It does not fix the underlying problem with the iterator.

@mantepse mantepse mentioned this issue Dec 6, 2023
Merged
5 tasks
@dimpase
Copy link
Member

dimpase commented Dec 8, 2023

still crashes in the latest beta 10.3.beta0

@jukkakohonen
Copy link
Contributor Author

PR #36814 should now fix this in all cases, both finite and infinite, both in cardinality and the iterator. In the end I basically special-cased all empty-domain situations.

I certainly did not feel the urge to find why the underlying elements_of_depth_iterator etc. were crashing. AFAIK they still do, if you call them carelessly (with an empty domain), but they are internal methods, and at least the exposed cardinality and iter methods are careful enough not to do that.

@jukkakohonen jukkakohonen self-assigned this Dec 8, 2023
vbraun pushed a commit to vbraun/sage that referenced this issue Dec 17, 2023
sagemathgh-36814: Fast cardinality method for IntegerVectorsModPermut…
5d0093c 
…ationGroup

    
# Fast cardinality method for IntegerVectorsModPermutationGroup

This patch fixes sagemath#36787 by implementing a `cardinality` method for
`IntegerVectorsModPermutationGroup_with_constraints`.  The method
calculates the cardinality using the the [Polya enumeration
theorem](https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem)
(also known as the cycle index theorem).

It is faster than the the default implementation, which iterates through
the full set to
find the cardinality.

Incidentally this PR fixes also sagemath#36681 so that cardinality and iter no
longer crash in empty-domain situations.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->
<!-- If your change requires a documentation PR, please link it
appropriately -->
<!-- If you're unsure about any of these, don't hesitate to ask. We're
here to help! -->
<!-- Feel free to remove irrelevant items. -->

- [x] The title is concise, informative, and self-explanatory.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation accordingly.

### ⌛ Dependencies

- sagemath#36873: we can use `is_trivial` from that PR
<!-- List all open PRs that this PR logically depends on
- sagemath#12345: short description why this is a dependency
- sagemath#34567: ...
-->

<!-- If you're unsure about any of these, don't hesitate to ask. We're
here to help! -->
    
URL: sagemath#36814
Reported by: Jukka Kohonen
Reviewer(s): Dima Pasechnik, Jukka Kohonen, Martin Rubey, Travis Scrimshaw
@dimpase
Copy link
Member

dimpase commented Dec 28, 2023

fixed by #36814

@dimpase dimpase closed this as completed Dec 28, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@jukkakohonen jukkakohonen

Labels
t: bug
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fast cardinality method for IntegerVectorsModPermutationGroup jukkakohonen/sage
3 participants
@dimpase @jukkakohonen @DaveWitteMorris