<< Back to previous view

[CLJ-944] Compiler sometimes gives constant collections types which mismatch with their runtime values Created: 04/Mar/12  Updated: 06/Mar/14  Resolved: 06/Mar/14

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.3, Release 1.4, Release 1.5
Fix Version/s: Release 1.6

Type: Defect Priority: Major
Reporter: Alf Kristian St√łyle Assignee: Unassigned
Resolution: Completed Votes: 2
Labels: compiler

Clojure 1.3 om Mac OS 10.7, Clojure 1.5.0 alpha1 on Linux x86_64 (OpenJDK 1.7.0 b147)

Attachments: Text File 0001-Fix-for-CLJ-944.patch     Text File 0002-Fix-for-CLJ-944.patch     Text File clj944-plus-tests.patch    
Patch: Code and Test
Approval: Ok

(.containsKey {:one 1} :one)
;=> ClassCastException clojure.lang.PersistentArrayMap cannot be cast to clojure.lang.PersistentHashMap

The map is a clojure.lang.PersistentArrayMap, which obviously has a containsKey method (https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentArrayMap.java#L95).

Casting it works fine though:

(.containsKey ^clojure.lang.PersistentArrayMap {:one 1} :one)
;=> true

The problem is not present in Clojure 1.2.1.

Cause: In the first example, the Compiler will parse the MapExpr (which reports a Java class of IPersistentMap) into a ConstantExpr whose value is a PersistentHashMap (and reports type as same). The .containsKey() call is a HostExpr which parses to an InstanceMethodExpr.

When emitted to bytecode, the ConstantExpr becomes a call to RT.map() to generate a map. RT.map() produces either a PersistentArrayMap or PersistentHashMap depending on size. The InstanceMethodExpr becomes a call to PersistentHashMap.containsKey() (based on the reported type of it's expression). In the case where RT.map() will produce a PersistentArrayMap at runtime (small maps), this causes a mismatch.

Note also that this same scenario occurs for constant sets, vectors, etc - all of those cases produce ConstantExpr's with the type of the concrete data structure, instead of the more general IPersistentMap, IPersistentSet, etc. All of those scenarios should be addressed in the same way. But, those interfaces do not capture the full capabilities of the returned object. The compiler and the marshaller need to agree on the types to produce.

Approach: One approach (A) explored previously was to have MapExpr always produce a ConstantExpr containing a value of the same type that will be produced at runtime by RT.map(). While this works, it is also fragile, and sidesteps the real issue that MapExpr creates a ConstantExpr with a type that is too specific. Rich said this is the wrong approach.

(B) Another approach is to create an anonymous subclass of ConstantExpr in MapExpr that overrides getJavaClass() to report a more general type. This isn't done anywhere else and it may have negative ramifications (but I have not found any).

(C) Another approach is to follow the path of example #2 above. That example wraps the map in a MetaExpr which reports getJavaClass() returning the hinted type. In the case above, it hints the concrete type that happens to match the return of RT.map(). Instead, we could wrap the ConstantExpr in a MetaExpr hinted on the abstract type IPersistentMap (the return type of RT.map()).

RH - a more general (interface) type will not give full capabilities. Perhaps APersistent*


Comment by Nicola Mometto [ 30/Oct/12 5:02 PM ]

The attached patch fixes the issue, by emitting IPersistentMap instead of Persistent{Hash|Array}Map as class type for maps literals

Comment by Nicola Mometto [ 01/Nov/12 3:48 PM ]

I uploaded another patch fixing the same problem in a different way.
While 0001-Fix-for-CLJ-944.patch makes clojure.lang.Complier.ConstantExpr#getJavaClass return clojure.lang.IPersistentMap for both clojure.lang.PersistentHashMap and clojure.lang.PersistentArrayMap, 0002-Fix-for-CLJ-944.patch makes clojure.lang.Compiler.MapExpr#parse return a PersistentArrayMap if the length is <= HASHTABLE_THRESHOLD, instead of always returning a PersistentHashMap.

This approach is more consistent, making the type of the compiler's internal representation of a map literal equal to the one of the reader.

Note that this second approach while being more consistent, breaks some tests that assume some operations on maps (specifically `seq` and `print`) to be order dependent, and written with the hash-map return order implementation in mind.

That should not be the case and if the second patch is preferred over the first one, I'll gladly fix those tests.

Comment by Stuart Halloway [ 01/Mar/13 12:09 PM ]

Approach #2, relying on consistent choice of concrete map class by size throughout, feels quite fragile.

Approach #1 seems to abuse the method name getJavaClass(), now having it return "get the base type I would need for cast".

Maybe there needs to be a different thing entirely?

Comment by Nicola Mometto [ 01/Mar/13 2:17 PM ]

Patch #2 should get merged (IMHO) regardless of the fragility of its approach to fixing this ticket's bug, since it fixes another bug:

prior to the patch:

user=> (class {:a 1})
user=> (def a {:a 1})
user=> (class a)

after the patch:

user=> (class {:a 1})
user=> (def a {:a 1})
user=> (class a)

This should also lead to some minor performance enhancement since prior to this moment, every map def'ed would be a HashMap instead of an ArrayMap

So, I think patch #2 should be applied if not for this ticket's bug, at least for the reason stated above.
If somebody has any proposal for making this patch more solid regarding this ticket's bug, any help is welcome

Comment by Rich Hickey [ 13/Apr/13 9:41 AM ]

This should not have passed screening. There are two issues, should be separate. I have no idea what has been screened nor what will be applied should it be approved. There's contention in the discussion but no resolution.

Comment by Nicola Mometto [ 13/Apr/13 12:06 PM ]

I don't think that there are two issues here.
The issue is only one: the compiler doesn't emit maps in a way consistent with what the reader returns and with how the compiler itself uses maps.
The symptoms are two: some interop calls fail, and def'ed vars with a literal map as value never use a PersistentArrayMap.

The underlying cause of those two symtoms is fixed by the patch 002 that i submitted (incorporated in Stu's clj944-plus-tests patch.

Stuart said that this approach feels fragile but the bug is caused by the fact that everywhere else clojure returns a PersistentArrayMap when the element count is <= than the PersistentHashMap threshold, and when emitting maps, it doesn't.

Making clojure emit maps consistently with how clojure does internally everywhere else looks to me like the only solution, and I don't really see how making clojure consistent is a fragile approach.

But again, if somebody can suggest a better solution to this problem, I'll gladly submit another patch.

Comment by Rich Hickey [ 14/Aug/13 8:36 AM ]

"Compiler makes different concrete maps then the reader" is not inherently a problem. But the code posted is a problem:

(.containsKey {:one 1} :one)
;=> ClassCastException clojure.lang.PersistentArrayMap cannot be cast to clojure.lang.PersistentHashMap

i.e. .containsKey isn't working in this scenario. Stating exactly why is the path to a good discussion and fix.

Comment by Nicola Mometto [ 14/Aug/13 10:01 AM ]

I don't know how you're getting that exception.

This patch removes exactly that problem, I just tried it out on a fresh clojure git repo with only that patch applied and it works:
Clojure 1.6.0-master-SNAPSHOT
user=> (.containsKey {:one 1} :one)

Comment by Alex Miller [ 16/Aug/13 10:49 AM ]

Nicola, I believe Rich is saying that:

1) the posted original example is showing a real problem
2) the title of the ticket and the suggested cause (compiler makes different concrete maps than the reader) is incorrect and that it is ok for them to make different concrete maps
3) the original error message (.containsKey isn't working) is the path to a correct diagnosis.

Rich is NOT saying that the patch doesn't resolve the error but rather that it resolves it in an undesired way due to a misdiagnosis of cause.

Comment by Nicola Mometto [ 17/Aug/13 7:38 AM ]

I'm going to try to describe as clearly as possible what's the problem and what could be the possible solutions (and thus what made me chose this as the best possible fix)

Problem: .containsKeys does not work on some maps

Constant maps are expressed as a ConstantExprs by the compiler; the ConstantExpr#getJavaClass method is implemented as a call to .getClass() on the constant object.

Since MapExpr#parse in case of a constant map always delegated to ConstantExpr a PersistentHashMap, it's clear that .getJavaClass on a ConstantExpr-wrapped map will always return PersistentHashMap.

This means that interop-calls will try to resolve PersistentHashMap methods instead of IPersistentMap (since they call .getJavaClass on the object to determine what to target).

When and why does this bug not manifest?

  • if the map is not constant:
    user=> (.containsKey {:one (Object.)} :one)
  • if the map gets compiled as opposed to being .eval'ed
    usser=> (def a (.containsKey {:one 1} :one))
    user=> a

This also mean that currently, maps that are hold in a Var or that are AOT compiled are always PHMs and never PAMs (removing a possible optimization)

What are the possible solutions?

  • Don't wrap constant maps in ConstantExprs so we always use MapExpr and remove the problem.
  • Special-case ConstantExpr#getJavaClass to return IPersistentMap for PHMs and PAMs (approach #1)
  • Be consistent in MapExpr#parse and create PAMs when the element number is above the PHM threshold as we do EVERYWHERE but in there. (approach #2)

Of the three possible solutions, the third seems to me the best one.

Comment by Alex Miller [ 18/Aug/13 3:55 PM ]

Thanks for this - it was a very useful summary for me as I'm still trying to get my head around all the details of this ticket. Stepping back a bit, I'd say in your diagnosis that the point at which I see something wrong is when MapExpr#parse returns something that depends on a particular implementation type (via getJavaClass).

Idea: what if MapExpr#Expr instead returned a anonymous subclass of ConstantExpr that overrode getJavaClass() to return IPersistentMap in this case?

return new ConstantExpr(m) { 
  public Class getJavaClass() {
    return IPersistentMap.class;
} };

That way, the ConstantExpr only commits to the abstraction. This seems to also fix the problem to me.

Separately, I agree that it may be useful as an optimization to emit a PAM instead of a PHM in this case (maybe even in all constant cases?). But I think we should not rely on two different pieces of code producing the identical map impl - that should be hidden behind the abstraction (IPersistentMap). I think I would like to break that out as an independent ticket though.

Comment by Alex Miller [ 18/Aug/13 4:03 PM ]

I see that my suggestion is effectively similar to the first patch on this ticket but (imho) cleaner in that it puts the change at the point where the knowledge exists and can thus be a simpler check.

Comment by Andy Fingerhut [ 08/Nov/13 10:19 AM ]

Patch clj944-plus-tests.patch no longer applies cleanly to latest master, probably due to changed context lines in a test file, but I haven't checked. Not worth updating until/unless there is agreement on what should be changed.

Comment by Nicola Mometto [ 08/Nov/13 1:27 PM ]

I would very like to see this fixed and will happily update my patches, however I'd first like some feedback on the correct approach here before making yet another patch.

Should we go with one of my two approaches or should I implement what Alex suggested?
Each approach fixes this bug, I stated before what's causing this and I have explained my solutions, Alex's one looks reasonable too, can we please get an opinion on what's the best move to get a satisfying fix for this?


Comment by Alex Miller [ 08/Nov/13 1:45 PM ]

Sorry it's not visible on the ticket, but I have actually spent several hours looking at this since my last comment but have not reached a final conclusion. I also would really like to see it fixed and have not given up on it yet.

Comment by Andy Fingerhut [ 08/Nov/13 1:53 PM ]

The most direct cause of the exception in the example of how to reproduce it is due to the compiler emitting a type check on a type that is different than the constant emitted.

This is just tossing out ideas, perhaps brain-dead ones, but eliminating that type check would eliminate the exception. Also, changing the emitted type check to be for a more general type than than the constant, e.g. IPersistentMap, should also eliminate the exception.

Comment by Nicola Mometto [ 08/Nov/13 2:27 PM ]

Alex, there's no need to be apologetic, I was in no way trying to imply a lack of interest, just asking for directions

Wrapping up for screeners/Rich:

Here is a diagnosis of the bug: http://dev.clojure.org/jira/browse/CLJ-944?focusedCommentId=31694&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-31694

To me now it looks like the best solutions right now are either:

  • My #2 solution: making MapExpr#parse return a PAM or a PHM consistently with RT/map
  • Alex's solution: making MapExpr#Expr return an anonymous subclass of ConstantExpr overriding getJavaClass() to return IPersistentMap

Right now my patch does not apply to master, and there is no patch implementing Alex's solution, once I get a feedback on which approach is preferable i can: update my patch to apply to master or implement Alex's solution (Alex, if you want to do it yourself I will not step in)

Comment by Alex Miller [ 08/Nov/13 2:33 PM ]

I have actually built a couple of variant patches locally but still have not convinced myself that any of them are the right patch to recommend. I hope to look at it again in the next couple weeks. I think the ticket itself is in the correct state (Incomplete). Ideally I would have a few minutes to look at it with Rich for further direction.

Comment by Nicola Mometto [ 20/Feb/14 6:50 PM ]

Any update on this? this is still marked for clojure 1.6

Comment by Alex Miller [ 20/Feb/14 8:59 PM ]

Actually yes! I spent some time on this today and have something to attach.

Comment by Nicola Mometto [ 22/Feb/14 12:28 PM ]

A problem I see with approaches b and c is that they don't address the issue I raised about (def a {:a 1}) here: http://dev.clojure.org/jira/browse/CLJ-944?focusedCommentId=29885&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-29885

Rich stated that it's a different issue than the one being discussed in this ticked, I don't agree, to me it's simply another symptom of the same bug.

I want to suggest a fourth alternative approach to this that combines approach -a with whichever is preferred between -b and -c.

Comment by Alex Miller [ 22/Feb/14 1:53 PM ]

Nicola, I'm not getting your point here (the linked comment doesn't seem to match up to the comments about (def a {:a 1}) so that's confusing me). In the case of (def a {:a 1}), my reading of the bytecode is that RT.map() (which returns IPersistentMap) will be invoked at runtime to generate the map. There is more than one potential concrete class for a (depending on size), but nothing is expecting it to be a particular concrete type here. I do not expect literal maps to retain order or be ArrayMaps (you should call array-map if you want that).

I'm hoping to get some consensus from Rich about the newly updated problem, cause, and approach before I move further. I'd currently classify the problem as the failed .containsKey call, the cause as the compiler replacing the MapExpr with an expression that specifies its type more narrowly than it should, and B and C as some candidate solutions.

If we want the compiler to generate concrete maps that match RT.map(), I think that's ok too, but I don't see it as the cause right now.

Comment by Nicola Mometto [ 22/Feb/14 2:25 PM ]

Alex, I'm sorry here's the correct link: http://dev.clojure.org/jira/browse/CLJ-944?focusedCommentId=30684&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-30684

Your analysis of the emitted bytecode is correct, however when the code is loaded JIT, calls to `def` will be interpreted https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Compiler.java#L409-L434 as a result, if the initexpr is a ConstantExpr, the in-memory value of that ConstantExpr will be used and if it's the case that the expression is a map, that will always be a PHM.

I understand that switching between PAMs and PHMs is merely an optimization but having code behave differently if it's AOT compiled rather than JIT loaded is undesiderable IMHO.

Comment by Nicola Mometto [ 22/Feb/14 2:41 PM ]

Immediatelly after posting the previous response it occurred to me that approaches b and c have an inherent problem:
with that approach it's no longer possible to access public fields/methods in instances of PAMs or PHMs that do not belong in IPersistentMap without incurring in reflection.

This means that for example calls to java.lang.Map instance methods would require type-hinting the map literal while now it can be resolved at compile-time without the need of type-hinting.

Here's an example using a first patch that implements the fix as described by approaches -b or -c

user=>  (set! *warn-on-reflection* true)

;; pre patch
user=>  (.isEmpty {:a 1})

;; after patch
user=>  (.isEmpty {:a 1})
Reflection warning, NO_SOURCE_PATH:2:2 - reference to field isEmpty on clojure.lang.IPersistentMap can't be resolved.
Comment by Alex Miller [ 05/Mar/14 11:44 AM ]

Remove from 1.6 release. Still needs more analysis.

Comment by Alex Miller [ 06/Mar/14 7:53 AM ]

Reopened just to fix the ticket fields.

Generated at Tue Jan 23 10:30:18 CST 2018 using JIRA 4.4#649-r158309.