• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

GothenburgBitFactory / taskwarrior / 11335495770

14 Oct 2024 09:47PM UTC coverage: 84.223% (-0.6%) from 84.776%
11335495770

push

github

web-flow
[pre-commit.ci] pre-commit autoupdate (#3650)

updates:
- [github.com/psf/black: 24.8.0 → 24.10.0](https://github.com/psf/black/compare/24.8.0...24.10.0)

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>

19005 of 22565 relevant lines covered (84.22%)

23473.55 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

92.16
/src/Eval.cpp
1
////////////////////////////////////////////////////////////////////////////////
2
//
3
// Copyright 2013 - 2021, Tomas Babej, Paul Beckingham, Federico Hernandez.
4
//
5
// Permission is hereby granted, free of charge, to any person obtaining a copy
6
// of this software and associated documentation files (the "Software"), to deal
7
// in the Software without restriction, including without limitation the rights
8
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9
// copies of the Software, and to permit persons to whom the Software is
10
// furnished to do so, subject to the following conditions:
11
//
12
// The above copyright notice and this permission notice shall be included
13
// in all copies or substantial portions of the Software.
14
//
15
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
16
// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21
// SOFTWARE.
22
//
23
// https://www.opensource.org/licenses/mit-license.php
24
//
25
////////////////////////////////////////////////////////////////////////////////
26

27
#include <cmake.h>
28
// cmake.h include header must come first
29

30
#include <Color.h>
31
#include <Context.h>
32
#include <DOM.h>
33
#include <Eval.h>
34
#include <Task.h>
35
#include <format.h>
36
#include <shared.h>
37
#include <time.h>
38

39
#include <map>
40

41
////////////////////////////////////////////////////////////////////////////////
42
// Supported operators, borrowed from C++, particularly the precedence.
43
// Note: table is sorted by length of operator string, so searches match
44
//       longest first.
45
static struct {
46
  std::string op;
47
  int precedence;
48
  char type;           // b=binary, u=unary, c=circumfix
49
  char associativity;  // l=left, r=right, _=?
50
} operators[] = {
51
    // Operator   Precedence  Type  Associativity
52
    {"^", 16, 'b', 'r'},  // Exponent
53

54
    {"!", 15, 'u', 'r'},      // Unary not
55
    {"_neg_", 15, 'u', 'r'},  // Unary minus
56
    {"_pos_", 15, 'u', 'r'},  // Unary plus
57

58
    {"_hastag_", 14, 'b', 'l'},  // +tag  [Pseudo-op]
59
    {"_notag_", 14, 'b', 'l'},   // -tag  [Pseudo-op]
60

61
    {"*", 13, 'b', 'l'},  // Multiplication
62
    {"/", 13, 'b', 'l'},  // Division
63
    {"%", 13, 'b', 'l'},  // Modulus
64

65
    {"+", 12, 'b', 'l'},  // Addition
66
    {"-", 12, 'b', 'l'},  // Subtraction
67

68
    {"<=", 10, 'b', 'l'},  // Less than or equal
69
    {">=", 10, 'b', 'l'},  // Greater than or equal
70
    {">", 10, 'b', 'l'},   // Greater than
71
    {"<", 10, 'b', 'l'},   // Less than
72

73
    {"=", 9, 'b', 'l'},    // Equal (partial)
74
    {"==", 9, 'b', 'l'},   // Equal (exact)
75
    {"!=", 9, 'b', 'l'},   // Inequal (partial)
76
    {"!==", 9, 'b', 'l'},  // Inequal (exact)
77

78
    {"~", 8, 'b', 'l'},   // Regex match
79
    {"!~", 8, 'b', 'l'},  // Regex non-match
80

81
    {"and", 5, 'b', 'l'},  // Conjunction
82
    {"or", 4, 'b', 'l'},   // Disjunction
83
    {"xor", 3, 'b', 'l'},  // Disjunction
84

85
    {"(", 0, 'c', '_'},  // Precedence start
86
    {")", 0, 'c', '_'},  // Precedence end
87
};
88

89
#define NUM_OPERATORS (sizeof(operators) / sizeof(operators[0]))
90

91
////////////////////////////////////////////////////////////////////////////////
92
// Built-in support for some named constants.
93
static bool namedConstants(const std::string& name, Variant& value) {
21,395✔
94
  if (name == "true")
21,395✔
95
    value = Variant(true);
2✔
96
  else if (name == "false")
21,393✔
97
    value = Variant(false);
2✔
98
  else if (name == "pi")
21,391✔
99
    value = Variant(3.14159165);
1✔
100
  else
101
    return false;
21,390✔
102

103
  return true;
5✔
104
}
105

106
////////////////////////////////////////////////////////////////////////////////
107
// Support for evaluating DOM references (add with `e.AddSource(domSource)`)
108
bool domSource(const std::string& identifier, Variant& value) {
21,378✔
109
  if (getDOM(identifier, Context::getContext().currentTask, value)) {
21,378✔
110
    value.source(identifier);
15,788✔
111
    return true;
15,788✔
112
  }
113

114
  return false;
5,590✔
115
}
116

117
////////////////////////////////////////////////////////////////////////////////
118
Eval::Eval() { addSource(namedConstants); }
2,105✔
119

120
////////////////////////////////////////////////////////////////////////////////
121
void Eval::addSource(bool (*source)(const std::string&, Variant&)) { _sources.push_back(source); }
4,210✔
122

123
////////////////////////////////////////////////////////////////////////////////
124
void Eval::evaluateInfixExpression(const std::string& e, Variant& v) const {
855✔
125
  // Reduce e to a vector of tokens.
126
  Lexer l(e);
855✔
127
  std::vector<std::pair<std::string, Lexer::Type>> tokens;
855✔
128
  std::string token;
855✔
129
  Lexer::Type type;
130
  while (l.token(token, type)) tokens.emplace_back(token, type);
2,210✔
131

132
  // Parse for syntax checking and operator replacement.
133
  if (_debug) Context::getContext().debug(" [1;37;42mFILTER [0m Infix        " + dump(tokens));
855✔
134
  infixParse(tokens);
855✔
135
  if (_debug) Context::getContext().debug(" [1;37;42mFILTER [0m Infix parsed " + dump(tokens));
855✔
136

137
  // Convert infix --> postfix.
138
  infixToPostfix(tokens);
855✔
139
  if (_debug) Context::getContext().debug(" [1;37;42mFILTER [0m Postfix      " + dump(tokens));
855✔
140

141
  // Call the postfix evaluator.
142
  evaluatePostfixStack(tokens, v);
855✔
143
}
1,103✔
144

145
////////////////////////////////////////////////////////////////////////////////
146
void Eval::evaluatePostfixExpression(const std::string& e, Variant& v) const {
16✔
147
  // Reduce e to a vector of tokens.
148
  Lexer l(e);
16✔
149
  std::vector<std::pair<std::string, Lexer::Type>> tokens;
16✔
150
  std::string token;
16✔
151
  Lexer::Type type;
152
  while (l.token(token, type)) tokens.emplace_back(token, type);
56✔
153

154
  if (_debug) Context::getContext().debug(" [1;37;42mFILTER [0m Postfix      " + dump(tokens));
16✔
155

156
  // Call the postfix evaluator.
157
  evaluatePostfixStack(tokens, v);
16✔
158
}
16✔
159

160
////////////////////////////////////////////////////////////////////////////////
161
void Eval::compileExpression(const std::vector<std::pair<std::string, Lexer::Type>>& precompiled) {
1,257✔
162
  _compiled = precompiled;
1,257✔
163

164
  // Parse for syntax checking and operator replacement.
165
  if (_debug) Context::getContext().debug(" [1;37;42mFILTER [0m Infix        " + dump(_compiled));
1,257✔
166
  infixParse(_compiled);
1,257✔
167
  if (_debug) Context::getContext().debug(" [1;37;42mFILTER [0m Infix parsed " + dump(_compiled));
1,257✔
168

169
  // Convert infix --> postfix.
170
  infixToPostfix(_compiled);
1,257✔
171
  if (_debug) Context::getContext().debug(" [1;37;42mFILTER [0m Postfix      " + dump(_compiled));
1,256✔
172
}
1,256✔
173

174
////////////////////////////////////////////////////////////////////////////////
175
void Eval::evaluateCompiledExpression(Variant& v) {
8,711✔
176
  // Call the postfix evaluator.
177
  evaluatePostfixStack(_compiled, v);
8,711✔
178
}
8,711✔
179

180
////////////////////////////////////////////////////////////////////////////////
181
void Eval::debug(bool value) { _debug = value; }
2,517✔
182

183
////////////////////////////////////////////////////////////////////////////////
184
// Static.
185
std::vector<std::string> Eval::getOperators() {
4,497✔
186
  std::vector<std::string> all;
4,497✔
187
  all.reserve(NUM_OPERATORS);
4,497✔
188
  for (const auto& opr : operators) all.push_back(opr.op);
121,419✔
189

190
  return all;
4,497✔
191
}
×
192

193
////////////////////////////////////////////////////////////////////////////////
194
// Static.
195
std::vector<std::string> Eval::getBinaryOperators() {
4,497✔
196
  std::vector<std::string> all;
4,497✔
197
  for (const auto& opr : operators)
121,419✔
198
    if (opr.type == 'b') all.push_back(opr.op);
116,922✔
199

200
  return all;
4,497✔
201
}
×
202

203
////////////////////////////////////////////////////////////////////////////////
204
void Eval::evaluatePostfixStack(const std::vector<std::pair<std::string, Lexer::Type>>& tokens,
9,582✔
205
                                Variant& result) const {
206
  if (tokens.size() == 0) throw std::string("No expression to evaluate.");
9,582✔
207

208
  // This is stack used by the postfix evaluator.
209
  std::vector<Variant> values;
9,582✔
210
  values.reserve(tokens.size());
9,582✔
211

212
  for (const auto& token : tokens) {
65,628✔
213
    // Unary operators.
214
    if (token.second == Lexer::Type::op && token.first == "!") {
56,170✔
215
      if (values.size() < 1) throw std::string("The expression could not be evaluated.");
4✔
216

217
      Variant right = values.back();
4✔
218
      values.pop_back();
4✔
219
      Variant result = !right;
4✔
220
      values.push_back(result);
4✔
221
      if (_debug)
4✔
222
        Context::getContext().debug(format("Eval {1} ↓'{2}' → ↑'{3}'", token.first,
×
223
                                           (std::string)right, (std::string)result));
×
224
    } else if (token.second == Lexer::Type::op && token.first == "_neg_") {
56,170✔
225
      if (values.size() < 1) throw std::string("The expression could not be evaluated.");
26✔
226

227
      Variant right = values.back();
26✔
228
      values.pop_back();
26✔
229

230
      Variant result(0);
26✔
231
      result -= right;
26✔
232
      values.push_back(result);
26✔
233

234
      if (_debug)
26✔
235
        Context::getContext().debug(format("Eval {1} ↓'{2}' → ↑'{3}'", token.first,
×
236
                                           (std::string)right, (std::string)result));
×
237
    } else if (token.second == Lexer::Type::op && token.first == "_pos_") {
56,166✔
238
      // The _pos_ operator is a NOP.
239
      if (_debug)
×
240
        Context::getContext().debug(format("[{1}] eval op {2} NOP", values.size(), token.first));
×
241
    }
242

243
    // Binary operators.
244
    else if (token.second == Lexer::Type::op) {
56,140✔
245
      if (values.size() < 2) throw std::string("The expression could not be evaluated.");
23,279✔
246

247
      Variant right = values.back();
23,279✔
248
      values.pop_back();
23,279✔
249

250
      Variant left = values.back();
23,279✔
251
      values.pop_back();
23,279✔
252

253
      auto contextTask = Context::getContext().currentTask;
23,279✔
254

255
      // Ordering these by anticipation frequency of use is a good idea.
256
      Variant result;
23,279✔
257
      if (token.first == "and")
23,279✔
258
        result = left && right;
7,092✔
259
      else if (token.first == "or")
16,187✔
260
        result = left || right;
153✔
261
      else if (token.first == "&&")
16,034✔
262
        result = left && right;
×
263
      else if (token.first == "||")
16,034✔
264
        result = left || right;
4✔
265
      else if (token.first == "<")
16,030✔
266
        result = left < right;
87✔
267
      else if (token.first == "<=")
15,943✔
268
        result = left <= right;
3,868✔
269
      else if (token.first == ">")
12,075✔
270
        result = left > right;
104✔
271
      else if (token.first == ">=")
11,971✔
272
        result = left >= right;
3,865✔
273
      else if (token.first == "==")
8,106✔
274
        result = left.operator==(right);
1,571✔
275
      else if (token.first == "!==")
6,535✔
276
        result = left.operator!=(right);
34✔
277
      else if (token.first == "=")
6,501✔
278
        result = left.operator_partial(right);
2,561✔
279
      else if (token.first == "!=")
3,940✔
280
        result = left.operator_nopartial(right);
41✔
281
      else if (token.first == "+")
3,899✔
282
        result = left + right;
70✔
283
      else if (token.first == "-")
3,829✔
284
        result = left - right;
191✔
285
      else if (token.first == "*")
3,638✔
286
        result = left * right;
4✔
287
      else if (token.first == "/")
3,634✔
288
        result = left / right;
3✔
289
      else if (token.first == "^")
3,631✔
290
        result = left ^ right;
×
291
      else if (token.first == "%")
3,631✔
292
        result = left % right;
×
293
      else if (token.first == "xor")
3,631✔
294
        result = left.operator_xor(right);
20✔
295
      else if (contextTask) {
3,611✔
296
        if (token.first == "~")
3,611✔
297
          result = left.operator_match(right, *contextTask);
767✔
298
        else if (token.first == "!~")
2,844✔
299
          result = left.operator_nomatch(right, *contextTask);
19✔
300
        else if (token.first == "_hastag_")
2,825✔
301
          result = left.operator_hastag(right, *contextTask);
887✔
302
        else if (token.first == "_notag_")
1,938✔
303
          result = left.operator_notag(right, *contextTask);
1,938✔
304
        else
305
          throw format("Unsupported operator '{1}'.", token.first);
×
306
      } else
307
        throw format("Unsupported operator '{1}'.", token.first);
×
308

309
      values.push_back(result);
23,155✔
310

311
      if (_debug)
23,155✔
312
        Context::getContext().debug(format("Eval ↓'{1}' {2} ↓'{3}' → ↑'{4}'", (std::string)left,
36✔
313
                                           token.first, (std::string)right, (std::string)result));
18✔
314
    }
23,527✔
315

316
    // Literals and identifiers.
317
    else {
318
      Variant v(token.first);
32,861✔
319
      switch (token.second) {
32,861✔
320
        case Lexer::Type::number:
9,401✔
321
          if (Lexer::isAllDigits(token.first)) {
9,401✔
322
            v.cast(Variant::type_integer);
9,367✔
323
            if (_debug)
9,367✔
324
              Context::getContext().debug(format("Eval literal number ↑'{1}'", (std::string)v));
×
325
          } else {
326
            v.cast(Variant::type_real);
34✔
327
            if (_debug)
34✔
328
              Context::getContext().debug(format("Eval literal decimal ↑'{1}'", (std::string)v));
×
329
          }
330
          break;
9,401✔
331

332
        case Lexer::Type::op:
×
333
          throw std::string("Operator expected.");
×
334
          break;
335

336
        case Lexer::Type::dom:
15,859✔
337
        case Lexer::Type::identifier: {
338
          bool found = false;
15,859✔
339
          for (const auto& source : _sources) {
31,802✔
340
            if (source(token.first, v)) {
31,715✔
341
              if (_debug)
15,772✔
342
                Context::getContext().debug(
14✔
343
                    format("Eval identifier source '{1}' → ↑'{2}'", token.first, (std::string)v));
28✔
344
              found = true;
15,772✔
345
              break;
15,772✔
346
            }
347
          }
348

349
          // An identifier that fails lookup is a string.
350
          if (!found) {
15,859✔
351
            v.cast(Variant::type_string);
87✔
352
            if (_debug)
87✔
353
              Context::getContext().debug(
×
354
                  format("Eval identifier source failed '{1}'", token.first));
×
355
          }
356
        } break;
15,859✔
357

358
        case Lexer::Type::date:
551✔
359
          v.cast(Variant::type_date);
551✔
360
          if (_debug)
551✔
361
            Context::getContext().debug(format("Eval literal date ↑'{1}'", (std::string)v));
×
362
          break;
551✔
363

364
        case Lexer::Type::duration:
228✔
365
          v.cast(Variant::type_duration);
228✔
366
          if (_debug)
228✔
367
            Context::getContext().debug(format("Eval literal duration ↑'{1}'", (std::string)v));
×
368
          break;
228✔
369

370
        // Nothing to do.
371
        case Lexer::Type::string:
6,822✔
372
        default:
373
          if (_debug)
6,822✔
374
            Context::getContext().debug(format("Eval literal string ↑'{1}'", (std::string)v));
21✔
375
          break;
6,822✔
376
      }
377

378
      values.push_back(v);
32,861✔
379
    }
32,861✔
380
  }
381

382
  // If there is more than one variant left on the stack, then the original
383
  // expression was not valid.
384
  if (values.size() != 1) throw std::string("The value is not an expression.");
9,458✔
385

386
  result = values[0];
9,458✔
387
}
9,582✔
388

389
////////////////////////////////////////////////////////////////////////////////
390
//
391
// Grammar:
392
//   Logical     --> Regex {( "and" | "or" | "xor" ) Regex}
393
//   Regex       --> Equality {( "~" | "!~" ) Equality}
394
//   Equality    --> Comparative {( "==" | "=" | "!=" ) Comparative}
395
//   Comparative --> Arithmetic {( "<=" | "<" | ">=" | ">" ) Arithmetic}
396
//   Arithmetic  --> Geometric {( "+" | "-" ) Geometric}
397
//   Geometric   --> Tag {( "*" | "/" | "%" ) Tag}
398
//   Tag         --> Unary {( "_hastag_" | "_notag_" ) Unary}
399
//   Unary       --> [( "-" | "+" | "!" )] Exponent
400
//   Exponent    --> Primitive ["^" Primitive]
401
//   Primitive   --> "(" Logical ")" | Variant
402
//
403
void Eval::infixParse(std::vector<std::pair<std::string, Lexer::Type>>& infix) const {
2,112✔
404
  unsigned int i = 0;
2,112✔
405
  parseLogical(infix, i);
2,112✔
406
}
2,112✔
407

408
////////////////////////////////////////////////////////////////////////////////
409
// Logical     --> Regex {( "and" | "or" | "xor" ) Regex}
410
bool Eval::parseLogical(std::vector<std::pair<std::string, Lexer::Type>>& infix,
4,919✔
411
                        unsigned int& i) const {
412
  if (i < infix.size() && parseRegex(infix, i)) {
4,919✔
413
    while (i < infix.size() && infix[i].second == Lexer::Type::op &&
9,720✔
414
           (infix[i].first == "and" || infix[i].first == "or" || infix[i].first == "xor")) {
3,810✔
415
      ++i;
998✔
416
      if (!parseRegex(infix, i)) return false;
998✔
417
    }
418

419
    return true;
4,912✔
420
  }
421

422
  return false;
5✔
423
}
424

425
////////////////////////////////////////////////////////////////////////////////
426
// Regex       --> Equality {( "~" | "!~" ) Equality}
427
bool Eval::parseRegex(std::vector<std::pair<std::string, Lexer::Type>>& infix,
5,917✔
428
                      unsigned int& i) const {
429
  if (i < infix.size() && parseEquality(infix, i)) {
5,917✔
430
    while (i < infix.size() && infix[i].second == Lexer::Type::op &&
10,008✔
431
           (infix[i].first == "~" || infix[i].first == "!~")) {
3,954✔
432
      ++i;
144✔
433
      if (!parseEquality(infix, i)) return false;
144✔
434
    }
435

436
    return true;
5,910✔
437
  }
438

439
  return false;
7✔
440
}
441

442
////////////////////////////////////////////////////////////////////////////////
443
// Equality    --> Comparative {( "==" | "=" | "!==" | "!=" ) Comparative}
444
bool Eval::parseEquality(std::vector<std::pair<std::string, Lexer::Type>>& infix,
6,061✔
445
                         unsigned int& i) const {
446
  if (i < infix.size() && parseComparative(infix, i)) {
6,061✔
447
    while (i < infix.size() && infix[i].second == Lexer::Type::op &&
12,568✔
448
           (infix[i].first == "==" || infix[i].first == "=" || infix[i].first == "!==" ||
5,234✔
449
            infix[i].first == "!=")) {
3,964✔
450
      ++i;
1,280✔
451
      if (!parseComparative(infix, i)) return false;
1,280✔
452
    }
453

454
    return true;
6,054✔
455
  }
456

457
  return false;
7✔
458
}
459

460
////////////////////////////////////////////////////////////////////////////////
461
// Comparative --> Arithmetic {( "<=" | "<" | ">=" | ">" ) Arithmetic}
462
bool Eval::parseComparative(std::vector<std::pair<std::string, Lexer::Type>>& infix,
7,341✔
463
                            unsigned int& i) const {
464
  if (i < infix.size() && parseArithmetic(infix, i)) {
7,341✔
465
    while (i < infix.size() && infix[i].second == Lexer::Type::op &&
12,758✔
466
           (infix[i].first == "<=" || infix[i].first == "<" || infix[i].first == ">=" ||
5,329✔
467
            infix[i].first == ">")) {
5,256✔
468
      ++i;
95✔
469
      if (!parseArithmetic(infix, i)) return false;
95✔
470
    }
471

472
    return true;
7,334✔
473
  }
474

475
  return false;
7✔
476
}
477

478
////////////////////////////////////////////////////////////////////////////////
479
// Arithmetic  --> Geometric {( "+" | "-" ) Geometric}
480
bool Eval::parseArithmetic(std::vector<std::pair<std::string, Lexer::Type>>& infix,
7,436✔
481
                           unsigned int& i) const {
482
  if (i < infix.size() && parseGeometric(infix, i)) {
7,436✔
483
    while (i < infix.size() && infix[i].second == Lexer::Type::op &&
13,238✔
484
           (infix[i].first == "+" || infix[i].first == "-")) {
5,569✔
485
      ++i;
240✔
486
      if (!parseGeometric(infix, i)) return false;
240✔
487
    }
488

489
    return true;
7,429✔
490
  }
491

492
  return false;
3✔
493
}
494

495
////////////////////////////////////////////////////////////////////////////////
496
// Geometric   --> Tag {( "*" | "/" | "%" ) Tag}
497
bool Eval::parseGeometric(std::vector<std::pair<std::string, Lexer::Type>>& infix,
7,676✔
498
                          unsigned int& i) const {
499
  if (i < infix.size() && parseTag(infix, i)) {
7,676✔
500
    while (i < infix.size() && infix[i].second == Lexer::Type::op &&
13,244✔
501
           (infix[i].first == "*" || infix[i].first == "/" || infix[i].first == "%")) {
5,572✔
502
      ++i;
3✔
503
      if (!parseTag(infix, i)) return false;
3✔
504
    }
505

506
    return true;
7,669✔
507
  }
508

509
  return false;
7✔
510
}
511

512
////////////////////////////////////////////////////////////////////////////////
513
// Tag         --> Unary {( "_hastag_" | "_notag_" ) Unary}
514
bool Eval::parseTag(std::vector<std::pair<std::string, Lexer::Type>>& infix,
7,675✔
515
                    unsigned int& i) const {
516
  if (i < infix.size() && parseUnary(infix, i)) {
7,675✔
517
    while (i < infix.size() && infix[i].second == Lexer::Type::op &&
14,580✔
518
           (infix[i].first == "_hastag_" || infix[i].first == "_notag_")) {
6,240✔
519
      ++i;
668✔
520
      if (!parseUnary(infix, i)) return false;
668✔
521
    }
522

523
    return true;
7,672✔
524
  }
525

526
  return false;
3✔
527
}
528

529
////////////////////////////////////////////////////////////////////////////////
530
// Unary       --> [( "-" | "+" | "!" )] Exponent
531
bool Eval::parseUnary(std::vector<std::pair<std::string, Lexer::Type>>& infix,
8,343✔
532
                      unsigned int& i) const {
533
  if (i < infix.size()) {
8,343✔
534
    if (infix[i].first == "-") {
8,343✔
535
      infix[i].first = "_neg_";
26✔
536
      ++i;
26✔
537
    } else if (infix[i].first == "+") {
8,317✔
538
      infix[i].first = "_pos_";
×
539
      ++i;
×
540
    } else if (infix[i].first == "!") {
8,317✔
541
      ++i;
2✔
542
    }
543
  }
544

545
  return parseExponent(infix, i);
8,343✔
546
}
547

548
////////////////////////////////////////////////////////////////////////////////
549
// Exponent    --> Primitive ["^" Primitive]
550
bool Eval::parseExponent(std::vector<std::pair<std::string, Lexer::Type>>& infix,
8,343✔
551
                         unsigned int& i) const {
552
  if (i < infix.size() && parsePrimitive(infix, i)) {
8,343✔
553
    while (i < infix.size() && infix[i].second == Lexer::Type::op && infix[i].first == "^") {
8,340✔
554
      ++i;
×
555
      if (!parsePrimitive(infix, i)) return false;
×
556
    }
557

558
    return true;
8,340✔
559
  }
560

561
  return false;
3✔
562
}
563

564
////////////////////////////////////////////////////////////////////////////////
565
// Primitive   --> "(" Logical ")" | Variant
566
bool Eval::parsePrimitive(std::vector<std::pair<std::string, Lexer::Type>>& infix,
8,343✔
567
                          unsigned int& i) const {
568
  if (i < infix.size()) {
8,343✔
569
    if (infix[i].first == "(") {
8,343✔
570
      ++i;
2,807✔
571
      if (i < infix.size() && parseLogical(infix, i)) {
2,807✔
572
        if (i < infix.size() && infix[i].first == ")") {
2,807✔
573
          ++i;
2,804✔
574
          return true;
2,804✔
575
        }
576
      }
577
    } else {
578
      bool found = false;
5,536✔
579
      for (const auto& source : _sources) {
16,584✔
580
        Variant v;
11,070✔
581
        if (source(infix[i].first, v)) {
11,070✔
582
          found = true;
22✔
583
          break;
22✔
584
        }
585
      }
11,070✔
586

587
      if (found) {
5,536✔
588
        ++i;
22✔
589
        return true;
22✔
590
      } else if (infix[i].second != Lexer::Type::op) {
5,514✔
591
        ++i;
5,514✔
592
        return true;
5,514✔
593
      }
594
    }
595
  }
596

597
  return false;
3✔
598
}
599

600
////////////////////////////////////////////////////////////////////////////////
601
// Dijkstra Shunting Algorithm.
602
// https://en.wikipedia.org/wiki/Shunting-yard_algorithm
603
//
604
//   While there are tokens to be read:
605
//     Read a token.
606
//     If the token is an operator, o1, then:
607
//       while there is an operator token, o2, at the top of the stack, and
608
//             either o1 is left-associative and its precedence is less than or
609
//             equal to that of o2,
610
//             or o1 is right-associative and its precedence is less than that
611
//             of o2,
612
//         pop o2 off the stack, onto the output queue;
613
//       push o1 onto the stack.
614
//     If the token is a left parenthesis, then push it onto the stack.
615
//     If the token is a right parenthesis:
616
//       Until the token at the top of the stack is a left parenthesis, pop
617
//       operators off the stack onto the output queue.
618
//       Pop the left parenthesis from the stack, but not onto the output queue.
619
//       If the token at the top of the stack is a function token, pop it onto
620
//       the output queue.
621
//       If the stack runs out without finding a left parenthesis, then there
622
//       are mismatched parentheses.
623
//     If the token is a number, then add it to the output queue.
624
//
625
//   When there are no more tokens to read:
626
//     While there are still operator tokens in the stack:
627
//       If the operator token on the top of the stack is a parenthesis, then
628
//       there are mismatched parentheses.
629
//       Pop the operator onto the output queue.
630
//   Exit.
631
//
632
void Eval::infixToPostfix(std::vector<std::pair<std::string, Lexer::Type>>& infix) const {
2,112✔
633
  // Short circuit.
634
  if (infix.size() == 1) return;
2,112✔
635

636
  // Result.
637
  std::vector<std::pair<std::string, Lexer::Type>> postfix;
1,496✔
638

639
  // Shunting yard.
640
  std::vector<std::pair<std::string, Lexer::Type>> op_stack;
1,496✔
641

642
  // Operator characteristics.
643
  char type;
644
  unsigned int precedence;
645
  char associativity;
646

647
  for (auto& token : infix) {
15,525✔
648
    if (token.second == Lexer::Type::op && token.first == "(") {
14,029✔
649
      op_stack.push_back(token);
2,827✔
650
    } else if (token.second == Lexer::Type::op && token.first == ")") {
11,202✔
651
      while (op_stack.size() && op_stack.back().first != "(") {
4,958✔
652
        postfix.push_back(op_stack.back());
2,132✔
653
        op_stack.pop_back();
2,132✔
654
      }
655

656
      if (op_stack.size())
2,826✔
657
        op_stack.pop_back();
2,826✔
658
      else
659
        throw std::string("Mismatched parentheses in expression");
×
660
    } else if (token.second == Lexer::Type::op &&
11,832✔
661
               identifyOperator(token.first, type, precedence, associativity)) {
3,456✔
662
      char type2;
663
      unsigned int precedence2;
664
      char associativity2;
665
      while (op_stack.size() > 0 &&
7,858✔
666
             identifyOperator(op_stack.back().first, type2, precedence2, associativity2) &&
7,858✔
667
             ((associativity == 'l' && precedence <= precedence2) ||
3,638✔
668
              (associativity == 'r' && precedence < precedence2))) {
2,874✔
669
        postfix.push_back(op_stack.back());
764✔
670
        op_stack.pop_back();
764✔
671
      }
672

673
      op_stack.push_back(token);
3,456✔
674
    } else {
675
      postfix.push_back(token);
4,920✔
676
    }
677
  }
678

679
  while (op_stack.size()) {
2,056✔
680
    if (op_stack.back().first == "(" || op_stack.back().first == ")")
561✔
681
      throw std::string("Mismatched parentheses in expression");
3✔
682

683
    postfix.push_back(op_stack.back());
560✔
684
    op_stack.pop_back();
560✔
685
  }
686

687
  infix = postfix;
1,495✔
688
}
1,497✔
689

690
////////////////////////////////////////////////////////////////////////////////
691
bool Eval::identifyOperator(const std::string& op, char& type, unsigned int& precedence,
7,094✔
692
                            char& associativity) const {
693
  for (const auto& opr : operators) {
135,598✔
694
    if (opr.op == op) {
135,598✔
695
      type = opr.type;
7,094✔
696
      precedence = opr.precedence;
7,094✔
697
      associativity = opr.associativity;
7,094✔
698
      return true;
7,094✔
699
    }
700
  }
701

702
  return false;
×
703
}
704

705
////////////////////////////////////////////////////////////////////////////////
706
std::string Eval::dump(std::vector<std::pair<std::string, Lexer::Type>>& tokens) const {
9✔
707
  // Set up a color mapping.
708
  std::map<Lexer::Type, Color> color_map;
9✔
709
  color_map[Lexer::Type::op] = Color("gray14 on gray6");
18✔
710
  color_map[Lexer::Type::number] = Color("rgb530 on gray6");
18✔
711
  color_map[Lexer::Type::hex] = Color("rgb303 on gray6");
18✔
712
  color_map[Lexer::Type::string] = Color("rgb550 on gray6");
18✔
713
  color_map[Lexer::Type::dom] = Color("rgb045 on gray6");
18✔
714
  color_map[Lexer::Type::identifier] = Color("rgb035 on gray6");
18✔
715
  color_map[Lexer::Type::date] = Color("rgb150 on gray6");
18✔
716
  color_map[Lexer::Type::duration] = Color("rgb531 on gray6");
9✔
717

718
  std::string output;
9✔
719
  for (auto i = tokens.begin(); i != tokens.end(); ++i) {
60✔
720
    if (i != tokens.begin()) output += ' ';
51✔
721

722
    Color c;
51✔
723
    if (color_map[i->second].nontrivial())
51✔
724
      c = color_map[i->second];
51✔
725
    else
726
      c = Color("rgb000 on gray6");
×
727

728
    output += c.colorize(i->first);
51✔
729
  }
730

731
  return output;
18✔
732
}
9✔
733

734
////////////////////////////////////////////////////////////////////////////////
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc