Added support for XSLT patterns.
authorFrederic Jolliton <frederic@jolliton.com>
Tue, 13 Sep 2005 07:23:40 +0000 (07:23 +0000)
committerFrederic Jolliton <frederic@jolliton.com>
Tue, 13 Sep 2005 07:23:40 +0000 (07:23 +0000)
git-archimport-id: frederic@jolliton.com--2005-main/tx--main--0.1--patch-44

pattern.py [new file with mode: 0644]
patternparser.py [new file with mode: 0644]

diff --git a/pattern.py b/pattern.py
new file mode 100644 (file)
index 0000000..d5cca59
--- /dev/null
@@ -0,0 +1,202 @@
+#!/usr/bin/env python
+# -*- coding:utf-8 -*-
+
+# XSLT Pattern
+# Copyright (C) 2005  Frédéric Jolliton <frederic@jolliton.com>
+# 
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+# 
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+from error import Error
+import xpath
+from xpath_misc import lispy
+import patternparser
+from context import Context
+from parser import NoMatch
+
+def naive( e ) :
+
+       '''Naive pattern implementation.'''
+
+       def processPath( e ) :
+
+               result = []
+               last = None
+               for step in e[ ::-1 ] :
+                       pred = None
+                       if step[ 0 ] == 'predicates' :
+                               step , pred = step[ 1 ] , step[ 2 : ]
+                       if step[ 0 ] == '/' :
+                               s = ( 'call' , 'fn:root' )
+                       elif step[ 0 ] == 'call' :
+                               s = step
+                       elif isinstance( step , tuple ) and len( step ) == 2 :
+                               axis , test = step
+                               if last is None :
+                                       if test[ 0 ] == 'document-node' :
+                                               if axis == 'implicit-child' :
+                                                       axis = 'self'
+                                       elif axis in ( 'implicit-child' , 'child' ) :
+                                               axis = 'child-or-top'
+                                       elif axis == 'attribute' :
+                                               axis = 'attribute-or-top'
+                                       else :
+                                               assert False , 'unexpected axis %r' % ( axis , )
+                               if axis == 'implicit-child' :
+                                       axis = 'child'
+                               s = ( axis , test )
+                       else :
+                               assert False , 'unexpected step %r' % ( step , )
+                       if pred is not None :
+                               s = ( 'predicates' , s ) + pred
+                       result.append( s )
+                       last = step
+               return ( 'path' , ) + tuple( result )
+
+       def processEither( e ) :
+
+               #print 'EITHER' , e
+               assert False , 'Not implemented yet'
+
+       def process( e ) :
+
+               if e[ 0 ] == 'path' :
+                       p = processPath( e[ 1 : ] )
+               elif e[ 0 ] == 'either' :
+                       p = processEither( e[ 1 : ] )
+               else :
+                       assert False , 'unexpected expr %r' % ( e , )
+               el = ( 'exprlist' , p )
+               return ( 'exprlist' , ( 'path' ,
+                                                               ( 'call' , 'fn:root' ) ,
+                                                               ( 'descendant-or-self' , ( 'node' , ) ) ,
+                                                               el ) )
+
+       def translateToXPath( e ) :
+
+               assert len( e ) == 2 and e[ 0 ] == 'pattern' , 'expected (pattern,<expr>)'
+               return process( e[ 1 ] )
+
+       return translateToXPath( e )
+
+def reverse( e ) :
+
+       '''Reverse pattern implementation.'''
+
+       def process( e ) :
+
+               if e[ 0 ] == 'path' :
+                       return makePath( e )
+               elif e[ 0 ] == 'either' :
+                       return ( 'union' ,
+                                        process( e[ 1 ] ) ,
+                                        process( e[ 2 ] ) )
+               else :
+                       assert False , 'Unexpected %r' % ( e , )
+
+       def makePath( e ) :
+
+               assert e[ 0 ] == 'path'
+               steps = e[ 1 : ]
+               result = []
+               nextAxis = 'self'
+               for i , step in enumerate( reversed( steps ) ) :
+                       if step == '/' :
+                               result.append( ( nextAxis , ( 'document' , ) ) )
+                       elif step == '//' :
+                               nextAxis = 'ancestor'
+                       elif step[ 0 ] == 'call' :
+                               result.append( step )
+                       else :
+                               pred = None
+                               if step[ 0 ] == 'predicates' :
+                                       pred = step[ 2 : ]
+                                       step = step[ 1 ]
+                               axis , test = step
+                               if pred is None :
+                                       result.append( ( nextAxis , test ) )
+                               else :
+                                       # self::<TEST>[PRED] -> ../child::<TEST>[PRED]
+                                       if nextAxis == 'self' :
+                                               s = ( 'exprlist',
+                                                         ( 'intersect' ,
+                                                               ( 'path' , '.' ) ,
+                                                               ( 'path' ,
+                                                                 ( 'parent' , ( 'node' , ) ) ,
+                                                                 ( 'predicates' , ( 'child' , test ) ) + pred ) ) )
+                                       else :
+                                               s = ( 'predicates' , ( nextAxis , test ) + pred )
+                                       result.append( s )
+                               nextAxis = 'parent'
+               return ( 'path' , ) + tuple( result )
+
+       def translateToXPath( e ) :
+
+               assert len( e ) == 2 and e[ 0 ] == 'pattern' , 'expected (pattern,<expr>)'
+               return ( 'exprlist' , process( e[ 1 ] ) )
+
+       return translateToXPath( e )
+
+def compile( s ) :
+
+       e = patternparser.parser( s )
+       if False :
+               r = naive( e )
+       else :
+               r = reverse( e )
+       return xpath.makeExprList( r )
+
+_cache = {}
+
+class Pattern( object ) :
+
+       __slots__ = [ 'pattern' , 'fun' ]
+
+       def __init__( self , pat ) :
+
+               self.pattern = pat
+               if pat in _cache :
+                       self.fun = _cache[ pat ]
+               else :
+                       try :
+                               self.fun = compile( pat )
+                       except NoMatch :
+                               raise Error( 'Unable to parse pattern %r' % pat )
+                       _cache[ pat ] = self.fun
+                       if len( _cache ) > 50 :
+                               _cache.clear() # FIXME: OUCH!
+
+       def eval( self , node ) :
+
+               f = self.fun
+               context = Context()
+               context.item = node
+               context.position = 1
+               context.last = 1
+               return bool( f( context ) )
+
+_cachePattern = {}
+
+def test( node , pat ) :
+
+       patternObject = _cachePattern.get( pat )
+       if patternObject is None :
+               patternObject = Pattern( pat )
+               _cachePattern[ pat ] = patternObject
+       return patternObject.eval( node )
+
+# Local Variables:
+# tab-width: 4
+# python-indent: 4
+# End:
diff --git a/patternparser.py b/patternparser.py
new file mode 100644 (file)
index 0000000..e6bbd5e
--- /dev/null
@@ -0,0 +1,159 @@
+#!/usr/bin/env python
+# -*- coding:utf-8 -*-
+
+# XSLT Pattern parser
+# Copyright (C) 2005  Frédéric Jolliton <frederic@jolliton.com>
+# 
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+# 
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+import re
+
+from xpath_misc import lispy
+from parser import *
+
+first = lambda l : l[ 0 ]
+second = lambda l : l[ 1 ]
+
+def tag( name ) :
+
+       return lambda o : ( name , o )
+
+def constantly( item ) :
+
+       return lambda o : item
+
+# ----[ XPath ]----
+
+from xpathparser import nodeTest, predicateList, varRef, literal, stringLiteral
+
+# ----[ XSLT pattern ]----
+
+# [8] KeyValue
+keyValue = \
+       Either( literal , varRef )
+
+# [7] IdValue
+idValue = \
+       Either( stringLiteral , varRef )
+
+# [6] IdKeyPattern
+def ptId( e ) :
+       return ( 'call' , 'ext:filter-by-id' , ( 'path' , e[ 2 ] ) )
+def ptKey( e ) :
+       return ( 'key' , e[ 2 ] , e[ 4 ] )
+idKeyPattern = \
+       Either( Sequence( 'id' , '(' , idValue , ')' ).call( ptId ) )
+                       #Sequence( 'key' , '(' , stringLiteral , ',' , keyValue , ')' ).call( ptKey ) )
+
+# [5] PatternAxis
+patternAxis = \
+       Either( Sequence( 'child' , Literal( '::' ).ignore() ).call( first ) ,
+                       Sequence( 'attribute' , Literal( '::' ).ignore() ).call( first ) ,
+                       '@' )
+
+# [4] PatternStep
+def ptPatternStep( e ) :
+       #print '>>' , e
+       if e[ 0 ] :
+               axis = e[ 0 ][ 0 ]
+               if axis == 'child' :
+                       if e[ 1 ][ 0 ] == 'name' :
+                               s = ( 'implicit-child' , ( 'element' , e[ 1 ][ 1 ] ) )
+                       else :
+                               s = ( axis , e[ 1 ] )
+               elif axis in ( 'attribute' , '@' ) :
+                       if e[ 1 ][ 0 ] == 'name' :
+                               s = ( 'attribute' , ( 'attribute' , e[ 1 ][ 1 ] ) )
+                       else :
+                               s = ( 'attribute' , e[ 1 ] )
+               else :
+                       raise NotReached
+       else :
+               if e[ 1 ][ 0 ] == 'name' :
+                       s = ( 'implicit-child' , ( 'element' , e[ 1 ][ 1 ] ) )
+               else :
+                       if e[ 1 ][ 0 ] == 'attribute' :
+                               axis = 'attribute'
+                       else :
+                               axis = 'implicit-child'
+                       s = ( axis , e[ 1 ] )
+       #print '<<' , s
+       if e[ 2 ] :
+               return ( 'predicates' , s ) + tuple( e[ 2 ] )
+       else :
+               return s
+patternStep = \
+       Sequence( Optional( patternAxis ) ,
+                         nodeTest ,
+                         predicateList ).call( ptPatternStep )
+
+# [3] RelativePathPattern
+def ptRelativePathPattern( e ) :
+       result = [ e[ 0 ] ]
+       e = e[ 1 : ]
+       while e :
+               if e[ 0 ] == '/' :
+                       pass
+               elif e[ 0 ] == '//' :
+                       result.append( '//' )
+               else :
+                       raise NotReached
+               result.append( e[ 1 ] )
+               e = e[ 2 : ]
+       return ( 'path' , ) + tuple( result )
+relativePathPattern = \
+       List( patternStep , Regex( '//|/' ) ).call( ptRelativePathPattern )
+
+# [2] PathPattern
+def ptPathPatternFromRoot( e ) :
+       if not e[ 1 ] :
+               return ( 'path' , '/' )
+       else :
+               return ( 'path' , '/' ) + e[ 1 ][ 0 ][ 1 : ]
+def ptPathPatternDescendant( e ) :
+       return ( 'path' , '//' ) + e[ 1 ][ 1 : ]
+def ptPathPatternId( e ) :
+       if not e[ 1 ] :
+               return ( 'path' , e[ 0 ] )
+       else :
+               p = e[ 1 ][ 0 ]
+               if p[ 0 ] == '/' :
+                       return ( 'path' , e[ 0 ] ) + tuple( p[ 1 ][ 1 : ] )
+               else :
+                       return ( 'path' , e[ 0 ] , p[ 0 ] ) + tuple( p[ 1 ][ 1 : ] )
+pathPattern = \
+       Either( relativePathPattern ,
+                       Sequence( '/' , Optional( relativePathPattern ) ).call( ptPathPatternFromRoot ) ,
+                       Sequence( '//' , relativePathPattern ).call( ptPathPatternDescendant ) ,
+                       Sequence( idKeyPattern ,
+                                         Optional( Sequence( Either( '/' , '//' ) ,
+                                                                                 relativePathPattern ) ) ).call( ptPathPatternId ) )
+
+# [1] Pattern
+def ptPattern( e ) :
+       if len( e ) > 1 :
+               e = ( 'either' , ) + tuple( e )
+       else :
+               e = e[ 0 ]
+       return ( 'pattern' , e )
+pattern = \
+       List( pathPattern , Literal( '|' ).ignore() ).call( ptPattern )
+
+parser = pattern.parse
+
+# Local Variables:
+# tab-width: 4
+# python-indent: 4
+# End: