content: /*
   * Copyright 2007-2019 Amazon.com, Inc. or its affiliates. All Rights Reserved.
   *
   * Licensed under the Apache License, Version 2.0 (the "License").
   * You may not use this file except in compliance with the License.
   * A copy of the License is located at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * or in the "license" file accompanying this file. This file 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 com.amazon.ion.util;
  
  import static com.amazon.ion.impl._Private_IonConstants.UNKNOWN_SYMBOL_TEXT_PREFIX;
  
  import com.amazon.ion.Decimal;
  import com.amazon.ion.IonBool;
  import com.amazon.ion.IonDecimal;
  import com.amazon.ion.IonException;
  import com.amazon.ion.IonFloat;
  import com.amazon.ion.IonInt;
  import com.amazon.ion.IonLob;
  import com.amazon.ion.IonSequence;
  import com.amazon.ion.IonStruct;
  import com.amazon.ion.IonSymbol;
  import com.amazon.ion.IonText;
  import com.amazon.ion.IonTimestamp;
  import com.amazon.ion.IonType;
  import com.amazon.ion.IonValue;
  import com.amazon.ion.SymbolToken;
  import java.io.IOException;
  import java.io.InputStream;
  import java.util.HashMap;
  import java.util.Iterator;
  import java.util.Map;
  import java.util.Set;
  
  /**
   * Provides equivalence comparisons between two {@link IonValue}s, following
   * the contract of {@link IonValue#equals(Object)}.
   *
   * <p>
   * Basic usage of this class is as follows:
   *
   *<pre>
   *    IonValue v1 = ...;
   *    IonValue v2 = ...;
   *    com.amazon.ion.util.Equivalence.ionEquals( v1, v2 );
   *</pre>
   *
   * More likely, a static import would make using this class easier.
   *
   *<pre>
   *    import static com.amazon.ion.util.Equivalence.ionEquals;
   *    ...
   *    boolean equivalent = ionEquals( v1, v2 );
   *</pre>
   *
   * <p>
   * Additional options are available by configuring an <code>Equivalence</code>
   * instance using {@link Equivalence.Builder}. For example:
   *
   * <pre>
   *     com.amazon.ion.util.Equivalence equivalence =
   *         new com.amazon.ion.util.Equivalence.Builder()
   *             .withEpsilon(1e-6)
   *             .build();
   *     IonValue v1 = ...;
   *     IonValue v2 = ...;
   *     equivalence.ionValueEquals( v1, v2 );
   * </pre>
   *
   * <p>
   * <h3>Ion Equivalence</h3>
   * In order to make Ion a useful model to describe data, we must first define
   * the notion of equivalence for all values representable in Ion. Equivalence
   * with respect to Ion values means that if two Ion values, X and Y, are
   * equivalent, they represent the same data and can be substituted for the other
   * without loss of information.
   *
   * This relationship is:
   * <ul>
   *   <li>
   *     symmetric: X is equivalent to Y if and only if Y is equivalent to X.
   *   </li>
   *   <li>
   *     transitive: if X is equivalent to Y and Y is equivalent to Z, then X is
   *     equivalent to Z.
   *   </li>
   *   <li>
   *     reflexive: X is equivalent to X.
   *   </li>
   * </ul>
   *
   * <h4>Ordered Sequence Equivalence</h4>
   * When an ordered sequence (i.e. tuple) of elements is specified in this
   * document, equivalence over such an ordered sequence is defined as follows.
   *
   * A tuple, A = (a1, a2, ..., an), is equivalent to another tuple, B = (b1, b2,
   * ..., bm) if and only if the cardinality (number of elements) of A equals the
   * cardinality of B (i.e. n == m) and ai is equivalent to bi for i = 1 ... n.
   *
   * <h4>Un-Ordered Sequence Equivalence</h4>
   * When an un-ordered sequence (i.e. bag or multi-set) is specified in this
   * document, equivalence over such a sequence is defined as follows.
   *
   * A bag, A = {a1, a2, ..., an} is equivalent to B = {b1, b2, ..., bm} if and
   * only if the cardinality of A is equal to the cardinality of B and for each
   * element, x, in A there exists a distinct element, y, in B for which x is
   * equivalent to y.
   *
   * <h4>Values</h4>
   * Any arbitrary, atomic value in the Ion Language can be denoted as the tuple,
   * (A, V), where A is an ordered list of annotations, and V is an Ion Primitive
   * Data or Ion Complex Data value. The list of annotations, A is an tuple of Ion
   * Symbols (a specific type of Ion Primitive).
   *
   * <p>
   * <h3>Terminology</h3>
   * Within this class, <i>strict</i> equivalence refers to Ion data model
   * equivalence as defined above and by the
   * <a href="https://amazon-ion.github.io/ion-docs/docs/spec.html">Ion
   * Specification</a>. <i>Structural</i> or <i>non-strict</i> equivalence
   * follows the same rules as strict equivalence, except that
   * <ul>
   *   <li>Annotations are not considered, and</li>
   *   <li>Timestamps that represent the same instant in time are always
   *   considered equivalent.</li>
   * </ul>
   */
  public final class Equivalence {
  
      /**
       * TODO amazon-ion/ion-java/issues/26 Marker for code that needs to be altered in order to
       * support a public comparison API to determine ordering of values, not
       * just equality.
       */
      private static final boolean PUBLIC_COMPARISON_API = false;
  
      /**
       * Configuration that requires strict data equivalence.
       * @see #ionEquals(IonValue, IonValue)
       */
      private static final Configuration STRICT_CONFIGURATION = new Configuration(new Builder().withStrict(true));
  
      /**
       * Configuration that requires structural equivalence without considering annotations.
       * @see #ionEqualsByContent(IonValue, IonValue)
       */
      private static final Configuration NON_STRICT_CONFIGURATION = new Configuration(new Builder().withStrict(false));
  
      /**
       * Contains the configuration to use when comparing Ion values.
       */
      static final class Configuration {
          private final boolean isStrict;
          private final Double epsilon;
          private final int maxComparisonDepth;
  
          Configuration(Builder builder) {
              this.isStrict = builder.isStrict;
              this.epsilon = builder.epsilon;
              this.maxComparisonDepth = builder.maxComparisonDepth;
          }
      }
  
      /**
       * Constructs {@link Equivalence} instances. To compare IonValues using an
       * Equivalence instance's configuration, call {@link #ionValueEquals(IonValue, IonValue)}
       * on that instance rather than calling {@link IonValue#equals(Object)}.
       */
      public static final class Builder {
  
          private boolean isStrict = true;
          private Double epsilon = null;
          private int maxComparisonDepth = 1000;
  
          /**
           * When true, checks for strict data equivalence over two Ion Values.
           * When false, checks for structural data equivalence over two Ion
           * Values. See {@link Equivalence} for discussion of the differences
           * between the two.
           * Default: true.
           * @param isStrict the value.
           * @return this builder.
           */
          public Builder withStrict(boolean isStrict) {
              this.isStrict = isStrict;
              return this;
          }
  
          /**
           * The maximum absolute difference between two Ion float values for
           * which the two values will be considered equivalent. Default: Ion
           * float values will only be considered equivalent when
           * <code>Double.compare(a, b) == 0</code>.
           * @param epsilon the value.
           * @return this builder.
           */
          public Builder withEpsilon(double epsilon) {
              this.epsilon = epsilon;
              return this;
          }
  
          /**
           * The maximum depth to which two values will be compared. If the two
           * values to be compared are still potentially equivalent beyond this
           * depth, {@link Equivalence#ionValueEquals(IonValue, IonValue)} will
           * throw an {@link IonException}.
           * @param maxComparisonDepth the value.
           * @return this builder.
           */
          public Builder withMaxComparisonDepth(int maxComparisonDepth) {
              if (maxComparisonDepth < 0) {
                  throw new IllegalArgumentException("Max comparison depth must not be negative.");
              }
              this.maxComparisonDepth = maxComparisonDepth;
              return this;
          }
  
          /**
           * @return a new Equivalence using this builder's configuration.
           */
          public Equivalence build() {
              return new Equivalence(new Configuration(this));
          }
      }
  
      private final Configuration configuration;
  
      private Equivalence(Configuration configuration) {
          this.configuration = configuration;
      }
  
  
      private static int compareAnnotations(SymbolToken[] ann1,
                                            SymbolToken[] ann2)
      {
          int len = ann1.length;
          int result = len - ann2.length;
  
          if (result == 0) {
              for (int i=0; (result == 0) && (i < len); i++) {
                  result = compareSymbolTokens(ann1[i], ann2[i]);
              }
          }
  
          return result;
      }
  
  
      private static int compareSymbolTokens(SymbolToken tok1,
                                             SymbolToken tok2)
      {
          String text1 = tok1.getText();
          String text2 = tok2.getText();
          if (text1 == null || text2 == null) {
              if (text1 != null) return  1;
              if (text2 != null) return -1;
  
              int sid1 = tok1.getSid();
              int sid2 = tok2.getSid();
              if (sid1 < sid2) return -1;
              if (sid1 > sid2) return  1;
              return 0;
          }
  
          return text1.compareTo(text2);
      }
  
  
      /**
       * Converts an IonStruct to a multi-set for use in IonStruct equality
       * checks. This method returns the multi-set as a {@code Map<Field, Field>}.
       * <p>
       * A multi-set supports order-independent equality, and may have duplicate
       * elements.
       * <p>
       * Take special note that {@link Set} is missing a {@code get()} API,
       * and cannot contain duplicate elements, hence we cannot use it.
       */
      private static final Map<Field, Field>
          convertToMultiSet(final IonStruct struct, final Configuration configuration, final int depth) {
  
          final Map<Field, Field> structMultiSet =
              new HashMap<Field, Field>();
  
          for (final IonValue val : struct) {
              final Field item = new Field(val, configuration, depth);
              Field curr = structMultiSet.put(item, item);
              // curr will be non-null if the multi-set already contains the
              // name/value pair
              if (curr != null) {
                  // Set the 'occurrences' of the Field that is contained in
                  // the multi-set (i.e. item) to that of the previously mapped
                  // Field (i.e. curr)
                  item.occurrences = curr.occurrences;
              }
              // At this point, item will be an existing
              // name/value pair in the multi-set - increment its occurrence
              item.occurrences++;
          }
  
          return structMultiSet;
      }
  
  
      private static int compareStructs(final IonStruct s1,
                                        final IonStruct s2,
                                        final Configuration configuration,
                                        final int depth)
      {
          int result = s1.size() - s2.size();
          if (result == 0) {
              // We convert IonStruct s1 to a multi-set (which is a
              // Map<Field, Field>). Refer to convertToMultiSet()'s
              // documentation for more info
              final Map<Field, Field> s1MultiSet
                      = convertToMultiSet(s1, configuration, depth);
  
              // Iterates through each name/value pair in IonStruct s2 and
              // determine if it also occurs in s1MultiSet.
              // During each iteration:
              //          If it does, remove an occurrence from s1MultiSet
              //          If it doesn't, the two IonStructs aren't equal
              for (IonValue val : s2) {
                  Field field = new Field(val, configuration, depth);
  
                  // Find an occurrence of the name/value pair in s1MultiSet
                  Field mappedValue = s1MultiSet.get(field);
  
                  if (mappedValue == null || mappedValue.occurrences == 0) {
                      // No match in occurrences, the IonStructs aren't equal
                      return -1;
                  }
  
                  // Remove an occurrence by decrementing count instead of
                  // explicitly calling Map.remove(), as Map.remove() is a slower
                  // operation
                  mappedValue.occurrences--;
              }
          }
          return result;
      }
  
  
      private static int compareSequences(final IonSequence s1,
                                          final IonSequence s2,
                                          final Configuration configuration,
                                          final int depth)
      {
          int result = s1.size() - s2.size();
          if (result == 0) {
              Iterator<IonValue> iter1 = s1.iterator();
              Iterator<IonValue> iter2 = s2.iterator();
              while (iter1.hasNext()) {
                  result = ionCompareToImpl(iter1.next(),
                                            iter2.next(),
                                            configuration,
                                            depth);
                  if (result != 0) {
                      break;
                  }
              }
          }
          return result;
      }
  
  
      /** Compare LOB content by stream--assuming non-null. */
      private static int compareLobContents(final IonLob lob1, final IonLob lob2)
      {
          int in1 = lob1.byteSize();
          int in2 = lob2.byteSize();
          int result = (in1- in2);
  
          if (result == 0) {
              final InputStream stream1 = lob1.newInputStream();
              final InputStream stream2 = lob2.newInputStream();
  
              // too bad Java doesn't do RAII with better syntax...
              try {
                try {
                  try {
                    while (result == 0) {
                        in1 = stream1.read();
                        in2 = stream2.read();
                        if (in1 == -1 || in2 == -1) {
                          if (in1 != -1) result = 1;
                          if (in2 != -1) result = -1;
                          break;
                        }
                        result = (in1 - in2);
                    }
                  } finally {
                    stream1.close();
                  }
                } finally {
                  stream2.close();
                }
              } catch (final IOException e) {
                  // XXX hopefully won't happen with LOB streams--if it does rethrow unchecked.
                  //     this would violate Object.equals() would it not?
                  throw new IonException(e);
              }
          }
  
          return result;
      }
  
      /**
       * Class that denotes a name/value pair in Structs.
       * <p>
       * Structs are unordered collections of name/value pairs. The names are
       * symbol tokens, and the values are unrestricted. Each name/value pair is
       * called a <em>field</em>.
       * <p>
       * The responsibilities of this class is to expose a
       * {@code Map<Field, Field>} as a multi-set. A Field instance holds the name
       * and value of a Struct field, and counts the number of times that
       * name/value pair occurs within the multi-set.
       * <p>
       * For example, an IonStruct:
       *<pre>
       *  {
       *    a : 123,
       *    a : 123
       *  }
       *</pre>
       * will be converted into a multi-set {@code Map<Field, Field>} with
       * a single {@code Field} -> {@code Field} with {@code occurrences} of 2.
       * <p>
       * Refer to
       * {@link Equivalence#convertToMultiSet(IonStruct, Configuration, int)} and
       * {@link Field#equals(Object)} for more info.
       * <p>
       * NOTE: This class should only be instantiated for the sole purpose of
       * using it as either a <em>key</em> or <em>value</em> in a {@link Map}.
       */
      static class Field {
          private final String    name; // aka field name
          private final IonValue  value;
          private final Configuration configuration;
          private final int depth;
  
          /**
           * Number of times that this specific field (with the same name
           * and value) occurs within the struct.
           */
          private int occurrences;
  
          Field(final IonValue value, final Configuration configuration, final int depth)
          {
              SymbolToken tok = value.getFieldNameSymbol();
              String name = tok.getText();
              if (name == null) {
                  // TODO amazon-ion/ion-java/issues/23 Problematic with unknown field names.
                  name = UNKNOWN_SYMBOL_TEXT_PREFIX + tok.getSid();
              }
              this.name = name;
              this.value = value;
              this.configuration = configuration;
              this.depth = depth;
  
              // Occurrences of this name/value pair is 0 initially
              this.occurrences = 0;
          }
  
          @Override
          public int hashCode() {
              return name.hashCode();
              // TODO amazon-ion/ion-java/issues/58 : implement hash code such that it respects
              // 'strict'. The prevously attempted fix is commented out below but
              // is not sufficient because value.hasCode will always include
              // type annotations in the hash computation. Type annotations
              // should not be part of the hash computation if strict=true.
  //            result = (31 * result) + value.hashCode();
  //            return result;
          }
  
          /**
           * This method is implicitly called by {@link Map#get(Object)} to
           * obtain a value to which {@code other} is mapped.
           */
          @Override
          public boolean equals(final Object other) {
              // We can assume other is always a Field and strict
              // is the same - internal usage dictates it.
              final Field sOther = (Field) other;
  
              return name.equals(sOther.name)
                  && ionEqualsImpl(value, ((Field) other).value, configuration, depth);
          }
      }
  
      private static boolean ionEqualsImpl(final IonValue v1,
                                           final IonValue v2,
                                           final Configuration configuration,
                                           final int depth)
      {
          return (ionCompareToImpl(v1, v2, configuration, depth) == 0);
      }
  
      private static int ionCompareToImpl(final IonValue v1,
                                          final IonValue v2,
                                          final Configuration configuration,
                                          final int depth)
      {
          int result = 0;
  
          if (v1 == null || v2 == null) {
              if (v1 != null) result = 1;
              if (v2 != null) result = -1;
              // otherwise v1 == v2 == null and result == 0
              return result;
          }
  
          // check type
          IonType ty1 = v1.getType();
          IonType ty2 = v2.getType();
          result = ty1.compareTo(ty2);
  
          if (result == 0) {
              boolean bo1 = v1.isNullValue();
              boolean bo2 = v2.isNullValue();
  
              if (bo1 || bo2) {
                   // null combination case--we already know they are
                   // the same type
                  if (!bo1) result = 1;
                  if (!bo2) result = -1;
                  // othersize they're equal (and null values)
              }
              else {
                  // value compare only if both are not null
                  switch (ty1)
                  {
                  case NULL:
                      // never visited, precondition is that both are not null
                      break;
                  case BOOL:
                      if (((IonBool) v1).booleanValue()) {
                          result = ((IonBool) v2).booleanValue() ? 0 : 1;
                      }
                      else {
                          result = ((IonBool) v2).booleanValue() ? -1 : 0;
                      }
                      break;
                  case INT:
                      result = ((IonInt) v1).bigIntegerValue().compareTo(
                               ((IonInt) v2).bigIntegerValue());
                      break;
                  case FLOAT:
                      double double1 = ((IonFloat) v1).doubleValue();
                      double double2 = ((IonFloat) v2).doubleValue();
                      if (configuration.epsilon != null
                              && (double1 == double2 || Math.abs(double1 - double2) <= configuration.epsilon)) {
                          result = 0;
                      } else {
                          result = Double.compare(double1, double2);
                      }
                      break;
                  case DECIMAL:
                      assert !PUBLIC_COMPARISON_API; // TODO amazon-ion/ion-java/issues/26
                      result = Decimal.equals(((IonDecimal) v1).decimalValue(),
                                              ((IonDecimal) v2).decimalValue())
                                              ? 0 : 1;
                      break;
                  case TIMESTAMP:
                      if (configuration.isStrict) {
                          assert !PUBLIC_COMPARISON_API; // TODO amazon-ion/ion-java/issues/26
                          result = (((IonTimestamp) v1).timestampValue().equals(
                                    ((IonTimestamp) v2).timestampValue())
                                    ? 0 : 1);
                      }
                      else {
                          // This is kind of lying here, the 'strict' boolean
                          // (if false) denotes ONLY that annotations are not
                          // check for equality. But what this is doing here is
                          // that it is also ignoring IonTimesamps' precision and
                          // local offset.
                          result = ((IonTimestamp) v1).timestampValue().compareTo(
                                   ((IonTimestamp) v2).timestampValue());
                      }
                      break;
                  case STRING:
                      result = (((IonText) v1).stringValue()).compareTo(
                                ((IonText) v2).stringValue());
                      break;
                  case SYMBOL:
                      result = compareSymbolTokens(((IonSymbol) v1).symbolValue(),
                                                   ((IonSymbol) v2).symbolValue());
                      break;
                  case BLOB:
                  case CLOB:
                      result = compareLobContents((IonLob) v1, (IonLob) v2);
                      break;
                  case STRUCT:
                      assert !PUBLIC_COMPARISON_API; // TODO amazon-ion/ion-java/issues/26
                      if (depth >= configuration.maxComparisonDepth) {
                          throw new IonException("Cannot continue comparison: maximum comparison depth exceeded. This limit may be raised using Equivalence.Builder.");
                      }
                      result = compareStructs((IonStruct) v1,
                                              (IonStruct) v2,
                                              configuration,
                                              depth + 1);
                      break;
                  case LIST:
                  case SEXP:
                  case DATAGRAM:
                      if (depth >= configuration.maxComparisonDepth) {
                          throw new IonException("Cannot continue comparison: maximum comparison depth exceeded. This limit may be raised using Equivalence.Builder.");
                      }
                      result = compareSequences((IonSequence) v1,
                                                (IonSequence) v2,
                                                configuration,
                                                depth + 1);
                      break;
                  }
              }
          }
  
          // if the values are otherwise equal, but the caller wants strict
          // comparison, then we check the annotations
          if ((result == 0) && configuration.isStrict) {
              // check tuple equality over the annotations
              // (which are symbol tokens)
              result = compareAnnotations(v1.getTypeAnnotationSymbols(),
                                          v2.getTypeAnnotationSymbols());
          }
  
          return result;
      }
  
      /**
       * Checks for strict data equivalence over two Ion Values.
       *
       * @param v1
       *            The first Ion value to compare.
       * @param v2
       *            The second Ion value to compare.
       *
       * @return true if two Ion Values represent the same data.
       */
      public static boolean ionEquals(final IonValue v1,
                                      final IonValue v2)
      {
          return ionEqualsImpl(v1, v2, STRICT_CONFIGURATION, 0);
      }
  
      /**
       * Checks for structural data equivalence over two Ion Values. That is,
       * equivalence without considering any annotations.
       *
       * @param v1
       *            The first Ion value to compare.
       * @param v2
       *            The second Ion value to compare.
       *
       * @return true if two Ion Values represent the same data without regard to
       *         annotations.
       */
      public static boolean ionEqualsByContent(final IonValue v1,
                                               final IonValue v2)
      {
          return ionEqualsImpl(v1, v2, NON_STRICT_CONFIGURATION, 0);
      }
  
      /**
       * Checks for data equivalence over two Ion values using this Equivalence's
       * configuration
       *
       * @see Builder
       *
       * @param v1
       *            The first Ion value to compare.
       * @param v2
       *            The second Ion value to compare.
       *
       * @return true if two Ion Values represent the same data.
       */
      public boolean ionValueEquals(final IonValue v1, final IonValue v2) {
          return ionEqualsImpl(v1, v2, configuration, 0);
      }
  
  }
  