Clojure

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

Details

  • Type: Defect Defect
  • Status: Open Open
  • Priority: Major Major
  • Resolution: Unresolved
  • Affects Version/s: Release 1.4
  • Fix Version/s: None
  • Component/s: None
  • Labels:
  • 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.

Activity

Hide
Philip Potter added a comment -

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

Show
Philip Potter added a comment - 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
Hide
Philip Potter added a comment -

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.

Show
Philip Potter added a comment - 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.
Philip Potter made changes -
Field Original Value New Value
Attachment 001-make-PersistentQueue-implement-List.diff [ 11501 ]
Andy Fingerhut made changes -
Patch Code and Test [ 10002 ]
Philip Potter made changes -
Affects Version/s Release 1.4 [ 10040 ]
Philip Potter made changes -
Assignee Philip Potter [ ppotter ]
Hide
Chouser added a comment -

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.

Show
Chouser added a comment - 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.
Hide
Chouser added a comment -

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

Show
Chouser added a comment - oh, also "git am" refused to apply the patch, but I'm not sure why. "patch -p 1" worked perfectly.
Hide
Philip Potter added a comment -

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.

Show
Philip Potter added a comment - 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.
Hide
Philip Potter added a comment -

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.

Show
Philip Potter added a comment - 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.
Hide
Philip Potter added a comment -

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.

Show
Philip Potter added a comment - 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.
Philip Potter made changes -
Attachment 002-make-PersistentQueue-implement-ASequential.diff [ 11509 ]
Hide
Philip Potter added a comment -

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.

Show
Philip Potter added a comment - 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.
Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.
Hide
Philip Potter added a comment -

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

Show
Philip Potter added a comment - Andy, thanks so much for your efforts to make people aware of these things. I will indeed submit new patches, hopefully later this week.
Philip Potter made changes -
Attachment 001-make-PersistentQueue-implement-List.diff [ 11501 ]
Philip Potter made changes -
Attachment 002-make-PersistentQueue-implement-ASequential.diff [ 11509 ]
Hide
Philip Potter added a comment -

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.

Show
Philip Potter added a comment - 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.
Philip Potter made changes -
Attachment 002-clj-1059-asequential.diff [ 11661 ]
Attachment 001-clj-1059-make-persistentqueue-implement-list.diff [ 11660 ]
Hide
Timothy Baldridge added a comment -

Vetting.

Show
Timothy Baldridge added a comment - Vetting.
Timothy Baldridge made changes -
Approval Vetted [ 10003 ]
Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.
Hide
Philip Potter added a comment -

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.

Show
Philip Potter added a comment - 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.
Philip Potter made changes -
Philip Potter made changes -
Attachment 002-clj-1059-asequential.diff [ 11661 ]
Rich Hickey made changes -
Approval Vetted [ 10003 ]
Alex Miller made changes -
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.
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:

{code}
(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
{code}

This happens because PersistentQueue is a Sequential but not a List, ArrayList is a List but not a Sequential, and PersistentVector is both.
Labels queue
Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.
Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.

People

Vote (1)
Watch (3)

Dates

  • Created:
    Updated: