| /* |
| * 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: 9:40:01 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.Instruction; |
| import com.intellij.openapi.util.Pair; |
| import com.intellij.util.Function; |
| import com.intellij.util.containers.ContainerUtil; |
| import com.intellij.util.containers.MultiMap; |
| import org.jetbrains.annotations.NotNull; |
| |
| import java.util.*; |
| |
| public class DfaInstructionState implements Comparable<DfaInstructionState> { |
| public static final DfaInstructionState[] EMPTY_ARRAY = new DfaInstructionState[0]; |
| private final DfaMemoryState myBeforeMemoryState; |
| private final Instruction myInstruction; |
| |
| public DfaInstructionState(@NotNull Instruction myInstruction, @NotNull DfaMemoryState myBeforeMemoryState) { |
| this.myBeforeMemoryState = myBeforeMemoryState; |
| this.myInstruction = myInstruction; |
| } |
| |
| @NotNull |
| public Instruction getInstruction() { |
| return myInstruction; |
| } |
| |
| @NotNull |
| public DfaMemoryState getMemoryState() { |
| return myBeforeMemoryState; |
| } |
| |
| public String toString() { |
| return getInstruction().getIndex() + " " + getInstruction() + ": " + getMemoryState().toString(); |
| } |
| |
| @Override |
| public int compareTo(@NotNull DfaInstructionState o) { |
| return myInstruction.getIndex() - o.myInstruction.getIndex(); |
| } |
| } |
| |
| class StateQueue { |
| private final PriorityQueue<DfaInstructionState> myQueue = new PriorityQueue<DfaInstructionState>(); |
| private final Set<Pair<Instruction, DfaMemoryState>> mySet = ContainerUtil.newHashSet(); |
| |
| void offer(DfaInstructionState state) { |
| if (mySet.add(Pair.create(state.getInstruction(), state.getMemoryState()))) { |
| myQueue.offer(state); |
| } |
| } |
| |
| boolean isEmpty() { |
| return myQueue.isEmpty(); |
| } |
| |
| List<DfaInstructionState> getNextInstructionStates(Set<Instruction> joinInstructions) { |
| DfaInstructionState state = myQueue.poll(); |
| final Instruction instruction = state.getInstruction(); |
| mySet.remove(Pair.create(instruction, state.getMemoryState())); |
| |
| DfaInstructionState next = myQueue.peek(); |
| if (next == null || next.compareTo(state) != 0) return Collections.singletonList(state); |
| |
| List<DfaMemoryStateImpl> memoryStates = ContainerUtil.newArrayList(); |
| memoryStates.add((DfaMemoryStateImpl)state.getMemoryState()); |
| while (!myQueue.isEmpty() && myQueue.peek().compareTo(state) == 0) { |
| DfaMemoryState anotherState = myQueue.poll().getMemoryState(); |
| mySet.remove(Pair.create(instruction, anotherState)); |
| memoryStates.add((DfaMemoryStateImpl)anotherState); |
| } |
| |
| if (memoryStates.size() > 1 && joinInstructions.contains(instruction)) { |
| MultiMap<Object, DfaMemoryStateImpl> groups = MultiMap.create(); |
| for (DfaMemoryStateImpl memoryState : memoryStates) { |
| groups.putValue(memoryState.getSuperficialKey(), memoryState); |
| } |
| |
| memoryStates = ContainerUtil.newArrayList(); |
| for (Map.Entry<Object, Collection<DfaMemoryStateImpl>> entry : groups.entrySet()) { |
| memoryStates.addAll(mergeGroup((List<DfaMemoryStateImpl>)entry.getValue())); |
| } |
| |
| } |
| |
| return ContainerUtil.map(memoryStates, new Function<DfaMemoryStateImpl, DfaInstructionState>() { |
| @Override |
| public DfaInstructionState fun(DfaMemoryStateImpl state) { |
| return new DfaInstructionState(instruction, state); |
| } |
| }); |
| } |
| |
| private static List<DfaMemoryStateImpl> mergeGroup(List<DfaMemoryStateImpl> group) { |
| if (group.size() < 2) { |
| return group; |
| } |
| |
| StateMerger merger = new StateMerger(); |
| while (true) { |
| List<DfaMemoryStateImpl> nextStates = merger.mergeByFacts(group); |
| if (nextStates == null) nextStates = merger.mergeByNullability(group); |
| if (nextStates == null) nextStates = merger.mergeByUnknowns(group); |
| if (nextStates == null) break; |
| group = nextStates; |
| } |
| return group; |
| } |
| } |