lib/ecoli_node_subset.c

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