enh: JackOfAllTradesIterator and BinaryTreeIterator now understand arbitrarily deep cons structures

Technologicat · Technologicat · commit d88c8e2f93af · 2019-02-28T14:53:53.000+02:00
diff --git a/README.md b/README.md
@@ -480,13 +480,15 @@ There is no ``copy`` method or ``lcopy`` function, because cons cells are immuta
 
 In general, copying cons structures can be error-prone. Given just a starting cell it is impossible to tell if a given instance of a cons structure represents a linked list, or something more general (such as a binary tree) that just happens to locally look like one, along the path that would be traversed if it was indeed a linked list.
 
-The linked list iteration strategy (which supports arbitrarily long lists) does not recurse in the ``car`` half, which could lead to incomplete copying. The tree strategy that recurses on both halves, on the other hand, is not safe to use on linked lists, because if the list is long, it will cause a stack overflow (due to lack of TCO in Python).
+The linked list iteration strategy does not recurse in the ``car`` half, which could lead to incomplete copying. The tree strategy that recurses on both halves, on the other hand, will flatten nested linked lists and produce also the final ``nil``.
 
-*Added in v0.13.0.* We provide a ``JackOfAllTradesIterator`` that uses unpythonic's TCO and understands both trees and linked lists, but it has to make some compromises to be able to do this: nested lists will be flattened, and in a tree any ``nil`` in a ``cdr`` position will be omitted from the output.
+*Added in v0.13.0.* We provide a ``JackOfAllTradesIterator`` as a compromise that understands both trees and linked lists. Nested lists will be flattened, and in a tree any ``nil`` in a ``cdr`` position will be omitted from the output.
+
+*Changed in v0.13.1.* ``BinaryTreeIterator`` and ``JackOfAllTradesIterator`` now use an explicit data stack instead of implicitly using the call stack for keeping track of the recursion. Hence now all ``cons`` iterators work for arbitrarily deep cons structures without causing Python's call stack to overflow, and without the need for TCO.
 
 ``cons`` has no ``collections.abc`` virtual superclasses (except the implicit ``Hashable`` since ``cons`` provides ``__hash__`` and ``__eq__``), because general cons structures do not fit into the contracts represented by membership in those classes. For example, size cannot be known without iterating, and depends on which iteration scheme is used (e.g. ``nil`` dropping, flattening); which scheme is appropriate depends on the content.
 
-**Caution**: the ``nil`` singleton is freshly created in each session; newnil is not oldnil, so don't pickle a standalone ``nil``. The unpickler of ``cons`` automatically refreshes any ``nil`` instances inside a pickled cons structure, so that **cons structures** support the illusion that ``nil`` is a special value like ``None`` or ``...``. After unpickling, ``car(c) is nil`` and ``cdr(c) is nil`` still work as expected, even though ``id(nil)`` has changed.
+**Caution**: the ``nil`` singleton is freshly created in each session; newnil is not oldnil, so don't pickle a standalone ``nil``. The unpickler of ``cons`` automatically refreshes any ``nil`` instances inside a pickled cons structure, so that **cons structures** support the illusion that ``nil`` is a special value like ``None`` or ``...``. After unpickling, ``car(c) is nil`` and ``cdr(c) is nil`` still work as expected, even though ``id(nil)`` has changed between sessions.
 
 
 ### ``box``: a mutable single-item container
@@ -1416,7 +1418,7 @@ For convenience, we introduce some special cases:
 
   - The ``box`` container from ``unpythonic.collections``; although mutable, its update is not conveniently expressible by the ``collections.abc`` APIs.
 
-  - The ``cons`` container from ``unpythonic.llist`` (including the ``ll``, ``llist`` linked lists). This is treated with the general tree strategy, so for long linked lists this will crash when the maximum call stack depth runs out.
+  - The ``cons`` container from ``unpythonic.llist`` (including the ``ll``, ``llist`` linked lists). This is treated with the general tree strategy, so nested linked lists will be flattened, and the final ``nil`` is also processed.
 
     Note that since ``cons`` is immutable, anyway, if you know you have a long linked list where you need to update the values, just iterate over it and produce a new copy - that will work as intended.
 
diff --git a/unpythonic/collections.py b/unpythonic/collections.py
@@ -59,7 +59,8 @@ def mogrify(func, container):
 
         - The ``cons`` container from ``unpythonic.llist`` (including the
           ``llist`` linked lists). This is treated with the general tree
-          strategy, so for long linked lists this will crash.
+          strategy, so nested linked lists will be flattened, and the
+          final ``nil`` is also processed.
 
     Any value that does not match any of these is treated as an atom.
 
diff --git a/unpythonic/llist.py b/unpythonic/llist.py
@@ -10,7 +10,6 @@
 from .fun import composer1i
 from .fold import foldr, foldl
 from .it import rev
-from .gtco import gtrampolined
 
 # explicit list better for tooling support
 _exports = ["cons", "nil",
@@ -142,19 +141,27 @@ def walker(head):
 class BinaryTreeIterator(ConsIterator):
     """Iterator for binary trees built from cons cells."""
     def __init__(self, root):
-        def walker(cell):
-            for x in (cell.car, cell.cdr):
-                if isinstance(x, cons):
-                    yield from walker(x)
-                else:
-                    yield x
+#        def walker(cell):  # FP, call stack overflow for deep trees
+#            for x in (cell.car, cell.cdr):
+#                if isinstance(x, cons):
+#                    yield from walker(x)
+#                else:
+#                    yield x
+        def walker(cell):  # imperative, no call stack overflow (we keep our own data stack instead)
+            stack = [cell]
+            while stack:
+                cell = stack.pop()
+                a, d = cell.car, cell.cdr
+                ac, dc = isinstance(a, cons), isinstance(d, cons)
+                if not ac: yield a
+                if not dc: yield d
+                if dc: stack.append(d)
+                if ac: stack.append(a)  # LIFO
         super().__init__(root, walker)
 
 class JackOfAllTradesIterator(ConsIterator):
     """Iterator that supports both binary trees and linked lists.
 
-    An optimized tail call is used to descend into the cdr half.
-
     **CAUTION**: *jack of all trades*, because:
 
         - To handle trees correctly, this iterator descends into any cons cell
@@ -170,16 +177,26 @@ class JackOfAllTradesIterator(ConsIterator):
     the specific kind of cons structure you have.
     """
     def __init__(self, root):
-        @gtrampolined
+#        @gtrampolined
+#        def walker(cell):  # FP, tail-recursive in the cdr half only
+#            if isinstance(cell.car, cons):
+#                yield from walker(cell.car)
+#            else:
+#                yield cell.car
+#            if isinstance(cell.cdr, cons):
+#                return walker(cell.cdr)  # signal gtrampolined to tail-chain
+#            elif cell.cdr is not nil:
+#                yield cell.cdr
         def walker(cell):
-            if isinstance(cell.car, cons):
-                yield from walker(cell.car)
-            else:
-                yield cell.car
-            if isinstance(cell.cdr, cons):
-                return walker(cell.cdr)  # signal gtrampolined to tail-chain
-            elif cell.cdr is not nil:
-                yield cell.cdr
+            stack = [cell]
+            while stack:
+                cell = stack.pop()
+                a, d = cell.car, cell.cdr
+                ac, dc = isinstance(a, cons), isinstance(d, cons)
+                if not ac: yield a
+                if not dc and d is not nil: yield d
+                if dc: stack.append(d)
+                if ac: stack.append(a)  # LIFO
         super().__init__(root, walker)
 
 class cons:
diff --git a/unpythonic/test/test_llist.py b/unpythonic/test/test_llist.py
@@ -79,6 +79,7 @@ def test():
     assert tuple(JackOfAllTradesIterator(t2)) == (nil, 1, nil, 2)  # but doesn't skip nil in the car slot
 
     assert tuple(JackOfAllTradesIterator(llist(range(10000)))) == tuple(range(10000))  # no crash
+    assert tuple(BinaryTreeIterator(llist(range(10000)))) == tuple(range(10000)) + (nil,)  # no crash
 
     # repr
     assert repr(cons(1, 2)) == "cons(1, 2)"
