Synopsis
========

The treexpr library is a Free Software library that applies regular expression concepts to tree structures. It it written in C and has a JNI binding to Java.

Primer
======

Syntax
------

    Expr   ::= Term | Expr "|" Term
    Term   ::= Factor | Term Factor
    Factor ::= Symbol | Symbol "*" | "~" | "(" Expr ")" | "(" Expr ")" "*"
               | Symbol "->" Expr | Symbol ":" String | Symbol Attrs | Symbol Attrs "->" Expr
    Attrs  ::= "<" Attr* ">"
    Attr   ::= Symbol | Symbol "=" String
    Symbol ::= any alphanumeric string with '_' and '-'
    String ::= quoted string (skips over \")

Semantics
---------

A tree can be thought of as a hierarchical list, each element of the list can have a list of
children. Consider the following tree:

        html
        /   \
     head   body
      /      / \
    title   h1  p 

    root list: html
    list of html's children: head body
    list of head's children: title
    list of body's children: h1 p
    list of h1's chlidren: ~ (where ~ denotes the empty list)
    list of p's children: ~

By the same token, a tree expression can be thought of as a hierarchical regular expression,
each symbol in the expression can have a child expression. The `->` operator binds a child
expression to a symbol in the parent expression. If a symbol has no child expression it is
equivalent to having a child expression that matches everything. In other words the children
of a symbol are ignored if there is no child expression. It can also be said that `->` adds
a restriction to the symbol on it's left-hand side: the symbol will only be matched if the
symbol's children match the child expression. Other restriction operators are discussed later to
improve matching of HTML. Consider the following expressions:

These match the tree above:

    html                        - matches the root list and ignores html's children
    html -> head body           - also matches html's children and ignores head and body's children
    html -> (head -> title) body        - also matches head's children and ignores title's children
    html -> (head -> title -> ~) body   - also matches title's children
    html -> (head -> title -> ~) (body -> h1 p)                 - also matches body's children
    html -> (head -> title -> ~) (body -> (h1 -> ~) (p -> ~))   - matches the tree exactly

These do not match the tree above:

    body                - does not match root list
    html -> body        - matches root list but does not match html's children (must match all)
    html -> body head   - matches root list but html's children are out of order

Note the grouping around `->`. In the second expression `->` binds the symbol `html` to the
expression `head body`. In the third expression we want the symbol `head` to be bound to the
expression `title` and not `title body` so we must group them together using parenthesis.

Tree expressions use the alternation `|` and closure `*` operators from reqular expressions.
Consider the following expressions:

    html*       - matches the root list because it consists of zero or more "html" symbols
    html | xml  - matches the root list because it consists of "html" or "xml"
    html -> (head -> title | title meta) body   - matches

In addition to the `~` special symbol there is `.` which matches any symbol:

    html -> .*          - matches the root list and html's children because html has zero or more
    html -> .* (body -> .* p .*) .*             - matches a tree that has "html" at the root, html has
                                                  atleast one child named "body", and body has atleast
                                                  one child named "p".

Extra matching operators for HTML
---------------------------------

The `:` operator binds a regular expression to a symbol, the symbol matches only if its
contents matches the regular expression. In HTML the only tags that have contents are `text`
and `comment`. So most of the time it will be used like:

    p -> text:"ab*c"    - matches the HTML '<p>abbbbbc</p>'

The `<`, `=`, and `>` operators are used together to bind a symbol to an attribute list,
the symbol matches only if every attribute matches an attribute of the HTML tag. An attribute
restriction is a list of name and value pairs. A name without a value is matched only if it
appears in the HTML without a value. Consider the following:

    table <bgcolor="blue">      - matches the HTML '<table bgcolor="blue">'
                                  and also the HTML '<table bgcolor="blue" border="1">'
    foo <bar>                   - matches the HTML '<foo bar>' but not '<foo bar="">' or '<foo bar="baz">'
    foo <bar> | foo <bar=".*">  - matches all three

It is possible to combine the attribute restriction operators with the `->` operator (for example
`option <selected> -> text:"blue"`), but it is not possible to combine the content restriction
operator with the `->` operator (for example `text:"blue" -> br`) because `text` and `comment`
symbols never have children.

Extracting values from an HTML page
-----------------------------------

This section has been up for debate because it can be very confusing. The way we extract strings
from the tree expressions is from the contents and attribute rescrictions. These restrictions
contain regular expressions that match against some of the data contained in an HTML page. Most
regular expression libraries allow you to use something called back references where each
parenthasized sub-expression is given a number and the string matching that sub-expression can be
referenced later. For example the expression "foo" has no sub-expressions, the expression `fo(o*)`
has one sub-expression, namely `o*`. When `fo(o*)` is matched against "fooo", the fist
sub-expression references the string "oo". The sub-expressions are numbered by the position of
their open parenthesis. For example `(b(a)(r))` has three sub-expressions, 1. `b(a)(r)` 2. `a`
3. `r`. If a sub-expression matches multiple strings then the last match is what is referenced.
For example `(ab|ac)*` matches "ababac" and the string referenced will be "ac".

A tree expression can have several regular expressions embedded in it. In order to find a specific
sub-expression they are numbered in the order they appear in the tree expression. For example:

        form -> input<value="([0-9]+)"> text:"."
                input<value="([0-9]+)"> text:"."
                input<value="([0-9]+)"> text:"."
                input<value="([0-9]+)"> input

has four sub-expressions. This tree expression would match against an HTML form that might be used
for changing an IP address:

    <form method="POST" action="/cgi-bin/setip">
        <input type="text" name="first" value="192"> .
        <input type="text" name="second" value="168"> .
        <input type="text" name="third" value="1"> .
        <input type="text" name="fourth" value="42"> <input type="submit" value="Set IP">
    </form>

In this case the extracted values will be:

1. "192"
2. "168"
3. "1"
4. "42"

It's simple to specify a method for combining the strings together to form a usefull output.
For example something like `\1.\2.\3.\4` would produce "192.168.1.42".

Example Program
---------------

    /* Example program to output all 1st headings in an HTML document */
    /* NB: please tell me if this works, I haven't tested it */
    #include <stdio.h>
    #include <treexpr.h>
    #include <libxml/HTMLtree.h>
    #include <libxml/HTMLparser.h>
    
    int main( int argc, char **argv )
    {
        const char *expr = "h1 -> text:\"(.*)\""; /* Expression to match */
        struct machine *m; /* Pointer to compiled expression */
        htmlDocPtr doc; /* Pointer to HTML document */
        const char *end; /* end of expression parsed */
        int error = 0; /* return code of main */
        struct match *z; /* matches returned by document_process */
    
        /* Check command line options */
        if( argc != 2 )
        {
                printf( "USAGE: %s <url>\n", argv[0] );
                return -1;
        }
    
        /* Parse expression, a pointer to the compiled expression is stored at m */
        end = parse_treexpr( expr, &m );
        if( end == NULL )
        {
                printf( "Error parsing expression near: %s\n", m->buf );
                printf( "Details: %s\n", m->error );
                error = -1;
                goto free_m;
        }
    
        /* Load HTML document from a URL */
        doc = htmlReadFile( arg[1], NULL, PARSER_OPTIONS );
        if( doc == NULL )
        {
                printf( "Error reading document: %s\n", arg[1] );
                error = -1;
                goto free_m;
        }
    
        /* Search for any matches of the expression */
        z = document_process( m, doc );
    
        /* Loop through linked list of matches */
        while( z != NULL )
        {
                struct regex_match *re = z->re; /* First subexpression */
                int i;
    
                puts( "Heading: " );
                for( i = re->match.rm_so; i < re->match.rm_eo; i++ )
                        putchar( re->str[i] );
                putchar( '\n' );
                z = z->next; /* Consider next match in list */
        }
    
        /* Free memory allocated by document_process */
        free_matches( z );
    
        /* Free memory and return */
        xmlFreeDoc( doc );
    free_m:
        free_machine( m );
        return error;
    }

TODO
====

* Autotoolize build
* Include a better C example program, possibly a make test
* Write lots of example expressions, maybe even a CGI interface for people to play with
* Clean up namespace
* Use SourceForge tasks instead of this list
* Rearrange code, make it usefull for more than just HTML documents
* Add Python bindings