package mclint.patterns;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

import mclint.util.Parsing;
import natlab.refactoring.AbstractNodeFunction;
import natlab.toolkits.utils.NodeFinder;
import ast.ASTNode;
import ast.Expr;
import ast.ForStmt;
import ast.Program;
import ast.Stmt;

public class Matcher {
  private static final boolean DEBUG = false;
  private UnparsedPattern pattern;
  private Stack<Object> stack;
  private ASTNode tree;
  private Map<Character, ASTNode> bindings = new HashMap<Character, ASTNode>();

  private static Match match(String pattern, ASTNode tree) {
    Stack<Object> stack = new Stack<Object>();
    stack.push(tree);
    return new Matcher(UnparsedPattern.fromString(pattern), tree, stack).match();
  }
  
  private static <T extends ASTNode> List<Match> findMatching(Class<T> clazz,
      final String pattern, ASTNode tree) {
    final List<Match> matches = new ArrayList<Match>();
    NodeFinder.apply(tree, clazz, new AbstractNodeFunction<T>() {
      @Override
      public void apply(T node) {
        Match match = match(pattern, node);
        if (match != null) {
          matches.add(match);
        }
      }
    });
    return Collections.unmodifiableList(matches);
  }
  
  public static List<Match> findMatchingStatements(String pattern, ASTNode tree) {
    return findMatching(Stmt.class, pattern, tree);
  }
  
  public static List<Match> findMatchingExpressions(String pattern, ASTNode tree) {
    return findMatching(Expr.class, pattern, tree);
  }

  public static List<Match> findAllMatches(String pattern, ASTNode tree) {
    List<Match> matches = new ArrayList<Match>();
    matches.addAll(findMatchingStatements(pattern, tree));
    matches.addAll(findMatchingExpressions(pattern, tree));
    return Collections.unmodifiableList(matches);
  }

  private Matcher(UnparsedPattern pattern, ASTNode tree, Stack<Object> stack) {
    this.pattern = pattern;
    this.tree = tree;
    this.stack = stack;
  }
  
  private Object lookahead() {
    return stack.get(stack.size() - 2);
  }
  
  private void dumpState(int stage) {
    if (DEBUG) {
      System.out.println("Stage: " + stage);
      System.out.println("Stack: " + stack);
      System.out.println("Pattern: " + pattern);
      System.out.println("Bindings: " + bindings);
    }
  }

  private Match match() {
    while (!stack.isEmpty()) {
      if (stack.peek() instanceof String) {
        String top = (String) stack.peek();
        if (pattern.consume(top)) {
          stack.pop();
        } else {
          dumpState(1);
          return null;
        }
      } else if (stack.peek() instanceof ASTNode) {
        // Resolve bind/unparse conflict
        // Lookahead; if we bind, will we fail?
        if (pattern.startsWithMeta()) {
          UnparsedPattern afterMeta = pattern.afterMeta();
          if (stack.size() == 1) {
            if (!pattern.emptyAfterMeta()) {
              unparse();
            }
          } else if (lookahead() instanceof ASTNode && !afterMeta.startsWithMeta()
                  || lookahead() instanceof String && !afterMeta.consume((String) lookahead())) {
            unparse();
          } else {
            if (!bind()) {
              dumpState(2);
              return null;
            }
          }
        } else {
          unparse();
        }
      }
    }
    if (!pattern.finished()) {
      dumpState(3);
      return null;
    }
    return new Match(tree, bindings, pattern);
  }

  private boolean bind() {
    char meta = pattern.popMeta();
    ASTNode tree = (ASTNode) stack.pop();
    if (meta == '_') {
      return true;
    }
    if (bindings.containsKey(meta) && !EqualityChecker.equals(tree, bindings.get(meta))) {
      return false;
    }
    bindings.put(meta, tree);
    return true;
  }

  private void unparse() {
    List<Object> tokens = LazyUnparser.unparse((ASTNode) stack.pop());
    Collections.reverse(tokens);
    for (Object token : tokens) {
      stack.push(token);
    }
  }

  public static void main(String[] args) {
    String pattern = new StringBuilder()
      .append("for %i=(%l:%r)\n")
      .append("  %a(%i) = %_;\n")
      .append("end").toString();
    Program program = Parsing.string(new StringBuilder()
      .append("for i = (1:10) \n")
      .append("  a(i) = 5; \n")
      .append("end \n").toString());
    List<Match> matches = findMatching(ForStmt.class, pattern, program);
    System.out.println(matches);
  }
}

@@ -755,30 +755,41 @@
 (tree);%0A    
-return
+Matcher matcher =
  new Matcher
@@ -842,25 +842,135 @@
 ack)
-.match()
+;%0A    Match match = matcher.match();%0A    if (match == null && DEBUG) %7B%0A      matcher.dumpState();%0A    %7D%0A    return match
 ;%0A  %7D%0A
-  
 %0A
+
   pr
@@ -1438,27 +1438,25 @@
 tches);%0A  %7D%0A
-  
 %0A
+
   public sta
@@ -1582,19 +1582,17 @@
 e);%0A  %7D%0A
-  
 %0A
+
   public
@@ -2177,27 +2177,25 @@
  stack;%0A  %7D%0A
-  
 %0A
+
   private Ob
@@ -2257,18 +2257,16 @@
 2);%0A  %7D%0A
-  
 %0A  priva
@@ -2287,99 +2287,26 @@
 ate(
-int stage) %7B%0A    if (DEBUG) %7B%0A      System.out.println(%22Stage: %22 + stage);%0A      System.out
+) %7B%0A    System.err
 .pri
@@ -2330,36 +2330,34 @@
 stack);%0A    
-  
 System.
-out
+err
 .println(%22Pa
@@ -2377,18 +2377,16 @@
 ttern);%0A
-  
     Syst
@@ -2380,35 +2380,35 @@
 rn);%0A    System.
-out
+err
 .println(%22Bindin
@@ -2426,22 +2426,16 @@
 dings);%0A
-    %7D%0A
   %7D%0A%0A  p
@@ -2656,32 +2656,8 @@
 e %7B%0A
-          dumpState(1);%0A
     
@@ -3298,36 +3298,8 @@
 ) %7B%0A
-              dumpState(2);%0A
     
@@ -3405,24 +3405,24 @@
     %7D%0A    %7D%0A
+
     if (!pat
@@ -3444,28 +3444,8 @@
 ) %7B%0A
-      dumpState(3);%0A
     

Clean up matching algorithm a little