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(user_error() << 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(user_error()
  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(user_error()
  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(user_error()
 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(user_error() << 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(user_error() << msg_info(
 212                                 L"Unhandled variable type of " + variable_name
 213                                 + at_position(cursor, str)));
 214 }
 215
 216 struct op
 217 {
 218         enum class 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         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::op_type::BINARY);
 254                 case L'*':
 255                 case L'/':
 256                 case L'%':
 257                         ++cursor;
 258                         return op(ch, 5, op::op_type::BINARY);
 259                 case L'?':
 260                 case L':':
 261                         ++cursor;
 262                         return op(ch, 15, op::op_type::TERNARY);
 263                 case L'-':
 264                         if (first == L'-')
 265                                 CASPAR_THROW_EXCEPTION(user_error() << 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(user_error() << 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(user_error() << 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(user_error() << 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::op_type::BINARY);
 304                         }
 305                         else if (first == L'!')
 306                         {
 307                                 ++cursor;
 308                                 return op(L"!=", 9, op::op_type::BINARY);
 309                         }
 310                         else if (first == L'>')
 311                         {
 312                                 ++cursor;
 313                                 return op(L">=", 8, op::op_type::BINARY);
 314                         }
 315                         else if (first == L'<')
 316                         {
 317                                 ++cursor;
 318                                 return op(L"<=", 8, op::op_type::BINARY);
 319                         }
 320                         else if (first == NONE)
 321                         {
 322                                 ++cursor;
 323                                 first = L'=';
 324                         }
 325                         else
 326                                 CASPAR_THROW_EXCEPTION(user_error() << 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::op_type::BINARY);
 335                         }
 336                         else if (first == NONE)
 337                         {
 338                                 ++cursor;
 339                                 first = L'|';
 340                         }
 341                         else
 342                                 CASPAR_THROW_EXCEPTION(user_error() << 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::op_type::BINARY);
 351                         }
 352                         else if (first == NONE)
 353                         {
 354                                 ++cursor;
 355                                 first = L'&';
 356                         }
 357                         else
 358                                 CASPAR_THROW_EXCEPTION(user_error() << 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::op_type::BINARY);
 366                         else if (first == L'!')
 367                                 return op(L'!', 3, op::op_type::UNARY);
 368                 default:
 369                         if (first == L'<')
 370                                 return op(L'<', 8, op::op_type::BINARY);
 371                         else if (first == L'>')
 372                                 return op(L'>', 8, op::op_type::BINARY);
 373                         else if (first == L'-')
 374                                 return op(L"unary-", 3, op::op_type::UNARY);
 375                         else if (first == L'!')
 376                                 return op(L'!', 3, op::op_type::UNARY);
 377                         else
 378                                 CASPAR_THROW_EXCEPTION(user_error() << msg_info(
 379                                                 L"Expected second character of operator"
 380                                                 + at_position(cursor, str)));
 381                 }
 382         }
 383
 384         CASPAR_THROW_EXCEPTION(user_error() << msg_info(
 385                         L"Unexpected end of input (Expected operator) in " + str));
 386 }
 387
 388 boost::any as_binding(const boost::any& value)
 389 {
 390         // Wrap supported constants as bindings
 391         if (is<double>(value))
 392                 return binding<double>(as<double>(value));
 393         else if (is<bool>(value))
 394                 return binding<bool>(as<bool>(value));
 395         else if (is<std::wstring>(value))
 396                 return binding<std::wstring>(as<std::wstring>(value));
 397         // Already one of the supported binding types
 398         else if (is<binding<double>>(value))
 399                 return as<binding<double>>(value);
 400         else if (is<binding<bool>>(value))
 401                 return as<binding<bool>>(value);
 402         else if (is<binding<std::wstring>>(value))
 403                 return as<binding<std::wstring>>(value);
 404         else
 405                 CASPAR_THROW_EXCEPTION(user_error() << msg_info(
 406                                 L"Couldn't detect type of " + u16(value.type().name())));
 407 }
 408
 409 template<typename T>
 410 binding<T> require(const boost::any& value)
 411 {
 412         auto b = as_binding(value);
 413
 414         if (is<binding<T>>(b))
 415                 return as<binding<T>>(b);
 416         else
 417                 CASPAR_THROW_EXCEPTION(user_error() << msg_info(
 418                                 L"Required binding of type " + u16(typeid(T).name())
 419                                 + L" but got " + u16(value.type().name())));
 420 }
 421
 422 boost::any negative(const boost::any& to_create_negative_of)
 423 {
 424         return -require<double>(to_create_negative_of);
 425 }
 426
 427 boost::any not_(const boost::any& to_create_not_of)
 428 {
 429         return !require<bool>(to_create_not_of);
 430 }
 431
 432 boost::any multiply(const boost::any& lhs, boost::any& rhs)
 433 {
 434         return require<double>(lhs) * require<double>(rhs);
 435 }
 436
 437 boost::any divide(const boost::any& lhs, boost::any& rhs)
 438 {
 439         return require<double>(lhs) / require<double>(rhs);
 440 }
 441
 442 boost::any modulus(const boost::any& lhs, boost::any& rhs)
 443 {
 444         return
 445                         (
 446                                         require<double>(lhs).as<int64_t>()
 447                                         % require<double>(rhs).as<int64_t>()
 448                         ).as<double>();
 449 }
 450
 451 binding<std::wstring> stringify(const boost::any& value)
 452 {
 453         auto b = as_binding(value);
 454
 455         if (is<binding<std::wstring>>(b))
 456                 return as<binding<std::wstring>>(b);
 457         else if (is<binding<double>>(b))
 458                 return as<binding<double>>(b).as<std::wstring>();
 459         else if (is<binding<bool>>(b))
 460                 return as<binding<bool>>(b).as<std::wstring>();
 461         else
 462                 CASPAR_THROW_EXCEPTION(user_error()
 463                                 << msg_info(L"Couldn't stringify " + u16(value.type().name())));
 464 }
 465
 466 boost::any add(const boost::any& lhs, boost::any& rhs)
 467 {
 468         auto l = as_binding(lhs);
 469         auto r = as_binding(rhs);
 470
 471         // number
 472         if (is<binding<double>>(l) && is<binding<double>>(r))
 473                 return as<binding<double>>(l) + as<binding<double>>(r);
 474         // string
 475         else if (is<binding<std::wstring>>(l) && is<binding<std::wstring>>(r))
 476                 return as<binding<std::wstring>>(l) + as<binding<std::wstring>>(r);
 477         // mixed types to string and concatenated
 478         else
 479                 return stringify(lhs) + stringify(rhs);
 480 }
 481
 482 boost::any subtract(const boost::any& lhs, boost::any& rhs)
 483 {
 484         return require<double>(lhs) - require<double>(rhs);
 485 }
 486
 487 boost::any less(const boost::any& lhs, boost::any& rhs)
 488 {
 489         return require<double>(lhs) < require<double>(rhs);
 490 }
 491
 492 boost::any less_or_equal(const boost::any& lhs, boost::any& rhs)
 493 {
 494         return require<double>(lhs) <= require<double>(rhs);
 495 }
 496
 497 boost::any greater(const boost::any& lhs, boost::any& rhs)
 498 {
 499         return require<double>(lhs) > require<double>(rhs);
 500 }
 501
 502 boost::any greater_or_equal(const boost::any& lhs, boost::any& rhs)
 503 {
 504         return require<double>(lhs) >= require<double>(rhs);
 505 }
 506
 507 boost::any equal(const boost::any& lhs, boost::any& rhs)
 508 {
 509         auto l = as_binding(lhs);
 510         auto r = as_binding(rhs);
 511
 512         // number
 513         if (is<binding<double>>(l) && is<binding<double>>(r))
 514                 return as<binding<double>>(l) == as<binding<double>>(r);
 515         // string
 516         else if (is<binding<std::wstring>>(l) && is<binding<std::wstring>>(r))
 517                 return as<binding<std::wstring>>(l) == as<binding<std::wstring>>(r);
 518         // boolean
 519         else
 520                 return require<bool>(l) == require<bool>(r);
 521 }
 522
 523 boost::any and_(const boost::any& lhs, boost::any& rhs)
 524 {
 525         return require<bool>(lhs) && require<bool>(rhs);
 526 }
 527
 528 boost::any or_(const boost::any& lhs, boost::any& rhs)
 529 {
 530         return require<bool>(lhs) || require<bool>(rhs);
 531 }
 532
 533 template<typename T>
 534 binding<T> ternary(
 535                 const binding<bool>& condition,
 536                 const binding<T>& true_value,
 537                 const binding<T>& false_value)
 538 {
 539         return when(condition).then(true_value).otherwise(false_value);
 540 }
 541
 542 boost::any ternary(
 543                 const boost::any& condition,
 544                 const boost::any& true_value,
 545                 const boost::any& false_value)
 546 {
 547         auto cond = require<bool>(condition);
 548         auto t = as_binding(true_value);
 549         auto f = as_binding(false_value);
 550
 551         // double
 552         if (is<binding<double>>(t) && is<binding<double>>(f))
 553                 return ternary(cond, as<binding<double>>(t), as<binding<double>>(f));
 554         // string
 555         else if (is<binding<std::wstring>>(t) && is<binding<std::wstring>>(f))
 556                 return ternary(
 557                                 cond,
 558                                 as<binding<std::wstring>>(t),
 559                                 as<binding<std::wstring>>(f));
 560         // bool
 561         else
 562                 return ternary(cond, require<bool>(t), require<bool>(f));
 563 }
 564
 565 void resolve_operators(int precedence, std::vector<boost::any>& tokens)
 566 {
 567         for (int i = 0; i < tokens.size(); ++i)
 568         {
 569                 auto& token = tokens.at(i);
 570
 571                 if (!is<op>(token))
 572                         continue;
 573
 574                 auto op_token = as<op>(token);
 575
 576                 if (op_token.precedence != precedence)
 577                         continue;
 578
 579                 int index_after = i + 1;
 580                 auto& token_after = tokens.at(index_after);
 581
 582                 switch (op_token.type)
 583                 {
 584                 case op::op_type::UNARY:
 585                         if (op_token.characters == L"unary-")
 586                         {
 587                                 tokens.at(i) = negative(token_after);
 588                         }
 589                         else if (op_token.characters == L"!")
 590                         {
 591                                 tokens.at(i) = not_(token_after);
 592                         }
 593
 594                         tokens.erase(tokens.begin() + index_after);
 595
 596                         break;
 597                 case op::op_type::BINARY:
 598                         {
 599                                 auto& token_before = tokens.at(i - 1);
 600
 601                                 if (op_token.characters == L"*")
 602                                         token_before = multiply(token_before, token_after);
 603                                 else if (op_token.characters == L"/")
 604                                         token_before = divide(token_before, token_after);
 605                                 else if (op_token.characters == L"%")
 606                                         token_before = modulus(token_before, token_after);
 607                                 else if (op_token.characters == L"+")
 608                                         token_before = add(token_before, token_after);
 609                                 else if (op_token.characters == L"-")
 610                                         token_before = subtract(token_before, token_after);
 611                                 else if (op_token.characters == L"<")
 612                                         token_before = less(token_before, token_after);
 613                                 else if (op_token.characters == L"<=")
 614                                         token_before = less_or_equal(token_before, token_after);
 615                                 else if (op_token.characters == L">")
 616                                         token_before = greater(token_before, token_after);
 617                                 else if (op_token.characters == L">=")
 618                                         token_before = greater_or_equal(token_before, token_after);
 619                                 else if (op_token.characters == L"==")
 620                                         token_before = equal(token_before, token_after);
 621                                 else if (op_token.characters == L"!=")
 622                                         token_before = not_(equal(token_before, token_after));
 623                                 else if (op_token.characters == L"&&")
 624                                         token_before = and_(token_before, token_after);
 625                                 else if (op_token.characters == L"||")
 626                                         token_before = or_(token_before, token_after);
 627                         }
 628
 629                         tokens.erase(tokens.begin() + i, tokens.begin() + i + 2);
 630                         --i;
 631
 632                         break;
 633                 case op::op_type::TERNARY:
 634                         if (op_token.characters == L"?")
 635                         {
 636                                 auto& token_before = tokens.at(i - 1);
 637                                 auto& token_colon_operator = tokens.at(i + 2);
 638
 639                                 if (as<op>(token_colon_operator).characters != L":")
 640                                         CASPAR_THROW_EXCEPTION(user_error() << msg_info(
 641                                                         L"Expected : as part of ternary expression"));
 642
 643                                 auto& token_false_value = tokens.at(i + 3);
 644                                 token_before = ternary(
 645                                                 token_before, token_after, token_false_value);
 646                                 tokens.erase(tokens.begin() + i, tokens.begin() + i + 4);
 647                                 --i;
 648                         }
 649
 650                         break;
 651                 }
 652         }
 653 }
 654
 655 boost::any parse_expression(
 656                 std::wstring::const_iterator& cursor,
 657                 const std::wstring& str,
 658                 const variable_repository& var_repo)
 659 {
 660         std::vector<boost::any> tokens;
 661         bool stop = false;
 662
 663         while (cursor != str.end())
 664         {
 665                 wchar_t ch = next_non_whitespace(cursor, str, L"Expected expression");
 666
 667                 switch (ch)
 668                 {
 669                 case L'0':
 670                 case L'1':
 671                 case L'2':
 672                 case L'3':
 673                 case L'4':
 674                 case L'5':
 675                 case L'6':
 676                 case L'7':
 677                 case L'8':
 678                 case L'9':
 679                         tokens.push_back(parse_constant(cursor, str));
 680                         break;
 681                 case L'+':
 682                 case L'-':
 683                 case L'*':
 684                 case L'/':
 685                 case L'%':
 686                 case L'<':
 687                 case L'>':
 688                 case L'!':
 689                 case L'=':
 690                 case L'|':
 691                 case L'&':
 692                 case L'?':
 693                 case L':':
 694                         tokens.push_back(parse_operator(cursor, str));
 695                         break;
 696                 case L'"':
 697                         tokens.push_back(parse_string_literal(cursor, str));
 698                         break;
 699                 case L'(':
 700                         tokens.push_back(parse_parenthesis(cursor, str, var_repo));
 701                         break;
 702                 case L')':
 703                         stop = true;
 704                         break;
 705                 default:
 706                         tokens.push_back(parse_variable(cursor, str, var_repo));
 707                         break;
 708                 }
 709
 710                 if (stop)
 711                         break;
 712         }
 713
 714         if (tokens.empty())
 715                 CASPAR_THROW_EXCEPTION(user_error()
 716                                 << msg_info(L"Expected expression"));
 717
 718         int precedence = 1;
 719
 720         while (tokens.size() > 1)
 721         {
 722                 resolve_operators(precedence++, tokens);
 723         }
 724
 725         return as_binding(tokens.at(0));
 726 }
 727
 728 }}}