PersistentQueue doesn't implement java.util.List, causing nontransitive equality

Question

PersistentQueue implements Sequential but doesn't implement java.util.List. Lists form an equality partition, as do Sequentials. This means that you can end up with nontransitive equality:

(def q (conj clojure.lang.PersistentQueue/EMPTY 1 2 3)) ;=> #user/q (def al (doto (java.util.ArrayList.) (.add 1) (.add 2) (.add 3))) ;=> #user/al (def v [1 2 3]) ;=> #user/v (= al v) ;=> true (= v q) ;=> true (not= al q) ;=> true

This happens because PersistentQueue is a Sequential but not a List, ArrayList is a List but not a Sequential, and PersistentVector is both.

Answer 1

Comment made by: ppotter

Whoops, according to http://dev.clojure.org/display/design/JIRA workflow I should have emailed clojure-dev before filing this ticket. Here is the discussion:

https://groups.google.com/d/topic/clojure-dev/ME3-Ke-RbNk/discussion

Answer 2

Comment made by: ppotter

Attached 001-make-PersistentQueue-implement-List.diff, 15/Sep/12

Note that this patch has a minor conflict with the one I added to CLJ-1070, because both add an extra interface to PersistentQueue - List in this case, IHashEq in CLJ-1070.

Answer 3

Comment made by: chouser@n01se.net

Philip, patch looks pretty good -- thanks for doing this. A couple notes:

This is only my opinion, but I prefer imports be listed without wildcards, even if it means an extra couple lines at the top of a .java file.

I noticed the "List stuff" code is a copy of what's in ASeq and EmptyList. I suppose this is copied because EmptyList and PersistentQueue extend Obj and therefore can't extend ASeq. Is this the only reason? It seems a shame to duplicate these method definitions, but I don't know of a better solution, do you?

It would also be nice if the test check a couple of the List methods you've implemented.

Answer 4

Comment made by: chouser@n01se.net

oh, also "git am" refused to apply the patch, but I'm not sure why. "patch -p 1" worked perfectly.

Answer 5

Comment made by: ppotter

did you use the --keep-cr option to git am?

I struggled to know whether I should be adding CRs or not to line endings, because the files I was editing weren't consistent in their usage. If you open them in emacs, half the lines have ^M at the end.

Answer 6

Comment made by: ppotter

Will submit another patch, with the import changed. I'll have a think about the list implementation and see what ideas I can come up with.

Answer 7

Comment made by: ppotter

Attached 002-make-PersistentQueue-implement-Asequential.diff

This patch is an alternative to 001-make-PersistentQueue-implement-List.diff

So I took on board what you said about ASeq, but it didn't feel right making PersistentQueue directly implement ISeq, somehow.

So I split ASeq into two parts -- ASequential, which implements j.u.{Collection,List} and manages List-equality and hashcodes; and ASeq, which... doesn't seem to be doing much anymore, to be honest.

As a bonus, this patch fixes CLJ-1070 too, so I went and added the tests from that ticket in to demonstrate this fact. It also tidies up PersistentQueue by removing all equals/hashcCode stuff and all Collection stuff.

(It turns out that because ASeq was already implementing Obj, the fact that PersistentQueue was implementing Obj was no barrier to using it.)

Would appreciate comments on this approach, and how it differs from the previous patch here and the patch on CLJ-1070.

Answer 8

Comment made by: ppotter

Looking at EmptyList's implementation of List, it is a duplicate of the others, but it shouldn't be. I think its implementation of indexOf is the biggest culprit - it should just be 'return -1;' but it has a great big for loop! But this is beyond the scope of this ticket, so I won't patch that here.

Answer 9

Comment made by: jafingerhut

Philip, now that the patch for CLJ-1070 has been applied, these patches no longer apply cleanly. Would you be willing to update them? If so, please remove the obsolete patches.

Answer 10

Comment made by: ppotter

Andy, thanks so much for your efforts to make people aware of these things. I will indeed submit new patches, hopefully later this week.

Answer 11

Comment made by: ppotter

Replaced existing patches with new ones which apply cleanly to master.

There are two patches:

001-clj-1059-make-persistentqueue-implement-list.diff

This fixes equality by making PersistentQueue implement List directly. I also took the opportunity to remove the wildcard import and to add tests for the List methods, as compared with the previous version of the patch.

002-clj-1059-asequential.diff

This fixes equality by creating a new abstract class ASequential, and making PersistentQueue extend this.

My preferred solution is still the ASequential patch, but I'm leaving both here for comparison.

Answer 12

Comment made by: halgari

Vetting.

Answer 13

Comment made by: jafingerhut

Philip, this time I think it was patches that were committed for CLJ-1000 that make your patch 002-clj-1059-asequential.diff not apply cleanly. I often fix up stale patches where the change is straightforward and mechanical, but in this case you are moving some methods that CLJ-1000's patch changed the implementation of, so it would be best if someone figured out a way to update this patch in a way that doesn't clobber the CLJ-1000 changes.

Answer 14

Comment made by: ppotter

Thanks Andy. Submitted a new patch, 002-clj-1059-asequential-rebased-to-cached-hasheq.diff, which supersedes 002-clj-1059-asequential.diff.

The patch 001-clj-1059-make-persistentqueue-implement-list.diff still applies cleanly, and is still an alternative to 002-clj-1059-asequential-rebased-to-cached-hasheq.diff.

Answer 15

Comment made by: jafingerhut

With the commits to Clojure master made in the week leading up to Jan 30 2014, particularly changes to hasheq, patch 002-clj-1059-asequential-rebased-to-cached-hasheq.diff no longer applies cleanly.

Patch 001-clj-1059-make-persistentqueue-implement-list.diff still does.