Why is __len__() called implicitly on a custom iterator

Question

I'm writing a simple linked list implementation as follows:

class Node(object):
    def __init__(self, value):
        self.value = value
        self._next = None

    def __iter__(self):
        here = self
        while here:
            yield here
            here = here._next

    def __len__(self):
        print("Calling __len__ on: {}".format(self))
        return sum(1 for _ in self)

    def append_to_tail(self, value):
        if self._next is None:
            self._next = Node(value)
        else:
            self._next.append_to_tail(value)

def print_list(ll):
    print(ll.value)
    if ll._next:
        print_list(ll._next)

my_list = Node('a')
my_list.append_to_tail('b')
my_list.append_to_tail('c')

print_list(my_list)

This code runs fine without the __len__ method. Deleting those three lines and running the code above outputs:

  first
  second
  third

However, if the __len__ method is present, then the results are:

    first
    Calling __len__ on: <__main__.Node object at 0x108804dd0>
    Calling __len__ on: <__main__.Node object at 0x108804dd0>
    <snip>
    Calling __len__ on: <__main__.Node object at 0x108804dd0>
    Calling __len__ on: <__main__.Node object at 0x108804dd0>
    Traceback (most recent call last):
      File "len_example.py", line 31, in <module>
        print_list(my_list)
      File "len_example.py", line 24, in print_list
        if ll._next:
      File "len_example.py", line 14, in __len__
        return sum(1 for _ in self)
      File "len_example.py", line 14, in <genexpr>
        return sum(1 for _ in self)
      File "len_example.py", line 8, in __iter__
        while here:
      File "len_example.py", line 14, in __len__
        return sum(1 for _ in self)
      File "len_example.py", line 14, in <genexpr>
        return sum(1 for _ in self)
    <snip>
      File "len_example.py", line 8, in __iter__
        while here:
      File "len_example.py", line 13, in __len__
        print("Calling __len__ on: {}".format(self))
    RuntimeError: maximum recursion depth exceeded while calling a Python object

Note the presence of first in the output. print_list() is executed once, but something is implicitly calling the __len__() method before recursing. What is calling that method?

I see the same behavior with python 3.3.1 and 2.7.3

Answer 1

You are using here in a boolean context:

while here:

This will use __len__ to see if it is an empty container (e.g. is false-y), see Truth Value Testing:

Any object can be tested for truth value, for use in an if or while condition or as operand of the Boolean operations below. The following values are considered false:

[...]

• instances of user-defined classes, if the class defines a __nonzero__() or __len__() method, when that method returns the integer zero or bool value False.

For your usecase, use is not None instead:

while here is not None: