Misty Programming Language:Patterns

Regular expressions have been used with great success in text editing and casual searching tools. They are an easy way of describing and matching patterns in texts. Regular expressions have infiltrated programming languages, becoming standard features in Perl and JavaScript. The regular expression notation itself has continued to grow past the point of regularity.

One of the critical activities in secure programming is input validation. Regular expressions are poorly suited to validation because the notation is so cryptic. If the validation rules are too confusing to read, how can we have confidence that they are correct?

As an alternative, the Misty Programming Language has patterns. A pattern is a special kind of object that can be used to match patterns in texts. Patterns are less terse than regular expressions, and much easier to read and write.

A pattern literal, written as pattern followed by a pattern group, produces an immutable pattern object.

An Example

We want to extract information from a url text. We define a lib library record containing two patterns (ip4 and name) and a url pattern that uses the lib. The word pattern introduces a pattern, much as function introduces a function.

def lib: {
    ip4: pattern {4 {"octet": 1-3 digit / "."}}
    name: pattern {1- [letter digit "_-%"]}
}
def url: pattern (lib) {
    - {"scheme": name ":"}
    "slash": 0-3 "/"
    "host":  {ip4 | 1- {name / "."}}
    - {":" "port": 1-5 digit}
    - {"/" "path": 0- [/ "?#" Cc]}
    - {"?" "query": 0- [/ "#" Cc]}
    - {"#" "hash": 0- char}
}

We can use the extract function to match a pattern against a text.

var result: extract("http://www.mistysystem.com/index.html#top" url)

The result is a record containing

{
    hash: "top"
    host: "www.mistysystem.com"
    path: "index.html"
    scheme: "http"
    slash: "//"
}

We can call extract again with a different text:

assign result: extract("216.168.224.111:9997?clearance=top" url)

The result is a record containing

{
    host: "216.168.224.111"
    octet: ["216" "168" "224" "111"]
    port: "9997"
    query: "clearance=top"
    slash: ""
}

To contrast, this is a JavaScript regular expression that does a similar thing:

/^(?:([A-Za-z\-_%0-9]+):)?(\/{0,3})([A-Za-z\-_%0-9]+(?:\.[A-Za-z\-_%0-9]+)*)(?:\:(\d+))?
(?:\/([^?#]*))?(?:\?([^#]*))?(?:#(.*))?$/

The regular expression is much more compact than the pattern, but it is also much harder to understand.

Let's take the pattern apart. First, we had a library pattern for matching a dotted IP address:

ip4: pattern {4 {"octet": 1-3 digit / "."}}

It matches exactly four groups of one to three digits separated by .period. Each group of digits is stored in the result under the name octet. So

extract("198.137.240.92" lib.ip4)
    # {octet: ["198" "137" "240" "92"]}

The /slash operator allows us to specify a separator. The pattern could be written without the /slash operator but the pattern would be longer.

ip4: pattern {"octet": 1-3 digit 3 {"." octet: 1-3 digit}}

If we attached the name octet: on an outer level

ip4: pattern {"octet": 4 {1-3 digit / "."}}

then the result would have been

    # {octet: "198.137.240.92"}

The second pattern matches a name.

name: pattern {1- [letter digit "_-%"]}

The definition of name in this case is pretty loose: any combination of letters, digits, and the characters _underbar, -minus sign, and %percent sign, but not .period.

The url pattern matches urls. It matches in seven steps.

1. It optionally matches a name followed by a :colon. If they match, the name is saved in the result record in the scheme field. A prefix of -minus sign means the same as 0-1. The item can occur once or not at all; it is optional.

   - {"scheme": name ":"}

   If it had been written as

   - {"scheme": {name ":"}}

   then the :colon would be saved as well as the name.
2. It matches between 0 and 3 slash characters and saves them under the name slash.

   "slash": 0-3 "/"

3. It matches a host name or address. This component is not optional. It is saved under the name host. First we attempt to match using the ip4 pattern we defined earlier. If that does not match, then we'll match a dotted domain name (one or more names separated by dots).

   "host": {ip4 | 1- {name / "."}}

4. It optionally matches a port number. If it is found, it is saved under the name port.

   - {":" "port": 1-5 digit}

5. It optionally matches a path. The path can contain any sequence of characters except control characters and "?" and "#". We are reserving "?" and "#" for the last two options. If a path is found, it is saved under the name path.

   - {"/" "path": 0- [/ "?#" Cc]}

6. It optionally matches a query text. The query text can contain any sequence of characters except control characters and "#". We are saving "#" for the final option. If a query text is found, it is saved under the name query.

   - {"?" "query": 0- [/ "#" Cc]}

7. It optionally matches a hash (or anchor name). If it is found, it is saved under the name hash.

   - {"#" "hash": 0- char}

Patterns are made of the same tokens as the rest of the Misty Programming Language. That has benefits for development tools. Features like paren balancing are not imperiled by the mixing of language conventions. Patterns can contain comments, just as functions can.

The pattern? function can be used to sense patterns.

pattern?(url)       # true
pattern?(lib)       # false
pattern?(lib.ip4)   # true
pattern?("pattern") # false
stone?(url)         # true
record?(url)        # false

Pattern Library

A pattern library is a record containing patterns that can be used by other patterns. The lib record in the first example is a pattern library.

A pattern library can contain patterns, texts, and arrays.

When an ordinary text is used as a pattern, it matches identical text.

When an ordinary array of texts is used as a pattern, it is used as a group of alternatives, trying the texts in order until there is a match.

Pattern Literal

pattern_literal "pattern" space optional_pattern_library pattern_group

optional_pattern_library "" '(' pattern_library_list ')' space

pattern_library_list indent expression pattern_library_list_open outdent expression pattern_library_list_closed

pattern_library_list_open "" linebreak expression pattern_library_list_open

pattern_library_list_closed "" space expression pattern_library_list_closed

A pattern literal is pattern optionally followed by one or more pattern libraries wrapped in ( )parens, followed by a pattern group wrapped in { }braces. Patterns may not be created in a function that has a variable in scope named pattern.

Item

pattern_element pattern_group pattern_class pattern_text name

pattern_item pattern_element pattern_depot pattern_element pattern_quantifier pattern_element pattern_depot pattern_quantifier pattern_element

A pattern element is a group of items wrapped in braces, or a character class wrapped in brackets, or literal text, or a name.

A pattern item is an element with an optional depot or quantifier, or both.

Depot

pattern_depot text_literal ':' space name ':' space

Patterns can be used to extract information from texts. The extract function returns a record containing the saved matching material.

To save material, place a text or a name and a :colon immediately before a pattern element or quantifier. The text that is matched is saved in the result record, using the text or name as the key. If multiple matches are made (because of repetition or multiple uses of the same text), then all of the matches are saved in an array under the text or name.

Quantifier

pattern_quantifier '-' space number_literal '-' number_literal space number_literal '-' space number_literal space

By default an element matches exactly once.

element

Any pattern element can be preceded by a repetition factor. It determines the number of times the element matches.

5 element

A range can be specified with two numbers separated by -minus. The element will match no fewer than the first number, and no more than the second number.

1-5 element

If the second number is omitted, then there is no limit to how many times the element can be matched.

1- element

An optional element is indicated by a prefix of -minus sign. This indicates that the item may match zero or one time.

- element

If the element matches emptiness, then the repetition count is satisfied, even if the minimum number of repetitions has not been reached yet.

Group

pattern_group '{' indent pattern_item more_open_pattern_group outdent '}' '{' pattern_item more_closed_pattern_group '}'

more_open_pattern_group "" linebreak pattern_item more_open_pattern_group linebreak '|' space pattern_item more_open_pattern_group linebreak '/' space pattern_item

more_closed_pattern_group "" space pattern_item more_closed_pattern_group space '|' space pattern_item more_closed_pattern_group space '/' space pattern_item

A pattern group is wrapped in { }braces. A group matches if all of the pattern items in it match. In the open form, every item is followed by a line break.

A group may contain alterative sequences of items. Alternatives are separated by |vertical bar. A group of alternatives matches if any one of the alternatives matches.

Optionally, an item after a /slash indicates a separator that appears before all but the first repetition. This is used only if the maximum number of repetitions is at least 2.

Text literal

pattern_text text_literal '*' space text_literal

A text in quotes matches characters in the text. Normally in Misty, text comparisons are case sensitive. In patterns, text comparison is also case sensitive, except when a text is preceded by *asterisk which allows lowercase letters to match uppercase letters.

"vorpal" matches "vorpal"

* "vorpal" matches "vorpal" and "Vorpal" and "VorPal" and "VORPAL"

* "Vorpal" matches "Vorpal" and "VorPal" and "VORPAL" but not "vorpal"

Name

A name can refer to one of the system-supplied names. These include ascii, char, digit, end, hex, letter, lower, space, upper as well as the two-character Unicode General Categories. The Unicode General Categories are only available in character classes.

A name can refer to a user-defined pattern in a library. This allows the breaking of a complex pattern into simpler subpatterns. It also allows for the recognition of context-free languages.

A name can refer to a user-defined text in a library.

A name matches if the thing it represents matches.

Character class

pattern_class '[' pattern_set ']'

pattern_set "" name optional_pattern_set pattern_text_range optional_pattern_set '/' optional_pattern_set

optional_pattern_set "" space pattern_set

pattern_text_range text_literal pattern_text_extent

pattern_text_extent "" space '-' space pattern_text_range

A character class specification is wrapped in brackets. A set is a sequence of zero or more names or texts, and contains the union of those characters.

[letter digit]   # matches any letter or digit.

Name

A name can refer to one of the built-in character classes, or to a library text, character class, or function.

Literal text

A text contains characters in the class. You can have one big text or lots of little texts.

Range

If there is a -minus sign between two texts, then an inclusive range is made from the last character of the first text thru the first character of the second text.

["0" - "9"] matches a digit, as does ["0123456789"].

Anticlass

The /slash signals characters to be excluded from the class.

["a" - "z" / "aeiou"]    # matches a lower case consonant.

[/ digit]                # matches any character that is not a digit.

A second /slash signals an intersection operation on the current set.

[ascii / / upper]        # matches upper case ASCII letters.

Pattern Functions

Patterns can be used with some of the intrinsic functions.

array(text pattern)
extract(text pattern from to)
match(text pattern)
replace(text pattern replacement limit)
search(text pattern from)

For example, the array() function can be used to break the contents of a file into an array of texts. If the separator pattern is found in the text, then the subtext before the match is stored in the new array, and the match is repeated on the remainder until no more matches are possible. The remainder of the text is stored in the array and the array is returned.

var lines: array(contents pattern {end})

This will break on linefeed, carriage_return, and carriage_return linefeed.