content: /*
   * Licensed to the Apache Software Foundation (ASF) under one
   * or more contributor license agreements.  See the NOTICE file
   * distributed with this work for additional information
   * regarding copyright ownership.  The ASF licenses this file
   * to you under the Apache License, Version 2.0 (the
   * "License"); you may not use this file except in compliance
   * with the License.  You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.cassandra.index.sasi.plan;
  
  import java.nio.ByteBuffer;
  import java.util.ArrayList;
  import java.util.List;
  import java.util.Objects;
  
  import org.apache.cassandra.schema.ColumnMetadata;
  import org.apache.cassandra.cql3.Operator;
  import org.apache.cassandra.index.sasi.analyzer.AbstractAnalyzer;
  import org.apache.cassandra.index.sasi.conf.ColumnIndex;
  import org.apache.cassandra.index.sasi.disk.OnDiskIndex;
  import org.apache.cassandra.index.sasi.utils.TypeUtil;
  import org.apache.cassandra.db.marshal.AbstractType;
  import org.apache.cassandra.db.marshal.UTF8Type;
  import org.apache.cassandra.utils.ByteBufferUtil;
  import org.apache.cassandra.utils.FBUtilities;
  
  import org.apache.commons.lang3.builder.HashCodeBuilder;
  
  import com.google.common.annotations.VisibleForTesting;
  import com.google.common.collect.Iterators;
  
  import org.slf4j.Logger;
  import org.slf4j.LoggerFactory;
  
  public class Expression
  {
      private static final Logger logger = LoggerFactory.getLogger(Expression.class);
  
      public enum Op
      {
          EQ, MATCH, PREFIX, SUFFIX, CONTAINS, NOT_EQ, RANGE, IN;
  
          public static Op valueOf(Operator operator)
          {
              switch (operator)
              {
                  case EQ:
                      return EQ;
  
                  case IN:
                      return IN;
  
                  case NEQ:
                      return NOT_EQ;
  
                  case LT:
                  case GT:
                  case LTE:
                  case GTE:
                      return RANGE;
  
                  case LIKE_PREFIX:
                      return PREFIX;
  
                  case LIKE_SUFFIX:
                      return SUFFIX;
  
                  case LIKE_CONTAINS:
                      return CONTAINS;
  
                  case LIKE_MATCHES:
                      return MATCH;
  
                  default:
                      throw new IllegalArgumentException("unknown operator: " + operator);
              }
          }
      }
  
      private final QueryController controller;
  
      public final AbstractAnalyzer analyzer;
  
      public final ColumnIndex index;
      public final AbstractType<?> validator;
      public final boolean isLiteral;
  
      @VisibleForTesting
      protected Op operation;
  
      public Bound lower, upper;
      public List<ByteBuffer> exclusions = new ArrayList<>();
  
      public Expression(Expression other)
      {
          this(other.controller, other.index);
          operation = other.operation;
      }
  
      public Expression(QueryController controller, ColumnIndex columnIndex)
      {
          this.controller = controller;
          this.index = columnIndex;
          this.analyzer = columnIndex.getAnalyzer();
          this.validator = columnIndex.getValidator();
          this.isLiteral = columnIndex.isLiteral();
      }
  
      @VisibleForTesting
      public Expression(String name, AbstractType<?> validator)
      {
          this(null, new ColumnIndex(UTF8Type.instance, ColumnMetadata.regularColumn("sasi", "internal", name, validator, ColumnMetadata.NO_UNIQUE_ID), null));
      }
  
      public Expression setLower(Bound newLower)
      {
          lower = newLower == null ? null : new Bound(newLower.value, newLower.inclusive);
          return this;
      }
  
      public Expression setUpper(Bound newUpper)
      {
          upper = newUpper == null ? null : new Bound(newUpper.value, newUpper.inclusive);
          return this;
      }
  
      public Expression setOp(Op op)
      {
          this.operation = op;
          return this;
      }
  
      public Expression add(Operator op, ByteBuffer value)
      {
          boolean lowerInclusive = false, upperInclusive = false;
          switch (op)
          {
              case LIKE_PREFIX:
              case LIKE_SUFFIX:
              case LIKE_CONTAINS:
              case LIKE_MATCHES:
              case EQ:
                  lower = new Bound(value, true);
                  upper = lower;
                  operation = Op.valueOf(op);
                  break;
  
              case NEQ:
                  // index expressions are priority sorted
                  // and NOT_EQ is the lowest priority, which means that operation type
                  // is always going to be set before reaching it in case of RANGE or EQ.
                  if (operation == null)
                  {
                      operation = Op.NOT_EQ;
                      lower = new Bound(value, true);
                      upper = lower;
                  }
                  else
                      exclusions.add(value);
                  break;
  
              case LTE:
                  if (index.getDefinition().isReversedType())
                      lowerInclusive = true;
                  else
                      upperInclusive = true;
              case LT:
                  operation = Op.RANGE;
                  if (index.getDefinition().isReversedType())
                      lower = new Bound(value, lowerInclusive);
                  else
                      upper = new Bound(value, upperInclusive);
                  break;
  
              case GTE:
                  if (index.getDefinition().isReversedType())
                      upperInclusive = true;
                  else
                      lowerInclusive = true;
              case GT:
                  operation = Op.RANGE;
                  if (index.getDefinition().isReversedType())
                      upper = new Bound(value, upperInclusive);
                  else
                      lower = new Bound(value, lowerInclusive);
  
                  break;
          }
  
          return this;
      }
  
      public Expression addExclusion(ByteBuffer value)
      {
          exclusions.add(value);
          return this;
      }
  
      public boolean isSatisfiedBy(ByteBuffer value)
      {
          if (!TypeUtil.isValid(value, validator))
          {
              int size = value.remaining();
              if ((value = TypeUtil.tryUpcast(value, validator)) == null)
              {
                  logger.error("Can't cast value for {} to size accepted by {}, value size is {}.",
                               index.getColumnName(),
                               validator,
                               FBUtilities.prettyPrintMemory(size));
                  return false;
              }
          }
  
          if (lower != null)
          {
              // suffix check
              if (isLiteral)
              {
                  if (!validateStringValue(value, lower.value))
                      return false;
              }
              else
              {
                  // range or (not-)equals - (mainly) for numeric values
                  int cmp = validator.compare(lower.value, value);
  
                  // in case of (NOT_)EQ lower == upper
                  if (operation == Op.EQ || operation == Op.NOT_EQ)
                      return cmp == 0;
  
                  if (cmp > 0 || (cmp == 0 && !lower.inclusive))
                      return false;
              }
          }
  
          if (upper != null && lower != upper)
          {
              // string (prefix or suffix) check
              if (isLiteral)
              {
                  if (!validateStringValue(value, upper.value))
                      return false;
              }
              else
              {
                  // range - mainly for numeric values
                  int cmp = validator.compare(upper.value, value);
                  if (cmp < 0 || (cmp == 0 && !upper.inclusive))
                      return false;
              }
          }
  
          // as a last step let's check exclusions for the given field,
          // this covers EQ/RANGE with exclusions.
          for (ByteBuffer term : exclusions)
          {
              if (isLiteral && validateStringValue(value, term))
                  return false;
              else if (validator.compare(term, value) == 0)
                  return false;
          }
  
          return true;
      }
  
      private boolean validateStringValue(ByteBuffer columnValue, ByteBuffer requestedValue)
      {
          analyzer.reset(columnValue.duplicate());
          while (analyzer.hasNext())
          {
              ByteBuffer term = analyzer.next();
  
              boolean isMatch = false;
              switch (operation)
              {
                  case EQ:
                  case MATCH:
                  // Operation.isSatisfiedBy handles conclusion on !=,
                  // here we just need to make sure that term matched it
                  case NOT_EQ:
                      isMatch = validator.compare(term, requestedValue) == 0;
                      break;
  
                  case PREFIX:
                      isMatch = ByteBufferUtil.startsWith(term, requestedValue);
                      break;
  
                  case SUFFIX:
                      isMatch = ByteBufferUtil.endsWith(term, requestedValue);
                      break;
  
                  case CONTAINS:
                      isMatch = ByteBufferUtil.contains(term, requestedValue);
                      break;
              }
  
              if (isMatch)
                  return true;
          }
  
          return false;
      }
  
      public Op getOp()
      {
          return operation;
      }
  
      public void checkpoint()
      {
          if (controller == null)
              return;
  
          controller.checkpoint();
      }
  
      public boolean hasLower()
      {
          return lower != null;
      }
  
      public boolean hasUpper()
      {
          return upper != null;
      }
  
      public boolean isLowerSatisfiedBy(OnDiskIndex.DataTerm term)
      {
          if (!hasLower())
              return true;
  
          int cmp = term.compareTo(validator, lower.value, operation == Op.RANGE && !isLiteral);
          return cmp > 0 || cmp == 0 && lower.inclusive;
      }
  
      public boolean isUpperSatisfiedBy(OnDiskIndex.DataTerm term)
      {
          if (!hasUpper())
              return true;
  
          int cmp = term.compareTo(validator, upper.value, operation == Op.RANGE && !isLiteral);
          return cmp < 0 || cmp == 0 && upper.inclusive;
      }
  
      public boolean isIndexed()
      {
          return index.isIndexed();
      }
  
      public String toString()
      {
          return String.format("Expression{name: %s, op: %s, lower: (%s, %s), upper: (%s, %s), exclusions: %s}",
                               index.getColumnName(),
                               operation,
                               lower == null ? "null" : validator.getString(lower.value),
                               lower != null && lower.inclusive,
                               upper == null ? "null" : validator.getString(upper.value),
                               upper != null && upper.inclusive,
                               Iterators.toString(Iterators.transform(exclusions.iterator(), validator::getString)));
      }
  
      public int hashCode()
      {
          return new HashCodeBuilder().append(index.getColumnName())
                                      .append(operation)
                                      .append(validator)
                                      .append(lower).append(upper)
                                      .append(exclusions).build();
      }
  
      public boolean equals(Object other)
      {
          if (!(other instanceof Expression))
              return false;
  
          if (this == other)
              return true;
  
          Expression o = (Expression) other;
  
          return Objects.equals(index.getColumnName(), o.index.getColumnName())
                  && validator.equals(o.validator)
                  && operation == o.operation
                  && Objects.equals(lower, o.lower)
                  && Objects.equals(upper, o.upper)
                  && exclusions.equals(o.exclusions);
      }
  
      public static class Bound
      {
          public final ByteBuffer value;
          public final boolean inclusive;
  
          public Bound(ByteBuffer value, boolean inclusive)
          {
              this.value = value;
              this.inclusive = inclusive;
          }
  
          public boolean equals(Object other)
          {
              if (!(other instanceof Bound))
                  return false;
  
              Bound o = (Bound) other;
              return value.equals(o.value) && inclusive == o.inclusive;
          }
  
          public int hashCode()
          {
              HashCodeBuilder builder = new HashCodeBuilder();
              builder.append(value);
              builder.append(inclusive);
              return builder.toHashCode();
          }
      }
  }
  