/* ____ ____ ____ ____ ______ *\
** / __// __ \/ __// __ \/ ____/ SOcos COmpiles Scala **
** __\_ \/ /_/ / /__/ /_/ /\_ \ (c) 2002, LAMP/EPFL **
** /_____/\____/\___/\____/____/ **
** **
** $Id$
\* */
package scalac.typechecker;
import java.io.*;
import java.util.*;
import scalac.*;
import scalac.util.*;
import scalac.symtab.*;
import scalac.ast.*;
import scalac.ast.printer.*;
import Tree.*;
/** A transformer for removing syntactic sugar. This transformer does
* not need any type or symbol-table information.
*
* @author Martin Odersky
* @version 2.0
*/
public class DeSugarize implements Kinds, Modifiers {
/** the global environment
*/
protected Global global;
/** the tree factory
*/
protected TreeFactory make;
/** The copying factory
*/
protected TreeCopier copy;
/** the tree generator
*/
protected TreeGen gen;
/** the type inferencer
*/
protected Infer infer;
/** the name creator
*/
protected final FreshNameCreator freshNameCreator;
/** the constructor
*/
public DeSugarize(Analyzer analyzer, Global global) {
this.global = global;
this.make = analyzer.make;
this.copy = analyzer.copy;
this.gen = analyzer.gen;
this.infer = analyzer.infer;
this.freshNameCreator = global.freshNameCreator;
}
// Auxiliary definitions and functions -------------------------------------------
/** introduce fresh variable of the form "ds$56"
*/
Name getvar() {
return freshNameCreator.newName("ds", '$');
}
Name setterName(Name name) {
return name.append(Names._EQ);
}
Name parameterName(int i) {
return Name.fromString("x$" + i);
}
Name tupleSelectorName(int i) {
return Name.fromString("_" + i);
}
/** extract variables from a pattern
*/
void getVariables(Tree tree, ArrayList vars) {
switch(tree) {
case Ident(Name name):
if (name.isVariable() && name != Names.WILDCARD) vars.add(name);
break;
case Typed(Tree expr, Tree type):
getVariables(expr, vars);
break;
case Apply(Tree fn, Tree[] args):
switch (fn) {
case Apply(_, _): getVariables(fn, vars);
}
for (int i = 0; i < args.length; i++)
getVariables(args[i], vars);
break;
case Sequence(Tree[] elems):
for (int i = 0; i < elems.length; i++)
getVariables(elems[i], vars);
break;
case Literal( _ ):
break;
case Bind( Name name, Tree t ):
if (name.isVariable() && name != Names.WILDCARD) vars.add(name);
getVariables( t, vars );
break;
case Alternative( Tree ts[] ):
for (int i = 0; i < ts.length; i++)
getVariables( ts[i], vars );
break;
default:
throw new ApplicationError ("illegal pattern", tree);
}
}
// Transform functions -----------------------------------------------------
/** (T_1, ..., T_N) => T ==> scala.FunctionN[T_1, ..., T_N, +T]
*/
public Tree FunType(Tree tree) {
switch(tree) {
case FunType(Tree[] argtpes, Tree restpe):
Tree[] types = new Tree[argtpes.length + 1];
System.arraycopy(argtpes, 0, types, 0, argtpes.length);
types[argtpes.length] = restpe;
return make.AppliedType(tree.pos,
make.Select(tree.pos,
make.Ident(tree.pos, Names.scala),
Name.fromString("Function" + argtpes.length).toTypeName()),
types);
default:
throw new ApplicationError("function type expected", tree);
}
}
public Tree mkTuple(int pos, Tree[] trees) {
if (trees.length == 0)
return make.Block(pos, trees);
else
return make.Apply(pos,
make.Select(pos,
make.Ident(pos, Names.scala),
Name.fromString("Tuple" + trees.length)),
trees);
}
/** Convert method to function type.
*/
Type meth2fun(Type tp) {
switch (tp) {
case MethodType(Symbol[] params, Type restype):
return global.definitions.functionType(
Symbol.type(params), meth2fun(restype));
default:
return tp;
}
}
/** If `pt' is a matching function type insert missing parameters
* in `vparams' from it, and return result type,
* else return AnyType.
*/
public Type preFunction(ValDef[] vparams, Type pt) {
switch (pt) {
case TypeRef(Type pre, Symbol psym, Type[] ptargs):
if (psym.fullName().startsWith(Names.scala_Function) &&
ptargs.length == vparams.length + 1) {
for (int i = 0; i < vparams.length; i++)
assignType(vparams[i], ptargs[i]);
return ptargs[vparams.length];
}
}
return Type.AnyType;
}
//where
void assignType(ValDef vparam, Type pt) {
if (vparam.tpe == Tree.Empty && infer.isFullyDefined(pt))
vparam.tpe = gen.mkType(vparam.pos, pt);
}
Tree isDefinedAtVisitor(Tree tree) {
switch (tree) {
case Visitor(CaseDef[] cases):
CaseDef lastCase = cases[cases.length - 1];
switch (lastCase) {
case CaseDef(Ident(Name name), Tree.Empty, Tree expr):
if (name.isVariable())
return make.Visitor(tree.pos,
new CaseDef[]{
make.CaseDef(lastCase.pos,
lastCase.pat.duplicate(),
Tree.Empty,
gen.mkBooleanLit(lastCase.body.pos, true))});
}
CaseDef[] cases1 = new CaseDef[cases.length + 1];
for (int i = 0; i < cases.length; i++) {
switch (cases[i]) {
case CaseDef(Tree pat, Tree guard, _):
cases1[i] = (CaseDef) make.CaseDef(
cases[i].pos,
pat.duplicate(),
guard.duplicate(),
gen.mkBooleanLit(tree.pos, true));
}
}
cases1[cases.length] = (CaseDef) make.CaseDef(
tree.pos,
make.Ident(tree.pos, Names.WILDCARD),
Tree.Empty,
gen.mkBooleanLit(tree.pos, false));
return make.Visitor(tree.pos, cases1);
default:
throw new ApplicationError("visitor expected", tree);
}
}
/** match => this.match
* match[targs] => this.match[targs]
* IMPORTANT: tree is already attributed and attributes need to be preserved.
*/
Tree postMatch(Tree tree, Symbol currentclazz) {
switch (tree) {
case Ident(Name name):
return
make.Select(tree.pos,
gen.This(tree.pos, currentclazz),
name).setSymbol(tree.symbol()).setType(tree.type);
case TypeApply(Tree fn, Tree[] args):
return copy.TypeApply(tree, postMatch(fn, currentclazz), args);
default:
return tree;
}
}
/** { cases } ==> (x => x.match {cases})
* only called when match has to be added
* no type for parameter x
*/
public Tree Visitor(Tree tree) {
switch(tree) {
case Visitor(CaseDef[] cases):
Name x = getvar();
ValDef param = (ValDef) make.ValDef(
tree.pos, PARAM, x, Tree.Empty, Tree.Empty);
Tree xuse = make.Ident(tree.pos, x);
// x.match {cases}
Tree body = make.Apply(tree.pos,
make.Select(tree.pos, xuse, Names.match),
new Tree[]{tree});
return make.Function(tree.pos, new ValDef[]{param}, body);
default:
throw new ApplicationError("visitor expected", tree);
}
}
/** e = e' ==> e_=(e')
*/
public Tree Assign(int pos, Tree lhs, Tree rhs) {
Tree lhs1;
switch (lhs) {
case Ident(Name name):
lhs1 = make.Ident(lhs.pos, setterName(name));
break;
case Select(Tree qual, Name name):
lhs1 = make.Select(lhs.pos, qual, setterName(name));
break;
default:
throw new ApplicationError();
}
return make.Apply(pos, lhs1, new Tree[]{rhs});
}
/** e(args) = e' ==> e.update(args ; e')
*/
public Tree Update(Tree tree) {
switch(tree) {
case Assign(Apply(Tree fn, Tree[] args), Tree rhs):
// e.update
Tree update = make.Select(fn.pos, fn, Names.update);
Tree[] args1 = new Tree[args.length + 1];
System.arraycopy(args, 0, args1, 0, args.length);
args1[args.length] = rhs;
return make.Apply(tree.pos, update, args1);
default:
throw new ApplicationError();
}
}
/** make a set of trees share the same documentation comment as a
* given tree (used for pattern and val definitions)
*/
Tree[] shareComment(Tree[] trees, Tree tree) {
String comment = (String) global.mapTreeComment.get(tree);
if (comment != null)
for(int i = 0; i < trees.length; i++)
global.mapTreeComment.put(trees[i], comment);
return trees;
}
/** expand pattern definitions and variable definitions in templates.
*/
public Tree[] Statements(Tree[] stats, boolean isLocal) {
boolean change = false;
for (int i = 0; i < stats.length && !change; i++) {
switch (stats[i]) {
case PatDef(_, _, _):
change = true;
break;
case ValDef(int mods, _, _, _):
change = !isLocal;
}
}
if (change) {
TreeList ts = new TreeList();
for (int i = 0; i < stats.length; i++) {
switch (stats[i]) {
case PatDef(_, _, _):
ts.append(Statements(this.PatDef(stats[i]), isLocal));
break;
case ValDef(_, _, _, _):
if (!isLocal) {
ts.append(this.ValDef(stats[i]));
} else
ts.append(stats[i]);
break;
default:
ts.append(stats[i]);
}
}
stats = ts.toArray();
//TextTreePrinter p = new TextTreePrinter();//debug
//p.print("desugarized:");//debug
//for (int i = 0; i < stats.length; i++) p.print(stats[i]).println();//debug
//p.end();//debug
return stats;
} else {
return stats;
}
}
/** expands pattern definitions
* in case pattern is a simple (typed) identifier:
* val x = e ==> val x = e
* val x: T = e ==> val x: T = e
*
* in case there are no variables in pattern
* val p = e ==> e.match (case p => ())
*
* in case there is exactly one variable in pattern
* val x_1 = e.match (case p => (x_1))
*
* in case there are more variables in pattern
* val p = e ==> private synthetic val t$ = e.match (case p => (x_1, ..., x_N))
* val x_1 = t$._1
* ...
* val x_N = t$._N
*
*/
public Tree[] PatDef(Tree tree) {
switch(tree) {
case PatDef(int mods, Ident(Name name), Tree rhs):
// val x = e ==> val x = e
return shareComment(new Tree[]{
make.ValDef(tree.pos, mods, name, Tree.Empty, rhs)}, tree);
case PatDef(int mods, Typed(Ident(Name name), Tree type), Tree rhs):
// val x: T = e ==> val x: T = e
return shareComment(new Tree[]{
make.ValDef(tree.pos, mods, name, type, rhs)}, tree);
case PatDef(int mods, Tree pat, Tree rhs):
int pos = tree.pos;
ArrayList varlist = new ArrayList();
getVariables(pat, varlist);
Name[] vars = new Name[varlist.size()];
varlist.toArray(vars);
// Tuple_N(x_1, ..., x_N)
Tree[] vtree = new Tree[vars.length];
for (int i = 0; i < vars.length; i++) {
vtree[i] = make.Ident(pos, vars[i]);
}
Tree tuple = vars.length == 1 ? vtree[0] : mkTuple(tree.pos, vtree);
// e.match (case p => Tuple_N(x_1, ..., x_N))
CaseDef[] cases = {make.CaseDef(pos, pat, Tree.Empty, tuple)};
Tree match = make.Apply(pos,
make.Select(pos, rhs, Names.match),
new Tree[]{make.Visitor(pos, cases)});
if (vars.length == 0) {
// e.match (case p => ())
print(pat, "patdef", match);
return new Tree[]{match};
} else if (vars.length == 1) {
// val x_1 = e.match (case p => x_1)
Tree valdef = make.ValDef(pos, mods, vars[0], Tree.Empty, match);
print(pat, "patdef", valdef);
return shareComment(new Tree[]{valdef}, tree);
} else {
// t$
Name var = getvar();
// private synthetic val t$ = e.match (case p => (x_1, ..., x_N))
Tree[] res = new Tree[vars.length + 1];
res[0] = make.ValDef(pos, PRIVATE | SYNTHETIC, var,
Tree.Empty, match);
for (int i = 0; i < vars.length; i ++) {
// val x_i = t$._i
res[i + 1] = make.ValDef(
pos, mods, vars[i], Tree.Empty,
make.Select(pos, make.Ident(pos, var), tupleSelectorName(i + 1)));
}
print(pat, "patdef", new Block(res));//debug
return shareComment(res, tree);
}
default:
throw new ApplicationError("pattern definition expected", tree);
}
}
public Tree[] ValDef(Tree tree) {
switch (tree) {
case ValDef(int mods, Name name, Tree tpe, Tree rhs):
Name valname = Name.fromString(name + "$");
Tree valdef1 = copy.ValDef(
tree, (mods & (DEFERRED | MUTABLE | CASEACCESSOR | MODUL)) | PRIVATE,
valname, tpe, rhs).setType(null);
int mods1 = mods | ACCESSOR;
if ((mods1 & MUTABLE) == 0) mods1 |= STABLE;
Tree getter = make.DefDef(
tree.pos, mods1, name,
Tree.AbsTypeDef_EMPTY_ARRAY, Tree.ValDef_EMPTY_ARRAY_ARRAY,
tpe.duplicate(),
((mods & DEFERRED) != 0) ? Tree.Empty
: make.Ident(tree.pos, valname));
if ((mods1 & MUTABLE) == 0) {
if ((mods1 & DEFERRED) != 0) return shareComment(new Tree[]{getter}, tree);
else return shareComment(new Tree[]{valdef1, getter}, tree);
} else {
Tree setter = make.DefDef(
tree.pos, mods1, setterName(name),
Tree.AbsTypeDef_EMPTY_ARRAY,
new ValDef[][]{{
(ValDef) make.ValDef(
tree.pos, SYNTHETIC | PARAM, parameterName(0), tpe.duplicate(), Tree.Empty)}},
gen.mkType(tree.pos, global.definitions.UNIT_TYPE),
((mods1 & DEFERRED) != 0) ? Tree.Empty
: make.Assign(
tree.pos,
make.Ident(tree.pos, valname),
make.Ident(tree.pos, parameterName(0))));
if ((mods1 & DEFERRED) != 0) return shareComment(new Tree[]{getter, setter}, tree);
else return shareComment(new Tree[]{valdef1, getter, setter}, tree);
}
default:
throw new ApplicationError();
}
}
/** Expand partial function applications of type `type'.
*
* p.f(es_1)...(es_n)
* ==> {
* private synthetic val eta$f = p.f // if p is not stable
* ...
* private synthetic val eta$e_i = e_i // if e_i is not stable
* ...
*
* (ps_1 => ... => ps_m => eta$f([es_1])...([es_m])(ps_1)...(ps_m))
* }
* tree is already attributed
*/
public Tree etaExpand(Tree tree, Type type) {
TreeList defs = new TreeList();
Tree lambda =
toFunction(toApply(liftoutPrefix(tree, defs), type), type);
defs.append(lambda);
Tree result = make.Block(tree.pos, defs.toArray());
print(tree, "eta", result);//debug
return result;
}
private static String preName = "eta$";
/** Append to `defs' value definitions for all non-stable subexpressions
* of the function application `tree'
*/
public Tree liftoutPrefix(Tree tree, TreeList defs) {
switch (tree) {
case Ident(_):
return tree;
case Select(Tree qual, _):
return copy.Select(tree, liftout(qual, defs)).setType(null);
case TypeApply(Tree fn, Tree[] args):
return copy.TypeApply(tree, liftoutPrefix(fn, defs), args).setType(null);
case Apply(Tree fn, Tree[] args):
return copy.Apply(tree, liftoutPrefix(fn, defs), liftout(args, defs))
.setType(null);
default:
throw new ApplicationError();
}
}
public Tree[] liftout(Tree[] trees, TreeList defs) {
Tree[] trees1 = trees;
for (int i = 0; i < trees.length; i++) {
Tree tree = trees[i];
Tree tree1 = liftout(tree, defs);
if (tree1 != tree && trees1 == trees) {
trees1 = new Tree[trees.length];
System.arraycopy(trees, 0, trees1, 0, trees.length);
}
trees1[i] = tree1;
}
return trees1;
}
public Tree liftout(Tree tree, TreeList defs) {
if (!TreeInfo.isPureExpr(tree)) {
Name vname = Name.fromString(preName + defs.length());
defs.append(
make.ValDef(
tree.pos, SYNTHETIC, vname, Tree.Empty, tree));
return make.Ident(tree.pos, vname);
} else {
return tree;
}
}
/** x => x @ _
* only within sequence patterns, for now. BE
* precondition: name != '_'
* post: returns *unattributed* Bind tree
*/
public Tree IdentPattern( Tree tree ) {
switch( tree ) {
case Ident( Name name ):
if( name == Names.WILDCARD ) throw new ApplicationError("nothing to desugarize");
return make.Bind( tree.pos,
name,
make.Ident( tree.pos, Names.WILDCARD ).setType( tree.type )).setType( tree.type );
default:
throw new ApplicationError("ident expected");
}
}
/** f, (syms_1)...(syms_n)T ==> f(ps_1)...(ps_n)
*/
Tree toApply(Tree tree, Type type) {
switch(type) {
case MethodType(Symbol[] vparams, Type restpe):
Tree res = make.Apply(tree.pos, tree, toIdents(vparams));
return toApply(res, restpe);
default:
return tree;
}
}
/** e, (syms_1)...(syms_n)T ==> (ps_1 => ... => ps_n => e)
*/
Tree toFunction(Tree tree, Type type) {
switch(type) {
case MethodType(Symbol[] vparams, Type restpe):
return //this.Function(
make.Function(tree.pos, toVparams(vparams), toFunction(tree, restpe));
//restpe);
default:
return tree;
}
}
/** Extract value parameters from type.
*/
ValDef[] toVparams(Symbol[] symbols) {
ValDef[] vpars = new ValDef[symbols.length];
for (int i = 0; i < symbols.length; i++) {
vpars[i] = (ValDef)make.ValDef(
symbols[i].pos, 0, symbols[i].name,
gen.mkType(symbols[i].pos, symbols[i].type()),
Tree.Empty);
}
return vpars;
}
/** Extract value identifiers from method type.
* It is assumed that all symbols are term symbols ==> make.Ident().
*/
Tree[] toIdents(Symbol[] symbols) {
Tree[] idents = new Ident[symbols.length];
for (int i = 0; i < symbols.length; i++) {
idents[i] = make.Ident(symbols[i].pos, symbols[i].name);
}
return idents;
}
/** Build value element definition name for case parameter.
*/
void addCaseElement(TreeList ts, ValDef vparam) {
//vparam.symbol().initialize();
ts.append(
make.ValDef(
vparam.pos, CASEACCESSOR, vparam.name, Tree.Empty,
make.Ident(vparam.pos, vparam.name)
.setSymbol(vparam.symbol())));
}
/** add case constructor, value defintiions and access functions.
*/
Tree[] addCaseElements(Tree[] body, ValDef[] vparams) {
TreeList stats = new TreeList();
for (int i = 0; i < vparams.length; i++) {
addCaseElement(stats, vparams[i]);
}
stats.append(body);
return stats.toArray();
}
//debug
void print(Tree tree, String conv, Tree result) {
if (global.log()) {
new TextTreePrinter()
.print(tree).println()
.print(" --" + conv + "--> ").println()
.print(result).println().end();
}
}
}