plugins/groovy/groovy-psi/src/org/jetbrains/plugins/groovy/lang/psi/dataFlow/DFAEngine.java

/*
 * Copyright 2000-2014 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 org.jetbrains.plugins.groovy.lang.psi.dataFlow;

import com.intellij.codeInspection.dataFlow.DataFlowRunner;
import com.intellij.codeInspection.dataFlow.WorkingTimeMeasurer;
import com.intellij.openapi.progress.ProgressManager;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;
import org.jetbrains.plugins.groovy.lang.psi.controlFlow.CallEnvironment;
import org.jetbrains.plugins.groovy.lang.psi.controlFlow.CallInstruction;
import org.jetbrains.plugins.groovy.lang.psi.controlFlow.ControlFlowBuilderUtil;
import org.jetbrains.plugins.groovy.lang.psi.controlFlow.Instruction;

import java.util.*;

/**
 * @author ven
 */
public class DFAEngine<E> {
  private static final long ourTimeLimit = DataFlowRunner.ourTimeLimit;

  private final Instruction[] myFlow;

  private final DfaInstance<E> myDfa;
  private final Semilattice<E> mySemilattice;

  public DFAEngine(Instruction[] flow, DfaInstance<E> dfa, Semilattice<E> semilattice) {
    myFlow = flow;
    myDfa = dfa;
    mySemilattice = semilattice;
  }

  private static class MyCallEnvironment implements CallEnvironment {
    ArrayList<Deque<CallInstruction>> myEnv;

    private MyCallEnvironment(int instructionNum) {
      myEnv = new ArrayList<Deque<CallInstruction>>(instructionNum);
      for (int i = 0; i < instructionNum; i++) {
        myEnv.add(new ArrayDeque<CallInstruction>());
      }
    }

    @Override
    public Deque<CallInstruction> callStack(Instruction instruction) {
      return myEnv.get(instruction.num());
    }

    @Override
    public void update(Deque<CallInstruction> callStack, Instruction instruction) {
      myEnv.set(instruction.num(), callStack);
    }
  }

  @NotNull
  public ArrayList<E> performForceDFA() {
    ArrayList<E> result = performDFA(false);
    assert result != null;
    return result;
  }

  @Nullable
  public ArrayList<E> performDFAWithTimeout() {
    return performDFA(true);
  }

  @Nullable
  private ArrayList<E> performDFA(boolean timeout) {
    WorkingTimeMeasurer measurer = new WorkingTimeMeasurer(ourTimeLimit);

    ArrayList<E> info = new ArrayList<E>(myFlow.length);
    CallEnvironment env = new MyCallEnvironment(myFlow.length);
    for (int i = 0; i < myFlow.length; i++) {
      info.add(myDfa.initial());
    }

    boolean[] visited = new boolean[myFlow.length];

    final boolean forward = myDfa.isForward();
    int[] order = ControlFlowBuilderUtil.postorder(myFlow); //todo for backward?
    int count = 0;
    for (int i = forward ? 0 : myFlow.length - 1; forward ? i < myFlow.length : i >= 0;) {
      Instruction instr = myFlow[order[i]];

      if (!visited[instr.num()]) {
        Queue<Instruction> workList = new LinkedList<Instruction>();

        workList.add(instr);
        visited[instr.num()] = true;

        while (!workList.isEmpty()) {
          count++;
          if (timeout && count % 512 == 0 && measurer.isTimeOver()) return null;

          ProgressManager.checkCanceled();
          final Instruction curr = workList.remove();
          final int num = curr.num();
          final E oldE = info.get(num);
          E newE = join(curr, info, env);
          myDfa.fun(newE, curr);
          if (!mySemilattice.eq(newE, oldE)) {
            info.set(num, newE);
            for (Instruction next : getNext(curr, env)) {
              workList.add(next);
              visited[next.num()] = true;
            }
          }
        }
      }

      if (forward) i++;
      else i--;
    }


    return info;
  }

  private E join(Instruction instruction, ArrayList<E> info, CallEnvironment env) {
    final Iterable<? extends Instruction> prev = myDfa.isForward() ? instruction.predecessors(env) : instruction.successors(env);
    ArrayList<E> prevInfos = new ArrayList<E>();
    for (Instruction i : prev) {
      prevInfos.add(info.get(i.num()));
    }
    return mySemilattice.join(prevInfos);
  }

  private Iterable<? extends Instruction> getNext(Instruction curr, CallEnvironment env) {
    return myDfa.isForward() ? curr.successors(env) : curr.predecessors(env);
  }
}