forchid commented 1 month ago

The test source

import std/lists 

proc main() =
    var sa = initSinglyLinkedList[int32]()
    sa.add(0)
    var sb = sa
    echo "#0 ok."

    sa.add(1)
    assert sa.contains(0) and sa.contains(1)
    assert sb.contains(0) and sb.contains(1)
    echo "#1 ok."

    sa.add(2)
    assert sa.contains(0) and sa.contains(1) and sa.contains(2)
    assert sb.contains(0) and sb.contains(1) and sb.contains(2)
    echo "#2 ok."

    sb.add(3)
    echo "#3.1 ok."
    assert sa.contains(0) and sa.contains(1) and sa.contains(2) and sa.contains(3)
    assert sb.contains(0) and sb.contains(1) and sb.contains(2) and sb.contains(3)
    echo "#3 ok."

main()

Nim Version

nim -v Nim Compiler Version 1.6.20 [Windows: amd64] Compiled at 2024-04-07 Copyright (c) 2006-2023 by Andreas Rumpf

active boot switches: -d:release

Current Output

>liststest
#0 ok.
#1 ok.
#2 ok.
fatal.nim(54)            sysFatal
Error: unhandled exception: lists.nim(408, 11) `L.tail.next == nil`  [AssertionDefect]

Expected Output

>liststest
#0 ok.
#1 ok.
#2 ok.
#3.1 ok.
#3 ok.

Known Workarounds

No response

Additional Information

No response

metagn commented 1 month ago

SinglyLinkedLists are objects which are value types, their contents which are SinglyLinkedNode are reference types. The actual data is stored in the SinglyLinkedNode but the tail node is stored in the SinglyLinkedList object for performance, in this case the tail node is updated for sa but not sb.

You can turn sa into a ref SinglyLinkedList to get the desired behavior, but maybe the stdlib should offer the API for this via newSinglyLinkedList and the same operations for ref SinglyLinkedList as SinglyLinkedList the same way tables do. At the very least this behavior should be documented, since it's unlike the other collection types which are entirely value types.

Araq commented 1 month ago

No bug here and linked lists always have surprising aliasing behavior, this is widely known.

nim-lang / Nim