git.intra.tuxee.net Git - tx/blob - xpathparser.py

   1 # -*- coding:utf-8 -*-
   2
   3 # XPath parser
   4 # Copyright (C) 2005  Frédéric Jolliton <frederic@jolliton.com>
   5 #
   6 # This program is free software; you can redistribute it and/or modify
   7 # it under the terms of the GNU General Public License as published by
   8 # the Free Software Foundation; either version 2 of the License, or
   9 # (at your option) any later version.
  10 #
  11 # This program is distributed in the hope that it will be useful,
  12 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 # GNU General Public License for more details.
  15 #
  16 # You should have received a copy of the GNU General Public License
  17 # along with this program; if not, write to the Free Software
  18 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA      02111-1307      USA
  19
  20 __all__ = [ 'parse' ]
  21
  22 import re
  23 import time
  24
  25 import parser
  26 from parser import *
  27
  28 first = lambda l : l[ 0 ]
  29 second = lambda l : l[ 1 ]
  30
  31 def debug( s ) :
  32
  33         print 'DEBUG' , s
  34         return s
  35
  36 def Debug( name ) :
  37
  38         def fun( s ) :
  39                 print 'DEBUG[%s] %s' % ( name , s )
  40         return fun
  41
  42 def join( lst ) :
  43
  44         return lst[ : 1 ] + lst[ 1 ]
  45
  46 def constantly( item ) :
  47
  48         return lambda o : item
  49
  50 def tag( name ) :
  51
  52         return lambda o : ( name , o )
  53
  54 def headIs( seq , o ) :
  55
  56         return isinstance( seq , ( tuple , list ) ) and seq[ 0 ] == o
  57
  58 EOS        = Regex( '$' )
  59
  60 textInsideComment = Regex( r'(?:[^:(]|:[^)]|\([^:])*' )
  61 comment = Wrapper()
  62 comment << Sequence( '(:' , List( textInsideComment , comment ) , ':)' )
  63
  64 space      = List( Regex( '\s*' ) , comment ).ignore()
  65
  66 reservedFunctionName = [
  67   'attribute' ,
  68   'comment' ,
  69   'document-node' ,
  70   'element' ,
  71   'if' ,
  72   'item' ,
  73   'node' ,
  74   'processing-instruction' ,
  75   'schema-attribute' ,
  76   'schema-element' ,
  77   'text' ,
  78   'typeswitch' ,
  79   'void'
  80 ]
  81
  82 def mark( s ) :
  83         def fun() :
  84                 print s
  85         return fun
  86
  87 def WithSpaceAround( expr ) :
  88         return Wrapper( Sequence( space , expr , space ).call( first ) )
  89
  90 xpString = lambda o : ( 'STRING' , o[ 1 : -1 ].replace( '""' , '"' ) )
  91
  92 rtNcname = '(?:[a-z_][-a-z_0-9]*)'
  93 rtQname  = '(?:(?:%s:)?%s)' % ( rtNcname , rtNcname )
  94
  95 #
  96 # [78] QName
  97 #
  98 qname = Regex( rtQname , re.I )
  99
 100 value = WithSpaceAround( qname )
 101
 102 expr = Wrapper()
 103 exprSingle = Wrapper()
 104
 105 #
 106 # [74] VarName
 107 #
 108 varName = qname
 109
 110 #
 111 # [73] StringLiteral
 112 #
 113 def xpString( e ) :
 114         if e[ 0 ] == '"' :
 115                 s = e[ 1 : -1 ].replace( '""' , '"' )
 116         elif e[ 0 ] == "'" :
 117                 s = e[ 1 : -1 ].replace( "''" , "'" )
 118         else :
 119                 raise NotReached
 120         return ( 'string' , s )
 121 stringLiteral = \
 122         Regex( '"(?:""|[^"])*"|\'(?:\'\'|[^\'])*\'' ).call( xpString )
 123
 124 #
 125 # [72] DoubleLiteral
 126 #
 127 doubleLiteral = \
 128         Regex( r'(?:\.\d+|\d+(?:\.\d*)?)[eE][+-]?\d+' ).call( tag( 'double' ) )
 129
 130 #
 131 # [71] DecimalLiteral
 132 #
 133 decimalLiteral = \
 134         Regex( r'\.\d+|\d+\.\d*' ).call( tag( 'decimal' ) )
 135
 136 #
 137 # [70] IntegerLiteral
 138 #
 139 integerLiteral = \
 140         Regex( '[-+]?\\d+' ).call( tag( 'integer' ) )
 141
 142 #
 143 # [68] ElementName
 144 #
 145 elementName = value
 146
 147 #
 148 # [67] AttributeName
 149 #
 150 attributeName = value
 151
 152 #
 153 # [64] ElementNameOrWildcard
 154 #
 155 elementNameOrWildcard = \
 156         Either( elementName ,
 157                         WithSpaceAround( Literal( '*' ) ) )
 158
 159 #
 160 # [63] ElementTest
 161 #
 162 def xpElementTest( e ) :
 163         if e[ 2 ] :
 164                 return ( 'element' , e[ 2 ][ 0 ] )
 165         else :
 166                 return ( 'element' , '*' )
 167 elementTest = \
 168         Sequence( 'element' ,
 169                           space ,
 170                           '(' ,
 171                           space ,
 172                           Optional( elementNameOrWildcard ) ,
 173                           space ,
 174                           ')' ).call( xpElementTest )
 175
 176 #
 177 # [60] AttribNameOrWildcard
 178 #
 179 attribNameOrWildcard = \
 180         Either( attributeName ,
 181                         WithSpaceAround( Literal( '*' ) ) )
 182
 183 #
 184 # [59] AttributeTest
 185 #
 186 def xpAttributeTest( e ) :
 187         if e[ 2 ] :
 188                 return ( 'attribute' , e[ 2 ][ 0 ] )
 189         else :
 190                 return ( 'attribute' , )
 191 attributeTest = \
 192         Sequence( 'attribute' ,
 193                           space ,
 194                           '(' ,
 195                           space ,
 196                           Optional( attribNameOrWildcard ) ,
 197                           space ,
 198                           ')' ).call( xpAttributeTest )
 199
 200 #
 201 # [57] CommentTest
 202 #
 203 commentTest = \
 204         Sequence( 'comment' ,
 205                           space ,
 206                           '(' ,
 207                           space ,
 208                           ')' ).call( constantly( ( 'comment' , ) ) )
 209
 210 #
 211 # [56] TextTest
 212 #
 213 textTest = \
 214         Sequence( 'text' ,
 215                           space ,
 216                           '(' ,
 217                           space ,
 218                           ')' ).call( constantly( ( 'text' , ) ) )
 219
 220 #
 221 # [55] DocumentTest
 222 #
 223 documentTest = \
 224         Sequence( 'document-node' ,
 225                           space ,
 226                           '(' ,
 227                           space ,
 228                           ')' ).call( constantly( ( 'document' , ) ) )
 229
 230 #
 231 # [54] AnyKindTest
 232 #
 233 anyKindTest = \
 234         Sequence( 'node' ,
 235                           space ,
 236                           '(' ,
 237                           space ,
 238                           ')' ).call( constantly( ( 'node' , ) ) )
 239
 240 #
 241 # [53] KindTest
 242 #
 243 kindTest = \
 244         Either( documentTest ,
 245                         elementTest ,
 246                         attributeTest ,
 247                         commentTest ,
 248                         textTest ,
 249                         anyKindTest )
 250
 251 #
 252 # [47] FunctionCall
 253 #
 254 def xpFunctionCall( e ) :
 255         if e[ 0 ] in reservedFunctionName :
 256                 raise Reject
 257         elif e[ 2 ] :
 258                 return ( 'call' , e[ 0 ] ) + tuple( e[ 2 ][ 0 ] )
 259         else :
 260                 return ( 'call' , e[ 0 ] )
 261 functionCall = \
 262         Sequence( qname ,
 263                           space ,
 264                           '(' ,
 265                           space ,
 266                           Optional( List( exprSingle , Literal( ',' ).ignore() ) ) ,
 267                           space ,
 268                           ')' ).call( xpFunctionCall )
 269
 270 #
 271 # [46] ContextItemExpr
 272 #
 273 contextItemExpr = \
 274         Literal( '.' )
 275
 276 #
 277 # [45] ParenthesizedExpr
 278 #
 279 def xpParenthesizedExpr( e ) :
 280         if not e :
 281                 return ( 'void' , )
 282         else :
 283                 return e[ 0 ]
 284 parenthesizedExpr = \
 285         Sequence( '(' , Optional( expr ) , ')' ).call( second ).call( xpParenthesizedExpr )
 286
 287 #
 288 # [44] VarRef
 289 #
 290 def xpVarRef( e ) :
 291         return ( 'varref' , e[ 1 ] )
 292 varRef = WithSpaceAround( Sequence( Literal( '$' ) , varName ) ).call( xpVarRef )
 293
 294 #
 295 # [43] NumericLiteral
 296 #
 297 numericLiteral = \
 298         Either( integerLiteral , decimalLiteral , doubleLiteral )
 299
 300 #
 301 # [42] Literal
 302 #
 303 literal = \
 304         Either( numericLiteral , stringLiteral )
 305
 306 #
 307 # [41] PrimaryExpr
 308 #
 309 primaryExpr = \
 310         Either( literal ,
 311                         varRef ,
 312                         parenthesizedExpr ,
 313                         contextItemExpr ,
 314                         functionCall )
 315
 316 #
 317 # [40] Predicate
 318 #
 319 predicate = Sequence( '[' , space , expr , space , ']' ).call( second )
 320
 321 #
 322 # [39] PredicateList
 323 #
 324 predicateList = \
 325         ZeroOrMore( predicate )
 326
 327 #
 328 # [38] FilterExpr
 329 #
 330 def xpFilterExpr( e ) :
 331         e , p = e
 332         if not p :
 333                 r = e
 334         else :
 335                 if e[ 0 ] == '.' :
 336                         # Allowd by grammar, but don't seem allowed by other XPath implementation. Bah.
 337                         raise Reject
 338                 r = ( 'filter' , e ) + tuple( p )
 339         return r
 340 filterExpr = \
 341         Sequence( primaryExpr ,
 342                           predicateList ).call( xpFilterExpr )
 343
 344 #
 345 # [37] Wildcard
 346 #
 347 wildcard = WithSpaceAround( '*' )
 348
 349 #
 350 # [36] NameTest
 351 #
 352 def xpNameTest( e ) :
 353         if e == '*' :
 354                 return ( 'name' , '*' )
 355         else :
 356                 return ( 'name' , e )
 357 nameTest = \
 358         Either( value ,
 359                         wildcard ).call( xpNameTest )
 360
 361 #
 362 # [35] NodeTest
 363 #
 364 nodeTest = \
 365         Either( kindTest ,
 366                         nameTest )
 367
 368 #
 369 # [34] AbbrevReverseStep
 370 #
 371 abbrevReverseStep = \
 372         Literal( '..' )
 373
 374 #
 375 # [33] ReverseAxis
 376 #
 377 reverseAxis = \
 378         Regex( '(' +
 379                    '|'.join( ( 'parent' ,
 380                                            'ancestor' ,
 381                                            'preceding-sibling' ,
 382                                            'preceding' ,
 383                                            'ancestor-or-self' ) ) +
 384                    ')::' )
 385
 386 #
 387 # [32] ReverseStep
 388 #
 389 def xpReverseStepUnabbrev( e ) :
 390         if headIs( e[ 1 ] , 'name' ) :
 391                 if e[ 0 ] == 'attribute' :
 392                         raise Reject
 393                 else :
 394                         default = 'element'
 395                 return ( e[ 0 ] , ( default , e[ 1 ][ 1 ] ) )
 396         else :
 397                 return tuple( e )
 398 reverseStep = \
 399         Either( Sequence( reverseAxis , nodeTest ).call( xpReverseStepUnabbrev ) ,
 400                         abbrevReverseStep )
 401
 402 #
 403 # [31] AbbrevForwardStep
 404 #
 405 def xpAbbrevForwardStep( e ) :
 406         if e[ 0 ] :
 407                 if headIs( e[ 1 ] , 'name' ) :
 408                         return ( 'attribute' , ( 'attribute' , e[ 1 ][ 1 ] ) )
 409                 else :
 410                         return ( 'attribute' , e[ 1 ] )
 411         else :
 412                 if headIs( e[ 1 ] , 'attribute' ) :
 413                         return ( 'attribute' , e[ 1 ] )
 414                 elif headIs( e[ 1 ] , 'name' ) :
 415                         return ( 'child' , ( 'element' , e[ 1 ][ 1 ] ) )
 416                 else :
 417                         return ( 'child' , e[ 1 ] )
 418 abbrevForwardStep = \
 419         Sequence( Optional( WithSpaceAround( '@' ) ) ,
 420                           nodeTest ).call( xpAbbrevForwardStep )
 421
 422 #
 423 # [30] ForwardAxis
 424 #
 425 forwardAxis = \
 426         Regex( '(' +
 427                    '|'.join( ( 'child' ,
 428                                            'descendant' ,
 429                                            'attribute' ,
 430                                            'self' ,
 431                                            'descendant-or-self' ,
 432                                            'following-sibling' ,
 433                                            'following' ) ) +
 434                    ')::' )
 435
 436 #
 437 # [29] ForwardStep
 438 #
 439 def xpForwardStepUnabbrev( e ) :
 440         if headIs( e[ 1 ] , 'name' ) :
 441                 if e[ 0 ] == 'attribute' :
 442                         default = 'attribute'
 443                 else :
 444                         default = 'element'
 445                 return ( e[ 0 ] , ( default , e[ 1 ][ 1 ] ) )
 446         else :
 447                 return tuple( e )
 448 forwardStep = \
 449         Either( Sequence( forwardAxis , nodeTest ).call( xpForwardStepUnabbrev ) ,
 450                         abbrevForwardStep )
 451
 452 #
 453 # [28] AxisStep
 454 #
 455 def xpAxisStep( e ) :
 456         if not e[ 1 ] :
 457                 if e[ 0 ] == '..' :
 458                         return ( 'parent' , ( 'node' , ) )
 459                 else :
 460                         return e[ 0 ]
 461         else :
 462                 if e[ 0 ] == '..' :
 463                         # See remark for '.'
 464                         raise Reject
 465                 return ( 'predicates' , e[ 0 ] ) + tuple( e[ 1 ] )
 466 axisStep = \
 467         Sequence( Either( forwardStep ,
 468                                           reverseStep ) ,
 469                           predicateList ).call( xpAxisStep )
 470
 471 #
 472 # [27] StepExpr
 473 #
 474 stepExpr = \
 475         Either( axisStep ,
 476                         filterExpr )
 477
 478 #
 479 # [26] RelativePathExpr
 480 #
 481 def xpRelativePathExpr( e ) :
 482         r , e = [ e[ 0 ] ] , e[ 1 : ]
 483         while e :
 484                 if e[ 0 ] == '//' :
 485                         r.append( ( 'descendant-or-self' , ( 'node' , ) ) )
 486                 r.append( e[ 1 ] )
 487                 e = e[ 2 : ]
 488         return r
 489 relativePathExpr = \
 490         List( stepExpr ,
 491                   Regex( '//|/' ) ).call( xpRelativePathExpr )
 492
 493 #
 494 # [25] PathExpr
 495 #
 496 # FIXME: Simplify (path E) into E ?
 497 #
 498 def xpPathExprRoot( e ) :
 499         return ( 'path' , '/' )
 500 def xpPathExpr( e ) :
 501         return ( 'path' , ) + tuple( e )
 502 def xpPathExprAbs( e ) :
 503         head , rest = e
 504         if head == '/' :
 505                 head = ( '/' , )
 506         elif head == '//' :
 507                 head = ( '/' ,
 508                                  ( 'descendant-or-self' , ( 'node' , ) ) )
 509         else :
 510                 raise NotReached
 511         return ( 'path' , ) + head + tuple( rest )
 512 pathExpr = \
 513         WithSpaceAround( Either( Literal( '/' ).call( xpPathExprRoot ) ,
 514                                                          Sequence( Regex( '//|/' ) ,
 515                                                                            relativePathExpr ).call( xpPathExprAbs ) ,
 516                                                          Wrapper( relativePathExpr ).call( xpPathExpr ) ) )
 517
 518 #
 519 # [24] NodeComp
 520 #
 521 nodeComp = \
 522         Regex( '|'.join( ( 'is' ,  '<<' , '>>' ) ) )
 523
 524 #
 525 # [23] ValueComp
 526 #
 527 valueComp = \
 528         Regex( '|'.join( ( 'eq' , 'ne' , 'lt' , 'le' , 'gt' , 'ge' ) ) )
 529
 530 #
 531 # [22] GeneralComp
 532 #
 533 generalComp = \
 534         Regex( '|'.join( ( '=' , '!=', '<=' , '<' , '>=' , '>' ) ) )
 535
 536 #
 537 # [21] ValueExpr
 538 #
 539 valueExpr = pathExpr
 540
 541 #
 542 # [20] UnaryExpr
 543 #
 544 def xpUnaryExpr( e ) :
 545         if e[ 0 ] :
 546                 neg = ( e[ 0 ].count( '-' ) % 2 )
 547                 if neg :
 548                         return ( 'minus' , e[ 1 ] )
 549                 else :
 550                         return ( 'plus' , e[ 1 ] )
 551         else :
 552                 return e[ 1 ]
 553 unaryExpr = \
 554         Sequence( WithSpaceAround( Regex( '[-+]*' ) ) , valueExpr ).call( xpUnaryExpr )
 555
 556 #
 557 # [15] IntersectExceptExpr
 558 #
 559 def xpIntersectExceptExpr( e ) :
 560         result , e = e[ 0 ] , e[ 1 : ]
 561         while e :
 562                 result , e = ( e[ 0 ] , result , e[ 1 ] ) , e[ 2 : ]
 563         return result
 564 intersectExceptExpr = \
 565         List( unaryExpr ,
 566                   Regex( 'intersect|except' ) ).call( xpIntersectExceptExpr )
 567
 568 #
 569 # [14] UnionExpr
 570 #
 571 def xpUnionExpr( e ) :
 572         if len( e ) == 1 :
 573                 return e[ 0 ]
 574         r = ( 'union' , e[ 0 ] , e[ 1 ] )
 575         for ee in e[ 2 : ] :
 576                 r = ( 'union' , r , ee )
 577         return r
 578 unionExpr = \
 579         List( intersectExceptExpr ,
 580                   Regex( 'union|[|]' ).ignore() ).call( xpUnionExpr )
 581
 582 #
 583 # [13] MultiplicativeExpr
 584 #
 585 def xpMultiplicativeExpr( e ) :
 586         r , rest = e[ 0 ] , e[ 1 : ]
 587         if rest and r == ( 'path' , '/' ) :
 588                 raise Reject
 589         while rest :
 590                 r , rest = ( rest[ 0 ] , r , rest[ 1 ] ) , rest[ 2 : ]
 591         return r
 592 multiplicativeExpr = \
 593         List( unionExpr ,
 594                   Regex( '[*]|div|idiv|mod' ) ).call( xpMultiplicativeExpr )
 595
 596 #
 597 # [12] AdditiveExpr
 598 #
 599 def xpAdditiveExpr( e ) :
 600         r , rest = e[ 0 ] , e[ 1 : ]
 601         while rest :
 602                 r , rest = ( rest[ 0 ] , r , rest[ 1 ] ) , rest[ 2 : ]
 603         return r
 604 additiveExpr = \
 605         List( multiplicativeExpr ,
 606                   Regex( '[+-]' ) ).call( xpAdditiveExpr )
 607
 608 #
 609 # [11] RangeExpr
 610 #
 611 def xpRangeExpr( e ) :
 612         if not e[ 1 ] :
 613                 return e[ 0 ]
 614         else :
 615                 return ( 'range' , e[ 0 ] , e[ 1 ][ 0 ][ 1 ] )
 616 rangeExpr = \
 617         Sequence( additiveExpr ,
 618                           Optional( Sequence( space , 'to' , space , additiveExpr ) ) ).call( xpRangeExpr )
 619
 620 #
 621 # [10] ComparisonExpr
 622 #
 623 def xpComparisonExpr( e ) :
 624         if not e[ 1 ] :
 625                 return e[ 0 ]
 626         else :
 627                 return ( e[ 1 ][ 0 ][ 0 ] , e[ 0 ] , e[ 1 ][ 0 ][ 1 ] )
 628 comparisonExpr = \
 629         Sequence( rangeExpr ,
 630                           Optional( Sequence( Either( valueComp , generalComp , nodeComp ) ,
 631                                                                   rangeExpr ) ) ).call( xpComparisonExpr )
 632
 633 #
 634 # [9] AndExpr
 635 #
 636 def xpAndExpr( e ) :
 637         return reduce( lambda a , b : ( 'and' , b , a ) , reversed( e ) )
 638 andExpr = \
 639         List( comparisonExpr ,
 640                   Literal( 'and' ).ignore() ).call( xpAndExpr )
 641
 642 #
 643 # [8] OrExpr
 644 #
 645 def xpOrExpr( e ) :
 646         return reduce( lambda a , b : ( 'or' , b , a ) , reversed( e ) )
 647 orExpr = \
 648         List( andExpr ,
 649                   Literal( 'or' ).ignore() ).call( xpOrExpr )
 650
 651 #
 652 # [7] IfExpr
 653 #
 654 def xpIfExpr( e ) :
 655         return ( 'if' , e[ 2 ] , e[ 5 ] , e[ 7 ] )
 656 ifExpr = \
 657         WithSpaceAround( Sequence( 'if' , space , '(' , expr , ')' , space ,
 658                                                            'then' , exprSingle ,
 659                                                            'else' , exprSingle ) ).call( xpIfExpr )
 660
 661 #
 662 # [6] QuantifiedExpr
 663 #
 664 def xpQuantifiedExprClause( e ) :
 665         return ( e[ 1 ] , e[ 3 ] )
 666 def xpQuantifiedExpr( e ) :
 667         return ( e[ 0 ] , tuple( e[ 1 ] ) , e[ 3 ] )
 668 quantifiedExpr = \
 669         Sequence( Either( 'some' , 'every' ) , space ,
 670                           List( Sequence( '$' , varName , space , 'in' , space , exprSingle ).call( xpQuantifiedExprClause ) ,
 671                                         WithSpaceAround( ',' ).ignore() ) ,
 672                           'satisfies' , exprSingle  ).call( xpQuantifiedExpr )
 673
 674 #
 675 # [5] SimpleForClause
 676 #
 677 def xpSimpleForClauseItem( e ) :
 678         return ( e[ 1 ] , e[ 3 ] )
 679 def xpSimpleForClause( e ) :
 680         return tuple( e[ 1 ] )
 681 simpleForClause = \
 682         Sequence( 'for' , space ,
 683                           List( Sequence( '$' , varName , space , 'in' , space , exprSingle ).call( xpSimpleForClauseItem ) ,
 684                                         WithSpaceAround( Literal( ',' ) ).ignore() ) ).call( xpSimpleForClause )
 685
 686
 687 #
 688 # [4] ForExpr
 689 #
 690 def xpForExpr( e ) :
 691         return ( 'for' , e[ 0 ] , e[ 2 ] )
 692 forExpr = \
 693         Sequence( simpleForClause , space , 'return' , space , exprSingle ).call( xpForExpr )
 694
 695 #
 696 # [3] ExprSingle
 697 #
 698 exprSingle << Either( forExpr , quantifiedExpr , ifExpr , orExpr )
 699
 700 #
 701 # [2] Expr
 702 #
 703 def xpExpr( e ) :
 704         return ( 'exprlist' , ) + tuple( e )
 705 expr << List( exprSingle ,
 706                           Literal( ',' ).ignore() ).call( xpExpr )
 707
 708 #
 709 # [1] XPath
 710 #
 711 XPath = Sequence( expr , EOS ).call( first )
 712
 713 #parser._debug = True
 714
 715 parser = XPath.parse
 716
 717 def parse( s ) :
 718
 719         t = time.time()
 720         r = parser( s )
 721         duration = time.time() - t
 722         #print 'DEBUG: Parsed %r in %.2gs' % ( s , duration )
 723         return r
 724
 725 # Local Variables:
 726 # tab-width: 4
 727 # python-indent: 4
 728 # End: