possible bug in `case'
Eric Schulte
The following case statement
#+begin_src clojure
(defn buggy-case [n]
(case (int n)
0 :null
1 :load
0x70000000 :loproc))
#+end_src
throws the following error
No distinct mapping found
[Thrown class java.lang.IllegalArgumentException]
However removing any of the cases alleviates the problem. Am I missing
something obvious, or is this a bug in the case statement?
Thanks -- Eric
Alan
on min-hash to generate ahead-of-time hashes of all the test clauses,
and while I can't easily follow what's going on, it seems to be trying
to find a shift/mask combination that is...somehow related to the
hashes of the test clauses. I speculate that it's easier to perform
this operation on N values than N+1; with (0,0x70000000) it's hard,
but with another 1 it becomes unmanageable with the simple algorithm.
Alex Osborne
Interesting! I hadn't looked at how case was implemented before. It
takes the keys and then finds a shift and bitmask which can be used to
differentiate them with a minimum number of contiguous bits. The
private function clojure.core/min-hash is used to do this. For example
if you have the case keys 0x400, 0x500 and 0x7700 then:
(min-hash [0x400 0x500 0x7700]) => [8 3]
Which means bit-shift-right by 8 bits and then bitwise-and by 3. So if
we apply that to our keys we get:
(map #(shift-mask 8 3 %) [0x400 0x500 0x7700]) => (0 1 3)
The resulting values are then turned into a jump table which the
tableswitch JVM instruction dispatches on.
The maximum size of the mask is 14 bits, presumably as that's the
maximum the tableswitch instruction supports.
Now the problem in your case is there's no simple shift mask that is
unique. If we write your keys in binary then the problem is obvious:
0000000000000000000000000000000
0000000000000000000000000000001
1110000000000000000000000000000
^-------------^
0000000000000000000000000000000
0000000000000000000000000000001
1110000000000000000000000000000
^-------------^
There's no way to position the 14-bit mask (the ^-------------^ in my
diagram) to obtain a unique result.
It looks like Java's switch statement falls back to the lookupswitch
instruction which is apparently usually implemented with a binary
search. That doesn't seem to be implemented in Clojure and would in any
case be breaking the "constant time" contract the case macro's docstring
mentions (binary search is logarithmic time).
Stuart Halloway
Volunteers welcome!
Stu
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en