path: root/doc/devel/bison.dox

// Copyright (C) 2017-2021 Internet Systems Consortium, Inc. ("ISC")
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

/**
@page parser Flex/Bison Parsers

@section parserIntro Parser background

Kea's data format of choice is JSON (defined in https://tools.ietf.org/html/rfc7159), which is used
in configuration files, in the command channel and also when communicating between the DHCP servers
and the DHCP-DDNS component. It is almost certain to be used as the data format for any new
features.

Historically, Kea used the @ref isc::data::Element::fromJSON and @ref
isc::data::Element::fromJSONFile methods to parse data expected to be in JSON syntax. This in-house
parser was developed back in the early days of Kea when it was part of BIND 10.  Its main advantages
were that it didn't have any external dependencies and that it was already available in the source
tree when Kea development started. On the other hand, it was very difficult to modify (several
attempts to implement more robust comments had failed) and lacked a number of features. Also, it was
a pure JSON parser, so accepted anything as long as the content was correct JSON. (This caused some
problems: for example, the syntactic checks were conducted late in the parsing process, by which
time some of the information, e.g. line numbers, was no longer available. To print meaningful error
messages, the Kea team had to develop a way to store filename, line and column information.
Unfortunately this gave rise to other problems such as data duplication.) The output from these
parsers was a tree of @ref isc::data::Element objects using shared pointers.  This part of the
processing we can refer to as phase 1.

The Element tree was then processed by set of dedicated parsers.  Each
parser was able to handle its own context, e.g. global, subnet list,
subnet, pool etc. This step took the tree generated in phase 1, parsed
it and generated an output configuration (e.g. @ref
isc::dhcp::SrvConfig) or dynamic structures
(e.g. isc::data::Host). During this stage, a large number of parser
objects derived from DhcpConfigParser could be instantiated for each
scope and instance of data (e.g. to parse 1000 host reservation
entries a thousand dedicated parsers were created).  For convenience,
this step is called phase 2.

Other issues with the old parsers are discussed here: @ref dhcpv6ConfigParserBison (this section is
focused on DHCPv6, but the same issues affected DHCPv4 and D2) and here:
https://gitlab.isc.org/isc-projects/kea/wikis/designs/simple-parser-design.

@section parserBisonIntro Flex/Bison Based Parser

To solve the issue of phase 1 mentioned earlier, a new parser has been developed that is based on
the "flex and "bison" tools. The following text uses DHCPv6 as an example, but the same principle
applies to DHCPv4 and D2; CA will likely to follow. The new parser consists of two core elements
with a wrapper around them.  The following descriptions are slightly oversimplified in order to
convey the intent; a more detailed description is available in subsequent sections.

-# Flex lexical analyzer (src/bin/dhcp6/dhcp6_lexer.ll): this is essentially a set of
   regular expressions and C++ code that creates new tokens that represent whatever
   was just parsed. This lexical analyzer (lexer) will be called iteratively by bison until the whole
   input text is parsed or an error is encountered. For example, a snippet of the
   code might look like this:
   @code
   \"socket-type\" {
        return isc::dhcp::Dhcp6Parser::make_SOCKET_TYPE(driver.loc_);
   }
   @endcode
   This tells the flex that if encounters "socket-type" (quoted), then it should
   create a token SOCKET_TYPE and pass to it its current location (that's the
   file name, line and column numbers).

-# Bison grammar (src/bin/dhcp6/dhcp6_parser.yy): the module that defines the syntax.  Grammar and
   syntax are perhaps fancy words, but they simply define what is allowed and where. Bison grammar
   starts with a list of tokens. Those tokens are defined only by name ("here's the list of possible
   tokens that could appear"). What constitutes a token is actually defined in the lexer. The
   grammar define how the incoming tokens are expected to fall into their places together. Let's
   take an example of the following input text:
   @code
   {
      "Dhcp6":
      {
          "renew-timer": 100
      }
   }
   @endcode
   The lexer would generate the following sequence of tokens: LCURLY_BRACKET, DHCP6, COLON,
   LCURLY_BRACKET, RENEW_TIMER, COLON, INTEGER (a token with a value of 100), RCURLY_BRACKET,
   RCURLY_BRACKET, END.  The bison grammar recognizes that the sequence forms a valid sentence and
   that there are no errors and act upon it. (Whereas if the left and right braces in the above
   example were exchanged, the bison module would identify the sequence as syntactically incorrect.)

-# Parser context. As there is some information that needs to be passed between parser and lexer,
   @ref isc::dhcp::Parser6Context is a convenience wrapper around those two bundled together. It
   also works as a nice encapsulation, hiding all the flex/bison details underneath.

@section parserBuild Building Flex/Bison Code

The only input file used by flex is the .ll file and the only input file used by bison is the .yy
file. When making changes to the lexer or parser, only those two files are edited. When processed,
the two tools generate a number of .h, .hh and .cc files. The major ones have the same name as their
.ll and .yy counterparts (e.g. dhcp6_lexer.cc, dhcp6_parser.cc and dhcp6_parser.h etc.), but an
additional file is also created: location.hh. Those are internal bison headers that are needed for
compilation.

To avoid the need for every user to have flex and bison installed, the output files are generated
when the .ll or .yy files are altered and are stored in the Kea repository. To generate those files,
issue the following sequence of commands from the top-level Kea directory:

@code
./configure --enable-generate-parser
cd src/bin/dhcp6
make parser
@endcode

Strictly speaking, the comment "make parser" is not necessary. If you updated the .ll or .yy file,
the regular "make" command should pick those changes up. However, since one source file generates
multiple output files and you are likely to be using a multi-process build (by specifying the "-j"
switch on the "make" command), there may be odd side effects: explicitly rebuilding the files
manually by using "make parser" avoids any trouble.

One problem brought on by use of flex/bison is tool version dependency. If one developer uses
version A of those tools and another developer uses B, the files generated by the different version
may be significantly different. This causes all sorts of problems, e.g.  coverity/cpp-check issues
may appear and disappear: in short, it can cause all sorts of general unhappiness.  To avoid those
problems, the Kea team generates the flex/bison files on a dedicated machine. See KeaRegen page
on ISC internal wiki for details.

@section parserFlex Flex Detailed

Earlier sections described the lexer in a bit of an over-simplified way. The .ll file contains a
number of elements in addition to the regular expressions and they're not as simple as was
described.

The file starts with a number of sections separated by percent (%) signs. Depending on which section
code is written in, it may be interpreted by flex, copied verbatim to the output .cc file, copied to
the output .h file or copied to both.

There is an initial section that defines flex options. These are somewhat documented, but the
documentation for it may be a bit cryptic. When developing new parsers, it's best to start by
copying whatever we have for DHCPv6 and tweak as needed.

Next comes the flex conditions. They are defined with %%x and they define a state of the lexer. A
good example of a state may be comment. Once the lexer detects that a comment's beginning, it
switches to a certain condition (by calling BEGIN(COMMENT) for example) and the code then ignores
whatever follows (especially strings that look like valid tokens) until the comment is closed (when
it returns to the default condition by calling BEGIN(INITIAL)). This is something that is not
frequently used and the only use cases for it are the forementioned comments and file inclusions.

After this come the syntactic contexts. Let's assume we have a parser that uses an "ip-address"
regular expression (regexp) that would return the IP_ADDRESS token. Whenever we want to allow
"ip-address", the grammar allows the IP_ADDRESS token to appear. When the lexer is called, it will
match the regexp, generate the IP_ADDRESS token and the parser will carry out its duty. This works
fine as long as you have very specific grammar that defines everything. Sadly, that's not the case
in DHCP as we have hooks. Hook libraries can have parameters that are defined by third party
developers and they can pick whatever parameter names they want, including "ip-address". Another
example could be Dhcp4 and Dhcp6 configurations defined in a single file. The grammar defining
"Dhcp6" main contain a clause that says "Dhcp4" may contain any generic JSON. However, the lexer may
find the "ip-address" string in the "Dhcp4" configuration and will say that it's not a part of
generic JSON, but a dedicated IP_ADDRESS token instead. The parser will then complain and the whole
thing would end up in failure. It was to solve this problem that syntactic contexts were introduced.
They tell the lexer whether input strings have specific or generic meaning.  For example, when
parsing host reservations, the lexer is expected to report the IP_ADDRESS token if "ip-address" is
detected. However, when parsing generic JSON, upon encountering "ip-address" it should return a
STRING with a value of "ip-address". The list of all contexts is enumerated in @ref
isc::dhcp::Parser6Context::ParserContext.

For a DHCPv6-specific description of the conflict avoidance, see @ref dhcp6ParserConflicts.

@section parserGrammar Bison Grammar

Bison has much better documentation than flex. Its latest version seems to be available here:
https://www.gnu.org/software/bison/manual. Bison is a LALR(1) parser, which essentially means that
it is able to parse (separate and analyze) any text that is described by set of rules. You can see
the more formal description here: https://en.wikipedia.org/wiki/LALR_parser, but the plain English
explanation is that you define a set of rules and bison will walk through input text trying to match
the content to those rules. While doing so, it will be allowed to peek at most one symbol (token)
ahead.

As an example, let's take a closer look at the bison grammar we have for DHCPv6. It is defined
in src/bin/dhcp6/dhcp6_parser.yy. Here's a simplified excerpt:

@code
// This defines a global Dhcp6 object.
dhcp6_object: DHCP6 COLON LCURLY_BRACKET global_params RCURLY_BRACKET;

// This defines all parameters that may appear in the Dhcp6 object.
// It can either contain a global_param (defined below) or a
// global_params list, followed by a comma followed by a global_param.
// Note this definition is recursive and can expand to a single
// instance of global_param or multiple instances separated by commas.
// This is how bison handles variable number of parameters.
global_params: global_param
             | global_params COMMA global_param
             ;

// These are the parameters that are allowed in the top-level for
// Dhcp6.
global_param: preferred_lifetime
            | valid_lifetime
            | renew_timer
            | rebind_timer
            | subnet6_list
            | interfaces_config
            | lease_database
            | hosts_database
            | mac_sources
            | relay_supplied_options
            | host_reservation_identifiers
            | client_classes
            | option_data_list
            | hooks_libraries
            | expired_leases_processing
            | server_id
            | dhcp4o6_port
            ;

renew_timer: RENEW_TIMER COLON INTEGER;

// Many other definitions follow.
@endcode

The code above defines parameters that may appear in the Dhcp6 object declaration. One important
trick to understand is understand the way to handle variable number of parameters. In bison it is
most convenient to present them as recursive lists: in this example, global_params defined in a way
that allows any number of global_param instances allowing the grammar to be easily extensible. If
one needs to add a new global parameter, just add it to the global_param list.

This type of definition has several levels, each representing logical structure of the configuration
data. We start with global scope, then step into a Dhcp6 object that has a Subnet6 list, which in
turn has Subnet6 instances, each of which has pools list and so on. Each level is represented as a
separate rule.

The "leaf" rules (that don't contain any other rules) must be defined by a series of tokens. An
example of such a rule is renew_timer, above. It is defined as a series of 3 tokens: RENEW_TIMER,
COLON and INTEGER.

Speaking of integers, it is worth noting that some tokens can have values. Those values are defined
using %token clause.  For example, dhcp6_parser.yy contains the following:

@code
%token <std::string> STRING "constant string"
%token <int64_t> INTEGER "integer"
%token <double> FLOAT "floating point"
%token <bool> BOOLEAN "boolean"
@endcode

The first line says that the token STRING has a type of std::string and when referring to this token
in error messages, it should be printed as "constant string".

In principle, it is valid to define just the grammar without any corresponding C++ code to it. Bison
will go through the whole input text, match the rules and will either say the input adhered to the
rules (parsing successful) or not (parsing failed). This may be a useful step when developing new
parser, but it has no practical value. To perform specific actions, bison allows the injection of
C++ code at almost any point. For example we could augment the parsing of renew_timer with some
extra code:

@code
renew_timer: RENEW_TIMER {
   cout << "renew-timer token detected, so far so good" << endl;
} COLON {
   cout << "colon detected!" << endl;
} INTEGER {
    uint32_t timer = $3;
    cout << "Got the renew-timer value: " << timer << endl;
    ElementPtr prf(new IntElement($3, ctx.loc2pos(@3)));
    ctx.stack_.back()->set("renew-timer", prf);
};
@endcode

This example showcases several important things. First, the ability to insert code at almost any
step is very useful. It's also a powerful debugging tool.

Second, some tokens are valueless (e.g. "renew-timer" when represented as the RENEW_TIMER token has
no value), but some have values. In particular, the INTEGER token has value which can be extracted
by $ followed by a number that represents its order, so $3 means "a value of third token or action
in this rule". If needed, the location of specific token (filename, line and column) can be
accessed with @ followed by a number that represents token number, e.g. @3 in the example above
returns exact location of INTEGER token.

Also, some rules may have values. This is not used often, but there are specific cases when it's
convenient. Let's take a look at the following excerpt from dhcp6_parser.yy:

@code
ncr_protocol: NCR_PROTOCOL {
    ctx.enter(ctx.NCR_PROTOCOL); (1)
} COLON ncr_protocol_value {
    ctx.stack_.back()->set("ncr-protocol", $4); (3)
    ctx.leave(); (4)
};

ncr_protocol_value:
    UDP { $$ = ElementPtr(new StringElement("UDP", ctx.loc2pos(@1))); }
  | TCP { $$ = ElementPtr(new StringElement("TCP", ctx.loc2pos(@1))); } (2)
  ;
@endcode

(The numbers in brackets at the end of some lines do not appear in the code; they are used identify
the statements in the following discussion.)

The "ncr-protocol" parameter accepts one of two values: either tcp or udp. To handle such a case, we
first enter the NCR_PROTOCOL context to tell the lexer that we're in this scope. The lexer will then
know that any incoming string of text that is either "UDP" or "TCP" should be represented as one of
the TCP or UDP tokens. The parser knows that after NCR_PROTOCOL there will be a colon followed by an
ncr_protocol_value. The rule for ncr_protocol_value says it can be either the TCP token or the UDP
token. Let's assume the input text is:
@code
"ncr-protocol": "TCP"
@endcode

Here's how the parser will handle it. First, it will attempt to match the rule for ncr_protocol. It
will discover the first token is NCR_PROTOCOL. As a result, it will run the code (1), which will
tell lexer to parse incoming tokens as ncr protocol values. The next token is expected to be COLON
and the one after that the ncr_protocol_value. The lexer has already been switched into the
NCR_PROTOCOL context, so it will recognize "TCP" as TCP token, not as a string with a value of
"TCP".  The parser will receive that token and match the line (2), which creates an appropriate
representation that will be used as the rule's value ($$). Finally, the parser will unroll back to
ncr_protocol rule and execute the code in lines (3) and (4).  Line (3) picks the value set up in
line (2) and adds it to the stack of values. Finally, line (4) tells the lexer that we finished the
NCR protocol parsing and it can go back to whatever state it was before.

@section parserBisonStack Generating the Element Tree in Bison

The bison parser keeps matching rules until it reaches the end of input file. During that process,
the code needs to build a hierarchy (a tree) of inter-connected Element objects that represents the
parsed text. @ref isc::data::Element has a complex structure that defines parent-child relation
differently depending on the type of parent (ae.g. a map and a list refer to their children in
different ways).  This requires the code to be aware of the parent content. In general, every time a
new scope (an opening curly bracket in input text) is encountered, the code pushes new Element to
the stack (see @ref isc::dhcp::Parser6Context::stack_) and every time the scope closes (a closing
curly bracket in input text) the element is removed from the stack. With this approach, we always
have access to the parent element as it's the last element on the stack. For example, when parsing
preferred-lifetime, the code does the following:

@code
preferred_lifetime: PREFERRED_LIFETIME COLON INTEGER {
    ElementPtr prf(new IntElement($3, ctx.loc2pos(@3)));
    ctx.stack_.back()->set("preferred-lifetime", prf);
}
@endcode

The first line creates an instance of IntElement with a value of the token.  The second line adds it
to the current map (current = the last on the stack).  This approach has a very nice property of
being generic. This rule can be referenced from both global and subnet scope (and possibly other
scopes as well) and the code will add the IntElement object to whatever is last on the stack, be it
global, subnet or perhaps even something else (maybe one day we will allow preferred lifetime to be
defined on a per pool or per host basis?).

@section parserSubgrammar Parsing a Partial Configuration

All the explanations so far assumed that we're operating in a default case of receiving the
configuration as a whole. That is the case during startup and reconfiguration. However, both DHCPv4
and DHCPv6 support certain cases when the input text is not the whole configuration, but rather
certain parts of it. There are several examples of such cases. The most common are unit-tests. They
typically don't have the outermost { } or Dhcp6 object, but simply define whatever parameters are
being tested. Second, we have the command channel that will, in the near future, contain parts of
the configuration, depending on the command. For example, "add-reservation" will contain a host
reservation only.

Bison by default does not support multiple start rules, but there's a trick that can provide such a
capability. The trick assumes that the starting rule may allow one of the artificial tokens that
represent the scope expected. For example, when called from the "add-reservation" command, the
artificial token will be SUB_RESERVATION and it will trigger the parser to bypass the global braces
{ and } and the "Dhcp6" token and jump immediately to the sub_reservation.

This trick is also implemented in the lexer. A flag called start_token_flag, when initially set to
true, will cause the lexer to emit an artificial token once, before parsing any input whatsoever.

This optional feature can be skipped altogether if you don't plan to parse parts of the
configuration.

@section parserBisonExtend Extending the Grammar

Adding new parameters to existing parsers is very easy once you get hold of the concept of what the
grammar rules represent. The first step is to understand where the parameter is to be
allowed. Typically a new parameter is allowed in one scope and only over time is it added to other
scopes. Recently support for a 4o6-interface-id parameter has been added. That is a parameter that
can be defined in a subnet and takes a string argument. You can see the actual change conducted in
this commit: (https://github.com/isc-projects/kea/commit/9fccdbf54c4611dc10111ad8ff96d36cad59e1d6).

Here's the complete set of changes that were necessary.

1. Define a new token in dhcp6_parser.yy:
   @code
   SUBNET_4O6_INTERFACE_ID "4o6-interface-id"
   @endcode
   This defines a token called SUBNET_4O6_INTERFACE_ID that, when it needs to
   be printed, e.g. in an error message, will be represented as "4o6-interface-id".

2. Tell the lexer how to recognize the new parameter:
   @code
   \"4o6-interface-id\" {
       switch(driver.ctx_) {
       case isc::dhcp::Parser4Context::SUBNET4:
           return isc::dhcp::Dhcp4Parser::make_SUBNET_4O6_INTERFACE_ID(driver.loc_);
       default:
           return isc::dhcp::Dhcp4Parser::make_STRING("4o6-interface-id", driver.loc_);
       }
   }
   @endcode
   It tells the parser that when in Subnet4 context, an incoming "4o6-interface-id" string should be
   represented as the SUBNET_4O6_INTERFACE_ID token. In any other context, it should be represented
   as a string.

3. Add the rule that will define the value. A user is expected to add something like
   @code
   "4o6-interface-id": "whatever"
   @endcode
   The rule to match this and similar statements looks as follows:
   @code
   subnet_4o6_interface_id: SUBNET_4O6_INTERFACE_ID {
       ctx.enter(ctx.NO_KEYWORD);
   } COLON STRING {
       ElementPtr iface(new StringElement($4, ctx.loc2pos(@4)));
       ctx.stack_.back()->set("4o6-interface-id", iface);
       ctx.leave();
   };
   @endcode
   Here's a good example of the context use. We have no idea what sort of interface-id the user will
   use. Typically that will be an integer, but it may be something weird that happens to match our
   reserved keywords. Therefore we switch to no keyword context. This tells the lexer to interpret
   everything as string, integer or float.

4. Finally, extend the existing subnet4_param that defines all allowed parameters
   in the Subnet4 scope to also cover our new parameter (the new line marked with *):
   @code
   subnet4_param: valid_lifetime
                | renew_timer
                | rebind_timer
                | option_data_list
                | pools_list
                | subnet
                | interface
                | interface_id
                | id
                | rapid_commit
                | client_class
                | reservations
                | reservation_mode
                | relay
                | match_client_id
                | authoritative
                | next_server
                | subnet_4o6_interface
                | subnet_4o6_interface_id (*)
                | subnet_4o6_subnet
                | unknown_map_entry
                ;
   @endcode

5. Regenerate the flex/bison files by typing "make parser".

6. Run the unit-tests that you wrote before you touched any of the bison stuff. You did write them
   in advance, right?
*/