pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
; open a viewport, print coordinates of mouse clicks
; currently need to ctrl-c to exit after closing the viewport
(function main [
  (window-on (("practice" literal)) 300:literal 300:literal)
  { begin
    (pos:integer-integer-pair click?:boolean <- mouse-position)
    (loop-unless click?:boolean)
    (x:integer <- get pos:integer-integer-pair 0:offset)
    (y:integer <- get pos:integer-integer-pair 1:offset)
;?     ($print (("AAA " literal)))
;?     ($print x:integer)
;?     ($print ((", " literal)))
;?     ($print y:integer)
;?     ($print (("\n" literal)))
    (print-integer nil:literal/terminal x:integer)
    (print-character nil:literal/terminal ((#\, literal)))
    (print-character nil:literal/terminal ((#\space literal)))
    (print-integer nil:literal/terminal y:integer)
    (print-character nil:literal/terminal ((#\newline literal)))
    (loop)
  }
  (window-off)
])

# A doubly linked list permits bidirectional traversal.

container duplex-list:_elem [
  value:_elem
  next:&:duplex-list:_elem
  prev:&:duplex-list:_elem
]

def push x:_elem, in:&:duplex-list:_elem/contained-in:result -> result:&:duplex-list:_elem [
  local-scope
  load-inputs
  result:&:duplex-list:_elem <- new {(duplex-list _elem): type}
  *result <- merge x, in, null
  return-unless in
  put *in, prev:offset, result
]

def first in:&:duplex-list:_elem -> result:_elem [
  local-scope
  load-inputs
  {
    break-if in
    zero:&:_elem <- new _elem:type
    zero-result:_elem <- copy *zero
    abandon zero
    return zero-result
  }
  result <- get *in, value:offset
]

def next in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
  local-scope
  load-inputs
  return-unless in, null
  result <- get *in, next:offset
]

def prev in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
  local-scope
  load-inputs
  return-unless in, null
  result <- get *in, prev:offset
  return result
]

scenario duplex-list-handling [
  run [
    local-scope
    # reserve locations 0-9 to check for missing null check
    10:num/raw <- copy 34
    11:num/raw <- copy 35
    list:&:duplex-list:num <- push 3, null
    list <- push 4, list
    list <- push 5, list
    list2:&:duplex-list:num <- copy list
    20:num/raw <- first list2
    list2 <- next list2
    21:num/raw <- first list2
    list2 <- next list2
    22:num/raw <- first list2
    30:&:duplex-list:num/raw <- next list2
    31:num/raw <- first 30:&:duplex-list:num/raw
    32:&:duplex-list:num/raw <- next 30:&:duplex-list:num/raw
    33:&:duplex-list:num/raw <- prev 30:&:duplex-list:num/raw
    list2 <- prev list2
    40:num/raw <- first list2
    list2 <- prev list2
    41:num/raw <- first list2
    50:bool/raw <- equal list, list2
  ]
  memory-should-contain [
    0 <- 0  # no modifications to null pointers
    10 <- 34
    11 <- 35
    20 <- 5  # scanning next
    21 <- 4
    22 <- 3
    30 <- 0  # null
    31 <- 0  # first of null
    32 <- 0  # next of null
    33 <- 0  # prev of null
    40 <- 4  # then start scanning prev
    41 <- 5
    50 <- 1  # list back at start
  ]
]

def length l:&:duplex-list:_elem -> result:num [
  local-scope
  load-inputs
  result <- copy 0
  {
    break-unless l
    result <- add result, 1
    l <- next l
    loop
  }
]

# insert 'x' after 'in'
def insert x:_elem, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
  local-scope
  load-inputs
  new-node:&:duplex-list:_elem <- new {(duplex-list _elem): type}
  *new-node <- put *new-node, value:offset, x
  # save old next before changing it
  next-node:&:duplex-list:_elem <- get *in, next:offset
  *in <- put *in, next:offset, new-node
  *new-node <- put *new-node, prev:offset, in
  *new-node <- put *new-node, next:offset, next-node
  return-unless next-node
  *next-node <- put *next-node, prev:offset, new-node
]

scenario inserting-into-duplex-list [
  local-scope
  list:&:duplex-list:num <- push 3, null
  list <- push 4, list
  list <- push 5, list
  run [
    list2:&:duplex-list:num <- next list  # inside list
    list2 <- insert 6, list2
    # check structure like before
    list2 <- copy list
    10:num/raw <- first list2
    list2 <- next list2
    11:num/raw <- first list2
    list2 <- next list2
    12:num/raw <- first list2
    list2 <- next list2
    13:num/raw <- first list2
    list2 <- prev list2
    20:num/raw <- first list2
    list2 <- prev list2
    21:num/raw <- first list2
    list2 <- prev list2
    22:num/raw <- first list2
    30:bool/raw <- equal list, list2
  ]
  memory-should-contain [
    10 <- 5  # scanning next
    11 <- 4
    12 <- 6  # inserted element
    13 <- 3
    20 <- 6  # then prev
    21 <- 4
    22 <- 5
    30 <- 1  # list back at start
  ]
]

scenario inserting-at-end-of-duplex-list [
  local-scope
  list:&:duplex-list:num <- push 3, null
  list <- push 4, list
  list <- push 5, list
  run [
    list2:&:duplex-list:num <- next list  # inside list
    list2 <- next list2  # now at end of list
    list2 <- insert 6, list2
    # check structure like before
    list2 <- copy list
    10:num/raw <- first list2
    list2 <- next list2
    11:num/raw <- first list2
    list2 <- next list2
    12:num/raw <- first list2
    list2 <- next list2
    13:num/raw <- first list2
    list2 <- prev list2
    20:num/raw <- first list2
    list2 <- prev list2
    21:num/raw <- first list2
    list2 <- prev list2
    22:num/raw <- first list2
    30:bool/raw <- equal list, list2
  ]
  memory-should-contain [
    10 <- 5  # scanning next
    11 <- 4
    12 <- 3
    13 <- 6  # inserted element
    20 <- 3  # then prev
    21 <- 4
    22 <- 5
    30 <- 1  # list back at start
  ]
]

scenario inserting-after-start-of-duplex-list [
  local-scope
  list:&:duplex-list:num <- push 3, null
  list <- push 4, list
  list <- push 5, list
  run [
    list <- insert 6, list
    # check structure like before
    list2:&:duplex-list:num <- copy list
    10:num/raw <- first list2
    list2 <- next list2
    11:num/raw <- first list2
    list2 <- next list2
    12:num/raw <- first list2
    list2 <- next list2
    13:num/raw <- first list2
    list2 <- prev list2
    20:num/raw <- first list2
    list2 <- prev list2
    21:num/raw <- first list2
    list2 <- prev list2
    22:num/raw <- first list2
    30:bool/raw <- equal list, list2
  ]
  memory-should-contain [
    10 <- 5  # scanning next
    11 <- 6  # inserted element
    12 <- 4
    13 <- 3
    20 <- 4  # then prev
    21 <- 6
    22 <- 5
    30 <- 1  # list back at start
  ]
]

# remove 'x' from its surrounding list 'in'
#
# Returns null if and only if list is empty. Beware: in that case any other
# pointers to the head are now invalid.
def remove x:&:duplex-list:_elem/contained-in:in, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
  local-scope
  load-inputs
  # if 'x' is null, return
  return-unless x
  next-node:&:duplex-list:_elem <- get *x, next:offset
  prev-node:&:duplex-list:_elem <- get *x, prev:offset
  # null x's pointers
  *x <- put *x, next:offset, null
  *x <- put *x, prev:offset, null
  # if next-node is not null, set its prev pointer
  {
    break-unless next-node
    *next-node <- put *next-node, prev:offset, prev-node
  }
  # if prev-node is not null, set its next pointer and return
  {
    break-unless prev-node
    *prev-node <- put *prev-node, next:offset, next-node
    return
  }
  # if prev-node is null, then we removed the head node at 'in'
  # return the new head rather than the old 'in'
  return next-node
]

scenario removing-from-duplex-list [
  local-scope
  list:&:duplex-list:num <- push 3, null
  list <- push 4, list
  list <- push 5, list
  run [
    list2:&:duplex-list:num <- next list  # second element
    list <- remove list2, list
    10:bool/raw <- equal list2, null
    # check structure like before
    list2 <- copy list
    11:num/raw <- first list2
    list2 <- next list2
    12:num/raw <- first list2
    20:&:duplex-list:num/raw <- next list2
    list2 <- prev list2
    30:num/raw <- first list2
    40:bool/raw <- equal list, list2
  ]
  memory-should-contain [
    10 <- 0  # remove returned non-null
    11 <- 5  # scanning next, skipping deleted element
    12 <- 3
    20 <- 0  # no more elements
    30 <- 5  # prev of final element
    40 <- 1  # list back at start
  ]
]

scenario removing-from-start-of-duplex-list [
  local-scope
  list:&:duplex-list:num <- push 3, null
  list <- push 4, list
  list <- push 5, list
  run [
    list <- remove list, list
    # check structure like before
    list2:&:duplex-list:num <- copy list
    10:num/raw <- first list2
    list2 <- next list2
    11:num/raw <- first list2
    20:&:duplex-list:num/raw <- next list2
    list2 <- prev list2
    30:num/raw <- first list2
    40:bool/raw <- equal list, list2
  ]
  memory-should-contain [
    10 <- 4  # scanning next, skipping deleted element
    11 <- 3
    20 <- 0  # no more elements
    30 <- 4  # prev of final element
    40 <- 1  # list back at start
  ]
]

scenario removing-from-end-of-duplex-list [
  local-scope
  list:&:duplex-list:num <- push 3, null
  list <- push 4, list
  list <- push 5, list
  run [
    # delete last element
    list2:&:duplex-list:num <- next list
    list2 <- next list2
    list <- remove list2, list
    10:bool/raw <- equal list2, null
    # check structure like before
    list2 <- copy list
    11:num/raw <- first list2
    list2 <- next list2
    12:num/raw <- first list2
    20:&:duplex-list:num/raw <- next list2
    list2 <- prev list2
    30:num/raw <- first list2
    40:bool/raw <- equal list, list2
  ]
  memory-should-contain [
    10 <- 0  # remove returned non-null
    11 <- 5  # scanning next, skipping deleted element
    12 <- 4
    20 <- 0  # no more elements
    30 <- 5  # prev of final element
    40 <- 1  # list back at start
  ]
]

scenario removing-from-singleton-duplex-list [
  local-scope
  list:&:duplex-list:num <- push 3, null
  run [
    list <- remove list, list
    1:num/raw <- deaddress list
  ]
  memory-should-contain [
    1 <- 0  # back to an empty list
  ]
]

def remove x:&:duplex-list:_elem/contained-in:in, n:num, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
  local-scope
  load-inputs
  i:num <- copy 0
  curr:&:duplex-list:_elem <- copy x
  {
    done?:bool <- greater-or-equal i, n
    break-if done?
    break-unless curr
    next:&:duplex-list:_elem <- next curr
    in <- remove curr, in
    curr <- copy next
    i <- add i, 1
    loop
  }
]

scenario removing-multiple-from-duplex-list [
  local-scope
  list:&:duplex-list:num <- push 3, null
  list <- push 4, list
  list <- push 5, list
  run [
    list2:&:duplex-list:num <- next list  # second element
    list <- remove list2, 2, list
    stash list
  ]
  trace-should-contain [
    app: 5
  ]
]

# remove values between 'start' and 'end' (both exclusive).
# also clear pointers back out from start/end for hygiene.
# set end to 0 to delete everything past start.
# can't set start to 0 to delete everything before end, because there's no
# clean way to return the new head pointer.
def remove-between start:&:duplex-list:_elem, end:&:duplex-list:_elem/contained-in:start -> start:&:duplex-list:_elem [
  local-scope
  load-inputs
  next:&:duplex-list:_elem <- get *start, next:offset
  nothing-to-delete?:bool <- equal next, end
  return-if nothing-to-delete?
  assert next, [malformed duplex list]
  # start->next->prev = 0
  # start->next = end
  *next <- put *next, prev:offset, null
  *start <- put *start, next:offset, end
  {
    break-if end
    stash [spliced:] next
    return
  }
  # end->prev->next = 0
  # end->prev = start
  prev:&:duplex-list:_elem <- get *end, prev:offset
  assert prev, [malformed duplex list - 2]
  *prev <- put *prev, next:offset, null
  stash [spliced:] next
  *end <- put *end, prev:offset, start
]

scenario remove-range [
  # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
  local-scope
  list:&:duplex-list:num <- push 18, null
  list <- push 17, list
  list <- push 16, list
  list <- push 15, list
  list <- push 14, list
  list <- push 13, list
  run [
    # delete 16 onwards
    # first pointer: to the third element
    list2:&:duplex-list:num <- next list
    list2 <- next list2
    list2 <- remove-between list2, null
    # now check the list
    10:num/raw <- get *list, value:offset
    list <- next list
    11:num/raw <- get *list, value:offset
    list <- next list
    12:num/raw <- get *list, value:offset
    20:&:duplex-list:num/raw <- next list
  ]
  memory-should-contain [
    10 <- 13
    11 <- 14
    12 <- 15
    20 <- 0
  ]
  trace-should-contain [
    app: spliced: 16 <-> 17 <-> 18
  ]
]

scenario remove-range-to-final [
  local-scope
  # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
  list:&:duplex-list:num <- push 18, null
  list <- push 17, list
  list <- push 16, list
  list <- push 15, list
  list <- push 14, list
  list <- push 13, list
  run [
    # delete 15, 16 and 17
    # start pointer: to the second element
    list2:&:duplex-list:num <- next list
    # end pointer: to the last (sixth) element
    end:&:duplex-list:num <- next list2
    end <- next end
    end <- next end
    end <- next end
    remove-between list2, end
    # now check the list
    10:num/raw <- get *list, value:offset
    list <- next list
    11:num/raw <- get *list, value:offset
    list <- next list
    12:num/raw <- get *list, value:offset
    20:&:duplex-list:num/raw <- next list
  ]
  memory-should-contain [
    10 <- 13
    11 <- 14
    12 <- 18
    20 <- 0  # no more elements
  ]
  trace-should-contain [
    app: spliced: 15 <-> 16 <-> 17
  ]
]

scenario remove-range-to-penultimate [
  local-scope
  # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
  list:&:duplex-list:num <- push 18, null
  list <- push 17, list
  list <- push 16, list
  list <- push 15, list
  list <- push 14, list
  list <- push 13, list
  run [
    # delete 15 and 16
    # start pointer: to the second element
    list2:&:duplex-list:num <- next list
    # end pointer: to the last (sixth) element
    end:&:duplex-list:num <- next list2
    end <- next end
    end <- next end
    remove-between list2, end
    # now check the list
    10:num/raw <- get *list, value:offset
    list <- next list
    11:num/raw <- get *list, value:offset
    list <- next list
    12:num/raw <- get *list, value:offset
    list <- next list
    13:num/raw <- get *list, value:offset
    20:&:duplex-list:num/raw <- next list
  ]
  memory-should-contain [
    10 <- 13
    11 <- 14
    12 <- 17
    13 <- 18
    20 <- 0  # no more elements
  ]
  trace-should-contain [
    app: spliced: 15 <-> 16
  ]
]

scenario remove-range-empty [
  local-scope
  # construct a duplex list with three elements [13, 14, 15]
  list:&:duplex-list:num <- push 15, null
  list <- push 14, list
  list <- push 13, list
  run [
    # delete between first and second element (i.e. nothing)
    list2:&:duplex-list:num <- next list
    remove-between list, list2
    # now check the list
    10:num/raw <- get *list, value:offset
    list <- next list
    11:num/raw <- get *list, value:offset
    list <- next list
    12:num/raw <- get *list, value:offset
    20:&:duplex-list:num/raw <- next list
  ]
  # no change
  memory-should-contain [
    10 <- 13
    11 <- 14
    12 <- 15
    20 <- 0
  ]
]

scenario remove-range-to-end [
  local-scope
  # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
  list:&:duplex-list:num <- push 18, null
  list <- push 17, list
  list <- push 16, list
  list <- push 15, list
  list <- push 14, list
  list <- push 13, list
  run [
    # remove the third element and beyond
    list2:&:duplex-list:num <- next list
    remove-between list2, null
    # now check the list
    10:num/raw <- get *list, value:offset
    list <- next list
    11:num/raw <- get *list, value:offset
    20:&:duplex-list:num/raw <- next list
  ]
  memory-should-contain [
    10 <- 13
    11 <- 14
    20 <- 0
  ]
]

# insert list beginning at 'start' after 'in'
def splice in:&:duplex-list:_elem, start:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
  local-scope
  load-inputs
  return-unless in
  return-unless start
  end:&:duplex-list:_elem <- last start
  next:&:duplex-list:_elem <- next in
  {
    break-unless next
    *end <- put *end, next:offset, next
    *next <- put *next, prev:offset, end
  }
  *in <- put *in, next:offset, start
  *start <- put *start, prev:offset, in
]

# insert contents of 'new' after 'in'
def insert in:&:duplex-list:_elem, new:&:@:_elem -> in:&:duplex-list:_elem [
  local-scope
  load-inputs
  return-unless in
  return-unless new
  len:num <- length *new
  return-unless len
  curr:&:duplex-list:_elem <- copy in
  idx:num <- copy 0
  {
    done?:bool <- greater-or-equal idx, len
    break-if done?
    c:_elem <- index *new, idx
    insert c, curr
    # next iter
    curr <- next curr
    idx <- add idx, 1
    loop
  }
]

def append in:&:duplex-list:_elem, new:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
  local-scope
  load-inputs
  last:&:duplex-list:_elem <- last in
  *last <- put *last, next:offset, new
  return-unless new
  *new <- put *new, prev:offset, last
]

def last in:&:duplex-list:_elem -> result:&:duplex-list:_elem [
  local-scope
  load-inputs
  result <- copy in
  {
    next:&:duplex-list:_elem <- next result
    break-unless next
    result <- copy next
    loop
  }
]

# does a duplex list start with a certain sequence of elements?
def match x:&:duplex-list:_elem, y:&:@:_elem -> result:bool [
  local-scope
  load-inputs
  i:num <- copy 0
  max:num <- length *y
  {
    done?:bool <- greater-or-equal i, max
    break-if done?
    expected:_elem <- index *y, i
    return-unless x, false/no-match
    curr:_elem <- first x
    curr-matches?:bool <- equal curr, expected
    return-unless curr-matches?, false/no-match
    x <- next x
    i <- add i, 1
    loop
  }
  return true/successful-match
]

scenario duplex-list-match [
  local-scope
  list:&:duplex-list:char <- push 97/a, null
  list <- push 98/b, list
  list <- push 99/c, list
  list <- push 100/d, list
  run [
    10:bool/raw <- match list, []
    11:bool/raw <- match list, [d]
    12:bool/raw <- match list, [dc]
    13:bool/raw <- match list, [dcba]
    14:bool/raw <- match list, [dd]
    15:bool/raw <- match list, [dcbax]
  ]
  memory-should-contain [
    10 <- 1  # matches []
    11 <- 1  # matches [d]
    12 <- 1  # matches [dc]
    13 <- 1  # matches [dcba]
    14 <- 0  # does not match [dd]
    15 <- 0  # does not match [dcbax]
  ]
]

# helper for debugging
def dump-from x:&:duplex-list:_elem [
  local-scope
  load-inputs
  $print x, [: ]
  {
    break-unless x
    c:_elem <- get *x, value:offset
    $print c, [ ]
    x <- next x
    {
      is-newline?:bool <- equal c, 10/newline
      break-unless is-newline?
      $print 10/newline
      $print x, [: ]
    }
    loop
  }
  $print 10/newline, [---], 10/newline
]

scenario stash-duplex-list [
  local-scope
  list:&:duplex-list:num <- push 1, null
  list <- push 2, list
  list <- push 3, list
  run [
    stash [list:], list
  ]
  trace-should-contain [
    app: list: 3 <-> 2 <-> 1
  ]
]

def to-text in:&:duplex-list:_elem -> result:text [
  local-scope
  load-inputs
  buf:&:buffer:char <- new-buffer 80
  buf <- to-buffer in, buf
  result <- buffer-to-array buf
]

# variant of 'to-text' which stops printing after a few elements (and so is robust to cycles)
def to-text-line in:&:duplex-list:_elem -> result:text [
  local-scope
  load-inputs
  buf:&:buffer:char <- new-buffer 80
  buf <- to-buffer in, buf, 6  # max elements to display
  result <- buffer-to-array buf
]

def to-buffer in:&:duplex-list:_elem, buf:&:buffer:char -> buf:&:buffer:char [
  local-scope
  load-inputs
  {
    break-if in
    buf <- append buf, [[]]
    return
  }
  # append in.value to buf
  val:_elem <- get *in, value:offset
  buf <- append buf, val
  # now prepare next
  next:&:duplex-list:_elem <- next in
  nextn:num <- deaddress next
  return-unless next
  buf <- append buf, [ <-> ]
  # and recurse
  remaining:num, optional-input-found?:bool <- next-input
  {
    break-if optional-input-found?
    # unlimited recursion
    buf <- to-buffer next, buf
    return
  }
  {
    break-unless remaining
    # limited recursion
    remaining <- subtract remaining, 1
    buf <- to-buffer next, buf, remaining
    return
  }
  # past recursion depth; insert ellipses and stop
  append buf, [...]
]

scenario stash-empty-duplex-list [
  local-scope
  x:&:duplex-list:num <- copy null
  run [
    stash x
  ]
  trace-should-contain [
    app: []
  ]
]