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