| /** |
| * 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.*; |
| |
| |
| /** the type inference/checker for MRQL expressions and algebraic forms */ |
| public class TypeInference extends Translator { |
| |
| private static Tree make_tuple ( Trees pl ) { |
| if (pl.length() == 1) |
| return pl.head(); |
| return #<tuple(...pl)>; |
| } |
| |
| public static Tree make_persistent_type ( Tree tp ) { |
| match tp { |
| case `T(`t): |
| if (!is_collection(T)) |
| fail; |
| String S = persistent_collection(T); |
| return #<`S(`t)>; |
| }; |
| return tp; |
| } |
| |
| private static String max_collection ( String x, String y ) { |
| boolean is_bag = x.equals("Bag") || y.equals("Bag") || x.equals("bag") || y.equals("bag"); |
| boolean is_persistent = x.equals("Bag") || y.equals("Bag") || x.equals("List") || y.equals("List"); |
| return (is_bag) ? ((is_persistent) ? "Bag" : "bag") : ((is_persistent) ? "List" : "list"); |
| } |
| |
| private static boolean numerical ( String tp ) { |
| return #[short,int,long,float,double].member(#<`tp>); |
| } |
| |
| static void type_error ( Tree e, String msg ) { |
| System.err.println("*** Type error (line: "+e.line+", position: "+e.position+")"); |
| if (Config.trace && type_env.iterator().hasNext()) { |
| msg += "\nVariable Types:"; |
| for ( String var: type_env ) |
| msg += "\n "+var + ": " + print_type(type_env.lookup(var)); |
| }; |
| System.err.println("*** "+msg); |
| throw new Error("Type Error"); |
| } |
| |
| /** given that pattern has type tp, bind the pattern variables to types */ |
| private static Trees bind_pattern_type ( Tree pattern, Tree tp ) { |
| Trees args = #[]; |
| match pattern { |
| case tuple(...pl): |
| match tp { |
| case tuple(...tl): |
| if (tl.length() != pl.length()) |
| type_error(pattern,"Tuple pattern "+print_query(pattern)+" must have exactly " |
| +tl.length()+" components"); |
| int i = 0; |
| for ( Tree p: pl ) |
| args = args.append(bind_pattern_type(p,tl.nth(i++))); |
| case `etp: type_error(pattern,"Wrong pattern: found "+print_query(pattern) |
| +" but expected a pattern that matches the type "+print_type(etp)); |
| }; |
| case record(...bl): |
| Trees attrs = #[]; |
| match tp { |
| case record(...tl): |
| for ( Tree b: bl ) |
| match b { |
| case bind(`n,`p): |
| boolean found = false; |
| if (attrs.member(n)) |
| type_error(pattern,"Duplicate record attribute name: "+n |
| +" in pattern "+print_query(pattern)); |
| attrs = attrs.append(n); |
| for ( Tree t: tl ) |
| match t { |
| case bind(`nt,`pt): |
| if (!nt.equals(n)) |
| fail; |
| found = true; |
| args = args.append(bind_pattern_type(p,pt)); |
| }; |
| if (!found) |
| type_error(pattern,"Wrong record component: "+n |
| +" in pattern "+print_query(pattern) |
| +" (expected one from "+print_type(tp)+")"); |
| }; |
| case `etp: type_error(pattern,"Wrong pattern: found "+print_query(pattern) |
| +" but expected a pattern that matches the type "+print_type(etp)); |
| }; |
| case typed(`p,`t): |
| if (subtype(t,tp)) |
| args = bind_pattern_type(p,t); |
| else type_error(pattern,"Type "+print_type(t)+" in pattern "+print_query(pattern) |
| +" does not match the expected type "+print_type(tp)); |
| case list(...pl): |
| match tp { |
| case list(`etp): |
| for ( Tree p: pl ) |
| args = args.append(bind_pattern_type(p,etp)); |
| case `stp: type_error(pattern,"List pattern "+print_query(pattern) |
| +" can only be used for lists (found "+print_type(tp)+")"); |
| }; |
| case call(`c,...s): |
| Tree ci = data_constructors.lookup(c.toString()); |
| if (ci == null) |
| type_error(pattern,"Undefined data constructor "+c+" in pattern "+print_query(pattern)); |
| match ci { |
| case `dname(`n,`dtp): |
| if (!subtype(tp,expand(#<`dname>))) |
| type_error(pattern,"Cannot use the data constructor "+print_query(pattern) |
| +" in a pattern that expects type "+print_type(tp)); |
| args = args.append(bind_pattern_type(s.length() == 1 ? s.head() : #<tuple(...s)>, |
| dtp)); |
| }; |
| case any: ; |
| case `v: |
| if (v.is_variable()) { |
| args = args.append(v); |
| type_env.insert(v.toString(),tp); |
| } else if (!subtype(type_inference2(v),tp)) |
| type_error(pattern,"The constant "+v+" in pattern " |
| +print_query(pattern)+" is not of type "+print_type(tp)); |
| }; |
| return args; |
| } |
| |
| private static short needs_coerce ( Tree x, Tree y ) { |
| if (x.is_variable() && numerical(x.toString()) |
| && y.is_variable() && numerical(y.toString())) { |
| short cx = MRContainer.type_code(x.toString()); |
| short cy = MRContainer.type_code(y.toString()); |
| return (cx == cy) ? -1 : (cx > cy) ? cx : cy; |
| }; |
| return -1; |
| } |
| |
| /** type equality in MRQL is structured equality, not named equality */ |
| public static boolean equal_types ( Tree tx, Tree ty ) { |
| tx = expand(tx); |
| ty = expand(ty); |
| if (tx.equals(ty)) |
| return true; |
| match tx { |
| case `f(...xs): |
| match ty { |
| case `g(...ys): |
| if (f.equals(g) && xs.length() == ys.length()) { |
| for ( ; !ys.is_empty(); xs = xs.tail(), ys = ys.tail() ) |
| if (!equal_types(xs.head(),ys.head())) |
| return false; |
| return true; |
| } |
| } |
| }; |
| return false; |
| } |
| |
| /** is the collection type name S a subtype of that of T? |
| List \lt Bag \lt bag and List \lt list \lt bag |
| */ |
| public static boolean subtype ( String S, String T ) { |
| return S.equals(T) |
| || (S.equals("List") && T.equals("list")) |
| || (S.equals("List") && T.equals("Bag")) |
| || (S.equals("list") && T.equals("bag")) |
| || (S.equals("Bag") && T.equals("bag")); |
| } |
| |
| /** is the type tx a subtype of type ty? */ |
| public static boolean subtype ( Tree tx, Tree ty ) { |
| tx = expand(tx); |
| ty = expand(ty); |
| if (ty.equals(#<any>)) |
| return true; |
| if (equal_types(tx,ty)) |
| return true; |
| if (tx.is_variable() && numerical(tx.toString()) |
| && ty.is_variable() && numerical(ty.toString())) |
| return MRContainer.type_code(tx.toString()) <= MRContainer.type_code(ty.toString()); |
| match tx { |
| case `T(`tex): |
| if (!is_collection(T)) |
| fail; |
| match ty { |
| case `S(`tey): |
| if (is_collection(S)) |
| return subtype(T,S) && subtype(tex,tey); |
| else fail |
| }; |
| case union(...): |
| if (ty.equals(#<union>)) // used for XML functions |
| return true; |
| else fail |
| case `f(...xs): |
| match ty { |
| case `g(...ys): |
| if (f.equals(g)) |
| return subtype(xs,ys); |
| } |
| }; |
| return false; |
| } |
| |
| public static boolean subtype ( Trees ts1, Trees ts2 ) { |
| if (ts1.length() != ts2.length()) |
| return false; |
| for ( Trees s1 = ts1, s2 = ts2; !s1.is_empty(); s1=s1.tail(), s2=s2.tail() ) |
| if (!subtype(s1.head(),s2.head())) |
| return false; |
| return true; |
| } |
| |
| public static int compare_types ( Tree t1, Tree t2 ) { |
| if (t1.equals(#<any>) && t2.equals(#<any>)) |
| return 0; |
| else if (t2.equals(#<any>)) |
| return -1; |
| else if (t1.equals(#<any>)) |
| return 1; |
| else if (t1 instanceof VariableLeaf && t2 instanceof VariableLeaf) |
| return MRContainer.type_code(((VariableLeaf)t1).value()) |
| -MRContainer.type_code(((VariableLeaf)t2).value()); |
| else if (t1 instanceof VariableLeaf) |
| return -1; |
| else return 1; |
| } |
| |
| /** if the expression at loc.head has type tx that is a subtype of ty, coerce it to ty |
| * NOTE: it destructively changes the expression at loc |
| */ |
| private static void coerce ( Tree tx, Tree ty, Trees loc ) { |
| tx = expand(tx); |
| ty = expand(ty); |
| if (ty.equals(#<any>) || equal_types(tx,ty)) |
| return; |
| if (tx.is_variable() && numerical(tx.toString()) |
| && ty.is_variable() && numerical(ty.toString())) { |
| loc.head = #<call(coerce,`(loc.head), // destructive |
| `(MRContainer.type_code(ty.toString())))>; |
| return; |
| }; |
| match tx { |
| case `T(`tex): |
| if (!is_collection(T)) |
| fail; |
| match ty { |
| case `S(`tey): |
| if (!is_collection(S)) |
| fail; |
| if (is_persistent_collection(T) && !is_persistent_collection(S)) |
| loc.head = #<Collect(`(loc.head))>; // destructive |
| if (subtype(tex,tey) && unify(tex,tey) == null) { |
| Tree nv = new_var(); |
| Tree b = #<bag(`nv)>; |
| coerce(tex,tey,((Node)b).children); |
| loc.head = #<cmap(lambda(`nv,`b),`(loc.head))>; // destructive |
| return; |
| } |
| }; |
| case tuple(...xs): |
| match ty { |
| case tuple(...ys): |
| Tree nv = new_var(); |
| Trees nt = #[]; |
| int i = 0; |
| for ( Trees xl = xs, yl = ys; xl != #[] && yl != #[]; xl = xl.tail, yl = yl.tail ) { |
| Trees dest = #[nth(`nv,`(i++))]; |
| coerce(xl.head,yl.head,dest); |
| nt = nt.append(dest); |
| }; |
| loc.head = #<let(`nv,`(loc.head),tuple(...nt))>; // destructive |
| } |
| case record(...xs): |
| match ty { |
| case record(...ys): |
| Tree nv = new_var(); |
| Trees nt = #[]; |
| for ( Tree x: xs ) |
| match x { |
| case bind(`ax,`tex): |
| for ( Tree y: ys ) |
| match y { |
| case bind(`ay,`tey): |
| if (equal_types(ax,ay)) { |
| Tree b = #<bind(`ax,project(`nv,`ax))>; |
| nt = nt.append(b); |
| coerce(tex,tey,((Node)b).children.tail); |
| } |
| } |
| }; |
| loc.head = #<let(`nv,`(loc.head),record(...nt))>; // destructive |
| } |
| } |
| } |
| |
| /** poor-man's type-unification (the any type unifies with everything) */ |
| private static Trees unify ( Trees ts1, Trees ts2 ) { |
| Trees s = #[]; |
| if (ts1.length() != ts2.length()) |
| return null; |
| for ( Trees s1 = ts1, s2 = ts2; !s1.is_empty(); s1=s1.tail(), s2=s2.tail() ) { |
| Tree t = unify(s1.head(),s2.head()); |
| if (t == null) |
| return null; |
| else s = s.append(t); |
| }; |
| return s; |
| } |
| |
| /** poor-man's type-unification (the any type unifies with everything) */ |
| public static Tree unify ( Tree t1, Tree t2 ) { |
| t1 = expand(t1); |
| t2 = expand(t2); |
| if (t1.equals(#<any>)) |
| return t2; |
| if (t2.equals(#<any>) || equal_types(t1,t2)) |
| return t1; |
| match t1 { |
| case `T(`t): |
| match t2 { |
| case `S(`s): |
| if (!T.equals(S)) |
| fail; |
| if (!is_collection(T)) |
| fail; |
| Tree ts = unify(t,s); |
| if (ts != null) |
| return #<`T(`ts)>; |
| } |
| case `f(...ts1): |
| match t2 { |
| case `g(...ts2): |
| Trees s = unify(ts1,ts2); |
| if (f.equals(g) && s != null) |
| return #<`f(...s)>; |
| } |
| }; |
| return null; |
| } |
| |
| /** similar to unify, but it returns the second type instantiated */ |
| private static Trees subtype_unify ( Trees ts1, Trees ts2 ) { |
| Trees s = #[]; |
| if (ts1.length() != ts2.length()) |
| return null; |
| for ( Trees s1 = ts1, s2 = ts2; !s1.is_empty(); s1=s1.tail(), s2=s2.tail() ) { |
| Tree t = subtype_unify(s1.head(),s2.head()); |
| if (t == null) |
| return null; |
| else s = s.append(t); |
| }; |
| return s; |
| } |
| |
| /** similar to unify, but it returns the second type instantiated */ |
| public static Tree subtype_unify ( Tree t1, Tree t2 ) { |
| t1 = expand(t1); |
| t2 = expand(t2); |
| if (t1.equals(#<any>)) |
| return t2; |
| if (t2.equals(#<any>) || equal_types(t1,t2)) |
| return t1; |
| match t1 { |
| case `T(`t): |
| match t2 { |
| case `S(`s): |
| if (!is_collection(T)) |
| fail; |
| Tree ts = subtype_unify(t,s); |
| if (ts != null) |
| return #<`T(`ts)>; |
| } |
| case `f(...ts1): |
| match t2 { |
| case `g(...ts2): |
| Trees s = subtype_unify(ts1,ts2); |
| if (f.equals(g) && s != null) |
| return #<`f(...s)>; |
| } |
| }; |
| return null; |
| } |
| |
| /** if the types tx and ty do not unify, try to coerce them */ |
| static Tree unify ( Tree tx, Tree ty, Trees destx, Trees desty ) { |
| Tree tp = unify(tx,ty); |
| if (tp != null) |
| return tp; |
| else if (subtype(tx,ty)) { |
| coerce(tx,ty,destx); |
| return subtype_unify(tx,ty); |
| } else if (subtype(ty,tx)) { |
| coerce(ty,tx,desty); |
| return subtype_unify(ty,tx); |
| } else return null; |
| } |
| |
| /** find a type from the list of types ts that is the supertype of all other types */ |
| private static Tree maximum_type ( Trees ts ) { |
| Tree maxt = ts.head; |
| for ( Tree t: ts.tail ) |
| if (subtype(maxt,t) || maxt.equals(#<any>)) |
| maxt = t; |
| return maxt; |
| } |
| |
| /** if the type tp is a named type, expand it using its definition */ |
| public static Tree expand ( Tree tp ) { |
| if (!tp.is_variable()) |
| return tp; |
| Tree rt = global_datatype_env.lookup(tp.toString()); |
| if (rt != null) |
| return expand(rt); |
| rt = type_names.lookup(tp.toString()); |
| if (rt == null) |
| return tp; |
| else return expand(rt); |
| } |
| |
| /** infer the type of an expression and expand it if necessary |
| * @param e the expression |
| * @return the type of e |
| */ |
| public static Tree type_inference2 ( Tree e ) { |
| return expand(type_inference(e)); |
| } |
| |
| /** infer the type of an expression |
| * @param e the expression |
| * @return the type of e |
| */ |
| public static Tree type_inference ( Tree e ) { |
| match e { |
| case select(`opt_dist,`u,from(...bl),where(`c),groupby(...gs),orderby(...os)): |
| type_env.begin_scope(); |
| Trees dvs = #[]; |
| String max_type = "list"; |
| for ( Tree b: bl ) |
| match b { |
| case bind(`p,`d): |
| match type_inference2(d) { |
| case `T(`tp): |
| if (!is_collection(T)) |
| fail; |
| dvs = dvs.append(bind_pattern_type(p,tp)); |
| max_type = max_collection(T,max_type); |
| case `ftp: |
| type_error(e,"The from-binding domain "+print_query(d)+" in " |
| +print_query(e)+" must be a collection (found " |
| +print_type(ftp)+")"); |
| } |
| }; |
| Tree ctp = type_inference2(c); |
| if (unify(ctp,#<bool>) == null) |
| type_error(e,"The predicate "+print_query(c)+" in "+print_query(e) |
| +" must be a boolean (found "+print_type(ctp)+")"); |
| match #<groupby(...gs)> { |
| case groupby(`h,...gl): |
| Trees pvs = #[]; |
| for ( Tree g: gl ) |
| match g { |
| case bind(`gp,`gd): |
| bind_pattern_type(gp,type_inference2(gd)); |
| pvs = pvs.append(pattern_variables(gp)); |
| }; |
| // find the type of the partition variable |
| Trees partl = #[]; |
| for ( Tree dv: pattern_variables(#<tuple(...dvs)>) ) |
| partl = partl.append(#<bind(`dv,`(type_env.lookup(dv.toString())))>); |
| type_env.insert("partition",#<bag(record(...partl))>); |
| // lift domain variables to bags |
| for ( Tree dv: dvs ) |
| if (!pvs.member(dv)) |
| type_env.insert(dv.toString(), |
| #<bag(`(type_env.lookup(dv.toString())))>); |
| Tree htp = type_inference2(h); |
| if (unify(htp,#<bool>) == null) |
| type_error(e,"The group-by predicate "+print_query(h)+" in "+print_query(e) |
| +" must be a boolean (found "+print_type(htp)+")"); |
| }; |
| match #<orderby(...os)> { |
| case orderby(`l,...ol): |
| if (!l.equals(#<none>)) { |
| Tree ltp = type_inference2(l); |
| if (unify(ltp,#<int>) == null) |
| type_error(e,"The limit "+print_query(l)+" in "+print_query(e) |
| +" must be an int (found "+print_type(ltp)+")"); |
| }; |
| for ( Tree o: ol) |
| type_inference2(o); |
| Tree rtp = type_inference2(u); |
| type_env.end_scope(); |
| return (is_persistent_collection(max_type)) ? #<List(`rtp)> : #<list(`rtp)>; |
| }; |
| Tree rtp = type_inference2(u); |
| type_env.end_scope(); |
| return (is_persistent_collection(max_type)) ? #<Bag(`rtp)> : #<bag(`rtp)>; |
| case select(`u,from(...bl),where(`c)): |
| String max_type = "list"; |
| for ( Tree b: bl ) |
| match b { |
| case bind(`v,`d): |
| match type_inference2(d) { |
| case `T(`tp): |
| if (!is_collection(T)) |
| fail; |
| type_env.insert(v.toString(),tp); |
| max_type = max_collection(T,max_type); |
| case _: type_error(e,"Expected a collection: "+print_query(d) |
| +" in "+print_query(e)); |
| } |
| }; |
| if (unify(type_inference2(c),#<bool>) != null) { |
| Tree tp = type_inference(u); |
| return (is_persistent_collection(max_type)) ? #<Bag(`tp)> : #<bag(`tp)>; |
| } else type_error(e,"The select predicate must be boolean: "+print_query(e)); |
| case let_bind(`p,`u,`b): |
| type_env.begin_scope(); |
| bind_pattern_type(p,type_inference2(u)); |
| Tree tp = type_inference2(b); |
| type_env.end_scope(); |
| return tp; |
| case let(`p,`u,`b): |
| bind_pattern_type(p,type_inference2(u)); |
| return type_inference2(b); |
| case Let(`p,`u,`b): |
| bind_pattern_type(p,type_inference2(u)); |
| return type_inference2(b); |
| case case(`u,...cs): |
| Tree tp = type_inference2(u); |
| Trees ts = #[]; |
| for ( Tree c: cs ) |
| match c { |
| case case(`p,`b): |
| type_env.begin_scope(); |
| bind_pattern_type(p,tp); |
| ts = ts.append(type_inference2(b)); |
| type_env.end_scope(); |
| }; |
| Tree maxt = maximum_type(ts); |
| for ( ; cs != #[] && ts != #[]; cs = cs.tail, ts = ts.tail ) |
| match cs.head { |
| case case(`p,`b): |
| if (subtype(ts.head,maxt)) |
| coerce(ts.head,maxt,((Node)(cs.head)).children.tail); |
| else type_error(cs.head,"Mismatched case output: "+b); |
| }; |
| return maxt; |
| case lambda(`v,`b): |
| if (!v.is_variable()) { |
| Tree nv = new_var(); |
| type_env.insert(nv.toString(),type_inference(v)); |
| st.begin_scope(); |
| if (!Normalization.bind_pattern(v,nv).is_empty()) |
| error("Lambda patterns must be irrefutable: "+print_query(e)); |
| for ( String nm: st ) |
| if (st.is_local(nm)) |
| b = Simplification.subst(#<`nm>,st.lookup(nm),b); |
| st.end_scope(); |
| return type_inference(#<lambda(`nv,`b)>); |
| } else if (type_env.lookup(v.toString()) == null) |
| type_env.insert(v.toString(),#<any>); |
| return #<arrow(`(type_env.lookup(v.toString())),`(type_inference(b)))>; |
| case function(tuple(...params),`outp,`body): |
| Trees as = #[]; |
| for ( Tree param: params ) |
| match param { |
| case `bind(`v,`tp): |
| type_env.insert(v.toString(),tp); |
| as = as.append(tp); |
| }; |
| Tree btp = type_inference(body); |
| if (!subtype(btp,outp)) |
| type_error(e,"The type of the function body "+print_type(btp) |
| +" does not match the expected type "+print_type(outp)+"\n"+e); |
| if (unify(btp,outp) == null) { // the body needs coercion |
| Trees b = #[`body]; |
| coerce(btp,outp,b); |
| body = b.head; |
| }; |
| return #<arrow(tuple(...as),`outp)>; |
| case call(source,binary,`f,`tp): |
| return tp; |
| case call(source,binary,`f): |
| if (!f.is_string()) |
| type_error(e,"The source file must be a constant string: "+print_query(f)); |
| Tree tp = null; |
| if (Config.hadoop_mode) |
| tp = Evaluator.evaluator.get_type(f.stringValue()); |
| else tp = MapReduceAlgebra.get_type(f.stringValue()); |
| if (tp == null) |
| type_error(e,"Cannot find the type of file "+f); |
| ((Node)e).children = ((Node)e).children.append(tp); // destructive |
| return tp; |
| case call(source,`parser,`f,...args): |
| if (!parser.is_variable()) |
| type_error(e,"The parser must be a constant name: "+print_query(parser)); |
| if (unify(type_inference(f),#<string>) == null) |
| type_error(e,"The source file must be a string: "+print_query(f)); |
| try { |
| Class<? extends Parser> pc = DataSource.parserDirectory.get(parser.toString()); |
| if (pc == null) |
| type_error(e,"Unrecognized parser: "+parser); |
| Parser p = pc.newInstance(); |
| p.initialize(args); |
| return #<Bag(`(p.type()))>; |
| } catch (Exception x) { |
| type_error(e,"Unrecognized parser type: "+parser); |
| } |
| case call(stream,binary,`f): |
| if (Config.stream_window == 0) |
| type_error(e,"Not in stream processing mode"); |
| Tree tp = type_inference(#<call(source,binary,`f)>); |
| ((Node)e).children = ((Node)e).children.append(tp); // destructive |
| return tp; |
| case call(stream,`parser,`f,...args): |
| if (parser.equals(#<binary>)) |
| fail; |
| if (Config.stream_window == 0) |
| type_error(e,"Not in stream processing mode"); |
| if (!parser.is_variable()) |
| type_error(e,"The parser must be a constant name: "+print_query(parser)); |
| if (unify(type_inference(f),#<string>) == null) |
| type_error(e,"The source file must be a string: "+print_query(f)); |
| if (unify(type_inference(args.head()),#<int>) != null) |
| args = args.tail(); |
| try { |
| Class<? extends Parser> pc = DataSource.parserDirectory.get(parser.toString()); |
| if (pc == null) |
| type_error(e,"Unrecognized parser: "+parser); |
| Parser p = pc.newInstance(); |
| p.initialize(args); |
| return #<Bag(`(p.type()))>; |
| } catch (Exception x) { |
| type_error(e,"Unrecognized parser type: "+parser); |
| } |
| case call(stream,...r): |
| if (Config.stream_window == 0) |
| type_error(e,"Not in stream processing mode"); |
| return type_inference(#<call(source,...r)>); |
| case BinaryStream(`path,`tp): |
| return tp; |
| case ParsedStream(`parser,...r): |
| return type_inference(#<call(stream,`parser,...r)>); |
| case stream(lambda(`v,`b),`u): |
| bind_pattern_type(v,type_inference2(u)); |
| return type_inference2(b); |
| case Stream(lambda(`v,`b),`u): |
| bind_pattern_type(v,type_inference2(u)); |
| return type_inference2(b); |
| case typed(null,`tp): |
| return tp; |
| case typed(tagged_union(`n,`u),`tp): |
| type_inference2(u); |
| return tp; |
| case typed(union_value(`u),`tp): |
| type_inference2(u); |
| return tp; |
| case typed(`x,`tp): |
| if (tp.is_variable() && !tp.equals(#<string>) |
| && MRContainer.type_code(tp.toString()) >= 0) { |
| Tree tx = type_inference(x); |
| if (tx.is_variable() && !tx.equals(#<string>) |
| && MRContainer.type_code(tx.toString()) >= 0) |
| return tp; |
| else type_error(e,"Expression "+print_query(x)+" of type "+print_type(tx) |
| +" cannot be coerced to type "+tp); |
| }; |
| Tree tx = type_inference(x); |
| if (!subtype(tx,tp)) |
| type_error(e,"Expression "+print_query(x)+" of type "+print_type(tx) |
| +" cannot be coerced to type "+print_type(tp)); |
| if (unify(tx,tp) == null) // need to coerce x |
| coerce(tx,tp,((Node)e).children); |
| return tp; |
| case tuple(...el): |
| Trees s = #[]; |
| for ( Tree a: el ) |
| s = s.append(type_inference(a)); |
| return #<tuple(...s)>; |
| case call(coerce,`x,`n): |
| return #<`(MRContainer.type_names[(int)n.longValue()])>; |
| case record(...el): |
| Trees s = #[]; |
| Trees attrs = #[]; |
| for ( Tree a: el ) |
| match a { |
| case bind(`v,`b): |
| s = s.append(#<bind(`v,`(type_inference(b)))>); |
| if (attrs.member(v)) |
| type_error(e,"Duplicate record attribute name: "+v+" in "+print_query(e)); |
| attrs = attrs.append(v); |
| }; |
| return #<record(...s)>; |
| case union_tag(`x): |
| return #<int>; |
| case `T(...el): |
| if (!is_collection(T)) |
| fail; |
| if (el.is_empty()) |
| return #<`T(any)>; |
| Trees ts = #[]; |
| for ( Tree t: el ) |
| ts = ts.append(type_inference(t)); |
| Tree maxt = maximum_type(ts); |
| for ( ; el != #[] && ts != #[]; el = el.tail, ts = ts.tail ) |
| if (subtype(ts.head,maxt)) |
| coerce(ts.head,maxt,el); |
| else type_error(e,"Incompatible values in "+T+" construction: "+print_query(e)); |
| return #<`T(`maxt)>; |
| case nth(`a,`n): |
| if (!n.is_long()) |
| type_error(e,"Tuple index must be an integer: "+print_query(e)); |
| int i = (int)n.longValue(); |
| match type_inference2(a) { |
| case tuple(...ts): |
| if (i < 0 || i >= ts.length()) |
| type_error(e,"Tuple index outside bounds: "+print_query(e)); |
| return ts.nth(i); |
| case `S(tuple(...ts)): |
| if (!is_collection(S)) |
| fail; |
| if (i < 0 || i >= ts.length()) |
| type_error(e,"Tuple index outside bounds: "+print_query(e)); |
| return #<`S(`(ts.nth(i)))>; |
| case `tp: |
| type_error(e,"Tuple index must be applied to a tuple: " |
| +print_query(a)+" of type: "+print_type(tp)+" in "+print_query(e)); |
| }; |
| case project(`a,`v): // highly overloaded |
| Tree ta = type_inference(a); |
| match ta { |
| case XML: |
| return #<list(XML)>; |
| case `S(`tp): |
| if (is_collection(S) && (tp.equals(#<XML>) || tp.equals(TopLevel.xml_type))) |
| return #<`S(XML)>; |
| }; |
| if (ta.equals(TopLevel.xml_type)) |
| return #<list(XML)>; |
| match expand(ta) { |
| case record(...ts): |
| for ( Tree t: ts ) |
| match t { |
| case bind(`w,`tp): |
| if (equal_types(w,v)) |
| return tp; |
| }; |
| type_error(e,"Record "+print_query(a)+" does not have a component "+v); |
| case union(...tl): |
| Trees s = #[]; |
| for ( Tree t: tl ) |
| match t { |
| case `c(record(...ts)): |
| for ( Tree tn: ts ) |
| match tn { |
| case bind(`w,`tp): |
| if (equal_types(w,v)) |
| s = s.append(tp); |
| }; |
| case `c(bag(tuple(string,`tv))): |
| s = s.append(tv); |
| }; |
| if (s.length() == 0) |
| type_error(e,"Wrong record projection "+print_query(e) |
| + " over the union "+print_type(ta)); |
| else if (s.length() > 1) |
| type_error(e,"Ambiguous record projection "+print_query(e) |
| + " over the union "+print_type(ta)); |
| return s.head(); |
| case `S(`ttp): |
| if (!is_collection(S)) |
| fail; |
| match expand(ttp) { |
| case record(...ts): |
| for ( Tree t: ts ) |
| match t { |
| case bind(`w,`tp): |
| if (equal_types(w,v)) |
| return #<`S(`tp)>; |
| }; |
| type_error(e,"The record collection "+print_query(a) |
| +" does not have a component "+v); |
| case tuple(string,`tv): |
| return tv; |
| case union(...tl): |
| Trees s = #[]; |
| for ( Tree t: tl ) |
| match t { |
| case `c(record(...ts)): |
| for ( Tree tn: ts ) |
| match tn { |
| case bind(`w,`tp): |
| if (equal_types(w,v)) |
| s = s.append(tp); |
| }; |
| case `c(bag(tuple(string,`tv))): |
| s = s.append(tv); |
| }; |
| if (s.length() == 0) |
| type_error(e,"Wrong record projection "+print_query(e) |
| + " over the union "+print_type(ta)); |
| else if (s.length() > 1) |
| type_error(e,"Ambiguous record projection "+print_query(e) |
| + " over the union "+print_type(ta)); |
| return #<`S(...s)>; |
| }; |
| case `t: |
| type_error(e,"The record projection "+print_query(e) |
| + " cannot apply to the type "+print_type(t)); |
| }; |
| case index(`a,`i): |
| Tree ti = type_inference2(i); |
| match type_inference2(a) { |
| case bag(tuple(`tk,`tv)): |
| if (subtype(ti,tk)) { |
| coerce(ti,tk,((Node)e).children.tail); |
| return tv; |
| } else fail |
| case Bag(tuple(`tk,`tv)): |
| if (subtype(ti,tk)) { |
| coerce(ti,tk,((Node)e).children.tail); |
| return tv; |
| } else fail |
| case list(`tp): |
| if (unify(ti,#<int>) != null) |
| return tp; |
| else type_error(e,"List index must be an integer: "+print_query(e)); |
| case List(`tp): |
| if (unify(ti,#<int>) != null) |
| return tp; |
| else type_error(e,"List index must be an integer: "+print_query(e)); |
| case union(...tl): |
| Trees s = #[]; |
| for ( Tree t: tl ) |
| match expand(t) { |
| case `c(bag(tuple(`tk,`tv))): |
| if (unify(ti,tk) != null) |
| s = s.append(tv); |
| else fail |
| case `c(list(`tp)): |
| if (unify(ti,#<int>) != null) |
| s = s.append(tp); |
| else fail |
| }; |
| if (s.length() == 0) |
| type_error(e,"Wrong indexing "+print_query(e) |
| + " in union "+print_type(#<union(...tl)>)); |
| else if (s.length() > 1) |
| type_error(e,"Ambiguous indexing "+print_query(e) |
| + " in union "+print_type(#<union(...tl)>)); |
| return s.head(); |
| case `tp: type_error(e,"Indexing is not allowed for type "+print_type(tp) |
| +" with index "+print_type(ti)+" in "+print_query(e)); |
| }; |
| case range(`u,`i,`j): |
| if (unify(type_inference2(i),#<int>) == null |
| || unify(type_inference2(j),#<int>) == null) |
| type_error(e,"Range indexes must be integer expressions: "+print_query(e)); |
| match type_inference2(u) { |
| case list(`a): return #<list(`a)>; |
| case List(`a): return #<list(`a)>; |
| }; |
| type_error(e,"Range indexing must be applied to a list: "+print_query(e)); |
| case range(`min,`max): |
| Tree tmin = type_inference(min); |
| Tree tmax = type_inference(max); |
| if (!subtype(tmin,#<long>)) |
| type_error(e,"Expected a long integer for min: "+print_query(min)); |
| else if (unify(tmin,#<long>) == null) // coerce |
| coerce(tmin,#<long>,((Node)e).children); |
| if (!subtype(tmax,#<long>)) |
| type_error(e,"Expected a long integer for max: "+print_query(max)); |
| else if (unify(tmax,#<long>) == null) // coerce |
| coerce(tmax,#<long>,((Node)e).children.tail); |
| return #<list(long)>; |
| case call(gen,`min,`max,`size): |
| return type_inference(#<gen(`min,`max,`size)>); |
| case gen(`min,`max,`size): |
| Tree tmin = type_inference(min); |
| Tree tmax = type_inference(max); |
| Tree tsize = type_inference(size); |
| if (!subtype(tmin,#<long>)) |
| type_error(e,"Expected a long integer for min: "+print_query(min)); |
| else if (unify(tmin,#<long>) == null) // coerce |
| coerce(tmin,#<long>,((Node)e).children); |
| if (!subtype(tmax,#<long>)) |
| type_error(e,"Expected a long integer for max: "+print_query(max)); |
| else if (unify(tmax,#<long>) == null) // coerce |
| coerce(tmax,#<long>,((Node)e).children.tail); |
| if (!subtype(tsize,#<long>)) |
| type_error(e,"Expected a long integer for size: "+print_query(size)); |
| else if (unify(tsize,#<long>) == null) // coerce |
| coerce(tsize,#<long>,((Node)e).children.tail.tail); |
| return #<Bag(long)>; |
| case dataset_size(`x): |
| return #<long>; |
| case groupBy(`u): |
| Tree tp = type_inference2(u); |
| match tp { |
| case `T(tuple(`k,`v)): |
| if (is_collection(T)) |
| return (is_persistent_collection(T)) |
| ? #<Bag(tuple(`k,list(`v)))> |
| : #<bag(tuple(`k,list(`v)))>; |
| }; |
| type_error(e,"Wrong groupBy: "+print_query(e)+" of type "+print_type(tp)); |
| case coGroup(`x,`y): |
| Tree xtp = type_inference2(x); |
| Tree ytp = type_inference2(y); |
| match xtp { |
| case `T(tuple(`kx,`a)): |
| if (!is_collection(T)) |
| type_error(e,"Wrong coGroup left operand: "+print_query(x)); |
| match ytp { |
| case `S(tuple(`ky,`b)): |
| if (!is_collection(S)) |
| type_error(e,"Wrong coGroup right operand: "+print_query(y)); |
| if (unify(kx,ky) == null) |
| type_error(e,"incompatible keys in coGroup: "+print_query(e)); |
| return (is_persistent_collection(T) && is_persistent_collection(S)) |
| ? #<Bag(tuple(`kx,tuple(`T(`a),`S(`b))))> |
| : #<bag(tuple(`kx,tuple(`T(`a),`S(`b))))>; |
| } |
| }; |
| type_error(e,"Wrong coGroup: "+print_query(e)); |
| case orderBy(`u): |
| Tree tp = type_inference2(u); |
| match tp { |
| case `T(tuple(`k,`v)): |
| if (is_collection(T)) |
| return (is_persistent_collection(T)) |
| ? #<List(tuple(`k,list(`v)))> |
| : #<list(tuple(`k,list(`v)))>; |
| }; |
| type_error(e,"Wrong orderBy: "+print_query(e)+" of type "+print_type(tp)); |
| case cmap(lambda(`v,`body),`s): |
| match type_inference2(s) { |
| case `T(`a): |
| if (!is_collection(T)) |
| fail; |
| type_env.insert(v.toString(),a); |
| match type_inference2(body) { |
| case `S(`tp): |
| if (!is_collection(S)) |
| fail; |
| return #<`T(`tp)>; |
| case _: type_error(e,"cmap must return a collection: "+print_query(e)); |
| }; |
| case `t: type_error(e,"cmap must be over a collection: "+print_query(e) |
| +" (found type "+print_type(t)+")"); |
| }; |
| type_error(e,"Wrong cmap: "+print_query(e)); |
| case fold(lambda(`v,`body),`n,`s): |
| match type_inference2(s) { |
| case `T(`a): |
| if (!is_collection(T)) |
| fail; |
| Tree tp = type_inference(n); |
| type_env.insert(v.toString(),#<tuple(`a,tp)>); |
| if (unify(type_inference2(body),tp) == null) |
| type_error(e,"Wrong types in fold: "+print_query(e)); |
| return tp; |
| }; |
| case join(lambda(`v1,`b1),lambda(`v2,`b2),lambda(`vr,`br),`x,`y): |
| match type_inference2(x) { |
| case `T(`a): |
| if (!is_collection(T)) |
| fail; |
| match type_inference2(y) { |
| case `S(`b): |
| if (!is_collection(S)) |
| fail; |
| type_env.insert(v1.toString(),a); |
| type_env.insert(v2.toString(),b); |
| T = transient_collection(T); |
| S = transient_collection(S); |
| type_env.insert(vr.toString(),#<tuple(`T(`a),`S(`b))>); |
| if (unify(type_inference2(b1),type_inference2(b2)) == null) |
| type_error(e,"Incompatible keys in join ("+type_inference2(b1) |
| +" and "+type_inference2(b2)+"): "+print_query(e)); |
| match type_inference(br) { |
| case `S3(`ntp): |
| if (!is_collection(S3)) |
| fail; |
| S3 = persistent_collection(S3); |
| return #<`S3(`ntp)>; |
| }; |
| type_error(e,"The join reducer must return a collection: "+print_query(br)); |
| case _: type_error(e,"The right join input is not a collection: "+print_query(y)); |
| }; |
| case _: type_error(e,"The left join input is not a collection: "+print_query(x)); |
| }; |
| case crossProduct(lambda(`v1,`b1),lambda(`v2,`b2),lambda(`vr,`br),`x,`y): |
| match type_inference2(x) { |
| case `T(`a): |
| if (!is_collection(T)) |
| fail; |
| match type_inference2(y) { |
| case `S(`b): |
| if (!is_collection(S)) |
| fail; |
| type_env.insert(v1.toString(),a); |
| type_env.insert(v2.toString(),b); |
| match type_inference2(b1) { |
| case `S1(`w1): |
| if (!is_collection(S1)) |
| fail; |
| match type_inference2(b2) { |
| case `S2(`w2): |
| if (!is_collection(S2)) |
| fail; |
| type_env.insert(vr.toString(),#<tuple(`w1,`w2)>); |
| match type_inference(br) { |
| case `S3(`ntp): |
| if (!is_collection(S3)) |
| fail; |
| S3 = persistent_collection(S3); |
| return #<`S3(`ntp)>; |
| }; |
| type_error(e,"The cross product reducer must return a collection: "+print_query(br)); |
| case _: type_error(e,"Wrong right mapper in a cross product: "+print_query(b2)); |
| }; |
| case _: type_error(e,"Wrong left mapper in a cross product: "+print_query(b1)); |
| }; |
| case _: type_error(e,"The right cross product input is not a collection: "+print_query(y)); |
| }; |
| case _: type_error(e,"The left cross product input is not a collection: "+print_query(x)); |
| }; |
| case mapReduce(lambda(`vm,`bm),lambda(`vr,`br),`X,_): |
| match type_inference2(X) { |
| case `T(`a): |
| if (!is_collection(T)) |
| fail; |
| type_env.insert(vm.toString(),a); |
| match type_inference2(bm) { |
| case `S(tuple(`k,`b)): |
| if (!is_collection(S)) |
| fail; |
| type_env.insert(vr.toString(),#<tuple(`k,list(`b))>); |
| match type_inference(br) { |
| case `S3(`ntp): |
| if (!is_collection(S3)) |
| fail; |
| if (is_persistent_collection(T)) |
| S3 = persistent_collection(S3); |
| return #<`S3(`ntp)>; |
| }; |
| type_error(e,"The MapReduce reducer must return a collection: "+print_query(br)); |
| case _: type_error(e,"Wrong mapper in mapReduce: "+print_query(bm)); |
| } |
| }; |
| type_error(e,"The MapReduce input is not a collection: "+print_query(X)); |
| case mapReduce2(lambda(`v1,`b1),lambda(`v2,`b2),lambda(`vr,`br),`X,`Y,_): |
| match type_inference2(X) { |
| case `T(`a): |
| if (!is_collection(T)) |
| fail; |
| match type_inference2(Y) { |
| case `S(`b): |
| if (!is_collection(S)) |
| fail; |
| type_env.insert(v1.toString(),a); |
| type_env.insert(v2.toString(),b); |
| match type_inference2(b1) { |
| case `S1(tuple(`k1,`w1)): |
| if (!is_collection(S1)) |
| fail; |
| match type_inference2(b2) { |
| case `S2(tuple(`k2,`w2)): |
| if (!is_collection(S2)) |
| fail; |
| if (unify(k1,k2) == null) |
| type_error(e,"incompatible keys in mapReduce2: "+print_query(e)); |
| S1 = transient_collection(S1); |
| S2 = transient_collection(S2); |
| type_env.insert(vr.toString(),#<tuple(`S1(`w1),`S2(`w2))>); |
| match type_inference(br) { |
| case `S3(`ntp): |
| if (!is_collection(S3)) |
| fail; |
| if (is_persistent_collection(T) && is_persistent_collection(S)) |
| S3 = persistent_collection(S3); |
| return #<`S3(`ntp)>; |
| }; |
| type_error(e,"The MapReduce2 reducer must return a collection: "+print_query(br)); |
| case _: type_error(e,"Wrong right mapper in mapReduce2: "+print_query(b2)); |
| }; |
| case _: type_error(e,"Wrong left mapper in mapReduce2: "+print_query(b1)); |
| }; |
| case _: type_error(e,"The right MapReduce2 input is not a collection: "+print_query(Y)); |
| }; |
| case _: type_error(e,"The left MapReduce2 input is not a collection: "+print_query(X)); |
| }; |
| case Collect(`x): |
| match type_inference2(x) { |
| case Bag(`tp): return #<bag(`tp)>; |
| case List(`tp): return #<list(`tp)>; |
| }; |
| type_error(e,"You can only cache persistent collections: "+e); |
| case aggregate(lambda(`v,`b),`z,`X): |
| match type_inference2(X) { |
| case `T(`a): |
| if (!is_collection(T)) |
| fail; |
| Tree ztp = type_inference2(z); |
| type_env.insert(v.toString(),#<tuple(`ztp,`a)>); |
| if (!subtype(ztp,type_inference2(b))) |
| type_error(e,"Wrong accumulator: "+print_query(e)); |
| return ztp; |
| }; |
| type_error(e,"Aggregation input is not a collection: "+print_query(e)); |
| case repeat(lambda(`p,`b),`s,...ns): |
| if (!ns.is_empty() && unify(type_inference2(ns.head()),#<int>) == null) |
| type_error(e,"The maximum number of steps in repeat must be an integer: " |
| +print_query(ns.head())); |
| Tree tp = type_inference2(s); |
| bind_pattern_type(p,tp); |
| match tp { |
| case `T(`a): |
| if (!is_collection(T)) |
| fail; |
| match type_inference2(b) { |
| case `S(`c): // transitive closure |
| if (!is_collection(S)) |
| fail; |
| if (unify(a,c) == null) |
| fail; |
| ((Node)e).name = #<closure>.toString(); // destructive |
| return #<`T(`a)>; |
| case `S(tuple(`w,`c)): |
| if (!is_collection(S)) |
| fail; |
| if (unify(c,#<bool>) == null) |
| fail; |
| if (unify(a,w) == null) |
| fail; |
| return #<`T(`a)>; |
| case `t: type_error(e,"The repeat body must return a collection of type " |
| +print_type(tp)+" or "+print_type(#<`T(tuple(`a,bool))>) |
| +" (Found type: "+print_type(t)+")"); |
| } |
| }; |
| type_error(e,"The repeat source must return a bag: "+print_query(e)); |
| case closure(lambda(`v,`b),`s,...ns): |
| if (!ns.is_empty() && unify(type_inference2(ns.head()),#<int>) == null) |
| type_error(e,"The maximum number of steps in closure must be an integer: " |
| +print_query(ns.head())); |
| match type_inference2(s) { |
| case `T(`a): |
| if (!is_collection(T)) |
| fail; |
| type_env.insert(v.toString(),#<`T(`a)>); |
| match type_inference2(b) { |
| case `S(`tp): |
| if (!is_collection(S)) |
| fail; |
| if (unify(a,tp) == null) |
| fail; |
| return #<`T(`a)>; |
| case `tp: type_error(e,"The closure body must return a collection of type " |
| +print_type(#<`T(`a)>)+" or "+print_type(#<`T(tuple(`a,bool))>) |
| +" (Found type: "+print_type(tp)+")"); |
| } |
| }; |
| type_error(e,"The closure source must return a bag: "+print_query(e)); |
| case loop(lambda(`p,`b),`s,`n): |
| if (unify(type_inference2(n),#<int>) == null) |
| type_error(e,"The number of steps in loop must be an integer: "+print_query(n)); |
| Tree tp = type_inference2(s); |
| bind_pattern_type(p,tp); |
| Tree btp = type_inference2(b); |
| if (unify(tp,btp) == null) |
| type_error(e,"The type of the repeat body ("+print_type(btp) |
| + ") and the type of the initial value ("+print_type(tp)+") do not match"); |
| return tp; |
| case step(`x): // used in QueryPlan for repeat |
| match type_inference(x) { |
| case `T(`tp): return #<`T(tuple(`tp,bool))>; |
| }; |
| case cstep(`x): // used in QueryPlan for closure |
| return type_inference(x); |
| case provenance(`x,...exprs): // used in Provenance generation |
| match type_inference(x) { |
| case `S(tuple(`tp,_)): |
| if (!is_collection(S)) |
| fail; |
| return #<`S(`tp)>; |
| case tuple(`tp,_): |
| return tp; |
| }; |
| type_error(e,"Wrong provenance injection"); |
| case Lineage(...as): // used in Provenance generation |
| type_inference(#<tuple(...as)>); |
| return #<lineage>; |
| case outerMerge(lambda(`v,`b),`s,`d): |
| Tree ts = type_inference(s); |
| if (unify(type_inference(d),ts) == null) |
| type_error(e,"Wrong outerMerge"); |
| match ts { |
| case `S(tuple(`k,`tp)): |
| if (!is_collection(S)) |
| fail; |
| type_env.insert(v.toString(),#<tuple(`tp,`tp)>); |
| type_inference(b); |
| return ts; |
| }; |
| type_error(e,"Wrong OuterMerge"); |
| case rightOuterMerge(lambda(`v,`b),`s,`d): |
| Tree ts = type_inference(s); |
| if (unify(type_inference(d),ts) == null) |
| type_error(e,"Wrong RightOuterMerge"); |
| match ts { |
| case `S(tuple(`k,`tp)): |
| if (!is_collection(S)) |
| fail; |
| type_env.insert(v.toString(),#<tuple(`tp,`tp)>); |
| type_inference(b); |
| return ts; |
| }; |
| type_error(e,"Wrong rightOuterMerge"); |
| case if(`p,`x,`y): |
| if (unify(type_inference2(p),#<bool>) == null) |
| type_error(e,"Expected a boolean predicate in if-then-else: "+print_query(p)); |
| Tree tx = type_inference2(x); |
| Tree ty = type_inference2(y); |
| Tree rt = unify(tx,ty,((Node)e).children.tail,((Node)e).children.tail.tail); |
| if (rt == null) |
| type_error(e,"Incompatible types in if-then-else: "+print_query(e)); |
| return rt; |
| case call(inv,`x): |
| return type_inference(x); |
| case incr(...s): |
| return type_inference(#<tuple(...s)>); |
| case call(plus,`x,`y): |
| Tree tx = type_inference2(x); |
| Tree ty = type_inference2(y); |
| match tx { |
| case `T(`xt): |
| if (!is_collection(T)) |
| fail; |
| match ty { |
| case `S(`yt): |
| if (!is_collection(S)) |
| fail; |
| Tree rt = unify(tx,ty,((Node)e).children.tail,((Node)e).children.tail.tail); |
| if (rt == null) |
| type_error(e,"Incompatible types in union/append: "+print_type(tx)+" and "+print_type(ty)); |
| return rt; |
| } |
| }; |
| fail |
| case `f(`x,`y): |
| if (! #[union,intersect,except].member(#<`f>)) |
| fail; |
| Tree tx = type_inference2(x); |
| Tree ty = type_inference2(y); |
| match tx { |
| case `T(`t1): |
| if (!is_collection(T)) |
| fail; |
| Tree t = unify(tx,ty,((Node)e).children,((Node)e).children.tail); |
| if (t != null) |
| return t; |
| }; |
| type_error(e,"Incompatible types in "+f+": "+print_type(tx)+" and "+print_type(ty)); |
| case call(member,`x,`y): |
| Tree tx = type_inference2(x); |
| Tree ty = type_inference2(y); |
| match ty { |
| case `T(`t1): |
| if (!is_collection(T)) |
| fail; |
| if (!subtype(tx,t1)) |
| type_error(e,"Incompatible types in member: "+print_type(tx)+" and "+print_type(ty)); |
| coerce(tx,t1,((Node)e).children.tail); |
| return #<bool>; |
| }; |
| case call(elem,`x): |
| Tree tp = type_inference2(x); |
| match tp { |
| case `T(`t): |
| if (is_collection(T)) |
| return t; |
| }; |
| type_error(e,"method elem must be applied to a collection: "+tp); |
| case call(`f,`x,`y): |
| if (! #[eq,neq,lt,leq,gt,geq].member(f)) |
| fail; |
| Tree tx = type_inference2(x); |
| Tree ty = type_inference2(y); |
| if (!subtype(tx,ty) && !subtype(ty,tx)) |
| type_error(e,"Incompatible types in comparison "+f+": " |
| +print_type(tx)+" and "+print_type(ty)); |
| if (unify(tx,ty) != null) |
| return #<bool>; |
| if (subtype(tx,ty)) |
| coerce(tx,ty,((Node)e).children.tail); |
| else if (subtype(ty,tx)) |
| coerce(ty,tx,((Node)e).children.tail.tail); |
| return #<bool>; |
| case call(`f,`s): |
| for ( Tree monoid: monoids ) |
| match monoid { |
| case `aggr(`mtp,`plus,`zero,`unit): |
| if (!aggr.equals(f.toString())) |
| continue; |
| match type_inference2(s) { |
| case `T(`tp): |
| if (!is_collection(T)) |
| type_error(e,"Aggregation must be over collections: "+s); |
| if (unify(mtp,tp) == null) |
| continue; |
| Tree nv = new_var(); |
| type_env.begin_scope(); |
| type_env.insert(nv.toString(),tp); |
| Tree t = type_inference2(#<apply(`unit,`nv)>); |
| Tree tz = type_inference2(zero); |
| type_env.end_scope(); |
| if (unify(t,tz) != null) |
| return t; |
| } |
| }; |
| fail |
| case call(avg,`s): |
| return type_inference(#<call(div,typed(call(sum,`s),double),call(count,`s))>); |
| case call(join_key,`s1,`s2): |
| match type_inference2(s1) { |
| case `T1(tuple(`tp1,_)): |
| match type_inference2(s2) { |
| case `T2(tuple(`tp2,_)): |
| if (is_collection(T1) && is_collection(T2) && unify(tp1,tp2) != null) |
| return tp1; |
| } |
| }; |
| type_error(e,"Expected two collections with the same key in join key: "+e); |
| case reduce(`m,`s): |
| return type_inference2(#<call(`m,`s)>); |
| case trace(`msg,`t,`x): |
| if (unify(type_inference2(msg),#<string>) == null) |
| type_error(e,"Expected a string in the trace message"); |
| Tree tp = type_inference2(x); |
| match tp { |
| case `T(_): |
| if (Config.bsp_mode && is_persistent_collection(T)) |
| type_error(e,"Cannot trace expressions of persistent type in BSP mode: "+x); |
| }; |
| if (t.equals(#<none>)) |
| ((Node)e).children.tail.head = tp; // destructive |
| return tp; |
| case apply(lambda(`v,`b),`arg): |
| type_env.begin_scope(); |
| type_env.insert(v.toString(),type_inference(arg)); |
| Tree tp = type_inference(b); |
| type_env.end_scope(); |
| return tp; |
| case call(`f,...al): |
| Tree macro = global_macros.lookup(f.toString()); |
| if (macro == null) |
| fail; |
| match macro { |
| case macro(params(...pl),`body): |
| Tree b = body; |
| if (pl.length() != al.length()) |
| fail; |
| for ( ; !pl.is_empty(); pl = pl.tail(), al = al.tail() ) |
| b = subst(pl.head(),al.head(),b); |
| return type_inference2(b); |
| }; |
| fail |
| case call(`f,...el): |
| if (!f.is_variable() || global_vars.lookup(f.toString()) != null) |
| fail; |
| Tree ret = data_constructors.lookup(f.toString()); |
| if (ret != null) |
| match ret { |
| case `v(`n,`tp): |
| if (unify(type_inference(make_tuple(el)),tp) != null) |
| return #<`v>; |
| else type_error(e,"Wrong data construction: "+print_query(e)); |
| }; |
| ret = type_env.lookup(f.toString()); |
| if (ret == null) |
| ret = global_type_env.lookup(f.toString()); |
| if (ret != null) |
| match ret { |
| case arrow(`s,`d): |
| Tree tp = type_inference(#<tuple(...el)>); |
| if (!subtype(tp,s)) |
| type_error(e,"The domain of the anonymous function "+print_type(s)+" in "+print_query(e) |
| +" does not match the argument types "+print_type(tp)); |
| if (unify(tp,s) == null) // coerce args |
| match #<tuple(`tp,`s)> { |
| case tuple(tuple(...txs),tuple(...tys)): |
| for ( ; txs != #[]; txs = txs.tail, tys = tys.tail, el = el.tail ) |
| coerce(txs.head,tys.head,el); |
| } |
| return d; |
| case _: type_error(e,"Expected a functional type for "+f+" (found "+print_type(ret)+")"); |
| }; |
| Trees tps = #[]; |
| for ( Tree a: el ) |
| tps = tps.append(type_inference(a)); |
| for ( Tree fnc: functions ) |
| match fnc { |
| case `fn(`otp,...tl): |
| if (!fn.equals(f.toString()) || !subtype(tps,tl)) |
| fail; |
| if (f.equals(#<XMLchildren>)) |
| return #<list(XML)>; |
| else if (f.equals(#<XMLattributes>)) |
| return #<list(string)>; |
| else if (f.equals(#<XMLattribute>) && collection_type(otp)) |
| return #<list(string)>; |
| else return otp; |
| }; |
| type_error(e,"Undefined function "+f+" over arguments of type "+print_type(#<tuple(...tps)>)); |
| case apply(`f,`u): |
| match type_inference2(f) { |
| case arrow(`s,`d): |
| Tree tp = type_inference(u); |
| if (!subtype(tp,s)) |
| type_error(e,"The domain of the anonymous function "+print_type(s)+" in "+print_query(e) |
| +" does not match the argument types "+print_type(tp)); |
| if (unify(tp,s) == null) // coerce args |
| coerce(tp,s,((Node)e).children.tail); |
| return d; |
| case `tp: type_error(e,"Expected a functional type for "+f+" (found "+print_type(tp)+")"); |
| }; |
| case callM(`f,_,...el): |
| return type_inference(#<call(`f,...el)>); |
| case true: return #<bool>; |
| case false: return #<bool>; |
| case null: return #<any>; |
| case `v: |
| if (!v.is_variable()) |
| fail; |
| Tree ret1 = type_env.lookup(v.toString()); |
| Tree ret2 = global_type_env.lookup(v.toString()); |
| if (ret1 == null) |
| if (ret2 == null) { |
| Tree ret = global_vars.lookup(v.toString()); |
| if (ret == null) { |
| String msg = ""; |
| if (!Config.trace && type_env.iterator().hasNext()) { |
| msg += "\nVariable Types:"; |
| for ( String var: type_env ) |
| msg += "\n "+var + ": " + print_type(type_env.lookup(var)); |
| }; |
| type_error(e,"Undefined variable: "+v+msg); |
| } else if (!v.equals(ret)) |
| return type_inference(ret); |
| } else return ret2; |
| else return ret1; |
| case `n: |
| if (n.is_long()) |
| return #<int>; |
| else if (n.is_double()) |
| return #<double>; |
| else if (n.is_string()) |
| return #<string>; |
| }; |
| type_error(e,"Wrong expression: "+print_query(e)); |
| throw new Error(); |
| } |
| |
| /** check the type for inconsistencies and fix the transient/persistent components */ |
| public static Tree normalize_type ( Tree type ) { |
| match type { |
| case record(...bs): |
| Trees as = #[]; |
| Trees vs = #[]; |
| for ( Tree b: bs ) |
| match b { |
| case bind(`v,`tp): |
| if (v.is_variable()) |
| if (vs.member(v)) |
| type_error(type,"Duplicate record attributes: "+print_type(type)); |
| else { |
| vs = vs.append(v); |
| as = as.append(#<bind(`v,`(normalize_type(tp)))>); |
| } |
| else type_error(type,"Expected an attribute name: "+v); |
| case _: type_error(type,"Ill-formed record type: "+print_type(type)); |
| }; |
| return #<record(...as)>; |
| case tuple(...ts): |
| Trees as = #[]; |
| for ( Tree t: ts ) |
| as = as.append(normalize_type(t)); |
| return #<tuple(...as)>; |
| case union(...bs): |
| Trees as = #[]; |
| for ( Tree b: bs ) |
| match b { |
| case `c(`tp): |
| as = as.append(#<`c(`(normalize_type(tp)))>); |
| case _: type_error(type,"Ill-formed union type: "+print_type(type)); |
| }; |
| return #<union(...as)>; |
| case persistent(bag(`tp)): |
| Tree ntp = normalize_type(tp); |
| return #<Bag(`ntp)>; |
| case persistent(list(`tp)): |
| Tree ntp = normalize_type(tp); |
| return #<List(`ntp)>; |
| case `T(`tp): |
| if (is_collection(T)) |
| return #<`T(`(normalize_type(tp)))>; |
| else fail |
| case `tp: |
| if (!tp.is_variable()) |
| fail; |
| if (#[bool,byte,short,int,long,float,double,string].member(tp)) |
| return tp; |
| Tree rt = global_datatype_env.lookup(tp.toString()); |
| if (rt != null) |
| return tp; |
| rt = type_names.lookup(tp.toString()); |
| if (rt != null) |
| return tp; |
| }; |
| type_error(type,"Unrecognized type: "+print_type(type)); |
| return type; |
| } |
| } |
