archive/1.vm/065duplex_list.mu

   1 # A doubly linked list permits bidirectional traversal.
   2
   3 container duplex-list:_elem [
   4   value:_elem
   5   next:&:duplex-list:_elem
   6   prev:&:duplex-list:_elem
   7 ]
   8
   9 def push x:_elem, in:&:duplex-list:_elem/contained-in:result -> result:&:duplex-list:_elem [
  10   local-scope
  11   load-inputs
  12   result:&:duplex-list:_elem <- new {(duplex-list _elem): type}
  13   *result <- merge x, in, null
  14   return-unless in
  15   put *in, prev:offset, result
  16 ]
  17
  18 def first in:&:duplex-list:_elem -> result:_elem [
  19   local-scope
  20   load-inputs
  21   {
  22     break-if in
  23     zero:&:_elem <- new _elem:type
  24     zero-result:_elem <- copy *zero
  25     abandon zero
  26     return zero-result
  27   }
  28   result <- get *in, value:offset
  29 ]
  30
  31 def next in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
  32   local-scope
  33   load-inputs
  34   return-unless in, null
  35   result <- get *in, next:offset
  36 ]
  37
  38 def prev in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
  39   local-scope
  40   load-inputs
  41   return-unless in, null
  42   result <- get *in, prev:offset
  43   return result
  44 ]
  45
  46 scenario duplex-list-handling [
  47   run [
  48     local-scope
  49     # reserve locations 0-9 to check for missing null check
  50     10:num/raw <- copy 34
  51     11:num/raw <- copy 35
  52     list:&:duplex-list:num <- push 3, null
  53     list <- push 4, list
  54     list <- push 5, list
  55     list2:&:duplex-list:num <- copy list
  56     20:num/raw <- first list2
  57     list2 <- next list2
  58     21:num/raw <- first list2
  59     list2 <- next list2
  60     22:num/raw <- first list2
  61     30:&:duplex-list:num/raw <- next list2
  62     31:num/raw <- first 30:&:duplex-list:num/raw
  63     32:&:duplex-list:num/raw <- next 30:&:duplex-list:num/raw
  64     33:&:duplex-list:num/raw <- prev 30:&:duplex-list:num/raw
  65     list2 <- prev list2
  66     40:num/raw <- first list2
  67     list2 <- prev list2
  68     41:num/raw <- first list2
  69     50:bool/raw <- equal list, list2
  70   ]
  71   memory-should-contain [
  72     0 <- 0  # no modifications to null pointers
  73     10 <- 34
  74     11 <- 35
  75     20 <- 5  # scanning next
  76     21 <- 4
  77     22 <- 3
  78     30 <- 0  # null
  79     31 <- 0  # first of null
  80     32 <- 0  # next of null
  81     33 <- 0  # prev of null
  82     40 <- 4  # then start scanning prev
  83     41 <- 5
  84     50 <- 1  # list back at start
  85   ]
  86 ]
  87
  88 def length l:&:duplex-list:_elem -> result:num [
  89   local-scope
  90   load-inputs
  91   result <- copy 0
  92   {
  93     break-unless l
  94     result <- add result, 1
  95     l <- next l
  96     loop
  97   }
  98 ]
  99
 100 # insert 'x' after 'in'
 101 def insert x:_elem, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
 102   local-scope
 103   load-inputs
 104   new-node:&:duplex-list:_elem <- new {(duplex-list _elem): type}
 105   *new-node <- put *new-node, value:offset, x
 106   # save old next before changing it
 107   next-node:&:duplex-list:_elem <- get *in, next:offset
 108   *in <- put *in, next:offset, new-node
 109   *new-node <- put *new-node, prev:offset, in
 110   *new-node <- put *new-node, next:offset, next-node
 111   return-unless next-node
 112   *next-node <- put *next-node, prev:offset, new-node
 113 ]
 114
 115 scenario inserting-into-duplex-list [
 116   local-scope
 117   list:&:duplex-list:num <- push 3, null
 118   list <- push 4, list
 119   list <- push 5, list
 120   run [
 121     list2:&:duplex-list:num <- next list  # inside list
 122     list2 <- insert 6, list2
 123     # check structure like before
 124     list2 <- copy list
 125     10:num/raw <- first list2
 126     list2 <- next list2
 127     11:num/raw <- first list2
 128     list2 <- next list2
 129     12:num/raw <- first list2
 130     list2 <- next list2
 131     13:num/raw <- first list2
 132     list2 <- prev list2
 133     20:num/raw <- first list2
 134     list2 <- prev list2
 135     21:num/raw <- first list2
 136     list2 <- prev list2
 137     22:num/raw <- first list2
 138     30:bool/raw <- equal list, list2
 139   ]
 140   memory-should-contain [
 141     10 <- 5  # scanning next
 142     11 <- 4
 143     12 <- 6  # inserted element
 144     13 <- 3
 145     20 <- 6  # then prev
 146     21 <- 4
 147     22 <- 5
 148     30 <- 1  # list back at start
 149   ]
 150 ]
 151
 152 scenario inserting-at-end-of-duplex-list [
 153   local-scope
 154   list:&:duplex-list:num <- push 3, null
 155   list <- push 4, list
 156   list <- push 5, list
 157   run [
 158     list2:&:duplex-list:num <- next list  # inside list
 159     list2 <- next list2  # now at end of list
 160     list2 <- insert 6, list2
 161     # check structure like before
 162     list2 <- copy list
 163     10:num/raw <- first list2
 164     list2 <- next list2
 165     11:num/raw <- first list2
 166     list2 <- next list2
 167     12:num/raw <- first list2
 168     list2 <- next list2
 169     13:num/raw <- first list2
 170     list2 <- prev list2
 171     20:num/raw <- first list2
 172     list2 <- prev list2
 173     21:num/raw <- first list2
 174     list2 <- prev list2
 175     22:num/raw <- first list2
 176     30:bool/raw <- equal list, list2
 177   ]
 178   memory-should-contain [
 179     10 <- 5  # scanning next
 180     11 <- 4
 181     12 <- 3
 182     13 <- 6  # inserted element
 183     20 <- 3  # then prev
 184     21 <- 4
 185     22 <- 5
 186     30 <- 1  # list back at start
 187   ]
 188 ]
 189
 190 scenario inserting-after-start-of-duplex-list [
 191   local-scope
 192   list:&:duplex-list:num <- push 3, null
 193   list <- push 4, list
 194   list <- push 5, list
 195   run [
 196     list <- insert 6, list
 197     # check structure like before
 198     list2:&:duplex-list:num <- copy list
 199     10:num/raw <- first list2
 200     list2 <- next list2
 201     11:num/raw <- first list2
 202     list2 <- next list2
 203     12:num/raw <- first list2
 204     list2 <- next list2
 205     13:num/raw <- first list2
 206     list2 <- prev list2
 207     20:num/raw <- first list2
 208     list2 <- prev list2
 209     21:num/raw <- first list2
 210     list2 <- prev list2
 211     22:num/raw <- first list2
 212     30:bool/raw <- equal list, list2
 213   ]
 214   memory-should-contain [
 215     10 <- 5  # scanning next
 216     11 <- 6  # inserted element
 217     12 <- 4
 218     13 <- 3
 219     20 <- 4  # then prev
 220     21 <- 6
 221     22 <- 5
 222     30 <- 1  # list back at start
 223   ]
 224 ]
 225
 226 # remove 'x' from its surrounding list 'in'
 227 #
 228 # Returns null if and only if list is empty. Beware: in that case any other
 229 # pointers to the head are now invalid.
 230 def remove x:&:duplex-list:_elem/contained-in:in, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
 231   local-scope
 232   load-inputs
 233   # if 'x' is null, return
 234   return-unless x
 235   next-node:&:duplex-list:_elem <- get *x, next:offset
 236   prev-node:&:duplex-list:_elem <- get *x, prev:offset
 237   # null x's pointers
 238   *x <- put *x, next:offset, null
 239   *x <- put *x, prev:offset, null
 240   # if next-node is not null, set its prev pointer
 241   {
 242     break-unless next-node
 243     *next-node <- put *next-node, prev:offset, prev-node
 244   }
 245   # if prev-node is not null, set its next pointer and return
 246   {
 247     break-unless prev-node
 248     *prev-node <- put *prev-node, next:offset, next-node
 249     return
 250   }
 251   # if prev-node is null, then we removed the head node at 'in'
 252   # return the new head rather than the old 'in'
 253   return next-node
 254 ]
 255
 256 scenario removing-from-duplex-list [
 257   local-scope
 258   list:&:duplex-list:num <- push 3, null
 259   list <- push 4, list
 260   list <- push 5, list
 261   run [
 262     list2:&:duplex-list:num <- next list  # second element
 263     list <- remove list2, list
 264     10:bool/raw <- equal list2, null
 265     # check structure like before
 266     list2 <- copy list
 267     11:num/raw <- first list2
 268     list2 <- next list2
 269     12:num/raw <- first list2
 270     20:&:duplex-list:num/raw <- next list2
 271     list2 <- prev list2
 272     30:num/raw <- first list2
 273     40:bool/raw <- equal list, list2
 274   ]
 275   memory-should-contain [
 276     10 <- 0  # remove returned non-null
 277     11 <- 5  # scanning next, skipping deleted element
 278     12 <- 3
 279     20 <- 0  # no more elements
 280     30 <- 5  # prev of final element
 281     40 <- 1  # list back at start
 282   ]
 283 ]
 284
 285 scenario removing-from-start-of-duplex-list [
 286   local-scope
 287   list:&:duplex-list:num <- push 3, null
 288   list <- push 4, list
 289   list <- push 5, list
 290   run [
 291     list <- remove list, list
 292     # check structure like before
 293     list2:&:duplex-list:num <- copy list
 294     10:num/raw <- first list2
 295     list2 <- next list2
 296     11:num/raw <- first list2
 297     20:&:duplex-list:num/raw <- next list2
 298     list2 <- prev list2
 299     30:num/raw <- first list2
 300     40:bool/raw <- equal list, list2
 301   ]
 302   memory-should-contain [
 303     10 <- 4  # scanning next, skipping deleted element
 304     11 <- 3
 305     20 <- 0  # no more elements
 306     30 <- 4  # prev of final element
 307     40 <- 1  # list back at start
 308   ]
 309 ]
 310
 311 scenario removing-from-end-of-duplex-list [
 312   local-scope
 313   list:&:duplex-list:num <- push 3, null
 314   list <- push 4, list
 315   list <- push 5, list
 316   run [
 317     # delete last element
 318     list2:&:duplex-list:num <- next list
 319     list2 <- next list2
 320     list <- remove list2, list
 321     10:bool/raw <- equal list2, null
 322     # check structure like before
 323     list2 <- copy list
 324     11:num/raw <- first list2
 325     list2 <- next list2
 326     12:num/raw <- first list2
 327     20:&:duplex-list:num/raw <- next list2
 328     list2 <- prev list2
 329     30:num/raw <- first list2
 330     40:bool/raw <- equal list, list2
 331   ]
 332   memory-should-contain [
 333     10 <- 0  # remove returned non-null
 334     11 <- 5  # scanning next, skipping deleted element
 335     12 <- 4
 336     20 <- 0  # no more elements
 337     30 <- 5  # prev of final element
 338     40 <- 1  # list back at start
 339   ]
 340 ]
 341
 342 scenario removing-from-singleton-duplex-list [
 343   local-scope
 344   list:&:duplex-list:num <- push 3, null
 345   run [
 346     list <- remove list, list
 347     1:num/raw <- deaddress list
 348   ]
 349   memory-should-contain [
 350     1 <- 0  # back to an empty list
 351   ]
 352 ]
 353
 354 def remove x:&:duplex-list:_elem/contained-in:in, n:num, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
 355   local-scope
 356   load-inputs
 357   i:num <- copy 0
 358   curr:&:duplex-list:_elem <- copy x
 359   {
 360     done?:bool <- greater-or-equal i, n
 361     break-if done?
 362     break-unless curr
 363     next:&:duplex-list:_elem <- next curr
 364     in <- remove curr, in
 365     curr <- copy next
 366     i <- add i, 1
 367     loop
 368   }
 369 ]
 370
 371 scenario removing-multiple-from-duplex-list [
 372   local-scope
 373   list:&:duplex-list:num <- push 3, null
 374   list <- push 4, list
 375   list <- push 5, list
 376   run [
 377     list2:&:duplex-list:num <- next list  # second element
 378     list <- remove list2, 2, list
 379     stash list
 380   ]
 381   trace-should-contain [
 382     app: 5
 383   ]
 384 ]
 385
 386 # remove values between 'start' and 'end' (both exclusive).
 387 # also clear pointers back out from start/end for hygiene.
 388 # set end to 0 to delete everything past start.
 389 # can't set start to 0 to delete everything before end, because there's no
 390 # clean way to return the new head pointer.
 391 def remove-between start:&:duplex-list:_elem, end:&:duplex-list:_elem/contained-in:start -> start:&:duplex-list:_elem [
 392   local-scope
 393   load-inputs
 394   next:&:duplex-list:_elem <- get *start, next:offset
 395   nothing-to-delete?:bool <- equal next, end
 396   return-if nothing-to-delete?
 397   assert next, [malformed duplex list]
 398   # start->next->prev = 0
 399   # start->next = end
 400   *next <- put *next, prev:offset, null
 401   *start <- put *start, next:offset, end
 402   {
 403     break-if end
 404     stash [spliced:] next
 405     return
 406   }
 407   # end->prev->next = 0
 408   # end->prev = start
 409   prev:&:duplex-list:_elem <- get *end, prev:offset
 410   assert prev, [malformed duplex list - 2]
 411   *prev <- put *prev, next:offset, null
 412   stash [spliced:] next
 413   *end <- put *end, prev:offset, start
 414 ]
 415
 416 scenario remove-range [
 417   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
 418   local-scope
 419   list:&:duplex-list:num <- push 18, null
 420   list <- push 17, list
 421   list <- push 16, list
 422   list <- push 15, list
 423   list <- push 14, list
 424   list <- push 13, list
 425   run [
 426     # delete 16 onwards
 427     # first pointer: to the third element
 428     list2:&:duplex-list:num <- next list
 429     list2 <- next list2
 430     list2 <- remove-between list2, null
 431     # now check the list
 432     10:num/raw <- get *list, value:offset
 433     list <- next list
 434     11:num/raw <- get *list, value:offset
 435     list <- next list
 436     12:num/raw <- get *list, value:offset
 437     20:&:duplex-list:num/raw <- next list
 438   ]
 439   memory-should-contain [
 440     10 <- 13
 441     11 <- 14
 442     12 <- 15
 443     20 <- 0
 444   ]
 445   trace-should-contain [
 446     app: spliced: 16 <-> 17 <-> 18
 447   ]
 448 ]
 449
 450 scenario remove-range-to-final [
 451   local-scope
 452   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
 453   list:&:duplex-list:num <- push 18, null
 454   list <- push 17, list
 455   list <- push 16, list
 456   list <- push 15, list
 457   list <- push 14, list
 458   list <- push 13, list
 459   run [
 460     # delete 15, 16 and 17
 461     # start pointer: to the second element
 462     list2:&:duplex-list:num <- next list
 463     # end pointer: to the last (sixth) element
 464     end:&:duplex-list:num <- next list2
 465     end <- next end
 466     end <- next end
 467     end <- next end
 468     remove-between list2, end
 469     # now check the list
 470     10:num/raw <- get *list, value:offset
 471     list <- next list
 472     11:num/raw <- get *list, value:offset
 473     list <- next list
 474     12:num/raw <- get *list, value:offset
 475     20:&:duplex-list:num/raw <- next list
 476   ]
 477   memory-should-contain [
 478     10 <- 13
 479     11 <- 14
 480     12 <- 18
 481     20 <- 0  # no more elements
 482   ]
 483   trace-should-contain [
 484     app: spliced: 15 <-> 16 <-> 17
 485   ]
 486 ]
 487
 488 scenario remove-range-to-penultimate [
 489   local-scope
 490   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
 491   list:&:duplex-list:num <- push 18, null
 492   list <- push 17, list
 493   list <- push 16, list
 494   list <- push 15, list
 495   list <- push 14, list
 496   list <- push 13, list
 497   run [
 498     # delete 15 and 16
 499     # start pointer: to the second element
 500     list2:&:duplex-list:num <- next list
 501     # end pointer: to the last (sixth) element
 502     end:&:duplex-list:num <- next list2
 503     end <- next end
 504     end <- next end
 505     remove-between list2, end
 506     # now check the list
 507     10:num/raw <- get *list, value:offset
 508     list <- next list
 509     11:num/raw <- get *list, value:offset
 510     list <- next list
 511     12:num/raw <- get *list, value:offset
 512     list <- next list
 513     13:num/raw <- get *list, value:offset
 514     20:&:duplex-list:num/raw <- next list
 515   ]
 516   memory-should-contain [
 517     10 <- 13
 518     11 <- 14
 519     12 <- 17
 520     13 <- 18
 521     20 <- 0  # no more elements
 522   ]
 523   trace-should-contain [
 524     app: spliced: 15 <-> 16
 525   ]
 526 ]
 527
 528 scenario remove-range-empty [
 529   local-scope
 530   # construct a duplex list with three elements [13, 14, 15]
 531   list:&:duplex-list:num <- push 15, null
 532   list <- push 14, list
 533   list <- push 13, list
 534   run [
 535     # delete between first and second element (i.e. nothing)
 536     list2:&:duplex-list:num <- next list
 537     remove-between list, list2
 538     # now check the list
 539     10:num/raw <- get *list, value:offset
 540     list <- next list
 541     11:num/raw <- get *list, value:offset
 542     list <- next list
 543     12:num/raw <- get *list, value:offset
 544     20:&:duplex-list:num/raw <- next list
 545   ]
 546   # no change
 547   memory-should-contain [
 548     10 <- 13
 549     11 <- 14
 550     12 <- 15
 551     20 <- 0
 552   ]
 553 ]
 554
 555 scenario remove-range-to-end [
 556   local-scope
 557   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
 558   list:&:duplex-list:num <- push 18, null
 559   list <- push 17, list
 560   list <- push 16, list
 561   list <- push 15, list
 562   list <- push 14, list
 563   list <- push 13, list
 564   run [
 565     # remove the third element and beyond
 566     list2:&:duplex-list:num <- next list
 567     remove-between list2, null
 568     # now check the list
 569     10:num/raw <- get *list, value:offset
 570     list <- next list
 571     11:num/raw <- get *list, value:offset
 572     20:&:duplex-list:num/raw <- next list
 573   ]
 574   memory-should-contain [
 575     10 <- 13
 576     11 <- 14
 577     20 <- 0
 578   ]
 579 ]
 580
 581 # insert list beginning at 'start' after 'in'
 582 def splice in:&:duplex-list:_elem, start:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
 583   local-scope
 584   load-inputs
 585   return-unless in
 586   return-unless start
 587   end:&:duplex-list:_elem <- last start
 588   next:&:duplex-list:_elem <- next in
 589   {
 590     break-unless next
 591     *end <- put *end, next:offset, next
 592     *next <- put *next, prev:offset, end
 593   }
 594   *in <- put *in, next:offset, start
 595   *start <- put *start, prev:offset, in
 596 ]
 597
 598 # insert contents of 'new' after 'in'
 599 def insert in:&:duplex-list:_elem, new:&:@:_elem -> in:&:duplex-list:_elem [
 600   local-scope
 601   load-inputs
 602   return-unless in
 603   return-unless new
 604   len:num <- length *new
 605   return-unless len
 606   curr:&:duplex-list:_elem <- copy in
 607   idx:num <- copy 0
 608   {
 609     done?:bool <- greater-or-equal idx, len
 610     break-if done?
 611     c:_elem <- index *new, idx
 612     insert c, curr
 613     # next iter
 614     curr <- next curr
 615     idx <- add idx, 1
 616     loop
 617   }
 618 ]
 619
 620 def append in:&:duplex-list:_elem, new:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
 621   local-scope
 622   load-inputs
 623   last:&:duplex-list:_elem <- last in
 624   *last <- put *last, next:offset, new
 625   return-unless new
 626   *new <- put *new, prev:offset, last
 627 ]
 628
 629 def last in:&:duplex-list:_elem -> result:&:duplex-list:_elem [
 630   local-scope
 631   load-inputs
 632   result <- copy in
 633   {
 634     next:&:duplex-list:_elem <- next result
 635     break-unless next
 636     result <- copy next
 637     loop
 638   }
 639 ]
 640
 641 # does a duplex list start with a certain sequence of elements?
 642 def match x:&:duplex-list:_elem, y:&:@:_elem -> result:bool [
 643   local-scope
 644   load-inputs
 645   i:num <- copy 0
 646   max:num <- length *y
 647   {
 648     done?:bool <- greater-or-equal i, max
 649     break-if done?
 650     expected:_elem <- index *y, i
 651     return-unless x, false/no-match
 652     curr:_elem <- first x
 653     curr-matches?:bool <- equal curr, expected
 654     return-unless curr-matches?, false/no-match
 655     x <- next x
 656     i <- add i, 1
 657     loop
 658   }
 659   return true/successful-match
 660 ]
 661
 662 scenario duplex-list-match [
 663   local-scope
 664   list:&:duplex-list:char <- push 97/a, null
 665   list <- push 98/b, list
 666   list <- push 99/c, list
 667   list <- push 100/d, list
 668   run [
 669     10:bool/raw <- match list, []
 670     11:bool/raw <- match list, [d]
 671     12:bool/raw <- match list, [dc]
 672     13:bool/raw <- match list, [dcba]
 673     14:bool/raw <- match list, [dd]
 674     15:bool/raw <- match list, [dcbax]
 675   ]
 676   memory-should-contain [
 677     10 <- 1  # matches []
 678     11 <- 1  # matches [d]
 679     12 <- 1  # matches [dc]
 680     13 <- 1  # matches [dcba]
 681     14 <- 0  # does not match [dd]
 682     15 <- 0  # does not match [dcbax]
 683   ]
 684 ]
 685
 686 # helper for debugging
 687 def dump-from x:&:duplex-list:_elem [
 688   local-scope
 689   load-inputs
 690   $print x, [: ]
 691   {
 692     break-unless x
 693     c:_elem <- get *x, value:offset
 694     $print c, [ ]
 695     x <- next x
 696     {
 697       is-newline?:bool <- equal c, 10/newline
 698       break-unless is-newline?
 699       $print 10/newline
 700       $print x, [: ]
 701     }
 702     loop
 703   }
 704   $print 10/newline, [---], 10/newline
 705 ]
 706
 707 scenario stash-duplex-list [
 708   local-scope
 709   list:&:duplex-list:num <- push 1, null
 710   list <- push 2, list
 711   list <- push 3, list
 712   run [
 713     stash [list:], list
 714   ]
 715   trace-should-contain [
 716     app: list: 3 <-> 2 <-> 1
 717   ]
 718 ]
 719
 720 def to-text in:&:duplex-list:_elem -> result:text [
 721   local-scope
 722   load-inputs
 723   buf:&:buffer:char <- new-buffer 80
 724   buf <- to-buffer in, buf
 725   result <- buffer-to-array buf
 726 ]
 727
 728 # variant of 'to-text' which stops printing after a few elements (and so is robust to cycles)
 729 def to-text-line in:&:duplex-list:_elem -> result:text [
 730   local-scope
 731   load-inputs
 732   buf:&:buffer:char <- new-buffer 80
 733   buf <- to-buffer in, buf, 6  # max elements to display
 734   result <- buffer-to-array buf
 735 ]
 736
 737 def to-buffer in:&:duplex-list:_elem, buf:&:buffer:char -> buf:&:buffer:char [
 738   local-scope
 739   load-inputs
 740   {
 741     break-if in
 742     buf <- append buf, [[]]
 743     return
 744   }
 745   # append in.value to buf
 746   val:_elem <- get *in, value:offset
 747   buf <- append buf, val
 748   # now prepare next
 749   next:&:duplex-list:_elem <- next in
 750   nextn:num <- deaddress next
 751   return-unless next
 752   buf <- append buf, [ <-> ]
 753   # and recurse
 754   remaining:num, optional-input-found?:bool <- next-input
 755   {
 756     break-if optional-input-found?
 757     # unlimited recursion
 758     buf <- to-buffer next, buf
 759     return
 760   }
 761   {
 762     break-unless remaining
 763     # limited recursion
 764     remaining <- subtract remaining, 1
 765     buf <- to-buffer next, buf, remaining
 766     return
 767   }
 768   # past recursion depth; insert ellipses and stop
 769   append buf, [...]
 770 ]
 771
 772 scenario stash-empty-duplex-list [
 773   local-scope
 774   x:&:duplex-list:num <- copy null
 775   run [
 776     stash x
 777   ]
 778   trace-should-contain [
 779     app: []
 780   ]
 781 ]