Order of insertion in sets (when parsing {})

Question

Someone asked here why when putting 1 and True in a set only 1 is kept.

This is of course because 1==True. But in which cases 1 is kept and in which cases True is kept?

Let's see:

passing a list to build the set instead of using the set notation:

>>> set([True,1])
{True}
>>> set([1,True])
{1}

seems logical: set iterates on the inner list, and doesn't add the second element because it is equal to the first element (note that set([True,1]) cannot yield 1, because set cannot know what's inside the list. It may even not be a list but an iterable)

Now using set notation:

>>> {True,1}
{1}
>>> {1,True}
{True} 

It seems that in that case, the list of items is processed in reverse order (tested on Python 2.7 and Python 3.4).

But is that guaranteed? Or just an implementation detail?

Answer 1

The order the elements in the set literal will be inserted does not seem to be guaranteed by the language specification. However, Python 3.6 was changed so that it has the expected left-to-right evaluation order. For full details of this change, here is the issue, and also the commit that introduced the change in insertion order.

---

To describe the change in a bit more detail, building the set literal {True, 1} triggers the BUILD_SET opcode (with oparg equal to 2) after first pushing pointers to True and 1 onto the virtual machine's internal stack.

In Python 3.4, BUILD_SET uses the following loop to insert elements into the set (note that oparg is 2 in our case):

while (--oparg >= 0) {
    PyObject *item = POP();
    if (err == 0)
        err = PySet_Add(set, item);
        Py_DECREF(item);

Since 1 was added to the stack last, it is popped off first and is the first object inserted into the set.

In newer versions of Python (such as 3.6), the BUILD_SET opcode uses PEEK instead of POP:

for (i = oparg; i > 0; i--) {
    PyObject *item = PEEK(i);
    if (err == 0)
        err = PySet_Add(set, item);
        Py_DECREF(item);

PEEK(i) fetches the i^th item down the stack, so for {True, 1}, the object True is added to the set first.