skmgoldin / sol-dll Goto Github PK

The changes in 52d97ca address most of the inconsistent list states from re-inserting an existing node, but one remains: if the last node is reinserted with itself as the previous node, the node sets its next and previous pointers to itself, and the actual previous item in the list isn't updated to point to the right place.

(I haven't written a test case for this, so feel free to ask for one if you don't see the bug.)

Recommendation

diff --git a/contracts/DLL.sol b/contracts/DLL.sol
index 18d4965..5226132 100644
--- a/contracts/DLL.sol
+++ b/contracts/DLL.sol
@@ -52,11 +52,13 @@ library DLL {
   */
   function insert(Data storage self, uint _prev, uint _curr, uint _next) public {
     require(_curr != NULL_NODE_ID);
-    require(_prev == NULL_NODE_ID || contains(self, _prev));
-
     remove(self, _curr);
 
+    require(_prev == NULL_NODE_ID || contains(self, _prev));
+    require(_next == NULL_NODE_ID || contains(self, _next));
+
     require(getNext(self, _prev) == _next);
+    require(getPrev(self, _next) == _prev);
 
     self.dll[_curr].prev = _prev;
     self.dll[_curr].next = _next;

Remove the current item from the list as early as possible in the function, right after the null node check. Since _prev will no longer be in the list, the contains() check will fail and the cycle won't be created. Make it harder to exploit lists that somehow get into a broken state by checking the invariants for _next, even though we expect them to always be consistent with the checks for _prev. Add a README that describes DLL as a list of unique elements.