mal_function.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 0.0
@+ Functions
MAL comes with a standard functional abstraction scheme.
Functions are represented by MAL instruction lists, enclosed
by a @sc{function} signature
and @sc{end} statement. The @sc{function}
signature lists the arguments and their types.
The @sc{end} statement marks the end of this sequence. 
Its argument is the function name.

An illustrative example is:
@example
function user.helloWorld(msg:str):str;
    io.print(msg);
	msg:= "done";
    return msg;
end user.hellowWorld;
@end example

The module name designates the collection to which this function
belongs.
All user defined functions are assembled in the module @sc{user}
by default. It may be dropped without affecting the intended semantics.

The functional abstraction scheme comes with several variations:
 @sc{commands}, @sc{patterns}, and @sc{factories}.
They are discussed shortly.
@menu
* Polymorphic Functions ::
* C Functions::
@end menu
@{
@-
The information maintained for each MAL function should both
be geared towards fast execution and to ease symbolic debugging.
@h
#ifndef _MAL_FCN_H
#define _MAL_FCN_H

#include "mal_module.h"
#include "mal_resolve.h"

/* #define DEBUG_MAL_FCN */
/* #define DEBUG_CLONE */

mal_export Symbol   newFunction(str nme,int kind);
mal_export void     renameFunction(str oldmod, str oldfcn,str modnme, str new);
mal_export void	    clearFcn(MalBlkPtr m);
mal_export int      getPC(MalBlkPtr mb, InstrPtr p);

mal_export InstrPtr newCall(Module scope, str fcnname, int kind);
mal_export Symbol cloneFunction(Module scope, Symbol proc, MalBlkPtr mb, InstrPtr p);

mal_export Symbol   getFunctionSymbol(Module scope, InstrPtr p);
mal_export void chkFlow(MalBlkPtr mb);
mal_export void chkDeclarations(MalBlkPtr mb,int reset);
mal_export int getBarrierEnvelop(MalBlkPtr mb);
mal_export int isLoopBarrier(MalBlkPtr mb, int pc);
mal_export int getBlockExit(MalBlkPtr mb,int pc);
mal_export int getBlockBegin(MalBlkPtr mb,int pc);
mal_export void setLifespan(MalBlkPtr mb);
mal_export void debugLifespan(MalBlkPtr mb);

mal_export void printFunction(stream *fd, MalBlkPtr mb, int listing);
mal_export void showFlowGraph(MalBlkPtr mb, MalStkPtr stk, str fname);

#include "mal_exception.h"

#define MAXDEPTH 32
#endif /*  _MAL_FCN_H*/
@-
The MAL function blocks are constructed incrementally while parsing the source.
The function kind determines its semantics. It is taken from the list
FUNCTION, FACTORY, COMMAND, and PATTERN.
@c
#include "mal_config.h"
#include "mal_function.h"
#include "mal_resolve.h"	/* for isPolymorphic() & chkProgram() */
#include "mal_interpreter.h"	/* for showErrors() */
#include "mal_namespace.h"

Symbol newFunction(str nme,int kind){
	Symbol s;
	InstrPtr p;

	s = newSymbol(nme,kind);
	p = newInstruction(NULL,kind);
	setFunctionId(p, nme);  /* name already in namespace */
	setDestVar(p, newVariable(s->def,GDKstrdup(nme),TYPE_any));
	pushInstruction(s->def,p);
	return s;
}
InstrPtr newCall(Module scope, str fcnname, int kind){
	InstrPtr p;
	p= newInstruction(NULL,kind);
	setModuleScope(p, scope);
	setFunctionId(p, putName(fcnname,strlen(fcnname)));
	return p;
}
@-
Optimizers may be interested in the function definition
for obtaining properties. Rather then polution of the
instruction record with a scope reference, we use a lookup function until it
becomes a performance hindrance.
@c
Symbol  getFunctionSymbol(Module scope, InstrPtr p){
	Module m;
	Symbol s;

	for(m= findModule(scope,getModuleId(p)); m; m= m->outer)
		if(idcmp(m->name, getModuleId(p))==0 ) {
				s= m->subscope[(int)(getSubScope(getFunctionId(p)))];
				for(; s; s= s->peer)
				if( getSignature(s)->fcn == p->fcn) return s;
		}
	return 0;
} 
@-
Remame all incarnations of a function.
@c
void renameFunction(str oldmod, str oldfcn, str modnme, str name){
	Module root,scope;
	Symbol s,prev;
	InstrPtr p;
	root= scope= MCgetClient()->nspace;
	while( scope != NULL){
		if( oldmod && strcmp(oldmod, scope->name) ){
			scope= scope->outer;
			continue;
		}
	    s= scope->subscope[(int)(*oldfcn)];
	    prev= NULL;
	    while(s != NULL){
	        if( idcmp(s->name,oldfcn) == 0) break;
	        prev= s;
	        s= s->skip;
	    }
	    if( s) {
	        if( prev == 0){
	            scope->subscope[(int)(*oldfcn)]= s->skip;
	        } else {
	            prev->peer= s->skip;
	        }
	        while(s){
	            prev= s->peer; 
	            s->peer= NULL;
	            s->name= GDKstrdup(name);
	            p= getInstrPtr(s->def,0);
	            setModuleId(p,putName(modnme,strlen(modnme)));
	            setFunctionId(p,putName(name,strlen(name)));
	            insertSymbol(root,s);
	            s= prev;
	        }
	        return;
	    }
	    scope=scope->outer;
	}
}
@- Flow of control
The nesting of (BARRIER, CATCH) and EXIT statements with their associated
flow of control primitives LEAVE, REDO and RAISE should form a valid
hierarchy. Failure to comply is considered a structural error
and leads to flagging the function as erroneous.

Check barrier should ensure that both exit-points of a block for the
variable referenced in 'pp' exists. In addition, we should ensure
proper weaveing of the begin-end pairs. This can simply be checked by
counting the begin/end pairs. It should balance for every block.
Currently, the barrier control variables should be of type bit,
sht, int, or lng. A number zero is interpreted as end of the barrier
block.

To speed-up interpretation of the control statements, we could also
include the program-counter in the instruction record. However, this implies
that any subsequent change to a program, i.e. by the optimizers,
should be followed by a call to recalculate the PC.
For the time being it will be a linear scan.

@c
int getPC(MalBlkPtr mb, InstrPtr p)
{   int i;
	for( i=0;i<mb->stop; i++)
	if( getInstrPtr(mb,i)==p) return i;
	return -1;
}
@-
Checking the control flow structure is done by a single pass over the
MAL program after the program has been type-checked.
It should inspect all BARRIER and CATCH blocks for proper structure.
If the flow is correct and not dependent on an undefined typed instruction
we avoid doing this check any further.
@c
#define DEPTH 128

void chkFlow(MalBlkPtr mb)
{   int i,j,k, v,lastInstruction;
	int  pc[DEPTH];
	int  var[DEPTH];
	InstrPtr stmt[DEPTH];
	int btop=0;
	int retseen=0;
	int fixed=1;    
	InstrPtr p;

	lastInstruction = mb->stop-1;
	for(i= 0; i<mb->stop; i++){
		p= getInstrPtr(mb,i);
		switch( p->barrier){
		case BARRIERsymbol:
		case CATCHsymbol:
			if(btop== DEPTH){
			    showScriptException(mb,i,SYNTAX,
					"Too many nested MAL blocks");
			    mb->errors++;
			    return;
			}
			pc[btop]= i;
			v= var[btop]= getDestVar(p);
			stmt[btop]=p;

			for(j=btop-1;j>=0;j--)
			if( v==var[j]){
			    showScriptException(mb,i,SYNTAX,
					"recursive %s[%d] shields %s[%d]",
						getVarName(mb,v), pc[j],
						getFcnName(mb),pc[i]);
			    mb->errors++;
			    return;
			}

			if( getVarType(mb,v) != TYPE_bit && 
			    getVarType(mb,v) != TYPE_int &&
			    getVarType(mb,v) != TYPE_str && 
			    getVarType(mb,v) != TYPE_lng && 
			    getVarType(mb,v) != TYPE_oid && 
			    getVarType(mb,v) != TYPE_sht && 
			    !isaBatType(getVarType(mb,v)) &&
			    getVarType(mb,v) != TYPE_chr && 
			    getVarType(mb,v) != TYPE_bte && 
			    getVarType(mb,v) != TYPE_wrd 
				){
			    showScriptException(mb,i,TYPE,
					"barrier '%s' should be of type bit, str or number",
					getVarName(mb, v));
					mb->errors++;
			}
			btop++;
			if( p->typechk != TYPE_RESOLVED) fixed =0;
			break;
		case EXITsymbol:
			v= getDestVar(p);
			if( btop>0 && var[btop-1] != v){
			    mb->errors++;
			    showScriptException(mb,i,SYNTAX,
					"exit-label '%s' doesnot match '%s'",
					getVarName(mb,v), getVarName(mb,var[btop-1]));
			}
			if(btop==0){
			    showScriptException(mb,i,SYNTAX,
					"exit-label '%s' without begin-label",
					getVarName(mb,v));
			    mb->errors++;
			    continue;
			}
			/* search the matching block */
			for(j=btop-1;j>=0;j--)
			if( var[j]==v) break;
			if(j>=0) btop= j; else btop--;

			/* retrofit LEAVE/REDO instructions */
			stmt[btop]->jump= i;
			for(k=pc[btop]; k<i; k++){
			    InstrPtr p1= getInstrPtr(mb,k);
			    if( getDestVar(p1)==v ) {
			        /* handle assignments with leave/redo option*/
			        if(p1->barrier== LEAVEsymbol )
			            p1->jump= i;
			        if( p1->barrier==REDOsymbol )
			            p1->jump= pc[btop]+1;
			    }
			}
			if( p->typechk != TYPE_RESOLVED) fixed =0;
			break;
		case LEAVEsymbol:
		case REDOsymbol:
			v= getDestVar(p);
			for(j=btop-1;j>=0;j--)
			if( var[j]==v) break;
			if(j<0){
				str nme= getVarName(mb,v);
			    showScriptException(mb,i,SYNTAX,
					"label '%s' not in guarded block",nme);
			    mb->errors++;
			} else
			if( p->typechk != TYPE_RESOLVED) fixed =0;
			break;
		case YIELDsymbol:
			{ InstrPtr ps= getInstrPtr(mb,0);
			if( ps->token != FACTORYsymbol){
			    showScriptException(mb,i,SYNTAX,"yield misplaced!");
			    mb->errors++;
			} }
		case RETURNsymbol:
			{   InstrPtr ps= getInstrPtr(mb,0);
			    int e;
			    if( ps->retc != p->retc){
			        showScriptException(mb,i,SYNTAX,
						"invalid return target!");
			        mb->errors++;
			    } else
			    if(ps->typechk == TYPE_RESOLVED)
			    for(e=0;e<p->retc; e++){
	                if( resolveType(getArgType(mb,ps,e),getArgType(mb,p,e)) <0 ){
	                    showScriptException(mb,i,TYPE,
							"%s type mismatch at type %d",
	                        (p->barrier==RETURNsymbol?"RETURN":"YIELD"),
			                                getArgType(mb,p,e));
	                    mb->errors++;
	                }
	            }
			    if(ps->typechk != TYPE_RESOLVED) fixed =0;
			}
			retseen = 1;
			break;
	    case ENDsymbol:
			lastInstruction = lastInstruction < mb->stop?i:lastInstruction;
			i= mb->stop;
			break;
	    case RAISEsymbol:
	        break;
		default:
			if( isaSignature(p) ){
				if( p->token == REMsymbol){
					/* do nothing */
				} else if( i) {
					str msg=instruction2str(mb,p,TRUE);
					showScriptException(mb,i,SYNTAX,"signature misplaced\n!%s",msg);
					GDKfree(msg);
					mb->errors++;
				}
			} 
		}
	}
	if( lastInstruction < mb->stop-1 ){
		showScriptException(mb,lastInstruction,SYNTAX,
			"instructions after END");
#ifdef DEBUG_MAL_FCN
		printFunction(GDKout, mb, LIST_MAL_ALL);
#endif
		mb->errors++;
	}
	for(btop--; btop>=0;btop--){
		showScriptException(mb,lastInstruction, SYNTAX,
			"begin '%s' without exit in %s[%d]",
				getVarName(mb,var[btop]),getFcnName(mb),i);
		mb->errors++;
	}
	p= getInstrPtr(mb,0);
	if( !isaSignature(p)){
		showScriptException(mb,0,SYNTAX,"signature missing");
		mb->errors++;
	}
	if( retseen == 0){
		if( getArgType(mb,p,0)!= TYPE_void &&
			(p->token==FUNCTIONsymbol || p->token==FACTORYsymbol)){
			showScriptException(mb,0,SYNTAX,"RETURN missing");
			mb->errors++;
		}
	}
	if( mb->errors == 0 )
		mb->flowfixed = fixed; /* we might not have to come back here */
}
@-
A code may contain temporary names for marking barrier blocks.
Since they are introduced by the compiler, the parser should locate
them itself when encountering the LEAVE,EXIT,REDO.
The starting position is mostly the last statement entered.
Purposely, the nameless envelops searches the name of the last
unclosed block. All others are ignored.
@c
int getBarrierEnvelop(MalBlkPtr mb){
	int pc;
	InstrPtr p;
	for(pc= mb->stop-2 ; pc>=0; pc--){
		p= getInstrPtr(mb,pc);
		if( blockExit(p)){
			int l= p->argv[0];
			for(; pc>=0;pc--){
			    p= getInstrPtr(mb,pc);
			    if( blockStart(p) && p->argv[0]==l) break;
			}
			continue;
		}
		if( blockStart(p) ) return p->argv[0];
	}
	return newTmpVariable(mb,TYPE_any);
}
@}
@-
@node Polymorphic Functions, C Functions, MAL Functions, MAL Functions
@- Polymorphic Functions
Polymorphic functions are characterised by type variables
denoted by @sc{:any} and an optional index.
Each time a polymorphic MAL function is called, the
symbol table is first inspected for the matching strongly typed
version.  If it does not exists, a copy of the MAL program
is generated, whereafter the type
variables are replaced with their concrete types.
The new MAL program is immediately type checked and, if
no errors occured, added to the symbol table.

The generic type variable @sc{:any} designates an unknown type, which may
be filled at type resolution time. Unlike indexed polymorphic type 
arguments, @sc{:any} type arguments match possibly with different 
concrete types.

An example of a parameterised function is shown below:
@example
function user.helloWorld(msg:any_1):any_1;
    io.print(msg);
return user.helloWorld;
@end example
The type variables ensure that the return type equals the
argument type. Type variables can be used at any place
where a type name is permitted. 
Beware that polymorphic typed variables are propagated
throughout the function body. This may invalidate 
type resolutions decisions taken  earlier (See @ref{MAL Type System}).

This version of @sc{helloWorld} can also be used for
other arguments types, i.e. @sc{bit,sht,lng,flt,dbl,...}.
For example, calling @sc{helloWorld(3.14:flt)} echoes
a float value.

@node C Functions, MAL Factories, Polymorphic Functions, MAL Functions
@- C functions
The MAL function body can also be implemented with a C-function.
They are introduced to the MAL type checker by providing their
signature and an @sc{address} qualifier for linkage.

We distinguish both @sc{command} and @sc{pattern} C-function blocks.
They differ in the information accessible at run time. The @sc{command}
variant calls the underlying C-function, passing pointers to the arguments
on the MAL runtime stack. The @sc{pattern} command is passed pointers
to the MAL definition block, the runtime stack, and the instruction itself.
It can be used to analyse the types of the arguments directly.

For example, the definitions below link the kernel routine @sc{BKCinsert_bun}
with the function @sc{bat.insert()}. 
It does not fully specify the result type.
The @sc{io.print()} pattern applies to any BAT argument list, 
provided they match on the head column type.
Such a polymorphic type list may only be used in the context of
a pattern.
@example
command bat.insert(b:bat[:any_1,:any_2], ht:any_1, tt:any_2)
	:bat[:any_1,:any_2]
address BKCinsert_bun;

pattern io.print(b1:bat[:any_1,:any]...):int
address IOtable;
@end example

@{
The internal representation of the MAL functions is rather traditional,
using C-structure to collect the necessary information.
Moreover, we assume that MAL functions are relatively small, up to
a few hundred of instructions. This assumption makes us to rely on
linear scans as it comes to locating information of interest.

Patterns should not be cloned, because the alternative interpretations
are handled by the underlying code fragments.
@c
void replaceTypeVar(MalBlkPtr mb, InstrPtr p, int v, malType t){
	int j,i,x,y;
#ifdef DEBUG_MAL_FCN
	stream_printf(GDKout,"replace type _%d by type %s\n",v,
		getTypeName(t));
#endif
	for(j=0; j<mb->stop; j++){
	    p= getInstrPtr(mb,j);
#ifdef DEBUG_MAL_FCN
		printInstruction(GDKout,mb,p,LIST_MAL_ALL);
#endif 
	if( p->polymorphic)
	for(i=0;i<p->argc; i++)
	if( isPolymorphic(x= getArgType(mb,p,i))) {
		if( isaBatType(x)){
			int head,tail;
			int hx,tx;