java/java-psi-impl/src/com/intellij/psi/controlFlow/DefUseUtil.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.psi.controlFlow;

 import com.intellij.openapi.diagnostic.Logger;
 import com.intellij.openapi.progress.ProgressManager;
 import com.intellij.psi.*;
 import com.intellij.psi.util.PsiTreeUtil;
 import com.intellij.psi.util.PsiUtil;
 import com.intellij.psi.util.PsiUtilCore;
 import com.intellij.util.containers.IntArrayList;
 import com.intellij.util.containers.Queue;
 import gnu.trove.THashSet;
 import org.jetbrains.annotations.NotNull;
 import org.jetbrains.annotations.Nullable;

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

 /**
  * @author max
  * Date: Mar 22, 2002
  */
 public class DefUseUtil {
   private static final Logger LOG = Logger.getInstance("#com.intellij.codeInspection.defUse.DefUseUtil");

   private DefUseUtil() { }

   public static class Info {
     private final PsiVariable myVariable;
     private final PsiElement myContext;
     private final boolean myIsRead;

     public Info(PsiVariable variable, PsiElement context, boolean read) {
       myVariable = variable;
       myContext = context;
       myIsRead = read;
     }

     public PsiVariable getVariable() {
       return myVariable;
     }

     public PsiElement getContext() {
       return myContext;
     }

     public boolean isRead() {
       return myIsRead;
     }
   }

   private static class InstructionState {
     private Set<PsiVariable> myVariablesUseArmed;
     private final int myInstructionIdx;
     private final IntArrayList myBackwardTraces;
     private boolean myIsVisited = false;

     public InstructionState(int instructionIdx) {
       myInstructionIdx = instructionIdx;
       myBackwardTraces = new IntArrayList();
       myVariablesUseArmed = null;
     }

     public void addBackwardTrace(int i) {
       myBackwardTraces.add(i);
     }

     public IntArrayList getBackwardTraces() {
       return myBackwardTraces;
     }

     public int getInstructionIdx() {
       return myInstructionIdx;
     }

     void mergeUseArmed(PsiVariable psiVariable) {
       touch();
       myVariablesUseArmed.add(psiVariable);
     }

     boolean mergeUseDisarmed(PsiVariable psiVariable) {
       touch();

       boolean result = myVariablesUseArmed.contains(psiVariable);
       myVariablesUseArmed.remove(psiVariable);

       return result;
     }

     private void touch() {
       if (myVariablesUseArmed == null) myVariablesUseArmed = new THashSet<PsiVariable>();
     }

     public void merge(InstructionState state) {
       touch();
       myVariablesUseArmed.addAll(state.myVariablesUseArmed);
     }

     public boolean contains(InstructionState state) {
       return myVariablesUseArmed != null && state.myVariablesUseArmed != null &&
              myVariablesUseArmed.containsAll(state.myVariablesUseArmed);
     }

     public boolean markVisited() {
       boolean old = myIsVisited;
       myIsVisited = true;
       return old;
     }

     public boolean isVisited() {
       return myIsVisited;
     }
   }

   @Nullable
   public static List<Info> getUnusedDefs(PsiCodeBlock body, Set<PsiVariable> outUsedVariables) {
     if (body == null) {
       return null;
     }

     ControlFlow flow;
     try {
       flow = ControlFlowFactory.getInstance(body.getProject()).getControlFlow(body, ourPolicy);
     }
     catch (AnalysisCanceledException e) {
       return null;
     }
     List<Instruction> instructions = flow.getInstructions();
     if (LOG.isDebugEnabled()) {
       LOG.debug(flow.toString());
     }

     Set<PsiVariable> assignedVariables = new THashSet<PsiVariable>();
     Set<PsiVariable> readVariables = new THashSet<PsiVariable>();
     for (int i = 0; i < instructions.size(); i++) {
       Instruction instruction = instructions.get(i);
       ProgressManager.checkCanceled();
       if (instruction instanceof WriteVariableInstruction) {
         WriteVariableInstruction writeInstruction = (WriteVariableInstruction)instruction;
         PsiElement context = flow.getElement(i);
         context = PsiTreeUtil.getParentOfType(context, PsiStatement.class, false);
         PsiVariable psiVariable = writeInstruction.variable;
         if (context != null && !(context instanceof PsiDeclarationStatement && psiVariable.getInitializer() == null)) {
           assignedVariables.add(psiVariable);
         }
       }
       else if (instruction instanceof ReadVariableInstruction) {
         ReadVariableInstruction readInstruction = (ReadVariableInstruction)instruction;
         readVariables.add(readInstruction.variable);
       }
     }

     InstructionState[] states = getStates(instructions);

     boolean[] defsArmed = new boolean[instructions.size()];

     Queue<InstructionState> queue = new Queue<InstructionState>(8);

     for (int i = states.length - 1; i >= 0; i--) {
       final InstructionState outerState = states[i];
       if (outerState.isVisited()) continue;
       outerState.touch();

       for (PsiVariable psiVariable : assignedVariables) {
         if (psiVariable instanceof PsiField) {
           outerState.mergeUseArmed(psiVariable);
         }
       }
       queue.addLast(outerState);

       while (!queue.isEmpty()) {
         ProgressManager.checkCanceled();
         InstructionState state = queue.pullFirst();
         state.markVisited();

         int idx = state.getInstructionIdx();
         if (idx < instructions.size()) {
           Instruction instruction = instructions.get(idx);

           if (instruction instanceof WriteVariableInstruction) {
             WriteVariableInstruction writeInstruction = (WriteVariableInstruction)instruction;
             PsiVariable psiVariable = writeInstruction.variable;
             outUsedVariables.add(psiVariable);
             if (state.mergeUseDisarmed(psiVariable)) {
               defsArmed[idx] = true;
             }
           }
           else if (instruction instanceof ReadVariableInstruction) {
             ReadVariableInstruction readInstruction = (ReadVariableInstruction)instruction;
             state.mergeUseArmed(readInstruction.variable);
             outUsedVariables.add(readInstruction.variable);
           }
           else {
             state.touch();
           }
         }

         IntArrayList backwardTraces = state.getBackwardTraces();
         for (int j = 0; j < backwardTraces.size(); j++) {
           int prevIdx = backwardTraces.get(j);
           InstructionState prevState = states[prevIdx];
           if (!prevState.contains(state)) {
             prevState.merge(state);
             queue.addLast(prevState);
           }
         }
       }
     }

     List<Info> unusedDefs = new ArrayList<Info>();

     for (int i = 0; i < instructions.size(); i++) {
       Instruction instruction = instructions.get(i);
       if (instruction instanceof WriteVariableInstruction) {
         WriteVariableInstruction writeInstruction = (WriteVariableInstruction)instruction;
         if (!defsArmed[i]) {
           PsiElement context = PsiTreeUtil.getNonStrictParentOfType(flow.getElement(i),
                                                                     PsiStatement.class, PsiAssignmentExpression.class,
                                                                     PsiPostfixExpression.class, PsiPrefixExpression.class);
           PsiVariable psiVariable = writeInstruction.variable;
           if (context != null && !(context instanceof PsiTryStatement)) {
             if (context instanceof PsiDeclarationStatement && psiVariable.getInitializer() == null) {
               if (!assignedVariables.contains(psiVariable)) {
                 unusedDefs.add(new Info(psiVariable, context, false));
               }
             }
             else {
               unusedDefs.add(new Info(psiVariable, context, readVariables.contains(psiVariable)));
             }
           }
         }
       }
     }

     return unusedDefs;
   }

   @NotNull
   public static PsiElement[] getDefs(PsiCodeBlock body, final PsiVariable def, PsiElement ref) {
     try {
       RefsDefs refsDefs = new RefsDefs(body) {
         private final InstructionState[] states = getStates(instructions);

         @Override
         protected int nNext(int index) {
           return states[index].getBackwardTraces().size();
         }

         @Override
         protected int getNext(int index, int no) {
           return states[index].getBackwardTraces().get(no);
         }

         @Override
         protected boolean defs() {
           return true;
         }

         @Override
         protected void processInstruction(final Set<PsiElement> res, final Instruction instruction, int index) {
           if (instruction instanceof WriteVariableInstruction) {
             WriteVariableInstruction instructionW = (WriteVariableInstruction)instruction;
             if (instructionW.variable == def) {

               final PsiElement element = flow.getElement(index);
               element.accept(new JavaRecursiveElementWalkingVisitor() {
                 @Override
                 public void visitReferenceExpression(PsiReferenceExpression ref) {
                   if (PsiUtil.isAccessedForWriting(ref)) {
                     if (ref.resolve() == def) {
                       res.add(ref);
                     }
                   }
                 }

                 @Override
                 public void visitVariable(PsiVariable var) {
                   if (var == def && (var instanceof PsiParameter || var.hasInitializer())) {
                     res.add(var);
                   }
                 }
               });
             }
           }
         }
       };
       return refsDefs.get(def, ref);
     }
     catch (AnalysisCanceledException e) {
       return PsiElement.EMPTY_ARRAY;
     }
   }

   @NotNull
   public static PsiElement[] getRefs(PsiCodeBlock body, final PsiVariable def, PsiElement ref) {
     try {
       RefsDefs refsDefs = new RefsDefs(body) {
         @Override
         protected int nNext(int index) {
           return instructions.get(index).nNext();
         }

         @Override
         protected int getNext(int index, int no) {
           return instructions.get(index).getNext(index, no);
         }

         @Override
         protected boolean defs() {
           return false;
         }

         @Override
         protected void processInstruction(final Set<PsiElement> res, final Instruction instruction, int index) {
           if (instruction instanceof ReadVariableInstruction) {
             ReadVariableInstruction instructionR = (ReadVariableInstruction)instruction;
             if (instructionR.variable == def) {

               final PsiElement element = flow.getElement(index);
               element.accept(new JavaRecursiveElementWalkingVisitor() {
                 @Override
                 public void visitReferenceExpression(PsiReferenceExpression ref) {
                   if (ref.resolve() == def) {
                     res.add(ref);
                   }
                 }
               });
             }
           }
         }
       };
       return refsDefs.get(def, ref);
     }
     catch (AnalysisCanceledException e) {
       return PsiElement.EMPTY_ARRAY;
     }
   }

   private abstract static class RefsDefs {
     protected abstract int   nNext(int index);
     protected abstract int getNext(int index, int no);

     final List<Instruction> instructions;
     final ControlFlow flow;
     final PsiCodeBlock body;


     protected RefsDefs(PsiCodeBlock body) throws AnalysisCanceledException {
       this.body = body;
       flow = ControlFlowFactory.getInstance(body.getProject()).getControlFlow(body, ourPolicy);
       instructions = flow.getInstructions();
     }

     protected abstract void processInstruction(Set<PsiElement> res, final Instruction instruction, int index);
     protected abstract boolean defs ();

     @NotNull
     private PsiElement[] get (final PsiVariable def, PsiElement refOrDef) {
       if (body == null) {
         return PsiElement.EMPTY_ARRAY;
       }

       final boolean [] visited = new boolean[instructions.size() + 1];
       visited [visited.length-1] = true; // stop on the code end
       int elem = defs() ? flow.getStartOffset(refOrDef) : flow.getEndOffset(refOrDef);

       // hack: ControlFlow doesn't contains parameters initialization
       if (elem == -1 && def instanceof PsiParameter) {
         elem = 0;
       }

       if (elem != -1) {
         if (!defs () && instructions.get(elem) instanceof ReadVariableInstruction) {
           LOG.assertTrue(nNext(elem) == 1);
           LOG.assertTrue(getNext(elem,0) == elem+1);
           elem += 1;
         }

         final Set<PsiElement> res = new THashSet<PsiElement>();
         class Inner {

           void traverse (int index) {
             visited [index] = true;

             if (defs ()) {
               final Instruction instruction = instructions.get(index);
               processInstruction(res, instruction, index);
               if (instruction instanceof WriteVariableInstruction) {
                 WriteVariableInstruction instructionW = (WriteVariableInstruction)instruction;
                 if (instructionW.variable == def) {
                   return;
                 }
               }

               // hack: ControlFlow doesnn't contains parameters initialization
               if (index == 0 && def instanceof PsiParameter) {
                 res.add(def.getNameIdentifier());
               }
             }

             final int nNext = nNext (index);
             for (int i = 0; i < nNext; i++) {
               final int prev = getNext(index, i);
               if (!visited [prev]) {
                 if (!defs ()) {
                   final Instruction instruction = instructions.get(prev);
                   if (instruction instanceof WriteVariableInstruction) {
                     WriteVariableInstruction instructionW = (WriteVariableInstruction)instruction;
                     if (instructionW.variable == def) {
                       continue;
                     }
                   } else {
                     processInstruction(res, instruction, prev);
                   }
                 }
                 traverse (prev);

               }
             }
           }
         }
         new Inner ().traverse (elem);
         return PsiUtilCore.toPsiElementArray(res);
       }
       return PsiElement.EMPTY_ARRAY;
     }
   }


   private static InstructionState[] getStates(final List<Instruction> instructions) {
     final InstructionState[] states = new InstructionState[instructions.size()];
     for (int i = 0; i < states.length; i++) {
       states[i] = new InstructionState(i);
     }

     for (int i = 0; i < instructions.size(); i++) {
       final Instruction instruction = instructions.get(i);
       for (int j = 0; j != instruction.nNext(); ++ j) {
         final int next = instruction.getNext(i, j);
         if (next < states.length) {
           states[next].addBackwardTrace(i);
         }
       }
     }
     return states;
   }

   private static final ControlFlowPolicy ourPolicy = new ControlFlowPolicy() {
     @Override
     public PsiVariable getUsedVariable(@NotNull PsiReferenceExpression refExpr) {
       if (refExpr.isQualified()) return null;

       PsiElement refElement = refExpr.resolve();
       if (refElement instanceof PsiLocalVariable || refElement instanceof PsiParameter) {
         return (PsiVariable) refElement;
       }

       return null;
     }

     @Override
     public boolean isParameterAccepted(@NotNull PsiParameter psiParameter) {
       return true;
     }

     @Override
     public boolean isLocalVariableAccepted(@NotNull PsiLocalVariable psiVariable) {
       return true;
     }
   };
 }
	/*
	* 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.psi.controlFlow;

	import com.intellij.openapi.diagnostic.Logger;
	import com.intellij.openapi.progress.ProgressManager;
	import com.intellij.psi.*;
	import com.intellij.psi.util.PsiTreeUtil;
	import com.intellij.psi.util.PsiUtil;
	import com.intellij.psi.util.PsiUtilCore;
	import com.intellij.util.containers.IntArrayList;
	import com.intellij.util.containers.Queue;
	import gnu.trove.THashSet;
	import org.jetbrains.annotations.NotNull;
	import org.jetbrains.annotations.Nullable;

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

	/**
	* @author max
	* Date: Mar 22, 2002
	*/
	public class DefUseUtil {
	private static final Logger LOG = Logger.getInstance("#com.intellij.codeInspection.defUse.DefUseUtil");

	private DefUseUtil() { }

	public static class Info {
	private final PsiVariable myVariable;
	private final PsiElement myContext;
	private final boolean myIsRead;

	public Info(PsiVariable variable, PsiElement context, boolean read) {
	myVariable = variable;
	myContext = context;
	myIsRead = read;
	}

	public PsiVariable getVariable() {
	return myVariable;
	}

	public PsiElement getContext() {
	return myContext;
	}

	public boolean isRead() {
	return myIsRead;
	}
	}

	private static class InstructionState {
	private Set<PsiVariable> myVariablesUseArmed;
	private final int myInstructionIdx;
	private final IntArrayList myBackwardTraces;
	private boolean myIsVisited = false;

	public InstructionState(int instructionIdx) {
	myInstructionIdx = instructionIdx;
	myBackwardTraces = new IntArrayList();
	myVariablesUseArmed = null;
	}

	public void addBackwardTrace(int i) {
	myBackwardTraces.add(i);
	}

	public IntArrayList getBackwardTraces() {
	return myBackwardTraces;
	}

	public int getInstructionIdx() {
	return myInstructionIdx;
	}

	void mergeUseArmed(PsiVariable psiVariable) {
	touch();
	myVariablesUseArmed.add(psiVariable);
	}

	boolean mergeUseDisarmed(PsiVariable psiVariable) {
	touch();

	boolean result = myVariablesUseArmed.contains(psiVariable);
	myVariablesUseArmed.remove(psiVariable);

	return result;
	}

	private void touch() {
	if (myVariablesUseArmed == null) myVariablesUseArmed = new THashSet<PsiVariable>();
	}

	public void merge(InstructionState state) {
	touch();
	myVariablesUseArmed.addAll(state.myVariablesUseArmed);
	}

	public boolean contains(InstructionState state) {
	return myVariablesUseArmed != null && state.myVariablesUseArmed != null &&
	myVariablesUseArmed.containsAll(state.myVariablesUseArmed);
	}

	public boolean markVisited() {
	boolean old = myIsVisited;
	myIsVisited = true;
	return old;
	}

	public boolean isVisited() {
	return myIsVisited;
	}
	}

	@Nullable
	public static List<Info> getUnusedDefs(PsiCodeBlock body, Set<PsiVariable> outUsedVariables) {
	if (body == null) {
	return null;
	}

	ControlFlow flow;
	try {
	flow = ControlFlowFactory.getInstance(body.getProject()).getControlFlow(body, ourPolicy);
	}
	catch (AnalysisCanceledException e) {
	return null;
	}
	List<Instruction> instructions = flow.getInstructions();
	if (LOG.isDebugEnabled()) {
	LOG.debug(flow.toString());
	}

	Set<PsiVariable> assignedVariables = new THashSet<PsiVariable>();
	Set<PsiVariable> readVariables = new THashSet<PsiVariable>();
	for (int i = 0; i < instructions.size(); i++) {
	Instruction instruction = instructions.get(i);
	ProgressManager.checkCanceled();
	if (instruction instanceof WriteVariableInstruction) {
	WriteVariableInstruction writeInstruction = (WriteVariableInstruction)instruction;
	PsiElement context = flow.getElement(i);
	context = PsiTreeUtil.getParentOfType(context, PsiStatement.class, false);
	PsiVariable psiVariable = writeInstruction.variable;
	if (context != null && !(context instanceof PsiDeclarationStatement && psiVariable.getInitializer() == null)) {
	assignedVariables.add(psiVariable);
	}
	}
	else if (instruction instanceof ReadVariableInstruction) {
	ReadVariableInstruction readInstruction = (ReadVariableInstruction)instruction;
	readVariables.add(readInstruction.variable);
	}
	}

	InstructionState[] states = getStates(instructions);

	boolean[] defsArmed = new boolean[instructions.size()];

	Queue<InstructionState> queue = new Queue<InstructionState>(8);

	for (int i = states.length - 1; i >= 0; i--) {
	final InstructionState outerState = states[i];
	if (outerState.isVisited()) continue;
	outerState.touch();

	for (PsiVariable psiVariable : assignedVariables) {
	if (psiVariable instanceof PsiField) {
	outerState.mergeUseArmed(psiVariable);
	}
	}
	queue.addLast(outerState);

	while (!queue.isEmpty()) {
	ProgressManager.checkCanceled();
	InstructionState state = queue.pullFirst();
	state.markVisited();

	int idx = state.getInstructionIdx();
	if (idx < instructions.size()) {
	Instruction instruction = instructions.get(idx);

	if (instruction instanceof WriteVariableInstruction) {
	WriteVariableInstruction writeInstruction = (WriteVariableInstruction)instruction;
	PsiVariable psiVariable = writeInstruction.variable;
	outUsedVariables.add(psiVariable);
	if (state.mergeUseDisarmed(psiVariable)) {
	defsArmed[idx] = true;
	}
	}
	else if (instruction instanceof ReadVariableInstruction) {
	ReadVariableInstruction readInstruction = (ReadVariableInstruction)instruction;
	state.mergeUseArmed(readInstruction.variable);
	outUsedVariables.add(readInstruction.variable);
	}
	else {
	state.touch();
	}
	}

	IntArrayList backwardTraces = state.getBackwardTraces();
	for (int j = 0; j < backwardTraces.size(); j++) {
	int prevIdx = backwardTraces.get(j);
	InstructionState prevState = states[prevIdx];
	if (!prevState.contains(state)) {
	prevState.merge(state);
	queue.addLast(prevState);
	}
	}
	}
	}

	List<Info> unusedDefs = new ArrayList<Info>();

	for (int i = 0; i < instructions.size(); i++) {
	Instruction instruction = instructions.get(i);
	if (instruction instanceof WriteVariableInstruction) {
	WriteVariableInstruction writeInstruction = (WriteVariableInstruction)instruction;
	if (!defsArmed[i]) {
	PsiElement context = PsiTreeUtil.getNonStrictParentOfType(flow.getElement(i),
	PsiStatement.class, PsiAssignmentExpression.class,
	PsiPostfixExpression.class, PsiPrefixExpression.class);
	PsiVariable psiVariable = writeInstruction.variable;
	if (context != null && !(context instanceof PsiTryStatement)) {
	if (context instanceof PsiDeclarationStatement && psiVariable.getInitializer() == null) {
	if (!assignedVariables.contains(psiVariable)) {
	unusedDefs.add(new Info(psiVariable, context, false));
	}
	}
	else {
	unusedDefs.add(new Info(psiVariable, context, readVariables.contains(psiVariable)));
	}
	}
	}
	}
	}

	return unusedDefs;
	}

	@NotNull
	public static PsiElement[] getDefs(PsiCodeBlock body, final PsiVariable def, PsiElement ref) {
	try {
	RefsDefs refsDefs = new RefsDefs(body) {
	private final InstructionState[] states = getStates(instructions);

	@Override
	protected int nNext(int index) {
	return states[index].getBackwardTraces().size();
	}

	@Override
	protected int getNext(int index, int no) {
	return states[index].getBackwardTraces().get(no);
	}

	@Override
	protected boolean defs() {
	return true;
	}

	@Override
	protected void processInstruction(final Set<PsiElement> res, final Instruction instruction, int index) {
	if (instruction instanceof WriteVariableInstruction) {
	WriteVariableInstruction instructionW = (WriteVariableInstruction)instruction;
	if (instructionW.variable == def) {

	final PsiElement element = flow.getElement(index);
	element.accept(new JavaRecursiveElementWalkingVisitor() {
	@Override
	public void visitReferenceExpression(PsiReferenceExpression ref) {
	if (PsiUtil.isAccessedForWriting(ref)) {
	if (ref.resolve() == def) {
	res.add(ref);
	}
	}
	}

	@Override
	public void visitVariable(PsiVariable var) {
	if (var == def && (var instanceof PsiParameter \|\| var.hasInitializer())) {
	res.add(var);
	}
	}
	});
	}
	}
	}
	};
	return refsDefs.get(def, ref);
	}
	catch (AnalysisCanceledException e) {
	return PsiElement.EMPTY_ARRAY;
	}
	}

	@NotNull
	public static PsiElement[] getRefs(PsiCodeBlock body, final PsiVariable def, PsiElement ref) {
	try {
	RefsDefs refsDefs = new RefsDefs(body) {
	@Override
	protected int nNext(int index) {
	return instructions.get(index).nNext();
	}

	@Override
	protected int getNext(int index, int no) {
	return instructions.get(index).getNext(index, no);
	}

	@Override
	protected boolean defs() {
	return false;
	}

	@Override
	protected void processInstruction(final Set<PsiElement> res, final Instruction instruction, int index) {
	if (instruction instanceof ReadVariableInstruction) {
	ReadVariableInstruction instructionR = (ReadVariableInstruction)instruction;
	if (instructionR.variable == def) {

	final PsiElement element = flow.getElement(index);
	element.accept(new JavaRecursiveElementWalkingVisitor() {
	@Override
	public void visitReferenceExpression(PsiReferenceExpression ref) {
	if (ref.resolve() == def) {
	res.add(ref);
	}
	}
	});
	}
	}
	}
	};
	return refsDefs.get(def, ref);
	}
	catch (AnalysisCanceledException e) {
	return PsiElement.EMPTY_ARRAY;
	}
	}

	private abstract static class RefsDefs {
	protected abstract int nNext(int index);
	protected abstract int getNext(int index, int no);

	final List<Instruction> instructions;
	final ControlFlow flow;
	final PsiCodeBlock body;


	protected RefsDefs(PsiCodeBlock body) throws AnalysisCanceledException {
	this.body = body;
	flow = ControlFlowFactory.getInstance(body.getProject()).getControlFlow(body, ourPolicy);
	instructions = flow.getInstructions();
	}

	protected abstract void processInstruction(Set<PsiElement> res, final Instruction instruction, int index);
	protected abstract boolean defs ();

	@NotNull
	private PsiElement[] get (final PsiVariable def, PsiElement refOrDef) {
	if (body == null) {
	return PsiElement.EMPTY_ARRAY;
	}

	final boolean [] visited = new boolean[instructions.size() + 1];
	visited [visited.length-1] = true; // stop on the code end
	int elem = defs() ? flow.getStartOffset(refOrDef) : flow.getEndOffset(refOrDef);

	// hack: ControlFlow doesn't contains parameters initialization
	if (elem == -1 && def instanceof PsiParameter) {
	elem = 0;
	}

	if (elem != -1) {
	if (!defs () && instructions.get(elem) instanceof ReadVariableInstruction) {
	LOG.assertTrue(nNext(elem) == 1);
	LOG.assertTrue(getNext(elem,0) == elem+1);
	elem += 1;
	}

	final Set<PsiElement> res = new THashSet<PsiElement>();
	class Inner {

	void traverse (int index) {
	visited [index] = true;

	if (defs ()) {
	final Instruction instruction = instructions.get(index);
	processInstruction(res, instruction, index);
	if (instruction instanceof WriteVariableInstruction) {
	WriteVariableInstruction instructionW = (WriteVariableInstruction)instruction;
	if (instructionW.variable == def) {
	return;
	}
	}

	// hack: ControlFlow doesnn't contains parameters initialization
	if (index == 0 && def instanceof PsiParameter) {
	res.add(def.getNameIdentifier());
	}
	}

	final int nNext = nNext (index);
	for (int i = 0; i < nNext; i++) {
	final int prev = getNext(index, i);
	if (!visited [prev]) {
	if (!defs ()) {
	final Instruction instruction = instructions.get(prev);
	if (instruction instanceof WriteVariableInstruction) {
	WriteVariableInstruction instructionW = (WriteVariableInstruction)instruction;
	if (instructionW.variable == def) {
	continue;
	}
	} else {
	processInstruction(res, instruction, prev);
	}
	}
	traverse (prev);

	}
	}
	}
	}
	new Inner ().traverse (elem);
	return PsiUtilCore.toPsiElementArray(res);
	}
	return PsiElement.EMPTY_ARRAY;
	}
	}


	private static InstructionState[] getStates(final List<Instruction> instructions) {
	final InstructionState[] states = new InstructionState[instructions.size()];
	for (int i = 0; i < states.length; i++) {
	states[i] = new InstructionState(i);
	}

	for (int i = 0; i < instructions.size(); i++) {
	final Instruction instruction = instructions.get(i);
	for (int j = 0; j != instruction.nNext(); ++ j) {
	final int next = instruction.getNext(i, j);
	if (next < states.length) {
	states[next].addBackwardTrace(i);
	}
	}
	}
	return states;
	}

	private static final ControlFlowPolicy ourPolicy = new ControlFlowPolicy() {
	@Override
	public PsiVariable getUsedVariable(@NotNull PsiReferenceExpression refExpr) {
	if (refExpr.isQualified()) return null;

	PsiElement refElement = refExpr.resolve();
	if (refElement instanceof PsiLocalVariable \|\| refElement instanceof PsiParameter) {
	return (PsiVariable) refElement;
	}

	return null;
	}

	@Override
	public boolean isParameterAccepted(@NotNull PsiParameter psiParameter) {
	return true;
	}

	@Override
	public boolean isLocalVariableAccepted(@NotNull PsiLocalVariable psiVariable) {
	return true;
	}
	};
	}