scScript Pattern Performance

The Pat being matched will have a big impact on the efficiency of the match operation. A simple search for the word "Hello" can be done with: Pat.Match(BN, "Hello");

While not a Pat per se, a string is the simplest pattern there is. So this trivial match call will default to #Once mode and quickly search from the beginning of BN for "Hello".

But one can also use a slightly more complex self-scanning Pat: PScan = Pat.Rep(0, 0, Pat.Char(Pat.#All)); // Will match anything! PHello = Pat.Seq(PScan, "Hello"); Pat.Match(BN, PHello, Pat.#Anchor);

PHello will match any sequence of characters that ends in "Hello"! In that sense, this Pat will itself scan down the buffer within a single match. So using #Once mode (instead of #Anchor) with such a Pat would be extremely wasteful if there is no match. In that case, Match would start at pos 0, search the entire buffer for "Hello", then move over to pos 1, and repeat the process, again and again. If BN has a modest 10K of data, #Once will look for "Hello" more than 50 million times.

A simpler version of Pat.Char(Pat.#All) is Pat.Any() (Of course, Pat.Go(1) is also an option). Pat.Any() was a relatively late addition, as the need for efficiently searching over all chars became apparent only with use. So perhaps
   PScan = Pat.Rep(0, 0, Pat.Any());
is an improvement.

Interestingly, PHello works almost as fast as the direct Match of "Hello". Matching in #Anchor mode, PHello will do the scanning and Pat.Match will succeed immediately when PHello strikes. But Pats do a lot of internal work in addition to string matching (stashing data, handling callbacks, etc.) so the direct (string) Match of "Hello" will always be faster!

Most Pats, like simple strings, either match or not depending on their contents, they have no say or leeway in how they operate. But some do have latitude in how and what they match. For example, given repeating data, Rep can decide, on its own, how many times to repeat!

There are two theoretical dimensions for Pats that enjoy matching latitude:

1. Greediness: How many strings, characters, iterations? (#Min or #Max)
2. Kindness: Selfish or considerate of subsequent Pats? (#Self or #Cons)

Matched on its own, the simple PScan Rep (from above) will immediately succeed on any text in the buffer. The Pat.Any component will match any char, but worse Pat.Rep will always match with 0 reps! In fact, a Pat of the form: (assuming it is not part of another Pat and not being considerate) Pat.Rep(0, 0, "xyz")
will instantly match with 0 reps! (scScript issues a warning for such a Pat.)

Pat.Rep defaults to #Min (minimalist) behavior. If its Min parameter is 0, as in this case, it simply declares itself successful and stops without matching anything! But if given a Min greater than 0, it will actually try to match repeatedly until the Min is satisfied. The #Max (Maximalist) flag changes all that, it makes Pat.Rep greedy. It will continue to iterate even after a successful match, again and again, until the repetition count equals its Max parameter (0 here means there is no Max limit) or it runs out of data (buffer) to match. So the maximalist Rep will succeed with the highest rep count it can, between its Min and Max limits, inclusively.

A minimalist PScan (as written) PScan = Pat.Rep(0, 0, Pat.Any());
if Matched on its own, will succeed immediately without eating any chars. A maximalist version: PMaxScan = Pat.Rep(0, 0, Pat.#Max, Pat.Any());
if matched on its own, will eat every last char in the buffer. If stashing #S_Cnt, the Rep would therefore store the char count for the whole buffer. #Max mode is clearly slower than #Min, as the Pat will keep going, even after a match succeeds! (SampleSC/Pat2.sc will have these examples.)

Pats with operating latitude generally default to selfish (#Self) but can also be considerate (#Cons), the default case for Rep. A selfish Pat only cares about itself, whether greedy or not, it seeks to match on its own and be done. A selfish version of the example above, PScanS, whether #Min or #Max, will fail (with one exception)! PScanS = Pat.Rep(0, 0, Pat.#Self, Pat.Any()); PHelloS = Pat.Seq(PScanS, "Hello");

A minimalist PScanS will eat no chars, so PHelloS will fail unless the buffer starts with "Hello". Worse, a maximalist PScanS will eat all chars, so PHelloS fails with nothing left to match!

A #Cons Pat, unlike the #Self variant, is a team player. It will look to subsequent Pats and succeeds only if they too can succeed. So it does a preliminary match, then checks with every subsequent Pat in the Match hierarchy (in this case PHelloS) to verify they too can be satisfied! This takes a lot of processing, but scScript has clever optimizations to avoid duplicate checks. (Yes, nasty complex code!)

The considerate (original) PScan in PHello will only eat until it reaches "Hello". Such a minimalist and considerate PScan will go until the first "Hello", but if PScan was maximalist, it would look past the first match, and eat until the very last "Hello"! In most cases #Cons slows down the match, but is semantically required. However, #Max and #Cons together are often a semantic error.

Pattern matchers have historically differentiated between lazy and greedy for iteration. But the traditional categorization defined greedy as maximalist and selfish, with lazy being minimalist and considerate. So lazy traditional patterns would often do more work than their greedy counterparts!

The most important rules of thumb:

• Rep (defaults to #Cons and #Min)
  • Make it #Self when possible (usually #Self and #Max).
  • Make it #Max if required,
  • Avoid #Cons and #Max together!
  • NEVER Rep with only #Neg Pats (It will loop forever)!!
  
  
• Span (defaults to #Self and #Min)
  • Make it #Cons if necessary.
  • Make it #Max if required.
  • But avoid #Cons and #Max together!
  
  
• Alt (defaults to #Self)
  • Sometimes needs #Cons.
  
  
• Avoid 2 or more sequenced #Cons Pats, unless absolutely necessary.

It is best to make everything #Self unless #Cons are necessary. #Cons and #Max together is usually a mistake while multiple #Cons Pats will require huge resources (memory and time) to match.

Rep Pats default to #Cons because they are often used as fillers where the container Pat specifies the end point. But Span specifies its own beginning and end patterns, so it defaults to #Self. Alt will also default to #Self as it is just a disjunctive version of Seq, so usually seeks to affirmatively match its own template. The big picture is easy to remember: everything is #Min and #Self, only Rep is #Cons.

A Pat of the form Pat.Rep(0, 0, Pat.#Neg, AnyPat) will generally not work! Rep must advance from one char to the next, but a failing AnyPat will not advance. So the Pat will loop forever!

One solution is Pat.Rep(0, 0, Pat.#Neg, AnyPat, Pat.#Pos, Pat.Go(1)). Here Go(1) will force an advance and avoid the infinite loop. (An automatic aid might help here, but would cause problems and complications in other cases; best to stick with the simplest paradigm.)