<< Back to previous view

[CLJS-784] PersistHashMap's -conj implementation recurses infinitely if element to be conjed is not a vector. Created: 15/Mar/14  Updated: 08/May/14  Resolved: 08/May/14

Status: Closed
Project: ClojureScript
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Alex Coventry Assignee: Michał Marczyk
Resolution: Completed Votes: 0
Labels: errormsgs
Environment:

Happens on cljsfiddle, among other environments.


Attachments: Text File 0001-CLJS-784-make-conj-on-maps-behave-as-it-does-in-Cloj.patch     Text File 0002-CLJS-784-Fix-Map.-conj-for-map-entry-seqs-that-don-t.patch     Text File 0003-CLJS-784-use-reduce-in-conj-on-maps.patch    

 Description   

In commit b8681e8 the implementation is

ICollection
  (-conj [coll entry]
    (if (vector? entry)
      (-assoc coll (-nth entry 0) (-nth entry 1))
      (reduce -conj coll entry)))

Thus, e.g., (-conj {} "foo") results in an infinite recursion, and a stack overflow. This causes things like (merge {} "foo") to fail for the same reason.

Not sure what the purpose of the not-vector branch could be. I can't think of a situation where it would give a useful result. Maybe it could throw a more helpful error message.



 Comments   
Comment by Michał Marczyk [ 22/Apr/14 6:13 AM ]

This actually applies to all three map types. (In fact, in (-conj {} "foo"), the map is an array map.) In Clojure, conj on a map works with a number of argument types:

1. map entries;

2. two-element vectors;

3. seqables of map entries.

The final case is, perhaps surprisingly, the oldest one. Merging maps falls under it, since for map arguments it boils down to merge minus special treatment of nil (merge uses conj to merge pairs of maps); but arbitrary seqables of map entries are supported. (NB. these must be actual map entries, not two-element vectors!) This allows one, for example, to filter a map and conj the result of that into another map.

So, we want to support the legitimate use cases while maybe complaining about code that wouldn't work in Clojure if it's not too much of a problem performance-wise. An example of a call that we'd probably like to throw: {{(conj {} (list (list [:foo 1])))}}.

The attached patch makes the -conj implementations in all the map types use an explicit loop in the non-vector branch and adds some test for the resulting behaviour.

Comment by David Nolen [ 05/May/14 5:07 PM ]

fixed https://github.com/clojure/clojurescript/commit/3d4405b9b22d36e2e686a084c54ae3f6e5a6208a

Comment by Herwig Hochleitner [ 06/May/14 6:11 AM ]

With patch 0001 (3d4405b), map conj fails for seqs, that don't implement -next.

(merge {:a 1} (hash-map :b 2))
;;=> Error: No protocol method INext.-next defined for type cljs.core/NodeSeq: ([:b 2])
...
at cljs.core.PersistentArrayMap.cljs$core$ICollection$_conj$arity$2 (http://localhost:6030/:15569:42)
...
Comment by Herwig Hochleitner [ 06/May/14 6:46 AM ]

I guess implementing INext is not part of the contract for ISeqable.-seq, which means NodeSeq doesn't have to implement it, right?
In that case, the right fix is to use next instead of -next inside of Map.-conj, when dealing with a (possibly user defined) seq of MapEntries.

Attached patch 0002 uses next instead of -next and adds tests for map-entry seqs not implementing INext

Comment by Michał Marczyk [ 06/May/14 3:04 PM ]

Good catch, thanks!

Another approach would be to use reduce, hopefully benefiting from IReduce speed boosts. Of course we'd need to use a custom reduction function wrapping -conj with a vector? check. The attached patch implements this.

Comment by Michał Marczyk [ 06/May/14 3:49 PM ]

Actually, scratch the part about IReduce speed boosts – sorry for the confusion!

Having run better benchmarks with the two patches on a recent build of V8 and I have to say that there doesn't seem to be much of a difference and actually the next-based approach comes out ahead sometimes. In Clojure, a hand-rolled loop-based "map-seq-conj" loses to a hand-rolled reduce-based impl consistently, as far as I can tell, although only by ~3-5%. I've been conj-ing seqs over vectors of vectors, which should be friendly to reduce.

Comment by Herwig Hochleitner [ 08/May/14 4:10 AM ]

Despite no direkt speed boost in benchmarks, I'm fond of using reduce here. GC Pressure is hard to benchmark.

Comment by David Nolen [ 08/May/14 6:18 PM ]

going to go with the next based patch.

Comment by David Nolen [ 08/May/14 6:18 PM ]

fixed https://github.com/clojure/clojurescript/commit/c1a29f1eceae9d1f1f637d9c5f2fa132efa58c47

Generated at Thu Nov 27 13:46:40 CST 2014 using JIRA 4.4#649-r158309.