| 1 | /******************************************************************************* | |
| 2 | * Copyright (C) 2026, Leo Galambos | |
| 3 | * All rights reserved. | |
| 4 | * | |
| 5 | * Redistribution and use in source and binary forms, with or without | |
| 6 | * modification, are permitted provided that the following conditions are met: | |
| 7 | * | |
| 8 | * 1. Redistributions of source code must retain the above copyright notice, | |
| 9 | * this list of conditions and the following disclaimer. | |
| 10 | * | |
| 11 | * 2. Redistributions in binary form must reproduce the above copyright notice, | |
| 12 | * this list of conditions and the following disclaimer in the documentation | |
| 13 | * and/or other materials provided with the distribution. | |
| 14 | * | |
| 15 | * 3. Neither the name of the copyright holder nor the names of its contributors | |
| 16 | * may be used to endorse or promote products derived from this software | |
| 17 | * without specific prior written permission. | |
| 18 | * | |
| 19 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | |
| 20 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
| 21 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
| 22 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | |
| 23 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
| 24 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
| 25 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
| 26 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
| 27 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
| 28 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
| 29 | * POSSIBILITY OF SUCH DAMAGE. | |
| 30 | ******************************************************************************/ | |
| 31 | package org.egothor.stemmer; | |
| 32 | ||
| 33 | import java.util.ArrayList; | |
| 34 | import java.util.Collections; | |
| 35 | import java.util.HashSet; | |
| 36 | import java.util.List; | |
| 37 | import java.util.Set; | |
| 38 | ||
| 39 | import org.egothor.stemmer.trie.CompiledNode; | |
| 40 | ||
| 41 | /** | |
| 42 | * Command-selection traversals for {@link LookupMode#LAST} and | |
| 43 | * {@link LookupMode#ALL}. | |
| 44 | * | |
| 45 | * <p> | |
| 46 | * The {@link LookupMode#FIRST} walk lives on the read hot path inside | |
| 47 | * {@link FrequencyTrie}. This collaborator hosts the less common most-specific | |
| 48 | * ({@code LAST}) and collect-all ({@code ALL}) traversals so the trie class | |
| 49 | * stays cohesive, together with the small value-assembly helpers those modes | |
| 50 | * need. All methods are stateless and operate on the shared, immutable compiled | |
| 51 | * node graph. | |
| 52 | * </p> | |
| 53 | */ | |
| 54 | final class TrieLookup { | |
| 55 | ||
| 56 | /** | |
| 57 | * Prevents instantiation of this stateless utility class. | |
| 58 | * | |
| 59 | * @throws AssertionError unconditionally, including reflective construction | |
| 60 | */ | |
| 61 | private TrieLookup() { | |
| 62 | throw new AssertionError("No instances."); | |
| 63 | } | |
| 64 | ||
| 65 | /** | |
| 66 | * Locates the deepest (most specific) node for {@code key}, using the deepest | |
| 67 | * accepting ancestor as a fallback when descent dead-ends or the exact | |
| 68 | * terminal stores no value. | |
| 69 | * | |
| 70 | * @param root compiled root node | |
| 71 | * @param backward whether traversal consumes the key from its end | |
| 72 | * @param key already-normalized key | |
| 73 | * @param <V> value type | |
| 74 | * @return resolved node, or {@code null} if no applicable node exists | |
| 75 | */ | |
| 76 | /* default */ static <V> CompiledNode<V> findLast(final CompiledNode<V> root, final boolean backward, | |
| 77 | final CharSequence key) { | |
| 78 | CompiledNode<V> current = root; | |
| 79 |
1
1. findLast : negated conditional → SURVIVED |
CompiledNode<V> fallback = current.acceptsRemainingInput() ? current : null; |
| 80 | final int length = key.length(); | |
| 81 |
2
1. findLast : changed conditional boundary → KILLED 2. findLast : negated conditional → KILLED |
for (int step = 0; step < length; step++) { |
| 82 |
3
1. findLast : Replaced integer subtraction with addition → KILLED 2. findLast : negated conditional → KILLED 3. findLast : Replaced integer subtraction with addition → KILLED |
final int index = backward ? length - 1 - step : step; |
| 83 | final CompiledNode<V> next = current.findChild(key.charAt(index)); | |
| 84 |
1
1. findLast : negated conditional → KILLED |
if (next == null) { |
| 85 | return fallback; | |
| 86 | } | |
| 87 | current = next; | |
| 88 |
1
1. findLast : negated conditional → KILLED |
if (current.acceptsRemainingInput()) { |
| 89 | fallback = current; | |
| 90 | } | |
| 91 | } | |
| 92 |
2
1. findLast : changed conditional boundary → SURVIVED 2. findLast : negated conditional → KILLED |
if (current.orderedValues().length > 0) { |
| 93 |
1
1. findLast : replaced return value with null for org/egothor/stemmer/TrieLookup::findLast → KILLED |
return current; |
| 94 | } | |
| 95 |
1
1. findLast : replaced return value with null for org/egothor/stemmer/TrieLookup::findLast → NO_COVERAGE |
return fallback; |
| 96 | } | |
| 97 | ||
| 98 | /** | |
| 99 | * Array-slice specialization of | |
| 100 | * {@link #findLast(CompiledNode, boolean, CharSequence)} that avoids a | |
| 101 | * temporary wrapper allocation on normalized visitor hot paths. | |
| 102 | * | |
| 103 | * @param root compiled root node | |
| 104 | * @param backward whether traversal consumes the slice from its end | |
| 105 | * @param key normalized key storage | |
| 106 | * @param offset first character in the slice | |
| 107 | * @param length number of characters in the slice | |
| 108 | * @param <V> value type | |
| 109 | * @return resolved node, or {@code null} if no applicable node exists | |
| 110 | */ | |
| 111 | /* default */ static <V> CompiledNode<V> findLast(final CompiledNode<V> root, final boolean backward, | |
| 112 | final char[] key, final int offset, final int length) { | |
| 113 | CompiledNode<V> current = root; | |
| 114 |
1
1. findLast : negated conditional → NO_COVERAGE |
CompiledNode<V> fallback = current.acceptsRemainingInput() ? current : null; |
| 115 |
2
1. findLast : negated conditional → NO_COVERAGE 2. findLast : changed conditional boundary → NO_COVERAGE |
for (int step = 0; step < length; step++) { |
| 116 |
5
1. findLast : Replaced integer subtraction with addition → NO_COVERAGE 2. findLast : Replaced integer subtraction with addition → NO_COVERAGE 3. findLast : Replaced integer addition with subtraction → NO_COVERAGE 4. findLast : Replaced integer addition with subtraction → NO_COVERAGE 5. findLast : negated conditional → NO_COVERAGE |
final int index = backward ? offset + length - 1 - step : offset + step; |
| 117 | final CompiledNode<V> next = current.findChild(key[index]); | |
| 118 |
1
1. findLast : negated conditional → NO_COVERAGE |
if (next == null) { |
| 119 | return fallback; | |
| 120 | } | |
| 121 | current = next; | |
| 122 |
1
1. findLast : negated conditional → NO_COVERAGE |
if (current.acceptsRemainingInput()) { |
| 123 | fallback = current; | |
| 124 | } | |
| 125 | } | |
| 126 |
3
1. findLast : replaced return value with null for org/egothor/stemmer/TrieLookup::findLast → NO_COVERAGE 2. findLast : negated conditional → NO_COVERAGE 3. findLast : changed conditional boundary → NO_COVERAGE |
return current.orderedValues().length > 0 ? current : fallback; |
| 127 | } | |
| 128 | ||
| 129 | /** | |
| 130 | * Collects every node whose values apply to {@code key}, most specific first: | |
| 131 | * the exact terminal (when the key is fully consumed) followed by each | |
| 132 | * accepting ancestor from deepest to shallowest. | |
| 133 | * | |
| 134 | * @param root compiled root node | |
| 135 | * @param backward whether traversal consumes the key from its end | |
| 136 | * @param key already-normalized key | |
| 137 | * @param <V> value type | |
| 138 | * @return ordered applicable nodes; empty when none apply | |
| 139 | */ | |
| 140 | /* default */ static <V> List<CompiledNode<V>> collectPath(final CompiledNode<V> root, | |
| 141 | final boolean backward, final CharSequence key) { | |
| 142 | final List<CompiledNode<V>> accepting = new ArrayList<>(); | |
| 143 | CompiledNode<V> current = root; | |
| 144 |
1
1. collectPath : negated conditional → SURVIVED |
if (current.acceptsRemainingInput()) { |
| 145 | accepting.add(current); | |
| 146 | } | |
| 147 | boolean fullyConsumed = true; | |
| 148 | final int length = key.length(); | |
| 149 |
2
1. collectPath : changed conditional boundary → KILLED 2. collectPath : negated conditional → KILLED |
for (int step = 0; step < length; step++) { |
| 150 |
3
1. collectPath : Replaced integer subtraction with addition → KILLED 2. collectPath : negated conditional → KILLED 3. collectPath : Replaced integer subtraction with addition → KILLED |
final int index = backward ? length - 1 - step : step; |
| 151 | final CompiledNode<V> next = current.findChild(key.charAt(index)); | |
| 152 |
1
1. collectPath : negated conditional → KILLED |
if (next == null) { |
| 153 | fullyConsumed = false; | |
| 154 | break; | |
| 155 | } | |
| 156 | current = next; | |
| 157 |
1
1. collectPath : negated conditional → KILLED |
if (current.acceptsRemainingInput()) { |
| 158 | accepting.add(current); | |
| 159 | } | |
| 160 | } | |
| 161 | ||
| 162 |
1
1. collectPath : Replaced integer addition with subtraction → SURVIVED |
final List<CompiledNode<V>> ordered = new ArrayList<>(accepting.size() + 1); |
| 163 | // A fully-consumed terminal that itself accepts is already the deepest | |
| 164 | // entry in `accepting`, so add the terminal only when it does not accept. | |
| 165 |
4
1. collectPath : changed conditional boundary → SURVIVED 2. collectPath : negated conditional → KILLED 3. collectPath : negated conditional → KILLED 4. collectPath : negated conditional → KILLED |
if (fullyConsumed && !current.acceptsRemainingInput() && current.orderedValues().length > 0) { |
| 166 | ordered.add(current); | |
| 167 | } | |
| 168 |
3
1. collectPath : Replaced integer subtraction with addition → KILLED 2. collectPath : negated conditional → KILLED 3. collectPath : changed conditional boundary → KILLED |
for (int index = accepting.size() - 1; index >= 0; index--) { |
| 169 | ordered.add(accepting.get(index)); | |
| 170 | } | |
| 171 |
1
1. collectPath : replaced return value with Collections.emptyList for org/egothor/stemmer/TrieLookup::collectPath → KILLED |
return ordered; |
| 172 | } | |
| 173 | ||
| 174 | /** | |
| 175 | * Collects all applicable values across {@code nodes}, de-duplicated by | |
| 176 | * {@link Object#equals(Object)}, in list order (most specific first). | |
| 177 | * | |
| 178 | * @param nodes ordered applicable nodes | |
| 179 | * @param empty shared empty array carrying the target component type | |
| 180 | * @param <V> value type | |
| 181 | * @return de-duplicated values, or {@code empty} when none apply | |
| 182 | */ | |
| 183 | @SuppressWarnings("PMD.UseVarargs") | |
| 184 | /* default */ static <V> V[] collectAllValues(final List<CompiledNode<V>> nodes, final V[] empty) { | |
| 185 |
1
1. collectAllValues : negated conditional → KILLED |
if (nodes.isEmpty()) { |
| 186 |
1
1. collectAllValues : replaced return value with null for org/egothor/stemmer/TrieLookup::collectAllValues → NO_COVERAGE |
return empty; |
| 187 | } | |
| 188 | final List<V> collected = new ArrayList<>(); | |
| 189 | final Set<V> seen = new HashSet<>(); | |
| 190 | for (final CompiledNode<V> node : nodes) { | |
| 191 | for (final V value : node.orderedValues()) { | |
| 192 |
1
1. collectAllValues : negated conditional → KILLED |
if (seen.add(value)) { |
| 193 | collected.add(value); | |
| 194 | } | |
| 195 | } | |
| 196 | } | |
| 197 |
2
1. collectAllValues : negated conditional → KILLED 2. collectAllValues : replaced return value with null for org/egothor/stemmer/TrieLookup::collectAllValues → KILLED |
return collected.isEmpty() ? empty : collected.toArray(empty); |
| 198 | } | |
| 199 | ||
| 200 | /** | |
| 201 | * Collects all applicable value-count entries across {@code nodes}, | |
| 202 | * de-duplicated by value, in list order (most specific first). | |
| 203 | * | |
| 204 | * @param nodes ordered applicable nodes | |
| 205 | * @param <V> value type | |
| 206 | * @return immutable de-duplicated entries | |
| 207 | */ | |
| 208 | /* default */ static <V> List<ValueCount<V>> collectAllEntries(final List<CompiledNode<V>> nodes) { | |
| 209 | final List<ValueCount<V>> entries = new ArrayList<>(); | |
| 210 | final Set<V> seen = new HashSet<>(); | |
| 211 | for (final CompiledNode<V> node : nodes) { | |
| 212 | final V[] values = node.orderedValues(); | |
| 213 | final int[] counts = node.orderedCounts(); | |
| 214 |
2
1. collectAllEntries : negated conditional → KILLED 2. collectAllEntries : changed conditional boundary → KILLED |
for (int index = 0; index < values.length; index++) { |
| 215 |
1
1. collectAllEntries : negated conditional → KILLED |
if (seen.add(values[index])) { |
| 216 | entries.add(new ValueCount<>(values[index], counts[index])); | |
| 217 | } | |
| 218 | } | |
| 219 | } | |
| 220 |
2
1. collectAllEntries : replaced return value with Collections.emptyList for org/egothor/stemmer/TrieLookup::collectAllEntries → KILLED 2. collectAllEntries : negated conditional → KILLED |
return entries.isEmpty() ? List.of() : Collections.unmodifiableList(entries); |
| 221 | } | |
| 222 | ||
| 223 | /** | |
| 224 | * Visits applicable values across {@code nodes}, de-duplicated by value, most | |
| 225 | * specific first, up to {@code maxResults}. Mirrors the | |
| 226 | * {@link FrequencyTrie.EntrySink} contract with the visit index as the rank. | |
| 227 | * | |
| 228 | * @param nodes ordered applicable nodes | |
| 229 | * @param sink value sink | |
| 230 | * @param maxResults maximum values to visit | |
| 231 | * @param <V> value type | |
| 232 | * @return number of visited values | |
| 233 | */ | |
| 234 | /* default */ static <V> int visitNodes(final List<CompiledNode<V>> nodes, | |
| 235 | final FrequencyTrie.EntrySink<? super V> sink, final int maxResults) { | |
| 236 | int visited = 0; | |
| 237 | final Set<V> seen = new HashSet<>(); | |
| 238 | for (final CompiledNode<V> node : nodes) { | |
| 239 | final V[] values = node.orderedValues(); | |
| 240 | final int[] counts = node.orderedCounts(); | |
| 241 |
2
1. visitNodes : changed conditional boundary → NO_COVERAGE 2. visitNodes : negated conditional → NO_COVERAGE |
for (int index = 0; index < values.length; index++) { |
| 242 |
2
1. visitNodes : changed conditional boundary → NO_COVERAGE 2. visitNodes : negated conditional → NO_COVERAGE |
if (visited >= maxResults) { |
| 243 |
1
1. visitNodes : replaced int return with 0 for org/egothor/stemmer/TrieLookup::visitNodes → NO_COVERAGE |
return visited; |
| 244 | } | |
| 245 |
1
1. visitNodes : negated conditional → NO_COVERAGE |
if (!seen.add(values[index])) { |
| 246 | continue; | |
| 247 | } | |
| 248 |
1
1. visitNodes : Changed increment from 1 to -1 → NO_COVERAGE |
visited++; |
| 249 |
2
1. visitNodes : Replaced integer subtraction with addition → NO_COVERAGE 2. visitNodes : negated conditional → NO_COVERAGE |
if (!sink.accept(values[index], counts[index], visited - 1)) { |
| 250 |
1
1. visitNodes : replaced int return with 0 for org/egothor/stemmer/TrieLookup::visitNodes → NO_COVERAGE |
return visited; |
| 251 | } | |
| 252 | } | |
| 253 | } | |
| 254 |
1
1. visitNodes : replaced int return with 0 for org/egothor/stemmer/TrieLookup::visitNodes → NO_COVERAGE |
return visited; |
| 255 | } | |
| 256 | } | |
Mutations | ||
| 79 |
1.1 |
|
| 81 |
1.1 2.2 |
|
| 82 |
1.1 2.2 3.3 |
|
| 84 |
1.1 |
|
| 88 |
1.1 |
|
| 92 |
1.1 2.2 |
|
| 93 |
1.1 |
|
| 95 |
1.1 |
|
| 114 |
1.1 |
|
| 115 |
1.1 2.2 |
|
| 116 |
1.1 2.2 3.3 4.4 5.5 |
|
| 118 |
1.1 |
|
| 122 |
1.1 |
|
| 126 |
1.1 2.2 3.3 |
|
| 144 |
1.1 |
|
| 149 |
1.1 2.2 |
|
| 150 |
1.1 2.2 3.3 |
|
| 152 |
1.1 |
|
| 157 |
1.1 |
|
| 162 |
1.1 |
|
| 165 |
1.1 2.2 3.3 4.4 |
|
| 168 |
1.1 2.2 3.3 |
|
| 171 |
1.1 |
|
| 185 |
1.1 |
|
| 186 |
1.1 |
|
| 192 |
1.1 |
|
| 197 |
1.1 2.2 |
|
| 214 |
1.1 2.2 |
|
| 215 |
1.1 |
|
| 220 |
1.1 2.2 |
|
| 241 |
1.1 2.2 |
|
| 242 |
1.1 2.2 |
|
| 243 |
1.1 |
|
| 245 |
1.1 |
|
| 248 |
1.1 |
|
| 249 |
1.1 2.2 |
|
| 250 |
1.1 |
|
| 254 |
1.1 |