Added more XPath functions.
authorFrederic Jolliton <frederic@jolliton.com>
Sun, 11 Sep 2005 06:13:41 +0000 (06:13 +0000)
committerFrederic Jolliton <frederic@jolliton.com>
Sun, 11 Sep 2005 06:13:41 +0000 (06:13 +0000)
 * Added support for special floats (nan, -inf, +inf)

 * Added optimization to prevent building full string representation of a
   node (using string iterator instead of dmStringValue.)

 * Several new functions.

 * Updated some functions to follow standard more closely.
git-archimport-id: frederic@jolliton.com--2005-main/tx--main--0.1--patch-21

xpathfn.py

index 0e26a4e..f0cb6b0 100644 (file)
 # along with this program; if not, write to the Free Software
 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
+# XO = http://www.w3.org/TR/xquery-operators/
+
 from __future__ import division
 
 # __all__ = [
 #      'functions'
 #      ]
 
-import operator
+import re
+import operator as op
+import string
+import math
+import time
 
 from error import Error, XPathError
 from sequence import *
 from sequence import _Empty, _EmptyString, _False, _True, _Boolean
 from nodes import *
-from misc import typeOf, iterSingle, identity
+from misc import typeOf, identity, stringValuesStartsWith, stringValuesCompare, stringValuesLength
+from misc import isNotANumber, isInfinity, isPositiveInfinity, isNegativeInfinity, isSpecialFloat
 from iterators import iterDescendantOrSelfFull
 
 functions = {}
 
+_NAN    = float( 'NaN' )
+_POSINF = float( 'inf' )
+_NEGINF = float( '-inf' )
+
+_Nan = Sequence( _NAN )
+_PositiveInfinity = Sequence( _POSINF )
+_NegativeInfinity = Sequence( _NEGINF )
+
 def functionNames( qname ) :
 
        '''
@@ -135,6 +150,18 @@ def ZeroOrOne( t ) :
                raise XPathError( 'XPTY0004' , 'Expected a sequence of 0 or 1 item (%r)' % t )
        return fun
 
+def OneOrMore( t ) :
+
+       def fun( sequence ) :
+               if len( sequence ) >= 1 :
+                       for item in sequence :
+                               if not t( item ) :
+                                       break
+                       else :
+                               return sequence
+               raise XPathError( 'XPTY0004' , 'Expected a sequence of 0 or 1 item (%r)' % t )
+       return fun
+
 def One( t ) :
 
        def fun( sequence ) :
@@ -154,6 +181,7 @@ def zeroOrMoreNodes( sequence ) :
 zeroOrOneNode  = ZeroOrOne( isNode )
 zeroOrOneItem  = ZeroOrOne( isItem )
 zeroOrMoreItem = identity
+oneOrMoreItem  = OneOrMore( isItem )
 oneNumber      = One( isNumber )
 oneAtomic      = One( isAtomic )
 oneItem        = One( isItem )
@@ -170,19 +198,33 @@ def atomize( item ) :
        else :
                return item
 
-def sequenceToData( sequence ) :
-
-       return tuple( atomize( item ) for item in sequence )
-
 def asString( item ) :
 
        '''Convert item (node or atomic value) to a string.'''
 
        result = atomize( item )
-       if not isinstance( result , basestring ) :
+       if result is None :
+               result = ''
+       elif not isinstance( result , basestring ) :
                result = str( result )
        return result
 
+def asStringOrStream( item ) :
+
+       '''Return either a string if item is note a node,
+       or a string iterator if item is a node.'''
+
+       if isNode( item ) :
+               return item.iterStringValue()
+       else :
+               return asString( item )
+
+def sequenceToData( sequence ) :
+
+       '''Convert sequence to a tuple of atomized items.'''
+
+       return tuple( atomize( item ) for item in sequence )
+
 def asNumber( item ) :
 
        '''
@@ -198,25 +240,36 @@ def asNumber( item ) :
                        return int( item )
                except :
                        try :
-                               return float( item )
+                               r = float( item )
+                               if isSpecialFloat( r ) :
+                                       r = _NAN # Don't allow inf/-inf/NaN construction from string
+                               return r
                        except :
-                               pass
+                               return _NAN
 
-def oneAtomizedItem( sequence ) :
+def asInteger( item ) :
 
-       return atomize( oneItem( sequence ) )
+       n = asNumber( item )
+       try :
+               return int( n )
+       except :
+               return long( n )
 
-def asStringOrStream( item ) :
+def asBoolean( item ) :
 
-       if isNode( item ) :
-               return item.iterStringValue()
-       else :
-               return asString( item )
+       return sequenceToBoolean( ( item , ) )
+
+def oneAtomizedItem( sequence ) :
+
+       return atomize( oneItem( sequence ) )
 
 #----------------------------------------------------------------------------
 
+# Used to implement XO/15.1.1
 def sequenceToBoolean( sequence ) :
 
+       '''Compute the effective boolean value of the sequence 'sequence'.'''
+
        if not sequence :
                return False
        else :
@@ -230,104 +283,7 @@ def sequenceToBoolean( sequence ) :
                                return bool( item )
                        elif isNumber( item ) :
                                return item != 0
-       raise XError( 'FORG0006' )
-
-#----------------------------------------------------------------------------
-
-def _startsWith( s1 , s2 ) :
-
-       '''
-       Compare strings 's1' and 's2'. This function also accept iterators
-       returning string. This is usefull to compare two nodes without
-       first converting them to strings for performance reason.
-       '''
-
-       if isinstance( s1 , basestring ) :
-               if isinstance( s2 , basestring ) :
-                       return s1.startswith( s2 )
-               else :
-                       s1 = iterSingle( s1 )
-       elif isinstance( s2 , basestring ) :
-               s2 = iterSingle( s2 )
-
-       result = 0
-       d1 = ''
-       d2 = ''
-       while 1 :
-               if not d1 :
-                       try :
-                               d1 = s1.next()
-                       except StopIteration :
-                               d1 = ''
-               if not d2 :
-                       try :
-                               d2 = s2.next()
-                       except StopIteration :
-                               d2 = ''
-               if not d1 :
-                       if not d2 :
-                               r = True
-                       else :
-                               r = False
-                       break
-               elif not d2 :
-                       r = True
-                       break
-               m = min( len( d1 ) , len( d2 ) )
-               r = cmp( d1[ : m ] , d2[ : m ] )
-               if r != 0 :
-                       r = False
-                       break
-               d1 = d1[ m : ]
-               d2 = d2[ m : ]
-       return r
-
-def _compareString( s1 , s2 ) :
-
-       '''
-       Compare strings 's1' and 's2'. This function also accept iterators
-       returning string. This is usefull to compare two nodes without
-       first converting them to strings for performance reason.
-       '''
-
-       if isinstance( s1 , basestring ) :
-               if isinstance( s2 , basestring ) :
-                       return cmp( s1 , s2 )
-               else :
-                       s1 = iterSingle( s1 )
-       elif isinstance( s2 , basestring ) :
-               s2 = iterSingle( s2 )
-
-       result = 0
-       d1 = ''
-       d2 = ''
-       while 1 :
-               if not d1 :
-                       try :
-                               d1 = s1.next()
-                       except StopIteration :
-                               d1 = ''
-               if not d2 :
-                       try :
-                               d2 = s2.next()
-                       except StopIteration :
-                               d2 = ''
-               if not d1 :
-                       if not d2 :
-                               r = 0
-                       else :
-                               r = -1
-                       break
-               elif not d2 :
-                       r = 1
-                       break
-               m = min( len( d1 ) , len( d2 ) )
-               r = cmp( d1[ : m ] , d2[ : m ] )
-               if r != 0 :
-                       break
-               d1 = d1[ m : ]
-               d2 = d2[ m : ]
-       return r
+       raise XPathError( 'FORG0006' , 'Cannot convert sequence to boolean' )
 
 #--[ Extensions ]------------------------------------------------------------
 
@@ -360,34 +316,186 @@ def extDescendantAttribute( context , arg ) :
 
 #--[ XPath/XQuery functions ]------------------------------------------------
 
-@registerFast( 'fn:id' )
-def fnId( context , arg , node = None ) :
+# XO/2.1
+@registerFast( 'fn:node-name' )
+def fnNodeName( context , arg ) :
 
+       node = zeroOrOneNode( arg )
        if node is None :
+               return _Empty
+       else :
+               return Sequence( node.dmNodeName() )
+
+# XO/2.3
+@registerFast( 'fn:string' )
+def fnString( context , arg = None ) :
+
+       if arg is None :
                item = context.item
                if item is None :
-                       raise XPathError( 'FONC0001' )
+                       raise XPathError( 'FONC0001' , 'Context item undefined' )
        else :
-               item = oneNode( node )
-       doc = item.root
-       if doc is None or not isDocument( doc ) :
-               raise XPathError( 'FODC0001' ) # unsure
-       ids = map( asString , zeroOrMoreItem( arg ) )
-       result = []
-       for id in ids :
-               n = doc.ids.get( id )
-               if n is not None :
-                       result.append( n )
-       result.sort( lambda a , b : cmp( a.position , b.position ) )
-       return Sequence( result )
+               item = zeroOrOneItem( arg )
+               if item is None :
+                       return _EmptyString
+       return Sequence( asString( item ) )
+
+# XO/4
+@registerFast( 'fn:trace' )
+def fnTrace( context , value , label ) :
+
+       label = atomize( oneItem( label ) )
+       print '[TRACE] %s = %s' % ( label , value )
+       return Sequence( value )
+
+# XO/6.4.1
+@registerFast( 'fn:abs' )
+def fnAbs( context , arg ) :
+
+       if not arg :
+               return arg
+       else :
+               item = oneItem( arg )
+               return Sequence( abs( asNumber( item ) ) )
+
+# XO/6.4.2
+@registerFast( 'fn:ceiling' )
+def fnCeiling( context , arg ) :
+
+       if not arg :
+               return arg
+       else :
+               item = asNumber( oneItem( arg ) )
+               if item == _POSINF :
+                       return _PositiveInfinity
+               elif item == _NEGINF :
+                       return _NegativeInfinity
+               else :
+                       return math.ceil( item )
+
+# XO/6.4.3
+@registerFast( 'fn:floor' )
+def fnFloor( context , arg ) :
+
+       if not arg :
+               return arg
+       else :
+               item = asNumber( oneItem( arg ) )
+               if item == _POSINF :
+                       return _PositiveInfinity
+               elif item == _NEGINF :
+                       return _NegativeInfinity
+               else :
+                       return math.floor( item )
+
+# XO/6.4.4
+@registerFast( 'fn:round' )
+def fnRound( context , arg ) :
+
+       if not arg :
+               return arg
+       else :
+               item = asNumber( oneItem( arg ) )
+               if item == _POSINF :
+                       return _PositiveInfinity
+               elif item == _NEGINF :
+                       return _NegativeInfinity
+               else :
+                       return math.floor( item + 0.5 )
+
+# XO/7.2.1
+@registerFast( 'fn:codepoints-to-string' )
+def fnCodepointsToString( context , arg ) :
+
+       return Sequence( ''.join( map( lambda item : unichr( asInteger( item ) ) , arg ) ) )
+
+# XO/7.2.2
+@registerFast( 'fn:string-to-codepoints' )
+def fnStringToCodepoints( context , arg ) :
+
+       item = zeroOrOneItem( arg )
+       if item is None :
+               return _Empty
+       else :
+               item = asString( item )
+               if not item :
+                       return _Empty
+               else :
+                       return Sequence( map( ord , asString( item ) ) )
+
+# XO/7.4.1
+@registerFast( 'fn:concat' )
+def fnConcat( context , *arg ) :
+
+       return Sequence( ''.join( map( lambda item : asString( zeroOrOneItem( item ) or '' ) , arg ) ) )
+
+# XO/7.4.2
+@registerFast( 'fn:string-join' )
+def fnStringJoin( context , arg1 , arg2 ) :
+
+       arg2 = oneItem( arg2 )
+       if not arg1 :
+               return _EmptyString
+       else :
+               return asString( arg2 ).join( map( asString , arg1 ) )
+
+# XO/7.4.3
+@registerFast( 'fn:substring' )
+def fnSubstring( context , sourceString , startingLoc , length = None ) :
+
+       string = zeroOrOneItem( sourceString )
+       if string is None :
+               return _EmptyString
+       else :
+               string = asString( string )
+               startingLoc = oneItem( startingLoc )
+               a = asNumber( startingLoc )
+               if length is None :
+                       b = _POSINF
+               else :
+                       b = asNumber( oneItem( length ) )
+               if isNaN( a ) or isNan( b ) :
+                       return _EmptyString
+               elif isNegativeInfinity( a ) and isPositiveInfinity( b ) :
+                       return _EmptyString # because a + b is NaN
+               elif isPositiveInfinity( a ) :
+                       return _EmptyString
+               elif b <= 0 :
+                       return _EmptyString
+               else :
+                       if isNegativeInfinity( a ) :
+                               a = 1
+                       else :
+                               a = math.floor( a + 0.5 )
+                       if isPositiveInfinity( b ) :
+                               return Sequence( string[ max( 0 , int( a - 1 ) ) : ] )
+                       else :
+                               b = math.floor( b + 0.5 )
+                               return Sequence( string[ max( 0 , int( a - 1 ) ) : max( 0 , int( a + b - 1 ) ) ] )
+
+# FO/7.4.4
+@registerFast( 'fn:string-length' )
+def fnStringLength( context , arg = None ) :
+
+       if arg is None :
+               item = context.item
+               if item is None :
+                       raise XPathError( 'FONC0001' , 'Context item undefined' )
+       else :
+               item = zeroOrOneItem( arg )
+       if item is None :
+               return Sequence( 0 )
+       else :
+               return Sequence( stringValuesLength( asStringOrStream( item ) ) )
 
+# XO/7.4.5
 @registerFast( 'fn:normalize-space' )
 def fnNormalizeSpace( context , arg = None ) :
 
        if arg is None :
                item = context.item
                if item is None :
-                       raise XPathError( 'FONC0001' )
+                       raise XPathError( 'FONC0001' , 'Context item undefined' )
                item = asString( item )
        else :
                item = zeroOrOneItem( arg )
@@ -397,13 +505,19 @@ def fnNormalizeSpace( context , arg = None ) :
        if not item :
                return _EmptyString
        else :
-               s = ' '.join( item.split() )
-               if s[ 0 ] != item[ 0 ] :
-                       s = ' ' + s
-               if s[ -1 ] != item[ -1 ] :
-                       s = s + ' '
-               return Sequence( s )
+               return Sequence( ' '.join( item.split() ) )
+
+# FO/7.4.7
+@registerFast( 'fn:upper-case' )
+def fnUpperCase( context , arg ) :
+
+       arg = zeroOrOneItem( arg )
+       if arg is None :
+               return _EmptyString
+       else :
+               return Sequence( asString( arg ).upper() )
 
+# FO/7.4.8
 @registerFast( 'fn:lower-case' )
 def fnLowerCase( context , arg ) :
 
@@ -413,48 +527,322 @@ def fnLowerCase( context , arg ) :
        else :
                return Sequence( asString( arg ).lower() )
 
-@registerFast( 'fn:upper-case' )
-def fnUpperCase( context , arg ) :
+# FO/7.4.9
+@registerFast( 'fn:translate' )
+def fnTranslate( context , arg , mapString , transString ) :
 
        arg = zeroOrOneItem( arg )
        if arg is None :
                return _EmptyString
        else :
-               return Sequence( asString( arg ).upper() )
+               mapString = asString( oneItem( mapString) )
+               transString = asString( oneItem( transString ) )
+               # FIXME: Slow !
+               result = ''
+               for ch in arg :
+                       p = mapString.find( ch )
+                       if p == -1 :
+                               result += ch
+                       elif p >= len( transString ) :
+                               pass
+                       else :
+                               result += transString[ p ]
+               return Sequence( result )
 
-@registerFast( 'fn:false' )
-def fnFalse( context ) :
+# [XF] 7.4.10
+_escapeUri1 = string.letters + string.digits + '%#-_.!~*"()'
+_escapeUri2 = _escapeUri1 + ';/?:@&=+$,[]'
 
-       return _False
+@registerFast( 'fn:escape-uri' )
+def fnEscapeUri( context , uriPart , escapeReserved ) :
+
+       uriPart = zeroOrOneItem( uriPart )
+       if uriPart is None :
+               return _EmptyString
+       else :
+               uriPart = asString( uriPart )
+               escapeReserved = asBoolean( oneItem( escapeReserved ) )
+
+               # FIXME: Slow !
+               result = ''
+               if isinstance( uriPart , unicode ) :
+                       uriPart = uriPart.encode( 'utf8' )
+               if escapeReserved :
+                       for ch in uriPart :
+                               if ch not in _escapeUri1 :
+                                       result += '%%%02X' % ord( ch )
+                               else :
+                                       result += ch
+               else :
+                       for ch in uriPart :
+                               if ch not in _escapeUri2 :
+                                       result += '%%%02X' % ord( ch )
+                               else :
+                                       result += ch
+               return Sequence( result )
+
+# XO/7.5.1
+@registerFast( 'fn:contains' )
+def fnContains( context , arg1 , arg2 , collation = None ) :
+
+       if collation is not None :
+               raise XPathError( 'FOCH0004' , 'Collation not supported' )
+       arg1 = zeroOrOneItem( arg1 )
+       if arg1 is None :
+               arg1 = ''
+       arg2 = zeroOrOneItem( arg2 )
+       if arg2 is None :
+               arg2 = ''
+       if arg1 is arg2 and arg2 == '' :
+               return _True
+       elif arg1 == '' :
+               return _False
+       else :
+               return _Boolean[ asString( arg2 ) in asString( arg1 ) ]
+
+# XO/7.5.2
+@registerFast( 'fn:starts-with' )
+def fnStartsWith( context , arg1 , arg2 , collation = None ) :
+
+       if collation is not None :
+               raise XPathError( 'FOCH0004' , 'Collation not supported' )
+       arg1 = zeroOrOneItem( arg1 )
+       if arg1 is None :
+               arg1 = ''
+       arg2 = zeroOrOneItem( arg2 )
+       if arg2 is None :
+               arg2 = ''
+       if arg1 is arg2 :
+               return _True
+       else :
+               return _Boolean[ stringValuesStartsWith( asStringOrStream( arg1 ) ,
+                                                                                                asStringOrStream( arg2 ) ) ]
+
+# XO/7.5.3
+@registerFast( 'fn:ends-with' )
+def fnEndsWith( context , arg1 , arg2 , collation = None ) :
+
+       if collation is not None :
+               raise XPathError( 'FOCH0004' , 'Collation not supported' )
+       arg1 = zeroOrOneItem( arg1 )
+       if arg1 is None :
+               arg1 = ''
+       arg2 = zeroOrOneItem( arg2 )
+       if arg2 is None :
+               arg2 = ''
+       if arg1 is arg2 or arg2 == '' :
+               return _True
+       elif arg1 == '' :
+               return _False
+       else :
+               return _Boolean[ asString( arg1 ).endswith( asString( arg2 ) ) ]
+
+# XO/7.5.4
+@registerFast( 'fn:substring-before' )
+def fnSubstringBefore( context , arg1 , arg2 , collation = None ) :
+
+       if collation is not None :
+               raise XPathError( 'FOCH0004' , 'Collation not supported' )
+       arg1 = asString( zeroOrOneItem( arg1 ) )
+       arg2 = asString( zeroOrOneItem( arg2 ) )
+
+       if not arg2 :
+               return _EmptyString
+       else :
+               p = arg1.find( arg2 )
+               if p == -1 :
+                       return _EmptyString
+               else :
+                       return Sequence( arg1[ : p ] )
+
+# XO/7.5.5
+@registerFast( 'fn:substring-after' )
+def fnSubstringAfter( context , arg1 , arg2 , collation = None ) :
+
+       if collation is not None :
+               raise XPathError( 'FOCH0004' , 'Collation not supported' )
+       arg1 = asString( zeroOrOneItem( arg1 ) )
+       arg2 = asString( zeroOrOneItem( arg2 ) )
+
+       if not arg2 :
+               return Sequence( arg1 )
+       else :
+               p = arg1.find( arg2 )
+               if p == -1 :
+                       return _EmptyString
+               else :
+                       return Sequence( arg1[ p + len( arg2 ) : ] )
+
+def _patternFlags( flags ) :
+
+       if flags is None :
+               r = 0
+       else :
+               flags = asString( oneItem( flags ) )
+               r = 0
+               if 'i' in flags :
+                       r |= re.I
+               elif 'm' in flags :
+                       r |= re.M
+               elif 's' in flags :
+                       r |= re.S
+       return r
+
+# XO/7.6.2
+@registerFast( 'fn:matches' )
+def fnMatches( context , input , pattern , flags = None ) :
+
+       input = asString( zeroOrOneItem( input ) )
+       pattern = asString( oneItem( pattern ) )
+
+       return _Boolean[ re.search( pattern , input , _patternFlags( flags ) ) is not None ]
+
+# XO/7.6.3
+# FIXME: Add support for $n
+@registerFast( 'fn:replace' )
+def fnReplace( context , input , pattern , replacement , flags = None ) :
+
+       input = asString( zeroOrOneItem( input ) )
+       pattern = asString( oneItem( pattern ) )
+       replacement = asString( oneItem( replacement ) )
+
+       return Sequence( re.sub( pattern , replacement , input , _patternFlags( flags ) ) )
+
+# XO/7.6.4
+@registerFast( 'fn:tokenize' )
+def fnTokenize( context , input , pattern , flags = None ) :
+
+       input = asString( zeroOrOneItem( input ) )
+       pattern = asString( oneItem( pattern ) )
 
+       return Sequence( re.compile( pattern , _patternFlags( flags ) ).split( input ) )
+
+# XO/9.1.1
 @registerFast( 'fn:true' )
 def fnTrue( context ) :
 
        return _True
 
-@registerFast( 'fn:empty' )
-def fnEmpty( context , sequence ) :
+# XO/9.1.2
+@registerFast( 'fn:false' )
+def fnFalse( context ) :
 
-       return _Boolean[ len( sequence ) == 0 ]
+       return _False
 
-@registerFast( 'fn:exists' )
-def fnExists( context , sequence ) :
+# XO/9.3.1
+@registerFast( 'fn:not' )
+def fnNot( context , arg ) :
 
-       return _Boolean[ len( sequence ) > 0 ]
+       return _Boolean[ not sequenceToBoolean( arg ) ]
 
-@registerFast( 'fn:string' )
-def fnString( context , arg = None ) :
+# XO/14.1
+@registerFast( 'fn:name' )
+def fnName( context , arg = None ) :
 
        if arg is None :
                item = context.item
                if item is None :
-                       raise XError( 'FONC0001' )
+                       raise XPathError( 'FONC0001' , 'Context item undefined' )
+               if not isNode( item ) :
+                       raise XPathError( 'XPTY0006' , 'Expected a node as context item' )
        else :
-               item = zeroOrOneItem( arg )
+               item = zeroOrOneNode( arg )
                if item is None :
                        return _EmptyString
-       return Sequence( asString( item ) )
+       return Sequence( item.dmNodeName() )
+
+# XO/14.4
+@registerFast( 'fn:number' )
+def fnNumber( context , arg = None ) :
+
+       if arg is None :
+               item = context.item
+               if item is None :
+                       raise XPathError( 'FONC0001' , 'Context item undefined' )
+       else :
+               item = zeroOrOneItem( arg )
+       return asNumber( item )
+
+# XO/14.5
+@registerFast( 'fn:lang' )
+def fnLang( context , testlang , node = None ) :
+
+       testlang = asString( zeroOrOneItem( testlang ) ).lower()
+       if node is None :
+               node = context.item
+               if node is None :
+                       raise XPathError( 'FONC0001' , 'Context item undefined' )
+               if not isNode( item ) :
+                       raise XPathError( 'XPTY0006' , 'Expected a node as context item' )
+       else :
+               node = oneNode( node )
+
+       while node is not None :
+               if isinstance( node , Element ) :
+                       att = node.getAttribute( 'xml:lang' )
+                       if att is not None :
+                               v = att.dmStringValue().lower()
+                               if v == testlang :
+                                       return _True
+                               if v.split( '-' , 1 )[ 0 ] == testlang :
+                                       return _True
+               node = node.parent
+       return _False
+
+# XO/14.9
+@registerFast( 'fn:root' )
+def fnRoot( context , sequence = None ) :
+
+       if sequence is None :
+               item = context.item
+               if item is None :
+                       raise XPathError( 'FONC0001' , 'Context item undefined' )
+               elif not isNode( item ) :
+                       raise XPathError( 'XPTY0006' , 'Expected a node as context item' )
+               elif isDocument( item ) :
+                       return Sequence( item )
+               else :
+                       return Sequence( item.root )
+       else :
+               item = zeroOrOneNode( sequence )
+               if item is None :
+                       return _Empty
+               elif isDocument( item ) :
+                       return sequence
+               else :
+                       return Sequence( item.root )
+
+# XO/15.1.1
+@registerFast( 'fn:boolean' )
+def fnBoolean( context , arg ) :
+
+       return Sequence( sequenceToBoolean( arg ) )
+
+# XO/15.1.3
+@registerFast( 'fn:index-of' )
+def fnIndexOf( context , seqParam , srchParam , collation = None ) :
+
+       if collation is not None :
+               raise XPathError( 'FOCH0004' , 'Collation not supported' )
+
+       seqParam = zeroOrMoreItem( seqParam )
+       srchParam = oneItem( srchParam )
 
+       return tuple( i + 1 for i , item in enumerate( seqParam ) if compareValue( item , srchParam ) == 0 )
+
+# XO/15.1.4
+@registerFast( 'fn:empty' )
+def fnEmpty( context , sequence ) :
+
+       return _Boolean[ len( sequence ) == 0 ]
+
+# XO/15.1.5
+@registerFast( 'fn:exists' )
+def fnExists( context , sequence ) :
+
+       return _Boolean[ len( sequence ) > 0 ]
+
+# XO/15.1.6
 @registerFast( 'fn:distinct-values' )
 def fnDistinctValues( context , arg ) :
 
@@ -476,138 +864,301 @@ def fnDistinctValues( context , arg ) :
                                result.append( item )
                return Sequence( result )
 
-@registerFast( 'fn:not' )
-def fnNot( context , arg ) :
+# XO/15.1.7
+@registerFast( 'fn:insert-before' )
+def fnInsertBefore( context , target , position , inserts ) :
 
-       return _Boolean[ not sequenceToBoolean( arg ) ]
+       target = zeroOrMoreItem( target )
+       position = asNumber( oneItem( position ) )
+       inserts = zeroOrMoreItem( inserts )
 
-@registerFast( 'fn:count' )
-def fnCount( context , arg ) :
+       position = max( 0 , int( position - 1 ) )
 
-       return Sequence( len( arg ) )
+       return target[ : position ] + inserts + target[ position : ]
 
-@registerFast( 'fn:root' )
-def fnRoot( context , sequence = None ) :
+# XO/15.1.8
+@registerFast( 'fn:remove' )
+def fnRemove( context , target , position ) :
 
-       if sequence is None :
-               item = context.item
-               if item is None :
-                       raise XError( 'FONC0001' )
-               elif not isNode( item ) :
-                       raise XError( 'XPTY0006' )
-               elif isDocument( item ) :
-                       return Sequence( item )
-               else :
-                       return Sequence( item.root )
+       target = zeroOrMoreItem( target )
+       position = asNumber( oneItem( position ) )
+
+       position = max( -1 , int( position - 1 ) )
+       if position < 0 :
+               return target
        else :
-               item = zeroOrOneNode( sequence )
-               if item is None :
+               return target[ : position ] + target[ position + 1 : ]
+
+# XO/15.1.9
+@registerFast( 'fn:reverse' )
+def fnReverse( context , arg ) :
+
+       return Sequence( arg[ ::-1 ] , type = arg.type )
+
+# XO/15.1.10
+@registerFast( 'fn:subsequence' )
+def fnSubstring( context , sourceSeq , startingLoc , length = None ) :
+
+       if sourceSeq is None :
+               return _EmptyString
+       else :
+               startingLoc = oneItem( startingLoc )
+               a = asNumber( startingLoc )
+               if length is None :
+                       b = _POSINF
+               else :
+                       b = asNumber( oneItem( length ) )
+               if isNotANumber( a ) or isNotANumber( b ) :
+                       return _Empty
+               elif isNegativeInfinity( a ) and isPositiveInfinity( b ) :
+                       return _Empty # because a + b is NaN
+               elif isPositiveInfinity( a ) :
+                       return _Empty
+               elif b <= 0 :
                        return _Empty
-               elif isDocument( item ) :
-                       return sequence
                else :
-                       return Sequence( item.root )
+                       if isNegativeInfinity( a ) :
+                               a = 1
+                       else :
+                               a = math.floor( a + 0.5 )
+                       if isPositiveInfinity( b ) :
+                               return Sequence( sourceSeq[ max( 0 , int( a - 1 ) ) : ] , type = sourceSeq.type )
+                       else :
+                               b = math.floor( b + 0.5 )
+                               return Sequence( sourceSeq[ max( 0 , int( a - 1 ) ) : max( 0 , int( a + b - 1 ) ) ] , type = sourceSeq.type )
 
-@registerFast( 'fn:position' )
-def fnPosition( context ) :
+# XO/15.1.11
+@registerFast( 'fn:unordered' )
+def fnUnordered( context , sourceSeq ) :
 
-       return Sequence( context.position )
+       return sourceSeq
 
-@registerFast( 'fn:last' )
-def fnLast( context ) :
+# XO/15.2.1
+@registerFast( 'fn:zero-or-one' )
+def fnZeroOrOne( context , arg ) :
 
-       return Sequence( context.last )
+       zeroOrMoreItem( arg )
+       return arg
 
-@registerFast( 'fn:boolean' )
-def fnBoolean( context , arg ) :
+# XO/15.2.2
+@registerFast( 'fn:one-or-more' )
+def fnOneOrMore( context , arg ) :
 
-       return Sequence( sequenceToBoolean( arg ) )
+       oneOrMoreItem( arg )
+       return arg
 
-@registerFast( 'fn:trace' )
-def fnTrace( context , value , label ) :
+# XO/15.2.3
+@registerFast( 'fn:exactly-one' )
+def fnExactlyONe( context , arg ) :
 
-       label = atomize( oneItem( label ) )
-       print '[TRACE] %s = %s' % ( label , value )
-       return value
+       zeroOrMoreItem( arg )
+       return arg
 
-@registerFast( 'fn:node-name' )
-def fnNodeName( context , arg ) :
+# FIXME: Rewrite it as iterative (following one tree iteratively, and
+# trying to match the other tree at each step) ?
+def treeDeepEqual( t1 , t2 ) :
 
-       node = zeroOrOneNode( arg )
-       if node is None :
+       if t1 is t2 :
+               #
+               # Same node
+               #
+               return True
+       elif type( t1 ) is not type( t2 ) :
+               #
+               # Different type
+               #
+               return False
+       elif isinstance( t1 , Document ) :
+               #
+               # Document
+               #
+               if len( t1.children ) != len( t2.children() ) :
+                       return False
+               for c1 , c2 in zip( t1.children , t2.children ) :
+                       if not treeDeepEqual( c1 , c2 ) :
+                               return False
+               return True
+       elif isinstance( t1 , Element ) :
+               #
+               # Element
+               #
+               if t1.name != t2.name :
+                       return False
+               #
+               # Same attributes ?
+               #
+               if len( t1.attributes ) != len( t2.attributes ) :
+                       return False
+               for a1 , a2 in zip( sorted( t1.attributes , key = op.attrgetter( 'name' ) ) ,
+                                                       sorted( t2.attributes , key = op.attrgetter( 'name' ) ) ) :
+                       if a1.name != a2.name or a1.value != a2.value :
+                               return False
+               #
+               # Same children ?
+               #
+               if len( t1.children ) != len( t2.children ) :
+                       return False
+               for c1 , c2 in zip( t1.children , t2.children ) :
+                       if not treeDeepEqual( c1 , c2 ) :
+                               return False
+               return True
+       elif isinstance( t1 , Text ) :
+               #
+               # Text
+               #
+               return t1.contents == t2.contents
+       elif isinstance( t1 , Comment ) :
+               #
+               # Comment
+               #
+               return t1.contents == t2.contents
+       else :
+               raise Error( 'Unexpected comparison between item of type %s' % typeOf( t1 ) )
+
+# XO/15.3.1
+@registerFast( 'fn:deep-equal' )
+def fnDeepEqual( context , parameter1 , parameter2 , collation = None ) :
+
+       if collation is not None :
+               raise XPathError( 'FOCH0004' , 'Collation not supported' )
+
+       parameter1 = zeroOrMoreItem( parameter1 )
+       parameter2 = zeroOrMoreItem( parameter2 )
+
+       if not parameter1 and not parameter2 :
+               return True
+       if len( parameter1 ) != len( parameter2 ) :
+               return False
+       for i1 , i2 in zip( parameter1 , parameter2 ) :
+               if isNode( i1 ) :
+                       if isNode( i2 ) :
+                               if not treeDeepEqual( i1 , i2 ) :
+                                       return False
+                       else :
+                               return False
+               else :
+                       if isNode( i2 ) :
+                               return False
+                       else :
+                               if compareValue( i1 , i2 ) != 0 :
+                                       return False
+       return True
+
+# XO/15.4.1
+@registerFast( 'fn:count' )
+def fnCount( context , arg ) :
+
+       return Sequence( len( arg ) )
+
+# XO/15.4.2
+@registerFast( 'fn:avg' )
+def fnAvg( context , arg ) :
+
+       if not arg :
                return _Empty
        else :
-               return Sequence( node.dmNodeName() )
+               return Sequence( sum( map( asNumber , arg ) ) / float( len( arg ) ) )
 
-@registerFast( 'fn:name' )
-def fnName( context , arg = None ) :
+def _makeFnMinMax( comparator ) :
 
-       if arg is None :
+       def fun( context , arg , collation = None ) :
+
+               if collation is not None :
+                       raise XPathError( 'FOCH0004' , 'Collation not supported' )
+
+               if not arg :
+                       return _Empty
+               else :
+                       r = arg[ 0 ]
+                       if isNode( r ) :
+                               r = asNumber( r )
+                       if isNotANumber( r ) :
+                               return _Nan
+
+                       for item in arg[ 1 : ] :
+                               if isNode( item ) :
+                                       item = asNumber( item )
+                               test = compareValue( item , r )
+                               if test is None :
+                                       raise XPathError( 'FORG0006' , 'inconsistency' )
+                               if comparator( test , 0 ) :
+                                       r = item
+
+                       return Sequence( r )
+
+       return fun
+
+# XO/15.4.3
+fnMax = _makeFnMinMax( op.gt )
+
+# XO/15.4.4
+fnMin = _makeFnMinMax( op.lt )
+
+registerFast( 'fn:max' )( fnMax )
+registerFast( 'fn:min' )( fnMin )
+
+@registerFast( 'fn:sum' )
+def fnSum( context , arg , zero = None ) :
+
+       if not arg :
+               if zero is not None :
+                       zero = zeroOrOneItem( zero )
+                       if zero is None :
+                               return _Empty
+                       else :
+                               return Sequence( zero )
+               else :
+                       return Sequence( 0 )
+
+       return Sequence( sum( map( asNumber , arg ) ) )
+
+# XO/15.5.2
+@registerFast( 'fn:id' )
+def fnId( context , arg , node = None ) :
+
+       if node is None :
                item = context.item
                if item is None :
-                       raise XError( 'FONC0001' )
-               if not isNode( item ) :
-                       raise XError( 'XPTY0006' )
+                       raise XPathError( 'FONC0001' , 'Context item undefined' )
        else :
-               item = zeroOrOneNode( arg )
-               if item is None :
-                       return _EmptyString
-       return Sequence( item.dmNodeName() )
+               item = oneNode( node )
+       doc = item.root
+       if doc is None or not isDocument( doc ) :
+               raise XPathError( 'FODC0001' , '..' ) # unsure
+       ids = map( asString , zeroOrMoreItem( arg ) )
+       result = []
+       for id in ids :
+               n = doc.ids.get( id )
+               if n is not None :
+                       result.append( n )
+       result.sort( lambda a , b : cmp( a.position , b.position ) )
+       return Sequence( result )
 
-@registerFast( 'fn:starts-with' )
-def fnStartsWith( context , arg1 , arg2 , collation = None ) :
+# XO/16.1
+@registerFast( 'fn:position' )
+def fnPosition( context ) :
 
-       if collation is not None :
-               raise XError( 'FOCH0004' , 'Collation not supported' )
-       arg1 = zeroOrOneItem( arg1 )
-       if arg1 is None :
-               arg1 = ''
-       arg2 = zeroOrOneItem( arg2 )
-       if arg2 is None :
-               arg2 = ''
-       if arg1 is arg2 :
-               return _True
-       else :
-               return _Boolean[ _startsWith( asStringOrStream( arg1 ) ,
-                                                                         asStringOrStream( arg2 ) ) ]
+       if context.item is None :
+               raise XPathError( 'FONC0001' , 'Context item undefined' )
+       return Sequence( context.position )
 
-@registerFast( 'fn:ends-with' )
-def fnEndsWith( context , arg1 , arg2 , collation = None ) :
+# XO/16.2
+@registerFast( 'fn:last' )
+def fnLast( context ) :
 
-       if collation is not None :
-               raise XError( 'FOCH0004' , 'Collation not supported' )
-       arg1 = zeroOrOneItem( arg1 )
-       if arg1 is None :
-               arg1 = ''
-       arg2 = zeroOrOneItem( arg2 )
-       if arg2 is None :
-               arg2 = ''
-       if arg1 is arg2 or arg2 == '' :
-               return _True
-       elif arg1 == '' :
-               return _False
-       else :
-               return _Boolean[ asString( arg1 ).endswith( asString( arg2 ) ) ]
+       if context.item is None :
+               raise XPathError( 'FONC0001' , 'Context item undefined' )
+       return Sequence( context.last )
 
-@registerFast( 'fn:contains' )
-def fnContains( context , arg1 , arg2 , collation = None ) :
+# XO/16.3
+@registerFast( 'fn:current-dateTime' )
+def fnCurrentDatetime( context ) :
 
-       if collation is not None :
-               raise XError( 'FOCH0004' , 'Collation not supported' )
-       arg1 = zeroOrOneItem( arg1 )
-       if arg1 is None :
-               arg1 = ''
-       arg2 = zeroOrOneItem( arg2 )
-       if arg2 is None :
-               arg2 = ''
-       if arg1 is arg2 and arg2 == '' :
-               return _True
-       elif arg1 == '' :
-               return _False
-       else :
-               return _Boolean[ asString( arg2 ) in asString( arg1 ) ]
+       t = context.currentDatetime
+       return '%04d-%02d-%02dT%02d:%02d:%02d.%06dZ' \
+               % ( time.gmtime( t )[ : 6 ] + ( int( math.modf( t )[ 0 ] * 1e6 ) , ) )
 
-#----------------------------------------------------------------------------
+#--[ XPath/XQuery operators ]------------------------------------------------
 
 @registerFast( 'op:is-same-node' )
 def opIsSameNode( context , arg1 , arg2 ) :
@@ -748,7 +1299,15 @@ def opDivide( context , arg1 , arg2 ) :
        if arg1 is None or arg2 is None :
                return _Empty
        else :
-               return Sequence( arg1 / float( arg2 ) )
+               if arg2 == 0 :
+                       if arg1 > 0 :
+                               return _PositiveInfinity
+                       elif arg1 < 0 :
+                               return _NegativeInfinity
+                       else :
+                               return _Nan
+               else :
+                       return Sequence( arg1 / float( arg2 ) )
 
 @registerFast( 'op:integer-divide' )
 def opIntegerDivide( context , arg1 , arg2 ) :
@@ -765,17 +1324,20 @@ def compareValue( a , b ) :
 
        if isNode( a ) :
                if isNode( b ) :
-                       return _compareString( a.iterStringValue() , b.iterStringValue() )
+                       return stringValuesCompare( a.iterStringValue() , b.iterStringValue() )
                elif isString( b ) :
-                       return _compareString( a.iterStringValue() , b )
+                       return stringValuesCompare( a.iterStringValue() , b )
        elif isString( a ) :
                if isNode( b ) :
-                       return _compareString( a , b.iterStringValue() )
+                       return stringValuesCompare( a , b.iterStringValue() )
                elif isString( b ) :
                        return cmp( a , b )
        elif isNumber( a ) :
                if isNumber( b ) :
                        return cmp( a , b )
+       elif isBoolean( a ) :
+               if isBoolean( b ) :
+                       return cmp( a , b )
 
 # eq, ne, lt, le, gt, ge
 def makeValueComparator( comparator ) :
@@ -803,7 +1365,9 @@ def makeGeneralComparator( comparator ) :
                        for item1 in arg1 :
                                for item2 in arg2 :
                                        r = False
-                                       if isNumber( item1 ) :
+                                       if item1 is item2 :
+                                               r = comparator( 0 , 0 )
+                                       elif isNumber( item1 ) :
                                                if isNumber( item2 ) :
                                                        r = comparator( item1 , item2 )
                                                else :
@@ -820,16 +1384,22 @@ def makeGeneralComparator( comparator ) :
                                                        else :
                                                                r = comparator( item1 , item2 )
                                                elif isNode( item2 ) :
-                                                       r = comparator( _compareString( item1.iterStringValue() , item2.iterStringValue() ) , 0 )
+                                                       r = comparator( stringValuesCompare( item1.iterStringValue() ,
+                                                                                                                                item2.iterStringValue() ) ,
+                                                                                       0 )
                                                elif isString( item2 ) :
-                                                       r = comparator( _compareString( item1.iterStringValue() , item2 ) , 0 )
+                                                       r = comparator( stringValuesCompare( item1.iterStringValue() ,
+                                                                                                                                item2 ) ,
+                                                                                       0 )
                                                else :
                                                        raise XPathError( 'XPTY0004' , 'cannot compare %s and %s' % ( typeOf( item1 ) , typeOf( item2 ) ) )
                                        elif isString( item1 ) :
                                                if isString( item2 ) :
                                                        r = comparator( item1 , item2 )
                                                elif isNode( item2 ) :
-                                                       r = comparator( _compareString( item1 , item2.iterStringValue() ) , 0 )
+                                                       r = comparator( stringValuesCompare( item1 ,
+                                                                                                                                item2.iterStringValue() ) ,
+                                                                                       0 )
                                                else :
                                                        raise XPathError( 'XPTY0004' , 'cannot compare %s and %s' % ( typeOf( item1 ) , typeOf( item2 ) ) )
                                        else :
@@ -843,15 +1413,19 @@ def makeGeneralComparator( comparator ) :
 # Not really XPath operators, but rather dispatcher to the right
 # operator.
 #
-opValueEqual       = makeValueComparator( operator.eq )
-opValueNotEqual    = makeValueComparator( operator.ne )
-opValueLessThan    = makeValueComparator( operator.lt )
-opValueGreaterThan = makeValueComparator( operator.gt )
-
-opGeneralEqual       = makeGeneralComparator( operator.eq )
-opGeneralNotEqual    = makeGeneralComparator( operator.ne )
-opGeneralLessThan    = makeGeneralComparator( operator.lt )
-opGeneralGreaterThan = makeGeneralComparator( operator.gt )
+opValueEqual          = makeValueComparator( op.eq )
+opValueNotEqual       = makeValueComparator( op.ne )
+opValueLessThan       = makeValueComparator( op.lt )
+opValueGreaterThan    = makeValueComparator( op.gt )
+opValueLessOrEqual    = makeValueComparator( op.le )
+opValueGreaterOrEqual = makeValueComparator( op.ge )
+
+opGeneralEqual          = makeGeneralComparator( op.eq )
+opGeneralNotEqual       = makeGeneralComparator( op.ne )
+opGeneralLessThan       = makeGeneralComparator( op.lt )
+opGeneralGreaterThan    = makeGeneralComparator( op.gt )
+opGeneralLessOrEqual    = makeGeneralComparator( op.le )
+opGeneralGreaterOrEqual = makeGeneralComparator( op.ge )
 
 # Local Variables:
 # tab-width: 4