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 no child tk matches, return a matching empty strvec */
 177         if (result.parsed_table_len == 0) {
 178                 ec_free(result.parsed_table);
 179                 match_strvec = ec_strvec_new();
 180                 if (match_strvec == NULL)
 181                         goto fail;
 182                 ec_parsed_tk_set_match(parsed_tk, gen_tk, match_strvec);
 183                 return parsed_tk;
 184         }
 185
 186         for (i = 0; i < result.parsed_table_len; i++) {
 187                 ec_parsed_tk_add_child(parsed_tk, result.parsed_table[i]);
 188                 result.parsed_table[i] = NULL;
 189         }
 190         ec_free(result.parsed_table);
 191         result.parsed_table = NULL;
 192
 193         match_strvec = ec_strvec_ndup(strvec, 0, result.len);
 194         if (match_strvec == NULL)
 195                 goto fail;
 196
 197         ec_parsed_tk_set_match(parsed_tk, gen_tk, match_strvec);
 198
 199         return parsed_tk;
 200
 201  fail:
 202         for (i = 0; i < result.parsed_table_len; i++)
 203                 ec_parsed_tk_free(result.parsed_table[i]);
 204         ec_free(result.parsed_table);
 205         ec_parsed_tk_free(parsed_tk);
 206
 207         return NULL;
 208 }
 209
 210 static struct ec_completed_tk *
 211 __ec_tk_subset_complete(struct ec_tk **table, size_t table_len,
 212         const struct ec_strvec *strvec)
 213 {
 214         struct ec_completed_tk *completed_tk = NULL;
 215         struct ec_completed_tk *child_completed_tk = NULL;
 216         struct ec_strvec *childvec = NULL;
 217         struct ec_parsed_tk *parsed_tk = NULL;
 218         struct ec_tk *save;
 219         size_t i, len;
 220
 221         /*
 222          * example with table = [a, b, c]
 223          * subset_complete([a,b,c], strvec) returns:
 224          *   complete(a, strvec) + complete(b, strvec) + complete(c, strvec) +
 225          *   + __subset_complete([b, c], childvec) if a matches
 226          *   + __subset_complete([a, c], childvec) if b matches
 227          *   + __subset_complete([a, b], childvec) if c matches
 228          */
 229
 230         completed_tk = ec_completed_tk_new();
 231         if (completed_tk == NULL)
 232                 goto fail;
 233
 234         /* first, try to complete with each token of the table */
 235         for (i = 0; i < table_len; i++) {
 236                 if (table[i] == NULL)
 237                         continue;
 238
 239                 child_completed_tk = ec_tk_complete_tokens(table[i],
 240                         strvec);
 241
 242                 if (child_completed_tk == NULL)
 243                         goto fail;
 244
 245                 ec_completed_tk_merge(completed_tk, child_completed_tk);
 246                 child_completed_tk = NULL;
 247         }
 248
 249         /* then, if a token matches, advance in strvec and try to complete with
 250          * all the other tokens */
 251         for (i = 0; i < table_len; i++) {
 252                 if (table[i] == NULL)
 253                         continue;
 254
 255                 parsed_tk = ec_tk_parse_tokens(table[i], strvec);
 256                 if (parsed_tk == NULL)
 257                         goto fail;
 258
 259                 if (!ec_parsed_tk_matches(parsed_tk)) {
 260                         ec_parsed_tk_free(parsed_tk);
 261                         parsed_tk = NULL;
 262                         continue;
 263                 }
 264
 265                 len = ec_parsed_tk_len(parsed_tk);
 266                 childvec = ec_strvec_ndup(strvec, len,
 267                                         ec_strvec_len(strvec) - len);
 268                 if (childvec == NULL)
 269                         goto fail;
 270
 271                 save = table[i];
 272                 table[i] = NULL;
 273                 child_completed_tk = __ec_tk_subset_complete(table,
 274                                                         table_len, childvec);
 275                 table[i] = save;
 276                 ec_strvec_free(childvec);
 277                 childvec = NULL;
 278
 279                 if (child_completed_tk == NULL)
 280                         goto fail;
 281
 282                 ec_completed_tk_merge(completed_tk, child_completed_tk);
 283                 child_completed_tk = NULL;
 284
 285                 ec_parsed_tk_free(parsed_tk);
 286                 parsed_tk = NULL;
 287         }
 288
 289         return completed_tk;
 290 fail:
 291         ec_parsed_tk_free(parsed_tk);
 292         ec_completed_tk_free(child_completed_tk);
 293         ec_completed_tk_free(completed_tk);
 294
 295         return NULL;
 296 }
 297
 298 static struct ec_completed_tk *ec_tk_subset_complete(const struct ec_tk *gen_tk,
 299         const struct ec_strvec *strvec)
 300 {
 301         struct ec_tk_subset *tk = (struct ec_tk_subset *)gen_tk;
 302
 303         return __ec_tk_subset_complete(tk->table, tk->len, strvec);
 304 }
 305
 306 static void ec_tk_subset_free_priv(struct ec_tk *gen_tk)
 307 {
 308         struct ec_tk_subset *tk = (struct ec_tk_subset *)gen_tk;
 309         unsigned int i;
 310
 311         for (i = 0; i < tk->len; i++)
 312                 ec_tk_free(tk->table[i]);
 313         ec_free(tk->table);
 314 }
 315
 316 int ec_tk_subset_add(struct ec_tk *gen_tk, struct ec_tk *child)
 317 {
 318         struct ec_tk_subset *tk = (struct ec_tk_subset *)gen_tk;
 319         struct ec_tk **table;
 320
 321         assert(tk != NULL);
 322
 323         if (child == NULL)
 324                 return -EINVAL;
 325
 326         gen_tk->flags &= ~EC_TK_F_BUILT;
 327
 328         table = ec_realloc(tk->table, (tk->len + 1) * sizeof(*tk->table));
 329         if (table == NULL) {
 330                 ec_tk_free(child);
 331                 return -1;
 332         }
 333
 334         tk->table = table;
 335         table[tk->len] = child;
 336         tk->len++;
 337
 338         child->parent = gen_tk;
 339         TAILQ_INSERT_TAIL(&gen_tk->children, child, next);
 340
 341         return 0;
 342 }
 343
 344 static struct ec_tk_type ec_tk_subset_type = {
 345         .name = "tk_subset",
 346         .parse = ec_tk_subset_parse,
 347         .complete = ec_tk_subset_complete,
 348         .free_priv = ec_tk_subset_free_priv,
 349 };
 350
 351 EC_TK_TYPE_REGISTER(ec_tk_subset_type);
 352
 353 struct ec_tk *ec_tk_subset(const char *id)
 354 {
 355         struct ec_tk *gen_tk = NULL;
 356         struct ec_tk_subset *tk = NULL;
 357
 358         gen_tk = ec_tk_new(id, &ec_tk_subset_type, sizeof(*tk));
 359         if (gen_tk == NULL)
 360                 return NULL;
 361
 362         tk = (struct ec_tk_subset *)gen_tk;
 363         tk->table = NULL;
 364         tk->len = 0;
 365
 366         return gen_tk;
 367 }
 368
 369 struct ec_tk *__ec_tk_subset(const char *id, ...)
 370 {
 371         struct ec_tk *gen_tk = NULL;
 372         struct ec_tk_subset *tk = NULL;
 373         struct ec_tk *child;
 374         va_list ap;
 375         int fail = 0;
 376
 377         va_start(ap, id);
 378
 379         gen_tk = ec_tk_subset(id);
 380         tk = (struct ec_tk_subset *)gen_tk;
 381         if (tk == NULL)
 382                 fail = 1;;
 383
 384         for (child = va_arg(ap, struct ec_tk *);
 385              child != EC_TK_ENDLIST;
 386              child = va_arg(ap, struct ec_tk *)) {
 387
 388                 /* on error, don't quit the loop to avoid leaks */
 389                 if (fail == 1 || child == NULL ||
 390                                 ec_tk_subset_add(gen_tk, child) < 0) {
 391                         fail = 1;
 392                         ec_tk_free(child);
 393                 }
 394         }
 395
 396         if (fail == 1)
 397                 goto fail;
 398
 399         va_end(ap);
 400         return gen_tk;
 401
 402 fail:
 403         ec_tk_free(gen_tk); /* will also free children */
 404         va_end(ap);
 405         return NULL;
 406 }
 407
 408 static int ec_tk_subset_testcase(void)
 409 {
 410         struct ec_tk *tk;
 411         int ret = 0;
 412
 413         tk = EC_TK_SUBSET(NULL,
 414                 EC_TK_OR(NULL,
 415                         ec_tk_str(NULL, "foo"),
 416                         ec_tk_str(NULL, "bar")),
 417                 ec_tk_str(NULL, "bar"),
 418                 ec_tk_str(NULL, "toto")
 419         );
 420         if (tk == NULL) {
 421                 ec_log(EC_LOG_ERR, "cannot create tk\n");
 422                 return -1;
 423         }
 424         ret |= EC_TEST_CHECK_TK_PARSE(tk, 0);
 425         ret |= EC_TEST_CHECK_TK_PARSE(tk, 1, "foo");
 426         ret |= EC_TEST_CHECK_TK_PARSE(tk, 1, "bar");
 427         ret |= EC_TEST_CHECK_TK_PARSE(tk, 2, "foo", "bar", "titi");
 428         ret |= EC_TEST_CHECK_TK_PARSE(tk, 3, "bar", "foo", "toto");
 429         ret |= EC_TEST_CHECK_TK_PARSE(tk, 1, "foo", "foo");
 430         ret |= EC_TEST_CHECK_TK_PARSE(tk, 2, "bar", "bar");
 431         ret |= EC_TEST_CHECK_TK_PARSE(tk, 2, "bar", "foo");
 432         ret |= EC_TEST_CHECK_TK_PARSE(tk, 0, " ");
 433         ret |= EC_TEST_CHECK_TK_PARSE(tk, 0, "foox");
 434         ec_tk_free(tk);
 435
 436         /* test completion */
 437         tk = EC_TK_SUBSET(NULL,
 438                 ec_tk_str(NULL, "foo"),
 439                 ec_tk_str(NULL, "bar"),
 440                 ec_tk_str(NULL, "bar2"),
 441                 ec_tk_str(NULL, "toto"),
 442                 ec_tk_str(NULL, "titi")
 443         );
 444         if (tk == NULL) {
 445                 ec_log(EC_LOG_ERR, "cannot create tk\n");
 446                 return -1;
 447         }
 448         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 449                 "", EC_TK_ENDLIST,
 450                 "foo", "bar", "bar2", "toto", "titi", EC_TK_ENDLIST,
 451                 "");
 452         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 453                 "bar", "bar2", "", EC_TK_ENDLIST,
 454                 "foo", "toto", "titi", EC_TK_ENDLIST,
 455                 "");
 456         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 457                 "f", EC_TK_ENDLIST,
 458                 "oo", EC_TK_ENDLIST,
 459                 "oo");
 460         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 461                 "b", EC_TK_ENDLIST,
 462                 "ar", "ar2", EC_TK_ENDLIST,
 463                 "ar");
 464         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 465                 "bar", EC_TK_ENDLIST,
 466                 "", "2", EC_TK_ENDLIST,
 467                 "");
 468         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 469                 "bar", "b", EC_TK_ENDLIST,
 470                 "ar2", EC_TK_ENDLIST,
 471                 "ar2");
 472         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 473                 "t", EC_TK_ENDLIST,
 474                 "oto", "iti", EC_TK_ENDLIST,
 475                 "");
 476         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 477                 "to", EC_TK_ENDLIST,
 478                 "to", EC_TK_ENDLIST,
 479                 "to");
 480         ret |= EC_TEST_CHECK_TK_COMPLETE(tk,
 481                 "x", EC_TK_ENDLIST,
 482                 EC_TK_ENDLIST,
 483                 "");
 484         ec_tk_free(tk);
 485
 486         return ret;
 487 }
 488
 489 static struct ec_test ec_tk_subset_test = {
 490         .name = "tk_subset",
 491         .test = ec_tk_subset_testcase,
 492 };
 493
 494 EC_TEST_REGISTER(ec_tk_subset_test);