--- a/src/Expression.cc Sun Mar 30 21:35:06 2014 +0300
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,651 +0,0 @@
-#include "Expression.h"
-#include "DataBuffer.h"
-#include "Lexer.h"
-
-struct OperatorInfo
-{
- ETokenType token;
- int priority;
- int numoperands;
- DataHeader header;
-};
-
-static const OperatorInfo g_Operators[] =
-{
- {TK_ExclamationMark, 0, 1, DH_NegateLogical, },
- {TK_Minus, 0, 1, DH_UnaryMinus, },
- {TK_Multiply, 10, 2, DH_Multiply, },
- {TK_Divide, 10, 2, DH_Divide, },
- {TK_Modulus, 10, 2, DH_Modulus, },
- {TK_Plus, 20, 2, DH_Add, },
- {TK_Minus, 20, 2, DH_Subtract, },
- {TK_LeftShift, 30, 2, DH_LeftShift, },
- {TK_RightShift, 30, 2, DH_RightShift, },
- {TK_Lesser, 40, 2, DH_LessThan, },
- {TK_Greater, 40, 2, DH_GreaterThan, },
- {TK_AtLeast, 40, 2, DH_AtLeast, },
- {TK_AtMost, 40, 2, DH_AtMost, },
- {TK_Equals, 50, 2, DH_Equals },
- {TK_NotEquals, 50, 2, DH_NotEquals },
- {TK_Amperstand, 60, 2, DH_AndBitwise },
- {TK_Caret, 70, 2, DH_EorBitwise },
- {TK_Bar, 80, 2, DH_OrBitwise },
- {TK_DoubleAmperstand, 90, 2, DH_AndLogical },
- {TK_DoubleBar, 100, 2, DH_OrLogical },
- {TK_QuestionMark, 110, 3, (DataHeader) 0 },
-};
-
-// =============================================================================
-//
-Expression::Expression (BotscriptParser* parser, Lexer* lx, DataType reqtype) :
- m_parser (parser),
- m_lexer (lx),
- m_type (reqtype)
-{
- ExpressionSymbol* sym;
-
- while ((sym = parseSymbol()) != null)
- m_symbols << sym;
-
- // If we were unable to get any expression symbols, something's wonky with
- // the script. Report an error. mBadTokenText is set to the token that
- // ParseSymbol ends at when it returns false.
- if (m_symbols.isEmpty())
- error ("unknown identifier '%1'", m_badTokenText);
-
- adjustOperators();
- verify();
- evaluate();
-}
-
-// =============================================================================
-//
-Expression::~Expression()
-{
- for (ExpressionSymbol* sym : m_symbols)
- delete sym;
-}
-
-// =============================================================================
-//
-// Try to parse an expression symbol (i.e. an OPER_erator or OPER_erand or a colon)
-// from the lexer.
-//
-ExpressionSymbol* Expression::parseSymbol()
-{
- int pos = m_lexer->position();
- ExpressionValue* op = null;
-
- if (m_lexer->next (TK_Colon))
- return new ExpressionColon;
-
- // Check for OPER_erator
- for (const OperatorInfo& op : g_Operators)
- if (m_lexer->next (op.token))
- return new ExpressionOperator ((ExpressionOperatorType) (&op - &g_Operators[0]));
-
- // Check sub-expression
- if (m_lexer->next (TK_ParenStart))
- {
- Expression expr (m_parser, m_lexer, m_type);
- m_lexer->mustGetNext (TK_ParenEnd);
- return expr.getResult()->clone();
- }
-
- op = new ExpressionValue (m_type);
-
- // Check function
- if (CommandInfo* comm = findCommandByName (m_lexer->peekNextString()))
- {
- m_lexer->skip();
-
- if (m_type != TYPE_Unknown && comm->returnvalue != m_type)
- error ("%1 returns an incompatible data type", comm->name);
-
- op->setBuffer (m_parser->parseCommand (comm));
- return op;
- }
-
- // Check for variables
- if (m_lexer->next (TK_DollarSign))
- {
- m_lexer->mustGetNext (TK_Symbol);
- Variable* var = m_parser->findVariable (getTokenString());
-
- if (var == null)
- error ("unknown variable %1", getTokenString());
-
- if (var->type != m_type)
- error ("expression requires %1, variable $%2 is of type %3",
- dataTypeName (m_type), var->name, dataTypeName (var->type));
-
- if (var->isarray)
- {
- m_lexer->mustGetNext (TK_BracketStart);
- Expression expr (m_parser, m_lexer, TYPE_Int);
- expr.getResult()->convertToBuffer();
- DataBuffer* buf = expr.getResult()->buffer()->clone();
- buf->writeDWord (DH_PushGlobalArray);
- buf->writeDWord (var->index);
- op->setBuffer (buf);
- m_lexer->mustGetNext (TK_BracketEnd);
- }
- elif (var->writelevel == WRITE_Constexpr)
- op->setValue (var->value);
- else
- {
- DataBuffer* buf = new DataBuffer (8);
-
- if (var->IsGlobal())
- buf->writeDWord (DH_PushGlobalVar);
- else
- buf->writeDWord (DH_PushLocalVar);
-
- buf->writeDWord (var->index);
- op->setBuffer (buf);
- }
-
- return op;
- }
-
- // Check for literal
- switch (m_type)
- {
- case TYPE_Void:
- case TYPE_Unknown:
- {
- error ("unknown identifier `%1` (expected keyword, function or variable)", getTokenString());
- break;
- }
-
- case TYPE_Bool:
- {
- if (m_lexer->next (TK_True) || m_lexer->next (TK_False))
- {
- ETokenType tt = m_lexer->tokenType();
- op->setValue (tt == TK_True ? 1 : 0);
- return op;
- }
- }
-
- case TYPE_Int:
- {
- if (m_lexer->next (TK_Number))
- {
- op->setValue (getTokenString().toLong());
- return op;
- }
- }
-
- case TYPE_String:
- {
- if (m_lexer->next (TK_String))
- {
- op->setValue (getStringTableIndex (getTokenString()));
- return op;
- }
- }
- }
-
- m_badTokenText = m_lexer->token()->text;
- m_lexer->setPosition (pos);
- delete op;
- return null;
-}
-
-// =============================================================================
-//
-// The symbol parsing process only does token-based checking for OPER_erators.
-// Thus ALL minus OPER_erators are actually unary minuses simply because both
-// have TK_Minus as their token and the unary minus is prior to the binary minus
-// in the OPER_erator table. Now that we have all symbols present, we can
-// correct cases like this.
-//
-void Expression::adjustOperators()
-{
- for (auto it = m_symbols.begin() + 1; it != m_symbols.end(); ++it)
- {
- if ((*it)->type() != EXPRSYM_Operator)
- continue;
-
- ExpressionOperator* op = static_cast<ExpressionOperator*> (*it);
-
- // Unary minus with a value as the previous symbol cannot really be
- // unary; replace with binary minus.
- if (op->id() == OPER_UnaryMinus && (*(it - 1))->type() == EXPRSYM_Value)
- op->setID (OPER_Subtraction);
- }
-}
-
-// =============================================================================
-//
-// Verifies a single value. Helper function for Expression::verify.
-//
-void Expression::tryVerifyValue (bool* verified, SymbolList::Iterator it)
-{
- // If it's an unary OPER_erator we skip to its value. The actual OPER_erator will
- // be verified separately.
- if ((*it)->type() == EXPRSYM_Operator &&
- g_Operators[static_cast<ExpressionOperator*> (*it)->id()].numoperands == 1)
- {
- ++it;
- }
-
- int i = it - m_symbols.begin();
-
- // Ensure it's an actual value
- if ((*it)->type() != EXPRSYM_Value)
- error ("malformed expression (symbol #%1 is not a value)", i);
-
- verified[i] = true;
-}
-
-// =============================================================================
-//
-// Ensures the expression is valid and well-formed and not OMGWTFBBQ. Throws an
-// error if this is not the case.
-//
-void Expression::verify()
-{
- if (m_symbols.size() == 1)
- {
- if (m_symbols[0]->type() != EXPRSYM_Value)
- error ("bad expression");
-
- return;
- }
-
- if (m_type == TYPE_String)
- error ("Cannot perform OPER_erations on strings");
-
- bool* verified = new bool[m_symbols.size()];
- memset (verified, 0, m_symbols.size() * sizeof (decltype (*verified)));
- const auto last = m_symbols.end() - 1;
- const auto first = m_symbols.begin();
-
- for (auto it = m_symbols.begin(); it != m_symbols.end(); ++it)
- {
- int i = (it - first);
-
- if ((*it)->type() != EXPRSYM_Operator)
- continue;
-
- ExpressionOperator* op = static_cast<ExpressionOperator*> (*it);
- int numoperands = g_Operators[op->id()].numoperands;
-
- switch (numoperands)
- {
- case 1:
- {
- // Ensure that:
- // - unary OPER_erator is not the last symbol
- // - unary OPER_erator is succeeded by a value symbol
- // - neither symbol overlaps with something already verified
- tryVerifyValue (verified, it + 1);
-
- if (it == last || verified[i] == true)
- error ("malformed expression");
-
- verified[i] = true;
- break;
- }
-
- case 2:
- {
- // Ensure that:
- // - binary OPER_erator is not the first or last symbol
- // - is preceded and succeeded by values
- // - none of the three tokens are already verified
- //
- // Basically similar logic as above.
- if (it == first || it == last || verified[i] == true)
- error ("malformed expression");
-
- tryVerifyValue (verified, it + 1);
- tryVerifyValue (verified, it - 1);
- verified[i] = true;
- break;
- }
-
- case 3:
- {
- // Ternary OPER_erator case. This goes a bit nuts.
- // This time we have the following:
- //
- // (VALUE) ? (VALUE) : (VALUE)
- // ^
- // --------/ we are here
- //
- // Check that the:
- // - questionmark OPER_erator is not misplaced (first or last)
- // - the value behind the OPER_erator (-1) is valid
- // - the value after the OPER_erator (+1) is valid
- // - the value after the colon (+3) is valid
- // - none of the five tokens are verified
- //
- tryVerifyValue (verified, it - 1);
- tryVerifyValue (verified, it + 1);
- tryVerifyValue (verified, it + 3);
-
- if (it == first ||
- it >= m_symbols.end() - 3 ||
- verified[i] == true ||
- verified[i + 2] == true ||
- (*(it + 2))->type() != EXPRSYM_Colon)
- {
- error ("malformed expression");
- }
-
- verified[i] = true;
- verified[i + 2] = true;
- break;
- }
-
- default:
- error ("WTF OPER_erator with %1 OPER_erands", numoperands);
- }
- }
-
- for (int i = 0; i < m_symbols.size(); ++i)
- if (verified[i] == false)
- error ("malformed expression: expr symbol #%1 is was left unverified", i);
-
- delete verified;
-}
-
-
-// =============================================================================
-//
-// Which operator to evaluate?
-//
-Expression::SymbolList::Iterator Expression::findPrioritizedOperator()
-{
- SymbolList::Iterator best = m_symbols.end();
- int bestpriority = __INT_MAX__;
-
- for (SymbolList::Iterator it = m_symbols.begin(); it != m_symbols.end(); ++it)
- {
- if ((*it)->type() != EXPRSYM_Operator)
- continue;
-
- ExpressionOperator* op = static_cast<ExpressionOperator*> (*it);
- const OperatorInfo* info = &g_Operators[op->id()];
-
- if (info->priority < bestpriority)
- {
- best = it;
- bestpriority = info->priority;
- }
- }
-
- return best;
-}
-
-// =============================================================================
-//
-// Process the given OPER_erator and values into a new value.
-//
-ExpressionValue* Expression::evaluateOperator (const ExpressionOperator* op,
- const List<ExpressionValue*>& values)
-{
- const OperatorInfo* info = &g_Operators[op->id()];
- bool isconstexpr = true;
- assert (values.size() == info->numoperands);
-
- for (ExpressionValue* val : values)
- {
- if (val->isConstexpr() == false)
- {
- isconstexpr = false;
- break;
- }
- }
-
- // If not all of the values are constant expressions, none of them shall be.
- if (isconstexpr == false)
- for (ExpressionValue* val : values)
- val->convertToBuffer();
-
- ExpressionValue* newval = new ExpressionValue (m_type);
-
- if (isconstexpr == false)
- {
- // This is not a constant expression so we'll have to use databuffers
- // to convey the expression to bytecode. Actual value cannot be evaluated
- // until Zandronum processes it at run-time.
- newval->setBuffer (new DataBuffer);
-
- if (op->id() == OPER_Ternary)
- {
- // There isn't a dataheader for ternary OPER_erator. Instead, we use DH_IfNotGoto
- // to create an "if-block" inside an expression.
- // Behold, big block of writing madness! :P
- //
- DataBuffer* buf = newval->buffer();
- DataBuffer* b0 = values[0]->buffer();
- DataBuffer* b1 = values[1]->buffer();
- DataBuffer* b2 = values[2]->buffer();
- ByteMark* mark1 = buf->addMark (""); // start of "else" case
- ByteMark* mark2 = buf->addMark (""); // end of expression
- buf->mergeAndDestroy (b0);
- buf->writeDWord (DH_IfNotGoto); // if the first OPER_erand (condition)
- buf->addReference (mark1); // didn't eval true, jump into mark1
- buf->mergeAndDestroy (b1); // otherwise, perform second OPER_erand (true case)
- buf->writeDWord (DH_Goto); // afterwards, jump to the end, which is
- buf->addReference (mark2); // marked by mark2.
- buf->adjustMark (mark1); // move mark1 at the end of the true case
- buf->mergeAndDestroy (b2); // perform third OPER_erand (false case)
- buf->adjustMark (mark2); // move the ending mark2 here
-
- for (int i = 0; i < 3; ++i)
- values[i]->setBuffer (null);
- }
- else
- {
- // Generic case: write all arguments and apply the OPER_erator's
- // data header.
- for (ExpressionValue* val : values)
- {
- newval->buffer()->mergeAndDestroy (val->buffer());
-
- // Null the pointer out so that the value's destructor will not
- // attempt to double-free it.
- val->setBuffer (null);
- }
-
- newval->buffer()->writeDWord (info->header);
- }
- }
- else
- {
- // We have a constant expression. We know all the values involved and
- // can thus compute the result of this expression on compile-time.
- List<int> nums;
- int a;
-
- for (ExpressionValue* val : values)
- nums << val->value();
-
- switch (op->id())
- {
- case OPER_Addition: a = nums[0] + nums[1]; break;
- case OPER_Subtraction: a = nums[0] - nums[1]; break;
- case OPER_Multiplication: a = nums[0] * nums[1]; break;
- case OPER_UnaryMinus: a = -nums[0]; break;
- case OPER_NegateLogical: a = !nums[0]; break;
- case OPER_LeftShift: a = nums[0] << nums[1]; break;
- case OPER_RightShift: a = nums[0] >> nums[1]; break;
- case OPER_CompareLesser: a = (nums[0] < nums[1]) ? 1 : 0; break;
- case OPER_CompareGreater: a = (nums[0] > nums[1]) ? 1 : 0; break;
- case OPER_CompareAtLeast: a = (nums[0] <= nums[1]) ? 1 : 0; break;
- case OPER_CompareAtMost: a = (nums[0] >= nums[1]) ? 1 : 0; break;
- case OPER_CompareEquals: a = (nums[0] == nums[1]) ? 1 : 0; break;
- case OPER_CompareNotEquals: a = (nums[0] != nums[1]) ? 1 : 0; break;
- case OPER_BitwiseAnd: a = nums[0] & nums[1]; break;
- case OPER_BitwiseOr: a = nums[0] | nums[1]; break;
- case OPER_BitwiseXOr: a = nums[0] ^ nums[1]; break;
- case OPER_LogicalAnd: a = (nums[0] && nums[1]) ? 1 : 0; break;
- case OPER_LogicalOr: a = (nums[0] || nums[1]) ? 1 : 0; break;
- case OPER_Ternary: a = (nums[0] != 0) ? nums[1] : nums[2]; break;
-
- case OPER_Division:
- {
- if (nums[1] == 0)
- error ("division by zero in constant expression");
-
- a = nums[0] / nums[1];
- break;
- }
-
- case OPER_Modulus:
- {
- if (nums[1] == 0)
- error ("modulus by zero in constant expression");
-
- a = nums[0] % nums[1];
- break;
- }
- }
-
- newval->setValue (a);
- }
-
- // The new value has been generated. We don't need the old stuff anymore.
- for (ExpressionValue* val : values)
- delete val;
-
- delete op;
- return newval;
-}
-
-// =============================================================================
-//
-ExpressionValue* Expression::evaluate()
-{
- SymbolList::Iterator it;
-
- while ((it = findPrioritizedOperator()) != m_symbols.end())
- {
- int i = it - m_symbols.begin();
- List<SymbolList::Iterator> OPER_erands;
- ExpressionOperator* op = static_cast<ExpressionOperator*> (*it);
- const OperatorInfo* info = &g_Operators[op->id()];
- int lower, upper; // Boundaries of area to replace
-
- switch (info->numoperands)
- {
- case 1:
- {
- lower = i;
- upper = i + 1;
- OPER_erands << it + 1;
- break;
- }
-
- case 2:
- {
- lower = i - 1;
- upper = i + 1;
- OPER_erands << it - 1
- << it + 1;
- break;
- }
-
- case 3:
- {
- lower = i - 1;
- upper = i + 3;
- OPER_erands << it - 1
- << it + 1
- << it + 3;
- break;
- }
-
- default:
- assert (false);
- }
-
- List<ExpressionValue*> values;
-
- for (auto it : OPER_erands)
- values << static_cast<ExpressionValue*> (*it);
-
- // Note: @op and all of @values are invalid after this call.
- ExpressionValue* newvalue = evaluateOperator (op, values);
-
- for (int i = upper; i >= lower; --i)
- m_symbols.removeAt (i);
-
- m_symbols.insert (lower, newvalue);
- }
-
- assert (m_symbols.size() == 1 && m_symbols.first()->type() == EXPRSYM_Value);
- ExpressionValue* val = static_cast<ExpressionValue*> (m_symbols.first());
- return val;
-}
-
-// =============================================================================
-//
-ExpressionValue* Expression::getResult()
-{
- return static_cast<ExpressionValue*> (m_symbols.first());
-}
-
-// =============================================================================
-//
-String Expression::getTokenString()
-{
- return m_lexer->token()->text;
-}
-
-// =============================================================================
-//
-ExpressionOperator::ExpressionOperator (ExpressionOperatorType id) :
- ExpressionSymbol (EXPRSYM_Operator),
- m_id (id) {}
-
-// =============================================================================
-//
-ExpressionValue::ExpressionValue (DataType valuetype) :
- ExpressionSymbol (EXPRSYM_Value),
- m_buffer (null),
- m_valueType (valuetype) {}
-
-// =============================================================================
-//
-ExpressionValue::~ExpressionValue()
-{
- delete m_buffer;
-}
-
-// =============================================================================
-//
-void ExpressionValue::convertToBuffer()
-{
- if (isConstexpr() == false)
- return;
-
- setBuffer (new DataBuffer);
-
- switch (m_valueType)
- {
- case TYPE_Bool:
- case TYPE_Int:
- buffer()->writeDWord (DH_PushNumber);
- buffer()->writeDWord (abs (value()));
-
- if (value() < 0)
- buffer()->writeDWord (DH_UnaryMinus);
- break;
-
- case TYPE_String:
- buffer()->writeDWord (DH_PushStringIndex);
- buffer()->writeDWord (value());
- break;
-
- case TYPE_Void:
- case TYPE_Unknown:
- assert (false);
- break;
- }
-}