search

lacuna / bifurcan

functional, durable data structures
MIT License
967 stars 51 forks source link

bug in List removeLast method #18

Closed jafingerhut closed 4 years ago

jafingerhut commented 5 years ago

The value of n shown below is the smallest one I know of that exhibits this problem.

One issue with generative testing and data structures like List with wide branching factors is that it can take a large number of operations to reach "interesting" tree structures that exercise new code paths. I have found that making a local change with SHIFT_INCREMENT=2 and thus MAX_BRANCHES=(1 << 2) = 4 causes the existing generative tests to find issues like this in a fairly short period of time.

That requires a few replacements of literal constants 5 and 32 in the List.java and ListNodes.java source files to be replaced with appropriate names, to avoid replacing them manually in multiple places. I can submit a PR with such changes if that would be of interest.

$ clj -Sdeps '{:deps {io.lacuna/bifurcan {:mvn/version "0.2.0-alpha1"} org.clojure/clojure {:mvn/version "1.10.1"}}}'
(import '(io.lacuna.bifurcan List))
(def n 33824)
(def l1 (.concat (List.) (List/from (range n))))
(= (seq (range n)) (iterator-seq (.iterator l1)))
;; true.  Good
(.size l1)
;; 33824 - the expected size

(def l2 (.removeLast l1))
(= (seq (range (dec n))) (iterator-seq (.iterator l2)))
;; false.  bug!
(.size l2)
;; 1055 - not even close to the correct value
jafingerhut commented 5 years ago

As a comparison point, with the changes of SHIFT_INCREMENT=2, the same test fails with n=84 (but no smaller).

jafingerhut commented 5 years ago

There is a deftest test case for this issue proposed in PR https://github.com/lacuna/bifurcan/pull/20, as well as another similar test that exposes a similar problem in removeFirst.