What is happening when I assign a list with self references to a list copy with the slice syntax `mylist[:] = [mylist, mylist, ...]`?

Question

I was just looking at the implementation of functools.lru_cache, when I stumbled across this snippet:

root = []  # root of the circular doubly linked list
root[:] = [root, root, None, None]  # initialize by pointing to self

I am familiar with circular and doubly linked lists. I am also aware that new_list = my_list[:] creates a copy of my_list. When looking for slice assignments or other implementations of circular doubly linked lists, I could not find any further information on this specific syntax.

Questions:

What is going on in this situation.
Is there a different syntax to achieve the same result?
Is there a different common use case for some_list[:] = some_iterable (without the self reference)?

score 5 · Accepted Answer · answered Nov 28 '18 at 17:27

in

root[:] = [root, root, None, None]

left hand slice assignment just says that the reference of root is reused to hold the contents of the right part.

So root reference never changes, and yes, in a list you can reference yourself (but don't try recursive flattening on those :). The representation displays a "recursion on list" in that case.

>>> root
[<Recursion on list with id=48987464>,
 <Recursion on list with id=48987464>,
 None,
 None]

and printing it shows ellipsis:

>>> print(root)
[[...], [...], None, None]

note that you don't need slice assignment for this. There are simple ways to trigger a recursion:

>>> root = []
>>> root.append(root)
>>> root
[<Recursion on list with id=51459656>]
>>>

using append doesn't change reference as we all know, it just mutates the list, adding a reference to itself. Maybe easier to comprehend.

I find the slice assignment `[:]` is actually a clever way to replace the entirety of the list without changing its reference. So `root[:] = [root, root, None, None]` is not readily reproducible without a handful of `append` and `remove` if `root` is more than an empty list. — r.ook, Nov 28 '18 at 17:40

score 2 · Answer 2 · answered Nov 28 '18 at 17:29

What is going on in this situation?

If l is the list, l[:] = items calls l.__setitem__(slice(None), items) is called. This method assigns the respective items from the given iterable to the list after clearing the same.

Is there a different syntax to achieve the same result?

You could do

l.clear()
l.extend(items)

Is there a different common use case for some_list[:] = some_iterable (without the self reference)?

In theory, you could put any iterable into the list.

Mazdak · Answer 3 · 2018-11-28T17:41:14.890

Just look into the disassembled code:

In [1]: def initializer():
   ...:     root = []  # root of the circular doubly linked list
   ...:     root[:] = [root, root, None, None]
   ...:     

In [2]: 

In [2]: import dis

In [3]: dis.dis(initializer)
  2           0 BUILD_LIST               0
              2 STORE_FAST               0 (root)

  3           4 LOAD_FAST                0 (root)
              6 LOAD_FAST                0 (root)
              8 LOAD_CONST               0 (None)
             10 LOAD_CONST               0 (None)
             12 BUILD_LIST               4
             14 LOAD_FAST                0 (root)
             16 LOAD_CONST               0 (None)
             18 LOAD_CONST               0 (None)
             20 BUILD_SLICE              2
             22 STORE_SUBSCR
             24 LOAD_CONST               0 (None)
             26 RETURN_VALUE

What you looking for is STORE_SUBSCR op code which is there to implement the following:

mplements TOS1[TOS] = TOS2

Which is due the do documentation an In-place operations. And if you wonder what's the In-place operations, here's how the doc defines it:

In-place operations are like binary operations, in that they remove TOS and TOS1, and push the result back on the stack, but the operation is done in-place when TOS1 supports it, and the resulting TOS may be (but does not have to be) the original TOS1.

This will verify what the inline doc in the source code says:

initialize by pointing to self.

Regarding your other questions:

Is there a different syntax to achieve the same result?

Yeah you can as it's mentioned in other answer clear and set the list items using list.extend attribute. Or assign the items one by one maybe lol

Is there a different common use case for some_list[:] = some_iterable (without the self reference)?

This is a very vague question 'cause it is what it is. Assigning items in an Injective manner which could have the benefit of replacing items without recreating references, etc.

What is happening when I assign a list with self references to a list copy with the slice syntax `mylist[:] = [mylist, mylist, ...]`?

3 Answers3