[COLLECTIONS-714] PatriciaTrie ignores trailing null characters in keys

• Type: Bug
• Status: Open
• Priority: Critical
• Resolution: Unresolved
• Affects Version/s: 4.3
• Component/s: Collection, Map
• External issue URL: https://github.com/apache/commons-collections/pull/78
• Assignee: Unassigned
• Reporter: Rohan Padhye
• Created: 30/Apr/19 23:11
• Updated: 21/Oct/24 12:59

Description

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: 

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
}

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: 

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
}

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.

 

Issue Links

• links to: GitHub Pull Request #99