Back to index

scribus-ng  1.3.4.dfsg+svn20071115
fparser.cpp
Go to the documentation of this file.
00001 /*
00002 For general Scribus (>=1.3.2) copyright and licensing information please refer
00003 to the COPYING file provided with the program. Following this notice may exist
00004 a copyright and/or license notice that predates the release of Scribus 1.3.2
00005 for which a new license (GPL+exception) is in place.
00006 */
00007 //==============================
00008 // Function parser v2.8 by Warp
00009 //==============================
00010 
00011 #include "fparser.h"
00012 #include "fpconfig.h"
00013 #include "fptypes.h"
00014 using namespace FUNCTIONPARSERTYPES;
00015 
00016 #include <cstdlib>
00017 #include <cstring>
00018 #include <cctype>
00019 #include <cmath>
00020 
00021 using namespace std;
00022 
00023 #ifndef M_PI
00024 #define M_PI 3.1415926535897932384626433832795
00025 #endif
00026 
00027 namespace
00028 {
00029     const unsigned FUNC_AMOUNT = sizeof(Functions)/sizeof(Functions[0]);
00030 
00031 
00032     // BCB4 does not implement the standard lower_bound function.
00033     // This is used instead:
00034     const FuncDefinition* fp_lower_bound(const FuncDefinition* first,
00035                                          const FuncDefinition* last,
00036                                          const FuncDefinition& value)
00037     {
00038         while(first < last)
00039         {
00040             const FuncDefinition* middle = first+(last-first)/2;
00041             if(*middle < value) first = middle+1;
00042             else last = middle;
00043         }
00044         return last;
00045     }
00046 
00047 
00048     // Returns a pointer to the FuncDefinition instance which 'name' is
00049     // the same as the one given by 'F'. If no such function name exists,
00050     // returns 0.
00051     inline const FuncDefinition* FindFunction(const char* F)
00052     {
00053         FuncDefinition func = { F, 0, 0, 0 };
00054         while(isalnum(F[func.nameLength])) ++func.nameLength;
00055         if(func.nameLength)
00056         {
00057             const FuncDefinition* found =
00058                 fp_lower_bound(Functions, Functions+FUNC_AMOUNT, func);
00059             if(found == Functions+FUNC_AMOUNT || func < *found)
00060                 return 0;
00061             return found;
00062         }
00063         return 0;
00064     }
00065 }
00066 
00067 
00068 //---------------------------------------------------------------------------
00069 // Copy-on-write method
00070 //---------------------------------------------------------------------------
00071 void FunctionParser::copyOnWrite()
00072 {
00073     if(data->referenceCounter > 1)
00074     {
00075         Data* oldData = data;
00076         data = new Data(*oldData);
00077         --(oldData->referenceCounter);
00078         data->referenceCounter = 1;
00079     }
00080 }
00081 
00082 
00083 //---------------------------------------------------------------------------
00084 // Constructors and destructors
00085 //---------------------------------------------------------------------------
00086 //===========================================================================
00087 FunctionParser::FunctionParser():
00088     parseErrorType(FP_NO_ERROR), evalErrorType(0),
00089     data(new Data),
00090     evalRecursionLevel(0)
00091 {
00092     data->referenceCounter = 1;
00093 }
00094 
00095 FunctionParser::~FunctionParser()
00096 {
00097     if(--(data->referenceCounter) == 0)
00098     {
00099         delete data;
00100     }
00101 }
00102 
00103 FunctionParser::FunctionParser(const FunctionParser& cpy):
00104     parseErrorType(cpy.parseErrorType),
00105     evalErrorType(cpy.evalErrorType),
00106     data(cpy.data),
00107     evalRecursionLevel(0)
00108 {
00109     ++(data->referenceCounter);
00110 }
00111 
00112 FunctionParser& FunctionParser::operator=(const FunctionParser& cpy)
00113 {
00114     if(data != cpy.data)
00115     {
00116         if(--(data->referenceCounter) == 0) delete data;
00117 
00118         parseErrorType = cpy.parseErrorType;
00119         evalErrorType = cpy.evalErrorType;
00120         data = cpy.data;
00121         evalRecursionLevel = cpy.evalRecursionLevel;
00122 
00123         ++(data->referenceCounter);
00124     }
00125 
00126     return *this;
00127 }
00128 
00129 
00130 FunctionParser::Data::Data():
00131     useDegreeConversion(false),
00132     ByteCode(0), ByteCodeSize(0),
00133     Immed(0), ImmedSize(0),
00134     Stack(0), StackSize(0)
00135 {}
00136 
00137 FunctionParser::Data::~Data()
00138 {
00139     if(ByteCode) { delete[] ByteCode; ByteCode=0; }
00140     if(Immed) { delete[] Immed; Immed=0; }
00141     if(Stack) { delete[] Stack; Stack=0; }
00142 }
00143 
00144 // Makes a deep-copy of Data:
00145 FunctionParser::Data::Data(const Data& cpy):
00146     varAmount(cpy.varAmount), useDegreeConversion(cpy.useDegreeConversion),
00147     Variables(cpy.Variables), Constants(cpy.Constants),
00148     FuncPtrNames(cpy.FuncPtrNames), FuncPtrs(cpy.FuncPtrs),
00149     FuncParserNames(cpy.FuncParserNames), FuncParsers(cpy.FuncParsers),
00150     ByteCode(0), ByteCodeSize(cpy.ByteCodeSize),
00151     Immed(0), ImmedSize(cpy.ImmedSize),
00152     Stack(0), StackSize(cpy.StackSize)
00153 {
00154     if(ByteCodeSize) ByteCode = new unsigned[ByteCodeSize];
00155     if(ImmedSize) Immed = new double[ImmedSize];
00156     if(StackSize) Stack = new double[StackSize];
00157 
00158     for(unsigned i=0; i<ByteCodeSize; ++i) ByteCode[i] = cpy.ByteCode[i];
00159     for(unsigned i=0; i<ImmedSize; ++i) Immed[i] = cpy.Immed[i];
00160 
00161     // No need to copy the stack contents because it's obsolete outside Eval()
00162 }
00163 
00164 
00165 //---------------------------------------------------------------------------
00166 // Function parsing
00167 //---------------------------------------------------------------------------
00168 //===========================================================================
00169 namespace
00170 {
00171     // Error messages returned by ErrorMsg():
00172     const char* ParseErrorMessage[]=
00173     {
00174         "Syntax error",                             // 0
00175         "Mismatched parenthesis",                   // 1
00176         "Missing ')'",                              // 2
00177         "Empty parentheses",                        // 3
00178         "Syntax error: Operator expected",          // 4
00179         "Not enough memory",                        // 5
00180         "An unexpected error occurred. Please make a full bug report "
00181         "to the author",                            // 6
00182         "Syntax error in parameter 'Vars' given to "
00183         "FunctionParser::Parse()",                  // 7
00184         "Illegal number of parameters to function", // 8
00185         "Syntax error: Premature end of string",    // 9
00186         "Syntax error: Expecting ( after function", // 10
00187         ""
00188     };
00189 
00190 
00191     // Parse variables
00192     bool ParseVars(const string& Vars, map<string, unsigned>& dest)
00193     {
00194         unsigned varNumber = VarBegin;
00195         unsigned ind1 = 0, ind2;
00196 
00197         while(ind1 < Vars.size())
00198         {
00199             if(!isalpha(Vars[ind1]) && Vars[ind1]!='_') return false;
00200             for(ind2=ind1+1; ind2<Vars.size() && Vars[ind2]!=','; ++ind2)
00201                 if(!isalnum(Vars[ind2]) && Vars[ind2]!='_') return false;
00202             const string varName = Vars.substr(ind1, ind2-ind1);
00203 
00204             if(dest.insert(make_pair(varName, varNumber++)).second == false)
00205                 return false;
00206 
00207             ind1 = ind2+1;
00208         }
00209         return true;
00210     }
00211 }
00212 
00213 bool FunctionParser::isValidName(const std::string& name) const
00214 {
00215     if(name.empty() || (!isalpha(name[0]) && name[0] != '_')) return false;
00216     for(unsigned i=0; i<name.size(); ++i)
00217         if(!isalnum(name[i]) && name[i] != '_') return false;
00218 
00219     if(FindFunction(name.c_str())) return false;
00220 
00221     return true;
00222 }
00223 
00224 
00225 // Constants:
00226 bool FunctionParser::AddConstant(const std::string& name, double value)
00227 {
00228     if(isValidName(name))
00229     {
00230         const char* n = name.c_str();
00231         if(FindVariable(n, data->FuncParserNames) !=
00232            data->FuncParserNames.end() ||
00233            FindVariable(n, data->FuncPtrNames) !=
00234            data->FuncPtrNames.end())
00235             return false;
00236 
00237         copyOnWrite();
00238 
00239         data->Constants[name] = value;
00240         return true;
00241     }
00242     return false;
00243 }
00244 
00245 // Function pointers
00246 bool FunctionParser::AddFunction(const std::string& name,
00247                                  FunctionPtr func, unsigned paramsAmount)
00248 {
00249     if(isValidName(name))
00250     {
00251         const char* n = name.c_str();
00252         if(FindVariable(n, data->FuncParserNames) !=
00253            data->FuncParserNames.end() ||
00254            FindConstant(n) != data->Constants.end())
00255             return false;
00256 
00257         copyOnWrite();
00258 
00259         data->FuncPtrNames[name] = data->FuncPtrs.size();
00260         data->FuncPtrs.push_back(Data::FuncPtrData(func, paramsAmount));
00261         return true;
00262     }
00263     return false;
00264 }
00265 
00266 bool FunctionParser::checkRecursiveLinking(const FunctionParser* fp) const
00267 {
00268     if(fp == this) return true;
00269     for(unsigned i=0; i<fp->data->FuncParsers.size(); ++i)
00270         if(checkRecursiveLinking(fp->data->FuncParsers[i])) return true;
00271     return false;
00272 }
00273 
00274 bool FunctionParser::AddFunction(const std::string& name,
00275                                  FunctionParser& parser)
00276 {
00277     if(isValidName(name))
00278     {
00279         const char* n = name.c_str();
00280         if(FindVariable(n, data->FuncPtrNames) != data->FuncPtrNames.end() ||
00281            FindConstant(n) != data->Constants.end())
00282             return false;
00283 
00284         if(checkRecursiveLinking(&parser)) return false;
00285 
00286         copyOnWrite();
00287 
00288         data->FuncParserNames[name] = data->FuncParsers.size();
00289         data->FuncParsers.push_back(&parser);
00290         return true;
00291     }
00292     return false;
00293 }
00294 
00295 
00296 
00297 // Main parsing function
00298 // ---------------------
00299 int FunctionParser::Parse(const std::string& Function,
00300                           const std::string& Vars,
00301                           bool useDegrees)
00302 {
00303     copyOnWrite();
00304 
00305     data->Variables.clear();
00306 
00307     if(!ParseVars(Vars, data->Variables))
00308     {
00309         parseErrorType = INVALID_VARS;
00310         return Function.size();
00311     }
00312     data->varAmount = data->Variables.size(); // this is for Eval()
00313 
00314     const char* Func = Function.c_str();
00315 
00316     parseErrorType = FP_NO_ERROR;
00317 
00318     int Result = CheckSyntax(Func);
00319     if(Result>=0) return Result;
00320 
00321     data->useDegreeConversion = useDegrees;
00322     if(!Compile(Func)) return Function.size();
00323 
00324     data->Variables.clear();
00325 
00326     parseErrorType = FP_NO_ERROR;
00327     return -1;
00328 }
00329 
00330 namespace
00331 {
00332     const char* const fpOperators[] =
00333     {
00334         "+", "-", "*", "/", "%", "^",
00335         "=", "!=", "<=", "<", ">=", ">", "&", "|",
00336         0
00337     };
00338 
00339     // Is given char an operator?
00340     // (Returns 0 if not, else the size of the operator)
00341     inline int IsOperator(const char* F)
00342     {
00343         for(unsigned opInd = 0; fpOperators[opInd]; ++opInd)
00344         {
00345             const char* op = fpOperators[opInd];
00346             for(unsigned n = 0; F[n] == *op; ++n)
00347             {
00348                 ++op;
00349                 if(*op == 0) return op-fpOperators[opInd];
00350             }
00351         }
00352         return 0;
00353     }
00354 
00355     // skip whitespace
00356     inline void sws(const char* F, int& Ind)
00357     {
00358         while(F[Ind] && isspace(F[Ind])) ++Ind;
00359     }
00360 }
00361 
00362 // Returns an iterator to the variable with the same name as 'F', or to
00363 // Variables.end() if no such variable exists:
00364 inline FunctionParser::Data::VarMap_t::const_iterator
00365 FunctionParser::FindVariable(const char* F, const Data::VarMap_t& vars) const
00366 {
00367     if(vars.size())
00368     {
00369         unsigned ind = 0;
00370         while(isalnum(F[ind]) || F[ind] == '_') ++ind;
00371         if(ind)
00372         {
00373             string name(F, ind);
00374             return vars.find(name);
00375         }
00376     }
00377     return vars.end();
00378 }
00379 
00380 inline FunctionParser::Data::ConstMap_t::const_iterator
00381 FunctionParser::FindConstant(const char* F) const
00382 {
00383     if(data->Constants.size())
00384     {
00385         unsigned ind = 0;
00386         while(isalnum(F[ind]) || F[ind] == '_') ++ind;
00387         if(ind)
00388         {
00389             string name(F, ind);
00390             return data->Constants.find(name);
00391         }
00392     }
00393     return data->Constants.end();
00394 }
00395 
00396 //---------------------------------------------------------------------------
00397 // Check function string syntax
00398 // ----------------------------
00399 int FunctionParser::CheckSyntax(const char* Function)
00400 {
00401     const Data::VarMap_t& Variables = data->Variables;
00402     const Data::ConstMap_t& Constants = data->Constants;
00403     const Data::VarMap_t& FuncPtrNames = data->FuncPtrNames;
00404     const Data::VarMap_t& FuncParserNames = data->FuncParserNames;
00405 
00406     vector<int> functionParenthDepth;
00407 
00408     int Ind=0, ParenthCnt=0, c;
00409     char* Ptr;
00410 
00411     while(true)
00412     {
00413         sws(Function, Ind);
00414         c=Function[Ind];
00415 
00416 // Check for valid operand (must appear)
00417 
00418         // Check for leading - or !
00419         if(c=='-' || c=='!') { sws(Function, ++Ind); c=Function[Ind]; }
00420         if(c==0) { parseErrorType=PREMATURE_EOS; return Ind; }
00421 
00422         // Check for math function
00423         bool foundFunc = false;
00424         const FuncDefinition* fptr = FindFunction(&Function[Ind]);
00425         if(fptr)
00426         {
00427             Ind += fptr->nameLength;
00428             foundFunc = true;
00429         }
00430         else
00431         {
00432             // Check for user-defined function
00433             Data::VarMap_t::const_iterator fIter =
00434                 FindVariable(&Function[Ind], FuncPtrNames);
00435             if(fIter != FuncPtrNames.end())
00436             {
00437                 Ind += fIter->first.size();
00438                 foundFunc = true;
00439             }
00440             else
00441             {
00442                 Data::VarMap_t::const_iterator pIter =
00443                     FindVariable(&Function[Ind], FuncParserNames);
00444                 if(pIter != FuncParserNames.end())
00445                 {
00446                     Ind += pIter->first.size();
00447                     foundFunc = true;
00448                 }
00449             }
00450         }
00451 
00452         if(foundFunc)
00453         {
00454             sws(Function, Ind);
00455             c = Function[Ind];
00456             if(c!='(') { parseErrorType=EXPECT_PARENTH_FUNC; return Ind; }
00457 
00458             int Ind2 = Ind+1;
00459             sws(Function, Ind2);
00460             if(Function[Ind2] == ')')
00461             {
00462                 Ind = Ind2+1;
00463                 sws(Function, Ind);
00464                 c = Function[Ind];
00465                 // Ugly, but other methods would just be uglier...
00466                 goto CheckOperator;
00467             }
00468 
00469             functionParenthDepth.push_back(ParenthCnt+1);
00470         }
00471 
00472         // Check for opening parenthesis
00473         if(c=='(')
00474         {
00475             ++ParenthCnt;
00476             sws(Function, ++Ind);
00477             if(Function[Ind]==')') { parseErrorType=EMPTY_PARENTH; return Ind;}
00478             continue;
00479         }
00480 
00481         // Check for number
00482         if(isdigit(c) || (c=='.' && isdigit(Function[Ind+1])))
00483         {
00484             strtod(&Function[Ind], &Ptr);
00485             Ind += int(Ptr-&Function[Ind]);
00486             sws(Function, Ind);
00487             c = Function[Ind];
00488         }
00489         else
00490         { // Check for variable
00491             Data::VarMap_t::const_iterator vIter =
00492                 FindVariable(&Function[Ind], Variables);
00493             if(vIter != Variables.end())
00494                 Ind += vIter->first.size();
00495             else
00496             {
00497                 // Check for constant
00498                 Data::ConstMap_t::const_iterator cIter =
00499                     FindConstant(&Function[Ind]);
00500                 if(cIter != Constants.end())
00501                     Ind += cIter->first.size();
00502                 else
00503                 { parseErrorType=SYNTAX_ERROR; return Ind; }
00504             }
00505             sws(Function, Ind);
00506             c = Function[Ind];
00507         }
00508 
00509         // Check for closing parenthesis
00510         while(c==')')
00511         {
00512             if(functionParenthDepth.size() &&
00513                functionParenthDepth.back() == ParenthCnt)
00514                 functionParenthDepth.pop_back();
00515             if((--ParenthCnt)<0) { parseErrorType=MISM_PARENTH; return Ind; }
00516             sws(Function, ++Ind);
00517             c=Function[Ind];
00518         }
00519 
00520 // If we get here, we have a legal operand and now a legal operator or
00521 // end of string must follow
00522 
00523     CheckOperator:
00524         // Check for EOS
00525         if(c==0) break; // The only way to end the checking loop without error
00526 
00527         // Check for operator
00528         int opSize = 0;
00529         if(c == ',' && !functionParenthDepth.empty() &&
00530            functionParenthDepth.back() == ParenthCnt)
00531             opSize = 1;
00532         else
00533             opSize = IsOperator(Function+Ind);
00534         if(opSize == 0)
00535         { parseErrorType=EXPECT_OPERATOR; return Ind; }
00536 
00537 // If we get here, we have an operand and an operator; the next loop will
00538 // check for another operand (must appear)
00539         Ind += opSize;
00540     } // while
00541 
00542     // Check that all opened parentheses are also closed
00543     if(ParenthCnt>0) { parseErrorType=MISSING_PARENTH; return Ind; }
00544 
00545 // The string is ok
00546     parseErrorType=FP_NO_ERROR;
00547     return -1;
00548 }
00549 
00550 
00551 // Compile function string to bytecode
00552 // -----------------------------------
00553 bool FunctionParser::Compile(const char* Function)
00554 {
00555     if(data->ByteCode) { delete[] data->ByteCode; data->ByteCode=0; }
00556     if(data->Immed) { delete[] data->Immed; data->Immed=0; }
00557     if(data->Stack) { delete[] data->Stack; data->Stack=0; }
00558 
00559     vector<unsigned> byteCode; byteCode.reserve(1024);
00560     tempByteCode = &byteCode;
00561 
00562     vector<double> immed; immed.reserve(1024);
00563     tempImmed = &immed;
00564 
00565     data->StackSize = StackPtr = 0;
00566 
00567     CompileExpression(Function, 0);
00568     if(parseErrorType != FP_NO_ERROR) return false;
00569 
00570     data->ByteCodeSize = byteCode.size();
00571     data->ImmedSize = immed.size();
00572 
00573     if(data->ByteCodeSize)
00574     {
00575         data->ByteCode = new unsigned[data->ByteCodeSize];
00576         memcpy(data->ByteCode, &byteCode[0],
00577                sizeof(unsigned)*data->ByteCodeSize);
00578     }
00579     if(data->ImmedSize)
00580     {
00581         data->Immed = new double[data->ImmedSize];
00582         memcpy(data->Immed, &immed[0],
00583                sizeof(double)*data->ImmedSize);
00584     }
00585     if(data->StackSize)
00586         data->Stack = new double[data->StackSize];
00587 
00588     return true;
00589 }
00590 
00591 
00592 inline void FunctionParser::AddCompiledByte(unsigned c)
00593 {
00594     tempByteCode->push_back(c);
00595 }
00596 
00597 inline void FunctionParser::AddImmediate(double i)
00598 {
00599     tempImmed->push_back(i);
00600 }
00601 
00602 inline void FunctionParser::AddFunctionOpcode(unsigned opcode)
00603 {
00604     if(data->useDegreeConversion)
00605         switch(opcode)
00606         {
00607           case cCos:
00608           case cCosh:
00609           case cCot:
00610           case cCsc:
00611           case cSec:
00612           case cSin:
00613           case cSinh:
00614           case cTan:
00615           case cTanh:
00616               AddCompiledByte(cRad);
00617         }
00618 
00619     AddCompiledByte(opcode);
00620 
00621     if(data->useDegreeConversion)
00622         switch(opcode)
00623         {
00624           case cAcos:
00625 #ifndef NO_ASINH
00626           case cAcosh:
00627           case cAsinh:
00628           case cAtanh:
00629 #endif
00630           case cAsin:
00631           case cAtan:
00632           case cAtan2:
00633               AddCompiledByte(cDeg);
00634         }
00635 }
00636 
00637 inline void FunctionParser::incStackPtr()
00638 {
00639     if(++StackPtr > data->StackSize) ++(data->StackSize);
00640 }
00641 
00642 
00643 // Compile if()
00644 int FunctionParser::CompileIf(const char* F, int ind)
00645 {
00646     int ind2 = CompileExpression(F, ind, true); // condition
00647     sws(F, ind2);
00648     if(F[ind2] != ',') { parseErrorType=ILL_PARAMS_AMOUNT; return ind2; }
00649     AddCompiledByte(cIf);
00650     unsigned curByteCodeSize = tempByteCode->size();
00651     AddCompiledByte(0); // Jump index; to be set later
00652     AddCompiledByte(0); // Immed jump index; to be set later
00653 
00654     --StackPtr;
00655 
00656     ind2 = CompileExpression(F, ind2+1, true); // then
00657     sws(F, ind2);
00658     if(F[ind2] != ',') { parseErrorType=ILL_PARAMS_AMOUNT; return ind2; }
00659     AddCompiledByte(cJump);
00660     unsigned curByteCodeSize2 = tempByteCode->size();
00661     unsigned curImmedSize2 = tempImmed->size();
00662     AddCompiledByte(0); // Jump index; to be set later
00663     AddCompiledByte(0); // Immed jump index; to be set later
00664 
00665     --StackPtr;
00666 
00667     ind2 = CompileExpression(F, ind2+1, true); // else
00668     sws(F, ind2);
00669     if(F[ind2] != ')') { parseErrorType=ILL_PARAMS_AMOUNT; return ind2; }
00670 
00671     // Set jump indices
00672     (*tempByteCode)[curByteCodeSize] = curByteCodeSize2+1;
00673     (*tempByteCode)[curByteCodeSize+1] = curImmedSize2;
00674     (*tempByteCode)[curByteCodeSize2] = tempByteCode->size()-1;
00675     (*tempByteCode)[curByteCodeSize2+1] = tempImmed->size();
00676 
00677     return ind2+1;
00678 }
00679 
00680 int FunctionParser::CompileFunctionParams(const char* F, int ind,
00681                                           unsigned requiredParams)
00682 {
00683     int ind2 = ind;
00684     if(requiredParams > 0)
00685     {
00686         unsigned curStackPtr = StackPtr;
00687         ind2 = CompileExpression(F, ind);
00688 
00689         if(StackPtr != curStackPtr+requiredParams)
00690         { parseErrorType=ILL_PARAMS_AMOUNT; return ind; }
00691 
00692         StackPtr -= requiredParams - 1;
00693     }
00694     else
00695     {
00696         incStackPtr();
00697     }
00698 
00699     sws(F, ind2);
00700     return ind2+1; // F[ind2] is ')'
00701 }
00702 
00703 // Compiles element
00704 int FunctionParser::CompileElement(const char* F, int ind)
00705 {
00706     sws(F, ind);
00707     char c = F[ind];
00708 
00709     if(c == '(')
00710     {
00711         ind = CompileExpression(F, ind+1);
00712         sws(F, ind);
00713         return ind+1; // F[ind] is ')'
00714     }
00715 
00716     if(isdigit(c) || c=='.' /*|| c=='-'*/) // Number
00717     {
00718         const char* startPtr = &F[ind];
00719         char* endPtr;
00720         double val = strtod(startPtr, &endPtr);
00721         AddImmediate(val);
00722         AddCompiledByte(cImmed);
00723         incStackPtr();
00724         return ind+(endPtr-startPtr);
00725     }
00726 
00727     if(isalpha(c) || c == '_') // Function, variable or constant
00728     {
00729         const FuncDefinition* func = FindFunction(F+ind);
00730         if(func) // is function
00731         {
00732             int ind2 = ind + func->nameLength;
00733             sws(F, ind2); // F[ind2] is '('
00734             if(strcmp(func->name, "if") == 0) // "if" is a special case
00735             {
00736                 return CompileIf(F, ind2+1);
00737             }
00738 
00739 #ifndef DISABLE_EVAL
00740             unsigned requiredParams =
00741                 strcmp(func->name, "eval") == 0 ?
00742                 data->Variables.size() : func->params;
00743 #else
00744             unsigned requiredParams = func->params;
00745 #endif
00746             ind2 = CompileFunctionParams(F, ind2+1, requiredParams);
00747             AddFunctionOpcode(func->opcode);
00748             return ind2; // F[ind2-1] is ')'
00749         }
00750 
00751         Data::VarMap_t::const_iterator vIter =
00752             FindVariable(F+ind, data->Variables);
00753         if(vIter != data->Variables.end()) // is variable
00754         {
00755             AddCompiledByte(vIter->second);
00756             incStackPtr();
00757             return ind + vIter->first.size();
00758         }
00759 
00760         Data::ConstMap_t::const_iterator cIter = FindConstant(F+ind);
00761         if(cIter != data->Constants.end()) // is constant
00762         {
00763             AddImmediate(cIter->second);
00764             AddCompiledByte(cImmed);
00765             incStackPtr();
00766             return ind + cIter->first.size();
00767         }
00768 
00769         Data::VarMap_t::const_iterator fIter =
00770             FindVariable(F+ind, data->FuncPtrNames);
00771         if(fIter != data->FuncPtrNames.end()) // is user-defined func pointer
00772         {
00773             unsigned index = fIter->second;
00774 
00775             int ind2 = ind + fIter->first.length();
00776             sws(F, ind2); // F[ind2] is '('
00777 
00778             ind2 = CompileFunctionParams(F, ind2+1,
00779                                          data->FuncPtrs[index].params);
00780 
00781             AddCompiledByte(cFCall);
00782             AddCompiledByte(index);
00783             return ind2;
00784         }
00785 
00786         Data::VarMap_t::const_iterator pIter =
00787             FindVariable(F+ind, data->FuncParserNames);
00788         if(pIter != data->FuncParserNames.end()) // is user-defined func parser
00789         {
00790             unsigned index = pIter->second;
00791 
00792             int ind2 = ind + pIter->first.length();
00793             sws(F, ind2); // F[ind2] is '('
00794 
00795             ind2 = CompileFunctionParams
00796                 (F, ind2+1, data->FuncParsers[index]->data->varAmount);
00797 
00798             AddCompiledByte(cPCall);
00799             AddCompiledByte(index);
00800             return ind2;
00801         }
00802     }
00803 
00804     parseErrorType = UNEXPECTED_ERROR;
00805     return ind;
00806 }
00807 
00808 // Compiles '^'
00809 int FunctionParser::CompilePow(const char* F, int ind)
00810 {
00811     int ind2 = CompileElement(F, ind);
00812     sws(F, ind2);
00813 
00814     while(F[ind2] == '^')
00815     {
00816         ind2 = CompileUnaryMinus(F, ind2+1);
00817         sws(F, ind2);
00818         AddCompiledByte(cPow);
00819         --StackPtr;
00820     }
00821 
00822     return ind2;
00823 }
00824 
00825 // Compiles unary '-'
00826 int FunctionParser::CompileUnaryMinus(const char* F, int ind)
00827 {
00828     sws(F, ind);
00829     if(F[ind] == '-' || F[ind] == '!')
00830     {
00831         int ind2 = ind+1;
00832         sws(F, ind2);
00833         ind2 = CompilePow(F, ind2);
00834         sws(F, ind2);
00835 
00836         // if we are negating a constant, negate the constant itself:
00837         if(F[ind] == '-' && tempByteCode->back() == cImmed)
00838             tempImmed->back() = -tempImmed->back();
00839 
00840         // if we are negating a negation, we can remove both:
00841         else if((F[ind] == '-' && tempByteCode->back() == cNeg))
00842             tempByteCode->pop_back();
00843 
00844         else
00845             AddCompiledByte(F[ind] == '-' ? cNeg : cNot);
00846 
00847         return ind2;
00848     }
00849 
00850     int ind2 = CompilePow(F, ind);
00851     sws(F, ind2);
00852     return ind2;
00853 }
00854 
00855 // Compiles '*', '/' and '%'
00856 int FunctionParser::CompileMult(const char* F, int ind)
00857 {
00858     int ind2 = CompileUnaryMinus(F, ind);
00859     sws(F, ind2);
00860     char op;
00861 
00862     while((op = F[ind2]) == '*' || op == '/' || op == '%')
00863     {
00864         ind2 = CompileUnaryMinus(F, ind2+1);
00865         sws(F, ind2);
00866         switch(op)
00867         {
00868           case '*': AddCompiledByte(cMul); break;
00869           case '/': AddCompiledByte(cDiv); break;
00870           case '%': AddCompiledByte(cMod); break;
00871         }
00872         --StackPtr;
00873     }
00874 
00875     return ind2;
00876 }
00877 
00878 // Compiles '+' and '-'
00879 int FunctionParser::CompileAddition(const char* F, int ind)
00880 {
00881     int ind2 = CompileMult(F, ind);
00882     sws(F, ind2);
00883     char op;
00884 
00885     while((op = F[ind2]) == '+' || op == '-')
00886     {
00887         ind2 = CompileMult(F, ind2+1);
00888         sws(F, ind2);
00889         AddCompiledByte(op=='+' ? cAdd : cSub);
00890         --StackPtr;
00891     }
00892 
00893     return ind2;
00894 }
00895 
00896 // Compiles '=', '<' and '>'
00897 int FunctionParser::CompileComparison(const char* F, int ind)
00898 {
00899     int ind2 = CompileAddition(F, ind);
00900     sws(F, ind2);
00901     char op;
00902 
00903     while((op = F[ind2]) == '=' || op == '<' || op == '>' || op == '!')
00904     {
00905         int opSize = (F[ind2+1] == '=' ? 2 : 1);
00906         ind2 = CompileAddition(F, ind2+opSize);
00907         sws(F, ind2);
00908         switch(op)
00909         {
00910           case '=':
00911               AddCompiledByte(cEqual); break;
00912           case '<':
00913               AddCompiledByte(opSize == 1 ? cLess : cLessOrEq); break;
00914           case '>':
00915               AddCompiledByte(opSize == 1 ? cGreater : cGreaterOrEq); break;
00916           case '!':
00917               AddCompiledByte(cNEqual); break;
00918         }
00919         --StackPtr;
00920     }
00921 
00922     return ind2;
00923 }
00924 
00925 // Compiles '&'
00926 int FunctionParser::CompileAnd(const char* F, int ind)
00927 {
00928     int ind2 = CompileComparison(F, ind);
00929     sws(F, ind2);
00930 
00931     while(F[ind2] == '&')
00932     {
00933         ind2 = CompileComparison(F, ind2+1);
00934         sws(F, ind2);
00935         AddCompiledByte(cAnd);
00936         --StackPtr;
00937     }
00938 
00939     return ind2;
00940 }
00941 
00942 // Compiles '|'
00943 int FunctionParser::CompileOr(const char* F, int ind)
00944 {
00945     int ind2 = CompileAnd(F, ind);
00946     sws(F, ind2);
00947 
00948     while(F[ind2] == '|')
00949     {
00950         ind2 = CompileAnd(F, ind2+1);
00951         sws(F, ind2);
00952         AddCompiledByte(cOr);
00953         --StackPtr;
00954     }
00955 
00956     return ind2;
00957 }
00958 
00959 // Compiles ','
00960 int FunctionParser::CompileExpression(const char* F, int ind, bool stopAtComma)
00961 {
00962     int ind2 = CompileOr(F, ind);
00963     sws(F, ind2);
00964 
00965     if(stopAtComma) return ind2;
00966 
00967     while(F[ind2] == ',')
00968     {
00969         ind2 = CompileOr(F, ind2+1);
00970         sws(F, ind2);
00971     }
00972 
00973     return ind2;
00974 }
00975 
00976 
00977 // Return parse error message
00978 // --------------------------
00979 const char* FunctionParser::ErrorMsg() const
00980 {
00981     if(parseErrorType != FP_NO_ERROR) return ParseErrorMessage[parseErrorType];
00982     return 0;
00983 }
00984 
00985 //---------------------------------------------------------------------------
00986 // Function evaluation
00987 //---------------------------------------------------------------------------
00988 //===========================================================================
00989 namespace
00990 {
00991     inline int doubleToInt(double d)
00992     {
00993         return d<0 ? -int((-d)+.5) : int(d+.5);
00994     }
00995 
00996     inline double Min(double d1, double d2)
00997     {
00998         return d1<d2 ? d1 : d2;
00999     }
01000     inline double Max(double d1, double d2)
01001     {
01002         return d1>d2 ? d1 : d2;
01003     }
01004 
01005 
01006     inline double DegreesToRadians(double degrees)
01007     {
01008         return degrees*(M_PI/180.0);
01009     }
01010     inline double RadiansToDegrees(double radians)
01011     {
01012         return radians*(180.0/M_PI);
01013     }
01014 }
01015 
01016 double FunctionParser::Eval(const double* Vars)
01017 {
01018     const unsigned* const ByteCode = data->ByteCode;
01019     const double* const Immed = data->Immed;
01020     double* const Stack = data->Stack;
01021     const unsigned ByteCodeSize = data->ByteCodeSize;
01022     unsigned IP, DP=0;
01023     int SP=-1;
01024 
01025     for(IP=0; IP<ByteCodeSize; ++IP)
01026     {
01027         switch(ByteCode[IP])
01028         {
01029 // Functions:
01030           case   cAbs: Stack[SP] = fabs(Stack[SP]); break;
01031           case  cAcos: if(Stack[SP] < -1 || Stack[SP] > 1)
01032                        { evalErrorType=4; return 0; }
01033                        Stack[SP] = acos(Stack[SP]); break;
01034 #ifndef NO_ASINH
01035           case cAcosh: Stack[SP] = acosh(Stack[SP]); break;
01036 #endif
01037           case  cAsin: if(Stack[SP] < -1 || Stack[SP] > 1)
01038                        { evalErrorType=4; return 0; }
01039                        Stack[SP] = asin(Stack[SP]); break;
01040 #ifndef NO_ASINH
01041           case cAsinh: Stack[SP] = asinh(Stack[SP]); break;
01042 #endif
01043           case  cAtan: Stack[SP] = atan(Stack[SP]); break;
01044           case cAtan2: Stack[SP-1] = atan2(Stack[SP-1], Stack[SP]);
01045                        --SP; break;
01046 #ifndef NO_ASINH
01047           case cAtanh: Stack[SP] = atanh(Stack[SP]); break;
01048 #endif
01049           case  cCeil: Stack[SP] = ceil(Stack[SP]); break;
01050           case   cCos: Stack[SP] = cos(Stack[SP]); break;
01051           case  cCosh: Stack[SP] = cosh(Stack[SP]); break;
01052 
01053           case   cCot:
01054               {
01055                   double t = tan(Stack[SP]);
01056                   if(t == 0) { evalErrorType=1; return 0; }
01057                   Stack[SP] = 1/t; break;
01058               }
01059           case   cCsc:
01060               {
01061                   double s = sin(Stack[SP]);
01062                   if(s == 0) { evalErrorType=1; return 0; }
01063                   Stack[SP] = 1/s; break;
01064               }
01065 
01066 
01067 #ifndef DISABLE_EVAL
01068           case  cEval:
01069               {
01070                   double retVal = 0;
01071                   if(evalRecursionLevel == EVAL_MAX_REC_LEVEL)
01072                   {
01073                       evalErrorType = 5;
01074                   }
01075                   else
01076                   {
01077                       data->Stack = new double[data->StackSize];
01078                       ++evalRecursionLevel;
01079                       retVal = Eval(&Stack[SP-data->varAmount+1]);
01080                       --evalRecursionLevel;
01081                       delete[] data->Stack;
01082                       data->Stack = Stack;
01083                   }
01084                   SP -= data->varAmount-1;
01085                   Stack[SP] = retVal;
01086                   break;
01087               }
01088 #endif
01089 
01090           case   cExp: Stack[SP] = exp(Stack[SP]); break;
01091           case cFloor: Stack[SP] = floor(Stack[SP]); break;
01092 
01093           case    cIf:
01094               {
01095                   unsigned jumpAddr = ByteCode[++IP];
01096                   unsigned immedAddr = ByteCode[++IP];
01097                   if(doubleToInt(Stack[SP]) == 0)
01098                   {
01099                       IP = jumpAddr;
01100                       DP = immedAddr;
01101                   }
01102                   --SP; break;
01103               }
01104 
01105           case   cInt: Stack[SP] = floor(Stack[SP]+.5); break;
01106           case   cLog: if(Stack[SP] <= 0) { evalErrorType=3; return 0; }
01107                        Stack[SP] = log(Stack[SP]); break;
01108           case cLog10: if(Stack[SP] <= 0) { evalErrorType=3; return 0; }
01109                        Stack[SP] = log10(Stack[SP]); break;
01110           case   cMax: Stack[SP-1] = Max(Stack[SP-1], Stack[SP]);
01111                        --SP; break;
01112           case   cMin: Stack[SP-1] = Min(Stack[SP-1], Stack[SP]);
01113                        --SP; break;
01114           case   cSec:
01115               {
01116                   double c = cos(Stack[SP]);
01117                   if(c == 0) { evalErrorType=1; return 0; }
01118                   Stack[SP] = 1/c; break;
01119               }
01120           case   cSin: Stack[SP] = sin(Stack[SP]); break;
01121           case  cSinh: Stack[SP] = sinh(Stack[SP]); break;
01122           case  cSqrt: if(Stack[SP] < 0) { evalErrorType=2; return 0; }
01123                        Stack[SP] = sqrt(Stack[SP]); break;
01124           case   cTan: Stack[SP] = tan(Stack[SP]); break;
01125           case  cTanh: Stack[SP] = tanh(Stack[SP]); break;
01126 
01127 
01128 // Misc:
01129           case cImmed: Stack[++SP] = Immed[DP++]; break;
01130           case  cJump: DP = ByteCode[IP+2];
01131                        IP = ByteCode[IP+1];
01132                        break;
01133 
01134 // Operators:
01135           case   cNeg: Stack[SP] = -Stack[SP]; break;
01136           case   cAdd: Stack[SP-1] += Stack[SP]; --SP; break;
01137           case   cSub: Stack[SP-1] -= Stack[SP]; --SP; break;
01138           case   cMul: Stack[SP-1] *= Stack[SP]; --SP; break;
01139           case   cDiv: if(Stack[SP] == 0) { evalErrorType=1; return 0; }
01140                        Stack[SP-1] /= Stack[SP]; --SP; break;
01141           case   cMod: if(Stack[SP] == 0) { evalErrorType=1; return 0; }
01142                        Stack[SP-1] = fmod(Stack[SP-1], Stack[SP]);
01143                        --SP; break;
01144           case   cPow: Stack[SP-1] = pow(Stack[SP-1], Stack[SP]);
01145                        --SP; break;
01146 
01147 #ifdef FP_EPSILON
01148           case cEqual: Stack[SP-1] =
01149                            (fabs(Stack[SP-1]-Stack[SP]) <= FP_EPSILON);
01150                        --SP; break;
01151           case cNEqual: Stack[SP-1] =
01152                             (fabs(Stack[SP-1] - Stack[SP]) >= FP_EPSILON);
01153                        --SP; break;
01154           case  cLess: Stack[SP-1] = (Stack[SP-1] < Stack[SP]-FP_EPSILON);
01155                        --SP; break;
01156           case  cLessOrEq: Stack[SP-1] = (Stack[SP-1] <= Stack[SP]+FP_EPSILON);
01157                        --SP; break;
01158           case cGreater: Stack[SP-1] = (Stack[SP-1]-FP_EPSILON > Stack[SP]);
01159                          --SP; break;
01160           case cGreaterOrEq: Stack[SP-1] =
01161                                  (Stack[SP-1]+FP_EPSILON >= Stack[SP]);
01162                          --SP; break;
01163 #else
01164           case cEqual: Stack[SP-1] = (Stack[SP-1] == Stack[SP]);
01165                        --SP; break;
01166           case cNEqual: Stack[SP-1] = (Stack[SP-1] != Stack[SP]);
01167                        --SP; break;
01168           case  cLess: Stack[SP-1] = (Stack[SP-1] < Stack[SP]);
01169                        --SP; break;
01170           case  cLessOrEq: Stack[SP-1] = (Stack[SP-1] <= Stack[SP]);
01171                        --SP; break;
01172           case cGreater: Stack[SP-1] = (Stack[SP-1] > Stack[SP]);
01173                          --SP; break;
01174           case cGreaterOrEq: Stack[SP-1] = (Stack[SP-1] >= Stack[SP]);
01175                          --SP; break;
01176 #endif
01177 
01178           case   cAnd: Stack[SP-1] =
01179                            (doubleToInt(Stack[SP-1]) &&
01180                             doubleToInt(Stack[SP]));
01181                        --SP; break;
01182           case    cOr: Stack[SP-1] =
01183                            (doubleToInt(Stack[SP-1]) ||
01184                             doubleToInt(Stack[SP]));
01185                        --SP; break;
01186           case   cNot: Stack[SP] = !doubleToInt(Stack[SP]); break;
01187 
01188 // Degrees-radians conversion:
01189           case   cDeg: Stack[SP] = RadiansToDegrees(Stack[SP]); break;
01190           case   cRad: Stack[SP] = DegreesToRadians(Stack[SP]); break;
01191 
01192 // User-defined function calls:
01193           case cFCall:
01194               {
01195                   unsigned index = ByteCode[++IP];
01196                   unsigned params = data->FuncPtrs[index].params;
01197                   double retVal =
01198                       data->FuncPtrs[index].ptr(&Stack[SP-params+1]);
01199                   SP -= int(params)-1;
01200                   Stack[SP] = retVal;
01201                   break;
01202               }
01203 
01204           case cPCall:
01205               {
01206                   unsigned index = ByteCode[++IP];
01207                   unsigned params = data->FuncParsers[index]->data->varAmount;
01208                   double retVal =
01209                       data->FuncParsers[index]->Eval(&Stack[SP-params+1]);
01210                   SP -= int(params)-1;
01211                   Stack[SP] = retVal;
01212                   break;
01213               }
01214 
01215 
01216 #ifdef SUPPORT_OPTIMIZER
01217           case   cVar: break; // Paranoia. These should never exist
01218           case   cDup: Stack[SP+1] = Stack[SP]; ++SP; break;
01219           case   cInv:
01220               if(Stack[SP] == 0.0) { evalErrorType=1; return 0; }
01221               Stack[SP] = 1.0/Stack[SP];
01222               break;
01223 #endif
01224 
01225 // Variables:
01226           default:
01227               Stack[++SP] = Vars[ByteCode[IP]-VarBegin];
01228         }
01229     }
01230 
01231     evalErrorType=0;
01232     return Stack[SP];
01233 }
01234 
01235 
01236 #ifdef FUNCTIONPARSER_SUPPORT_DEBUG_OUTPUT
01237 namespace
01238 {
01239     inline void printHex(std::ostream& dest, unsigned n)
01240     {
01241         dest.width(8); dest.fill('0'); hex(dest); //uppercase(dest);
01242         dest << n;
01243     }
01244 }
01245 
01246 void FunctionParser::PrintByteCode(std::ostream& dest) const
01247 {
01248     const unsigned* const ByteCode = data->ByteCode;
01249     const double* const Immed = data->Immed;
01250 
01251     for(unsigned IP=0, DP=0; IP<data->ByteCodeSize; ++IP)
01252     {
01253         printHex(dest, IP);
01254         dest << ": ";
01255 
01256         unsigned opcode = ByteCode[IP];
01257 
01258         switch(opcode)
01259         {
01260           case cIf:
01261               dest << "jz\t";
01262               printHex(dest, ByteCode[IP+1]+1);
01263               dest << endl;
01264               IP += 2;
01265               break;
01266 
01267           case cJump:
01268               dest << "jump\t";
01269               printHex(dest, ByteCode[IP+1]+1);
01270               dest << endl;
01271               IP += 2;
01272               break;
01273           case cImmed:
01274               dest.precision(10);
01275               dest << "push\t" << Immed[DP++] << endl;
01276               break;
01277 
01278           case cFCall:
01279               {
01280                   unsigned index = ByteCode[++IP];
01281                   Data::VarMap_t::const_iterator iter =
01282                       data->FuncPtrNames.begin();
01283                   while(iter->second != index) ++iter;
01284                   dest << "fcall\t" << iter->first
01285                        << " (" << data->FuncPtrs[index].params << ")" << endl;
01286                   break;
01287               }
01288 
01289           case cPCall:
01290               {
01291                   unsigned index = ByteCode[++IP];
01292                   Data::VarMap_t::const_iterator iter =
01293                       data->FuncParserNames.begin();
01294                   while(iter->second != index) ++iter;
01295                   dest << "pcall\t" << iter->first
01296                        << " (" << data->FuncParsers[index]->data->varAmount
01297                        << ")" << endl;
01298                   break;
01299               }
01300 
01301           default:
01302               if(opcode < VarBegin)
01303               {
01304                   string n;
01305                   unsigned params = 1;
01306                   switch(opcode)
01307                   {
01308                     case cNeg: n = "neg"; break;
01309                     case cAdd: n = "add"; break;
01310                     case cSub: n = "sub"; break;
01311                     case cMul: n = "mul"; break;
01312                     case cDiv: n = "div"; break;
01313                     case cMod: n = "mod"; break;
01314                     case cPow: n = "pow"; break;
01315                     case cEqual: n = "eq"; break;
01316                     case cNEqual: n = "neq"; break;
01317                     case cLess: n = "lt"; break;
01318                     case cLessOrEq: n = "le"; break;
01319                     case cGreater: n = "gt"; break;
01320                     case cGreaterOrEq: n = "ge"; break;
01321                     case cAnd: n = "and"; break;
01322                     case cOr: n = "or"; break;
01323                     case cNot: n = "not"; break;
01324                     case cDeg: n = "deg"; break;
01325                     case cRad: n = "rad"; break;
01326 
01327 #ifndef DISABLE_EVAL
01328                     case cEval: n = "call\t0"; break;
01329 #endif
01330 
01331 #ifdef SUPPORT_OPTIMIZER
01332                     case cVar: n = "(var)"; break;
01333                     case cDup: n = "dup"; break;
01334                     case cInv: n = "inv"; break;
01335 #endif
01336 
01337                     default:
01338                         n = Functions[opcode-cAbs].name;
01339                         params = Functions[opcode-cAbs].params;
01340                   }
01341                   dest << n;
01342                   if(params != 1) dest << " (" << params << ")";
01343                   dest << endl;
01344               }
01345               else
01346               {
01347                   dest << "push\tVar" << opcode-VarBegin << endl;
01348               }
01349         }
01350     }
01351 }
01352 #endif
01353 
01354 
01355 
01356 
01357 #ifndef SUPPORT_OPTIMIZER
01358 void FunctionParser::MakeTree(void *) const {}
01359 void FunctionParser::Optimize()
01360 {
01361     // Do nothing if no optimizations are supported.
01362 }
01363 #endif