[% setvar title Regex: Support for incremental pattern matching %]

This file is part of the Perl 6 Archive

Note: these documents may be out of date. Do not use as reference!

To see what is currently happening visit http://www.perl6.org/


Regex: Support for incremental pattern matching


  Maintainer: Damian Conway <damian@conway.org>
  Date: 11 Aug 2000
  Last Modified: 18 Sep 2000
  Number: 93
  Version: 3
  Mailing List: perl6-language-regex@perl.org
  Status: Frozen


This RFC proposes that, in addition to strings, subroutine references may be bound (with =~ or !~ or implicitly) to a regular expression.


It is proposed that the Perl 6 regular expression engine be extended to allow a regex to match against an incremental character source, rather than only against a fixed string.

Specifically, it is proposed that a subroutine reference could be bound to a regular expression:

	sub {...} =~ /pattern/;

As the regular expression is matched, it would make calls to the subroutine to request additional characters to match, or (after it has matched) to return any unused characters.

When the regex engine requires additional characters to match, the subroutine would be called with a single argument, and would be expected to return a character string containing the extra characters. The single argument would specify how many characters should be returned (typically this would be 1, unless internal analysis by the regex engine can deduce that more than one character will be required). Returning fewer than the requested number of characters would typically indicate a premature end-of-string and would probably trigger backtracking and/or failure to match.

When the match is finished, the subroutine would be called one final time, and passed two arguments: a string containing the "unused" characters (what would be $' for a fixed string), and a flag set to 1. The subroutine could use this call to push-back (or cache) unused data. In the case of a failure to match (or success of the !~ operator), every character requested during the match would be sent back.

A typical structure for a subroutine against which a regex was matched would therefore be:

	sub s {
	    if ($_[1]) {		# "putback unused data" request
	    else {			# "send more data" request
		return get_chars(max=>$_[0])


The most obvious example would be matching against an input stream:

	sub { $_[1] ? $fh->pushback($_[0]) : $fh->getn($_[0]) } =~ /pat/;

which could also be written:

	^1 ? $fh->pushback(^0) : $fh->getn(^0)	=~ /pat/;

Of course, it would often be useful to have a subroutine that returns a closure on a particular filehandle:

	sub fhmatch { ^1 ? $_[0]->pushback(^0) : $_[0]->getn(^0) }

	fhmatch($fh)     =~ /pat/
	fhmatch(\*STDIN) =~ /pat/
	# etc.

In fact, this might be so commonly useful that matching against a file handle should be made to work directly. That is:

	$fh =~ /pat/
	\*STDIN =~ /pat/

One could then do interactive lexing cleanly:

	until (eof $fh) {
		switch ($fh) {
			/^\s*/;			# skip leading whitespace
			case /^(lexeme1)/	{ push @tokens, $1=>LEX1 }
			case /^(lexeme2)/	{ interact_somehow }
			case /^(lexeme3)/	{ push @tokens, $1=>LEX3 }
			# etc.

Note the use of the proposed PAIR data structure to store tokens in the above example.

Because the character source is a subroutine, one could also match against data coming out of a socket:

	my $cache = "";

	sub matching_socks {
		if ($_[1]) { $cache .= $_[0]; return }	# putback
		if (length($cache) < $_[0]) {		# not enough cached
			my $extra;			# so get some more
			recv(SOCKET, $extra, $_[0]-length($cache));
			$cache .= $extra;
		return substr($cache,0,$_[0],"");

	switch (\&matching_socks) {
		case /pat1/ { action1() }
		case /pat2/ { action1() }
		case /pat3/ { action1() }

or any other source:

	sub mega_ape {
		return join "", map {['a'..'z',(' ')x6]->[rand 32]} (1..$_[0])
			unless $_[1]

	\&mega_ape =~ /Now is the Winter of our discontent.../i;

	print "Art after ", length($`), "chars\n";


Dammit, Jim, I'm a doctor, not an magician!

Probably needs to be integrated with IO disciplines too.


RFC 22: Builtin switch statement

RFC 23: Higher order functions

RFC 84: Replace => (stringifying comma) with => (pair constructor)