src/ecoli_node_subset.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <assert.h>
   9 #include <stdarg.h>
  10 #include <errno.h>
  11 #include <stdbool.h>
  12
  13 #include <ecoli_malloc.h>
  14 #include <ecoli_log.h>
  15 #include <ecoli_strvec.h>
  16 #include <ecoli_node.h>
  17 #include <ecoli_parse.h>
  18 #include <ecoli_complete.h>
  19 #include <ecoli_node_subset.h>
  20 #include <ecoli_node_str.h>
  21 #include <ecoli_node_or.h>
  22 #include <ecoli_test.h>
  23
  24 EC_LOG_TYPE_REGISTER(node_subset);
  25
  26 struct ec_node_subset {
  27         struct ec_node gen;
  28         struct ec_node **table;
  29         unsigned int len;
  30 };
  31
  32 struct parse_result {
  33         size_t parse_len;           /* number of parsed nodes */
  34         size_t len;                 /* consumed strings */
  35 };
  36
  37 /* recursively find the longest list of nodes that matches: the state is
  38  * updated accordingly. */
  39 static int
  40 __ec_node_subset_parse(struct parse_result *out, struct ec_node **table,
  41                 size_t table_len, struct ec_parse *state,
  42                 const struct ec_strvec *strvec)
  43 {
  44         struct ec_node **child_table;
  45         struct ec_strvec *childvec = NULL;
  46         size_t i, j, len = 0;
  47         struct parse_result best_result, result;
  48         struct ec_parse *best_parse = NULL;
  49         int ret;
  50
  51         if (table_len == 0)
  52                 return 0;
  53
  54         memset(&best_result, 0, sizeof(best_result));
  55
  56         child_table = ec_calloc(table_len - 1, sizeof(*child_table));
  57         if (child_table == NULL)
  58                 goto fail;
  59
  60         for (i = 0; i < table_len; i++) {
  61                 /* try to parse elt i */
  62                 ret = ec_node_parse_child(table[i], state, strvec);
  63                 if (ret < 0)
  64                         goto fail;
  65
  66                 if (ret == EC_PARSE_NOMATCH)
  67                         continue;
  68
  69                 /* build a new table without elt i */
  70                 for (j = 0; j < table_len; j++) {
  71                         if (j < i)
  72                                 child_table[j] = table[j];
  73                         else if (j > i)
  74                                 child_table[j - 1] = table[j];
  75                 }
  76
  77                 /* build a new strvec (ret is the len of matched strvec) */
  78                 len = ret;
  79                 childvec = ec_strvec_ndup(strvec, len,
  80                                         ec_strvec_len(strvec) - len);
  81                 if (childvec == NULL)
  82                         goto fail;
  83
  84                 memset(&result, 0, sizeof(result));
  85                 ret = __ec_node_subset_parse(&result, child_table,
  86                                         table_len - 1, state, childvec);
  87                 ec_strvec_free(childvec);
  88                 childvec = NULL;
  89                 if (ret < 0)
  90                         goto fail;
  91
  92                 /* if result is not the best, ignore */
  93                 if (result.parse_len < best_result.parse_len) {
  94                         memset(&result, 0, sizeof(result));
  95                         ec_parse_del_last_child(state);
  96                         continue;
  97                 }
  98
  99                 /* replace the previous best result */
 100                 ec_parse_free(best_parse);
 101                 best_parse = ec_parse_get_last_child(state);
 102                 ec_parse_unlink_child(state, best_parse);
 103
 104                 best_result.parse_len = result.parse_len + 1;
 105                 best_result.len = len + result.len;
 106
 107                 memset(&result, 0, sizeof(result));
 108         }
 109
 110         *out = best_result;
 111         ec_free(child_table);
 112         if (best_parse != NULL)
 113                 ec_parse_link_child(state, best_parse);
 114
 115         return 0;
 116
 117  fail:
 118         ec_parse_free(best_parse);
 119         ec_strvec_free(childvec);
 120         ec_free(child_table);
 121         return -1;
 122 }
 123
 124 static int
 125 ec_node_subset_parse(const struct ec_node *gen_node,
 126                 struct ec_parse *state,
 127                 const struct ec_strvec *strvec)
 128 {
 129         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
 130         struct ec_parse *parse = NULL;
 131         struct parse_result result;
 132         int ret;
 133
 134         memset(&result, 0, sizeof(result));
 135
 136         ret = __ec_node_subset_parse(&result, node->table,
 137                                 node->len, state, strvec);
 138         if (ret < 0)
 139                 goto fail;
 140
 141         /* if no child node matches, return a matching empty strvec */
 142         if (result.parse_len == 0)
 143                 return 0;
 144
 145         return result.len;
 146
 147  fail:
 148         ec_parse_free(parse);
 149         return ret;
 150 }
 151
 152 static int
 153 __ec_node_subset_complete(struct ec_node **table, size_t table_len,
 154                         struct ec_comp *comp,
 155                         const struct ec_strvec *strvec)
 156 {
 157         struct ec_parse *parse = ec_comp_get_state(comp);
 158         struct ec_strvec *childvec = NULL;
 159         struct ec_node *save;
 160         size_t i, len;
 161         int ret;
 162
 163         /*
 164          * example with table = [a, b, c]
 165          * subset_complete([a,b,c], strvec) returns:
 166          *   complete(a, strvec) + complete(b, strvec) + complete(c, strvec) +
 167          *   + __subset_complete([b, c], childvec) if a matches
 168          *   + __subset_complete([a, c], childvec) if b matches
 169          *   + __subset_complete([a, b], childvec) if c matches
 170          */
 171
 172         /* first, try to complete with each node of the table */
 173         for (i = 0; i < table_len; i++) {
 174                 if (table[i] == NULL)
 175                         continue;
 176
 177                 ret = ec_node_complete_child(table[i],
 178                                         comp, strvec);
 179                 if (ret < 0)
 180                         goto fail;
 181         }
 182
 183         /* then, if a node matches, advance in strvec and try to complete with
 184          * all the other nodes */
 185         for (i = 0; i < table_len; i++) {
 186                 if (table[i] == NULL)
 187                         continue;
 188
 189                 ret = ec_node_parse_child(table[i], parse, strvec);
 190                 if (ret < 0)
 191                         goto fail;
 192
 193                 if (ret == EC_PARSE_NOMATCH)
 194                         continue;
 195
 196                 len = ret;
 197                 childvec = ec_strvec_ndup(strvec, len,
 198                                         ec_strvec_len(strvec) - len);
 199                 if (childvec == NULL) {
 200                         ec_parse_del_last_child(parse);
 201                         goto fail;
 202                 }
 203
 204                 save = table[i];
 205                 table[i] = NULL;
 206                 ret = __ec_node_subset_complete(table, table_len,
 207                                                 comp, childvec);
 208                 table[i] = save;
 209                 ec_strvec_free(childvec);
 210                 childvec = NULL;
 211                 ec_parse_del_last_child(parse);
 212
 213                 if (ret < 0)
 214                         goto fail;
 215         }
 216
 217         return 0;
 218
 219 fail:
 220         return -1;
 221 }
 222
 223 static int
 224 ec_node_subset_complete(const struct ec_node *gen_node,
 225                         struct ec_comp *comp,
 226                         const struct ec_strvec *strvec)
 227 {
 228         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
 229
 230         return __ec_node_subset_complete(node->table, node->len, comp,
 231                                         strvec);
 232 }
 233
 234 static void ec_node_subset_free_priv(struct ec_node *gen_node)
 235 {
 236         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
 237         size_t i;
 238
 239         for (i = 0; i < node->len; i++)
 240                 ec_node_free(node->table[i]);
 241         ec_free(node->table);
 242 }
 243
 244 static size_t
 245 ec_node_subset_get_children_count(const struct ec_node *gen_node)
 246 {
 247         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
 248         return node->len;
 249 }
 250
 251 static int
 252 ec_node_subset_get_child(const struct ec_node *gen_node, size_t i,
 253                         struct ec_node **child, unsigned int *refs)
 254 {
 255         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
 256
 257         if (i >= node->len)
 258                 return -1;
 259
 260         *child = node->table[i];
 261         *refs = 1;
 262         return 0;
 263 }
 264
 265 static struct ec_node_type ec_node_subset_type = {
 266         .name = "subset",
 267         .parse = ec_node_subset_parse,
 268         .complete = ec_node_subset_complete,
 269         .size = sizeof(struct ec_node_subset),
 270         .free_priv = ec_node_subset_free_priv,
 271         .get_children_count = ec_node_subset_get_children_count,
 272         .get_child = ec_node_subset_get_child,
 273 };
 274
 275 EC_NODE_TYPE_REGISTER(ec_node_subset_type);
 276
 277 int ec_node_subset_add(struct ec_node *gen_node, struct ec_node *child)
 278 {
 279         struct ec_node_subset *node = (struct ec_node_subset *)gen_node;
 280         struct ec_node **table;
 281
 282         assert(node != NULL); // XXX specific assert for it, like in libyang
 283
 284         if (child == NULL) {
 285                 errno = EINVAL;
 286                 goto fail;
 287         }
 288
 289         if (ec_node_check_type(gen_node, &ec_node_subset_type) < 0)
 290                 goto fail;
 291
 292         table = ec_realloc(node->table, (node->len + 1) * sizeof(*node->table));
 293         if (table == NULL) {
 294                 ec_node_free(child);
 295                 return -1;
 296         }
 297
 298         node->table = table;
 299         table[node->len] = child;
 300         node->len++;
 301
 302         return 0;
 303
 304 fail:
 305         ec_node_free(child);
 306         return -1;
 307 }
 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_from_type(&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 testres = 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         testres |= EC_TEST_CHECK_PARSE(node, 0);
 366         testres |= EC_TEST_CHECK_PARSE(node, 1, "foo");
 367         testres |= EC_TEST_CHECK_PARSE(node, 1, "bar");
 368         testres |= EC_TEST_CHECK_PARSE(node, 2, "foo", "bar", "titi");
 369         testres |= EC_TEST_CHECK_PARSE(node, 3, "bar", "foo", "toto");
 370         testres |= EC_TEST_CHECK_PARSE(node, 1, "foo", "foo");
 371         testres |= EC_TEST_CHECK_PARSE(node, 2, "bar", "bar");
 372         testres |= EC_TEST_CHECK_PARSE(node, 2, "bar", "foo");
 373         testres |= EC_TEST_CHECK_PARSE(node, 0, " ");
 374         testres |= 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         testres |= EC_TEST_CHECK_COMPLETE(node,
 390                 "", EC_NODE_ENDLIST,
 391                 "foo", "bar", "bar2", "toto", "titi", EC_NODE_ENDLIST);
 392         testres |= EC_TEST_CHECK_COMPLETE(node,
 393                 "", EC_NODE_ENDLIST,
 394                 "bar2", "bar", "foo", "toto", "titi", EC_NODE_ENDLIST);
 395         testres |= EC_TEST_CHECK_COMPLETE(node,
 396                 "bar", "bar2", "", EC_NODE_ENDLIST,
 397                 "foo", "toto", "titi", EC_NODE_ENDLIST);
 398         testres |= EC_TEST_CHECK_COMPLETE(node,
 399                 "f", EC_NODE_ENDLIST,
 400                 "foo", EC_NODE_ENDLIST);
 401         testres |= EC_TEST_CHECK_COMPLETE(node,
 402                 "b", EC_NODE_ENDLIST,
 403                 "bar", "bar2", EC_NODE_ENDLIST);
 404         testres |= EC_TEST_CHECK_COMPLETE(node,
 405                 "bar", EC_NODE_ENDLIST,
 406                 "bar", "bar2", EC_NODE_ENDLIST);
 407         testres |= EC_TEST_CHECK_COMPLETE(node,
 408                 "bar", "b", EC_NODE_ENDLIST,
 409                 "bar2", EC_NODE_ENDLIST);
 410         testres |= EC_TEST_CHECK_COMPLETE(node,
 411                 "t", EC_NODE_ENDLIST,
 412                 "toto", "titi", EC_NODE_ENDLIST);
 413         testres |= EC_TEST_CHECK_COMPLETE(node,
 414                 "to", EC_NODE_ENDLIST,
 415                 "toto", EC_NODE_ENDLIST);
 416         testres |= EC_TEST_CHECK_COMPLETE(node,
 417                 "x", EC_NODE_ENDLIST,
 418                 EC_NODE_ENDLIST);
 419         ec_node_free(node);
 420
 421         return testres;
 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);