src/lens.h

   1 /*
   2  * lens.h: Repreentation of lenses
   3  *
   4  * Copyright (C) 2007-2016 David Lutterkort
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
  19  *
  20  * Author: David Lutterkort <dlutter@redhat.com>
  21  */
  22
  23 #ifndef LENS_H_
  24 #define LENS_H_
  25
  26 #include "syntax.h"
  27 #include "fa.h"
  28 #include "jmt.h"
  29
  30 /* keep in sync with tag name table */
  31 enum lens_tag {
  32     L_DEL = 42,    /* Shift tag values so we fail fast(er) on bad pointers */
  33     L_STORE,
  34     L_VALUE,
  35     L_KEY,
  36     L_LABEL,
  37     L_SEQ,
  38     L_COUNTER,
  39     L_CONCAT,
  40     L_UNION,
  41     L_SUBTREE,
  42     L_STAR,
  43     L_MAYBE,
  44     L_REC,
  45     L_SQUARE
  46 };
  47
  48 /* A lens. The way the type information is computed is a little
  49  * delicate. There are various regexps involved to form the final type:
  50  *
  51  * CTYPE - the concrete type, used to parse file -> tree
  52  * ATYPE - the abstract type, used to parse tree -> file
  53  * KTYPE - the 'key' type, matching the label that this lens
  54  *         can produce, or NULL if no label is produced
  55  * VTYPE - the 'value' type, matching the value that this lens
  56  *         can produce, or NULL if no value is produce
  57  *
  58  * We distinguish between regular and recursive (context-free) lenses. Only
  59  * L_REC and the combinators can be marked recursive.
  60  *
  61  * Types are computed at different times, depending on whether the lens is
  62  * recursive or not. For non-recursive lenses, types are computed when the
  63  * lens is constructed by one of the LNS_MAKE_* functions; for recursive
  64  * lenses, we never compute an explicit ctype (since regular approximations
  65  * of it are pretty much useless), we do however compute regular
  66  * approximations of the ktype, vtype, and atype in LNS_CHECK_REC. That
  67  * means that recursive lenses accept context free languages in the string
  68  * -> tree direction, but only regular tree languages in the tree -> string
  69  * direction.
  70  *
  71  * Any lens that uses a recursive lens somehow is marked as recursive
  72  * itself.
  73  */
  74 struct lens {
  75     unsigned int              ref;
  76     enum lens_tag             tag;
  77     struct info              *info;
  78     struct regexp            *ctype;  /* NULL when recursive == 1 */
  79     struct regexp            *atype;
  80     struct regexp            *ktype;
  81     struct regexp            *vtype;
  82     struct jmt               *jmt;    /* When recursive == 1, might have jmt */
  83     unsigned int              value : 1;
  84     unsigned int              key : 1;
  85     unsigned int              recursive : 1;
  86     unsigned int              consumes_value : 1;
  87     /* Whether we are inside a recursive lens or outside */
  88     unsigned int              rec_internal : 1;
  89     unsigned int              ctype_nullable : 1;
  90     union {
  91         /* Primitive lenses */
  92         struct {                   /* L_DEL uses both */
  93             struct regexp *regexp; /* L_STORE, L_KEY */
  94             struct string *string; /* L_VALUE, L_LABEL, L_SEQ, L_COUNTER */
  95         };
  96         /* Combinators */
  97         struct lens *child;         /* L_SUBTREE, L_STAR, L_MAYBE, L_SQUARE */
  98         struct {                    /* L_UNION, L_CONCAT */
  99             unsigned int nchildren;
 100             struct lens **children;
 101         };
 102         struct {
 103             struct lens *body;      /* L_REC */
 104             /* We represent a recursive lens as two instances of struct
 105              * lens with L_REC. One has rec_internal set to 1, the other
 106              * has it set to 0. The one with rec_internal is used within
 107              * the body, the other is what is used from the 'outside'. This
 108              * is necessary to break the cycles inherent in recursive
 109              * lenses with reference counting. The link through alias is
 110              * set up in lns_check_rec, and not reference counted.
 111              *
 112              * Generally, any lens used in the body of a recursive lens is
 113              * marked with rec_internal == 1; lenses that use the recursive
 114              * lens 'from the outside' are marked with rec_internal ==
 115              * 0. In the latter case, we can assign types right away,
 116              * except for the ctype, which we never have for any recursive
 117              * lens.
 118              */
 119             struct lens *alias;
 120         };
 121     };
 122 };
 123
 124 /* Constructors for various lens types. Constructor assumes ownership of
 125  * arguments without incrementing. Caller owns returned lenses.
 126  *
 127  * The return type is VALUE instead of LENS so that we can return an
 128  * exception iftypechecking fails.
 129  */
 130 struct value *lns_make_prim(enum lens_tag tag, struct info *info,
 131                             struct regexp *regexp, struct string *string);
 132 struct value *lns_make_union(struct info *, struct lens *, struct lens *,
 133                              int check);
 134 struct value *lns_make_concat(struct info *, struct lens *, struct lens *,
 135                               int check);
 136 struct value *lns_make_subtree(struct info *, struct lens *);
 137 struct value *lns_make_star(struct info *, struct lens *,
 138                             int check);
 139 struct value *lns_make_plus(struct info *, struct lens *,
 140                             int check);
 141 struct value *lns_make_maybe(struct info *, struct lens *,
 142                              int check);
 143 struct value *lns_make_square(struct info *, struct lens *, struct lens *,
 144                               struct lens *lens, int check);
 145
 146
 147 /* Pretty-print a lens */
 148 char *format_lens(struct lens *l);
 149
 150 /* Pretty-print the atype of a lens. Allocates BUF, which must be freed by
 151  * the caller */
 152 int lns_format_atype(struct lens *, char **buf);
 153
 154 /* Recursive lenses */
 155 struct value *lns_make_rec(struct info *info);
 156 struct value *lns_check_rec(struct info *info,
 157                             struct lens *body, struct lens *rec,
 158                             int check);
 159
 160 /* Auxiliary data structures used during get/put/create */
 161 struct skel {
 162     struct skel *next;
 163     enum lens_tag tag;
 164     union {
 165         char        *text;    /* L_DEL */
 166         struct skel *skels;   /* L_CONCAT, L_STAR, L_SQUARE */
 167     };
 168     /* Also tag == L_SUBTREE, with no data in the union */
 169 };
 170
 171 struct lns_error {
 172     struct lens  *lens;
 173     struct lens  *last;       /* The last lens that matched */
 174     struct lens  *next;       /* The next lens that should match but doesn't */
 175     int           pos;        /* Errors from get/parse */
 176     char         *path;       /* Errors from put, pos will be -1 */
 177     char         *message;
 178 };
 179
 180 struct dict *make_dict(char *key, struct skel *skel, struct dict *subdict);
 181 void dict_lookup(const char *key, struct dict *dict,
 182                  struct skel **skel, struct dict **subdict);
 183 int dict_append(struct dict **dict, struct dict *d2);
 184 void free_skel(struct skel *skel);
 185 void free_dict(struct dict *dict);
 186 void free_lns_error(struct lns_error *err);
 187
 188 /* Parse text TEXT with LENS. INFO indicats where TEXT was read from.
 189  *
 190  * If ERR is non-NULL, *ERR is set to NULL on success, and to an error
 191  * message on failure; the constructed tree is always returned. If ERR is
 192  * NULL, return the tree on success, and NULL on failure.
 193  *
 194  * FLAGS controls what is printed and should be a set of flags from enum
 195  * parse_flags
 196  */
 197 struct tree *lns_get(struct info *info, struct lens *lens, const char *text,
 198                      struct lns_error **err);
 199 struct skel *lns_parse(struct lens *lens, const char *text,
 200                        struct dict **dict, struct lns_error **err);
 201 void lns_put(FILE *out, struct lens *lens, struct tree *tree,
 202              const char *text, struct lns_error **err);
 203
 204 /* Free up temporary data structures, most importantly compiled
 205    regular expressions */
 206 void lens_release(struct lens *lens);
 207 void free_lens(struct lens *lens);
 208
 209 /*
 210  * Encoding of tree levels into strings
 211  */
 212
 213 /* Special characters used when encoding one level of the tree as a string.
 214  * We encode one tree node as KEY . ENC_EQ . VALUE . ENC_SLASH; if KEY or
 215  * VALUE are NULL, we use ENC_NULL, which is the empty string. This has the
 216  * effect that NULL strings are treated the same as empty strings.
 217  *
 218  * This encoding is used both for actual trees in the put direction, and to
 219  * produce regular expressions describing one level in the tree (we
 220  * disregard subtrees)
 221  *
 222  * For this to work, neither ENC_EQ nor ENC_SLASH can be allowed in a
 223  * VALUE; we do this behind the scenes by rewriting regular expressions for
 224  * values.
 225  */
 226 #define ENC_EQ        "\003"
 227 #define ENC_SLASH     "\004"
 228 #define ENC_NULL      ""
 229 #define ENC_EQ_CH     (ENC_EQ[0])
 230 #define ENC_SLASH_CH  (ENC_SLASH[0])
 231
 232 /* The reserved range of characters that we do not allow in user-supplied
 233    regular expressions, since we need them for internal bookkeeping.
 234
 235    This range must include the ENC_* characters
 236 */
 237 #define RESERVED_FROM '\001'
 238 #define RESERVED_TO   ENC_SLASH_CH
 239
 240 /* The length of the string S encoded */
 241 #define ENCLEN(s) ((s) == NULL ? strlen(ENC_NULL) : strlen(s))
 242 #define ENCSTR(s) ((s) == NULL ? ENC_NULL : s)
 243
 244 /* helper to access first and last child */
 245 #define child_first(l) (l)->children[0]
 246 #define child_last(l) (l)->children[(l)->nchildren - 1]
 247
 248 /* Format an encoded level as
 249  *    { key1 = value1 } { key2 = value2 } .. { keyN = valueN }
 250  */
 251 char *enc_format(const char *e, size_t len);
 252 /* Format an encoded level similar to ENC_FORMAT, but put each tree node
 253  * on a new line indented by INDENT spaces. If INDENT is negative, produce the
 254  * same output as ENC_FORMAT
 255  *    { key1 = value1 } { key2 = value2 } .. { keyN = valueN }
 256  */
 257 char *enc_format_indent(const char *e, size_t len, int indent);
 258
 259 #if ENABLE_DEBUG
 260 void dump_lens_tree(struct lens *lens);
 261 void dump_lens(FILE *out, struct lens *lens);
 262 #endif
 263
 264 #endif
 265
 266
 267 /*
 268  * Local variables:
 269  *  indent-tabs-mode: nil
 270  *  c-indent-level: 4
 271  *  c-basic-offset: 4
 272  *  tab-width: 4
 273  * End:
 274  */