public static <V> DataflowExpression<Set<V>> one(V e) {
	return new SetExpression<V>(e);
} public static <V> DataflowExpression<Set<V>> remove(
	DataflowExpression<Set<V>> set, V e) {
		
	return new RemoveOperation<V>(set, e);
} public static <V> DataflowExpression<Set<V>> sub(
	DataflowExpression<Set<V>> e1,
	DataflowExpression<Set<V>> e2) {
		
	return new SubstractOperation<V>(e1, e2);
} public static <V> DataflowExpression<Set<V>> union(
	DataflowExpression<Set<V>> e1,
	DataflowExpression<Set<V>> e2) {
		
	return new UnionOperation<V>(e1, e2);
} public abstract class AbstractNode {
	private Set<AbstractNode> successors = new HashSet<AbstractNode>();
	private Set<AbstractNode> predecessors = new HashSet<AbstractNode>();
	
	/**
	 * Adds given successor to this node. This node will be
	 * automatically added to the given node's predecessors.
	 */
	public void addSuccessor(AbstractNode n) {
		successors.add(n);
		n.predecessors.add(this);
	}
	
	/**
	 * Returns all successors of this node.
	 */
	public Set<AbstractNode> getSuccessors() {
		return successors;
	}
	
	public Set<AbstractNode> getPredecessors() {
		return predecessors;
	}

	public <V> void visitNodes(AbstractNodeVisitor<V> visitor) {
		if (!visitor.hasVisited(this)) {
			visit(visitor);
			
			for (AbstractNode node : predecessors) {
				node.visitNodes(visitor);
			}
			
			for (AbstractNode node : successors) {
				node.visitNodes(visitor);
			}
		}
	}
	
	protected abstract <V> void visit(AbstractNodeVisitor<V> visitor);

	@Override
	public boolean equals(Object obj) {
		throw new UnsupportedOperationException("Subclasses of AbstractNode must implement equals method");
	}

	@Override
	public int hashCode() {
		throw new UnsupportedOperationException("Subclasses of AbstractNode must implement hashCode method");
	}
	
} public class AssignmentNode extends AbstractNode {
	private Assignment assignment;
	
	public AssignmentNode(Assignment assignment) {
		this.assignment = assignment;
	}

	public Identifier getIdentifier() {
		return assignment.getIdentifier();
	}
	
	public Expression getExpression() {
		return assignment.getExpression();
	}

	@Override
	protected <V> void visit(AbstractNodeVisitor<V> visitor) {
		visitor.visitAssignment(this);
	}

	@Override
	public String toString() {
		return assignment.toString();
	}

	@Override
	public boolean equals(Object obj) {
		return obj instanceof AssignmentNode
			&& ((AssignmentNode) obj).assignment.equals(assignment);
	}

	@Override
	public int hashCode() {
		return assignment.hashCode();
	}
	
	/**
	 * Common method to retrieve variables as strings from this node.
	 */
	public DataflowExpression<Set<String>> vars() {
		Set<Identifier> vars = new HashSet<Identifier>();
		assignment.getExpression().collectVariables(vars);
		
		return PowersetDomain.set(CollectionUtil.transform(
				vars, new HashSet<String>(), new VariableNameTransform()));
	}
	
} public class ConditionNode extends AbstractNode {
	private Expression condition;

	public ConditionNode(Expression condition) {
		this.condition = condition;
	}

	@Override
	protected <V> void visit(AbstractNodeVisitor<V> visitor) {
		visitor.visitCondition(this);
	}

	public Expression getCondition() {
		return condition;
	}

	@Override
	public String toString() {
		return condition.toString();
	}
	
	@Override
	public boolean equals(Object obj) {
		return obj instanceof ConditionNode
			&& ((ConditionNode) obj).condition.equals(condition);
	}

	@Override
	public int hashCode() {
		return condition.hashCode();
	}
	
	/**
	 * Common method to retrieve variables as strings from this node.
	 */
	public DataflowExpression<Set<String>> vars() {
		Set<Identifier> vars = new HashSet<Identifier>();
		condition.collectVariables(vars);
		
		return PowersetDomain.set(CollectionUtil.transform(
				vars, new HashSet<String>(), new VariableNameTransform()));
	}

} public class DeclarationNode extends AbstractNode {
	private Declaration variables;

	public DeclarationNode(Declaration variables) {
		this.variables = variables;
	}

	public List<Identifier> getIdentifiers() {
		return variables.getIdentifiers();
	}

	@Override
	protected <V> void visit(AbstractNodeVisitor<V> visitor) {
		visitor.visitDeclaration(this);
	}

	@Override
	public String toString() {
		return variables.toString();
	}

	@Override
	public boolean equals(Object obj) {
		return obj instanceof DeclarationNode
			&& ((DeclarationNode) obj).variables.equals(variables);
	}

	@Override
	public int hashCode() {
		return variables.hashCode();
	}
	
	/**
	 * Common method to retrieve variables as strings from this node.
	 */
	public DataflowExpression<Set<String>> vars() {
		return PowersetDomain.set(CollectionUtil.transform(
				variables.getIdentifiers(), new HashSet<String>(), new VariableNameTransform()));
	}
	
} public class EntryNode extends AbstractNode {

	@Override
	protected <V> void visit(AbstractNodeVisitor<V> visitor) {
		visitor.visitEntry(this);
	}

	@Override
	public boolean equals(Object obj) {
		return obj instanceof EntryNode;
	}

	@Override
	public int hashCode() {
		return 0;
	}

	@Override
	public String toString() {
		return "entry";
	}

} public class ExitNode extends AbstractNode {

	@Override
	protected <V> void visit(AbstractNodeVisitor<V> visitor) {
		visitor.visitExit(this);
	}

	@Override
	public String toString() {
		return "exit";
	}

	@Override
	public boolean equals(Object obj) {
		return obj instanceof ExitNode;
	}

	@Override
	public int hashCode() {
		return 0;
	}

} public class OutputNode extends AbstractNode {
	private Output output;

	public OutputNode(Output output) {
		this.output = output;
	}

	public Identifier getIdentifier() {
		return output.getIdentifier();
	}

	@Override
	protected <V> void visit(AbstractNodeVisitor<V> visitor) {
		visitor.visitOutput(this);
	}

	@Override
	public String toString() {
		return output.toString();
	}

	@Override
	public boolean equals(Object obj) {
		return obj instanceof OutputNode
			&& ((OutputNode) obj).output.equals(output);
	}

	@Override
	public int hashCode() {
		return output.hashCode();
	}

} public abstract class AbstractNodeVisitor<V> {
	
	private Map<AbstractNode, DataflowExpression<V>> visited =
		new HashMap<AbstractNode, DataflowExpression<V>>();
	
	private int currentVarId = 0;
	private Map<AbstractNode, Integer> variables =
		new HashMap<AbstractNode, Integer>();
	
	public abstract void visitAssignment(AssignmentNode node);
	
	public abstract void visitDeclaration(DeclarationNode node);
	
	public abstract void visitExit(ExitNode node);
	
	public abstract void visitOutput(OutputNode node);
	
	public abstract void visitCondition(ConditionNode node);
	
	public abstract void visitEntry(EntryNode node);
	
	public boolean hasVisited(AbstractNode node) {
		return visited.containsKey(node);
	}
	
	public void markVisited(AbstractNode node) {
		visited.put(node, null);
	}
	
	protected void setConstraint(AbstractNode node, DataflowExpression<V> expression) {
		visited.put(node, expression);
	}

	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		
		for (Entry<AbstractNode, DataflowExpression<V>> e : visited.entrySet()) {
			builder.append("[[").append(e.getKey()).append("]]")
				.append(" = ").append(e.getValue()).append('\n');
		}
		
		return builder.toString();
	}
	
	/**
	 * Returns collected dataflow expressions.
	 */
	public Map<AbstractNode, DataflowExpression<V>> getExpressions() {
		return visited;
	}
	
	/**
	 * Helper method to generate variable id from given node.
	 * For this analysis each node is a variable.
	 */
	protected int getVariableId(AbstractNode node) {
		Integer id = variables.get(node);
		if (id == null) {
			id = currentVarId++;
			variables.put(node, id);
		}
		
		return id;
	}
	
	/**
	 * Creates constraint set from found expressions.
	 */
	public DataflowConstraintSet<V, AbstractNode> getConstraints() {
		
		DataflowConstraintSet<V, AbstractNode> set =
			new DataflowConstraintSet<V, AbstractNode>();
		
		for (Entry<AbstractNode, DataflowExpression<V>> e : visited.entrySet()) {
			
			// Ignore if there is no constraint
			// for the node.
			if (e.getValue() == null) {
				continue;
			}
			
			set.addConstraint(getVariableId(e.getKey()), e.getValue(), e.getKey());
		}
		
		return set;
	}

} public interface DataflowExpression<V> {
	/**
	 * Evaluates expression using the given variable values.
	 */
	V eval(V[] values);
	
	/**
	 * Helper to collect all variables,
	 */
	void collectVariables(Set<Integer> variables);
} public class DataflowVariable<V>
	implements DataflowExpression<V> {
	
	private int id;
	private AbstractNode node;
	
	public DataflowVariable(int id, AbstractNode node) {
		this.id = id;
		this.node = node;
	}

	@Override
	public V eval(V[] values) {
		return values[id];
	}

	@Override
	public String toString() {
		return "[[" + node + "]]";
	}

	@Override
	public void collectVariables(Set<Integer> variables) {
		variables.add(id);
	}

} public class AllUnionOperation<V> implements DataflowExpression<Set<V>> {
	private List<DataflowVariable<Set<V>>> variables;

	public AllUnionOperation(List<DataflowVariable<Set<V>>> variables) {
		this.variables = variables;
	}

	@Override
	public Set<V> eval(Set<V>[] values) {
		Set<V> set = new HashSet<V>();
		
		for (DataflowVariable<Set<V>> v : variables) {
			set.addAll(v.eval(values));
		}
		
		return set;
	}

	@Override
	public String toString() {
		return "U(" + StringUtil.join(variables, ",") + ")";
	}

	@Override
	public void collectVariables(Set<Integer> variables) {
		for (DataflowVariable<Set<V>> v : this.variables) {
			v.collectVariables(variables);
		}
	}

} public class EmptySet<V> implements DataflowExpression<Set<V>> {

	@Override
	public Set<V> eval(Set<V>[] values) {
		return Collections.emptySet();
	}

	@Override
	public String toString() {
		return "{}";
	}

	@Override
	public void collectVariables(Set<Integer> variables) {}

}
import static com.infdot.analysis.solver.lattice.powerset.PowersetDomain.one;
import static com.infdot.analysis.solver.lattice.powerset.PowersetDomain.remove;
import static com.infdot.analysis.solver.lattice.powerset.PowersetDomain.sub;
import static com.infdot.analysis.solver.lattice.powerset.PowersetDomain.union;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import com.infdot.analysis.cfg.node.AbstractNode;
import com.infdot.analysis.cfg.node.AssignmentNode;
import com.infdot.analysis.cfg.node.ConditionNode;
import com.infdot.analysis.cfg.node.DeclarationNode;
import com.infdot.analysis.cfg.node.EntryNode;
import com.infdot.analysis.cfg.node.ExitNode;
import com.infdot.analysis.cfg.node.OutputNode;
import com.infdot.analysis.cfg.node.visitor.AbstractNodeVisitor;
import com.infdot.analysis.solver.DataflowExpression;
import com.infdot.analysis.solver.DataflowVariable;
import com.infdot.analysis.solver.lattice.powerset.AllUnionOperation;
import com.infdot.analysis.solver.lattice.powerset.EmptySet;
package com.infdot.analysis.examples.liveness;




public class LivenessVisitor extends AbstractNodeVisitor<Set<String>> {
	
	/**
	 * For assignments we have [[n]]=JOIN(n) \ {id} U vars(E).
	 */
	@Override
	public void visitAssignment(AssignmentNode node) {
		setConstraint(node, union(remove(join(node), node.getIdentifier().getName()), node.vars()));
	}

	/**
	 * For declarations we have [[n]]=JOIN(n) \ {id1, ..., idk}
	 */
	@Override
	public void visitDeclaration(DeclarationNode node) {
		setConstraint(node, sub(join(node), node.vars()));
	}

	/**
	 * For exit node we have the empty set.
	 */
	@Override
	public void visitExit(ExitNode node) {
		setConstraint(node, new EmptySet<String>());
	}

	/**
	 * For output statements we have [[n]] = JOIN(n) U vars(E)
	 */
	@Override
	public void visitOutput(OutputNode node) {
		setConstraint(node, union(join(node), one(node.getIdentifier().getName())));
	}
	
	/**
	 * For conditions we have [[n]] = JOIN(n) U vars(E)
	 */
	@Override
	public void visitCondition(ConditionNode node) {