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.Nullable;
025
026/**
027 * A strategy for determining whether two instances are considered equivalent, and for computing
028 * hash codes in a manner consistent with that equivalence. Two examples of equivalences are the
029 * {@linkplain #identity() identity equivalence} and the {@linkplain #equals "equals" equivalence}.
030 *
031 * @author Bob Lee
032 * @author Ben Yu
033 * @author Gregory Kick
034 * @since 10.0 (<a href="https://github.com/google/guava/wiki/Compatibility">mostly
035 *     source-compatible</a> since 4.0)
036 */
037@GwtCompatible
038@ElementTypesAreNonnullByDefault
039/*
040 * The type parameter is <T> rather than <T extends @Nullable> so that we can use T in the
041 * doEquivalent and doHash methods to indicate that the parameter cannot be null.
042 */
043public abstract class Equivalence<T> implements BiPredicate<@Nullable T, @Nullable T> {
044  /** Constructor for use by subclasses. */
045  protected Equivalence() {}
046
047  /**
048   * Returns {@code true} if the given objects are considered equivalent.
049   *
050   * <p>This method describes an <i>equivalence relation</i> on object references, meaning that for
051   * all references {@code x}, {@code y}, and {@code z} (any of which may be null):
052   *
053   * <ul>
054   *   <li>{@code equivalent(x, x)} is true (<i>reflexive</i> property)
055   *   <li>{@code equivalent(x, y)} and {@code equivalent(y, x)} each return the same result
056   *       (<i>symmetric</i> property)
057   *   <li>If {@code equivalent(x, y)} and {@code equivalent(y, z)} are both true, then {@code
058   *       equivalent(x, z)} is also true (<i>transitive</i> property)
059   * </ul>
060   *
061   * <p>Note that all calls to {@code equivalent(x, y)} are expected to return the same result as
062   * long as neither {@code x} nor {@code y} is modified.
063   */
064  public final boolean equivalent(@CheckForNull T a, @CheckForNull T b) {
065    if (a == b) {
066      return true;
067    }
068    if (a == null || b == null) {
069      return false;
070    }
071    return doEquivalent(a, b);
072  }
073
074  /**
075   * @deprecated Provided only to satisfy the {@link BiPredicate} interface; use {@link #equivalent}
076   *     instead.
077   * @since 21.0
078   */
079  @Deprecated
080  @Override
081  public final boolean test(@CheckForNull T t, @CheckForNull T u) {
082    return equivalent(t, u);
083  }
084
085  /**
086   * Implemented by the user to determine whether {@code a} and {@code b} are considered equivalent,
087   * subject to the requirements specified in {@link #equivalent}.
088   *
089   * <p>This method should not be called except by {@link #equivalent}. When {@link #equivalent}
090   * calls this method, {@code a} and {@code b} are guaranteed to be distinct, non-null instances.
091   *
092   * @since 10.0 (previously, subclasses would override equivalent())
093   */
094  @ForOverride
095  protected abstract boolean doEquivalent(T a, T b);
096
097  /**
098   * Returns a hash code for {@code t}.
099   *
100   * <p>The {@code hash} has the following properties:
101   *
102   * <ul>
103   *   <li>It is <i>consistent</i>: for any reference {@code x}, multiple invocations of {@code
104   *       hash(x}} consistently return the same value provided {@code x} remains unchanged
105   *       according to the definition of the equivalence. The hash need not remain consistent from
106   *       one execution of an application to another execution of the same application.
107   *   <li>It is <i>distributable across equivalence</i>: for any references {@code x} and {@code
108   *       y}, if {@code equivalent(x, y)}, then {@code hash(x) == hash(y)}. It is <i>not</i>
109   *       necessary that the hash be distributable across <i>inequivalence</i>. If {@code
110   *       equivalence(x, y)} is false, {@code hash(x) == hash(y)} may still be true.
111   *   <li>{@code hash(null)} is {@code 0}.
112   * </ul>
113   */
114  public final int hash(@CheckForNull T t) {
115    if (t == null) {
116      return 0;
117    }
118    return doHash(t);
119  }
120
121  /**
122   * Implemented by the user to return a hash code for {@code t}, subject to the requirements
123   * specified in {@link #hash}.
124   *
125   * <p>This method should not be called except by {@link #hash}. When {@link #hash} calls this
126   * method, {@code t} is guaranteed to be non-null.
127   *
128   * @since 10.0 (previously, subclasses would override hash())
129   */
130  @ForOverride
131  protected abstract int doHash(T t);
132
133  /**
134   * Returns a new equivalence relation for {@code F} which evaluates equivalence by first applying
135   * {@code function} to the argument, then evaluating using {@code this}. That is, for any pair of
136   * non-null objects {@code x} and {@code y}, {@code equivalence.onResultOf(function).equivalent(a,
137   * b)} is true if and only if {@code equivalence.equivalent(function.apply(a), function.apply(b))}
138   * is true.
139   *
140   * <p>For example:
141   *
142   * <pre>{@code
143   * Equivalence<Person> SAME_AGE = Equivalence.equals().onResultOf(GET_PERSON_AGE);
144   * }</pre>
145   *
146   * <p>{@code function} will never be invoked with a null value.
147   *
148   * <p>Note that {@code function} must be consistent according to {@code this} equivalence
149   * relation. That is, invoking {@link Function#apply} multiple times for a given value must return
150   * equivalent results. For example, {@code
151   * Equivalence.identity().onResultOf(Functions.toStringFunction())} is broken because it's not
152   * guaranteed that {@link Object#toString}) always returns the same string instance.
153   *
154   * @since 10.0
155   */
156  public final <F> Equivalence<F> onResultOf(Function<? super F, ? extends @Nullable T> function) {
157    return new FunctionalEquivalence<>(function, this);
158  }
159
160  /**
161   * Returns a wrapper of {@code reference} that implements {@link Wrapper#equals(Object)
162   * Object.equals()} such that {@code wrap(a).equals(wrap(b))} if and only if {@code equivalent(a,
163   * b)}.
164   *
165   * @since 10.0
166   */
167  public final <S extends @Nullable T> Wrapper<S> wrap(@ParametricNullness S reference) {
168    /*
169     * I'm pretty sure that this warning "makes sense" but doesn't indicate a real problem.
170     *
171     * Why it "makes sense": If we pass a `@Nullable Foo`, then we should also pass an
172     * `Equivalence<? super @Nullable Foo>`. And there's no such thing because Equivalence doesn't
173     * permit nullable type arguments.
174     *
175     * Why there's no real problem: Every Equivalence can handle null.
176     *
177     * We could work around this by giving Wrapper 2 type parameters. In the terms of this method,
178     * that would be both the T parameter (from the class) and the S parameter (from this method).
179     * However, such a change would be source-incompatible. (Plus, there's no reason for the S
180     * parameter from the user's perspective, so it would be a wart.)
181     *
182     * We could probably also work around this by making Wrapper non-final and putting the
183     * implementation into a subclass with those 2 type parameters. But we like `final`, if only to
184     * deter users from using mocking frameworks to construct instances. (And could also complicate
185     * serialization, which is discussed more in the next paragraph.)
186     *
187     * We could probably also work around this by having Wrapper accept an instance of a new
188     * WrapperGuts class, which would then be the class that would declare the 2 type parameters.
189     * But that would break deserialization of previously serialized Wrapper instances. And while we
190     * specifically say not to rely on serialization across Guava versions, users sometimes do. So
191     * we'd rather not break them without a good enough reason.
192     *
193     * (We could work around the serialization problem by writing custom serialization code. But
194     * even that helps only the case of serializing with an old version and deserializing with a
195     * new, not vice versa -- unless we introduce WrapperGuts and the logic to handle it today, wait
196     * until "everyone" has picked up a version of Guava with that code, and *then* change to use
197     * WrapperGuts.)
198     *
199     * Anyway, a suppression isn't really a big deal. But I have tried to do some due diligence on
200     * avoiding it :)
201     */
202    @SuppressWarnings("nullness")
203    Wrapper<S> w = new Wrapper<>(this, reference);
204    return w;
205  }
206
207  /**
208   * Wraps an object so that {@link #equals(Object)} and {@link #hashCode()} delegate to an {@link
209   * Equivalence}.
210   *
211   * <p>For example, given an {@link Equivalence} for {@link String strings} named {@code equiv}
212   * that tests equivalence using their lengths:
213   *
214   * <pre>{@code
215   * equiv.wrap("a").equals(equiv.wrap("b")) // true
216   * equiv.wrap("a").equals(equiv.wrap("hello")) // false
217   * }</pre>
218   *
219   * <p>Note in particular that an equivalence wrapper is never equal to the object it wraps.
220   *
221   * <pre>{@code
222   * equiv.wrap(obj).equals(obj) // always false
223   * }</pre>
224   *
225   * @since 10.0
226   */
227  public static final class Wrapper<T extends @Nullable Object> implements Serializable {
228    private final Equivalence<? super T> equivalence;
229    @ParametricNullness private final T reference;
230
231    private Wrapper(Equivalence<? super T> equivalence, @ParametricNullness T reference) {
232      this.equivalence = checkNotNull(equivalence);
233      this.reference = reference;
234    }
235
236    /** Returns the (possibly null) reference wrapped by this instance. */
237    @ParametricNullness
238    public T get() {
239      return reference;
240    }
241
242    /**
243     * Returns {@code true} if {@link Equivalence#equivalent(Object, Object)} applied to the wrapped
244     * references is {@code true} and both wrappers use the {@link Object#equals(Object) same}
245     * equivalence.
246     */
247    @Override
248    public boolean equals(@CheckForNull Object obj) {
249      if (obj == this) {
250        return true;
251      }
252      if (obj instanceof Wrapper) {
253        Wrapper<?> that = (Wrapper<?>) obj; // note: not necessarily a Wrapper<T>
254
255        if (this.equivalence.equals(that.equivalence)) {
256          /*
257           * We'll accept that as sufficient "proof" that either equivalence should be able to
258           * handle either reference, so it's safe to circumvent compile-time type checking.
259           */
260          @SuppressWarnings("unchecked")
261          Equivalence<Object> equivalence = (Equivalence<Object>) this.equivalence;
262          return equivalence.equivalent(this.reference, that.reference);
263        }
264      }
265      return false;
266    }
267
268    /** Returns the result of {@link Equivalence#hash(Object)} applied to the wrapped reference. */
269    @Override
270    public int hashCode() {
271      return equivalence.hash(reference);
272    }
273
274    /**
275     * Returns a string representation for this equivalence wrapper. The form of this string
276     * representation is not specified.
277     */
278    @Override
279    public String toString() {
280      return equivalence + ".wrap(" + reference + ")";
281    }
282
283    private static final long serialVersionUID = 0;
284  }
285
286  /**
287   * Returns an equivalence over iterables based on the equivalence of their elements. More
288   * specifically, two iterables are considered equivalent if they both contain the same number of
289   * elements, and each pair of corresponding elements is equivalent according to {@code this}. Null
290   * iterables are equivalent to one another.
291   *
292   * <p>Note that this method performs a similar function for equivalences as {@link
293   * com.google.common.collect.Ordering#lexicographical} does for orderings.
294   *
295   * @since 10.0
296   */
297  @GwtCompatible(serializable = true)
298  public final <S extends @Nullable T> Equivalence<Iterable<S>> pairwise() {
299    // Ideally, the returned equivalence would support Iterable<? extends T>. However,
300    // the need for this is so rare that it's not worth making callers deal with the ugly wildcard.
301    return new PairwiseEquivalence<>(this);
302  }
303
304  /**
305   * Returns a predicate that evaluates to true if and only if the input is equivalent to {@code
306   * target} according to this equivalence relation.
307   *
308   * @since 10.0
309   */
310  public final Predicate<@Nullable T> equivalentTo(@CheckForNull T target) {
311    return new EquivalentToPredicate<T>(this, target);
312  }
313
314  private static final class EquivalentToPredicate<T>
315      implements Predicate<@Nullable T>, Serializable {
316
317    private final Equivalence<T> equivalence;
318    @CheckForNull private final T target;
319
320    EquivalentToPredicate(Equivalence<T> equivalence, @CheckForNull T target) {
321      this.equivalence = checkNotNull(equivalence);
322      this.target = target;
323    }
324
325    @Override
326    public boolean apply(@CheckForNull T input) {
327      return equivalence.equivalent(input, target);
328    }
329
330    @Override
331    public boolean equals(@CheckForNull Object obj) {
332      if (this == obj) {
333        return true;
334      }
335      if (obj instanceof EquivalentToPredicate) {
336        EquivalentToPredicate<?> that = (EquivalentToPredicate<?>) obj;
337        return equivalence.equals(that.equivalence) && Objects.equal(target, that.target);
338      }
339      return false;
340    }
341
342    @Override
343    public int hashCode() {
344      return Objects.hashCode(equivalence, target);
345    }
346
347    @Override
348    public String toString() {
349      return equivalence + ".equivalentTo(" + target + ")";
350    }
351
352    private static final long serialVersionUID = 0;
353  }
354
355  /**
356   * Returns an equivalence that delegates to {@link Object#equals} and {@link Object#hashCode}.
357   * {@link Equivalence#equivalent} returns {@code true} if both values are null, or if neither
358   * value is null and {@link Object#equals} returns {@code true}. {@link Equivalence#hash} returns
359   * {@code 0} if passed a null value.
360   *
361   * @since 13.0
362   * @since 8.0 (in Equivalences with null-friendly behavior)
363   * @since 4.0 (in Equivalences)
364   */
365  public static Equivalence<Object> equals() {
366    return Equals.INSTANCE;
367  }
368
369  /**
370   * Returns an equivalence that uses {@code ==} to compare values and {@link
371   * System#identityHashCode(Object)} to compute the hash code. {@link Equivalence#equivalent}
372   * returns {@code true} if {@code a == b}, including in the case that a and b are both null.
373   *
374   * @since 13.0
375   * @since 4.0 (in Equivalences)
376   */
377  public static Equivalence<Object> identity() {
378    return Identity.INSTANCE;
379  }
380
381  static final class Equals extends Equivalence<Object> implements Serializable {
382
383    static final Equals INSTANCE = new Equals();
384
385    @Override
386    protected boolean doEquivalent(Object a, Object b) {
387      return a.equals(b);
388    }
389
390    @Override
391    protected int doHash(Object o) {
392      return o.hashCode();
393    }
394
395    private Object readResolve() {
396      return INSTANCE;
397    }
398
399    private static final long serialVersionUID = 1;
400  }
401
402  static final class Identity extends Equivalence<Object> implements Serializable {
403
404    static final Identity INSTANCE = new Identity();
405
406    @Override
407    protected boolean doEquivalent(Object a, Object b) {
408      return false;
409    }
410
411    @Override
412    protected int doHash(Object o) {
413      return System.identityHashCode(o);
414    }
415
416    private Object readResolve() {
417      return INSTANCE;
418    }
419
420    private static final long serialVersionUID = 1;
421  }
422}