lib/ecoli_completed.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 #include <ecoli_parsed.h>
  40 #include <ecoli_completed.h>
  41
  42 struct ec_completed *ec_completed(void)
  43 {
  44         struct ec_completed *completed = NULL;
  45
  46         completed = ec_calloc(1, sizeof(*completed));
  47         if (completed == NULL)
  48                 return NULL;
  49
  50         TAILQ_INIT(&completed->nodes);
  51
  52         return completed;
  53 }
  54
  55 /* XXX on error, states are not freed ?
  56  * they can be left in a bad state and should not be reused */
  57 int
  58 ec_node_complete_child(struct ec_node *node,
  59                 struct ec_completed *completed,
  60                 struct ec_parsed *parsed_state,
  61                 const struct ec_strvec *strvec)
  62 {
  63         struct ec_parsed *child_state = NULL;
  64         int ret;
  65
  66         /* build the node if required */
  67         if (node->type->build != NULL) {
  68                 if ((node->flags & EC_NODE_F_BUILT) == 0) {
  69                         ret = node->type->build(node);
  70                         if (ret < 0)
  71                                 return ret;
  72                 }
  73         }
  74         node->flags |= EC_NODE_F_BUILT;
  75
  76         if (node->type->complete == NULL)
  77                 return -ENOTSUP;
  78
  79         child_state = ec_parsed();
  80         if (child_state == NULL)
  81                 return -ENOMEM;
  82         child_state->node = node;
  83         ec_parsed_add_child(parsed_state, child_state);
  84
  85         ret = ec_completed_add_node(completed, node);
  86         if (ret < 0)
  87                 return ret;
  88
  89         ret = node->type->complete(node, completed,
  90                                 child_state, strvec);
  91         if (ret < 0)
  92                 return ret;
  93
  94 #if 0 // XXX dump
  95         printf("----------------------------------------------------------\n");
  96         ec_node_dump(stdout, node);
  97         ec_strvec_dump(stdout, strvec);
  98         ec_completed_dump(stdout, completed);
  99         ec_parsed_dump(stdout, parsed_state);
 100 #endif
 101
 102         ec_parsed_del_child(parsed_state, child_state);
 103         assert(TAILQ_EMPTY(&child_state->children));
 104         ec_parsed_free(child_state);
 105
 106         return 0;
 107 }
 108
 109 struct ec_completed *ec_node_complete_strvec(struct ec_node *node,
 110         const struct ec_strvec *strvec)
 111 {
 112         struct ec_parsed *parsed_state = NULL;
 113         struct ec_completed *completed = NULL;
 114         int ret;
 115
 116         parsed_state = ec_parsed();
 117         if (parsed_state == NULL)
 118                 goto fail;
 119
 120         completed = ec_completed();
 121         if (completed == NULL)
 122                 goto fail;
 123
 124         ret = ec_node_complete_child(node, completed,
 125                                 parsed_state, strvec);
 126         if (ret < 0)
 127                 goto fail;
 128
 129         ec_parsed_free(parsed_state);
 130
 131         return completed;
 132
 133 fail:
 134         ec_parsed_free(parsed_state);
 135         ec_completed_free(completed);
 136         return NULL;
 137 }
 138
 139 struct ec_completed *ec_node_complete(struct ec_node *node,
 140         const char *str)
 141 {
 142         struct ec_strvec *strvec = NULL;
 143         struct ec_completed *completed;
 144
 145         errno = ENOMEM;
 146         strvec = ec_strvec();
 147         if (strvec == NULL)
 148                 goto fail;
 149
 150         if (ec_strvec_add(strvec, str) < 0)
 151                 goto fail;
 152
 153         completed = ec_node_complete_strvec(node, strvec);
 154         if (completed == NULL)
 155                 goto fail;
 156
 157         ec_strvec_free(strvec);
 158         return completed;
 159
 160  fail:
 161         ec_strvec_free(strvec);
 162         return NULL;
 163 }
 164
 165 /* count the number of identical chars at the beginning of 2 strings */
 166 static size_t strcmp_count(const char *s1, const char *s2)
 167 {
 168         size_t i = 0;
 169
 170         while (s1[i] && s2[i] && s1[i] == s2[i])
 171                 i++;
 172
 173         return i;
 174 }
 175
 176 static struct ec_completed_node *
 177 ec_completed_node(const struct ec_node *node)
 178 {
 179         struct ec_completed_node *compnode = NULL;
 180
 181         compnode = ec_calloc(1, sizeof(*compnode));
 182         if (compnode == NULL)
 183                 return NULL;
 184
 185         compnode->node = node;
 186         TAILQ_INIT(&compnode->items);
 187
 188         return compnode;
 189 }
 190
 191 static struct ec_completed_item *
 192 ec_completed_item(struct ec_parsed *state, const struct ec_node *node)
 193 {
 194         struct ec_completed_item *item = NULL;
 195         struct ec_parsed *p;
 196         size_t len;
 197
 198         item = ec_calloc(1, sizeof(*item));
 199         if (item == NULL)
 200                 return NULL;
 201
 202         /* get path len */
 203         for (p = state, len = 0; p != NULL;
 204              p = ec_parsed_get_parent(p), len++)
 205                 ;
 206         /* allocate room for path */
 207         item->path = ec_calloc(len, sizeof(*item->path));
 208         if (item->path == NULL)
 209                 goto fail;
 210         item->pathlen = len;
 211         /* write path in array */
 212         for (p = state, len = 0; p != NULL;
 213              p = ec_parsed_get_parent(p), len++)
 214                 item->path[len] = p->node;
 215
 216         item->type = EC_NO_MATCH;
 217         item->node = node;
 218
 219         return item;
 220
 221 fail:
 222         if (item != NULL) {
 223                 ec_free(item->path);
 224                 ec_free(item->str);
 225         }
 226         ec_completed_item_free(item);
 227
 228         return NULL;
 229 }
 230
 231 static int
 232 __ec_completed_add_match(enum ec_completed_type type,
 233                         struct ec_completed *completed,
 234                         struct ec_parsed *parsed_state,
 235                         const struct ec_node *node, const char *str)
 236 {
 237         struct ec_completed_node *compnode = NULL;
 238         struct ec_completed_item *item = NULL;
 239         int ret = -ENOMEM;
 240
 241         /* find the compnode entry corresponding to this node */
 242         TAILQ_FOREACH(compnode, &completed->nodes, next) {
 243                 if (compnode->node == node)
 244                         break;
 245         }
 246         if (compnode == NULL)
 247                 return -ENOENT;
 248
 249         item = ec_completed_item(parsed_state, node);
 250         if (item == NULL)
 251                 goto fail;
 252         item->type = type;
 253         if (str != NULL) {
 254                 item->str = ec_strdup(str);
 255                 if (item->str == NULL)
 256                         goto fail;
 257         }
 258
 259         if (item->str != NULL)
 260                 completed->count_match++;
 261
 262         TAILQ_INSERT_TAIL(&compnode->items, item, next);
 263         completed->count++;
 264
 265         return 0;
 266
 267 fail:
 268         ec_completed_item_free(item);
 269         return ret;
 270 }
 271
 272 int
 273 ec_completed_add_match(struct ec_completed *completed,
 274                 struct ec_parsed *parsed_state,
 275                 const struct ec_node *node, const char *str)
 276 {
 277         struct ec_completed_node *compnode = NULL;
 278         struct ec_completed_item *item = NULL;
 279         int ret = -ENOMEM;
 280
 281         /* find the compnode entry corresponding to this node */
 282         TAILQ_FOREACH(compnode, &completed->nodes, next) {
 283                 if (compnode->node == node)
 284                         break;
 285         }
 286         if (compnode == NULL)
 287                 return -ENOENT;
 288
 289         item = ec_completed_item(parsed_state, node);
 290         if (item == NULL)
 291                 goto fail;
 292         item->type = EC_MATCH;
 293         if (str != NULL) {
 294                 item->str = ec_strdup(str);
 295                 if (item->str == NULL)
 296                         goto fail;
 297         }
 298
 299         if (item->str != NULL)
 300                 completed->count_match++;
 301
 302         TAILQ_INSERT_TAIL(&compnode->items, item, next);
 303         completed->count++;
 304
 305         return 0;
 306
 307 fail:
 308         ec_completed_item_free(item);
 309         return ret;
 310 }
 311
 312 int
 313 ec_completed_add_no_match(struct ec_completed *completed,
 314                 struct ec_parsed *parsed_state,
 315                 const struct ec_node *node)
 316 {
 317         return __ec_completed_add_match(EC_NO_MATCH, completed, parsed_state,
 318                                         node, NULL);
 319 }
 320
 321 int
 322 ec_completed_add_partial_match(struct ec_completed *completed,
 323                 struct ec_parsed *parsed_state,
 324                 const struct ec_node *node, const char *str)
 325 {
 326         return __ec_completed_add_match(EC_PARTIAL_MATCH, completed, parsed_state,
 327                                         node, str);
 328 }
 329
 330 int
 331 ec_completed_add_node(struct ec_completed *completed,
 332                 const struct ec_node *node)
 333 {
 334         struct ec_completed_node *compnode = NULL;
 335
 336         compnode = ec_completed_node(node);
 337         if (compnode == NULL)
 338                 return -ENOMEM;
 339
 340         TAILQ_INSERT_TAIL(&completed->nodes, compnode, next);
 341         return 0;
 342 }
 343
 344 void ec_completed_item_free(struct ec_completed_item *match)
 345 {
 346         ec_free(match->str);
 347         ec_free(match->path);
 348         ec_free(match);
 349 }
 350
 351 /* default completion function: return a no-match element */
 352 int
 353 ec_node_default_complete(const struct ec_node *gen_node,
 354                         struct ec_completed *completed,
 355                         struct ec_parsed *parsed_state,
 356                         const struct ec_strvec *strvec)
 357 {
 358         int ret;
 359
 360         if (ec_strvec_len(strvec) != 1)
 361                 return 0;
 362
 363         ret = ec_completed_add_no_match(completed, parsed_state, gen_node);
 364         if (ret < 0)
 365                 return ret;
 366
 367         return 0;
 368 }
 369
 370 void ec_completed_free(struct ec_completed *completed)
 371 {
 372         struct ec_completed_node *compnode;
 373         struct ec_completed_item *item;
 374
 375         if (completed == NULL)
 376                 return;
 377
 378         while (!TAILQ_EMPTY(&completed->nodes)) {
 379                 compnode = TAILQ_FIRST(&completed->nodes);
 380                 TAILQ_REMOVE(&completed->nodes, compnode, next);
 381
 382                 while (!TAILQ_EMPTY(&compnode->items)) {
 383                         item = TAILQ_FIRST(&compnode->items);
 384                         TAILQ_REMOVE(&compnode->items, item, next);
 385                         ec_completed_item_free(item);
 386                 }
 387                 ec_free(compnode);
 388         }
 389         ec_free(completed);
 390 }
 391
 392 void ec_completed_dump(FILE *out, const struct ec_completed *completed)
 393 {
 394         struct ec_completed_node *compnode;
 395         struct ec_completed_item *item;
 396
 397         if (completed == NULL || completed->count == 0) {
 398                 fprintf(out, "no completion\n");
 399                 return;
 400         }
 401
 402         fprintf(out, "completion: count=%u match=%u\n",
 403                 completed->count, completed->count_match);
 404
 405         TAILQ_FOREACH(compnode, &completed->nodes, next) {
 406                 fprintf(out, "node=%p, node_type=%s\n",
 407                         compnode->node, compnode->node->type->name);
 408                 TAILQ_FOREACH(item, &compnode->items, next) {
 409                         const char *typestr;
 410
 411                         switch (item->type) {
 412                         case EC_NO_MATCH: typestr = "no-match"; break;
 413                         case EC_MATCH: typestr = "match"; break;
 414                         case EC_PARTIAL_MATCH: typestr = "partial-match"; break;
 415                         default: typestr = "unknown"; break;
 416                         }
 417
 418                         fprintf(out, "  type=%s str=<%s>\n", typestr, item->str);
 419                 }
 420         }
 421 }
 422
 423 char *ec_completed_smallest_start(const struct ec_completed *completed)
 424 {
 425         struct ec_completed_node *compnode;
 426         struct ec_completed_item *item;
 427         char *smallest_start = NULL;
 428         size_t n;
 429
 430         if (completed == NULL)
 431                 goto fail;
 432
 433         TAILQ_FOREACH(compnode, &completed->nodes, next) {
 434                 TAILQ_FOREACH(item, &compnode->items, next) {
 435                         if (item->str == NULL)
 436                                 continue;
 437                         if (smallest_start == NULL) {
 438                                 smallest_start = ec_strdup(item->str);
 439                                 if (smallest_start == NULL)
 440                                         goto fail;
 441                         } else {
 442                                 n = strcmp_count(item->str, smallest_start);
 443                                 smallest_start[n] = '\0';
 444                         }
 445                 }
 446         }
 447
 448         return smallest_start;
 449
 450 fail:
 451         ec_free(smallest_start);
 452         return NULL;
 453 }
 454
 455 unsigned int ec_completed_count(
 456         const struct ec_completed *completed,
 457         enum ec_completed_type type)
 458 {
 459         unsigned int count = 0;
 460
 461         if (completed == NULL)
 462                 return count;
 463
 464         if (type & EC_MATCH)
 465                 count += completed->count_match;
 466         if (type & EC_NO_MATCH)
 467                 count += (completed->count - completed->count_match); //XXX
 468
 469         return count;
 470 }
 471
 472 struct ec_completed_iter *
 473 ec_completed_iter(struct ec_completed *completed,
 474         enum ec_completed_type type)
 475 {
 476         struct ec_completed_iter *iter;
 477
 478         iter = ec_calloc(1, sizeof(*iter));
 479         if (iter == NULL)
 480                 return NULL;
 481
 482         iter->completed = completed;
 483         iter->type = type;
 484         iter->cur_node = NULL;
 485         iter->cur_match = NULL;
 486
 487         return iter;
 488 }
 489
 490 const struct ec_completed_item *ec_completed_iter_next(
 491         struct ec_completed_iter *iter)
 492 {
 493         const struct ec_completed *completed = iter->completed;
 494         const struct ec_completed_node *cur_node;
 495         const struct ec_completed_item *cur_match;
 496
 497         if (completed == NULL)
 498                 return NULL;
 499
 500         cur_node = iter->cur_node;
 501         cur_match = iter->cur_match;
 502
 503         /* first call */
 504         if (cur_node == NULL) {
 505                 TAILQ_FOREACH(cur_node, &completed->nodes, next) {
 506                         TAILQ_FOREACH(cur_match, &cur_node->items, next) {
 507                                 if (cur_match != NULL &&
 508                                                 cur_match->type & iter->type)
 509                                         goto found;
 510                         }
 511                 }
 512                 return NULL;
 513         } else {
 514                 cur_match = TAILQ_NEXT(cur_match, next);
 515                 if (cur_match != NULL &&
 516                                 cur_match->type & iter->type)
 517                         goto found;
 518                 cur_node = TAILQ_NEXT(cur_node, next);
 519                 while (cur_node != NULL) {
 520                         cur_match = TAILQ_FIRST(&cur_node->items);
 521                         if (cur_match != NULL &&
 522                                         cur_match->type & iter->type)
 523                                 goto found;
 524                         cur_node = TAILQ_NEXT(cur_node, next);
 525                 }
 526                 return NULL;
 527         }
 528
 529 found:
 530         iter->cur_node = cur_node;
 531         iter->cur_match = cur_match;
 532
 533         return iter->cur_match;
 534 }
 535
 536 void ec_completed_iter_free(struct ec_completed_iter *iter)
 537 {
 538         ec_free(iter);
 539 }