Uploaded image for project: 'Commons Collections'
  1. Commons Collections
  2. COLLECTIONS-714

PatriciaTrie ignores trailing null characters in keys

    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Open
    • Priority: Critical
    • Resolution: Unresolved
    • Affects Version/s: 4.3
    • Fix Version/s: None
    • Component/s: Collection, Map
    • Labels:
      None

      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.

       

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                rohanpadhye Rohan Padhye
              • Votes:
                0 Vote for this issue
                Watchers:
                4 Start watching this issue

                Dates

                • Created:
                  Updated:

                  Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 0.5h
                  0.5h