lib/ecoli_parsed.c

   1 /*
   2  * Copyright (c) 2016, Olivier MATZ <zer0@droids-corp.org>
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of the University of California, Berkeley nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include <stdint.h>
  31 #include <string.h>
  32 #include <assert.h>
  33 #include <errno.h>
  34
  35 #include <ecoli_assert.h>
  36 #include <ecoli_malloc.h>
  37 #include <ecoli_strvec.h>
  38 #include <ecoli_keyval.h>
  39 #include <ecoli_log.h>
  40 #include <ecoli_node.h>
  41 #include <ecoli_parsed.h>
  42
  43 TAILQ_HEAD(ec_parsed_list, ec_parsed);
  44
  45 /* XXX idea for parse: maintain a "cursor" ?
  46 struct ec_parsed {
  47    struct ec_parsed_tree *root;
  48    stuct ec_parsed_tree *cursor;
  49 };
  50 */
  51
  52 struct ec_parsed {
  53         TAILQ_ENTRY(ec_parsed) next;
  54         struct ec_parsed_list children;
  55         struct ec_parsed *parent;
  56         const struct ec_node *node;
  57         struct ec_strvec *strvec;
  58         struct ec_keyval *attrs;
  59 };
  60
  61 static int __ec_node_parse_child(struct ec_node *node, struct ec_parsed *state,
  62                                 bool is_root, const struct ec_strvec *strvec)
  63 {
  64         struct ec_strvec *match_strvec;
  65         struct ec_parsed *child;
  66         int ret;
  67
  68         /* build the node if required */
  69         if (node->type->build != NULL) {
  70                 if ((node->flags & EC_NODE_F_BUILT) == 0) {
  71                         ret = node->type->build(node);
  72                         if (ret < 0)
  73                                 return ret;
  74                 }
  75         }
  76         node->flags |= EC_NODE_F_BUILT;
  77
  78         if (node->type->parse == NULL)
  79                 return -ENOTSUP;
  80
  81         if (!is_root) {
  82                 child = ec_parsed(node);
  83                 if (child == NULL)
  84                         return -ENOMEM;
  85
  86                 ec_parsed_add_child(state, child);
  87         } else {
  88                 child = state;
  89         }
  90         ret = node->type->parse(node, child, strvec);
  91         if (ret < 0) // XXX should we free state, child?
  92                 return ret;
  93
  94         if (ret == EC_PARSED_NOMATCH) {
  95                 if (!is_root) {
  96                         ec_parsed_del_child(state, child);
  97                         assert(TAILQ_EMPTY(&child->children));
  98                         ec_parsed_free(child);
  99                 }
 100                 return ret;
 101         }
 102
 103         match_strvec = ec_strvec_ndup(strvec, 0, ret);
 104         if (match_strvec == NULL)
 105                 return -ENOMEM;
 106
 107         child->strvec = match_strvec;
 108
 109         return ret;
 110 }
 111
 112 int ec_node_parse_child(struct ec_node *node, struct ec_parsed *state,
 113                         const struct ec_strvec *strvec)
 114 {
 115         assert(state != NULL);
 116         return __ec_node_parse_child(node, state, false, strvec);
 117 }
 118
 119 struct ec_parsed *ec_node_parse_strvec(struct ec_node *node,
 120                                 const struct ec_strvec *strvec)
 121 {
 122         struct ec_parsed *parsed = ec_parsed(node);
 123         int ret;
 124
 125         if (parsed == NULL)
 126                 return NULL;
 127
 128         ret = __ec_node_parse_child(node, parsed, true, strvec);
 129         if (ret < 0) {
 130                 ec_parsed_free(parsed);
 131                 return NULL;
 132         }
 133
 134         return parsed;
 135 }
 136
 137 struct ec_parsed *ec_node_parse(struct ec_node *node, const char *str)
 138 {
 139         struct ec_strvec *strvec = NULL;
 140         struct ec_parsed *parsed = NULL;
 141
 142         errno = ENOMEM;
 143         strvec = ec_strvec();
 144         if (strvec == NULL)
 145                 goto fail;
 146
 147         if (ec_strvec_add(strvec, str) < 0)
 148                 goto fail;
 149
 150         parsed = ec_node_parse_strvec(node, strvec);
 151         if (parsed == NULL)
 152                 goto fail;
 153
 154         ec_strvec_free(strvec);
 155         return parsed;
 156
 157  fail:
 158         ec_strvec_free(strvec);
 159         ec_parsed_free(parsed);
 160         return NULL;
 161 }
 162
 163 struct ec_parsed *ec_parsed(const struct ec_node *node)
 164 {
 165         struct ec_parsed *parsed = NULL;
 166
 167         parsed = ec_calloc(1, sizeof(*parsed));
 168         if (parsed == NULL)
 169                 goto fail;
 170
 171         TAILQ_INIT(&parsed->children);
 172
 173         parsed->node = node;
 174         parsed->attrs = ec_keyval();
 175         if (parsed->attrs == NULL)
 176                 goto fail;
 177
 178         return parsed;
 179
 180  fail:
 181         if (parsed != NULL)
 182                 ec_keyval_free(parsed->attrs);
 183         ec_free(parsed);
 184
 185         return NULL;
 186 }
 187
 188 static struct ec_parsed *
 189 __ec_parsed_dup(const struct ec_parsed *root, const struct ec_parsed *ref,
 190                 struct ec_parsed **new_ref)
 191 {
 192         struct ec_parsed *dup = NULL;
 193         struct ec_parsed *child, *dup_child;
 194         struct ec_keyval *attrs = NULL;
 195
 196         if (root == NULL)
 197                 return NULL;
 198
 199         dup = ec_parsed(root->node);
 200         if (dup == NULL)
 201                 return NULL;
 202
 203         if (root == ref)
 204                 *new_ref = dup;
 205
 206         attrs = ec_keyval_dup(root->attrs);
 207         if (attrs == NULL)
 208                 goto fail;
 209         ec_keyval_free(dup->attrs);
 210         dup->attrs = attrs;
 211
 212         if (root->strvec != NULL) {
 213                 dup->strvec = ec_strvec_dup(root->strvec);
 214                 if (dup->strvec == NULL)
 215                         goto fail;
 216         }
 217
 218         TAILQ_FOREACH(child, &root->children, next) {
 219                 dup_child = __ec_parsed_dup(child, ref, new_ref);
 220                 if (dup_child == NULL)
 221                         goto fail;
 222                 ec_parsed_add_child(dup, dup_child);
 223         }
 224
 225         return dup;
 226
 227 fail:
 228         ec_parsed_free(dup);
 229         return NULL;
 230 }
 231
 232 struct ec_parsed *ec_parsed_dup(struct ec_parsed *parsed) //XXX const
 233 {
 234         struct ec_parsed *root, *dup_root, *dup = NULL;
 235
 236         root = ec_parsed_get_root(parsed);
 237         dup_root = __ec_parsed_dup(root, parsed, &dup);
 238         if (dup_root == NULL)
 239                 return NULL;
 240         assert(dup != NULL);
 241
 242         return dup;
 243 }
 244
 245 void ec_parsed_free_children(struct ec_parsed *parsed)
 246 {
 247         struct ec_parsed *child;
 248
 249         if (parsed == NULL)
 250                 return;
 251
 252         while (!TAILQ_EMPTY(&parsed->children)) {
 253                 child = TAILQ_FIRST(&parsed->children);
 254                 TAILQ_REMOVE(&parsed->children, child, next);
 255                 ec_parsed_free(child);
 256         }
 257 }
 258
 259 void ec_parsed_free(struct ec_parsed *parsed)
 260 {
 261         if (parsed == NULL)
 262                 return;
 263
 264         // assert(parsed->parent == NULL); XXX
 265         // or
 266         // parsed = ec_parsed_get_root(parsed);
 267
 268         ec_parsed_free_children(parsed);
 269         ec_strvec_free(parsed->strvec);
 270         ec_keyval_free(parsed->attrs);
 271         ec_free(parsed);
 272 }
 273
 274 static void __ec_parsed_dump(FILE *out,
 275         const struct ec_parsed *parsed, size_t indent)
 276 {
 277         struct ec_parsed *child;
 278         const struct ec_strvec *vec;
 279         size_t i;
 280         const char *id = "none", *typename = "none";
 281
 282         if (parsed->node != NULL) {
 283                 if (parsed->node->id != NULL)
 284                         id = parsed->node->id;
 285                 typename = parsed->node->type->name;
 286         }
 287
 288         /* XXX enhance */
 289         for (i = 0; i < indent; i++) {
 290                 if (i % 2)
 291                         fprintf(out, " ");
 292                 else
 293                         fprintf(out, "|");
 294         }
 295
 296         fprintf(out, "node_type=%s id=%s vec=", typename, id);
 297         vec = ec_parsed_strvec(parsed);
 298         ec_strvec_dump(out, vec);
 299
 300         TAILQ_FOREACH(child, &parsed->children, next)
 301                 __ec_parsed_dump(out, child, indent + 2);
 302 }
 303
 304 void ec_parsed_dump(FILE *out, const struct ec_parsed *parsed)
 305 {
 306         fprintf(out, "------------------- parsed dump:\n"); //XXX
 307
 308         if (parsed == NULL) {
 309                 fprintf(out, "parsed is NULL, error in parse\n");
 310                 return;
 311         }
 312
 313         /* only exist if it does not match (strvec == NULL) and if it
 314          * does not have children: an incomplete parse, like those
 315          * generated by complete() don't match but have children that
 316          * may match. */
 317         if (!ec_parsed_matches(parsed) && TAILQ_EMPTY(&parsed->children)) {
 318                 fprintf(out, "no match\n");
 319                 return;
 320         }
 321
 322         __ec_parsed_dump(out, parsed, 0);
 323 }
 324
 325 void ec_parsed_add_child(struct ec_parsed *parsed,
 326         struct ec_parsed *child)
 327 {
 328         TAILQ_INSERT_TAIL(&parsed->children, child, next);
 329         child->parent = parsed;
 330 }
 331
 332 // XXX we can remove the first arg ? parsed == child->parent ?
 333 void ec_parsed_del_child(struct ec_parsed *parsed, // XXX rename del in unlink?
 334         struct ec_parsed *child)
 335 {
 336         TAILQ_REMOVE(&parsed->children, child, next);
 337         child->parent = NULL;
 338 }
 339
 340 struct ec_parsed *
 341 ec_parsed_get_first_child(const struct ec_parsed *parsed)
 342 {
 343         return TAILQ_FIRST(&parsed->children);
 344 }
 345
 346 struct ec_parsed *
 347 ec_parsed_get_last_child(const struct ec_parsed *parsed)
 348 {
 349         return TAILQ_LAST(&parsed->children, ec_parsed_list);
 350 }
 351
 352 struct ec_parsed *ec_parsed_get_next(const struct ec_parsed *parsed)
 353 {
 354         return TAILQ_NEXT(parsed, next);
 355 }
 356
 357 bool ec_parsed_has_child(const struct ec_parsed *parsed)
 358 {
 359         return !TAILQ_EMPTY(&parsed->children);
 360 }
 361
 362 const struct ec_node *ec_parsed_get_node(const struct ec_parsed *parsed)
 363 {
 364         return parsed->node;
 365 }
 366
 367 void ec_parsed_del_last_child(struct ec_parsed *parsed) // rename in free
 368 {
 369         struct ec_parsed *child;
 370
 371         child = ec_parsed_get_last_child(parsed);
 372         ec_parsed_del_child(parsed, child);
 373         ec_parsed_free(child);
 374 }
 375
 376 struct ec_parsed *ec_parsed_get_root(struct ec_parsed *parsed)
 377 {
 378         if (parsed == NULL)
 379                 return NULL;
 380
 381         while (parsed->parent != NULL)
 382                 parsed = parsed->parent;
 383
 384         return parsed;
 385 }
 386
 387 struct ec_parsed *ec_parsed_get_parent(struct ec_parsed *parsed)
 388 {
 389         if (parsed == NULL)
 390                 return NULL;
 391
 392         return parsed->parent;
 393 }
 394
 395 struct ec_parsed *ec_parsed_iter_next(struct ec_parsed *parsed)
 396 {
 397         struct ec_parsed *child, *parent, *next;
 398
 399         child = TAILQ_FIRST(&parsed->children);
 400         if (child != NULL)
 401                 return child;
 402         parent = parsed->parent;
 403         while (parent != NULL) {
 404                 next = TAILQ_NEXT(parsed, next);
 405                 if (next != NULL)
 406                         return next;
 407                 parsed = parent;
 408                 parent = parsed->parent;
 409         }
 410         return NULL;
 411 }
 412
 413 struct ec_parsed *ec_parsed_find_first(struct ec_parsed *parsed,
 414         const char *id)
 415 {
 416         struct ec_parsed *child, *ret;
 417
 418         if (parsed == NULL)
 419                 return NULL;
 420
 421         if (parsed->node != NULL &&
 422                         parsed->node->id != NULL &&
 423                         !strcmp(parsed->node->id, id))
 424                 return parsed;
 425
 426         TAILQ_FOREACH(child, &parsed->children, next) {
 427                 ret = ec_parsed_find_first(child, id);
 428                 if (ret != NULL)
 429                         return ret;
 430         }
 431
 432         return NULL;
 433 }
 434
 435 struct ec_keyval *
 436 ec_parsed_get_attrs(struct ec_parsed *parsed)
 437 {
 438         if (parsed == NULL)
 439                 return NULL;
 440
 441         return parsed->attrs;
 442 }
 443
 444 const struct ec_strvec *ec_parsed_strvec(const struct ec_parsed *parsed)
 445 {
 446         if (parsed == NULL || parsed->strvec == NULL)
 447                 return NULL;
 448
 449         return parsed->strvec;
 450 }
 451
 452 /* number of strings in the parsed vector */
 453 size_t ec_parsed_len(const struct ec_parsed *parsed)
 454 {
 455         if (parsed == NULL || parsed->strvec == NULL)
 456                 return 0;
 457
 458         return ec_strvec_len(parsed->strvec);
 459 }
 460
 461 size_t ec_parsed_matches(const struct ec_parsed *parsed)
 462 {
 463         if (parsed == NULL)
 464                 return 0;
 465
 466         if (parsed->strvec == NULL)
 467                 return 0;
 468
 469         return 1;
 470 }