/* ____ ____ ____ ____ ______ *\
** / __// __ \/ __// __ \/ ____/ SOcos COmpiles Scala **
** __\_ \/ /_/ / /__/ /_/ /\_ \ (c) 2002, LAMP/EPFL **
** /_____/\____/\___/\____/____/ **
** **
** $Id$
\* */
package scalac.transformer.matching;
import ch.epfl.lamp.util.Position;
import scalac.*;
import scalac.ast.*;
import scalac.util.*;
import scalac.symtab.*;
import scalac.typechecker.*;
import PatternNode.*;
import Tree.*;
import scalac.transformer.TransMatch.Matcher ;
import java.util.Vector ;
import java.util.Iterator ;
public class PatternMatcher extends PatternTool {
/** the owner of the pattern matching expression
*/
Symbol owner;
/** the selector expression
*/
Tree selector;
/** the root of the pattern node structure
*/
PatternNode root;
/** the symbol of the result variable
*/
Symbol resultVar;
/** the statics of class Boolean
*/
//Symbol statics;
/** container
*/
Matcher _m;
/** methods to generate scala code
*/
CodeFactory cf;
/** methods to create pattern nodes
*/
PatternNodeCreator mk;
/** constructor
*/
public PatternMatcher( Unit unit, Infer infer ) {
super( unit, infer );
}
/** constructs an algebraic pattern matcher from cases
*/
public void construct( Matcher m, Tree[] cases /*, boolean doBinding*/) {
//this.doBinding = doBinding;
this._m = m;
initialize();
for( int i = 0; i < cases.length; i++ ) {
enter( (CaseDef) cases[i]/*, i*/ );
}
_m.tree = toTree();
}
/** initializes this AlgebraicMatcher, see Matcher.initialize
*/
protected void initialize() {
this.mk = new PatternNodeCreator( unit, infer, _m.owner );
this.cf = new CodeFactory( unit, infer/*, _m.pos*/ );
this.owner = _m.owner;
this.selector = _m.selector;
this.root = mk.ConstrPat( _m.pos,
_m.selector.type.widen() );
this.root.and = mk.Header( _m.pos,
_m.selector.type.widen(),
gen.Ident( _m.pos, root.symbol() )
.setType(_m.selector.type.widen()));
this.resultVar = new TermSymbol(_m.pos,
/*cf.*/fresh.newName( RESULT_N ),
_m.owner,
Modifiers.MUTABLE );
//this.resultType = resultType;
this.resultVar.setType( _m.resultType );
//System.out.println(" constructed matcherDefs ");
}
/** return the analyzed type
*/
public Type typeOf(Symbol sym) {
return sym.type();
//return sym.typeAt(unit.global.ANALYZER_PHASE.id);
}
/** return the analyzed type
*/
public Type typeOf0(Symbol sym) {
return sym.typeAt(unit.global.PHASE.ANALYZER.id);
}
//
public void updateBody(Body tree, ValDef[] bound, Tree guard, Tree body) {
if (tree.guard[tree.guard.length - 1] == Tree.Empty)
unit.error(body.pos, "unreachable code");
ValDef[][] bd = new ValDef[tree.bound.length + 1][];
Tree[] ng = new Tree[tree.guard.length + 1];
Tree[] nb = new Tree[tree.body.length + 1];
System.arraycopy(tree.bound, 0, bd, 0, tree.bound.length);
System.arraycopy(tree.guard, 0, ng, 0, tree.guard.length);
System.arraycopy(tree.body, 0, nb, 0, tree.body.length);
bd[bd.length - 1] = bound;
ng[ng.length - 1] = guard;
nb[nb.length - 1] = body;
tree.bound = bd;
tree.guard = ng;
tree.body = nb;
}
public TermSymbol newVar(int pos, Name name, Type type) {
TermSymbol sym = new TermSymbol(pos, name, owner, 0);
sym.setType(type);
return sym;
}
public TermSymbol newVar(int pos, Type type) {
return newVar(pos, fresh.newName("temp"), type);
}
public Tree copy(Tree tree) {
return tree; // insert copy function here
}
/** pretty printer
*/
public void print() {
print(root.and, "");
}
public void print(PatternNode patNode, String indent) {
if (patNode == null)
System.out.println(indent + "NULL");
else
switch (patNode) {
case Header(Tree selector, Header next):
System.out.println(indent + "HEADER(" + patNode.type +
", " + selector + ")");
print(patNode.or, indent + "|");
if (next != null)
print(next, indent);
break;
case ConstrPat(Symbol casted):
String s = "-- " + patNode.type.symbol().name +
"(" + patNode.type + ", " + casted + ") -> ";
String ind = indent;
indent = (patNode.or != null) ?
indent :
indent.substring(0, indent.length() - 1) + " ";
for (int i = 0; i < s.length(); i++)
indent += " ";
System.out.println(ind + s);
print(patNode.and, indent);
if (patNode.or != null)
print(patNode.or, ind);
break;
case SequencePat(Symbol casted, int plen, _):
String s = "-- " + patNode.type.symbol().name + "(" + patNode.type +
", " + casted + ", " + plen + ") -> ";
String ind = indent;
indent = (patNode.or != null) ?
indent :
indent.substring(0, indent.length() - 1) + " ";
for (int i = 0; i < s.length(); i++)
indent += " ";
System.out.println(ind + s);
print(patNode.and, indent);
if (patNode.or != null)
print(patNode.or, ind);
break;
case DefaultPat():
System.out.println(indent + "-- _ -> ");
print(patNode.and, indent.substring(0, indent.length() - 1) +
" ");
if (patNode.or != null)
print(patNode.or, indent);
break;
case ConstantPat(Object value):
String s = "-- CONST(" + value + ") -> ";
String ind = indent;
indent = (patNode.or != null) ?
indent :
indent.substring(0, indent.length() - 1) + " ";
for (int i = 0; i < s.length(); i++)
indent += " ";
System.out.println(ind + s);
print(patNode.and, indent);
if (patNode.or != null)
print(patNode.or, ind);
break;
case VariablePat(Tree tree):
String s = "-- STABLEID(" + tree + ": " + patNode.type + ") -> ";
String ind = indent;
indent = (patNode.or != null) ?
indent :
indent.substring(0, indent.length() - 1) + " ";
for (int i = 0; i < s.length(); i++)
indent += " ";
System.out.println(ind + s);
print(patNode.and, indent);
if (patNode.or != null)
print(patNode.or, ind);
break;
case Body(_, _, Tree[] stats):
System.out.println(indent + "BODY(" + stats.length + ")");
break;
}
}
public void enter(CaseDef tree) {
enter(tree.pos, tree.pat, tree.guard, tree.body);
}
protected CaseEnv enter(int pos, Tree pat, Tree guard, Tree body) {
CaseEnv env = new CaseEnv( _m.owner, unit );
//PatternNode matched = match(pat, root);
PatternNode target = enter1(pat, -1, root, root.symbol(), env);
//if (target.and != null)
// unit.error(pat.pos, "duplicate case");
if (target.and == null)
target.and = mk.Body(pos, env.boundVars(), guard, body);
else if (target.and instanceof Body)
updateBody((Body)target.and, env.boundVars(), guard, body);
else
unit.error(pat.pos, "duplicate case");
return env;
}
public PatternNode match(Tree pat, PatternNode target) {
// advance one step in pattern
PatternNode next = target.and;
// we are done (no match yet)
if (next == null)
return null;
// check if matched
switch (next) {
case Body(_, _, _):
return next;
case Header(_, _):
Header header = (Header)next;
// get pattern arguments
Tree[] patArgs = patternArgs(pat);
// get next pattern node
PatternNode patNode = patternNode(pat, header, null);
do {
next = header;
while ((next = next.or) != null)
if (superPat(next, patNode) &&
((target = match(patArgs, next)) != null))
return target;
else if (isDefaultPat(next))
return next.and;
} while ((header = header.next) != null);
return null;
default:
throw new ApplicationError();
}
}
public PatternNode match(Tree[] pats, PatternNode target) {
for (int i = 0; i < pats.length; i++)
if ((target = match(pats[i], target)) == null)
return null;
return target;
}
protected Tree[] patternArgs(Tree tree) {
switch (tree) {
case Apply(_, Tree[] args):
if (args.length == 1 && (tree.type.symbol().flags & Modifiers.CASE) == 0)
switch (args[0]) {
case Sequence(Tree[] ts):
return ts;
}
return args;
case Sequence(Tree[] ts):
//if( TestRegTraverser.apply( tree ) )
// return Tree.EMPTY_ARRAY; // let sequence matcher handle it
return ts;
default:
return Tree.EMPTY_ARRAY;
}
}
protected Type getConstrType(Type tpe) {
return tpe;
/*
switch (tpe) {
case ConstructorType(Type result):
return result;
default:
return tpe;
} */
}
protected Type getHeaderType(Type tpe) {
switch (tpe) {
case PolyType(_, Type res):
return res;
default:
return tpe;
}
}
protected PatternNode patternNode(Tree tree, Header header, CaseEnv env) {
switch (tree) {
case Apply(Tree fn, Tree[] args): // pattern with args
if (args.length == 1 && (tree.type.symbol().flags & Modifiers.CASE) == 0)
switch (args[0]) {
case Sequence(Tree[] ts):
return mk.SequencePat(tree.pos, tree.type, ts.length, args[0]);
}
return mk.ConstrPat(tree.pos, getConstrType(tree.type));
case Typed(Ident(Name name), Tree tpe): // variable pattern
PatternNode node =
(header.type.isSubType(getConstrType(tpe.type))) ?
mk.DefaultPat(tree.pos, getConstrType(tpe.type))
: mk.ConstrPat(tree.pos, getConstrType(tpe.type));
if ((env != null) && (name != WILDCARD_N))
switch (node) {
case ConstrPat(Symbol casted):
env.newBoundVar(
tree.pos,
((Tree.Typed)tree).expr.symbol(),
getConstrType(tpe.type),
make.Ident(tree.pos, casted.name).
setType(typeOf(casted)).
setSymbol(casted));
break;
default:
env.newBoundVar(
tree.pos,
((Tree.Typed)tree).expr.symbol(),
getConstrType(tpe.type),
header.selector);
}
return node;
case Ident(Name name): // pattern without args or variable
if (tree.symbol().isPrimaryConstructor())
return mk.ConstrPat(tree.pos, getConstrType(tree.type));
else if (name.isVariable()) {
if ((env != null) && (name != WILDCARD_N))
env.newBoundVar(
tree.pos,
tree.symbol(),
getConstrType(tree.type),
header.selector);
return mk.DefaultPat(tree.pos, getConstrType(header.type));
} else
return mk.VariablePat(tree.pos, tree);
case Select(_, Name name): // variable
if (tree.symbol().isPrimaryConstructor())
return mk.ConstrPat(tree.pos, getConstrType(tree.type));
else
return mk.VariablePat(tree.pos, tree);
case Literal(Object value):
return mk.ConstantPat(tree.pos, getConstrType(tree.type), value);
case Sequence(Tree[] ts):
return mk.SequencePat(tree.pos, tree.type, ts.length, tree);
case Alternative(Tree[] ts): // CAN THIS WORK ?
assert ts.length > 0;
PatternNode res = patternNode( ts[ 0 ], header, env );
for( int i = 1; i<ts.length; i++ ) {
res.or = patternNode( ts[ i ], header, env );
res = res.or ;
}
return res;
default:
new scalac.ast.printer.TextTreePrinter().print(tree).flush();
throw new ApplicationError(tree);
}
}
protected boolean superPat(PatternNode p, PatternNode q) {
switch (p) {
case DefaultPat():
switch (q) {
case DefaultPat():
return true;
//case ConstantPat(_, _):
// return q.type.isSubType(p.type);
}
return false;
case ConstrPat(_):
switch (q) {
case ConstrPat(_):
return q.type.isSubType(p.type);
}
return false;
case SequencePat(_, int plen, _):
switch (q) {
case SequencePat(_, int qlen, _):
return (plen == qlen) && q.type.isSubType(p.type);
}
return false;
case ConstantPat(Object pval):
switch (q) {
case ConstantPat(Object qval):
return pval.equals(qval);
}
return false;
case VariablePat(Tree tree):
switch (q) {
case VariablePat(Tree other):
return (tree.symbol() != null) &&
(tree.symbol().kind != Kinds.NONE) &&
(tree.symbol().kind != Kinds.ERROR) &&
(tree.symbol() == other.symbol());
}
return false;
}
return false;
}
protected boolean isDefaultPat(PatternNode p) {
switch (p) {
case DefaultPat():
return true;
default:
return false;
}
}
public PatternNode enter(Tree pat,
int index,
PatternNode target,
Symbol casted,
CaseEnv env) {
switch (target) {
case ConstrPat(Symbol newCasted):
return enter1(pat, index, target, newCasted, env);
case SequencePat(Symbol newCasted, int len, _):
return enter1(pat, index, target, newCasted, env);
default:
return enter1(pat, index, target, casted, env);
}
}
public PatternNode enter1(Tree pat,
int index,
PatternNode target,
Symbol casted,
CaseEnv env) {
//System.out.println("enter(" + pat + ", " + index + ", " + target + ", " + casted + ")");
// get pattern arguments
Tree[] patArgs = patternArgs(pat);
// get case fields
//assert patArgs.length == nCaseComponents(pat);
// advance one step in pattern
Header curHeader = (Header)target.and;
// check if we have to add a new header
if (curHeader == null) {
assert index >= 0 : casted;
if (casted.pos == Position.NOPOS) {
Symbol atSym = casted.type().lookup(AT_N);
//System.out.println("casted type = " + typeOf(casted));
Type seqType = casted.type().baseType(defs.SEQ_CLASS).typeArgs()[0];
Tree t = make.Select(
pat.pos,
make.Ident(pat.pos, casted.name)
.setType(typeOf(casted))
.setSymbol(casted),
AT_N);
switch (typeOf(atSym)) {
case OverloadedType(Symbol[] alts, Type[] alttypes):
infer.methodAlternative(t, alts, alttypes,
new Type[]{defs.INT_TYPE}, seqType);
t = make.Apply(pat.pos, t,
new Tree[]{
make.Literal(pat.pos, new Integer(index))
.setType(defs.INT_TYPE)
}).setType(seqType);
break;
default:
t.setSymbol(atSym);
t.setType(typeOf(atSym));
t = make.Apply(pat.pos, t,
new Tree[]{
make.Literal(pat.pos, new Integer(index))
.setType(defs.INT_TYPE)
}).setType(seqType);
}
target.and = curHeader = mk.Header(pat.pos, seqType, t);
} else {
Symbol ts = ((ClassSymbol) casted.type().symbol())
.caseFieldAccessor(index);
// target.and = curHeader = mk.Header(
// pat.pos,
// getHeaderType(typeOf0(ts)),
// make.Select(
// pat.pos,
// make.Ident(pat.pos, casted.name)
// .setType(typeOf(casted))
// .setSymbol(casted),
// ts.name)
// .setType(getHeaderType(typeOf0(ts)))
// .setSymbol(ts));
target.and = curHeader = mk.Header(
pat.pos,
getHeaderType(typeOf0(ts)),
make.Apply(
pat.pos,
make.Select(
pat.pos,
make.Ident(pat.pos, casted.name)
.setType(typeOf(casted))
.setSymbol(casted),
ts.name)
.setType(Type.MethodType(
Symbol.EMPTY_ARRAY,
getHeaderType(typeOf0(ts))))
.setSymbol(ts),
Tree.EMPTY_ARRAY).setType(getHeaderType(typeOf0(ts))));
}
curHeader.or = patternNode(pat, curHeader, env);
return enter(patArgs, curHeader.or, casted, env);
}
// find most recent header
while (curHeader.next != null)
curHeader = curHeader.next;
// create node
PatternNode patNode = patternNode(pat, curHeader, env);
PatternNode next = curHeader;
// enter node
while (true)
if (superPat(next, patNode))
return enter(patArgs, next, casted, env);
else if (isDefaultPat(next) ||
((next.or == null) && isDefaultPat(patNode)))
return enter(
patArgs,
(curHeader = (curHeader.next =
mk.Header(patNode.pos, curHeader.type, curHeader.selector))).or
= patNode,
casted,
env);
else if (next.or == null)
return enter(patArgs, next.or = patNode, casted, env);
else
next = next.or;
}
public PatternNode enter(Tree[] pats, PatternNode target, Symbol casted, CaseEnv env) {
switch (target) {
case ConstrPat(Symbol newCasted):
casted = newCasted;
break;
case SequencePat(Symbol newCasted, int len, _):
casted = newCasted;
break;
}
for (int i = 0; i < pats.length; i++)
target = enter1(pats[i], i, target, casted, env);
return target;
}
protected int nCaseComponents(Tree tree) {
switch (tree) {
case Apply(Tree fn, _):
Type tpe = typeOf(tree.type.symbol().constructor());
//System.out.println("~~~ " + tree.type() + ", " + tree.type().symbol().constructor());
switch (tpe) {
// I'm not sure if this is a good idea, but obviously, currently all case classes
// without constructor arguments have type NoType
case NoType:
return 0;
case MethodType(Symbol[] args, _):
return args.length;
case PolyType(Symbol[] tvars, MethodType(Symbol[] args, _)):
return args.length;
case PolyType(Symbol[] tvars, _):
return 0;
default:
throw new ApplicationError("not yet implemented;" +
"pattern matching for " + tree + ": " + tpe);
}
}
return 0;
}
//////////// generator methods
public Tree toTree() {
TreeList ts = new TreeList();
ts.append(
make.ValDef(selector.pos,
0,
root.symbol().name,
gen.mkType(selector.pos, selector.type),
selector).setType(defs.UNIT_TYPE).setSymbol(root.symbol()));
ts.append(
make.ValDef(selector.pos,
Modifiers.MUTABLE,
resultVar.name,
gen.mkType(selector.pos, typeOf(resultVar)),
Tree.Empty).setType(defs.UNIT_TYPE).setSymbol(resultVar));
ts.append(
make.If(
selector.pos,
toTree(root.and),
make.Ident(selector.pos,
resultVar.name).setType(typeOf(resultVar)).setSymbol(resultVar),
cf.ThrowMatchError(selector.pos, typeOf(resultVar))).setType(typeOf(resultVar)));
return cf.Block(selector.pos, ts.toArray(), typeOf(resultVar));
}
protected Tree toTree(PatternNode node) {
Tree res = gen.mkBooleanLit(node.pos, false);
while (node != null)
switch (node) {
case Header(Tree selector, Header next):
//res = cf.And(mkNegate(res), toTree(node.or, selector));
//System.out.println("HEADER TYPE = " + selector.type);
res = cf.Or(res, toTree(node.or, selector));
node = next;
break;
case Body(ValDef[][] bound, Tree[] guard, Tree[] body):
for (int i = guard.length - 1; i >= 0; i--) {
Tree[] ts = new Tree[bound[i].length + 1];
System.arraycopy(bound[i], 0, ts, 0, bound[i].length);
ts[bound[i].length] = cf.Block(body[i].pos,
new Tree[]{
make.Assign(
body[i].pos,
make.Ident(body[i].pos, resultVar.name)
.setType(typeOf(resultVar)).setSymbol(resultVar),
body[i]).setType(defs.UNIT_TYPE),
gen.mkBooleanLit(body[i].pos, true)
}, defs.BOOLEAN_TYPE);
if (guard[i] != Tree.Empty)
ts[bound[i].length] = cf.And(guard[i], ts[bound[i].length]);
res = cf.Or(cf.Block(body[i].pos, ts, defs.BOOLEAN_TYPE), res);
}
return res;
default:
throw new ApplicationError();
}
return res;
}
protected Tree toTree(PatternNode node, Tree selector) {
if (node == null)
return gen.mkBooleanLit(selector.pos, false);
switch (node) {
case DefaultPat():
return toTree(node.and);
case ConstrPat(Symbol casted):
return make.If(
selector.pos,
cf.Is(selector.duplicate(), node.type),
cf.Block(selector.pos,
new Tree[]{
make.ValDef(selector.pos,
0,
casted.name,
gen.mkType(selector.pos, node.type),
cf.As(selector.duplicate(), node.type))
.setType(defs.UNIT_TYPE).setSymbol(casted),
toTree(node.and)}, defs.BOOLEAN_TYPE),
toTree(node.or, selector.duplicate())).setType(defs.BOOLEAN_TYPE);
case SequencePat(Symbol casted, int len, Tree tree):
Symbol lenSym = casted.type().lookup(LENGTH_N);
Tree t = make.Select(selector.pos, cf.As(selector.duplicate(), node.type), LENGTH_N);
switch (typeOf(lenSym)) {
case OverloadedType(Symbol[] alts, Type[] alttypes):
infer.methodAlternative(t, alts, alttypes, new Type[0], defs.INT_TYPE);
break;
default:
t.setSymbol(lenSym);
t.setType(typeOf(lenSym));
}
return make.If(
selector.pos,
cf.And(
cf.Is(selector.duplicate(), node.type),
cf.Equals(
make.Apply(
selector.pos, t,
Tree.EMPTY_ARRAY).setType(defs.INT_TYPE),
make.Literal(selector.pos, new Integer(len))
.setType(defs.INT_TYPE))),
cf.Block(selector.pos,
new Tree[]{
make.ValDef(selector.pos,
0,
casted.name,
gen.mkType(selector.pos, node.type),
cf.As(selector.duplicate(), node.type))
.setType(defs.UNIT_TYPE).setSymbol(casted),
toTree(node.and)}, defs.BOOLEAN_TYPE),
toTree(node.or, selector.duplicate()))
.setType(defs.BOOLEAN_TYPE);
case ConstantPat(Object value):
return make.If(
selector.pos,
cf.Equals(selector.duplicate(),
make.Literal(selector.pos, value)
.setType(node.type)),
toTree(node.and),
toTree(node.or, selector.duplicate())).setType(defs.BOOLEAN_TYPE);
case VariablePat(Tree tree):
return make.If(
selector.pos,
cf.Equals(selector.duplicate(), tree),
toTree(node.and),
toTree(node.or, selector.duplicate())).setType(defs.BOOLEAN_TYPE);
default:
throw new ApplicationError();
}
}
/** collects all sequence patterns and returns the default
*/
PatternNode collectSeqPats( PatternNode node,
Vector seqPatNodes,
Vector bodies ) {
PatternNode defaultNode = null;
do {
if( node == null )
break;// defaultNode = node;
else
switch( node ) {
case SequencePat( _, _, _ ):
seqPatNodes.add( node );
bodies.add( toTree( node.and ) );
node = node.or;
break;
default:
defaultNode = node;
}
} while (defaultNode == null) ;
System.out.println("collectSeqPats(1):"+seqPatNodes);
System.out.println("collectSeqPats(2):"+bodies);
return defaultNode;
}
Tree callSequenceMatcher( PatternNode node,
Tree selector) {
System.out.println("callSequenceMatcher("+node+","+selector+")");
/* ???????????????????????? necessary to test whether is a Seq?
make.If(selector.pos,
maybe cf.And( cf.Is(selector, seqpat.type())
...
*/
// translate the _.and subtree of this SequencePat
Vector seqPatNodes = new Vector();
Vector bodies = new Vector();
PatternNode defaultNode = collectSeqPats( node,
seqPatNodes,
bodies );
Tree defaultCase = toTree( defaultNode, selector );
SequenceMatcher wordRec = new SequenceMatcher(unit, infer);
Matcher m = new Matcher( _m.owner,
selector,
defs.BOOLEAN_TYPE );
Tree pats[] = new Tree[ seqPatNodes.size() ];
Tree body[] = new Tree[ seqPatNodes.size() ];
Object tmp[] = bodies.toArray();
int j = 0;
for( Iterator it = seqPatNodes.iterator();
it.hasNext();) {
pats[ j ] = ((SequencePat) it.next()).seqpat;
body[ j ] = (Tree) tmp[j];
j++;
}
wordRec.construct( m, pats, body, defaultCase, true /*doBinding*/ );
return m.tree;
}
}