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