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