public class Cfg {
	private AbstractNode start;
	
	/**
	 * Constructs CFG from the given program. Adds single exit
	 * node automatically.
	 */
	public Cfg(Statement program) {
		Fragment fragment = program.visit(new FragmentBuilderVisitor());
		fragment.addSuccessor(new Fragment(new ExitNode()));
		start = new EntryNode();
		start.addSuccessor(fragment.getStart());
	}

	public AbstractNode getStart() {
		return start;
	}
	
	public <V> void visit(AbstractNodeVisitor<V> visitor) {
		start.visitNodes(visitor);
	}

} public abstract class ConstraintBuilder<V> extends AbstractNodeVisitor<V> {

	@Override
	public void visitAssignment(AssignmentNode node) {
		setConstraint(node, assignment(node));
	}

	@Override
	public void visitDeclaration(DeclarationNode node) {
		setConstraint(node, declaration(node));
	}

	@Override
	public void visitExit(ExitNode node) {
		setConstraint(node, exit(node));
	}

	@Override
	public void visitOutput(OutputNode node) {
		setConstraint(node, output(node));
	}

	@Override
	public void visitCondition(ConditionNode node) {
		setConstraint(node, condition(node));
	}
	
	@Override
	public void visitEntry(EntryNode node) {
		setConstraint(node, entry(node));
	}

	public abstract DataflowExpression<V> assignment(AssignmentNode assignment);
	
	public abstract DataflowExpression<V> declaration(DeclarationNode declaration);
	
	public abstract DataflowExpression<V> exit(ExitNode exit);
	
	public abstract DataflowExpression<V> output(OutputNode output);
	
	public abstract DataflowExpression<V> condition(ConditionNode condition);
	
	public abstract DataflowExpression<V> entry(EntryNode exit);
} 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 class Liveness {
	
	public static void main(String[] args) throws ParseException {
		
		Statement program = WhileLang.parse(Liveness.class.getResourceAsStream("liveness.while"));
		StringBuilder builder = new StringBuilder();
		program.toCodeString(builder, "");
		
		System.out.println(builder);
		
		StatementExpressionVisitor numberingVisitor =
			new StatementExpressionVisitor(new ExpressionNumberingVisitor());
		
		program.visit(numberingVisitor);
		
		Cfg cfg = new Cfg(program);
		LivenessVisitor visitor = new LivenessVisitor();
		cfg.visit(visitor);
		
		System.out.println(visitor);
		
		DataflowConstraintSet<Set<String>, AbstractNode> constraints
			= visitor.getConstraints();
		
		Solver<Set<String>> solver = new Solver<Set<String>>(
				new PowersetDomain<String>(), constraints);
		
		Set<String>[] solution = solver.solve();
		
		constraints.dumpWithMetainfo(solution);
		
	}
} public class ExpressionNumberingVisitor extends AbstractExpressionVisitor<Void> {
	private int expressionId = 0;
	
	@Override
	public Void visitConstant(Constant constant) {
		setId(constant);
		return null;
	}

	@Override
	public Void visitDiv(Div div, Void e1, Void e2) {
		setId(div);
		return null;
	}

	@Override
	public Void visitGt(Gt gt, Void e1, Void e2) {
		setId(gt);
		return null;
	}

	@Override
	public Void visitIdentifier(Identifier identifier) {
		setId(identifier);
		return null;
	}

	@Override
	public Void visitInput(Input input) {
		setId(input);
		return null;
	}

	@Override
	public Void visitSub(Sub sub, Void e1, Void e2) {
		setId(sub);
		return null;
	}
	
	private void setId(Expression e) {
		e.setId(expressionId++);
	}

} public interface Statement {
	/**
	 * Method to build string representation of code.
	 */
	void toCodeString(StringBuilder builder, String ident);
	
	/**
	 * Method for accepting statement visitor.
	 */
	<T> T visit(AbstractStatementVisitor<T> visitor);
} public class StatementExpressionVisitor extends AbstractStatementVisitor<Void> {
	private AbstractExpressionVisitor visitor;

	public StatementExpressionVisitor(AbstractExpressionVisitor visitor) {
		this.visitor = visitor;
	}

	@Override
	public Void visitAssignment(Assignment assignment) {
		assignment.getIdentifier().visit(visitor);
		assignment.getExpression().visit(visitor);
		
		return null;
	}

	@Override
	public Void visitCompound(Compound compound, Void s1, Void s2) {
		return null;
	}

	@Override
	public Void visitDeclaration(Declaration declaration) {
		for (Identifier id : declaration.getIdentifiers()) {
			id.visit(visitor);
		}
		
		return null;
	}

	@Override
	public Void visitIf(If ifStatement, Void body) {
		ifStatement.getCondition().visit(visitor);
		return null;
	}

	@Override
	public Void visitOutput(Output output) {
		output.getIdentifier().visit(visitor);
		return null;
	}

	@Override
	public Void visitWhile(While whileStatement, Void body) {
		whileStatement.getCondition().visit(visitor);
		return null;
	}

} public class ParseException extends Exception {

  /**
   * The version identifier for this Serializable class.
   * Increment only if the <i>serialized</i> form of the
   * class changes.
   */
  private static final long serialVersionUID = 1L;

  /**
   * This constructor is used by the method "generateParseException"
   * in the generated parser.  Calling this constructor generates
   * a new object of this type with the fields "currentToken",
   * "expectedTokenSequences", and "tokenImage" set.
   */
  public ParseException(Token currentTokenVal,
                        int[][] expectedTokenSequencesVal,
                        String[] tokenImageVal
                       )
  {
    super(initialise(currentTokenVal, expectedTokenSequencesVal, tokenImageVal));
    currentToken = currentTokenVal;
    expectedTokenSequences = expectedTokenSequencesVal;
    tokenImage = tokenImageVal;
  }

  /**
   * The following constructors are for use by you for whatever
   * purpose you can think of.  Constructing the exception in this
   * manner makes the exception behave in the normal way - i.e., as
   * documented in the class "Throwable".  The fields "errorToken",
   * "expectedTokenSequences", and "tokenImage" do not contain
   * relevant information.  The JavaCC generated code does not use
   * these constructors.
   */

  public ParseException() {
    super();
  }

  /** Constructor with message. */
  public ParseException(String message) {
    super(message);
  }


  /**
   * This is the last token that has been consumed successfully.  If
   * this object has been created due to a parse error, the token
   * followng this token will (therefore) be the first error token.
   */
  public Token currentToken;

  /**
   * Each entry in this array is an array of integers.  Each array
   * of integers represents a sequence of tokens (by their ordinal
   * values) that is expected at this point of the parse.
   */
  public int[][] expectedTokenSequences;

  /**
   * This is a reference to the "tokenImage" array of the generated
   * parser within which the parse error occurred.  This array is
   * defined in the generated ...Constants interface.
   */
  public String[] tokenImage;

  /**
   * It uses "currentToken" and "expectedTokenSequences" to generate a parse
   * error message and returns it.  If this object has been created
   * due to a parse error, and you do not catch it (it gets thrown
   * from the parser) the correct error message
   * gets displayed.
   */
  private static String initialise(Token currentToken,
                           int[][] expectedTokenSequences,
                           String[] tokenImage) {
    String eol = System.getProperty("line.separator", "\n");
    StringBuffer expected = new StringBuffer();
    int maxSize = 0;
    for (int i = 0; i < expectedTokenSequences.length; i++) {
      if (maxSize < expectedTokenSequences[i].length) {
        maxSize = expectedTokenSequences[i].length;
      }
      for (int j = 0; j < expectedTokenSequences[i].length; j++) {
        expected.append(tokenImage[expectedTokenSequences[i][j]]).append(' ');
      }
      if (expectedTokenSequences[i][expectedTokenSequences[i].length - 1] != 0) {
        expected.append("...");
      }
      expected.append(eol).append("    ");
    }
    String retval = "Encountered \"";
    Token tok = currentToken.next;
    for (int i = 0; i < maxSize; i++) {
      if (i != 0) retval += " ";
      if (tok.kind == 0) {
        retval += tokenImage[0];
        break;
      }
      retval += " " + tokenImage[tok.kind];
      retval += " \"";
      retval += add_escapes(tok.image);
      retval += " \"";
      tok = tok.next;
    }
    retval += "\" at line " + currentToken.next.beginLine + ", column " + currentToken.next.beginColumn;
    retval += "." + eol;
    if (expectedTokenSequences.length == 1) {
      retval += "Was expecting:" + eol + "    ";
    } else {
      retval += "Was expecting one of:" + eol + "    ";
    }
    retval += expected.toString();
    return retval;
  }

  /**
   * The end of line string for this machine.
   */
  protected String eol = System.getProperty("line.separator", "\n");

  /**
   * Used to convert raw characters to their escaped version
   * when these raw version cannot be used as part of an ASCII
   * string literal.
   */
  static String add_escapes(String str) {
      StringBuffer retval = new StringBuffer();
      char ch;
      for (int i = 0; i < str.length(); i++) {
        switch (str.charAt(i))
        {
           case 0 :
              continue;
           case '\b':
              retval.append("\\b");
              continue;
           case '\t':
              retval.append("\\t");
              continue;
           case '\n':
              retval.append("\\n");
              continue;
           case '\f':
              retval.append("\\f");
              continue;
           case '\r':
              retval.append("\\r");
              continue;
           case '\"':
              retval.append("\\\"");
              continue;
           case '\'':
              retval.append("\\\'");
              continue;
           case '\\':
              retval.append("\\\\");
              continue;
           default:
              if ((ch = str.charAt(i)) < 0x20 || ch > 0x7e) {
                 String s = "0000" + Integer.toString(ch, 16);
                 retval.append("\\u" + s.substring(s.length() - 4, s.length()));
              } else {
                 retval.append(ch);
              }
              continue;
        }
      }
      return retval.toString();
   }

} @SuppressWarnings("unused")
public class WhileLang implements WhileLangConstants {
        public static Statement parse(String code) throws ParseException {
                return new WhileLang(new StringReader(code)).program();
        }

        public static Statement parse(InputStream input) throws ParseException {
                return new WhileLang(input).program();
        }

        public static Statement makeStatement(List<Statement> statements) {
                Statement statement = statements.get(0);
                for (Statement next : statements.subList(1, statements.size())) {
                        statement = new Compound(statement, next);
                }

                return statement;
        }

        public static Expression makeBinaryOperator(String symbol,
                        List<Expression> expressions, boolean isLeftAssociative) {
                expressions = new ArrayList<Expression>(expressions);
                if (isLeftAssociative) {
                        Collections.reverse(expressions);
                }

                return makeBinaryOperator1(symbol, expressions, isLeftAssociative);
        }

        private static Expression makeBinaryOperator1(String symbol,
                        List<Expression> expressions, boolean isLeftAssociative) {
                if (expressions.size() == 1) {
                        return expressions.get(0);
                }
                Expression left = expressions.get(0);
                expressions.remove(0);
                Expression right = makeBinaryOperator1(symbol, expressions,
                                isLeftAssociative);

                if (isLeftAssociative) {
                        return makeBinaryOperator(symbol, right, left);
                } else {
                        return makeBinaryOperator(symbol, left, right);
                }
        }

        private static Expression makeBinaryOperator(String op, Expression e1, Expression e2) {
                if ("/".equals(op)) {
                        return new Div(e1, e2);
                } else if ("-".equals(op)) {
                        return new Sub(e1, e2);
                } else if (">".equals(op)) {
                        return new Gt(e1, e2);
                } else {
                        throw new IllegalArgumentException("Unknown operator: " + op);
                }
        }

  final public Statement program() throws ParseException {
        Statement t;
    t = statements();
    jj_consume_token(0);
                {if (true) return t;}
    throw new Error("Missing return statement in function");
  }

  final public Statement statements() throws ParseException {
        Statement t;
        List<Statement> list = new ArrayList<Statement>();
    t = statement();
                          list.add(t);
    label_1:
    while (true) {
      switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
      case OUTPUT:
      case WHILE:
      case IF:
      case VAR:
      case IDENTIFIER:
      case 25:
        ;
        break;
      default:
        jj_la1[0] = jj_gen;
        break label_1;
      }
      t = statement();
                            list.add(t);
    }
                {if (true) return makeStatement(list);}
    throw new Error("Missing return statement in function");
  }

  final public Statement statement() throws ParseException {
        Statement t;
    switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
    case VAR:
      t = declaration();
      break;
    case IDENTIFIER:
      t = assignment();
      break;
    case IF:
      t = ifs();
      break;
    case WHILE:
      t = whiles();
      break;
    case 25:
      t = block();
      break;
    case OUTPUT:
      t = output();
      break;
    default:
      jj_la1[1] = jj_gen;
      jj_consume_token(-1);
      throw new ParseException();
    }
                {if (true) return t;}
    throw new Error("Missing return statement in function");
  }

  final public Statement declaration() throws ParseException {
        Token t;
        List<Identifier> ids = new ArrayList<Identifier>();
    jj_consume_token(VAR);
    t = jj_consume_token(IDENTIFIER);
                                 ids.add(new Identifier(t.image));
    label_2:
    while (true) {
      switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
      case COMMA:
        ;
        break;
      default:
        jj_la1[2] = jj_gen;
        break label_2;
      }
      jj_consume_token(COMMA);
      t = jj_consume_token(IDENTIFIER);
                                 ids.add(new Identifier(t.image));
    }
    jj_consume_token(SEMICOLON);
                {if (true) return new Declaration(ids);}
    throw new Error("Missing return statement in function");
  }

  final public Statement assignment() throws ParseException {
        Token t;
        Expression e;
    t = jj_consume_token(IDENTIFIER);
    jj_consume_token(ASSIGN);
    e = expression();
    jj_consume_token(SEMICOLON);
                {if (true) return new Assignment(new Identifier(t.image), e);}
    throw new Error("Missing return statement in function");
  }

  final public Expression expression() throws ParseException {
        Expression e;
        List<Expression> list = new ArrayList<Expression>();
    e = additive();
                         list.add(e);
    label_3:
    while (true) {
      switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
      case GT:
        ;
        break;
      default:
        jj_la1[3] = jj_gen;
        break label_3;
      }
      jj_consume_token(GT);
      e = additive();
                               list.add(e);
    }
                {if (true) return makeBinaryOperator(">", list, true);}
    throw new Error("Missing return statement in function");
  }

  final public Expression additive() throws ParseException {
        Expression e;
        List<Expression> list = new ArrayList<Expression>();
    e = multiplicative();
                               list.add(e);
    label_4:
    while (true) {
      switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
      case MINUS:
        ;
        break;
      default:
        jj_la1[4] = jj_gen;
        break label_4;
      }
      jj_consume_token(MINUS);
      e = multiplicative();
                                     list.add(e);
    }
                {if (true) return makeBinaryOperator("-", list, true);}
    throw new Error("Missing return statement in function");
  }

  final public Expression multiplicative() throws ParseException {
        Expression e;
        List<Expression> list = new ArrayList<Expression>();
    e = unary();
                      list.add(e);
    label_5:
    while (true) {
      switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
      case SLASH:
        ;
        break;
      default:
        jj_la1[5] = jj_gen;
        break label_5;
      }
      jj_consume_token(SLASH);
      e = unary();
                            list.add(e);
    }
                {if (true) return makeBinaryOperator("/", list, true);}
    throw new Error("Missing return statement in function");
  }

  final public Expression unary() throws ParseException {
        Token t;
        Expression e;
    switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {
    case INTEGER_LITERAL:
      t = jj_consume_token(INTEGER_LITERAL);
                                {if (true) return new Constant(Integer.parseInt(t.image));}
      break;
    case IDENTIFIER:
      t = jj_consume_token(IDENTIFIER);
                             {if (true) return new Identifier(t.image);}
      break;
    case INPUT:
      e = input();
                        {if (true) return e;}
      break;
    default:
      jj_la1[6] = jj_gen;
      jj_consume_token(-1);
      throw new ParseException();
    }
    throw new Error("Missing return statement in function");
  }

  final public Expression input() throws ParseException {
    jj_consume_token(INPUT);
                {if (true) return new Input();}
    throw new Error("Missing return statement in function");
  }

  final public Statement ifs() throws ParseException {
        Expression c;
        Statement s;
    jj_consume_token(IF);
    jj_consume_token(LPAREN);
    c = expression();
    jj_consume_token(RPAREN);
    s = statement();
                {if (true) return new If(c, s);}
    throw new Error("Missing return statement in function");
  }

  final public Statement whiles() throws ParseException {
        Expression c;
        Statement s;
    jj_consume_token(WHILE);
    jj_consume_token(LPAREN);
    c = expression();
    jj_consume_token(RPAREN);
    s = statement();
                {if (true) return new While(c, s);}
    throw new Error("Missing return statement in function");
  }

  final public Statement block() throws ParseException {
        Statement s;
    jj_consume_token(25);
    s = statements();
    jj_consume_token(26);
                {if (true) return s;}
    throw new Error("Missing return statement in function");
  }

  final public Statement output() throws ParseException {
        Token t;
    jj_consume_token(OUTPUT);
    t = jj_consume_token(IDENTIFIER);
    jj_consume_token(SEMICOLON);
                {if (true) return new Output(t.image);}
    throw new Error("Missing return statement in function");
  }

  /** Generated Token Manager. */
  public WhileLangTokenManager token_source;
  SimpleCharStream jj_input_stream;
  /** Current token. */
  public Token token;
  /** Next token. */
  public Token jj_nt;
  private int jj_ntk;
  private int jj_gen;
  final private int[] jj_la1 = new int[7];
  static private int[] jj_la1_0;
  static {
      jj_la1_init_0();
   }
   private static void jj_la1_init_0() {
      jj_la1_0 = new int[] {0x20015c0,0x20015c0,0x40000,0x100000,0x400000,0x1000000,0x1820,};
   }

  /** Constructor with InputStream. */
  public WhileLang(java.io.InputStream stream) {
     this(stream, null);
  }
  /** Constructor with InputStream and supplied encoding */
  public WhileLang(java.io.InputStream stream, String encoding) {
    try { jj_input_stream = new SimpleCharStream(stream, encoding, 1, 1); } catch(java.io.UnsupportedEncodingException e) { throw new RuntimeException(e); }
    token_source = new WhileLangTokenManager(jj_input_stream);
    token = new Token();
    jj_ntk = -1;
    jj_gen = 0;
    for (int i = 0; i < 7; i++) jj_la1[i] = -1;
  }

  /** Reinitialise. */
  public void ReInit(java.io.InputStream stream) {
     ReInit(stream, null);
  }
  /** Reinitialise. */
  public void ReInit(java.io.InputStream stream, String encoding) {
    try { jj_input_stream.ReInit(stream, encoding, 1, 1); } catch(java.io.UnsupportedEncodingException e) { throw new RuntimeException(e); }
    token_source.ReInit(jj_input_stream);
    token = new Token();
    jj_ntk = -1;
    jj_gen = 0;
    for (int i = 0; i < 7; i++) jj_la1[i] = -1;
  }

  /** Constructor. */
  public WhileLang(java.io.Reader stream) {
    jj_input_stream = new SimpleCharStream(stream, 1, 1);
    token_source = new WhileLangTokenManager(jj_input_stream);
    token = new Token();
    jj_ntk = -1;
    jj_gen = 0;
    for (int i = 0; i < 7; i++) jj_la1[i] = -1;
  }

  /** Reinitialise. */
  public void ReInit(java.io.Reader stream) {
    jj_input_stream.ReInit(stream, 1, 1);
    token_source.ReInit(jj_input_stream);
    token = new Token();
    jj_ntk = -1;
    jj_gen = 0;
    for (int i = 0; i < 7; i++) jj_la1[i] = -1;
  }

  /** Constructor with generated Token Manager. */
  public WhileLang(WhileLangTokenManager tm) {
    token_source = tm;
    token = new Token();
    jj_ntk = -1;
    jj_gen = 0;
    for (int i = 0; i < 7; i++) jj_la1[i] = -1;
  }

  /** Reinitialise. */
  public void ReInit(WhileLangTokenManager tm) {
    token_source = tm;
    token = new Token();
    jj_ntk = -1;
    jj_gen = 0;
    for (int i = 0; i < 7; i++) jj_la1[i] = -1;
  }

  private Token jj_consume_token(int kind) throws ParseException {
    Token oldToken;
    if ((oldToken = token).next != null) token = token.next;
    else token = token.next = token_source.getNextToken();
    jj_ntk = -1;
    if (token.kind == kind) {
      jj_gen++;
      return token;
    }
    token = oldToken;
    jj_kind = kind;
    throw generateParseException();
  }


/** Get the next Token. */
  final public Token getNextToken() {
    if (token.next != null) token = token.next;
    else token = token.next = token_source.getNextToken();
    jj_ntk = -1;
    jj_gen++;
    return token;
  }

/** Get the specific Token. */
  final public Token getToken(int index) {
    Token t = token;
    for (int i = 0; i < index; i++) {
      if (t.next != null) t = t.next;
      else t = t.next = token_source.getNextToken();
    }
    return t;
  }

  private int jj_ntk() {
    if ((jj_nt=token.next) == null)
      return (jj_ntk = (token.next=token_source.getNextToken()).kind);
    else
      return (jj_ntk = jj_nt.kind);
  }

  private java.util.List<int[]> jj_expentries = new java.util.ArrayList<int[]>();
  private int[] jj_expentry;
  private int jj_kind = -1;

  /** Generate ParseException. */
  public ParseException generateParseException() {
    jj_expentries.clear();
    boolean[] la1tokens = new boolean[27];
    if (jj_kind >= 0) {
      la1tokens[jj_kind] = true;
      jj_kind = -1;
    }
    for (int i = 0; i < 7; i++) {
      if (jj_la1[i] == jj_gen) {
        for (int j = 0; j < 32; j++) {
          if ((jj_la1_0[i] & (1<<j)) != 0) {
            la1tokens[j] = true;
          }
        }
      }
    }
    for (int i = 0; i < 27; i++) {
      if (la1tokens[i]) {
        jj_expentry = new int[1];
        jj_expentry[0] = i;
        jj_expentries.add(jj_expentry);
      }
    }
    int[][] exptokseq = new int[jj_expentries.size()][];
    for (int i = 0; i < jj_expentries.size(); i++) {
      exptokseq[i] = jj_expentries.get(i);
    }
    return new ParseException(token, exptokseq, tokenImage);
  }

  /** Enable tracing. */
  final public void enable_tracing() {
  }

  /** Disable tracing. */
  final public void disable_tracing() {
  }

} public class DataflowConstraintSet<V, M> {
	private Map<Integer, DataflowContraint<V>> constraints =
		new HashMap<Integer, DataflowContraint<V>>();
	
	/**
	 * Associates variable to node where it belongs.
	 * Used for interpreting results later.
	 */
	private Map<Integer, M> metainfo = new HashMap<Integer, M>();
	
	/**
	 * Adds constraint xi = F(x1, ..., xn) to the constraint set.
	 */
	public void addConstraint(int variable, DataflowExpression<V> expression, M metainfo) {
		constraints.put(variable, new DataflowContraint<V>(variable, expression));
		this.metainfo.put(variable, metainfo);
	}
	
	/**
	 * Recalculates dependency sets for each constraints. Constraint
	 * Cd depends on constraint xi = ... when xi occurs as variable
	 * in Cd and thus Cd has to be recalculated. 
	 */
	public void recalculateDependencies() {
		for (DataflowContraint<V> constraint : constraints.values()) {
			constraint.clearDependencies();
		}
		
		for (DataflowContraint<V> constraint : constraints.values()) {
			for (int i : constraint.getVariables()) {
				constraints.get(i).addDependent(constraint);
			}
		}
	}
	
	/**
	 * Creates start state for analysis.
	 */
	public V[] createStartState(Domain<V> domain) {
		int size = Collections.max(constraints.keySet()) + 1;
		
		return domain.createStartState(size);
	}
	
	/**
	 * Returns collection of constraints in this set.
	 */
	public Collection<DataflowContraint<V>> getConstraints() {
		return constraints.values();
	}
	
	/**
	 * Helper method for debugging. Outputs variable values with
	 * associated metainfo.
	 */
	public void dumpWithMetainfo(V[] analysis) {
		for (int i = 0; i < analysis.length; i++) {
			System.out.println(metainfo.get(i) + " = " + analysis[i]);
		}
	}
} 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 Solver<V> {
	private Domain<V> domain;
	private DataflowConstraintSet<V, ?> constraints;
	
	/**
	 * Constructs new solver instance.
	 */
	public Solver(Domain<V> domain, DataflowConstraintSet<V, ?> constraints) {
		this.domain = domain;
		this.constraints = constraints;
	}
	
	/**
	 * Solves the analysis. Before solving recalculates constraint
	 * dependencies.
	 */
	public V[] solve() {
		constraints.recalculateDependencies();
		V[] analysis = constraints.createStartState(domain);
		
		// Queue is our worklist.
		Queue<DataflowContraint<V>> queue = new LinkedList<DataflowContraint<V>>();
		queue.addAll(constraints.getConstraints());
		
		while (!queue.isEmpty()) {
			DataflowContraint<V> constraint = queue.poll();
			V x = constraint.getExpression().eval(analysis);
			int v = constraint.getVariable();
			if (!analysis[v].equals(x)) {
				analysis[v] = x;
				// Put all constraints that has to be re-evaluated
				// into the worklist.
				queue.addAll(constraint.getDependent());
			}
		}
		
		return analysis;
	}
} public class AllIntersectOperation<V> implements DataflowExpression<Set<V>> {
	private List<DataflowVariable<Set<V>>> variables;
	
	public AllIntersectOperation(List<DataflowVariable<Set<V>>> variables) {
		this.variables = variables;
	}

	@Override
	public Set<V> eval(Set<V>[] values) {
		Set<V> set = variables.get(0).eval(values);
		
		for (DataflowVariable<Set<V>> v : variables.subList(1, variables.size())) {
			set.retainAll(v.eval(values));
		}
		
		return set;
	}

	@Override
	public void collectVariables(Set<Integer> variables) {
		for (DataflowVariable<Set<V>> v : this.variables) {
			v.collectVariables(variables);
		}
	}
	
	@Override
	public String toString() {
		return "I(" + StringUtil.join(variables, ",") + ")";
	}

} public class PowersetDomain<T> implements Domain<Set<T>> {

	@Override
	public Set<T> bottom() {
		return Collections.<T>emptySet();
	}

	@Override
	public Set<T>[] createStartState(int size) {
		@SuppressWarnings("unchecked")
		Set<T>[] s = new Set[size];
		
		for (int i = 0; i < size; i++) {
			s[i] = bottom();
		}
		
		return s;
	}
	
	/**
	 * Helper method to construct set expression from concrete set.
	 */
	public static <V> DataflowExpression<Set<V>> set(Collection<V> set) {
		Set<V> strings = new HashSet<V>();
		
		for (V i : set) {
			strings.add(i);
		}
		
		return new SetExpression<V>(strings);
	}
	
	/**
	 * Helper method to construct expression for removing single
	 * element from the powerset value.
	 */
	public static <V> DataflowExpression<Set<V>> remove(
		DataflowExpression<Set<V>> set, V e) {
		
		return new RemoveOperation<V>(set, e);
	}
	
	/**
	 * Helper method to construct union operation between two
	 * powerset dataflow expressions.
	 */
	public static <V> DataflowExpression<Set<V>> union(
		DataflowExpression<Set<V>> e1,
		DataflowExpression<Set<V>> e2) {
		
		return new UnionOperation<V>(e1, e2);
	}
	
	/**
	 * Helper method to construct set substract operation.
	 */
	public static <V> DataflowExpression<Set<V>> sub(
		DataflowExpression<Set<V>> e1,
		DataflowExpression<Set<V>> e2) {
		
		return new SubstractOperation<V>(e1, e2);
	}
	
	/**
	 * Helper method to construct singleton set.
	 */
	public static <V> DataflowExpression<Set<V>> one(V e) {
		return new SetExpression<V>(e);
	}

	public static <V> DataflowExpression<Set<V>> empty() {
		return new EmptySet<V>();
	}

}
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import com.infdot.analysis.cfg.Cfg;
import com.infdot.analysis.cfg.ConstraintBuilder;
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.examples.liveness.Liveness;
import com.infdot.analysis.language.expression.visitor.ExpressionNumberingVisitor;
import com.infdot.analysis.language.statement.Statement;
import com.infdot.analysis.language.statement.visitor.StatementExpressionVisitor;
import com.infdot.analysis.parser.ParseException;
import com.infdot.analysis.parser.WhileLang;
import com.infdot.analysis.solver.DataflowConstraintSet;
import com.infdot.analysis.solver.DataflowExpression;
import com.infdot.analysis.solver.DataflowVariable;
import com.infdot.analysis.solver.Solver;
import com.infdot.analysis.solver.lattice.powerset.AllIntersectOperation;
import com.infdot.analysis.solver.lattice.powerset.PowersetDomain;
package com.infdot.analysis.examples.iv;



public class InitializedVariablesExample extends ConstraintBuilder<Set<String>> {

	/**
	 * For assignments we have [[n]] = insersect [[w]] U {id}
	 */
	@Override
	public DataflowExpression<Set<String>> assignment(AssignmentNode assignment) {
		return PowersetDomain.union(
			intersect(assignment),
			PowersetDomain.one(assignment.getIdentifier().getName())
		);
	}

	@Override
	public DataflowExpression<Set<String>> declaration(DeclarationNode declaration) {
		return intersect(declaration);
	}

	@Override
	public DataflowExpression<Set<String>> exit(ExitNode exit) {
		return intersect(exit);
	}

	@Override
	public DataflowExpression<Set<String>> output(OutputNode output) {
		return intersect(output);
	}

	@Override
	public DataflowExpression<Set<String>> condition(ConditionNode condition) {