This is an automated email from the ASF dual-hosted git repository.
garydgregory pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-collections.git
The following commit(s) were added to refs/heads/master by this push:
new 3099308e4 [COLLECTIONS-714] PatriciaTrie ignores trailing null
characters in keys (#712)
3099308e4 is described below
commit 3099308e4bb0155da6e8f4ea0d0455e06985a91a
Author: sankalp suman <[email protected]>
AuthorDate: Thu Jul 16 02:47:04 2026 +0530
[COLLECTIONS-714] PatriciaTrie ignores trailing null characters in keys
(#712)
* COLLECTIONS-732: Document UnsupportedOperationException on
MultiValuedMap.mapIterator().setValue()
* COLLECTIONS-732: Fix Javadoc on
AbstractMultiValuedMapDecorator.mapIterator
* [COLLECTIONS-714]Fix StringKeyAnalyzer bitIndex and isBitSet for keys
containing null characters
* COLLECTIONS-714: Add regression tests for Java UTF-16 control characters
in PatriciaTrie
* COLLECTIONS-714: Remove useless parentheses in StringKeyAnalyzer to fix
PMD violation
* Fix formatting in StringKeyAnalyzer.java
* Remove bogus Javadoc
Removed unsupported operation documentation from setValue method.
* Remove bogus Javadoc.
Removed unsupported operation note from mapIterator method documentation.
* Remove unsupported operation comment from mapIterator
Removed unsupported operation documentation from mapIterator method.
---------
Co-authored-by: Gary Gregory <[email protected]>
---
.../multimap/UnmodifiableMultiValuedMap.java | 7 ++
.../trie/analyzer/StringKeyAnalyzer.java | 47 +++-----
.../collections4/trie/PatriciaTrieTest.java | 121 ++++++++++++++++++++-
3 files changed, 144 insertions(+), 31 deletions(-)
diff --git
a/src/main/java/org/apache/commons/collections4/multimap/UnmodifiableMultiValuedMap.java
b/src/main/java/org/apache/commons/collections4/multimap/UnmodifiableMultiValuedMap.java
index 90b8c780d..74e81cb0c 100644
---
a/src/main/java/org/apache/commons/collections4/multimap/UnmodifiableMultiValuedMap.java
+++
b/src/main/java/org/apache/commons/collections4/multimap/UnmodifiableMultiValuedMap.java
@@ -114,6 +114,13 @@ public final class UnmodifiableMultiValuedMap<K, V>
return UnmodifiableSet.unmodifiableSet(decorated().keySet());
}
+ /**
+ * {@inheritDoc}
+ * <p>
+ * The returned map iterator's {@link MapIterator#setValue(Object)} method
is not supported
+ * and will throw an {@link UnsupportedOperationException}.
+ * </p>
+ */
@Override
public MapIterator<K, V> mapIterator() {
return
UnmodifiableMapIterator.unmodifiableMapIterator(decorated().mapIterator());
diff --git
a/src/main/java/org/apache/commons/collections4/trie/analyzer/StringKeyAnalyzer.java
b/src/main/java/org/apache/commons/collections4/trie/analyzer/StringKeyAnalyzer.java
index 6b0aaa6df..f28c98d14 100644
---
a/src/main/java/org/apache/commons/collections4/trie/analyzer/StringKeyAnalyzer.java
+++
b/src/main/java/org/apache/commons/collections4/trie/analyzer/StringKeyAnalyzer.java
@@ -33,8 +33,8 @@ public class StringKeyAnalyzer extends KeyAnalyzer<String> {
/** A singleton instance of {@link StringKeyAnalyzer}. */
public static final StringKeyAnalyzer INSTANCE = new StringKeyAnalyzer();
- /** The number of bits per {@link Character}. */
- public static final int LENGTH = Character.SIZE;
+ /** The number of bits per {@link Character} plus a presence bit. */
+ public static final int LENGTH = Character.SIZE + 1;
/** A bit mask where the first bit is 1 and the others are zero. */
private static final int MSB = 0x8000;
@@ -58,8 +58,6 @@ public class StringKeyAnalyzer extends KeyAnalyzer<String> {
public int bitIndex(final String key, final int offsetInBits, final int
lengthInBits,
final String other, final int otherOffsetInBits, final
int otherLengthInBits) {
- boolean allNull = true;
-
if (offsetInBits % LENGTH != 0 || otherOffsetInBits % LENGTH != 0
|| lengthInBits % LENGTH != 0 || otherLengthInBits % LENGTH !=
0) {
throw new IllegalArgumentException("The offsets and lengths must
be at Character boundaries");
@@ -69,43 +67,29 @@ public class StringKeyAnalyzer extends KeyAnalyzer<String> {
final int beginIndex2 = otherOffsetInBits / LENGTH;
final int endIndex1 = beginIndex1 + lengthInBits / LENGTH;
- final int endIndex2 = beginIndex2 + otherLengthInBits / LENGTH;
+ final int endIndex2 = other == null ? beginIndex2 : beginIndex2 +
otherLengthInBits / LENGTH;
final int length = Math.max(endIndex1, endIndex2);
- // Look at each character, and if they're different
- // then figure out which bit makes the difference
- // and return it.
- char k = 0;
- char f = 0;
for (int i = 0; i < length; i++) {
final int index1 = beginIndex1 + i;
final int index2 = beginIndex2 + i;
- if (index1 >= endIndex1) {
- k = 0;
- } else {
- k = key.charAt(index1);
- }
+ if (index1 < endIndex1 && other != null && index2 < endIndex2) {
+ final char k = key.charAt(index1);
+ final char f = other.charAt(index2);
- if (other == null || index2 >= endIndex2) {
- f = 0;
+ if (k != f) {
+ final int x = k ^ f;
+ return i * LENGTH + 1 + Integer.numberOfLeadingZeros(x) -
(LENGTH - 1);
+ }
} else {
- f = other.charAt(index2);
- }
-
- if (k != f) {
- final int x = k ^ f;
- return i * LENGTH + Integer.numberOfLeadingZeros(x) - LENGTH;
- }
-
- if (k != 0) {
- allNull = false;
+ // One has ended, the other has not. They differ at the
presence bit of this block.
+ return i * LENGTH;
}
}
- // All bits are 0
- if (allNull) {
+ if (lengthInBits == 0 && (other == null || otherLengthInBits == 0)) {
return NULL_BIT_KEY;
}
@@ -127,7 +111,10 @@ public class StringKeyAnalyzer extends KeyAnalyzer<String>
{
final int index = bitIndex / LENGTH;
final int bit = bitIndex % LENGTH;
- return (key.charAt(index) & mask(bit)) != 0;
+ if (bit == 0) {
+ return true;
+ }
+ return (key.charAt(index) & mask(bit - 1)) != 0;
}
@Override
diff --git
a/src/test/java/org/apache/commons/collections4/trie/PatriciaTrieTest.java
b/src/test/java/org/apache/commons/collections4/trie/PatriciaTrieTest.java
index ad2c73084..46f1bef91 100644
--- a/src/test/java/org/apache/commons/collections4/trie/PatriciaTrieTest.java
+++ b/src/test/java/org/apache/commons/collections4/trie/PatriciaTrieTest.java
@@ -667,6 +667,126 @@ public class PatriciaTrieTest<V> extends
AbstractSortedMapTest<String, V> {
assertEquals("ge", tailMap.get("ge"));
}
+ @Test
+ void testNullTerminatedKey1() {
+ final PatriciaTrie<Integer> trie = new PatriciaTrie<>();
+ trie.put("x", 0);
+ trie.put("x\u0000", 1);
+ assertTrue(trie.containsKey("x"));
+ assertTrue(trie.containsKey("x\u0000"));
+ assertEquals(2, trie.size());
+ assertEquals(0, trie.get("x"));
+ assertEquals(1, trie.get("x\u0000"));
+ }
+
+ @Test
+ void testNullTerminatedKey2() {
+ final PatriciaTrie<Integer> trie = new PatriciaTrie<>();
+ trie.put("x\u0000", 1);
+ trie.put("x", 0);
+ assertTrue(trie.containsKey("x"));
+ assertTrue(trie.containsKey("x\u0000"));
+ assertEquals(2, trie.size());
+ assertEquals(0, trie.get("x"));
+ assertEquals(1, trie.get("x\u0000"));
+ }
+
+ @Test
+ public void testControlCharactersRegression() {
+ final String[] keys = {
+ "",
+ "\u0000",
+ "\u0001",
+ "\u0002",
+ "\u001F",
+ "\u007F",
+ "x",
+ "x\u0000",
+ "x\u0001",
+ "x\u0002",
+ "x\u001F",
+ "x\u007F",
+ "x\u0000y",
+ "x\u0001y"
+ };
+
+ // 1. Insertion, Retrieval, containsKey, size compared with HashMap
+ final java.util.Map<String, String> hashMap = new
java.util.HashMap<>();
+ final PatriciaTrie<String> trie = new PatriciaTrie<>();
+
+ for (int i = 0; i < keys.length; i++) {
+ final String key = keys[i];
+ final String value = "val_" + i;
+
+ assertFalse(trie.containsKey(key));
+ assertNull(trie.get(key));
+
+ trie.put(key, value);
+ hashMap.put(key, value);
+
+ assertEquals(hashMap.size(), trie.size());
+ assertTrue(trie.containsKey(key));
+ assertEquals(value, trie.get(key));
+ }
+
+ // Verify all elements present and distinct
+ for (int i = 0; i < keys.length; i++) {
+ final String key = keys[i];
+ assertTrue(trie.containsKey(key));
+ assertEquals("val_" + i, trie.get(key));
+ }
+
+ // 2. Iteration order (compared with TreeMap)
+ final java.util.TreeMap<String, String> treeMap = new
java.util.TreeMap<>(hashMap);
+ final java.util.List<String> trieKeys = new
java.util.ArrayList<>(trie.keySet());
+ final java.util.List<String> expectedKeys = new
java.util.ArrayList<>(treeMap.keySet());
+ assertEquals(expectedKeys, trieKeys);
+
+ // 3. prefixMap
+ final String[] prefixes = {"", "x", "x\u0000", "x\u0001", "x\u0002",
"x\u001F", "x\u007F", "y"};
+ for (final String prefix : prefixes) {
+ final java.util.SortedMap<String, String> prefixMap =
trie.prefixMap(prefix);
+ final java.util.TreeMap<String, String> expectedPrefixMap = new
java.util.TreeMap<>();
+ for (final java.util.Map.Entry<String, String> entry :
treeMap.entrySet()) {
+ if (entry.getKey().startsWith(prefix)) {
+ expectedPrefixMap.put(entry.getKey(), entry.getValue());
+ }
+ }
+ assertEquals(expectedPrefixMap.size(), prefixMap.size());
+ assertEquals(expectedPrefixMap, new
java.util.TreeMap<>(prefixMap));
+ }
+
+ // 4. headMap, tailMap, subMap (compared with TreeMap)
+ for (final String k1 : keys) {
+ assertEquals(new java.util.TreeMap<>(treeMap.headMap(k1)), new
java.util.TreeMap<>(trie.headMap(k1)));
+ assertEquals(new java.util.TreeMap<>(treeMap.tailMap(k1)), new
java.util.TreeMap<>(trie.tailMap(k1)));
+ for (final String k2 : keys) {
+ if (k1.compareTo(k2) <= 0) {
+ assertEquals(new java.util.TreeMap<>(treeMap.subMap(k1,
k2)), new java.util.TreeMap<>(trie.subMap(k1, k2)));
+ } else {
+ assertThrows(IllegalArgumentException.class, () ->
trie.subMap(k1, k2));
+ }
+ }
+ }
+
+ // 5. Remove (compared with HashMap)
+ for (int i = 0; i < keys.length; i++) {
+ final String key = keys[i];
+ final String value = "val_" + i;
+
+ assertTrue(trie.containsKey(key));
+ assertEquals(value, trie.remove(key));
+ assertFalse(trie.containsKey(key));
+ assertNull(trie.get(key));
+
+ hashMap.remove(key);
+ assertEquals(hashMap.size(), trie.size());
+ }
+
+ assertTrue(trie.isEmpty());
+ assertEquals(0, trie.size());
+ }
+
// void testCreate() throws Exception {
// resetEmpty();
// writeExternalFormToDisk(
@@ -677,5 +797,4 @@ public class PatriciaTrieTest<V> extends
AbstractSortedMapTest<String, V> {
// (java.io.Serializable) map,
//
"src/test/resources/data/test/PatriciaTrie.fullCollection.version4.obj");
// }
-
}
