juce/source/src/maths/juce_Expression.cpp

   1 /*
   2   ==============================================================================
   3
   4    This file is part of the JUCE library - "Jules' Utility Class Extensions"
   5    Copyright 2004-11 by Raw Material Software Ltd.
   6
   7   ------------------------------------------------------------------------------
   8
   9    JUCE can be redistributed and/or modified under the terms of the GNU General
  10    Public License (Version 2), as published by the Free Software Foundation.
  11    A copy of the license is included in the JUCE distribution, or can be found
  12    online at www.gnu.org/licenses.
  13
  14    JUCE is distributed in the hope that it will be useful, but WITHOUT ANY
  15    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  16    A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
  17
  18   ------------------------------------------------------------------------------
  19
  20    To release a closed-source product which uses JUCE, commercial licenses are
  21    available: visit www.rawmaterialsoftware.com/juce for more information.
  22
  23   ==============================================================================
  24 */
  25
  26 #include "../core/juce_StandardHeader.h"
  27
  28 BEGIN_JUCE_NAMESPACE
  29
  30 #include "juce_Expression.h"
  31 #include "../memory/juce_HeapBlock.h"
  32
  33
  34 //==============================================================================
  35 class Expression::Term  : public SingleThreadedReferenceCountedObject
  36 {
  37 public:
  38     Term() {}
  39     virtual ~Term() {}
  40
  41     virtual Type getType() const noexcept = 0;
  42     virtual Term* clone() const = 0;
  43     virtual ReferenceCountedObjectPtr<Term> resolve (const Scope&, int recursionDepth) = 0;
  44     virtual String toString() const = 0;
  45     virtual double toDouble() const                                          { return 0; }
  46     virtual int getInputIndexFor (const Term*) const                         { return -1; }
  47     virtual int getOperatorPrecedence() const                                { return 0; }
  48     virtual int getNumInputs() const                                         { return 0; }
  49     virtual Term* getInput (int) const                                       { return nullptr; }
  50     virtual ReferenceCountedObjectPtr<Term> negated();
  51
  52     virtual ReferenceCountedObjectPtr<Term> createTermToEvaluateInput (const Scope&, const Term* /*inputTerm*/,
  53                                                                              double /*overallTarget*/, Term* /*topLevelTerm*/) const
  54     {
  55         jassertfalse;
  56         return nullptr;
  57     }
  58
  59     virtual String getName() const
  60     {
  61         jassertfalse; // You shouldn't call this for an expression that's not actually a function!
  62         return String::empty;
  63     }
  64
  65     virtual void renameSymbol (const Symbol& oldSymbol, const String& newName, const Scope& scope, int recursionDepth)
  66     {
  67         for (int i = getNumInputs(); --i >= 0;)
  68             getInput (i)->renameSymbol (oldSymbol, newName, scope, recursionDepth);
  69     }
  70
  71     class SymbolVisitor
  72     {
  73     public:
  74         virtual ~SymbolVisitor() {}
  75         virtual void useSymbol (const Symbol&) = 0;
  76     };
  77
  78     virtual void visitAllSymbols (SymbolVisitor& visitor, const Scope& scope, int recursionDepth)
  79     {
  80         for (int i = getNumInputs(); --i >= 0;)
  81             getInput(i)->visitAllSymbols (visitor, scope, recursionDepth);
  82     }
  83
  84 private:
  85     JUCE_DECLARE_NON_COPYABLE (Term);
  86 };
  87
  88
  89 //==============================================================================
  90 class Expression::Helpers
  91 {
  92 public:
  93     typedef ReferenceCountedObjectPtr<Term> TermPtr;
  94
  95     // This helper function is needed to work around VC6 scoping bugs
  96     static inline const TermPtr& getTermFor (const Expression& exp) noexcept      { return exp.term; }
  97
  98     static void checkRecursionDepth (const int depth)
  99     {
 100         if (depth > 256)
 101             throw EvaluationError ("Recursive symbol references");
 102     }
 103
 104     friend class Expression::Term; // (also only needed as a VC6 workaround)
 105
 106     //==============================================================================
 107     /** An exception that can be thrown by Expression::evaluate(). */
 108     class EvaluationError  : public std::exception
 109     {
 110     public:
 111         EvaluationError (const String& description_)
 112             : description (description_)
 113         {
 114             DBG ("Expression::EvaluationError: " + description);
 115         }
 116
 117         String description;
 118     };
 119
 120     //==============================================================================
 121     class Constant  : public Term
 122     {
 123     public:
 124         Constant (const double value_, const bool isResolutionTarget_)
 125             : value (value_), isResolutionTarget (isResolutionTarget_) {}
 126
 127         Type getType() const noexcept                { return constantType; }
 128         Term* clone() const                          { return new Constant (value, isResolutionTarget); }
 129         TermPtr resolve (const Scope&, int)          { return this; }
 130         double toDouble() const                      { return value; }
 131         TermPtr negated()                            { return new Constant (-value, isResolutionTarget); }
 132
 133         String toString() const
 134         {
 135             String s (value);
 136             if (isResolutionTarget)
 137                 s = "@" + s;
 138
 139             return s;
 140         }
 141
 142         double value;
 143         bool isResolutionTarget;
 144     };
 145
 146     //==============================================================================
 147     class BinaryTerm  : public Term
 148     {
 149     public:
 150         BinaryTerm (Term* const left_, Term* const right_) : left (left_), right (right_)
 151         {
 152             jassert (left_ != nullptr && right_ != nullptr);
 153         }
 154
 155         int getInputIndexFor (const Term* possibleInput) const
 156         {
 157             return possibleInput == left ? 0 : (possibleInput == right ? 1 : -1);
 158         }
 159
 160         Type getType() const noexcept       { return operatorType; }
 161         int getNumInputs() const            { return 2; }
 162         Term* getInput (int index) const    { return index == 0 ? left.getObject() : (index == 1 ? right.getObject() : 0); }
 163
 164         virtual double performFunction (double left, double right) const = 0;
 165         virtual void writeOperator (String& dest) const = 0;
 166
 167         TermPtr resolve (const Scope& scope, int recursionDepth)
 168         {
 169             return new Constant (performFunction (left->resolve (scope, recursionDepth)->toDouble(),
 170                                                   right->resolve (scope, recursionDepth)->toDouble()), false);
 171         }
 172
 173         String toString() const
 174         {
 175             String s;
 176
 177             const int ourPrecendence = getOperatorPrecedence();
 178             if (left->getOperatorPrecedence() > ourPrecendence)
 179                 s << '(' << left->toString() << ')';
 180             else
 181                 s = left->toString();
 182
 183             writeOperator (s);
 184
 185             if (right->getOperatorPrecedence() >= ourPrecendence)
 186                 s << '(' << right->toString() << ')';
 187             else
 188                 s << right->toString();
 189
 190             return s;
 191         }
 192
 193     protected:
 194         const TermPtr left, right;
 195
 196         TermPtr createDestinationTerm (const Scope& scope, const Term* input, double overallTarget, Term* topLevelTerm) const
 197         {
 198             jassert (input == left || input == right);
 199             if (input != left && input != right)
 200                 return nullptr;
 201
 202             const Term* const dest = findDestinationFor (topLevelTerm, this);
 203
 204             if (dest == nullptr)
 205                 return new Constant (overallTarget, false);
 206
 207             return dest->createTermToEvaluateInput (scope, this, overallTarget, topLevelTerm);
 208         }
 209     };
 210
 211     //==============================================================================
 212     class SymbolTerm  : public Term
 213     {
 214     public:
 215         explicit SymbolTerm (const String& symbol_) : symbol (symbol_) {}
 216
 217         TermPtr resolve (const Scope& scope, int recursionDepth)
 218         {
 219             checkRecursionDepth (recursionDepth);
 220             return getTermFor (scope.getSymbolValue (symbol))->resolve (scope, recursionDepth + 1);
 221         }
 222
 223         Type getType() const noexcept   { return symbolType; }
 224         Term* clone() const             { return new SymbolTerm (symbol); }
 225         String toString() const         { return symbol; }
 226         String getName() const          { return symbol; }
 227
 228         void visitAllSymbols (SymbolVisitor& visitor, const Scope& scope, int recursionDepth)
 229         {
 230             checkRecursionDepth (recursionDepth);
 231             visitor.useSymbol (Symbol (scope.getScopeUID(), symbol));
 232             getTermFor (scope.getSymbolValue (symbol))->visitAllSymbols (visitor, scope, recursionDepth + 1);
 233         }
 234
 235         void renameSymbol (const Symbol& oldSymbol, const String& newName, const Scope& scope, int /*recursionDepth*/)
 236         {
 237             if (oldSymbol.symbolName == symbol && scope.getScopeUID() == oldSymbol.scopeUID)
 238                 symbol = newName;
 239         }
 240
 241         String symbol;
 242     };
 243
 244     //==============================================================================
 245     class Function  : public Term
 246     {
 247     public:
 248         explicit Function (const String& functionName_)  : functionName (functionName_) {}
 249
 250         Function (const String& functionName_, const Array<Expression>& parameters_)
 251             : functionName (functionName_), parameters (parameters_)
 252         {}
 253
 254         Type getType() const noexcept   { return functionType; }
 255         Term* clone() const             { return new Function (functionName, parameters); }
 256         int getNumInputs() const        { return parameters.size(); }
 257         Term* getInput (int i) const    { return getTermFor (parameters [i]); }
 258         String getName() const          { return functionName; }
 259
 260         TermPtr resolve (const Scope& scope, int recursionDepth)
 261         {
 262             checkRecursionDepth (recursionDepth);
 263             double result = 0;
 264             const int numParams = parameters.size();
 265             if (numParams > 0)
 266             {
 267                 HeapBlock<double> params (numParams);
 268                 for (int i = 0; i < numParams; ++i)
 269                     params[i] = getTermFor (parameters.getReference(i))->resolve (scope, recursionDepth + 1)->toDouble();
 270
 271                 result = scope.evaluateFunction (functionName, params, numParams);
 272             }
 273             else
 274             {
 275                 result = scope.evaluateFunction (functionName, nullptr, 0);
 276             }
 277
 278             return new Constant (result, false);
 279         }
 280
 281         int getInputIndexFor (const Term* possibleInput) const
 282         {
 283             for (int i = 0; i < parameters.size(); ++i)
 284                 if (getTermFor (parameters.getReference(i)) == possibleInput)
 285                     return i;
 286
 287             return -1;
 288         }
 289
 290         String toString() const
 291         {
 292             if (parameters.size() == 0)
 293                 return functionName + "()";
 294
 295             String s (functionName + " (");
 296
 297             for (int i = 0; i < parameters.size(); ++i)
 298             {
 299                 s << getTermFor (parameters.getReference(i))->toString();
 300
 301                 if (i < parameters.size() - 1)
 302                     s << ", ";
 303             }
 304
 305             s << ')';
 306             return s;
 307         }
 308
 309         const String functionName;
 310         Array<Expression> parameters;
 311     };
 312
 313     //==============================================================================
 314     class DotOperator  : public BinaryTerm
 315     {
 316     public:
 317         DotOperator (SymbolTerm* const left_, Term* const right_)  : BinaryTerm (left_, right_) {}
 318
 319         TermPtr resolve (const Scope& scope, int recursionDepth)
 320         {
 321             checkRecursionDepth (recursionDepth);
 322
 323             EvaluationVisitor visitor (right, recursionDepth + 1);
 324             scope.visitRelativeScope (getSymbol()->symbol, visitor);
 325             return visitor.output;
 326         }
 327
 328         Term* clone() const                             { return new DotOperator (getSymbol(), right); }
 329         String getName() const                          { return "."; }
 330         int getOperatorPrecedence() const               { return 1; }
 331         void writeOperator (String& dest) const         { dest << '.'; }
 332         double performFunction (double, double) const   { return 0.0; }
 333
 334         void visitAllSymbols (SymbolVisitor& visitor, const Scope& scope, int recursionDepth)
 335         {
 336             checkRecursionDepth (recursionDepth);
 337             visitor.useSymbol (Symbol (scope.getScopeUID(), getSymbol()->symbol));
 338
 339             SymbolVisitingVisitor v (right, visitor, recursionDepth + 1);
 340
 341             try
 342             {
 343                 scope.visitRelativeScope (getSymbol()->symbol, v);
 344             }
 345             catch (...) {}
 346         }
 347
 348         void renameSymbol (const Symbol& oldSymbol, const String& newName, const Scope& scope, int recursionDepth)
 349         {
 350             checkRecursionDepth (recursionDepth);
 351             getSymbol()->renameSymbol (oldSymbol, newName, scope, recursionDepth);
 352
 353             SymbolRenamingVisitor visitor (right, oldSymbol, newName, recursionDepth + 1);
 354
 355             try
 356             {
 357                 scope.visitRelativeScope (getSymbol()->symbol, visitor);
 358             }
 359             catch (...) {}
 360         }
 361
 362     private:
 363         //==============================================================================
 364         class EvaluationVisitor  : public Scope::Visitor
 365         {
 366         public:
 367             EvaluationVisitor (const TermPtr& input_, const int recursionCount_)
 368                 : input (input_), output (input_), recursionCount (recursionCount_) {}
 369
 370             void visit (const Scope& scope)   { output = input->resolve (scope, recursionCount); }
 371
 372             const TermPtr input;
 373             TermPtr output;
 374             const int recursionCount;
 375
 376         private:
 377             JUCE_DECLARE_NON_COPYABLE (EvaluationVisitor);
 378         };
 379
 380         class SymbolVisitingVisitor  : public Scope::Visitor
 381         {
 382         public:
 383             SymbolVisitingVisitor (const TermPtr& input_, SymbolVisitor& visitor_, const int recursionCount_)
 384                 : input (input_), visitor (visitor_), recursionCount (recursionCount_) {}
 385
 386             void visit (const Scope& scope)   { input->visitAllSymbols (visitor, scope, recursionCount); }
 387
 388         private:
 389             const TermPtr input;
 390             SymbolVisitor& visitor;
 391             const int recursionCount;
 392
 393             JUCE_DECLARE_NON_COPYABLE (SymbolVisitingVisitor);
 394         };
 395
 396         class SymbolRenamingVisitor   : public Scope::Visitor
 397         {
 398         public:
 399             SymbolRenamingVisitor (const TermPtr& input_, const Expression::Symbol& symbol_, const String& newName_, const int recursionCount_)
 400                 : input (input_), symbol (symbol_), newName (newName_), recursionCount (recursionCount_)  {}
 401
 402             void visit (const Scope& scope)   { input->renameSymbol (symbol, newName, scope, recursionCount); }
 403
 404         private:
 405             const TermPtr input;
 406             const Symbol& symbol;
 407             const String newName;
 408             const int recursionCount;
 409
 410             JUCE_DECLARE_NON_COPYABLE (SymbolRenamingVisitor);
 411         };
 412
 413         SymbolTerm* getSymbol() const  { return static_cast <SymbolTerm*> (left.getObject()); }
 414
 415         JUCE_DECLARE_NON_COPYABLE (DotOperator);
 416     };
 417
 418     //==============================================================================
 419     class Negate  : public Term
 420     {
 421     public:
 422         explicit Negate (const TermPtr& input_) : input (input_)
 423         {
 424             jassert (input_ != nullptr);
 425         }
 426
 427         Type getType() const noexcept                           { return operatorType; }
 428         int getInputIndexFor (const Term* possibleInput) const  { return possibleInput == input ? 0 : -1; }
 429         int getNumInputs() const                                { return 1; }
 430         Term* getInput (int index) const                        { return index == 0 ? input.getObject() : nullptr; }
 431         Term* clone() const                                     { return new Negate (input->clone()); }
 432
 433         TermPtr resolve (const Scope& scope, int recursionDepth)
 434         {
 435             return new Constant (-input->resolve (scope, recursionDepth)->toDouble(), false);
 436         }
 437
 438         String getName() const          { return "-"; }
 439         TermPtr negated()               { return input; }
 440
 441         TermPtr createTermToEvaluateInput (const Scope& scope, const Term* input_, double overallTarget, Term* topLevelTerm) const
 442         {
 443             (void) input_;
 444             jassert (input_ == input);
 445
 446             const Term* const dest = findDestinationFor (topLevelTerm, this);
 447
 448             return new Negate (dest == nullptr ? new Constant (overallTarget, false)
 449                                                : dest->createTermToEvaluateInput (scope, this, overallTarget, topLevelTerm));
 450         }
 451
 452         String toString() const
 453         {
 454             if (input->getOperatorPrecedence() > 0)
 455                 return "-(" + input->toString() + ")";
 456             else
 457                 return "-" + input->toString();
 458         }
 459
 460     private:
 461         const TermPtr input;
 462     };
 463
 464     //==============================================================================
 465     class Add  : public BinaryTerm
 466     {
 467     public:
 468         Add (Term* const left_, Term* const right_) : BinaryTerm (left_, right_) {}
 469
 470         Term* clone() const                     { return new Add (left->clone(), right->clone()); }
 471         double performFunction (double lhs, double rhs) const    { return lhs + rhs; }
 472         int getOperatorPrecedence() const       { return 3; }
 473         String getName() const                  { return "+"; }
 474         void writeOperator (String& dest) const { dest << " + "; }
 475
 476         TermPtr createTermToEvaluateInput (const Scope& scope, const Term* input, double overallTarget, Term* topLevelTerm) const
 477         {
 478             const TermPtr newDest (createDestinationTerm (scope, input, overallTarget, topLevelTerm));
 479             if (newDest == nullptr)
 480                 return nullptr;
 481
 482             return new Subtract (newDest, (input == left ? right : left)->clone());
 483         }
 484
 485     private:
 486         JUCE_DECLARE_NON_COPYABLE (Add);
 487     };
 488
 489     //==============================================================================
 490     class Subtract  : public BinaryTerm
 491     {
 492     public:
 493         Subtract (Term* const left_, Term* const right_) : BinaryTerm (left_, right_) {}
 494
 495         Term* clone() const                     { return new Subtract (left->clone(), right->clone()); }
 496         double performFunction (double lhs, double rhs) const    { return lhs - rhs; }
 497         int getOperatorPrecedence() const       { return 3; }
 498         String getName() const                  { return "-"; }
 499         void writeOperator (String& dest) const { dest << " - "; }
 500
 501         TermPtr createTermToEvaluateInput (const Scope& scope, const Term* input, double overallTarget, Term* topLevelTerm) const
 502         {
 503             const TermPtr newDest (createDestinationTerm (scope, input, overallTarget, topLevelTerm));
 504             if (newDest == nullptr)
 505                 return nullptr;
 506
 507             if (input == left)
 508                 return new Add (newDest, right->clone());
 509             else
 510                 return new Subtract (left->clone(), newDest);
 511         }
 512
 513     private:
 514         JUCE_DECLARE_NON_COPYABLE (Subtract);
 515     };
 516
 517     //==============================================================================
 518     class Multiply  : public BinaryTerm
 519     {
 520     public:
 521         Multiply (Term* const left_, Term* const right_) : BinaryTerm (left_, right_) {}
 522
 523         Term* clone() const                     { return new Multiply (left->clone(), right->clone()); }
 524         double performFunction (double lhs, double rhs) const    { return lhs * rhs; }
 525         String getName() const                  { return "*"; }
 526         void writeOperator (String& dest) const { dest << " * "; }
 527         int getOperatorPrecedence() const       { return 2; }
 528
 529         TermPtr createTermToEvaluateInput (const Scope& scope, const Term* input, double overallTarget, Term* topLevelTerm) const
 530         {
 531             const TermPtr newDest (createDestinationTerm (scope, input, overallTarget, topLevelTerm));
 532             if (newDest == nullptr)
 533                 return nullptr;
 534
 535             return new Divide (newDest, (input == left ? right : left)->clone());
 536         }
 537
 538     private:
 539         JUCE_DECLARE_NON_COPYABLE (Multiply);
 540     };
 541
 542     //==============================================================================
 543     class Divide  : public BinaryTerm
 544     {
 545     public:
 546         Divide (Term* const left_, Term* const right_) : BinaryTerm (left_, right_) {}
 547
 548         Term* clone() const                     { return new Divide (left->clone(), right->clone()); }
 549         double performFunction (double lhs, double rhs) const    { return lhs / rhs; }
 550         String getName() const                  { return "/"; }
 551         void writeOperator (String& dest) const { dest << " / "; }
 552         int getOperatorPrecedence() const       { return 2; }
 553
 554         TermPtr createTermToEvaluateInput (const Scope& scope, const Term* input, double overallTarget, Term* topLevelTerm) const
 555         {
 556             const TermPtr newDest (createDestinationTerm (scope, input, overallTarget, topLevelTerm));
 557             if (newDest == nullptr)
 558                 return nullptr;
 559
 560             if (input == left)
 561                 return new Multiply (newDest, right->clone());
 562             else
 563                 return new Divide (left->clone(), newDest);
 564         }
 565
 566     private:
 567         JUCE_DECLARE_NON_COPYABLE (Divide);
 568     };
 569
 570     //==============================================================================
 571     static Term* findDestinationFor (Term* const topLevel, const Term* const inputTerm)
 572     {
 573         const int inputIndex = topLevel->getInputIndexFor (inputTerm);
 574         if (inputIndex >= 0)
 575             return topLevel;
 576
 577         for (int i = topLevel->getNumInputs(); --i >= 0;)
 578         {
 579             Term* const t = findDestinationFor (topLevel->getInput (i), inputTerm);
 580
 581             if (t != nullptr)
 582                 return t;
 583         }
 584
 585         return nullptr;
 586     }
 587
 588     static Constant* findTermToAdjust (Term* const term, const bool mustBeFlagged)
 589     {
 590         {
 591             Constant* const c = dynamic_cast<Constant*> (term);
 592             if (c != nullptr && (c->isResolutionTarget || ! mustBeFlagged))
 593                 return c;
 594         }
 595
 596         if (dynamic_cast<Function*> (term) != nullptr)
 597             return nullptr;
 598
 599         int i;
 600         const int numIns = term->getNumInputs();
 601         for (i = 0; i < numIns; ++i)
 602         {
 603             Constant* const c = dynamic_cast<Constant*> (term->getInput (i));
 604             if (c != nullptr && (c->isResolutionTarget || ! mustBeFlagged))
 605                 return c;
 606         }
 607
 608         for (i = 0; i < numIns; ++i)
 609         {
 610             Constant* const c = findTermToAdjust (term->getInput (i), mustBeFlagged);
 611             if (c != nullptr)
 612                 return c;
 613         }
 614
 615         return nullptr;
 616     }
 617
 618     static bool containsAnySymbols (const Term* const t)
 619     {
 620         if (t->getType() == Expression::symbolType)
 621             return true;
 622
 623         for (int i = t->getNumInputs(); --i >= 0;)
 624             if (containsAnySymbols (t->getInput (i)))
 625                 return true;
 626
 627         return false;
 628     }
 629
 630     //==============================================================================
 631     class SymbolCheckVisitor  : public Term::SymbolVisitor
 632     {
 633     public:
 634         SymbolCheckVisitor (const Symbol& symbol_) : wasFound (false), symbol (symbol_) {}
 635         void useSymbol (const Symbol& s)    { wasFound = wasFound || s == symbol; }
 636
 637         bool wasFound;
 638
 639     private:
 640         const Symbol& symbol;
 641
 642         JUCE_DECLARE_NON_COPYABLE (SymbolCheckVisitor);
 643     };
 644
 645     //==============================================================================
 646     class SymbolListVisitor  : public Term::SymbolVisitor
 647     {
 648     public:
 649         SymbolListVisitor (Array<Symbol>& list_) : list (list_) {}
 650         void useSymbol (const Symbol& s)    { list.addIfNotAlreadyThere (s); }
 651
 652     private:
 653         Array<Symbol>& list;
 654
 655         JUCE_DECLARE_NON_COPYABLE (SymbolListVisitor);
 656     };
 657
 658     //==============================================================================
 659     class Parser
 660     {
 661     public:
 662         //==============================================================================
 663         Parser (String::CharPointerType& stringToParse)
 664             : text (stringToParse)
 665         {
 666         }
 667
 668         TermPtr readUpToComma()
 669         {
 670             if (text.isEmpty())
 671                 return new Constant (0.0, false);
 672
 673             const TermPtr e (readExpression());
 674
 675             if (e == nullptr || ((! readOperator (",")) && ! text.isEmpty()))
 676                 throw ParseError ("Syntax error: \"" + String (text) + "\"");
 677
 678             return e;
 679         }
 680
 681     private:
 682         String::CharPointerType& text;
 683
 684         //==============================================================================
 685         static inline bool isDecimalDigit (const juce_wchar c) noexcept
 686         {
 687             return c >= '0' && c <= '9';
 688         }
 689
 690         bool readChar (const juce_wchar required) noexcept
 691         {
 692             if (*text == required)
 693             {
 694                 ++text;
 695                 return true;
 696             }
 697
 698             return false;
 699         }
 700
 701         bool readOperator (const char* ops, char* const opType = nullptr) noexcept
 702         {
 703             text = text.findEndOfWhitespace();
 704
 705             while (*ops != 0)
 706             {
 707                 if (readChar (*ops))
 708                 {
 709                     if (opType != nullptr)
 710                         *opType = *ops;
 711
 712                     return true;
 713                 }
 714
 715                 ++ops;
 716             }
 717
 718             return false;
 719         }
 720
 721         bool readIdentifier (String& identifier) noexcept
 722         {
 723             text = text.findEndOfWhitespace();
 724             String::CharPointerType t (text);
 725             int numChars = 0;
 726
 727             if (t.isLetter() || *t == '_')
 728             {
 729                 ++t;
 730                 ++numChars;
 731
 732                 while (t.isLetterOrDigit() || *t == '_')
 733                 {
 734                     ++t;
 735                     ++numChars;
 736                 }
 737             }
 738
 739             if (numChars > 0)
 740             {
 741                 identifier = String (text, numChars);
 742                 text = t;
 743                 return true;
 744             }
 745
 746             return false;
 747         }
 748
 749         Term* readNumber() noexcept
 750         {
 751             text = text.findEndOfWhitespace();
 752             String::CharPointerType t (text);
 753
 754             const bool isResolutionTarget = (*t == '@');
 755             if (isResolutionTarget)
 756             {
 757                 ++t;
 758                 t = t.findEndOfWhitespace();
 759                 text = t;
 760             }
 761
 762             if (*t == '-')
 763             {
 764                 ++t;
 765                 t = t.findEndOfWhitespace();
 766             }
 767
 768             if (isDecimalDigit (*t) || (*t == '.' && isDecimalDigit (t[1])))
 769                 return new Constant (CharacterFunctions::readDoubleValue (text), isResolutionTarget);
 770
 771             return nullptr;
 772         }
 773
 774         TermPtr readExpression()
 775         {
 776             TermPtr lhs (readMultiplyOrDivideExpression());
 777
 778             char opType;
 779             while (lhs != nullptr && readOperator ("+-", &opType))
 780             {
 781                 TermPtr rhs (readMultiplyOrDivideExpression());
 782
 783                 if (rhs == nullptr)
 784                     throw ParseError ("Expected expression after \"" + String::charToString (opType) + "\"");
 785
 786                 if (opType == '+')
 787                     lhs = new Add (lhs, rhs);
 788                 else
 789                     lhs = new Subtract (lhs, rhs);
 790             }
 791
 792             return lhs;
 793         }
 794
 795         TermPtr readMultiplyOrDivideExpression()
 796         {
 797             TermPtr lhs (readUnaryExpression());
 798
 799             char opType;
 800             while (lhs != nullptr && readOperator ("*/", &opType))
 801             {
 802                 TermPtr rhs (readUnaryExpression());
 803
 804                 if (rhs == nullptr)
 805                     throw ParseError ("Expected expression after \"" + String::charToString (opType) + "\"");
 806
 807                 if (opType == '*')
 808                     lhs = new Multiply (lhs, rhs);
 809                 else
 810                     lhs = new Divide (lhs, rhs);
 811             }
 812
 813             return lhs;
 814         }
 815
 816         TermPtr readUnaryExpression()
 817         {
 818             char opType;
 819             if (readOperator ("+-", &opType))
 820             {
 821                 TermPtr term (readUnaryExpression());
 822
 823                 if (term == nullptr)
 824                     throw ParseError ("Expected expression after \"" + String::charToString (opType) + "\"");
 825
 826                 if (opType == '-')
 827                     term = term->negated();
 828
 829                 return term;
 830             }
 831
 832             return readPrimaryExpression();
 833         }
 834
 835         TermPtr readPrimaryExpression()
 836         {
 837             TermPtr e (readParenthesisedExpression());
 838             if (e != nullptr)
 839                 return e;
 840
 841             e = readNumber();
 842             if (e != nullptr)
 843                 return e;
 844
 845             return readSymbolOrFunction();
 846         }
 847
 848         TermPtr readSymbolOrFunction()
 849         {
 850             String identifier;
 851             if (readIdentifier (identifier))
 852             {
 853                 if (readOperator ("(")) // method call...
 854                 {
 855                     Function* const f = new Function (identifier);
 856                     ScopedPointer<Term> func (f);  // (can't use ScopedPointer<Function> in MSVC)
 857
 858                     TermPtr param (readExpression());
 859
 860                     if (param == nullptr)
 861                     {
 862                         if (readOperator (")"))
 863                             return func.release();
 864
 865                         throw ParseError ("Expected parameters after \"" + identifier + " (\"");
 866                     }
 867
 868                     f->parameters.add (Expression (param));
 869
 870                     while (readOperator (","))
 871                     {
 872                         param = readExpression();
 873
 874                         if (param == nullptr)
 875                             throw ParseError ("Expected expression after \",\"");
 876
 877                         f->parameters.add (Expression (param));
 878                     }
 879
 880                     if (readOperator (")"))
 881                         return func.release();
 882
 883                     throw ParseError ("Expected \")\"");
 884                 }
 885                 else if (readOperator ("."))
 886                 {
 887                     TermPtr rhs (readSymbolOrFunction());
 888
 889                     if (rhs == nullptr)
 890                         throw ParseError ("Expected symbol or function after \".\"");
 891
 892                     if (identifier == "this")
 893                         return rhs;
 894
 895                     return new DotOperator (new SymbolTerm (identifier), rhs);
 896                 }
 897                 else // just a symbol..
 898                 {
 899                     jassert (identifier.trim() == identifier);
 900                     return new SymbolTerm (identifier);
 901                 }
 902             }
 903
 904             return nullptr;
 905         }
 906
 907         TermPtr readParenthesisedExpression()
 908         {
 909             if (! readOperator ("("))
 910                 return nullptr;
 911
 912             const TermPtr e (readExpression());
 913             if (e == nullptr || ! readOperator (")"))
 914                 return nullptr;
 915
 916             return e;
 917         }
 918
 919         JUCE_DECLARE_NON_COPYABLE (Parser);
 920     };
 921 };
 922
 923 //==============================================================================
 924 Expression::Expression()
 925     : term (new Expression::Helpers::Constant (0, false))
 926 {
 927 }
 928
 929 Expression::~Expression()
 930 {
 931 }
 932
 933 Expression::Expression (Term* const term_)
 934     : term (term_)
 935 {
 936     jassert (term != nullptr);
 937 }
 938
 939 Expression::Expression (const double constant)
 940     : term (new Expression::Helpers::Constant (constant, false))
 941 {
 942 }
 943
 944 Expression::Expression (const Expression& other)
 945     : term (other.term)
 946 {
 947 }
 948
 949 Expression& Expression::operator= (const Expression& other)
 950 {
 951     term = other.term;
 952     return *this;
 953 }
 954
 955 Expression::Expression (const String& stringToParse)
 956 {
 957     String::CharPointerType text (stringToParse.getCharPointer());
 958     Helpers::Parser parser (text);
 959     term = parser.readUpToComma();
 960 }
 961
 962 Expression Expression::parse (String::CharPointerType& stringToParse)
 963 {
 964     Helpers::Parser parser (stringToParse);
 965     return Expression (parser.readUpToComma());
 966 }
 967
 968 double Expression::evaluate() const
 969 {
 970     return evaluate (Expression::Scope());
 971 }
 972
 973 double Expression::evaluate (const Expression::Scope& scope) const
 974 {
 975     try
 976     {
 977         return term->resolve (scope, 0)->toDouble();
 978     }
 979     catch (Helpers::EvaluationError&)
 980     {}
 981
 982     return 0;
 983 }
 984
 985 double Expression::evaluate (const Scope& scope, String& evaluationError) const
 986 {
 987     try
 988     {
 989         return term->resolve (scope, 0)->toDouble();
 990     }
 991     catch (Helpers::EvaluationError& e)
 992     {
 993         evaluationError = e.description;
 994     }
 995
 996     return 0;
 997 }
 998
 999 Expression Expression::operator+ (const Expression& other) const  { return Expression (new Helpers::Add (term, other.term)); }
1000 Expression Expression::operator- (const Expression& other) const  { return Expression (new Helpers::Subtract (term, other.term)); }
1001 Expression Expression::operator* (const Expression& other) const  { return Expression (new Helpers::Multiply (term, other.term)); }
1002 Expression Expression::operator/ (const Expression& other) const  { return Expression (new Helpers::Divide (term, other.term)); }
1003 Expression Expression::operator-() const                          { return Expression (term->negated()); }
1004 Expression Expression::symbol (const String& symbol)              { return Expression (new Helpers::SymbolTerm (symbol)); }
1005
1006 Expression Expression::function (const String& functionName, const Array<Expression>& parameters)
1007 {
1008     return Expression (new Helpers::Function (functionName, parameters));
1009 }
1010
1011 Expression Expression::adjustedToGiveNewResult (const double targetValue, const Expression::Scope& scope) const
1012 {
1013     ScopedPointer<Term> newTerm (term->clone());
1014
1015     Helpers::Constant* termToAdjust = Helpers::findTermToAdjust (newTerm, true);
1016
1017     if (termToAdjust == nullptr)
1018         termToAdjust = Helpers::findTermToAdjust (newTerm, false);
1019
1020     if (termToAdjust == nullptr)
1021     {
1022         newTerm = new Helpers::Add (newTerm.release(), new Helpers::Constant (0, false));
1023         termToAdjust = Helpers::findTermToAdjust (newTerm, false);
1024     }
1025
1026     jassert (termToAdjust != nullptr);
1027
1028     const Term* const parent = Helpers::findDestinationFor (newTerm, termToAdjust);
1029
1030     if (parent == nullptr)
1031     {
1032         termToAdjust->value = targetValue;
1033     }
1034     else
1035     {
1036         const Helpers::TermPtr reverseTerm (parent->createTermToEvaluateInput (scope, termToAdjust, targetValue, newTerm));
1037
1038         if (reverseTerm == nullptr)
1039             return Expression (targetValue);
1040
1041         termToAdjust->value = reverseTerm->resolve (scope, 0)->toDouble();
1042     }
1043
1044     return Expression (newTerm.release());
1045 }
1046
1047 Expression Expression::withRenamedSymbol (const Expression::Symbol& oldSymbol, const String& newName, const Scope& scope) const
1048 {
1049     jassert (newName.toLowerCase().containsOnly ("abcdefghijklmnopqrstuvwxyz0123456789_"));
1050
1051     if (oldSymbol.symbolName == newName)
1052         return *this;
1053
1054     Expression e (term->clone());
1055     e.term->renameSymbol (oldSymbol, newName, scope, 0);
1056     return e;
1057 }
1058
1059 bool Expression::referencesSymbol (const Expression::Symbol& symbolToCheck, const Scope& scope) const
1060 {
1061     Helpers::SymbolCheckVisitor visitor (symbolToCheck);
1062
1063     try
1064     {
1065         term->visitAllSymbols (visitor, scope, 0);
1066     }
1067     catch (Helpers::EvaluationError&)
1068     {}
1069
1070     return visitor.wasFound;
1071 }
1072
1073 void Expression::findReferencedSymbols (Array<Symbol>& results, const Scope& scope) const
1074 {
1075     try
1076     {
1077         Helpers::SymbolListVisitor visitor (results);
1078         term->visitAllSymbols (visitor, scope, 0);
1079     }
1080     catch (Helpers::EvaluationError&)
1081     {}
1082 }
1083
1084 String Expression::toString() const                     { return term->toString(); }
1085 bool Expression::usesAnySymbols() const                 { return Helpers::containsAnySymbols (term); }
1086 Expression::Type Expression::getType() const noexcept   { return term->getType(); }
1087 String Expression::getSymbolOrFunction() const          { return term->getName(); }
1088 int Expression::getNumInputs() const                    { return term->getNumInputs(); }
1089 Expression Expression::getInput (int index) const       { return Expression (term->getInput (index)); }
1090
1091 //==============================================================================
1092 ReferenceCountedObjectPtr<Expression::Term> Expression::Term::negated()
1093 {
1094     return new Helpers::Negate (this);
1095 }
1096
1097 //==============================================================================
1098 Expression::ParseError::ParseError (const String& message)
1099     : description (message)
1100 {
1101     DBG ("Expression::ParseError: " + message);
1102 }
1103
1104 //==============================================================================
1105 Expression::Symbol::Symbol (const String& scopeUID_, const String& symbolName_)
1106     : scopeUID (scopeUID_), symbolName (symbolName_)
1107 {
1108 }
1109
1110 bool Expression::Symbol::operator== (const Symbol& other) const noexcept
1111 {
1112     return symbolName == other.symbolName && scopeUID == other.scopeUID;
1113 }
1114
1115 bool Expression::Symbol::operator!= (const Symbol& other) const noexcept
1116 {
1117     return ! operator== (other);
1118 }
1119
1120 //==============================================================================
1121 Expression::Scope::Scope()  {}
1122 Expression::Scope::~Scope() {}
1123
1124 Expression Expression::Scope::getSymbolValue (const String& symbol) const
1125 {
1126     throw Helpers::EvaluationError ("Unknown symbol: " + symbol);
1127 }
1128
1129 double Expression::Scope::evaluateFunction (const String& functionName, const double* parameters, int numParams) const
1130 {
1131     if (numParams > 0)
1132     {
1133         if (functionName == "min")
1134         {
1135             double v = parameters[0];
1136             for (int i = 1; i < numParams; ++i)
1137                 v = jmin (v, parameters[i]);
1138
1139             return v;
1140         }
1141         else if (functionName == "max")
1142         {
1143             double v = parameters[0];
1144             for (int i = 1; i < numParams; ++i)
1145                 v = jmax (v, parameters[i]);
1146
1147             return v;
1148         }
1149         else if (numParams == 1)
1150         {
1151             if      (functionName == "sin")     return sin (parameters[0]);
1152             else if (functionName == "cos")     return cos (parameters[0]);
1153             else if (functionName == "tan")     return tan (parameters[0]);
1154             else if (functionName == "abs")     return std::abs (parameters[0]);
1155         }
1156     }
1157
1158     throw Helpers::EvaluationError ("Unknown function: \"" + functionName + "\"");
1159 }
1160
1161 void Expression::Scope::visitRelativeScope (const String& scopeName, Visitor&) const
1162 {
1163     throw Helpers::EvaluationError ("Unknown symbol: " + scopeName);
1164 }
1165
1166 String Expression::Scope::getScopeUID() const
1167 {
1168     return String::empty;
1169 }
1170
1171
1172 END_JUCE_NAMESPACE