search

lambdaisland / deep-diff2

Deep diff Clojure data structures and pretty print the result
Eclipse Public License 1.0
296 stars 18 forks source link

ddiff not terminating #24

Closed joda closed 2 years ago

joda commented 3 years ago

Thanks for providing deep-diff, it's a super usable tool.

We do think we've found a bug in version 2.0.108 though. We we're able to minimize the test case to this:

(require
  '[lambdaisland.deep-diff2 :as ddiff])

(def actual [nil])
(def expected [{}])

;; works
(ddiff/diff actual expected)

;; does not terminate
(ddiff/diff expected actual)

So the last line seems to never terminate. Any ideas what might cause this?

alysbrooks commented 3 years ago

I was able to reproduce this, thanks for the test case! It looks like it's in the diffing algorithm itself, lambdaisland.clj_diff.miller$backtrack_snake, so this may actually be an issue with lambdaisland/clj_diff. Our algorithm uses loop and recur, so that's why it's not overflowing the stack.

From jstack:

"main" #1 prio=5 os_prio=0 cpu=56912.97ms elapsed=101.84s tid=0x00007f3c8c012110 nid=0x3b1ca6 runnable  [0x00007f3c9254a000]
   java.lang.Thread.State: RUNNABLE
    at clojure.lang.RT.get(RT.java:760)
    at lambdaisland.clj_diff.miller$backtrack_snake.invokeStatic(miller.cljc:133)
    at lambdaisland.clj_diff.miller$backtrack_snake.invoke(miller.cljc:127)
    at lambdaisland.clj_diff.miller$next_edit.invokeStatic(miller.cljc:146)
    at lambdaisland.clj_diff.miller$next_edit.invoke(miller.cljc:140)
    at clojure.lang.AFn.applyToHelper(AFn.java:186)
    at clojure.lang.AFn.applyTo(AFn.java:144)
    at clojure.core$apply.invokeStatic(core.clj:673)
    at clojure.core$partial$fn__5864.doInvoke(core.clj:2647)
    at clojure.lang.RestFn.invoke(RestFn.java:436)
    at lambdaisland.clj_diff.miller$edits.invokeStatic(miller.cljc:166)
    at lambdaisland.clj_diff.miller$edits.invoke(miller.cljc:156)
    at clojure.lang.AFn.applyToHelper(AFn.java:171)
    at clojure.lang.AFn.applyTo(AFn.java:144)
    at clojure.core$apply.invokeStatic(core.clj:671)
    at clojure.core$apply.invoke(core.clj:662)
    at lambdaisland.clj_diff.miller$seq_diff.invokeStatic(miller.cljc:209)
    at lambdaisland.clj_diff.miller$seq_diff.invoke(miller.cljc:205)
    at lambdaisland.clj_diff.miller$eval6153$fn__6154.invoke(miller.cljc:224)
    at clojure.lang.MultiFn.invoke(MultiFn.java:234)
    at lambdaisland.clj_diff.core$diff.invokeStatic(core.cljc:21)
    at lambdaisland.clj_diff.core$diff.invoke(core.cljc:5)
    at lambdaisland.deep_diff2.diff_impl$del_PLUS_ins.invokeStatic(diff_impl.cljc:65)
    at lambdaisland.deep_diff2.diff_impl$del_PLUS_ins.invoke(diff_impl.cljc:61)
    at lambdaisland.deep_diff2.diff_impl$diff_seq.invokeStatic(diff_impl.cljc:93)
    at lambdaisland.deep_diff2.diff_impl$diff_seq.invoke(diff_impl.cljc:92)
    at lambdaisland.deep_diff2.diff_impl$eval6455$fn__6456.invoke(diff_impl.cljc:171)
    at lambdaisland.deep_diff2.diff_impl$eval6333$fn__6334$G__6324__6341.invoke(diff_impl.cljc:11)
    at lambdaisland.deep_diff2.diff_impl$diff_similar.invokeStatic(diff_impl.cljc:134)
    at lambdaisland.deep_diff2.diff_impl$diff_similar.invoke(diff_impl.cljc:131)
    at lambdaisland.deep_diff2.diff_impl$diff.invokeStatic(diff_impl.cljc:151)
    at lambdaisland.deep_diff2.diff_impl$diff.invoke(diff_impl.cljc:144)
    at lambdaisland.deep_diff2$diff.invokeStatic(deep_diff2.cljc:20)
    at lambdaisland.deep_diff2$diff.invoke(deep_diff2.cljc:5)
    at user$eval8256.invokeStatic(NO_SOURCE_FILE:1)
    at user$eval8256.invoke(NO_SOURCE_FILE:1)
    at clojure.lang.Compiler.eval(Compiler.java:7181)
    at clojure.lang.Compiler.eval(Compiler.java:7136)
    at clojure.core$eval.invokeStatic(core.clj:3202)
    at clojure.core$eval.invoke(core.clj:3198)
    at clojure.main$repl$read_eval_print__9112$fn__9115.invoke(main.clj:437)
    at clojure.main$repl$read_eval_print__9112.invoke(main.clj:437)
    at clojure.main$repl$fn__9121.invoke(main.clj:458)
    at clojure.main$repl.invokeStatic(main.clj:458)
    at clojure.main$repl.doInvoke(main.clj:368)
    at clojure.lang.RestFn.applyTo(RestFn.java:137)
    at clojure.core$apply.invokeStatic(core.clj:667)
    at clojure.core$apply.invoke(core.clj:662)
    at rebel_readline.clojure.main$eval1451$repl_STAR___1452.invoke(main.clj:82)
    at rebel_readline.clojure.main$repl.invokeStatic(main.clj:91)
    at rebel_readline.clojure.main$repl.doInvoke(main.clj:90)
    at clojure.lang.RestFn.invoke(RestFn.java:397)
    at rebel_readline.clojure.main$_main.invokeStatic(main.clj:112)
    at rebel_readline.clojure.main$_main.doInvoke(main.clj:111)
    at clojure.lang.RestFn.applyTo(RestFn.java:137)
    at clojure.core$apply.invokeStatic(core.clj:667)
    at clojure.core$apply.invoke(core.clj:662)
    at rebel_readline.main$_main.invokeStatic(main.clj:6)
    at rebel_readline.main$_main.doInvoke(main.clj:5)
    at clojure.lang.RestFn.applyTo(RestFn.java:137)
    at clojure.lang.Var.applyTo(Var.java:705)
    at clojure.core$apply.invokeStatic(core.clj:667)
    at clojure.main$main_opt.invokeStatic(main.clj:514)
    at clojure.main$main_opt.invoke(main.clj:510)
    at clojure.main$main.invokeStatic(main.clj:664)
    at clojure.main$main.doInvoke(main.clj:616)
    at clojure.lang.RestFn.applyTo(RestFn.java:137)
    at clojure.lang.Var.applyTo(Var.java:705)
    at clojure.main.main(main.java:40)
alysbrooks commented 3 years ago

Hmm, this isn't a problem in 0.0-47, but it is a problem in 2.0.0-72, so perhaps it was introduced during changes made to clj-diff that we adopted in deep-diff2 but not deep-diff.

kevinmershon commented 2 years ago

Just ran into this issue today in certain circumstances and was very confused. Thank you @joda for providing the minimal example of it failing

plexus commented 2 years ago

Thanks @joda for the minimal repro and @alysbrooks for looking into this, this case has been fixed in lambdaisland/clj-diff, and we've upgrade deep-diff2 to make use of the fixed version.

[lambdaisland/deep-diff2 "2.1.121"]
{lambdaisland/deep-diff2 {:mvn/version "2.1.121"}}

[lambdaisland/clj-diff "1.2.62"]                                                                                                                                                                                                                                                  
{lambdaisland/clj-diff {:mvn/version "1.2.62"}}
kevinmershon commented 2 years ago

@plexus It looks like the latest update breaks compatibility with most stable jvm versions https://app.circleci.com/pipelines/github/lambdaisland/deep-diff2/104/workflows/f0790f39-a836-46e0-8d97-6e510ff151f8/jobs/302

plexus commented 2 years ago

I see, we'll have to pin the bytecode version we target. Small change but might be a day or two before I get to it. Sorry for the inconvenience!

plexus commented 2 years ago

Should be fixed in the latest versions

[lambdaisland/deep-diff2 "2.2.124"]
{lambdaisland/deep-diff2 {:mvn/version "2.2.124"}}