src/lens.h

   1 /*
   2  * lens.h: Repreentation of lenses
   3  *
   4  * Copyright (C) 2007-2011 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     unsigned int              value : 1;
  83     unsigned int              key : 1;
  84     unsigned int              recursive : 1;
  85     unsigned int              consumes_value : 1;
  86     /* Whether we are inside a recursive lens or outside */
  87     unsigned int              rec_internal : 1;
  88     unsigned int              ctype_nullable : 1;
  89     union {
  90         /* Primitive lenses */
  91         struct {                   /* L_DEL uses both */
  92             /* L_DEL string set to NULL means it belongs to parent L_SQUARE lens
  93              * and the put and create copy the current key
  94              */
  95             struct regexp *regexp; /* L_STORE, L_KEY */
  96             struct string *string; /* L_VALUE, L_LABEL, L_SEQ, L_COUNTER */
  97         };
  98         /* Combinators */
  99         struct lens *child;         /* L_SUBTREE, L_STAR, L_MAYBE, L_SQUARE */
 100         struct {                    /* L_UNION, L_CONCAT */
 101             unsigned int nchildren;
 102             struct lens **children;
 103         };
 104         struct {
 105             struct lens *body;      /* L_REC */
 106             /* We represent a recursive lens as two instances of struct
 107              * lens with L_REC. One has rec_internal set to 1, the other
 108              * has it set to 0. The one with rec_internal is used within
 109              * the body, the other is what is used from the 'outside'. This
 110              * is necessary to break the cycles inherent in recursive
 111              * lenses with reference counting. The link through alias is
 112              * set up in lns_check_rec, and not reference counted.
 113              *
 114              * Generally, any lens used in the body of a recursive lens is
 115              * marked with rec_internal == 1; lenses that use the recursive
 116              * lens 'from the outside' are marked with rec_internal ==
 117              * 0. In the latter case, we can assign types right away,
 118              * except for the ctype, which we never have for any recursive
 119              * lens.
 120              */
 121             struct lens *alias;
 122             struct jmt  *jmt;
 123         };
 124     };
 125 };
 126
 127 /* Constructors for various lens types. Constructor assumes ownership of
 128  * arguments without incrementing. Caller owns returned lenses.
 129  *
 130  * The return type is VALUE instead of LENS so that we can return an
 131  * exception iftypechecking fails.
 132  */
 133 struct value *lns_make_prim(enum lens_tag tag, struct info *info,
 134                             struct regexp *regexp, struct string *string);
 135 struct value *lns_make_union(struct info *, struct lens *, struct lens *,
 136                              int check);
 137 struct value *lns_make_concat(struct info *, struct lens *, struct lens *,
 138                               int check);
 139 struct value *lns_make_subtree(struct info *, struct lens *);
 140 struct value *lns_make_star(struct info *, struct lens *,
 141                             int check);
 142 struct value *lns_make_plus(struct info *, struct lens *,
 143                             int check);
 144 struct value *lns_make_maybe(struct info *, struct lens *,
 145                              int check);
 146 struct value *lns_make_square(struct info *, struct regexp *, struct lens *,
 147                               int check);
 148
 149 /* Pretty-print a lens */
 150 char *format_lens(struct lens *l);
 151
 152 /* Pretty-print the atype of a lens. Allocates BUF, which must be freed by
 153  * the caller */
 154 int lns_format_atype(struct lens *, char **buf);
 155
 156 /* Recursive lenses */
 157 struct value *lns_make_rec(struct info *info);
 158 struct value *lns_check_rec(struct info *info,
 159                             struct lens *body, struct lens *rec,
 160                             int check);
 161
 162 /* Auxiliary data structures used during get/put/create */
 163 struct skel {
 164     struct skel *next;
 165     enum lens_tag tag;
 166     union {
 167         char        *text;    /* L_DEL */
 168         struct skel *skels;   /* L_CONCAT, L_STAR */
 169     };
 170     /* Also tag == L_SUBTREE, with no data in the union */
 171 };
 172
 173 struct lns_error {
 174     struct lens  *lens;
 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 /* Format an encoded level as
 245  *    { key1 = value1 } { key2 = value2 } .. { keyN = valueN }
 246  */
 247 char *enc_format(const char *e, size_t len);
 248
 249 #if ENABLE_DEBUG
 250 void dump_lens_tree(struct lens *lens);
 251 void dump_lens(FILE *out, struct lens *lens);
 252 #endif
 253
 254 #endif
 255
 256
 257 /*
 258  * Local variables:
 259  *  indent-tabs-mode: nil
 260  *  c-indent-level: 4
 261  *  c-basic-offset: 4
 262  *  tab-width: 4
 263  * End:
 264  */