Branch: refs/heads/yves/octet_trie_followups
  Home:   https://github.com/Perl/perl5
  Commit: c033f5285299fabfb5be4255af002730160f8ef0
      
https://github.com/Perl/perl5/commit/c033f5285299fabfb5be4255af002730160f8ef0
  Author: Yves Orton <[email protected]>
  Date:   2026-10-10 (Sat, 10 Oct 2026)

  Changed paths:
    M pod/perldelta.pod
    M regcomp.c
    M regcomp.h
    M regcomp_trie.c
    M regexec.c
    M t/re/pat.t

  Log Message:
  -----------
  regex: accelerate Aho-Corasick scans with octet prefilters

complement Aho-Corasick matching, which can be slow, with various optimized
prefilters to find likely start points. These prefilters include a
Boyer-Moore-Horspool (BMH) shift tables of the words in the Aho-Corasick/Trie,
which can allow us to scan the string without actually looking at every octet,
along with a unified bitmap which allows us to track the legal start octets in
both latin-1 and utf8 in one data structure.

We also include a special optimization to handle long runs of characters that
cant start a match. Repeated sequences of 1, 2, 4, or 8 octet length which
cannot start are skipped at UV processing speeds. Giving very high throughput.

This combination allows us to handle most of the awkward cases at high
speed, and very often process the string at very high throughput.  A BMH
shift table can allow us to scan the string by looking at far less than
every character, potentially every Kth character, where K could be up to
255 in an extreme case.

Also includes some other minor cleanup, like avoid point-ring updates on
failed root transitions (point-ring updates how we know where a sequence
started). Another minor optimization is to reject Latin-1 targets when every
"word" requires a code point above 255.

Partial fix for https://github.com/Perl/perl5/issues/24934


  Commit: 441b64a9f91c4c81b713b8e0facc3d333ed758c9
      
https://github.com/Perl/perl5/commit/441b64a9f91c4c81b713b8e0facc3d333ed758c9
  Author: Yves Orton <[email protected]>
  Date:   2026-10-10 (Sat, 10 Oct 2026)

  Changed paths:
    M pod/perldelta.pod
    M regcomp.h
    M regcomp_trie.c
    M regexec.c
    M t/re/pat.t

  Log Message:
  -----------
  regex: use start-octet maps for folded Aho-Corasick tries

Build a conservative map of original target starts for folded tries. Use
inverse fold closures for their initial codepoints and include codepoints
whose multi-character folds begin with a possible initial folded character.
Extra candidates are safe because AC applies the actual folding rules
independently.

Leave both BMH (Boyer-Moore-Horspool) tables zero for folded tries. Their
folded octet offsets cannot describe shifts in the original target. Instead we
use the map and repeated-window scanner only at the root, with no buffered
fold or encoded transition octets required.

Also adds additional tests covering simple and multi-character folds, target
encodings, and /u, /d, /a, and /aa restrictions.

Resolves: https://github.com/Perl/perl5/issues/24935


  Commit: aaf5cd40fbb989ed05c049c828f940c243cc4b94
      
https://github.com/Perl/perl5/commit/aaf5cd40fbb989ed05c049c828f940c243cc4b94
  Author: Yves Orton <[email protected]>
  Date:   2026-10-10 (Sat, 10 Oct 2026)

  Changed paths:
    M pod/perldelta.pod
    M regexec.c
    M t/re/pat.t

  Log Message:
  -----------
  regex: stop folded start-class scans at end of UTF-8 input

Require an input character before trying a nonempty folded literal start
class.  HOP3c clamps the candidate limit to the current position when too few
characters remain.  At the end of a UTF-8 target, UTF8_SAFE_SKIP returns zero,
so the scanner otherwise retries the same failed match indefinitely.

This can occur on a subsequent /g attempt after a successful match when trie
prefix extraction leaves a folded literal start class. The reproducer also
hangs in unchanged blead. It does not use the Aho-Corasick prefilter.

Final fix for: https://github.com/Perl/perl5/issues/24934


Compare: https://github.com/Perl/perl5/compare/c033f5285299%5E...aaf5cd40fbb9

To unsubscribe from these emails, change your notification settings at 
https://github.com/Perl/perl5/settings/notifications

Reply via email to