python "in" operator

Hello comrade,

recently I had smth like this in my code:

>>> string = 'hdfjghweurj'
>>> sub = 'ghw'
>>> sub in string
True

I have asked myself - how "in" is working? This knowledge might be useless, but knowing how to get this info might help you understand how language works and what algorithms does it use. All examples below are for python 2, basically in python 3 it is pretty the same, but some methods differ.

Here are the steps:

dis

First, lets disassemble.

>>> import dis
>>> def foo():
...     'aaa' in []
... 
>>> dis.dis(foo)
  2           0 LOAD_CONST               1 ('aaa')
              3 LOAD_CONST               2 (())
              6 COMPARE_OP               6 (in)
              9 POP_TOP             
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE        

We now know, that it is a COMPARE_OP. Let's dive into sources.

ceval.c

Let's have a look at ceval.c loop and find our COMPARE_OP:

        
        TARGET(COMPARE_OP) {
            ...
            else {
              slow_compare:
                x = cmp_outcome(oparg, v, w);
            }
            ...
        }

Looks like all logic is in cmp_outcome. It can be found in the same file, what we interested in is:

      case PyCmp_IN:
        res = PySequence_Contains(w, v);
        if (res < 0)
            return NULL;
        break;

PySequence_Contains is interesting for us.

Objects

Searching the repo we will land at Objects/abstract.c:

int
PySequence_Contains(PyObject *seq, PyObject *ob)
{
    Py_ssize_t result;
    if (PyType_HasFeature(seq->ob_type, Py_TPFLAGS_HAVE_SEQUENCE_IN)) {
        PySequenceMethods *sqm = seq->ob_type->tp_as_sequence;
        if (sqm != NULL && sqm->sq_contains != NULL)
            return (*sqm->sq_contains)(seq, ob);
    }
    result = _PySequence_IterSearch(seq, ob, PY_ITERSEARCH_CONTAINS);
    return Py_SAFE_DOWNCAST(result, Py_ssize_t, int);
}

PySequenceMethods is our guy. As we are talking about strings, we should look for them. This leads us to Objects/stringobject.c:

Objects/stringobject.c:    (objobjproc)string_contains /*sq_contains*/

string_contains could be found in the same file:

...
return stringlib_contains_obj(str_obj, sub_obj);

Now,  of course, we must go to Objects/stringlib/find.h. Not looking through the source, at the header you might see, that it uses fastsearch.h:

#ifndef STRINGLIB_FASTSEARCH_H
#error must include "stringlib/fastsearch.h" before including this module
#endif

Lets have a look at it. The first comment states:

/* fast search/count implementation, based on a mix between boyer-
   moore and horspool, with a few more bells and whistles on the top.
   for some more background, see: http://effbot.org/zone/stringlib.htm */

That is how you know, that "in" operator in Python, when used for strings, uses Boyer-Moore-Horspool algorithm, with some "bells and whistles".