ClojureScript

PersistHashMap's -conj implementation recurses infinitely if element to be conjed is not a vector.

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Minor Minor
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
  • Environment:
    Happens on cljsfiddle, among other environments.

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.

Activity

Hide
David Nolen added a comment -

going to go with the next based patch.

Show
David Nolen added a comment - going to go with the next based patch.
Hide
Herwig Hochleitner added a comment -

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

Show
Herwig Hochleitner added a comment - Despite no direkt speed boost in benchmarks, I'm fond of using reduce here. GC Pressure is hard to benchmark.
Hide
Michał Marczyk added a comment -

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.

Show
Michał Marczyk added a comment - 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.
Hide
Michał Marczyk added a comment -

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.

Show
Michał Marczyk added a comment - 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.
Hide
Herwig Hochleitner added a comment -

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

Show
Herwig Hochleitner added a comment - 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
Hide
Herwig Hochleitner added a comment -

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)
...
Show
Herwig Hochleitner added a comment - 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)
...
Hide
Michał Marczyk added a comment - - edited

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.

Show
Michał Marczyk added a comment - - edited 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.

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
    Resolved: