001/*
002 * Copyright (C) 2010 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.base;
016
017import static com.google.common.base.Preconditions.checkNotNull;
018
019import com.google.common.annotations.GwtCompatible;
020import com.google.errorprone.annotations.ForOverride;
021import java.io.Serializable;
022import java.util.function.BiPredicate;
023import javax.annotation.CheckForNull;
024import org.checkerframework.checker.nullness.qual.NonNull;
025import org.checkerframework.checker.nullness.qual.Nullable;
026
027/**
028 * A strategy for determining whether two instances are considered equivalent, and for computing
029 * hash codes in a manner consistent with that equivalence. Two examples of equivalences are the
030 * {@linkplain #identity() identity equivalence} and the {@linkplain #equals "equals" equivalence}.
031 *
032 * @author Bob Lee
033 * @author Ben Yu
034 * @author Gregory Kick
035 * @since 10.0 (<a href="https://github.com/google/guava/wiki/Compatibility">mostly
036 *     source-compatible</a> since 4.0)
037 */
038@GwtCompatible
039@ElementTypesAreNonnullByDefault
040/*
041 * The type parameter is <T> rather than <T extends @Nullable> so that we can use T in the
042 * doEquivalent and doHash methods to indicate that the parameter cannot be null.
043 */
044public abstract class Equivalence<T> implements BiPredicate<@Nullable T, @Nullable T> {
045  /** Constructor for use by subclasses. */
046  protected Equivalence() {}
047
048  /**
049   * Returns {@code true} if the given objects are considered equivalent.
050   *
051   * <p>This method describes an <i>equivalence relation</i> on object references, meaning that for
052   * all references {@code x}, {@code y}, and {@code z} (any of which may be null):
053   *
054   * <ul>
055   *   <li>{@code equivalent(x, x)} is true (<i>reflexive</i> property)
056   *   <li>{@code equivalent(x, y)} and {@code equivalent(y, x)} each return the same result
057   *       (<i>symmetric</i> property)
058   *   <li>If {@code equivalent(x, y)} and {@code equivalent(y, z)} are both true, then {@code
059   *       equivalent(x, z)} is also true (<i>transitive</i> property)
060   * </ul>
061   *
062   * <p>Note that all calls to {@code equivalent(x, y)} are expected to return the same result as
063   * long as neither {@code x} nor {@code y} is modified.
064   */
065  public final boolean equivalent(@CheckForNull T a, @CheckForNull T b) {
066    if (a == b) {
067      return true;
068    }
069    if (a == null || b == null) {
070      return false;
071    }
072    return doEquivalent(a, b);
073  }
074
075  /**
076   * @deprecated Provided only to satisfy the {@link BiPredicate} interface; use {@link #equivalent}
077   *     instead.
078   * @since 21.0
079   */
080  @Deprecated
081  @Override
082  public final boolean test(@CheckForNull T t, @CheckForNull T u) {
083    return equivalent(t, u);
084  }
085
086  /**
087   * Implemented by the user to determine whether {@code a} and {@code b} are considered equivalent,
088   * subject to the requirements specified in {@link #equivalent}.
089   *
090   * <p>This method should not be called except by {@link #equivalent}. When {@link #equivalent}
091   * calls this method, {@code a} and {@code b} are guaranteed to be distinct, non-null instances.
092   *
093   * @since 10.0 (previously, subclasses would override equivalent())
094   */
095  @ForOverride
096  protected abstract boolean doEquivalent(T a, T b);
097
098  /**
099   * Returns a hash code for {@code t}.
100   *
101   * <p>The {@code hash} has the following properties:
102   *
103   * <ul>
104   *   <li>It is <i>consistent</i>: for any reference {@code x}, multiple invocations of {@code
105   *       hash(x}} consistently return the same value provided {@code x} remains unchanged
106   *       according to the definition of the equivalence. The hash need not remain consistent from
107   *       one execution of an application to another execution of the same application.
108   *   <li>It is <i>distributable across equivalence</i>: for any references {@code x} and {@code
109   *       y}, if {@code equivalent(x, y)}, then {@code hash(x) == hash(y)}. It is <i>not</i>
110   *       necessary that the hash be distributable across <i>inequivalence</i>. If {@code
111   *       equivalence(x, y)} is false, {@code hash(x) == hash(y)} may still be true.
112   *   <li>{@code hash(null)} is {@code 0}.
113   * </ul>
114   */
115  public final int hash(@CheckForNull T t) {
116    if (t == null) {
117      return 0;
118    }
119    return doHash(t);
120  }
121
122  /**
123   * Implemented by the user to return a hash code for {@code t}, subject to the requirements
124   * specified in {@link #hash}.
125   *
126   * <p>This method should not be called except by {@link #hash}. When {@link #hash} calls this
127   * method, {@code t} is guaranteed to be non-null.
128   *
129   * @since 10.0 (previously, subclasses would override hash())
130   */
131  @ForOverride
132  protected abstract int doHash(T t);
133
134  /**
135   * Returns a new equivalence relation for {@code F} which evaluates equivalence by first applying
136   * {@code function} to the argument, then evaluating using {@code this}. That is, for any pair of
137   * non-null objects {@code x} and {@code y}, {@code equivalence.onResultOf(function).equivalent(a,
138   * b)} is true if and only if {@code equivalence.equivalent(function.apply(a), function.apply(b))}
139   * is true.
140   *
141   * <p>For example:
142   *
143   * <pre>{@code
144   * Equivalence<Person> SAME_AGE = Equivalence.equals().onResultOf(GET_PERSON_AGE);
145   * }</pre>
146   *
147   * <p>{@code function} will never be invoked with a null value.
148   *
149   * <p>Note that {@code function} must be consistent according to {@code this} equivalence
150   * relation. That is, invoking {@link Function#apply} multiple times for a given value must return
151   * equivalent results. For example, {@code
152   * Equivalence.identity().onResultOf(Functions.toStringFunction())} is broken because it's not
153   * guaranteed that {@link Object#toString}) always returns the same string instance.
154   *
155   * @since 10.0
156   */
157  public final <F> Equivalence<F> onResultOf(Function<? super F, ? extends @Nullable T> function) {
158    return new FunctionalEquivalence<>(function, this);
159  }
160
161  /**
162   * Returns a wrapper of {@code reference} that implements {@link Wrapper#equals(Object)
163   * Object.equals()} such that {@code wrap(a).equals(wrap(b))} if and only if {@code equivalent(a,
164   * b)}.
165   *
166   * <p>The returned object is serializable if both this {@code Equivalence} and {@code reference}
167   * are serializable (including when {@code reference} is null).
168   *
169   * @since 10.0
170   */
171  public final <S extends @Nullable T> Wrapper<S> wrap(@ParametricNullness S reference) {
172    Wrapper<S> w = new Wrapper<>(this, reference);
173    return w;
174  }
175
176  /**
177   * Wraps an object so that {@link #equals(Object)} and {@link #hashCode()} delegate to an {@link
178   * Equivalence}.
179   *
180   * <p>For example, given an {@link Equivalence} for {@link String strings} named {@code equiv}
181   * that tests equivalence using their lengths:
182   *
183   * <pre>{@code
184   * equiv.wrap("a").equals(equiv.wrap("b")) // true
185   * equiv.wrap("a").equals(equiv.wrap("hello")) // false
186   * }</pre>
187   *
188   * <p>Note in particular that an equivalence wrapper is never equal to the object it wraps.
189   *
190   * <pre>{@code
191   * equiv.wrap(obj).equals(obj) // always false
192   * }</pre>
193   *
194   * @since 10.0
195   */
196  public static final class Wrapper<T extends @Nullable Object> implements Serializable {
197    /*
198     * Equivalence's type argument is always non-nullable: Equivalence<Number>, never
199     * Equivalence<@Nullable Number>. That can still produce wrappers of various types --
200     * Wrapper<Number>, Wrapper<Integer>, Wrapper<@Nullable Integer>, etc. If we used just
201     * Equivalence<? super T> below, no type could satisfy both that bound and T's own
202     * bound. With this type, they have some overlap: in our example, Equivalence<Number>
203     * and Equivalence<Object>.
204     */
205    private final Equivalence<? super @NonNull T> equivalence;
206
207    @ParametricNullness private final T reference;
208
209    private Wrapper(Equivalence<? super @NonNull T> equivalence, @ParametricNullness T reference) {
210      this.equivalence = checkNotNull(equivalence);
211      this.reference = reference;
212    }
213
214    /** Returns the (possibly null) reference wrapped by this instance. */
215    @ParametricNullness
216    public T get() {
217      return reference;
218    }
219
220    /**
221     * Returns {@code true} if {@link Equivalence#equivalent(Object, Object)} applied to the wrapped
222     * references is {@code true} and both wrappers use the {@link Object#equals(Object) same}
223     * equivalence.
224     */
225    @Override
226    public boolean equals(@CheckForNull Object obj) {
227      if (obj == this) {
228        return true;
229      }
230      if (obj instanceof Wrapper) {
231        Wrapper<?> that = (Wrapper<?>) obj; // note: not necessarily a Wrapper<T>
232
233        if (this.equivalence.equals(that.equivalence)) {
234          /*
235           * We'll accept that as sufficient "proof" that either equivalence should be able to
236           * handle either reference, so it's safe to circumvent compile-time type checking.
237           */
238          @SuppressWarnings("unchecked")
239          Equivalence<Object> equivalence = (Equivalence<Object>) this.equivalence;
240          return equivalence.equivalent(this.reference, that.reference);
241        }
242      }
243      return false;
244    }
245
246    /** Returns the result of {@link Equivalence#hash(Object)} applied to the wrapped reference. */
247    @Override
248    public int hashCode() {
249      return equivalence.hash(reference);
250    }
251
252    /**
253     * Returns a string representation for this equivalence wrapper. The form of this string
254     * representation is not specified.
255     */
256    @Override
257    public String toString() {
258      return equivalence + ".wrap(" + reference + ")";
259    }
260
261    private static final long serialVersionUID = 0;
262  }
263
264  /**
265   * Returns an equivalence over iterables based on the equivalence of their elements. More
266   * specifically, two iterables are considered equivalent if they both contain the same number of
267   * elements, and each pair of corresponding elements is equivalent according to {@code this}. Null
268   * iterables are equivalent to one another.
269   *
270   * <p>Note that this method performs a similar function for equivalences as {@link
271   * com.google.common.collect.Ordering#lexicographical} does for orderings.
272   *
273   * <p>The returned object is serializable if this object is serializable.
274   *
275   * @since 10.0
276   */
277  @GwtCompatible(serializable = true)
278  public final <S extends @Nullable T> Equivalence<Iterable<S>> pairwise() {
279    // Ideally, the returned equivalence would support Iterable<? extends T>. However,
280    // the need for this is so rare that it's not worth making callers deal with the ugly wildcard.
281    return new PairwiseEquivalence<>(this);
282  }
283
284  /**
285   * Returns a predicate that evaluates to true if and only if the input is equivalent to {@code
286   * target} according to this equivalence relation.
287   *
288   * @since 10.0
289   */
290  public final Predicate<@Nullable T> equivalentTo(@CheckForNull T target) {
291    return new EquivalentToPredicate<T>(this, target);
292  }
293
294  private static final class EquivalentToPredicate<T>
295      implements Predicate<@Nullable T>, Serializable {
296
297    private final Equivalence<T> equivalence;
298    @CheckForNull private final T target;
299
300    EquivalentToPredicate(Equivalence<T> equivalence, @CheckForNull T target) {
301      this.equivalence = checkNotNull(equivalence);
302      this.target = target;
303    }
304
305    @Override
306    public boolean apply(@CheckForNull T input) {
307      return equivalence.equivalent(input, target);
308    }
309
310    @Override
311    public boolean equals(@CheckForNull Object obj) {
312      if (this == obj) {
313        return true;
314      }
315      if (obj instanceof EquivalentToPredicate) {
316        EquivalentToPredicate<?> that = (EquivalentToPredicate<?>) obj;
317        return equivalence.equals(that.equivalence) && Objects.equal(target, that.target);
318      }
319      return false;
320    }
321
322    @Override
323    public int hashCode() {
324      return Objects.hashCode(equivalence, target);
325    }
326
327    @Override
328    public String toString() {
329      return equivalence + ".equivalentTo(" + target + ")";
330    }
331
332    private static final long serialVersionUID = 0;
333  }
334
335  /**
336   * Returns an equivalence that delegates to {@link Object#equals} and {@link Object#hashCode}.
337   * {@link Equivalence#equivalent} returns {@code true} if both values are null, or if neither
338   * value is null and {@link Object#equals} returns {@code true}. {@link Equivalence#hash} returns
339   * {@code 0} if passed a null value.
340   *
341   * @since 13.0
342   * @since 8.0 (in Equivalences with null-friendly behavior)
343   * @since 4.0 (in Equivalences)
344   */
345  public static Equivalence<Object> equals() {
346    return Equals.INSTANCE;
347  }
348
349  /**
350   * Returns an equivalence that uses {@code ==} to compare values and {@link
351   * System#identityHashCode(Object)} to compute the hash code. {@link Equivalence#equivalent}
352   * returns {@code true} if {@code a == b}, including in the case that a and b are both null.
353   *
354   * @since 13.0
355   * @since 4.0 (in Equivalences)
356   */
357  public static Equivalence<Object> identity() {
358    return Identity.INSTANCE;
359  }
360
361  static final class Equals extends Equivalence<Object> implements Serializable {
362
363    static final Equals INSTANCE = new Equals();
364
365    @Override
366    protected boolean doEquivalent(Object a, Object b) {
367      return a.equals(b);
368    }
369
370    @Override
371    protected int doHash(Object o) {
372      return o.hashCode();
373    }
374
375    private Object readResolve() {
376      return INSTANCE;
377    }
378
379    private static final long serialVersionUID = 1;
380  }
381
382  static final class Identity extends Equivalence<Object> implements Serializable {
383
384    static final Identity INSTANCE = new Identity();
385
386    @Override
387    protected boolean doEquivalent(Object a, Object b) {
388      return false;
389    }
390
391    @Override
392    protected int doHash(Object o) {
393      return System.identityHashCode(o);
394    }
395
396    private Object readResolve() {
397      return INSTANCE;
398    }
399
400    private static final long serialVersionUID = 1;
401  }
402}