/* // $Id: //guest/julian_hyde/saffron/src/main/saffron/opt/Implementor.java#6 $ // Saffron preprocessor and data engine // Copyright (C) 2002 Julian Hyde <julian.hyde@mail.com> // // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Library General Public // License as published by the Free Software Foundation; either // version 2 of the License, or (at your option) any later version. // // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // Library General Public License for more details. // // You should have received a copy of the GNU Library General Public // License along with this library; if not, write to the // Free Software Foundation, Inc., 59 Temple Place - Suite 330, // Boston, MA 02111-1307, USA. // // See the COPYING file located in the top-level-directory of // the archive of this library for complete text of license. */ package saffron.opt; import openjava.mop.OJClass; import openjava.mop.OJField; import openjava.ptree.*; import openjava.ptree.util.EvaluationShuttle; import openjava.ptree.util.SyntheticClass; import openjava.tools.DebugOut; import saffron.rel.Rel; import saffron.rel.Project; import saffron.rel.Join; import saffron.util.RelEnvironment; import saffron.util.Util; import java.util.Hashtable; import java.util.Stack; import java.util.Vector; /** * <code>Implementor</code> deals with the nastiness of converting a tree of * relational expressions into an implementation, generally an {@link ParseTree * openjava parse tree}. * * <p> The {@link #bind} method allows relational expressions to register which * Java variable holds their row. They can bind 'lazily', so that the variable * is only declared and initialized if it is actually used in another * expression. **/ public class Implementor { Hashtable mapRel2Frame; // Rel --> Frame such that frame.rel == rel /** Map String --> Frame such that frame.rel.corelVariable == corelName **/ Hashtable mapCorel2Frame; Stack stmtListStack; // elements are StatementList openjava.ptree.Statement exitStatement; Hashtable mapCorelNameToVariable; public Implementor() { mapRel2Frame = new Hashtable(); mapCorel2Frame = new Hashtable(); stmtListStack = new Stack(); mapCorelNameToVariable = new Hashtable(); } public Variable newVariable() { return Variable.generateUniqueVariable(); } /** * Starts an iteration, by calling {@link saffron.rel.Rel#implement} on the * root element. **/ public Object implementRoot(Rel rel) { return implementChild(null, -1, rel); } /** * Implements a relational expression according to a calling convention. */ public Object implementChild(Rel parent, int ordinal, Rel child) { if (parent != null) { Util.assert(child == parent.getInputs()[ordinal]); } Frame frame = new Frame(); frame.rel = child; frame.parent = parent; frame.ordinal = ordinal; mapRel2Frame.put(child, frame); String corel = child.getCorelVariable(); if (corel != null) { // Record that this frame is responsible for setting this // variable. But if another frame is already doing the job -- // this frame's parent, which belongs to the same set -- don't // override it. if (mapCorel2Frame.get(corel) == null) { mapCorel2Frame.put(corel, frame); } } int ordinal2 = -1; // indicates that parent is calling child return child.implement(this, ordinal2); } /** * Implements the body of the current expression's parent. If * <code>variable</code> is not null, bind the current expression to * <code>variable</code>. * * For example, a nested loops join would generate * * <blockquote><pre> * for (int i = 0; i < emps.length; i++) { * Emp emp = emps[i]; * for (int j = 0; j < depts.length; j++) { * Dept dept = depts[j]; * if (emp.deptno == dept.deptno) { * <<parent body>> * } * } * } * </pre></blockquote> * * which corresponds to * * <blockquote><pre> * [emp:iter * [dept:iter * [join:body(emp,dept) * [parent:body] * ] * ] * ] * </pre></blockquote> * * @param rel child relation * @param stmtList block that child was generating its code into */ public void generateParentBody(Rel rel, StatementList stmtList) { if (stmtList != null) { pushStatementList(stmtList); } Frame frame = (Frame) mapRel2Frame.get(rel); if (!frame.hasVariable()) { // this relational expression has not bound itself, so we presume // that we can call its implementSelf() method bindDeferred(rel, getStatementList()); } Object o = frame.parent.implement(this, frame.ordinal); Util.assert(o == null); if (stmtList != null) { popStatementList(stmtList); } } public void setExitStatement(openjava.ptree.Statement stmt) { this.exitStatement = stmt; } public Statement getExitStatement() { return exitStatement; } /** * Record the fact that instances of <code>rel</code> are available in * <code>variable</code>. */ public void bind(Rel rel, Variable variable) { bind(rel, new EagerBind(variable)); } /** * Record the fact that instances of <code>rel</code> are available via * <code>bind</code> (which may be eager or lazy). */ private void bind(Rel rel, Bind bind) { if (DebugOut.getDebugLevel() > 0) { DebugOut.println("Bind " + rel.toStringShort() + " to " + bind); } Frame frame = (Frame) mapRel2Frame.get(rel); frame.bind = bind; boolean stupid = Util.getProperties().getBooleanProperty( "saffron.stupid"); if (stupid) { // trigger the declaration of the variable, even though it // may not be used Util.discard(bind.getVariable()); } } /** * Declare a variable, and bind it lazily, so it only gets initialized * if it is actually used. */ public Variable bind( Rel rel, StatementList statementList, final VariableInitializer initializer) { return bind( rel, statementList, rel.getRowType(), new VariableInitializerThunk() { public VariableInitializer getInitializer() { return initializer; } }); } private Variable bind( Rel rel, StatementList statementList, OJClass clazz, VariableInitializerThunk thunk) { Variable variable = newVariable(); LazyBind lazyBind = new LazyBind( variable, statementList, clazz, thunk); bind(rel, lazyBind); return variable; } /** * A relational expression calls this method to declare that its * initializer can be generated by calling its {@link Rel#implementSelf} * method. * * <p> Why this devious indirection? The advantage occurs if no one ever * wants to reference this relational expression's row; then we spare * the effort of computing a value which no one will use. */ public Variable bindDeferred(final Rel rel, StatementList statementList) { final Implementor implementor = this; return bind( rel, statementList, rel.getRowType(), new VariableInitializerThunk() { public VariableInitializer getInitializer() { return rel.implementSelf(implementor); } }); } /** * A <code>VariableInitializerThunk</code> yields a {@link * VariableInitializer}. */ public interface VariableInitializerThunk { VariableInitializer getInitializer(); } /** * Shares a variable between relations. <code>previous</code> already has * a variable, and calling this method indicates that <code>rel</code>'s * output will appear in this variable too. */ public void bind(Rel rel, Rel previous) { while (true) { Frame frame = (Frame) mapRel2Frame.get(previous); if (frame.bind != null) { if (DebugOut.getDebugLevel() > 0) { DebugOut.println("Bind " + rel.toStringShort() + " to " + previous.toStringShort() + "(" + frame.bind + ")"); } bind(rel, frame.bind); return; } // go deeper Rel[] inputs = previous.getInputs(); Util.assert(inputs.length == 1, "input is not bound"); previous = inputs[0]; } } /** * Binds a correlating variable. References to correlating variables such * as <code>$corel2</code> will be replaced with java variables such as * <code>$Oj14</code>. **/ public void bindCorel(String corelName, Variable variable) { mapCorelNameToVariable.put(corelName, variable); } /** * Converts an expression in internal form (the input relation is * referenced using the variable <code>$input0</code>) to generated form * (the input relation is referenced using the bindings in this * <code>Implementor</code>). Compare this method with {@link * saffron.rel.QueryInfo#convertExpToInternal}, which converts from source * form to internal form. * * @param exp the expression to translate (it is cloned, not modified) * @param rel the relational expression which is the context for * <code>exp</code> **/ public Expression translate(Rel rel, Expression exp) { Expression clone = Util.clone(exp); Translator translator = new Translator(this,rel); return Util.go(translator, clone); } /** * Creates an expression which references the <i>ordinal</i><sup>th</sup> * input. **/ public Expression translateInput(Rel rel, int ordinal) { return translate(rel, RelEnvironment.makeReference(ordinal)); } /** * Creates an expression which references the * <i>fieldOrdinal</i><sup>th</sup> field of the * <i>ordinal</i><sup>th</sup> input. * * <p> (We can potentially optimize the generation process, so we can * access field values without actually instantiating the row.) **/ public Expression translateInputField(Rel rel, int ordinal, int fieldOrdinal) { OJClass rowType = rel.getInput(ordinal).getRowType(); OJField field = rowType.getDeclaredFields()[fieldOrdinal]; return translate( rel, new FieldAccess( RelEnvironment.makeReference(ordinal), field.getName())); } /** * Creates an expression which references correlating variable * <code>corelName<code> from the context of <code>rel</code>. For * example, if <code>corelName</code> is set by the 1st child of * <code>rel</code>'s 2nd child, then this method returns * <code>$input2.$input1</code>. **/ public Expression makeReference(String corelName, Rel rel) { Frame frame = (Frame) mapCorel2Frame.get(corelName); Util.assert(frame != null); Util.assert(Util.equal(frame.rel.getCorelVariable(), corelName)); Util.assert(frame.hasVariable()); return frame.getVariable(); } /** * Creates an expression with which to implement "expression" from the * context of "rel". If "expression" is a field-access referencing an * input relation, it goes directly to that relation. */ private Expression findExp(Rel rel, Expression expression) { if (expression instanceof Variable) { Variable variable = (Variable) expression; String varName = variable.toString(); // is this a correlating variable ("$corel0", say)? Variable corelVariable = (Variable) mapCorelNameToVariable.get(varName); if (corelVariable != null) { return corelVariable; } } // is this an input variable ("$input0", say)? Rel inputRel = findRel(rel, expression); if (inputRel == null) { return null; } return findInputVariable(inputRel); } public Rel findRel(Rel rel, Expression expression) { if (expression instanceof Variable) { Variable variable = (Variable) expression; String name = variable.toString(); int input = RelEnvironment.getInputOrdinal(name); if (input < 0) { return null; } if (rel instanceof Join) { return findInputRel(rel, input); } else { return rel.getInput(input); } } else if (expression instanceof FieldAccess) { FieldAccess fieldAccess = (FieldAccess) expression; String fieldName = fieldAccess.getName(); Expression refExp = fieldAccess.getReferenceExpr(); Rel rel2 = findRel(rel, refExp); // recursive if (rel2 == null) { return null; } return rel2.implementFieldAccess(this, fieldName); } else { return null; } } private Rel findInputRel(Rel rel, int offset) { return findInputRel(rel, offset, new int[] {0}); } private Rel findInputRel(Rel rel, int offset, int offsets[]) { if (rel instanceof Join) { // no variable here -- go deeper Rel[] inputs = rel.getInputs(); for (int i = 0; i < inputs.length; i++) { Rel result = findInputRel(inputs[i], offset, offsets); if (result != null) { return result; } } } else if (offset == offsets[0]) { return rel; } else { offsets[0]++; } return null; // not found } private Variable findInputVariable(Rel rel) { while (true) { Frame frame = (Frame) mapRel2Frame.get(rel); if (frame != null && frame.hasVariable()) { return frame.getVariable(); } Rel[] inputs = rel.getInputs(); if (inputs.length == 1) { rel = inputs[0]; } else { return null; } } } public void pushStatementList(StatementList stmtList) { stmtListStack.push(stmtList); } public void popStatementList(StatementList stmtList) { Util.assert(stmtList == getStatementList()); stmtListStack.pop(); } public StatementList getStatementList() { return (StatementList) stmtListStack.peek(); } private static class Frame { /** relation which is being implemented in this frame */ Rel rel; /** <code>rel</code>'s parent */ Rel parent; /** ordinal of <code>rel</code> within <code>parent</code> */ int ordinal; /** Retrieves the variable, executing the lazy bind if necessary. */ Variable getVariable() { Util.assert(hasVariable()); return bind.getVariable(); } /** * Returns whether the frame has, or potentially has, a variable. */ boolean hasVariable() { return bind != null; } /** Holds variable which hasn't been declared yet. **/ private Bind bind; }; private interface Bind { Variable getVariable(); }; private static class EagerBind implements Bind { Variable variable; EagerBind(Variable variable) { this.variable = variable; } public String toString() { return super.toString() + "(variable=" + variable.toString() + ")"; } public Variable getVariable() { return variable; } } private static class LazyBind implements Bind { Variable variable; StatementList statementList; Statement after; OJClass clazz; VariableInitializerThunk thunk; boolean bound; LazyBind( Variable variable, StatementList statementList, OJClass clazz, VariableInitializerThunk thunk) { this.variable = variable; this.statementList = statementList; this.after = statementList.size() == 0 ? null : statementList.get(statementList.size() - 1); this.clazz = clazz; this.thunk = thunk; } public String toString() { return super.toString() + "(variable=" + variable.toString() + ", thunk=" + thunk.toString() + ")"; } public Variable getVariable() { if (!bound) { bound = true; int position = find(statementList, after); VariableDeclaration varDecl = new VariableDeclaration( TypeName.forOJClass(clazz), variable.toString(), null); statementList.insertElementAt(varDecl, position); varDecl.setInitializer(thunk.getInitializer()); } return variable; } private static int find(StatementList list, Statement statement) { if (statement == null) { return 0; } else { for (int i = 0, n = list.size(); i < n; i++) { if (list.get(i) == statement) { return i + 1; } } throw Util.newInternal( "could not find statement " + statement + " in list " + list); } } }; /** * <code>Translator</code> is a shuttle used to implement {@link * #translate(Expression,Rel)}. */ private static class Translator extends EvaluationShuttle { Implementor implementor; Rel rel; Translator(Implementor implementor, Rel rel) { super(rel.getEnvironment()); this.implementor = implementor; this.rel = rel; } public Expression evaluateDown(Variable p) throws ParseTreeException { Expression expression = implementor.findExp(rel, p); if (expression != null) { return expression; } return super.evaluateDown(p); } public Expression evaluateDown(FieldAccess p) throws ParseTreeException { Expression expression = implementor.findExp(rel, p); if (expression != null) { return expression; } return super.evaluateDown(p); } } } // End Implementor.java
# | Change | User | Description | Committed | |
---|---|---|---|---|---|
#6 | 1853 | Julian Hyde |
saffron: Further improve binding of rows to variables. |
||
#5 | 1818 | Julian Hyde |
saffron: Oops (forgot ParseTreeAction.java), Correlation now works, Smarter code generation (now burrow into synthetic classes, rather than invoking constructors). |
||
#4 | 1801 | Julian Hyde |
saffron: add ObjectSchema; rules can now be matched more than once; started to implement correlations in queries in from list. |
||
#3 | 1748 | Julian Hyde |
saffron: convert unit tests to JUnit; add CallingConvention.ITERABLE; lots of other stuff; release 0.1. |
||
#2 | 1474 | Julian Hyde |
saffron: Aggregations are working. Renamed 'aggregator' to 'aggregation'. |
||
#1 | 1467 | Julian Hyde |
saffron: First saffron check-in; incorporate my changes to openjava. |