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