joy/utils/stack.py

   1 # -*- coding: utf-8 -*-
   2 #
   3 #    Copyright © 2014, 2015, 2017 Simon Forman
   4 #
   5 #    This file is part of Thun
   6 #
   7 #    Thun is free software: you can redistribute it and/or modify
   8 #    it under the terms of the GNU General Public License as published by
   9 #    the Free Software Foundation, either version 3 of the License, or
  10 #    (at your option) any later version.
  11 #
  12 #    Thun is distributed in the hope that it will be useful,
  13 #    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 #    GNU General Public License for more details.
  16 #
  17 #    You should have received a copy of the GNU General Public License
  18 #    along with Thun.  If not see <http://www.gnu.org/licenses/>.
  19 #
  20 '''
  21 When talking about Joy we use the terms "stack", "quote", "sequence",
  22 "list", and others to mean the same thing: a simple linear datatype that
  23 permits certain operations such as iterating and pushing and popping
  24 values from (at least) one end.
  25
  26 There is no "Stack" Python class, instead we use the  `cons list`_, a
  27 venerable two-tuple recursive sequence datastructure, where the
  28 empty tuple ``()`` is the empty stack and ``(head, rest)`` gives the
  29 recursive form of a stack with one or more items on it::
  30
  31     stack := () | (item, stack)
  32
  33 Putting some numbers onto a stack::
  34
  35     ()
  36     (1, ())
  37     (2, (1, ()))
  38     (3, (2, (1, ())))
  39     ...
  40
  41 Python has very nice "tuple packing and unpacking" in its syntax which
  42 means we can directly "unpack" the expected arguments to a Joy function.
  43
  44 For example::
  45
  46         def dup((head, tail)):
  47                 return head, (head, tail)
  48
  49 We replace the argument "stack" by the expected structure of the stack,
  50 in this case "(head, tail)", and Python takes care of unpacking the
  51 incoming tuple and assigning values to the names.  (Note that Python
  52 syntax doesn't require parentheses around tuples used in expressions
  53 where they would be redundant.)
  54
  55 Unfortunately, the Sphinx documentation generator, which is used to generate this
  56 web page, doesn't handle tuples in the function parameters.  And in Python 3, this
  57 syntax was removed entirely.  Instead you would have to write::
  58
  59         def dup(stack):
  60                 head, tail = stack
  61                 return head, (head, tail)
  62
  63
  64 We have two very simple functions, one to build up a stack from a Python
  65 iterable and another to iterate through a stack and yield its items
  66 one-by-one in order.  There are also two functions to generate string representations
  67 of stacks.  They only differ in that one prints the terms in stack from left-to-right while the other prints from right-to-left.  In both functions *internal stacks* are
  68 printed left-to-right.  These functions are written to support :doc:`../pretty`.
  69
  70 .. _cons list: https://en.wikipedia.org/wiki/Cons#Lists
  71
  72 '''
  73
  74
  75 from builtins import map
  76 def list_to_stack(el, stack=()):
  77         '''Convert a Python list (or other sequence) to a Joy stack::
  78
  79         [1, 2, 3] -> (1, (2, (3, ())))
  80
  81         :param list el: A Python list or other sequence (iterators and generators
  82                          won't work because ``reverse()`` is called on ``el``.)
  83         :param stack stack: A stack, optional, defaults to the empty stack.
  84         :rtype: stack
  85
  86         '''
  87         for item in reversed(el):
  88                 stack = item, stack
  89         return stack
  90
  91
  92 def iter_stack(stack):
  93         '''Iterate through the items on the stack.
  94
  95         :param stack stack: A stack.
  96         :rtype: iterator
  97         '''
  98         while stack:
  99                 item, stack = stack
 100                 yield item
 101
 102
 103 def stack_to_string(stack):
 104         '''
 105         Return a "pretty print" string for a stack.
 106
 107         The items are written right-to-left::
 108
 109                 (top, (second, ...)) -> '... second top'
 110
 111         :param stack stack: A stack.
 112         :rtype: str
 113         '''
 114         f = lambda stack: reversed(list(iter_stack(stack)))
 115         return _to_string(stack, f)
 116
 117
 118 def expression_to_string(expression):
 119         '''
 120         Return a "pretty print" string for a expression.
 121
 122         The items are written left-to-right::
 123
 124                 (top, (second, ...)) -> 'top second ...'
 125
 126         :param stack expression: A stack.
 127         :rtype: str
 128         '''
 129         return _to_string(expression, iter_stack)
 130
 131
 132 def _to_string(stack, f):
 133         if not isinstance(stack, tuple): return repr(stack)
 134         if not stack: return ''  # shortcut
 135         return ' '.join(map(_s, f(stack)))
 136
 137
 138 _s = lambda s: (
 139         '[%s]' % expression_to_string(s) if isinstance(s, tuple)
 140         else repr(s)
 141         )
 142
 143
 144 def concat(quote, expression):
 145         '''Concatinate quote onto expression.
 146
 147         In joy [1 2] [3 4] would become [1 2 3 4].
 148
 149         :param stack quote: A stack.
 150         :param stack expression: A stack.
 151         :raises RuntimeError: if quote is larger than sys.getrecursionlimit().
 152         :rtype: stack
 153         '''
 154         # This is the fastest implementation, but will trigger
 155         # RuntimeError: maximum recursion depth exceeded
 156         # on quotes longer than sys.getrecursionlimit().
 157
 158         return (quote[0], concat(quote[1], expression)) if quote else expression
 159
 160         # Original implementation.
 161
 162 ##  return list_to_stack(list(iter_stack(quote)), expression)
 163
 164         # In-lining is slightly faster (and won't break the
 165         # recursion limit on long quotes.)
 166
 167 ##  temp = []
 168 ##  while quote:
 169 ##    item, quote = quote
 170 ##    temp.append(item)
 171 ##  for item in reversed(temp):
 172 ##    expression = item, expression
 173 ##  return expression
 174
 175
 176
 177 def dnd(stack, from_index, to_index):
 178         '''
 179         Given a stack and two indices return a rearranged stack.
 180         First remove the item at from_index and then insert it at to_index,
 181         the second index is relative to the stack after removal of the item
 182         at from_index.
 183
 184         This function reuses all of the items and as much of the stack as it
 185         can.  It's meant to be used by remote clients to support drag-n-drop
 186         rearranging of the stack from e.g. the StackListbox.
 187         '''
 188         assert 0 <= from_index
 189         assert 0 <= to_index
 190         if from_index == to_index:
 191                 return stack
 192         head, n = [], from_index
 193         while True:
 194                 item, stack = stack
 195                 n -= 1
 196                 if n < 0:
 197                         break
 198                 head.append(item)
 199         assert len(head) == from_index
 200         # now we have two cases:
 201         diff = from_index - to_index
 202         if diff < 0:
 203                 # from < to
 204                 # so the destination index is still in the stack
 205                 while diff:
 206                         h, stack = stack
 207                         head.append(h)
 208                         diff += 1
 209         else:
 210                 # from > to
 211                 # so the destination is in the head list
 212                 while diff:
 213                         stack = head.pop(), stack
 214                         diff -= 1
 215         stack = item, stack
 216         while head:
 217                 stack = head.pop(), stack
 218         return stack
 219
 220
 221 def pick(stack, n):
 222         '''
 223         Return the nth item on the stack.
 224
 225         :param stack stack: A stack.
 226         :param int n: An index into the stack.
 227         :raises ValueError: if ``n`` is less than zero.
 228         :raises IndexError: if ``n`` is equal to or greater than the length of ``stack``.
 229         :rtype: whatever
 230         '''
 231         if n < 0:
 232                 raise ValueError
 233         while True:
 234                 try:
 235                         item, stack = stack
 236                 except ValueError:
 237                         raise IndexError
 238                 n -= 1
 239                 if n < 0:
 240                         break
 241         return item