[RFC]: Pattern matching & corellation ideas

5 Sep 2012

      In the past few months, I talked a lot about patterndb and related
things with colleagues - during coffee break, over a beer, etc -, and
last night, I got as far as drafting a proof of concept tool that
realizes some of the ideas we've had. Some of these might have been
discussed on this list too, in the past, I really can't remember all the
influences I'm afraid.

Anyway! I like the concept of patterndb, but I absolutely hate XML. It's
not a natural format for describing how to match patterns, and what to
do with them. Not for me, anyway. I'd like something that is much closer
to how I normally think, something that feels more like a programming
language, a domain specific one, engineered for this task only, but
still somewhat familiar. I also want it to be fast.

For a long time, I also wanted to play with developing both a Domain
Specific Language (DSL for short) and a compiler, but never had the
opportunity. Pattern matching is one now!

How about a small language, that we'd compile down to C, automatically
add some boilerplate, and we'd get a syslog-ng parser plugin in return?
That would mean the language is fairly easy to extend, it produces
native code, which will hopefully run as fast - if not faster - than
patterndb, and we skip the entire XML pile too!

To demonstrate, this is what I've been thinking of:

,----
| (cond :message
|   (match "foo (bar) ([:number:])")
|     (do
|       (set! :bar "$1")
|       (set! :stuff "$2")
|       (conj! :tags "test stuff")))
|
| (deftest message-match
|   "this is a foo bar 1234 message!"
|
|   (== :bar "bar")
|   (== :stuff "1234")
|   (contains? :tags "test stuff"))
`----

This would compile down to roughly the following C code (with the test
excluded, for now):

,----
| gboolean
| m_something(LogMsg *message, GString *subject)
| {
|   GString *m1; /* ([:number:]) */
|
|   /* The subject must be at least as long as the static strings in the
|   pattern, if it's shorter, we don't match */
|   if (subject->len < 8)
|     return FALSE;
|
|   /* If we don't find part of the pattern, bail out. */
|   if (strncmp(subject->str, "foo bar ") != 0)
|     return FALSE;
|
|   if (!find_number(subject->str + 8, &m1))
|     return FALSE;
|
|   /* The whole stuff matched, yay! Lets fill in the fields. */
|
|   /* "bar" is a static string, fill it in as-is, no need to extract it
|   from the subject. */
|   log_msg_set_value(msg, "bar", "bar", 3);
|
|   /* :stuff is a number, so that needs to come from the
|   subject. Thankfully find_number() already did the extraction for
|   us. */
|   log_msg_set_value(msg, "stuff", m1->str, m1->len);
|
|   log_msg_set_tag_by_name(msg, "test stuff");
|
|   return TRUE;
| }
`----

I believe this is pretty efficient, the code generator can comment the
the generated source nicely too. If we add named capture-groups, then
the variables used can have meaningful names too!

For example: (match "this (?<object>[:qstring:]) is good")

In this case, the variable would be called m_object.

However, the pattern-string is a bit awkward, when the rest is lispy, it
also complicates the generator, so I was thinking of turning the pattern
into a lispy syntax too:

,----
| (match "foo " (capture "bar") " " (capture :number))
`----

Or, with named capture groups added:

,----
| (match "this " (capture :qstring :as "object") " is good")
`----

Of course, the action to take on a match can also contain another
cond+match pair, so it can be nested as deep as one wishes to, the
compiler will compile each cond into a separate function, and just call
the appropriate one. Or perhaps inline them - that's an implementation
detail, and doesn't really matter.

The big advantage I see, is a DSL that is much closer to how I think,
one that has the potential to produce a compact parser, one that is also
easy to debug with conventional tools (gdb ;) because it compiles down
to C. There is less run-time overhead too.

Also, if implemented correctly, the generator would have the parser and
the code generator entirely independent, so adding a different syntax
would be as easy as writing a parser that produces the same abstract
syntax tree the generator works with. This way, for those who're more
familiar with C-like languages, the above matcher could be rewritten
like this:

,----
| switch ($message)
|   {
|     case match("foo ", capture("bar"), " ", capture(:number:))
|       {
|         set("bar", "$1");
|         set("stuff", "$2");
|         append($tags, "test stuff");
|       }
|   }
`----

And it would compile down to the exact same C code, accompanied by an
appropriate autotools-based build system, so all you'd have to do in the
end is to write the matcher, and issue the following commands:

,----
| $ matcher-generate test-patterns.pm
| $ cd test-patterns
| $ autoreconf -i && ./configure && make && make install
`----

And finally, modify your syslog-ng.conf:

,----
| @module test-patterns
| parser p_test { parser(test-patterns); };
`----

It does have downsides, though, namely that you need to regenerate &
recompile the module and restart syslog-ng each time you modify the
source, which is less convenient than just restarting syslog-ng
itself. One also needs to learn a 'new' language to write pattern
matchers in (but one has to learn patterndb too, anyway, so this isn't
that big a disadvantage, especially since a more language-like thing is,
in my opinion, easier to learn :).

However, I believe that the advantages are worth it. For me, they
certainly do, so I already started to hash out a proof of concept. So
far, my PoC code can generate C functions, and supports a small subset
of the DSL explained below.

Do note that all this does not include corellation, because I believe
that corellation should be separate from parsing, and a similar
technique could be used to write advanced corellation setups - I will go
into detail once I have a working proof of concept compiler for the
parser.

As a start, the DSL would support the following constructs:

Top-level constructs:
---------------------

* (cond :field condition action ...)

  Where :field can be any field, condition is a single condition
  function (see below) and action is a single action too (see even
  further below).

  Any number of condition-action paris can be specified, the first one
  matching will win, and the rest won't be tried. These two must always
  be paired together.

* (deftest test-name
    "source string"

    test-conditions)

  Right now, lets ignore this. But in the long run, I want to be able to
  write down reasonably complex tests too. Not entirely sure yet what I
  need it to do though.

Condition functions:
--------------------

* (match pattern-spec)

  Matches a pattern-spec, simple as that. See below for the definition
  of the pattern-spec!

* (not-match pattern-spec)

  The opposite of (match): action is triggered if the pattern does not
  match.

* (exists?)

  Triggers the action if the field in the condition exists.

* (not-exists?)

  Opposite of (exists?).

* :default or (always)

  Always triggers, so one can do catch-all actions.

Action functions:
-----------------

* (set! :field value)
* (clear! :field)

These two should speak for themselves, I believe.

* (conj! :field values)

Conjoin (append) values to the specified field. Some fields (:tags) that
need to be, will be treated specially, otherwise it just appends a
separator (",") and the values.

* (do actions...)

Does all the specified actions.

Pattern spec:
-------------

The pattern can be built up from the sequence of the following things,
in any order:

* A plain string

* (capture pattern-spec [:as name])

  This just marks the pattern-spec as something to capture. While the
  implementation may produce code that captures things anyway, the only
  guarantee that something will be available for the actions, is to wrap
  it in (capture). The pattern-spec can be anything, it can contain
  nested captures.

  If :as name is specified, the capture will be named, and actions can
  refer to the captured thing by name. Otherwise, they need to refer it
  by a number. Each capture - named or anonymous - has a different
  number, starting from one, increasing with each occurrence of
  (capture).

* Any of the following special keywords:

  * :number
  * :string
  * :qstring
  * :ipv4-address
  * :ipv6-address
  * :mac-address

Future ideas
------------

Later, once the basics are ready and work, it would make sense to
introduce a way to share common blocks of code: functions and perhaps
variables.

Conclusion
==========

XML sucks, DSL rocks.

Feedback appreciated, be that on the syntax, or the initially proposed
features/functions/etc, or anything else.

-- 
|8],
who perhaps spent a little too much time near LISP-y stuff

Gergely Nagy

Jakub Jankowski

Gergely Nagy

Peter Gyongyosi

Gergely Nagy

Evan Rempel

Peter Gyongyosi

Gergely Nagy

Gergely Nagy

tags

participants (4)