lib/ecoli_node_subset.c

   1 /*
   2  * Copyright (c) 2016-2017, 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 <stdarg.h>
  33 #include <errno.h>
  34 #include <stdbool.h>
  35
  36 #include <ecoli_malloc.h>
  37 #include <ecoli_log.h>
  38 #include <ecoli_strvec.h>
  39 #include <ecoli_node.h>
  40 #include <ecoli_parsed.h>
  41 #include <ecoli_completed.h>
  42 #include <ecoli_node_subset.h>
  43 #include <ecoli_node_str.h>
  44 #include <ecoli_node_or.h>
  45 #include <ecoli_test.h>
  46
  47 struct ec_node_subset {
  48         struct ec_node gen;
  49         struct ec_node **table;
  50         unsigned int len;
  51 };
  52
  53 struct parse_result {
  54         struct ec_parsed **parsed_table; /* list of parsed node */
  55         size_t parsed_table_len;         /* number of parsed node */
  56         size_t len;                      /* consumed strings */
  57 };
  58
  59 static int __ec_node_subset_parse(struct ec_node **table, size_t table_len,
  60                                 const struct ec_strvec *strvec,
  61                                 struct parse_result *out)
  62 {
  63         struct ec_node **child_table;
  64         struct ec_parsed *child_parsed = NULL;
  65         struct ec_strvec *childvec = NULL;
  66         size_t i, j, len = 0;
  67         struct parse_result best_result, result;
  68         int ret;
  69
  70         if (table_len == 0)
  71                 return 0;
  72
  73         memset(&best_result, 0, sizeof(best_result));
  74         best_result.parsed_table =
  75                 ec_calloc(table_len, sizeof(*best_result.parsed_table[0]));
  76         if (best_result.parsed_table == NULL)
  77                 goto fail;
  78
  79         child_table = ec_calloc(table_len - 1, sizeof(*child_table));
  80         if (child_table == NULL)
  81                 goto fail;
  82
  83         for (i = 0; i < table_len; i++) {
  84                 /* try to parse elt i */
  85                 child_parsed = ec_node_parse_strvec(table[i], strvec);
  86                 if (child_parsed == NULL)
  87                         goto fail;
  88
  89                 if (!ec_parsed_matches(child_parsed)) {
  90                         ec_parsed_free(child_parsed);
  91                         child_parsed = NULL;
  92                         continue;
  93                 }
  94
  95                 /* build a new table without elt i */
  96                 for (j = 0; j < table_len; j++) {
  97                         if (j < i)
  98                                 child_table[j] = table[j];
  99                         else if (j > i)
 100                                 child_table[j - 1] = table[j];
 101                 }
 102
 103                 /* build a new strvec */
 104                 len = ec_parsed_len(child_parsed);
 105                 childvec = ec_strvec_ndup(strvec, len,
 106                                         ec_strvec_len(strvec) - len);
 107                 if (childvec == NULL)
 108                         goto fail;
 109
 110                 memset(&result, 0, sizeof(result));
 111
 112                 ret = __ec_node_subset_parse(child_table, table_len - 1,
 113                                         childvec, &result);
 114                 ec_strvec_free(childvec);
 115                 childvec = NULL;
 116                 if (ret < 0)
 117                         goto fail;
 118
 119                 /* if result is not the best, ignore */
 120                 if (result.parsed_table_len + 1 <=
 121                                 best_result.parsed_table_len) {
 122                         ec_parsed_free(child_parsed);
 123                         child_parsed = NULL;
 124                         for (j = 0; j < result.parsed_table_len; j++)
 125                                 ec_parsed_free(result.parsed_table[j]);
 126                         ec_free(result.parsed_table);
 127                         memset(&result, 0, sizeof(result));
 128                         continue;
 129                 }
 130
 131                 /* replace the previous best result */
 132                 for (j = 0; j < best_result.parsed_table_len; j++)
 133                         ec_parsed_free(best_result.parsed_table[j]);
 134                 best_result.parsed_table[0] = child_parsed;
 135                 child_parsed = NULL;
 136                 for (j = 0; j < result.parsed_table_len; j++)
 137                         best_result.parsed_table[j+1] = result.parsed_table[j];
 138                 best_result.parsed_table_len = result.parsed_table_len + 1;
 139                 best_result.len = len + result.len;
 140                 ec_free(result.parsed_table);
 141         }
 142
 143         *out = best_result;
 144         ec_free(child_table);
 145
 146         return 0;
 147
 148  fail:
 149         ec_parsed_free(child_parsed);
 150         ec_strvec_free(childvec);
 151         for (j = 0; j < best_result.parsed_table_len; j++)
 152                 ec_parsed_free(best_result.parsed_table[j]);
 153         ec_free(best_result.parsed_table);
 154         ec_free(child_table);
 155         return -1;
 156 }
 157
 158 static struct ec_parsed *ec_node_subset_parse(const struct ec_node *gen_node,
 159         const struct ec_strvec *strvec)
 160 {
 161         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
 162         struct ec_parsed *parsed = NULL;
 163         struct parse_result result;
 164         struct ec_strvec *match_strvec;
 165         size_t i;
 166         int ret;
 167
 168         memset(&result, 0, sizeof(result));
 169
 170         parsed = ec_parsed();
 171         if (parsed == NULL)
 172                 goto fail;
 173
 174         ret = __ec_node_subset_parse(node->table, node->len, strvec, &result);
 175         if (ret < 0)
 176                 goto fail;
 177
 178         /* if no child node matches, return a matching empty strvec */
 179         if (result.parsed_table_len == 0) {
 180                 ec_free(result.parsed_table);
 181                 match_strvec = ec_strvec();
 182                 if (match_strvec == NULL)
 183                         goto fail;
 184                 ec_parsed_set_match(parsed, gen_node, match_strvec);
 185                 return parsed;
 186         }
 187
 188         for (i = 0; i < result.parsed_table_len; i++) {
 189                 ec_parsed_add_child(parsed, result.parsed_table[i]);
 190                 result.parsed_table[i] = NULL;
 191         }
 192         ec_free(result.parsed_table);
 193         result.parsed_table = NULL;
 194
 195         match_strvec = ec_strvec_ndup(strvec, 0, result.len);
 196         if (match_strvec == NULL)
 197                 goto fail;
 198
 199         ec_parsed_set_match(parsed, gen_node, match_strvec);
 200
 201         return parsed;
 202
 203  fail:
 204         for (i = 0; i < result.parsed_table_len; i++)
 205                 ec_parsed_free(result.parsed_table[i]);
 206         ec_free(result.parsed_table);
 207         ec_parsed_free(parsed);
 208
 209         return NULL;
 210 }
 211
 212 static struct ec_completed *
 213 __ec_node_subset_complete(struct ec_node **table, size_t table_len,
 214         const struct ec_strvec *strvec)
 215 {
 216         struct ec_completed *completed = NULL;
 217         struct ec_completed *child_completed = NULL;
 218         struct ec_strvec *childvec = NULL;
 219         struct ec_parsed *parsed = NULL;
 220         struct ec_node *save;
 221         size_t i, len;
 222
 223         /*
 224          * example with table = [a, b, c]
 225          * subset_complete([a,b,c], strvec) returns:
 226          *   complete(a, strvec) + complete(b, strvec) + complete(c, strvec) +
 227          *   + __subset_complete([b, c], childvec) if a matches
 228          *   + __subset_complete([a, c], childvec) if b matches
 229          *   + __subset_complete([a, b], childvec) if c matches
 230          */
 231
 232         completed = ec_completed();
 233         if (completed == NULL)
 234                 goto fail;
 235
 236         /* first, try to complete with each node of the table */
 237         for (i = 0; i < table_len; i++) {
 238                 if (table[i] == NULL)
 239                         continue;
 240
 241                 child_completed = ec_node_complete_strvec(table[i],
 242                         strvec);
 243
 244                 if (child_completed == NULL)
 245                         goto fail;
 246
 247                 ec_completed_merge(completed, child_completed);
 248                 child_completed = NULL;
 249         }
 250
 251         /* then, if a node matches, advance in strvec and try to complete with
 252          * all the other nodes */
 253         for (i = 0; i < table_len; i++) {
 254                 if (table[i] == NULL)
 255                         continue;
 256
 257                 parsed = ec_node_parse_strvec(table[i], strvec);
 258                 if (parsed == NULL)
 259                         goto fail;
 260
 261                 if (!ec_parsed_matches(parsed)) {
 262                         ec_parsed_free(parsed);
 263                         parsed = NULL;
 264                         continue;
 265                 }
 266
 267                 len = ec_parsed_len(parsed);
 268                 childvec = ec_strvec_ndup(strvec, len,
 269                                         ec_strvec_len(strvec) - len);
 270                 if (childvec == NULL)
 271                         goto fail;
 272
 273                 save = table[i];
 274                 table[i] = NULL;
 275                 child_completed = __ec_node_subset_complete(table,
 276                                                         table_len, childvec);
 277                 table[i] = save;
 278                 ec_strvec_free(childvec);
 279                 childvec = NULL;
 280
 281                 if (child_completed == NULL)
 282                         goto fail;
 283
 284                 ec_completed_merge(completed, child_completed);
 285                 child_completed = NULL;
 286
 287                 ec_parsed_free(parsed);
 288                 parsed = NULL;
 289         }
 290
 291         return completed;
 292 fail:
 293         ec_parsed_free(parsed);
 294         ec_completed_free(child_completed);
 295         ec_completed_free(completed);
 296
 297         return NULL;
 298 }
 299
 300 static struct ec_completed *ec_node_subset_complete(const struct ec_node *gen_node,
 301         const struct ec_strvec *strvec)
 302 {
 303         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
 304
 305         return __ec_node_subset_complete(node->table, node->len, strvec);
 306 }
 307
 308 static void ec_node_subset_free_priv(struct ec_node *gen_node)
 309 {
 310         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
 311         unsigned int i;
 312
 313         for (i = 0; i < node->len; i++)
 314                 ec_node_free(node->table[i]);
 315         ec_free(node->table);
 316 }
 317
 318 int ec_node_subset_add(struct ec_node *gen_node, struct ec_node *child)
 319 {
 320         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
 321         struct ec_node **table;
 322
 323         assert(node != NULL);
 324
 325         if (child == NULL)
 326                 return -EINVAL;
 327
 328         gen_node->flags &= ~EC_NODE_F_BUILT;
 329
 330         table = ec_realloc(node->table, (node->len + 1) * sizeof(*node->table));
 331         if (table == NULL) {
 332                 ec_node_free(child);
 333                 return -1;
 334         }
 335
 336         node->table = table;
 337         table[node->len] = child;
 338         node->len++;
 339
 340         child->parent = gen_node;
 341         TAILQ_INSERT_TAIL(&gen_node->children, child, next);
 342
 343         return 0;
 344 }
 345
 346 static struct ec_node_type ec_node_subset_type = {
 347         .name = "subset",
 348         .parse = ec_node_subset_parse,
 349         .complete = ec_node_subset_complete,
 350         .size = sizeof(struct ec_node_subset),
 351         .free_priv = ec_node_subset_free_priv,
 352 };
 353
 354 EC_NODE_TYPE_REGISTER(ec_node_subset_type);
 355
 356 struct ec_node *__ec_node_subset(const char *id, ...)
 357 {
 358         struct ec_node *gen_node = NULL;
 359         struct ec_node_subset *node = NULL;
 360         struct ec_node *child;
 361         va_list ap;
 362         int fail = 0;
 363
 364         va_start(ap, id);
 365
 366         gen_node = __ec_node(&ec_node_subset_type, id);
 367         node = (struct ec_node_subset *)gen_node;
 368         if (node == NULL)
 369                 fail = 1;;
 370
 371         for (child = va_arg(ap, struct ec_node *);
 372              child != EC_NODE_ENDLIST;
 373              child = va_arg(ap, struct ec_node *)) {
 374
 375                 /* on error, don't quit the loop to avoid leaks */
 376                 if (fail == 1 || child == NULL ||
 377                                 ec_node_subset_add(gen_node, child) < 0) {
 378                         fail = 1;
 379                         ec_node_free(child);
 380                 }
 381         }
 382
 383         if (fail == 1)
 384                 goto fail;
 385
 386         va_end(ap);
 387         return gen_node;
 388
 389 fail:
 390         ec_node_free(gen_node); /* will also free children */
 391         va_end(ap);
 392         return NULL;
 393 }
 394
 395 static int ec_node_subset_testcase(void)
 396 {
 397         struct ec_node *node;
 398         int ret = 0;
 399
 400         node = EC_NODE_SUBSET(NULL,
 401                 EC_NODE_OR(NULL,
 402                         ec_node_str(NULL, "foo"),
 403                         ec_node_str(NULL, "bar")),
 404                 ec_node_str(NULL, "bar"),
 405                 ec_node_str(NULL, "toto")
 406         );
 407         if (node == NULL) {
 408                 ec_log(EC_LOG_ERR, "cannot create node\n");
 409                 return -1;
 410         }
 411         ret |= EC_TEST_CHECK_PARSE(node, 0);
 412         ret |= EC_TEST_CHECK_PARSE(node, 1, "foo");
 413         ret |= EC_TEST_CHECK_PARSE(node, 1, "bar");
 414         ret |= EC_TEST_CHECK_PARSE(node, 2, "foo", "bar", "titi");
 415         ret |= EC_TEST_CHECK_PARSE(node, 3, "bar", "foo", "toto");
 416         ret |= EC_TEST_CHECK_PARSE(node, 1, "foo", "foo");
 417         ret |= EC_TEST_CHECK_PARSE(node, 2, "bar", "bar");
 418         ret |= EC_TEST_CHECK_PARSE(node, 2, "bar", "foo");
 419         ret |= EC_TEST_CHECK_PARSE(node, 0, " ");
 420         ret |= EC_TEST_CHECK_PARSE(node, 0, "foox");
 421         ec_node_free(node);
 422
 423         /* test completion */
 424         node = EC_NODE_SUBSET(NULL,
 425                 ec_node_str(NULL, "foo"),
 426                 ec_node_str(NULL, "bar"),
 427                 ec_node_str(NULL, "bar2"),
 428                 ec_node_str(NULL, "toto"),
 429                 ec_node_str(NULL, "titi")
 430         );
 431         if (node == NULL) {
 432                 ec_log(EC_LOG_ERR, "cannot create node\n");
 433                 return -1;
 434         }
 435         ret |= EC_TEST_CHECK_COMPLETE(node,
 436                 "", EC_NODE_ENDLIST,
 437                 "foo", "bar", "bar2", "toto", "titi", EC_NODE_ENDLIST,
 438                 "");
 439         ret |= EC_TEST_CHECK_COMPLETE(node,
 440                 "bar", "bar2", "", EC_NODE_ENDLIST,
 441                 "foo", "toto", "titi", EC_NODE_ENDLIST,
 442                 "");
 443         ret |= EC_TEST_CHECK_COMPLETE(node,
 444                 "f", EC_NODE_ENDLIST,
 445                 "oo", EC_NODE_ENDLIST,
 446                 "oo");
 447         ret |= EC_TEST_CHECK_COMPLETE(node,
 448                 "b", EC_NODE_ENDLIST,
 449                 "ar", "ar2", EC_NODE_ENDLIST,
 450                 "ar");
 451         ret |= EC_TEST_CHECK_COMPLETE(node,
 452                 "bar", EC_NODE_ENDLIST,
 453                 "", "2", EC_NODE_ENDLIST,
 454                 "");
 455         ret |= EC_TEST_CHECK_COMPLETE(node,
 456                 "bar", "b", EC_NODE_ENDLIST,
 457                 "ar2", EC_NODE_ENDLIST,
 458                 "ar2");
 459         ret |= EC_TEST_CHECK_COMPLETE(node,
 460                 "t", EC_NODE_ENDLIST,
 461                 "oto", "iti", EC_NODE_ENDLIST,
 462                 "");
 463         ret |= EC_TEST_CHECK_COMPLETE(node,
 464                 "to", EC_NODE_ENDLIST,
 465                 "to", EC_NODE_ENDLIST,
 466                 "to");
 467         ret |= EC_TEST_CHECK_COMPLETE(node,
 468                 "x", EC_NODE_ENDLIST,
 469                 EC_NODE_ENDLIST,
 470                 "");
 471         ec_node_free(node);
 472
 473         return ret;
 474 }
 475
 476 static struct ec_test ec_node_subset_test = {
 477         .name = "node_subset",
 478         .test = ec_node_subset_testcase,
 479 };
 480
 481 EC_TEST_REGISTER(ec_node_subset_test);