lib/ecoli_tk_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_tk.h>
  40 #include <ecoli_tk_subset.h>
  41 #include <ecoli_tk_str.h>
  42 #include <ecoli_tk_or.h>
  43 #include <ecoli_test.h>
  44
  45 struct ec_tk_subset {
  46         struct ec_tk gen;
  47         struct ec_tk **table;
  48         unsigned int len;
  49 };
  50
  51 struct parse_result {
  52         struct ec_parsed_tk **parsed_table; /* list of parsed tk */
  53         size_t parsed_table_len;            /* number of parsed tk */
  54         size_t len;                         /* consumed strings */
  55 };
  56
  57 static int __ec_tk_subset_parse(struct ec_tk **table, size_t table_len,
  58                                 const struct ec_strvec *strvec,
  59                                 struct parse_result *out)
  60 {
  61         struct ec_tk **child_table;
  62         struct ec_parsed_tk *child_parsed_tk = NULL;
  63         struct ec_strvec *childvec = NULL;
  64         size_t i, j, len = 0;
  65         struct parse_result best_result, result;
  66         int ret;
  67
  68         if (table_len == 0)
  69                 return 0;
  70
  71         memset(&best_result, 0, sizeof(best_result));
  72         best_result.parsed_table =
  73                 ec_calloc(table_len, sizeof(*best_result.parsed_table[0]));
  74         if (best_result.parsed_table == NULL)
  75                 goto fail;
  76
  77         child_table = ec_calloc(table_len - 1, sizeof(*child_table));
  78         if (child_table == NULL)
  79                 goto fail;
  80
  81         for (i = 0; i < table_len; i++) {
  82                 /* try to parse elt i */
  83                 child_parsed_tk = ec_tk_parse_tokens(table[i], strvec);
  84                 if (child_parsed_tk == NULL)
  85                         goto fail;
  86
  87                 if (!ec_parsed_tk_matches(child_parsed_tk)) {
  88                         ec_parsed_tk_free(child_parsed_tk);
  89                         child_parsed_tk = NULL;
  90                         continue;
  91                 }
  92
  93                 /* build a new table without elt i */
  94                 for (j = 0; j < table_len; j++) {
  95                         if (j < i)
  96                                 child_table[j] = table[j];
  97                         else if (j > i)
  98                                 child_table[j - 1] = table[j];
  99                 }
 100
 101                 /* build a new strvec */
 102                 len = ec_parsed_tk_len(child_parsed_tk);
 103                 childvec = ec_strvec_ndup(strvec, len,
 104                                         ec_strvec_len(strvec) - len);
 105                 if (childvec == NULL)
 106                         goto fail;
 107
 108                 memset(&result, 0, sizeof(result));
 109
 110                 ret = __ec_tk_subset_parse(child_table, table_len - 1,
 111                                         childvec, &result);
 112                 ec_strvec_free(childvec);
 113                 childvec = NULL;
 114                 if (ret < 0)
 115                         goto fail;
 116
 117                 /* if result is not the best, ignore */
 118                 if (result.parsed_table_len + 1 <=
 119                                 best_result.parsed_table_len) {
 120                         ec_parsed_tk_free(child_parsed_tk);
 121                         child_parsed_tk = NULL;
 122                         for (j = 0; j < result.parsed_table_len; j++)
 123                                 ec_parsed_tk_free(result.parsed_table[j]);
 124                         ec_free(result.parsed_table);
 125                         memset(&result, 0, sizeof(result));
 126                         continue;
 127                 }
 128
 129                 /* replace the previous best result */
 130                 for (j = 0; j < best_result.parsed_table_len; j++)
 131                         ec_parsed_tk_free(best_result.parsed_table[j]);
 132                 best_result.parsed_table[0] = child_parsed_tk;
 133                 child_parsed_tk = NULL;
 134                 for (j = 0; j < result.parsed_table_len; j++)
 135                         best_result.parsed_table[j+1] = result.parsed_table[j];
 136                 best_result.parsed_table_len = result.parsed_table_len + 1;
 137                 best_result.len = len + result.len;
 138                 ec_free(result.parsed_table);
 139         }
 140
 141         *out = best_result;
 142         ec_free(child_table);
 143
 144         return 0;
 145
 146  fail:
 147         ec_parsed_tk_free(child_parsed_tk);
 148         ec_strvec_free(childvec);
 149         for (j = 0; j < best_result.parsed_table_len; j++)
 150                 ec_parsed_tk_free(best_result.parsed_table[j]);
 151         ec_free(best_result.parsed_table);
 152         ec_free(child_table);
 153         return -1;
 154 }
 155
 156 static struct ec_parsed_tk *ec_tk_subset_parse(const struct ec_tk *gen_tk,
 157         const struct ec_strvec *strvec)
 158 {
 159         struct ec_tk_subset *tk = (struct ec_tk_subset *)gen_tk;
 160         struct ec_parsed_tk *parsed_tk = NULL;
 161         struct parse_result result;
 162         struct ec_strvec *match_strvec;
 163         size_t i;
 164         int ret;
 165
 166         memset(&result, 0, sizeof(result));
 167
 168         parsed_tk = ec_parsed_tk_new();
 169         if (parsed_tk == NULL)
 170                 goto fail;
 171
 172         ret = __ec_tk_subset_parse(tk->table, tk->len, strvec, &result);
 173         if (ret < 0)
 174                 goto fail;
 175
 176         if (result.parsed_table_len == 0) {
 177                 ec_free(result.parsed_table);
 178                 return parsed_tk;
 179         }
 180
 181         for (i = 0; i < result.parsed_table_len; i++) {
 182                 ec_parsed_tk_add_child(parsed_tk, result.parsed_table[i]);
 183                 result.parsed_table[i] = NULL;
 184         }
 185         ec_free(result.parsed_table);
 186         result.parsed_table = NULL;
 187
 188         match_strvec = ec_strvec_ndup(strvec, 0, result.len);
 189         if (match_strvec == NULL)
 190                 goto fail;
 191
 192         ec_parsed_tk_set_match(parsed_tk, gen_tk, match_strvec);
 193
 194         return parsed_tk;
 195
 196  fail:
 197         for (i = 0; i < result.parsed_table_len; i++)
 198                 ec_parsed_tk_free(result.parsed_table[i]);
 199         ec_free(result.parsed_table);
 200         ec_parsed_tk_free(parsed_tk);
 201
 202         return NULL;
 203 }
 204
 205 static struct ec_completed_tk *
 206 __ec_tk_subset_complete(struct ec_tk **table, size_t table_len,
 207         const struct ec_strvec *strvec)
 208 {
 209         struct ec_completed_tk *completed_tk = NULL;
 210         struct ec_completed_tk *child_completed_tk = NULL;
 211         struct ec_strvec *childvec = NULL;
 212         struct ec_parsed_tk *parsed_tk = NULL;
 213         struct ec_tk *save;
 214         size_t i, len;
 215
 216         /*
 217          * example with table = [a, b, c]
 218          * subset_complete([a,b,c], strvec) returns:
 219          *   complete(a, strvec) + complete(b, strvec) + complete(c, strvec) +
 220          *   + __subset_complete([b, c], childvec) if a matches
 221          *   + __subset_complete([a, c], childvec) if b matches
 222          *   + __subset_complete([a, b], childvec) if c matches
 223          */
 224
 225         completed_tk = ec_completed_tk_new();
 226         if (completed_tk == NULL)
 227                 goto fail;
 228
 229         /* first, try to complete with each token of the table */
 230         for (i = 0; i < table_len; i++) {
 231                 if (table[i] == NULL)
 232                         continue;
 233
 234                 child_completed_tk = ec_tk_complete_tokens(table[i],
 235                         strvec);
 236
 237                 if (child_completed_tk == NULL)
 238                         goto fail;
 239
 240                 ec_completed_tk_merge(completed_tk, child_completed_tk);
 241                 child_completed_tk = NULL;
 242         }
 243
 244         /* then, if a token matches, advance in strvec and try to complete with
 245          * all the other tokens */
 246         for (i = 0; i < table_len; i++) {
 247                 if (table[i] == NULL)
 248                         continue;
 249
 250                 parsed_tk = ec_tk_parse_tokens(table[i], strvec);
 251                 if (parsed_tk == NULL)
 252                         goto fail;
 253
 254                 if (!ec_parsed_tk_matches(parsed_tk)) {
 255                         ec_parsed_tk_free(parsed_tk);
 256                         parsed_tk = NULL;
 257                         continue;
 258                 }
 259
 260                 len = ec_parsed_tk_len(parsed_tk);
 261                 childvec = ec_strvec_ndup(strvec, len,
 262                                         ec_strvec_len(strvec) - len);
 263                 if (childvec == NULL)
 264                         goto fail;
 265
 266                 save = table[i];
 267                 table[i] = NULL;
 268                 child_completed_tk = __ec_tk_subset_complete(table,
 269                                                         table_len, childvec);
 270                 table[i] = save;
 271                 ec_strvec_free(childvec);
 272                 childvec = NULL;
 273
 274                 if (child_completed_tk == NULL)
 275                         goto fail;
 276
 277                 ec_completed_tk_merge(completed_tk, child_completed_tk);
 278                 child_completed_tk = NULL;
 279
 280                 ec_parsed_tk_free(parsed_tk);
 281                 parsed_tk = NULL;
 282         }
 283
 284         return completed_tk;
 285 fail:
 286         ec_parsed_tk_free(parsed_tk);
 287         ec_completed_tk_free(child_completed_tk);
 288         ec_completed_tk_free(completed_tk);
 289
 290         return NULL;
 291 }
 292
 293 static struct ec_completed_tk *ec_tk_subset_complete(const struct ec_tk *gen_tk,
 294         const struct ec_strvec *strvec)
 295 {
 296         struct ec_tk_subset *tk = (struct ec_tk_subset *)gen_tk;
 297
 298         return __ec_tk_subset_complete(tk->table, tk->len, strvec);
 299 }
 300
 301 static void ec_tk_subset_free_priv(struct ec_tk *gen_tk)
 302 {
 303         struct ec_tk_subset *tk = (struct ec_tk_subset *)gen_tk;
 304         unsigned int i;
 305
 306         for (i = 0; i < tk->len; i++)
 307                 ec_tk_free(tk->table[i]);
 308         ec_free(tk->table);
 309 }
 310
 311 int ec_tk_subset_add(struct ec_tk *gen_tk, struct ec_tk *child)
 312 {
 313         struct ec_tk_subset *tk = (struct ec_tk_subset *)gen_tk;
 314         struct ec_tk **table;
 315
 316         assert(tk != NULL);
 317
 318         if (child == NULL)
 319                 return -EINVAL;
 320
 321         gen_tk->flags &= ~EC_TK_F_BUILT;
 322
 323         table = ec_realloc(tk->table, (tk->len + 1) * sizeof(*tk->table));
 324         if (table == NULL) {
 325                 ec_tk_free(child);
 326                 return -1;
 327         }
 328
 329         tk->table = table;
 330         table[tk->len] = child;
 331         tk->len++;
 332
 333         child->parent = gen_tk;
 334         TAILQ_INSERT_TAIL(&gen_tk->children, child, next);
 335
 336         return 0;
 337 }
 338
 339 static struct ec_tk_type ec_tk_subset_type = {
 340         .name = "tk_subset",
 341         .parse = ec_tk_subset_parse,
 342         .complete = ec_tk_subset_complete,
 343         .free_priv = ec_tk_subset_free_priv,
 344 };
 345
 346 EC_TK_TYPE_REGISTER(ec_tk_subset_type);
 347
 348 struct ec_tk *ec_tk_subset(const char *id)
 349 {
 350         struct ec_tk *gen_tk = NULL;
 351         struct ec_tk_subset *tk = NULL;
 352
 353         gen_tk = ec_tk_new(id, &ec_tk_subset_type, sizeof(*tk));
 354         if (gen_tk == NULL)
 355                 return NULL;
 356
 357         tk = (struct ec_tk_subset *)gen_tk;
 358         tk->table = NULL;
 359         tk->len = 0;
 360
 361         return gen_tk;
 362 }
 363
 364 struct ec_tk *__ec_tk_subset(const char *id, ...)
 365 {
 366         struct ec_tk *gen_tk = NULL;
 367         struct ec_tk_subset *tk = NULL;
 368         struct ec_tk *child;
 369         va_list ap;
 370         int fail = 0;
 371
 372         va_start(ap, id);
 373
 374         gen_tk = ec_tk_subset(id);
 375         tk = (struct ec_tk_subset *)gen_tk;
 376         if (tk == NULL)
 377                 fail = 1;;
 378
 379         for (child = va_arg(ap, struct ec_tk *);
 380              child != EC_TK_ENDLIST;
 381              child = va_arg(ap, struct ec_tk *)) {
 382
 383                 /* on error, don't quit the loop to avoid leaks */
 384                 if (fail == 1 || child == NULL ||
 385                                 ec_tk_subset_add(gen_tk, child) < 0) {
 386                         fail = 1;
 387                         ec_tk_free(child);
 388                 }
 389         }
 390
 391         if (fail == 1)
 392                 goto fail;
 393
 394         va_end(ap);
 395         return gen_tk;
 396
 397 fail:
 398         ec_tk_free(gen_tk); /* will also free children */
 399         va_end(ap);
 400         return NULL;
 401 }
 402
 403 static int ec_tk_subset_testcase(void)
 404 {
 405         struct ec_tk *tk;
 406         int ret = 0;
 407
 408         tk = EC_TK_SUBSET(NULL,
 409                 EC_TK_OR(NULL,
 410                         ec_tk_str(NULL, "foo"),
 411                         ec_tk_str(NULL, "bar")),
 412                 ec_tk_str(NULL, "bar"),
 413                 ec_tk_str(NULL, "toto")
 414         );
 415         if (tk == NULL) {
 416                 ec_log(EC_LOG_ERR, "cannot create tk\n");
 417                 return -1;
 418         }
 419         ret |= EC_TEST_CHECK_TK_PARSE(tk, 1, "foo");
 420         ret |= EC_TEST_CHECK_TK_PARSE(tk, 1, "bar");
 421         ret |= EC_TEST_CHECK_TK_PARSE(tk, 2, "foo", "bar", "titi");
 422         ret |= EC_TEST_CHECK_TK_PARSE(tk, 3, "bar", "foo", "toto");
 423         ret |= EC_TEST_CHECK_TK_PARSE(tk, 1, "foo", "foo");
 424         ret |= EC_TEST_CHECK_TK_PARSE(tk, 2, "bar", "bar");
 425         ret |= EC_TEST_CHECK_TK_PARSE(tk, 2, "bar", "foo");
 426         ret |= EC_TEST_CHECK_TK_PARSE(tk, -1, " ");
 427         ret |= EC_TEST_CHECK_TK_PARSE(tk, -1, "foox");
 428         ret |= EC_TEST_CHECK_TK_PARSE(tk, -1, "titi");
 429         ret |= EC_TEST_CHECK_TK_PARSE(tk, -1, "");
 430         ec_tk_free(tk);
 431
 432         /* test completion */
 433         tk = EC_TK_SUBSET(NULL,
 434                 ec_tk_str(NULL, "foo"),
 435                 ec_tk_str(NULL, "bar"),
 436                 ec_tk_str(NULL, "bar2"),
 437                 ec_tk_str(NULL, "toto"),
 438                 ec_tk_str(NULL, "titi")
 439         );
 440         if (tk == NULL) {
 441                 ec_log(EC_LOG_ERR, "cannot create tk\n");
 442                 return -1;
 443         }
 444         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 445                 "", EC_TK_ENDLIST,
 446                 "foo", "bar", "bar2", "toto", "titi", EC_TK_ENDLIST,
 447                 "");
 448         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 449                 "bar", "bar2", "", EC_TK_ENDLIST,
 450                 "foo", "toto", "titi", EC_TK_ENDLIST,
 451                 "");
 452         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 453                 "f", EC_TK_ENDLIST,
 454                 "oo", EC_TK_ENDLIST,
 455                 "oo");
 456         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 457                 "b", EC_TK_ENDLIST,
 458                 "ar", "ar2", EC_TK_ENDLIST,
 459                 "ar");
 460         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 461                 "bar", EC_TK_ENDLIST,
 462                 "", "2", EC_TK_ENDLIST,
 463                 "");
 464         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 465                 "bar", "b", EC_TK_ENDLIST,
 466                 "ar2", EC_TK_ENDLIST,
 467                 "ar2");
 468         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 469                 "t", EC_TK_ENDLIST,
 470                 "oto", "iti", EC_TK_ENDLIST,
 471                 "");
 472         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 473                 "to", EC_TK_ENDLIST,
 474                 "to", EC_TK_ENDLIST,
 475                 "to");
 476         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 477                 "x", EC_TK_ENDLIST,
 478                 EC_TK_ENDLIST,
 479                 "");
 480         ec_tk_free(tk);
 481
 482         return ret;
 483 }
 484
 485 static struct ec_test ec_tk_subset_test = {
 486         .name = "tk_subset",
 487         .test = ec_tk_subset_testcase,
 488 };
 489
 490 EC_TEST_REGISTER(ec_tk_subset_test);