Bug merging maps with option duplicates:combine?
Hello, When executing: map:merge(( map { "DENW21AL100077Hs": "a", "DENW21AL100076i5": "a" }, map { "DENW21AL100077Hs": "b", "DENW21AL100076i5": "b", "DENW21AL100076hT": "b" } ), map {'duplicates': 'combine'}) in the BaseX GUI I get: Error: Improper use? Potential bug? Your feedback is welcome: Contact: basex-talk@mailman.uni-konstanz.de Version: BaseX 9.3.1 Java: AdoptOpenJDK, 1.8.0_212 OS: Windows 10, amd64 Stack Trace: java.lang.ArrayIndexOutOfBoundsException: 2 at org.basex.query.value.map.TrieList.add(TrieList.java:199) at org.basex.query.value.map.TrieList.addAll(TrieList.java:141) at org.basex.query.value.map.XQMap.addAll(XQMap.java:106) at org.basex.query.func.map.MapMerge.item(MapMerge.java:33) at org.basex.query.func.StandardFunc.optimize(StandardFunc.java:82) at org.basex.query.expr.Arr.compile(Arr.java:43) at org.basex.query.scope.MainModule.comp(MainModule.java:81) at org.basex.query.QueryCompiler.compile(QueryCompiler.java:114) at org.basex.query.QueryCompiler.compile(QueryCompiler.java:105) at org.basex.query.QueryContext.compile(QueryContext.java:312) at org.basex.query.QueryProcessor.compile(QueryProcessor.java:79) at org.basex.core.cmd.AQuery.query(AQuery.java:93) at org.basex.core.cmd.XQuery.run(XQuery.java:22) at org.basex.core.Command.run(Command.java:257) at org.basex.core.Command.execute(Command.java:93) at org.basex.gui.GUI.exec(GUI.java:422) at org.basex.gui.GUI.lambda$4(GUI.java:365) at java.lang.Thread.run(Thread.java:748) Best regards, Johannes
Hi all, While I don't have any answer to this question, I can corroborate Johannes' finding. Also, Johannes, did you find a magic string? I tried some longer keys and they seem to work :) Best, Bridger On Thu, Jan 9, 2020 at 11:51 AM Johannes Echterhoff < echterhoff@interactive-instruments.de> wrote:
Hello,
When executing:
map:merge(( map { "DENW21AL100077Hs": "a", "DENW21AL100076i5": "a" }, map { "DENW21AL100077Hs": "b", "DENW21AL100076i5": "b", "DENW21AL100076hT": "b" } ), map {'duplicates': 'combine'})
in the BaseX GUI I get:
Error:
Improper use? Potential bug? Your feedback is welcome:
Contact: basex-talk@mailman.uni-konstanz.de
Version: BaseX 9.3.1
Java: AdoptOpenJDK, 1.8.0_212
OS: Windows 10, amd64
Stack Trace:
java.lang.ArrayIndexOutOfBoundsException: 2
at org.basex.query.value.map.TrieList.add(TrieList.java:199)
at org.basex.query.value.map.TrieList.addAll(TrieList.java:141)
at org.basex.query.value.map.XQMap.addAll(XQMap.java:106)
at org.basex.query.func.map.MapMerge.item(MapMerge.java:33)
at org.basex.query.func.StandardFunc.optimize(StandardFunc.java:82)
at org.basex.query.expr.Arr.compile(Arr.java:43)
at org.basex.query.scope.MainModule.comp(MainModule.java:81)
at org.basex.query.QueryCompiler.compile(QueryCompiler.java:114)
at org.basex.query.QueryCompiler.compile(QueryCompiler.java:105)
at org.basex.query.QueryContext.compile(QueryContext.java:312)
at org.basex.query.QueryProcessor.compile(QueryProcessor.java:79)
at org.basex.core.cmd.AQuery.query(AQuery.java:93)
at org.basex.core.cmd.XQuery.run(XQuery.java:22)
at org.basex.core.Command.run(Command.java:257)
at org.basex.core.Command.execute(Command.java:93)
at org.basex.gui.GUI.exec(GUI.java:422)
at org.basex.gui.GUI.lambda$4(GUI.java:365)
at java.lang.Thread.run(Thread.java:748)
Best regards,
Johannes
Hi Bridger and Johannes, wow, this is a really old and obscure bug in the `map:merge(...)` logic you found there. It only occurs if both maps to be merged contain hash collisions on the same key, and the two collision buckets are merged together. This is not a common scenario. In a quick search I did not find any BaseX versions that included maps but not this bug, so it could well be that I introduced it in my original implementation -- whoopsie! The AIOOB exception is only triggered when the second bucket is larger than the first one, otherwise the result would just silently be wrong. I am currently testing a proper fix for this, together with some regression tests for all the merging strategies. Afterwards I'll open a pull request. Cheers, Leo On 09.01.2020 21:23, Bridger Dyson-Smith wrote:
Hi all,
While I don't have any answer to this question, I can corroborate Johannes' finding.
Also, Johannes, did you find a magic string? I tried some longer keys and they seem to work :) Best, Bridger
On Thu, Jan 9, 2020 at 11:51 AM Johannes Echterhoff <echterhoff@interactive-instruments.de <mailto:echterhoff@interactive-instruments.de>> wrote:
Hello,____
When executing:____
__ __
map:merge(( map { "DENW21AL100077Hs": "a", "DENW21AL100076i5": "a" }, map { "DENW21AL100077Hs": "b", "DENW21AL100076i5": "b", "DENW21AL100076hT": "b" } ), map {'duplicates': 'combine'})____
__ __
in the BaseX GUI I get:____
__ __
Error:____
Improper use? Potential bug? Your feedback is welcome:____
Contact: basex-talk@mailman.uni-konstanz.de <mailto:basex-talk@mailman.uni-konstanz.de>____
Version: BaseX 9.3.1____
Java: AdoptOpenJDK, 1.8.0_212____
OS: Windows 10, amd64____
Stack Trace: ____
java.lang.ArrayIndexOutOfBoundsException: 2____
at org.basex.query.value.map.TrieList.add(TrieList.java:199)____
at org.basex.query.value.map.TrieList.addAll(TrieList.java:141)____
at org.basex.query.value.map.XQMap.addAll(XQMap.java:106)____
at org.basex.query.func.map.MapMerge.item(MapMerge.java:33)____
at org.basex.query.func.StandardFunc.optimize(StandardFunc.java:82)____
at org.basex.query.expr.Arr.compile(Arr.java:43)____
at org.basex.query.scope.MainModule.comp(MainModule.java:81)____
at org.basex.query.QueryCompiler.compile(QueryCompiler.java:114)____
at org.basex.query.QueryCompiler.compile(QueryCompiler.java:105)____
at org.basex.query.QueryContext.compile(QueryContext.java:312)____
at org.basex.query.QueryProcessor.compile(QueryProcessor.java:79)____
at org.basex.core.cmd.AQuery.query(AQuery.java:93)____
at org.basex.core.cmd.XQuery.run(XQuery.java:22)____
at org.basex.core.Command.run(Command.java:257)____
at org.basex.core.Command.execute(Command.java:93)____
at org.basex.gui.GUI.exec(GUI.java:422)____
at org.basex.gui.GUI.lambda$4(GUI.java:365)____
at java.lang.Thread.run(Thread.java:748)____
__ __
Best regards,____
Johannes____
Thank you, Leo. Your quick analysis of the bug, and your efforts to fix it, are much appreciated! @Bridger: We have a number of fairly large (GBs) datasets that we are processing with a number of diverse queries. In rare occasions this combination appears to uncover a bug. :-) Best regards, Johannes -----Ursprüngliche Nachricht----- Von: Leonard Wörteler [mailto:leonard.woerteler@uni-konstanz.de] Gesendet: Donnerstag, 9. Januar 2020 23:40 An: Bridger Dyson-Smith <bdysonsmith@gmail.com>; Johannes Echterhoff <echterhoff@interactive-instruments.de> Cc: BaseX <basex-talk@mailman.uni-konstanz.de> Betreff: Re: [basex-talk] Bug merging maps with option duplicates:combine? Hi Bridger and Johannes, wow, this is a really old and obscure bug in the `map:merge(...)` logic you found there. It only occurs if both maps to be merged contain hash collisions on the same key, and the two collision buckets are merged together. This is not a common scenario. In a quick search I did not find any BaseX versions that included maps but not this bug, so it could well be that I introduced it in my original implementation -- whoopsie! The AIOOB exception is only triggered when the second bucket is larger than the first one, otherwise the result would just silently be wrong. I am currently testing a proper fix for this, together with some regression tests for all the merging strategies. Afterwards I'll open a pull request. Cheers, Leo On 09.01.2020 21:23, Bridger Dyson-Smith wrote:
Hi all,
While I don't have any answer to this question, I can corroborate Johannes' finding.
Also, Johannes, did you find a magic string? I tried some longer keys and they seem to work :) Best, Bridger
On Thu, Jan 9, 2020 at 11:51 AM Johannes Echterhoff <echterhoff@interactive-instruments.de <mailto:echterhoff@interactive-instruments.de>> wrote:
Hello,____
When executing:____
__ __
map:merge(( map { "DENW21AL100077Hs": "a", "DENW21AL100076i5": "a" }, map { "DENW21AL100077Hs": "b", "DENW21AL100076i5": "b", "DENW21AL100076hT": "b" } ), map {'duplicates': 'combine'})____
__ __
in the BaseX GUI I get:____
__ __
Error:____
Improper use? Potential bug? Your feedback is welcome:____
Contact: basex-talk@mailman.uni-konstanz.de <mailto:basex-talk@mailman.uni-konstanz.de>____
Version: BaseX 9.3.1____
Java: AdoptOpenJDK, 1.8.0_212____
OS: Windows 10, amd64____
Stack Trace: ____
java.lang.ArrayIndexOutOfBoundsException: 2____
at org.basex.query.value.map.TrieList.add(TrieList.java:199)____
at org.basex.query.value.map.TrieList.addAll(TrieList.java:141)____
at org.basex.query.value.map.XQMap.addAll(XQMap.java:106)____
at org.basex.query.func.map.MapMerge.item(MapMerge.java:33)____
at org.basex.query.func.StandardFunc.optimize(StandardFunc.java:82)____
at org.basex.query.expr.Arr.compile(Arr.java:43)____
at org.basex.query.scope.MainModule.comp(MainModule.java:81)____
at org.basex.query.QueryCompiler.compile(QueryCompiler.java:114)____
at org.basex.query.QueryCompiler.compile(QueryCompiler.java:105)____
at org.basex.query.QueryContext.compile(QueryContext.java:312)____
at org.basex.query.QueryProcessor.compile(QueryProcessor.java:79)____
at org.basex.core.cmd.AQuery.query(AQuery.java:93)____
at org.basex.core.cmd.XQuery.run(XQuery.java:22)____
at org.basex.core.Command.run(Command.java:257)____
at org.basex.core.Command.execute(Command.java:93)____
at org.basex.gui.GUI.exec(GUI.java:422)____
at org.basex.gui.GUI.lambda$4(GUI.java:365)____
at java.lang.Thread.run(Thread.java:748)____
__ __
Best regards,____
Johannes____
Hi Leo, that’s awesome, thanks a lot! And I can clarify that the problem was introduced by me and the intent to provide support for the duplicates option three years ago. Your original map implementation has been rock solid since its very beginnings. @Johannes: A new stable snapshot will be available later today (and you can expect the next patch release later this month). Best Christian On Thu, Jan 9, 2020 at 11:40 PM Leonard Wörteler <leonard.woerteler@uni-konstanz.de> wrote:
Hi Bridger and Johannes,
wow, this is a really old and obscure bug in the `map:merge(...)` logic you found there. It only occurs if both maps to be merged contain hash collisions on the same key, and the two collision buckets are merged together. This is not a common scenario. In a quick search I did not find any BaseX versions that included maps but not this bug, so it could well be that I introduced it in my original implementation -- whoopsie!
The AIOOB exception is only triggered when the second bucket is larger than the first one, otherwise the result would just silently be wrong.
I am currently testing a proper fix for this, together with some regression tests for all the merging strategies. Afterwards I'll open a pull request.
Cheers, Leo
On 09.01.2020 21:23, Bridger Dyson-Smith wrote:
Hi all,
While I don't have any answer to this question, I can corroborate Johannes' finding.
Also, Johannes, did you find a magic string? I tried some longer keys and they seem to work :) Best, Bridger
On Thu, Jan 9, 2020 at 11:51 AM Johannes Echterhoff <echterhoff@interactive-instruments.de <mailto:echterhoff@interactive-instruments.de>> wrote:
Hello,____
When executing:____
__ __
map:merge(( map { "DENW21AL100077Hs": "a", "DENW21AL100076i5": "a" }, map { "DENW21AL100077Hs": "b", "DENW21AL100076i5": "b", "DENW21AL100076hT": "b" } ), map {'duplicates': 'combine'})____
__ __
in the BaseX GUI I get:____
__ __
Error:____
Improper use? Potential bug? Your feedback is welcome:____
Contact: basex-talk@mailman.uni-konstanz.de <mailto:basex-talk@mailman.uni-konstanz.de>____
Version: BaseX 9.3.1____
Java: AdoptOpenJDK, 1.8.0_212____
OS: Windows 10, amd64____
Stack Trace: ____
java.lang.ArrayIndexOutOfBoundsException: 2____
at org.basex.query.value.map.TrieList.add(TrieList.java:199)____
at org.basex.query.value.map.TrieList.addAll(TrieList.java:141)____
at org.basex.query.value.map.XQMap.addAll(XQMap.java:106)____
at org.basex.query.func.map.MapMerge.item(MapMerge.java:33)____
at org.basex.query.func.StandardFunc.optimize(StandardFunc.java:82)____
at org.basex.query.expr.Arr.compile(Arr.java:43)____
at org.basex.query.scope.MainModule.comp(MainModule.java:81)____
at org.basex.query.QueryCompiler.compile(QueryCompiler.java:114)____
at org.basex.query.QueryCompiler.compile(QueryCompiler.java:105)____
at org.basex.query.QueryContext.compile(QueryContext.java:312)____
at org.basex.query.QueryProcessor.compile(QueryProcessor.java:79)____
at org.basex.core.cmd.AQuery.query(AQuery.java:93)____
at org.basex.core.cmd.XQuery.run(XQuery.java:22)____
at org.basex.core.Command.run(Command.java:257)____
at org.basex.core.Command.execute(Command.java:93)____
at org.basex.gui.GUI.exec(GUI.java:422)____
at org.basex.gui.GUI.lambda$4(GUI.java:365)____
at java.lang.Thread.run(Thread.java:748)____
__ __
Best regards,____
Johannes____
participants (4)
-
Bridger Dyson-Smith -
Christian Grün -
Johannes Echterhoff -
Leonard Wörteler