/*
 * Copyright 2000-2015 JetBrains s.r.o.
 *
 * 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.jetbrains.python.psi.types;

import com.intellij.psi.util.CachedValue;
import com.intellij.psi.util.CachedValueProvider;
import com.intellij.psi.util.CachedValuesManager;
import com.intellij.psi.util.PsiModificationTracker;
import com.intellij.util.Function;
import org.jetbrains.annotations.NotNull;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

/**
 * Engine to cache something in map, where {@link TypeEvalContext} is used as key.
 * This cache is weak-based (no memory leaks), thread safe and purges on any PSI change.
 *
 * @author Ilya.Kazakevich
 */
public final class TypeEvalContextBasedCache<T> {
  @NotNull
  private final CachedValue<ConcurrentMap<TypeEvalConstraints, T>> myCachedMapStorage;

  @NotNull
  private final Function<TypeEvalContext, T> myProvider;

  /**
   * @param manager       Cache manager to be used to store cache
   * @param valueProvider engine to create value based on context.
   */
  public TypeEvalContextBasedCache(@NotNull final CachedValuesManager manager,
                                   @NotNull final Function<TypeEvalContext, T> valueProvider) {
    myCachedMapStorage = manager.createCachedValue(new MapCreator<T>(), false);
    myProvider = valueProvider;
  }

  /**
   * Returns value (executes provider to obtain new if no any and stores it in cache).
   * It is better to run this method under read action to make sure PSI not modified in the middle of its execution
   *
   * @param context to be used as key
   * @return value
   */
  @NotNull
  public T getValue(@NotNull final TypeEvalContext context) {

    // map is thread safe but not atomic nor getValue() is, so in worst case several threads may produce same result
    // myProvider.fun should never be launched under lock to prevent deadlocks like PY-24300 and PY-24625
    // both explicit locking and computeIfAbsent leads to deadlock
    final ConcurrentMap<TypeEvalConstraints, T> map = myCachedMapStorage.getValue();
    final TypeEvalConstraints key = context.getConstraints();
    final T value = map.get(key);
    if (value != null) {
      return value;
    }
    final T newValue = myProvider.fun(context);
    map.put(key, newValue); // ConcurrentMap guarantees happens-before so from this moment get() should work in other threads
    return newValue;
  }

  /**
   * Provider that creates map to store cache. Map depends on PSI modification
   */
  private static final class MapCreator<T> implements CachedValueProvider<ConcurrentMap<TypeEvalConstraints, T>> {
    @NotNull
    @Override
    public Result<ConcurrentMap<TypeEvalConstraints, T>> compute() {
      // This method is called if cache is empty. Create new map for it.
      // Concurrent map allows several threads to call get and put, so it is thread safe but not atomic
      final ConcurrentHashMap<TypeEvalConstraints, T> map = new ConcurrentHashMap<>();
      return new Result<>(map, PsiModificationTracker.MODIFICATION_COUNT);
    }
  }
}

@@ -876,90 +876,94 @@
 ort 
-org.jetbrains.annotations.NotNul
+com.intellij.util.containers.ContainerUti
 l;%0A
-%0A
 import 
-java.util.concurrent.ConcurrentHashMap;
+org.jetbrains.annotations.NotNull;%0A
 %0Aimp
@@ -2797,14 +2797,41 @@
     
-map.pu
+T oldValue =%0A      map.putIfAbsen
 t(ke
@@ -2843,17 +2843,16 @@
 wValue);
- 
 // Concu
@@ -2952,19 +2952,49 @@
  return 
-new
+oldValue == null ? newValue : old
 Value;%0A 
@@ -3494,28 +3494,24 @@
 l Concurrent
-Hash
 Map%3CTypeEval
@@ -3532,20 +3532,36 @@
 %3E map = 
-new 
+ContainerUtil.create
 Concurre
@@ -3566,17 +3566,20 @@
 rent
-Hash
+SoftValue
 Map
-%3C%3E
 ();%0A

make values in TypeEvalContextBasedCache soft