I6 Template Layer

Algorithm.

Once Inform 7 supported (indexed) text, regular-expression matching became an obvious goal: regexp-based features offer more or less the gold standard in text search and replace facilities, and I7 is so concerned with text that we shouldn't make do with less. But the best and most portable implementation of regular expression matching, PCRE by Philip Hazel, is about a hundred times larger than the code in this section, and also had unacceptable memory needs: there was no practicable way to make it small enough to do useful work on the Z-machine. Nor could an I6 regexp-matcher compile just-in-time code, or translate the expression into a suitable deterministic finite state machine. One day, though, I read one of the papers which Brian Kernighan writes every few years to the effect that regular-expression matching is much easier than you think. Kernighan is right: writing a regexp matcher is indeed easier than you think (one day's worth of cheerful hacking), but debugging one until it passes the trickiest hundred of Perl's 645 test cases is another matter (and it took a whole week more). Still, the result seems to be robust. The main compromise made is that backtracking is not always comprehensive with regexps like ^(a\1?){4}$, because we do not allocate individual storage to backtrack individually through all possibilities of each of the four uses of the bracketed subexpression – which means we miss some cases, since the subexpression contains a reference to itself, so that its content can vary in the four uses. PCRE's approach here is to expand the expression as if it were a sequence of four bracketed expressions, thus removing the awkward quantifier {4}, but that costs memory: indeed this is why PCRE cannot solve all of Perl's test cases without its default memory allocation being raised. In other respects, the algorithm below appears to be accurate if not very fast.

Class Codes.

While in principle we could keep the match expression in textual form, in practice the syntax of regular expressions is complex enough that this would be tricky and rather slow: we would be parsing the same notations over and over again. So we begin by compiling it to a simple tree structure. The tree is made up of nodes, and each node has a "class code": these are identified by the *_RE_CC constants below. Note that the class codes below are all negative: this is so that they are distinct from all valid ZSCII or Unicode characters. (ZSCII is used only on the Z-machine, which has a 16-bit word but an 8-bit character set, so that all character values are positive; similarly, Unicode is (for our purposes) a 16-bit character set on a 32-bit virtual machine.)

Packets.

The nodes of the compiled expression tree are stored in "packets", which are segments of a fixed array. A regexp complicated enough that it cannot be stored in RE_MAX_PACKETS packets will be rejected with an error: it looks like a rather low limit, but in fact suffices to handle all of Perl's test cases, some of which are works of diabolism.

A packet is then a record containing 14 fields, with offsets defined by the constants defined below. These fields combine the compilation of the corresponding fragment of the regexp with both the tree structure holding these packets together and also the current state of the temporary variables recording how far we have progressed in trying all of the possible ways to match the packet.

Nodes.

The routine to create a node, something which happens only during the compilation phase, and also the routine which returns the address of a given node. Nodes are numbered from 0 up to M-1, where M is the constant RE_MAX_PACKETS.

Match Variables.

A bracketed subexpression can be used as a variable: we support \1, ..., \9 to mean "the value of subexpression 1 to 9", and \0 to mean "the whole text matched", as if the entire regexp were bracketed. (PCRE and Perl also allow \10, \11, ..., but we don't, because it complicates parsing and memory is too short.)

RE_Subexpressions-->10 stores the number of subexpressions in use, not counting \0. During the compiling stage, RE_Subexpressions-->N is set to point to the node representating \N, where N varies from 1 to 9. When matching is complete, and assuming we care about the contents of these variables – which we might not, and if not we certainly don't want to waste time and memory – we call TEXT_TY_RE_CreateMatchVars to allocate text variables and fill them in as appropriate, memory permitting.

TEXT_TY_RE_EmptyMatchVars empties any such variables which may survive from a previous match, setting them to the empty text.

Markers.

At each node, the -->RE_DATA1 and -->RE_DATA2 fields represent the character positions of the start and end of the text matched by the node and its subtree (if any). These are called markers.

Thus TEXT_TY_MV_End(N, 0) returns the start of \N and TEXT_TY_MV_End(N, 1) the end of \N, according to the current match of subexpression N.

Debugging.

Code in this paragraph simply prints a convenient screen representation of the compiled regexp, together with the current values of its markers. It is invaluable for debugging purposes and, touch wood, may not be needed again, but it is relatively compact and we keep it just in case.

Compiling Tree For Substring Search.

When we search for a literal substring, say looking for "per" in "Supernumerary", we will in fact use the same apparatus as when searching for a regular expression: we compile a very simple node tree in which \0 as the root contains just one child node, a LITERAL_RE_CC matching exactly the text "per". We return 2 since that's the number of nodes in the tree.

Compiling Tree For Regexp Search.

But in general we need to compile a regular expression string into a tree of the kind described above, and here is the routine which does that, returning the number of nodes used to build the tree. The syntax it accepts is very fully documented in Writing with Inform, so no details are given here.

Parser.

The virtue of all of that tree compilation is that the code which actually does the work – which parses the source text to see if the regular expression matches it – is much shorter and quicker: indeed, it takes up fewer lines than the compiler part, which goes to show that decoding regular expression syntax is a more complex task than acting upon it. This would have surprised the pioneers of regexp, but the syntax has become much more complicated over the decades because of a steady increase in the number of extended notations. The process shows no sign of stopping, with Python and PCRE continuing to push boundaries beyond Perl, which was once thought the superest, duperest regexp syntax there could be. However: to work.

The main matcher simply starts a recursive subroutine to perform the match. However, the subroutine tests for a match at a particular position in the source text; so the main routine tries the subroutine everywhere convenient in the source text, from left to right, until a match is made – unless the regexp is constrained by a ^ glyph to begin matching at the start of the source text, which will cause a START_RE_CC node to be the eldest child of the \0 root.

Parse At Position.

TEXT_TY_RE_ParseAtPosition(ftxt, txt, ifrom, ito) attempts to match text beginning at position ifrom in the text txt and extending for any length up to position ito: it returns the number of characters which were matched (which can legitimately be 0), or -1 if no match could be made. ftxt is the original text of the regular expression in its precompiled form, which we need partly to print good debugging information, but mostly in order to match against a LITERAL_RE_CC node.

Backtracking.

It would be very straightforward to match regular expressions with the above recursive code if, for every node, there were a fixed number of characters (depending on the node) such that there would either be a match eating that many characters, or else no match at all. If that were true, we could simply march through the text matching until we could match no more, and although some nodes might have ambiguous readings, we could always match the first possibility which worked. There would never be any need to retreat.

Well, in fact that happy state does apply to a surprising number of nodes, and some quite complicated regular expressions can be made which use only them: <abc>{2}\d\d\1, for instance, matches a sequence of exactly 6 characters or else fails to match altogether, and there is never any need to backtrack. One reason why backtracking is a fairly good algorithm in practice is that these "good" cases occur fairly often, in subexpressions if not in the entire expression, and the simple method above disposes of them efficiently.

But in an expression like ab+bb, there is no alternative to backtracking if we are going to try to match the nodes from left to right: we match the "a", then we match as many "b"s as we can – but then we find that we have to match "bb", and this is necessarily impossible because we have just eaten all of the "b"s available. We therefore backtrack one node to the b+ and try again. We obviously can't literally try again because that would give the same result: instead we impose a constraint. Suppose it previously matched a row of 23 letter "b"s, so that the quantifier + resulted in a multiplicity of 23. We then constrain the node and in effect consider it to be b{1,22}, that is, to match at least 1 and at most 22 letter "b"s. That still won't work, as it happens, so we backtrack again with a constraint tightened to make it b{1,21}, and now the match occurs as we would hope. When the expression becomes more complex, backtracking becomes a longer-distance, recursive procedure – we have to exhaust all possibilities of a more recent node before tracking back to one from longer ago. (This is why the worst test cases are those which entice us into a long, long series of matches only to find that a guess made right back at the start was ill-fated.)

Rather than describing TEXT_TY_RE_SeekBacktrack in detail here, it is probably more useful to suggest that the reader observe it in action by setting TEXT_TY_RE_Trace and trying a few regular expressions.

Fail Subexpressions.

Here, an attempt to make a complicated match against the node in token has failed: that means that any subexpressions which were matched in the course of the attempt must also in retrospect be considered unmatched. So we work down through the subtree at token and empty any markers for subexpressions, which in effect clears their backslash variables – this is important as, otherwise, the contents left over could cause the alternative reading of the token to be misparsed if it refers to the backslash variables in question. (If you think nobody would ever be crazy enough to write a regular expression like that, you haven't see Perl's test suite.)

If the downwards flag is clear, it not only invalidates subexpression matches below the node but also to the right of the node – this is useful for a backtrack which runs back quite some distance.

Erasing Constraints.

As explained above, temporary constraints are placed on some nodes when we are backtracking to test possible cases. When we do backtrack, though, it's important to lift any constraints left over from the previous attempt to parse material which is part of or subsequent to the token whose match attempt has been abandoned.

Matching Literal Text.

Here we attempt to make a match of the substring of the text mtxt which runs from character mfrom to character mto, looking for it at the given position ipos in the source text txt.

Matching Character Range.

Suppose that a character range is stored in ftxt between the character positions rf and rt. Then TEXT_TY_RE_Range(ch, ftxt, rf, rt, negate, insens) tests whether a given character ch lies within that character range, negating the outcome if negate is set, and performing comparisons case insensitively if insens is set.

Search And Replace.

And finally, last but not least: the routine which searches an indexed text txt trying to match it against ftxt. If ftxtype is set to REGEXP_BLOB then ftxt is expected to be a regular expression such as ab+(c*de)?, whereas if ftxtype is CHR_BLOB then it is expected only to be a simple string of characters taken literally, such as frog.

Each match found is replaced with the contents of rtxt, except that if the blob type is REGEXP_BLOB then we recognise a few syntaxes as special: for instance, \2 expands to the value of subexpression 2 as it was matched – see Writing with Inform for details.

The optional argument insens is a flag which, if set, causes the matching to be done case insensitively; the optional argument exactly, if set, causes the matching to work only if the entire txt is matched. (This is not especially useful with regular expressions, because the effect can equally be achieved by turning ab+c, say, into ^ab+c$, but it is indeed useful where the blob type is CHR_BLOB.)

For an explanation of the use of the word "blob", see Text.i6t.

Concatenation.

See the corresponding routine in Text.i6t: this is a variation which handles the special syntaxes used in search-and-replace.