[jira] [Comment Edited] (COLLECTIONS-714) PatriciaTrie ignores trailing null characters in keys

["Rohan Padhye (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/COLLECTIONS-714?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16831896#comment-16831896 ] 

Rohan Padhye edited comment on COLLECTIONS-714 at 5/3/19 5:39 AM:
------------------------------------------------------------------

Upon further investigation I noticed that the problem lies in the way PatriciaTrie uses the results of StringKeyAnalyzer.

The insertion of entry with key "x\u0000" when key "x" already exists, hits this path in AbstractPatriciaTrie.put():
{code:java}
} else if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
    // This is a very special and rare case.

    /* REPLACE OLD KEY+VALUE */
    if (found != root) { // NOPMD
        incrementModCount();
        return found.setKeyValue(key, value);
    }
}
{code}
 

I'm not sure what the "very special and rare case" is that the original developer intended, but it incorrectly overwrites the found key "x" with new key "x\u0000".

The above branch is executed because the call to AbstractPatriciaTrie.bitIndex("x", "x\u0000") returns EQUAL_BIT_KEY, which seems incorrect. The bug may be rooted in the way StringKeyAnalyzer.bitIndex() handles cases where index1 >= endIndex1: with the placeholder value `0`, which is actually a valid character in Java.

I cannot think of a simple fix at the top of my head, since the entire XOR-based algorithm seems to rely on the assumption that two non-equal keys must have a bit-index where their corresponding bits differ. This algorithm does not consider the fact that two keys can be non-equal simply because they have different lengths.


was (Author: rohanpadhye):
Upon further investigation I noticed that the problem lies in the way PatriciaTrie uses the results of StringKeyAnalyzer.

The insertion of entry with key "x\u0000" when key "x" already exists, hits this path in AbstractPatriciaTrie.put():
{code:java}
} else if (KeyAnalyzer.isEqualBitKey(bitIndex)) {
    // This is a very special and rare case.

    /* REPLACE OLD KEY+VALUE */
    if (found != root) { // NOPMD
        incrementModCount();
        return found.setKeyValue(key, value);
    }
}
{code}
 

I'm not sure what the "very special and rare case" is that the original developer intended, but it incorrectly overwrites the found key "x" with new key "x\u0000".

Why is the above branch executed? Because the call to AbstractPatriciaTrie.bitIndex("x", "x\u0000") returns EQUAL_BIT_KEY, which seems incorrect. The bug may be rooted in the way StringKeyAnalyzer.bitIndex() handles cases where index1 >= endIndex1: with the placeholder value "0", which is actually a valid character in Java.

I cannot think of a simple fix at the top of my head, since the entire XOR-based algorithm seems to rely on the assumption that two non-equal keys must have a bit-index where their corresponding bits differ. This algorithm does not consider the fact that two keys can be non-equal simply because they have different lengths.

> 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
(v7.6.3#76005)