doc/architecture.rst

   1 ..  SPDX-License-Identifier: BSD-3-Clause
   2     Copyright 2019 Olivier Matz <zer0@droids-corp.org>
   3
   4 Architecture
   5 ============
   6
   7 Most of *libecoli* is written in C. It provides a C API to ease the
   8 creation of interactive command line interfaces. It is split in several
   9 parts:
  10
  11 - the core: it provides the main API to parse and complete strings.
  12 - ecoli nodes: this is the modular part of *libecoli*. Each node
  13   implements a specific parsing (integers, strings, regular expressions,
  14   sequence, ...)
  15 - yaml parser: load an ecoli tree described in yaml.
  16 - editline: helpers to instantiate an *editline* and connect it to
  17   *libecoli*.
  18 - utilities: logging, string, strings vector, hash table, ...
  19
  20 The grammar tree
  21 ----------------
  22
  23 The *ecoli nodes* are organized in a tree. An *ecoli grammar tree*
  24 describes how the input is parsed and completed. Let's take a simple
  25 example:
  26
  27 .. figure:: simple-tree.svg
  28
  29    A simple *ecoli grammar tree*.
  30
  31 We can also represent it as text like this::
  32
  33   sh_lex(
  34     seq(
  35       str(foo),
  36       option(
  37         str(bar)
  38       )
  39     )
  40   )
  41
  42 This tree matches the following strings:
  43
  44 - ``foo``
  45 - ``foo bar``
  46
  47 But, for instance, it does **not** match the following strings:
  48
  49 - ``bar``
  50 - ``foobar``
  51 - (empty string)
  52
  53 Parsing an input
  54 ----------------
  55
  56 When the *libecoli* parses an input, it browses the tree (depth first
  57 search) and returns an *ecoli parse tree*. Let's decompose what is done
  58 when ``ec_parse_strvec(root_node, input)`` is called, step by step:
  59
  60 1. The initial input is a string vector ``["foo bar"]``.
  61 2. The *sh_lex* node splits the input as a shell would have done it, in
  62    ``["foo", "bar"]``, and passes it to its child.
  63 3. The *seq* node (sequence) passes the input to its first child.
  64 4. The *str* node matches if the first element of the string vector is
  65    ``foo``. This is the case, so it returns the number of eaten
  66    strings (1) to its parent.
  67 5. The *seq* node passes the remaining part ``["bar"]`` to its next
  68    child.
  69 6. The option node passes the string vector to its child, which
  70    matches. It returns 1 to its parent.
  71 7. The *seq* node has no more child, it returns the number of eaten
  72    strings in the vector (2).
  73 8. Finally, *sh_lex* compares the returned value to the number of
  74    strings in its initial vector, and return 1 (match) to its caller.
  75
  76 If a node does not match, it returns ``EC_PARSE_NOMATCH`` to its parent,
  77 and it is propagated until it reaches a node that handle the case. For
  78 instance, the *or* node is able to handle this error. If a child does
  79 not match, the next one is tried until it finds one that matches.
  80
  81 The parse tree
  82 --------------
  83
  84 Let's take another simple example.
  85
  86 .. figure:: simple-tree2.svg
  87
  88    Another simple *ecoli grammar tree*.
  89
  90 In that case, there is no lexer (the *sh_lex* node), so the input must
  91 be a string vector that is already split. For instance, it matches:
  92
  93 - ``["foo"]``
  94 - ``["bar", "1"]``
  95 - ``["bar", "100"]``
  96
  97 But it does **not** match:
  98
  99 - ``["bar 1"]``, because there is no *sh_lex* node on the top of the tree
 100 - ``["bar"]``
 101 - ``[]`` (empty vector)
 102
 103 At the time the input is parsed, a *parse tree* is built. When it
 104 matches, it describes which part of the *ecoli grammar tree* that
 105 actually matched, and what input matched for each node.
 106
 107 Passing ``["bar", "1"]`` to the previous tree would result in the
 108 following *parse tree*:
 109
 110 .. figure:: parse-tree.svg
 111
 112    The *ecoli parse tree*, result of parsing.
 113
 114 Each node of the *parse tree* references the node of the *grammar tree*
 115 that matched. It also stores the string vector that matched.
 116
 117 .. figure:: parse-tree2.svg
 118
 119    The same *ecoli parse tree*, showing the references to the grammar
 120    tree.
 121
 122 We can see that not all of the grammar nodes are referenced, since the
 123 str("foo") node was not parsed. Similarly, one grammar node can be
 124 referenced several times in the parse tree, as we can see it in the
 125 following example:
 126
 127 .. figure:: simple-tree3.svg
 128
 129    A simple *ecoli grammar tree*, that matches ``[]``, ``[foo]``,
 130    ``[foo, foo]``, ...
 131
 132 Here is the resulting *parse tree* when the input vector is ``[foo, foo,
 133 foo]``:
 134
 135 .. figure:: parse-tree3.svg
 136
 137    The resulting *parse tree*.
 138
 139 Node identifier
 140 ---------------
 141
 142 XXX
 143
 144 Todo
 145 ----
 146
 147 - completions
 148 - C example
 149 - ec_config
 150 - parse yaml
 151 - params are consumed
 152 - nodes
 153 - attributes