ClojureScript

hash-map assoc stackoverflow

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None
  • Environment:
    Using clojurescript master and a browser environment

Description

A particular combination of keys in a hash-map will cause a stackoverflow when added into the same hash-map, whether using transient or non-transient assoc.

Minimal case:

(defrecord T [index a b])

(def bad-key-1 (map->T {:index :eavt, :a 17592186192276, :b nil}))
(def bad-key-2 (map->T {:index :avet, :a 10, :b :fhir.ElementDefinition/minValueDateTime$cr}))

;; Implicit Transient assoc
(hash-map bad-key-1 nil bad-key-2 nil)

;RangeError: Maximum call stack size exceeded

;;; From a browser console:
;core.cljs:5034 Uncaught RangeError: Maximum call stack size exceeded
;cljs.core.PersistentVector.cljs$core$ISeqable$_seq$arity$1 @ core.cljs:5034
;cljs$core$seq @ core.cljs:1121
;cljs.core.concat.cljs$core$IFn$_invoke$arity$2 @ core.cljs:3619
;cljs.core.LazySeq.sval @ core.cljs:3269
;cljs.core.LazySeq.cljs$core$ISeqable$_seq$arity$1 @ core.cljs:3323
;cljs$core$seq @ core.cljs:1121
;cljs.core.pr_str.call.cljs.user.T.cljs$core$ISeqable$_seq$arity$1 @ VM2295:158
;cljs$core$seq @ core.cljs:1121
;cljs$core$first @ core.cljs:1143
;(anonymous) @ core.cljs:4049
;cljs$core$every_QMARK_ @ core.cljs:4049
;cljs$core$equiv_map @ core.cljs:5836
;(anonymous) @ VM2295:114
;cljs.core.pr_str.call.cljs.user.T.cljs$core$IEquiv$_equiv$arity$2 @ VM2295:118
;cljs$core$_equiv @ core.cljs:617
;cljs.core._EQ_.cljs$core$IFn$_invoke$arity$2 @ core.cljs:1179
;cljs$core$key_test @ core.cljs:6494
;cljs.core.BitmapIndexedNode.inode_assoc_BANG_ @ core.cljs:6752
;cljs.core.create_node.cljs$core$IFn$_invoke$arity$7 @ core.cljs:7050
;(anonymous) @ core.cljs:6760
;;; Last 3 lines repeat forever


;; Explicit non-transient assoc
(assoc (hash-map bad-key-1 nil) bad-key-2 nil)

;RangeError: Maximum call stack size exceeded
;;; Stack is similar to above, except `inode-assoc` instead of `inode-assoc!`
;;; is repeating, because this version is not transient

As near as I can tell, the fundamental problem is that the (zero? (bit-and bitmap bit)) test in inode-assoc is always false. I have a hunch this is due to some bit-twiddling difference between js and Java that isn't accounted for in bit-count or bitmap-indexed-node-index or the recursive call to inode-assoc. I am investigating further.

Activity

Hide
Francis Avila added a comment -

(Just to note: we encountered this issue in production.)

The fundamental problem is that JS hash values may use more than 32 bits, but only 32 bits should be considered.

These two records have different hash values, but if only 32 bits are compared they have the same hash value. At least create-node naively assumes that hash values are normalized and does normal comparison between them using ==, meaning it does not detect the hash collision correctly.

This is a problem for records because they use an older (pre-murmur) hash-imap, which is not careful to truncate to 32 bits.

However, it is also a problem for dates for the same reason:

(hash-map #inst "2017-03-13T22:21:08.666-00:00" nil  #inst "2015-11-02T19:53:15.706-00:00" nil)
;RangeError: Maximum call stack size exceeded

My proposed fix is to force all hash values to be normalized to 32 bits to preserve the invariant that two equal hash values means they collide.

Show
Francis Avila added a comment - (Just to note: we encountered this issue in production.) The fundamental problem is that JS hash values may use more than 32 bits, but only 32 bits should be considered. These two records have different hash values, but if only 32 bits are compared they have the same hash value. At least create-node naively assumes that hash values are normalized and does normal comparison between them using ==, meaning it does not detect the hash collision correctly. This is a problem for records because they use an older (pre-murmur) hash-imap, which is not careful to truncate to 32 bits. However, it is also a problem for dates for the same reason:
(hash-map #inst "2017-03-13T22:21:08.666-00:00" nil  #inst "2015-11-02T19:53:15.706-00:00" nil)
;RangeError: Maximum call stack size exceeded
My proposed fix is to force all hash values to be normalized to 32 bits to preserve the invariant that two equal hash values means they collide.

People

Vote (0)
Watch (2)

Dates

  • Created:
    Updated:
    Resolved: