Publish

5 files changed, 614 insertions, 0 deletions

diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/Binding.java b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/Binding.java
new file mode 100644
index 00000000000..a440365ceba
--- /dev/null
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/Binding.java
@@ -0,0 +1,128 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.search.query.profile.compiled;
+
+import com.yahoo.search.query.profile.DimensionBinding;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * An immutable binding of a set of dimensions to values.
+ * This binding is minimal in that it only includes dimensions which actually have values.
+ *
+ * @author <a href="mailto:bratseth@yahoo-inc.com">Jon Bratseth</a>
+ */
+public class Binding implements Comparable<Binding> {
+
+    private static final int maxDimensions = 31;
+
+    /**
+     * A higher number means this is more general. This accounts for both the number and position of the bindings
+     * in the dimensional space, such that bindings in earlier dimensions are matched before bindings in
+     * later dimensions
+     */
+    private final int generality;
+
+    /** The dimensions of this. Unenforced invariant: Content never changes. */
+    private final String[] dimensions;
+
+    /** The values of those dimensions. Unenforced invariant: Content never changes. */
+    private final String[] dimensionValues;
+
+    private final int hashCode;
+
+    @SuppressWarnings("unchecked")
+    public static final Binding nullBinding= new Binding(Integer.MAX_VALUE, Collections.<String,String>emptyMap());
+
+    public static Binding createFrom(DimensionBinding dimensionBinding) {
+        if (dimensionBinding.getDimensions().size() > maxDimensions)
+            throw new IllegalArgumentException("More than 31 dimensions is not supported");
+
+        int generality = 0;
+        Map<String, String> context = new HashMap<>();
+        if (dimensionBinding.getDimensions() == null || dimensionBinding.getDimensions().isEmpty()) { // TODO: Just have this return the nullBinding
+            generality = Integer.MAX_VALUE;
+        }
+        else {
+            for (int i = 0; i <= maxDimensions; i++) {
+                String value = i < dimensionBinding.getDimensions().size() ? dimensionBinding.getValues().get(i) : null;
+                if (value == null)
+                    generality += Math.pow(2, maxDimensions - i-1);
+                else
+                    context.put(dimensionBinding.getDimensions().get(i), value);
+            }
+        }
+        return new Binding(generality, context);
+    }
+
+    private Binding(int generality, Map<String, String> binding) {
+        this.generality = generality;
+
+        // Map -> arrays to limit memory consumption and speed up evaluation
+        dimensions = new String[binding.size()];
+        dimensionValues = new String[binding.size()];
+
+        int i = 0;
+        int bindingHash = 0;
+        for (Map.Entry<String,String> entry : binding.entrySet()) {
+            dimensions[i] = entry.getKey();
+            dimensionValues[i] = entry.getValue();
+            bindingHash += i * entry.getKey().hashCode() +  11 * i * entry.getValue().hashCode();
+            i++;
+        }
+        this.hashCode = bindingHash;
+    }
+
+    /** Returns true only if this binding is null (contains no values for its dimensions (if any) */
+    public boolean isNull() { return dimensions.length == 0; }
+
+    @Override
+    public String toString() {
+        StringBuilder b = new StringBuilder("Binding[");
+        for (int i = 0; i < dimensions.length; i++)
+            b.append(dimensions[i]).append("=").append(dimensionValues[i]).append(",");
+        if (dimensions.length > 0)
+            b.setLength(b.length()-1);
+        b.append("] (generality " + generality + ")");
+        return b.toString();
+    }
+
+    /** Returns whether the given binding has exactly the same values as this */
+    @Override
+    public boolean equals(Object o) {
+        if (o == this) return true;
+        if (! (o instanceof Binding)) return false;
+        Binding other = (Binding)o;
+        return Arrays.equals(this.dimensions, other.dimensions)
+            && Arrays.equals(this.dimensionValues, other.dimensionValues);
+    }
+
+    @Override
+    public int hashCode() { return hashCode; }
+
+    /**
+     * Returns true if all the dimension values in this have the same values
+     * in the given context.
+     */
+    public boolean matches(Map<String,String> context) {
+        for (int i = 0; i < dimensions.length; i++) {
+            if ( ! dimensionValues[i].equals(context.get(dimensions[i]))) return false;
+        }
+        return true;
+    }
+
+    /**
+     * Implements a partial ordering where more specific bindings come before less specific ones,
+     * taking both the number of bindings and their positions into account (earlier dimensions
+     * take precedence over later ones.
+     * <p>
+     * The order is not well defined for bindings in different dimensional spaces.
+     */
+    @Override
+    public int compareTo(Binding other) {
+        return Integer.compare(this.generality, other.generality);
+    }
+
+}
diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfile.java b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfile.java
new file mode 100644
index 00000000000..a4056ee55a2
--- /dev/null
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfile.java
@@ -0,0 +1,183 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.search.query.profile.compiled;
+
+import com.yahoo.component.AbstractComponent;
+import com.yahoo.component.ComponentId;
+import com.yahoo.processing.request.CompoundName;
+import com.yahoo.processing.request.Properties;
+import com.yahoo.search.query.profile.QueryProfileProperties;
+import com.yahoo.search.query.profile.SubstituteString;
+import com.yahoo.search.query.profile.types.QueryProfileType;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
+
+/**
+ * A query profile in a state where it is optimized for fast lookups.
+ *
+ * @author bratseth
+ */
+public class CompiledQueryProfile extends AbstractComponent implements Cloneable {
+
+    private static final Pattern namePattern=Pattern.compile("[$a-zA-Z_/][-$a-zA-Z0-9_/()]*");
+
+    private final CompiledQueryProfileRegistry registry;
+
+    /** The type of this, or null if none */
+    private final QueryProfileType type;
+
+    /** The values of this */
+    private final DimensionalMap<CompoundName, Object> entries;
+
+    /** Keys which have a type in this */
+    private final DimensionalMap<CompoundName, QueryProfileType> types;
+
+    /** Keys which are (typed or untyped) references to other query profiles in this. Used as a set. */
+    private final DimensionalMap<CompoundName, Object> references;
+
+    /** Values which are not overridable in this. Used as a set. */
+    private final DimensionalMap<CompoundName, Object> unoverridables;
+
+    /**
+     * Creates a new query profile from an id.
+     */
+    public CompiledQueryProfile(ComponentId id, QueryProfileType type,
+                                DimensionalMap<CompoundName, Object> entries,
+                                DimensionalMap<CompoundName, QueryProfileType> types,
+                                DimensionalMap<CompoundName, Object> references,
+                                DimensionalMap<CompoundName, Object> unoverridables,
+                                CompiledQueryProfileRegistry registry) {
+        super(id);
+        this.registry = registry;
+        if (type != null)
+            type.freeze();
+        this.type = type;
+        this.entries = entries;
+        this.types = types;
+        this.references = references;
+        this.unoverridables = unoverridables;
+        if ( ! id.isAnonymous())
+            validateName(id.getName());
+    }
+
+    // ----------------- Public API -------------------------------------------------------------------------------
+
+    /** Returns the registry this belongs to, or null if none (in which case runtime profile reference assignment won't work) */
+    public CompiledQueryProfileRegistry getRegistry() { return registry; }
+
+    /** Returns the type of this or null if it has no type */
+    // TODO: Move into below
+    public QueryProfileType getType() { return type; }
+
+    /**
+     * Returns whether or not the given field name can be overridden at runtime.
+     * Attempts to override values which cannot be overridden will not fail but be ignored.
+     * Default: true.
+     *
+     * @param name the name of the field to check
+     * @param context the context in which to check, or null if none
+     */
+    public final boolean isOverridable(CompoundName name, Map<String, String> context) {
+        return unoverridables.get(name, context) == null;
+    }
+
+    /** Returns the type of a given prefix reachable from this profile, or null if none */
+    public final QueryProfileType getType(CompoundName name, Map<String, String> context) {
+        return types.get(name, context);
+    }
+
+    /** Returns the types reachable from this, or an empty map (never null) if none */
+    public DimensionalMap<CompoundName, QueryProfileType> getTypes() { return types; }
+
+    /** Returns the references reachable from this, or an empty map (never null) if none */
+    public DimensionalMap<CompoundName, Object> getReferences() { return references; }
+
+    /**
+     * Return all objects that start with the given prefix path using no context. Use "" to list all.
+     * <p>
+     * For example, if {a.d =&gt; "a.d-value" ,a.e =&gt; "a.e-value", b.d =&gt; "b.d-value", then calling listValues("a")
+     * will return {"d" =&gt; "a.d-value","e" =&gt; "a.e-value"}
+     */
+    public final Map<String, Object> listValues(final CompoundName prefix) {  return listValues(prefix, Collections.<String,String>emptyMap()); }
+    public final Map<String, Object> listValues(final String prefix) { return listValues(new CompoundName(prefix)); }
+    /**
+     * Return all objects that start with the given prefix path. Use "" to list all.
+     * <p>
+     * For example, if {a.d =&gt; "a.d-value" ,a.e =&gt; "a.e-value", b.d =&gt; "b.d-value", then calling listValues("a")
+     * will return {"d" =&gt; "a.d-value","e" =&gt; "a.e-value"}
+     */
+    public final Map<String, Object> listValues(final String prefix,Map<String,String> context) {
+        return listValues(new CompoundName(prefix), context);
+    }
+    /**
+     * Return all objects that start with the given prefix path. Use "" to list all.
+     * <p>
+     * For example, if {a.d =&gt; "a.d-value" ,a.e =&gt; "a.e-value", b.d =&gt; "b.d-value", then calling listValues("a")
+     * will return {"d" =&gt; "a.d-value","e" =&gt; "a.e-value"}
+     */
+    public final Map<String, Object> listValues(final CompoundName prefix,Map<String,String> context) {
+        return listValues(prefix, context, null);
+    }
+    /**
+     * Adds all objects that start with the given path prefix to the given value map. Use "" to list all.
+     * <p>
+     * For example, if {a.d =&gt; "a.d-value" ,a.e =&gt; "a.e-value", b.d =&gt; "b.d-value", then calling listValues("a")
+     * will return {"d" =&gt; "a.d-value","e" =&gt; "a.e-value"}
+     */
+    public Map<String, Object> listValues(CompoundName prefix, Map<String,String> context, Properties substitution) {
+        Map<String, Object> values = new HashMap<>();
+        for (Map.Entry<CompoundName, DimensionalValue<Object>> entry : entries.entrySet()) {
+            if ( entry.getKey().size() <= prefix.size()) continue;
+            if ( ! entry.getKey().hasPrefix(prefix)) continue;
+
+            Object value = entry.getValue().get(context);
+            if (value == null) continue;
+
+            value = substitute(value, context, substitution);
+            CompoundName suffixName = entry.getKey().rest(prefix.size());
+            values.put(suffixName.toString(), value);
+        }
+        return values;
+    }
+
+    public final Object get(String name) {
+        return get(name, Collections.<String,String>emptyMap());
+    }
+    public final Object get(String name, Map<String,String> context) {
+        return get(name, context, new QueryProfileProperties(this));
+    }
+    public final Object get(String name, Map<String,String> context, Properties substitution) {
+        return get(new CompoundName(name), context, substitution);
+    }
+    public final Object get(CompoundName name, Map<String, String> context, Properties substitution) {
+        return substitute(entries.get(name, context), context, substitution);
+    }
+
+    private Object substitute(Object value, Map<String,String> context, Properties substitution) {
+        if (value == null) return value;
+        if (substitution == null) return value;
+        if (value.getClass() != SubstituteString.class) return value;
+        return ((SubstituteString)value).substitute(context, substitution);
+    }
+
+    /** Throws IllegalArgumentException if the given string is not a valid query profile name */
+    private static void validateName(String name) {
+        Matcher nameMatcher=namePattern.matcher(name);
+        if ( ! nameMatcher.matches())
+            throw new IllegalArgumentException("Illegal name '" + name + "'");
+    }
+
+    @Override
+    public CompiledQueryProfile clone() {
+        return this; // immutable
+    }
+
+    @Override
+    public String toString() {
+        return "query profile '" + getId()  + "'" + (type!=null ? " of type '" + type.getId() + "'" : "");
+    }
+
+}
diff --git a/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfileRegistry.java b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfileRegistry.java
new file mode 100644
index 00000000000..91a81888267
--- /dev/null
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/CompiledQueryProfileRegistry.java
@@ -0,0 +1,76 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.search.query.profile.compiled;
+
+import com.yahoo.component.ComponentSpecification;
+import com.yahoo.component.provider.ComponentRegistry;
+import com.yahoo.search.query.profile.types.QueryProfileType;
+import com.yahoo.search.query.profile.types.QueryProfileTypeRegistry;
+
+/**
+ * A set of compiled query profiles.
+ *
+ * @author bratseth
+ */
+public class CompiledQueryProfileRegistry extends ComponentRegistry<CompiledQueryProfile> {
+
+    private final QueryProfileTypeRegistry typeRegistry;
+
+    /** Creates a compiled query profile registry with no types */
+    public CompiledQueryProfileRegistry() {
+        this(QueryProfileTypeRegistry.emptyFrozen());
+    }
+
+    public CompiledQueryProfileRegistry(QueryProfileTypeRegistry typeRegistry) {
+        this.typeRegistry = typeRegistry;
+    }
+
+    /** Registers a type by its id */
+    public void register(CompiledQueryProfile profile) {
+        super.register(profile.getId(), profile);
+    }
+
+    public QueryProfileTypeRegistry getTypeRegistry() { return typeRegistry; }
+
+    /**
+     * <p>Returns a query profile for the given request string, or null if a suitable one is not found.</p>
+     *
+     * The request string must be a valid {@link com.yahoo.component.ComponentId} or null.<br>
+     * If the string is null, the profile named "default" is returned, or null if that does not exists.
+     *
+     * <p>
+     * The version part (if any) is matched used the usual component version patching rules.
+     * If the name part matches a query profile name perfectly, that profile is returned.
+     * If not, and the name is a slash-separated path, the profile with the longest matching left sub-path
+     * which has a type which allows path matching is used. If there is no such profile, null is returned.
+     */
+    public CompiledQueryProfile findQueryProfile(String idString) {
+        if (idString==null || idString.isEmpty()) return getComponent("default");
+        ComponentSpecification id=new ComponentSpecification(idString);
+        CompiledQueryProfile profile=getComponent(id);
+        if (profile!=null) return profile;
+
+        return findPathParentQueryProfile(new ComponentSpecification(idString));
+    }
+
+    private CompiledQueryProfile findPathParentQueryProfile(ComponentSpecification id) {
+        // Try the name with "/" appended - should have the same semantics with path matching
+        CompiledQueryProfile slashedProfile=getComponent(new ComponentSpecification(id.getName() + "/",id.getVersionSpecification()));
+        if (slashedProfile!=null && slashedProfile.getType()!=null && slashedProfile.getType().getMatchAsPath())
+            return slashedProfile;
+
+        // Extract the parent (if any)
+        int slashIndex=id.getName().lastIndexOf("/");
+        if (slashIndex<1) return null;
+        String parentName=id.getName().substring(0,slashIndex);
+        if (parentName.equals("")) return null;
+
+        ComponentSpecification parentId=new ComponentSpecification(parentName,id.getVersionSpecification());
+
+        CompiledQueryProfile pathParentProfile=getComponent(parentId);
+
+        if (pathParentProfile!=null && pathParentProfile.getType()!=null && pathParentProfile.getType().getMatchAsPath())
+            return pathParentProfile;
+        return findPathParentQueryProfile(parentId);
+    }
+
+}
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
new file mode 100644
index 00000000000..b82939fa4ac
--- /dev/null
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalMap.java
@@ -0,0 +1,68 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.search.query.profile.compiled;
+
+import com.google.common.collect.ImmutableMap;
+import com.yahoo.search.query.profile.DimensionBinding;
+
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * A map which may return different values depending on the values given in a context
+ * supplied with the key on all operations.
+ * <p>
+ * Dimensional maps are immutable and created through a DimensionalMap.Builder
+ *
+ * @author <a href="mailto:bratseth@yahoo-inc.com">Jon Bratseth</a>
+ */
+public class DimensionalMap<KEY, VALUE> {
+
+    private final Map<KEY, DimensionalValue<VALUE>> values;
+
+    private DimensionalMap(Map<KEY, DimensionalValue<VALUE>> values) {
+        this.values = ImmutableMap.copyOf(values);
+    }
+
+    /** Returns the value for this key matching a context, or null if none */
+    public VALUE get(KEY key, Map<String, String> context) {
+        DimensionalValue<VALUE> variants = values.get(key);
+        if (variants == null) return null;
+        return variants.get(context);
+    }
+
+    /** Returns the set of dimensional entries across all contexts. */
+    public Set<Map.Entry<KEY, DimensionalValue<VALUE>>> entrySet() {
+        return values.entrySet();
+    }
+
+    /** Returns true if this is empty for all contexts. */
+    public boolean isEmpty() {
+        return values.isEmpty();
+    }
+
+    public static class Builder<KEY, VALUE> {
+
+        private Map<KEY, DimensionalValue.Builder<VALUE>> entries = new HashMap<>();
+
+        // TODO: DimensionBinding -> Binding?
+        public void put(KEY 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 DimensionalMap<KEY, VALUE> build() {
+            Map<KEY, DimensionalValue<VALUE>> map = new HashMap<>();
+            for (Map.Entry<KEY, DimensionalValue.Builder<VALUE>> entry : entries.entrySet()) {
+                map.put(entry.getKey(), entry.getValue().build());
+            }
+            return new DimensionalMap<>(map);
+        }
+
+    }
+
+}
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
new file mode 100644
index 00000000000..0112928ada6
--- /dev/null
+++ b/container-search/src/main/java/com/yahoo/search/query/profile/compiled/DimensionalValue.java
@@ -0,0 +1,159 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.search.query.profile.compiled;
+
+import com.yahoo.search.query.profile.DimensionBinding;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Contains the values a given key in a DimensionalMap may take for different dimensional contexts.
+ *
+ * @author <a href="mailto:bratseth@yahoo-inc.com">Jon Bratseth</a>
+ */
+public class DimensionalValue<VALUE> {
+
+    private final List<Value<VALUE>> values;
+
+    /** Create a set of variants which is a single value regardless of dimensions */
+    public DimensionalValue(Value<VALUE> value) {
+        this.values = Collections.singletonList(value);
+    }
+
+    public DimensionalValue(List<Value<VALUE>> valueVariants) {
+        if (valueVariants.size() == 1) { // special cased for efficiency
+            this.values = Collections.singletonList(valueVariants.get(0));
+        }
+        else {
+            this.values = new ArrayList<>(valueVariants);
+            Collections.sort(this.values);
+        }
+    }
+
+    /** Returns the value matching this context, or null if none */
+    public VALUE get(Map<String, String> context) {
+        if (context == null)
+            context = Collections.emptyMap();
+        for (Value<VALUE> value : values) {
+            if (value.matches(context))
+                return value.value();
+        }
+        return null;
+    }
+
+    public boolean isEmpty() { return values.isEmpty(); }
+
+    @Override
+    public String toString() {
+        return values.toString();
+    }
+
+    public static class Builder<VALUE> {
+
+        /** The minimal set of variants needed to capture all values at this key */
+        private Map<VALUE, Value.Builder<VALUE>> buildableVariants = new HashMap<>();
+
+        public void add(VALUE value, DimensionBinding 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
+            Value.Builder variant = buildableVariants.get(value);
+            if (variant == null) {
+                variant = new Value.Builder<>(value);
+                buildableVariants.put(value, variant);
+            }
+            variant.addVariant(variantBinding);
+        }
+
+        public DimensionalValue<VALUE> build() {
+            List<Value> variants = new ArrayList<>();
+            for (Value.Builder buildableVariant : buildableVariants.values()) {
+                variants.addAll(buildableVariant.build());
+            }
+            return new DimensionalValue(variants);
+        }
+
+    }
+
+    /** A value for a particular binding */
+    private static class Value<VALUE> implements Comparable<Value> {
+
+        private VALUE value = null;
+
+        /** The minimal binding this holds for */
+        private Binding binding = null;
+
+        public Value(VALUE value, Binding binding) {
+            this.value = value;
+            this.binding = binding;
+        }
+
+        /** Returns the value at this entry or null if none */
+        public VALUE value() { return value; }
+
+        /** Returns the binding that must match for this to be a valid entry, or Binding.nullBinding if none */
+        public Binding binding() {
+            if (binding == null) return Binding.nullBinding;
+            return binding;
+        }
+
+        public boolean matches(Map<String, String> context) {
+            return binding.matches(context);
+        }
+
+        @Override
+        public int compareTo(Value other) {
+            return this.binding.compareTo(other.binding);
+        }
+
+        @Override
+        public String toString() {
+            return " value '" + value + "' for " + binding;
+        }
+
+        /**
+         * A single value with the minimal set of dimension combinations it holds for.
+         */
+        private static class Builder<VALUE> {
+
+            private final VALUE value;
+
+            /**
+             * The set of bindings this value is for.
+             * Some of these are more general versions of others.
+             * We need to keep both to allow interleaving a different value with medium generality.
+             */
+            private Set<DimensionBinding> variants = new HashSet<>();
+
+            public Builder(VALUE value) {
+                this.value = value;
+            }
+
+            /** Add a binding this holds for */
+            public void addVariant(DimensionBinding binding) {
+                variants.add(binding);
+            }
+
+            /** Build a separate value object for each dimension combination which has this value */
+            public List<Value<VALUE>> build() {
+                // Shortcut for efficiency of the normal case
+                if (variants.size()==1)
+                    return Collections.singletonList(new Value<>(value, Binding.createFrom(variants.iterator().next())));
+
+                List<Value<VALUE>> values = new ArrayList<>(variants.size());
+                for (DimensionBinding variant : variants)
+                    values.add(new Value<>(value, Binding.createFrom(variant)));
+                return values;
+            }
+
+            public Object value() {
+                return value;
+            }
+
+        }
+    }
+}