Subject: Re: [scim] Filter negation

From: "Steven W. Moyer" <[email-masked]>
Date: Wed, 18 Sep 2013 21:19:51 -0400 (EDT)

Since we're defining "NOT" as an operator, I thought I'd perform a simple test of the proposed change.  I simply added NOT to the LogicalOperator enum in our lexer/parser and ran the example filters provided by Bjorn Aannestad along with two variations to see what happened in the absence of parenthesis.  I didn't however enforce a grouping requirement on the NOT operator and I didn't fix the "over-recursion" that occurred in the fifth case.

In any case, after seeing the results and looking at parser complexity, I'd like to make some comments and suggestions:

1)  Enforcing the parenthesis after the NOT token (processed as a token stream) requires either a look-ahead or carrying state in the parser (beyond what's provided by the head and/or tail recursion).  I'd suggest we not require parenthesis unless you want the NOT operator to apply to the group following it.  Otherwise, the NOT operator is in reality a function.

2)  Enforcing the parenthesis after the NOT is in effect saying that the NOT operator is a higher precedence than both the AND and OR operators (only considering the logical operators).  It makes sense for the logical operators to be a lower precedence than both the attribute operators and the grouping operators, but I'd suggest that it doesn't make sense to specify the precedence between the AND and OR operators in the API document and the precedence of the NOT in relation to the AND and OR operators using explicit grouping.  I'd like to suggest that the consistency of the filter specification would be better with any of the following:

- Declare that AND, NOT and OR have equal precedence and always process them left to right, forcing grouping operators for cases where that's not desired.

- Explicitly state that NOT has a higher precedence than AND and OR understanding that this will require the parser to either preprocess these operators or to vary the extent of the left to right processing in the absence of grouping operators.

- Abandon the NOT operator as a prefix and either use it as a modifier to an attribute operator or provide a set of negated operators (or both).

3)  I think we can all agree that logically, these filters are the same:

- not userType eq "Employee"
- userType not eq "Employee"
- userType neq "Employee"

But these filters will (without heroics in the parser), result in different expressions as follows:

- not userType eq "Employee"     ----> not usertype = 'Employee'
- userType not eq "Employee"     ----> usertype <> 'Employee'
- userType neq "Employee"        ----> usertype <> 'Employee'

So in the first case, where using an SQL logical operator to negate the result of an "=" comparison operator, but in the second and third cases, we're realizing that "not eq" and "neq" are synonyms.  I think it would require an optimizer to make all three expressions evaluate to the same SQL fragment.  And in fact, the third and fourth examples that Bjorn provided are an example of a complex equality that follows De Morgan's Law (1), yet the effort to optimize those expressions in one common variant wouldn't be worth the effort.

I realize I'm relatively new here and I'll freely admit I haven't read much of the mailing list prior to April (assuming the 01 specification was current when that document came out), so please don't take this as criticism and feel free to ignore points that don't align with the group's interests.  We'll create our implementation to comply with whatever the group decides.

Thanks again for all the effort that you (collectively) have put into making something that I believe will be revolutionary.

Steve Moyer

===== SNIP =====

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: not(userType eq "Employee")
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
NOT
|
+---EQ
    |
    +---userType
    +---Employee

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: not userType eq "Employee"
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
NOT
|
+---EQ
    |
    +---userType
    +---Employee

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: userType eq "Employee" and not(emails co "example.com" or emails co "example.org")
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
AND
|
+---EQ
|   |
|   +---userType
|   +---Employee
|   
+---NOT
    |
    +---OR
        |
        +---CO
        |   |
        |   +---emails
        |   +---example.com
        |   
        +---CO
            |
            +---emails
            +---example.org

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: not(userType eq "Employee") and not(userType eq "Intern")
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
AND
|
+---NOT
|   |
|   +---EQ
|       |
|       +---userType
|       +---Employee
|       
|   
+---NOT
    |
    +---EQ
        |
        +---userType
        +---Intern

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: not userType eq "Employee" and not userType eq "Intern"
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
NOT
|
+---AND
    |
    +---EQ
    |   |
    |   +---userType
    |   +---Employee
    |   
    +---NOT
        |
        +---EQ
            |
            +---userType
            +---Intern

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: not(userType eq "Employee" or userType eq "Intern")
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
NOT
|
+---OR
    |
    +---EQ
    |   |
    |   +---userType
    |   +---Employee
    |   
    +---EQ
        |
        +---userType
        +---Intern

---

From: Phil Hunt <[email-masked]>
Date: Wed, 18 Sep 2013 19:30:26 -0700

I think not as a function is a requirement. We need to be able to say
NOT(a eq b AND c eq d)

It is often easier to scale what something isn't than what it is. 

We need both grouping and not functions. 

The alternative means a much much longer filter. So any parsing performance is lost. 

IMHO parsing is the smallest part of performance cost by several orders of magnitude when compared to database connections and http connection handling ... which is pretty darn fast. Just sayin'

Phil

> On Sep 18, 2013, at 18:19, "Steven W. Moyer" <[email-masked]> wrote:
> 
> _______________________________________________
> scim mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/scim

---

From: "Steven W. Moyer" <[email-masked]>
Date: Thu, 19 Sep 2013 04:46:35 -0400 (EDT)

I completely agree that the syntax you've shown should represent a valid filter, but I was more suggesting that using NOT as a negation operator for the expression that followed was more consistent.  In that case, your example remains the same (I've added spaces where our lexer would tokenize it):

NOT ( a EQ b AND c eq d )

Treating NOT as an operator would however change (shorten) some of the other uses:

NOT ( userType EQ "Employee" )

would be equivalent to:

NOT userType EQ "Employee"

since the expression containing the EQ has a higher precedence anyway (I've again used spaces to indicate where our lexer is splitting tokens).

Rereading issue #24 (http://trac.tools.ietf.org/wg/scim/trac/ticket/24), I'm realizing that perhaps my misunderstanding is thinking of the NOT token as a logical operator.  As a grouping operator is the token really always "NOT("?  Should the syntax support "NOT (" (with a space between the NOT and opening parenthesis)?  In this case I understand why it's precedence is higher than the LogicalOperators and lower than the AttributeOperators, but when would the precedence of NOT( over ( come into play?  The examples I've considered can all be resolved by matching those operators to their closing parenthesis.

Steve
----- Original Message -----
From: "Phil Hunt" <[email-masked]>
To: "Steven W. Moyer" <[email-masked]>
Cc: [email-masked]
Sent: Wednesday, September 18, 2013 10:30:26 PM
Subject: Re: [scim] Filter negation

Phil

---

From: "Steven W. Moyer" <[email-masked]>
Date: Thu, 19 Sep 2013 05:39:22 -0400 (EDT)

If I'd considered my previous examples using an LDAP filter representation instead of SQL, I'd have seen the rationale for using NOT( as a grouping operator immediately:

- not userType eq "Employee"  ---->  not usertype = 'Employee'  |  (!(userType=Employee))
- userType not eq "Employee"  ---->  usertype <> 'Employee'     |  No inequality operator
- userType neq "Employee"     ---->  usertype <> 'Employee'     |  No inequality operator

This also makes me wonder how the SCIM GT and LT operators would be translated ... would:

filter=meta.lastModified gt "2011-05-13T04:42:34Z"  ---->  (!(modifiedTimestamp<=2011-05-13T04:42:34Z))

In any case, I'll rework our lexer to tokenize "NOT *(" (regex) as NOT( and alter the parser to create an expression up to the terminating ")".  If someone could provide one or more examples where the precedence of ( and NOT( matters, I'll add them to our test cases.  I'd like to build up a library of examples (in addition to the thirteen I pulled from the specification).

Would the group be interested in a simple web page that allowed a filter string to be entered, showed whether it was valid or invalid, what tokens the lexer found and the expression tree generated by the parser.  I could also show examples of how the expression tree would be translated into an LDAP filter and SQL where clause.  Since the mapping of SCIM attributes to database columns or LDAP attributes would vary, this would only be for educational purposes.

Steve

----- Original Message -----
From: "Steven W. Moyer" <[email-masked]>
To: "Phil Hunt" <[email-masked]>
Cc: [email-masked]
Sent: Thursday, September 19, 2013 4:46:35 AM
Subject: Re: [scim] Filter negation

would be equivalent to:

Steve
----- Original Message -----
From: "Phil Hunt" <[email-masked]>
To: "Steven W. Moyer" <[email-masked]>
Cc: [email-masked]
Sent: Wednesday, September 18, 2013 10:30:26 PM
Subject: Re: [scim] Filter negation

Phil

---

From: Bjorn Aannestad <[email-masked]>
Date: Thu, 19 Sep 2013 10:17:10 -0500

Steven, thank you for the in-depth discussion!  This is a great 
exploration of the rationale.

Couple of points:
a) In your earlier note, you're right that I was intending "not(" or 
"not (" to be the token, just like "(" is the grouping token.

b) I also couldn't discover a case where the precedence of "not(" vs "(" 
was important.    If people agree, the text could say that those two 
have equal precedence.

c) Although I used the word "INVALID" for examples with the 
logical-operator-not, it's more accurate to describe those forms as not 
being required to be supported.  =>  userType not eq "Employee".   A 
Service Provide _could_ support this, but it wouldn't be standard.

d) If you do make an expression checker, consider linking it to 
simplecloud.info .

Regards,
-Bjorn