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