gallop_left() and gallop_right() functions explicitly rely on overflowing behavior of Py_ssize_t (https://github.com/python/cpython/blob/6015cc50bc38b9e920ce4986ee10658eaa14f561/Objects/listobject.c#L1361):

    ofs = (ofs << 1) + 1;
    if (ofs <= 0)                   /* int overflow */
        ofs = maxofs;

Signed integer overflow is undefined in C, and the above is guaranteed to work only if compiler-specific workarounds are applied, such as GCC's -fwrapv (that is what CPython does). Without such workarounds the compiler would be free to remove the if statement.

This doesn't actually matter - the code can never trigger.  It would be fine to replace it with an assert to that effect (see below for a specific suggestion).

The reason:  The indices in this code are into vectors of PyObject*.  These vectors can't contain more than

    floor(PY_SSIZE_T_MAX / sizeof(PyObject*))

pointers (see listobject.c & Python's heap allocation routines).  So the largest legit index this code can ever see is 1 less than that.  Since pointers are at least 4 bytes on all machines Python runs on, that implies (with room to spare) that

    assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);

can't fail.  Which in turn implies that, mathematically,

    2*ofs + 1 <= PY_SSIZE_T_MAX

So

       if (ofs <= 0)                   /* int overflow */

can't happen, regardless of how the platform C treats signed overflow (signed overflow can't happen to begin with).  The existing `while (ofs < maxofs)` check already ensures that `ofs` is a legit index, and _any_ legit index into a PyObject* vector can be doubled and incremented without overflowing Py_ssize_t.

In fact, that would remain so even if listobject.c allowed its PyObject* vectors to contain twice as many pointers as they actually can contain now.

> This doesn't actually matter - the code can never trigger.

Yes, I considered this, and wondered why assert wasn't used in the first place, but the explicit check with a comment suggested that possibility of overflow was deemed real.

I've submitted a third PR that simply removes the checks and adds asserts instead.

I left the code in because it was harmless (a 100%-predictable branch), and it was easier to show that overflow was _considered_ than to explain in full why it was impossible.  In the context of CPython.  For example, the Java port of this code couldn't rely on the far-removed-from-this-code details of Python's C heap management (the largest Java signed integer is a legit Java array index), and signed integer overflow _is_ wholly defined in Java.  Which happens to be the same way it worked under virtually all C compilers at the time the code was written.  The idea that C compilers should be as aggressive as Fortran compilers instead of just supplying a portable assembly language is a modern conceit ;-)

The code is useless, but it's not "a bug", so I'm removing Python 2 from the list of targets.

New changeset 6bc5917903b722bdd0e5d3020949f26fec5dfe9a by Miss Islington (bot) (Alexey Izbyshev) in branch 'master':
bpo-35091: Objects/listobject.c: Replace overflow checks in gallop fu… (GH-10202)
https://github.com/python/cpython/commit/6bc5917903b722bdd0e5d3020949f26fec5dfe9a

New changeset 367fe5757a707c4e3602dee807a9315199ed0b5c by Miss Islington (bot) in branch '3.7':
bpo-35091: Objects/listobject.c: Replace overflow checks in gallop fu… (GH-10202)
https://github.com/python/cpython/commit/367fe5757a707c4e3602dee807a9315199ed0b5c

nosy: + tim.peters