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