[jira] [Updated] (COLLECTIONS-714) PatriciaTrie ignores trailing null characters in keys
[
https://issues.apache.org/jira/browse/COLLECTIONS-714?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Rohan Padhye updated COLLECTIONS-714:
-
External issue URL: https://github.com/apache/commons-collections/pull/78
> 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\u" (of length = 2 chars). However,
> PatriciaTrie does not seem to distinguish between these strings.
> To reproduce:
> {code:java}
> public void testNullTerminatedKey1() {
> Map map = new HashMap<>();
> map.put("x", 0); // key of length 1
> map.put("x\u", 1); // key of length 2
> map.put("x\uy", 2); // key of length 3
> Assert.assertEquals(3, map.size()); // ok, 3 distinct keys
> PatriciaTrie 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\u" and
> "x\uy". The key "x" gets overwritten. Here is another way to repro the
> bug:
> {code:java}
> public void testNullTerminatedKey2() {
> PatriciaTrie trie = new PatriciaTrie<>();
> trie.put("x", 0);
> Assert.assertTrue(trie.containsKey("x")); // ok
> trie.put("x\u", 1);
> Assert.assertTrue(trie.containsKey("x")); // fail
> }
> {code}
> In the above example, the key "x" suddenly disappears when an entry with key
> "x\u" 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\u") is false.
> This bug was found automatically using JQF:
> [https://github.com/rohanpadhye/jqf].
>
--
This message was sent by Atlassian JIRA
(v7.6.14#76016)
[jira] [Updated] (COLLECTIONS-714) PatriciaTrie ignores trailing null characters in keys
[
https://issues.apache.org/jira/browse/COLLECTIONS-714?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Rohan Padhye updated COLLECTIONS-714:
-
Description:
In Java, strings are not null terminated. The string "x" (of length = 1 char)
is different from the string "x\u" (of length = 2 chars). However,
PatriciaTrie does not seem to distinguish between these strings.
To reproduce:
{code:java}
public void testNullTerminatedKey1() {
Map map = new HashMap<>();
map.put("x", 0); // key of length 1
map.put("x\u", 1); // key of length 2
map.put("x\uy", 2); // key of length 3
Assert.assertEquals(3, map.size()); // ok, 3 distinct keys
PatriciaTrie 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\u" and
"x\uy". The key "x" gets overwritten. Here is another way to repro the bug:
{code:java}
public void testNullTerminatedKey2() {
PatriciaTrie trie = new PatriciaTrie<>();
trie.put("x", 0);
Assert.assertTrue(trie.containsKey("x")); // ok
trie.put("x\u", 1);
Assert.assertTrue(trie.containsKey("x")); // fail
}
{code}
In the above example, the key "x" suddenly disappears when an entry with key
"x\u" 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\u") is false.
This bug was found automatically using JQF:
[https://github.com/rohanpadhye/jqf].
was:
In Java, strings are not null terminated. The string "x" (of length = 1 char)
is different from the string "x\u" (of length = 2 chars). However,
PatriciaTrie does not seem to distinguish between these strings.
To reproduce:
{code:java}
public void testNullTerminatedKey1() {
Map map = new HashMap<>();
map.put("x", 0); // key of length 1
map.put("x\u", 1); // key of length 2
map.put("x\uy", 2); // key of length 3
Assert.assertEquals(3, map.size()); // ok, 3 distinct keys
PatriciaTrie 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\u" and
"x\uy". The key "x" gets overwritten. Here is another way to repro the bug:
{code:java}
public void testNullTerminatedKey2() {
PatriciaTrie trie = new PatriciaTrie<>();
trie.put("x", 0);
Assert.assertTrue(trie.containsKey("x")); // ok
trie.put("x\u", 1);
Assert.assertTrue(trie.containsKey("x")); // fail
}
{code}
In the above example, the key "x" suddenly disappears when an entry with key
"x\u" 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\u") is false.
This bug was found automatically using JQF:
[https://github.com/rohanpadhye/jqf].
> 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\u" (of length = 2 chars). However,
> PatriciaTrie does not seem to distinguish between these strings.
> To reproduce:
> {code:java}
> public void testNullTerminatedKey1() {
> Map map = new HashMap<>();
> map.put("x", 0); // key of length 1
> map.put("x\u", 1); // key of length 2
> map.put("x\uy", 2); // key of length 3
> Assert.assertEquals(3, map.size()); // ok, 3 distinct keys
> PatriciaTrie 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\u" and
> "x\uy". The key "x" gets overwritten. Here is another way to repro the
> bug:
> {code:java}
> public void testNullTerminatedKey2() {
> PatriciaTrie trie = new PatriciaTrie<>();
> trie.put("x", 0);
> Assert.assertTrue(trie.containsKey("x")); // ok
> trie.put("x\u", 1);
> Assert.assertTrue(trie.containsKey("x")); // fail
> }
> {code}
> In the above example, the key "x" suddenly disappears when an entry with key
> "x\u" 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\u") is false.
> This bug was found automatically using JQF:
>
[jira] [Updated] (COLLECTIONS-714) PatriciaTrie ignores trailing null characters in keys
[
https://issues.apache.org/jira/browse/COLLECTIONS-714?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Rohan Padhye updated COLLECTIONS-714:
-
Description:
In Java, strings are not null terminated. The string "x" (of length = 1 char)
is different from the string "x\u" (of length = 2 chars). However,
PatriciaTrie does not seem to distinguish between these strings.
To reproduce:
{code:java}
@Test
public void testNullTerminatedKey1() {
Map map = new HashMap<>();
map.put("x", 0); // key of length 1
map.put("x\u", 1); // key of length 2
map.put("x\uy", 2); // key of length 3
Assert.assertEquals(3, map.size()); // ok, 3 distinct keys
PatriciaTrie 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\u" and
"x\uy". The key "x" gets overwritten. Here is another way to repro the bug:
{code:java}
@Test
public void testNullTerminatedKey2() {
PatriciaTrie trie = new PatriciaTrie<>();
trie.put("x", 0);
Assert.assertTrue(trie.containsKey("x")); // ok
trie.put("x\u", 1);
Assert.assertTrue(trie.containsKey("x")); // fail
}
{code}
In the above example, the key "x" suddenly disappears when an entry with key
"x\u" 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\u") is false.
This bug was found automatically using JQF:
[https://github.com/rohanpadhye/jqf].
was:
In Java, strings are not null terminated. The string "x" (of length = 1 char)
is different from the string "x\u" (of length = 2 chars). However,
PatriciaTrie does not seem to distinguish between these strings.
To reproduce:
{code:java}
@Test
public void testNullTerminatedKey1() {
Map map = new HashMap<>();
map.put("x", 0); // key of length 1
map.put("x\u", 1); // key of length 2
map.put("x\uy", 2); // key of length 3
Assert.assertEquals(3, map.size()); // ok, 3 distinct keys
PatriciaTrie 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\u" and
"x\uy". The key "x" gets overwritten. Here is another way to repro the bug:
{code:java}
@Test
public void testNullTerminatedKey2() {
PatriciaTrie trie = new PatriciaTrie<>();
trie.put("x", 0);
Assert.assertTrue(trie.containsKey("x")); // ok
trie.put("x\u", 1);
Assert.assertTrue(trie.containsKey("x")); // fail
}
{code}
In the above example, the key "x" suddenly disappears when an entry with key
"x\u" 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\u") is false.
This bug was found automatically using
[JQF|[https://github.com/rohanpadhye/jqf]].
> 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\u" (of length = 2 chars). However,
> PatriciaTrie does not seem to distinguish between these strings.
> To reproduce:
> {code:java}
> @Test
> public void testNullTerminatedKey1() {
> Map map = new HashMap<>();
> map.put("x", 0); // key of length 1
> map.put("x\u", 1); // key of length 2
> map.put("x\uy", 2); // key of length 3
> Assert.assertEquals(3, map.size()); // ok, 3 distinct keys
> PatriciaTrie 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\u" and
> "x\uy". The key "x" gets overwritten. Here is another way to repro the
> bug:
> {code:java}
> @Test
> public void testNullTerminatedKey2() {
> PatriciaTrie trie = new PatriciaTrie<>();
> trie.put("x", 0);
> Assert.assertTrue(trie.containsKey("x")); // ok
> trie.put("x\u", 1);
> Assert.assertTrue(trie.containsKey("x")); // fail
> }
> {code}
> In the above example, the key "x" suddenly disappears when an entry with key
> "x\u" 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\u") is false.
> This bug
[jira] [Updated] (COLLECTIONS-714) PatriciaTrie ignores trailing null characters in keys
[
https://issues.apache.org/jira/browse/COLLECTIONS-714?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Rohan Padhye updated COLLECTIONS-714:
-
Description:
In Java, strings are not null terminated. The string "x" (of length = 1 char)
is different from the string "x\u" (of length = 2 chars). However,
PatriciaTrie does not seem to distinguish between these strings.
To reproduce:
{code:java}
public void testNullTerminatedKey1() {
Map map = new HashMap<>();
map.put("x", 0); // key of length 1
map.put("x\u", 1); // key of length 2
map.put("x\uy", 2); // key of length 3
Assert.assertEquals(3, map.size()); // ok, 3 distinct keys
PatriciaTrie 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\u" and
"x\uy". The key "x" gets overwritten. Here is another way to repro the bug:
{code:java}
public void testNullTerminatedKey2() {
PatriciaTrie trie = new PatriciaTrie<>();
trie.put("x", 0);
Assert.assertTrue(trie.containsKey("x")); // ok
trie.put("x\u", 1);
Assert.assertTrue(trie.containsKey("x")); // fail
}
{code}
In the above example, the key "x" suddenly disappears when an entry with key
"x\u" 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\u") is false.
This bug was found automatically using JQF:
[https://github.com/rohanpadhye/jqf].
was:
In Java, strings are not null terminated. The string "x" (of length = 1 char)
is different from the string "x\u" (of length = 2 chars). However,
PatriciaTrie does not seem to distinguish between these strings.
To reproduce:
{code:java}
@Test
public void testNullTerminatedKey1() {
Map map = new HashMap<>();
map.put("x", 0); // key of length 1
map.put("x\u", 1); // key of length 2
map.put("x\uy", 2); // key of length 3
Assert.assertEquals(3, map.size()); // ok, 3 distinct keys
PatriciaTrie 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\u" and
"x\uy". The key "x" gets overwritten. Here is another way to repro the bug:
{code:java}
@Test
public void testNullTerminatedKey2() {
PatriciaTrie trie = new PatriciaTrie<>();
trie.put("x", 0);
Assert.assertTrue(trie.containsKey("x")); // ok
trie.put("x\u", 1);
Assert.assertTrue(trie.containsKey("x")); // fail
}
{code}
In the above example, the key "x" suddenly disappears when an entry with key
"x\u" 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\u") is false.
This bug was found automatically using JQF:
[https://github.com/rohanpadhye/jqf].
> 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\u" (of length = 2 chars). However,
> PatriciaTrie does not seem to distinguish between these strings.
> To reproduce:
> {code:java}
> public void testNullTerminatedKey1() {
> Map map = new HashMap<>();
> map.put("x", 0); // key of length 1
> map.put("x\u", 1); // key of length 2
> map.put("x\uy", 2); // key of length 3
> Assert.assertEquals(3, map.size()); // ok, 3 distinct keys
> PatriciaTrie 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\u" and
> "x\uy". The key "x" gets overwritten. Here is another way to repro the
> bug:
> {code:java}
> public void testNullTerminatedKey2() {
> PatriciaTrie trie = new PatriciaTrie<>();
> trie.put("x", 0);
> Assert.assertTrue(trie.containsKey("x")); // ok
> trie.put("x\u", 1);
> Assert.assertTrue(trie.containsKey("x")); // fail
> }
> {code}
> In the above example, the key "x" suddenly disappears when an entry with key
> "x\u" 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\u") is false.
> This bug was found automatically using
