/* File: SimpleMatcher.java
 * Contains: A simple pattern-matcher
 * Author: Jeff Dalton <J.Dalton@ed.ac.uk>
 * Created: January 1998
 * Updated: Tue Dec  4 22:43:03 2001 by Jeff Dalton
 * Copyright: (c) 1998, AIAI, University of Edinburgh
 */

package ix.util.match;

import java.util.*;
import ix.util.*;
import ix.util.lisp.*;

import ix.icore.process.Variable; // sigh /\/


/**
 * A simple pattern-matcher.
 */

public final class SimpleMatcher {

    /**
     * emptyEnv is used to return non-null without allocating an env.
     */
    public static final MatchEnv emptyEnv = new MatchEnv() {
	public Object put(Object key, Object Value) {
	    Debug.assert(false, "emptyEnv can't be modified");
	    return null;
	}
    };

    public static final Symbol REST = Symbol.intern("&rest");

    public static final 
    MatchEnv mustMatch(Object pat, Object dat) {
	return mustMatch(pat, dat, null);
    }

    public static final
    MatchEnv mustMatch(Object pat, Object dat, MatchEnv env) {
	MatchEnv result = match(pat, dat, env);
	Debug.assert(result != null, "Failed to match", pat);
	return result;
    }

    /**
     * Match tries to match a pattern against an object. <p>
     *
     * Only the pattern can contain variables.  If a variable appears
     * more than once in a pattern, there's no attempt to check that it
     * matches the same thing each time.<p>
     *
     * For now, numbers are compared as objects, not by comparing
     * their numeric values.
     *
     * @return a MatchEnv or null.
     *
     * @see MatchEnv
     * @see ix.util.lisp.ItemVar
     */

    public static final MatchEnv match(Object pat, Object dat) {
	return match(pat, dat, null);
    }

    public static final MatchEnv match(Object pat, Object dat, MatchEnv env) {
	if (pat instanceof ItemVar) {
	    if (env == null)
		env = new MatchEnv();
	    if (dat instanceof Variable) {
		Object val = ((Variable)dat).getValue();
		if (val != null)
		    // Don't let Variables propagate any further
		    // than they have to.
		    dat = val;
	    }
	    env.put(pat, dat);
	    return env;
	}
	else if (pat == dat) {
	    return success(env);
	}
	else if (pat instanceof Cons && ((Cons)pat).car() == REST) {
	    return matchRest(pat, dat, env);
	}
	else if (pat.getClass() != dat.getClass()) {
	    return null;
	}
	else if (pat instanceof Symbol) {
	    return null;	// matching symbols would have been ==
	}
	else if (pat instanceof String) {
	    return when(((String)pat).equals((String)dat), env);
	}
	else if (pat instanceof Cons) {
	    Cons p = (Cons)pat;
	    Cons d = (Cons)dat;
	    MatchEnv e = match(p.car(), d.car(), env);
	    if (e == null)
		return null;
	    else if (e == emptyEnv)
		return match(p.cdr(), d.cdr(), null);
	    else
		return when(match(p.cdr(), d.cdr(), e) != null,
			    e);
	}
	else {
	    return null;
	}

    }

    private static final MatchEnv matchRest(Object pat, Object dat,
					    MatchEnv env) {
	if (!(dat instanceof LList))
	    return null;

	Cons p = (Cons)pat;
	Object var = p.cdr().car();

	if (var == Lisp.NIL)	 	// (&rest) matches any List
	    return success(env);

	Debug.assert(var instanceof ItemVar, "(&rest ?var ...)");
	Debug.assert(p.cdr().cdr() == Lisp.NIL, "(&rest ?var)");

	if (env == null)
	    env = new MatchEnv();
	env.put(var, dat);
	return env;
    }

    private static final MatchEnv when(boolean cond, MatchEnv env) {
	if (cond)
	    return success(env);
	else
	    return null;
    }

    private static final MatchEnv success(MatchEnv env) {
	if (env == null)
	    return emptyEnv;
	else
	    return env;
    }

}