platform/lang-impl/src/com/intellij/codeInsight/controlflow/ControlFlowBuilder.java

/*
 * Copyright 2000-2012 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.intellij.codeInsight.controlflow;

import com.intellij.codeInsight.controlflow.impl.ConditionalInstructionImpl;
import com.intellij.codeInsight.controlflow.impl.ControlFlowImpl;
import com.intellij.codeInsight.controlflow.impl.InstructionImpl;
import com.intellij.openapi.util.Pair;
import com.intellij.psi.PsiElement;
import com.intellij.psi.PsiElementVisitor;
import com.intellij.psi.util.PsiTreeUtil;
import com.intellij.util.containers.ContainerUtil;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.ArrayList;
import java.util.List;

/**
* @author oleg
*/
public class ControlFlowBuilder {
  // Here we store all the instructions
  public List<Instruction> instructions;

  // The last instruction
  public Instruction prevInstruction;

  // Here we store all the pending instructions with their scope
  public List<Pair<PsiElement, Instruction>> pending;

  // Number of instructions already added
  public int instructionCount;

  public ControlFlowBuilder() {
    instructions = ContainerUtil.newArrayList();
    pending = ContainerUtil.newArrayList();
    instructionCount = 0;
  }

  @Nullable
  public Instruction findInstructionByElement(final PsiElement element) {
    for (int i = instructions.size() - 1; i >= 0; i--) {
      final Instruction instruction = instructions.get(i);
      if (element.equals(instruction.getElement())) {
        return instruction;
      }
    }
    return null;
  }

  /**
   * Adds edge between 2 edges
   *
   * @param beginInstruction Begin of new edge
   * @param endInstruction   End of new edge
   */
  public void addEdge(final Instruction beginInstruction, final Instruction endInstruction) {
    if (beginInstruction == null || endInstruction == null) {
      return;
    }
    if (!beginInstruction.allSucc().contains(endInstruction)) {
      beginInstruction.allSucc().add(endInstruction);
    }

    if (!endInstruction.allPred().contains(beginInstruction)) {
      endInstruction.allPred().add(beginInstruction);
    }
  }

  /**
   * Add new node and set prev instruction pointing to this instruction
   *
   * @param instruction new instruction
   */
  public void addNode(final Instruction instruction) {
    instructions.add(instruction);
    if (prevInstruction != null) {
      addEdge(prevInstruction, instruction);
    }
    prevInstruction = instruction;
  }

  /**
   * Stops control flow, used for break, next, redo
   */
  public void flowAbrupted() {
    prevInstruction = null;
  }

  /**
   * Adds pending edge in pendingScope
   *
   * @param pendingScope Scope for instruction
   * @param instruction  "Last" pending instruction
   */
  public void addPendingEdge(@Nullable final PsiElement pendingScope, final Instruction instruction) {
    if (instruction == null) {
      return;
    }

    int i = 0;
    // another optimization! Place pending before first scope, not contained in pendingScope
    // the same logic is used in checkPending
    if (pendingScope != null) {
      for (; i < pending.size(); i++) {
        final Pair<PsiElement, Instruction> pair = pending.get(i);
        final PsiElement scope = pair.getFirst();
        if (scope == null) {
          continue;
        }
        if (!PsiTreeUtil.isAncestor(scope, pendingScope, true)) {
          break;
        }
      }
    }
    pending.add(i, Pair.create(pendingScope, instruction));
  }

  /**
   * Creates edges from the pending list to the specified instruction.
   *
   * @param instruction target instruction for pending edges
   */
  public void checkPending(@NotNull final Instruction instruction) {
    final PsiElement element = instruction.getElement();
    if (element == null) {
      // if element is null (fake element, we just process all pending)
      for (Pair<PsiElement, Instruction> pair : pending) {
        addEdge(pair.getSecond(), instruction);
      }
      pending.clear();
    }
    else {
      // else we just process all the pending with scope containing in element
      // reverse order is just an optimization
      for (int i = pending.size() - 1; i >= 0; i--) {
        final Pair<PsiElement, Instruction> pair = pending.get(i);
        final PsiElement scopeWhenToAdd = pair.getFirst();
        if (scopeWhenToAdd == null) {
          continue;
        }
        if (!PsiTreeUtil.isAncestor(scopeWhenToAdd, element, false)) {
          addEdge(pair.getSecond(), instruction);
          pending.remove(i);
        }
        else {
          break;
        }
      }
    }
  }

  /**
   * Creates instruction for given element, and adds it to myInstructionsStack
   *
   * @param element Element to create instruction for
   * @return new instruction
   */
  public Instruction startNode(@Nullable final PsiElement element) {
    final Instruction instruction = new InstructionImpl(this, element);
    addNode(instruction);
    checkPending(instruction);
    return instruction;
  }

  /**
   * Creates conditional instruction for given element, and adds it to myInstructionsStack
   *
   * @param element Element to create instruction for
   * @return new instruction
   */
  public Instruction startConditionalNode(final PsiElement element, final PsiElement condition, final boolean result) {
    final ConditionalInstruction instruction = new ConditionalInstructionImpl(this, element, condition, result);
    addNode(instruction);
    checkPending(instruction);
    return instruction;
  }

  public ControlFlow build(final PsiElementVisitor visitor, final PsiElement element) {
    // create start pseudo node
    startNode(null);

    element.acceptChildren(visitor);

    // create end pseudo node and close all pending edges
    checkPending(startNode(null));

    final List<Instruction> result = instructions;
    return new ControlFlowImpl(result.toArray(new Instruction[result.size()]));
  }


  public interface PendingProcessor {
    void process(PsiElement pendingScope, Instruction instruction);
  }

  public void processPending(final PendingProcessor processor) {
    final List<Pair<PsiElement, Instruction>> pending = this.pending;
    this.pending = new ArrayList<Pair<PsiElement, Instruction>>();
    for (Pair<PsiElement, Instruction> pair : pending) {
      processor.process(pair.getFirst(), pair.getSecond());
    }
  }
}