src/augprint.h

   1 /*
   2  * Copyright (C) 2022 George Hansper <george@hansper.id.au>
   3  * -----------------------------------------------------------------------
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  12  * See the GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along with this program.
  15  * If not, see <https://www.gnu.org/licenses/>.
  16  *
  17  * Author: George Hansper <george@hansper.id.au>
  18  * -----------------------------------------------------------------------
  19  *
  20  Have:
  21      /head/label_a[pos1]/mid/label_b[pos2]/tail  value_a1_b1
  22      /head/label_a[pos3]/mid/label_b[pos4]/tail  value_a2_b1
  23
  24  +-------------------------------------------------------+
  25  | augeas_path_value                                     |
  26  |   path = "/head/label_a[pos1]/mid/label_b[pos2]/tail" |
  27  |   value = "value_a1_b1"                               |
  28  |   value_qq = "'value_a1_b1'" or "\"value_a1_b1\""     |
  29  |   segments --.                                        |
  30  +---------------\---------------------------------------+
  31                   \
  32  +----------------------------------------+     +--------------------------------------------+
  33  | path_segment                           |     | path_segment                               |
  34  |   head = "/head/label_a"               |     |   head = "/head/label_a[pos1]/mid/label_b" |
  35  |   segment = "/head/label_a"            |     |   seqment = "/mid/label_b"                 |
  36  |   simplified_tail = "mid/label_b/tail" |     |   simplified_tail = "tail"                 |
  37  |   position = (int) pos1                |     |   position = (int) pos2                    |
  38  |   next ------------------------------------->|   next --> NULL                            |
  39  |   group --.                            |     |   group --.                                |
  40  +------------\---------------------------+     +------------\-------------------------------+
  41                \                                              \
  42  +-----------------------------+                +--------------------------------------------+
  43  | group                       |                | group                                      |
  44  |   head = "/head/label_a"    |                |   head = "/head/label_a[pos1]/mid/label_b" |
  45  |   max_position              |                |   max_position                             |
  46  |   chosen_tail[]             |                |   chosen_tail[]                            |   array of *tail, index is position
  47  |   tails_at_position[]----------------.       |   tails_at_position[]----------------.     |   array of *tail_stub lists, index is position
  48  |   all_tails ---.            |         \      |   all_tails ---.                      \    |   linked list, unique to group
  49  +-----------------\-----------+          \     +-----------------\----------------------\---+
  50                     \                      \                       \                      \
  51  +------------------------------------+     \   +------------------------------------+     \
  52  | tail                               |-+   |   | tail                               |-+   |
  53  |   simple_tail = "mid/label_b/tail" | |   |   |   simple_tail = "tail"             | |   |
  54  |   value = "value_a1_b1"            | |   |   |   value = "value_a1_b1"            | |   |
  55  |   next (next in all_tails list)    | |   |   |   next (next in all_tails list)    | |   |
  56  |   tail_value_found                 | |   |   |   tail_value_found                 | |   |     count of matching tail+value
  57  |   tail_value_found_map[]           | |   |   |   tail_value_found_map[]           | |   |     per-position count of tail+value
  58  |   tail_found_map[]                 | |   |   |   tail_found_map[]                 | |   |     per-position count of matching tail
  59  +------------------------------------+ |   |   +------------------------------------+ |   |
  60    +------------------------------------+   |     +------------------------------------+   |
  61    (linked-list)       ^                    |     (linked-list)      ^                     |
  62                        |                    |                        |                     |
  63                        |        .-----------'                        |        .------------'
  64                        |        |                                    |        |
  65                        |        |                                    |        |
  66                        |        v                                    |        v
  67  +---------------------|--------------+        +---------------------|--------------+
  68  | tail_stub           |              |-+      | tail_stub           |              |-+
  69  |   *tail    (ptr) ---'              | |      |   *tail    (ptr) ---'              | |
  70  |   next (in order of appearance)    | |      |   next (in order of appearance)    | |
  71  +------------------------------------+ |      +------------------------------------+ |
  72    +------------------------------------+        +------------------------------------+
  73    (linked-list)                                 (linked-list)
  74
  75 all_tails is a linked-list of (struct tail), in no particular order, where the combination of tail+value is unique in this list
  76
  77 all_tails list is unique to a group, and the (struct tail) records are not shared outside the group
  78 The (struct tail) records are shared within the group, across all [123] positions
  79
  80 Each (struct_tail) contains three counters:
  81 * tail_value_found
  82     This is the number of times this tail+value combination appears within the group
  83     If this counter >1, this indicates a duplicate tail+value, ie two (or more) identical entries within the group
  84 * tail_value_found_map
  85     This is similar to tail_value_found, but there is an individiual counter for each position within the group
  86 * tail_found_map
  87     This is the number of times this tail (regardless of value) appears for each position within the group
  88
  89 There is a (struct tail_stub) record for _every_ tail that we find for this group, including duplicates
  90
  91 The (struct group) record keeps an array tails_at_position[] which is indexed by position
  92 Each array-element points to a linked-list of tail_stub records, which contain
  93 a pointer to a (struct tail) record from the all_tails linked list
  94 The tails_at_position[position] linked-list give us a complete list of all the tail+value records
  95 for this position in the group, in their original order of appearance
  96 */
  97
  98 /* all_tails record */
  99 struct tail {
 100   char         *simple_tail;
 101   char         *value;
 102   char         *value_qq;               /* The value, quoted and escaped as-needed */
 103   char         *value_re;               /* The value expressed as a regular-expression, long enough to uniquely identify the value */
 104   struct tail  *next;                   /* next all_tails record */
 105   unsigned int  tail_value_found;       /* number of times we have seen this tail+value within this group, (used by 1st preference) */
 106   unsigned int *tail_value_found_map;   /* Array, indexed by position, number of times we have seen this tail+value within this group (used by 3rd preference) */
 107   unsigned int *tail_found_map;         /* Array, indexed by position, number of times we have seen this tail (regardless of value) within this group (used by 2nd preference) */
 108 };
 109
 110 /* Linked list of pointers into the all_tails list
 111  * One such linked-list exists for each position within the group
 112  * Each list begins at group->tails_at_position[position]
 113  */
 114 struct tail_stub {
 115   struct tail      *tail;
 116   struct tail_stub *next;
 117 };
 118
 119 /* subgroup exists only to analyse the 3rd preference
 120  * it maps a subset of positions within a group
 121  */
 122 struct subgroup {
 123   struct tail      *first_tail;
 124   unsigned int     *matching_positions;   /* zero-terminated array of positions with the same first_tail */
 125   struct subgroup  *next;
 126 };
 127
 128 typedef enum {
 129     NOT_DONE=0,
 130     FIRST_TAIL=1,                         /* 1st preference */
 131     CHOSEN_TAIL_START=4,                  /* 2nd preference - unique tail found for this position */
 132     CHOSEN_TAIL_WIP=5,                    /* 2nd preference */
 133     CHOSEN_TAIL_DONE=6,                   /* 2nd preference */
 134     CHOSEN_TAIL_PLUS_FIRST_TAIL_START=8,  /* 3rd preference - unique tail found in a subgroup with a common first_tail */
 135     CHOSEN_TAIL_PLUS_FIRST_TAIL_WIP=9,    /* 3rd preference */
 136     CHOSEN_TAIL_PLUS_FIRST_TAIL_DONE=10,  /* 3rd preference */
 137     FIRST_TAIL_PLUS_POSITION=12,          /* Fallback - use first_tail subgroup and append a position */
 138     NO_CHILD_NODES=16,                    /* /head/123 with no child nodes */
 139 } chosen_tail_state_t;
 140
 141 struct group {
 142   char                   *head;
 143   struct tail            *all_tails;             /* Linked list */
 144   struct tail_stub      **tails_at_position;     /* array of linked-lists, index is position */
 145   struct tail           **chosen_tail;           /* array of (struct tail)      pointers, index is position */
 146   struct tail_stub      **first_tail;            /* array of (struct tail_stub) pointers, index is position */
 147   unsigned int            max_position;          /* highest position seen for this group */
 148   unsigned int            position_array_size;   /* array size for arrays indexed by position, >= max_position+1, used for malloc() */
 149   chosen_tail_state_t    *chosen_tail_state;     /* array, index is position */
 150   struct subgroup        *subgroups;             /* Linked list, subgroups based on common first-tail - used only for 3rd preference and fallback */
 151   unsigned int           *subgroup_position;     /* array, position within subgroup for this position - used only for fallback */
 152   /* For --pretty */
 153   unsigned int           *pretty_width_ct;      /* array, index is position, value width to use for --pretty */
 154   /* For --regexp */
 155   unsigned int           *re_width_ct;           /* array, index is position, matching width to use for --regexp */
 156   unsigned int           *re_width_ft;           /* array, index is position, matching width to use for --regexp */
 157 };
 158
 159 struct path_segment {
 160   char                *head;
 161   char                *segment;
 162   char                *simplified_tail;
 163   unsigned int         position;
 164   struct group        *group;
 165   struct path_segment *next;
 166 };
 167
 168 /* Results of aug_match() and aug_get() - one record per path returned by aug_match() */
 169 struct augeas_path_value {
 170   char *path;
 171   char *value;
 172   char *value_qq;            /* value in quotes - used in path-expressions, and as the value being assigned */
 173   /* result of split_path() */
 174   struct path_segment *segments;
 175 };