compiler.cpp

实现内存数据库的源代码

//-< COMPILE.CPP >---------------------------------------------------*--------*
// FastDB                    Version 1.0         (c) 1999  GARRET    *     ?  *
// (Main Memory Database Management System)                          *   /\|  *
//                                                                   *  /  \  *
//                          Created:     20-Nov-98    K.A. Knizhnik  * / [] \ *
//                          Last update: 15-Jan-99    K.A. Knizhnik  * GARRET *
//-------------------------------------------------------------------*--------*
// Conditional expresion compiler
//-------------------------------------------------------------------*--------*

#define INSIDE_FASTDB

#include <ctype.h>
#include "database.h"
#include "array.h"
#include "query.h"
#include "cursor.h"
#include "compiler.h"
#include "symtab.h"

nat1 const dbExprNode::nodeTypes[] = { 
#define DBVM(cop, type, n_opernads, commutative) type,
#include "compiler.d"
0};

nat1 const dbExprNode::nodeOperands[] = { 
#define DBVM(cop, type, n_operands, commutative) n_operands,
#include "compiler.d"
0};

nat1 const dbExprNode::commutativeOperator[] = { 
#define DBVM(cop, type, n_operands, commutative) commutative,
#include "compiler.d"
0};

dbExprNode* dbExprNode::freeNodeList;
dbMutex&    dbExprNode::mutex = *new dbMutex;
bool        dbCompiler::initialized;

dbExprNodeSegment* dbExprNode::segmentList;

dbExprNode::dbExprNode(dbExprNode* node)
{
    memcpy(this, node, sizeof(*this));
    
    for (int i = nodeOperands[cop]; --i >= 0;) { 
	operand[i] = new dbExprNode(operand[i]);
    }
    if (cop == dbvmLoadStringConstant) { 
	char* s = new char[strlen(svalue.str)+1];
	strcpy(s, svalue.str);
	svalue.str = s;
    } 
}

void* dbExprNode::operator new(size_t) 
{ 
    dbCriticalSection cs(mutex);
    dbExprNode* node = freeNodeList;
    if (node == NULL) {
	dbExprNodeSegment* seg = new dbExprNodeSegment;
	seg->next = segmentList;
	segmentList = seg;
	node = (dbExprNode*)seg->buf;
	dbExprNode* freeNode = NULL;
	for (int i = dbExprNodeSegment::allocationQuantum; --i != 0;) { 
	    node->next = freeNode;
	    freeNode = node++;
	} 
	freeNodeList = freeNode;
    } else { 
	freeNodeList = node->next;
    }
    return node;
}

void dbExprNode::cleanup()
{
    dbExprNode* freeNode = NULL;
    for (dbExprNodeSegment* seg = segmentList; seg != NULL; seg = seg->next) 
    { 
	dbExprNode* node = (dbExprNode*)seg->buf;
	for (int i = dbExprNodeSegment::allocationQuantum; --i >= 0;) { 
	    node->next = freeNode;
	    freeNode = node++;
	 }
    }
    freeNodeList = freeNode;
}

dbExprNode::~dbExprNode()
{
    if (cop == dbvmLoadStringConstant) { 
	delete[] svalue.str;
    } else { 
	for (int i = nodeOperands[cop]; --i >= 0; ) { 
	    delete operand[i];
	}
    }
}

int dbCompiler::scan() 
{
    char ch;
    char *p, *q;
    int  i, n, value;
    char buf[maxStrLen+1];


   nextElement:
    if (queryElement == NULL) { 
	return tkn_eof;
    }
    if (queryElement->type != dbQueryElement::qExpression) {
	varType = queryElement->type;
	varPtr = queryElement->ptr;
	varRefTable = queryElement->ref;
	queryElement = queryElement->next;
	return tkn_var;
    } 
    p = q = (char*)queryElement->ptr + currPos;
    
    do { 
	ch = *p++;
	if (ch == '\n') { 
	    offsetWithinStatement = (char*)queryElement->ptr - p;
	    firstPos = 0;
	}
    } while (isspace(byte(ch)));
    currPos += p - q;

    switch (ch) { 
      case '\0':
	if ((queryElement = queryElement->next) == NULL) { 
	    return tkn_eof;
	}
	currPos = 0;
	goto nextElement;
      case '+':
	return tkn_add;
      case '-':
	if (*p == '-') { 
	    // ANSI comments
	    q = p;
	    do { 
		p += 1;
	    } while (*p != '\n' && *p != '\0');
	    currPos += p - q;
	    goto nextElement;
	}
	return tkn_sub;
      case '*':
	return tkn_mul;
      case '/':
	return tkn_div;
      case '.':
	return tkn_dot;
      case ',':
	return tkn_comma;
      case '(':
	return tkn_lpar;
      case ')':
	return tkn_rpar;
      case '[':
	return tkn_lbr;
      case ']':
	return tkn_rbr;
      case ':':
	return tkn_col;
      case '^':
	return tkn_power;
      case '<':
	if (*p == '=') { 
	    currPos += 1;
	    return tkn_le;
	} else if (*p == '>') { 
	    currPos += 1;
	    return tkn_ne;
	}
	return tkn_lt;
      case '>':
	if (*p == '=') { 
	    currPos += 1;
	    return tkn_ge;
	}
	return tkn_gt;
      case '=':
	return tkn_eq;
      case '!':
	if (*p != '=') { 
	    error("Invalid token '!'");
	} 
	currPos += 1;
	return tkn_ne;
      case '|':
	if (*p != '|') { 
	    error("Invalid token '|'");
	} 
	currPos += 1;
	return tkn_add;
      case '\'':
	q = p;
	i = 0; 
	while (true) { 
	    if (*p == '\'') { 
		if (*++p != '\'') { 
		    break;
		}
	    } else if (*p == '\0') { 
		error("Unterminated character constant");
	    }
	    if (i == maxStrLen) { 
		error("String constant too long");
	    }
	    buf[i++] = *p++;
	}
	buf[i++] = '\0';
	currPos += p - q;
	svalue.str = new char[i];
	strcpy(svalue.str, buf);
	svalue.len = i;
	return tkn_sconst;
      case '0': case '1': case '2': case '3': case '4': 
      case '5': case '6': case '7': case '8': case '9':
	value = ch - '0';
	for (q = p; isdigit(*(byte*)p); p++) { 
	    value = value*10 + *p - '0';
	}
	if (*p == '.' || *p == 'e' || *p == 'E') { 
	    if (sscanf(q-1, "%lf%n", &fvalue, &n) != 1) { 
		error("Bad floating point constant");
	    }
	    currPos += n - 1;
	    return tkn_fconst;
	} else if (p - q >= 9) { 
	    if (sscanf(q-1, INT8_FORMAT "%n", &ivalue, &n) != 1) { 
		error("Bad integer constant");
	    }
	    currPos += n - 1;
	    return tkn_iconst;
	} else { 
	    currPos += p - q; 
	    ivalue = value;
	    return tkn_iconst;
	}
      default:
	if (isalpha(byte(ch)) || ch == '$' || ch == '_') { 
	    i = 0;
	    do { 
		if (i == maxStrLen) { 
		    error("Name too long");
		}
		buf[i++] = ch;
		ch = *p++;
	    } while (isalnum(byte(ch)) || ch == '$' || ch == '_');
	    buf[i] = '\0';
	    name = buf;
	    currPos += i - 1;
	} else { 
	    error("Invalid symbol");
	} 
	return dbSymbolTable::add(name, tkn_ident);
   }
}

dbExprNode* dbCompiler::disjunction()
{
    dbExprNode* left = conjunction();
    if (lex == tkn_or) { 
	int pos = currPos;
	dbExprNode* right = disjunction();
	if (left->type == tpInteger && right->type == tpInteger) { 
	    left = new dbExprNode(dbvmOrInt, left, right);
	} else if (left->type == tpBoolean && right->type == tpBoolean) { 
	    left = new dbExprNode(dbvmOrBool, left, right);
	} else { 
	    error("Bad operands for OR operator", pos);
	}
    }
    return left;
}

dbExprNode* dbCompiler::conjunction()
{
    dbExprNode* left = comparison();
    if (lex == tkn_and) { 
	int pos = currPos;
	dbExprNode* right = conjunction();
	if (left->type == tpInteger && right->type == tpInteger) { 
	    left = new dbExprNode(dbvmAndInt, left, right);
	} else if (left->type == tpBoolean && right->type == tpBoolean) { 
	    left = new dbExprNode(dbvmAndBool, left, right);
	} else { 
	    error("Bad operands for AND operator", pos);
	}
    }
    return left;
}

inline dbExprNode* int2real(dbExprNode* expr) 
{
    if (expr->cop == dbvmLoadIntConstant) { 
	expr->fvalue = (real8)expr->ivalue;
	expr->cop = dbvmLoadRealConstant;
	expr->type = tpReal;
    } else { 
	expr = new dbExprNode(dbvmIntToReal, expr);
    }
    return expr;
}

int dbCompiler::compare(dbExprNode* expr, dbExprNode* list)
{
    int n = 1;
    if (list->operand[0] != NULL) { 
	n = compare(expr, list->operand[0]);
	expr = new dbExprNode(expr);
    }
    dbExprNode* elem = list->operand[1];
    int cop = dbvmVoid;
    int rawBinarySize = 0;
    if (expr->type == tpInteger) { 
	if (elem->type == tpReal) { 
	    expr = int2real(expr);
	    cop = dbvmEqReal;
	} else if (elem->type == tpInteger) { 
	    cop = dbvmEqInt;
	}
    } else if (expr->type == tpReal) {
	if (elem->type == tpReal) { 
	    cop = dbvmEqReal;
	} else if (elem->type == tpInteger) { 
	    cop = dbvmEqReal;
	    elem = int2real(elem);
	}
    } else if (expr->type == tpString && elem->type == tpString) {
	cop = dbvmEqString;
    } else if (expr->type == tpReference && elem->type == tpReference) {
	cop = dbvmEqReference;
    } else if (expr->type == tpBoolean && elem->type == tpBoolean) {
	cop = dbvmEqBool;
    } else if (expr->type == tpRawBinary && elem->type == tpRawBinary) {
	cop = dbvmEqBinary;
	if ((expr->cop == dbvmLoadSelfRawBinary || expr->cop == dbvmLoadRawBinary) 
	    && expr->ref.field != NULL)
	{
	    rawBinarySize = expr->ref.field->dbsSize;
	} else if ((elem->cop == dbvmLoadSelfRawBinary || elem->cop == dbvmLoadRawBinary) 
	    && elem->ref.field != NULL)
	{
	    rawBinarySize = elem->ref.field->dbsSize;
	} else { 
	    error("Operations with raw binary types should include at least one record field");
	}
    }
    if (cop == dbvmVoid) { 
	char buf[256];
	sprintf(buf, "Expression %d in right part of IN operator have "
		"incompatible type", n);
	error(buf);
    } else { 
	list->type = tpBoolean;
	if (list->operand[0] != NULL) { 
	    list->operand[1] = new dbExprNode(cop, expr, elem, rawBinarySize);
	    list->cop = dbvmOrBool;
	} else { 
	    list->operand[0] = expr;
	    list->cop = cop;
	    list->offs = rawBinarySize;
	}
    }
    return ++n;
}

dbExprNode* dbCompiler::comparison()
{
    int leftPos = currPos;
    dbExprNode *left, *right;
    left = addition();
    int cop = lex;
    if (cop == tkn_eq || cop == tkn_ne || cop == tkn_gt || cop == tkn_ge
	|| cop == tkn_le || cop == tkn_lt || cop == tkn_between 
	|| cop == tkn_like || cop == tkn_not || cop == tkn_is || cop == tkn_in)
    {
	int rightPos = currPos;
	bool notOp = false;
	if (cop == tkn_not) { 
	    notOp = true;
	    cop = scan();
	    if (cop != tkn_like && cop != tkn_between && cop != tkn_in) { 
		error("LIKE, BETWEEN or IN expected", rightPos);
	    } 
	    rightPos = currPos;
	} else if (cop == tkn_is) {
	    if (left->type != tpReference) { 
		error("IS [NOT] NULL predicate can be applied only to "
		      "references", rightPos);
	    } 
	    rightPos = currPos;
	    if ((cop = scan()) == tkn_null) { 
		left = new dbExprNode(dbvmIsNull, left);
	    } else if (cop == tkn_not) { 
		rightPos = currPos;
		if (scan() == tkn_null) { 
		    left = new dbExprNode(dbvmNotBool, 
					  new dbExprNode(dbvmIsNull, left));
		} else { 
		    error("NULL expected", rightPos);
		}
	    } else { 
		error("[NOT] NULL expected", rightPos);
	    } 
	    lex = scan();
	    return left;
	}	
	right = addition();
	if (cop == tkn_in) { 
	    int type;
	    switch (right->type) {
	      case tpArray:
		type = (right->cop == dbvmLoadVarArray || right->cop == dbvmLoadVarArrayPtr)
		     ? dbField::tpReference 
		     : right->ref.field->components->type;
		if ((left->type == tpBoolean && type == dbField::tpBool) 
		    || (left->type == tpInteger 
			&& (type == dbField::tpInt1 
			    || type == dbField::tpInt2
			    || type == dbField::tpInt4 
			    || type == dbField::tpInt8))
		    || (left->type == tpReal 
			&& (type == dbField::tpReal4
			    || type == dbField::tpReal8))
		    || (left->type == tpString && type == dbField::tpString)
		    || (left->type == tpReference 
			&& type == dbField::tpReference))
		{
		    left = new dbExprNode(dbvmInArrayBool + type, left, right);
		} else {
		    error("Type of selective expression of IN operator doesn't"
			  " match type of the array");
		}
		break;
	      case tpString:
		if (left->type == tpString) { 
		    left = new dbExprNode(dbvmInString, left, right);
		} else { 
		    error("Left operand of IN expression hasn't string type");
		}
		break;
	      case tpList:
		compare(left, right);
		left = right;
		break;
	      default:
		error("List of expressions or array expected", rightPos);
	    }
	} else if (cop == tkn_between) { 
	    int andPos = currPos;
	    if (lex != tkn_and) { 
		error("AND expected");
	    }
	    dbExprNode* right2 = addition();
	    if (left->type == tpReal 
		|| right->type == tpReal || right2->type == tpReal)
	    {
		if (left->type == tpInteger) { 
		    left = int2real(left);
		} else if (left->type != tpReal) { 
		    error("operand of BETWEEN operator should be of "
			  "integer, real or string type", leftPos);
		}