[jira] [Created] (COLLECTIONS-577) PatriciaTrie bugs when only a few bits change

["Chris Duncan (JIRA)" <ji...@apache.org>]

Chris Duncan created COLLECTIONS-577:
----------------------------------------

             Summary: PatriciaTrie bugs when only a few bits change
                 Key: COLLECTIONS-577
                 URL: https://issues.apache.org/jira/browse/COLLECTIONS-577
             Project: Commons Collections
          Issue Type: Bug
          Components: Map
    Affects Versions: 4.0
            Reporter: Chris Duncan
            Priority: Critical


I have a bug report for you.  It has to do with how you handle bits when they are very close to each other.  For example, some of your methods seem to think that if the only difference between a prefix and a longer string, is a single additional bit, then they are actually the same data.  Or if the only difference is some number of zero bits, then it also thinks they are the same data.  There are also MANY situations where the prefixMap does not return all the strings that start with the prefix.

Take the following code for example, which shows the bugs happening in a very simple context.
I create two strings.  The first string is always a prefix of the second string.  Here are the characters I am using:

    final char u0000 = Character.toChars(0)[0]; // U+0000 (0000000000000000)
    final char u0001 = Character.toChars(1)[0]; // U+0001 (0000000000000001)
    final char u8000 = Character.toChars(32768)[0]; // U+8000 (1000000000000000)
    final char uffff = Character.toChars(65535)[0]; // U+FFFF (1111111111111111)
    final char char_b = 'b'; // 1100010
    final char char_c = 'c'; // 1100011
    final PatriciaTrie<String> trie = new PatriciaTrie<>();

And here is a quick example of the trie working correctly, showing how it should work:

    final String prefixString = "" + char_b;
    final String longerString = prefixString + char_c;
    System.out.println(trie.prefixMap(prefixString)); // {b=prefixString, bc=longerString} // correct!


In the first example, I show that a character who's bits are all zeros is always mishandled:

    final String prefixString = "" + char_b;
    final String longerString = prefixString + u0000;

    System.out.println(prefixString);
    System.out.println(prefixString.length()); // 1

    System.out.println(longerString);
    System.out.println(longerString.length()); // 2

    System.out.println(longerString.startsWith(prefixString)); // true

    trie.put(prefixString, "prefixString");
    System.out.println(trie); // prefixString is in

    trie.put(longerString, "longerString");
    System.out.println(trie); // only longerString shown... prefixString has disappeared

    System.out.println(trie.prefixMap(prefixString).size()); // prints 1, but should be 2
    System.out.println(trie.prefixMap(prefixString)); // {b =longerString} // prefixString should be here, but isn't

    trie.put(prefixString, "prefixString");
    System.out.println(trie); // prefixString is in again, but longerString has now disappeared

    System.out.println(trie.prefixMap(prefixString).size()); // prints 1, but should be 2
    System.out.println(trie.prefixMap(prefixString)); // {b=prefixString} // longerString should be here, but isn't


Next, I show that if the longer string is only 1 bit longer (ignoring zeros) than the prefix string, then the PatriciaTree fails to include it in the prefix map.
Here the string would look like: 0000000001100011 1000000000000000

    final String prefixString = "" + char_c;  // you can use any character for the prefix, same results
    final String longerString = prefixString + u8000;

    System.out.println(prefixString);
    System.out.println(prefixString.length()); // 1

    System.out.println(longerString);
    System.out.println(longerString.length()); // 2

    System.out.println(longerString.startsWith(prefixString)); // true

    trie.put(prefixString, "prefixString");
    System.out.println(trie); // prefixString is in

    trie.put(longerString, "longerString");
    System.out.println(trie); // both are in

    System.out.println(trie.prefixMap(prefixString).size()); // prints 1, but should be 2
    System.out.println(trie.prefixMap(prefixString)); // {c=prefixString} // longerString should be here, but isn't


And again, except flipping it so that the prefix ends with a 1, and the longer string starts with 1's:

    final String prefixString = "" + u0003;
    final String longerString = prefixString + u8000; // can also use uffff here, same result

    System.out.println(prefixString);
    System.out.println(prefixString.length()); // 1

    System.out.println(longerString);
    System.out.println(longerString.length()); // 2

    System.out.println(longerString.startsWith(prefixString)); // true

    trie.put(prefixString, "prefixString");
    System.out.println(trie); // prefixString is in

    trie.put(longerString, "longerString");
    System.out.println(trie); // both are in

    System.out.println(trie.prefixMap(prefixString).size()); // prints 1, but should be 2
    System.out.println(trie.prefixMap(prefixString)); // {c=prefixString} // longerString should be here, but isn't


The class is honestly pretty complex and I wasn't able to completely debug why this is behaving badly, but I believe it is because of how you are handling the "bitIndex" and "bitLength".
For example, in the method AbstractPatriciaTrie .subtree(), my comments in bold (this definitely isn't the only place with weird handling of bitIndex and lengthInBits):

    TrieEntry<K, V> subtree(final K prefix, final int offsetInBits, final int lengthInBits) {
        TrieEntry<K, V> current = root.left;
        TrieEntry<K, V> path = root;
        while(true) {
// If our bit index has only increased by 1, then our bitIndex will never get to be greater than lengthInBits, we could still start with the prefix, yet we have no way to break out of here with current being set to the longer string.
            if (current.bitIndex <= path.bitIndex || lengthInBits < current.bitIndex) {
                break;
            }
            path = current;
            if (!isBitSet(prefix, offsetInBits + current.bitIndex, offsetInBits + lengthInBits)) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
      ...


Can you also make AbstractPatriciaTrie public, and your other package level methods into protected level, that way I don't have to copy the entire class and subclasse's code out into another class just to extend it?

thank you,
Chris Duncan (github user: VEQRYN)




--
This message was sent by Atlassian JIRA
(v6.3.4#6332)