Subject: [scim] Processing SCIM search/query filters

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

We've created a lexer and predictive parser (a recursive descent parser for LL grammars) that we believe will properly convert a filter string into an expression hierarchy.  The only issue with this parser is that the precedence of AND over OR means that the SCIM filter grammar is not strictly LL, so this lexer/parser will currently produce errors for sum-of-product type filters when the AND clauses are not grouped in parenthesis (so the grammar is parsed into groups recursively but otherwise proceeds left-to-right).

Currently, our requirements don't include OR clauses, but we do intend to make the parser compliant with the SCIM specifications (probably by adding a preprocessor that inserts grouping operators around and clauses).  In the mean-time, we thought we'd post a sample of input/output here for comments and advice.  We'd be happy to add filters to the test cases and would appreciate verification of the operation we've shown below.

It's also our intention to share the Java code for this project as well as the (currently) minimal test suite.  If anyone is interested, we'll make the repository public sooner rather than later.

Thanks,

Steve Moyer

P.S.  In the output below, the input filter string is printed, followed by the tree the parser created.

===== SNIP =====

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: userName eq "bjensen"
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
EQ
|
+---userName
+---bjensen

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: name.familyName co "O'Malley"
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
CO
|
+---name.familyName
+---O'Malley

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: userName sw "J"
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
SW
|
+---userName
+---J

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: title pr
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
PR
|
+---title
+---null

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: meta.lastModified gt "2011-05-13T04:42:34Z"
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
GT
|
+---meta.lastModified
+---2011-05-13T04:42:34Z

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: meta.lastModified ge "2011-05-13T04:42:34Z"
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
GE
|
+---meta.lastModified
+---2011-05-13T04:42:34Z

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: meta.lastModified lt "2011-05-13T04:42:34Z"
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
LT
|
+---meta.lastModified
+---2011-05-13T04:42:34Z

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: meta.lastModified le "2011-05-13T04:42:34Z"
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
LE
|
+---meta.lastModified
+---2011-05-13T04:42:34Z

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: title pr and userType eq "Employee"
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
AND
|
+---PR
|   |
|   +---title
|   +---null
|   
+---EQ
    |
    +---userType
    +---Employee

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: title pr or userType eq "Intern"
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
OR
|
+---PR
|   |
|   +---title
|   +---null
|   
+---EQ
    |
    +---userType
    +---Intern

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

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: (emails co "example.com" or emails co "example.org")
[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
OR
|
+---CO
|   |
|   +---emails
|   +---example.com
|   
+---CO
    |
    +---emails
    +---example.org

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

---

From: Kelly Grizzle <[email-masked]>
Date: Thu, 19 Sep 2013 13:46:16 +0000

Thanks Steven ... this is great!  The output below all looks correct to me.

I have been asked by a number of people about SCIM libraries - specifically around filter processing - so I know that there will be interest in this.

--Kelly

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Steven W. Moyer
Sent: Wednesday, September 18, 2013 3:02 PM
To: [email-masked]
Subject: [scim] Processing SCIM search/query filters

Thanks,

Steve Moyer

===== SNIP =====

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: title pr [main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
PR
|
+---title
+---null

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

[main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter string: (emails co "example.com" or emails co "example.org") [main] INFO org.apache.directory.scim.search.lexerparser.FilterParser - Filter expression:
OR
|
+---CO
|   |
|   +---emails
|   +---example.com
|   
+---CO
    |
    +---emails
    +---example.org

_______________________________________________
scim mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/scim

---

From: Steve Moyer <[email-masked]>
Date: Thu, 19 Sep 2013 10:01:06 -0400 (EDT)

Thanks for checking our work.  We're following the on-going discussion on filter negation, but considered the NOT operator to be a logical operator rather than a grouping operator in our first implementation.  It's just about fixed now, and I'll post the results to that thread.  Since we've tailored the filter negation around the ability to create LDAP filters, I'm wondering if we're going to have problems with LT and GT since those operators don't exist in the LDAP syntax.  The alternative is using negation there too:

a < b ----> !(a >= b)
a > b ----> !(a <= b)

Steve

----- Original Message -----
From: "Kelly Grizzle" <[email-masked]>
To: "Steven W. Moyer" <[email-masked]>, [email-masked]
Sent: Thursday, September 19, 2013 9:46:16 AM
Subject: RE: Processing SCIM search/query filters

--Kelly

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Steven W. Moyer
Sent: Wednesday, September 18, 2013 3:02 PM
To: [email-masked]
Subject: [scim] Processing SCIM search/query filters

Thanks,

Steve Moyer

===== SNIP =====

---

From: Kelly Grizzle <[email-masked]>
Date: Thu, 19 Sep 2013 14:06:23 +0000

Yes - I think that converting less-than to a not-greater-than-or-equal-to is the usual way to solve this limitation in LDAP.

From your previous email:

> 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.

Yes - this would be valuable.  Perhaps we could even add it as another link off of the compliance tests - http://www.simplecloud.info/#complianceTest.

--Kelly

-----Original Message-----
From: Steve Moyer [mailto:[email-masked]] 
Sent: Thursday, September 19, 2013 9:01 AM
To: Kelly Grizzle
Cc: [email-masked]
Subject: Re: Processing SCIM search/query filters

a < b ----> !(a >= b)
a > b ----> !(a <= b)

Steve

----- Original Message -----
From: "Kelly Grizzle" <[email-masked]>
To: "Steven W. Moyer" <[email-masked]>, [email-masked]
Sent: Thursday, September 19, 2013 9:46:16 AM
Subject: RE: Processing SCIM search/query filters

--Kelly

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Steven W. Moyer
Sent: Wednesday, September 18, 2013 3:02 PM
To: [email-masked]
Subject: [scim] Processing SCIM search/query filters

Thanks,

Steve Moyer

===== SNIP =====