PersistentQueue, equiv, and hasheq

201 views
Skip to first unread message

Philip Potter

unread,
Sep 11, 2012, 2:52:05 PM9/11/12
to cloju...@googlegroups.com
Hi there,

I recently did a talk at the london clojure user group on persistent
data structures, and as a result I've been reading through the clojure
source code in some detail. It's really great, fascinating stuff,
which I've learned a lot from.

I spent a lot of time looking at PersistentQueue, which I found
fascinating, particularly since it isn't often mentioned in
introductory materials for Clojure.

However, PersistentQueue seems to have a few rough edges:

* It is a Sequential but not a List (reported as CLJ-1059)
* this means that you can construct an ArrayList al, vector v, and
queue q, such that:
(= al v)
(= v q)
(not= al q)
* It has an equiv() method but no hasheq()
* this means that (= #queue[(Long. -1)] #queue[(Integer. -1)]) but
their hasheq's differ
* It is a Sequential but doesn't implement the same hashing algorithm
as other Sequentials (which is in turn the one stipulated by
java.util.List)
* this means that (= [1 2 3] #queue[1 2 3]) but their hasheq's differ

Should I file tickets for these?

I have written some tests & fixes and am willing to supply patches. I
have signed a CA. I have implemented a proof-of-concept in these
branches:

https://github.com/philandstuff/clojure/tree/fix-queue-hasheq (adds
hasheq() to PersistentQueue)
https://github.com/philandstuff/clojure/tree/make-queue-implement-list
(as above, but also makes PersistentQueue implement List and use
List's hashing algorithm)

Phil

Philip Potter

unread,
Sep 15, 2012, 4:57:46 AM9/15/12
to cloju...@googlegroups.com
Hi there,

I realise my original message was rambly and didn't provide
cut-and-paste demostrations of the bugs. Let me try again, to see if I
can be clearer.

I would like to know the answers to two questions: should I file JIRA
tickets for these bugs? Should I attach patches?

--------------
1) PersistentQueue equality bug (already filed as CLJ-1059, but not vetted)

(def al (doto (java.util.ArrayList.) (addAll [1 2 3])))
(def q (conj clojure.lang.PersistentQueue/EMPTY 1 2 3))
[(= al [1 2 3]) (= [1 2 3] q) (= al q)]
;=> [true true false]

I expect [true true true] here, preserving transitivity of equality.

-----------------
2) PersistentQueue hashing doesn't match equality (not currently filed)

(def iq (conj clojure.lang.PersistentQueue/EMPTY (Integer. -1)))
(def lq (conj clojure.lang.PersistentQueue/EMPTY (Long. -1)))
[(= iq lq) (= (hash iq) (hash lq))]
;=> [true false]

I expect [true true] here, because if two values are equal they should
have the same hashcode. This means that you can put two equals into a
set:

#{iq lq}
;=> #{#<PersistentQueue clojure.lang.PersistentQueue@9e3779b8>
#<PersistentQueue clojure.lang.PersistentQueue@9e3779b9>}

I expect either IllegalArgumentException: Duplicate key, or a set with
size 1 here. I shouldn't get a set with size 2.

---------------------
3) PersistentQueue hashing doesn't match List hashing (not currently filed)

(def q (conj clojure.lang.PersistentQueue/EMPTY 1 2 3))
[(= [1 2 3] q) (= (hash [1 2 3]) (hash q))]
;=> [true false]

I expect [true true], because if two values are equal they should have
the same hashcode. Again you can put two equals into a set:

#{[1 2 3] q}
;=> #{[1 2 3] #<PersistentQueue clojure.lang.PersistentQueue@6b58d153>}

-----------------
Once again: should I file tickets? Should I attach patches?

(Am I following the process correctly here? According to
http://dev.clojure.org/display/design/JIRA+workflow it looks like I
shouldn't file a ticket til I've received approval on this list, and I
shouldn't file a patch til the ticket itself has been vetted. Is this
correct? If people accept these are genuine bugs, I'm ready to file
patches straight away!)

Phil

Andy Fingerhut

unread,
Sep 15, 2012, 12:03:33 PM9/15/12
to cloju...@googlegroups.com
If you do file a ticket, I highly recommend attaching patches, if you have them.  A ticket can be vetted with or without a patch attached, and if there is a patch, it might be vetted and screened all at once by a screener, saving one time examining the ticket by a screener.

From my quick look at your results, it appears like you've found a defect here, and it is worth creating a ticket to fix it.  Note that I'm not a screener, just another contributor.

Andy

On Sat, Sep 15, 2012 at 1:57 AM, Philip Potter <philip....@gmail.com> wrote:
Hi there,

Chris Houser

unread,
Sep 15, 2012, 12:21:39 PM9/15/12
to cloju...@googlegroups.com
On Sep 15, 2012, at 12:03 PM, Andy Fingerhut <andy.fi...@gmail.com> wrote:

If you do file a ticket, I highly recommend attaching patches, if you have them.  A ticket can be vetted with or without a patch attached, and if there is a patch, it might be vetted and screened all at once by a screener, saving one time examining the ticket by a screener.

From my quick look at your results, it appears like you've found a defect here, and it is worth creating a ticket to fix it.  Note that I'm not a screener, just another contributor.

I agree, this seems worthy of a ticket, and I'd you've got patches, please attach them.

--Chouser

--
You received this message because you are subscribed to the Google Groups "Clojure Dev" group.
To post to this group, send email to cloju...@googlegroups.com.
To unsubscribe from this group, send email to clojure-dev...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/clojure-dev?hl=en.

Philip Potter

unread,
Sep 15, 2012, 12:56:45 PM9/15/12
to cloju...@googlegroups.com
Thanks for the feedback. Should I submit one ticket or three? There
are three different issues, but they are all related and it might take
less time to process (and cause less conflicts between the patches) to
file as one...

Phil

Chris Houser

unread,
Sep 15, 2012, 1:01:36 PM9/15/12
to cloju...@googlegroups.com
Any patches that apply cleanly independently will go more smoothly as
separate tickets, I would think. For example, the equality fix might
be independent of the hash fixes.

But if the patches depend on each other, a single patch on a single
ticket would probably be fine.

--Chouser
Laboriously typed on my mobile device.

Philip Potter

unread,
Sep 15, 2012, 1:27:45 PM9/15/12
to cloju...@googlegroups.com
Okay, hash issues filed as CLJ-1070, equailty issue filed under
previous ticket of CLJ-1059. Will file patches once I get my
permission bump.

Phil

Bronsa

unread,
Sep 15, 2012, 3:05:29 PM9/15/12
to cloju...@googlegroups.com
I sumitted a patch for CLJ-1070, I didn't read you hade it ready.
Feel free to submit yours, I'm sorry.

Stuart Halloway

unread,
Sep 17, 2012, 7:57:45 AM9/17/12
to cloju...@googlegroups.com
Chouser,

Since you seem to have context could  you please screen these?

Stu
Stuart Halloway
Clojure/core
http://clojure.com

Philip Potter

unread,
Sep 18, 2012, 4:44:58 PM9/18/12
to cloju...@googlegroups.com
Chouser,

Thanks for your feedback on my previous patch on CLJ-1059. I've taken
on board what you said and attached another patch which tries an
alternative approach, but is a bit more of a refactoring.

Long story short, I split out a new class ASequential from ASeq, so I
could reuse the equality and the java.util.Collection/List stuff,
without having to directly implement ISeq, which somehow didn't feel
appropriate for PersistentQueue.

This patch also happens to fix both CLJ-1059 and CLJ-1070
simultaneously, since all of the ASeq equals/hashcode/equiv/hasheq
code was working correctly already.

I would appreciate feedback on whether this approach, or my original
patch, or something different, would be preferable.

Phil
Reply all
Reply to author
Forward
0 new messages