summaryrefslogtreecommitdiff
path: root/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java
diff options
context:
space:
mode:
Diffstat (limited to 'java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java')
-rw-r--r--java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java360
1 files changed, 140 insertions, 220 deletions
diff --git a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java
index 1dec1de8a606..21e749e12b29 100644
--- a/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java
+++ b/java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java
@@ -15,10 +15,8 @@
*/
package com.intellij.codeInspection.bytecodeAnalysis;
-import com.intellij.util.containers.LongStack;
-import gnu.trove.TLongHashSet;
-import gnu.trove.TLongIterator;
-import gnu.trove.TLongObjectHashMap;
+import com.intellij.util.ArrayFactory;
+import com.intellij.util.ArrayUtil;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException;
@@ -48,88 +46,6 @@ final class ELattice<T extends Enum<T>> {
}
}
-// component specialized for ints
-final class IntIdComponent {
- Value value;
- final long[] ids;
-
- IntIdComponent(Value value, long[] ids) {
- this.value = value;
- this.ids = ids;
- }
-
- @Override
- public boolean equals(Object o) {
- if (this == o) return true;
- if (o == null || getClass() != o.getClass()) return false;
-
- IntIdComponent that = (IntIdComponent)o;
-
- if (!Arrays.equals(ids, that.ids)) return false;
- if (value != that.value) return false;
-
- return true;
- }
-
- @Override
- public int hashCode() {
- return value.ordinal() + Arrays.hashCode(ids);
- }
-
- public boolean remove(long id) {
- return IdUtils.remove(ids, id);
- }
-
- public boolean isEmpty() {
- return IdUtils.isEmpty(ids);
- }
-
- IntIdComponent copy() {
- return new IntIdComponent(value, ids.clone());
- }
-}
-
-class IdUtils {
- // removed value
- static final long nullId = 0;
-
- static boolean contains(long[] ids, int id) {
- for (long id1 : ids) {
- if (id1 == id) return true;
- }
-
- return false;
- }
-
- static boolean isEmpty(long[] ids) {
- for (long id : ids) {
- if (id != nullId) return false;
- }
- return true;
- }
-
- static IntIdComponent[] toArray(Collection<IntIdComponent> set) {
- IntIdComponent[] result = new IntIdComponent[set.size()];
- int i = 0;
- for (IntIdComponent intIdComponent : set) {
- result[i] = intIdComponent;
- i++;
- }
-
- return result;
- }
-
- static boolean remove(long[] ids, long id) {
- boolean removed = false;
- for (int i = 0; i < ids.length; i++) {
- if (ids[i] == id) {
- ids[i] = nullId;
- removed = true;
- }
- }
- return removed;
- }
-}
class ResultUtil<Id, T extends Enum<T>> {
private final ELattice<T> lattice;
@@ -183,6 +99,55 @@ class ResultUtil<Id, T extends Enum<T>> {
}
}
+class HResultUtil {
+ private static final HKey[] EMPTY_PRODUCT = new HKey[0];
+ private static final ArrayFactory<HComponent> HCOMPONENT_ARRAY_FACTORY = new ArrayFactory<HComponent>() {
+ @NotNull
+ @Override
+ public HComponent[] create(int count) {
+ return new HComponent[count];
+ }
+ };
+ private final ELattice<Value> lattice;
+ final Value top;
+
+ HResultUtil(ELattice<Value> lattice) {
+ this.lattice = lattice;
+ top = lattice.top;
+ }
+
+ HResult join(HResult r1, HResult r2) {
+ if (r1 instanceof HFinal && ((HFinal) r1).value == top) {
+ return r1;
+ }
+ if (r2 instanceof HFinal && ((HFinal) r2).value == top) {
+ return r2;
+ }
+ if (r1 instanceof HFinal && r2 instanceof HFinal) {
+ return new HFinal(lattice.join(((HFinal) r1).value, ((HFinal) r2).value));
+ }
+ if (r1 instanceof HFinal && r2 instanceof HPending) {
+ HFinal f1 = (HFinal)r1;
+ HPending pending = (HPending) r2;
+ HComponent[] delta = new HComponent[pending.delta.length + 1];
+ delta[0] = new HComponent(f1.value, EMPTY_PRODUCT);
+ System.arraycopy(pending.delta, 0, delta, 1, pending.delta.length);
+ return new HPending(delta);
+ }
+ if (r1 instanceof HPending && r2 instanceof HFinal) {
+ HFinal f2 = (HFinal)r2;
+ HPending pending = (HPending) r1;
+ HComponent[] delta = new HComponent[pending.delta.length + 1];
+ delta[0] = new HComponent(f2.value, EMPTY_PRODUCT);
+ System.arraycopy(pending.delta, 0, delta, 1, pending.delta.length);
+ return new HPending(delta);
+ }
+ HPending pending1 = (HPending) r1;
+ HPending pending2 = (HPending) r2;
+ return new HPending(ArrayUtil.mergeArrays(pending1.delta, pending2.delta, HCOMPONENT_ARRAY_FACTORY));
+ }
+}
+
final class Product<K, V> {
@NotNull final V value;
@NotNull final Set<K> ids;
@@ -235,195 +200,150 @@ final class Pending<Id, T> implements Result<Id, T> {
}
-interface IdResult {}
-// this just wrapper, no need for this really
-final class IdFinal implements IdResult {
- final Value value;
- public IdFinal(Value value) {
- this.value = value;
- }
-
- @Override
- public boolean equals(Object o) {
- if (this == o) return true;
- if (o == null || getClass() != o.getClass()) return false;
-
- IdFinal that = (IdFinal)o;
-
- if (value != that.value) return false;
-
- return true;
- }
-
- @Override
- public int hashCode() {
- return value.ordinal();
- }
+final class Solution<Id, Val> {
+ final Id id;
+ final Val value;
- @Override
- public String toString() {
- return super.toString();
+ Solution(Id id, Val value) {
+ this.id = id;
+ this.value = value;
}
}
-final class IdPending implements IdResult {
- final IntIdComponent[] delta;
-
- IdPending(IntIdComponent[] delta) {
- this.delta = delta;
- }
+final class Equation<Id, T> {
+ final Id id;
+ final Result<Id, T> rhs;
- @Override
- public boolean equals(Object o) {
- if (this == o) return true;
- if (!(o instanceof IdPending)) return false;
- IdPending pending = (IdPending)o;
- return Arrays.equals(delta, pending.delta);
+ Equation(Id id, Result<Id, T> rhs) {
+ this.id = id;
+ this.rhs = rhs;
}
@Override
- public int hashCode() {
- return Arrays.hashCode(delta);
- }
-
- IdPending copy() {
- IntIdComponent[] delta1 = new IntIdComponent[delta.length];
- for (int i = 0; i < delta.length; i++) {
- delta1[i] = delta[i].copy();
- }
- return new IdPending(delta1);
+ public String toString() {
+ return "Equation{" + "id=" + id + ", rhs=" + rhs + '}';
}
}
-final class IdEquation {
- final long id;
- final IdResult rhs;
+final class CoreHKey {
+ @NotNull
+ final byte[] key;
+ final int dirKey;
- IdEquation(long id, IdResult rhs) {
- this.id = id;
- this.rhs = rhs;
+ CoreHKey(@NotNull byte[] key, int dirKey) {
+ this.key = key;
+ this.dirKey = dirKey;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
- if (!(o instanceof IdEquation)) return false;
-
- IdEquation equation = (IdEquation)o;
+ if (o == null || getClass() != o.getClass()) return false;
- if (id != equation.id) return false;
- if (!rhs.equals(equation.rhs)) return false;
+ CoreHKey coreHKey = (CoreHKey)o;
+ if (dirKey != coreHKey.dirKey) return false;
+ if (!Arrays.equals(key, coreHKey.key)) return false;
return true;
}
@Override
public int hashCode() {
- return 31 * ((int)(id ^ (id >>> 32))) + rhs.hashCode();
- }
-}
-
-final class Solution<Id, Val> {
- final Id id;
- final Val value;
-
- Solution(Id id, Val value) {
- this.id = id;
- this.value = value;
- }
-}
-
-final class Equation<Id, T> {
- final Id id;
- final Result<Id, T> rhs;
-
- Equation(Id id, Result<Id, T> rhs) {
- this.id = id;
- this.rhs = rhs;
- }
-
- @Override
- public String toString() {
- return "Equation{" + "id=" + id + ", rhs=" + rhs + '}';
+ int result = Arrays.hashCode(key);
+ result = 31 * result + dirKey;
+ return result;
}
}
final class Solver {
- private int size = 0;
private final ELattice<Value> lattice;
- private final TLongObjectHashMap<TLongHashSet> dependencies = new TLongObjectHashMap<TLongHashSet>();
- private final TLongObjectHashMap<IdPending> pending = new TLongObjectHashMap<IdPending>();
- private final TLongObjectHashMap<Value> solved = new TLongObjectHashMap<Value>();
- private final LongStack moving = new LongStack();
+ private final HashMap<HKey, HashSet<HKey>> dependencies = new HashMap<HKey, HashSet<HKey>>();
+ private final HashMap<HKey, HPending> pending = new HashMap<HKey, HPending>();
+ private final HashMap<HKey, Value> solved = new HashMap<HKey, Value>();
+ private final Stack<HKey> moving = new Stack<HKey>();
- int getSize() {
- return size;
- }
+ private final HResultUtil resultUtil;
+ private final HashMap<CoreHKey, HEquation> equations = new HashMap<CoreHKey, HEquation>();
Solver(ELattice<Value> lattice) {
this.lattice = lattice;
+ resultUtil = new HResultUtil(lattice);
+ }
+
+ void addEquation(HEquation equation) {
+ HKey key = equation.key;
+ CoreHKey coreKey = new CoreHKey(key.key, key.dirKey);
+
+ HEquation previousEquation = equations.get(coreKey);
+ if (previousEquation == null) {
+ equations.put(coreKey, equation);
+ } else {
+ HKey joinKey = new HKey(coreKey.key, coreKey.dirKey, equation.key.stable && previousEquation.key.stable);
+ HResult joinResult = resultUtil.join(equation.result, previousEquation.result);
+ HEquation joinEquation = new HEquation(joinKey, joinResult);
+ equations.put(coreKey, joinEquation);
+ }
}
- void addEquation(IdEquation equation) {
- size ++;
- IdResult rhs = equation.rhs;
- if (rhs instanceof IdFinal) {
- solved.put(equation.id, ((IdFinal) rhs).value);
- moving.push(equation.id);
- } else if (rhs instanceof IdPending) {
- IdPending pendResult = ((IdPending)rhs).copy();
- IdResult norm = normalize(pendResult.delta);
- if (norm instanceof IdFinal) {
- solved.put(equation.id, ((IdFinal) norm).value);
- moving.push(equation.id);
+ void queueEquation(HEquation equation) {
+ HResult rhs = equation.result;
+ if (rhs instanceof HFinal) {
+ solved.put(equation.key, ((HFinal) rhs).value);
+ moving.push(equation.key);
+ } else if (rhs instanceof HPending) {
+ HPending pendResult = ((HPending)rhs).copy();
+ HResult norm = normalize(pendResult.delta);
+ if (norm instanceof HFinal) {
+ solved.put(equation.key, ((HFinal) norm).value);
+ moving.push(equation.key);
}
else {
- IdPending pendResult1 = ((IdPending)rhs).copy();
- for (IntIdComponent component : pendResult1.delta) {
- for (long trigger : component.ids) {
- TLongHashSet set = dependencies.get(trigger);
+ HPending pendResult1 = ((HPending)rhs).copy();
+ for (HComponent component : pendResult1.delta) {
+ for (HKey trigger : component.ids) {
+ HashSet<HKey> set = dependencies.get(trigger);
if (set == null) {
- set = new TLongHashSet();
+ set = new HashSet<HKey>();
dependencies.put(trigger, set);
}
- set.add(equation.id);
+ set.add(equation.key);
}
- pending.put(equation.id, pendResult1);
+ pending.put(equation.key, pendResult1);
}
}
}
}
- TLongObjectHashMap<Value> solve() {
+ HashMap<HKey, Value> solve() {
+ for (HEquation hEquation : equations.values()) {
+ queueEquation(hEquation);
+ }
while (!moving.empty()) {
- long id = moving.pop();
+ HKey id = moving.pop();
Value value = solved.get(id);
- boolean stable = id > 0;
- long[] pIds = stable ? new long[]{id, -id} : new long[]{-id, id};
- Value[] pVals = stable ? new Value[]{value, value} : new Value[]{value, lattice.top};
+ HKey[] pIds = id.stable ? new HKey[]{id, id.negate()} : new HKey[]{id.negate(), id};
+ Value[] pVals = id.stable ? new Value[]{value, value} : new Value[]{value, lattice.top};
for (int i = 0; i < pIds.length; i++) {
- long pId = pIds[i];
+ HKey pId = pIds[i];
Value pVal = pVals[i];
- TLongHashSet dIds = dependencies.get(pId);
+ HashSet<HKey> dIds = dependencies.get(pId);
if (dIds == null) {
continue;
}
- TLongIterator dIdsIterator = dIds.iterator();
- while (dIdsIterator.hasNext()) {
- long dId = dIdsIterator.next();
- IdPending pend = pending.remove(dId);
+ for (HKey dId : dIds) {
+ HPending pend = pending.remove(dId);
if (pend != null) {
- IdResult pend1 = substitute(pend, pId, pVal);
- if (pend1 instanceof IdFinal) {
- IdFinal fi = (IdFinal)pend1;
+ HResult pend1 = substitute(pend, pId, pVal);
+ if (pend1 instanceof HFinal) {
+ HFinal fi = (HFinal)pend1;
solved.put(dId, fi.value);
moving.push(dId);
}
else {
- pending.put(dId, (IdPending)pend1);
+ pending.put(dId, (HPending)pend1);
}
}
}
@@ -434,9 +354,9 @@ final class Solver {
}
// substitute id -> value into pending
- IdResult substitute(IdPending pending, long id, Value value) {
- IntIdComponent[] sum = pending.delta;
- for (IntIdComponent intIdComponent : sum) {
+ HResult substitute(@NotNull HPending pending, @NotNull HKey id, @NotNull Value value) {
+ HComponent[] sum = pending.delta;
+ for (HComponent intIdComponent : sum) {
if (intIdComponent.remove(id)) {
intIdComponent.value = lattice.meet(intIdComponent.value, value);
}
@@ -444,17 +364,17 @@ final class Solver {
return normalize(sum);
}
- IdResult normalize(IntIdComponent[] sum) {
+ @NotNull HResult normalize(@NotNull HComponent[] sum) {
Value acc = lattice.bot;
boolean computableNow = true;
- for (IntIdComponent prod : sum) {
+ for (HComponent prod : sum) {
if (prod.isEmpty() || prod.value == lattice.bot) {
acc = lattice.join(acc, prod.value);
} else {
computableNow = false;
}
}
- return (acc == lattice.top || computableNow) ? new IdFinal(acc) : new IdPending(sum);
+ return (acc == lattice.top || computableNow) ? new HFinal(acc) : new HPending(sum);
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-23 22:29:15 +0000