Adding upstream version 2.2.0.upstream/2.2.0upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 450 insertions, 0 deletions

diff --git a/doc/devel/bison.dox b/doc/devel/bison.dox
new file mode 100644
index 0000000..4c96302
--- /dev/null
+++ b/doc/devel/bison.dox
@@ -0,0 +1,450 @@
+// 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?
+*/