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