Mercurial > botc / file comparison

comparison: src/Expression.cc

src/Expression.cc

changeset 119
bdf8d46c145f
parent 118
e3361cf7cbf4
child 120
5ea0faefa82a
equal deleted inserted replaced
118:e3361cf7cbf4 119:bdf8d46c145f
1 #include "Expression.h"
2 #include "DataBuffer.h"
3 #include "Lexer.h"
4
5 struct OperatorInfo
6 {
7 ETokenType token;
8 int priority;
9 int numoperands;
10 DataHeader header;
11 };
12
13 static const OperatorInfo g_Operators[] =
14 {
15 {TK_ExclamationMark, 0, 1, DH_NegateLogical, },
16 {TK_Minus, 0, 1, DH_UnaryMinus, },
17 {TK_Multiply, 10, 2, DH_Multiply, },
18 {TK_Divide, 10, 2, DH_Divide, },
19 {TK_Modulus, 10, 2, DH_Modulus, },
20 {TK_Plus, 20, 2, DH_Add, },
21 {TK_Minus, 20, 2, DH_Subtract, },
22 {TK_LeftShift, 30, 2, DH_LeftShift, },
23 {TK_RightShift, 30, 2, DH_RightShift, },
24 {TK_Lesser, 40, 2, DH_LessThan, },
25 {TK_Greater, 40, 2, DH_GreaterThan, },
26 {TK_AtLeast, 40, 2, DH_AtLeast, },
27 {TK_AtMost, 40, 2, DH_AtMost, },
28 {TK_Equals, 50, 2, DH_Equals },
29 {TK_NotEquals, 50, 2, DH_NotEquals },
30 {TK_Amperstand, 60, 2, DH_AndBitwise },
31 {TK_Caret, 70, 2, DH_EorBitwise },
32 {TK_Bar, 80, 2, DH_OrBitwise },
33 {TK_DoubleAmperstand, 90, 2, DH_AndLogical },
34 {TK_DoubleBar, 100, 2, DH_OrLogical },
35 {TK_QuestionMark, 110, 3, (DataHeader) 0 },
36 };
37
38 // =============================================================================
39 //
40 Expression::Expression (BotscriptParser* parser, Lexer* lx, DataType reqtype) :
41 m_parser (parser),
42 m_lexer (lx),
43 m_type (reqtype)
44 {
45 ExpressionSymbol* sym;
46
47 while ((sym = parseSymbol()) != null)
48 m_symbols << sym;
49
50 // If we were unable to get any expression symbols, something's wonky with
51 // the script. Report an error. mBadTokenText is set to the token that
52 // ParseSymbol ends at when it returns false.
53 if (m_symbols.isEmpty())
54 error ("unknown identifier '%1'", m_badTokenText);
55
56 adjustOperators();
57 verify();
58 evaluate();
59 }
60
61 // =============================================================================
62 //
63 Expression::~Expression()
64 {
65 for (ExpressionSymbol* sym : m_symbols)
66 delete sym;
67 }
68
69 // =============================================================================
70 //
71 // Try to parse an expression symbol (i.e. an OPER_erator or OPER_erand or a colon)
72 // from the lexer.
73 //
74 ExpressionSymbol* Expression::parseSymbol()
75 {
76 int pos = m_lexer->position();
77 ExpressionValue* op = null;
78
79 if (m_lexer->next (TK_Colon))
80 return new ExpressionColon;
81
82 // Check for OPER_erator
83 for (const OperatorInfo& op : g_Operators)
84 if (m_lexer->next (op.token))
85 return new ExpressionOperator ((ExpressionOperatorType) (&op - &g_Operators[0]));
86
87 // Check sub-expression
88 if (m_lexer->next (TK_ParenStart))
89 {
90 Expression expr (m_parser, m_lexer, m_type);
91 m_lexer->mustGetNext (TK_ParenEnd);
92 return expr.getResult()->clone();
93 }
94
95 op = new ExpressionValue (m_type);
96
97 // Check function
98 if (CommandInfo* comm = findCommandByName (m_lexer->peekNextString()))
99 {
100 m_lexer->skip();
101
102 if (m_type != TYPE_Unknown && comm->returnvalue != m_type)
103 error ("%1 returns an incompatible data type", comm->name);
104
105 op->setBuffer (m_parser->parseCommand (comm));
106 return op;
107 }
108
109 // Check for variables
110 if (m_lexer->next (TK_DollarSign))
111 {
112 m_lexer->mustGetNext (TK_Symbol);
113 Variable* var = m_parser->findVariable (getTokenString());
114
115 if (var == null)
116 error ("unknown variable %1", getTokenString());
117
118 if (var->type != m_type)
119 error ("expression requires %1, variable $%2 is of type %3",
120 dataTypeName (m_type), var->name, dataTypeName (var->type));
121
122 if (var->isarray)
123 {
124 m_lexer->mustGetNext (TK_BracketStart);
125 Expression expr (m_parser, m_lexer, TYPE_Int);
126 expr.getResult()->convertToBuffer();
127 DataBuffer* buf = expr.getResult()->buffer()->clone();
128 buf->writeDWord (DH_PushGlobalArray);
129 buf->writeDWord (var->index);
130 op->setBuffer (buf);
131 m_lexer->mustGetNext (TK_BracketEnd);
132 }
133 elif (var->writelevel == WRITE_Constexpr)
134 op->setValue (var->value);
135 else
136 {
137 DataBuffer* buf = new DataBuffer (8);
138
139 if (var->IsGlobal())
140 buf->writeDWord (DH_PushGlobalVar);
141 else
142 buf->writeDWord (DH_PushLocalVar);
143
144 buf->writeDWord (var->index);
145 op->setBuffer (buf);
146 }
147
148 return op;
149 }
150
151 // Check for literal
152 switch (m_type)
153 {
154 case TYPE_Void:
155 case TYPE_Unknown:
156 {
157 error ("unknown identifier `%1` (expected keyword, function or variable)", getTokenString());
158 break;
159 }
160
161 case TYPE_Bool:
162 {
163 if (m_lexer->next (TK_True) || m_lexer->next (TK_False))
164 {
165 ETokenType tt = m_lexer->tokenType();
166 op->setValue (tt == TK_True ? 1 : 0);
167 return op;
168 }
169 }
170
171 case TYPE_Int:
172 {
173 if (m_lexer->next (TK_Number))
174 {
175 op->setValue (getTokenString().toLong());
176 return op;
177 }
178 }
179
180 case TYPE_String:
181 {
182 if (m_lexer->next (TK_String))
183 {
184 op->setValue (getStringTableIndex (getTokenString()));
185 return op;
186 }
187 }
188 }
189
190 m_badTokenText = m_lexer->token()->text;
191 m_lexer->setPosition (pos);
192 delete op;
193 return null;
194 }
195
196 // =============================================================================
197 //
198 // The symbol parsing process only does token-based checking for OPER_erators.
199 // Thus ALL minus OPER_erators are actually unary minuses simply because both
200 // have TK_Minus as their token and the unary minus is prior to the binary minus
201 // in the OPER_erator table. Now that we have all symbols present, we can
202 // correct cases like this.
203 //
204 void Expression::adjustOperators()
205 {
206 for (auto it = m_symbols.begin() + 1; it != m_symbols.end(); ++it)
207 {
208 if ((*it)->type() != EXPRSYM_Operator)
209 continue;
210
211 ExpressionOperator* op = static_cast<ExpressionOperator*> (*it);
212
213 // Unary minus with a value as the previous symbol cannot really be
214 // unary; replace with binary minus.
215 if (op->id() == OPER_UnaryMinus && (*(it - 1))->type() == EXPRSYM_Value)
216 op->setID (OPER_Subtraction);
217 }
218 }
219
220 // =============================================================================
221 //
222 // Verifies a single value. Helper function for Expression::verify.
223 //
224 void Expression::tryVerifyValue (bool* verified, SymbolList::Iterator it)
225 {
226 // If it's an unary OPER_erator we skip to its value. The actual OPER_erator will
227 // be verified separately.
228 if ((*it)->type() == EXPRSYM_Operator &&
229 g_Operators[static_cast<ExpressionOperator*> (*it)->id()].numoperands == 1)
230 {
231 ++it;
232 }
233
234 int i = it - m_symbols.begin();
235
236 // Ensure it's an actual value
237 if ((*it)->type() != EXPRSYM_Value)
238 error ("malformed expression (symbol #%1 is not a value)", i);
239
240 verified[i] = true;
241 }
242
243 // =============================================================================
244 //
245 // Ensures the expression is valid and well-formed and not OMGWTFBBQ. Throws an
246 // error if this is not the case.
247 //
248 void Expression::verify()
249 {
250 if (m_symbols.size() == 1)
251 {
252 if (m_symbols[0]->type() != EXPRSYM_Value)
253 error ("bad expression");
254
255 return;
256 }
257
258 if (m_type == TYPE_String)
259 error ("Cannot perform OPER_erations on strings");
260
261 bool* verified = new bool[m_symbols.size()];
262 memset (verified, 0, m_symbols.size() * sizeof (decltype (*verified)));
263 const auto last = m_symbols.end() - 1;
264 const auto first = m_symbols.begin();
265
266 for (auto it = m_symbols.begin(); it != m_symbols.end(); ++it)
267 {
268 int i = (it - first);
269
270 if ((*it)->type() != EXPRSYM_Operator)
271 continue;
272
273 ExpressionOperator* op = static_cast<ExpressionOperator*> (*it);
274 int numoperands = g_Operators[op->id()].numoperands;
275
276 switch (numoperands)
277 {
278 case 1:
279 {
280 // Ensure that:
281 // - unary OPER_erator is not the last symbol
282 // - unary OPER_erator is succeeded by a value symbol
283 // - neither symbol overlaps with something already verified
284 tryVerifyValue (verified, it + 1);
285
286 if (it == last || verified[i] == true)
287 error ("malformed expression");
288
289 verified[i] = true;
290 break;
291 }
292
293 case 2:
294 {
295 // Ensure that:
296 // - binary OPER_erator is not the first or last symbol
297 // - is preceded and succeeded by values
298 // - none of the three tokens are already verified
299 //
300 // Basically similar logic as above.
301 if (it == first || it == last || verified[i] == true)
302 error ("malformed expression");
303
304 tryVerifyValue (verified, it + 1);
305 tryVerifyValue (verified, it - 1);
306 verified[i] = true;
307 break;
308 }
309
310 case 3:
311 {
312 // Ternary OPER_erator case. This goes a bit nuts.
313 // This time we have the following:
314 //
315 // (VALUE) ? (VALUE) : (VALUE)
316 // ^
317 // --------/ we are here
318 //
319 // Check that the:
320 // - questionmark OPER_erator is not misplaced (first or last)
321 // - the value behind the OPER_erator (-1) is valid
322 // - the value after the OPER_erator (+1) is valid
323 // - the value after the colon (+3) is valid
324 // - none of the five tokens are verified
325 //
326 tryVerifyValue (verified, it - 1);
327 tryVerifyValue (verified, it + 1);
328 tryVerifyValue (verified, it + 3);
329
330 if (it == first ||
331 it >= m_symbols.end() - 3 ||
332 verified[i] == true ||
333 verified[i + 2] == true ||
334 (*(it + 2))->type() != EXPRSYM_Colon)
335 {
336 error ("malformed expression");
337 }
338
339 verified[i] = true;
340 verified[i + 2] = true;
341 break;
342 }
343
344 default:
345 error ("WTF OPER_erator with %1 OPER_erands", numoperands);
346 }
347 }
348
349 for (int i = 0; i < m_symbols.size(); ++i)
350 if (verified[i] == false)
351 error ("malformed expression: expr symbol #%1 is was left unverified", i);
352
353 delete verified;
354 }
355
356
357 // =============================================================================
358 //
359 // Which operator to evaluate?
360 //
361 Expression::SymbolList::Iterator Expression::findPrioritizedOperator()
362 {
363 SymbolList::Iterator best = m_symbols.end();
364 int bestpriority = __INT_MAX__;
365
366 for (SymbolList::Iterator it = m_symbols.begin(); it != m_symbols.end(); ++it)
367 {
368 if ((*it)->type() != EXPRSYM_Operator)
369 continue;
370
371 ExpressionOperator* op = static_cast<ExpressionOperator*> (*it);
372 const OperatorInfo* info = &g_Operators[op->id()];
373
374 if (info->priority < bestpriority)
375 {
376 best = it;
377 bestpriority = info->priority;
378 }
379 }
380
381 return best;
382 }
383
384 // =============================================================================
385 //
386 // Process the given OPER_erator and values into a new value.
387 //
388 ExpressionValue* Expression::evaluateOperator (const ExpressionOperator* op,
389 const List<ExpressionValue*>& values)
390 {
391 const OperatorInfo* info = &g_Operators[op->id()];
392 bool isconstexpr = true;
393 assert (values.size() == info->numoperands);
394
395 for (ExpressionValue* val : values)
396 {
397 if (val->isConstexpr() == false)
398 {
399 isconstexpr = false;
400 break;
401 }
402 }
403
404 // If not all of the values are constant expressions, none of them shall be.
405 if (isconstexpr == false)
406 for (ExpressionValue* val : values)
407 val->convertToBuffer();
408
409 ExpressionValue* newval = new ExpressionValue (m_type);
410
411 if (isconstexpr == false)
412 {
413 // This is not a constant expression so we'll have to use databuffers
414 // to convey the expression to bytecode. Actual value cannot be evaluated
415 // until Zandronum processes it at run-time.
416 newval->setBuffer (new DataBuffer);
417
418 if (op->id() == OPER_Ternary)
419 {
420 // There isn't a dataheader for ternary OPER_erator. Instead, we use DH_IfNotGoto
421 // to create an "if-block" inside an expression.
422 // Behold, big block of writing madness! :P
423 //
424 DataBuffer* buf = newval->buffer();
425 DataBuffer* b0 = values[0]->buffer();
426 DataBuffer* b1 = values[1]->buffer();
427 DataBuffer* b2 = values[2]->buffer();
428 ByteMark* mark1 = buf->addMark (""); // start of "else" case
429 ByteMark* mark2 = buf->addMark (""); // end of expression
430 buf->mergeAndDestroy (b0);
431 buf->writeDWord (DH_IfNotGoto); // if the first OPER_erand (condition)
432 buf->addReference (mark1); // didn't eval true, jump into mark1
433 buf->mergeAndDestroy (b1); // otherwise, perform second OPER_erand (true case)
434 buf->writeDWord (DH_Goto); // afterwards, jump to the end, which is
435 buf->addReference (mark2); // marked by mark2.
436 buf->adjustMark (mark1); // move mark1 at the end of the true case
437 buf->mergeAndDestroy (b2); // perform third OPER_erand (false case)
438 buf->adjustMark (mark2); // move the ending mark2 here
439
440 for (int i = 0; i < 3; ++i)
441 values[i]->setBuffer (null);
442 }
443 else
444 {
445 // Generic case: write all arguments and apply the OPER_erator's
446 // data header.
447 for (ExpressionValue* val : values)
448 {
449 newval->buffer()->mergeAndDestroy (val->buffer());
450
451 // Null the pointer out so that the value's destructor will not
452 // attempt to double-free it.
453 val->setBuffer (null);
454 }
455
456 newval->buffer()->writeDWord (info->header);
457 }
458 }
459 else
460 {
461 // We have a constant expression. We know all the values involved and
462 // can thus compute the result of this expression on compile-time.
463 List<int> nums;
464 int a;
465
466 for (ExpressionValue* val : values)
467 nums << val->value();
468
469 switch (op->id())
470 {
471 case OPER_Addition: a = nums[0] + nums[1]; break;
472 case OPER_Subtraction: a = nums[0] - nums[1]; break;
473 case OPER_Multiplication: a = nums[0] * nums[1]; break;
474 case OPER_UnaryMinus: a = -nums[0]; break;
475 case OPER_NegateLogical: a = !nums[0]; break;
476 case OPER_LeftShift: a = nums[0] << nums[1]; break;
477 case OPER_RightShift: a = nums[0] >> nums[1]; break;
478 case OPER_CompareLesser: a = (nums[0] < nums[1]) ? 1 : 0; break;
479 case OPER_CompareGreater: a = (nums[0] > nums[1]) ? 1 : 0; break;
480 case OPER_CompareAtLeast: a = (nums[0] <= nums[1]) ? 1 : 0; break;
481 case OPER_CompareAtMost: a = (nums[0] >= nums[1]) ? 1 : 0; break;
482 case OPER_CompareEquals: a = (nums[0] == nums[1]) ? 1 : 0; break;
483 case OPER_CompareNotEquals: a = (nums[0] != nums[1]) ? 1 : 0; break;
484 case OPER_BitwiseAnd: a = nums[0] & nums[1]; break;
485 case OPER_BitwiseOr: a = nums[0] | nums[1]; break;
486 case OPER_BitwiseXOr: a = nums[0] ^ nums[1]; break;
487 case OPER_LogicalAnd: a = (nums[0] && nums[1]) ? 1 : 0; break;
488 case OPER_LogicalOr: a = (nums[0] || nums[1]) ? 1 : 0; break;
489 case OPER_Ternary: a = (nums[0] != 0) ? nums[1] : nums[2]; break;
490
491 case OPER_Division:
492 {
493 if (nums[1] == 0)
494 error ("division by zero in constant expression");
495
496 a = nums[0] / nums[1];
497 break;
498 }
499
500 case OPER_Modulus:
501 {
502 if (nums[1] == 0)
503 error ("modulus by zero in constant expression");
504
505 a = nums[0] % nums[1];
506 break;
507 }
508 }
509
510 newval->setValue (a);
511 }
512
513 // The new value has been generated. We don't need the old stuff anymore.
514 for (ExpressionValue* val : values)
515 delete val;
516
517 delete op;
518 return newval;
519 }
520
521 // =============================================================================
522 //
523 ExpressionValue* Expression::evaluate()
524 {
525 SymbolList::Iterator it;
526
527 while ((it = findPrioritizedOperator()) != m_symbols.end())
528 {
529 int i = it - m_symbols.begin();
530 List<SymbolList::Iterator> OPER_erands;
531 ExpressionOperator* op = static_cast<ExpressionOperator*> (*it);
532 const OperatorInfo* info = &g_Operators[op->id()];
533 int lower, upper; // Boundaries of area to replace
534
535 switch (info->numoperands)
536 {
537 case 1:
538 {
539 lower = i;
540 upper = i + 1;
541 OPER_erands << it + 1;
542 break;
543 }
544
545 case 2:
546 {
547 lower = i - 1;
548 upper = i + 1;
549 OPER_erands << it - 1
550 << it + 1;
551 break;
552 }
553
554 case 3:
555 {
556 lower = i - 1;
557 upper = i + 3;
558 OPER_erands << it - 1
559 << it + 1
560 << it + 3;
561 break;
562 }
563
564 default:
565 assert (false);
566 }
567
568 List<ExpressionValue*> values;
569
570 for (auto it : OPER_erands)
571 values << static_cast<ExpressionValue*> (*it);
572
573 // Note: @op and all of @values are invalid after this call.
574 ExpressionValue* newvalue = evaluateOperator (op, values);
575
576 for (int i = upper; i >= lower; --i)
577 m_symbols.removeAt (i);
578
579 m_symbols.insert (lower, newvalue);
580 }
581
582 assert (m_symbols.size() == 1 && m_symbols.first()->type() == EXPRSYM_Value);
583 ExpressionValue* val = static_cast<ExpressionValue*> (m_symbols.first());
584 return val;
585 }
586
587 // =============================================================================
588 //
589 ExpressionValue* Expression::getResult()
590 {
591 return static_cast<ExpressionValue*> (m_symbols.first());
592 }
593
594 // =============================================================================
595 //
596 String Expression::getTokenString()
597 {
598 return m_lexer->token()->text;
599 }
600
601 // =============================================================================
602 //
603 ExpressionOperator::ExpressionOperator (ExpressionOperatorType id) :
604 ExpressionSymbol (EXPRSYM_Operator),
605 m_id (id) {}
606
607 // =============================================================================
608 //
609 ExpressionValue::ExpressionValue (DataType valuetype) :
610 ExpressionSymbol (EXPRSYM_Value),
611 m_buffer (null),
612 m_valueType (valuetype) {}
613
614 // =============================================================================
615 //
616 ExpressionValue::~ExpressionValue()
617 {
618 delete m_buffer;
619 }
620
621 // =============================================================================
622 //
623 void ExpressionValue::convertToBuffer()
624 {
625 if (isConstexpr() == false)
626 return;
627
628 setBuffer (new DataBuffer);
629
630 switch (m_valueType)
631 {
632 case TYPE_Bool:
633 case TYPE_Int:
634 buffer()->writeDWord (DH_PushNumber);
635 buffer()->writeDWord (abs (value()));
636
637 if (value() < 0)
638 buffer()->writeDWord (DH_UnaryMinus);
639 break;
640
641 case TYPE_String:
642 buffer()->writeDWord (DH_PushStringIndex);
643 buffer()->writeDWord (value());
644 break;
645
646 case TYPE_Void:
647 case TYPE_Unknown:
648 assert (false);
649 break;
650 }
651 }

Mercurial Repository: botc

mercurial