/*
 * 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.*;
import com.intellij.util.Function;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.HashMap;
import java.util.Map;

/**
 * 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> {
  /**
   * Lock to sync
   */
  @NotNull
  private final Object myLock = new Object();
  @NotNull
  private final CachedValue<Map<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)
   * @param context to be used as key
   * @return value
   */
  @NotNull
  public T getValue(@NotNull final TypeEvalContext context) {

    // Map is not thread safe, and "getValue" is not atomic. I do not want several maps to be created.
    synchronized (myLock) {
      final Map<TypeEvalConstraints, T> map = myCachedMapStorage.getValue();
      T value = map.get(context.getConstraints());
      if (value != null) {
        return value;
      }
      // This is the same value, semantically: value for context-key
      //noinspection ReuseOfLocalVariable
      value = myProvider.fun(context);
      map.put(context.getConstraints(), value);
      return value;
    }
  }

  /**
   * Provider that creates map to store cache. Map depends on PSI modification
   */
  private static final class MapCreator<T> implements CachedValueProvider<Map<TypeEvalConstraints, T>> {
    @Nullable
    @Override
    public Result<Map<TypeEvalConstraints, T>> compute() {
      // This method is called if cache is empty. Create new map for it.
      final HashMap<TypeEvalConstraints, T> map = new HashMap<>();
      return new Result<>(map, PsiModificationTracker.MODIFICATION_COUNT);
    }
  }
}

@@ -664,17 +664,27 @@
 si.util.
-*
+CachedValue
 ;%0Aimport
@@ -701,63 +701,174 @@
 lij.
+psi.
 util.
-Function;%0Aimport org.jetbrains.annotations.NotNull
+CachedValueProvider;%0Aimport com.intellij.psi.util.CachedValuesManager;%0Aimport com.intellij.psi.util.PsiModificationTracker;%0Aimport com.intellij.util.Function
 ;%0Aim
@@ -899,23 +899,22 @@
 ations.N
+otN
 ull
-able
 ;%0A%0Aimpor
@@ -925,16 +925,37 @@
 va.util.
+concurrent.Concurrent
 HashMap;
@@ -972,16 +972,37 @@
 va.util.
+concurrent.Concurrent
 Map;%0A%0A/*
@@ -1263,95 +1263,8 @@
 %3E %7B%0A
-  /**%0A   * Lock to sync%0A   */%0A  @NotNull%0A  private final Object myLock = new Object();%0A
   @N
@@ -1298,16 +1298,26 @@
 edValue%3C
+Concurrent
 Map%3CType
@@ -2104,19 +2104,15 @@
  // 
-M
+m
 ap is 
-not 
 thre
@@ -2122,23 +2122,36 @@
 safe
-, and %22
+ but not atomic nor 
 getValue
 %22 is
@@ -2150,107 +2150,184 @@
 alue
-%22 is not atomic. I do not want several maps to b
+() is, so in worst case several threads may produce sam
 e 
-c
 re
-ated.%0A    synchronized (myLock) %7B%0A      final 
+sult%0A    // but explicit synchronization is also slow and may lead to deadlocks like in PY-24300%0A    final Concurrent
 Map%3C
@@ -2395,28 +2395,40 @@
     
-  T value = map.get(
+final TypeEvalConstraints key = 
 cont
@@ -2451,192 +2451,43 @@
 ts()
-)
 ;%0A    
-  if (value != null) %7B%0A        return value;%0A      %7D%0A      // This is the same value, semantically: value for context-key%0A      //noinspection ReuseOfLocalVariable%0A      value =
+map.computeIfAbsent(key, o -%3E
  myP
@@ -2510,83 +2510,35 @@
 ext)
+)
 ;%0A    
-  map.put(context.getConstraints(), value);%0A      return value;%0A    %7D
+return map.get(key);
 %0A  %7D
@@ -2704,16 +2704,26 @@
 rovider%3C
+Concurrent
 Map%3CType
@@ -2755,15 +2755,14 @@
   @N
+otN
 ull
-able
 %0A   
@@ -2790,16 +2790,26 @@
  Result%3C
+Concurrent
 Map%3CType
@@ -2920,22 +2920,136 @@
 .%0A      
-final 
+// Concurrent map allows several threads to call get and put, so it is thread safe but not atomic%0A      final Concurrent
 HashMap%3C
@@ -3082,16 +3082,26 @@
 p = new 
+Concurrent
 HashMap%3C

Remove explicit locking in favor to concurrent map to simplify code and prevent deadlock