src/Qtx/QtxParser.cxx

   1
   2 #include "QtxParser.h"
   3 #include "QtxOperations.h"
   4
   5 //================================================================
   6 // Function :
   7 // Purpose  :
   8 //================================================================
   9 QtxParser::QtxParser( QtxOperations* operations,
  10                       const QString& expr )
  11 : myOperations( operations )
  12 {
  13     if( myOperations )
  14     {
  15         setLastError( OK );
  16         setExpr( expr );
  17     }
  18     else
  19         setLastError( OperationsNull );
  20 }
  21
  22 //================================================================
  23 // Function :
  24 // Purpose  :
  25 //================================================================
  26 QtxParser::~QtxParser()
  27 {
  28 }
  29
  30 //================================================================
  31 // Function :
  32 // Purpose  :
  33 //================================================================
  34 int QtxParser::search( const QStringList& list, const QString& str, int offset,
  35                        int& matchLen, int& listind )
  36 {
  37     QStringList::const_iterator anIt = list.begin(), aLast = list.end();
  38     int min = -1;
  39     for( int ind = 0; anIt!=aLast; anIt++, ind++ )
  40     {
  41       //const char* where = str.latin1(), *what = (*anIt).latin1();
  42         int pos = str.find( *anIt, offset );
  43         if( pos>=0 && ( min < 0 || min > pos ||
  44                         ( min==pos && matchLen< (int)(*anIt).length() ) ) )
  45         {
  46             min = pos;
  47             listind = ind;
  48             matchLen = (*anIt).length();
  49         }
  50     }
  51     if( min<0 )
  52         matchLen = 0;
  53     return min;
  54 }
  55
  56 //================================================================
  57 // Function :
  58 // Purpose  :
  59 //================================================================
  60 QString QtxParser::note( const QString& str, int pos, int len )
  61 {
  62     return str.mid( pos, len ).stripWhiteSpace();
  63 }
  64
  65 //================================================================
  66 // Function :
  67 // Purpose  :
  68 //================================================================
  69 bool QtxParser::prepare( const QString& expr, Postfix& post )
  70 {
  71     int pos = 0, len = expr.length();
  72     QValueStack< int > aBracketStack;
  73     QStringList anOpers, anOpenBr, aCloseBr;
  74     if( myOperations )
  75     {
  76         myOperations->bracketsList( anOpenBr, true );
  77         myOperations->bracketsList( aCloseBr, false );
  78         myOperations->opersList( anOpers );
  79     }
  80     else
  81     {
  82         setLastError( OperationsNull );
  83         return false;
  84     }
  85
  86     while( pos < len && lastError()==OK )
  87     {
  88         PostfixItem item;
  89         while( expr[ pos ].isSpace() && pos<len ) pos++;
  90         if( pos>=len )
  91             break;
  92
  93         int mBrLen = 0, mLen = 0, br_ind = -1, op_ind = -1;
  94         int oPos = search( anOpenBr, expr, pos, mBrLen, br_ind ),
  95             cPos = oPos==pos ? -1 : search( aCloseBr, expr, pos, mBrLen, br_ind ),
  96             opPos = search( anOpers, expr, pos, mLen, op_ind );
  97
  98         if( expr[ pos ]=="'" )
  99         {
 100             int vpos = pos+1;
 101             while ( vpos< (int)expr.length() && expr[ vpos ]!="'" )
 102                 vpos++;
 103
 104             mLen = vpos-pos+1;
 105
 106             int res = myOperations->createValue( note( expr, pos, mLen ), item.myValue );
 107             item.myType = res ? Value : Param;
 108             post.append( item );
 109             pos = vpos+1;
 110             continue;
 111         }
 112
 113         if( oPos==pos )
 114         {
 115             aBracketStack.push( br_ind );
 116             item.myValue = note( expr, pos, mBrLen );
 117             item.myType = Open;
 118             post.append( item );
 119         }
 120
 121         else if( cPos==pos )
 122         {
 123             if( aBracketStack.count()==0 )
 124             {
 125                 setLastError( ExcessClose );
 126                 break;
 127             }
 128             if( br_ind!=aBracketStack.top() )
 129             {
 130                 setLastError( BracketsNotMatch );
 131                 break;
 132             }
 133             else
 134             {
 135                 aBracketStack.pop();
 136                 item.myValue = note( expr, pos, mBrLen );
 137                 item.myType = Close;
 138                 post.append( item );
 139             }
 140         }
 141         else
 142             mBrLen = 0;
 143
 144         if( opPos==pos )
 145         {
 146             mBrLen = 0;
 147             item.myValue = note( expr, pos, mLen );
 148             item.myType = Binary;
 149             //the type is set by default;
 150             //the method setOperationTypes will set correct types
 151
 152             if( oPos==pos )
 153                 post.insert( post.at( post.count()-1 ), item );
 154             else
 155                 post.append( item );
 156         }
 157         else
 158         {
 159             mLen = 0;
 160             if( oPos!=pos && cPos!=pos )
 161             {
 162                 int i;
 163                 for( i=pos+1; i<(int)expr.length(); i++ )
 164                     if( expr[ i ].isSpace() )
 165                         break;
 166
 167                 int vpos = i;
 168                 if( oPos>=0 && oPos<vpos )
 169                     vpos = oPos;
 170                 if( cPos>=0 && cPos<vpos )
 171                     vpos = cPos;
 172                 if( opPos>=0 && opPos<vpos )
 173                     vpos = opPos;
 174
 175                 while( vpos<(int)expr.length() &&
 176                        ( expr[vpos].isLetter() || expr[vpos].isDigit() || expr[vpos]=='_' ) )
 177                     vpos++;
 178
 179                 mLen = vpos-pos;
 180                 bool res = myOperations->createValue( note( expr, pos, mLen ), item.myValue );
 181                 item.myType = res ? Value : Param;
 182                 post.append( item );
 183             }
 184         }
 185
 186         pos+=mBrLen+mLen;
 187     }
 188
 189     //Bracket checking
 190     PostfixIterator anIt = post.begin(),
 191                     aLast = post.end();
 192     int brValue = 0;
 193     for( ; anIt!=aLast; anIt++ )
 194         if( (*anIt).myType==Open )
 195             brValue++;
 196         else if( (*anIt).myType==Close )
 197             if( brValue>0 )
 198                 brValue--;
 199             else
 200             {
 201                 setLastError( ExcessClose );
 202                 break;
 203             }
 204     if( brValue>0 )
 205         setLastError( CloseExpected );
 206
 207     return lastError()==OK;
 208 }
 209
 210 //================================================================
 211 // Function :
 212 // Purpose  :
 213 //================================================================
 214 bool QtxParser::setOperationTypes( Postfix& post )
 215 {
 216     Postfix::iterator aStart = post.begin(),
 217                       aLast = post.end(),
 218                       anIt = aStart, aPrev, aNext;
 219     QStringList anOpen, aClose;
 220     if( myOperations )
 221     {
 222         myOperations->bracketsList( anOpen, true );
 223         myOperations->bracketsList( aClose, false );
 224     }
 225     else
 226         return false;
 227
 228     for( ; anIt!=aLast; anIt++ )
 229     {
 230         aPrev = anIt; aPrev--;
 231         aNext = anIt; aNext++;
 232         if( (*anIt).myType != Binary )
 233             continue;
 234
 235         if( ( anIt==aStart || (*aPrev).myType == Open ||
 236                               (*aPrev).myType == Pre ||
 237                               (*aPrev).myType == Binary )
 238             &&
 239             aNext!=aLast && ( (*aNext).myType == Value ||
 240                               (*aNext).myType == Param ||
 241                               (*aNext).myType == Open  ||
 242                               (*aNext).myType == Binary ) )
 243             (*anIt).myType = Pre;
 244
 245         else if( anIt!=aStart && ( (*aPrev).myType == Close ||
 246                                    (*aPrev).myType == Param ||
 247                                    (*aPrev).myType == Value ||
 248                                    (*aPrev).myType == Pre ||
 249                                    (*aPrev).myType == Post ||
 250                                    (*aPrev).myType == Binary )
 251                  &&
 252                  ( aNext==aLast || (*aNext).myType == Close ) )
 253             (*anIt).myType = Post;
 254
 255         if( anOpen.contains( ( *anIt ).myValue.toString() )>0 )
 256             (*anIt).myType = Pre;
 257         else if( aClose.contains( ( *anIt ).myValue.toString() )>0 )
 258             (*anIt).myType = Post;
 259     }
 260
 261     return lastError()==OK;
 262 }
 263
 264 //================================================================
 265 // Function :
 266 // Purpose  :
 267 //================================================================
 268 int QtxParser::globalBrackets( const QtxParser::Postfix& post, int f, int l )
 269 {
 270     int i,
 271         start_br = 0,
 272         fin_br = 0,
 273         br = 0,
 274         br_num = 0,
 275         min_br_num = (l-f+1)*5;
 276
 277     for( i=f; i<=l; i++ )
 278         if( post[ i ].myType==QtxParser::Open )
 279             start_br++;
 280         else
 281             break;
 282     for( i=l; i>=f; i-- )
 283         if( post[ i ].myType==QtxParser::Close )
 284             fin_br++;
 285         else
 286             break;
 287
 288     br = start_br<fin_br ? start_br : fin_br;
 289     for( i=f+br; i<=l-br; i++ )
 290     {
 291         if( post[i].myType==QtxParser::Open )
 292             br_num++;
 293         else if( post[i].myType==QtxParser::Close )
 294             br_num--;
 295         if( br_num<min_br_num )
 296             min_br_num = br_num;
 297     }
 298
 299     return br+min_br_num;
 300 }
 301
 302 //================================================================
 303 // Function :
 304 // Purpose  :
 305 //================================================================
 306 bool QtxParser::sort( const Postfix& post, Postfix& res,
 307                       const QStringList& anOpen,
 308                       const QStringList& aClose,
 309                       int f, int l )
 310 {
 311     if( l<f )
 312         return true;
 313
 314     if( f<0 )
 315         f = 0;
 316     if( l<0 )
 317         l = post.count()-1;
 318
 319     int br = globalBrackets( post, f, l );
 320     f+=br; l-=br;
 321
 322     if( f==l && f>=0 )
 323         res.append( post[ f ] );
 324     if( l<=f )
 325         return true;
 326
 327     if( myOperations )
 328     {
 329         int min = -1;
 330         QIntList argmin;
 331         QValueList< PostfixItemType > min_types;
 332
 333         //Find operation with minimal priority
 334         //PostfixIterator anIt = post.at( f ),
 335         //                aLast = post.at( l+1 );
 336         for( int i=0, j=f; j<=l; i++, j++ )
 337         {
 338             const PostfixItem& item = post[ j ];
 339             PostfixItemType tt = item.myType;
 340             if( tt==Binary || tt==Pre || tt==Post )
 341             {
 342                 int cur_pr = myOperations->prior( item.myValue.toString(), tt==Binary );
 343                 if( cur_pr>0 )
 344                 {
 345                     if( min<0 || min>=cur_pr )
 346                     {
 347                         if( min==cur_pr )
 348                         {
 349                             argmin.append( f+i );
 350                             min_types.append( tt );
 351                         }
 352                         else
 353                         {
 354                             min = cur_pr;
 355                             argmin.clear(); argmin.append( f+i );
 356                             min_types.clear(); min_types.append( tt );
 357                         }
 358                     }
 359                 }
 360                 else
 361                 {
 362                     setLastError( InvalidOperation );
 363                     break;
 364                 }
 365             }
 366             else if( tt==Open )
 367             {
 368                 QString opBr = item.myValue.toString();
 369                 int ind = anOpen.findIndex( opBr ), brValue = 0;
 370                 while( j<=l )
 371                 {
 372                     const PostfixItem& anItem = post[ j ];
 373                     if( anItem.myType==Open )
 374                         brValue++;
 375
 376                     if( anItem.myType==Close )
 377                     {
 378                         brValue--;
 379                         QString clBr = anItem.myValue.toString();
 380                         if( aClose.findIndex( clBr )==ind && brValue==0 )
 381                             break;
 382                     }
 383                     i++; j++;
 384                 }
 385                 if( brValue>0 )
 386                 {
 387                     setLastError( CloseExpected );
 388                     break;
 389                 }
 390             }
 391         }
 392
 393         if( lastError()==OK )
 394             if( min>=0 )
 395             {
 396                 QValueList< Postfix > parts;
 397                 QIntList::const_iterator anIt = argmin.begin(),
 398                                          aLast = argmin.end();
 399                 Postfix one;
 400                 bool ok = sort( post, one, anOpen, aClose, f, *anIt - 1 );
 401                 parts.append( one );
 402                 one.clear();
 403                 for( ; anIt!=aLast && ok; anIt++ )
 404                 {
 405                     QIntList::const_iterator aNext = anIt; aNext++;
 406                     ok = sort( post, one, anOpen, aClose, *anIt + 1, aNext==aLast ? l : *aNext - 1 );
 407                     parts.append( one );
 408                     one.clear();
 409                 }
 410                 if( !ok )
 411                     return false;
 412
 413                 QValueList< Postfix >::const_iterator aPIt = parts.begin();
 414                 QValueList< PostfixItemType >::const_iterator aTIt = min_types.begin();
 415                 QValueStack< PostfixItem > aStack;
 416                 res += (*aPIt); aPIt++;
 417                 anIt = argmin.begin();
 418                 for( ; anIt!=aLast; anIt++, aPIt++, aTIt++ )
 419                 {
 420                     if( *aTIt==Pre )
 421                         if( anOpen.contains( post[ *anIt ].myValue.toString() )==0 )
 422                         {
 423                             res+=(*aPIt);
 424                             aStack.push( post[ *anIt ] );
 425                         }
 426                         else
 427                         {
 428                             res.append( post[ *anIt ] );
 429                             res+=(*aPIt);
 430                         }
 431                     else
 432                     {
 433                         res+=(*aPIt);
 434                         while( !aStack.isEmpty() )
 435                         {
 436                             res.append( aStack.top() );
 437                             aStack.pop();
 438                         }
 439                         res.append( post[ *anIt ] );
 440                     }
 441                 }
 442                 while( !aStack.isEmpty() )
 443                 {
 444                     res.append( aStack.top() );
 445                     aStack.pop();
 446                 }
 447             }
 448             else
 449             { //there are no operations
 450                 PostfixIterator anIt = post.at( f ),
 451                                 aLast = post.at( l+1 );
 452                 for( ; anIt!=aLast; anIt++ )
 453                     if( (*anIt).myType==Value || (*anIt).myType==Param )
 454                         res.append( *anIt );
 455             }
 456     }
 457     else
 458         setLastError( OperationsNull );
 459
 460     return lastError()==OK;
 461 }
 462
 463 //================================================================
 464 // Function :
 465 // Purpose  :
 466 //================================================================
 467 bool QtxParser::parse( const QString& expr )
 468 {
 469     myPost.clear();
 470
 471     Postfix p;
 472     QStringList opens, closes;
 473
 474     if( myOperations )
 475     {
 476         setLastError( OK );
 477         myOperations->bracketsList( opens, true );
 478         myOperations->bracketsList( closes, false );
 479     }
 480     else
 481     {
 482         setLastError( OperationsNull );
 483         return false;
 484     }
 485
 486     //return prepare( expr, myPost ) && setOperationTypes( myPost );
 487     return prepare( expr, p ) && setOperationTypes( p ) &&
 488            sort( p, myPost, opens, closes );
 489 }
 490
 491 //================================================================
 492 // Function :
 493 // Purpose  :
 494 //================================================================
 495 bool QtxParser::calculate( const QString& op, QtxValue& v1, QtxValue& v2 )
 496 {
 497     Error err = myOperations->isValid( op, v1.type(), v2.type() );
 498     if( err==OK )
 499         setLastError( myOperations->calculate( op, v1, v2 ) );
 500     else
 501         setLastError( err );
 502
 503     return lastError()==OK;
 504 }
 505
 506 //================================================================
 507 // Function :
 508 // Purpose  :
 509 //================================================================
 510 QtxValue QtxParser::calculate()
 511 {
 512     setLastError( OK );
 513
 514     QStringList anOpen, aClose;
 515     if( myOperations )
 516     {
 517         myOperations->bracketsList( anOpen, true );
 518         myOperations->bracketsList( aClose, false );
 519     }
 520     else
 521     {
 522         setLastError( OperationsNull );
 523         return QtxValue();
 524     }
 525
 526     QtxValueStack aStack;
 527     PostfixIterator anIt = myPost.begin(),
 528                     aLast = myPost.end();
 529     for( ; anIt!=aLast && lastError()==OK; anIt++ )
 530     {
 531         QString nn = (*anIt).myValue.toString();
 532         if( (*anIt).myType==Param )
 533         {
 534             if( has( nn ) )
 535             {
 536                 QVariant& v = myParameters[ nn ];
 537                 if( v.isValid() )
 538                     aStack.push( v );
 539                 else
 540                     setLastError( InvalidToken );
 541             }
 542             else
 543                 setLastError( InvalidToken );
 544         }
 545
 546         else if( (*anIt).myType==Value )
 547             aStack.push( (*anIt).myValue );
 548
 549         else if( (*anIt).myType==Pre || (*anIt).myType==Post )
 550         {
 551             if( anOpen.contains( nn )>0 )
 552             {
 553                 QtxValue inv;
 554                 if( calculate( nn, inv, inv ) )
 555                     aStack.push( QtxValue() );
 556             }
 557             else if( aClose.contains( nn )>0 )
 558             {
 559                 QValueList< QtxValue > set;
 560                 while( true )
 561                 {
 562                     if( aStack.count()==0 )
 563                     {
 564                         setLastError( StackUnderflow );
 565                         break;
 566                     }
 567                     if( aStack.top().isValid() )
 568                     {
 569                         set.append( aStack.top() );
 570                         aStack.pop();
 571                     }
 572                     else
 573                     {
 574                         aStack.pop();
 575                         break;
 576                     }
 577                 }
 578
 579                 QtxValue qSet = set, inv;
 580                 if( calculate( nn, qSet, inv ) )
 581                     aStack.push( set );
 582             }
 583             else if( aStack.count()>=1 )
 584             {
 585                 QtxValue inv;
 586                 QtxValue* v1 = &aStack.top(), *v2 = &inv; //"post-" case
 587                 if( (*anIt).myType==Pre )
 588                 {
 589                     v2 = &aStack.top(); v1 = &inv;
 590                 }
 591
 592                 calculate( nn, *v1, *v2 );
 593             }
 594             else
 595                 setLastError( StackUnderflow );
 596         }
 597
 598         else if( (*anIt).myType==Binary )
 599         {
 600             if( aStack.count()>=2 )
 601             {
 602                 QVariant v2 = aStack.top(); aStack.pop();
 603                 calculate( nn, aStack.top(), v2 );
 604             }
 605             else
 606                 setLastError( StackUnderflow );
 607         }
 608     }
 609
 610     QtxValue res;
 611     if( lastError()==OK )
 612     {
 613         int count = aStack.count();
 614         if( count==0 )
 615             setLastError( StackUnderflow );
 616         else if( count==1 )
 617             res = aStack.top();
 618         else
 619             setLastError( ExcessData );
 620     }
 621     return res;
 622 }
 623
 624 //================================================================
 625 // Function :
 626 // Purpose  :
 627 //================================================================
 628 QtxValue QtxParser::calculate( const QString& expr )
 629 {
 630     setExpr( expr );
 631     return calculate();
 632 }
 633
 634 //================================================================
 635 // Function :
 636 // Purpose  :
 637 //================================================================
 638 bool QtxParser::setExpr( const QString& expr )
 639 {
 640     return parse( expr );
 641 }
 642
 643 //================================================================
 644 // Function :
 645 // Purpose  :
 646 //================================================================
 647 bool QtxParser::has( const QString& name ) const
 648 {
 649     return myParameters.contains( name.stripWhiteSpace() );
 650 }
 651
 652 //================================================================
 653 // Function :
 654 // Purpose  :
 655 //================================================================
 656 void QtxParser::set( const QString& name, const QtxValue& value )
 657 {
 658     myParameters[ name.stripWhiteSpace() ] = value;
 659 }
 660
 661 //================================================================
 662 // Function :
 663 // Purpose  :
 664 //================================================================
 665 bool QtxParser::remove( const QString& name )
 666 {
 667     QString sname = name.stripWhiteSpace();
 668     bool res = has( sname );
 669     if( res )
 670         myParameters.remove( sname );
 671     return res;
 672 }
 673
 674 //================================================================
 675 // Function :
 676 // Purpose  :
 677 //================================================================
 678 QtxValue QtxParser::value( const QString& name ) const
 679 {
 680     QString sname = name.stripWhiteSpace();
 681     if( has( sname ) )
 682         return myParameters[ sname ].toString();
 683     else
 684         return QtxValue();
 685 }
 686
 687 //================================================================
 688 // Function :
 689 // Purpose  :
 690 //================================================================
 691 bool QtxParser::firstInvalid( QString& name ) const
 692 {
 693     QMap< QString, QtxValue >::const_iterator anIt = myParameters.begin(),
 694                                               aLast = myParameters.end();
 695     for( ; anIt!=aLast; anIt++ )
 696         if( !anIt.data().isValid() )
 697         {
 698             name = anIt.key();
 699             return true;
 700         }
 701     return false;
 702 }
 703
 704 //================================================================
 705 // Function :
 706 // Purpose  :
 707 //================================================================
 708 void QtxParser::removeInvalids()
 709 {
 710     QStringList toDelete;
 711     QMap< QString, QtxValue >::const_iterator anIt = myParameters.begin(),
 712                                               aLast = myParameters.end();
 713     for( ; anIt!=aLast; anIt++ )
 714         if( !anIt.data().isValid() )
 715             toDelete.append( anIt.key() );
 716
 717     QStringList::const_iterator aLIt = toDelete.begin(),
 718                                 aLLast = toDelete.end();
 719     for( ; aLIt!=aLLast; aLIt++ )
 720         myParameters.remove( *aLIt );
 721 }
 722
 723 //================================================================
 724 // Function :
 725 // Purpose  :
 726 //================================================================
 727 QtxParser::Error QtxParser::lastError() const
 728 {
 729     return myLastError;
 730 }
 731
 732 //================================================================
 733 // Function :
 734 // Purpose  :
 735 //================================================================
 736 void QtxParser::setLastError( QtxParser::Error err )
 737 {
 738     myLastError = err;
 739 }
 740
 741 //================================================================
 742 // Function :
 743 // Purpose  :
 744 //================================================================
 745 QString QtxParser::dump() const
 746 {
 747     return dump( myPost );
 748 }
 749
 750 //================================================================
 751 // Function :
 752 // Purpose  :
 753 //================================================================
 754 QString QtxParser::dump( const Postfix& post ) const
 755 {
 756     QString res;
 757
 758     if( myOperations )
 759     {
 760         PostfixIterator anIt = post.begin(),
 761                         aLast = post.end();
 762         for( ; anIt!=aLast; anIt++ )
 763         {
 764             if( (*anIt).myType == Value &&
 765                     ( ( *anIt ).myValue.type()==QVariant::String ||
 766                     ( *anIt ).myValue.type()==QVariant::CString ) )
 767                 res += "'" + ( *anIt ).myValue.toString() + "'";
 768             else
 769                 res += ( *anIt ).myValue.toString();
 770             if( (*anIt).myType == Pre )
 771                 res += "(pre)";
 772             else if( (*anIt).myType == Post )
 773                 res += "(post)";
 774             else if( (*anIt).myType == Binary )
 775                 res += "(bin)";
 776
 777             res += "_";
 778         }
 779     }
 780     return res;
 781 }
 782
 783 //================================================================
 784 // Function :
 785 // Purpose  :
 786 //================================================================
 787 void QtxParser::paramsList( QStringList& list )
 788 {
 789     PostfixIterator anIt = myPost.begin(),
 790                     aLast = myPost.end();
 791     for( ; anIt!=aLast; anIt++ )
 792         if( (*anIt).myType==Param )
 793         {
 794             QString name = (*anIt).myValue.toString();
 795             if( list.contains( name )==0 )
 796                 list.append( name );
 797         }
 798 }
 799
 800 //================================================================
 801 // Function :
 802 // Purpose  :
 803 //================================================================
 804 void QtxParser::clear()
 805 {
 806     myParameters.clear();
 807 }
 808
 809 //================================================================
 810 // Function :
 811 // Purpose  :
 812 //================================================================
 813 QString QtxParser::toString( const QValueList< QtxValue >& list )
 814 {
 815     QValueList< QtxValue >::const_iterator anIt = list.begin(),
 816                                            aLast = list.end();
 817     QString res = "set : [ ";
 818     for( ; anIt!=aLast; anIt++ )
 819         res+=(*anIt).toString()+" ";
 820     res+="]";
 821     return res;
 822 }