// Copyright 2023 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.lib.concurrent;

import com.google.common.collect.Interner;
import com.google.common.collect.MapMaker;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadHostile;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.errorprone.annotations.ForOverride;
import java.lang.reflect.Field;
import java.util.Collections;
import java.util.Map;
import java.util.Set;
import javax.annotation.Nullable;

/**
 * An extension of the weak interner which uses a global pool in addition to the weak interner's
 * {@code ConcurrentHashMap} to store instances.
 *
 * <p>The reason of implementing {@link PooledInterner} is that the same object can be stored in
 * both weak interner and some other container ({@code InMemoryGraphImple#nodeMap}) in blaze with
 * two equal references, causing some memory overhead.
 *
 * <p>{@link PooledInterner} enables the client to manage where a single object is stored,
 * addressing the memory overhead issue. In more detail,
 *
 * <ul>
 *   <li>If the object is already canonicalized in the global pool, it should not be stored in
 *       {@link #weakInterner} again, thus removing the storage overhead of using a traditional weak
 *       interner;
 *   <li>User can also remove the object from {@link #weakInterner}'s underlying {@link
 *       #internerAsMap} when the object appears in the global pool.
 * </ul>
 *
 * <p>Subclasses are only responsible for providing the appropriate {@link Pool} by overriding
 * {@link #getPool()} method.
 */
public abstract class PooledInterner<T> implements Interner<T> {
  private Interner<T> weakInterner = BlazeInterners.newWeakInterner();
  private Map<?, ?> internerAsMap = getMapReflectively(weakInterner);

  /**
   * Holds all PooledInterner instances registered in the lifetime of this Blaze server as a weak
   * collection to prevent memory leaks. This is also thread-safe to handle multiple PooledInterners
   * from being instantiated concurrently, for instance during class initializations.
   */
  private static final Set<PooledInterner<?>> instances =
      Collections.newSetFromMap(new MapMaker().weakKeys().makeMap());

  protected PooledInterner() {
    instances.add(this);
  }

  /**
   * Interns {@code sample} directly into {@link #weakInterner} without checking the global pool and
   * returns the canonical instance of {@code sample}.
   */
  @CanIgnoreReturnValue
  public final T weakIntern(T sample) {
    return weakInterner.intern(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 final void removeWeak(Object sample) {
    internerAsMap.remove(sample);
  }

  /**
   * Returns the canonical instance of {@code sample} from either global pool or {@link
   * #weakInterner}.
   */
  @Override
  public final T intern(T sample) {
    Pool<T> pool = getPool();
    return pool != null ? pool.getOrWeakIntern(sample) : weakInterner.intern(sample);
  }

  /**
   * Provides the global pool instance for {@link #intern(Object)} method.
   */
  @ForOverride
  @Nullable
  protected abstract Pool<T> getPool();

  public final int size() {
    return internerAsMap.size();
  }

  /**
   * Shrinks all interner instances' backing map to reclaim memory.
   *
   * <p>This needs a prior GC to be effective.
   *
   * <p>WARNING: This must not be called concurrently with any interning operations, because it
   * provides unsynchronized access to multiple mutable static interners.
   */
  @ThreadHostile
  public static final void shrinkAll() {
    instances.forEach(PooledInterner::shrink);
  }

  /** Shrinks the weak interner and obtain a new reference to the newly shrunk map. */
  private void shrink() {
    this.weakInterner = shrinkAsNewWeakInterner(weakInterner);
    this.internerAsMap = getMapReflectively(weakInterner);
  }

  /**
   * Shrink an interner by rebuilding a new weak interner and backing map/array. Use this if you
   * expect a GC to clear references into an interner's backing map.
   *
   * <p>If there are references to the backing map, use {@code getMapReflectively} to update them.
   *
   * <p>This is created because backing maps do not automatically resize after removing entries.
   */
  private static <T> Interner<T> shrinkAsNewWeakInterner(Interner<T> fromInterner) {
    Interner<T> toInterner = BlazeInterners.newWeakInterner();
    Map<T, ?> map = getMapReflectively(fromInterner);
    map.keySet().parallelStream()
        .forEach(
            k -> {
              T unused = toInterner.intern(k);
            });
    return toInterner;
  }

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

  /**
   * An alternative container to the weak interner for storing type T instance.
   *
   * <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.
   */
  public interface Pool<T> {
    /**
     * Returns the canonical instance for the given key in the pool if it is present, otherwise
     * interns the key using its {@linkplain #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 #removeWeak
     * removed from the weak interner}.
     */
    T getOrWeakIntern(T sample);
  }
}