[
https://issues.apache.org/jira/browse/COLLECTIONS-714?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16937868#comment-16937868
]
Rohan Padhye commented on COLLECTIONS-714:
------------------------------------------
If there is no fix, then silently failing (with only comments in the doc) does
not seem like a great idea. The data structure is quite unstable if a
previously inserted key disappears because another distinct key gets added.
Also, this breaks the JDK Map contract since two non-equals() keys cannot be
distinguished by two Map entries. If PatriciaTrie cannot support trailing null
bytes in keys, it needs to throw an IllegalArgumentException or something in
the put() method, constructor, and other places where new entries are created.
> PatriciaTrie ignores trailing null characters in keys
> -----------------------------------------------------
>
> Key: COLLECTIONS-714
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-714
> Project: Commons Collections
> Issue Type: Bug
> Components: Collection, Map
> Affects Versions: 4.3
> Reporter: Rohan Padhye
> Priority: Critical
>
> In Java, strings are not null terminated. The string "x" (of length = 1 char)
> is different from the string "x\u0000" (of length = 2 chars). However,
> PatriciaTrie does not seem to distinguish between these strings.
> To reproduce:
> {code:java}
> public void testNullTerminatedKey1() {
> Map<String, Integer> map = new HashMap<>();
> map.put("x", 0); // key of length 1
> map.put("x\u0000", 1); // key of length 2
> map.put("x\u0000y", 2); // key of length 3
> Assert.assertEquals(3, map.size()); // ok, 3 distinct keys
> PatriciaTrie<Integer> trie = new PatriciaTrie<>(map);
> Assert.assertEquals(3, trie.size()); // fail; actual=2
> }{code}
> In the above example, the resulting trie has only two keys: "x\u0000" and
> "x\u0000y". The key "x" gets overwritten. Here is another way to repro the
> bug:
> {code:java}
> public void testNullTerminatedKey2() {
> PatriciaTrie<Integer> trie = new PatriciaTrie<>();
> trie.put("x", 0);
> Assert.assertTrue(trie.containsKey("x")); // ok
> trie.put("x\u0000", 1);
> Assert.assertTrue(trie.containsKey("x")); // fail
> }
> {code}
> In the above example, the key "x" suddenly disappears when an entry with key
> "x\u0000" is inserted.
> The PatriciaTrie docs do not mention anything about null-terminated strings.
> In general, I believe this also breaks the JDK Map contract since the keys
> "x".equals("x\u0000") is false.
> This bug was found automatically using JQF:
> [https://github.com/rohanpadhye/jqf].
>
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
