git.sesse.net Git - casparcg/blob - core/producer/scene/expression_parser.cpp

   1 /*
   2 * Copyright (c) 2011 Sveriges Television AB <info@casparcg.com>
   3 *
   4 * This file is part of CasparCG (www.casparcg.com).
   5 *
   6 * CasparCG is free software: you can redistribute it and/or modify
   7 * it under the terms of the GNU General Public License as published by
   8 * the Free Software Foundation, either version 3 of the License, or
   9 * (at your option) any later version.
  10 *
  11 * CasparCG is distributed in the hope that it will be useful,
  12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 * GNU General Public License for more details.
  15 *
  16 * You should have received a copy of the GNU General Public License
  17 * along with CasparCG. If not, see <http://www.gnu.org/licenses/>.
  18 *
  19 * Author: Helge Norberg, helge.norberg@svt.se
  20 */
  21
  22 #include "../../stdafx.h"
  23
  24 #include "expression_parser.h"
  25
  26 #include <string>
  27 #include <memory>
  28 #include <vector>
  29 #include <functional>
  30 #include <typeinfo>
  31
  32 #include <boost/any.hpp>
  33
  34 #include <common/log.h>
  35 #include <common/except.h>
  36 #include <common/utf.h>
  37
  38 namespace caspar { namespace core { namespace scene {
  39
  40 wchar_t next_non_whitespace(
  41                 std::wstring::const_iterator& cursor,
  42                 const std::wstring& str,
  43                 const std::wstring& error_if_eof)
  44 {
  45         while (cursor != str.end())
  46         {
  47                 switch (*cursor)
  48                 {
  49                 case L' ':
  50                 case L'\t':
  51                         ++cursor;
  52                         continue;
  53                 default:
  54                         return *cursor;
  55                 }
  56         }
  57
  58         CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
  59                         L"Unexpected end of input (" + error_if_eof + L") in " + str));
  60 }
  61
  62 std::wstring at_position(
  63                 const std::wstring::const_iterator& cursor, const std::wstring& str)
  64 {
  65         int index = static_cast<int>(cursor - str.begin());
  66
  67         return L" at index " + boost::lexical_cast<std::wstring>(index)
  68                         + L" in " + str;
  69 }
  70
  71 boost::any parse_expression(
  72                 std::wstring::const_iterator& cursor,
  73                 const std::wstring& str,
  74                 const variable_repository& var_repo);
  75
  76 boost::any parse_parenthesis(
  77                 std::wstring::const_iterator& cursor,
  78                 const std::wstring& str,
  79                 const variable_repository& var_repo)
  80 {
  81         if (*cursor++ != L'(')
  82                 CASPAR_THROW_EXCEPTION(caspar_exception()
  83                                 << msg_info(L"Expected (" + at_position(cursor, str)));
  84
  85         auto expr = parse_expression(cursor, str, var_repo);
  86
  87         if (*cursor++ != L')')
  88                 CASPAR_THROW_EXCEPTION(caspar_exception()
  89                                 << msg_info(L"Expected )" + at_position(cursor, str)));
  90
  91         return expr;
  92 }
  93
  94 double parse_constant(
  95                 std::wstring::const_iterator& cursor, const std::wstring& str)
  96 {
  97         std::wstring constant;
  98
  99         while (cursor != str.end())
 100         {
 101                 wchar_t ch = *cursor;
 102
 103                 if ((ch >= L'0' && ch <= L'9') || ch == L'.')
 104                         constant += ch;
 105                 else
 106                         break;
 107
 108                 ++cursor;
 109         }
 110
 111         return boost::lexical_cast<double>(constant);
 112 }
 113
 114 std::wstring parse_string_literal(
 115                 std::wstring::const_iterator& cursor, const std::wstring& str)
 116 {
 117         std::wstring literal;
 118
 119         if (*cursor++ != L'"')
 120                 CASPAR_THROW_EXCEPTION(caspar_exception()
 121                                 << msg_info(L"Expected (" + at_position(cursor, str)));
 122
 123         bool escaping = false;
 124
 125         while (cursor != str.end())
 126         {
 127                 wchar_t ch = *cursor;
 128
 129                 switch (ch)
 130                 {
 131                 case L'\\':
 132                         if (escaping)
 133                         {
 134                                 literal += ch;
 135                                 escaping = false;
 136                         }
 137                         else
 138                                 escaping = true;
 139                         break;
 140                 case L'"':
 141                         if (escaping)
 142                         {
 143                                 literal += ch;
 144                                 escaping = false;
 145                                 break;
 146                         }
 147                         else
 148                         {
 149                                 ++cursor;
 150                                 return std::move(literal);
 151                         }
 152                 case L'n':
 153                         if (escaping)
 154                         {
 155                                 literal += L'\n';
 156                                 escaping = false;
 157                         }
 158                         else
 159                                 literal += ch;
 160                         break;
 161                 default:
 162                         literal += ch;
 163                 }
 164
 165                 ++cursor;
 166         }
 167
 168         CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 169                         L"Unexpected end of input (Expected closing \") in " + str));
 170 }
 171
 172 boost::any parse_variable(
 173                 std::wstring::const_iterator& cursor,
 174                 const std::wstring& str,
 175                 const variable_repository& var_repo)
 176 {
 177         std::wstring variable_name;
 178
 179         while (cursor != str.end())
 180         {
 181                 wchar_t ch = *cursor;
 182
 183                 if (ch == L'.'
 184                                 || ch == L'_'
 185                                 || (ch >= L'a' && ch <= L'z')
 186                                 || (ch >= L'A' && ch <= L'Z'))
 187                         variable_name += ch;
 188                 else
 189                         break;
 190
 191                 ++cursor;
 192         }
 193
 194         if (variable_name == L"true")
 195                 return true;
 196         else if (variable_name == L"false")
 197                 return false;
 198
 199         variable& var = var_repo(variable_name);
 200
 201         if (var.is<double>())
 202                 return var.as<double>();
 203         else if (var.is<int64_t>())
 204                 return var.as<int64_t>().as<double>();
 205         else if (var.is<std::wstring>())
 206                 return var.as<std::wstring>();
 207         else if (var.is<bool>())
 208                 return var.as<bool>();
 209
 210         CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 211                                 L"Unhandled variable type of " + variable_name
 212                                 + at_position(cursor, str)));
 213 }
 214
 215 struct op
 216 {
 217         enum op_type
 218         {
 219                 UNARY,
 220                 BINARY,
 221                 TERNARY
 222         };
 223
 224         std::wstring characters;
 225         int precedence;
 226         op_type type;
 227
 228         op(wchar_t ch, int precedence, op_type type)
 229                 : characters(1, ch), precedence(precedence), type(type)
 230         {
 231         }
 232
 233         op(const std::wstring& chs, int precedence, op_type type)
 234                 : characters(chs), precedence(precedence), type(type)
 235         {
 236         }
 237 };
 238
 239 op parse_operator(std::wstring::const_iterator& cursor, const std::wstring& str)
 240 {
 241         std::wstring characters;
 242         static const wchar_t NONE = L' ';
 243         wchar_t first = NONE;
 244
 245         while (cursor != str.end())
 246         {
 247                 wchar_t ch = *cursor;
 248
 249                 switch (ch)
 250                 {
 251                 case L'+':
 252                         ++cursor;
 253                         return op(ch, 6, op::BINARY);
 254                 case L'*':
 255                 case L'/':
 256                 case L'%':
 257                         ++cursor;
 258                         return op(ch, 5, op::BINARY);
 259                 case L'?':
 260                 case L':':
 261                         ++cursor;
 262                         return op(ch, 15, op::TERNARY);
 263                 case L'-':
 264                         if (first == L'-')
 265                                 CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 266                                                 L"Did not expect -" + at_position(cursor, str)));
 267                         else
 268                                 first = ch;
 269
 270                         ++cursor;
 271                         break;
 272                 case L'!':
 273                         if (first == L'!')
 274                                 CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 275                                                 L"Did not expect !" + at_position(cursor, str)));
 276                         else
 277                                 first = ch;
 278
 279                         ++cursor;
 280                         break;
 281                 case L'<':
 282                         if (first == L'<')
 283                                 CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 284                                                 L"Did not expect <" + at_position(cursor, str)));
 285                         else
 286                                 first = ch;
 287
 288                         ++cursor;
 289                         break;
 290                 case L'>':
 291                         if (first == L'>')
 292                                 CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 293                                                 L"Did not expect >" + at_position(cursor, str)));
 294                         else
 295                                 first = ch;
 296
 297                         ++cursor;
 298                         break;
 299                 case L'=':
 300                         if (first == L'=')
 301                         {
 302                                 ++cursor;
 303                                 return op(L"==", 9, op::BINARY);
 304                         }
 305                         else if (first == L'!')
 306                         {
 307                                 ++cursor;
 308                                 return op(L"!=", 9, op::BINARY);
 309                         }
 310                         else if (first == L'>')
 311                         {
 312                                 ++cursor;
 313                                 return op(L">=", 8, op::BINARY);
 314                         }
 315                         else if (first == L'<')
 316                         {
 317                                 ++cursor;
 318                                 return op(L"<=", 8, op::BINARY);
 319                         }
 320                         else if (first == NONE)
 321                         {
 322                                 ++cursor;
 323                                 first = L'=';
 324                         }
 325                         else
 326                                 CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 327                                                 L"Did not expect =" + at_position(cursor, str)));
 328
 329                         break;
 330                 case L'|':
 331                         if (first == L'|')
 332                         {
 333                                 ++cursor;
 334                                 return op(L"||", 14, op::BINARY);
 335                         }
 336                         else if (first == NONE)
 337                         {
 338                                 ++cursor;
 339                                 first = L'|';
 340                         }
 341                         else
 342                                 CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 343                                                 L"Did not expect =" + at_position(cursor, str)));
 344
 345                         break;
 346                 case L'&':
 347                         if (first == L'&')
 348                         {
 349                                 ++cursor;
 350                                 return op(L"&&", 13, op::BINARY);
 351                         }
 352                         else if (first == NONE)
 353                         {
 354                                 ++cursor;
 355                                 first = L'&';
 356                         }
 357                         else
 358                                 CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 359                                                 L"Did not expect =" + at_position(cursor, str)));
 360
 361                         break;
 362                 case L' ':
 363                 case L'\t':
 364                         if (first == L'-')
 365                                 return op(L'-', 6, op::BINARY);
 366                         else if (first == L'!')
 367                                 return op(L'!', 3, op::UNARY);
 368                 default:
 369                         if (first == L'<')
 370                                 return op(L'<', 8, op::BINARY);
 371                         else if (first == L'>')
 372                                 return op(L'>', 8, op::BINARY);
 373                         else if (first == L'-')
 374                                 return op(L"unary-", 3, op::UNARY);
 375                         else if (first == L'!')
 376                                 return op(L'!', 3, op::UNARY);
 377                         else
 378                                 CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 379                                                 L"Expected second character of operator"
 380                                                 + at_position(cursor, str)));
 381                 }
 382         }
 383
 384         CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 385                         L"Unexpected end of input (Expected operator) in " + str));
 386 }
 387
 388 template<typename T>
 389 T as(const boost::any& value)
 390 {
 391         return boost::any_cast<T>(value);
 392 }
 393
 394 boost::any as_binding(const boost::any& value)
 395 {
 396         // Wrap supported constants as bindings
 397         if (is<double>(value))
 398                 return binding<double>(as<double>(value));
 399         else if (is<bool>(value))
 400                 return binding<bool>(as<bool>(value));
 401         else if (is<std::wstring>(value))
 402                 return binding<std::wstring>(as<std::wstring>(value));
 403         // Already one of the supported binding types
 404         else if (is<binding<double>>(value))
 405                 return as<binding<double>>(value);
 406         else if (is<binding<bool>>(value))
 407                 return as<binding<bool>>(value);
 408         else if (is<binding<std::wstring>>(value))
 409                 return as<binding<std::wstring>>(value);
 410         else
 411                 CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 412                                 L"Couldn't detect type of " + u16(value.type().name())));
 413 }
 414
 415 template<typename T>
 416 binding<T> require(const boost::any& value)
 417 {
 418         auto b = as_binding(value);
 419
 420         if (is<binding<T>>(b))
 421                 return as<binding<T>>(b);
 422         else
 423                 CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 424                                 L"Required binding of type " + u16(typeid(T).name())
 425                                 + L" but got " + u16(value.type().name())));
 426 }
 427
 428 boost::any negative(const boost::any& to_create_negative_of)
 429 {
 430         return -require<double>(to_create_negative_of);
 431 }
 432
 433 boost::any not(const boost::any& to_create_not_of)
 434 {
 435         return !require<bool>(to_create_not_of);
 436 }
 437
 438 boost::any multiply(const boost::any& lhs, boost::any& rhs)
 439 {
 440         return require<double>(lhs) * require<double>(rhs);
 441 }
 442
 443 boost::any divide(const boost::any& lhs, boost::any& rhs)
 444 {
 445         return require<double>(lhs) / require<double>(rhs);
 446 }
 447
 448 boost::any modulus(const boost::any& lhs, boost::any& rhs)
 449 {
 450         return
 451                         (
 452                                         require<double>(lhs).as<int64_t>()
 453                                         % require<double>(rhs).as<int64_t>()
 454                         ).as<double>();
 455 }
 456
 457 binding<std::wstring> stringify(const boost::any& value)
 458 {
 459         auto b = as_binding(value);
 460
 461         if (is<binding<std::wstring>>(b))
 462                 return as<binding<std::wstring>>(b);
 463         else if (is<binding<double>>(b))
 464                 return as<binding<double>>(b).as<std::wstring>();
 465         else if (is<binding<bool>>(b))
 466                 return as<binding<bool>>(b).as<std::wstring>();
 467         else
 468                 CASPAR_THROW_EXCEPTION(caspar_exception()
 469                                 << msg_info(L"Couldn't stringify " + u16(value.type().name())));
 470 }
 471
 472 boost::any add(const boost::any& lhs, boost::any& rhs)
 473 {
 474         auto l = as_binding(lhs);
 475         auto r = as_binding(rhs);
 476
 477         // number
 478         if (is<binding<double>>(l) && is<binding<double>>(r))
 479                 return as<binding<double>>(l) + as<binding<double>>(r);
 480         // string
 481         else if (is<binding<std::wstring>>(l) && is<binding<std::wstring>>(r))
 482                 return as<binding<std::wstring>>(l) + as<binding<std::wstring>>(r);
 483         // mixed types to string and concatenated
 484         else
 485                 return stringify(lhs) + stringify(rhs);
 486 }
 487
 488 boost::any subtract(const boost::any& lhs, boost::any& rhs)
 489 {
 490         return require<double>(lhs) - require<double>(rhs);
 491 }
 492
 493 boost::any less(const boost::any& lhs, boost::any& rhs)
 494 {
 495         return require<double>(lhs) < require<double>(rhs);
 496 }
 497
 498 boost::any less_or_equal(const boost::any& lhs, boost::any& rhs)
 499 {
 500         return require<double>(lhs) <= require<double>(rhs);
 501 }
 502
 503 boost::any greater(const boost::any& lhs, boost::any& rhs)
 504 {
 505         return require<double>(lhs) > require<double>(rhs);
 506 }
 507
 508 boost::any greater_or_equal(const boost::any& lhs, boost::any& rhs)
 509 {
 510         return require<double>(lhs) >= require<double>(rhs);
 511 }
 512
 513 boost::any equal(const boost::any& lhs, boost::any& rhs)
 514 {
 515         auto l = as_binding(lhs);
 516         auto r = as_binding(rhs);
 517
 518         // number
 519         if (is<binding<double>>(l) && is<binding<double>>(r))
 520                 return as<binding<double>>(l) == as<binding<double>>(r);
 521         // string
 522         else if (is<binding<std::wstring>>(l) && is<binding<std::wstring>>(r))
 523                 return as<binding<std::wstring>>(l) == as<binding<std::wstring>>(r);
 524         // boolean
 525         else
 526                 return require<bool>(l) == require<bool>(r);
 527 }
 528
 529 boost::any and(const boost::any& lhs, boost::any& rhs)
 530 {
 531         return require<bool>(lhs) && require<bool>(rhs);
 532 }
 533
 534 boost::any or(const boost::any& lhs, boost::any& rhs)
 535 {
 536         return require<bool>(lhs) || require<bool>(rhs);
 537 }
 538
 539 template<typename T>
 540 binding<T> ternary(
 541                 const binding<bool>& condition,
 542                 const binding<T>& true_value,
 543                 const binding<T>& false_value)
 544 {
 545         return when(condition).then(true_value).otherwise(false_value);
 546 }
 547
 548 boost::any ternary(
 549                 const boost::any& condition,
 550                 const boost::any& true_value,
 551                 const boost::any& false_value)
 552 {
 553         auto cond = require<bool>(condition);
 554         auto t = as_binding(true_value);
 555         auto f = as_binding(false_value);
 556
 557         // double
 558         if (is<binding<double>>(t) && is<binding<double>>(f))
 559                 return ternary(cond, as<binding<double>>(t), as<binding<double>>(f));
 560         // string
 561         else if (is<binding<std::wstring>>(t) && is<binding<std::wstring>>(f))
 562                 return ternary(
 563                                 cond,
 564                                 as<binding<std::wstring>>(t),
 565                                 as<binding<std::wstring>>(f));
 566         // bool
 567         else
 568                 return ternary(cond, require<bool>(t), require<bool>(f));
 569 }
 570
 571 void resolve_operators(int precedence, std::vector<boost::any>& tokens)
 572 {
 573         for (int i = 0; i < tokens.size(); ++i)
 574         {
 575                 auto& token = tokens.at(i);
 576
 577                 if (!is<op>(token))
 578                         continue;
 579
 580                 auto op_token = as<op>(token);
 581
 582                 if (op_token.precedence != precedence)
 583                         continue;
 584
 585                 int index_after = i + 1;
 586                 auto& token_after = tokens.at(index_after);
 587
 588                 switch (op_token.type)
 589                 {
 590                 case op::UNARY:
 591                         if (op_token.characters == L"unary-")
 592                         {
 593                                 tokens.at(i) = negative(token_after);
 594                         }
 595                         else if (op_token.characters == L"!")
 596                         {
 597                                 tokens.at(i) = not(token_after);
 598                         }
 599
 600                         tokens.erase(tokens.begin() + index_after);
 601
 602                         break;
 603                 case op::BINARY:
 604                         {
 605                                 auto& token_before = tokens.at(i - 1);
 606
 607                                 if (op_token.characters == L"*")
 608                                         token_before = multiply(token_before, token_after);
 609                                 else if (op_token.characters == L"/")
 610                                         token_before = divide(token_before, token_after);
 611                                 else if (op_token.characters == L"%")
 612                                         token_before = modulus(token_before, token_after);
 613                                 else if (op_token.characters == L"+")
 614                                         token_before = add(token_before, token_after);
 615                                 else if (op_token.characters == L"-")
 616                                         token_before = subtract(token_before, token_after);
 617                                 else if (op_token.characters == L"<")
 618                                         token_before = less(token_before, token_after);
 619                                 else if (op_token.characters == L"<=")
 620                                         token_before = less_or_equal(token_before, token_after);
 621                                 else if (op_token.characters == L">")
 622                                         token_before = greater(token_before, token_after);
 623                                 else if (op_token.characters == L">=")
 624                                         token_before = greater_or_equal(token_before, token_after);
 625                                 else if (op_token.characters == L"==")
 626                                         token_before = equal(token_before, token_after);
 627                                 else if (op_token.characters == L"!=")
 628                                         token_before = not(equal(token_before, token_after));
 629                                 else if (op_token.characters == L"&&")
 630                                         token_before = and(token_before, token_after);
 631                                 else if (op_token.characters == L"||")
 632                                         token_before = or(token_before, token_after);
 633                         }
 634
 635                         tokens.erase(tokens.begin() + i, tokens.begin() + i + 2);
 636                         --i;
 637
 638                         break;
 639                 case op::TERNARY:
 640                         if (op_token.characters == L"?")
 641                         {
 642                                 auto& token_before = tokens.at(i - 1);
 643                                 auto& token_colon_operator = tokens.at(i + 2);
 644
 645                                 if (as<op>(token_colon_operator).characters != L":")
 646                                         CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 647                                                         L"Expected : as part of ternary expression"));
 648
 649                                 auto& token_false_value = tokens.at(i + 3);
 650                                 token_before = ternary(
 651                                                 token_before, token_after, token_false_value);
 652                                 tokens.erase(tokens.begin() + i, tokens.begin() + i + 4);
 653                                 --i;
 654                         }
 655
 656                         break;
 657                 }
 658         }
 659 }
 660
 661 boost::any parse_expression(
 662                 std::wstring::const_iterator& cursor,
 663                 const std::wstring& str,
 664                 const variable_repository& var_repo)
 665 {
 666         std::vector<boost::any> tokens;
 667         bool stop = false;
 668
 669         while (cursor != str.end())
 670         {
 671                 wchar_t ch = next_non_whitespace(cursor, str, L"Expected expression");
 672
 673                 switch (ch)
 674                 {
 675                 case L'0':
 676                 case L'1':
 677                 case L'2':
 678                 case L'3':
 679                 case L'4':
 680                 case L'5':
 681                 case L'6':
 682                 case L'7':
 683                 case L'8':
 684                 case L'9':
 685                         tokens.push_back(parse_constant(cursor, str));
 686                         break;
 687                 case L'+':
 688                 case L'-':
 689                 case L'*':
 690                 case L'/':
 691                 case L'%':
 692                 case L'<':
 693                 case L'>':
 694                 case L'!':
 695                 case L'=':
 696                 case L'|':
 697                 case L'&':
 698                 case L'?':
 699                 case L':':
 700                         tokens.push_back(parse_operator(cursor, str));
 701                         break;
 702                 case L'"':
 703                         tokens.push_back(parse_string_literal(cursor, str));
 704                         break;
 705                 case L'(':
 706                         tokens.push_back(parse_parenthesis(cursor, str, var_repo));
 707                         break;
 708                 case L')':
 709                         stop = true;
 710                         break;
 711                 default:
 712                         tokens.push_back(parse_variable(cursor, str, var_repo));
 713                         break;
 714                 }
 715
 716                 if (stop)
 717                         break;
 718         }
 719
 720         if (tokens.empty())
 721                 CASPAR_THROW_EXCEPTION(caspar_exception()
 722                                 << msg_info(L"Expected expression"));
 723
 724         int precedence = 1;
 725
 726         while (tokens.size() > 1)
 727         {
 728                 resolve_operators(precedence++, tokens);
 729         }
 730
 731         return as_binding(tokens.at(0));
 732 }
 733
 734 template<>
 735 binding<std::wstring> parse_expression(
 736                 const std::wstring& str, const variable_repository& var_repo)
 737 {
 738         auto cursor = str.cbegin();
 739         auto expr = parse_expression(cursor, str, var_repo);
 740
 741         if (is<binding<std::wstring>>(expr))
 742                 return as<binding<std::wstring>>(expr);
 743         else if (is<binding<double>>(expr))
 744                 return as<binding<double>>(expr).as<std::wstring>();
 745         else
 746                 CASPAR_THROW_EXCEPTION(caspar_exception() << msg_info(
 747                                 L"parse_expression() Unsupported type "
 748                                 + u16(expr.type().name())));
 749 }
 750
 751 }}}