2 * Copyright (c) 2016, 2020 ARM Limited
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.
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.
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.
38 #include "sim/mathexpr.hh"
45 #include "base/logging.hh"
47 MathExpr::MathExpr(std::string expr
)
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
); }
61 expr
.erase(remove_if(expr
.begin(), expr
.end(), isspace
), expr
.end());
63 root
= MathExpr::parse(expr
);
64 panic_if(!root
, "Invalid expression\n");
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\.$\\]+
75 MathExpr::parse(std::string expr
) {
79 // From low to high priority
81 for (unsigned p
= 0; p
< MAX_PRIO
; p
++) {
82 for (int i
= expr
.size() - 1; i
>= 0; i
--) {
88 if (par
< 0) return NULL
;
89 if (par
> 0) continue;
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
97 l
= parse(expr
.substr(0, i
));
98 Node
*r
= parse(expr
.substr(i
+ 1));
99 if ((l
&& r
) || (!ops
[opt
].binary
&& r
)) {
101 Node
*n
= new Node();
112 // Remove trivial parenthesis
113 if (expr
.size() >= 2 && expr
[0] == '(' && expr
[expr
.size() - 1] == ')')
114 return parse(expr
.substr(1, expr
.size() - 2));
119 double v
= strtod(expr
.c_str(), &sptr
);
120 if (sptr
!= expr
.c_str()) {
121 Node
*n
= new Node();
130 bool contains_non_alpha
= false;
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
== '_');
138 if (!contains_non_alpha
) {
139 Node
* n
= new Node();
150 MathExpr::eval(const Node
*n
, EvalCallback fn
) const {
153 else if (n
->op
== sValue
)
155 else if (n
->op
== sVariable
)
156 return fn(n
->variable
);
158 for (auto & opt
: ops
)
160 return opt
.fn( eval(n
->l
, fn
), eval(n
->r
, fn
) );
162 panic("Invalid node!\n");
167 MathExpr::toStr(Node
*n
, std::string prefix
) const {
169 ret
+= prefix
+ "|-- " + n
->toStr() + "\n";
171 ret
+= toStr(n
->r
, prefix
+ "| ");
173 ret
+= toStr(n
->l
, prefix
+ "| ");
178 MathExpr::getVariables(const Node
*n
,
179 std::vector
<std::string
> &variables
) const
181 if (!n
|| n
->op
== sValue
|| n
->op
== nInvalid
) {
183 } else if (n
->op
== sVariable
) {
184 variables
.push_back(n
->variable
);
186 getVariables(n
->l
, variables
);
187 getVariables(n
->r
, variables
);