diff options
Diffstat (limited to 'sources/scalac/transformer/LambdaLift.java')
| -rw-r--r-- | sources/scalac/transformer/LambdaLift.java | 763 |
1 files changed, 0 insertions, 763 deletions
diff --git a/sources/scalac/transformer/LambdaLift.java b/sources/scalac/transformer/LambdaLift.java deleted file mode 100644 index fdf14e8d9b..0000000000 --- a/sources/scalac/transformer/LambdaLift.java +++ /dev/null @@ -1,763 +0,0 @@ -/* ____ ____ ____ ____ ______ *\ -** / __// __ \/ __// __ \/ ____/ SOcos COmpiles Scala ** -** __\_ \/ /_/ / /__/ /_/ /\_ \ (c) 2002-2005, LAMP/EPFL ** -** /_____/\____/\___/\____/____/ ** -\* */ - -// $Id$ - -package scalac.transformer; - -import java.io.*; -import java.util.HashMap; - -import scalac.*; -import scalac.ast.*; -import scalac.symtab.*; -import scalac.util.*; -import Tree.*; - - -/** A lambda lifting transformer - * - * @author Martin Odersky - * @version 1.0 - * - * What it does: - * Lift every class and function that's contained in another function - * out to be a member to the next enclosing class. - * Pass free variables and type variables as parameters to class constructors. - * Variables and values that are free in some function or class - * are given new unique names. - * Free mutable variables are converted to reference cells. - * All types are updated so that proxies are passed for additional free - * type variables. - */ -public class LambdaLift extends OwnerTransformer - implements Modifiers, Kinds { - - final Global global; - final Definitions definitions; - final FreeVars free; - final LambdaLiftPhase descr; - private CompilationUnit unit; - - public LambdaLift(Global global, LambdaLiftPhase descr) { - super(global); - this.global = global; - this.definitions = global.definitions; - this.free = new FreeVars(global); - this.descr = descr; - } - - public void apply(CompilationUnit unit) { - this.unit = unit; - global.log(unit.source.toString()); - free.initialize(unit); - currentOwner = global.definitions.ROOT_CLASS; - unit.body = transformTemplateStats(unit.body, currentOwner); - } - - /** If `sym' is a class, return its primary constructor; - * otherwise current symbol itself - * - * @param sym - * @return - */ - static Symbol asFunction(Symbol sym) { - return sym.kind == CLASS ? sym.primaryConstructor() : sym; - } - - /** Is symbol local relative to owner? - * Primary constructor parameters are local iff owner (contained in) - * the primary constructor. - * - * @param sym - * @param owner - * @return <code>true</code> if the symbol <code>sym</code> - * is local relative to <code>owner</code> - */ - static boolean isLocal(Symbol sym, Symbol owner) { - if (sym.isParameter() && - sym.owner().isPrimaryConstructor() && - sym.owner().constructorClass().kind == CLASS && - !(owner.isParameter() && owner.owner() == sym)) { - Symbol encl = sym.owner().owner(); - Symbol clazz = sym.owner().constructorClass(); - //System.out.println("isLocal " + sym + " " + encl + " " + clazz + " " + owner);//DEBUG - while (owner != encl && - owner.kind != NONE && - owner != clazz) { - owner = owner.owner(); - //System.out.println(":" + owner);//DEBUG - } - return owner != clazz; - } - return sym.isLocal(); - } - - /** Propagate free variables from all called functions. - * `asFunction' applied to the next enclosing function or class owner. - * - * @param owner - * @return - */ - static Symbol enclFun(Symbol owner) { - Symbol sym = owner; - while (!asFunction(sym).isMethod()) sym = sym.owner(); - return asFunction(sym); - } - - /** Return SymSet from a hashmap. - * - * @param f - * @param sym - * @return - */ - private static SymSet get(HashMap f, Symbol sym) { - SymSet ss = (SymSet) f.get(sym); - return ss == null ? SymSet.EMPTY : ss; - } - - /** Compute free variables map `fvs'. - * Also assign unique names to all - * value/variable/let symbols that are free in some function or class, and to - * all class/function symbols that are owned by some function. - */ - static class FreeVars extends OwnerTransformer { - - private CompilationUnit unit; - - public FreeVars(Global global) { - super(global); - } - - /** A hashtable storing free variables of functions and class constructors. - */ - private HashMap/*<Symbol,SymSet>*/ fvs; - - /** A hashtable storing free type variables of functions and class constructors. - */ - private HashMap/*<Symbol,SymSet>*/ ftvs; - - /** A hashtable storing calls between functions and class constructors - */ - private HashMap/*<Symbol,SymSet>*/ called; - - /** The set of symbols that need to be renamed. - */ - private SymSet renamable; - - /** The set of symbols that bound by polytypes - * and therefore are not free type variables. - */ - private SymSet excluded; - - /** A flag to indicate whether new free variables have been found - */ - private boolean changedFreeVars; - - /** A flag to indicate whether we are in propagation phase - * (used in assertion). - */ - private boolean propagatePhase; - - /** Insert `sym' into the set of free variables of `owner' - * - * @param owner - * @param sym - */ - private void putFree(Symbol owner, Symbol sym) { - assert owner.isLocal(); - HashMap f = sym.isType() ? ftvs : fvs; - SymSet ss = get(f, owner); - if (!ss.contains(sym)) { - f.put(owner, ss.incl(sym)); - changedFreeVars = true; - if (global.debug) global.log(sym + " is free in " + owner); - } - } - - /** Insert `to' into the set of functions called by `from' - * - * @param from - * @param to - */ - private void putCall(Symbol from, Symbol to) { - SymSet ss = get(called, from); - if (!ss.contains(to)) { - called.put(from, ss.incl(to)); - } - } - - /** Mark symbol `sym' as being free in `owner', unless `sym' - * is defined in `owner' or there is a class between `owner's owner - * and the owner of `sym'. - * Return `true' if there is no class between `owner' and - * the owner of sym. - * - * @param sym - * @param owner - * @return - */ - private boolean markFree(Symbol sym, Symbol owner) { - if (global.debug) - global.log("mark " + sym + " of " + sym.owner() + - " free in " + owner);//debug - if (owner.kind == NONE) { - assert propagatePhase : sym + " in " + sym.owner(); - return false; - } else if (sym.owner() == owner) { - return true; - } else if (markFree(sym, owner.owner())) { - Symbol fowner = asFunction(owner); - if (fowner.isMethod()) { - putFree(fowner, sym); - renamable = renamable.incl(sym); - if (sym.isVariable()) sym.flags |= CAPTURED; - } - return owner.kind != CLASS; - } else { - return false; - } - } - - /** Assign unique name to symbol. - * If symbol is a class assign same name to its primary constructor. - */ - private void makeUnique(Symbol sym) { - sym.name = unit.fresh.newName(sym.name); - } - - private Type.Map traverseTypeMap = new Type.Map() { - public Type apply(Type tp) { - if (global.debug) global.log("traverse " + tp);//debug - switch (tp) { - case TypeRef(NoPrefix, Symbol sym, Type[] targs): - if (isLocal(sym, currentOwner) && - sym.kind == TYPE && - !excluded.contains(sym)) - markFree(sym, currentOwner); - break; - case SingleType(NoPrefix, Symbol sym): - if (isLocal(sym, currentOwner)) - markFree(sym, currentOwner); - break; - case PolyType(Symbol[] tparams, Type restp): - for (int i = 0; i < tparams.length; i++) - excluded = excluded.incl(tparams[i]); - Type tp1 = super.map(tp); - for (int i = 0; i < tparams.length; i++) - excluded = excluded.excl(tparams[i]); - return tp1; - } - return map(tp); - } - }; - - public Tree transform(Tree tree) { - if (global.debug) global.log("free " + tree);//debug - assert tree.type != null : tree; - traverseTypeMap.apply(tree.type.widen()); - Symbol sym = tree.symbol(); - switch(tree) { - case ClassDef(_, _, _, _, _, _): - case DefDef(_, _, _, _, _, _): - if (sym.isLocal()) { - renamable = renamable.incl(sym); - } - return super.transform(tree); - - case AbsTypeDef(int mods, Name name, Tree rhs, Tree lobound): - // ignore type definition as owner. - // reason: it might be in a refinement - // todo: handle type parameters? - return copy.AbsTypeDef( - tree, sym, - transform(rhs, currentOwner), - transform(lobound, currentOwner)); - - case AliasTypeDef(int mods, Name name, AbsTypeDef[] tparams, Tree rhs): - // ignore type definition as owner. - // reason: it might be in a refinement - // todo: handle type parameters? - return copy.AliasTypeDef( - tree, sym, - transform(tparams, currentOwner), - transform(rhs, currentOwner)); - - case Ident(_): - if (isLocal(sym, currentOwner)) { - if (sym.isMethod()) { - Symbol f = enclFun(currentOwner); - if (f.name.length() > 0) // it is not a template function { - putCall(f, sym); - } else if (sym.kind == VAL || sym.kind == TYPE) { - markFree(sym, currentOwner); - } - } - return tree; - - default: - return super.transform(tree); - } - } - - /** Propagate free fariables from all called functions. - * - * @param fvs - */ - void propagateFvs(HashMap fvs) { - Object[] fs = called.keySet().toArray(); - for (int i = 0; i < fs.length; i++) { - Symbol f = (Symbol) fs[i]; - Symbol[] calledFromF = get(called, f).toArray(); - for (int j = 0; j < calledFromF.length; j++) { - //System.out.println(f + " calls " + calledFromF[j]);//DEBUG - Symbol[] newFvs = get(fvs, calledFromF[j]).toArray(); - for (int k = 0; k < newFvs.length; k++) { - markFree(newFvs[k], f); - } - } - } - } - - /** This method re-enters all free variables into their free variable - * sets. This is necessary because the names of these variables (and - * therefore their `isLess' order have changed. - * - * @param fvs - */ - private void restoreFvs(HashMap fvs) { - Object[] fs = fvs.keySet().toArray(); - for (int i = 0; i < fs.length; i++) { - Symbol f = (Symbol) fs[i]; - Symbol[] elems = get(fvs, f).toArray(); - SymSet elems1 = SymSet.EMPTY; - for (int j = 0; j < elems.length; j++) - elems1 = elems1.incl(elems[j]); - fvs.put(f, elems1); - } - } - - /** Compute a mapping from symbols to their free variables - * in hashtable `fvs'. Also rename all variables that need it. - * - * @param unit - */ - public void initialize(CompilationUnit unit) { - this.unit = unit; - fvs = new HashMap(); - ftvs = new HashMap(); - called = new HashMap(); - renamable = SymSet.EMPTY; - excluded = SymSet.EMPTY; - apply(unit); - - propagatePhase = true; - do { - changedFreeVars = false; - propagateFvs(fvs); - propagateFvs(ftvs); - } while (changedFreeVars); - - Symbol[] ss = renamable.toArray(); - for (int i = 0; i < ss.length; i++) { - makeUnique(ss[i]); - } - - restoreFvs(fvs); - restoreFvs(ftvs); - } - } - - private TreeList liftedDefs; - - /** Transform template and add lifted definitions to it. - * - * @param stats - * @param tsym - * @return - */ - public Tree[] transformTemplateStats(Tree[] stats, Symbol tsym) { - TreeList prevLiftedDefs = liftedDefs; - liftedDefs = new TreeList(); - TreeList stats1 = new TreeList(super.transformTemplateStats(stats, tsym)); - stats1.append(liftedDefs); - liftedDefs = prevLiftedDefs; - return stats1.toArray(); - } - - /** ... - * - * @param tree - */ - public Tree transform(Tree tree) { - //global.debugPrinter.print("lifting ").print(tree).println().end();//DEBUG - //System.out.print(tree.type + " --> ");//DEBUG - tree.type = descr.transform(tree.type, currentOwner); - //System.out.println(tree.type);//DEBUG - switch (tree) { - case Block(Tree[] stats, Tree value): - for (int i = 0; i < stats.length; i++) - liftSymbol(stats[i]); - return copy.Block(tree, transform(stats), transform(value)); - - case ClassDef(int mods, _, AbsTypeDef[] tparams, ValDef[][] vparams, Tree tpe, Template impl): - Symbol sym = tree.symbol(); - if ((mods & LIFTED) != 0) { - ((ClassDef) tree).mods &= ~LIFTED; - Tree tree1 = copy.ClassDef( - tree, sym, - addTypeParams(transform(tparams, sym), newtparams(sym.primaryConstructor())), - new ValDef[][]{ - addParams(transform(vparams, sym)[0], newparams(sym.primaryConstructor()))}, - transform(tpe, sym), - transform(impl, sym)); - liftedDefs.append(tree1); - return Tree.Empty; - } else { - assert !sym.isLocal() : sym; - return copy.ClassDef( - tree, sym, - transform(tparams, sym), - transform(vparams, sym), - transform(tpe, sym), - transform(impl, sym)); - } - - case DefDef(int mods, _, AbsTypeDef[] tparams, ValDef[][] vparams, Tree tpe, Tree rhs): - Symbol sym = tree.symbol(); - if ((mods & LIFTED) != 0) { - ((DefDef) tree).mods &= ~LIFTED; - Tree tree1 = copy.DefDef( - tree, sym, - addTypeParams(transform(tparams, sym), newtparams(sym)), - new ValDef[][]{ - addParams(transform(vparams, sym)[0], newparams(sym))}, - transform(tpe, sym), - transform(rhs, sym)); - liftedDefs.append(tree1); - return Tree.Empty; - } else { - assert !sym.isLocal() : sym; - return copy.DefDef( - tree, sym, - transform(tparams, sym), transform(vparams, sym), transform(tpe, sym), - transform(rhs, sym)); - } - - case AbsTypeDef(int mods, Name name, Tree rhs, Tree lobound): - // ignore type definition as owner. - // reason: it might be in a refinement - // todo: handle type parameters? - return copy.AbsTypeDef( - tree, tree.symbol(), - transform(rhs, currentOwner), - transform(lobound, currentOwner)); - - case AliasTypeDef(int mods, Name name, AbsTypeDef[] tparams, Tree rhs): - // ignore type definition as owner. - // reason: it might be in a refinement - // todo: handle type parameters? - return copy.AliasTypeDef( - tree, tree.symbol(), - transform(tparams, currentOwner), - transform(rhs, currentOwner)); - - case ValDef(_, _, _, Tree rhs): - Symbol sym = tree.symbol(); - rhs = transform(rhs, sym); - if (sym.isCaptured()) { - assert sym.isLocal(); - switch (sym.nextType()) { - case TypeRef(_, Symbol clasz, Type[] args): - Tree constr = gen.mkPrimaryConstructorGlobalRef(rhs.pos, clasz); - rhs = gen.New(gen.mkApplyTV(constr, args, new Tree[]{rhs})); - break; - default: - throw Debug.abort("illegal case", sym.nextType()); - } - } - return gen.ValDef(sym, rhs); - - case Sequence(Tree[] args): - throw new ApplicationError("this should not happen"); - /* // moved this to Uncurry - Tree tree1 = gen.mkNewList(tree.pos, tree.type.typeArgs()[0], transform(args)); - //System.out.println("TUPLE: " + tree + "\n ==> \n" + tree1);//DEBUG - return tree1; - */ - - case Return(Block(Tree[] stats, Tree value)): - return transform( - gen.Block(stats, gen.Return(tree.pos, tree.symbol(), value))); - - case Return(Tree expr): - if (tree.symbol() != currentOwner.enclMethod()) { - unit.error(tree.pos, "non-local return not yet implemented"); - } - return super.transform(tree); - - case Apply(Tree fn, Tree[] args): - Symbol fsym = TreeInfo.methSymbol(fn); - Tree fn1 = transform(fn); - switch (fn1) { - case TypeApply(Tree fn2, Tree[] targs): - //if (args.length == 1 && fn2.symbol() == definitions.PREDEF_ARRAY()) { - // throw new ApplicationError("this should not happen"); - /* // this moved to UnCurry - switch (args[0]) { - case Sequence(Tree[] items): - assert targs.length == 1: tree; - Tree array = gen.mkNewArray( - args[0].pos, - targs[0].type(), - transform(items), - currentOwner); - // fn2 may be like "{ println("hello"); Predef}.Array" - switch (fn2) { - case Select(Tree qualifier, _): - return gen.mkBlock(args[0].pos, qualifier, array); - default: - throw Debug.abort("illegal case", fn2); - } - } - */ - //} - fn1 = copy.TypeApply( - fn1, fn2, addFreeArgs(tree.pos, get(free.ftvs, fsym), targs, true)); - break; - default: - Tree[] targs = addFreeArgs( - tree.pos, get(free.ftvs, fsym), Tree.EMPTY_ARRAY, true); - if (targs.length > 0) - fn1 = gen.TypeApply(fn1, targs); - } - Tree[] args1 = transform(args); - return copy.Apply( - tree, fn1, addFreeArgs(tree.pos, get(free.fvs, fsym), args1, false)); - - case Ident(_): - Symbol sym = tree.symbol(); - if (isLocal(sym, currentOwner) && - (sym.kind == TYPE || (sym.kind == VAL && !sym.isMethod()))) { - sym = descr.proxy(sym, currentOwner); - } - Tree tree1 = gen.mkLocalRef(tree.pos, sym); - if (sym.isCaptured()) - return gen.Select(tree1, definitions.REF_ELEM()); - else - return tree1; - - default: - return super.transform(tree); - } - } - - private Symbol[] ftvsParams(Symbol owner) { - Symbol[] freevars = get(free.ftvs, owner).toArray(); - Symbol[] params = new Symbol[freevars.length]; - for (int i = 0; i < params.length; i++) { - params[i] = freevars[i].cloneSymbol(owner); - params[i].pos = owner.pos; - params[i].flags = PARAM | SYNTHETIC; - } - for (int i = 0; i < params.length; i++) - params[i].setInfo(freevars[i].info().subst(freevars, params)); - return params; - } - - private Symbol[] fvsParams(Symbol owner) { - Symbol[] freevars = get(free.fvs, owner).toArray(); - Symbol[] params = new Symbol[freevars.length]; - for (int i = 0; i < params.length; i++) { - params[i] = freevars[i].cloneSymbol(owner); - params[i].pos = owner.pos; - params[i].flags &= CAPTURED; - params[i].flags |= PARAM | SYNTHETIC; - params[i].setInfo(freevars[i].type()); - } - return params; - } - - private Symbol[] newtparams(Symbol owner) { - Symbol[] tparams = owner.nextType().typeParams(); - int nfree = get(free.ftvs, owner).size(); - assert nfree == tparams.length - owner.type().typeParams().length - : owner + " " + nfree + " " + tparams.length + " " + owner.type().firstParams().length; - Symbol[] newtparams = new Symbol[nfree]; - System.arraycopy(tparams, tparams.length - nfree, newtparams, 0, nfree); - return newtparams; - } - - private Symbol[] newparams(Symbol owner) { - Symbol[] params = owner.nextType().firstParams(); - int nfree = get(free.fvs, owner).size(); - assert nfree == params.length - owner.type().firstParams().length; - Symbol[] newparams = new Symbol[nfree]; - System.arraycopy(params, params.length - nfree, newparams, 0, nfree); - return newparams; - } - - /** For members: - * change symbol of tree so that - * owner = currentClass - * newparams are added - * enter symbol in scope of currentClass - * For non-members: - * change symbol of tree so that - * owner = currentMember - */ - private void liftSymbol(Tree tree) { - switch (tree) { - case ClassDef(_, _, _, _, _, _): - ((ClassDef) tree).mods |= LIFTED; - Symbol sym = tree.symbol(); - sym.flags |= LIFTED; - assert sym.isLocal() : sym; - Symbol constr = sym.primaryConstructor(); - liftSymbol( - sym, get(free.ftvs, constr).toArray(), - ftvsParams(constr), fvsParams(constr)); - break; - - case DefDef(_, _, _, _, _, _): - ((DefDef) tree).mods |= LIFTED; - Symbol sym = tree.symbol(); - sym.flags |= LIFTED | PRIVATE; - assert sym.isLocal() : sym; - liftSymbol( - sym, get(free.ftvs, sym).toArray(), - ftvsParams(sym), fvsParams(sym)); - break; - - case ValDef(_, _, _, _): - case LabelDef(_, _, _): - Symbol sym = tree.symbol(); - assert sym.isLocal() : sym; - // This is to fix the owner of y from x to f in this example: - // class C { def f = { val x = { val y = ...; y } } } - if (!isClassMember(sym.owner())) { - assert isClassMember(sym.owner().owner()): Debug.show(tree, sym); - sym.setOwner(sym.owner().owner()); - } - break; - - } - } - // where - private boolean isClassMember(Symbol sym) { - return sym.isConstructor() || sym.owner().isClass(); - } - - private void liftSymbol(Symbol sym, Symbol[] oldtparams, - Symbol[] newtparams, Symbol[] newparams) { - Symbol enclClass = sym.owner(); - while (!enclClass.isClassType()) { - enclClass = enclClass.isConstructor() && !enclClass.isPrimaryConstructor() - ? enclClass.constructorClass() - : enclClass.owner(); - } - if (!sym.isConstructor()) sym.setOwner(enclClass); - if (!sym.isConstructor()) enclClass.members().enter(sym); - if (sym.isMethod()) { - if (newtparams.length != 0 || newparams.length != 0) { - sym.updateInfo( - addParams( - addTypeParams( - sym.nextInfo(), oldtparams, newtparams), - newparams)); - if (global.debug) - global.log(sym + " has now type " + sym.nextType()); - } - } else if (sym.kind == CLASS) { - Symbol constr = sym.primaryConstructor(); - liftSymbol(constr, oldtparams, newtparams, newparams); - // fix result type of constructor - constr.updateInfo(descr.transform(constr.nextInfo(), constr)); - } else { - throw new ApplicationError(); - } - } - - private Type addTypeParams(Type tp, Symbol[] oldtparams, Symbol[] newtparams) { - if (newtparams.length == 0) return tp; - switch (tp) { - case MethodType(_, _): - return Type.PolyType( - newtparams, - Type.getSubst(oldtparams, newtparams, true).apply(tp)); - case PolyType(Symbol[] tparams, Type restpe): - Symbol[] tparams1 = new Symbol[tparams.length + newtparams.length]; - System.arraycopy(tparams, 0, tparams1, 0, tparams.length); - System.arraycopy(newtparams, 0, tparams1, tparams.length, newtparams.length); - return Type.PolyType( - tparams1, - Type.getSubst(oldtparams, newtparams, true).apply(restpe)); - default: - throw new ApplicationError("illegal type: " + tp); - } - } - - private Type addParams(Type tp, Symbol[] newparams) { - if (newparams.length == 0) return tp; - switch (tp) { - case MethodType(Symbol[] params, Type restpe): - Symbol[] params1 = new Symbol[params.length + newparams.length]; - System.arraycopy(params, 0, params1, 0, params.length); - System.arraycopy(newparams, 0, params1, params.length, newparams.length); - return Type.MethodType(params1, restpe); - case PolyType(Symbol[] tparams, Type restpe): - return Type.PolyType(tparams, addParams(restpe, newparams)); - default: - throw new ApplicationError("illegal type: " + tp); - } - } - - private AbsTypeDef[] addTypeParams(AbsTypeDef[] tparams, Symbol[] newtparams) { - if (newtparams.length == 0) return tparams; - AbsTypeDef[] tparams1 = new AbsTypeDef[tparams.length + newtparams.length]; - System.arraycopy(tparams, 0, tparams1, 0, tparams.length); - for (int i = 0; i < newtparams.length; i++) { - tparams1[tparams.length + i] = gen.mkTypeParam(newtparams[i]); - } - return tparams1; - } - - private ValDef[] addParams(ValDef[] params, Symbol[] newparams) { - if (newparams.length == 0) return params; - ValDef[] params1 = new ValDef[params.length + newparams.length]; - System.arraycopy(params, 0, params1, 0, params.length); - for (int i = 0; i < newparams.length; i++) { - params1[params.length + i] = gen.mkParam(newparams[i]); - } - return params1; - } - - /** For all variables or type variables in `fvs', - * append proxies to argument array `args'. - * - * @param pos - * @param fvs - * @param args - * @param types - * @return - */ - private Tree[] addFreeArgs(int pos, SymSet fvs, Tree[] args, boolean types) { - if (fvs != SymSet.EMPTY) { - Symbol[] fparams = fvs.toArray(); - Tree[] args1 = new Tree[args.length + fparams.length]; - System.arraycopy(args, 0, args1, 0, args.length); - for (int i = 0; i < fparams.length; i++) { - Symbol farg = descr.proxy(fparams[i], currentOwner); - args1[args.length + i] = - types ? gen.mkTypeRef(pos, farg) : gen.Ident(pos, farg); - } - return args1; - } else { - return args; - } - } - -} |