Generate all matching collections in one pass through the Trie

4 files changed, 37 insertions, 26 deletions

diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java b/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java
index e3cadd7b795..7d159c993e1 100644
--- a/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/QueryProfileCompiler.java
@@ -2,19 +2,23 @@
 package com.yahoo.search.query.profile;
 
 import com.yahoo.processing.request.CompoundName;
+import com.yahoo.search.query.profile.compiled.Binding;
 import com.yahoo.search.query.profile.compiled.CompiledQueryProfile;
 import com.yahoo.search.query.profile.compiled.CompiledQueryProfileRegistry;
 import com.yahoo.search.query.profile.compiled.DimensionalMap;
 import com.yahoo.search.query.profile.compiled.ValueWithSource;
 import com.yahoo.search.query.profile.types.QueryProfileType;
 
+import java.util.ArrayDeque;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.SortedMap;
 import java.util.TreeMap;
+import java.util.function.BiConsumer;
 import java.util.function.Consumer;
 import java.util.logging.Logger;
 
@@ -111,15 +115,17 @@ public class QueryProfileCompiler {
         for (var variant : variants)
             trie.add(variant);
 
-        for (var variant : variants) {
-            if ( ! variant.binding.isNull())
-                trie.forEachPrefix(variant, prefixVariant -> {
-                    if ( ! hasWildcardBeforeEnd(prefixVariant.binding)) return;
-                    DimensionBinding combined = prefixVariant.binding().combineWith(variant.binding());
-                    if ( ! combined.isInvalid() )
-                        expanded.add(new DimensionBindingForPath(combined, prefixVariant.path()));
-                });
-        }
+        trie.forEachPrefix((prefixes, variantz) -> {
+            for (var prefix : prefixes)
+                if (hasWildcardBeforeEnd(prefix.binding))
+                    for (var variant : variantz)
+                        if ( ! variant.binding.isNull() && variant != prefix) {
+                            DimensionBinding combined = prefix.binding().combineWith(variant.binding());
+                            if ( ! combined.isInvalid() )
+                                expanded.add(new DimensionBindingForPath(combined, prefix.path()));
+                        }
+        });
+
         return expanded;
     }
 
@@ -231,6 +237,10 @@ public class QueryProfileCompiler {
             root.visit(entry, action);
          }
 
+        void forEachPrefix(BiConsumer<Collection<DimensionBindingForPath>, Collection<DimensionBindingForPath>> action) {
+            root.visit(new ArrayDeque<>(), action);
+        }
+
         private static class Node {
 
             private final int depth;
@@ -241,6 +251,15 @@ public class QueryProfileCompiler {
                 this.depth = depth;
             }
 
+            void visit(Deque<DimensionBindingForPath> prefixes, BiConsumer<Collection<DimensionBindingForPath>, Collection<DimensionBindingForPath>> action) {
+                prefixes.addAll(elements);
+                action.accept(prefixes, elements);
+                for (Node child : children.values())
+                    child.visit(prefixes, action);
+                for (int i = 0; i < elements.size(); i++)
+                    prefixes.removeLast();
+            }
+
             void visit(DimensionBindingForPath entry, Consumer<DimensionBindingForPath> action) {
                 elements.forEach(action);
                 if (depth < entry.path().size() && children.containsKey(entry.path().get(depth)))
diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalMap.java b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalMap.java
index b6bd6dc5a6a..6dc5f61c1f6 100644
--- a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalMap.java
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalMap.java
@@ -46,14 +46,9 @@ public class DimensionalMap<VALUE> {
 
         private final Map<CompoundName, DimensionalValue.Builder<VALUE>> entries = new HashMap<>();
 
-        // TODO: DimensionBinding -> Binding?
-        public void put(CompoundName key, DimensionBinding binding, VALUE value) {
-            DimensionalValue.Builder<VALUE> entry = entries.get(key);
-            if (entry == null) {
-                entry = new DimensionalValue.Builder<>();
-                entries.put(key, entry);
-            }
-            entry.add(value, binding);
+        public void put(CompoundName key, Binding binding, VALUE value) {
+            entries.computeIfAbsent(key, __ -> new DimensionalValue.Builder<>())
+                   .add(value, binding);
         }
 
         public DimensionalMap<VALUE> build() {
diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalValue.java b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalValue.java
index fb62cfca7d3..afe07b09d41 100644
--- a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalValue.java
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalValue.java
@@ -76,15 +76,11 @@ public class DimensionalValue<VALUE> {
             return null;
         }
 
-        public void add(VALUE value, DimensionBinding variantBinding) {
+        public void add(VALUE value, Binding variantBinding) {
             // Note: We know we can index by the value because its possible types are constrained
             // to what query profiles allow: String, primitives and query profiles (wrapped as a ValueWithSource)
-            Value.Builder<VALUE> variant = buildableVariants.get(value);
-            if (variant == null) {
-                variant = new Value.Builder<>(value);
-                buildableVariants.put(value, variant);
-            }
-            variant.addVariant(variantBinding, value);
+            buildableVariants.computeIfAbsent(value, Value.Builder::new)
+                             .addVariant(variantBinding, value);
         }
 
         public DimensionalValue<VALUE> build(Map<CompoundName, DimensionalValue.Builder<VALUE>> entries) {
@@ -156,8 +152,8 @@ public class DimensionalValue<VALUE> {
 
             /** Add a binding this holds for */
             @SuppressWarnings("unchecked")
-            public void addVariant(DimensionBinding binding, VALUE newValue) {
-                variants.add(Binding.createFrom(binding));
+            public void addVariant(Binding binding, VALUE newValue) {
+                variants.add(binding);
 
                 // We're combining values for efficiency, so remove incorrect provenance info
                 if (value instanceof ValueWithSource) {
diff --git a/processing/src/main/java/com/yahoo/processing/request/CompoundName.java b/processing/src/main/java/com/yahoo/processing/request/CompoundName.java
index 09c0879fdbf..43cd6fdad80 100644
--- a/processing/src/main/java/com/yahoo/processing/request/CompoundName.java
+++ b/processing/src/main/java/com/yahoo/processing/request/CompoundName.java
@@ -62,6 +62,7 @@ public final class CompoundName {
      * @param name the string representation of the compounds
      * @param compounds the compounds of this name
      */
+    // TODO jonmv: add constructor which reuses rests? Also, keep children in a weak-map for reuse? Avoid unneeded lower-casing?
     private CompoundName(String name, List<String> compounds) {
         if (name == null) throw new NullPointerException("Name can not be null");