lib/ecoli_node.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 <string.h>
  31 #include <assert.h>
  32 #include <errno.h>
  33
  34 #include <ecoli_malloc.h>
  35 #include <ecoli_strvec.h>
  36 #include <ecoli_keyval.h>
  37 #include <ecoli_log.h>
  38 #include <ecoli_node.h>
  39
  40 static struct ec_node_type_list node_type_list =
  41         TAILQ_HEAD_INITIALIZER(node_type_list);
  42
  43 struct ec_node_type *ec_node_type_lookup(const char *name)
  44 {
  45         struct ec_node_type *type;
  46
  47         TAILQ_FOREACH(type, &node_type_list, next) {
  48                 if (!strcmp(name, type->name))
  49                         return type;
  50         }
  51
  52         return NULL;
  53 }
  54
  55 int ec_node_type_register(struct ec_node_type *type)
  56 {
  57         if (ec_node_type_lookup(type->name) != NULL)
  58                 return -EEXIST;
  59         if (type->size < sizeof(struct ec_node))
  60                 return -EINVAL;
  61
  62         TAILQ_INSERT_TAIL(&node_type_list, type, next);
  63
  64         return 0;
  65 }
  66
  67 void ec_node_type_dump(FILE *out)
  68 {
  69         struct ec_node_type *type;
  70
  71         TAILQ_FOREACH(type, &node_type_list, next)
  72                 fprintf(out, "%s\n", type->name);
  73 }
  74
  75 struct ec_node *__ec_node(const struct ec_node_type *type, const char *id)
  76 {
  77         struct ec_node *node = NULL;
  78         char buf[256]; // XXX
  79
  80         ec_log(EC_LOG_DEBUG, "create node type=%s id=%s\n", type->name, id);
  81
  82         node = ec_calloc(1, type->size);
  83         if (node == NULL)
  84                 goto fail;
  85
  86         TAILQ_INIT(&node->children);
  87         node->type = type;
  88         node->refcnt = 1;
  89
  90         if (id != NULL) {
  91                 node->id = ec_strdup(id);
  92                 if (node->id == NULL)
  93                         goto fail;
  94         }
  95
  96         snprintf(buf, sizeof(buf), "<%s>", type->name);
  97         node->desc = ec_strdup(buf); // XXX ec_asprintf ?
  98         if (node->desc == NULL)
  99                 goto fail;
 100
 101         node->attrs = ec_keyval();
 102         if (node->attrs == NULL)
 103                 goto fail;
 104
 105         return node;
 106
 107  fail:
 108         ec_node_free(node);
 109         return NULL;
 110 }
 111
 112 struct ec_node *ec_node(const char *typename, const char *id)
 113 {
 114         struct ec_node_type *type;
 115
 116         type = ec_node_type_lookup(typename);
 117         if (type == NULL) {
 118                 ec_log(EC_LOG_ERR, "type=%s does not exist\n", typename);
 119                 return NULL;
 120         }
 121
 122         return __ec_node(type, id);
 123 }
 124
 125 void ec_node_free(struct ec_node *node)
 126 {
 127         if (node == NULL)
 128                 return;
 129
 130         assert(node->refcnt > 0);
 131
 132         if (--node->refcnt > 0)
 133                 return;
 134
 135         if (node->type != NULL && node->type->free_priv != NULL)
 136                 node->type->free_priv(node);
 137         ec_free(node->id);
 138         ec_free(node->desc);
 139         ec_free(node->attrs);
 140         ec_free(node);
 141 }
 142
 143 struct ec_node *ec_node_clone(struct ec_node *node)
 144 {
 145         if (node != NULL)
 146                 node->refcnt++;
 147         return node;
 148 }
 149
 150 struct ec_node *ec_node_find(struct ec_node *node, const char *id)
 151 {
 152         struct ec_node *child, *ret;
 153         const char *node_id = ec_node_id(node);
 154
 155         if (id != NULL && node_id != NULL && !strcmp(node_id, id))
 156                 return node;
 157
 158         TAILQ_FOREACH(child, &node->children, next) {
 159                 ret = ec_node_find(child, id);
 160                 if (ret != NULL)
 161                         return ret;
 162         }
 163
 164         return NULL;
 165 }
 166
 167 struct ec_keyval *ec_node_attrs(const struct ec_node *node)
 168 {
 169         return node->attrs;
 170 }
 171
 172 const char *ec_node_id(const struct ec_node *node)
 173 {
 174         return node->id;
 175 }
 176
 177 struct ec_node *ec_node_parent(const struct ec_node *node)
 178 {
 179         return node->parent;
 180 }
 181
 182 static void __ec_node_dump(FILE *out,
 183         const struct ec_node *node, size_t indent)
 184 {
 185         struct ec_node *child;
 186         size_t i;
 187         const char *id = "None", *typename = "None";
 188
 189         if (node->id != NULL)
 190                 id = node->id;
 191         typename = node->type->name;
 192
 193         /* XXX enhance */
 194         for (i = 0; i < indent; i++) {
 195                 if (i % 2)
 196                         fprintf(out, " ");
 197                 else
 198                         fprintf(out, "|");
 199         }
 200
 201         fprintf(out, "node_type=%s id=%s\n", typename, id);
 202         TAILQ_FOREACH(child, &node->children, next)
 203                 __ec_node_dump(out, child, indent + 2);
 204 }
 205
 206 void ec_node_dump(FILE *out, const struct ec_node *node)
 207 {
 208         fprintf(out, "------------------- node dump:\n"); //XXX
 209
 210         if (node == NULL) {
 211                 fprintf(out, "node is NULL\n");
 212                 return;
 213         }
 214
 215         __ec_node_dump(out, node, 0);
 216 }
 217
 218 struct ec_parsed *ec_node_parse(struct ec_node *node, const char *str)
 219 {
 220         struct ec_strvec *strvec = NULL;
 221         struct ec_parsed *parsed;
 222
 223         errno = ENOMEM;
 224         strvec = ec_strvec();
 225         if (strvec == NULL)
 226                 goto fail;
 227
 228         if (ec_strvec_add(strvec, str) < 0)
 229                 goto fail;
 230
 231         parsed = ec_node_parse_strvec(node, strvec);
 232         if (parsed == NULL)
 233                 goto fail;
 234
 235         ec_strvec_free(strvec);
 236         return parsed;
 237
 238  fail:
 239         ec_strvec_free(strvec);
 240         return NULL;
 241 }
 242
 243 struct ec_parsed *ec_node_parse_strvec(struct ec_node *node,
 244         const struct ec_strvec *strvec)
 245 {
 246         struct ec_parsed *parsed;
 247         int ret;
 248
 249         /* build the node if required */
 250         if (node->type->build != NULL) {
 251                 if ((node->flags & EC_NODE_F_BUILT) == 0) {
 252                         ret = node->type->build(node);
 253                         if (ret < 0) {
 254                                 errno = -ret;
 255                                 return NULL;
 256                         }
 257                 }
 258         }
 259         node->flags |= EC_NODE_F_BUILT;
 260
 261         if (node->type->parse == NULL) {
 262                 errno = ENOTSUP;
 263                 return NULL;
 264         }
 265
 266         parsed = node->type->parse(node, strvec);
 267
 268         return parsed;
 269 }
 270
 271
 272 struct ec_parsed *ec_parsed(void)
 273 {
 274         struct ec_parsed *parsed = NULL;
 275
 276         parsed = ec_calloc(1, sizeof(*parsed));
 277         if (parsed == NULL)
 278                 goto fail;
 279
 280         TAILQ_INIT(&parsed->children);
 281
 282         return parsed;
 283
 284  fail:
 285         return NULL;
 286 }
 287
 288 void ec_parsed_set_match(struct ec_parsed *parsed,
 289         const struct ec_node *node, struct ec_strvec *strvec)
 290 {
 291         parsed->node = node;
 292         parsed->strvec = strvec;
 293 }
 294
 295 void ec_parsed_free_children(struct ec_parsed *parsed)
 296 {
 297         struct ec_parsed *child;
 298
 299         if (parsed == NULL)
 300                 return;
 301
 302         while (!TAILQ_EMPTY(&parsed->children)) {
 303                 child = TAILQ_FIRST(&parsed->children);
 304                 TAILQ_REMOVE(&parsed->children, child, next);
 305                 ec_parsed_free(child);
 306         }
 307 }
 308
 309 void ec_parsed_free(struct ec_parsed *parsed)
 310 {
 311         if (parsed == NULL)
 312                 return;
 313
 314         ec_parsed_free_children(parsed);
 315         ec_strvec_free(parsed->strvec);
 316         ec_free(parsed);
 317 }
 318
 319 static void __ec_parsed_dump(FILE *out,
 320         const struct ec_parsed *parsed, size_t indent)
 321 {
 322         struct ec_parsed *child;
 323         const struct ec_strvec *vec;
 324         size_t i;
 325         const char *id = "None", *typename = "None";
 326
 327         if (parsed->node != NULL) {
 328                 if (parsed->node->id != NULL)
 329                         id = parsed->node->id;
 330                 typename = parsed->node->type->name;
 331         }
 332
 333         /* XXX enhance */
 334         for (i = 0; i < indent; i++) {
 335                 if (i % 2)
 336                         fprintf(out, " ");
 337                 else
 338                         fprintf(out, "|");
 339         }
 340
 341         fprintf(out, "node_type=%s id=%s vec=[", typename, id);
 342         vec = ec_parsed_strvec(parsed);
 343         for (i = 0; i < ec_strvec_len(vec); i++)
 344                 fprintf(out, "%s<%s>",
 345                         i == 0 ? "" : ",",
 346                         ec_strvec_val(vec, i));
 347         fprintf(out, "]\n");
 348
 349         TAILQ_FOREACH(child, &parsed->children, next)
 350                 __ec_parsed_dump(out, child, indent + 2);
 351 }
 352
 353 void ec_parsed_dump(FILE *out, const struct ec_parsed *parsed)
 354 {
 355         fprintf(out, "------------------- parsed dump:\n"); //XXX
 356
 357         if (parsed == NULL) {
 358                 fprintf(out, "parsed is NULL, error in parse\n");
 359                 return;
 360         }
 361         if (!ec_parsed_matches(parsed)) {
 362                 fprintf(out, "no match\n");
 363                 return;
 364         }
 365
 366         __ec_parsed_dump(out, parsed, 0);
 367 }
 368
 369 void ec_parsed_add_child(struct ec_parsed *parsed,
 370         struct ec_parsed *child)
 371 {
 372         TAILQ_INSERT_TAIL(&parsed->children, child, next);
 373 }
 374
 375 void ec_parsed_del_child(struct ec_parsed *parsed,
 376         struct ec_parsed *child)
 377 {
 378         TAILQ_REMOVE(&parsed->children, child, next);
 379 }
 380
 381 struct ec_parsed *ec_parsed_find_first(struct ec_parsed *parsed,
 382         const char *id)
 383 {
 384         struct ec_parsed *child, *ret;
 385
 386         if (parsed == NULL)
 387                 return NULL;
 388
 389         if (parsed->node != NULL &&
 390                         parsed->node->id != NULL &&
 391                         !strcmp(parsed->node->id, id))
 392                 return parsed;
 393
 394         TAILQ_FOREACH(child, &parsed->children, next) {
 395                 ret = ec_parsed_find_first(child, id);
 396                 if (ret != NULL)
 397                         return ret;
 398         }
 399
 400         return NULL;
 401 }
 402
 403 const struct ec_strvec *ec_parsed_strvec(
 404         const struct ec_parsed *parsed)
 405 {
 406         if (parsed == NULL || parsed->strvec == NULL)
 407                 return NULL;
 408
 409         return parsed->strvec;
 410 }
 411
 412 /* number of parsed strings in the vector */
 413 size_t ec_parsed_len(const struct ec_parsed *parsed)
 414 {
 415         if (parsed == NULL || parsed->strvec == NULL)
 416                 return 0;
 417
 418         return ec_strvec_len(parsed->strvec);
 419 }
 420
 421 size_t ec_parsed_matches(const struct ec_parsed *parsed)
 422 {
 423         if (parsed == NULL)
 424                 return 0;
 425
 426         if (parsed->node == NULL && TAILQ_EMPTY(&parsed->children))
 427                 return 0;
 428
 429         return 1;
 430 }
 431
 432 struct ec_completed *ec_completed(void)
 433 {
 434         struct ec_completed *completed = NULL;
 435
 436         completed = ec_calloc(1, sizeof(*completed));
 437         if (completed == NULL)
 438                 return NULL;
 439
 440         TAILQ_INIT(&completed->elts);
 441         completed->count_match = 0;
 442
 443         return completed;
 444 }
 445
 446 struct ec_completed_elt *ec_completed_elt(const struct ec_node *node,
 447         const char *add)
 448 {
 449         struct ec_completed_elt *elt = NULL;
 450
 451         elt = ec_calloc(1, sizeof(*elt));
 452         if (elt == NULL)
 453                 return NULL;
 454
 455         elt->node = node;
 456         if (add != NULL) {
 457                 elt->add = ec_strdup(add);
 458                 if (elt->add == NULL) {
 459                         ec_completed_elt_free(elt);
 460                         return NULL;
 461                 }
 462         }
 463
 464         return elt;
 465 }
 466
 467 /* XXX define when to use ec_node_complete() or node->complete()
 468  * (same for parse)
 469  * suggestion: node->op() is internal, user calls the function
 470  * other idea: have 2 functions
 471  */
 472 struct ec_completed *ec_node_complete(struct ec_node *node,
 473         const char *str)
 474 {
 475         struct ec_strvec *strvec = NULL;
 476         struct ec_completed *completed;
 477
 478         errno = ENOMEM;
 479         strvec = ec_strvec();
 480         if (strvec == NULL)
 481                 goto fail;
 482
 483         if (ec_strvec_add(strvec, str) < 0)
 484                 goto fail;
 485
 486         completed = ec_node_complete_strvec(node, strvec);
 487         if (completed == NULL)
 488                 goto fail;
 489
 490         ec_strvec_free(strvec);
 491         return completed;
 492
 493  fail:
 494         ec_strvec_free(strvec);
 495         return NULL;
 496 }
 497
 498 /* default completion function: return a no-match element */
 499 struct ec_completed *ec_node_default_complete(const struct ec_node *gen_node,
 500         const struct ec_strvec *strvec)
 501 {
 502         struct ec_completed *completed;
 503         struct ec_completed_elt *completed_elt;
 504
 505         (void)strvec;
 506
 507         completed = ec_completed();
 508         if (completed == NULL)
 509                 return NULL;
 510
 511         completed_elt = ec_completed_elt(gen_node, NULL);
 512         if (completed_elt == NULL) {
 513                 ec_completed_free(completed);
 514                 return NULL;
 515         }
 516
 517         ec_completed_add_elt(completed, completed_elt);
 518
 519         return completed;
 520 }
 521
 522 struct ec_completed *ec_node_complete_strvec(struct ec_node *node,
 523         const struct ec_strvec *strvec)
 524 {
 525         int ret;
 526
 527         /* build the node if required */
 528         if (node->type->build != NULL) {
 529                 if ((node->flags & EC_NODE_F_BUILT) == 0) {
 530                         ret = node->type->build(node);
 531                         if (ret < 0) {
 532                                 errno = -ret;
 533                                 return NULL;
 534                         }
 535                 }
 536         }
 537         node->flags |= EC_NODE_F_BUILT;
 538
 539         if (node->type->complete == NULL) {
 540                 errno = ENOTSUP;
 541                 return NULL;
 542         }
 543
 544         return node->type->complete(node, strvec);
 545 }
 546
 547 /* count the number of identical chars at the beginning of 2 strings */
 548 static size_t strcmp_count(const char *s1, const char *s2)
 549 {
 550         size_t i = 0;
 551
 552         while (s1[i] && s2[i] && s1[i] == s2[i])
 553                 i++;
 554
 555         return i;
 556 }
 557
 558 void ec_completed_add_elt(
 559         struct ec_completed *completed, struct ec_completed_elt *elt)
 560 {
 561         size_t n;
 562
 563         TAILQ_INSERT_TAIL(&completed->elts, elt, next);
 564         completed->count++;
 565         if (elt->add != NULL)
 566                 completed->count_match++;
 567         if (elt->add != NULL) {
 568                 if (completed->smallest_start == NULL) {
 569                         completed->smallest_start = ec_strdup(elt->add);
 570                 } else {
 571                         n = strcmp_count(elt->add,
 572                                 completed->smallest_start);
 573                         completed->smallest_start[n] = '\0';
 574                 }
 575         }
 576 }
 577
 578 void ec_completed_elt_free(struct ec_completed_elt *elt)
 579 {
 580         ec_free(elt->add);
 581         ec_free(elt);
 582 }
 583
 584 void ec_completed_merge(struct ec_completed *completed1,
 585         struct ec_completed *completed2)
 586 {
 587         struct ec_completed_elt *elt;
 588
 589         assert(completed1 != NULL);
 590         assert(completed2 != NULL);
 591
 592         while (!TAILQ_EMPTY(&completed2->elts)) {
 593                 elt = TAILQ_FIRST(&completed2->elts);
 594                 TAILQ_REMOVE(&completed2->elts, elt, next);
 595                 ec_completed_add_elt(completed1, elt);
 596         }
 597
 598         ec_completed_free(completed2);
 599 }
 600
 601 void ec_completed_free(struct ec_completed *completed)
 602 {
 603         struct ec_completed_elt *elt;
 604
 605         if (completed == NULL)
 606                 return;
 607
 608         while (!TAILQ_EMPTY(&completed->elts)) {
 609                 elt = TAILQ_FIRST(&completed->elts);
 610                 TAILQ_REMOVE(&completed->elts, elt, next);
 611                 ec_completed_elt_free(elt);
 612         }
 613         ec_free(completed->smallest_start);
 614         ec_free(completed);
 615 }
 616
 617 void ec_completed_dump(FILE *out, const struct ec_completed *completed)
 618 {
 619         struct ec_completed_elt *elt;
 620
 621         if (completed == NULL || completed->count == 0) {
 622                 fprintf(out, "no completion\n");
 623                 return;
 624         }
 625
 626         fprintf(out, "completion: count=%u match=%u smallest_start=<%s>\n",
 627                 completed->count, completed->count_match,
 628                 completed->smallest_start);
 629
 630         TAILQ_FOREACH(elt, &completed->elts, next) {
 631                 fprintf(out, "add=<%s>, node=%p, node_type=%s\n",
 632                         elt->add, elt->node, elt->node->type->name);
 633         }
 634 }
 635
 636 const char *ec_completed_smallest_start(
 637         const struct ec_completed *completed)
 638 {
 639         if (completed == NULL || completed->smallest_start == NULL)
 640                 return "";
 641
 642         return completed->smallest_start;
 643 }
 644
 645 unsigned int ec_completed_count(
 646         const struct ec_completed *completed,
 647         enum ec_completed_filter_flags flags)
 648 {
 649         unsigned int count = 0;
 650
 651         if (completed == NULL)
 652                 return count;
 653
 654         if (flags & EC_MATCH)
 655                 count += completed->count_match;
 656         if (flags & EC_NO_MATCH)
 657                 count += (completed->count - completed->count_match); //XXX
 658
 659         return count;
 660 }
 661
 662 struct ec_completed_iter *
 663 ec_completed_iter(struct ec_completed *completed,
 664         enum ec_completed_filter_flags flags)
 665 {
 666         struct ec_completed_iter *iter;
 667
 668         iter = ec_calloc(1, sizeof(*iter));
 669         if (iter == NULL)
 670                 return NULL;
 671
 672         iter->completed = completed;
 673         iter->flags = flags;
 674         iter->cur = NULL;
 675
 676         return iter;
 677 }
 678
 679 const struct ec_completed_elt *ec_completed_iter_next(
 680         struct ec_completed_iter *iter)
 681 {
 682         if (iter->completed == NULL)
 683                 return NULL;
 684
 685         do {
 686                 if (iter->cur == NULL) {
 687                         iter->cur = TAILQ_FIRST(&iter->completed->elts);
 688                 } else {
 689                         iter->cur = TAILQ_NEXT(iter->cur, next);
 690                 }
 691
 692                 if (iter->cur == NULL)
 693                         break;
 694
 695                 if (iter->cur->add == NULL &&
 696                                 (iter->flags & EC_NO_MATCH))
 697                         break;
 698
 699                 if (iter->cur->add != NULL &&
 700                                 (iter->flags & EC_MATCH))
 701                         break;
 702
 703         } while (iter->cur != NULL);
 704
 705         return iter->cur;
 706 }
 707
 708 void ec_completed_iter_free(struct ec_completed_iter *iter)
 709 {
 710         ec_free(iter);
 711 }
 712
 713 const char *ec_node_desc(const struct ec_node *node)
 714 {
 715         if (node->type->desc != NULL)
 716                 return node->type->desc(node);
 717
 718         return node->desc;
 719 }