<< Back to previous view

[CLJ-1059] PersistentQueue doesn't implement java.util.List, causing nontransitive equality Created: 03/Sep/12  Updated: 31/Mar/14

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.4
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Philip Potter Assignee: Philip Potter
Resolution: Unresolved Votes: 1
Labels: queue

Attachments: File 001-clj-1059-make-persistentqueue-implement-list.diff     File 002-clj-1059-asequential-rebased-to-cached-hasheq.diff    
Patch: Code and Test

 Description   

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.



 Comments   
Comment by Philip Potter [ 15/Sep/12 3:41 AM ]

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

Comment by Philip Potter [ 15/Sep/12 2:37 PM ]

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.

Comment by Chouser [ 18/Sep/12 1:04 AM ]

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.

Comment by Chouser [ 18/Sep/12 1:08 AM ]

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

Comment by Philip Potter [ 18/Sep/12 1:19 AM ]

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.

Comment by Philip Potter [ 18/Sep/12 1:21 AM ]

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.

Comment by Philip Potter [ 18/Sep/12 3:17 PM ]

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.

Comment by Philip Potter [ 18/Sep/12 3:44 PM ]

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.

Comment by Andy Fingerhut [ 20/Oct/12 12:29 PM ]

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.

Comment by Philip Potter [ 22/Oct/12 5:10 AM ]

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

Comment by Philip Potter [ 03/Nov/12 12:23 PM ]

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.

Comment by Timothy Baldridge [ 30/Nov/12 3:37 PM ]

Vetting.

Comment by Andy Fingerhut [ 11/Dec/12 12:50 PM ]

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.

Comment by Philip Potter [ 11/Dec/12 1:57 PM ]

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.

Comment by Andy Fingerhut [ 30/Jan/14 4:50 PM ]

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.

Comment by Andy Fingerhut [ 31/Mar/14 5:33 PM ]

This issue was run into again and a duplicate ticket CLJ-1374 created – later closed as a duplicate of this one. Just wanted to record that this issue is being hit by others besides those originally reporting it.





Generated at Wed Jul 30 02:12:40 CDT 2014 using JIRA 4.4#649-r158309.