scScript Pattern Debugging
Pats are inherently recursive (tree) structures, as each Pat may include one or more other Pat/Str. Matching therefore requires a depth-first traversal of the Pat tree to compare terminal nodes (strings and chars) to data in the given buffer. In that sense, there is always an order to Pat elements, there are preceding Pats and subsequent Pats to compare. #Cons adds an extra dimension to this recursion, as a given match is placed on hold, while subsequent Pats are visited and verified.
All this recursion in two dimensions can be quite expensive, both in memory usage
and processing time. scScript uses a more efficient and manageable iterative process
instead, where automata theory guarantees the conversion at the cost of an explicit control
stack. So scScript uses an MStack of match steps to control its
iterative process. There is also an RStack to store results for RFunc
invocation without backtracking. But the combination is quite complex and all but
incomprehensible without specialized printouts.
scScript provides compile-time #define macros to turn on/off pattern matching
information displays. The SC_DEBUG_DISP_MATCH macro, if set to 1,
will print out a trace of the matching steps to stdout (either the debugger or
the terminal, not *Output*). This is normally turned off as such output will
drastically slow down operations. A sample match display is shown below:
...
Match Succeeded... Steps:590 Recursions:2
Begin Matching... From:75
Pat:Alt From:75
| Pat:Seq From:75
| Pat:Seq From:75
| | Pat:Rep From:77
| | | Pat:Alt From:77
| | | | Pat:Char From:77
| | | Pat:Alt From:78
| | | | Pat:Char From:78
| | | | Pat:Rep From:78
...
| | | | | Pat:Char From:108
| | | | | Pat:Char From:109
| | | | | Pat:Char From:110
| | | | | Pat:Char From:111
Match Succeeded... Steps:228 Recursions:2
Begin Matching... From:112
Pat:Alt From:112
| Pat:Seq From:112
| Pat:Seq From:112
| | Pat:Rep From:114
| | | Pat:Alt From:114
...
These (often voluminous) displays are hard to read if there are many sub-parts with the
same Pat type. So #S_Name (attachment) directives are provided
to name individual Pats, making debugging display references, as shown below, easy to
disambiguate:
...
Match Succeeded... Steps:590 Recursions:2
Begin Matching... From:75
Pat:Alt "Cnt" From:75
| Pat:Seq "DStr" From:75
| Pat:Seq "LCom" From:75
| | Pat:Rep "ComW" From:77
| | | Pat:Alt From:77
| | | | Pat:Char From:77
| | | Pat:Alt From:78
| | | | Pat:Char From:78
| | | | Pat:Rep "Word" From:78
...
| | | | | Pat:Char From:108
| | | | | Pat:Char From:109
| | | | | Pat:Char From:110
| | | | | Pat:Char From:111
Match Succeeded... Steps:228 Recursions:2
Begin Matching... From:112
Pat:Alt "Cnt" From:112
| Pat:Seq "DStr" From:112
| Pat:Seq "LCom" From:112
| | Pat:Rep "ComW" From:114
| | | Pat:Alt From:114
...
The display below is produced when SC_DEBUG_DISP_MSTACK is set
to 1, it shows MStack contents at every step. The exact
details are available in scScript source files, but each entry corresponds to a Pat. The
number shows the stage being evaluated and the final -> indicates the target
position in the buffer. In this example, "Cnt" is an Alt pattern, with its
entries numbered 1 through 5. It starts by looking at Pos
75 of the buffer. Stage 0 is generally the initial setup phase for
every Pat. Stage 3 of "Cnt", therefore refers to checking its 3rd
entry, the "DStr" Seq pattern. This, in turn quickly fails when its very first
entry does not match in step 00005. But apparently
the 4th alternative in "Cnt" matches in step
00009 and launches a #Cons check in step 00010.
...
1>MStack(Res:1)... Steps:590 Levels:2
1>Starting Match at 75...
00001 L01: ["Cnt"*0]->75
00002 L01: ["Cnt"*1]->75
00003 L01: ["Cnt"*2]->75
00004 L01: ["Cnt"*3]["DStr"*0]->75
00005 L01: ["Cnt"*3]["DStr"*1]->75 ***** FAIL
00006 L01: ["Cnt"*3]->75
00007 L01: ["Cnt"*4]["LCom"*0]->75
00008 L01: ["Cnt"*4]["LCom"*1]->77
00009 L01: ["Cnt"*4]["LCom"*1]["ComW":0]->77
00010 L02: ["Cnt"*4]["LCom"*1]["ComW"*0][C:1->1]->77
00011 L02: ["Cnt"*4]["LCom":1]["ComW"*0][C:1->0]["LCom"*2|1]->77
00012 L02: ["Cnt"*4]["LCom":1]["ComW"*0][C:1->0]["LCom"*3|1]->77 ***** FAIL
00013 L01: ["Cnt"*4]["LCom"*1]["ComW"*0]->77
00014 L01: ["Cnt"*4]["LCom"*1]["ComW"*1][Alt*0]->77
00015 L01: ["Cnt"*4]["LCom"*1]["ComW"*1][Alt*1][Char*32]->78
00016 L01: ["Cnt"*4]["LCom"*1]["ComW"*1][Alt*1]->78
00017 L01: ["Cnt"*4]["LCom"*1]["ComW"*1]->78
00018 L02: ["Cnt"*4]["LCom"*1]["ComW"*1][C:1->1]->78
00019 L02: ["Cnt"*4]["LCom":1]["ComW"*1][C:1->0]["LCom"*2|1]->78
00020 L02: ["Cnt"*4]["LCom":1]["ComW"*1][C:1->0]["LCom"*3|1]->78 ***** FAIL
...
[C:1->1] on the MStack indicates a #Cons check has been
initiated. The first 1 indicates the cons level, more useful when there
are 17 levels and the display wraps around many times. The
second 1 indicates which MStack record to check next
(0-based with -1 meaning it is done). Using the iterative
MStack-controlled algorithm, #Cons checks proceed backwards by re-visiting (and
advancing) previous steps. So the next step is to re-visit and advance
entry 1, therefore to check the 2nd stage
of "LCom".
There are quite a few symbols in these notations and they each convey their own subtle
information about the Matching algorithm. For example, step 00011 has two
"LCom" entries on the MStack, the first now uses a colon
while the second has the more common asterix. This has to do with how
the MStack is back-traversed to generate RStack entries when the
match succeeds. The MStack entry with the asterix will set
the RStack results, while the one(s) with the colon should be ignored on the
reverse traversal (as they have been superseded) for this purpose. This is an optimization
in the matching algorithm, there is no need to repeat a match that has already been done as
part of #Cons deliberations!
Importantly, each match may take very many steps and nested #Cons checks can quickly become
quite inefficient and confusing. It is not hard to write a match that pushes 50 or more
entries on the MStack. To aid legibility (and avoid wrap-arounds), the system
will write out the full MStack only on every 5th step, displaying just the last
row for the other 4.
The time it takes to match and the number of steps involved (shown as a 5-digit counter
above) is generally proportional to the size of the data buffer being matched. This is
entirely expected and makes good sense as going through 100K of
data should take longer than 10K. The complexity of the Pat will
obviously have a similar impact, as each individual match, whether hit or miss, would
require more steps. One would also expect to have more items on the MStack at
a given time (horizontal span on the display above) for more complex patterns.
Nevertheless, memory requirements should remain generally fixed for a given pattern,
regardless of the data size it scans over.
Unfortunately nested #Cons have an exponential impact on memory requirements (average
MStack depth) as well as processing time. Worse, nested #Cons could yield an
MStack peak depth proportional to the data size! This is a problem, as the
system will fail on larger data sets.
The following (highly) contrived example illustrates the point: (Alt will always
treat its last entry as #Self, the source code had to be changed for this example to
remove this optimization.)
AnyC = Pat.Alt(Pat.#Cons, |>\"<|, Pat.Any());
EatStr = Pat.Rep(0, 0, AnyC);
DStr = Pat.Seq(|>"<|, EatStr, |>"<|);
Pat.Match(BN, DStr, Pat.#Once);
For this example, assume BN contains a total of only 8 data characters:
<space>"Test"<newline>
The above match would result in the following (abbreviated) MStack trace:
1>Starting Match at 0...
00001 L01: [Seq*0]->0
00002 L01: [Seq*1]->0 ***** FAIL
1>MStack(Res:0)... Steps:2 Levels:1
1>Starting Match at 1...
00001 L01: [Seq*0]->1
00002 L01: [Seq*1]->2
00003 L01: [Seq*1][Rep:0]->2
00004 L02: [Seq*1][Rep*0][C:1->0]->2
00005 L02: [Seq:1][Rep*0][C:1->-1][Seq*2|0]->2
00006 L02: [Seq:1][Rep*0][C:1->-1][Seq*3|0]->2 ***** FAIL
00007 L01: [Seq*1][Rep*0]->2
00008 L01: [Seq*1][Rep*1][Alt*0]->2
00009 L01: [Seq*1][Rep*1][Alt*1]->2
00010 L01: [Seq*1][Rep*1][Alt*2][Any*1]->3
00011 L01: [Seq*1][Rep*1][Alt*2]->3
00012 L02: [Seq*1][Rep*1][Alt:2][C:1->1]->3
...
00040 L04: [Seq*1][Rep:1][Alt:2][C:1->0][Rep:2|1][Alt:2][C:2->0][Rep:3|1][Alt:2][C:3->0]
[Rep*4|1][Alt*2][Any*1]->6
00041 L04: [+5..][Alt:2][C:2->0][Rep:3|1][Alt:2][C:3->0][Rep*4|1][Alt*2]->6
00042 L05: [+6..][C:2->0][Rep:3|1][Alt:2][C:3->0][Rep*4|1][Alt:2][C:4->10]->6
00043 L05: [+7..][Rep:3|1][Alt:2][C:3->0][Rep:4|1][Alt:2][C:4->0][Rep*4|1]->6
00044 L06: [+8..][Alt:2][C:3->0][Rep:4|1][Alt:2][C:4->0][Rep*4|1][C:5->0]->6
00045 L06: [Seq:1][Rep:1][Alt:2][C:1->0][Rep:2|1][Alt:2][C:2->0][Rep:3|1][Alt:2][C:3->0]
[Rep:4|1][Alt:2][C:4->0][Rep*4|1][C:5->-1][Seq*2|0]->6
00046 L06: [+9..][C:3->0][Rep:4|1][Alt:2][C:4->0][Rep*4|1][C:5->-1][Seq*3|0]->7
1>MStack(Res:1)... Steps:46 Levels:6
Where MStack usage peaks at 16 entries, all to match 4 characters
(Interestingly, the normal #Self version still requires 42 steps, but only
4 MStack entries). Doubling the data to 8 characters requires an acceptable 86
steps instead of the previous 46. But the MStack would peak at 28 entries!
Matching 16 characters will need 188 steps and 52 MStack entries while 32
characters requires 326 steps and 100 entries. By extension, a modest 16K of data would
need 48K MStack entries, each 64 bytes! (3 MB of stack memory seems huge to us
older folks who started with 4k of RAM on 8-bit processors!)
Alas, there are no obvious shortcuts or heuristics to reduce the burden of combined #Cons. Each #Cons level provides a fork in the search tree of matches and one cannot be eliminated without wiping out possible solutions.