src/sim/mathexpr.cc

   1 /*
   2  * Copyright (c) 2016 ARM Limited
   3  * All rights reserved
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Redistribution and use in source and binary forms, with or without
  15  * modification, are permitted provided that the following conditions are
  16  * met: redistributions of source code must retain the above copyright
  17  * notice, this list of conditions and the following disclaimer;
  18  * redistributions in binary form must reproduce the above copyright
  19  * notice, this list of conditions and the following disclaimer in the
  20  * documentation and/or other materials provided with the distribution;
  21  * neither the name of the copyright holders nor the names of its
  22  * contributors may be used to endorse or promote products derived from
  23  * this software without specific prior written permission.
  24  *
  25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  28  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  29  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  31  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  35  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 #include "sim/mathexpr.hh"
  39
  40 #include <algorithm>
  41 #include <cmath>
  42 #include <regex>
  43 #include <string>
  44
  45 #include "base/logging.hh"
  46
  47 MathExpr::MathExpr(std::string expr)
  48  : ops(
  49      std::array<OpSearch, uNeg + 1> {{
  50       OpSearch {true, bAdd, 0, '+', [](double a, double b) { return a + b; }},
  51       OpSearch {true, bSub, 0, '-', [](double a, double b) { return a - b; }},
  52       OpSearch {true, bMul, 1, '*', [](double a, double b) { return a * b; }},
  53       OpSearch {true, bDiv, 1, '/', [](double a, double b) { return a / b; }},
  54       OpSearch {false,uNeg, 2, '-', [](double a, double b) { return -b; }},
  55       OpSearch {true, bPow, 3, '^', [](double a, double b) {
  56                  return std::pow(a,b); }
  57       }},
  58     })
  59 {
  60     // Cleanup
  61     expr.erase(remove_if(expr.begin(), expr.end(), isspace), expr.end());
  62
  63     root = MathExpr::parse(expr);
  64     panic_if(!root, "Invalid expression\n");
  65 }
  66
  67 /**
  68  * This function parses a string expression into an expression tree.
  69  * It will look for operators in priority order to recursively build the
  70  * tree, respecting parenthesization.
  71  * Constants can be expressed in any format accepted by std::stod, whereas
  72  * variables are essentially [A-Za-z0-9\.$\\]+
  73  */
  74 MathExpr::Node *
  75 MathExpr::parse(std::string expr) {
  76     if (expr.size() == 0)
  77         return NULL;
  78
  79     // From low to high priority
  80     int par = 0;
  81     for (unsigned p = 0; p < MAX_PRIO; p++) {
  82         for (int i = expr.size() - 1; i >= 0; i--) {
  83             if (expr[i] == ')')
  84                 par++;
  85             if (expr[i] == '(')
  86                 par--;
  87
  88             if (par < 0) return NULL;
  89             if (par > 0) continue;
  90
  91             for (unsigned opt = 0; opt < ops.size(); opt++) {
  92                 if (ops[opt].priority != p) continue;
  93                 if (ops[opt].c == expr[i]) {
  94                     // Try to parse each side
  95                     Node *l = NULL;
  96                     if (ops[opt].binary)
  97                         l = parse(expr.substr(0, i));
  98                     Node *r = parse(expr.substr(i + 1));
  99                     if ((l && r) || (!ops[opt].binary && r)) {
 100                         // Match!
 101                         Node *n = new Node();
 102                         n->op = ops[opt].op;
 103                         n->l = l;
 104                         n->r = r;
 105                         return n;
 106                     }
 107                 }
 108             }
 109         }
 110     }
 111
 112     // Remove trivial parenthesis
 113     if (expr.size() >= 2 && expr[0] == '(' && expr[expr.size() - 1] == ')')
 114         return parse(expr.substr(1, expr.size() - 2));
 115
 116     // Match a number
 117     {
 118         char *sptr;
 119         double v = strtod(expr.c_str(), &sptr);
 120         if (sptr != expr.c_str()) {
 121             Node *n = new Node();
 122             n->op = sValue;
 123             n->value = v;
 124             return n;
 125         }
 126     }
 127
 128     // Match a variable
 129     {
 130         bool contains_non_alpha = false;
 131         for (auto & c: expr)
 132             contains_non_alpha = contains_non_alpha or
 133                 !( (c >= 'a' && c <= 'z') ||
 134                    (c >= 'A' && c <= 'Z') ||
 135                    (c >= '0' && c <= '9') ||
 136                    c == '$' || c == '\\' || c == '.' || c == '_');
 137
 138         if (!contains_non_alpha) {
 139             Node * n = new Node();
 140             n->op = sVariable;
 141             n->variable = expr;
 142             return n;
 143         }
 144     }
 145
 146     return NULL;
 147 }
 148
 149 double
 150 MathExpr::eval(const Node *n, EvalCallback fn) const {
 151     if (!n)
 152         return 0;
 153     else if (n->op == sValue)
 154         return n->value;
 155     else if (n->op == sVariable)
 156         return fn(n->variable);
 157
 158     for (auto & opt : ops)
 159         if (opt.op == n->op)
 160             return opt.fn( eval(n->l, fn), eval(n->r, fn) );
 161
 162     panic("Invalid node!\n");
 163     return 0;
 164 }
 165
 166 std::string
 167 MathExpr::toStr(Node *n, std::string prefix) const {
 168     std::string ret;
 169     ret += prefix + "|-- " + n->toStr() + "\n";
 170     if (n->r)
 171         ret += toStr(n->r, prefix + "|   ");
 172     if (n->l)
 173         ret += toStr(n->l, prefix + "|   ");
 174     return ret;
 175 }
 176