[yunqa.de] Re: TDIRegEx2SearchStream

  • From: brett@xxxxxxxxxxx
  • To: yunqa@xxxxxxxxxxxxx
  • Date: Sat, 01 Jun 2019 11:11:47 +1000

Thanks Ralf,
   It is an excellent description of the issues.  Thanks.
Ciao
Brett

On 2019-06-01 01:06, Delphi Inspiration wrote:

You describe a known and documented limitation of the DFA matching
algorithm. In this regard, your problem applies to
TDIRegEx2SearchStream, but is not specific to it.

Could TDIRegEx2SearchStream use PERL instead of DFA matching? The
purpose of TDIRegEx2SearchStream is multi-segment regular expression
matching with little memory only. The PERL algorithm, on the contrary,
needs the entire match in memory. Simple patterns can result in large
matches and use huge amounts of memory. This conflicts with the
intention of TDIRegEx2SearchStream.

The PCRE documentation recommends PCRE2_PARTIAL_HARD for multi-segment
matching. I followed the recommendation and used PCRE2_PARTIAL_HARD for
TDIRegEx2SearchStream.

However, could PCRE2_PARTIAL_HARD be optional? PCRE2_PARTIAL_SOFT would
prefer a complete match over a partial match. In your particular
example, the pattern would match the subject. But an alternative
complete match would be missing.

More important: PCRE2_PARTIAL_SOFT already matches at the end of a
block. This leads to different results depending on where a match
crosses memory blocks and where in a block it is located. Example:

Pattern: 1.{1,200}2

Block:    1         | 2
Position: 1234567890|123456789|
          ----------+---------|
Subject:  1 2 2 2 2 |2              Result: 1 2 2 2 2
Subject:   1 2 2 2 2| 2             Result: 1 2 2 2 2
Subject:    1 2 2 2 |2 2            Result: 1 2 2 2
Subject:     1 2 2 2| 2 2           Result: 1 2 2 2
Subject:      1 2 2 |2 2 2          Result: 1 2 2

It shows that the same subject can return different results. This should
not happen and does not happen with PCRE2_PARTIAL_HARD.

Ralf

On 31.05.2019 06:26, brett@xxxxxxxxxxx wrote:

DIRegEx and YuPcre2 use the DFA variant of regex in the TDIRegEx2SearchStream class. Is it possible to use the PERL
variant? For example the search

(dave).{1,200}(this)

on a file containing

“I spoke to dave and he said he that this and this and this and that
and blah and blah happened before he shook”

Will not return a result (in say the demo YuPcre2_RegEx2_SearchStream_prog). The DFA can be changed to
PARTIALSOFT (instead of the current HARD) and it will return a greedy
result.

But using a (?U) or

(dave).{1,200}?(this)

will always return greedy (ie. The last “this”) in TDIRegEx2SearchStream. The vectors do contain all “this” hits, but I don’t know if they wanted greedy or lazy without decoding the
expression so do not know which vector to show (there are 3 in this
example case).

A PERL variant would return the lazy version.  Is it possible use
the PERL in the TDIRegEx2SearchStream, or is there a flag/option I am
missing?
_______________________________________________
Delphi Inspiration mailing list
yunqa@xxxxxxxxxxxxx
//www.freelists.org/list/yunqa
_______________________________________________
Delphi Inspiration mailing list
yunqa@xxxxxxxxxxxxx
//www.freelists.org/list/yunqa



Other related posts: