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(const struct ec_node *node,
  62                                 struct ec_parsed *state,
  63                                 bool is_root, const struct ec_strvec *strvec)
  64 {
  65         struct ec_strvec *match_strvec;
  66         struct ec_parsed *child;
  67         int ret;
  68
  69         if (node->type->parse == NULL)
  70                 return -ENOTSUP;
  71
  72         if (!is_root) {
  73                 child = ec_parsed(node);
  74                 if (child == NULL)
  75                         return -ENOMEM;
  76
  77                 ec_parsed_add_child(state, child);
  78         } else {
  79                 child = state;
  80         }
  81         ret = node->type->parse(node, child, strvec);
  82         if (ret < 0) // XXX should we free state, child?
  83                 return ret;
  84
  85         if (ret == EC_PARSED_NOMATCH) {
  86                 if (!is_root) {
  87                         ec_parsed_del_child(state, child);
  88                         assert(TAILQ_EMPTY(&child->children));
  89                         ec_parsed_free(child);
  90                 }
  91                 return ret;
  92         }
  93
  94         match_strvec = ec_strvec_ndup(strvec, 0, ret);
  95         if (match_strvec == NULL)
  96                 return -ENOMEM;
  97
  98         child->strvec = match_strvec;
  99
 100         return ret;
 101 }
 102
 103 int ec_node_parse_child(const struct ec_node *node, struct ec_parsed *state,
 104                         const struct ec_strvec *strvec)
 105 {
 106         assert(state != NULL);
 107         return __ec_node_parse_child(node, state, false, strvec);
 108 }
 109
 110 struct ec_parsed *ec_node_parse_strvec(const struct ec_node *node,
 111                                 const struct ec_strvec *strvec)
 112 {
 113         struct ec_parsed *parsed = ec_parsed(node);
 114         int ret;
 115
 116         if (parsed == NULL)
 117                 return NULL;
 118
 119         ret = __ec_node_parse_child(node, parsed, true, strvec);
 120         if (ret < 0) {
 121                 ec_parsed_free(parsed);
 122                 return NULL;
 123         }
 124
 125         return parsed;
 126 }
 127
 128 struct ec_parsed *ec_node_parse(const struct ec_node *node, const char *str)
 129 {
 130         struct ec_strvec *strvec = NULL;
 131         struct ec_parsed *parsed = NULL;
 132
 133         errno = ENOMEM;
 134         strvec = ec_strvec();
 135         if (strvec == NULL)
 136                 goto fail;
 137
 138         if (ec_strvec_add(strvec, str) < 0)
 139                 goto fail;
 140
 141         parsed = ec_node_parse_strvec(node, strvec);
 142         if (parsed == NULL)
 143                 goto fail;
 144
 145         ec_strvec_free(strvec);
 146         return parsed;
 147
 148  fail:
 149         ec_strvec_free(strvec);
 150         ec_parsed_free(parsed);
 151         return NULL;
 152 }
 153
 154 struct ec_parsed *ec_parsed(const struct ec_node *node)
 155 {
 156         struct ec_parsed *parsed = NULL;
 157
 158         parsed = ec_calloc(1, sizeof(*parsed));
 159         if (parsed == NULL)
 160                 goto fail;
 161
 162         TAILQ_INIT(&parsed->children);
 163
 164         parsed->node = node;
 165         parsed->attrs = ec_keyval();
 166         if (parsed->attrs == NULL)
 167                 goto fail;
 168
 169         return parsed;
 170
 171  fail:
 172         if (parsed != NULL)
 173                 ec_keyval_free(parsed->attrs);
 174         ec_free(parsed);
 175
 176         return NULL;
 177 }
 178
 179 static struct ec_parsed *
 180 __ec_parsed_dup(const struct ec_parsed *root, const struct ec_parsed *ref,
 181                 struct ec_parsed **new_ref)
 182 {
 183         struct ec_parsed *dup = NULL;
 184         struct ec_parsed *child, *dup_child;
 185         struct ec_keyval *attrs = NULL;
 186
 187         if (root == NULL)
 188                 return NULL;
 189
 190         dup = ec_parsed(root->node);
 191         if (dup == NULL)
 192                 return NULL;
 193
 194         if (root == ref)
 195                 *new_ref = dup;
 196
 197         attrs = ec_keyval_dup(root->attrs);
 198         if (attrs == NULL)
 199                 goto fail;
 200         ec_keyval_free(dup->attrs);
 201         dup->attrs = attrs;
 202
 203         if (root->strvec != NULL) {
 204                 dup->strvec = ec_strvec_dup(root->strvec);
 205                 if (dup->strvec == NULL)
 206                         goto fail;
 207         }
 208
 209         TAILQ_FOREACH(child, &root->children, next) {
 210                 dup_child = __ec_parsed_dup(child, ref, new_ref);
 211                 if (dup_child == NULL)
 212                         goto fail;
 213                 ec_parsed_add_child(dup, dup_child);
 214         }
 215
 216         return dup;
 217
 218 fail:
 219         ec_parsed_free(dup);
 220         return NULL;
 221 }
 222
 223 struct ec_parsed *ec_parsed_dup(struct ec_parsed *parsed) //XXX const
 224 {
 225         struct ec_parsed *root, *dup_root, *dup = NULL;
 226
 227         root = ec_parsed_get_root(parsed);
 228         dup_root = __ec_parsed_dup(root, parsed, &dup);
 229         if (dup_root == NULL)
 230                 return NULL;
 231         assert(dup != NULL);
 232
 233         return dup;
 234 }
 235
 236 void ec_parsed_free_children(struct ec_parsed *parsed)
 237 {
 238         struct ec_parsed *child;
 239
 240         if (parsed == NULL)
 241                 return;
 242
 243         while (!TAILQ_EMPTY(&parsed->children)) {
 244                 child = TAILQ_FIRST(&parsed->children);
 245                 TAILQ_REMOVE(&parsed->children, child, next);
 246                 ec_parsed_free(child);
 247         }
 248 }
 249
 250 void ec_parsed_free(struct ec_parsed *parsed)
 251 {
 252         if (parsed == NULL)
 253                 return;
 254
 255         // assert(parsed->parent == NULL); XXX
 256         // or
 257         // parsed = ec_parsed_get_root(parsed);
 258
 259         ec_parsed_free_children(parsed);
 260         ec_strvec_free(parsed->strvec);
 261         ec_keyval_free(parsed->attrs);
 262         ec_free(parsed);
 263 }
 264
 265 static void __ec_parsed_dump(FILE *out,
 266         const struct ec_parsed *parsed, size_t indent)
 267 {
 268         struct ec_parsed *child;
 269         const struct ec_strvec *vec;
 270         size_t i;
 271         const char *id = "none", *typename = "none";
 272
 273         if (parsed->node != NULL) {
 274                 if (parsed->node->id != NULL)
 275                         id = parsed->node->id;
 276                 typename = parsed->node->type->name;
 277         }
 278
 279         /* XXX enhance */
 280         for (i = 0; i < indent; i++) {
 281                 if (i % 2)
 282                         fprintf(out, " ");
 283                 else
 284                         fprintf(out, "|");
 285         }
 286
 287         fprintf(out, "node_type=%s id=%s vec=", typename, id);
 288         vec = ec_parsed_strvec(parsed);
 289         ec_strvec_dump(out, vec);
 290
 291         TAILQ_FOREACH(child, &parsed->children, next)
 292                 __ec_parsed_dump(out, child, indent + 2);
 293 }
 294
 295 void ec_parsed_dump(FILE *out, const struct ec_parsed *parsed)
 296 {
 297         fprintf(out, "------------------- parsed dump:\n"); //XXX
 298
 299         if (parsed == NULL) {
 300                 fprintf(out, "parsed is NULL, error in parse\n");
 301                 return;
 302         }
 303
 304         /* only exist if it does not match (strvec == NULL) and if it
 305          * does not have children: an incomplete parse, like those
 306          * generated by complete() don't match but have children that
 307          * may match. */
 308         if (!ec_parsed_matches(parsed) && TAILQ_EMPTY(&parsed->children)) {
 309                 fprintf(out, "no match\n");
 310                 return;
 311         }
 312
 313         __ec_parsed_dump(out, parsed, 0);
 314 }
 315
 316 void ec_parsed_add_child(struct ec_parsed *parsed,
 317         struct ec_parsed *child)
 318 {
 319         TAILQ_INSERT_TAIL(&parsed->children, child, next);
 320         child->parent = parsed;
 321 }
 322
 323 // XXX we can remove the first arg ? parsed == child->parent ?
 324 void ec_parsed_del_child(struct ec_parsed *parsed, // XXX rename del in unlink?
 325         struct ec_parsed *child)
 326 {
 327         TAILQ_REMOVE(&parsed->children, child, next);
 328         child->parent = NULL;
 329 }
 330
 331 struct ec_parsed *
 332 ec_parsed_get_first_child(const struct ec_parsed *parsed)
 333 {
 334         return TAILQ_FIRST(&parsed->children);
 335 }
 336
 337 struct ec_parsed *
 338 ec_parsed_get_last_child(const struct ec_parsed *parsed)
 339 {
 340         return TAILQ_LAST(&parsed->children, ec_parsed_list);
 341 }
 342
 343 struct ec_parsed *ec_parsed_get_next(const struct ec_parsed *parsed)
 344 {
 345         return TAILQ_NEXT(parsed, next);
 346 }
 347
 348 bool ec_parsed_has_child(const struct ec_parsed *parsed)
 349 {
 350         return !TAILQ_EMPTY(&parsed->children);
 351 }
 352
 353 const struct ec_node *ec_parsed_get_node(const struct ec_parsed *parsed)
 354 {
 355         return parsed->node;
 356 }
 357
 358 void ec_parsed_del_last_child(struct ec_parsed *parsed) // rename in free
 359 {
 360         struct ec_parsed *child;
 361
 362         child = ec_parsed_get_last_child(parsed);
 363         ec_parsed_del_child(parsed, child);
 364         ec_parsed_free(child);
 365 }
 366
 367 struct ec_parsed *ec_parsed_get_root(struct ec_parsed *parsed)
 368 {
 369         if (parsed == NULL)
 370                 return NULL;
 371
 372         while (parsed->parent != NULL)
 373                 parsed = parsed->parent;
 374
 375         return parsed;
 376 }
 377
 378 struct ec_parsed *ec_parsed_get_parent(struct ec_parsed *parsed)
 379 {
 380         if (parsed == NULL)
 381                 return NULL;
 382
 383         return parsed->parent;
 384 }
 385
 386 struct ec_parsed *ec_parsed_iter_next(struct ec_parsed *parsed)
 387 {
 388         struct ec_parsed *child, *parent, *next;
 389
 390         child = TAILQ_FIRST(&parsed->children);
 391         if (child != NULL)
 392                 return child;
 393         parent = parsed->parent;
 394         while (parent != NULL) {
 395                 next = TAILQ_NEXT(parsed, next);
 396                 if (next != NULL)
 397                         return next;
 398                 parsed = parent;
 399                 parent = parsed->parent;
 400         }
 401         return NULL;
 402 }
 403
 404 struct ec_parsed *ec_parsed_find_first(struct ec_parsed *parsed,
 405         const char *id)
 406 {
 407         struct ec_parsed *child, *ret;
 408
 409         if (parsed == NULL)
 410                 return NULL;
 411
 412         if (parsed->node != NULL &&
 413                         parsed->node->id != NULL &&
 414                         !strcmp(parsed->node->id, id))
 415                 return parsed;
 416
 417         TAILQ_FOREACH(child, &parsed->children, next) {
 418                 ret = ec_parsed_find_first(child, id);
 419                 if (ret != NULL)
 420                         return ret;
 421         }
 422
 423         return NULL;
 424 }
 425
 426 struct ec_keyval *
 427 ec_parsed_get_attrs(struct ec_parsed *parsed)
 428 {
 429         if (parsed == NULL)
 430                 return NULL;
 431
 432         return parsed->attrs;
 433 }
 434
 435 const struct ec_strvec *ec_parsed_strvec(const struct ec_parsed *parsed)
 436 {
 437         if (parsed == NULL || parsed->strvec == NULL)
 438                 return NULL;
 439
 440         return parsed->strvec;
 441 }
 442
 443 /* number of strings in the parsed vector */
 444 size_t ec_parsed_len(const struct ec_parsed *parsed)
 445 {
 446         if (parsed == NULL || parsed->strvec == NULL)
 447                 return 0;
 448
 449         return ec_strvec_len(parsed->strvec);
 450 }
 451
 452 size_t ec_parsed_matches(const struct ec_parsed *parsed)
 453 {
 454         if (parsed == NULL)
 455                 return 0;
 456
 457         if (parsed->strvec == NULL)
 458                 return 0;
 459
 460         return 1;
 461 }