| /** |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.mrql; |
| |
| import org.apache.mrql.gen.*; |
| import java.util.*; |
| import java.io.*; |
| |
| |
| /** contains useful methods used by all stages of compilation and code generation */ |
| public class Translator extends Printer { |
| static Trees functions = #[ ]; |
| |
| static { |
| ClassImporter.load_classes(); |
| DataSource.loadParsers(); |
| } |
| |
| /** type environment that binds local variables to types */ |
| static SymbolTable type_env = new SymbolTable(); |
| |
| /** type environment that binds global variables to types */ |
| static SymbolTable global_type_env = new SymbolTable(); |
| |
| /** type environment that binds datatype names to types */ |
| static SymbolTable global_datatype_env = new SymbolTable(); |
| |
| /** used in pattern compilation and variable renaming */ |
| static SymbolTable st = new SymbolTable(); |
| |
| /** binds macro names to MRQL expressions (used for 'name = expr;' syntax) */ |
| static SymbolTable global_vars = new SymbolTable(); |
| |
| /** binds a UDF name to its plan */ |
| static SymbolTable global_functions = new SymbolTable(); |
| |
| /** binds a macro name to its body */ |
| static SymbolTable global_macros = new SymbolTable(); |
| |
| /** used in typedefs */ |
| static SymbolTable type_names = new SymbolTable(); |
| |
| /** binds a data constructor name to its type */ |
| static SymbolTable data_constructors = new SymbolTable(); |
| |
| static Trees repeat_variables = #[]; |
| |
| static { |
| global_type_env.insert("args",#<list(string)>); |
| } |
| |
| /** expressions with impure functions cannot factored out */ |
| static Trees impure_functions = #[random]; |
| |
| private static int var_count = 0; |
| |
| static void reset () { |
| var_count = 0; |
| type_env = global_type_env; |
| st = new SymbolTable(); |
| type_env = new SymbolTable(); |
| repeat_variables = #[]; |
| } |
| |
| static void global_reset () { |
| reset(); |
| global_type_env = new SymbolTable(); |
| global_datatype_env = new SymbolTable(); |
| global_vars = new SymbolTable(); |
| global_functions = new SymbolTable(); |
| global_macros = new SymbolTable(); |
| type_names = new SymbolTable(); |
| data_constructors = new SymbolTable(); |
| new TopLevel(); |
| } |
| |
| static void error ( String msg ) { |
| System.err.println("*** MRQL error at line "+Main.parser.line_pos()+": "+msg); |
| throw new Error(); |
| } |
| |
| final static Tree identity = #<lambda(x,x)>; |
| |
| static Tree identity () { |
| return Normalization.rename(#<lambda(x,bag(x))>); |
| } |
| |
| /** is this type a collection type? */ |
| public static boolean is_collection ( String x ) { |
| return x.equals("Bag") || x.equals("bag") || x.equals("List") || x.equals("list"); |
| } |
| |
| /** is this type a collection type? */ |
| public static boolean collection_type ( Tree tp ) { |
| match tp { |
| case `T(`t1): return is_collection(T); |
| }; |
| return false; |
| } |
| |
| /** is this type a collection type for values stored in HDFS? */ |
| public static boolean is_persistent_collection ( String x ) { |
| return x.equals("Bag") || x.equals("List"); |
| } |
| |
| /** make this collection type a persistent type that is stored in HDFS */ |
| public static String persistent_collection ( String x ) { |
| return (x.equals("list")) ? "List" : (x.equals("bag")) ? "Bag" : x; |
| } |
| |
| /** make this collection type a transient type stored in memory */ |
| public static String transient_collection ( String x ) { |
| return (x.equals("List")) ? "list" : (x.equals("Bag")) ? "bag" : x; |
| } |
| |
| /** An aggeregation must be based on a commutative monoid (plus,zero) with a unit: |
| * name(type,plus,zero,unit) |
| * plus: function from (b,b) to b, zero: b, unit: function from a to b |
| */ |
| static Trees monoids = |
| #[ count(any,lambda(x,call(plus,nth(x,0),nth(x,1))),typed(0,long),lambda(x,typed(1,long))), |
| sum(int,lambda(x,call(plus,nth(x,0),nth(x,1))),typed(0,long),lambda(x,typed(x,long))), |
| sum(long,lambda(x,call(plus,nth(x,0),nth(x,1))),typed(0,long),`identity), |
| sum(float,lambda(x,call(plus,nth(x,0),nth(x,1))),typed(0.0,double),lambda(x,typed(x,double))), |
| sum(double,lambda(x,call(plus,nth(x,0),nth(x,1))),typed(0.0,double),`identity), |
| max(int,lambda(x,call(max,nth(x,0),nth(x,1))),typed(`(Integer.MIN_VALUE),int),`identity), |
| max(long,lambda(x,call(max,nth(x,0),nth(x,1))),typed(`(Long.MIN_VALUE),long),`identity), |
| max(float,lambda(x,call(max,nth(x,0),nth(x,1))),typed(`(Float.MIN_VALUE),float),`identity), |
| max(double,lambda(x,call(max,nth(x,0),nth(x,1))),typed(`(Double.MIN_VALUE),double),`identity), |
| min(int,lambda(x,call(min,nth(x,0),nth(x,1))),typed(`(Integer.MAX_VALUE),int),`identity), |
| min(long,lambda(x,call(min,nth(x,0),nth(x,1))),typed(`(Long.MAX_VALUE),long),`identity), |
| min(float,lambda(x,call(min,nth(x,0),nth(x,1))),typed(`(Float.MAX_VALUE),float),`identity), |
| min(double,lambda(x,call(min,nth(x,0),nth(x,1))),typed(`(Double.MAX_VALUE),double),`identity), |
| avg_aggr(int,lambda(x,tuple(call(plus,nth(nth(x,0),0),nth(nth(x,1),0)), |
| call(plus,nth(nth(x,0),1),nth(nth(x,1),1)))), |
| tuple(typed(0.0,double),typed(0,long)), |
| lambda(x,tuple(typed(x,double),typed(1,long)))), |
| avg_aggr(long,lambda(x,tuple(call(plus,nth(nth(x,0),0),nth(nth(x,1),0)), |
| call(plus,nth(nth(x,0),1),nth(nth(x,1),1)))), |
| tuple(typed(0.0,double),typed(0,long)), |
| lambda(x,tuple(typed(x,double),typed(1,long)))), |
| avg_aggr(float,lambda(x,tuple(call(plus,nth(nth(x,0),0),nth(nth(x,1),0)), |
| call(plus,nth(nth(x,0),1),nth(nth(x,1),1)))), |
| tuple(typed(0.0,double),typed(0,long)), |
| lambda(x,tuple(typed(x,double),typed(1,long)))), |
| avg_aggr(double,lambda(x,tuple(call(plus,nth(nth(x,0),0),nth(nth(x,1),0)), |
| call(plus,nth(nth(x,0),1),nth(nth(x,1),1)))), |
| tuple(typed(0.0,double),typed(0,long)), |
| lambda(x,tuple(typed(x,double),typed(1,long)))), |
| all(bool,lambda(x,call(and,nth(x,0),nth(x,1))),true,`identity), |
| some(bool,lambda(x,call(or,nth(x,0),nth(x,1))),false,`identity) |
| ]; |
| |
| static void print_aggregates () { |
| for ( Tree m: monoids ) |
| match m { |
| case `f(`tp,...): |
| System.out.print(" "+f+":"+print_type(tp)); |
| } |
| System.out.println(); |
| } |
| |
| static Trees plans_with_distributed_lambdas |
| = #[MapReduce,MapAggregateReduce,MapCombineReduce,FroupByJoin,Aggregate, |
| MapReduce2,MapCombineReduce2,MapAggregateReduce2,MapJoin,MapAggregateJoin, |
| CrossProduct,CrossAggregateProduct,cMap,AggregateMap,BSP,GroupByJoin, |
| OuterMerge,RightOuterMerge,Provenance]; |
| |
| static Trees algebraic_operators |
| = #[mapReduce,mapReduce2,cmap,join,groupBy,orderBy,aggregate,map,filter,repeat,closure]; |
| |
| static Trees plan_names = plans_with_distributed_lambdas.append(algebraic_operators) |
| .append(#[Repeat,Closure,Generator,Let,If,Stream]); |
| |
| /** generates new variable names */ |
| public static Tree new_var () { |
| return new VariableLeaf("x_"+(Integer.toString(var_count++))); |
| } |
| |
| /** is this expression pure? (does it contain calls to impure functions?) */ |
| static boolean is_pure ( Tree expr ) { |
| match expr { |
| case call(`f,...al): |
| if (impure_functions.member(f)) |
| return false; |
| else fail |
| case `f(...al): |
| for ( Tree a: al ) |
| if (!is_pure(a)) |
| return false; |
| }; |
| return true; |
| } |
| |
| public static Trees union ( Trees xs, Trees ys ) { |
| Trees res = xs; |
| for ( Tree y: ys ) |
| if (!xs.member(y)) |
| res = res.append(y); |
| return res; |
| } |
| |
| /** return the variables of a pattern */ |
| static Trees pattern_variables ( Tree pattern ) { |
| Trees args = #[]; |
| match pattern { |
| case tuple(...pl): |
| for ( Tree p: pl ) |
| args = union(args,pattern_variables(p)); |
| case record(...bl): |
| for ( Tree b: bl ) |
| match b { |
| case bind(`n,`p): |
| args = union(args,pattern_variables(p)); |
| }; |
| case typed(`p,_): |
| args = pattern_variables(p); |
| case `v: |
| if (v.is_variable()) |
| args = #[`v]; |
| }; |
| return args; |
| } |
| |
| /** replace all occurences of from_expr in expr with to_expr |
| * @param from_expr target |
| * @param to_expr replacement |
| * @param expr input |
| * @return equal to expr but with all occurences of from_expr replaced with to_expr |
| */ |
| public static Tree subst ( Tree from_expr, Tree to_expr, Tree expr ) { |
| if (expr.equals(from_expr)) |
| return to_expr; |
| match expr { |
| case lambda(`v,_): |
| if (pattern_variables(v).member(from_expr)) |
| return expr; |
| else fail |
| case bind(`a,`u): |
| return #<bind(`a,`(subst(from_expr,to_expr,u)))>; |
| case `f(...al): |
| return #<`f(...(subst_list(from_expr,to_expr,al)))>; |
| }; |
| return expr; |
| } |
| |
| /** replace all occurences of from_expr in el with to_expr |
| * @param from_expr target |
| * @param to_expr replacement |
| * @param el list of input expressions |
| * @return equal to el but with all occurences of from_expr replaced with to_expr |
| */ |
| public static Trees subst_list ( Tree from_expr, Tree to_expr, Trees el ) { |
| Trees bl = #[]; |
| for ( Tree e: el ) |
| bl = bl.append(subst(from_expr,to_expr,e)); |
| return bl; |
| } |
| |
| /** replace all occurences of var in expr with to_expr only if to_expr is pure or it is used once only |
| * @param var target |
| * @param to_expr replacement |
| * @param expr input |
| * @return equal to expr but with all occurences of from_expr replaced with to_expr |
| */ |
| public static Tree subst_var ( Tree var, Tree to_expr, Tree expr ) { |
| if (!is_pure(to_expr) && occurences(var,expr) > 1) |
| return #<let(`var,`to_expr,`expr)>; |
| else return subst(var,to_expr,expr); |
| } |
| |
| /** used in the MRQL parser to handle templates */ |
| public static Tree template ( Tree s ) { |
| match s { |
| case template(`parser,...as): |
| try { |
| Trees args = #[]; |
| String tx = ""; |
| int i = 0; |
| for ( Tree a: as ) |
| match a { |
| case text(`t): tx += t; |
| case _: args = args.append(a); |
| tx += "{{"+(i++)+"}}"; |
| }; |
| Class<? extends Parser> pc = DataSource.parserDirectory.get(parser.toString()); |
| if (pc == null) |
| throw new Error("Unrecognized parser: "+parser); |
| Parser p = pc.newInstance(); |
| p.initialize(#[]); |
| Bag e = p.parse(tx); |
| Tree res = Interpreter.reify(e.get(0),p.type()); |
| for ( int j = 0; j < i; j++ ) |
| res = subst(new VariableLeaf("t_"+j),args.nth(j),res); |
| return res; |
| } catch (Exception e) { |
| throw new Error("Wrong template: "+s+"\n"+e); |
| } |
| }; |
| throw new Error("Wrong template: "+s); |
| } |
| |
| /** convert Tree constructions to code that construct these Trees (used in the Compiler) */ |
| public static String reify ( Tree e ) { |
| if (e instanceof LongLeaf) |
| return "new org.apache.mrql.gen.LongLeaf(" + e + ")"; |
| else if (e instanceof DoubleLeaf) |
| return "new org.apache.mrql.gen.DoubleLeaf(" + e + ")"; |
| else if (e instanceof VariableLeaf) |
| return "new org.apache.mrql.gen.VariableLeaf(\"" + e.variableValue() + "\")"; |
| else if (e instanceof StringLeaf) |
| return "new org.apache.mrql.gen.StringLeaf(" + e.toString().replace("\\","\\\\") + ")"; |
| else { |
| Node n = (Node) e; |
| return "new org.apache.mrql.gen.Node(\""+n.name()+"\","+reify(n.children())+")"; |
| } |
| } |
| |
| /** convert Tree constructions to code that construct these Trees (used in the Compiler) */ |
| public static String reify ( Trees ts ) { |
| String s = "org.apache.mrql.gen.Trees.nil"; |
| for ( Tree c: ts ) |
| s += ".append("+reify(c)+")"; |
| return s; |
| } |
| |
| /** return the list of free variables in e that are not in exclude list */ |
| public static Trees free_variables ( Tree e, Trees exclude ) { |
| if (e == null) |
| return #[]; |
| match e { |
| case lambda(`x,`b): |
| return free_variables(b,exclude.append(pattern_variables(x))); |
| case let(`x,`u,`b): |
| return free_variables(b,exclude.append(pattern_variables(x))) |
| .append(free_variables(u,exclude)); |
| case Let(`x,`u,`b): |
| return free_variables(b,exclude.append(pattern_variables(x))) |
| .append(free_variables(u,exclude)); |
| case select(`u,from(...bs),`p): |
| Trees ex = exclude; |
| Trees fs = #[]; |
| for ( Tree b: bs ) |
| match b { |
| case bind(`v,`x): |
| fs = fs.append(free_variables(x,ex)); |
| ex = ex.append(pattern_variables(v)); |
| }; |
| return free_variables(p,ex).append(free_variables(u,ex)).append(fs); |
| case `f(...as): |
| Trees res = #[]; |
| for ( Tree a: as ) |
| res = res.append(free_variables(a,exclude)); |
| return res; |
| case `v: |
| if (v.is_variable() && v.toString().startsWith("x_") && !exclude.member(v)) |
| return #[`v]; |
| }; |
| return #[]; |
| } |
| |
| /** count the occurences of x in e */ |
| public static int occurences ( Tree x, Tree e ) { |
| if (x.equals(e)) |
| return 1; |
| match e { |
| case `f(...as): |
| int i = 0; |
| for ( Tree a: as ) |
| i += occurences(x,a); |
| return i; |
| }; |
| return 0; |
| } |
| |
| /** return true if x is equal to y modulo variable substitution */ |
| public static boolean alpha_equivalent ( Tree x, Tree y, SymbolTable st ) { |
| match #<T(`x,`y)> { |
| case T(lambda(`vx,`bx),lambda(`vy,`by)): |
| if (!vx.equals(vy)) |
| st.insert(vx.toString(),vy); |
| return alpha_equivalent(bx,by,st); |
| case T(`f(...xs),`g(...ys)): |
| if (!f.equals(g) || xs.length() != ys.length()) |
| return false; |
| for ( ; !xs.is_empty(); xs = xs.tail(), ys = ys.tail() ) |
| if (!alpha_equivalent(xs.head(),ys.head(),st)) |
| return false; |
| return true; |
| case T(`v,`w): |
| if (v.is_variable() && w.is_variable()) |
| return v.equals(w) || (st.lookup(v.toString()) != null |
| && st.lookup(v.toString()).equals(w)); |
| }; |
| return x.equals(y); |
| } |
| |
| private static SymbolTable alpha_symbol_table = new SymbolTable(); |
| |
| /** return true if x is equal to y modulo variable substitution */ |
| public static boolean alpha_equivalent ( Tree x, Tree y ) { |
| alpha_symbol_table.begin_scope(); |
| boolean b = alpha_equivalent(x,y,alpha_symbol_table); |
| alpha_symbol_table.end_scope(); |
| return b; |
| } |
| |
| /** translate a simplified select MRQL query to an algebraic form */ |
| public static Tree translate_select ( Tree e ) { |
| match e { |
| case select(`u,from(),where(true)): |
| return #<bag(`(translate_select(u)))>; |
| case select(`u,from(),where(`c)): |
| return #<if(`(translate_select(c)),bag(`(translate_select(u))),bag())>; |
| case select(`u,from(bind(`v,`d),...bl),where(`c)): |
| Tree n = translate_select(#<select(`u,from(...bl),where(`c))>); |
| return #<cmap(lambda(`v,`n),`(translate_select(d)))>; |
| case `f(...al): |
| Trees bl = #[]; |
| for ( Tree a: al ) |
| bl = bl.append(translate_select(a)); |
| return #<`f(...bl)>; |
| }; |
| return e; |
| } |
| |
| /** the MRQL top-level interfacse to evaluate a single MRQL expression or command */ |
| public static void top_level ( Tree expr ) { |
| TopLevel.evaluate_top_level(expr); |
| } |
| } |
