[XSLT] Use of multiple predicates: order of evaluation

[michaelhkay]

I notice I added an example pattern to the draft XSLT4 spec match=".[. castable as xs:date][xs:date(.) le current-date()]" which is incorrect because processors are allowed to change the order of predicates, so you can't use the first predicate as a guard to stop the second predicate throwing an error. I've seen users fall over this (Saxon does sometimes reorder predicates). My instinct is to ban reordering of predicates; if you want to allow it, you can use the "and" operator. An alternative would be an "and" operator (say "and-also") with explicit ordering semantics, as in XPath 1.0.

[benibela]

I would ban any reordering that would lead to throwing errors

[ChristianGruen]

Banning sounds good.

[yamahito]

I have been thinking a while about this, and agree that banning is correct; consider:

preceding-sibling::*[1][@type='footnote']
preceding-sibling::*[@type='footnote'][1]

Even though no type error would be thrown, reordering of the predicates here significantly changes the meaning and result of the XPath statement.

[michaelhkay]

Obviously you're only allowed to reorder predicates where it doesn't affect the semantics of a non-error query. The debate here is about case where the only effect of reordering is on the detection or non-detection of errors, that is, the scenario within the scope of the infamous "Errors and Optimization" section of the spec.

[dnovatchev]

The debate here is about case where the only effect of reordering is on the detection or non-detection of errors

But we still can have (note the parens below):

(.[. castable as xs:date]) [xs:date(.) le current-date()]

and this enforces the wanted order of evaluation, right?

For me the problem is whether or not there should be "shortcutting". That is, should evaluation continue even after it has been determined that the value of the sub-expression, on which the predicate must be applied, is ()

Not sure if the Spec says anything about shortcutting in this case.

BaseX doesn't raise an error on this:

for $d in 10,
    $sub in $d[. castable as xs:date]
  return
     $sub[xs:date(.) le current-date()]

But throws an error ("[XPTY0004] Cannot convert xs:integer to xs:date : 10") on this:

for $d in  10
  return
    ($d[. castable as xs:date])[xs:date(.) le current-date()]

[ChristianGruen]

BaseX doesn't raise an error on this:

I noticed it also raises an error with the latest release of BaseX (because both queries are now rewritten to the same representation). The error results from a compilation step, which determines that the evaluation of the second predicate will never succeed for the given input.

[michaelhkay]

Parens don't enforce order of evaluation. The infamous rules in "Errors and Optimization" allow all expressions (with a few exceptions such as conditionals) to be rewritten to equivalent expressions without regard to the effect on error behaviour. Stripping parens is an obvious example.

As for your example, type errors are subject to different rules. A processor can report a type error statically for any expression if it can determine that execution of that expression would always fail; it doesn't have to establish that the expression will actually be evaluated.

[dnovatchev]

Parens don't enforce order of evaluation

Then what are they for?

[michaelhkay]

Parens override the default precedence of operators, they don't control order of evaluation. (a+b)+c can be rewritten as a+(b+c) because in the absence of errors the results are the same.

[dnovatchev]

Parens override the default precedence of operators, they don't control order of evaluation.

Yes. Then we probably need a special operator or function that would instruct the XPath processor that a sub-expression should be evaluated lazily. Such as:

.[. castable as xs:date] => lazy( [xs:date($z) le current-date()] )

It seems that (at least in this case) we can use the ! operator to achieve evaluation in the wanted order.
For example, instead of:

for $d in  10
  return
    $d[. castable as xs:date]![xs:date(.) le current-date()]

which produces an error in Saxon but is evaluated successfully in BaseX 9.5

we can have:

for $d in  10
  return
    $d[. castable as xs:date]  !  function($x) {$x[xs:date(.) le current-date()]}

And the latter expression is evaluated without raising an error, both in Saxon and BaseX.

So,

lazy(expression($arg1, $arg2, ..., $argN))

could be an abbreviation for:

! function($arg1, $arg2, ..., $argN) {expression($arg1, $arg2, ..., $argN)}

[ChristianGruen]

But throws an error ("[XPTY0004] Cannot convert xs:integer to xs:date : 10") on this:

The query yielded an error because the input was supplied statically. While that should be a rather uncommon use case, I decided to change the behavior of BaseX: If values are inlined at compile time, no error will be raised anymore, but the predicate expression will be replaced with an fn:error function, which will only be raised later on at runtime if the predicate will actually be evaluated.

[ChristianGruen]

@michaelhkay Thanks for my answer to #78 (comment). I’m continuing in the original issue:

Because some XQuery vendors translate operators such as and/or to other languages such as SQL, and reordering of terms in a WHERE clause to take maximum advantage of indexes is a key feature of SQL optimisers.

I see how this was a substantial argument for XQuery 1.0. I wonder if it’s still relevant for XQuery 4? XQuery 3/3.1 has so many constructs that cannot be expressed with standard relational algebra anymore. Do any SQL implementations for XQuery 3.1 exist at all?

Multiple predicates can easily be rewritten to a sequence of and operands, and vice versa. The same applies to multiple subsequent where clauses, so I always regarded all those as interchangeable:

(: currently equivalent if the tests are not positional :)
SEQ [ TEST1 and TEST2 ]

SEQ [ TEST1 ] [ TEST2 ]

for ITEM in SEQ
where TEST1 and TEST2
return RESULT

for ITEM in SEQ
where TEST1
where TEST2
return RESULT

If we restricted the evaluation order of predicates, those queries would not be equivalent anymore, and potential SQL implementations would also need to suppress these kinds of rewritings in the future.

From the user perspective, I’m pretty sure that the reordering of logical expressions is rather unexpected (as long as a developer doesn’t have a strong database background). I would claim there is already so much code out there that relies on a short-circuit evaluation of logical expressions – even more than for predicates, the syntax of which is not that explicit.

[michaelhkay]

Coming back to this thread after a long absence.

Firstly, I think there's a need both for constructs that allow reordering for optimisation purposes, and for constructs that force short-circuiting so that dynamic errors can be prevented.

Currently the only way of writing (A and B) in a way that forces A to be checked before B is evaluated is to use a conditional: if (A) then B else false().

Neither [A and B] nor [A][B] currently enforces the order. If existing implementations take advantage of this for optimization purposes then I don't think we should require them to change - the effect could be quite significant on performance of existing code.

So I think my preferred option would to add new operators with enforced short-circuiting: possible syntax "and-if" and "or-if". The semantics would be defined in terms of conditional expressions, which require that only one branch is evaluated (or at any rate, if a branch is pre-emptively evaluated, this must not have any visible effects like throwing an error).

Note: Saxon treats the predicates [A][B] and [A and B] as interchangeable (assuming the predicates are non-positional), and the optimiser does reorder the terms in some circumstances, as permitted by the spec. For example, if one of the terms is eligible for indexing then it will be moved to the left of terms that require a serial search.

[dnovatchev]

So I think my preferred option would to add new operators with enforced short-circuiting: possible syntax "and-if" and "or-if". The semantics would be defined in terms of conditional expressions, which require that only one branch is evaluated (or at any rate, if a branch is pre-emptively evaluated, this must not have any visible effects like throwing an error).

This is good and it specifies shortcutting based on the value of the 1st argument of and.

For functions like fn:fold-right() it is necessary to have shortcutting on the second (right) argument, so we will also need:

A and-if-only B

This evaluates B first and if B is false, it skips the evaluation of A and returns false()

[michaelhkay]

I don't understand. Why can't they just write B and-if A if they have this rather unusual requirement?

[ndw]

I think and-if is confusing. I see what is intended, but the thing that comes after "if" would usually be the conditional in ordinary prose. So it reads like it depends on B which isn't the intent (unless I've misunderstood entirely).

I asked my resident linguist and she proposed and-then which I think is better.

[dnovatchev]

I wrote:

For functions like fn:fold-right() it is necessary to have shortcutting on the second (right) argument, so we will also need:

A and-if-only B

Sorry, this would be unnecessary if we move forward with lazy evaluation (on demand) of the arguments on a function call -- this will be the subject of a new, separate proposal, to come shortly. With Lazy Arguments evaluation:

fold-right( (false(), (1 to 1000000000000000000000000000000000000) ! true() ),   true(),   op('and') )

this is evaluated as:

false() and fold-right($notEvaluatedNotAvailableYetTailArgument, true(), op('and') )

And due to the shortcutting of and , this immediately evaluates to false(), thus the 2nd argument to this and: (fold-right($notEvaluatedNotAvailableYetTailArgument, true(), op('and')` is completely ignored (skipped, not evaluated at all)

I have seen some people wonder: "why on Earth fn:fold-right() exists at all", and they would be right were it not for shortcutting and lazy argument evaluation, as it is in Haskell, from which foldr was borrowed, renamed and its signature (order of arguments) adjusted.

[michaelhkay]

I thought about and-then (and and-also)

• If I am tired and if it's past midnight then I should go to bed.
• If I am tired and then it's past midnight then I should go to bed.
• If I am tired and also it's past midnight then I should go to bed.

I still prefer and-if.

[ndw]

I really think and-if is going to be confusing for a lot of users.

An ordinary reading of "if I am tired and if it's past midnight then I should go to bed" means that you should go to bed if you're tired AND it's past midnight. That doesn't convey the short-circuit semantics to me at all. Of course, that's equally true of the other options you've shown so...bleh.

I think it would be better to have something that doesn't imply any particular semantics than something that implies the wrong semantics. Maybe short-and and short-or?

[ChristianGruen]

I agree with Norm that and if doesn't really indicate what is going to happen. What about then-and/then-or?

If we hadn't || for concatenations, we could have used && and ||.

[dnovatchev]

I thought about and-then (and and-also)

• If I am tired and if it's past midnight then I should go to bed.
• If I am tired and then it's past midnight then I should go to bed.
• If I am tired and also it's past midnight then I should go to bed.

I still prefer and-if.

Considering all above alternatives, I feel that and also is closest to denoting sequential execution: we first check condition-1 and then also we check condition-2.

Maybe it would be even more unambiguous to use:

if condition1 and only then if condition2

Without the ifs:

condition1 and only then condition2

[ChristianGruen]

Or (one of my favorites), if(A) then B without else, defaulting to an empty sequence ;) Obviously, this would only work if the result can be xs:boolean?.

[dnovatchev]

condition1 and only then condition2

On further thought:

condition1 and additionally condition2

[michaelhkay]

For another example of a Saxon user falling over this, see https://saxonica.plan.io/issues/5721.

I think that defining the rules for predicates is probably more important than providing a short-cut "and-also" operator. Note that we don't need to define or constrain order of evaluation, we only have to say that no error is reported in respect of the second predicate unless the first predicate returns true. Optimizers that want to use indexes can still do so, provided they adjust the error handling accordingly.

[dnovatchev]

I think that defining the rules for predicates is probably more important than providing a short-cut "and-also" operator. Note that we don't need to define or constrain order of evaluation, we only have to say that no error is reported in respect of the second predicate unless the first predicate returns true. Optimizers that want to use indexes can still do so, provided they adjust the error handling accordingly.

I think Haskell got it right and lazy by default is the way to go.

And it is good for the carbon footprint.

Not giving the programmer full control can have bad consequences. It is like not knowing at any moment who does what with your money.

I am beginning to understand why many wise, prominent and deeply understanding people are warning of the dangers of AI.

No need to watch "Rick and Morty" in order to arrive at this conclusion.

Why would anyone want to use Saxon after seeing that it needs 100 seconds in order to evaluate this expression:

when it can be evaluated infinitely faster (0 seconds) in Haskell and also using BaseX (though they spent many many days working on their optimization techniques, which would have come for free if we had lazy evaluation) ?

And here is a video of doing the same in Haskell:

https://github.com/dnovatchev/FXSL-XSLT2/raw/master/Comp-Foldr%20Shortcutting%20-%20With%20Haskell%20-%20Replit%20-%20Google%20Chrome%202022-10-10%2012-45-44.m4v

[ChristianGruen]

Why should this be a problem?

Look at the following code: Which values would you expect to be assigned to $it1 and $it2?

head(sort( (2, error(), 1 ))`

If the evaluation hasn't taken place yet, then the guard provides useful information

Guards should not be dependent on specifics of the implementation.

I’ll be glad to explain more details in the chat.

[dnovatchev]

Look at the following code: Which values would you expect to be assigned to $it1 and $it2?

head(sort( (2, error(), 1 ))`

@ChristianGruen It was an error from my side -- please ignore this. fn:head has just a single argument and it needs it. Thus at least for now let us not discuss it.

I am talking about functions that have at least one argument and their authors know that in certain cases the function may produce its results without needing some of its arguments. Then, it will be good if the author of the function could specify this fact. Like:

let $and :=function($a, lazy $b) { $a and $b}

[dnovatchev]

You only know the properties of the function item, as described in the data model. One of those properties is the implementation of the function, but you're not going to start decompiling byte code to find out what it does...

@michaelhkay,

Yes, but the XDM gives us the arity.

Thus, if:

  f($x, $y) = { g($x) ($y)}

where by definition, g($x) is exactly f($x, ?) ,

and if for a given $x,

function-arity( f($x, ?)) eq 0

Then the developer can specify a hint about this, and even the arity of a dynamically-produced function can be evaluated dynamically by the XPath processor,

Thus, in the case of 2-argument function, as above, the XPath processor can determine that the returned function f($x, ?) is the constant function (has arity 0), and thus can decide to short-circuit (skip the evaluation of the remaining argument(s))

Thus, we do not need to add any new properties to the XDM for functions.

Based on this, I will be writing a proposal for giving the developer the ability to specify short-circuiting hints.

[michaelhkay]

A postscript: I've been reviewing some of the Saxon optimizations to see whether they conform to the new rules. An interesting case is one that arose from the queries/stylesheets generated by Gunther Rademacher' Rex parser, where we get a lot of expressions of the form ($x = 5 or $x = 10 or $x = 12 or $x = 15 ...). We start by turning this into a general comparison ($x = (5, 10, 12, 15)) and this then gets turned into map{5:(), 10:(), 12:(), 15:()}=>contains($x). With some caveats about type checking, of course. With only literals involved, the question of guarding against errors doesn't arise. But it's a good illustration of why we should allow processors to change the order of evaluation provided it doesn't cause unwanted errors.

[ChristianGruen]

But it's a good illustration of why we should allow processors to change the order of evaluation provided it doesn't cause unwanted errors.

I agree, and I had ignored we also have such cases before you addressed it. Based on statistics of the accessed database, we are choosing a predicate and rewrite it to an index requests if we are confident that the rewritten expression is equivalent. For example, an expression like…

collection('DB')//element[text() = 'VALUE'][@id = 'ID']

…may be rewritten to one of the following expressions:

db:attribute('db', 'ID')/self::attribute(id)/parent::element[text() = 'VALUE']
db:text('db', 'VALUE')/parent::element[@id = 'ID']

[michaelhkay]

We have added rules about "guarded sub-expressions" and I think this resolves the issue.

[dnovatchev]

Based on the discussions on a related issue: #281, I propose that we add one more bullet (an additional case of a guarded expression):

• In an expression of the type E(A1, A2, ..., AN) any of the right-hand operands (arguments) AK is guarded by the the condition function-arity(E) ge K being true()
  This rule has the consequence that if the arity of E() is less than K then if any argument Am is evaluated, this must not raise a dynamic error unless function-arity(E) ge K is true() , and of course, there is such an error to be raised. An implementation may delay the evaluation of the arguments until the actual arity of E() is dynamically known.

[michaelhkay]

Does this proposal apply to static function calls, or dynamic function calls, or both?

In both cases I think the rule should be unnecessary, because the rules for evaluating static function calls and the rules for evaluating dynamic function calls both check the arity and raise an error before they attempt to evaluate the arguments.

We do have a problem, I think, that the "Errors and Optimization" rules are still too liberal. It should be clearer that when we prescribe a detailed sequence of evaluation, as we do for function calls, the outcome should be the same as if that sequence is followed literally.

[dnovatchev]

Does this proposal apply to static function calls, or dynamic function calls, or both?

Both .

In both cases I think the rule should be unnecessary, because the rules for evaluating static function calls and the rules for evaluating dynamic function calls both check the arity and raise an error before they attempt to evaluate the arguments.

The rules for coercion (4.4.4 Function coercion rules) dictate that:

"If F has lower arity than the expected type, then F is wrapped in a new function that declares and ignores the additional argument;"

So in our case the resulting function "has lower arity than the expected type" thus following the function coercion rules no error is raised, the resulting function is "wrapped in a new function that declares and ignores the additional argument".

Following this rule, the resulting function-arity being less than K means that the resulting function is "wrapped in a new function that declares and ignores the additional (N -K) arguments". It is these additional arguments that are ignored, for which the arity of the resulting function is therefore a guard.

[dnovatchev]

We need to consider adding to the list a few more obvious cases of expressions that have guarded subexpressions:

• pow(x, y) (do not raise an error from eventually evaluating x if y eq 0 )

• E1 ! E2 (Do not raise an error from eventually evaluating E2 if empty(E1) )

• anyFunction( $arg1, $arg2, ..., $argN) (do not raise an error from eventually evaluating any $argK (1 <= K <= N), unless the function anyFunction() has actually been called and the argument(s) are not guarded by other types of guards.

[ChristianGruen]

If the first operand of an arithmetic expression is 0, the second operand does influence the result in numerous cases. Examples:

• 0 * xs:double('NaN') returns NaN
• 0 div xs:double('-INF') returns -0
• 0 div 0 raises an error

[michaelhkay]

This is far too constraining on implementations, and achieves very little benefit for applications.

Remember that conditional jumps break the CPU pipeline and slow things down enormously. Doing (eval(x), eval(y), MUL) is much more efficient than doing (eval(x), IF zero GOTO end, eval(y), MUL, end:)

[dnovatchev]

If the first operand of an arithmetic expression is 0, the second operand does influence the result in numerous cases. Examples:

• 0 * xs:double('NaN') returns NaN
• 0 div xs:double('-INF') returns -0
• 0 div 0 raises an error

Fair enough.

I am updating and removing these from the list. Still there are 4 new guard-types,

[dnovatchev]

This is far too constraining on implementations, and achieves very little benefit for applications.

Remember that conditional jumps break the CPU pipeline and slow things down enormously. Doing (eval(x), eval(y), MUL) is much more efficient than doing (eval(x), IF zero GOTO end, eval(y), MUL, end:)

@michaelhkay Duly noted.

I have updated the comment and removed * and div from the proposed new guard-conditions.

[michaelhkay]

E1 ! E2 is already on the list ("In a path expression of the form E1/E2 or E1//E2, and in a mapping expression of the form E1!E2, the right-hand operand E2 is guarded by the existence of the relevant context item in the result of evaluating E1.")

pow(x, y) - I can't see why you want to impose a rule here for the case y=0. An implementation is likely by default to evaluate its arguments from left to right and you're asking for pow() to be treated as a special case with a different order of evaluation. There's no significant user benefit from imposing such complexity on the implementation. And in any case, pow((), 0) is () so it's not true that the value doesn't depend on x.

[dnovatchev]

E1 ! E2 is already on the list ("In a path expression of the form E1/E2 or E1//E2, and in a mapping expression of the form E1!E2, the right-hand operand E2 is guarded by the existence of the relevant context item in the result of evaluating E1.")

Yes, now I see it.

Maybe it would be more easier/obvious to see in the text if the these three cases are listed as separate guard conditions?

pow(x, y) - I can't see why you want to impose a rule here for the case y=0. An implementation is likely by default to evaluate its arguments from left to right and you're asking for pow() to be treated as a special case with a different order of evaluation. There's no significant user benefit from imposing such complexity on the implementation. And in any case, pow((), 0) is () so it's not true that the value doesn't depend on x.

Well, it is not a big deal, but I think pow((), 0) should raise an error. Dobn't see any reason for the described behavior!

[michaelhkay]

All the math functions (like many others...) accept an empty sequence for the first argument and return an empty sequence in that case. I wouldn't argue that it was the right design choice, but we obviously can't change it.

[liamquin]

On Wed, 2023-01-11 at 10:51 -0800, Michael Kay wrote: All the math functions (like many others...) accept an empty sequence for the first argument and return an empty sequence in that case. I wouldn't argue that it was the right design choice, but we obviously can't change it.

This came from a time when XQuery 1 and XPath 2 had pessimistic static typing, so if something could possibly be an empty sequence it was an error. This meant writing ***@***.***) was a static (compile-time) error since there might not be a width attribute. So allowing the empty sequence was a result from feedback from users of an early implementation. I was never sure it was a good choice, and it was made worse by the fact that the implementation in question implemented strong typing but did not support user-defined schemas, so it couldn't consult a schema to find whether @width was required and/or had a fallback value.

…

-- Liam Quin, https://www.delightfulcomputing.com/ Available for XML/Document/Information Architecture/XSLT/ XSL/XQuery/Web/Text Processing/A11Y training, work & consulting. Barefoot Web-slave, antique illustrations:  http://www.fromoldbooks.org

[dnovatchev]

All the math functions (like many others...) accept an empty sequence for the first argument and return an empty sequence in that case. I wouldn't argue that it was the right design choice, but we obviously can't change it.

Let us ask the community if there is even a single case of someone relying on this. If none are reported, which seems the most likely outcome, then we will know that changing the semantics of the functions will not affect anyone and is the right thing to do.

I believe that this current "feature" makes some bugs very difficult to catch, thus it is not just a "curiosity" but is really harmful.

[ChristianGruen]

Let us ask the community if there is even a single case of someone relying on this.

We should try to stay focused. Initially, this issue was about the order of predicates.

[dnovatchev]

Let us ask the community if there is even a single case of someone relying on this.

We should try to stay focused. Initially, this issue was about the order of predicates.

Yes, I will open a separate issue/bug

[michaelhkay]

There are thousands of users running XSLT code that hasn't been touched for years, no-one knows who wrote it, let alone what edge cases in the spec it relies on. There is no-one in those organisations who regards themselves as a member of "the community" or who would read any notice we put out to that community, let alone respond to it. People expect to be able to switch in a new Saxon release without it breaking their code. The bar for introducing incompatibilities has to be very high; there have to be very strong benefits to justify the high costs.

[michaelhkay]

And of course people are using this feature. Perhaps not with the pow() function, but certainly with common functions like round(). People write things like if (round(@size) = 3)... all the time, expecting it to evaluate to false if @size does not exist. Breaking this code is unthinkable.

[dnovatchev]

There are thousands of users running XSLT code that hasn't been touched for years, no-one knows who wrote it, let alone what edge cases in the spec it relies on. There is no-one in those organisations who regards themselves as a member of "the community" or who would read any notice we put out to that community, let alone respond to it. People expect to be able to switch in a new Saxon release without it breaking their code. The bar for introducing incompatibilities has to be very high; there have to be very strong benefits to justify the high costs.

Completely understood.

There were very strong beliefs at the time that the Earth was flat. Heretics that dared say it was round were really brave, daring people. There seemed to be no too-strong and immediate benefits of accepting the truth. And it took the Church 350 years to admit that Galileo was right claiming the Earth revolves around the Sun.

Given these facts, why should we be in a hurry to try correcting such minor things as bugs in functions' specifications?

[ChristianGruen]

Given these facts, why should we be in a hurry to try correcting such minor things as bugs in functions' specifications?

Just joking: Given this analogy, maybe we should strive for something more universal than tweaking secondary rules in secondary utility functions…

[benibela]

Just joking: Given this analogy, maybe we should strive for something more universal than tweaking secondary rules in secondary utility functions…

Or a radical cut: Delete the XPath/XQuery/XSLT specs, and port all existing code to Javascript

[michaelhkay]

This thread is going nowhere. The original issue has been resolved: predicates cannot be reordered in a way that changes behaviour in either error or non-error cases. If there are other issues that remain, they should be explained in a new thread.