/* // $Id: //guest/julian_hyde/saffron/src/main/saffron/opt/Implementor.java#3 $ // 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 saffron.rel.Rel; 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}. **/ 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); 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) { Frame frame = (Frame) mapRel2Frame.get(rel); frame.variable = variable; } /** * 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.variable != null) { bind(rel, frame.variable); 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(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, new Variable(RelEnvironment.makeName(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( new Variable(RelEnvironment.makeName(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.variable != null); return frame.variable; } private Expression _makeReference(String corelName, Rel rel) { Vector fields = new Vector(); boolean found = _collectPath(corelName, rel, fields); Util.assert(found); Expression exp = null; for (int i = 0, n = fields.size(); i < n; i++) { String field = (String) fields.elementAt(i); if (exp == null) { exp = new Variable(field); } else { exp = new FieldAccess(exp, field); } } return exp; } /** * Populates <code>fields</code> with a list of field names required to get * from <code>rel</code> to <code>targetRel</code>, in reverse order. For * example, if <code>targetRel</code> is the 1st child of * <code>rel</code>'s 2nd child, then <code>fields</code> will contain * <code>{"$input1", "$input2"}</code>. **/ private boolean _collectPath(String corelName, Rel rel, Vector fields) { Rel[] inputs = rel.getInputs(); for (int i = 0; i < inputs.length; i++) { if (inputs[i].getCorelVariable() == corelName) { fields.addElement(RelEnvironment.makeName(i)); return true; } if (_collectPath(corelName, inputs[i], fields)) { fields.addElement(RelEnvironment.makeName(i)); return true; } } return false; } /** * Creates an expression which references <code>targetRel</code> from the * context of <code>rel</code>. For example, if <code>targetRel</code> is * <code>rel</code>'s 0th child, and <code>exp</code> is * <code>myVar</code>, then this method returns <code>myVar.$input1</code>. **/ public Expression _translate(Expression exp, Rel targetRel, Rel rel) { if (targetRel == rel) { return exp; } else { Rel[] inputs = rel.getInputs(); for (int i = 0; i < inputs.length; i++) { Expression newExp = _translate(exp, targetRel, inputs[i]); if (newExp != null) { continue; } } return null; // rel not found under any input } } private Variable findInputVariable(Rel rel, int offset) { return findInputVariable(rel, offset, new int[] {0}); } private Variable findInputVariable(Rel rel, int offset, int offsets[]) { Frame frame = (Frame) mapRel2Frame.get(rel); if (frame != null && frame.variable != null) { if (offset == offsets[0]) { return frame.variable; } else { offsets[0]++; } } else { // no variable here -- go deeper Rel[] inputs = rel.getInputs(); for (int i = 0; i < inputs.length; i++) { Variable result = findInputVariable( inputs[i], offset, offsets); if (result != null) { return result; } } } return null; // not found } 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; /** variable which holds the current row of <code>rel</code> in this * implementation */ Variable variable; }; /** * <code>Translator</code> is a shuttle used to implement {@link * #translate(Expression,Rel)}. */ private class Translator extends EvaluationShuttle { Rel rel; Translator(Rel rel) { super(rel.getEnvironment()); this.rel = rel; } public Expression evaluateDown(Variable p) { return getField(p, 0); } public Expression evaluateDown(FieldAccess p) throws ParseTreeException { ParseTree ref = p.getReference(); if (ref instanceof Expression) { Expression refExp = (Expression) ref; OJClass clazz = Util.getType(getEnvironment(), refExp); if (SyntheticClass.isJoinClass(clazz)) { // This field access is something like "$input0.$f1". String fieldName = p.getName(); int field = SyntheticClass.getOrdinal(fieldName); Util.assert(refExp instanceof Variable); return getField((Variable) refExp, field); } } return super.evaluateDown(p); } private Variable getField(Variable variable, int field) { String varName = variable.toString(); Variable corelVariable = (Variable) mapCorelNameToVariable.get(varName); if (corelVariable != null) { return corelVariable; } int input = RelEnvironment.getInputOrdinal(varName); if (input >= 0) { Rel inputRel = rel.getInput(input); Variable var = findInputVariable(inputRel, field); if (var == null) { throw Util.newInternal( "could not find input " + field + " in " + inputRel); } return var; } else { return variable; } } }; } // 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. |