classification
Title: Undefined behaviour in Objects/complexobject.c's complex_pow
Type: behavior Stage: resolved
Components: Versions: Python 3.11, Python 3.10, Python 3.9, Python 3.8, Python 3.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: mark.dickinson Nosy List: gregory.p.smith, lukasz.langa, mark.dickinson, miss-islington, pablogsal, seberg, tim.peters, twouters
Priority: normal Keywords: patch

Created on 2021-07-21 15:06 by twouters, last changed 2021-08-17 18:22 by mark.dickinson. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 27278 merged twouters, 2021-07-21 15:26
PR 27366 merged miss-islington, 2021-07-26 16:03
PR 27367 merged miss-islington, 2021-07-26 16:03
PR 27772 merged mark.dickinson, 2021-08-15 09:44
PR 27796 merged miss-islington, 2021-08-17 16:51
PR 27797 merged miss-islington, 2021-08-17 16:51
Messages (19)
msg397947 - (view) Author: Thomas Wouters (twouters) * (Python committer) Date: 2021-07-21 15:06
Objects/complexobject.c's complex_pow uses undefined behaviour, by casting a float of unknown magnitude to a long:

    int_exponent = (long)exponent.real;

At Google we build with clang and -fsanitize=float-cast-overflow by default, which catches this particular kind of undefined behaviour. We didn't notice, however, because the only code we've come across that exercises this behaviour was a commented-out test in test_complex, which was uncommented in 3.8. Running the test, or just '1e19+1j ** 1e19', is enough to trigger the undefined behaviour. I'll prepare a PR to fix it.
msg398239 - (view) Author: Łukasz Langa (lukasz.langa) * (Python committer) Date: 2021-07-26 16:03
New changeset 1d582bbc969e05896addf97844ddf17ce9830e5e by T. Wouters in branch 'main':
bpo-44698: Fix undefined behaviour in complex exponentiation. (GH-27278)
https://github.com/python/cpython/commit/1d582bbc969e05896addf97844ddf17ce9830e5e
msg398249 - (view) Author: Łukasz Langa (lukasz.langa) * (Python committer) Date: 2021-07-26 19:30
New changeset 85ac81499ec5fb156a57408bcd95b06de4531488 by Miss Islington (bot) in branch '3.9':
bpo-44698: Fix undefined behaviour in complex exponentiation. (GH-27278) (GH-27367)
https://github.com/python/cpython/commit/85ac81499ec5fb156a57408bcd95b06de4531488
msg398250 - (view) Author: Łukasz Langa (lukasz.langa) * (Python committer) Date: 2021-07-26 19:30
New changeset 256d97c8a3151ec7caba6c06bf2a1e682008c304 by Miss Islington (bot) in branch '3.10':
bpo-44698: Fix undefined behaviour in complex exponentiation. (GH-27278) (#27366)
https://github.com/python/cpython/commit/256d97c8a3151ec7caba6c06bf2a1e682008c304
msg398928 - (view) Author: Sebastian Berg (seberg) * Date: 2021-08-04 18:21
The fix broke NumPy (see also https://github.com/numpy/numpy/pull/19612)

It seems incorrect.  After all, it doesn't matter much whether the float can be converted to an integer correctly (or even if it returns an undefined value), so long `int_value == float_value` remains sensible.

The old cast cast integers to complex when they were out of range (which is fine), the new code raises an error instead.
msg398930 - (view) Author: Sebastian Berg (seberg) * Date: 2021-08-04 18:29
Hmm, sorry, I overshot/misread :(.

The thing that the NumPy test-suite trips over is that:

    c_powi(inf+0j, 3)

seems to not raise, but:

    _Py_c_pow(inf+0j, 3.+0j)

(or nan+0.j rather then inf+0j)

does seem to raise (returning `nan+nanj` in both cases).  If this is the `inf` code path, raising an error may actually be fix and the integer code path should maybe also do it.
msg398932 - (view) Author: Sebastian Berg (seberg) * Date: 2021-08-04 18:40
(Sorry for the spam.  I think we can/should just hard-code the expected values in the NumPy test-suite.  So this is not actually an issue for NumPy and probably just warrants a double-check that the behaviour change is desirable.)
msg398935 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-08-04 18:53
Thanks, @seberg. I'll take a look and see if we can restore the old behaviour, at least for Python 3.9 and 3.10. I'm not convinced that the new behaviour is objectively wrong, but I agree that the *change* in behaviour is problematic.

I do find it a little odd that we're special-casing integer exponents for complex numbers when no such special-casing exists for floats. It's not purely for optimization (despite what the code might say). And all the messing around with trying to figure out exactly _which_ doubles can safely be cast to long (which was the original cause of this issue) seems like a symptom of a deeper problem, which is that it doesn't make a whole lot of sense to be distinguishing in the first place. But if we're going to change the behaviour, we should only be doing that in 3.11.

OTOH, there *is* real value in z**2 being fast and accurate; we definitely want to keep that. (Perhaps the math and cmath modules should grow a `square` function.)
msg398937 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-08-04 19:03
> a double-check that the behaviour change is desirable

I'm not sure I'm brave or foolhardy enough to try to figure out what all of the special case results *should* be for complex pow. The special cases seem reasonably clear cut for everything else in the cmath module, but for pow it's pretty much going to be a nightmare. I'm not sure there's much Python can do here in the way of guarantees, other than "not obviously horribly wrong". (And while I have reasonable confidence we can achieve the "not obviously horribly wrong" goal for everything else, I still have doubts for pow.)
msg398940 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-08-04 19:19
> brave or foolhardy enough to try to figure out what all of the special case results *should* be for complex pow

Addendum: even the C standards give up at this point. For everything else the special cases are spelled out in detail, but for cpow, from §G.6.4.1 of C17 (in Annex G), we have:

> The cpow functions raise floating-point exceptions if appropriate for the calculation of the parts of the result, and may also raise spurious floating-point exceptions.

And that's it. (Well, not quite: there's a footnote, which says:

> This allows cpow(z, c) to be implemented as cexp(cclog(z)) without precluding implementations that treat special cases more carefully.

)
msg398941 - (view) Author: Sebastian Berg (seberg) * Date: 2021-08-04 19:28
Thanks for looking into it!

`cpow` is indeed complicated.  We had some discussion in NumPy about `0**y` branch cuts (I did yet not finish it, because thinking about the branch cuts is tricky).

It is almost reassuring that the C standard also hedges out :).  Although, it means that there is no reliance on math libraries if we want to treat the special cases more carefully :(.
msg399610 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-08-15 10:00
@Pablo: I'm adding you to the nosy list to get your opinion on whether (the backport of) GH-27772 can go into 3.10.0.rc2.

Summary: GH-27278 (which I reviewed and approved) and its backports fixed some undefined behaviour in complex exponentiation, but also introduced a behaviour change that affected NumPy: some exponentiation expressions that returned a result in 3.10.0b4 raise an OverflowError in 3.10.0.rc1.

GH-27772 reverts the behaviour change but keeps the fix for the undefined behaviour. Can the backport of GH-27772 to the 3.10 branch go in before 3.10.0 final?
msg399620 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2021-08-15 14:37
> GH-27772 reverts the behaviour change but keeps the fix for the undefined behaviour. Can the backport of GH-27772 to the 3.10 branch go in before 3.10.0 final?

Thanks for checking with me! 

Given that this is fixing a bug that we introduced in rc1, I think it makes sense to backport to fix it. I have reviewed the code in GH-27772 and is contained enough, so I think is a good idea to go ahead.

Thanks Mark for all the work!
msg399621 - (view) Author: Pablo Galindo Salgado (pablogsal) * (Python committer) Date: 2021-08-15 14:38
I'm keeping track to the 3.10 backports to the second rc so could you add me as a reviewer for the backport?
msg399666 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-08-16 18:24
Thanks, Pablo!

> could you add me as a reviewer for the backport

Will do! I'll waiting on review for the PR against the main branch, but hope to get the backport PR up by this coming weekend at the latest.
msg399767 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-08-17 16:51
New changeset 4b9a2dcf19e5d13c3bc2afea2de1f65cd994c699 by Mark Dickinson in branch 'main':
bpo-44698: Restore complex pow behaviour for small integral exponents (GH-27772)
https://github.com/python/cpython/commit/4b9a2dcf19e5d13c3bc2afea2de1f65cd994c699
msg399775 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-08-17 17:38
New changeset 3f81e9628f6f104c103d0e38adb84c51e5261626 by Miss Islington (bot) in branch '3.10':
bpo-44698: Restore complex pow behaviour for small integral exponents (GH-27772) (GH-27796)
https://github.com/python/cpython/commit/3f81e9628f6f104c103d0e38adb84c51e5261626
msg399776 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-08-17 17:38
New changeset beb3a835dae3cd940b93e7caa32450890c4cd539 by Miss Islington (bot) in branch '3.9':
bpo-44698: Restore complex pow behaviour for small integral exponents (GH-27772) (GH-27797)
https://github.com/python/cpython/commit/beb3a835dae3cd940b93e7caa32450890c4cd539
msg399779 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2021-08-17 18:22
Re-closing; we should be good now.
History
Date User Action Args
2021-08-17 18:22:58mark.dickinsonsetstatus: open -> closed

messages: + msg399779
stage: patch review -> resolved
2021-08-17 17:38:49mark.dickinsonsetmessages: + msg399776
2021-08-17 17:38:12mark.dickinsonsetmessages: + msg399775
2021-08-17 16:51:43miss-islingtonsetpull_requests: + pull_request26266
2021-08-17 16:51:39miss-islingtonsetpull_requests: + pull_request26265
2021-08-17 16:51:37mark.dickinsonsetmessages: + msg399767
2021-08-16 18:24:09mark.dickinsonsetmessages: + msg399666
2021-08-15 14:38:47pablogsalsetmessages: + msg399621
2021-08-15 14:37:00pablogsalsetmessages: + msg399620
2021-08-15 10:00:59mark.dickinsonsetnosy: + pablogsal
messages: + msg399610
2021-08-15 09:44:53mark.dickinsonsetstage: resolved -> patch review
pull_requests: + pull_request26246
2021-08-04 19:28:20sebergsetmessages: + msg398941
2021-08-04 19:19:17mark.dickinsonsetmessages: + msg398940
2021-08-04 19:14:08mark.dickinsonsetstatus: closed -> open
assignee: twouters -> mark.dickinson
2021-08-04 19:03:17mark.dickinsonsetmessages: + msg398937
2021-08-04 18:53:38mark.dickinsonsetmessages: + msg398935
2021-08-04 18:40:26sebergsetmessages: + msg398932
2021-08-04 18:29:00sebergsetmessages: + msg398930
2021-08-04 18:21:36sebergsetnosy: + seberg
messages: + msg398928
2021-07-26 19:30:49lukasz.langasetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2021-07-26 19:30:24lukasz.langasetmessages: + msg398250
2021-07-26 19:30:24lukasz.langasetmessages: + msg398249
2021-07-26 16:03:51miss-islingtonsetpull_requests: + pull_request25905
2021-07-26 16:03:44miss-islingtonsetnosy: + miss-islington
pull_requests: + pull_request25904
2021-07-26 16:03:44lukasz.langasetnosy: + lukasz.langa
messages: + msg398239
2021-07-21 23:59:02rhettingersetnosy: + tim.peters
2021-07-21 23:46:07rhettingersetnosy: + mark.dickinson
2021-07-21 15:26:21twouterssetkeywords: + patch
stage: patch review
pull_requests: + pull_request25823
2021-07-21 15:06:49twouterscreate