Kea 2.5.8
libkea-eval - Expression Evaluation and Client Classification Library

Introduction

The core of the libeval library is a parser that is able to parse an expression (e.g. option[123].text == 'APC'). This is currently used for client classification, but in the future may be also used for other applications.

The external interface to the library is the isc::eval::EvalContext class. Once instantiated, it offers a major method: isc::eval::EvalContext::parseString, which parses the specified string. Once the expression is parsed, it is converted to a collection of tokens that are stored in Reverse Polish Notation in EvalContext::expression.

Parameters to the isc::eval::EvalContext class constructor are the universe to choose between DHCPv4 and DHCPv6 for DHCP version dependent expressions, and a function used by the parser to accept only already defined or built-in client class names in client class membership expressions. This function defaults to accept all client class names.

Internally, the parser code is generated by flex and bison. These two tools convert lexer.ll and parser.yy files into a number of .cc and .hh files. To avoid a build of Kea depending on the presence of flex and bison, the result of the generation is checked into the github repository and is distributed in the tarballs.

Lexer generation using flex

Flex is used to generate the lexer, a piece of code that converts input data into a series of tokens. It contains a small number of directives, but the majority of the code consists of the definitions of tokens. These definitions are regular expressions that define various tokens, e.g. strings, numbers, parentheses, etc. Once the expression is matched, the associated action is executed. In the majority of the cases a generator method from isc::eval::EvalParser is called, which returns returns a newly created bison token. The purpose of the lexer is to generate a stream of tokens that are consumed by the parser.

lexer.cc and lexer.hh must not be edited. If there is a need to introduce changes, lexer.ll must be updated and the .cc and .hh files regenerated.

Parser generation using bison

Bison is used to generate the parser, a piece of code that consumes a stream of tokens and attempts to match it against a defined grammar. The bison parser is created from parser.yy. It contains a number of directives, but the two most important sections are: a list of tokens (for each token defined here, bison will generate the make_NAMEOFTOKEN method in the isc::eval::EvalParser class) and the grammar. The Grammar is a tree like structure with possible loops.

Here is an over-simplified version of the grammar:

01. %start expression;
02.
03. expression : token EQUAL token
04. | token
05. ;
06.
07. token : STRING
08. {
09. TokenPtr str(new TokenString($1));
10. ctx.expression.push_back(str);
11. }
12. | HEXSTRING
13. {
14. TokenPtr hex(new TokenHexString($1));
15. ctx.expression.push_back(hex);
16. }
17. | OPTION '[' INTEGER ']' DOT TEXT
18. {
19. TokenPtr opt(new TokenOption($3, TokenOption::TEXTUAL));
20. ctx.expression.push_back(opt);
21. }
22. | OPTION '[' INTEGER ']' DOT HEX
23. {
24. TokenPtr opt(new TokenOption($3, TokenOption::HEXADECIMAL));
25. ctx.expression.push_back(opt);
26. }
27. ;
isc::dhcp::TokenPtr
boost::shared_ptr< Token > TokenPtr
Pointer to a single Token.
Definition: token.h:20

This code determines that the grammar starts from expression (line 1). The actual definition of expression (lines 3-5) may either be a single token or an expression "token == token" (EQUAL has been defined as "==" elsewhere). Token is further defined in lines 7-22: it may either be a string (lines 7-11), a hex string (lines 12-16), option in the textual format (lines 17-21) or option in a hexadecimal format (lines 22-26). When the actual case is determined, the respective C++ action is executed. For example, if the token is a string, the TokenString class is instantiated with the appropriate value and put onto the expression vector.

Generating parser files

In the general case, we want to avoid generating parser files, so an average user interested in just compiling Kea would not need flex or bison. Therefore the generated files are already included in the git repository and will be included in the tarball releases.

However, there will be cases when one of the developers would want to tweak the lexer.ll and parser.yy files and then regenerate the code. For this purpose, two makefile targets are defined:

make parser

will generate the parsers and

make parser-clean

will remove the files. Generated files removal was also hooked into the maintainer-clean target.

Configure options

Since the flex/bison tools are not necessary for a regular compilation, checks are conducted during the configure script, but the lack of flex or bison tools does not stop the process. There is a flag (–enable-generate-parser) that tells configure script that the parser will be generated. With this flag, the checks for flex/bison are mandatory. If either tool is missing or at too early a version, the configure process will terminate with an error.

Supported tokens

There are a number of tokens implemented. Each token is derived from isc::eval::Token class and represents a certain expression primitive. Currently supported tokens are:

More operators are expected to be implemented in upcoming releases.

Multi-Threading Consideration for Expression Evaluation Library

This library is not thread safe, for instance isc::dhcp::evaluateBool or isc::dhcp::evaluateString must not be called in different threads on the same packet.