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         TAILQ_INIT(&completed->matches);
  52
  53         return completed;
  54 }
  55
  56 /* XXX on error, states are not freed ?
  57  * they can be left in a bad state and should not be reused */
  58 int
  59 ec_node_complete_child(struct ec_node *node,
  60                 struct ec_completed *completed,
  61                 struct ec_parsed *parsed_state,
  62                 const struct ec_strvec *strvec)
  63 {
  64         struct ec_parsed *child_state = NULL;
  65         int ret;
  66
  67         /* build the node if required */
  68         if (node->type->build != NULL) {
  69                 if ((node->flags & EC_NODE_F_BUILT) == 0) {
  70                         ret = node->type->build(node);
  71                         if (ret < 0)
  72                                 return ret;
  73                 }
  74         }
  75         node->flags |= EC_NODE_F_BUILT;
  76
  77         if (node->type->complete == NULL)
  78                 return -ENOTSUP;
  79
  80         child_state = ec_parsed();
  81         if (child_state == NULL)
  82                 return -ENOMEM;
  83         child_state->node = node;
  84         ec_parsed_add_child(parsed_state, child_state);
  85
  86         ret = ec_completed_add_node(completed, child_state, node);
  87         if (ret < 0)
  88                 return ret;
  89
  90         ret = node->type->complete(node, completed,
  91                                         child_state, strvec);
  92         if (ret < 0)
  93                 return ret;
  94
  95 #if 0 // XXX dump
  96         printf("----------------------------------------------------------\n");
  97         ec_node_dump(stdout, node);
  98         ec_strvec_dump(stdout, strvec);
  99         ec_completed_dump(stdout, completed);
 100         ec_parsed_dump(stdout, parsed_state);
 101 #endif
 102
 103         ec_parsed_del_child(parsed_state, child_state);
 104         assert(TAILQ_EMPTY(&child_state->children));
 105         ec_parsed_free(child_state);
 106
 107         return 0;
 108 }
 109
 110 struct ec_completed *ec_node_complete_strvec(struct ec_node *node,
 111         const struct ec_strvec *strvec)
 112 {
 113         struct ec_parsed *parsed_state = NULL;
 114         struct ec_completed *completed = NULL;
 115         int ret;
 116
 117         parsed_state = ec_parsed();
 118         if (parsed_state == NULL)
 119                 goto fail;
 120
 121         completed = ec_completed();
 122         if (completed == NULL)
 123                 goto fail;
 124
 125         ret = ec_node_complete_child(node, completed,
 126                                 parsed_state, strvec);
 127         if (ret < 0)
 128                 goto fail;
 129
 130         ec_parsed_free(parsed_state);
 131
 132         return completed;
 133
 134 fail:
 135         ec_parsed_free(parsed_state);
 136         ec_completed_free(completed);
 137         return NULL;
 138 }
 139
 140 struct ec_completed *ec_node_complete(struct ec_node *node,
 141         const char *str)
 142 {
 143         struct ec_strvec *strvec = NULL;
 144         struct ec_completed *completed;
 145
 146         errno = ENOMEM;
 147         strvec = ec_strvec();
 148         if (strvec == NULL)
 149                 goto fail;
 150
 151         if (ec_strvec_add(strvec, str) < 0)
 152                 goto fail;
 153
 154         completed = ec_node_complete_strvec(node, strvec);
 155         if (completed == NULL)
 156                 goto fail;
 157
 158         ec_strvec_free(strvec);
 159         return completed;
 160
 161  fail:
 162         ec_strvec_free(strvec);
 163         return NULL;
 164 }
 165
 166 /* count the number of identical chars at the beginning of 2 strings */
 167 static size_t strcmp_count(const char *s1, const char *s2)
 168 {
 169         size_t i = 0;
 170
 171         while (s1[i] && s2[i] && s1[i] == s2[i])
 172                 i++;
 173
 174         return i;
 175 }
 176
 177 static struct ec_completed_item *
 178 ec_completed_item(enum ec_completed_type type, struct ec_parsed *state,
 179                 const struct ec_node *node, const char *add)
 180 {
 181         struct ec_completed_item *item = NULL;
 182
 183         item = ec_calloc(1, sizeof(*item));
 184         if (item == NULL)
 185                 return NULL;
 186
 187         /* XXX can state be NULL? */
 188         if (state != NULL) {
 189                 struct ec_parsed *p;
 190                 size_t len;
 191
 192                 /* get path len */
 193                 for (p = state, len = 0; p != NULL;
 194                      p = ec_parsed_get_parent(p), len++)
 195                         ;
 196
 197                 item->path = ec_calloc(len, sizeof(*item->path));
 198                 if (item->path == NULL)
 199                         goto fail;
 200
 201                 item->pathlen = len;
 202
 203                 /* write path in array */
 204                 for (p = state, len = 0; p != NULL;
 205                      p = ec_parsed_get_parent(p), len++)
 206                         item->path[len] = p->node;
 207         }
 208
 209         item->type = type;
 210         item->node = node;
 211         if (add != NULL) {
 212                 item->add = ec_strdup(add);
 213                 if (item->add == NULL)
 214                         goto fail;
 215         }
 216
 217         return item;
 218
 219 fail:
 220         if (item != NULL) {
 221                 ec_free(item->path);
 222                 ec_free(item->add);
 223         }
 224         ec_completed_item_free(item);
 225
 226         return NULL;
 227 }
 228
 229 int
 230 ec_completed_add_match(struct ec_completed *completed,
 231                 struct ec_parsed *parsed_state,
 232                 const struct ec_node *node, const char *add)
 233 {
 234         struct ec_completed_item *item = NULL;
 235         int ret = -ENOMEM;
 236         size_t n;
 237
 238         item = ec_completed_item(EC_MATCH, parsed_state, node, add);
 239         if (item == NULL)
 240                 goto fail;
 241
 242         if (item->add != NULL) {
 243                 if (completed->smallest_start == NULL) {
 244                         completed->smallest_start = ec_strdup(item->add);
 245                         if (completed->smallest_start == NULL)
 246                                 goto fail;
 247                 } else {
 248                         n = strcmp_count(item->add,
 249                                 completed->smallest_start);
 250                         completed->smallest_start[n] = '\0';
 251                 }
 252                 completed->count_match++;
 253         }
 254
 255         TAILQ_INSERT_TAIL(&completed->matches, item, next);
 256         completed->count++;
 257
 258         return 0;
 259
 260 fail:
 261         ec_completed_item_free(item);
 262         return ret;
 263 }
 264
 265 int
 266 ec_completed_add_node(struct ec_completed *completed,
 267                 struct ec_parsed *parsed_state,
 268                 const struct ec_node *node)
 269 {
 270 #if 0
 271         struct ec_completed_item *item = NULL;
 272         int ret;
 273
 274         item = ec_completed_item(EC_NO_MATCH, parsed_state, node, NULL);
 275         if (item == NULL)
 276                 return -ENOMEM;
 277
 278         ret = ec_completed_add_item(completed, item);
 279         if (ret < 0) {
 280                 ec_completed_item_free(item);
 281                 return ret;
 282         }
 283 #endif
 284         (void)completed;
 285         (void)parsed_state;
 286         (void)node;
 287         return 0;
 288 }
 289
 290 void ec_completed_item_free(struct ec_completed_item *item)
 291 {
 292         ec_free(item->add);
 293         ec_free(item->path);
 294         ec_free(item);
 295 }
 296
 297 /* default completion function: return a no-item element */
 298 int
 299 ec_node_default_complete(const struct ec_node *gen_node,
 300                         struct ec_completed *completed,
 301                         struct ec_parsed *parsed,
 302                         const struct ec_strvec *strvec)
 303 {
 304         (void)strvec;
 305
 306         if (ec_strvec_len(strvec) != 1) //XXX needed?
 307                 return 0;
 308
 309         if (ec_completed_add_node(completed, parsed, gen_node) < 0)
 310                 return -1;
 311
 312         return 0;
 313 }
 314
 315 void ec_completed_merge(struct ec_completed *completed1,
 316         struct ec_completed *completed2)
 317 {
 318         struct ec_completed_item *item;
 319
 320         assert(completed1 != NULL);
 321         assert(completed2 != NULL);
 322
 323         while (!TAILQ_EMPTY(&completed2->matches)) {
 324                 item = TAILQ_FIRST(&completed2->matches);
 325                 TAILQ_REMOVE(&completed2->matches, item, next);
 326                 //ec_completed_add_item(completed1, item);
 327         }
 328
 329         ec_completed_free(completed2);
 330 }
 331
 332 void ec_completed_free(struct ec_completed *completed)
 333 {
 334         struct ec_completed_item *item;
 335
 336         if (completed == NULL)
 337                 return;
 338
 339         while (!TAILQ_EMPTY(&completed->matches)) {
 340                 item = TAILQ_FIRST(&completed->matches);
 341                 TAILQ_REMOVE(&completed->matches, item, next);
 342                 ec_completed_item_free(item);
 343         }
 344         ec_free(completed->smallest_start);
 345         ec_free(completed);
 346 }
 347
 348 void ec_completed_dump(FILE *out, const struct ec_completed *completed)
 349 {
 350         struct ec_completed_item *item;
 351
 352         if (completed == NULL || completed->count == 0) {
 353                 fprintf(out, "no completion\n");
 354                 return;
 355         }
 356
 357         fprintf(out, "completion: count=%u match=%u smallest_start=<%s>\n",
 358                 completed->count, completed->count_match,
 359                 completed->smallest_start);
 360
 361         TAILQ_FOREACH(item, &completed->matches, next) {
 362                 fprintf(out, "add=<%s>, node=%p, node_type=%s\n",
 363                         item->add, item->node, item->node->type->name);
 364         }
 365 }
 366
 367 const char *ec_completed_smallest_start(
 368         const struct ec_completed *completed)
 369 {
 370         if (completed == NULL || completed->smallest_start == NULL)
 371                 return "";
 372
 373         return completed->smallest_start;
 374 }
 375
 376 unsigned int ec_completed_count(
 377         const struct ec_completed *completed,
 378         enum ec_completed_type type)
 379 {
 380         unsigned int count = 0;
 381
 382         if (completed == NULL)
 383                 return count;
 384
 385         if (type & EC_MATCH)
 386                 count += completed->count_match;
 387         if (type & EC_NO_MATCH)
 388                 count += (completed->count - completed->count_match); //XXX
 389
 390         return count;
 391 }
 392
 393 struct ec_completed_iter *
 394 ec_completed_iter(struct ec_completed *completed,
 395         enum ec_completed_type type)
 396 {
 397         struct ec_completed_iter *iter;
 398
 399         iter = ec_calloc(1, sizeof(*iter));
 400         if (iter == NULL)
 401                 return NULL;
 402
 403         iter->completed = completed;
 404         iter->type = type;
 405         iter->cur_item = NULL;
 406
 407         return iter;
 408 }
 409
 410 const struct ec_completed_item *ec_completed_iter_next(
 411         struct ec_completed_iter *iter)
 412 {
 413         const struct ec_completed *completed = iter->completed;
 414
 415         if (completed == NULL)
 416                 return NULL;
 417
 418         do {
 419                 if (iter->cur_item == NULL)
 420                         iter->cur_item = TAILQ_FIRST(&completed->matches);
 421                 else
 422                         iter->cur_item = TAILQ_NEXT(iter->cur_item, next);
 423
 424                 if (iter->cur_item == NULL)
 425                         break;
 426
 427                 if (iter->cur_item->add == NULL &&
 428                                 (iter->type & EC_NO_MATCH))
 429                         break;
 430
 431                 if (iter->cur_item->add != NULL &&
 432                                 (iter->type & EC_MATCH))
 433                         break;
 434
 435         } while (iter->cur_item != NULL);
 436
 437         return iter->cur_item;
 438 }
 439
 440 void ec_completed_iter_free(struct ec_completed_iter *iter)
 441 {
 442         ec_free(iter);
 443 }