mal_resolve.mx

一个内存数据库的源代码这是服务器端还有客户端

@' The contents of this file are subject to the MonetDB Public License
@' Version 1.1 (the "License"); you may not use this file except in
@' compliance with the License. You may obtain a copy of the License at
@' http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' Software distributed under the License is distributed on an "AS IS"
@' basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
@' License for the specific language governing rights and limitations
@' under the License.
@'
@' The Original Code is the MonetDB Database System.
@'
@' The Initial Developer of the Original Code is CWI.
@' Portions created by CWI are Copyright (C) 1997-2007 CWI.
@' All Rights Reserved.

@a M. Kersten
@v 1.0
@+ Type Resolution
Given the interpretative nature of many of the MAL instructions,
when and where type resolution takes place is a critical design issue.
Performing it too late, i.e. at each instruction call, leads to 
performance problems if we derive the same information over and over again.
However, many built-in operators have polymorphic typed signatures, 
so we cannot escape it altogether.

Consider the small illustrative MAL program:
@example
function sample(nme:str, val:any_1):bit;
   c := 2 * 3;
   b := bbp.bind(nme);  #find a BAT
   h := algebra.select(b,val,val);
   t := aggr.count(h);
   x := io.print(t);
   y := io.print(val);
end sample;
@end example
@-
The function definition is polymorphic typed on the 2nd argument,
it becomes a concrete type upon invocation. The system could attempt
a type check, but quickly runs into assumptions that generally do not hold.
The first assignment can be type checked during parsing
and a symbolic optimizer could even evaluate the expression once. 
Looking up a BAT in the buffer pool leads to
an element @sc{:bat[@emph{ht,tt}]} where @emph{ht} and @emph{tt}
are runtime dependent types, which means that the selection operation can
not be type-checked immediately. It is an example of an embedded
polypmorphic statement, which requires intervention of the user/optimizer
to make the type explicit before the type resolver becomes active.
The operation @sc{count} can be checked, if it is given a BAT argument. 
This assumes that we can infer that 'h' is indeed a BAT, which requires 
assurance that @sc{algebra.select} produces one. However, there are
no rules to avoid addition of new operators, or to differentiate among
different implementations based on the argument types.
Since @sc{print(t)} contains an undetermined typed
argument we should postpone typechecking as well.
The last print statement can be checked upon function invocation.

Life becomes really complex if the body contains a loop with 
variable types. For then we also have to keep track of the original
state of the function. Or alternatively, type checking should consider
the runtime stack rather than the function definition itself.

These examples give little room to achieve our prime objective, i.e.
a fast and early type resolution scheme. Any non-polymorphic function
can be type checked and marked type-safe upon completion.
Type checking polymorphic functions are post-poned until a concrete
type instance is known. It leads to a clone, which can be type checked
and is entered into the symbol table.
@{
The type resolution status is marked in each instruction.
TYPE_RESOLVED implies that the type of the instruction is fully
resolved, it is marked TYPE_DYNAMIC otherwise.

@h
#ifndef _MAL_RESOLVE_H
#define _MAL_RESOLVE_H

#include "mal_exception.h"
#include "mal_function.h"
#include "mal_exception.h"

/*
#define DEBUG_MAL_RESOLVE 1 
*/
#define MAXTYPEVAR  10

mal_export void chkProgram(Module s, MalBlkPtr mb);
mal_export void chkInstruction(Module s, MalBlkPtr mb, InstrPtr p);
mal_export void chkTypes(Module s, MalBlkPtr mb);
mal_export void typeChecker(Module scope, MalBlkPtr mb, InstrPtr p, int silent);
mal_export InstrPtr dynamicTypeChecker(Module scope,MalBlkPtr mb, MalStkPtr stk, InstrPtr p);
mal_export int fcnBinder(Module scope, MalBlkPtr mb, InstrPtr p);

extern void typeMismatch(MalBlkPtr mb, InstrPtr p, int lhs, int rhs,int silent);
extern str traceFcnName;
mal_export void expandMacro(MalBlkPtr mb, InstrPtr p, MalBlkPtr mc);

#endif /*  _MAL_RESOLVE_H*/
@- Function call resolution
Search the first definition of the operator in the current module
and check the parameter types.
For a polymorphic MAL function we make a fully instantiated clone.
It will be prepended to the symbol list as it is more restrictive.
This effectively overloads the MAL procedure.

@c
#include "mal_config.h"
#include "mal_resolve.h"
#include "mal_namespace.h"

malType getPolyType(malType t, int *polytype);
int updateTypeMap(int formal, int actual, int polytype[MAXTYPEVAR]);
int typeKind(MalBlkPtr mb, InstrPtr p, int i);

#define MAXMALARG 256

str traceFcnName= "____";
int tracefcn;
int polyVector[MAXTYPEVAR];
void polyInit(){
	int i;
	for(i=0;i<MAXTYPEVAR;i++) polyVector[i]= TYPE_any;
}

malType findFunctionType(Module scope, MalBlkPtr mb, InstrPtr p,int silent){
	Module m;
	Symbol s;
	InstrPtr sig;
	int i,k, unmatched = 0, s1;
	int foundbutwrong=0;
	int polytype[MAXTYPEVAR];
	int *returntype;
@-
Within a module find the subscope to locate the element in its list
of symbols. A skiplist is used to speed up the search for the
definition of the function.

For the implementation we should be aware that over 90% of the
functions in the kernel have just a few arguments and a single
return value.
A point of concern is that polymorphic arithmetic operations
lead to an explosion in the symbol table. This increase the
loop to find a candidate.

Consider to collect the argument type into a separate structure, because
it will be looked up multiple types to resolve the instruction.[todo]
Simplify polytype using a map into the concrete argument table.
@c
	m= scope;
	s= m->subscope[(int)(getSubScope(getFunctionId(p)))];
	if( s == 0) return -1;
	while(s != NULL){   /* single scope element check */
	if( getFunctionId(p) != s->name  ){
		s= s->skip; continue;
	}
@-
Perform a strong type-check on the actual arguments. If it turns
out to be a polymorphic MAL function, we have to clone it. 
Provided the actual/formal parameters are compliant throughout
the function call.

Also look out for variable argument lists. This means that we
have to keep two iterators, one for the caller (i) and one for
the callee (k). Since a variable argument only occurs as the last one,
we simple avoid an increment when running out of formal arguments.

A call of the form (X1,..., Xi) := f(Y1,....,Yn) can be matched against
the function signature (B1,...,Bk):= f(A1,...,Am) where i==k , n<=m
and type(Ai)=type(Yi). Furthermore, the variables Xi obtain their type
from Bi (or type(Bi)==type(Xi)).
@c
	sig = getSignature(s); 
	unmatched = 0;

#ifdef DEBUG_MAL_RESOLVE
	if(tracefcn) {
	stream_printf(GDKout,"-->resolving\n");
	printInstruction(GDKout,mb,p,LIST_MAL_ALL);
	stream_printf(GDKout,"++> test against signature\n");
	printInstruction(GDKout,s->def,getSignature(s),LIST_MAL_ALL);
	stream_printf(GDKout," %s \n", sig->polymorphic?"polymorphic":"");
	}
#endif
@-
The simple case could be taken care of separately to speedup processing
However, it turned out not to make a big difference.
The first time we encounter a polymorphic argument in the
signature.
Subsequently, the polymorphic arguments update this table
and check for any type mismatches that might occur.
There are at most 2 type variables involved per argument
due to the limited type nesting permitted.
Note, each function returns at least one value.
@c
	if( sig->polymorphic ){
	int limit = sig->polymorphic;
	if( ! (sig->argc== p->argc ||
		(sig->argc<p->argc && sig->varargs & (VARARGS | VARRETS) )) 
	){
		s= s->peer; continue;
	}
	if( sig->retc != p->retc) {
		s= s->peer;
		continue;
	}
/*  if(polyVector[0]==0) polyInit();
	memcpy(polytype,polyVector, 2*sig->argc*sizeof(int)); */

	for(k=0; k< limit; k++) polytype[k] = TYPE_any;
@-
Most polymorphic functions don;t have a variable argument
list. So we save some instructions factoring this caise out.
@c
	for(i=p->retc; i<sig->argc; i++){
		int actual = getArgType(mb,p,i);
		int formal = getArgType(s->def,sig,i);
@-
Take care of variable argument lists. 
They are allowed as the last in the signature only.
Furthermore, for patterns if the formal type is 'any' then all remaining arguments 
are acceptable and detailed type analysis becomes part of the pattern 
implementation.
In all other cases the type should apply to all remaining arguments.
@c
		if( formal == actual)
			continue;
		if( isPolyType(formal) && getVar(mb,getArg(p,i))->props){
			/* printf("perform union type check\n");*/
		}
		if( updateTypeMap(formal, actual, polytype)){
			unmatched= i; 
		   break;
		}
		formal= getPolyType(formal,polytype);
@-
Collect the polymorphic types and resolve them.
If it fails, we know this isn;t the function we are
looking for.
@c
		if( resolveType( formal,actual) == -1 ){
			unmatched= i;
			break;
		}
	}
@-
The last argument type could be a polymorphic variable list. It should only be
allowed for patterns, where it can deal with the stack.
We also know that at least one element of the argument list
has been resolved and its type information is consolidated in the
type administration. 
@c
	  if( sig->varargs ) {
		if( sig->token != PATTERNsymbol )
			unmatched = i;
		else
		for(k=i-1; i<p->argc; i++){
			int actual = getArgType(mb,p,i);
			int formal = getArgType(s->def,sig,k);
			formal= getPolyType(formal,polytype);
			if( formal == actual || formal == TYPE_any) 
				continue;
			if( resolveType( formal,actual) == -1 ){
				unmatched= i;
				break;
			}
		}
	  }
   } else {
@-
We have to check the argument types to determine a
possible match for the non-polymorphic case.
@c
		if( sig->argc != p->argc ||
			sig->retc != p->retc) {
			s= s->peer;
			continue;
		}
		for(i=p->retc;i<p->argc;i++){
			int actual = getArgType(mb,p,i);
			int formal = getArgType(s->def,sig,i);
			if(formal!=actual ){
#ifdef DEBUG_MAL_RESOLVE
			stream_printf(GDKout,"unmatched %d formal %s actual %s\n",
				i, getTypeName(formal), getTypeName(actual));
#endif
				unmatched= i;
				break;
			}
		}
	}
@-
It is possible that you may have to coerce the value to another type.
We assume that coercions are explicit at the MAL
level. (e.g. var2:= var0:int). This avoids repeated type analysis
just before you execute a function.
An optimizer may at a later stage automatically insert such coercion requests.
@c
#ifdef DEBUG_MAL_RESOLVE
	if(tracefcn) {
		 stream_printf(GDKout,"finished %s.%s unmatched=%d polymorphic=%d %d\n",
			getModuleId(sig), getFunctionId(sig), unmatched, sig->polymorphic,p==sig);
		if( sig->polymorphic){
			int l;
			for(l=0;l<2*p->argc;l++) 
			if( polytype[l] != TYPE_any)
			stream_printf(GDKout,"poly %d %s\n",l,getTypeName(polytype[l]));
		}
		stream_printf(GDKout,"-->resolving\n");
		printInstruction(GDKout,mb,p,LIST_MAL_ALL);
		stream_printf(GDKout,"++> test against signature\n");
		printInstruction(GDKout,s->def,getSignature(s),LIST_MAL_ALL);
		stream_printf(GDKout,"\nmismatch unmatched %d test %s poly %s\n",
			unmatched, getTypeName(getArgType(mb,p,unmatched)),
			getTypeName(getArgType(s->def,sig,unmatched)));
	}
#endif
	if( unmatched) { s= s->peer; continue; }
@-
At this stage we know all arguments are type compatible with the
signature. 
We should assure that also the target variables have the proper types
or can inherit them from the signature. The result type vector should be
build separately first, because we may encounter an error later on.

If any of the arguments refer to a constraint type, any_x, then
the resulting type can not be determined.
@c
	s1 = 0;
	returntype= (int*) alloca(p->retc * sizeof(int));
	if( sig->polymorphic)
	for(i=0; i < p->retc; i++){
		int actual = getArgType(mb,p,i);
		int formal = getArgType(s->def,sig,i);

		updateTypeMap(formal, actual, polytype);
		s1= getPolyType(formal, polytype);

		returntype[i]= resolveType(s1,actual);
		if( returntype[i]== -1 ){
			s1= -1;
			break;
		}
	} else 
	/* check for non-polymorphic return */
	for(i=0; i < p->retc; i++){
		int actual = getArgType(mb,p,i);
		int formal = getArgType(s->def,sig,i);

		if( actual== formal)
			returntype[i]= actual;
		else {
			returntype[i]= resolveType(formal,actual);
			if( returntype[i]== -1 ){
				s1= -1;
				break;
			}
		}
	}
	if(s1<0 ){
		/* if(getSignature(s)->token !=PATTERNsymbol) foundbutwrong++;*/
		s= s->peer; continue;
	}
@-
If the return types are correct, copy them in place. 
Beware that signatures should be left untouched, which
means that we may not overwrite any formal argument.
Using the knowledge dat the arguments occupy the header
of the symbol stack, it is easy to filter such errors.
Also mark all variables that are subject to garbage control.
Beware, this is not yet effectuated in the interpreter.
@c
	p->typechk= TYPE_RESOLVED;
	for(i=0;i<p->retc;i++) {
		int ts= returntype[i];
		if( !isFixed(mb,getArg(p,i)) && ts>=0) {
			setVarType(mb, getArg(p,i),ts);
			setFixed(mb, getArg(p,i));
		}
		@:prepostProcess(ts,i,mb)@
	}
@-
 signatures are handled by the caller
	if( p == getSignature(s)){
printf("handle signature prepost\n");
	for(i=p->retc;i<p->argc;i++) {
		int ts= getArgType(mb,p,i);
		@:prepostProcess(ts,i,mb)@
	}
}
@-
It may happen that an argument was still untyped and as a result of
the polymorphism matching became strongly typed. This should be
reflected in the symbol table. 
@c
	s1= returntype[0];  /* for those interested */
	foundbutwrong = 0;
@-
If the call refers to a polymorphic function, we
clone it to arrive at a bounded instance. Polymorphic patterns and
commands are responsible for type resolution themselves.
Note that cloning pre-supposes that the function being cloned
does not contain errors detected earlier in the process,
nor does it contain polymorphic actual arguments.
@c
	if( sig->polymorphic){ 
		int cnt=0;
		for(k=i=p->retc;i<p->argc;i++){
			int actual = getArgType(mb,p,i);
			if( isAnyExpression(actual)) cnt++;
		}
		if(cnt==0 && s->kind!= COMMANDsymbol && s->kind!=PATTERNsymbol ){
			s = cloneFunction(scope, s, mb,p);
			if( s->def->errors) return -3;
		}
	}
@-
We found the proper function. Copy some properties. In particuler,
determine the calling strategy, i.e. FCNcall, CMDcall, FACcall, PATcall
This piece of code may be shared by the separate binder
@= bindFunction
	if( p->token == ASSIGNsymbol){
		switch(getSignature(s)->token){
		case COMMANDsymbol: 
			p->token = CMDcall; 
			p->fcn = getSignature(s)->fcn;
			if( p->fcn == 0) {
				p->typechk= TYPE_UNKNOWN;
				mb->errors++;
				return -3;
			}
			break;
		case PATTERNsymbol: 
			p->token = PATcall; 
			p->fcn = getSignature(s)->fcn;
			break;
		case FACTORYsymbol:
			p->token = FACcall; 
			p->fcn = getSignature(s)->fcn;
			break;
		case FUNCTIONsymbol: 
			p->token = FCNcall; 
			if( getSignature(s)->fcn)
				p->fcn = getSignature(s)->fcn;
			break;
		default: {
			showScriptException(mb, getPC(mb, p), MAL, 
					"MALresolve: unexpected token type");
			mb->errors++;
			return -3;
		}
		} /* retarded indenting */
		p->blk = s->def;
	}
@-
@c
	@:bindFunction@
@-
Since we now know the storage type of the receiving variable, we can
set the garbagge collection flag.