This code is part of a solution for the exercism's Linked List exercise for someone I mentored
type
LinkedList*[T] = object ## A doubly linked list.
first: ListNode[T]
last {.cursor.}: ListNode[T] # notice the cursor
len: int
ListNode[T] = ref object
next: ListNode[T]
prev {.cursor.}: ListNode[T]
val: T
proc insert[T](list: var LinkedList[T], prev, next: ListNode[T], val: T) =
var node = ListNode[T](val: val)
if prev == nil:
list.first = node
else:
node.prev = prev
prev.next = node
if next == nil:
list.last = node
else:
node.next = next
next.prev = node
proc push*[T](list: var LinkedList[T], val: T) =
## Appends a node with the given `val` to `list`.
list.insert list.last, nil, val
proc unshift*[T](list: var LinkedList[T], val: T) =
## Prepends a node with the given `val` to `list`.
list.insert nil, list.first, val
block:
# make a list of [4, 1, 5]
var list = LinkedList[int]()
# These operations, in this order, cause "Error: execution of an external program failed"
list.push(1)
list.unshift(4)
list.push(5)
# uncomment and the program no longer errors but enters an infinite loop.
# var it = list.first
# while it != nil:
# echo it.val
# it = it.next
# 4
# 5
# 5
# 5
# ...
Can Someone explain What is the problem with using cursor here ?
Compile this code with nim c -r --mm:orc test.nim:
type
NodeObj = object
left: Node
right {.cursor.}: Node
name: string
Node = ref NodeObj
proc `=destroy`(x: var NodeObj) =
echo "destroy ", x.name
proc main =
var
n0 = Node(name: "n0")
r = Node(left: n0, right: n0, name: "r")
n0 = nil
echo "r.left = nil"
r.left = nil
echo "r.right = nil"
r.right = nil
echo "end of main"
main()Your insert was too complicated for me to understand so I rewrote the code to:
proc push*[T](list: var LinkedList[T], val: T) =
## Appends a node with the given `val` to `list`.
#list.insert list.last, nil, val
var node = ListNode[T](val: val)
node.prev = list.last
# node.next remains nil
list.last = node
if list.first.isNil: list.first = node
proc unshift*[T](list: var LinkedList[T], val: T) =
## Prepends a node with the given `val` to `list`.
#list.insert nil, list.first, val
var node = ListNode[T](val: val)
node.next = list.first
# node.prev remains nil
list.first = node
if list.last.isNil: list.last = node
And the errors that valgrind showed disappeared.
I solved the same exercise some weeks ago, without using .cursor pragma though.
After adding the pragma, my code kept working flawlessly. Even after changing the approach to use a similar insert proc as provided in the question.
After some tinkering around I noticed that I used the object constructor to its full power and already set prev and next fields here, which even allows to shorten the insert proc a little bit
proc insert[T](list: var LinkedList[T]; prev, next: ListNode[T]; val: T) =
let node = ListNode[T](val: val, prev: prev, next: next)
if prev.isNil:
list.first = node
else:
#node.prev = prev # (redundant)
prev.next = node
if next.isNil:
list.last = node
else:
#node.next = next # (redundant)
next.prev = node
However I'm not able to explain why the initial solution didn't work. Maybe someone else can, based on my observations.
This actually makes things more confusing. Your version seems equivalent to the original, why does it work ? For reference, here's the --expandArc:insert result for: The original
var
node
:tmpD
node = ListNode[T](val:
:tmpD = val_1
:tmpD)
if prev == nil:
`=copy`(list.first, node)
else:
node.prev_1_cursor = prev
`=copy`(prev.next, node)
if next_1 == nil:
list.last_cursor = node
else:
`=copy`(node.next, next_1)
next_1.prev_1_cursor = node
list.len += 1
`=destroy`(node)
var
node
:tmpD
:tmpD_1
node = ListNode[T](val:
:tmpD = val_1
:tmpD, prev_cursor: prev_1, next:
`=wasMoved`(:tmpD_1)
`=copy`(:tmpD_1, next_1)
:tmpD_1)
if prev_1 == nil:
`=copy`(list.first, node)
else:
`=copy`(prev_1.next, node)
if next_1 == nil:
`=sink`(list.last, node)
`=wasMoved`(node)
else:
next_1.prev_cursor = node
list.len += 1
`=destroy`(node)
@@ -1,19 +1,22 @@
var
node
:tmpD
+ :tmpD_1
node = ListNode[T](val:
:tmpD = val_1
- :tmpD)
-if prev == nil:
+ :tmpD, prev_cursor: prev_1, next:
+ `=wasMoved`(:tmpD_1)
+ `=copy`(:tmpD_1, next_1)
+ :tmpD_1)
+if prev_1 == nil:
`=copy`(list.first, node)
else:
- node.prev_1_cursor = prev
- `=copy`(prev.next, node)
+ `=copy`(prev_1.next, node)
if next_1 == nil:
- list.last_cursor = node
+ `=sink`(list.last, node)
+ `=wasMoved`(node)
else:
- `=copy`(node.next, next_1)
- next_1.prev_1_cursor = node
+ next_1.prev_cursor = node
list.len += 1
`=destroy`(node)
I think it's a bug, and it just disappeared when I tried to echo everything before they're accessed.
proc insert[T](list: var LinkedList[T], prev, next: ListNode[T], val: T) =
echo [if prev != nil: prev.val else: 0, val, if next != nil: next.val else: 0]
var node = ListNode[T](val: val)
if prev == nil:
echo "prev == nil"
echo "list.first = node" & " val: " & $val
list.first = node
else:
echo "node.prev = prev" & " val: " & $(prev.val)
node.prev = prev
echo "prev.next = node" & " val: " & $val
prev.next = node
if next == nil:
echo "next == nil"
echo "list.last = node" & " val: " & $val
list.last = node
else:
echo "node.next = next" & " val: " & $(next.val)
node.next = next
echo "next.prev = node" & " val: " & $val
next.prev = node
if node.next.isNil():
echo "node.next == nil;"
[0, 1, 0]
prev == nil
list.first = node val: 1
next == nil
list.last = node val: 1
node.next == nil;
[0, 4, 1]
prev == nil
list.first = node val: 4
node.next = next val: 1
next.prev = node val: 4
[1, 5, 0]
node.prev = prev val: 1
prev.next = node val: 5
next == nil
list.last = node val: 5
node.next == nil;
4
1
5
Why does this work then ? (Smintheus98's)
proc insert[T](list: var LinkedList[T]; prev, next: ListNode[T]; val: T) =
let node = ListNode[T](val: val, prev: prev, next: next)
if prev.isNil:
list.first = node
else:
#node.prev = prev # (redundant)
prev.next = node
if next.isNil:
list.last = node
else:
#node.next = next # (redundant)
next.prev = node
Interestingly, this simple cursorless code compiled with ARC makes valgrind cry:
type
List = object
first: Node
second : Node
Node = ref object
proc push(list: var List, node: Node) =
list.first = Node() # list.first os decref and destroyed
list.second = node
proc main() =
var list = List(first: Node())
push(list, list.first)
main()
Beginning of valgrind output:
Invalid read of size 8
at 0x10D21D: nimIncRef (arc.nim:46)
by 0x10D2CA: eqcopy___bug_u29 (bug.nim:13)
by 0x10D38B: foo__bug_u7 (bug.nim:15)
by 0x10D499: main__bug_u40 (bug.nim:16)
by 0x10D54B: NimMainModule (bug.nim:18)
by 0x10D586: NimMainInner (bug.nim:40)
by 0x10D599: NimMain (bug.nim:51)
by 0x10D5BB: main (bug.nim:59)
Address 0x4b6b040 is 0 bytes inside a block of size 16 free'd
at 0x484426F: free (vg_replace_malloc.c:884)
by 0x109E16: deallocImpl__system_u1772 (malloc.nim:28)
by 0x109E24: deallocSharedImpl__system_u1785 (malloc.nim:46)
by 0x109E32: deallocShared (memalloc.nim:300)
by 0x10A1D6: alignedDealloc (memalloc.nim:367)
by 0x10B26A: nimRawDispose (arc.nim:145)
by 0x10D2AF: eqsink___bug_u32 (bug.nim:17)
by 0x10D37F: foo__bug_u7 (bug.nim:14)
by 0x10D499: main__bug_u40 (bug.nim:16)
by 0x10D54B: NimMainModule (bug.nim:18)
by 0x10D586: NimMainInner (bug.nim:40)
by 0x10D599: NimMain (bug.nim:51)
Block was alloc'd at
at 0x4841888: malloc (vg_replace_malloc.c:393)
by 0x109ECA: allocImpl__system_u1768 (malloc.nim:6)
by 0x109ED8: allocSharedImpl (malloc.nim:35)
by 0x10B99F: alignedAlloc__system_u1908 (memalloc.nim:332)
by 0x10CB13: nimNewObjUninit (arc.nim:86)
by 0x10D47A: main__bug_u40 (bug.nim:20)
by 0x10D54B: NimMainModule (bug.nim:18)
by 0x10D586: NimMainInner (bug.nim:40)
by 0x10D599: NimMain (bug.nim:51)
by 0x10D5BB: main (bug.nim:59)
In push, list.first is passed 'as-is', so its Ref Count is still 1 despite the fact there is two references of it at the beginning of push. On can “fix” it by forcing an incref with an intermediary variable before calling push:
proc main() =
var list = List(first: Node())
let first = list.first
foo(list, first)
Note that technically the first code violates Nim's (experimental and unenforced) aliasing rules.
With the list.first = node assignment, there's no more reference that keeps the node previously pointed to by first alive and the cell is thus immediately destroyed.
I was confused by the "immediatly destroyed" part as I couldn't find where is the old node destroyed, then, examining the generated C, I understood it's destroyed in the =copy function (eqdestroy___llbug_u88(colontmp_);):
N_LIB_PRIVATE N_NIMCALL(void, eqcopy___llbug_u75)(tyObject_ListNodeObj__bQHnN9ccFzE14H9cD8IIbU3g** dest_p0, tyObject_ListNodeObj__bQHnN9ccFzE14H9cD8IIbU3g* src_p1, NIM_BOOL cyclic_p2) {
tyObject_ListNodeObj__bQHnN9ccFzE14H9cD8IIbU3g* colontmp_;
colontmp_ = (*dest_p0);
{
if (!src_p1) goto LA3_;
nimIncRefCyclic(src_p1, cyclic_p2);
}
LA3_: ;
(*dest_p0) = src_p1;
{
NIM_BOOL T7_;
T7_ = (NIM_BOOL)0;
T7_ = nimDecRefIsLastCyclicStatic(colontmp_, (&NTIv2__bQHnN9ccFzE14H9cD8IIbU3g_));
if (!T7_) goto LA8_;
eqdestroy___llbug_u88(colontmp_);
nimRawDispose(colontmp_, ((NI)8));
}
LA8_: ;
}
The cursor pragma certainly is dangerous. Thanks again for clarifying this 🙂.