You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Rohan Padhye (JIRA)" <ji...@apache.org> on 2019/04/30 23:12:00 UTC
[jira] [Created] (COLLECTIONS-714) PatriciaTrie ignores trailing
null characters in keys
Rohan Padhye created COLLECTIONS-714:
----------------------------------------
Summary: 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
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}
@Test
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}
@Test
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 PatriciaKey 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
(v7.6.3#76005)