Cleanup: NotNull/Nullable
[idea/community.git] / java / java-analysis-impl / src / com / intellij / codeInspection / dataFlow / LoopAnalyzer.java
1 /*
2  * Copyright 2000-2015 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.codeInspection.dataFlow;
17
18 import com.intellij.codeInspection.dataFlow.instructions.ConditionalGotoInstruction;
19 import com.intellij.codeInspection.dataFlow.instructions.ControlTransferInstruction;
20 import com.intellij.codeInspection.dataFlow.instructions.GotoInstruction;
21 import com.intellij.codeInspection.dataFlow.instructions.Instruction;
22 import com.intellij.util.ArrayUtil;
23 import com.intellij.util.containers.EmptyIterator;
24 import com.intellij.util.graph.DFSTBuilder;
25 import com.intellij.util.graph.Graph;
26 import gnu.trove.TIntArrayList;
27 import gnu.trove.TIntObjectHashMap;
28 import gnu.trove.TIntProcedure;
29 import org.jetbrains.annotations.NotNull;
30
31 import java.util.*;
32
33 class LoopAnalyzer {
34   private static class MyGraph implements Graph<Instruction> {
35     @NotNull private final ControlFlow myFlow;
36     private final Instruction[] myInstructions;
37     private final TIntObjectHashMap<int[]> myIns = new TIntObjectHashMap<>();
38
39     private MyGraph(@NotNull ControlFlow flow) {
40       myFlow = flow;
41       myInstructions = flow.getInstructions();
42       for (Instruction instruction : myInstructions) {
43         int fromIndex = instruction.getIndex();
44         int[] to = getSuccessorIndices(fromIndex, myInstructions);
45         for (int toIndex : to) {
46           int[] froms = myIns.get(toIndex);
47           if (froms == null) {
48             froms = new int[]{fromIndex};
49             myIns.put(toIndex, froms);
50           }
51           else {
52             froms = ArrayUtil.append(froms, fromIndex);
53             myIns.put(toIndex, froms);
54           }
55         }
56       }
57     }
58
59     @NotNull
60     @Override
61     public Collection<Instruction> getNodes() {
62       return Arrays.asList(myFlow.getInstructions());
63     }
64
65     @NotNull
66     @Override
67     public Iterator<Instruction> getIn(Instruction n) {
68       int[] ins = myIns.get(n.getIndex());
69       return indicesToInstructions(ins);
70     }
71
72     @NotNull
73     @Override
74     public Iterator<Instruction> getOut(Instruction instruction) {
75       int fromIndex = instruction.getIndex();
76       int[] next = getSuccessorIndices(fromIndex, myInstructions);
77       return indicesToInstructions(next);
78     }
79
80     @NotNull
81     private Iterator<Instruction> indicesToInstructions(int[] next) {
82       if (next == null) return EmptyIterator.getInstance();
83       List<Instruction> out = new ArrayList<>(next.length);
84       for (int i : next) {
85         out.add(myInstructions[i]);
86       }
87       return out.iterator();
88     }
89   }
90
91
92
93   static int[] calcInLoop(ControlFlow controlFlow) {
94     final int[] loop = new int[controlFlow.getInstructionCount()]; // loop[i] = loop number(strongly connected component number) of i-th instruction or 0 if outside loop
95
96     MyGraph graph = new MyGraph(controlFlow);
97     final DFSTBuilder<Instruction> builder = new DFSTBuilder<>(graph);
98     TIntArrayList sccs = builder.getSCCs();
99     sccs.forEach(new TIntProcedure() {
100       private int myTNumber;
101       private int component;
102
103       @Override
104       public boolean execute(int size) {
105         int value = size > 1 ? ++component : 0;
106         for (int i = 0; i < size; i++) {
107           Instruction instruction = builder.getNodeByTNumber(myTNumber + i);
108           loop[instruction.getIndex()] = value;
109         }
110         myTNumber += size;
111         return true;
112       }
113     });
114
115     return loop;
116   }
117
118   @NotNull
119   static int[] getSuccessorIndices(int i, Instruction[] myInstructions) {
120     Instruction instruction = myInstructions[i];
121     if (instruction instanceof GotoInstruction) {
122       return new int[]{((GotoInstruction)instruction).getOffset()};
123     }
124     if (instruction instanceof ControlTransferInstruction) {
125       return ArrayUtil.toIntArray(((ControlTransferInstruction)instruction).getPossibleTargetIndices());
126     }
127     if (instruction instanceof ConditionalGotoInstruction) {
128       int offset = ((ConditionalGotoInstruction)instruction).getOffset();
129       if (offset != i+1) {
130         return new int[]{i + 1, offset};
131       }
132     }
133     return i == myInstructions.length-1 ? ArrayUtil.EMPTY_INT_ARRAY : new int[]{i + 1};
134   }
135
136
137 }