java.lang.IllegalArgumentException #178

Azhrei · 2018-03-14T02:37:05Z

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeLo(TimSort.java:777)
at java.util.TimSort.mergeAt(TimSort.java:514)
at java.util.TimSort.mergeCollapse(TimSort.java:441)
at java.util.TimSort.sort(TimSort.java:245)
at java.util.Arrays.sort(Arrays.java:1438)
at java.util.List.sort(List.java:478)
at java.util.Collections.sort(Collections.java:175)
at net.rptools.maptool.model.Zone.putToken(Zone.java:1114)
at net.rptools.maptool.client.ClientMethodHandler$1.run(ClientMethodHandler.java:220)
at java.awt.event.InvocationEvent.dispatch(InvocationEvent.java:311)
at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:756)
at java.awt.EventQueue.access$500(EventQueue.java:97)
at java.awt.EventQueue$3.run(EventQueue.java:709)
at java.awt.EventQueue$3.run(EventQueue.java:703)
at java.security.AccessController.doPrivileged(Native Method)
at java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:76)
at java.awt.EventQueue.dispatchEvent(EventQueue.java:726)
at net.rptools.maptool.client.swing.MapToolEventQueue.dispatchEvent(MapToolEventQueue.java:36)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:109)
at java.awt.WaitDispatchSupport$2.run(WaitDispatchSupport.java:184)
at java.awt.WaitDispatchSupport$4.run(WaitDispatchSupport.java:229)
at java.awt.WaitDispatchSupport$4.run(WaitDispatchSupport.java:227)
at java.security.AccessController.doPrivileged(Native Method)
at java.awt.WaitDispatchSupport.enter(WaitDispatchSupport.java:227)
at java.awt.Dialog.show(Dialog.java:1084)
at java.awt.Component.show(Component.java:1671)
at java.awt.Component.setVisible(Component.java:1623)
at java.awt.Window.setVisible(Window.java:1014)
at java.awt.Dialog.setVisible(Dialog.java:1005)
at net.rptools.maptool.client.swing.MapToolEventQueue.displayPopup(MapToolEventQueue.java:62)
at net.rptools.maptool.client.swing.MapToolEventQueue.dispatchEvent(MapToolEventQueue.java:47)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:109)
at java.awt.WaitDispatchSupport$2.run(WaitDispatchSupport.java:184)
at java.awt.WaitDispatchSupport$4.run(WaitDispatchSupport.java:229)
at java.awt.WaitDispatchSupport$4.run(WaitDispatchSupport.java:227)
at java.security.AccessController.doPrivileged(Native Method)
at java.awt.WaitDispatchSupport.enter(WaitDispatchSupport.java:227)
at java.awt.Dialog.show(Dialog.java:1084)
at java.awt.Component.show(Component.java:1671)
at java.awt.Component.setVisible(Component.java:1623)
at java.awt.Window.setVisible(Window.java:1014)
at java.awt.Dialog.setVisible(Dialog.java:1005)
at net.rptools.maptool.client.swing.MapToolEventQueue.displayPopup(MapToolEventQueue.java:62)
at net.rptools.maptool.client.swing.MapToolEventQueue.dispatchEvent(MapToolEventQueue.java:47)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:109)
at java.awt.WaitDispatchSupport$2.run(WaitDispatchSupport.java:184)
at java.awt.WaitDispatchSupport$4.run(WaitDispatchSupport.java:229)
at java.awt.WaitDispatchSupport$4.run(WaitDispatchSupport.java:227)
at java.security.AccessController.doPrivileged(Native Method)
at java.awt.WaitDispatchSupport.enter(WaitDispatchSupport.java:227)
at java.awt.Dialog.show(Dialog.java:1084)
at java.awt.Component.show(Component.java:1671)
at java.awt.Component.setVisible(Component.java:1623)
at java.awt.Window.setVisible(Window.java:1014)
at java.awt.Dialog.setVisible(Dialog.java:1005)
at net.rptools.maptool.client.swing.MapToolEventQueue.displayPopup(MapToolEventQueue.java:62)
at net.rptools.maptool.client.swing.MapToolEventQueue.dispatchEvent(MapToolEventQueue.java:47)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:109)
at java.awt.WaitDispatchSupport$2.run(WaitDispatchSupport.java:184)
at java.awt.WaitDispatchSupport$4.run(WaitDispatchSupport.java:229)
at java.awt.WaitDispatchSupport$4.run(WaitDispatchSupport.java:227)
at java.security.AccessController.doPrivileged(Native Method)
at java.awt.WaitDispatchSupport.enter(WaitDispatchSupport.java:227)
at java.awt.Dialog.show(Dialog.java:1084)
at java.awt.Component.show(Component.java:1671)
at java.awt.Component.setVisible(Component.java:1623)
at java.awt.Window.setVisible(Window.java:1014)
at java.awt.Dialog.setVisible(Dialog.java:1005)
at net.rptools.maptool.client.swing.MapToolEventQueue.displayPopup(MapToolEventQueue.java:62)
at net.rptools.maptool.client.swing.MapToolEventQueue.dispatchEvent(MapToolEventQueue.java:47)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:109)
at java.awt.WaitDispatchSupport$2.run(WaitDispatchSupport.java:184)
at java.awt.WaitDispatchSupport$4.run(WaitDispatchSupport.java:229)
at java.awt.WaitDispatchSupport$4.run(WaitDispatchSupport.java:227)
at java.security.AccessController.doPrivileged(Native Method)
at java.awt.WaitDispatchSupport.enter(WaitDispatchSupport.java:227)
at java.awt.Dialog.show(Dialog.java:1084)
at java.awt.Component.show(Component.java:1671)
at java.awt.Component.setVisible(Component.java:1623)
at java.awt.Window.setVisible(Window.java:1014)
at java.awt.Dialog.setVisible(Dialog.java:1005)
at net.rptools.maptool.client.swing.MapToolEventQueue.displayPopup(MapToolEventQueue.java:62)
at net.rptools.maptool.client.swing.MapToolEventQueue.dispatchEvent(MapToolEventQueue.java:47)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:201)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:116)
at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:105)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:101)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:93)
at java.awt.EventDispatchThread.run(EventDispatchThread.java:82)

irisiflimsi · 2018-03-14T13:25:53Z

I don't know whether I already said this. There are two ways of violating the comparator-contract: equals!=0 but not compare=0. The implementation doesn't look like this can happen. The other is compare!=0 but equals=0. This can happen, when, for instance, a token is cloned and his z-order is changed. I couldn't quite find how exactly this can happen, but cloning happens "close" to the Zone, so I think this is the likely culprit. Looking at the code of timsort and also the comments on this "contract" issue, it is hard to understand when exactly this problem appears. I couldn't get the violation to appear by randomly and semi-randomly creating contract violations.

I would suggest fixing this by having a clause "if (equal) return 0". as first statement in the comparator.

Do we have this bug reproducible?

Jaggeroth · 2018-03-14T14:23:40Z

I don't believe we have ever been in the position to reproduce the bug.

I suspect the only way to solve this issue is to move the Zone.getFigureZOrder() logic into the Token.getZOrder() method.

Syndaryl · 2018-03-14T14:28:09Z

We're beginning to get this weekly, although it's not clear on exactly how we're provoking it. One particular client or another will be afflicted with it; the exceptions go away after that client disconnects and reconnects to the server.
EDIT: To be clear, it's no one specific client with the issue. It isn't everyone, and it isn't simultaneously, but we will have multiple players per night afflicted.

Jaggeroth · 2018-03-14T14:44:34Z

Can I ask if you are using Figure Tokens on your maps?

Azhrei · 2018-03-14T15:08:48Z

I don’t think that’s the problem.

When I looked at this previously, I saw an IF statement in the middle of the routine and it looked like it could cause inconsistent return values (so that in one case it might return a value, but when the params were swapped it didn’t return the opposite value), however, my train was coming and I didn’t have time to fix it.

(Sorry, bad joke.)

Anyway, I plan to focus on that area of the code when I have time later today.

irisiflimsi · 2018-03-14T15:45:48Z

Hmm, I can't see that (asymmetry). On the other hand, the whole thing is not thread-safe, i.e. when queried, changing tokens may produce inconsistent results. This may be the underlying cause, because (if I understand correctly) this issue requires a client. But then the problem is not correlated to timsort. Is one of the finders able to activate the no-timsort-switch to check?

(The "correction" I proposed would solve the timsort-contract-violation most probably, so while not understanding the root cause, would fix that issue in isolation.)

Jaggeroth · 2018-03-14T16:13:28Z

Are we all looking at the same comparator? Zone.getZOrderComparator() ?

I naturally assume the "bug" is in the Figure Token logic as I added that ;)

Phergus · 2018-03-14T17:27:33Z

I'm not sure that a client connection is required. I received a campaign from one of those reporting the issue but could not reproduce it on my end. After I reported back to her, she said that she loaded the campaign and within a couple minutes she had reproduced it just by moving tokens around.

Syndaryl · 2018-03-14T17:48:05Z

We're using figure tokens, yes. And some pogs.

Azhrei · 2018-03-14T17:57:37Z

Well, now I'm looking at the code and I don't remember what I saw as the problem. :(

I think the issue might be the OR condition. The contract says that if A<B and B<C, then A<C. But I think that OR condition can cause the contract to fail. I need to study that some more and walk through it with a couple of examples to see if that's correct...

Azhrei · 2018-03-14T19:14:41Z

So... Say there are two CIRCLEs and a FIGURE, call them C1, C2, and F. Given this Comparator, C1 and C2 would be compared based on their z property (and by object ID if the z properties are the same). So let's say C1 has a z value of 100 and C2 has a z value of 200. Clearly, C1<C2 is true.

Now add F. When comparing C1 and F, the comparison is completely different and it's possible that C1>F but C2<F, thus breaking the contract.

The question is: How do we fix this? I need to review the code for getFigureZOrder() to figure out what a possible solution might be. I have a couple ideas, but I need to review it in more detail.

Phergus · 2018-03-14T19:45:32Z

The point is to get them in the correct Z order is it not? If so, the first test is always z-order and thus F cant be simultaneously less than C1 (100) while also greater than C2 (200).
One of these has to be true:

F.z < C1.z and thus F < C1 < C2
F.z == C1.z and thus either F < C1 < C2 or C1 < F < C2 based on Object ID comparison
C1.z < F.z < C2.z and thus C1 < F < C2
F.z == C2.z and either C1 < F < C2 or C1 < C2 < F based on Object ID comparison
C1.z < C2.z < F.z and thus C1 < C2 < F
It's only when they are equal in Z order that the object ID is compared, right?

Phergus · 2018-03-14T20:08:02Z

FWIW, just heard back from Hypatia and she says,

The error used to occur both running a server and also just working on my own unconnected to anything. Since I have changed all tokens so that none of them are figures then I have not experienced the error at all since we last messaged.

Jaggeroth · 2018-03-14T20:22:19Z

I have long suspected it was a mixture of Figure Tokens and non-figure tokens that was causing the issue.

The logic in the current Zone.getZOrderComparator() is correct but it can break the contract because it uses a certain set of logic to decide z-order if a figure token is involved, but otherwise just uses the z valve. This means that SquareTokenA could be less than FigureToken and FigureToken could be less than SquareTokenB but SquareTokenB might be more than SquareTokenA :(

This means the logic needs a complete rework. Let me mull ...

irisiflimsi · 2018-03-14T20:37:41Z

Breaking the contract also means that the "logic" is flawed, transitivity is quite elementary. To me it looks as if the intention is that the z-order for a figure is calculated (and not just "gotten"). That should be easy. The height piece can also be kept for all tokens. (I don't know, if non-figure tokens have height != 0, but since it's a fallback, it doesn't matter.) The isStamp/isToken combo is suspicious and probably also not transitive. What is the intention?

Jaggeroth · 2018-03-14T20:51:42Z

If a figure token is actually a "stamp" then it is really part of the background and should always be behind another figure token that stands on the same square.

The issue with Figure Tokens is that they need a certain logic to decide who goes in front of who and they loose the ability to be "arranged".

I would say that maybe all figure tokens should go in front or behind other types of tokens, but then you get the issue of "stamps" and tokens.

Azhrei · 2018-03-14T23:22:23Z

Yeah, I think this is going to require the author (thats you!) to decide what the sort order should actually be in a variety of situations. Then you can figure out how to implement it...

Jaggeroth · 2018-03-15T00:00:09Z

I've been mulling ... which involves wine and dog walks ... and I think I know the solution.

There is a special stage within the Zone Rendering process when all the figure tokens are rendered again. This is necessary due to the ways in which figure tokens can break the rules about Object and Token layers and how they can break the rules regarding the VBL. This is the ONLY point at which the special rules regarding foreground positioning are needed and at this point you are only dealing with Figure Tokens.

Therefore I can solve the problem by using the original simple z-order comparator, except during this special stage during Zone Rendering, where I will use a version that only does the Figure comparisons. Which will not break the transitivity rules.

Initial tests look promising, although I've never been able to recreate the problem so its something of guess that the solution will work.

Azhrei · 2018-03-15T00:09:12Z

That's a great idea. That leaves it to Craig to fix when he rewrites the rendering pipeline! Woohoo! 😉

Jaggeroth · 2018-03-15T07:40:51Z

While I recognise you are joking, it should solve the problem by limiting the sort logic. So should not cause any problems to whoever rewrites the renderer :-)

irisiflimsi · 2018-03-15T07:58:27Z

Here's a test that exposes the problem, now that we know where it is:

public static void main(String[] args) {
    Random r = new Random();
    List<Token> l = new LinkedList<>();
    for (int i = 0; i < 1000; i++) {
        Token t = new Token();
        if (r.nextInt(3) == 1) {
            t.setShape(Token.TokenShape.FIGURE);
        }
        t.setZOrder(r.nextInt(5));
        t.setHeight(r.nextInt(5));
        l.add(t);
    }
    Collections.sort(l, new C());
}

(The bounding rectangle depends on the grid - I made it constant 10+10+10x10. C is the comparator, of course.)

Jaggeroth · 2018-03-15T09:33:42Z

I have a fix.
Currently testing.

Azhrei · 2018-05-22T22:04:50Z

So this is done and merged, right? I can close this one?

Jaggeroth · 2018-05-22T22:31:30Z

Yes. This is fixed by pull request
"Z order violation #179"

Azhrei added the bug label Mar 14, 2018

Azhrei closed this as completed May 26, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

java.lang.IllegalArgumentException #178

java.lang.IllegalArgumentException #178

Azhrei commented Mar 14, 2018

irisiflimsi commented Mar 14, 2018 •

edited

Loading

Jaggeroth commented Mar 14, 2018

Syndaryl commented Mar 14, 2018 •

edited

Loading

Jaggeroth commented Mar 14, 2018

Azhrei commented Mar 14, 2018

irisiflimsi commented Mar 14, 2018

Jaggeroth commented Mar 14, 2018

Phergus commented Mar 14, 2018

Syndaryl commented Mar 14, 2018

Azhrei commented Mar 14, 2018

Azhrei commented Mar 14, 2018

Phergus commented Mar 14, 2018

Phergus commented Mar 14, 2018

Jaggeroth commented Mar 14, 2018

irisiflimsi commented Mar 14, 2018 •

edited

Loading

Jaggeroth commented Mar 14, 2018

Azhrei commented Mar 14, 2018

Jaggeroth commented Mar 15, 2018

Azhrei commented Mar 15, 2018

Jaggeroth commented Mar 15, 2018

irisiflimsi commented Mar 15, 2018 •

edited

Loading

Jaggeroth commented Mar 15, 2018

Azhrei commented May 22, 2018

Jaggeroth commented May 22, 2018

java.lang.IllegalArgumentException #178

java.lang.IllegalArgumentException #178

Comments

Azhrei commented Mar 14, 2018

irisiflimsi commented Mar 14, 2018 • edited Loading

Jaggeroth commented Mar 14, 2018

Syndaryl commented Mar 14, 2018 • edited Loading

Jaggeroth commented Mar 14, 2018

Azhrei commented Mar 14, 2018

irisiflimsi commented Mar 14, 2018

Jaggeroth commented Mar 14, 2018

Phergus commented Mar 14, 2018

Syndaryl commented Mar 14, 2018

Azhrei commented Mar 14, 2018

Azhrei commented Mar 14, 2018

Phergus commented Mar 14, 2018

Phergus commented Mar 14, 2018

Jaggeroth commented Mar 14, 2018

irisiflimsi commented Mar 14, 2018 • edited Loading

Jaggeroth commented Mar 14, 2018

Azhrei commented Mar 14, 2018

Jaggeroth commented Mar 15, 2018

Azhrei commented Mar 15, 2018

Jaggeroth commented Mar 15, 2018

irisiflimsi commented Mar 15, 2018 • edited Loading

Jaggeroth commented Mar 15, 2018

Azhrei commented May 22, 2018

Jaggeroth commented May 22, 2018

irisiflimsi commented Mar 14, 2018 •

edited

Loading

Syndaryl commented Mar 14, 2018 •

edited

Loading

irisiflimsi commented Mar 14, 2018 •

edited

Loading

irisiflimsi commented Mar 15, 2018 •

edited

Loading