Subject: ListMatch Clarification

From: Daniel Henninger <[email-masked]>
Date: Sat, 19 Jun 2004 21:29:39 -0400 (EDT)

Folk,

I'm looking into implementing the ListMatch style matches and submitting a
patch.  I am having some trouble understanding part of the specification.
I understand that $ is effectively a newline.  The draft seems to indicate
that you ignore $ (ie, pull it out) and escape (\).  That said, the part
I'm not clear on is the actual search string.  Does the $ get handled in
the search string as well?  For example, lets say I want to find someone
on Foo Street, in Raleigh, NC.  Would I do a search along the lines of:
postalAddress=*Foo Street $ Raleigh, NC*
or
postalAddress=*Foo Street * Raleigh, NC*
or both?

Also is there supposed to be a space on both sides of the $, similar to
how $'s are used in schema, or would there be no spaces?

Daniel

-- 
/\\\----------------------------------------------------------------------///\
\ \\\      Daniel Henninger           http://www.vorpalcloud.org/        /// /
 \_\\\      North Carolina State University - Systems Programmer        ///_/
    \\\                   Information Technology <IT>                  ///
     """--------------------------------------------------------------"""

---

From: Steven Legg <[email-masked]>
Date: Mon, 21 Jun 2004 12:02:31 +1000

Daniel,

> postalAddress=*Foo Street * Raleigh, NC*

The second assertion value is the one that applies. The assertion syntax for
caseIgnoreListSubstringsMatch is Substring Assertion, for which $ is an
ordinary character (only * and \ are special). The first assertion value
would only match if there were an escaped $ (i.e. not a line separator)
in a line of the address (where only $ and \ are special).

The unescaped $ line separators in a Postal Address value are an artefact
of the LDAP-specific encoding and are not matchable character data.

> how $'s are used in schema, or would there be no spaces?

There is no requirement either way, and for caseIgnoreListMatch it makes no
difference since each line of the address is matched according to
caseIgnoreMatch which ignores leading and trailing space on each line.
It makes no difference for caseIgnoreListSubstringsMatch as well
because of the interaction of stringprep and the requirement that
a substring in an assertion value for caseIgnoreListSubstringsMatch
does not match characters across multiple lines.

Regards,
Steven

---

From: [email-masked]
Date: Mon, 21 Jun 2004 07:55:08 -0400 (EDT)

> of the LDAP-specific encoding and are not matchable character data.

Hrm.  Ok, let me see if I understand this correctly.  The address query is
matched on lines, not the string as a whole?  Given address:
123 Foo Street
Raleigh, NC 12345
aka: 123 Foo Street $ Raleigh, NC 12345

If I did a query of *Raleigh*, I would expect it to:
123 Foo Street		no match
Raleigh, NC 12345	match
	address matches

If I did a query of *Foo*, I would expect it to:
123 Foo Street		match
Raleigh, NC 12345	no match
	address matches

But what if I did *Foo Street*Raleigh*, I would expect it to:
123 Foo Street		no match
Raleigh, NC 12345	no match
	address doesn't match

Is this a correct interpretation of how it should work?  If you wanted to
make sure it was Foo Street in Raleigh, NC, how would you go about doing
that?  (&(postalAddress=*Foo Street*)(postalAddress=*Raleigh*)) ?

Thanks!

Daniel

---

From: John McMeeking <[email-masked]>
Date: Mon, 21 Jun 2004 08:18:06 -0500

I'm responding to test my understanding.

As I understand it, matching applies to the entire address as a
concatinated string, excluding the $ separators, except that * --
<initial>, <any>, or <final> -- does not span lines in an attribute value.
That is, * matches a substring of a line or the entire line, but not parts
of two lines.

> aka: 123 Foo Street $ Raleigh, NC 12345

Matching will be applied to the concatinated string "123 Foo Street
Raleigh, NC 12345" with a hidden separator replacing the $.

> If I did a query of *Raleigh*, I would expect it to:

Matches:
Initial * matches "123 Foo Street", "Raleigh" matches Raleigh, final *
matches ", NC 12345"

> Raleigh, NC 12345   no match

No match:
Initial * matches either a) the entire first line or b) "123"
a) "Foo *" does not match second line
b) "Foo *" matches "Foo Street" but does not include the next line of the
address.

> Raleigh, NC 12345   no match

Matches:
Initial "*Foo Street" matches 1st line, 2nd "*" matches empty string,
"Raleigh*" matches 2nd line.

Personal observations:
- Since the middle * is matching an empty string, "*Foo Street Raleigh*"
should also match.
- "*Foo Street*Raleigh*" could also match addresses like:
   123 Foo Street NW
   Raleigh, NC 12345
or
   123 Foo Street
   North Raleigh, NC 12345

> that?  (&(postalAddress=*Foo Street*)(postalAddress=*Raleigh*)) ?

Is my interpretation any better?

John  McMeeking

---

From: Daniel Henninger <[email-masked]>
Date: Mon, 21 Jun 2004 11:12:00 -0400 (EDT)

> That is, * matches a substring of a line or the entire line, but not parts

So if I'm understanding that correctly, one would have to do:
*Foo**NC* to match my example below?  I'll get to that.

> Raleigh, NC 12345" with a hidden separator replacing the $.

but the hidden seperator "stops dead" the *?  is that correct?

> Initial * matches "123 Foo Street", "Raleigh" matches Raleigh, final *

And it only matches Raleigh because Raleigh is right at the beginning of
the line.  Correct?  If it were *NC*, it would -not- match?

> b) "Foo *" matches "Foo Street" but does not include the next line of the

Ok, that makes sense based off my understanding from above.  =)

> - "*Foo Street*Raleigh*" could also match addresses like:

Because the first line would match *Foo Street* and the second line
would match the Raleigh* portion.

>    North Raleigh, NC 12345

And because the first line would match *Foo Street and the second line
would match *Raleigh*.

> Is my interpretation any better?

Yes, that makes sense.  Makes it a lot harder to parse, but hey.  =)
Thanks!

Daniel

---

From: John McMeeking <[email-masked]>
Date: Mon, 21 Jun 2004 10:54:11 -0500

I think you've got it right, assuming someone else doesn't correct me.

Would it help to have some examples in the ldapbis syntaxes draft
illustrating some of these cases?

John  McMeeking

> *Foo**NC* to match my example below?  I'll get to that.

That's how I understand it.

> > > Hrm.  Ok, let me see if I understand this correctly.  The address
query
> > is

I believe so.  Both X.520 and ldapbis [SYNTAXES] say:

   ... none of the <initial>, <any>, or <final> substrings of the
   assertion value are considered to match a substring of the
   concatenated string which spans more than one of the original strings
   of the attribute value.

> the line.  Correct?  If it were *NC*, it would -not- match?

Correct, (postaladdress=*NC*) would not match this address.

> > > > > that you ignore $ (ie, pull it out) and escape (\).  That said,
the
> > part
> > > > > I'm not clear on is the actual search string.  Does the $ get
handled
> > in
> > > > > on Foo Street, in Raleigh, NC.  Would I do a search along the
lines
> > of:
> > > Hrm.  Ok, let me see if I understand this correctly.  The address
query
> > is
> > > > > Also is there supposed to be a space on both sides of the $,
similar
> > to

---

From: Daniel Henninger <[email-masked]>
Date: Mon, 21 Jun 2004 12:59:54 -0400 (EDT)

> illustrating some of these cases?

=)  I always think examples are a good thing!

Daniel

---

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Mon, 21 Jun 2004 14:22:11 -0700

I think the syntax I-D note regarding LDAP-string encoding
handling is causing some confusion here.  I would instead
say that caseIgnoreSubstringsListMatch(substrings,list) is,
in terms of the LDAP-specific encodings, acts like
caseIgnoreMatch(escape(substrings),list) where escape()
escapes "\" and "$" appearing in substrings so that they
will properly match like characters appearing in list
strings (but not list separators).

>> That is, * matches a substring of a line or the entire line, but not parts

I think it a bit dangerous to think of * as wildcard.
But if one has foo*bar*foo than each * can certain "match"
portions of multiple lines.  However, each substring
(foo, bar, foo) must appear wholly within one line.
That is, *foobar* does not match foo$bar.

>*Foo**NC* to match my example below?  I'll get to that.

This assertion is invalid.  All substrings must have
non-zero length.

>> Applying this to your later examples:

I think the rest of this stuff is confused.

Do not think of '*' as a wildcard.  Think in terms
of the <initial>, <any>, and <final> substrings being
asserted and the list of strings they are matched
against.

---

From: Steven Legg <[email-masked]>
Date: Tue, 22 Jun 2004 10:56:14 +1000

Daniel,

Daniel Henninger wrote:
 > John McMeeking wrote:

It is not the intention that the * separators in a Substring Assertion value
are part of the substrings that are matched, and which are required to match
entirely within a line. As Kurt points out, it isn't appropriate to think
of the *'s as wildcards either. I will try to rewrite the text about substring
matching to make this clearer in the next revision.

> *Foo**NC* to match my example below?  I'll get to that.

The substrings to be matched are "Foo" and "NC", so the correct assertion
is "*Foo*NC*". The position of the *'s tells us that "Foo" and "NC" are
both any substrings (as opposed to initial or final substrings).

>>>Hrm.  Ok, let me see if I understand this correctly.  The address query
>>
>>is
>>

No, because the * isn't part of a substring to be matched.

> the line.  Correct?  If it were *NC*, it would -not- match?

"*NC*" would match because the any substring "NC" completely matches a string
of characters wholly contained within a line of the address (the second line).

>>b) "Foo *" matches "Foo Street" but does not include the next line of the

"*Foo*" would match because the any substring "Foo" completely matches a string
of characters wholly contained within a line of the address (the first line).

>>"Raleigh*" matches 2nd line.

The address matches. The any substring "Foo Street" completely matches a
string of characters wholly contained within a line of the address (the
first line) and the any substring "Raleigh" completely matches a subsequent
string of characters wholly contained within a line of the address (the
the second line).

>>- Since the middle * is matching an empty string, "*Foo Street Raleigh*"

"*Foo Street Raleigh*" won't match because the any substring "Foo Street Raleigh"
does not match any string of characters which is wholly contained within any
one line of the address.

> would match the Raleigh* portion.

It's the right answer, but the reasoning is that the any substring "Foo Street"
completely matches a string of characters wholly contained within a line of the
address (the first line) and the any substring "Raleigh" completely matches a
subsequent string of characters wholly contained within a line of the address
(the second line).

The examples have substrings matching strings of characters on separate lines
but there is nothing to stop the substrings matching disjoint strings of
characters on the same line.

Regards,
Steven

>>>>>I'm looking into implementing the ListMatch style matches and
>>
>>submitting a
>>
>>>>>patch.  I am having some trouble understanding part of the
>>
>>specification.
>>
>>>>>I understand that $ is effectively a newline.  The draft seems to
>>
>>indicate
>>
>>>>>that you ignore $ (ie, pull it out) and escape (\).  That said, the
>>
>>part
>>
>>>>>I'm not clear on is the actual search string.  Does the $ get handled
>>
>>in
>>
>>>>>the search string as well?  For example, lets say I want to find
>>
>>someone
>>
>>>>>on Foo Street, in Raleigh, NC.  Would I do a search along the lines
>>
>>of:
>>
>>>>The second assertion value is the one that applies. The assertion
>>
>>syntax for
>>
>>>>ordinary character (only * and \ are special). The first assertion
>>
>>value
>>
>>>>The unescaped $ line separators in a Postal Address value are an
>>
>>artefact
>>
>>>Hrm.  Ok, let me see if I understand this correctly.  The address query
>>
>>is
>>
>>>>>Also is there supposed to be a space on both sides of the $, similar
>>
>>to
>>
>>>>There is no requirement either way, and for caseIgnoreListMatch it
>>
>>makes no
>>
>>>\ \\\      Daniel Henninger           http://www.vorpalcloud.org/
>>
>>/// /
>>
>>> \_\\\      North Carolina State University - Systems Programmer
>>
>>///_/
>>
>>>    \\\                   Information Technology <IT>
>>
>>///
>>

---

From: Steven Legg <[email-masked]>
Date: Tue, 22 Jun 2004 10:58:24 +1000

I'll look at adding some examples in the next revision.

Regards,
Steven

Daniel Henninger wrote:
>>>><initial>, <any>, or <final> -- does not span lines in an attribute
>>
>>value.
>>
>>>>That is, * matches a substring of a line or the entire line, but not
>>
>>parts
>>
>>>>of two lines.
>>>
>>>>b) "Foo *" matches "Foo Street" but does not include the next line of
>>
>>the
>>
>>>>address.
>>>
>>>>- Since the middle * is matching an empty string, "*Foo Street
>>
>>Raleigh*"
>>
>>>>should also match.
>>>>>>caseIgnoreListSubstringsMatch is Substring Assertion, for which $
>>
>>is an
>>
>>>>>>would only match if there were an escaped $ (i.e. not a line
>>
>>separator)
>>
>>>>>Is this a correct interpretation of how it should work?  If you
>>
>>wanted to
>>
>>>>>make sure it was Foo Street in Raleigh, NC, how would you go about
>>
>>doing
>>
>>>>>>caseIgnoreMatch which ignores leading and trailing space on each
>>
>>line.
>>

---

From: Steven Legg <[email-masked]>
Date: Tue, 22 Jun 2004 12:51:09 +1000

Kurt,

> say that caseIgnoreSubstringsListMatch(substrings,list) is,

caseIgnoreListSubstringsMatch

The function notation you are using hasn't been defined anywhere.

> caseIgnoreMatch(escape(substrings),list) where escape()

caseIgnoreSubstringsMatch

> strings (but not list separators).

I prefer to be replacing escapes in the concatenated string rather
than adding escapes to the substrings of the substring assertion because
the latter is heading down the direction of comparing LDAP-specific
encodings rather than comparing abstract values.

The syntax definition for SubstringAssertion currently only allows
escapes for "\" and "*". It would need to be extended to allow for "$"
as well.

There is also the problem that the concatenated string, which is notionally
of the Directory String syntax, or similar, would contain escaped "$" but
the Directory String syntax does not have a defined escaping mechanism in
either RFC 2252 or the syntaxes draft. If we regard "\24" as literal text
then we have a weird situation where caseIgnoreSubstringsMatch matches "\24"
with "\24" but not "$", while "\2A" matches "*" but not "\2A". Yikes!

Regards,
Steven

---

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Mon, 21 Jun 2004 20:11:32 -0700

>encodings rather than comparing abstract values. 

I actually dislike, to a lessor degree, the current note for
the same reason (but not enough to call for the note to be
removed).

Kurt

---

From: Daniel Henninger <[email-masked]>
Date: Wed, 23 Jun 2004 08:06:13 -0400 (EDT)

=)  Ok, I hushed up briefly to let all the responses come in and level
off.  So one important thing I am to understand is that * is not
'wildcard', instead it means:

Foo*      Foo is at the beginning of the line
*Foo      Foo is at the end of the line
*Foo*     Foo is somewhere in the line

Is this correct?  So they are not necessarily treated as wild cards
(though they behave similarly)?

I am still not clear on *Foo*Raleigh*.  Is that equal to:
*Foo*
 and
*Raleigh*

or is it 'split up' and equal more to:
*Foo*
Raleigh*
 or
*Foo
*Raleigh*

if the latter is the case, which one wins?

If the former is the case, if I wanted to search for Foo anywhere in a
line plus Raleigh at the beginning of a line, would I need to do:
*Foo* Raleigh*
(ie, have a space separator?)

Anyway, for the List match aspect, do you just try to match each piece and
if all of the pieces match, then you have a list match?  Like you would go
through looking for a match for *Foo*.  When you found it, move in to
the Raleigh part and continue on looking for it.  If you find the Raleigh
part, great, you have a match.  Otherwise, nope?

Daniel

---

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Wed, 23 Jun 2004 11:40:57 -0700

>Foo*      Foo is at the beginning of the line

Foo is to be matched with initial portion of the value,
in this case, the beginning of the first line of the list.

>*Foo      Foo is at the end of the line

Foo is to be matched with final portion of the value,
in this case, the end of the last line of the list.

>*Foo*     Foo is somewhere in the line

Foo is to be matched with a portion of the value,
in this case, any part of any line of the list.

>I am still not clear on *Foo*Raleigh*.  Is that equal to:

No, the substrings assertion *Foo*Raleigh* is not
equivalent to the AND of substrings assertions *Foo*
and *Raleigh*.

In evaluation of *Foo*Raleigh*, Foo is to matched with any
part of any line of the list and Raleigh is to be matched
with any part of any line of the list subsequent to the
part which *Foo* matched.  That is, *Foo*Raleigh* would
match Foo$Raleigh or Foo_Raleigh but not Raleigh$Foo nor
Raleigh_Foo.

>if I wanted to search for Foo anywhere in a

The substrings matching rule doesn't support such assertions.
As a substrings assertions, *Foo* Raleigh* and *Foo*Raleigh*
will match the same entries as the extra leading space in
the second any string (in the first assertion) is simply
ignored.

>part, great, you have a match.  Otherwise, nope?

It's unclear to me that your description is correct.

caseIgnoreListSubstringsMatch has the same basic substrings
semantics as caseIgnoreSubstringsMatch.  Instead of matching
against a single directory string, the former matches against
a list of directory strings (lines).  The initial substring, if
asserted, must match the beginning of the first line.  The
final substring, if asserted, must match the end of the last
line.  Each any substrings match in between.  The matched
portions must not overlap each other, must not span lines,
and must appear in the same order as the substrings.  Multiple
matched portions, however, may be in the same line... and
some lines may have no matched portions.

Kurt

---

From: Daniel Henninger <[email-masked]>
Date: Wed, 23 Jun 2004 14:49:21 -0400 (EDT)

> some lines may have no matched portions.

Ok so, caseIgnoreListSubstringsMatch is no different than
caseIgnoreSubstringsMatch -except- for:

A. the list is effectively concatenated into one line
B. there are "markers" where there were line breaks that no single pattern
   can cross
C. \'s and $'s are handled so that they can be escaped out

Does that sound right?

Daniel

---

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Wed, 23 Jun 2004 13:15:16 -0700

>C. \'s and $'s are handled so that they can be escaped out

Yes.

---

From: Daniel Henninger <[email-masked]>
Date: Mon, 28 Jun 2004 13:56:56 -0400 (EDT)

> >C. \'s and $'s are handled so that they can be escaped out

Excellent.  So I've been looking at what it would take to implement this,
and here is how I "think I should implement it".  I'd definitely like
feedback before going through with this.  I also have a side question, but
I'll get to this.  First of all, here's how I propose that I would
implement this:

given: A. is the query string
       B. is the entity within the ldap db I am comparing against

1. convert A to "escaped" format by running that escape command on it
   (assuming that is a real command  haven't looked at that)  escape
   out $ and \

2. convert B by turning the line separator $ into a ^M (ctrl-M)  (or a \n
   not sure which would be better there)

3. turn the converted A and B over to caseIgnoreSubstringsMatch for
   comparison

This does mean that an added side effect is that you could actually
-match- those newlines using ^M or \n, depending on which were used.
Personally, I don't think anything is wrong with that.  ;)

If I can do that, then my second question is moot.  If I can not allow the
newline to be matchable at all, then how is it possible to do a
non-substrings match?

Daniel

---

From: Steven Legg <[email-masked]>
Date: Tue, 29 Jun 2004 11:05:54 +1000

Daniel,

>    (assuming that is a real command  haven't looked at that)  escape

Our implementation unescapes B and stores it as a list of lines. This is
closer to the spirit of X.500. Escaping A should have the same effect as far
as I can see, but there are nuances to deal with.

>    not sure which would be better there)

Why change the $ separator ? If you have escaped $ in the assertion substrings
then none of the substrings can match a literal $ in B. What you will need to
do though is escape any *'s in B because they are already escaped in A. All this
assumes that the routine for matching substrings is doing a literal character
comparison and is ignorant of character escapes.

> Personally, I don't think anything is wrong with that.  ;)

It would not be conformant with the specification of caseIgnoreListSubstringsMatch.

> newline to be matchable at all, then how is it possible to do a

1) Don't map the $'s in B to anything else. Do escape the *'s in B.

OR

2) The description of caseIgnoreListSubstringsMatch depends on the description
of caseIgnoreSubstringsMatch but that doesn't mean it must necessarily be
implemented that way. Our implementation uses a separate function for
caseIgnoreListSubstringsMatch. It attempts to match as many of the assertion
substrings as it can in the first line (where an initial substring must match
the beginning of the first line). If there are any left over it attempts
to match the remainder on the second line. If there are still some left over it
attempts to match the new remainder on the third line, and so on. If all the substrings
get matched, and any final substring matches the end of the last line, then success!

Since we store B as a list of separately terminated lines (and do much the same for A)
there is no need to worry about separators or escaping (except to undo it on input).

Regards,
Steven

---

From: [email-masked]
Date: Mon, 28 Jun 2004 21:13:54 -0400 (EDT)

Aiyee!  Ok, folk, I'm sorry.  I'm apparantly just not getting what the
goal is with these list matches.  I keep hearing what sound like, to me,
conflicting definitions of how it should work.  I am going to humbly back
off and continue to use openldap as is until someone else who is more
familiar with the standard and the code has some time to implement
listmatches.  Sorry folk.  Thanks much for all the help and
explanations regardless!

Daniel