<commit_before>/*
 * Copyright 2000-2009 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.
 */

/*
 * Created by IntelliJ IDEA.
 * User: max
 * Date: Jan 28, 2002
 * Time: 10:16:39 PM
 * To change template for new class use
 * Code Style | Class Templates options (Tools | IDE Options).
 */
package com.intellij.codeInspection.dataFlow;

import com.intellij.codeInspection.dataFlow.instructions.*;
import com.intellij.codeInspection.dataFlow.value.DfaValueFactory;
import com.intellij.codeInspection.dataFlow.value.DfaVariableValue;
import com.intellij.openapi.application.ApplicationManager;
import com.intellij.openapi.diagnostic.Logger;
import com.intellij.openapi.progress.ProgressManager;
import com.intellij.openapi.util.Key;
import com.intellij.openapi.util.Pair;
import com.intellij.psi.*;
import com.intellij.psi.util.PsiTreeUtil;
import com.intellij.psi.util.PsiUtil;
import com.intellij.util.containers.ContainerUtil;
import com.intellij.util.containers.MultiMap;
import com.intellij.util.containers.MultiMapBasedOnSet;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.*;

public class DataFlowRunner {
  private static final Logger LOG = Logger.getInstance("#com.intellij.codeInspection.dataFlow.DataFlowRunner");
  private static final Key<Integer> TOO_EXPENSIVE_HASH = Key.create("TOO_EXPENSIVE_HASH");
  public static final long ourTimeLimit = 1000 * 1000 * 1000; //1 sec in nanoseconds

  private Instruction[] myInstructions;
  private final MultiMap<PsiElement, DfaMemoryState> myNestedClosures = new MultiMap<PsiElement, DfaMemoryState>();
  private DfaVariableValue[] myFields;
  private final DfaValueFactory myValueFactory = new DfaValueFactory();

  // Maximum allowed attempts to process instruction. Fail as too complex to process if certain instruction
  // is executed more than this limit times.
  public static final int MAX_STATES_PER_BRANCH = 300;

  protected DataFlowRunner() {
  }

  public DfaValueFactory getFactory() {
    return myValueFactory;
  }

  protected void prepareAnalysis(@NotNull PsiElement psiBlock, Iterable<DfaMemoryState> initialStates) {
  }

  @Nullable
  private Collection<DfaMemoryState> createInitialStates(@NotNull PsiElement psiBlock, InstructionVisitor visitor) {
    PsiClass containingClass = PsiTreeUtil.getParentOfType(psiBlock, PsiClass.class);
    if (containingClass != null && PsiUtil.isLocalOrAnonymousClass(containingClass)) {
      final PsiElement parent = containingClass.getParent();
      final PsiCodeBlock block = DfaPsiUtil.getTopmostBlockInSameClass(parent);
      if ((parent instanceof PsiNewExpression || parent instanceof PsiDeclarationStatement) && block != null) {
        final RunnerResult result = analyzeMethod(block, visitor);
        if (result == RunnerResult.OK) {
          final Collection<DfaMemoryState> closureStates = myNestedClosures.get(DfaPsiUtil.getTopmostBlockInSameClass(psiBlock));
          if (!closureStates.isEmpty()) {
            return closureStates;
          }
        }
        return null;
      }
    }

    return Arrays.asList(createMemoryState());
  }

  public final RunnerResult analyzeMethod(@NotNull PsiElement psiBlock, InstructionVisitor visitor) {
    Collection<DfaMemoryState> initialStates = createInitialStates(psiBlock, visitor);
    return initialStates == null ? RunnerResult.NOT_APPLICABLE : analyzeMethod(psiBlock, visitor, false, initialStates);
  }
  
  public final RunnerResult analyzeMethod(@NotNull PsiElement psiBlock,
                                          InstructionVisitor visitor,
                                          boolean ignoreAssertions,
                                          @NotNull Collection<DfaMemoryState> initialStates) {
    try {
      prepareAnalysis(psiBlock, initialStates);

      final ControlFlow flow = createControlFlowAnalyzer().buildControlFlow(psiBlock, ignoreAssertions);
      if (flow == null) return RunnerResult.NOT_APPLICABLE;

      int endOffset = flow.getInstructionCount();
      myInstructions = flow.getInstructions();
      myFields = flow.getFields();
      myNestedClosures.clear();
      
      Set<Instruction> joinInstructions = ContainerUtil.newHashSet();
      for (Instruction instruction : myInstructions) {
        if (instruction instanceof GotoInstruction) {
          joinInstructions.add(myInstructions[((GotoInstruction)instruction).getOffset()]);
        } else if (instruction instanceof ConditionalGotoInstruction) {
          joinInstructions.add(myInstructions[((ConditionalGotoInstruction)instruction).getOffset()]);
        } else if (instruction instanceof GosubInstruction) {
          joinInstructions.add(myInstructions[((GosubInstruction)instruction).getSubprogramOffset()]);
        }
      }

      if (LOG.isDebugEnabled()) {
        LOG.debug("Analyzing code block: " + psiBlock.getText());
        for (int i = 0; i < myInstructions.length; i++) {
          Instruction instruction = myInstructions[i];
          LOG.debug(i + ": " + instruction.toString());
        }
      }

      Integer tooExpensiveHash = psiBlock.getUserData(TOO_EXPENSIVE_HASH);
      if (tooExpensiveHash != null && tooExpensiveHash == psiBlock.getText().hashCode()) {
        LOG.debug("Too complex because hasn't changed since being too complex already");
        return RunnerResult.TOO_COMPLEX;
      }

      final StateQueue queue = new StateQueue();
      for (final DfaMemoryState initialState : initialStates) {
        queue.offer(new DfaInstructionState(myInstructions[0], initialState));
      }

      MultiMapBasedOnSet<BranchingInstruction, DfaMemoryState> processedStates = new MultiMapBasedOnSet<BranchingInstruction, DfaMemoryState>();

      WorkingTimeMeasurer measurer = new WorkingTimeMeasurer(shouldCheckTimeLimit() ? ourTimeLimit : ourTimeLimit * 42);
      int count = 0;
      while (!queue.isEmpty()) {
        for (DfaInstructionState instructionState : queue.getNextInstructionStates(joinInstructions)) {
          if (count++ % 1024 == 0 && measurer.isTimeOver()) {
            LOG.debug("Too complex because the analysis took too long");
            psiBlock.putUserData(TOO_EXPENSIVE_HASH, psiBlock.getText().hashCode());
            return RunnerResult.TOO_COMPLEX;
          }
          ProgressManager.checkCanceled();

          if (LOG.isDebugEnabled()) {
            LOG.debug(instructionState.toString());
          }
          //System.out.println(instructionState.toString());

          Instruction instruction = instructionState.getInstruction();

          if (instruction instanceof BranchingInstruction) {
            BranchingInstruction branching = (BranchingInstruction)instruction;
            if (processedStates.get(branching).contains(instructionState.getMemoryState())) {
              continue;
            }
            if (processedStates.get(branching).size() > MAX_STATES_PER_BRANCH) {
              LOG.debug("Too complex because too many different possible states");
              return RunnerResult.TOO_COMPLEX; // Too complex :(
            }
            processedStates.putValue(branching, instructionState.getMemoryState().createCopy());
          }

          DfaInstructionState[] after = acceptInstruction(visitor, instructionState);
          for (DfaInstructionState state : after) {
            Instruction nextInstruction = state.getInstruction();
            if (nextInstruction.getIndex() >= endOffset) {
              continue;
            }
            if (nextInstruction instanceof BranchingInstruction && 
                processedStates.get((BranchingInstruction)nextInstruction).contains(state.getMemoryState())) {
              continue;
            }
            queue.offer(state);
          }
        }
      }

      psiBlock.putUserData(TOO_EXPENSIVE_HASH, null);
      LOG.debug("Analysis ok");
      return RunnerResult.OK;
    }
    catch (ArrayIndexOutOfBoundsException e) {
      LOG.error(psiBlock.getText(), e); // TODO fix in better times
      return RunnerResult.ABORTED;
    }
    catch (EmptyStackException e) {
      if (LOG.isDebugEnabled()) {
        LOG.error(e); // TODO fix in better times
      }<commit_msg>dfa: don't go into the same instruction twice with the same state<commit_after>/*
 * Copyright 2000-2009 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.
 */

/*
 * Created by IntelliJ IDEA.
 * User: max
 * Date: Jan 28, 2002
 * Time: 10:16:39 PM
 * To change template for new class use
 * Code Style | Class Templates options (Tools | IDE Options).
 */
package com.intellij.codeInspection.dataFlow;

import com.intellij.codeInspection.dataFlow.instructions.*;
import com.intellij.codeInspection.dataFlow.value.DfaValueFactory;
import com.intellij.codeInspection.dataFlow.value.DfaVariableValue;
import com.intellij.openapi.application.ApplicationManager;
import com.intellij.openapi.diagnostic.Logger;
import com.intellij.openapi.progress.ProgressManager;
import com.intellij.openapi.util.Key;
import com.intellij.openapi.util.Pair;
import com.intellij.psi.*;
import com.intellij.psi.util.PsiTreeUtil;
import com.intellij.psi.util.PsiUtil;
import com.intellij.util.containers.ContainerUtil;
import com.intellij.util.containers.MultiMap;
import com.intellij.util.containers.MultiMapBasedOnSet;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.*;

public class DataFlowRunner {
  private static final Logger LOG = Logger.getInstance("#com.intellij.codeInspection.dataFlow.DataFlowRunner");
  private static final Key<Integer> TOO_EXPENSIVE_HASH = Key.create("TOO_EXPENSIVE_HASH");
  public static final long ourTimeLimit = 1000 * 1000 * 1000; //1 sec in nanoseconds

  private Instruction[] myInstructions;
  private final MultiMap<PsiElement, DfaMemoryState> myNestedClosures = new MultiMap<PsiElement, DfaMemoryState>();
  private DfaVariableValue[] myFields;
  private final DfaValueFactory myValueFactory = new DfaValueFactory();

  // Maximum allowed attempts to process instruction. Fail as too complex to process if certain instruction
  // is executed more than this limit times.
  public static final int MAX_STATES_PER_BRANCH = 300;

  protected DataFlowRunner() {
  }

  public DfaValueFactory getFactory() {
    return myValueFactory;
  }

  protected void prepareAnalysis(@NotNull PsiElement psiBlock, Iterable<DfaMemoryState> initialStates) {
  }

  @Nullable
  private Collection<DfaMemoryState> createInitialStates(@NotNull PsiElement psiBlock, InstructionVisitor visitor) {
    PsiClass containingClass = PsiTreeUtil.getParentOfType(psiBlock, PsiClass.class);
    if (containingClass != null && PsiUtil.isLocalOrAnonymousClass(containingClass)) {
      final PsiElement parent = containingClass.getParent();
      final PsiCodeBlock block = DfaPsiUtil.getTopmostBlockInSameClass(parent);
      if ((parent instanceof PsiNewExpression || parent instanceof PsiDeclarationStatement) && block != null) {
        final RunnerResult result = analyzeMethod(block, visitor);
        if (result == RunnerResult.OK) {
          final Collection<DfaMemoryState> closureStates = myNestedClosures.get(DfaPsiUtil.getTopmostBlockInSameClass(psiBlock));
          if (!closureStates.isEmpty()) {
            return closureStates;
          }
        }
        return null;
      }
    }

    return Arrays.asList(createMemoryState());
  }

  public final RunnerResult analyzeMethod(@NotNull PsiElement psiBlock, InstructionVisitor visitor) {
    Collection<DfaMemoryState> initialStates = createInitialStates(psiBlock, visitor);
    return initialStates == null ? RunnerResult.NOT_APPLICABLE : analyzeMethod(psiBlock, visitor, false, initialStates);
  }
  
  public final RunnerResult analyzeMethod(@NotNull PsiElement psiBlock,
                                          InstructionVisitor visitor,
                                          boolean ignoreAssertions,
                                          @NotNull Collection<DfaMemoryState> initialStates) {
    try {
      prepareAnalysis(psiBlock, initialStates);

      final ControlFlow flow = createControlFlowAnalyzer().buildControlFlow(psiBlock, ignoreAssertions);
      if (flow == null) return RunnerResult.NOT_APPLICABLE;

      int endOffset = flow.getInstructionCount();
      myInstructions = flow.getInstructions();
      myFields = flow.getFields();
      myNestedClosures.clear();
      
      Set<Instruction> joinInstructions = ContainerUtil.newHashSet();
      for (Instruction instruction : myInstructions) {
        if (instruction instanceof GotoInstruction) {
          joinInstructions.add(myInstructions[((GotoInstruction)instruction).getOffset()]);
        } else if (instruction instanceof ConditionalGotoInstruction) {
          joinInstructions.add(myInstructions[((ConditionalGotoInstruction)instruction).getOffset()]);
        } else if (instruction instanceof GosubInstruction) {
          joinInstructions.add(myInstructions[((GosubInstruction)instruction).getSubprogramOffset()]);
        }
      }

      if (LOG.isDebugEnabled()) {
        LOG.debug("Analyzing code block: " + psiBlock.getText());
        for (int i = 0; i < myInstructions.length; i++) {
          Instruction instruction = myInstructions[i];
          LOG.debug(i + ": " + instruction.toString());
        }
      }

      Integer tooExpensiveHash = psiBlock.getUserData(TOO_EXPENSIVE_HASH);
      if (tooExpensiveHash != null && tooExpensiveHash == psiBlock.getText().hashCode()) {
        LOG.debug("Too complex because hasn't changed since being too complex already");
        return RunnerResult.TOO_COMPLEX;
      }

      final StateQueue queue = new StateQueue();
      for (final DfaMemoryState initialState : initialStates) {
        queue.offer(new DfaInstructionState(myInstructions[0], initialState));
      }

      MultiMapBasedOnSet<BranchingInstruction, DfaMemoryState> processedStates = new MultiMapBasedOnSet<BranchingInstruction, DfaMemoryState>();
      MultiMapBasedOnSet<BranchingInstruction, DfaMemoryState> incomingStates = new MultiMapBasedOnSet<BranchingInstruction, DfaMemoryState>();

      WorkingTimeMeasurer measurer = new WorkingTimeMeasurer(shouldCheckTimeLimit() ? ourTimeLimit : ourTimeLimit * 42);
      int count = 0;
      while (!queue.isEmpty()) {
        for (DfaInstructionState instructionState : queue.getNextInstructionStates(joinInstructions)) {
          if (count++ % 1024 == 0 && measurer.isTimeOver()) {
            LOG.debug("Too complex because the analysis took too long");
            psiBlock.putUserData(TOO_EXPENSIVE_HASH, psiBlock.getText().hashCode());
            return RunnerResult.TOO_COMPLEX;
          }
          ProgressManager.checkCanceled();

          if (LOG.isDebugEnabled()) {
            LOG.debug(instructionState.toString());
          }
          //System.out.println(instructionState.toString());

          Instruction instruction = instructionState.getInstruction();

          if (instruction instanceof BranchingInstruction) {
            BranchingInstruction branching = (BranchingInstruction)instruction;
            if (processedStates.get(branching).contains(instructionState.getMemoryState())) {
              continue;
            }
            if (processedStates.get(branching).size() > MAX_STATES_PER_BRANCH) {
              LOG.debug("Too complex because too many different possible states");
              return RunnerResult.TOO_COMPLEX; // Too complex :(
            }
            processedStates.putValue(branching, instructionState.getMemoryState().createCopy());
          }

          DfaInstructionState[] after = acceptInstruction(visitor, instructionState);
          for (DfaInstructionState state : after) {
            Instruction nextInstruction = state.getInstruction();
            if (nextInstruction.getIndex() >= endOffset) {
              continue;
            }
            if (nextInstruction instanceof BranchingInstruction) {
              BranchingInstruction branching = (BranchingInstruction)nextInstruction;
              if (processedStates.get(branching).contains(state.getMemoryState()) || 
                  incomingStates.get(branching).contains(state.getMemoryState())) {
                continue;
              }
              incomingStates.putValue(branching, state.getMemoryState().createCopy());
            }
            queue.offer(state);
          }
        }
      }

      psiBlock.putUserData(TOO_EXPENSIVE_HASH, null);
      LOG.debug("Analysis ok");
      return RunnerResult.OK;
    }
    catch (ArrayIndexOutOfBoundsException e) {
      LOG.error(psiBlock.getText(), e); // TODO fix in better times
      return RunnerResult.ABORTED;
    }
    catch (EmptyStackException e) {
      if (LOG.isDebugEnabled()) {
        LOG.error(e); // TODO fix in better times
      }
{'fraction_non_alphanumeric': 0.09201456990753712, 'fraction_numerical': 0.005603810591202018, 'mean_word_length': 3.370805780063679, 'pattern_counts': {'":': 2, '<': 29, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5329321', 'n_tokens_mistral': 4857, 'n_tokens_neox': 4711, 'n_words': 1110}