diff options
Diffstat (limited to 'predicate-search-core/src/main/java/com/yahoo/document/predicate')
17 files changed, 1403 insertions, 0 deletions
diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/BinaryFormat.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BinaryFormat.java new file mode 100644 index 00000000000..89dcbc59d99 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BinaryFormat.java @@ -0,0 +1,167 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import com.yahoo.slime.Cursor; +import com.yahoo.slime.Inspector; +import com.yahoo.slime.Slime; + +import java.util.Objects; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class BinaryFormat { + + final static String NODE_TYPE = "type"; + final static String KEY = "key"; + final static String SET = "feature_set"; + final static String RANGE_MIN = "range_min"; + final static String RANGE_MAX = "range_max"; + final static String CHILDREN = "children"; + final static String PARTITIONS = "partitions"; + final static String EDGE_PARTITIONS = "edge_partitions"; + final static String HASHED_PARTITIONS = "hashed_partitions"; + final static String HASHED_EDGE_PARTITIONS = "hashed_edge_partitions"; + final static String HASH = "hash"; + final static String PAYLOAD = "payload"; + final static String LABEL = "label"; + final static String VALUE = "value"; + final static String LOWER_BOUND = "lower_bound"; + final static String UPPER_BOUND = "upper_bound"; + + final static int TYPE_CONJUNCTION = 1; + final static int TYPE_DISJUNCTION = 2; + final static int TYPE_NEGATION = 3; + final static int TYPE_FEATURE_SET = 4; + final static int TYPE_FEATURE_RANGE = 5; + final static int TYPE_TRUE = 6; + final static int TYPE_FALSE = 7; + + public static byte[] encode(Predicate predicate) { + Objects.requireNonNull(predicate, "predicate"); + Slime slime = new Slime(); + encode(predicate, slime.setObject()); + return com.yahoo.slime.BinaryFormat.encode(slime); + } + + public static Predicate decode(byte[] buf) { + Objects.requireNonNull(buf, "buf"); + Slime slime = com.yahoo.slime.BinaryFormat.decode(buf); + return decode(slime.get()); + } + + private static Predicate decode(Inspector in) { + switch ((int)in.field(NODE_TYPE).asLong()) { + case TYPE_CONJUNCTION: + Conjunction conjunction = new Conjunction(); + in = in.field(CHILDREN); + for (int i = 0, len = in.children(); i < len; ++i) { + conjunction.addOperand(decode(in.entry(i))); + } + return conjunction; + + case TYPE_DISJUNCTION: + Disjunction disjunction = new Disjunction(); + in = in.field(CHILDREN); + for (int i = 0, len = in.children(); i < len; ++i) { + disjunction.addOperand(decode(in.entry(i))); + } + return disjunction; + + case TYPE_NEGATION: + return new Negation(decode(in.field(CHILDREN).entry(0))); + + case TYPE_FEATURE_RANGE: + FeatureRange featureRange = new FeatureRange(in.field(KEY).asString()); + if (in.field(RANGE_MIN).valid()) { + featureRange.setFromInclusive(in.field(RANGE_MIN).asLong()); + } + if (in.field(RANGE_MAX).valid()) { + featureRange.setToInclusive(in.field(RANGE_MAX).asLong()); + } + Inspector p_in = in.field(PARTITIONS); + for (int i = 0, len = p_in.children(); i < len; ++i) { + featureRange.addPartition(new RangePartition(p_in.entry(i).asString())); + } + p_in = in.field(EDGE_PARTITIONS); + for (int i = 0, len = p_in.children(); i < len; ++i) { + Inspector obj = p_in.entry(i); + featureRange.addPartition(new RangeEdgePartition( + obj.field(LABEL).asString(), obj.field(VALUE).asLong(), + (int)obj.field(LOWER_BOUND).asLong(), (int)obj.field(UPPER_BOUND).asLong())); + } + return featureRange; + + case TYPE_FEATURE_SET: + FeatureSet featureSet = new FeatureSet(in.field(KEY).asString()); + in = in.field(SET); + for (int i = 0, len = in.children(); i < len; ++i) { + featureSet.addValue(in.entry(i).asString()); + } + return featureSet; + + case TYPE_TRUE: + return new BooleanPredicate(true); + + case TYPE_FALSE: + return new BooleanPredicate(false); + + default: + throw new UnsupportedOperationException(String.valueOf(in.field(NODE_TYPE).asLong())); + } + } + + private static void encode(Predicate predicate, Cursor out) { + if (predicate instanceof Conjunction) { + out.setLong(NODE_TYPE, TYPE_CONJUNCTION); + out = out.setArray(CHILDREN); + for (Predicate operand : ((Conjunction)predicate).getOperands()) { + encode(operand, out.addObject()); + } + } else if (predicate instanceof Disjunction) { + out.setLong(NODE_TYPE, TYPE_DISJUNCTION); + out = out.setArray(CHILDREN); + for (Predicate operand : ((Disjunction)predicate).getOperands()) { + encode(operand, out.addObject()); + } + } else if (predicate instanceof FeatureRange) { + FeatureRange range = (FeatureRange) predicate; + out.setLong(NODE_TYPE, TYPE_FEATURE_RANGE); + out.setString(KEY, range.getKey()); + Long from = range.getFromInclusive(); + if (from != null) { + out.setLong(RANGE_MIN, from); + } + Long to = range.getToInclusive(); + if (to != null) { + out.setLong(RANGE_MAX, to); + } + Cursor p_out = out.setArray(HASHED_PARTITIONS); + for (RangePartition p : range.getPartitions()) { + p_out.addLong(PredicateHash.hash64(p.getLabel())); + } + p_out = out.setArray(HASHED_EDGE_PARTITIONS); + for (RangeEdgePartition p : range.getEdgePartitions()) { + Cursor obj = p_out.addObject(); + obj.setLong(HASH, PredicateHash.hash64(p.getLabel())); + obj.setLong(VALUE, p.getValue()); + obj.setLong(PAYLOAD, p.encodeBounds()); + } + } else if (predicate instanceof FeatureSet) { + out.setLong(NODE_TYPE, TYPE_FEATURE_SET); + out.setString(KEY, ((FeatureSet)predicate).getKey()); + out = out.setArray(SET); + for (String value : ((FeatureSet)predicate).getValues()) { + out.addString(value); + } + } else if (predicate instanceof Negation) { + out.setLong(NODE_TYPE, TYPE_NEGATION); + out = out.setArray(CHILDREN); + encode(((Negation)predicate).getOperand(), out.addObject()); + } else if (predicate instanceof BooleanPredicate) { + out.setLong(NODE_TYPE, ((BooleanPredicate)predicate).getValue() ? TYPE_TRUE : TYPE_FALSE); + } else { + throw new UnsupportedOperationException(predicate.getClass().getName()); + } + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/BooleanPredicate.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BooleanPredicate.java new file mode 100644 index 00000000000..507d48bf241 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/BooleanPredicate.java @@ -0,0 +1,54 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class BooleanPredicate extends PredicateValue { + + private boolean value; + + public BooleanPredicate(boolean value) { + this.value = value; + } + + public boolean getValue() { + return value; + } + + public BooleanPredicate setValue(boolean value) { + this.value = value; + return this; + } + + @Override + public BooleanPredicate clone() throws CloneNotSupportedException { + return (BooleanPredicate)super.clone(); + } + + @Override + public int hashCode() { + return value ? Boolean.TRUE.hashCode() : Boolean.FALSE.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof BooleanPredicate)) { + return false; + } + BooleanPredicate rhs = (BooleanPredicate)obj; + if (value != rhs.value) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + out.append(value ? "true" : "false"); + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Conjunction.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Conjunction.java new file mode 100644 index 00000000000..d917e374b69 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Conjunction.java @@ -0,0 +1,93 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class Conjunction extends PredicateOperator { + + private List<Predicate> operands; + + public Conjunction(Predicate... operands) { + this(Arrays.asList(operands)); + } + + public Conjunction(List<? extends Predicate> operands) { + this.operands = new ArrayList<>(operands); + } + + public Conjunction addOperand(Predicate operand) { + operands.add(operand); + return this; + } + + public Conjunction addOperands(Collection<? extends Predicate> operands) { + this.operands.addAll(operands); + return this; + } + + public Conjunction setOperands(Collection<? extends Predicate> operands) { + this.operands.clear(); + this.operands.addAll(operands); + return this; + } + + @Override + public List<Predicate> getOperands() { + return operands; + } + + @Override + public Conjunction clone() throws CloneNotSupportedException { + Conjunction obj = (Conjunction)super.clone(); + obj.operands = new ArrayList<>(operands.size()); + for (Predicate operand : operands) { + obj.operands.add(operand.clone()); + } + return obj; + } + + @Override + public int hashCode() { + return operands.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof Conjunction)) { + return false; + } + Conjunction rhs = (Conjunction)obj; + if (!operands.equals(rhs.operands)) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + for (Iterator<Predicate> it = operands.iterator(); it.hasNext(); ) { + Predicate operand = it.next(); + if (operand instanceof Disjunction || operand instanceof FeatureConjunction) { + out.append('('); + operand.appendTo(out); + out.append(')'); + } else { + operand.appendTo(out); + } + if (it.hasNext()) { + out.append(" and "); + } + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Disjunction.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Disjunction.java new file mode 100644 index 00000000000..c5fa6ba1f70 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Disjunction.java @@ -0,0 +1,93 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class Disjunction extends PredicateOperator { + + private List<Predicate> operands; + + public Disjunction(Predicate... operands) { + this(Arrays.asList(operands)); + } + + public Disjunction(List<? extends Predicate> operands) { + this.operands = new ArrayList<>(operands); + } + + public Disjunction addOperand(Predicate operand) { + operands.add(operand); + return this; + } + + public Disjunction addOperands(Collection<? extends Predicate> operands) { + this.operands.addAll(operands); + return this; + } + + public Disjunction setOperands(Collection<? extends Predicate> operands) { + this.operands.clear(); + this.operands.addAll(operands); + return this; + } + + @Override + public List<Predicate> getOperands() { + return operands; + } + + @Override + public Disjunction clone() throws CloneNotSupportedException { + Disjunction obj = (Disjunction)super.clone(); + obj.operands = new ArrayList<>(operands.size()); + for (Predicate operand : operands) { + obj.operands.add(operand.clone()); + } + return obj; + } + + @Override + public int hashCode() { + return operands.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof Disjunction)) { + return false; + } + Disjunction rhs = (Disjunction)obj; + if (!operands.equals(rhs.operands)) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + for (Iterator<Predicate> it = operands.iterator(); it.hasNext(); ) { + Predicate operand = it.next(); + if (operand instanceof Conjunction) { + out.append('('); + operand.appendTo(out); + out.append(')'); + } else { + operand.appendTo(out); + } + if (it.hasNext()) { + out.append(" or "); + } + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureConjunction.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureConjunction.java new file mode 100644 index 00000000000..ba6bb32e05f --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureConjunction.java @@ -0,0 +1,104 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + +/** + * A FeatureConjunction is a special type of Conjunction where + * all children are either a FeatureSet or a Negation (with an underlying FeatureSet). + * The underlying FeatureSets may only have one value. + * + * @author bjorncs + */ +public class FeatureConjunction extends PredicateOperator { + private final List<Predicate> operands; + + public FeatureConjunction(List<Predicate> operands) { + validateOperands(operands); + this.operands = new ArrayList<>(operands); + } + + private static void validateOperands(List<Predicate> operands) { + if (operands.size() <= 1) { + throw new IllegalArgumentException("Number of operands must 2 or more, was: " + operands.size()); + } + if (!operands.stream() + .allMatch(FeatureConjunction::isValidFeatureConjunctionOperand)) { + throw new IllegalArgumentException( + "A FeatureConjunction may only contain instances of Negation and FeatureSet, " + + "and a FeatureSet may only have one value."); + } + + long uniqueKeys = operands.stream().map(FeatureConjunction::getFeatureSetKey).distinct().count(); + if (operands.size() > uniqueKeys) { + throw new IllegalArgumentException("Each FeatureSet key must have a unique key."); + } + } + + private static String getFeatureSetKey(Predicate predicate) { + if (predicate instanceof FeatureSet) { + return ((FeatureSet) predicate).getKey(); + } else { + Negation negation = (Negation) predicate; + return ((FeatureSet) negation.getOperand()).getKey(); + } + } + + public static boolean isValidFeatureConjunctionOperand(Predicate operand) { + return operand instanceof Negation + && ((Negation) operand).getOperand() instanceof FeatureSet + && isValidFeatureConjunctionOperand(((Negation) operand).getOperand()) + || operand instanceof FeatureSet && ((FeatureSet) operand).getValues().size() == 1; + } + + @Override + public List<Predicate> getOperands() { + return operands; + } + + @Override + protected void appendTo(StringBuilder out) { + for (Iterator<Predicate> it = operands.iterator(); it.hasNext(); ) { + Predicate operand = it.next(); + if (operand instanceof Disjunction) { + out.append('('); + operand.appendTo(out); + out.append(')'); + } else { + operand.appendTo(out); + } + if (it.hasNext()) { + out.append(" conj "); + } + } + } + + @Override + public FeatureConjunction clone() throws CloneNotSupportedException { + return new FeatureConjunction(operands); + } + + @Override + public int hashCode() { + return operands.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof FeatureConjunction)) { + return false; + } + FeatureConjunction rhs = (FeatureConjunction)obj; + if (!operands.equals(rhs.operands)) { + return false; + } + return true; + } + + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureRange.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureRange.java new file mode 100644 index 00000000000..2ca09ee98f0 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureRange.java @@ -0,0 +1,190 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.ArrayList; +import java.util.List; +import java.util.Objects; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class FeatureRange extends PredicateValue { + + private String key; + private Long from; + private Long to; + private List<RangePartition> partitions; + private List<RangeEdgePartition> edgePartitions; + + public FeatureRange(String key) { + this(key, null, null); + } + + public FeatureRange(String key, Long fromInclusive, Long toInclusive) { + setKey(key); + setFromInclusive(fromInclusive); + setToInclusive(toInclusive); + partitions = new ArrayList<>(); + edgePartitions = new ArrayList<>(); + } + + public FeatureRange setKey(String key) { + Objects.requireNonNull(key, "key"); + this.key = key; + return this; + } + + public String getKey() { + return key; + } + + public FeatureRange setFromInclusive(Long from) { + if (from != null && to != null && from > to) { + throw new IllegalArgumentException("Expected 'from' less than or equal to " + to + ", got " + from + "."); + } + this.from = from; + return this; + } + + public Long getFromInclusive() { + return from; + } + + public FeatureRange setToInclusive(Long to) { + if (from != null && to != null && from > to) { + throw new IllegalArgumentException("Expected 'to' greater than or equal to " + from + ", got " + to + "."); + } + this.to = to; + return this; + } + + public Long getToInclusive() { + return to; + } + + public void addPartition(RangePartition p) { + if (p instanceof RangeEdgePartition) { + edgePartitions.add((RangeEdgePartition)p); + } else { + partitions.add(p); + } + } + + public List<RangeEdgePartition> getEdgePartitions() { + return edgePartitions; + } + + public List<RangePartition> getPartitions() { + return partitions; + } + + public void clearPartitions() { + partitions.clear(); + edgePartitions.clear(); + } + + @Override + public FeatureRange clone() throws CloneNotSupportedException { + return (FeatureRange)super.clone(); + } + + @Override + public int hashCode() { + return ((key.hashCode() + (from != null ? from.hashCode() : 0)) * 31 + (to != null ? to.hashCode() : 0)) * 31; + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof FeatureRange)) { + return false; + } + FeatureRange rhs = (FeatureRange)obj; + if (!key.equals(rhs.key)) { + return false; + } + if (!Objects.equals(from, rhs.from)) { + return false; + } + if (!Objects.equals(to, rhs.to)) { + return false; + } + return partitions.equals(rhs.partitions) && edgePartitions.equals(rhs.edgePartitions); + } + + @Override + protected void appendTo(StringBuilder out) { + appendQuotedTo(key, out); + out.append(" in ["); + if (from != null) { + out.append(from); + } + out.append(".."); + if (to != null) { + out.append(to); + } + if (!partitions.isEmpty() || !edgePartitions.isEmpty()) { + out.append(" ("); + for (RangeEdgePartition p : edgePartitions) { + p.appendTo(out); + out.append(','); + } + for (RangePartition p : partitions) { + p.appendTo(out); + out.append(','); + } + out.deleteCharAt(out.length() - 1); // Remove extra ',' + out.append(")"); + } + out.append("]"); + } + + public static FeatureRange buildFromMixedIn(String key, List<String> partitions, int arity) { + Long fromInclusive = null; + Long toInclusive = null; + long from = 0; + long to = 0; + for (String p : partitions) { + String[] parts = p.split(","); + if (parts.length == 1) { + String[] subparts = parts[0].split("=|-"); + int offset = subparts.length == 3? 0 : 1; + if (subparts.length < 3 || subparts.length > 4) { + throw new IllegalArgumentException("MIXED_IN range partition must be on the form label=val-val"); + } + from = Long.parseLong(subparts[offset + 1]); + to = Long.parseLong(subparts[offset + 2]); + if (parts[0].contains("=-")) { + long tmp = from; + from = -to; + to = -tmp; + } + } else { + if (parts.length != 3) { + throw new IllegalArgumentException("MIXED_IN range edge partition must be on the form label=val,val,payload"); + } + long value = Long.parseLong(parts[1]); + long payload = Long.parseLong(parts[2]); + if ((payload & 0xc0000000) == 0x80000000L) { + from = value + (payload & 0xffff); + to = value + arity - 1; + } else if ((payload & 0xc0000000) == 0x40000000L) { + from = value; + to = value + (payload & 0xffff); + } else { + from = value + (payload >> 16); + to = value + (payload & 0xffff); + } + } + if (fromInclusive == null || fromInclusive > from) { + fromInclusive = from; + } + if (toInclusive == null || toInclusive > to) { + toInclusive = to; + } + } + return new FeatureRange(key, fromInclusive, toInclusive); + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureSet.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureSet.java new file mode 100644 index 00000000000..be560514995 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/FeatureSet.java @@ -0,0 +1,119 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; +import java.util.Objects; +import java.util.Set; +import java.util.TreeSet; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class FeatureSet extends PredicateValue { + + private Set<String> values; + private String key; + + public FeatureSet(String key, String... values) { + this(key, Arrays.asList(values)); + } + + public FeatureSet(String key, Collection<String> values) { + Objects.requireNonNull(key, "key"); + if (values == null) { + throw new NullPointerException("values"); + } + this.key = key; + this.values = new TreeSet<>(values); + } + + public FeatureSet setKey(String key) { + Objects.requireNonNull(key, "key"); + this.key = key; + return this; + } + + public String getKey() { + return key; + } + + public FeatureSet addValue(String value) { + Objects.requireNonNull(value, "value"); + values.add(value); + return this; + } + + public FeatureSet addValues(Collection<String> values) { + if (values == null) { + throw new NullPointerException("values"); + } + this.values.addAll(values); + return this; + } + + public FeatureSet setValues(Collection<String> values) { + if (values == null) { + throw new NullPointerException("values"); + } + this.values.clear(); + this.values.addAll(values); + return this; + } + + public Set<String> getValues() { + return values; + } + + @Override + public FeatureSet clone() throws CloneNotSupportedException { + FeatureSet obj = (FeatureSet)super.clone(); + obj.values = new TreeSet<>(values); + return obj; + } + + @Override + public int hashCode() { + return (key.hashCode() + values.hashCode()) * 31; + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof FeatureSet)) { + return false; + } + FeatureSet rhs = (FeatureSet)obj; + if (!key.equals(rhs.key)) { + return false; + } + if (!values.equals(rhs.values)) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + appendInAsTo("in", out); + } + + protected void appendNegatedTo(StringBuilder out) { + appendInAsTo("not in", out); + } + + private void appendInAsTo(String in, StringBuilder out) { + appendQuotedTo(key, out); + out.append(' ').append(in).append(" ["); + for (Iterator<String> it = values.iterator(); it.hasNext(); ) { + appendQuotedTo(it.next(), out); + if (it.hasNext()) { + out.append(", "); + } + } + out.append("]"); + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Negation.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Negation.java new file mode 100644 index 00000000000..c5a4cb802ee --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Negation.java @@ -0,0 +1,72 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.List; +import java.util.Objects; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class Negation extends PredicateOperator { + + private Predicate operand; + + public Negation(Predicate operand) { + Objects.requireNonNull(operand, "operand"); + this.operand = operand; + } + + public Negation setOperand(Predicate operand) { + Objects.requireNonNull(operand, "operand"); + this.operand = operand; + return this; + } + + public Predicate getOperand() { + return operand; + } + + @Override + public List<Predicate> getOperands() { + return java.util.Arrays.asList(operand); + } + + @Override + public Negation clone() throws CloneNotSupportedException { + Negation obj = (Negation)super.clone(); + obj.operand = operand.clone(); + return obj; + } + + @Override + public int hashCode() { + return operand.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof Negation)) { + return false; + } + Negation rhs = (Negation)obj; + if (!operand.equals(rhs.operand)) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + if (operand instanceof FeatureSet) { + ((FeatureSet)operand).appendNegatedTo(out); + } else { + out.append("not ("); + operand.appendTo(out); + out.append(')'); + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicate.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicate.java new file mode 100644 index 00000000000..2446d3e3524 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicate.java @@ -0,0 +1,79 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import com.yahoo.document.predicate.parser.PredicateLexer; +import com.yahoo.document.predicate.parser.PredicateParser; +import com.yahoo.text.Ascii; +import org.antlr.runtime.ANTLRStringStream; +import org.antlr.runtime.CommonTokenStream; +import org.antlr.runtime.RecognitionException; + +import java.nio.charset.StandardCharsets; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public abstract class Predicate implements Cloneable { + + private final static char QUOTE_CHAR = '\''; + private final static Ascii.Encoder ASCII_ENCODER = Ascii.newEncoder(StandardCharsets.UTF_8, QUOTE_CHAR); + private final static Ascii.Decoder ASCII_DECODER = Ascii.newDecoder(StandardCharsets.UTF_8); + + @Override + public Predicate clone() throws CloneNotSupportedException { + return (Predicate)super.clone(); + } + + @Override + public final String toString() { + StringBuilder out = new StringBuilder(); + appendTo(out); + return out.toString(); + } + + protected abstract void appendTo(StringBuilder out); + + protected static void appendQuotedTo(String str, StringBuilder out) { + String encoded = asciiEncode(str); + if (requiresQuote(encoded)) { + out.append(QUOTE_CHAR).append(encoded).append(QUOTE_CHAR); + } else { + out.append(str); + } + } + + private static boolean requiresQuote(String str) { + for (int i = 0, len = str.length(); i < len; i = str.offsetByCodePoints(i, 1)) { + int c = str.codePointAt(i); + if (c == Ascii.ESCAPE_CHAR || !Character.isLetterOrDigit(c)) { + return true; + } + } + return false; + } + + public static String asciiEncode(String str) { + return ASCII_ENCODER.encode(str); + } + + public static String asciiDecode(String str) { + return ASCII_DECODER.decode(str); + } + + public static Predicate fromBinary(byte[] buf) { + return BinaryFormat.decode(buf); + } + + public static Predicate fromString(String str) { + ANTLRStringStream input = new ANTLRStringStream(str); + PredicateLexer lexer = new PredicateLexer(input); + CommonTokenStream tokens = new CommonTokenStream(lexer); + PredicateParser parser = new PredicateParser(tokens); + try { + return parser.predicate(); + } catch (RecognitionException e) { + throw new IllegalArgumentException(e); + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateHash.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateHash.java new file mode 100644 index 00000000000..8c0c9ee590e --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateHash.java @@ -0,0 +1,111 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + + +import com.yahoo.text.Utf8; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + * This hash function must match the corresponding C++ hash function in 'ConvertClass', + * currently located at 'rise_platform/src/interface/cpp/api/ConvertClass.h' + */ +public class PredicateHash { + @SuppressWarnings("fallthrough") + public static long hash64(String s) { + byte[] bytes = Utf8.toBytes(s); + long a=0L, b=0L; + long c=0x9e3779b97f4a7c13L; + int len = bytes.length; + int offset = 0; + while (len >= 24) { + c += ((0xffL & (long)bytes[offset + 23]) << 56) + + ((0xffL & (long)bytes[offset + 22]) << 48) + + ((0xffL & (long)bytes[offset + 21]) << 40) + + ((0xffL & (long)bytes[offset + 20]) << 32) + + ((0xffL & (long)bytes[offset + 19]) << 24) + + ((0xffL & (long)bytes[offset + 18]) << 16) + + ((0xffL & (long)bytes[offset + 17]) << 8) + + ((0xffL & (long)bytes[offset + 16])); + + b += ((0xffL & (long)bytes[offset + 15]) << 56) + + ((0xffL & (long)bytes[offset + 14]) << 48) + + ((0xffL & (long)bytes[offset + 13]) << 40) + + ((0xffL & (long)bytes[offset + 12]) << 32) + + ((0xffL & (long)bytes[offset + 11]) << 24) + + ((0xffL & (long)bytes[offset + 10]) << 16) + + ((0xffL & (long)bytes[offset + 9]) << 8) + + ((0xffL & (long)bytes[offset + 8])); + + a += ((0xffL & (long)bytes[offset + 7]) << 56) + + ((0xffL & (long)bytes[offset + 6]) << 48) + + ((0xffL & (long)bytes[offset + 5]) << 40) + + ((0xffL & (long)bytes[offset + 4]) << 32) + + ((0xffL & (long)bytes[offset + 3]) << 24) + + ((0xffL & (long)bytes[offset + 2]) << 16) + + ((0xffL & (long)bytes[offset + 1]) << 8) + + ((0xffL & (long)bytes[offset + 0])); + + // Mix. This arithmetic must match the mix below. + a -= b; a -= c; a ^= (c>>>43); + b -= c; b -= a; b ^= (a<<9); + c -= a; c -= b; c ^= (b>>>8); + a -= b; a -= c; a ^= (c>>>38); + b -= c; b -= a; b ^= (a<<23); + c -= a; c -= b; c ^= (b>>>5); + a -= b; a -= c; a ^= (c>>>35); + b -= c; b -= a; b ^= (a<<49); + c -= a; c -= b; c ^= (b>>>11); + a -= b; a -= c; a ^= (c>>>12); + b -= c; b -= a; b ^= (a<<18); + c -= a; c -= b; c ^= (b>>>22); + // End mix. + + offset += 24; + len -= 24; + } + + c += bytes.length; + switch (len) { + case 23: c+= (0xffL & (long)bytes[offset + 22]) << 56; + case 22: c+= (0xffL & (long)bytes[offset + 21]) << 48; + case 21: c+= (0xffL & (long)bytes[offset + 20]) << 40; + case 20: c+= (0xffL & (long)bytes[offset + 19]) << 32; + case 19: c+= (0xffL & (long)bytes[offset + 18]) << 24; + case 18: c+= (0xffL & (long)bytes[offset + 17]) << 16; + case 17: c+= (0xffL & (long)bytes[offset + 16]) << 8; + // The first byte of c is reserved for the length + case 16: b+= (0xffL & (long)bytes[offset + 15]) << 56; + case 15: b+= (0xffL & (long)bytes[offset + 14]) << 48; + case 14: b+= (0xffL & (long)bytes[offset + 13]) << 40; + case 13: b+= (0xffL & (long)bytes[offset + 12]) << 32; + case 12: b+= (0xffL & (long)bytes[offset + 11]) << 24; + case 11: b+= (0xffL & (long)bytes[offset + 10]) << 16; + case 10: b+= (0xffL & (long)bytes[offset + 9]) << 8; + case 9: b+= (0xffL & (long)bytes[offset + 8]); + case 8: a+= (0xffL & (long)bytes[offset + 7]) << 56; + case 7: a+= (0xffL & (long)bytes[offset + 6]) << 48; + case 6: a+= (0xffL & (long)bytes[offset + 5]) << 40; + case 5: a+= (0xffL & (long)bytes[offset + 4]) << 32; + case 4: a+= (0xffL & (long)bytes[offset + 3]) << 24; + case 3: a+= (0xffL & (long)bytes[offset + 2]) << 16; + case 2: a+= (0xffL & (long)bytes[offset + 1]) << 8; + case 1: a+= (0xffL & (long)bytes[offset + 0]); + } + // Mix. This arithmetic must match the mix above. + a -= b; a -= c; a ^= (c>>>43); + b -= c; b -= a; b ^= (a<<9); + c -= a; c -= b; c ^= (b>>>8); + a -= b; a -= c; a ^= (c>>>38); + b -= c; b -= a; b ^= (a<<23); + c -= a; c -= b; c ^= (b>>>5); + a -= b; a -= c; a ^= (c>>>35); + b -= c; b -= a; b ^= (a<<49); + c -= a; c -= b; c ^= (b>>>11); + a -= b; a -= c; a ^= (c>>>12); + b -= c; b -= a; b ^= (a<<18); + c -= a; c -= b; c ^= (b>>>22); + // End mix. + + return c; + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateOperator.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateOperator.java new file mode 100644 index 00000000000..0c0af37a791 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateOperator.java @@ -0,0 +1,12 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.List; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +abstract public class PredicateOperator extends Predicate { + + public abstract List<Predicate> getOperands(); +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateValue.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateValue.java new file mode 100644 index 00000000000..f34a8f4b268 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/PredicateValue.java @@ -0,0 +1,9 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +abstract class PredicateValue extends Predicate { + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicates.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicates.java new file mode 100644 index 00000000000..7362eb5ba6d --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/Predicates.java @@ -0,0 +1,69 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class Predicates { + + public static Conjunction and(Predicate... operands) { + return new Conjunction(operands); + } + + public static Disjunction or(Predicate... operands) { + return new Disjunction(operands); + } + + public static Negation not(Predicate operand) { + return new Negation(operand); + } + + public static BooleanPredicate value(boolean value) { + return new BooleanPredicate(value); + } + + public static FeatureBuilder feature(String key) { + return new FeatureBuilder(key); + } + + public static class FeatureBuilder { + + private final String key; + + public FeatureBuilder(String key) { + this.key = key; + } + + public FeatureRange lessThan(long toExclusive) { + return new FeatureRange(key, null, toExclusive - 1); + } + + public FeatureRange lessThanOrEqualTo(long toInclusive) { + return new FeatureRange(key, null, toInclusive); + } + + public FeatureRange greaterThan(long fromExclusive) { + return new FeatureRange(key, fromExclusive + 1, null); + } + + public FeatureRange greaterThanOrEqualTo(long fromInclusive) { + return new FeatureRange(key, fromInclusive, null); + } + + public FeatureRange inRange(long fromInclusive, long toInclusive) { + return new FeatureRange(key, fromInclusive, toInclusive); + } + + public Negation notInRange(long fromInclusive, long toInclusive) { + return new Negation(new FeatureRange(key, fromInclusive, toInclusive)); + } + + public FeatureSet inSet(String... values) { + return new FeatureSet(key, values); + } + + public Negation notInSet(String... values) { + return new Negation(new FeatureSet(key, values)); + } + } +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangeEdgePartition.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangeEdgePartition.java new file mode 100644 index 00000000000..0771f0ec08e --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangeEdgePartition.java @@ -0,0 +1,86 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ +public class RangeEdgePartition extends RangePartition { + private final long value; + private final int lowerBound; + private final int upperBound; + + public RangeEdgePartition(String label, long value, int lower, int upper) { + super(label); + this.value = value; + this.lowerBound = lower; + this.upperBound = upper; + } + + public long getValue() { + return value; + } + + public int getLowerBound() { + return lowerBound; + } + + public int getUpperBound() { + return upperBound; + } + + @Override + public RangeEdgePartition clone() throws CloneNotSupportedException { + return (RangeEdgePartition)super.clone(); + } + + @Override + public int hashCode() { + return super.hashCode() + new Long(value).hashCode() + + new Integer(lowerBound).hashCode() + new Integer(upperBound).hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof RangeEdgePartition)) { + return false; + } + RangeEdgePartition other = (RangeEdgePartition)obj; + return super.equals(other) && + value == other.value && + lowerBound == other.lowerBound && + upperBound == other.upperBound; + } + + @Override + protected void appendTo(StringBuilder out) { + super.appendTo(out); + + out.append("+["); + if (lowerBound > 0) + out.append(lowerBound); + out.append(".."); + if (upperBound >= 0) + out.append(upperBound); + out.append(']'); + } + + public long encodeBounds() { + if (lowerBound > 0) { + if (upperBound >= 0) { + return lowerBound << 16 | (upperBound + 1); + } else { + return lowerBound | 0x80000000L; + } + } else { + if (upperBound >= 0) { + return (upperBound + 1) | 0x40000000; + } else { + return 0x80000000L; // >0 + } + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangePartition.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangePartition.java new file mode 100644 index 00000000000..33cdd23c45c --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/RangePartition.java @@ -0,0 +1,67 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +/** + * @author <a href="mailto:magnarn@yahoo-inc.com">Magnar Nedland</a> + */ +public class RangePartition extends PredicateValue { + + private String label; + + public RangePartition(String label) { + this.label = label; + } + + public RangePartition(String key, long fromInclusive, long toInclusive, boolean isNeg) { + this(makeLabel(key, fromInclusive, toInclusive, isNeg)); + } + + private static String makeLabel(String key, long fromInclusive, long toInclusive, boolean isNeg) { + if (isNeg) { + // special case for toInclusive==long_min: It will print its own hyphen. + return key + "=" + (toInclusive==0x8000000000000000L? "" : "-") + toInclusive + "-" + fromInclusive; + } else { + // special case for toInclusive==long_min: It will print its own hyphen. + return key + "=" + fromInclusive + (toInclusive==0x8000000000000000L? "" : "-") + toInclusive; + } + } + + public String getLabel() { + return label; + } + + @Override + public RangePartition clone() throws CloneNotSupportedException { + return (RangePartition)super.clone(); + } + + @Override + public int hashCode() { + return label.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof RangePartition)) { + return false; + } + return label.equals(((RangePartition)obj).getLabel()); + } + + @Override + protected void appendTo(StringBuilder out) { + int i = label.lastIndexOf('='); + appendQuotedTo(label.substring(0, i), out); + if (out.charAt(out.length() - 1) == '\'') { + out.deleteCharAt(out.length() - 1); + out.append(label.substring(i)); + out.append('\''); + } else { + out.append(label.substring(i)); + } + } + +} diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/SimplePredicates.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/SimplePredicates.java new file mode 100644 index 00000000000..1b339767109 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/SimplePredicates.java @@ -0,0 +1,70 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.document.predicate; + +import java.util.ArrayList; +import java.util.List; + +/** + * @author <a href="mailto:simon@yahoo-inc.com">Simon Thoresen Hult</a> + */ +public class SimplePredicates { + + public static Predicate newPredicate() { + return new Predicate() { + + @Override + protected void appendTo(StringBuilder out) { + out.append("<anon>"); + } + + }; + } + + public static Predicate newString(String str) { + return new StringNode(str); + } + + public static List<Predicate> newStrings(String... arr) { + List<Predicate> ret = new ArrayList<>(arr.length); + for (String str : arr) { + ret.add(newString(str)); + } + return ret; + } + + private static class StringNode extends Predicate { + + final String str; + + StringNode(String str) { + this.str = str; + } + + @Override + public int hashCode() { + return str.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (!(obj instanceof StringNode)) { + return false; + } + StringNode rhs = (StringNode)obj; + if (!str.equals(rhs.str)) { + return false; + } + return true; + } + + @Override + protected void appendTo(StringBuilder out) { + out.append(str); + } + + } +} + diff --git a/predicate-search-core/src/main/java/com/yahoo/document/predicate/package-info.java b/predicate-search-core/src/main/java/com/yahoo/document/predicate/package-info.java new file mode 100644 index 00000000000..ef3b6954992 --- /dev/null +++ b/predicate-search-core/src/main/java/com/yahoo/document/predicate/package-info.java @@ -0,0 +1,8 @@ +// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +@com.yahoo.osgi.annotation.ExportPackage +@com.yahoo.api.annotations.PublicApi +/* + The predicate package is exported by the document module (OSGi). + Do not remove unless the intention is to modify the public API of document. + */ +package com.yahoo.document.predicate; |