Partial DFA match semantics

[sjshuck]

I apologize for the vague title. I opened an issue in 2021, bug 2761 in the old exim issue tracker, and I don't have access to that. I wanted to keep tracking it here as I've had that in my list of things to poke at since then.

I have emails from exim with Philip's and others' contributions to that thread, but not the whole thread (and especially not my own OP).

[NWilson]

I'm afraid I don't have access to that either.

Are you able to reproduce or reconstruct an outline of the problem?

[sjshuck]

I can't reproduce it right now but I think I was trying to match over a chunk boundary using PCRE2_PARTIAL_HARD and PCRE2_PARTIAL_SOFT and neither was fulfilling my expectation "of achieving the same results that would happen if the entire string was available for searching all the time" (quoting the docs). Here's a quote from Philip in the bug thread:

Consider the pattern /1234|3789/. If the first segment is "ABC123" there is a partial match for "1234". There is no partial match for the second alternative, because such a match does not start at the same point in the subject string. Attempting to continue with the string "7890" does not yield a match because only those alternatives that match at one point in the subject are remembered.

In short, even assuming that the user held onto all chunks comprising a prospective match, it's unclear which offset to jump back to to retry the match at an advanced starting position. Non-partial matching takes care of retrying automatically. The partial matching documentation doesn't indicate this extra responsibility of the user or how best to accomplish it.

I'm not sure what the issue is here, whether just docs or an actual technical impossibility given the current implementation. I'd have to sit down and attempt a PoC to know. For now I'll just leave it with these comments in the thread from Philip and Petr Pisar, respectively, which seem to contradict the above quoted docs:

For multi-segment matching it is probably best not to make use of the "restart"
feature at all, but instead to retain the partially matched string and do a
normal match when some more text has been joined on. You can do this with DFA
or non-DFA matching.

An inability to remember an arbitrary long string
is an inherent limitation of any deterministic finite automaton. If a users
needs to remember the strings, he needs to use a different matching algorithm
than DFA.

[PhilipHazel]

Restarting a DFA partial match seemed like a good idea at the time, but I had not thought it through properly, leading to issues like the 1234|3789 problem mentioned above. In retrospect, it should probably not have been implemented. I stand by comment quoted above, advising against the use of the restart facility. Perhaps the documentation could be made stronger and/or the facility could be deprecated.

[NWilson]

I think I understand the issue after reading the documentation and comments above.

The PCRE2_DFA_RESTART feature has some questionable usability issues, but in theory, it could be useful to someone.

There is a marginal efficiency improvement when using PCRE2_DFA_RESTART. However, it doesn't avoid the central issue that you need to return to the previous chunk to continue matching.

From one loop to the next, whether you use PCRE2_DFA_RESTART or not, you need to retain all the text from the partial match start onwards (plus also MAX_LOOKBEHIND previous characters). If you hope to be able to process the file, but never ever need more than one page of it loaded in RAM at any time... well, you'd have to be prepared to go back and re-read the file to get back the previous chunk, if you throw it away.

So again in theory, with some very careful buffer management, you could get some mileage from PCRE2_DFA_RESTART. However, my suggestion would be in the docs to clarify that it's fiddly and only of use in specific RAM-constrained environments.

"Normal" chunk-wise matching (works for both pcre2_match and pcre2_dfa_match):

# Python-style pseudo-code.
# Code assumes there is a file which can be read chunk-by-chunk into a buffer,
# and searches for a match while avoiding loading the entire file into RAM at once.

# Create a buffer; populate with start of file
buffer = new byte[1024]
buffer_used = 0
buffer, buffer_used = populate_buffer(file_handle, buffer, buffer_used)

partial_flags = PCRE2_PARTIAL_HARD

start_offset = 0
while buffer_used > 0:
    # Run a search with the PARTIAL flags.
    # Either normal or DFA matching can be used
    result = do_match(buffer, buffer_used, start_offset, partial_flags)

    # If no match found, continue with next chunk/page
    if result == PCRE2_ERROR_NOMATCH:
        # Retain some data for the purpose of lookbehinds. See note below - this
        # is an imperfect heuristic (since lookbehinds can be, in theory, very long)
        buffer_keep = min(512, buffer_used)
        memmove(buffer, buffer + buffer_used - buffer_keep, buffer_keep)
        buffer_used = buffer_keep

        buffer, buffer_used = populate_buffer(file_handle, buffer, buffer_used)
        start_offset = buffer_keep
        continue

    # If a partial match is found, double the buffer size and populate it, then try again
    if result == PCRE2_ERROR_PARTIAL:
        buffer = double_buffer_and_copy(buffer)
        buffer, buffer_used = populate_buffer(file_handle, buffer, buffer_used)
        start_offset = result.ovector[0]
        continue

    # !!! NOTE: if partial matches keep being found at the end of a chunk, then the
    # code above can end up loading the entire file into the buffer. A more robust
    # loop would memmove the buffer leftwards if start_offset becomes too
    # large. This depends on knowing the size of the largest lookbehind (which
    # can be rather large).

    # Otherwise, we have either a match error, or a complete match
    return result

Special DFA chunk-wise matching

# Python-style pseudo-code.
# Code assumes there is a file which can be read chunk-by-chunk into a buffer,
# and searches for a match while avoiding loading the entire file into RAM at once.

# Create a buffer; populate with start of file
buffer = new byte[1024]
buffer_used = 0
buffer, buffer_used = populate_buffer(file_handle, buffer, buffer_used)

partial_flags = PCRE2_PARTIAL_HARD # const

start_offset = 0
restart_offset_0 = 0
restart_offset_1 = 0
restart_flags = 0
while buffer_used > 0:
    # Run a search with the PARTIAL flags.
    # DFA matching is used here
    result = do_dfa_match(
        buffer + restart_offset_1, buffer_used - restart_offset_1,
        start_offset, partial_flags | restart_flags)
    result.ovector[0] += restart_offset_1 # keep offsets all in same units
    result.ovector[1] += restart_offset_1

    # If no match found after restart, then go back to the match point
    if result == PCRE2_ERROR_NOMATCH and restart_flags != 0:
        # NB. Could do a bump-along here as the docs suggest; not mandatory
        # however.
        start_offset = restart_offset_0
        restart_offset_0 = 0
        restart_offset_1 = 0
        restart_flags = 0
        continue

    # Otherwise, if no match found, continue with next chunk/page
    if result == PCRE2_ERROR_NOMATCH:
        # NOTE: should actually keep some buffer as noted in previous code snippet
        buffer_used = 0
        buffer, buffer_used = populate_buffer(file_handle, buffer, buffer_used)
        start_offset = 0
        restart_offset_0 = 0
        restart_offset_1 = 0
        restart_flags = 0
        continue

    # If a partial match is found, double the buffer size and populate it, then try again
    if result == PCRE2_ERROR_PARTIAL:
        buffer = double_buffer_and_copy(buffer)
        buffer, buffer_used = populate_buffer(file_handle, buffer, buffer_used)
        if restart_flags == 0:
            # (retain restart_offset_0 if we're already doing a restart)
            restart_offset_0 = result.ovector[0]
        restart_offset_1 = result.ovector[1]
        restart_flags = PCRE2_DFA_RESTART
        continue

    # Otherwise, we have either a match error, or a complete match
    return result

[PhilipHazel]

The size of the largest lookbehind in a pattern is known, and can be retrieved with PCRE2_INFO_MAXLOOKBEHIND. There is also MAX_LOOKBEHIND, which is the largest that PCRE2 supports.

[NWilson]

You note in the docs that nested lookbehinds can multiply this (potentially by up to 255?).

[sjshuck]

FWIW, my use case is implementing matching on infinite streams, freeing any prior chunks as they are proven to be no longer needed.

[NWilson]

In that case, I would suggest avoiding PCRE2_DFA_RESTART. The first pseudocode chunk I provided may be useful - I haven't tested it, but it matches how I would expect the API to be used.

Thank you for bringing this issue to my attention. It probably should be documented a little further.