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