// Copyright 2014 The Bazel Authors. 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.
// 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 com.google.devtools.build.skyframe;

import com.google.common.collect.Interner;
import com.google.devtools.build.lib.concurrent.BlazeInterners;
import com.google.devtools.build.lib.concurrent.ThreadSafety;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import java.io.Serializable;
import java.lang.reflect.Field;
import java.util.Map;
import javax.annotation.Nullable;

/**
 * A {@link SkyKey} is effectively a pair (type, name) that identifies a Skyframe value.
 *
 * <p>SkyKey implementations are heavily used as map keys. Thus, they should have fast {@link
 * #hashCode} implementations (cached if necessary). The same SkyKey may be created multiple times
 * by different {@code SkyFunction}s requesting it, and so it should have effective interning. There
 * will likely be more SkyKeys on the JVM heap than any other non-native type, so be mindful of
 * memory usage (in particular object wrapper size and memory alignment)! Typically the
 * implementation should have a fixed {@link #functionName} implementation and return itself as the
 * {@link #argument} in order to reduce the cost of wrapper objects.
 */
public interface SkyKey extends Serializable {
  SkyFunctionName functionName();

  default Object argument() {
    return this;
  }

  /**
   * Returns {@code true} if this key produces a {@link SkyValue} that can be reused across builds.
   *
   * <p>Values may be unshareable because they are just not serializable, or because they contain
   * data that cannot safely be reused as-is by another invocation, such as stamping information or
   * "flaky" values like test statuses.
   *
   * <p>Unshareable data should not be serialized, since it will never be reused. Attempts to fetch
   * a key's serialized data will call this method and only perform the fetch if it returns {@code
   * true}.
   *
   * <p>The result of this method only applies to non-error values. In case of an error, {@link
   * ErrorInfo#isTransitivelyTransient()} can be used to determine shareability.
   */
  default boolean valueIsShareable() {
    return true;
  }

  /**
   * Returns {@code true} if this key's {@link SkyFunction} would like Skyframe to schedule its
   * reevaluation when any of its previously requested unfinished deps completes. Otherwise,
   * Skyframe will schedule reevaluation only when all previously requested unfinished deps
   * complete.
   */
  default boolean supportsPartialReevaluation() {
    return false;
  }

  /** Returns null if the {@link SkyKey} does not participate in pooled interning. */
  @Nullable
  default SkyKeyInterner<?> getSkyKeyInterner() {
    return null;
  }

  static <T extends SkyKey> SkyKeyInterner<T> newInterner() {
    return new SkyKeyInterner<>();
  }

  /**
   * An alternative container to the weak interner for storing {@link SkyKey}.
   *
   * <p>A pool is a storage space that already exists during normal program execution and provides
   * lookup functionality for interning, thus eliminating storage overhead from using a classic weak
   * interner.
   */
  interface SkyKeyPool {

    /**
     * Returns the canonical instance for the given key in the pool if it is present, otherwise
     * interns the key using its {@linkplain SkyKeyInterner#weakIntern weak interner}.
     *
     * <p>To ensure a single canonical instance, if the key is not present in the pool, it should be
     * weakly interned using synchronization so that it is not concurrently {@linkplain
     * SkyKeyInterner#removeWeak removed from the weak interner}.
     */
    SkyKey getOrWeakIntern(SkyKey key);

    /**
     * Cleans up {@link SkyKey}s stored in the {@link SkyKeyPool} if necessary and uninstalls the in
     * memory graph instance from being {@link SkyKeyInterner}'s static global pool.
     */
    void cleanupPool();
  }

  /**
   * An extension of the weak interner which contains an alternative and static {@link #globalPool}
   * container in addition to a weak interner and supports removing {@link SkyKey} from the {@link
   * #weakInterner}.
   *
   * <p>The reason of implementing {@link SkyKeyInterner} is that the same {@link SkyKey} object can
   * be stored in both weak interner and some other container in blaze with two equal references,
   * causing some memory overhead.
   *
   * <p>{@link SkyKeyInterner} enables the client to manage where the {@link SkyKey} object is
   * stored, addressing the memory overhead issue. In more detail,
   *
   * <ul>
   *   <li>If the {@link SkyKey} object is already canonicalized in the {@link #globalPool}, it
   *       should not be stored in {@link #weakInterner} again, thus removing the storage overhead
   *       of using a weak interner;
   *   <li>User can also remove {@link SkyKey} from {@link #weakInterner}'s underlying {@link
   *       #internerAsMap} when the {@link SkyKey} object appears in {@link #globalPool}.
   * </ul>
   */
  final class SkyKeyInterner<T extends SkyKey> implements Interner<T> {
    @Nullable private static SkyKeyPool globalPool = null;

    private final Interner<T> weakInterner = BlazeInterners.newWeakInterner();
    private final Map<?, ?> internerAsMap = getMapReflectively(weakInterner);

    private SkyKeyInterner() {}

    // There was a Guava API review to include the feature of removing from an interner, and the
    // outcome was that we should just get the map reflectively.
    private static Map<?, ?> getMapReflectively(Interner<?> interner) {
      try {
        Field field = interner.getClass().getDeclaredField("map");
        field.setAccessible(true);
        return (Map<?, ?>) field.get(interner);
      } catch (ReflectiveOperationException e) {
        throw new IllegalStateException(e);
      }
    }

    /**
     * Sets the {@link SkyKeyPool} to be used for interning.
     *
     * <p>The pool is strongly retained until another pool is set. {@code null} can be passed to
     * clear the global pool.
     */
    @ThreadSafety.ThreadCompatible
    public static void setGlobalPool(@Nullable SkyKeyPool pool) {
      // No synchronization is needed. Setting global pool is guaranteed to happen sequentially
      // since only one build can happen at the same time.
      globalPool = pool;
    }

    /**
     * Returns the canonical instance of {@code sample} from either {@link #globalPool} or the
     * {@link #weakInterner}.
     */
    @Override
    @SuppressWarnings("unchecked")
    public T intern(T sample) {
      SkyKeyPool pool = globalPool;
      return pool != null ? (T) pool.getOrWeakIntern(sample) : weakInterner.intern(sample);
    }

    /**
     * Interns {@code sample} directly into {@link #weakInterner} without checking {@link
     * #globalPool} and returns the canonical instance of {@code sample}.
     */
    @SuppressWarnings("unchecked")
    @CanIgnoreReturnValue
    public T weakIntern(SkyKey sample) {
      return weakInterner.intern((T) sample);
    }

    /**
     * Removes sample from the weak interner. Client can call this method when the sample is already
     * stored in the global pool in order to reduce the memory overhead.
     */
    public void removeWeak(SkyKey sample) {
      internerAsMap.remove(sample);
    }
  }

  /**
   * A hint to schedulers that evaluating this key shouldn't cause high fanout.
   *
   * <p>Keys with high fan-out create memory pressure and are assigned low priority.
   */
  default boolean hasLowFanout() {
    return false;
  }
}