lib/ecoli_tk.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_tk.h>
  39
  40 struct ec_tk *ec_tk_new(const char *id, const struct ec_tk_ops *ops,
  41         size_t size)
  42 {
  43         struct ec_tk *tk = NULL;
  44         char buf[256]; // XXX
  45
  46         assert(size >= sizeof(*tk));
  47
  48         ec_log(EC_LOG_DEBUG, "create node type=%s id=%s\n", ops->typename, id);
  49
  50         tk = ec_calloc(1, size);
  51         if (tk == NULL)
  52                 goto fail;
  53
  54         TAILQ_INIT(&tk->children);
  55         tk->ops = ops;
  56         tk->refcnt = 1;
  57
  58         if (id != NULL) {
  59                 tk->id = ec_strdup(id);
  60                 if (tk->id == NULL)
  61                         goto fail;
  62         }
  63
  64         snprintf(buf, sizeof(buf), "<%s>", ops->typename);
  65         tk->desc = ec_strdup(buf); // XXX ec_asprintf ?
  66         if (tk->desc == NULL)
  67                 goto fail;
  68
  69         tk->attrs = ec_keyval_new();
  70         if (tk->attrs == NULL)
  71                 goto fail;
  72
  73         return tk;
  74
  75  fail:
  76         ec_tk_free(tk);
  77         return NULL;
  78 }
  79
  80 void ec_tk_free(struct ec_tk *tk)
  81 {
  82         if (tk == NULL)
  83                 return;
  84
  85         assert(tk->refcnt > 0);
  86
  87         if (--tk->refcnt > 0)
  88                 return;
  89
  90         if (tk->ops != NULL && tk->ops->free_priv != NULL)
  91                 tk->ops->free_priv(tk);
  92         ec_free(tk->id);
  93         ec_free(tk->desc);
  94         ec_free(tk->attrs);
  95         ec_free(tk);
  96 }
  97
  98 struct ec_tk *ec_tk_clone(struct ec_tk *tk)
  99 {
 100         if (tk != NULL)
 101                 tk->refcnt++;
 102         return tk;
 103 }
 104
 105 struct ec_tk *ec_tk_find(struct ec_tk *tk, const char *id)
 106 {
 107         struct ec_tk *child, *ret;
 108         const char *tk_id = ec_tk_id(tk);
 109
 110         if (id != NULL && tk_id != NULL && !strcmp(tk_id, id))
 111                 return tk;
 112
 113         TAILQ_FOREACH(child, &tk->children, next) {
 114                 ret = ec_tk_find(child, id);
 115                 if (ret != NULL)
 116                         return ret;
 117         }
 118
 119         return NULL;
 120 }
 121
 122 struct ec_keyval *ec_tk_attrs(const struct ec_tk *tk)
 123 {
 124         return tk->attrs;
 125 }
 126
 127 const char *ec_tk_id(const struct ec_tk *tk)
 128 {
 129         return tk->id;
 130 }
 131
 132 struct ec_tk *ec_tk_parent(const struct ec_tk *tk)
 133 {
 134         return tk->parent;
 135 }
 136
 137 struct ec_parsed_tk *ec_tk_parse(struct ec_tk *tk, const char *str)
 138 {
 139         struct ec_strvec *strvec = NULL;
 140         struct ec_parsed_tk *parsed_tk;
 141
 142         errno = ENOMEM;
 143         strvec = ec_strvec_new();
 144         if (strvec == NULL)
 145                 goto fail;
 146
 147         if (ec_strvec_add(strvec, str) < 0)
 148                 goto fail;
 149
 150         parsed_tk = ec_tk_parse_tokens(tk, strvec);
 151         if (parsed_tk == NULL)
 152                 goto fail;
 153
 154         ec_strvec_free(strvec);
 155         return parsed_tk;
 156
 157  fail:
 158         ec_strvec_free(strvec);
 159         return NULL;
 160 }
 161
 162 struct ec_parsed_tk *ec_tk_parse_tokens(struct ec_tk *tk,
 163         const struct ec_strvec *strvec)
 164 {
 165         struct ec_parsed_tk *parsed_tk;
 166         int ret;
 167
 168         /* build the node if required */
 169         if (tk->ops->build != NULL) {
 170                 if ((tk->flags & EC_TK_F_BUILT) == 0) {
 171                         ret = tk->ops->build(tk);
 172                         if (ret < 0) {
 173                                 errno = -ret;
 174                                 return NULL;
 175                         }
 176                 }
 177         }
 178         tk->flags |= EC_TK_F_BUILT;
 179
 180         if (tk->ops->parse == NULL) {
 181                 errno = ENOTSUP;
 182                 return NULL;
 183         }
 184
 185         parsed_tk = tk->ops->parse(tk, strvec);
 186
 187         return parsed_tk;
 188 }
 189
 190
 191 struct ec_parsed_tk *ec_parsed_tk_new(void)
 192 {
 193         struct ec_parsed_tk *parsed_tk = NULL;
 194
 195         parsed_tk = ec_calloc(1, sizeof(*parsed_tk));
 196         if (parsed_tk == NULL)
 197                 goto fail;
 198
 199         TAILQ_INIT(&parsed_tk->children);
 200
 201         return parsed_tk;
 202
 203  fail:
 204         return NULL;
 205 }
 206
 207 void ec_parsed_tk_set_match(struct ec_parsed_tk *parsed_tk,
 208         const struct ec_tk *tk, struct ec_strvec *strvec)
 209 {
 210         parsed_tk->tk = tk;
 211         parsed_tk->strvec = strvec;
 212 }
 213
 214 void ec_parsed_tk_free_children(struct ec_parsed_tk *parsed_tk)
 215 {
 216         struct ec_parsed_tk *child;
 217
 218         if (parsed_tk == NULL)
 219                 return;
 220
 221         while (!TAILQ_EMPTY(&parsed_tk->children)) {
 222                 child = TAILQ_FIRST(&parsed_tk->children);
 223                 TAILQ_REMOVE(&parsed_tk->children, child, next);
 224                 ec_parsed_tk_free(child);
 225         }
 226 }
 227
 228 void ec_parsed_tk_free(struct ec_parsed_tk *parsed_tk)
 229 {
 230         if (parsed_tk == NULL)
 231                 return;
 232
 233         ec_parsed_tk_free_children(parsed_tk);
 234         ec_strvec_free(parsed_tk->strvec);
 235         ec_free(parsed_tk);
 236 }
 237
 238 static void __ec_parsed_tk_dump(FILE *out,
 239         const struct ec_parsed_tk *parsed_tk, size_t indent)
 240 {
 241         struct ec_parsed_tk *child;
 242         const struct ec_strvec *vec;
 243         size_t i;
 244         const char *id = "None", *typename = "None";
 245
 246         if (parsed_tk->tk != NULL) {
 247                 if (parsed_tk->tk->id != NULL)
 248                         id = parsed_tk->tk->id;
 249                 typename = parsed_tk->tk->ops->typename;
 250         }
 251
 252         /* XXX remove this debug hack */
 253         if (!strcmp(typename, "str") || !strcmp(typename, "int"))
 254                 fprintf(out, ">>> ");
 255         else
 256                 fprintf(out, "    ");
 257
 258         /* XXX enhance */
 259         for (i = 0; i < indent; i++) {
 260                 if (i % 2)
 261                         fprintf(out, " ");
 262                 else
 263                         fprintf(out, "|");
 264         }
 265
 266         fprintf(out, "tk_type=%s id=%s vec=[", typename, id);
 267         vec = ec_parsed_tk_strvec(parsed_tk);
 268         for (i = 0; i < ec_strvec_len(vec); i++)
 269                 fprintf(out, "%s<%s>",
 270                         i == 0 ? "" : ",",
 271                         ec_strvec_val(vec, i));
 272         fprintf(out, "]\n");
 273
 274         TAILQ_FOREACH(child, &parsed_tk->children, next)
 275                 __ec_parsed_tk_dump(out, child, indent + 2);
 276 }
 277
 278 void ec_parsed_tk_dump(FILE *out, const struct ec_parsed_tk *parsed_tk)
 279 {
 280         fprintf(out, "------------------- dump:\n");
 281
 282         if (parsed_tk == NULL) {
 283                 fprintf(out, "parsed_tk is NULL, error in parse\n");
 284                 return;
 285         }
 286         if (!ec_parsed_tk_matches(parsed_tk)) {
 287                 fprintf(out, "no match\n");
 288                 return;
 289         }
 290
 291         __ec_parsed_tk_dump(out, parsed_tk, 0);
 292 }
 293
 294 void ec_parsed_tk_add_child(struct ec_parsed_tk *parsed_tk,
 295         struct ec_parsed_tk *child)
 296 {
 297         TAILQ_INSERT_TAIL(&parsed_tk->children, child, next);
 298 }
 299
 300 struct ec_parsed_tk *ec_parsed_tk_find_first(struct ec_parsed_tk *parsed_tk,
 301         const char *id)
 302 {
 303         struct ec_parsed_tk *child, *ret;
 304
 305         if (parsed_tk == NULL)
 306                 return NULL;
 307
 308         if (parsed_tk->tk != NULL &&
 309                         parsed_tk->tk->id != NULL &&
 310                         !strcmp(parsed_tk->tk->id, id))
 311                 return parsed_tk;
 312
 313         TAILQ_FOREACH(child, &parsed_tk->children, next) {
 314                 ret = ec_parsed_tk_find_first(child, id);
 315                 if (ret != NULL)
 316                         return ret;
 317         }
 318
 319         return NULL;
 320 }
 321
 322 const struct ec_strvec *ec_parsed_tk_strvec(
 323         const struct ec_parsed_tk *parsed_tk)
 324 {
 325         if (parsed_tk == NULL || parsed_tk->strvec == NULL)
 326                 return NULL;
 327
 328         return parsed_tk->strvec;
 329 }
 330
 331 /* number of parsed tokens */
 332 size_t ec_parsed_tk_len(const struct ec_parsed_tk *parsed_tk)
 333 {
 334         if (parsed_tk == NULL || parsed_tk->strvec == NULL)
 335                 return 0;
 336
 337         return ec_strvec_len(parsed_tk->strvec);
 338 }
 339
 340 size_t ec_parsed_tk_matches(const struct ec_parsed_tk *parsed_tk)
 341 {
 342         if (parsed_tk == NULL)
 343                 return 0;
 344
 345         if (parsed_tk->tk == NULL && TAILQ_EMPTY(&parsed_tk->children))
 346                 return 0;
 347
 348         return 1;
 349 }
 350
 351 struct ec_completed_tk *ec_completed_tk_new(void)
 352 {
 353         struct ec_completed_tk *completed_tk = NULL;
 354
 355         completed_tk = ec_calloc(1, sizeof(*completed_tk));
 356         if (completed_tk == NULL)
 357                 return NULL;
 358
 359         TAILQ_INIT(&completed_tk->elts);
 360         completed_tk->count_match = 0;
 361
 362         return completed_tk;
 363 }
 364
 365 struct ec_completed_tk_elt *ec_completed_tk_elt_new(const struct ec_tk *tk,
 366         const char *add)
 367 {
 368         struct ec_completed_tk_elt *elt = NULL;
 369
 370         elt = ec_calloc(1, sizeof(*elt));
 371         if (elt == NULL)
 372                 return NULL;
 373
 374         elt->tk = tk;
 375         if (add != NULL) {
 376                 elt->add = ec_strdup(add);
 377                 if (elt->add == NULL) {
 378                         ec_completed_tk_elt_free(elt);
 379                         return NULL;
 380                 }
 381         }
 382
 383         return elt;
 384 }
 385
 386 /* XXX define when to use ec_tk_complete() or tk->complete()
 387  * (same for parse)
 388  * suggestion: tk->op() is internal, user calls the function
 389  * other idea: have 2 functions
 390  */
 391 struct ec_completed_tk *ec_tk_complete(const struct ec_tk *tk,
 392         const char *str)
 393 {
 394         struct ec_strvec *strvec = NULL;
 395         struct ec_completed_tk *completed_tk;
 396
 397         errno = ENOMEM;
 398         strvec = ec_strvec_new();
 399         if (strvec == NULL)
 400                 goto fail;
 401
 402         if (ec_strvec_add(strvec, str) < 0)
 403                 goto fail;
 404
 405         completed_tk = ec_tk_complete_tokens(tk, strvec);
 406         if (completed_tk == NULL)
 407                 goto fail;
 408
 409         ec_strvec_free(strvec);
 410         return completed_tk;
 411
 412  fail:
 413         ec_strvec_free(strvec);
 414         return NULL;
 415 }
 416
 417 /* default completion function: return a no-match element */
 418 struct ec_completed_tk *ec_tk_default_complete(const struct ec_tk *gen_tk,
 419         const struct ec_strvec *strvec)
 420 {
 421         struct ec_completed_tk *completed_tk;
 422         struct ec_completed_tk_elt *completed_tk_elt;
 423
 424         (void)strvec;
 425
 426         completed_tk = ec_completed_tk_new();
 427         if (completed_tk == NULL)
 428                 return NULL;
 429
 430         completed_tk_elt = ec_completed_tk_elt_new(gen_tk, NULL);
 431         if (completed_tk_elt == NULL) {
 432                 ec_completed_tk_free(completed_tk);
 433                 return NULL;
 434         }
 435
 436         ec_completed_tk_add_elt(completed_tk, completed_tk_elt);
 437
 438         return completed_tk;
 439 }
 440
 441 struct ec_completed_tk *ec_tk_complete_tokens(const struct ec_tk *tk,
 442         const struct ec_strvec *strvec)
 443 {
 444         return tk->ops->complete(tk, strvec);
 445 }
 446
 447 /* count the number of identical chars at the beginning of 2 strings */
 448 static size_t strcmp_count(const char *s1, const char *s2)
 449 {
 450         size_t i = 0;
 451
 452         while (s1[i] && s2[i] && s1[i] == s2[i])
 453                 i++;
 454
 455         return i;
 456 }
 457
 458 void ec_completed_tk_add_elt(
 459         struct ec_completed_tk *completed_tk, struct ec_completed_tk_elt *elt)
 460 {
 461         size_t n;
 462
 463         TAILQ_INSERT_TAIL(&completed_tk->elts, elt, next);
 464         completed_tk->count++;
 465         if (elt->add != NULL)
 466                 completed_tk->count_match++;
 467         if (elt->add != NULL) {
 468                 if (completed_tk->smallest_start == NULL) {
 469                         completed_tk->smallest_start = ec_strdup(elt->add);
 470                 } else {
 471                         n = strcmp_count(elt->add,
 472                                 completed_tk->smallest_start);
 473                         completed_tk->smallest_start[n] = '\0';
 474                 }
 475         }
 476 }
 477
 478 void ec_completed_tk_elt_free(struct ec_completed_tk_elt *elt)
 479 {
 480         ec_free(elt->add);
 481         ec_free(elt);
 482 }
 483
 484 void ec_completed_tk_merge(struct ec_completed_tk *completed_tk1,
 485         struct ec_completed_tk *completed_tk2)
 486 {
 487         struct ec_completed_tk_elt *elt;
 488
 489         assert(completed_tk1 != NULL);
 490         assert(completed_tk2 != NULL);
 491
 492         while (!TAILQ_EMPTY(&completed_tk2->elts)) {
 493                 elt = TAILQ_FIRST(&completed_tk2->elts);
 494                 TAILQ_REMOVE(&completed_tk2->elts, elt, next);
 495                 ec_completed_tk_add_elt(completed_tk1, elt);
 496         }
 497
 498         ec_completed_tk_free(completed_tk2);
 499 }
 500
 501 void ec_completed_tk_free(struct ec_completed_tk *completed_tk)
 502 {
 503         struct ec_completed_tk_elt *elt;
 504
 505         if (completed_tk == NULL)
 506                 return;
 507
 508         while (!TAILQ_EMPTY(&completed_tk->elts)) {
 509                 elt = TAILQ_FIRST(&completed_tk->elts);
 510                 TAILQ_REMOVE(&completed_tk->elts, elt, next);
 511                 ec_completed_tk_elt_free(elt);
 512         }
 513         ec_free(completed_tk->smallest_start);
 514         ec_free(completed_tk);
 515 }
 516
 517 void ec_completed_tk_dump(FILE *out, const struct ec_completed_tk *completed_tk)
 518 {
 519         struct ec_completed_tk_elt *elt;
 520
 521         if (completed_tk == NULL || completed_tk->count == 0) {
 522                 fprintf(out, "no completion\n");
 523                 return;
 524         }
 525
 526         fprintf(out, "completion: count=%u match=%u smallest_start=<%s>\n",
 527                 completed_tk->count, completed_tk->count_match,
 528                 completed_tk->smallest_start);
 529
 530         TAILQ_FOREACH(elt, &completed_tk->elts, next) {
 531                 fprintf(out, "add=<%s>, tk=%p, tk_type=%s\n",
 532                         elt->add, elt->tk, elt->tk->ops->typename);
 533         }
 534 }
 535
 536 const char *ec_completed_tk_smallest_start(
 537         const struct ec_completed_tk *completed_tk)
 538 {
 539         if (completed_tk == NULL || completed_tk->smallest_start == NULL)
 540                 return "";
 541
 542         return completed_tk->smallest_start;
 543 }
 544
 545 unsigned int ec_completed_tk_count(
 546         const struct ec_completed_tk *completed_tk,
 547         enum ec_completed_tk_filter_flags flags)
 548 {
 549         unsigned int count = 0;
 550
 551         if (completed_tk == NULL)
 552                 return count;
 553
 554         if (flags & EC_MATCH)
 555                 count += completed_tk->count_match;
 556         if (flags & EC_NO_MATCH)
 557                 count += (completed_tk->count - completed_tk->count_match); //XXX
 558
 559         return count;
 560 }
 561
 562 struct ec_completed_tk_iter *
 563 ec_completed_tk_iter_new(struct ec_completed_tk *completed_tk,
 564         enum ec_completed_tk_filter_flags flags)
 565 {
 566         struct ec_completed_tk_iter *iter;
 567
 568         iter = ec_calloc(1, sizeof(*iter));
 569         if (iter == NULL)
 570                 return NULL;
 571
 572         iter->completed_tk = completed_tk;
 573         iter->flags = flags;
 574         iter->cur = NULL;
 575
 576         return iter;
 577 }
 578
 579 const struct ec_completed_tk_elt *ec_completed_tk_iter_next(
 580         struct ec_completed_tk_iter *iter)
 581 {
 582         if (iter->completed_tk == NULL)
 583                 return NULL;
 584
 585         do {
 586                 if (iter->cur == NULL) {
 587                         iter->cur = TAILQ_FIRST(&iter->completed_tk->elts);
 588                 } else {
 589                         iter->cur = TAILQ_NEXT(iter->cur, next);
 590                 }
 591
 592                 if (iter->cur == NULL)
 593                         break;
 594
 595                 if (iter->cur->add == NULL &&
 596                                 (iter->flags & EC_NO_MATCH))
 597                         break;
 598
 599                 if (iter->cur->add != NULL &&
 600                                 (iter->flags & EC_MATCH))
 601                         break;
 602
 603         } while (iter->cur != NULL);
 604
 605         return iter->cur;
 606 }
 607
 608 void ec_completed_tk_iter_free(struct ec_completed_tk_iter *iter)
 609 {
 610         ec_free(iter);
 611 }
 612
 613 const char *ec_tk_desc(const struct ec_tk *tk)
 614 {
 615         if (tk->ops->desc != NULL)
 616                 return tk->ops->desc(tk);
 617
 618         return tk->desc;
 619 }