java/java-analysis-impl/src/com/intellij/codeInspection/bytecodeAnalysis/Solver.java - platform/tools/idea - Git at Google

 /*
  * 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 com.intellij.codeInspection.bytecodeAnalysis;

 import com.intellij.util.ArrayFactory;
 import com.intellij.util.ArrayUtil;
 import org.jetbrains.annotations.NotNull;
 import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException;

 import java.util.*;

 final class ELattice<T extends Enum<T>> {
   final T bot;
   final T top;

   ELattice(T bot, T top) {
     this.bot = bot;
     this.top = top;
   }

   final T join(T x, T y) {
     if (x == bot) return y;
     if (y == bot) return x;
     if (x == y) return x;
     return top;
   }

   final T meet(T x, T y) {
     if (x == top) return y;
     if (y == top) return x;
     if (x == y) return x;
     return bot;
   }
 }


 class ResultUtil<Id, T extends Enum<T>> {
   private final ELattice<T> lattice;
   final T top;
   ResultUtil(ELattice<T> lattice) {
     this.lattice = lattice;
     top = lattice.top;
   }

   Result<Id, T> join(Result<Id, T> r1, Result<Id, T> r2) throws AnalyzerException {
     if (r1 instanceof Final && ((Final) r1).value == top) {
       return r1;
     }
     if (r2 instanceof Final && ((Final) r2).value == top) {
       return r2;
     }
     if (r1 instanceof Final && r2 instanceof Final) {
       return new Final<Id, T>(lattice.join(((Final<?, T>) r1).value, ((Final<?, T>) r2).value));
     }
     if (r1 instanceof Final && r2 instanceof Pending) {
       Final<?, T> f1 = (Final<?, T>)r1;
       Pending<Id, T> pending = (Pending<Id, T>) r2;
       Set<Product<Id, T>> sum1 = new HashSet<Product<Id, T>>(pending.sum);
       sum1.add(new Product<Id, T>(f1.value, Collections.<Id>emptySet()));
       return new Pending<Id, T>(sum1);
     }
     if (r1 instanceof Pending && r2 instanceof Final) {
       Final<?, T> f2 = (Final<?, T>)r2;
       Pending<Id, T> pending = (Pending<Id, T>) r1;
       Set<Product<Id, T>> sum1 = new HashSet<Product<Id, T>>(pending.sum);
       sum1.add(new Product<Id, T>(f2.value, Collections.<Id>emptySet()));
       return new Pending<Id, T>(sum1);
     }
     Pending<Id, T> pending1 = (Pending<Id, T>) r1;
     Pending<Id, T> pending2 = (Pending<Id, T>) r2;
     Set<Product<Id, T>> sum = new HashSet<Product<Id, T>>();
     sum.addAll(pending1.sum);
     sum.addAll(pending2.sum);
     checkLimit(sum);
     return new Pending<Id, T>(sum);
   }

   private void checkLimit(Set<Product<Id, T>> sum) throws AnalyzerException {
     int size = 0;
     for (Product<Id, T> prod : sum) {
       size += prod.ids.size();
     }
     if (size > Analysis.EQUATION_SIZE_LIMIT) {
       throw new AnalyzerException(null, "Equation size is too big");
     }
   }
 }

 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;

   Product(@NotNull V value, @NotNull Set<K> 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;

     Product product = (Product)o;

     if (!ids.equals(product.ids)) return false;
     if (!value.equals(product.value)) return false;

     return true;
   }

   @Override
   public int hashCode() {
     int result = value.hashCode();
     result = 31 * result + ids.hashCode();
     return result;
   }
 }

 interface Result<Id, T> {}
 final class Final<Id, T> implements Result<Id, T> {
   final T value;
   Final(T value) {
     this.value = value;
   }

   @Override
   public String toString() {
     return "Final{" + "value=" + value + '}';
   }
 }

 final class Pending<Id, T> implements Result<Id, T> {
   final Set<Product<Id, T>> sum;

   Pending(Set<Product<Id, T>> sum) {
     this.sum = sum;
   }

 }

 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 + '}';
   }
 }

 final class CoreHKey {
   @NotNull
   final byte[] key;
   final int dirKey;

   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 == null || getClass() != o.getClass()) 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() {
     int result = Arrays.hashCode(key);
     result = 31 * result + dirKey;
     return result;
   }
 }

 final class Solver {

   private final ELattice<Value> lattice;
   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>();

   private final HResultUtil resultUtil;
   private final HashMap<CoreHKey, HEquation> equations = new HashMap<CoreHKey, HEquation>();
   private final Value unstableValue;

   Solver(ELattice<Value> lattice, Value unstableValue) {
     this.lattice = lattice;
     this.unstableValue = unstableValue;
     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 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 {
         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 HashSet<HKey>();
               dependencies.put(trigger, set);
             }
             set.add(equation.key);
           }
           pending.put(equation.key, pendResult1);
         }
       }
     }
   }

   HashMap<HKey, Value> solve() {
     for (HEquation hEquation : equations.values()) {
       queueEquation(hEquation);
     }
     while (!moving.empty()) {
       HKey id = moving.pop();
       Value value = solved.get(id);

       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, unstableValue};

       for (int i = 0; i < pIds.length; i++) {
         HKey pId = pIds[i];
         Value pVal = pVals[i];
         HashSet<HKey> dIds = dependencies.get(pId);
         if (dIds == null) {
           continue;
         }
         for (HKey dId : dIds) {
           HPending pend = pending.remove(dId);
           if (pend != null) {
             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, (HPending)pend1);
             }
           }
         }
       }
     }
     pending.clear();
     return solved;
   }

   // substitute id -> value into pending
   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);
       }
     }
     return normalize(sum);
   }

   @NotNull HResult normalize(@NotNull HComponent[] sum) {
     Value acc = lattice.bot;
     boolean computableNow = true;
     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 HFinal(acc) : new HPending(sum);
   }

 }
	/*
	* 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 com.intellij.codeInspection.bytecodeAnalysis;

	import com.intellij.util.ArrayFactory;
	import com.intellij.util.ArrayUtil;
	import org.jetbrains.annotations.NotNull;
	import org.jetbrains.org.objectweb.asm.tree.analysis.AnalyzerException;

	import java.util.*;

	final class ELattice<T extends Enum<T>> {
	final T bot;
	final T top;

	ELattice(T bot, T top) {
	this.bot = bot;
	this.top = top;
	}

	final T join(T x, T y) {
	if (x == bot) return y;
	if (y == bot) return x;
	if (x == y) return x;
	return top;
	}

	final T meet(T x, T y) {
	if (x == top) return y;
	if (y == top) return x;
	if (x == y) return x;
	return bot;
	}
	}


	class ResultUtil<Id, T extends Enum<T>> {
	private final ELattice<T> lattice;
	final T top;
	ResultUtil(ELattice<T> lattice) {
	this.lattice = lattice;
	top = lattice.top;
	}

	Result<Id, T> join(Result<Id, T> r1, Result<Id, T> r2) throws AnalyzerException {
	if (r1 instanceof Final && ((Final) r1).value == top) {
	return r1;
	}
	if (r2 instanceof Final && ((Final) r2).value == top) {
	return r2;
	}
	if (r1 instanceof Final && r2 instanceof Final) {
	return new Final<Id, T>(lattice.join(((Final<?, T>) r1).value, ((Final<?, T>) r2).value));
	}
	if (r1 instanceof Final && r2 instanceof Pending) {
	Final<?, T> f1 = (Final<?, T>)r1;
	Pending<Id, T> pending = (Pending<Id, T>) r2;
	Set<Product<Id, T>> sum1 = new HashSet<Product<Id, T>>(pending.sum);
	sum1.add(new Product<Id, T>(f1.value, Collections.<Id>emptySet()));
	return new Pending<Id, T>(sum1);
	}
	if (r1 instanceof Pending && r2 instanceof Final) {
	Final<?, T> f2 = (Final<?, T>)r2;
	Pending<Id, T> pending = (Pending<Id, T>) r1;
	Set<Product<Id, T>> sum1 = new HashSet<Product<Id, T>>(pending.sum);
	sum1.add(new Product<Id, T>(f2.value, Collections.<Id>emptySet()));
	return new Pending<Id, T>(sum1);
	}
	Pending<Id, T> pending1 = (Pending<Id, T>) r1;
	Pending<Id, T> pending2 = (Pending<Id, T>) r2;
	Set<Product<Id, T>> sum = new HashSet<Product<Id, T>>();
	sum.addAll(pending1.sum);
	sum.addAll(pending2.sum);
	checkLimit(sum);
	return new Pending<Id, T>(sum);
	}

	private void checkLimit(Set<Product<Id, T>> sum) throws AnalyzerException {
	int size = 0;
	for (Product<Id, T> prod : sum) {
	size += prod.ids.size();
	}
	if (size > Analysis.EQUATION_SIZE_LIMIT) {
	throw new AnalyzerException(null, "Equation size is too big");
	}
	}
	}

	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;

	Product(@NotNull V value, @NotNull Set<K> 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;

	Product product = (Product)o;

	if (!ids.equals(product.ids)) return false;
	if (!value.equals(product.value)) return false;

	return true;
	}

	@Override
	public int hashCode() {
	int result = value.hashCode();
	result = 31 * result + ids.hashCode();
	return result;
	}
	}

	interface Result<Id, T> {}
	final class Final<Id, T> implements Result<Id, T> {
	final T value;
	Final(T value) {
	this.value = value;
	}

	@Override
	public String toString() {
	return "Final{" + "value=" + value + '}';
	}
	}

	final class Pending<Id, T> implements Result<Id, T> {
	final Set<Product<Id, T>> sum;

	Pending(Set<Product<Id, T>> sum) {
	this.sum = sum;
	}

	}

	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 + '}';
	}
	}

	final class CoreHKey {
	@NotNull
	final byte[] key;
	final int dirKey;

	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 == null \|\| getClass() != o.getClass()) 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() {
	int result = Arrays.hashCode(key);
	result = 31 * result + dirKey;
	return result;
	}
	}

	final class Solver {

	private final ELattice<Value> lattice;
	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>();

	private final HResultUtil resultUtil;
	private final HashMap<CoreHKey, HEquation> equations = new HashMap<CoreHKey, HEquation>();
	private final Value unstableValue;

	Solver(ELattice<Value> lattice, Value unstableValue) {
	this.lattice = lattice;
	this.unstableValue = unstableValue;
	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 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 {
	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 HashSet<HKey>();
	dependencies.put(trigger, set);
	}
	set.add(equation.key);
	}
	pending.put(equation.key, pendResult1);
	}
	}
	}
	}

	HashMap<HKey, Value> solve() {
	for (HEquation hEquation : equations.values()) {
	queueEquation(hEquation);
	}
	while (!moving.empty()) {
	HKey id = moving.pop();
	Value value = solved.get(id);

	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, unstableValue};

	for (int i = 0; i < pIds.length; i++) {
	HKey pId = pIds[i];
	Value pVal = pVals[i];
	HashSet<HKey> dIds = dependencies.get(pId);
	if (dIds == null) {
	continue;
	}
	for (HKey dId : dIds) {
	HPending pend = pending.remove(dId);
	if (pend != null) {
	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, (HPending)pend1);
	}
	}
	}
	}
	}
	pending.clear();
	return solved;
	}

	// substitute id -> value into pending
	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);
	}
	}
	return normalize(sum);
	}

	@NotNull HResult normalize(@NotNull HComponent[] sum) {
	Value acc = lattice.bot;
	boolean computableNow = true;
	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 HFinal(acc) : new HPending(sum);
	}

	}