src/get.c

   1 /*
   2  * parser.c: parse a configuration file according to a grammar
   3  *
   4  * Copyright (C) 2007-2016 David Lutterkort
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
  19  *
  20  * Author: David Lutterkort <dlutter@redhat.com>
  21  */
  22
  23 #include <config.h>
  24
  25 #include <regex.h>
  26 #include <stdarg.h>
  27
  28 #include "regexp.h"
  29 #include "list.h"
  30 #include "internal.h"
  31 #include "memory.h"
  32 #include "info.h"
  33 #include "lens.h"
  34 #include "errcode.h"
  35
  36 /* Our favorite error message */
  37 static const char *const short_iteration =
  38     "Iterated lens matched less than it should";
  39
  40 struct seq {
  41     struct seq *next;
  42     const char *name;
  43     int value;
  44 };
  45
  46 struct state {
  47     struct info      *info;
  48     struct span      *span;
  49     const char       *text;
  50     struct seq       *seqs;
  51     char             *key;
  52     char             *value;     /* GET_STORE leaves a value here */
  53     struct lns_error *error;
  54     /* We use the registers from a regular expression match to keep track
  55      * of the substring we are currently looking at. REGS are the registers
  56      * from the last regexp match; NREG is the number of the register
  57      * in REGS that describes the substring we are currently looking at.
  58      *
  59      * We adjust NREG as we traverse lenses either because we know the
  60      * grouping structure of lenses (for L_STAR, the child lens is always
  61      * in NREG + 1) or by looking at the number of groups in a sublens (as
  62      * we move from one child of L_CONCAT to the next, we need to add 1 +
  63      * number of groups of that child to NREG) How NREG is adjusted is
  64      * closely related to how the REGEXP_* routines build up bigger regexps
  65      * from smaller ones.
  66      */
  67     struct re_registers *regs;
  68     uint                 nreg;
  69 };
  70
  71 /* Used by recursive lenses to stack intermediate results
  72    Frames are used for a few different purposes:
  73
  74    (1) to save results from individual lenses that are later gathered and
  75        combined by combinators like L_STAR and L_CONCAT
  76    (2) to preserve parse state when descending into a L_SUBTREE
  77    (3) as a marker to determine if a L_MAYBE had a match or not
  78  */
  79 struct frame {
  80     struct lens     *lens;
  81     char            *key;
  82     struct span     *span;
  83     union {
  84         struct { /* MGET */
  85             char        *value;
  86             struct tree *tree;
  87         };
  88         struct { /* M_PARSE */
  89             struct skel *skel;
  90             struct dict *dict;
  91         };
  92     };
  93 };
  94
  95 /* Used by recursive lenses in get_rec and parse_rec */
  96 enum mode_t { M_GET, M_PARSE };
  97
  98 /* Abstract Syntax Tree for recursive parse */
  99 struct ast {
 100     struct ast         *parent;
 101     struct ast        **children;
 102     uint                nchildren;
 103     uint                capacity;
 104     struct lens        *lens;
 105     uint                start;
 106     uint                end;
 107 };
 108
 109 struct rec_state {
 110     enum mode_t          mode;
 111     struct state        *state;
 112     uint                 fsize;
 113     uint                 fused;
 114     struct frame        *frames;
 115     size_t               start;
 116     uint                 lvl;  /* Debug only */
 117     struct ast          *ast;
 118     /* Will either be get_combine or parse_combine, depending on MODE, for
 119        the duration of the whole recursive parse */
 120     void (*combine)(struct rec_state *, struct lens *, uint);
 121 };
 122
 123 #define REG_START(state) ((state)->regs->start[(state)->nreg])
 124 #define REG_END(state)   ((state)->regs->end[(state)->nreg])
 125 #define REG_SIZE(state) (REG_END(state) - REG_START(state))
 126 #define REG_POS(state) ((state)->text + REG_START(state))
 127 #define REG_VALID(state) ((state)->regs != NULL &&                      \
 128                           (state)->nreg < (state)->regs->num_regs)
 129 #define REG_MATCHED(state) (REG_VALID(state)                            \
 130                             && (state)->regs->start[(state)->nreg] >= 0)
 131
 132 /* The macros SAVE_REGS and RESTORE_REGS are used to remember and restore
 133  * where our caller was in processing their regexp match before we do
 134  * matching ourselves (and would therefore clobber the caller's state)
 135  *
 136  * These two macros are admittedly horrible in that they declare local
 137  * variables called OLD_REGS and OLD_NREG. The alternative to avoiding that
 138  * would be to manually manage a stack of regs/nreg in STATE.
 139  */
 140 #define SAVE_REGS(state)                                                \
 141     struct re_registers *old_regs = state->regs;                        \
 142     uint old_nreg = state->nreg;                                        \
 143     state->regs = NULL;                                                 \
 144     state->nreg = 0
 145
 146 #define RESTORE_REGS(state)                                             \
 147     free_regs(state);                                                   \
 148     state->regs = old_regs;                                             \
 149     state->nreg = old_nreg;
 150
 151 /*
 152  * AST utils
 153  */
 154 static struct ast *make_ast(struct lens *lens) {
 155     struct ast *ast = NULL;
 156
 157     if (ALLOC(ast) < 0)
 158         return NULL;
 159     ast->lens = lens;
 160     ast->capacity = 4;
 161     if (ALLOC_N(ast->children, ast->capacity) < 0) {
 162         FREE(ast);
 163         return NULL;
 164     }
 165     return ast;
 166 }
 167
 168 /* recursively free the node and all it's descendants */
 169 static void free_ast(struct ast *ast) {
 170     int i;
 171     if (ast == NULL)
 172         return;
 173     for (i = 0; i < ast->nchildren; i++) {
 174         free_ast(ast->children[i]);
 175     }
 176     if (ast->children != NULL)
 177         FREE(ast->children);
 178     FREE(ast);
 179 }
 180
 181 static struct ast *ast_root(struct ast *ast) {
 182     struct ast *root = ast;
 183     while(root != NULL && root->parent != NULL)
 184         root = root->parent;
 185     return root;
 186 }
 187
 188 static void ast_set(struct ast *ast, uint start, uint end) {
 189     if (ast == NULL)
 190         return;
 191     ast->start = start;
 192     ast->end = end;
 193 }
 194
 195 /* append a child to the parent ast */
 196 static struct ast *ast_append(struct rec_state *rec_state, struct lens *lens,
 197                            uint start, uint end) {
 198     int ret;
 199     struct ast *child, *parent;
 200     struct state *state = rec_state->state;
 201
 202     parent = rec_state->ast;
 203     if (parent == NULL)
 204        return NULL;
 205
 206     child = make_ast(lens);
 207     ERR_NOMEM(child == NULL, state->info);
 208
 209     ast_set(child, start, end);
 210     if (parent->nchildren >= parent->capacity) {
 211        ret = REALLOC_N(parent->children, parent->capacity * 2);
 212        ERR_NOMEM(ret < 0, state->info);
 213        parent->capacity = parent->capacity * 2;
 214     }
 215     parent->children[parent->nchildren++] = child;
 216     child->parent = parent;
 217
 218     return child;
 219  error:
 220     free_ast(child);
 221     return NULL;
 222 }
 223
 224 /* pop the ast from one level, fail the parent is NULL */
 225 static void ast_pop(struct rec_state *rec_state) {
 226     ensure(rec_state->ast != NULL && rec_state->ast->parent != NULL, rec_state->state->info);
 227     rec_state->ast = rec_state->ast->parent;
 228  error:
 229     return;
 230 }
 231
 232 static void print_ast(const struct ast *ast, int lvl) {
 233     int i;
 234     char *lns;
 235     if (ast == NULL)
 236         return;
 237     for (i = 0; i < lvl; i++) fputs(" ", stdout);
 238     lns = format_lens(ast->lens);
 239     printf("%d..%d %s\n", ast->start, ast->end, lns);
 240     free(lns);
 241     for (i = 0; i < ast->nchildren; i++) {
 242         print_ast(ast->children[i], lvl + 1);
 243     }
 244 }
 245
 246 static void get_error(struct state *state, struct lens *lens,
 247                       const char *format, ...)
 248     ATTRIBUTE_FORMAT(printf, 3, 4);
 249
 250 void free_lns_error(struct lns_error *err) {
 251     if (err == NULL)
 252         return;
 253     free(err->message);
 254     free(err->path);
 255     unref(err->lens, lens);
 256     free(err);
 257 }
 258
 259 static void vget_error(struct state *state, struct lens *lens,
 260                        const char *format, va_list ap) {
 261     int r;
 262
 263     if (state->error != NULL)
 264         return;
 265     if (ALLOC(state->error) < 0)
 266         return;
 267     state->error->lens = ref(lens);
 268     if (REG_MATCHED(state))
 269         state->error->pos  = REG_END(state);
 270     else
 271         state->error->pos = 0;
 272     r = vasprintf(&state->error->message, format, ap);
 273     if (r == -1)
 274         state->error->message = NULL;
 275 }
 276
 277 static void get_error(struct state *state, struct lens *lens,
 278                       const char *format, ...)
 279 {
 280     va_list ap;
 281
 282     va_start(ap, format);
 283     vget_error(state, lens, format, ap);
 284     va_end(ap);
 285 }
 286
 287 static struct skel *make_skel(struct lens *lens) {
 288     struct skel *skel;
 289     enum lens_tag tag = lens->tag;
 290     CALLOC(skel, 1);
 291     skel->tag = tag;
 292     return skel;
 293 }
 294
 295 void free_skel(struct skel *skel) {
 296     if (skel == NULL)
 297         return;
 298     if (skel->tag == L_CONCAT || skel->tag == L_STAR || skel->tag == L_MAYBE ||
 299         skel->tag == L_SQUARE) {
 300         while (skel->skels != NULL) {
 301             struct skel *del = skel->skels;
 302             skel->skels = del->next;
 303             free_skel(del);
 304         }
 305     } else if (skel->tag == L_DEL) {
 306         free(skel->text);
 307     }
 308     free(skel);
 309 }
 310
 311 static void print_skel(struct skel *skel);
 312 static void print_skel_list(struct skel *skels, const char *beg,
 313                             const char *sep, const char *end) {
 314     printf("%s", beg);
 315     list_for_each(s, skels) {
 316         print_skel(s);
 317         if (s->next != NULL)
 318             printf("%s", sep);
 319     }
 320     printf("%s", end);
 321 }
 322
 323 static void print_skel(struct skel *skel) {
 324     switch(skel->tag) {
 325     case L_DEL:
 326         if (skel->text == NULL) {
 327             printf("<>");
 328         } else {
 329             fputc('\'', stdout);
 330             print_chars(stdout, skel->text, -1);
 331             fputc('\'', stdout);
 332         }
 333         break;
 334     case L_CONCAT:
 335         print_skel_list(skel->skels, "", " . ", "");
 336         break;
 337     case L_STAR:
 338         print_skel_list(skel->skels, "(", " ", ")*");
 339         break;
 340     case L_MAYBE:
 341         print_skel_list(skel->skels, "(", " ", ")?");
 342         break;
 343     case L_SUBTREE:
 344         print_skel_list(skel->skels, "[", " ", "]");
 345         break;
 346     default:
 347         printf("??");
 348         break;
 349     }
 350 }
 351
 352 // DICT_DUMP is only used for debugging
 353 #ifdef DICT_DUMP
 354 static void print_dict(struct dict *dict, int indent) {
 355     list_for_each(d, dict) {
 356         printf("%*s%s:\n", indent, "", d->key);
 357         list_for_each(e, d->entry) {
 358             printf("%*s", indent+2, "");
 359             print_skel(e->skel);
 360             printf("\n");
 361             print_dict(e->dict, indent+2);
 362         }
 363     }
 364 }
 365 #endif
 366
 367 static void get_expected_error(struct state *state, struct lens *l) {
 368     /* Size of the excerpt of the input text we'll show */
 369     static const int wordlen = 10;
 370     char word[wordlen+1];
 371     char *p, *pat;
 372
 373     if (REG_MATCHED(state))
 374         strncpy(word, REG_POS(state), wordlen);
 375     else
 376         strncpy(word, state->text, wordlen);
 377     word[wordlen] = '\0';
 378     for (p = word; *p != '\0' && *p != '\n'; p++);
 379     *p = '\0';
 380
 381     pat = escape(l->ctype->pattern->str, -1, NULL);
 382     get_error(state, l, "expected %s at '%s'", pat, word);
 383     free(pat);
 384 }
 385
 386 /*
 387  * Splitting of the input text
 388  */
 389
 390 static char *token(struct state *state) {
 391     ensure0(REG_MATCHED(state), state->info);
 392     return strndup(REG_POS(state), REG_SIZE(state));
 393 }
 394
 395 static char *token_range(const char *text, uint start, uint end) {
 396     return strndup(text + start, end - start);
 397 }
 398
 399 static void regexp_match_error(struct state *state, struct lens *lens,
 400                                int count, struct regexp *r) {
 401     char *text = NULL;
 402     char *pat = regexp_escape(r);
 403
 404     if (state->regs != NULL)
 405         text = strndup(REG_POS(state), REG_SIZE(state));
 406     else
 407         text = strdup("(unknown)");
 408
 409     if (count == -1) {
 410         get_error(state, lens, "Failed to match /%s/ with %s", pat, text);
 411     } else if (count == -2) {
 412         get_error(state, lens, "Internal error matching /%s/ with %s",
 413                   pat, text);
 414     } else if (count == -3) {
 415         /* Should have been caught by the typechecker */
 416         get_error(state, lens, "Syntax error in regexp /%s/", pat);
 417     }
 418     free(pat);
 419     free(text);
 420 }
 421
 422 static void no_match_error(struct state *state, struct lens *lens) {
 423     ensure(lens->tag == L_KEY || lens->tag == L_DEL
 424            || lens->tag == L_STORE, state->info);
 425     char *pat = regexp_escape(lens->ctype);
 426     const char *lname = "(lname)";
 427     if (lens->tag == L_KEY)
 428         lname = "key";
 429     else if (lens->tag == L_DEL)
 430         lname = "del";
 431     else if (lens->tag == L_STORE)
 432         lname = "store";
 433     get_error(state, lens, "no match for %s /%s/", lname, pat);
 434     free(pat);
 435  error:
 436     return;
 437 }
 438
 439 /* Modifies STATE->REGS and STATE->NREG. The caller must save these
 440  * if they are still needed
 441  *
 442  * Return the number of characters matched
 443  */
 444 static int match(struct state *state, struct lens *lens,
 445                  struct regexp *re, uint size, uint start) {
 446     struct re_registers *regs;
 447     int count;
 448
 449     if (ALLOC(regs) < 0)
 450         return -1;
 451
 452     count = regexp_match(re, state->text, size, start, regs);
 453     if (count < -1) {
 454         regexp_match_error(state, lens, count, re);
 455         FREE(regs);
 456         return -1;
 457     }
 458     state->regs = regs;
 459     state->nreg = 0;
 460     return count;
 461 }
 462
 463 static void free_regs(struct state *state) {
 464     if (state->regs != NULL) {
 465         free(state->regs->start);
 466         free(state->regs->end);
 467         FREE(state->regs);
 468     }
 469 }
 470
 471 static struct tree *get_lens(struct lens *lens, struct state *state);
 472 static struct skel *parse_lens(struct lens *lens, struct state *state,
 473                                struct dict **dict);
 474
 475 static void free_seqs(struct seq *seqs) {
 476     /* Do not free seq->name; it's not owned by the seq, but by some lens */
 477     list_free(seqs);
 478 }
 479
 480 static struct seq *find_seq(const char *name, struct state *state) {
 481     ensure0(name != NULL, state->info);
 482     struct seq *seq;
 483
 484     for (seq=state->seqs;
 485          seq != NULL && STRNEQ(seq->name, name);
 486          seq = seq->next);
 487
 488     if (seq == NULL) {
 489         CALLOC(seq, 1);
 490         seq->name = name;
 491         seq->value = 1;
 492         list_append(state->seqs, seq);
 493     }
 494
 495     return seq;
 496 }
 497
 498 static struct tree *get_seq(struct lens *lens, struct state *state) {
 499     ensure0(lens->tag == L_SEQ, state->info);
 500     struct seq *seq = find_seq(lens->string->str, state);
 501     int r;
 502
 503     r = asprintf((char **) &(state->key), "%d", seq->value);
 504     ERR_NOMEM(r < 0, state->info);
 505
 506     seq->value += 1;
 507  error:
 508     return NULL;
 509 }
 510
 511 static struct skel *parse_seq(struct lens *lens, struct state *state) {
 512     get_seq(lens, state);
 513     return make_skel(lens);
 514 }
 515
 516 static struct tree *get_counter(struct lens *lens, struct state *state) {
 517     ensure0(lens->tag == L_COUNTER, state->info);
 518     struct seq *seq = find_seq(lens->string->str, state);
 519     seq->value = 1;
 520     return NULL;
 521 }
 522
 523 static struct skel *parse_counter(struct lens *lens, struct state *state) {
 524     get_counter(lens, state);
 525     return make_skel(lens);
 526 }
 527
 528 static struct tree *get_del(struct lens *lens, struct state *state) {
 529     ensure0(lens->tag == L_DEL, state->info);
 530     if (! REG_MATCHED(state)) {
 531         char *pat = regexp_escape(lens->ctype);
 532         get_error(state, lens, "no match for del /%s/", pat);
 533         free(pat);
 534     }
 535     update_span(state->span, REG_START(state), REG_END(state));
 536     return NULL;
 537 }
 538
 539 static struct skel *parse_del(struct lens *lens, struct state *state) {
 540     ensure0(lens->tag == L_DEL, state->info);
 541     struct skel *skel = NULL;
 542
 543     skel = make_skel(lens);
 544     if (! REG_MATCHED(state))
 545         no_match_error(state, lens);
 546     else
 547         skel->text = token(state);
 548     return skel;
 549 }
 550
 551 static struct tree *get_store(struct lens *lens, struct state *state) {
 552     ensure0(lens->tag == L_STORE, state->info);
 553     ensure0(state->value == NULL, state->info);
 554
 555     struct tree *tree = NULL;
 556
 557     if (state->value != NULL)
 558         get_error(state, lens, "More than one store in a subtree");
 559     else if (! REG_MATCHED(state))
 560         no_match_error(state, lens);
 561     else {
 562         state->value = token(state);
 563         if (state->span) {
 564             state->span->value_start = REG_START(state);
 565             state->span->value_end = REG_END(state);
 566             update_span(state->span, REG_START(state), REG_END(state));
 567         }
 568     }
 569     return tree;
 570 }
 571
 572 static struct skel *parse_store(struct lens *lens,
 573                                 ATTRIBUTE_UNUSED struct state *state) {
 574     ensure0(lens->tag == L_STORE, state->info);
 575     return make_skel(lens);
 576 }
 577
 578 static struct tree *get_value(struct lens *lens, struct state *state) {
 579     ensure0(lens->tag == L_VALUE, state->info);
 580     state->value = strdup(lens->string->str);
 581     return NULL;
 582 }
 583
 584 static struct skel *parse_value(struct lens *lens,
 585                                 ATTRIBUTE_UNUSED struct state *state) {
 586     ensure0(lens->tag == L_VALUE, state->info);
 587     return make_skel(lens);
 588 }
 589
 590 static struct tree *get_key(struct lens *lens, struct state *state) {
 591     ensure0(lens->tag == L_KEY, state->info);
 592     if (! REG_MATCHED(state))
 593         no_match_error(state, lens);
 594     else {
 595         state->key = token(state);
 596         if (state->span) {
 597             state->span->label_start = REG_START(state);
 598             state->span->label_end = REG_END(state);
 599             update_span(state->span, REG_START(state), REG_END(state));
 600         }
 601     }
 602     return NULL;
 603 }
 604
 605 static struct skel *parse_key(struct lens *lens, struct state *state) {
 606     get_key(lens, state);
 607     return make_skel(lens);
 608 }
 609
 610 static struct tree *get_label(struct lens *lens, struct state *state) {
 611     ensure0(lens->tag == L_LABEL, state->info);
 612     state->key = strdup(lens->string->str);
 613     return NULL;
 614 }
 615
 616 static struct skel *parse_label(struct lens *lens, struct state *state) {
 617     get_label(lens, state);
 618     return make_skel(lens);
 619 }
 620
 621 static struct tree *get_union(struct lens *lens, struct state *state) {
 622     ensure0(lens->tag == L_UNION, state->info);
 623
 624     struct tree *tree = NULL;
 625     int applied = 0;
 626     uint old_nreg = state->nreg;
 627
 628     state->nreg += 1;
 629     for (int i=0; i < lens->nchildren; i++) {
 630         if (REG_MATCHED(state)) {
 631             tree = get_lens(lens->children[i], state);
 632             applied = 1;
 633             break;
 634         }
 635         state->nreg += 1 + regexp_nsub(lens->children[i]->ctype);
 636     }
 637     state->nreg = old_nreg;
 638     if (!applied)
 639         get_expected_error(state, lens);
 640     return tree;
 641 }
 642
 643 static struct skel *parse_union(struct lens *lens, struct state *state,
 644                                 struct dict **dict) {
 645     ensure0(lens->tag == L_UNION, state->info);
 646
 647     struct skel *skel = NULL;
 648     int applied = 0;
 649     uint old_nreg = state->nreg;
 650
 651     state->nreg += 1;
 652     for (int i=0; i < lens->nchildren; i++) {
 653         struct lens *l = lens->children[i];
 654         if (REG_MATCHED(state)) {
 655             skel = parse_lens(l, state, dict);
 656             applied = 1;
 657             break;
 658         }
 659         state->nreg += 1 + regexp_nsub(lens->children[i]->ctype);
 660     }
 661     state->nreg = old_nreg;
 662     if (! applied)
 663         get_expected_error(state, lens);
 664
 665     return skel;
 666 }
 667
 668 static struct tree *get_concat(struct lens *lens, struct state *state) {
 669     ensure0(lens->tag == L_CONCAT, state->info);
 670
 671     struct tree *tree = NULL;
 672     uint old_nreg = state->nreg;
 673
 674     state->nreg += 1;
 675     for (int i=0; i < lens->nchildren; i++) {
 676         struct tree *t = NULL;
 677         if (! REG_VALID(state)) {
 678             get_error(state, lens->children[i],
 679                       "Not enough components in concat");
 680             free_tree(tree);
 681             state->nreg = old_nreg;
 682             return NULL;
 683         }
 684
 685         t = get_lens(lens->children[i], state);
 686         list_append(tree, t);
 687         state->nreg += 1 + regexp_nsub(lens->children[i]->ctype);
 688     }
 689     state->nreg = old_nreg;
 690
 691     return tree;
 692 }
 693
 694 static struct skel *parse_concat(struct lens *lens, struct state *state,
 695                                  struct dict **dict) {
 696     ensure0(lens->tag == L_CONCAT, state->info);
 697     struct skel *skel = make_skel(lens);
 698     uint old_nreg = state->nreg;
 699
 700     state->nreg += 1;
 701     for (int i=0; i < lens->nchildren; i++) {
 702         struct skel *sk = NULL;
 703         struct dict *di = NULL;
 704         if (! REG_VALID(state)) {
 705             get_error(state, lens->children[i],
 706                       "Not enough components in concat");
 707             free_skel(skel);
 708             return NULL;
 709         }
 710
 711         sk = parse_lens(lens->children[i], state, &di);
 712         list_append(skel->skels, sk);
 713         dict_append(dict, di);
 714         state->nreg += 1 + regexp_nsub(lens->children[i]->ctype);
 715     }
 716     state->nreg = old_nreg;
 717
 718     return skel;
 719 }
 720
 721 /* Given a lens that does not match at the current position, try to find
 722  * the left-most child LAST that does match and the lens next to it NEXT
 723  * that does not match. Return the length of the match.
 724  *
 725  * If no such child exists, return 0
 726  */
 727 static int try_match(struct lens *lens, struct state *state,
 728                      uint start, uint end,
 729                      struct lens **last, struct lens **next) {
 730     int result = 0, r;
 731
 732     switch(lens->tag) {
 733     case L_VALUE:
 734     case L_LABEL:
 735     case L_SEQ:
 736     case L_COUNTER:
 737         *last = lens;
 738         return result;
 739         break;
 740     case L_DEL:
 741     case L_KEY:
 742     case L_STORE:
 743         result = regexp_match(lens->ctype, state->text, end, start, NULL);
 744         if (result >= 0)
 745             *last = lens;
 746         return result;
 747     case L_CONCAT:
 748         for (int i=0; i < lens->nchildren; i++) {
 749             struct lens *child = lens->children[i];
 750             struct lens *next_child  =
 751                 (i < lens->nchildren - 1) ? lens->children[i+1] : NULL;
 752
 753             r = regexp_match(child->ctype, state->text, end, start, NULL);
 754             if (r >= 0) {
 755                 result += r;
 756                 start += r;
 757                 *last = child;
 758             } else if (result > 0) {
 759                 if (*next == NULL)
 760                     *next = child;
 761                 return result;
 762             } else {
 763                 result = try_match(child, state, start, end, last, next);
 764                 if (result > 0 && *next == NULL)
 765                     *next = next_child;
 766                 return result;
 767             }
 768         }
 769         return result;
 770         break;
 771     case L_UNION:
 772         for (int i=0; i < lens->nchildren; i++) {
 773             struct lens *child = lens->children[i];
 774             result = try_match(child, state, start, end, last, next);
 775             if (result > 0)
 776                 return result;
 777         }
 778         return 0;
 779         break;
 780     case L_SUBTREE:
 781     case L_STAR:
 782     case L_MAYBE:
 783     case L_SQUARE:
 784         return try_match(lens->child, state, start, end, last, next);
 785         break;
 786     default:
 787         BUG_ON(true, state->info, "illegal lens tag %d", lens->tag);
 788         break;
 789     }
 790  error:
 791     return 0;
 792 }
 793
 794 static void short_iteration_error(struct lens *lens, struct state *state,
 795                                     uint start, uint end) {
 796     int match_count;
 797
 798     get_error(state, lens, "%s", short_iteration);
 799
 800     match_count = try_match(lens->child, state, start, end,
 801                             &state->error->last, &state->error->next);
 802     state->error->pos = start + match_count;
 803 }
 804
 805 static struct tree *get_quant_star(struct lens *lens, struct state *state) {
 806     ensure0(lens->tag == L_STAR, state->info);
 807     struct lens *child = lens->child;
 808     struct tree *tree = NULL, *tail = NULL;
 809     uint end = REG_END(state);
 810     uint start = REG_START(state);
 811     uint size = end - start;
 812
 813     SAVE_REGS(state);
 814     while (size > 0 && match(state, child, child->ctype, end, start) > 0) {
 815         struct tree *t = NULL;
 816
 817         t = get_lens(lens->child, state);
 818         list_tail_cons(tree, tail, t);
 819
 820         start += REG_SIZE(state);
 821         size -= REG_SIZE(state);
 822         free_regs(state);
 823     }
 824     RESTORE_REGS(state);
 825     if (size != 0) {
 826         short_iteration_error(lens, state, start, end);
 827     }
 828     return tree;
 829 }
 830
 831 static struct skel *parse_quant_star(struct lens *lens, struct state *state,
 832                                      struct dict **dict) {
 833     ensure0(lens->tag == L_STAR, state->info);
 834     struct lens *child = lens->child;
 835     struct skel *skel = make_skel(lens), *tail = NULL;
 836     uint end = REG_END(state);
 837     uint start = REG_START(state);
 838     uint size = end - start;
 839
 840     *dict = NULL;
 841     SAVE_REGS(state);
 842     while (size > 0 && match(state, child, child->ctype, end, start) > 0) {
 843         struct skel *sk;
 844         struct dict *di = NULL;
 845
 846         sk = parse_lens(lens->child, state, &di);
 847         list_tail_cons(skel->skels, tail, sk);
 848         dict_append(dict, di);
 849
 850         start += REG_SIZE(state);
 851         size -= REG_SIZE(state);
 852         free_regs(state);
 853     }
 854     RESTORE_REGS(state);
 855     if (size != 0) {
 856         get_error(state, lens, "%s", short_iteration);
 857     }
 858     return skel;
 859 }
 860
 861 static struct tree *get_quant_maybe(struct lens *lens, struct state *state) {
 862     ensure0(lens->tag == L_MAYBE, state->info);
 863     struct tree *tree = NULL;
 864
 865     /* Check that our child matched. For a construct like (r)?, the
 866      * matcher will report a zero length match for group 0, even if r
 867      * does not match at all
 868      */
 869     state->nreg += 1;
 870     if (REG_MATCHED(state)) {
 871         tree = get_lens(lens->child, state);
 872     }
 873     state->nreg -= 1;
 874     return tree;
 875 }
 876
 877 static struct skel *parse_quant_maybe(struct lens *lens, struct state *state,
 878                                       struct dict **dict) {
 879     ensure0(lens->tag == L_MAYBE, state->info);
 880
 881     struct skel *skel = NULL;
 882
 883     state->nreg += 1;
 884     if (REG_MATCHED(state)) {
 885         skel = parse_lens(lens->child, state, dict);
 886     }
 887     state->nreg -= 1;
 888     if (skel == NULL)
 889         skel = make_skel(lens);
 890     return skel;
 891 }
 892
 893 static struct tree *get_subtree(struct lens *lens, struct state *state) {
 894     char *key = state->key;
 895     char *value = state->value;
 896     struct span *span = move(state->span);
 897
 898     struct tree *tree = NULL, *children;
 899
 900     state->key = NULL;
 901     state->value = NULL;
 902     if (state->info->flags & AUG_ENABLE_SPAN) {
 903         state->span = make_span(state->info);
 904         ERR_NOMEM(state->span == NULL, state->info);
 905     }
 906
 907     children = get_lens(lens->child, state);
 908
 909     tree = make_tree(state->key, state->value, NULL, children);
 910     ERR_NOMEM(tree == NULL, state->info);
 911     tree->span = move(state->span);
 912
 913     if (tree->span != NULL) {
 914         update_span(span, tree->span->span_start, tree->span->span_end);
 915     }
 916
 917     state->key = key;
 918     state->value = value;
 919     state->span = span;
 920     return tree;
 921  error:
 922     free_span(state->span);
 923     state->span = span;
 924     return NULL;
 925 }
 926
 927 static struct skel *parse_subtree(struct lens *lens, struct state *state,
 928                                   struct dict **dict) {
 929     char *key = state->key;
 930     struct skel *skel;
 931     struct dict *di = NULL;
 932
 933     state->key = NULL;
 934     skel = parse_lens(lens->child, state, &di);
 935     *dict = make_dict(state->key, skel, di);
 936     state->key = key;
 937     return make_skel(lens);
 938 }
 939
 940 /* Check if left and right strings matches according to the square lens
 941  * definition.
 942  *
 943  * Returns 1 if strings matches, 0 otherwise
 944  */
 945 static int square_match(struct lens *lens, char *left, char *right) {
 946     int cmp = 0;
 947     struct lens *concat = NULL;
 948
 949     // if one of the argument is NULL, returns no match
 950     if (left == NULL || right == NULL || lens == NULL)
 951         return cmp;
 952
 953     concat = lens->child;
 954     /* If either right or left lens is nocase, then ignore case */
 955     if (child_first(concat)->ctype->nocase ||
 956             child_last(concat)->ctype->nocase) {
 957         cmp = STRCASEEQ(left, right);
 958     } else {
 959         cmp = STREQ(left, right);
 960     }
 961     return cmp;
 962 }
 963
 964 /*
 965  * This function applies only for non-recursive lens, handling of recursive
 966  * square is done in visit_exit().
 967  */
 968 static struct tree *get_square(struct lens *lens, struct state *state) {
 969     ensure0(lens->tag == L_SQUARE, state->info);
 970
 971     struct lens *concat = lens->child;
 972     struct tree *tree = NULL;
 973     uint end = REG_END(state);
 974     uint start = REG_START(state);
 975     char *rsqr = NULL, *lsqr = NULL;
 976     int r;
 977
 978     SAVE_REGS(state);
 979     r = match(state, lens->child, lens->child->ctype, end, start);
 980     ERR_NOMEM(r < 0, state->info);
 981
 982     tree = get_lens(lens->child, state);
 983
 984     /* retrieve left component */
 985     state->nreg = 1;
 986     start = REG_START(state);
 987     end = REG_END(state);
 988     lsqr = token_range(state->text, start, end);
 989
 990     /* retrieve right component */
 991     /* compute nreg for the last children */
 992     for (int i = 0; i < concat->nchildren - 1; i++)
 993         state->nreg += 1 + regexp_nsub(concat->children[i]->ctype);
 994
 995     start = REG_START(state);
 996     end = REG_END(state);
 997     rsqr = token_range(state->text, start, end);
 998
 999     if (!square_match(lens, lsqr, rsqr)) {
1000         get_error(state, lens, "%s \"%s\" %s \"%s\"",
1001             "Parse error: mismatched in square lens, expecting", lsqr,
1002             "but got", rsqr);
1003         goto error;
1004     }
1005
1006  done:
1007     RESTORE_REGS(state);
1008     FREE(lsqr);
1009     FREE(rsqr);
1010     return tree;
1011
1012  error:
1013     free_tree(tree);
1014     tree = NULL;
1015     goto done;
1016 }
1017
1018 static struct skel *parse_square(struct lens *lens, struct state *state,
1019                                  struct dict **dict) {
1020     ensure0(lens->tag == L_SQUARE, state->info);
1021     uint end = REG_END(state);
1022     uint start = REG_START(state);
1023     struct skel *skel = NULL, *sk = NULL;
1024     int r;
1025
1026     SAVE_REGS(state);
1027     r = match(state, lens->child, lens->child->ctype, end, start);
1028     ERR_NOMEM(r < 0, state->info);
1029
1030     skel = parse_lens(lens->child, state, dict);
1031     if (skel == NULL)
1032         return NULL;
1033     sk = make_skel(lens);
1034     sk->skels = skel;
1035
1036  error:
1037     RESTORE_REGS(state);
1038     return sk;
1039 }
1040
1041 /*
1042  * Helpers for recursive lenses
1043  */
1044
1045 ATTRIBUTE_UNUSED
1046 static void print_frames(struct rec_state *state) {
1047     for (int j = state->fused - 1; j >=0; j--) {
1048         struct frame *f = state->frames + j;
1049         for (int i=0; i < state->lvl; i++) fputc(' ', stderr);
1050         fprintf(stderr, "%2d %s %s", j, f->key, f->value);
1051         if (f->tree == NULL) {
1052             fprintf(stderr, " - ");
1053         } else {
1054             fprintf(stderr, " { %s = %s } ", f->tree->label, f->tree->value);
1055         }
1056         char *s = format_lens(f->lens);
1057         if (s != NULL) {
1058             fprintf(stderr, "%s\n", s);
1059             free(s);
1060         }
1061     }
1062 }
1063
1064 ATTRIBUTE_PURE
1065 static struct frame *top_frame(struct rec_state *state) {
1066     ensure0(state->fsize > 0, state->state->info);
1067     return state->frames + state->fused - 1;
1068 }
1069
1070 /* The nth frame from the top of the stack, where 0th frame is the top */
1071 ATTRIBUTE_PURE
1072 static struct frame *nth_frame(struct rec_state *state, uint n) {
1073     ensure0(state->fsize > n, state->state->info);
1074     return state->frames + state->fused - (n+1);
1075 }
1076
1077 static struct frame *push_frame(struct rec_state *state, struct lens *lens) {
1078     int r;
1079
1080     if (state->fused >= state->fsize) {
1081         uint expand = state->fsize;
1082         if (expand < 8)
1083             expand = 8;
1084         r = REALLOC_N(state->frames, state->fsize + expand);
1085         ERR_NOMEM(r < 0, state->state->info);
1086         state->fsize += expand;
1087     }
1088
1089     state->fused += 1;
1090
1091     struct frame *top = top_frame(state);
1092     MEMZERO(top, 1);
1093     top->lens = lens;
1094     return top;
1095  error:
1096     return NULL;
1097 }
1098
1099 static struct frame *pop_frame(struct rec_state *state) {
1100     ensure0(state->fused > 0, state->state->info);
1101
1102     struct frame *result = top_frame(state);
1103     state->fused -= 1;
1104     return result;
1105 }
1106
1107 static void dbg_visit(struct lens *lens, char action, size_t start, size_t end,
1108                       int fused, int lvl) {
1109     char *lns;
1110     for (int i=0; i < lvl; i++)
1111         fputc(' ', stderr);
1112     lns = format_lens(lens);
1113     fprintf(stderr, "%c %zd..%zd %d %s\n", action, start, end,
1114             fused, lns);
1115     free(lns);
1116 }
1117
1118 static void get_terminal(struct frame *top, struct lens *lens,
1119                          struct state *state) {
1120     top->tree = get_lens(lens, state);
1121     top->key = state->key;
1122     top->value = state->value;
1123     state->key = NULL;
1124     state->value = NULL;
1125 }
1126
1127 static void parse_terminal(struct frame *top, struct lens *lens,
1128                            struct state *state) {
1129     top->dict = NULL;
1130     top->skel = parse_lens(lens, state, &top->dict);
1131     top->key = state->key;
1132     state->key = NULL;
1133 }
1134
1135 static void visit_terminal(struct lens *lens, size_t start, size_t end,
1136                            void *data) {
1137     struct rec_state *rec_state = data;
1138     struct state *state = rec_state->state;
1139     struct ast *child;
1140
1141     if (state->error != NULL)
1142         return;
1143
1144     SAVE_REGS(state);
1145     if (debugging("cf.get"))
1146         dbg_visit(lens, 'T', start, end, rec_state->fused, rec_state->lvl);
1147     match(state, lens, lens->ctype, end, start);
1148     struct frame *top = push_frame(rec_state, lens);
1149     ERR_BAIL(state->info);
1150     if (rec_state->mode == M_GET)
1151         get_terminal(top, lens, state);
1152     else
1153         parse_terminal(top, lens, state);
1154     child = ast_append(rec_state, lens, start, end);
1155     ERR_NOMEM(child == NULL, state->info);
1156  error:
1157     RESTORE_REGS(state);
1158 }
1159
1160 static bool rec_gen_span(struct rec_state *rec_state) {
1161     return ((rec_state->mode == M_GET)
1162             && (rec_state->state->info->flags & AUG_ENABLE_SPAN));
1163 }
1164
1165 static void visit_enter(struct lens *lens,
1166                         ATTRIBUTE_UNUSED size_t start,
1167                         ATTRIBUTE_UNUSED size_t end,
1168                         void *data) {
1169     struct rec_state *rec_state = data;
1170     struct state *state = rec_state->state;
1171     struct ast *child;
1172
1173     if (state->error != NULL)
1174         return;
1175
1176     if (debugging("cf.get"))
1177         dbg_visit(lens, '{', start, end, rec_state->fused, rec_state->lvl);
1178     rec_state->lvl += 1;
1179     if (lens->tag == L_SUBTREE) {
1180         /* Same for parse and get */
1181         /* Use this frame to preserve the current state before we process
1182            the contents of the subtree, i.e., lens->child */
1183         struct frame *f = push_frame(rec_state, lens);
1184         ERR_BAIL(state->info);
1185         f->key = state->key;
1186         f->value = state->value;
1187         state->key = NULL;
1188         state->value = NULL;
1189         if (rec_gen_span(rec_state)) {
1190             f->span = state->span;
1191             state->span = make_span(state->info);
1192             ERR_NOMEM(state->span == NULL, state->info);
1193         }
1194     } else if (lens->tag == L_MAYBE) {
1195         /* Push a frame as a marker so we can tell whether lens->child
1196            actually had a match or not */
1197         push_frame(rec_state, lens);
1198         ERR_BAIL(state->info);
1199     }
1200     child = ast_append(rec_state, lens, start, end);
1201     if (child != NULL)
1202         rec_state->ast = child;
1203  error:
1204     return;
1205 }
1206
1207 /* Combine n frames from the stack into one new frame for M_GET */
1208 static void get_combine(struct rec_state *rec_state,
1209                         struct lens *lens, uint n) {
1210     struct tree *tree = NULL, *tail = NULL;
1211     char *key = NULL, *value = NULL;
1212     struct frame *top = NULL;
1213
1214     for (int i=0; i < n; i++) {
1215         top = pop_frame(rec_state);
1216         ERR_BAIL(lens->info);
1217         list_tail_cons(tree, tail, top->tree);
1218         /* top->tree might have more than one node, update tail */
1219         if (tail != NULL)
1220             while (tail->next != NULL) tail = tail->next;
1221
1222         if (top->key != NULL) {
1223             ensure(key == NULL, rec_state->state->info);
1224             key = top->key;
1225         }
1226         if (top->value != NULL) {
1227             ensure(value == NULL, rec_state->state->info);
1228             value = top->value;
1229         }
1230     }
1231     top = push_frame(rec_state, lens);
1232     ERR_BAIL(lens->info);
1233     top->tree = tree;
1234     top->key = key;
1235     top->value = value;
1236  error:
1237     return;
1238 }
1239
1240 /* Combine n frames from the stack into one new frame for M_PUT */
1241 static void parse_combine(struct rec_state *rec_state,
1242                           struct lens *lens, uint n) {
1243     struct skel *skel = make_skel(lens), *tail = NULL;
1244     struct dict *dict = NULL;
1245     char *key = NULL;
1246     struct frame *top = NULL;
1247
1248     for (int i=0; i < n; i++) {
1249         top = pop_frame(rec_state);
1250         ERR_BAIL(lens->info);
1251         list_tail_cons(skel->skels, tail, top->skel);
1252         /* top->skel might have more than one node, update skel */
1253         if (tail != NULL)
1254             while (tail->next != NULL) tail = tail->next;
1255         dict_append(&dict, top->dict);
1256         if (top->key != NULL) {
1257             ensure(key == NULL, rec_state->state->info);
1258             key = top->key;
1259         }
1260     }
1261     top = push_frame(rec_state, lens);
1262     ERR_BAIL(lens->info);
1263     top->skel = move(skel);
1264     top->dict = move(dict);
1265     top->key = key;
1266  error:
1267     free_skel(skel);
1268     free_dict(dict);
1269     return;
1270 }
1271
1272 static void visit_exit_put_subtree(struct lens *lens,
1273                                    struct rec_state *rec_state,
1274                                    struct frame *top) {
1275     struct state *state = rec_state->state;
1276     struct skel *skel = NULL;
1277     struct dict *dict = NULL;
1278
1279     skel = make_skel(lens);
1280     ERR_NOMEM(skel == NULL, lens->info);
1281     dict = make_dict(top->key, top->skel, top->dict);
1282     ERR_NOMEM(dict == NULL, lens->info);
1283
1284     top = pop_frame(rec_state);
1285     ERR_BAIL(state->info);
1286     ensure(lens == top->lens, state->info);
1287     state->key = top->key;
1288     top = push_frame(rec_state, lens);
1289     ERR_BAIL(state->info);
1290     top->skel = move(skel);
1291     top->dict = move(dict);
1292  error:
1293     free_skel(skel);
1294     free_dict(dict);
1295 }
1296
1297 static void visit_exit(struct lens *lens,
1298                        ATTRIBUTE_UNUSED size_t start,
1299                        ATTRIBUTE_UNUSED size_t end,
1300                        void *data) {
1301     struct rec_state *rec_state = data;
1302     struct state *state = rec_state->state;
1303     struct tree *tree = NULL;
1304
1305     if (state->error != NULL)
1306         return;
1307
1308     rec_state->lvl -= 1;
1309     if (debugging("cf.get"))
1310         dbg_visit(lens, '}', start, end, rec_state->fused, rec_state->lvl);
1311
1312     ERR_BAIL(lens->info);
1313
1314     if (lens->tag == L_SUBTREE) {
1315         /* Get the result of parsing lens->child */
1316         struct frame *top = pop_frame(rec_state);
1317         ERR_BAIL(state->info);
1318         if (rec_state->mode == M_GET) {
1319             tree = make_tree(top->key, top->value, NULL, top->tree);
1320             ERR_NOMEM(tree == NULL, lens->info);
1321             tree->span = state->span;
1322             /* Restore the parse state from before entering this subtree */
1323             top = pop_frame(rec_state);
1324             ERR_BAIL(state->info);
1325             ensure(lens == top->lens, state->info);
1326             state->key = top->key;
1327             state->value = top->value;
1328             state->span = top->span;
1329             /* Push the result of parsing this subtree */
1330             top = push_frame(rec_state, lens);
1331             ERR_BAIL(state->info);
1332             top->tree = move(tree);
1333         } else {
1334             visit_exit_put_subtree(lens, rec_state, top);
1335         }
1336     } else if (lens->tag == L_CONCAT) {
1337         ensure(rec_state->fused >= lens->nchildren, state->info);
1338         for (int i = 0; i < lens->nchildren; i++) {
1339             struct frame *fr = nth_frame(rec_state, i);
1340             ERR_BAIL(state->info);
1341             BUG_ON(lens->children[i] != fr->lens,
1342                     lens->info,
1343              "Unexpected lens in concat %zd..%zd\n  Expected: %s\n  Actual: %s",
1344                     start, end,
1345                     format_lens(lens->children[i]),
1346                     format_lens(fr->lens));
1347         }
1348         rec_state->combine(rec_state, lens, lens->nchildren);
1349     } else if (lens->tag == L_STAR) {
1350         uint n = 0;
1351         while (n < rec_state->fused &&
1352                nth_frame(rec_state, n)->lens == lens->child)
1353             n++;
1354         ERR_BAIL(state->info);
1355         rec_state->combine(rec_state, lens, n);
1356     } else if (lens->tag == L_MAYBE) {
1357         uint n = 1;
1358         if (rec_state->fused > 0
1359             && top_frame(rec_state)->lens == lens->child) {
1360             n = 2;
1361         }
1362         ERR_BAIL(state->info);
1363         /* If n = 2, the top of the stack is our child's result, and the
1364            frame underneath it is the marker frame we pushed during
1365            visit_enter. Combine these two frames into one, which represents
1366            the result of parsing the whole L_MAYBE. */
1367         rec_state->combine(rec_state, lens, n);
1368     } else if (lens->tag == L_SQUARE) {
1369         if (rec_state->mode == M_GET) {
1370             struct ast *square, *concat, *right, *left;
1371             char *rsqr, *lsqr;
1372             int ret;
1373
1374             square = rec_state->ast;
1375             concat = child_first(square);
1376             right = child_first(concat);
1377             left = child_last(concat);
1378             lsqr = token_range(state->text, left->start, left->end);
1379             rsqr = token_range(state->text, right->start, right->end);
1380             ret = square_match(lens, lsqr, rsqr);
1381             if (! ret) {
1382                 get_error(state, lens, "%s \"%s\" %s \"%s\"",
1383                         "Parse error: mismatched in square lens, expecting", lsqr,
1384                         "but got", rsqr);
1385             }
1386             FREE(lsqr);
1387             FREE(rsqr);
1388             if (! ret)
1389                 goto error;
1390         }
1391         rec_state->combine(rec_state, lens, 1);
1392     } else {
1393         /* Turn the top frame from having the result of one of our children
1394            to being our result */
1395         top_frame(rec_state)->lens = lens;
1396         ERR_BAIL(state->info);
1397     }
1398     ast_pop(rec_state);
1399  error:
1400     free_tree(tree);
1401     return;
1402 }
1403
1404 static void visit_error(struct lens *lens, void *data, size_t pos,
1405                         const char *format, ...) {
1406     struct rec_state *rec_state = data;
1407     va_list ap;
1408
1409     va_start(ap, format);
1410     vget_error(rec_state->state, lens, format, ap);
1411     va_end(ap);
1412     rec_state->state->error->pos = rec_state->start + pos;
1413 }
1414
1415 static struct frame *rec_process(enum mode_t mode, struct lens *lens,
1416                                  struct state *state) {
1417     uint end = REG_END(state);
1418     uint start = REG_START(state);
1419     size_t len = 0;
1420     int r;
1421     struct jmt_visitor visitor;
1422     struct rec_state rec_state;
1423     int i;
1424     struct frame *f = NULL;
1425
1426     MEMZERO(&rec_state, 1);
1427     MEMZERO(&visitor, 1);
1428     SAVE_REGS(state);
1429
1430     if (lens->jmt == NULL) {
1431         lens->jmt = jmt_build(lens);
1432         ERR_BAIL(lens->info);
1433     }
1434
1435     rec_state.mode  = mode;
1436     rec_state.state = state;
1437     rec_state.fused = 0;
1438     rec_state.lvl   = 0;
1439     rec_state.start = start;
1440     rec_state.ast = make_ast(lens);
1441     rec_state.combine = (mode == M_GET) ? get_combine : parse_combine;
1442     ERR_NOMEM(rec_state.ast == NULL, state->info);
1443
1444     visitor.parse = jmt_parse(lens->jmt, state->text + start, end - start);
1445     ERR_BAIL(lens->info);
1446     visitor.terminal = visit_terminal;
1447     visitor.enter = visit_enter;
1448     visitor.exit = visit_exit;
1449     visitor.error = visit_error;
1450     visitor.data = &rec_state;
1451     r = jmt_visit(&visitor, &len);
1452     ERR_BAIL(lens->info);
1453     if (r != 1) {
1454         get_error(state, lens, "Syntax error");
1455         state->error->pos = start + len;
1456     }
1457     if (rec_state.fused == 0) {
1458         get_error(state, lens,
1459                   "Parse did not leave a result on the stack");
1460         goto error;
1461     } else if (rec_state.fused > 1) {
1462         get_error(state, lens,
1463                   "Parse left additional garbage on the stack");
1464         goto error;
1465     }
1466
1467     rec_state.ast = ast_root(rec_state.ast);
1468     ensure(rec_state.ast->parent == NULL, state->info);
1469  done:
1470     if (debugging("cf.get.ast"))
1471         print_ast(ast_root(rec_state.ast), 0);
1472     RESTORE_REGS(state);
1473     jmt_free_parse(visitor.parse);
1474     free_ast(ast_root(rec_state.ast));
1475     return rec_state.frames;
1476  error:
1477
1478     for(i = 0; i < rec_state.fused; i++) {
1479         f = nth_frame(&rec_state, i);
1480         FREE(f->key);
1481         free_span(f->span);
1482         if (mode == M_GET) {
1483             FREE(f->value);
1484             free_tree(f->tree);
1485         } else if (mode == M_PARSE) {
1486             free_skel(f->skel);
1487             free_dict(f->dict);
1488         }
1489     }
1490     FREE(rec_state.frames);
1491     goto done;
1492 }
1493
1494 static struct tree *get_rec(struct lens *lens, struct state *state) {
1495     struct frame *fr;
1496     struct tree *tree = NULL;
1497
1498     fr = rec_process(M_GET, lens, state);
1499     if (fr != NULL) {
1500         tree = fr->tree;
1501         state->key = fr->key;
1502         state->value = fr->value;
1503         FREE(fr);
1504     }
1505     return tree;
1506 }
1507
1508 static struct skel *parse_rec(struct lens *lens, struct state *state,
1509                               struct dict **dict) {
1510     struct skel *skel = NULL;
1511     struct frame *fr;
1512
1513     fr = rec_process(M_PARSE, lens, state);
1514     if (fr != NULL) {
1515         skel = fr->skel;
1516         *dict = fr->dict;
1517         state->key = fr->key;
1518         FREE(fr);
1519     }
1520     return skel;
1521 }
1522
1523 static struct tree *get_lens(struct lens *lens, struct state *state) {
1524     struct tree *tree = NULL;
1525
1526     switch(lens->tag) {
1527     case L_DEL:
1528         tree = get_del(lens, state);
1529         break;
1530     case L_STORE:
1531         tree = get_store(lens, state);
1532         break;
1533     case L_VALUE:
1534         tree = get_value(lens, state);
1535         break;
1536     case L_KEY:
1537         tree = get_key(lens, state);
1538         break;
1539     case L_LABEL:
1540         tree = get_label(lens, state);
1541         break;
1542     case L_SEQ:
1543         tree = get_seq(lens, state);
1544         break;
1545     case L_COUNTER:
1546         tree = get_counter(lens, state);
1547         break;
1548     case L_CONCAT:
1549         tree = get_concat(lens, state);
1550         break;
1551     case L_UNION:
1552         tree = get_union(lens, state);
1553         break;
1554     case L_SUBTREE:
1555         tree = get_subtree(lens, state);
1556         break;
1557     case L_STAR:
1558         tree = get_quant_star(lens, state);
1559         break;
1560     case L_MAYBE:
1561         tree = get_quant_maybe(lens, state);
1562         break;
1563     case L_SQUARE:
1564         tree = get_square(lens, state);
1565         break;
1566     default:
1567         BUG_ON(true, state->info, "illegal lens tag %d", lens->tag);
1568         break;
1569     }
1570  error:
1571     return tree;
1572 }
1573
1574 /* Initialize registers. Return 0 if the lens matches the entire text, 1 if
1575  * it does not and -1 on error.
1576  */
1577 static int init_regs(struct state *state, struct lens *lens, uint size) {
1578     int r;
1579
1580     if (lens->tag != L_STAR && ! lens->recursive) {
1581         r = match(state, lens, lens->ctype, size, 0);
1582         if (r == -1)
1583             get_error(state, lens, "Input string does not match at all");
1584         if (r <= -1)
1585             return -1;
1586         return r != size;
1587     }
1588     /* Special case the very common situation that the lens is (l)*
1589      * We can avoid matching the entire text in that case - that
1590      * match can be very expensive
1591      */
1592     if (ALLOC(state->regs) < 0)
1593         return -1;
1594     state->regs->num_regs = 1;
1595     if (ALLOC(state->regs->start) < 0 || ALLOC(state->regs->end) < 0)
1596         return -1;
1597     state->regs->start[0] = 0;
1598     state->regs->end[0] = size;
1599     return 0;
1600 }
1601
1602 struct tree *lns_get(struct info *info, struct lens *lens, const char *text,
1603                      struct lns_error **err) {
1604     struct state state;
1605     struct tree *tree = NULL;
1606     uint size = strlen(text);
1607     int partial, r;
1608
1609     MEMZERO(&state, 1);
1610     r = ALLOC(state.info);
1611     ERR_NOMEM(r < 0, info);
1612
1613     *state.info = *info;
1614     state.info->ref = UINT_MAX;
1615
1616     state.text = text;
1617
1618     /* We are probably being overly cautious here: if the lens can't process
1619      * all of TEXT, we should really fail somewhere in one of the sublenses.
1620      * But to be safe, we check that we can process everything anyway, then
1621      * try to process, hoping we'll get a more specific error, and if that
1622      * fails, we throw our arms in the air and say 'something went wrong'
1623      */
1624     partial = init_regs(&state, lens, size);
1625     if (partial >= 0) {
1626         if (lens->recursive)
1627             tree = get_rec(lens, &state);
1628         else
1629             tree = get_lens(lens, &state);
1630     }
1631
1632     free_seqs(state.seqs);
1633     if (state.key != NULL) {
1634         get_error(&state, lens, "get left unused key %s", state.key);
1635         free(state.key);
1636     }
1637     if (state.value != NULL) {
1638         get_error(&state, lens, "get left unused value %s", state.value);
1639         free(state.value);
1640     }
1641     if (partial && state.error == NULL) {
1642         get_error(&state, lens, "Get did not match entire input");
1643     }
1644
1645  error:
1646     free_regs(&state);
1647     FREE(state.info);
1648
1649     if (err != NULL) {
1650         *err = state.error;
1651     } else {
1652         if (state.error != NULL) {
1653             free_tree(tree);
1654             tree = NULL;
1655         }
1656         free_lns_error(state.error);
1657     }
1658     return tree;
1659 }
1660
1661 static struct skel *parse_lens(struct lens *lens, struct state *state,
1662                                struct dict **dict) {
1663     struct skel *skel = NULL;
1664
1665     switch(lens->tag) {
1666     case L_DEL:
1667         skel = parse_del(lens, state);
1668         break;
1669     case L_STORE:
1670         skel = parse_store(lens, state);
1671         break;
1672     case L_VALUE:
1673         skel = parse_value(lens, state);
1674         break;
1675     case L_KEY:
1676         skel = parse_key(lens, state);
1677         break;
1678     case L_LABEL:
1679         skel = parse_label(lens, state);
1680         break;
1681     case L_SEQ:
1682         skel = parse_seq(lens, state);
1683         break;
1684     case L_COUNTER:
1685         skel = parse_counter(lens, state);
1686         break;
1687     case L_CONCAT:
1688         skel = parse_concat(lens, state, dict);
1689         break;
1690     case L_UNION:
1691         skel = parse_union(lens, state, dict);
1692         break;
1693     case L_SUBTREE:
1694         skel = parse_subtree(lens, state, dict);
1695         break;
1696     case L_STAR:
1697         skel = parse_quant_star(lens, state, dict);
1698         break;
1699     case L_MAYBE:
1700         skel = parse_quant_maybe(lens, state, dict);
1701         break;
1702     case L_SQUARE:
1703         skel = parse_square(lens, state, dict);
1704         break;
1705     default:
1706         BUG_ON(true, state->info, "illegal lens tag %d", lens->tag);
1707         break;
1708     }
1709  error:
1710     return skel;
1711 }
1712
1713 struct skel *lns_parse(struct lens *lens, const char *text, struct dict **dict,
1714                        struct lns_error **err) {
1715     struct state state;
1716     struct skel *skel = NULL;
1717     uint size = strlen(text);
1718     int partial, r;
1719
1720     MEMZERO(&state, 1);
1721     r = ALLOC(state.info);
1722     ERR_NOMEM(r< 0, lens->info);
1723     state.info->ref = UINT_MAX;
1724     state.info->error = lens->info->error;
1725     state.text = text;
1726
1727     state.text = text;
1728
1729     partial = init_regs(&state, lens, size);
1730     if (! partial) {
1731         *dict = NULL;
1732         if (lens->recursive)
1733             skel = parse_rec(lens, &state, dict);
1734         else
1735             skel = parse_lens(lens, &state, dict);
1736
1737         free_seqs(state.seqs);
1738         if (state.error != NULL) {
1739             free_skel(skel);
1740             skel = NULL;
1741             free_dict(*dict);
1742             *dict = NULL;
1743         }
1744         if (state.key != NULL) {
1745             get_error(&state, lens, "parse left unused key %s", state.key);
1746             free(state.key);
1747         }
1748         if (state.value != NULL) {
1749             get_error(&state, lens, "parse left unused value %s", state.value);
1750             free(state.value);
1751         }
1752     } else {
1753         // This should never happen during lns_parse
1754         get_error(&state, lens, "parse can not process entire input");
1755     }
1756
1757  error:
1758     free_regs(&state);
1759     FREE(state.info);
1760     if (err != NULL) {
1761         *err = state.error;
1762     } else {
1763         free_lns_error(state.error);
1764     }
1765     return skel;
1766 }
1767
1768 /*
1769  * Local variables:
1770  *  indent-tabs-mode: nil
1771  *  c-indent-level: 4
1772  *  c-basic-offset: 4
1773  *  tab-width: 4
1774  * End:
1775  */