Statistics
| Branch: | Revision:

root / src / common / expression.cc @ master

History | View | Annotate | Download (21.9 KB)

1 01873262 Georg Kunz
//==========================================================================
2
//  EXPRESSION.CC  - part of
3
//                     OMNeT++/OMNEST
4
//            Discrete System Simulation in C++
5
//
6
//  Author: Andras Varga
7
//
8
//==========================================================================
9
10
/*--------------------------------------------------------------*
11
  Copyright (C) 2006-2008 OpenSim Ltd.
12

13
  This file is distributed WITHOUT ANY WARRANTY. See the file
14
  `license' for details on this and other legal matters.
15
*--------------------------------------------------------------*/
16
17
#include <stdio.h>
18
#include <math.h>
19
#include <sstream>
20
#include "expression.h"
21
#include "expressionyydefs.h"
22
23
USING_NAMESPACE
24
25
26
#define eESTKOFLOW   "Stack overflow"
27
#define eESTKUFLOW   "Stack underflow"
28
#define eEBADARGS    "Wrong arguments for '%s'"
29
#define eBADEXP      "Malformed expression"
30
#define eECANTCAST   "Cannot cast to %s"
31
32
33
// should be member of Elem, but the VC++ 9.0 linker disagrees
34
void Expression::Elem_eq(Elem& e, const Elem& other)
35
{
36
    e.deleteOld();
37
38
    memcpy(&e, &other, sizeof(Elem));
39
40
    if (e.type==Elem::STR)
41
        e.s = opp_strdup(e.s);
42
    else if (e.type==Elem::FUNCTOR)
43
        e.fu = e.fu->dup();
44
}
45
46
// should be member of Elem, but the VC++ 9.0 linker disagrees
47
int Expression::Elem_getNumArgs(const Elem& e)
48
{
49
    switch(e.type)
50
    {
51
        case Elem::UNDEF: case Elem::BOOL: case Elem::DBL: case Elem::STR:
52
            return 0;
53
        case Elem::FUNCTOR:
54
            return e.getFunctor()->getNumArgs();
55
            break;
56
        case Elem::OP:
57
            switch(e.getOp()) {
58
                case NEG: case NOT: case BIN_NOT: return 1;
59
                case IIF: return 3;
60
                default: return 2;
61
            }
62
        default: Assert(false); return 0;
63
    }
64
}
65
66
//std::string Expression::Elem::str() const
67
std::string Expression::Elem_str(int type, bool b, double d, const char *s, Functor *fu, int op)
68
{
69
    std::stringstream os;
70
    switch(type)
71
    {
72
        case Elem::UNDEF: os << "<undefined>"; break;
73
        case Elem::BOOL: os << (b ? "true" : "false"); break;
74
        case Elem::DBL: os << d; break;
75
        case Elem::STR: os << "\"" << s << "\""; break;
76
        case Elem::FUNCTOR: os << fu->getName() << "(argc=" << fu->getNumArgs() << ")"; break;
77
        case Elem::OP: os << "op" << op; break;
78
        default: Assert(false);
79
    }
80
    return os.str();
81
}
82
83
std::string Expression::Value::str()
84
{
85
    char buf[32];
86
    switch (type)
87
    {
88
      case BOOL: return bl ? "true" : "false";
89
      case DBL:  sprintf(buf, "%g", dbl); return buf;
90
      case STR:  return opp_quotestr(s.c_str());
91
      default:   throw opp_runtime_error("internal error: bad Value type");
92
    }
93
}
94
95
// should be member of Function, but the VC++ 9.0 linker disagrees
96
std::string Expression::Function_str(const char *name, std::string args[], int numargs)
97
{
98
    std::stringstream os;
99
    os << name << "(";
100
    for (int i=0; i<numargs; i++)
101
        os << (i==0 ? "" : ", ") << args[i];
102
    os << ")";
103
    return os.str();
104
}
105
106
Expression::Expression()
107
{
108
    elems = NULL;
109
    nelems = 0;
110
}
111
112
Expression::~Expression()
113
{
114
    delete [] elems;
115
}
116
117
Expression& Expression::operator=(const Expression& other)
118
{
119
    if (this==&other) return *this;
120
121
    delete [] elems;
122
123
    nelems = other.nelems;
124
    elems = new Elem[nelems];
125
    for (int i=0; i<nelems; i++)
126
        elems[i] = other.elems[i];
127
    return *this;
128
}
129
130
void Expression::setExpression(Elem e[], int n)
131
{
132
    delete [] elems;
133
    elems = e;
134
    nelems = n;
135
}
136
137
#define ulong(x) ((unsigned long)(x))
138
139
Expression::Value Expression::evaluate() const
140
{
141
    const int stksize = 20;
142
    Value stk[stksize];
143
144
    int tos = -1;
145
    for (int i = 0; i < nelems; i++)
146
    {
147
       Elem& e = elems[i];
148
       switch (e.type)
149
       {
150
           case Elem::BOOL:
151
             if (tos>=stksize-1)
152
                 throw opp_runtime_error(eESTKOFLOW);
153
             stk[++tos] = e.b;
154
             break;
155
156
           case Elem::DBL:
157
             if (tos>=stksize-1)
158
                 throw opp_runtime_error(eESTKOFLOW);
159
             stk[++tos] = e.d;
160
             break;
161
162
           case Elem::STR:
163
             if (tos>=stksize-1)
164
                 throw opp_runtime_error(eESTKOFLOW);
165
             stk[++tos] = e.s;
166
             break;
167
168
           case Elem::FUNCTOR:
169
             {
170
             int numargs = e.fu->getNumArgs();
171
             int argpos = tos-numargs+1; // stk[] index of 1st arg to pass
172
             if (argpos<0)
173
                 throw opp_runtime_error(eESTKUFLOW);
174
             const char *argtypes = e.fu->getArgTypes();
175
             for (int i=0; i<numargs; i++)
176
                 if (stk[argpos+i].type != (argtypes[i]=='L' ? 'D' : argtypes[i]))
177
                     throw opp_runtime_error(eEBADARGS,e.fu->getName());
178
             stk[argpos] = e.fu->evaluate(stk+argpos, numargs);
179
             tos = argpos;
180
             break;
181
             }
182
183
           case Elem::OP:
184
             if (e.op==NEG || e.op==NOT || e.op==BIN_NOT)
185
             {
186
                 // unary
187
                 if (tos<0)
188
                     throw opp_runtime_error(eESTKUFLOW);
189
                 switch (e.op)
190
                 {
191
                     case NEG:
192
                         if (stk[tos].type!=Value::DBL)
193
                             throw opp_runtime_error(eEBADARGS,"-");
194
                         stk[tos] = -stk[tos].dbl;
195
                         break;
196
                     case NOT:
197
                         if (stk[tos].type!=Value::BOOL)
198
                             throw opp_runtime_error(eEBADARGS,"!");
199
                         stk[tos] = !stk[tos].bl;
200
                         break;
201
                     case BIN_NOT:
202
                         if (stk[tos].type!=Value::DBL)
203
                             throw opp_runtime_error(eEBADARGS,"~");
204
                         stk[tos] = (double)~ulong(stk[tos].dbl);
205
                         break;
206
                     default: Assert(false);
207
                 }
208
             }
209
             else if (e.op==IIF)
210
             {
211
                 // tertiary
212
                 if (tos<2)
213
                     throw opp_runtime_error(eESTKUFLOW);
214
                 // 1st arg must be bool, others 2nd and 3rd can be anything
215
                 if (stk[tos-2].type!=Value::BOOL)
216
                     throw opp_runtime_error(eEBADARGS,""); //XXX fix error msg
217
                 stk[tos-2] = (stk[tos-2].bl ? stk[tos-1] : stk[tos]);
218
                 tos-=2;
219
             }
220
             else
221
             {
222
                 // binary
223
                 if (tos<1)
224
                     throw opp_runtime_error(eESTKUFLOW);
225
                 switch(e.op)
226
                 {
227
                   case ADD:
228
                       // double addition or string concatenation
229
                       if (stk[tos-1].type==Value::DBL && stk[tos].type==Value::DBL)
230
                           stk[tos-1] = stk[tos-1].dbl + stk[tos].dbl;
231
                       else if (stk[tos-1].type==Value::STR && stk[tos].type==Value::STR)
232
                           stk[tos-1] = stk[tos-1].s + stk[tos].s;
233
                       else
234
                           throw opp_runtime_error(eEBADARGS,"+");
235
                       tos--;
236
                       break;
237
                   case SUB:
238
                       if (stk[tos].type!=Value::DBL || stk[tos-1].type!=Value::DBL)
239
                           throw opp_runtime_error(eEBADARGS,"-");
240
                       stk[tos-1] = stk[tos-1].dbl - stk[tos].dbl;
241
                       tos--;
242
                       break;
243
                   case MUL:
244
                       if (stk[tos].type!=Value::DBL || stk[tos-1].type!=Value::DBL)
245
                           throw opp_runtime_error(eEBADARGS,"*");
246
                       stk[tos-1] = stk[tos-1].dbl * stk[tos].dbl;
247
                       tos--;
248
                       break;
249
                   case DIV:
250
                       if (stk[tos].type!=Value::DBL || stk[tos-1].type!=Value::DBL)
251
                           throw opp_runtime_error(eEBADARGS,"/");
252
                       stk[tos-1] = stk[tos-1].dbl / stk[tos].dbl;
253
                       tos--;
254
                       break;
255
                   case MOD:
256
                       if (stk[tos].type!=Value::DBL || stk[tos-1].type!=Value::DBL)
257
                           throw opp_runtime_error(eEBADARGS,"%");
258
                       stk[tos-1] = (double)(ulong(stk[tos-1].dbl) % ulong(stk[tos].dbl));
259
                       tos--;
260
                       break;
261
                   case POW:
262
                       if (stk[tos].type!=Value::DBL || stk[tos-1].type!=Value::DBL)
263
                           throw opp_runtime_error(eEBADARGS,"^");
264
                       stk[tos-1] = pow(stk[tos-1].dbl, stk[tos].dbl);
265
                       tos--;
266
                       break;
267
                   case AND:
268
                       if (stk[tos].type!=Value::BOOL || stk[tos-1].type!=Value::BOOL)
269
                           throw opp_runtime_error(eEBADARGS,"&&");
270
                       stk[tos-1] = stk[tos-1].bl && stk[tos].bl;
271
                       tos--;
272
                       break;
273
                   case OR:
274
                       if (stk[tos].type!=Value::BOOL || stk[tos-1].type!=Value::BOOL)
275
                           throw opp_runtime_error(eEBADARGS,"||");
276
                       stk[tos-1] = stk[tos-1].bl || stk[tos].bl;
277
                       tos--;
278
                       break;
279
                   case XOR:
280
                       if (stk[tos].type!=Value::BOOL || stk[tos-1].type!=Value::BOOL)
281
                           throw opp_runtime_error(eEBADARGS,"##");
282
                       stk[tos-1] = stk[tos-1].bl != stk[tos].bl;
283
                       tos--;
284
                       break;
285
                   case BIN_AND:
286
                       if (stk[tos].type!=Value::DBL || stk[tos-1].type!=Value::DBL)
287
                           throw opp_runtime_error(eEBADARGS,"&");
288
                       stk[tos-1] = (double)(ulong(stk[tos-1].dbl) & ulong(stk[tos].dbl));
289
                       tos--;
290
                       break;
291
                   case BIN_OR:
292
                       if (stk[tos].type!=Value::DBL || stk[tos-1].type!=Value::DBL)
293
                           throw opp_runtime_error(eEBADARGS,"|");
294
                       stk[tos-1] = (double)(ulong(stk[tos-1].dbl) | ulong(stk[tos].dbl));
295
                       tos--;
296
                       break;
297
                   case BIN_XOR:
298
                       if (stk[tos].type!=Value::DBL || stk[tos-1].type!=Value::DBL)
299
                           throw opp_runtime_error(eEBADARGS,"#");
300
                       stk[tos-1] = (double)(ulong(stk[tos-1].dbl) ^ ulong(stk[tos].dbl));
301
                       tos--;
302
                       break;
303
                   case LSHIFT:
304
                       if (stk[tos].type!=Value::DBL || stk[tos-1].type!=Value::DBL)
305
                           throw opp_runtime_error(eEBADARGS,"<<");
306
                       stk[tos-1] = (double)(ulong(stk[tos-1].dbl) << ulong(stk[tos].dbl));
307
                       tos--;
308
                       break;
309
                   case RSHIFT:
310
                       if (stk[tos].type!=Value::DBL || stk[tos-1].type!=Value::DBL)
311
                           throw opp_runtime_error(eEBADARGS,">>");
312
                       stk[tos-1] = (double)(ulong(stk[tos-1].dbl) >> ulong(stk[tos].dbl));
313
                       tos--;
314
                       break;
315
#define COMPARISON(RELATION) \
316
                                 if (stk[tos-1].type==Value::DBL && stk[tos].type==Value::DBL) \
317
                                     stk[tos-1] = (stk[tos-1].dbl RELATION stk[tos].dbl); \
318
                                 else if (stk[tos-1].type==Value::STR && stk[tos].type==Value::STR) \
319
                                     stk[tos-1] = (stk[tos-1].s RELATION stk[tos].s); \
320
                                 else if (stk[tos-1].type==Value::BOOL && stk[tos].type==Value::BOOL) \
321
                                     stk[tos-1] = (stk[tos-1].bl RELATION stk[tos].bl); \
322
                                 else \
323
                                     throw opp_runtime_error(eEBADARGS,#RELATION); \
324
                                 tos--;
325
                   case EQ:
326
                       COMPARISON(==);
327
                       break;
328
                   case NE:
329
                       COMPARISON(!=);
330
                       break;
331
                   case LT:
332
                       COMPARISON(<);
333
                       break;
334
                   case LE:
335
                       COMPARISON(<=);
336
                       break;
337
                   case GT:
338
                       COMPARISON(>);
339
                       break;
340
                   case GE:
341
                       COMPARISON(>=);
342
                       break;
343
#undef COMPARISON
344
                   default:
345
                       throw opp_runtime_error(eBADEXP);
346
                 }
347
             }
348
             break;
349
           default:
350
             throw opp_runtime_error(eBADEXP);
351
       }
352
    }
353
    if (tos!=0)
354
        throw opp_runtime_error(eBADEXP);
355
356
    return stk[tos];
357
}
358
359
bool Expression::boolValue()
360
{
361
    Value v = evaluate();
362
    if (v.type!=Value::BOOL)
363
        throw opp_runtime_error(eECANTCAST,"bool");
364
    return v.bl;
365
}
366
367
long Expression::longValue()
368
{
369
    Value v = evaluate();
370
    if (v.type!=Value::DBL)
371
        throw opp_runtime_error(eECANTCAST,"long");
372
    return (long) v.dbl;
373
}
374
375
double Expression::doubleValue()
376
{
377
    Value v = evaluate();
378
    if (v.type!=Value::DBL)
379
        throw opp_runtime_error(eECANTCAST,"double");
380
    return v.dbl;
381
}
382
383
std::string Expression::stringValue()
384
{
385
    Value v = evaluate();
386
    if (v.type!=Value::STR)
387
        throw opp_runtime_error(eECANTCAST,"string");
388
    return v.s;
389
}
390
391
std::string Expression::str() const
392
{
393
    // We perform the same algorithm as during evaluation (i.e. stack machine),
394
    // only instead of actual calculations we store the result as string.
395
    // We need to keep track of operator precendences to be able to add parens where needed.
396
397
    try
398
    {
399
        const int stksize = 20;
400
        std::string strstk[stksize];
401
        int pristk[stksize];
402
403
        int tos = -1;
404
        for (int i = 0; i < nelems; i++)
405
        {
406
           Elem& e = elems[i];
407
           switch (e.type)
408
           {
409
               case Elem::BOOL:
410
                 if (tos>=stksize-1)
411
                     throw opp_runtime_error(eESTKOFLOW);
412
                 strstk[++tos] = (e.b ? "true" : "false");
413
                 pristk[tos] = 0;
414
                 break;
415
               case Elem::DBL:
416
                 {
417
                 if (tos>=stksize-1)
418
                     throw opp_runtime_error(eESTKOFLOW);
419
                 char buf[32];
420
                 sprintf(buf, "%g", e.d);
421
                 strstk[++tos] = buf;
422
                 pristk[tos] = 0;
423
                 }
424
                 break;
425
               case Elem::STR:
426
                 if (tos>=stksize-1)
427
                     throw opp_runtime_error(eESTKOFLOW);
428
                 strstk[++tos] = opp_quotestr(e.s ? e.s : "");
429
                 pristk[tos] = 0;
430
                 break;
431
               case Elem::FUNCTOR:
432
                 {
433
                 int numargs = e.fu->getNumArgs();
434
                 int argpos = tos-numargs+1; // strstk[] index of 1st arg to pass
435
                 if (argpos<0)
436
                     throw opp_runtime_error(eESTKUFLOW);
437
                 strstk[argpos] = e.fu->str(strstk+argpos, numargs);
438
                 tos = argpos;
439
                 pristk[tos] = 0;
440
                 break;
441
                 }
442
               case Elem::OP:
443
                 if (e.op==NEG || e.op==NOT || e.op==BIN_NOT)
444
                 {
445
                     if (tos<0)
446
                         throw opp_runtime_error(eESTKUFLOW);
447
                     const char *op;
448
                     switch (e.op)
449
                     {
450
                         case NEG: op=" -"; break;
451
                         case NOT: op=" !"; break;
452
                         case BIN_NOT: op=" ~"; break;
453
                         default:  op=" ???";
454
                     }
455
                     strstk[tos] = std::string(op) + strstk[tos]; // pri=0: never needs parens
456
                     pristk[tos] = 0;
457
                 }
458
                 else if (e.op==IIF)  // conditional (tertiary)
459
                 {
460
                     if (tos<2)
461
                         throw opp_runtime_error(eESTKUFLOW);
462
                     strstk[tos-2] = strstk[tos-2] + " ? " + strstk[tos-1] + " : " + strstk[tos];
463
                     tos-=2;
464
                     pristk[tos] = 8;
465
                 }
466
                 else
467
                 {
468
                     // binary
469
                     if (tos<1)
470
                         throw opp_runtime_error(eESTKUFLOW);
471
                     int pri;
472
                     const char *op;
473
                     switch(e.op)
474
                     {
475
                         //
476
                         // Precedences, based on expr.y:
477
                         //   prec=7: && || ##
478
                         //   prec=6: == != > >= < <=
479
                         //   prec=5: & | #
480
                         //   prec=4: << >>
481
                         //   prec=3: + -
482
                         //   prec=2: * / %
483
                         //   prec=1: ^
484
                         //   prec=0: UMIN ! ~
485
                         //
486
                         case ADD: op=" + "; pri=3; break;
487
                         case SUB: op=" - "; pri=3; break;
488
                         case MUL: op=" * "; pri=2; break;
489
                         case DIV: op=" / "; pri=2; break;
490
                         case MOD: op=" % "; pri=2; break;
491
                         case POW: op=" ^ "; pri=1; break;
492
                         case EQ:  op=" == "; pri=6; break;
493
                         case NE:  op=" != "; pri=6; break;
494
                         case LT:  op=" < "; pri=6; break;
495
                         case GT:  op=" > "; pri=6; break;
496
                         case LE:  op=" <= "; pri=6; break;
497
                         case GE:  op=" >= "; pri=6; break;
498
                         case AND: op=" && "; pri=7; break;
499
                         case OR:  op=" || "; pri=7; break;
500
                         case XOR: op=" ## "; pri=7; break;
501
                         case BIN_AND: op=" & "; pri=5; break;
502
                         case BIN_OR:  op=" | "; pri=5; break;
503
                         case BIN_XOR: op=" # "; pri=5; break;
504
                         case LSHIFT:  op=" << "; pri=4; break;
505
                         case RSHIFT:  op=" >> "; pri=4; break;
506
                         default:  op=" ??? "; pri=10; break;
507
                     }
508
509
                     // add parens, depending on the operator precedences
510
                     std::string tmp;
511
                     if (pri < pristk[tos-1])
512
                         tmp = std::string("(") + strstk[tos-1] + ")";
513
                     else
514
                         tmp = strstk[tos-1];
515
                     tmp += op;
516
                     if (pri < pristk[tos])
517
                         tmp += std::string("(") + strstk[tos] + ")";
518
                     else
519
                         tmp += strstk[tos];
520
                     strstk[tos-1] = tmp;
521
                     tos--;
522
                     pristk[tos] = pri;
523
                     break;
524
                 }
525
                 break;
526
               default:
527
                 throw opp_runtime_error(eBADEXP);
528
           }
529
        }
530
        if (tos!=0)
531
            throw opp_runtime_error(eBADEXP);
532
        return strstk[tos];
533
    }
534
    catch (std::exception& e)
535
    {
536
        std::string ret = std::string("[[ ") + e.what() + " ]]";
537
        return ret;
538
    }
539
}
540
541
void Expression::parse(const char *text, Resolver *resolver)
542
{
543
    // fills elems[]; throws exception if something goes wrong
544
    ::doParseExpression(text, resolver, elems, nelems);
545
}
546
547
bool Expression::isAConstant() const
548
{
549
    for (int i=0; i<nelems; i++)
550
    {
551
        switch(elems[i].type)
552
        {
553
            // literals and anything calculated from them are OK
554
            case Elem::BOOL:
555
            case Elem::DBL:
556
            case Elem::STR:
557
            case Elem::OP:
558
                continue; //OK
559
            default:
560
                return false;
561
        }
562
    }
563
    return true;
564
}
565
566
//----------------------
567
568
#define F0(name)   {#name, (double(*)(...)) (double(*)())name, 0}
569
#define F1(name)   {#name, (double(*)(...)) (double(*)(double))name, 1}
570
#define F2(name)   {#name, (double(*)(...)) (double(*)(double,double))name, 2}
571
#define F3(name)   {#name, (double(*)(...)) (double(*)(double,double,double))name, 3}
572
573
MathFunction::FuncDesc MathFunction::functable[] = {
574
    F1(acos),
575
    F1(asin),
576
    F1(atan),
577
    F2(atan2),
578
    F1(sin),
579
    F1(cos),
580
    F1(tan),
581
    F1(ceil),
582
    F1(floor),
583
    F1(exp),
584
    F2(pow),
585
    F1(sqrt),
586
    F1(fabs),
587
    F2(fmod),
588
    F2(hypot),
589
    F1(log),
590
    F1(log10),
591
    {NULL, NULL, 0}
592
};
593
594
MathFunction::MathFunction(const char *name)
595
{
596
    funcname = name;
597
    FuncDesc *fd = lookup(funcname.c_str());
598
    if (!fd)
599
        throw opp_runtime_error("unrecognized function %s", name);
600
    f = fd->f;
601
    argcount = fd->argcount;
602
}
603
604
MathFunction::~MathFunction()
605
{
606
}
607
608
Expression::Functor *MathFunction::dup() const
609
{
610
    return new MathFunction(getName());
611
}
612
613
const char *MathFunction::getName() const
614
{
615
     return funcname.c_str();
616
}
617
618
MathFunction::FuncDesc *MathFunction::lookup(const char *name)
619
{
620
    for (FuncDesc *f = functable; f->name!=NULL; f++)
621
        if (strcmp(f->name, name)==0)
622
            return f;
623
    return NULL;
624
}
625
626
bool MathFunction::supports(const char *name)
627
{
628
    return lookup(name)!=NULL;
629
}
630
631
const char *MathFunction::getArgTypes() const
632
{
633
    Assert(Expression::Value::DBL == 'D');
634
    FuncDesc *fd = lookup(funcname.c_str());
635
    int n = fd==NULL ? 0 : fd->argcount;
636
    const char *ddd = "DDDDDDDDDDDDDDDDDD";
637
    return ddd+strlen(ddd)-n;
638
}
639
640
char MathFunction::getReturnType() const
641
{
642
    return Expression::Value::DBL;
643
}
644
645
Expression::Value MathFunction::evaluate(Expression::Value args[], int numargs)
646
{
647
    Assert(numargs==argcount);
648
    switch (numargs)
649
    {
650
        case 0: return f();
651
        case 1: return f(args[0].dbl);
652
        case 2: return f(args[0].dbl, args[1].dbl);
653
        case 3: return f(args[0].dbl, args[1].dbl, args[2].dbl);
654
        default: throw opp_runtime_error("too many args");
655
    }
656
}