src/jmt.c

   1 /*
   2  * jmt.c: Earley parser for lenses based on Jim/Mandelbaum transducers
   3  *
   4  * Copyright (C) 2009-2015 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 <lutter@redhat.com>
  21  */
  22
  23 #include <config.h>
  24
  25 #include "jmt.h"
  26 #include "internal.h"
  27 #include "memory.h"
  28 #include "errcode.h"
  29
  30 /* This is an implementation of the Earley parser described in the paper
  31  * "Efficient Earley Parsing with Regular Right-hand Sides" by Trever Jim
  32  * and Yitzhak Mandelbaum.
  33  *
  34  * Since we only deal in lenses, they are both terminals and nonterminals:
  35  * recursive lenses (those with lens->recursive set) are nonterminals, and
  36  * non-recursive lenses are terminals, with the exception of non-recursive
  37  * lenses that match the empty word. Lenses are also the semantic actions
  38  * attached to a SCAN or COMPLETE during recosntruction of the parse
  39  * tree. Our SCAN makes sure that we only ever scan nonempty words - that
  40  * means that for nonrecursive lenses which match the empty word (e.g., del
  41  * [ \t]* "") we need to make sure we get a COMPLETE when the lens matched
  42  * the empty word.
  43  *
  44  * That is achieved by treating such a lens t as the construct (t|T) with
  45  * T := eps.
  46  */
  47
  48 /*
  49  * Data structures for the Jim/Mandelbaum parser
  50  */
  51
  52 #define IND_MAX UINT32_MAX
  53
  54 struct array {
  55     size_t elem_size;
  56     ind_t used;
  57     ind_t size;
  58     void *data;
  59 };
  60
  61 #define array_elem(arr, ind, typ)                               \
  62     (((typ *) (arr).data) + ind)
  63
  64 #define array_for_each(i, arr)                                  \
  65     for(ind_t i = 0; i < (arr).used; i++)
  66
  67 #define array_each_elem(elt, arr, typ)                          \
  68     for(typ *elt = (typ *) (arr).data + 0;                      \
  69         elt - (typ *) (arr).data < (arr).used;                  \
  70         elt++)
  71
  72 static void array_init(struct array *arr, size_t elem_size) {
  73     MEMZERO(arr, 1);
  74     arr->elem_size = elem_size;
  75 }
  76
  77 ATTRIBUTE_RETURN_CHECK
  78 static int array_add(struct array *arr, ind_t *ind) {
  79     if (arr->used >= arr->size) {
  80         int r;
  81         ind_t expand = arr->size;
  82         if (expand < 8)
  83             expand = 8;
  84         r = mem_realloc_n(&(arr->data), arr->elem_size, arr->size + expand);
  85         if (r < 0)
  86             return -1;
  87         memset((char *) arr->data + arr->elem_size*arr->size, 0,
  88                arr->elem_size * expand);
  89         arr->size += expand;
  90     }
  91     *ind = arr->used;
  92     arr->used += 1;
  93     return 0;
  94 }
  95
  96 /* Insert a new entry into the array at index IND. Shift all entries from
  97  * IND on back by one. */
  98 ATTRIBUTE_RETURN_CHECK
  99 static int array_insert(struct array *arr, ind_t ind) {
 100     ind_t last;
 101
 102     if (array_add(arr, &last) < 0)
 103         return -1;
 104
 105     if (ind >= last)
 106         return 0;
 107
 108     memmove((char *) arr->data + arr->elem_size*(ind+1),
 109             (char *) arr->data + arr->elem_size*ind,
 110             arr->elem_size * (arr->used - ind - 1));
 111     memset((char *) arr->data + arr->elem_size*ind, 0, arr->elem_size);
 112     return 0;
 113 }
 114
 115 static void array_release(struct array *arr) {
 116     if (arr != NULL) {
 117         free(arr->data);
 118         arr->used = arr->size = 0;
 119     }
 120 }
 121
 122 static void array_remove(struct array *arr, ind_t ind) {
 123     char *data = arr->data;
 124     memmove(data + ind * arr->elem_size,
 125             data + (ind + 1) * arr->elem_size,
 126             (arr->used - ind - 1) * arr->elem_size);
 127     arr->used -= 1;
 128 }
 129
 130 ATTRIBUTE_RETURN_CHECK
 131 static int array_join(struct array *dst, struct array *src) {
 132     int r;
 133
 134     if (dst->elem_size != src->elem_size)
 135         return -1;
 136
 137     r = mem_realloc_n(&(dst->data), dst->elem_size,
 138                       dst->used + src->used);
 139     if (r < 0)
 140         return -1;
 141
 142     memcpy(((char *) dst->data) + dst->used * dst->elem_size,
 143            src->data,
 144            src->used * src->elem_size);
 145     dst->used += src->used;
 146     dst->size = dst->used;
 147     return 0;
 148 }
 149
 150 /* Special lens indices - these don't reference lenses, but
 151  * some pseudo actions. We stash them at the top of the range
 152  * of IND_T, with LENS_MAX giving us the maximal lens index for
 153  * a real lens
 154  */
 155 enum trans_op {
 156     EPS = IND_MAX,
 157     CALL = EPS - 1,
 158     LENS_MAX = CALL - 1
 159 };
 160
 161 struct trans {
 162     struct state *to;
 163     ind_t lens;
 164 };
 165
 166 struct state {
 167     struct state *next;      /* Linked list for memory management */
 168     struct array trans;      /* Array of struct trans */
 169     ind_t  nret;             /* Number of returned lenses */
 170     ind_t  *ret;             /* The returned lenses */
 171     ind_t  num;              /* Counter for num of new states */
 172     unsigned int reachable : 1;
 173     unsigned int live : 1;
 174 };
 175
 176 /* Sets of states used in determinizing the NFA to a DFA */
 177 struct nfa_state {
 178     struct state *state;  /* The new state in the DFA */
 179     struct array     set; /* Set of (struct state *) in the NFA, sorted */
 180 };
 181
 182 /* For recursive lenses (nonterminals), the mapping of nonterminal to
 183  * state. We also store nonrecursive lenses here; in that case, the state
 184  * will be NULL */
 185 struct jmt_lens {
 186     struct lens  *lens;
 187     struct state *state;
 188 };
 189
 190 /* A Jim/Mandelbaum transducer */
 191 struct jmt {
 192     struct error *error;
 193     struct array lenses;       /* Array of struct jmt_lens */
 194     struct state *start;
 195     ind_t  lens;               /* The start symbol of the grammar */
 196     ind_t  state_count;
 197 };
 198
 199 enum item_reason {
 200     R_ROOT = 1,
 201     R_COMPLETE = R_ROOT << 1,
 202     R_PREDICT = R_COMPLETE << 1,
 203     R_SCAN = R_PREDICT << 1
 204 };
 205
 206 /* The reason an item was added for parse reconstruction; can be R_SCAN,
 207  * R_COMPLETE, R_PREDICT or R_COMPLETE|R_PREDICT */
 208 struct link {
 209     enum item_reason reason;
 210     ind_t            lens;       /* R_COMPLETE, R_SCAN */
 211     ind_t            from_set;   /* R_COMPLETE, R_PREDICT, R_SCAN */
 212     ind_t            from_item;  /* R_COMPLETE, R_PREDICT, R_SCAN */
 213     ind_t            to_item;    /* R_COMPLETE */
 214     ind_t            caller;     /* number of a state */
 215 };
 216
 217 struct item {
 218     /* The 'classical' Earley item (state, parent) */
 219     struct state    *state;
 220     ind_t            parent;
 221     /* Backlinks to why item was added */
 222     ind_t            nlinks;
 223     struct link     *links;
 224 };
 225
 226 struct item_set {
 227     struct array items;
 228 };
 229
 230 struct jmt_parse {
 231     struct jmt       *jmt;
 232     struct error     *error;
 233     const char       *text;
 234     ind_t             nsets;
 235     struct item_set **sets;
 236 };
 237
 238 #define for_each_item(it, set)                                  \
 239     array_each_elem(it, (set)->items, struct item)
 240
 241 #define for_each_trans(t, s)                                    \
 242     array_each_elem(t, (s)->trans, struct trans)
 243
 244 #define parse_state(parse, ind)                                 \
 245     array_elem(parse->states, ind, struct state)
 246
 247 static struct item *set_item(struct jmt_parse *parse, ind_t set,
 248                                  ind_t item) {
 249     ensure(parse->sets[set] != NULL, parse);
 250     ensure(item < parse->sets[set]->items.used, parse);
 251     return array_elem(parse->sets[set]->items, item, struct item);
 252  error:
 253     return NULL;
 254 }
 255
 256 static struct state *item_state(struct jmt_parse *parse, ind_t set,
 257                                     ind_t item) {
 258     return set_item(parse, set, item)->state;
 259 }
 260
 261 static struct trans *state_trans(struct state *state, ind_t t) {
 262     return array_elem(state->trans, t, struct trans);
 263 }
 264
 265 static ind_t item_parent(struct jmt_parse *parse, ind_t set, ind_t item) {
 266     return set_item(parse, set, item)->parent;
 267 }
 268
 269 static bool is_return(const struct state *s) {
 270     return s->nret > 0;
 271 }
 272
 273 static struct lens *lens_of_parse(struct jmt_parse *parse, ind_t lens) {
 274     return array_elem(parse->jmt->lenses, lens, struct jmt_lens)->lens;
 275 }
 276
 277 /*
 278  * The parser
 279  */
 280
 281 /*
 282  * Manipulate the Earley graph. We denote edges in the graph as
 283  *   [j, (s,i)] -> [k, item_k] => [l, item_l]
 284  * to indicate that we are adding item (s,i) to E_j and record that its
 285  * child is the item with index item_k in E_k and its sibling is item
 286  * item_l in E_l.
 287  */
 288
 289 /* Add item (s, k) to E_j. Note that the item was caused by action reason
 290  * using lens starting at from_item in E_{from_set}
 291  *
 292  * [j, (s,k)] -> [from_set, from_item] => [j, to_item]
 293  */
 294 static ind_t parse_add_item(struct jmt_parse *parse, ind_t j,
 295                             struct state *s, ind_t k,
 296                             enum item_reason reason, ind_t lens,
 297                             ind_t from_set,
 298                             ind_t from_item, ind_t to_item,
 299                             ind_t caller) {
 300
 301     int r;
 302     struct item_set *set = parse->sets[j];
 303     struct item *item = NULL;
 304     ind_t result = IND_MAX;
 305
 306     ensure(from_item == EPS || from_item < parse->sets[from_set]->items.used,
 307            parse);
 308     ensure(to_item == EPS || to_item < parse->sets[j]->items.used,
 309            parse);
 310
 311     if (set == NULL) {
 312         r = ALLOC(parse->sets[j]);
 313         ERR_NOMEM(r < 0, parse);
 314         array_init(&parse->sets[j]->items, sizeof(struct item));
 315         set = parse->sets[j];
 316     }
 317
 318     for (ind_t i=0; i < set->items.used; i++) {
 319         if (item_state(parse, j, i) == s
 320             && item_parent(parse, j, i) == k) {
 321             result = i;
 322             item = set_item(parse, j, i);
 323             break;
 324         }
 325     }
 326
 327     if (result == IND_MAX) {
 328         r = array_add(&set->items, &result);
 329         ERR_NOMEM(r < 0, parse);
 330
 331         item = set_item(parse, j, result);
 332         item->state = s;
 333         item->parent = k;
 334     }
 335
 336     for (ind_t i = 0; i < item->nlinks; i++) {
 337         struct link *lnk = item->links + i;
 338         if (lnk->reason == reason && lnk->lens == lens
 339             && lnk->from_set == from_set && lnk->from_item == from_item
 340             && lnk->to_item == to_item && lnk->caller == caller)
 341             return result;
 342     }
 343
 344     r = REALLOC_N(item->links, item->nlinks + 1);
 345     ERR_NOMEM(r < 0, parse);
 346
 347     struct link *lnk = item->links+ item->nlinks;
 348     item->nlinks += 1;
 349
 350     lnk->reason = reason;
 351     lnk->lens = lens;
 352     lnk->from_set = from_set;
 353     lnk->from_item = from_item;
 354     lnk->to_item = to_item;
 355     lnk->caller = caller;
 356  error:
 357     return result;
 358 }
 359
 360 /* Add item (s, i) to set E_j and record that it was added because
 361  * a parse of nonterminal lens, starting at itemk in E_k, was completed
 362  * by item item in E_j
 363  *
 364  * [j, (s,i)] -> [j, item] => [k, itemk]
 365  */
 366 static void parse_add_complete(struct jmt_parse *parse, ind_t j,
 367                                struct state *s, ind_t i,
 368                                ind_t k, ind_t itemk,
 369                                ind_t lens,
 370                                ind_t item) {
 371     parse_add_item(parse, j, s, i, R_COMPLETE, lens, k, itemk, item, IND_MAX);
 372 }
 373
 374 /* Same as parse_add_complete, but mark the item also as a predict
 375  *
 376  * [j, (s,i)] -> [j, item] => [k, itemk]
 377  */
 378 static void parse_add_predict_complete(struct jmt_parse *parse, ind_t j,
 379                                        struct state *s, ind_t i,
 380                                        ind_t k, ind_t itemk,
 381                                        ind_t lens,
 382                                        ind_t item, ind_t caller) {
 383     parse_add_item(parse, j, s, i, R_COMPLETE|R_PREDICT,
 384                    lens, k, itemk, item, caller);
 385 }
 386
 387 /* Add item (s, j) to E_j and record that it was added because of a
 388  * prediction from item from in E_j
 389  */
 390 static ind_t parse_add_predict(struct jmt_parse *parse, ind_t j,
 391                                struct state *s, ind_t from) {
 392
 393     ensure(from < parse->sets[j]->items.used, parse);
 394     struct state *t = item_state(parse, j, from);
 395
 396     return parse_add_item(parse, j, s, j, R_PREDICT, EPS, j, from, EPS,
 397                           t->num);
 398  error:
 399     return IND_MAX;
 400 }
 401
 402 /* Add item (s,i) to E_j and record that it was added because of scanning
 403  * with lens starting from item item in E_k.
 404  *
 405  * [j, (s,i)] -> [k, item]
 406  */
 407 static void parse_add_scan(struct jmt_parse *parse, ind_t j,
 408                            struct state *s, ind_t i,
 409                            ind_t lens, ind_t k, ind_t item) {
 410     ensure(item < parse->sets[k]->items.used, parse);
 411
 412     parse_add_item(parse, j, s, i, R_SCAN, lens, k, item, EPS, IND_MAX);
 413  error:
 414     return;
 415 }
 416
 417 ATTRIBUTE_PURE
 418 static bool is_complete(const struct link *lnk) {
 419     return lnk->reason & R_COMPLETE;
 420 }
 421
 422 ATTRIBUTE_PURE
 423 static bool is_predict(const struct link *lnk) {
 424     return lnk->reason & R_PREDICT;
 425 }
 426
 427 ATTRIBUTE_PURE
 428 static bool is_scan(const struct link *lnk) {
 429     return lnk->reason & R_SCAN;
 430 }
 431
 432 ATTRIBUTE_PURE
 433 static bool is_last_sibling(const struct link *lnk) {
 434     if (is_complete(lnk))
 435         return false;
 436     return lnk->reason & (R_PREDICT|R_ROOT);
 437 }
 438
 439 ATTRIBUTE_PURE
 440 static bool returns(const struct state *s, ind_t l) {
 441     for (ind_t i = 0; i < s->nret; i++)
 442         if (s->ret[i] == l)
 443             return true;
 444     return false;
 445 }
 446
 447 static void state_add_return(struct jmt *jmt, struct state *s, ind_t l) {
 448     int r;
 449
 450     if (s == NULL || returns(s, l))
 451         return;
 452
 453     r = REALLOC_N(s->ret, s->nret + 1);
 454     ERR_NOMEM(r < 0, jmt);
 455     s->ret[s->nret] = l;
 456     s->nret += 1;
 457  error:
 458     return;
 459 }
 460
 461 static void state_merge_returns(struct jmt *jmt, struct state *dst,
 462                                 const struct state *src) {
 463     for (ind_t l = 0; l < src->nret; l++)
 464         state_add_return(jmt, dst, src->ret[l]);
 465 }
 466
 467 static void nncomplete(struct jmt_parse *parse, ind_t j,
 468                        struct state *t, ind_t k, ind_t item) {
 469
 470     for (ind_t itemk = 0; itemk < parse->sets[k]->items.used; itemk++) {
 471         struct state *u = item_state(parse, k, itemk);
 472         for_each_trans(y, u) {
 473             if (returns(t, y->lens)) {
 474                 ind_t parent = item_parent(parse, k, itemk);
 475                 parse_add_complete(parse, j,
 476                                    y->to, parent,
 477                                    k, itemk, y->lens, item);
 478             }
 479         }
 480     }
 481 }
 482
 483 /* NCALLER for (t, i) in E_j, which has index item in E_j, and t -> s a
 484  * call in the transducer and s a return. The item (s,j) has index pred in
 485  * E_j
 486  */
 487 static void ncaller(struct jmt_parse *parse, ind_t j, ind_t item,
 488                     struct state *t, ind_t i, struct state *s, ind_t pred) {
 489     for_each_trans(u, t) {
 490         if (returns(s, u->lens)) {
 491             /* [j, (u->to, i)] -> [j, pred] => [j, item] */
 492             parse_add_predict_complete(parse, j,
 493                                        u->to, i,
 494                                        j, item, u->lens,
 495                                        pred, t->num);
 496         }
 497     }
 498 }
 499
 500 /* NCALLEE for (t, parent) in E_j, which has index item in E_j, and t -> s
 501  * a call in the transducer and s a return. The item (s,j) has index pred
 502  * in E_j
 503  */
 504 static void ncallee(struct jmt_parse *parse, ind_t j, ATTRIBUTE_UNUSED ind_t item,
 505                     ATTRIBUTE_UNUSED struct state *t, ATTRIBUTE_UNUSED ind_t parent, struct state *s, ind_t pred) {
 506     for_each_trans(u, s) {
 507         if (returns(s, u->lens)) {
 508             /* [j, (u->to, j)] -> [j, item] => [j, item] */
 509             parse_add_predict_complete(parse, j,
 510                                        u->to, j,
 511                                        j, pred, u->lens,
 512                                        pred, t->num);
 513         }
 514     }
 515 }
 516
 517 static struct jmt_parse *parse_init(struct jmt *jmt,
 518                                     const char *text, size_t text_len) {
 519     int r;
 520     struct jmt_parse *parse;
 521
 522     r = ALLOC(parse);
 523     ERR_NOMEM(r < 0, jmt);
 524
 525     parse->jmt = jmt;
 526     parse->error = jmt->error;
 527     parse->text = text;
 528     parse->nsets = text_len + 1;
 529     r = ALLOC_N(parse->sets, parse->nsets);
 530     ERR_NOMEM(r < 0, jmt);
 531     return parse;
 532  error:
 533     if (parse != NULL)
 534         free(parse->sets);
 535     free(parse);
 536     return NULL;
 537 }
 538
 539 void jmt_free_parse(struct jmt_parse *parse) {
 540     if (parse == NULL)
 541         return;
 542     for (int i=0; i < parse->nsets; i++) {
 543         struct item_set *set = parse->sets[i];
 544         if (set != NULL) {
 545             array_each_elem(x, set->items, struct item)
 546                 free(x->links);
 547             array_release(&set->items);
 548             free(set);
 549         }
 550     }
 551     free(parse->sets);
 552     free(parse);
 553 }
 554
 555 static struct state *lens_state(struct jmt *jmt, ind_t l);
 556
 557 static void flens(FILE *fp, ind_t l) {
 558     if (l == 0)
 559         fprintf(fp, "%c", 'S');
 560     else if (l < 'S' - 'A')
 561         fprintf(fp, "%c", 'A' + l - 1);
 562     else if (l <= 'Z' - 'A')
 563         fprintf(fp, "%c", 'A' + l);
 564     else
 565         fprintf(fp, "%u", l);
 566 }
 567
 568 static void parse_dot_link(FILE *fp, struct jmt_parse *parse,
 569                            ind_t k, struct item *x, struct link *lnk) {
 570     char *lens_label = NULL;
 571     if (is_complete(lnk) || is_scan(lnk)) {
 572         struct state *sA = lens_state(parse->jmt, lnk->lens);
 573         int r;
 574
 575         if (sA == NULL)
 576             r = xasprintf(&lens_label, "<%d>", lnk->lens);
 577         else
 578             r = xasprintf(&lens_label, "%d", lnk->lens);
 579         if (r < 0) {
 580             fprintf(fp, "// Internal error generating lens_label\n");
 581             return;
 582         }
 583     }
 584     fprintf(fp, "    n%d_%d_%d [ label = \"(%d, %d)\"];\n",
 585             k, x->state->num, x->parent, x->state->num, x->parent);
 586     if (is_complete(lnk)) {
 587         struct item *y = set_item(parse, k, lnk->to_item);
 588         const char *pred = is_predict(lnk) ? "p" : "";
 589         fprintf(fp, "    n%d_%d_%d -> n%s%d_%d_%d [ style = dashed ];\n",
 590                 k, x->state->num, x->parent,
 591                 pred, k, y->state->num, y->parent);
 592         if (is_predict(lnk)) {
 593             fprintf(fp, "    n%s%d_%d_%d [ label = \"\" ];\n",
 594                     pred, k, y->state->num, y->parent);
 595             fprintf(fp, "    n%s%d_%d_%d -> n%d_%d_%d [ style = bold ];\n",
 596                     pred, k, y->state->num, y->parent,
 597                     k, y->state->num, y->parent);
 598         }
 599         y = set_item(parse, lnk->from_set, lnk->from_item);
 600         fprintf(fp,
 601                 "    n%d_%d_%d -> n%d_%d_%d [ style = dashed, label = \"",
 602                 k, x->state->num, x->parent,
 603                 lnk->from_set, y->state->num, y->parent);
 604         flens(fp, lnk->lens);
 605         fprintf(fp, "\" ];\n");
 606     } else if (is_scan(lnk)) {
 607         struct item *y =
 608             set_item(parse, lnk->from_set, lnk->from_item);
 609         fprintf(fp,
 610                 "    n%d_%d_%d -> n%d_%d_%d [ label = \"",
 611                 k, x->state->num, x->parent,
 612                 lnk->from_set, y->state->num, y->parent);
 613         for (ind_t i=lnk->from_set; i < k; i++)
 614             fprintf(fp, "%c", parse->text[i]);
 615         fprintf(fp, "\" ];\n");
 616
 617     } else if (is_predict(lnk)) {
 618         struct item *y =
 619             set_item(parse, lnk->from_set, lnk->from_item);
 620         fprintf(fp,
 621                 "    n%d_%d_%d -> n%d_%d_%d [ style = bold ];\n",
 622                 k, x->state->num, x->parent,
 623                 lnk->from_set, y->state->num, y->parent);
 624
 625     }
 626     free(lens_label);
 627 }
 628
 629 static void parse_dot(struct jmt_parse *parse, const char *fname) {
 630     FILE *fp = debug_fopen("%s", fname);
 631     if (fp == NULL)
 632         return;
 633
 634     fprintf(fp, "digraph \"jmt_parse\" {\n");
 635     fprintf(fp, "  rankdir = RL;\n");
 636     for (int k=0; k < parse->nsets; k++) {
 637         struct item_set *set = parse->sets[k];
 638
 639         if (set == NULL)
 640             continue;
 641
 642         fprintf(fp, "  subgraph \"cluster_E_%d\" {\n", k);
 643         fprintf(fp, "    rankdir=RL;\n    rank=same;\n");
 644         fprintf(fp, "    title%d [ label=\"E%d\", shape=plaintext ]\n", k, k);
 645         for_each_item(x, set) {
 646             for (int i=0; i < x->nlinks; i++) {
 647                 struct link *lnk = x->links + i;
 648                 parse_dot_link(fp, parse, k, x, lnk);
 649             }
 650         }
 651         fprintf(fp, "}\n");
 652     }
 653     fprintf(fp, "}\n");
 654     fclose(fp);
 655 }
 656
 657 struct jmt_parse *
 658 jmt_parse(struct jmt *jmt, const char *text, size_t text_len)
 659 {
 660     struct jmt_parse *parse = NULL;
 661
 662     parse = parse_init(jmt, text, text_len);
 663     ERR_BAIL(jmt);
 664
 665     /* INIT */
 666     parse_add_item(parse, 0, jmt->start, 0, R_ROOT, EPS, EPS, EPS, EPS,
 667                    jmt->lens);
 668     /* NINIT */
 669     if (is_return(jmt->start)) {
 670         for_each_trans(x, jmt->start) {
 671             if (returns(jmt->start, x->lens))
 672                 parse_add_predict_complete(parse, 0, x->to, 0,
 673                                            0, 0, x->lens, 0, 0);
 674         }
 675     }
 676
 677     for (int j=0; j <= text_len; j++) {
 678         struct item_set *set = parse->sets[j];
 679         if (set == NULL)
 680             continue;
 681
 682         for (int item=0; item < set->items.used; item++) {
 683             struct state *t = item_state(parse, j, item);
 684             ind_t i = item_parent(parse, j, item);
 685
 686             if (is_return(t) && i != j) {
 687                 /* NNCOMPLETE */
 688                 nncomplete(parse, j, t, i, item);
 689             }
 690
 691             for_each_trans(x, t) {
 692                 if (x->lens == CALL) {
 693                     /* PREDICT */
 694                     ind_t pred = parse_add_predict(parse, j, x->to, item);
 695                     ERR_BAIL(parse);
 696                     if (is_return(x->to)) {
 697                         /* NCALLER */
 698                         ncaller(parse, j, item, t, i, x->to, pred);
 699                         /* NCALLEE */
 700                         ncallee(parse, j, item, t, i, x->to, pred);
 701                     }
 702                 } else {
 703                     int count;
 704                     struct lens *lens = lens_of_parse(parse, x->lens);
 705                     struct state *sA = lens_state(parse->jmt, x->lens);
 706                     if (! lens->recursive && sA == NULL) {
 707                         /* SCAN, terminal */
 708                         // FIXME: We really need to find every k so that
 709                         // text[j..k] matches lens->ctype, not just one
 710                         count = regexp_match(lens->ctype, text, text_len, j, NULL);
 711                         if (count > 0) {
 712                             parse_add_scan(parse, j+count,
 713                                            x->to, i,
 714                                            x->lens, j, item);
 715                         }
 716                     }
 717                 }
 718             }
 719         }
 720     }
 721     if (debugging("cf.jmt.parse"))
 722         parse_dot(parse, "jmt_parse.dot");
 723     return parse;
 724  error:
 725     jmt_free_parse(parse);
 726     return NULL;
 727 }
 728
 729 /*
 730  * Reconstruction of the parse tree
 731  */
 732
 733 static void
 734 build_nullable(struct jmt_parse *parse, ind_t pos,
 735                struct jmt_visitor *visitor, struct lens *lens, int lvl) {
 736     if (! lens->recursive) {
 737         if (visitor->terminal != NULL) {
 738             (*visitor->terminal)(lens, pos, pos, visitor->data);
 739             ERR_BAIL(parse);
 740         }
 741     } else {
 742         if (visitor->enter != NULL) {
 743             (*visitor->enter)(lens, pos, pos, visitor->data);
 744             ERR_BAIL(parse);
 745         }
 746
 747         switch(lens->tag) {
 748         case L_REC:
 749             build_nullable(parse, pos, visitor, lens->body, lvl+1);
 750             break;
 751         case L_CONCAT:
 752             for (int i=0; i < lens->nchildren; i++)
 753                 build_nullable(parse, pos, visitor, lens->children[i], lvl+1);
 754             break;
 755         case L_UNION:
 756             for (int i=0; i < lens->nchildren; i++)
 757                 if (lens->children[i]->ctype_nullable)
 758                     build_nullable(parse, pos, visitor,
 759                                    lens->children[i], lvl+1);
 760             break;
 761         case L_SUBTREE:
 762         case L_SQUARE:
 763             build_nullable(parse, pos, visitor, lens->child, lvl+1);
 764             break;
 765         case L_STAR:
 766         case L_MAYBE:
 767             break;
 768         default:
 769             BUG_ON(true, parse, "Unexpected lens tag %d", lens->tag);
 770         }
 771
 772         if (visitor->exit != NULL) {
 773             (*visitor->exit)(lens, pos, pos, visitor->data);
 774             ERR_BAIL(parse);
 775         }
 776     }
 777  error:
 778     return;
 779 }
 780
 781 static void build_trace(const char *msg, ind_t start, ind_t end,
 782                         struct item *x, int lvl) {
 783     for (int i=0; i < lvl; i++) putc(' ', stderr);
 784     if (x != NULL) {
 785         printf("%s %d..%d: (%d, %d) %d %s%s%s\n", msg,
 786                start, end, x->state->num,
 787                x->parent, x->links->lens,
 788                is_complete(x->links) ? "c" : "",
 789                is_predict(x->links) ? "p" : "",
 790                is_scan(x->links) ? "s" : "");
 791     } else {
 792         printf("%s %d..%d\n", msg, start, end);
 793     }
 794 }
 795
 796 static int add_sibling(struct array *siblings, ind_t lnk) {
 797     int r;
 798     ind_t ind;
 799
 800     r = array_add(siblings, &ind);
 801     if (r < 0)
 802         return -1;
 803     *array_elem(*siblings, ind, ind_t) = lnk;
 804     return 0;
 805 }
 806
 807 /* Return true if CALLER is a possible caller for the link LNK which starts
 808  * at item X.
 809  *
 810  * FIXME: We can get rid of the caller field on a link if we distinguish
 811  * between NCALLER and NCALLEE in the Earley graph, rather than collapse
 812  * them both into links with reason PREDICT|COMPLETE
 813  */
 814 static bool is_caller(struct item *x, struct link *lnk, ind_t caller) {
 815     if (lnk->reason & R_ROOT)
 816         return caller == lnk->caller;
 817
 818     if (! is_predict(lnk))
 819         return false;
 820
 821     if (is_complete(lnk)) {
 822         /* NCALLER: caller == t
 823          * NCALLEE: caller == s */
 824         return caller == lnk->caller;
 825     }
 826     /* PREDICT: caller == t || caller == s */
 827     return caller == lnk->caller || caller == x->state->num;
 828 }
 829
 830 /* Traverse the siblings of x and check that the callee's set of callers
 831  * contains CALLER. When a path ending with a call from CALLER exists,
 832  * record the number of the corresponding link for each item in
 833  * SIBLINGS. The links are recorded in left-to-right order, i.e. the number
 834  * of the first link to follow is in the last entry in SIBLINGS.
 835  *
 836  * Returns 0 if there is a path ending in a callee of CALLER. Return -1 if
 837  * there is none. Return -2 if there are multiple such paths. Return -3 for
 838  * any other error.
 839  */
 840 static int filter_siblings(struct jmt_visitor *visitor, struct lens *lens,
 841                           ind_t k, ind_t item, ind_t caller,
 842                           struct array *siblings) {
 843     struct jmt_parse *parse = visitor->parse;
 844     struct item *x = set_item(parse, k, item);
 845     ind_t nlast = 0;
 846     int r;
 847
 848     for (ind_t lnk = 0; lnk < x->nlinks; lnk++)
 849         if (is_last_sibling(x->links + lnk))
 850             nlast += 1;
 851
 852     if (nlast > 0 && nlast < x->nlinks)
 853         goto ambig;
 854
 855     if (nlast == x->nlinks) {
 856         for (ind_t lnk = 0; lnk < x->nlinks; lnk++) {
 857             if (is_caller(x, x->links + lnk, caller)) {
 858                 siblings->used = 0;
 859                 r = add_sibling(siblings, lnk);
 860                 if (r < 0) {
 861                     ERR_REPORT(parse, AUG_ENOMEM, NULL);
 862                     return -3;
 863                 }
 864                 return 0;
 865             }
 866         }
 867         return -1;
 868     } else {
 869         /* nlast == 0 */
 870         ind_t found = IND_MAX;
 871         for (ind_t lnk = 0; lnk < x->nlinks; lnk++) {
 872             struct link *l = x->links + lnk;
 873             r = filter_siblings(visitor, lens,
 874                                 l->from_set, l->from_item, caller,
 875                                 siblings);
 876             if (r == -1)
 877                 continue;
 878             if (r == 0) {
 879                 if (found != IND_MAX)
 880                     goto ambig;
 881                 else
 882                     found = lnk;
 883             } else {
 884                 return r;
 885             }
 886         }
 887         if (found == IND_MAX) {
 888             return -1;
 889         } else {
 890             r = add_sibling(siblings, found);
 891             if (r < 0) {
 892                 ERR_REPORT(parse, AUG_ENOMEM, NULL);
 893                 return -3;
 894             }
 895             return 0;
 896         }
 897     }
 898  ambig:
 899     (*visitor->error)(lens, visitor->data, k,
 900                       "Ambiguous parse: %d links in state (%d, %d) in E_%d",
 901                       x->nlinks, x->state->num, x->parent, k);
 902     return -2;
 903 }
 904
 905 static void visit_enter(struct jmt_visitor *visitor, struct lens *lens,
 906                         size_t start, size_t end,
 907                         struct item *x, int lvl) {
 908     if (debugging("cf.jmt.visit"))
 909         build_trace("{", start, end, x, lvl);
 910     if (visitor->enter != NULL)
 911         (*visitor->enter)(lens, start, end, visitor->data);
 912 }
 913
 914 static void visit_exit(struct jmt_visitor *visitor, struct lens *lens,
 915                        size_t start, size_t end,
 916                        struct item *x, int lvl) {
 917     if (debugging("cf.jmt.visit"))
 918         build_trace("}", start, end, x, lvl);
 919     if (visitor->exit != NULL)
 920         (*visitor->exit)(lens, start, end, visitor->data);
 921 }
 922
 923 static int
 924 build_children(struct jmt_parse *parse, ind_t k, ind_t item,
 925                struct jmt_visitor *visitor, int lvl, ind_t caller);
 926
 927 static int
 928 build_tree(struct jmt_parse *parse, ind_t k, ind_t item, struct lens *lens,
 929            struct jmt_visitor *visitor, int lvl) {
 930     struct item *x = set_item(parse, k, item);
 931     ind_t start = x->links->from_set;
 932     ind_t end = k;
 933     struct item *old_x = x;
 934
 935     if (start == end) {
 936         /* This completion corresponds to a nullable nonterminal
 937          * that match epsilon. Reconstruct the full parse tree
 938          * for matching epsilon */
 939         if (debugging("cf.jmt.visit"))
 940             build_trace("N", x->links->from_set, k, x, lvl);
 941         build_nullable(parse, start, visitor, lens, lvl);
 942         return end;
 943     }
 944
 945     ensure(is_complete(x->links), parse);
 946
 947     visit_enter(visitor, lens, start, end, x, lvl);
 948     ERR_BAIL(parse);
 949
 950     /* x is a completion item. (k, x->to_item) is its first child in the
 951      * parse tree. */
 952     if (! is_predict(x->links)) {
 953         struct link *lnk = x->links;
 954         struct item *sib = set_item(parse, lnk->from_set, lnk->from_item);
 955         ind_t caller = sib->state->num;
 956
 957         item = lnk->to_item;
 958         x = set_item(parse, k, item);
 959         build_children(parse, k, item, visitor, lvl, caller);
 960         ERR_BAIL(parse);
 961     }
 962
 963     visit_exit(visitor, lens, start, end, old_x, lvl);
 964     ERR_BAIL(parse);
 965  error:
 966     return end;
 967 }
 968
 969 static int
 970 build_children(struct jmt_parse *parse, ind_t k, ind_t item,
 971                struct jmt_visitor *visitor, int lvl, ind_t caller) {
 972     struct item *x = set_item(parse, k, item);
 973     struct lens *lens = lens_of_parse(parse, x->links->lens);
 974     struct array siblings;
 975     ind_t end = k;
 976     int r;
 977
 978     array_init(&siblings, sizeof(ind_t));
 979     r = filter_siblings(visitor, lens, k, item, caller, &siblings);
 980     if (r < 0)
 981         goto error;
 982
 983     /* x the first item in a list of siblings; visit items (x->from_set,
 984      * x->from_item) in order, which will visit x and its siblings in the
 985      * parse tree from right to left */
 986     for (ind_t i = siblings.used - 1; i > 0; i--) {
 987         ind_t lnk = *array_elem(siblings, i, ind_t);
 988         struct lens *sub = lens_of_parse(parse, x->links[lnk].lens);
 989         if (sub->recursive) {
 990             build_tree(parse, k, item, sub, visitor, lvl+1);
 991             ERR_BAIL(parse);
 992         } else {
 993             if (debugging("cf.jmt.visit"))
 994                 build_trace("T", x->links->from_set, k, x, lvl+1);
 995             if (visitor->terminal != NULL) {
 996                 (*visitor->terminal)(sub,
 997                                      x->links->from_set, k, visitor->data);
 998                 ERR_BAIL(parse);
 999             }
1000         }
1001         k = x->links[lnk].from_set;
1002         item = x->links[lnk].from_item;
1003         x = set_item(parse, k, item);
1004     }
1005  error:
1006     array_release(&siblings);
1007     return end;
1008 }
1009
1010 int jmt_visit(struct jmt_visitor *visitor, size_t *len) {
1011     struct jmt_parse *parse = visitor->parse;
1012     ind_t k = parse->nsets - 1;     /* Current Earley set */
1013     ind_t item;
1014     struct item_set *set = parse->sets[k];
1015
1016     if (set == NULL)
1017         goto noparse;
1018
1019     for (item = 0; item < set->items.used; item++) {
1020         struct item *x = set_item(parse, k, item);
1021         if (x->parent == 0 && returns(x->state, parse->jmt->lens)) {
1022             for (ind_t i = 0; i < x->nlinks; i++) {
1023                 if (is_complete(x->links + i) || is_scan(x->links + i)) {
1024                     if (debugging("cf.jmt.visit"))
1025                         printf("visit: found (%d, %d) in E_%d\n",
1026                                x->state->num, x->parent, k);
1027                     goto found;
1028                 }
1029             }
1030         }
1031     }
1032  found:
1033     if (item >= parse->sets[k]->items.used)
1034         goto noparse;
1035     struct lens *lens = lens_of_parse(parse, parse->jmt->lens);
1036
1037     visit_enter(visitor, lens, 0, k, NULL, 0);
1038     ERR_BAIL(parse);
1039
1040     *len = build_children(parse, k, item, visitor, 0,
1041                           parse->jmt->start->num);
1042     ERR_BAIL(parse);
1043
1044     visit_exit(visitor, lens, 0, k, NULL, 0);
1045     ERR_BAIL(parse);
1046     return 1;
1047  error:
1048     return -1;
1049  noparse:
1050     for (; k > 0; k--)
1051         if (parse->sets[k] != NULL) break;
1052     *len = k;
1053     return 0;
1054 }
1055
1056 /*
1057  * Build the automaton
1058  */
1059
1060
1061 static struct state *make_state(struct jmt *jmt) {
1062     struct state *s;
1063     int r;
1064
1065     r = ALLOC(s);
1066     ERR_NOMEM(r < 0, jmt);
1067     s->num = jmt->state_count++;
1068     array_init(&s->trans, sizeof(struct trans));
1069     if (jmt->start != NULL)
1070         list_cons(jmt->start->next, s);
1071     else
1072         jmt->start = s;
1073     return s;
1074  error:
1075     return NULL;
1076 }
1077
1078 static ind_t add_lens(struct jmt *jmt, struct lens *lens) {
1079     int r;
1080     ind_t l;
1081     struct state *sA = NULL;
1082     int nullable = 0;
1083
1084     r = array_add(&jmt->lenses, &l);
1085     ERR_NOMEM(r < 0, jmt);
1086     ERR_NOMEM(l == IND_MAX, jmt);
1087
1088     if (! lens->recursive)
1089         nullable = regexp_matches_empty(lens->ctype);
1090
1091     array_elem(jmt->lenses, l, struct jmt_lens)->lens = lens;
1092     /* A nonrecursive lens that matches epsilon is both a terminal
1093      * and a nonterminal */
1094     if (lens->recursive || nullable) {
1095         sA = make_state(jmt);
1096         ERR_NOMEM(sA == NULL, jmt);
1097         array_elem(jmt->lenses, l, struct jmt_lens)->state = sA;
1098         if (! lens->recursive) {
1099             /* Add lens again, so that l refers to the nonterminal T
1100              * for the lens, and l+1 refers to the terminal t for it */
1101             ind_t m;
1102             r = array_add(&jmt->lenses, &m);
1103             ERR_NOMEM(r < 0, jmt);
1104             ERR_NOMEM(m == IND_MAX, jmt);
1105
1106             array_elem(jmt->lenses, m, struct jmt_lens)->lens = lens;
1107         }
1108     }
1109
1110     if (debugging("cf.jmt")) {
1111         if (sA == NULL) {
1112             printf("add_lens: ");
1113             print_regexp(stdout, lens->ctype);
1114             printf(" %s\n", format_lens(lens));
1115         } else {
1116             printf("add_lens: ");
1117             flens(stdout, l);
1118             printf(" %u %s\n", sA->num, format_lens(lens));
1119             if (nullable) {
1120                 printf("add_lens: // %s\n", format_lens(lens));
1121             }
1122         }
1123     }
1124
1125     return l;
1126  error:
1127     return IND_MAX;
1128 }
1129
1130 static struct trans *
1131 add_new_trans(struct jmt *jmt,
1132               struct state *from, struct state *to, ind_t lens) {
1133     struct trans *t;
1134     ind_t i;
1135     int r;
1136
1137     if (from == NULL || to == NULL)
1138         return NULL;
1139
1140     r = array_add(&from->trans, &i);
1141     ERR_NOMEM(r < 0, jmt);
1142     t = array_elem(from->trans, i, struct trans);
1143     t->to = to;
1144     t->lens = lens;
1145     return t;
1146  error:
1147     return NULL;
1148 }
1149
1150 static struct trans *
1151 add_eps_trans(struct jmt *jmt, struct state *from, struct state *to) {
1152     return add_new_trans(jmt, from, to, EPS);
1153 }
1154
1155 static struct lens *lens_of_jmt(struct jmt *jmt, ind_t l) {
1156     return array_elem(jmt->lenses, l, struct jmt_lens)->lens;
1157 }
1158
1159 static ind_t lens_index(struct jmt *jmt, struct lens *lens) {
1160     array_for_each(i, jmt->lenses)
1161         if (lens_of_jmt(jmt, i) == lens)
1162             return i;
1163     return IND_MAX;
1164 }
1165
1166 static struct state *lens_state(struct jmt *jmt, ind_t l) {
1167     return array_elem(jmt->lenses, l, struct jmt_lens)->state;
1168 }
1169
1170 static void print_lens_symbol(FILE *fp, struct jmt *jmt, struct lens *lens) {
1171     ind_t l = lens_index(jmt, lens);
1172     struct state *sA = lens_state(jmt, l);
1173
1174     if (sA == NULL)
1175         print_regexp(fp, lens->ctype);
1176     else
1177         flens(fp, l);
1178 }
1179
1180 static void print_grammar(struct jmt *jmt, struct lens *lens) {
1181     ind_t l = lens_index(jmt, lens);
1182     struct state *sA = lens_state(jmt, l);
1183
1184     if (sA == NULL || (lens->tag == L_REC && lens->rec_internal))
1185         return;
1186
1187     printf("  ");
1188     print_lens_symbol(stdout, jmt, lens);
1189     printf(" := ");
1190
1191     if (! lens->recursive) {
1192         /* Nullable regexps */
1193         print_regexp(stdout, lens->ctype);
1194         printf("\n");
1195         return;
1196     }
1197
1198     switch (lens->tag) {
1199     case L_CONCAT:
1200         print_lens_symbol(stdout, jmt, lens->children[0]);
1201         for (int i=1; i < lens->nchildren; i++) {
1202             printf(" . ");
1203             print_lens_symbol(stdout, jmt, lens->children[i]);
1204         }
1205         printf("\n");
1206         for (int i=0; i < lens->nchildren; i++)
1207             print_grammar(jmt, lens->children[i]);
1208         break;
1209     case L_UNION:
1210         print_lens_symbol(stdout, jmt, lens->children[0]);
1211         for (int i=1; i < lens->nchildren; i++) {
1212             printf(" | ");
1213             print_lens_symbol(stdout, jmt, lens->children[i]);
1214         }
1215         printf("\n");
1216         for (int i=0; i < lens->nchildren; i++)
1217             print_grammar(jmt, lens->children[i]);
1218         break;
1219     case L_SUBTREE:
1220         print_lens_symbol(stdout, jmt, lens->child);
1221         printf("\n");
1222         print_grammar(jmt, lens->child);
1223         break;
1224     case L_STAR:
1225         print_lens_symbol(stdout, jmt, lens->child);
1226         printf("*\n");
1227         print_grammar(jmt, lens->child);
1228         break;
1229     case L_MAYBE:
1230         print_lens_symbol(stdout, jmt, lens->child);
1231         printf("?\n");
1232         print_grammar(jmt, lens->child);
1233         break;
1234     case L_REC:
1235         print_lens_symbol(stdout, jmt, lens->body);
1236         printf("\n");
1237         print_grammar(jmt, lens->body);
1238         break;
1239     case L_SQUARE:
1240        print_lens_symbol(stdout, jmt, lens->child);
1241        printf("\n");
1242        print_grammar(jmt, lens->child);
1243        break;
1244     default:
1245         BUG_ON(true, jmt, "Unexpected lens tag %d", lens->tag);
1246         break;
1247     }
1248  error:
1249     return;
1250 }
1251
1252 static void print_grammar_top(struct jmt *jmt, struct lens *lens) {
1253     printf("Grammar:\n");
1254     print_grammar(jmt, lens);
1255     if (lens->tag == L_REC) {
1256         printf("  ");
1257         print_lens_symbol(stdout, jmt, lens->alias);
1258         printf(" := ");
1259         print_lens_symbol(stdout, jmt, lens->alias->body);
1260         printf("\n");
1261     }
1262 }
1263
1264 static void index_lenses(struct jmt *jmt, struct lens *lens) {
1265     ind_t l;
1266
1267     l = lens_index(jmt, lens);
1268     if (l == IND_MAX) {
1269         l = add_lens(jmt, lens);
1270         ERR_BAIL(jmt);
1271     }
1272
1273     if (! lens->recursive)
1274         return;
1275
1276     switch (lens->tag) {
1277     case L_CONCAT:
1278     case L_UNION:
1279         for (int i=0; i < lens->nchildren; i++)
1280             index_lenses(jmt, lens->children[i]);
1281         break;
1282     case L_SUBTREE:
1283     case L_STAR:
1284     case L_MAYBE:
1285     case L_SQUARE:
1286         index_lenses(jmt, lens->child);
1287         break;
1288     case L_REC:
1289         if (! lens->rec_internal)
1290             index_lenses(jmt, lens->body);
1291         break;
1292     default:
1293         BUG_ON(true, jmt, "Unexpected lens tag %d", lens->tag);
1294         break;
1295     }
1296  error:
1297     return;
1298 }
1299
1300 static void thompson(struct jmt *jmt, struct lens *lens,
1301                      struct state **s, struct state **f) {
1302     ind_t l = lens_index(jmt, lens);
1303     struct state *sA = lens_state(jmt, l);
1304     ensure(l < jmt->lenses.used, jmt);
1305
1306     *s = make_state(jmt);
1307     *f = make_state(jmt);
1308     ERR_BAIL(jmt);
1309
1310     if (lens->recursive) {
1311         /* A nonterminal */
1312         add_new_trans(jmt, *s, *f, l);
1313         add_new_trans(jmt, *s, sA, CALL);
1314     } else if (sA == NULL) {
1315         /* A terminal that never matches epsilon */
1316         add_new_trans(jmt, *s, *f, l);
1317     } else {
1318         /* A terminal that matches epsilon */
1319         add_new_trans(jmt, *s, *f, l);
1320         add_new_trans(jmt, *s, sA, CALL);
1321         add_new_trans(jmt, *s, *f, l+1);
1322     }
1323  error:
1324     return;
1325 }
1326
1327 static void conv(struct jmt *jmt, struct lens *lens,
1328                  struct state **s, struct state **e,
1329                  struct state **f) {
1330     ind_t l = lens_index(jmt, lens);
1331     ensure(l < jmt->lenses.used, jmt);
1332     struct state *sA = lens_state(jmt, l);
1333
1334     *s = NULL;
1335     *e = NULL;
1336     *f = NULL;
1337
1338     if (lens->recursive) {
1339         /* A nonterminal */
1340         *s = make_state(jmt);
1341         *f = make_state(jmt);
1342         ERR_BAIL(jmt);
1343         add_new_trans(jmt, *s, *f, l);
1344         ERR_BAIL(jmt);
1345         ensure(sA != NULL, jmt);
1346         add_new_trans(jmt, *s, sA, EPS);
1347         ERR_BAIL(jmt);
1348     } else if (sA == NULL) {
1349         /* A terminal that never matches epsilon */
1350         *s = make_state(jmt);
1351         *f = make_state(jmt);
1352         ERR_BAIL(jmt);
1353         add_new_trans(jmt, *s, *f, l);
1354         ERR_BAIL(jmt);
1355     } else {
1356         /* A terminal that matches epsilon */
1357         *s = make_state(jmt);
1358         *f = make_state(jmt);
1359         ERR_BAIL(jmt);
1360         add_new_trans(jmt, *s, *f, l);
1361         add_new_trans(jmt, *s, *f, l+1);
1362         add_new_trans(jmt, *s, sA, EPS);
1363         ERR_BAIL(jmt);
1364     }
1365  error:
1366     return;
1367 }
1368
1369 static void conv_concat(struct jmt *jmt, struct lens *lens,
1370                         struct state **s, struct state **e,
1371                         struct state **f) {
1372     struct state *s2, *f2, *e2;
1373
1374     conv(jmt, lens->children[0], &s2, &e2, &f2);
1375     *s = make_state(jmt);
1376     add_new_trans(jmt, *s, s2, EPS);
1377
1378     for (int i=1; i < lens->nchildren; i++) {
1379         struct state *s3, *e3, *f3, *scall, *fcall;
1380         conv(jmt, lens->children[i], &s3, &e3, &f3);
1381         thompson(jmt, lens->children[i], &scall, &fcall);
1382         ERR_BAIL(jmt);
1383         add_eps_trans(jmt, f2, scall);
1384         add_eps_trans(jmt, e2, s3);
1385         *f = make_state(jmt);
1386         add_eps_trans(jmt, f3, *f);
1387         add_eps_trans(jmt, fcall, *f);
1388         *e = make_state(jmt);
1389         add_eps_trans(jmt, e3, *e);
1390         f2 = *f;
1391         e2 = *e;
1392     }
1393  error:
1394     return;
1395 }
1396
1397 static void conv_union(struct jmt *jmt, struct lens *lens,
1398                         struct state **s, struct state **e,
1399                         struct state **f) {
1400
1401     *s = make_state(jmt);
1402     *e = make_state(jmt);
1403     *f = make_state(jmt);
1404     ERR_BAIL(jmt);
1405
1406     for (int i = 0; i < lens->nchildren; i++) {
1407         struct state *s2, *e2, *f2;
1408
1409         conv(jmt, lens->children[i], &s2, &e2, &f2);
1410         ERR_BAIL(jmt);
1411
1412         add_eps_trans(jmt, *s, s2);
1413         add_eps_trans(jmt, e2, *e);
1414         add_eps_trans(jmt, f2, *f);
1415     }
1416
1417  error:
1418     return;
1419 }
1420
1421 static void conv_star(struct jmt *jmt, struct lens *lens,
1422                       struct state **s, struct state **e,
1423                       struct state **f) {
1424
1425     *s = make_state(jmt);
1426     *e = make_state(jmt);
1427     *f = make_state(jmt);
1428     ERR_BAIL(jmt);
1429
1430     struct state *si, *ei, *fi, *scall, *fcall;
1431     conv(jmt, lens->child, &si, &ei, &fi);
1432     thompson(jmt, lens->child, &scall, &fcall);
1433     ERR_BAIL(jmt);
1434
1435     add_eps_trans(jmt, *s, si);
1436     add_eps_trans(jmt, ei, si);
1437     add_eps_trans(jmt, *s, *e);
1438     add_eps_trans(jmt, ei, *e);
1439     add_eps_trans(jmt, fi, scall);
1440     add_eps_trans(jmt, fcall, scall);
1441     add_eps_trans(jmt, fi, *f);
1442     add_eps_trans(jmt, fcall, *f);
1443     ERR_BAIL(jmt);
1444
1445  error:
1446     return;
1447 }
1448
1449 static void conv_rhs(struct jmt *jmt, ind_t l) {
1450     struct lens *lens = lens_of_jmt(jmt, l);
1451     struct state *s = NULL, *e = NULL, *f = NULL;
1452     struct state *sA = lens_state(jmt, l);
1453
1454     if (! lens->recursive) {
1455         /* Nothing to do for terminals that do not match epsilon */
1456         if (sA != NULL)
1457             state_add_return(jmt, sA, l);
1458         return;
1459     }
1460
1461     /* All other nonterminals/recursive lenses */
1462
1463     /* Maintain P1 */
1464     if (lens->ctype_nullable)
1465         state_add_return(jmt, sA, l);
1466
1467     switch (lens->tag) {
1468     case L_REC:
1469         conv(jmt, lens->body, &s, &e, &f);
1470         break;
1471     case L_CONCAT:
1472         conv_concat(jmt, lens, &s, &e, &f);
1473         break;
1474     case L_UNION:
1475         conv_union(jmt, lens, &s, &e, &f);
1476         break;
1477     case L_SUBTREE:
1478         conv(jmt, lens->child, &s, &e, &f);
1479         break;
1480     case L_STAR:
1481         conv_star(jmt, lens, &s, &e, &f);
1482         break;
1483     case L_MAYBE:
1484         conv(jmt, lens->child, &s, &e, &f);
1485         add_new_trans(jmt, s, e, EPS);
1486         break;
1487     case L_SQUARE:
1488        conv(jmt, lens->child, &s, &e, &f);
1489        break;
1490     default:
1491         BUG_ON(true, jmt, "Unexpected lens tag %d", lens->tag);
1492     }
1493
1494     ensure(sA != NULL, jmt);
1495
1496     add_eps_trans(jmt, sA, s);
1497     state_add_return(jmt, e, l);
1498     state_add_return(jmt, f, l);
1499
1500  error:
1501     return;
1502 }
1503
1504 ATTRIBUTE_RETURN_CHECK
1505 static int push_state(struct array *worklist, struct state *s) {
1506     int r;
1507     ind_t ind;
1508
1509     r = array_add(worklist, &ind);
1510     if (r < 0)
1511         return -1;
1512     *array_elem(*worklist, ind, struct state *) = s;
1513     return 0;
1514 }
1515
1516 static struct state *pop_state(struct array *worklist) {
1517     if (worklist->used > 0) {
1518         worklist->used -= 1;
1519         return *array_elem(*worklist, worklist->used, struct state *);
1520     } else {
1521         return NULL;
1522     }
1523 }
1524
1525 static void free_state(struct state *s) {
1526     if (s == NULL)
1527         return;
1528     free(s->ret);
1529     array_release(&s->trans);
1530     free(s);
1531 }
1532
1533 static void collect(struct jmt *jmt) {
1534     struct array worklist;
1535     size_t count, removed;
1536     int r;
1537
1538     count = 0;
1539     list_for_each(s, jmt->start) {
1540         s->live = 0;
1541         s->reachable = 0;
1542         count += 1;
1543     }
1544
1545     array_init(&worklist, sizeof(struct state *));
1546     jmt->start->reachable = 1;
1547     for (struct state *s = jmt->start;
1548          s != NULL;
1549          s = pop_state(&worklist)) {
1550         for_each_trans(t, s) {
1551             if (! t->to->reachable) {
1552                 t->to->reachable = 1;
1553                 r = push_state(&worklist, t->to);
1554                 ERR_NOMEM(r < 0, jmt);
1555             }
1556         }
1557     }
1558
1559     list_for_each(s, jmt->start)
1560         if (s->reachable && is_return(s))
1561             s->live = 1;
1562
1563     bool changed;
1564     do {
1565         changed = false;
1566         list_for_each(s, jmt->start) {
1567             if (! s->live && s->reachable) {
1568                 for_each_trans(t, s) {
1569                     if (t->lens != CALL && t->to->live) {
1570                         s->live = 1;
1571                         changed = true;
1572                         break;
1573                     }
1574                 }
1575             }
1576         }
1577     } while (changed);
1578
1579     list_for_each(s, jmt->start) {
1580         if (s->live && s->reachable) {
1581             for (ind_t i = 0; i < s->trans.used; ) {
1582                 struct trans *t = state_trans(s, i);
1583                 if (! (t->to->live && t->to->reachable))
1584                     array_remove(&s->trans, i);
1585                 else
1586                     i += 1;
1587             }
1588         }
1589     }
1590
1591     removed = 0;
1592     for (struct state *s = jmt->start;
1593          s->next != NULL; ) {
1594         struct state *p = s->next;
1595         if (p->live && p->reachable) {
1596             s = p;
1597         } else {
1598             s->next = p->next;
1599             free_state(p);
1600             removed += 1;
1601         }
1602     }
1603
1604  error:
1605     array_release(&worklist);
1606     return;
1607 }
1608
1609 static void dedup(struct state *s) {
1610     array_for_each(i, s->trans) {
1611         struct trans *t = state_trans(s, i);
1612         for (ind_t j = i+1; j < s->trans.used;) {
1613             struct trans *u = state_trans(s, j);
1614             if (t->to == u->to && t->lens == u->lens)
1615                 array_remove(&s->trans, j);
1616             else
1617                 j += 1;
1618         }
1619     }
1620 }
1621
1622 static void unepsilon(struct jmt *jmt) {
1623     int r;
1624
1625     if (debugging("cf.jmt.build"))
1626         jmt_dot(jmt, "jmt_10_raw.dot");
1627     collect(jmt);
1628
1629     /* Get rid of epsilon transitions */
1630     bool changed;
1631     do {
1632         changed = false;
1633         list_for_each(s, jmt->start) {
1634             array_for_each(i , s->trans) {
1635                 struct trans *t = state_trans(s, i);
1636                 if (t->lens == EPS) {
1637                     struct state *to = t->to;
1638                     array_remove(&s->trans, i);
1639                     r = array_join(&s->trans, &to->trans);
1640                     ERR_NOMEM(r < 0, jmt);
1641                     state_merge_returns(jmt, s, to);
1642                     dedup(s);
1643                     changed = true;
1644                 }
1645             }
1646         }
1647     } while (changed);
1648
1649     collect(jmt);
1650     if (debugging("cf.jmt.build"))
1651         jmt_dot(jmt, "jmt_20_uneps.dot");
1652  error:
1653     return;
1654 }
1655
1656 static bool is_deterministic(struct jmt *jmt) {
1657     list_for_each(s, jmt->start) {
1658         array_for_each(i, s->trans) {
1659             struct trans *t = state_trans(s, i);
1660             for (ind_t j = i+1; j < s->trans.used; j++) {
1661                 struct trans *u = state_trans(s, j);
1662                 if (t->lens == u->lens)
1663                     return false;
1664             }
1665         }
1666     }
1667     return true;
1668 }
1669
1670 static void free_nfa_state(struct nfa_state *s) {
1671     if (s == NULL)
1672         return;
1673     array_release(&s->set);
1674     free(s);
1675 }
1676
1677 static struct nfa_state *make_nfa_state(struct jmt *jmt) {
1678     struct nfa_state *result = NULL;
1679     int r;
1680
1681     r = ALLOC(result);
1682     ERR_NOMEM(r < 0, jmt);
1683
1684     array_init(&result->set, sizeof(struct state *));
1685
1686     return result;
1687  error:
1688     FREE(result);
1689     return NULL;
1690 }
1691
1692 static ind_t nfa_state_add(struct jmt *jmt, struct nfa_state *nfa,
1693                            struct state *s) {
1694     ind_t i;
1695     int r;
1696
1697     array_for_each(j, nfa->set) {
1698         struct state *q = *array_elem(nfa->set, j, struct state *);
1699         if (q == s)
1700             return j;
1701     }
1702
1703     /* Keep the list of states sorted */
1704     i = nfa->set.used;
1705     for (int j=0; j + 1 < nfa->set.used; j++) {
1706         if (s < *array_elem(nfa->set, j, struct state *)) {
1707             i = j;
1708             break;
1709         }
1710     }
1711     r = array_insert(&nfa->set, i);
1712     ERR_NOMEM(r < 0, jmt);
1713
1714     *array_elem(nfa->set, i, struct state *) = s;
1715     return i;
1716  error:
1717     return IND_MAX;
1718 }
1719
1720 static bool nfa_same_set(struct nfa_state *s1, struct nfa_state *s2) {
1721     if (s1->set.used != s2->set.used)
1722         return false;
1723
1724     array_for_each(i, s1->set) {
1725         struct state *q1 = *array_elem(s1->set, i, struct state *);
1726         struct state *q2 = *array_elem(s2->set, i, struct state *);
1727         if (q1 != q2)
1728             return false;
1729     }
1730
1731     return true;
1732 }
1733
1734 static struct nfa_state *nfa_uniq(struct jmt *jmt, struct array *newstates,
1735                                   struct nfa_state *s) {
1736     ind_t ind;
1737     int r;
1738
1739     array_each_elem(q, *newstates, struct nfa_state *) {
1740         if (nfa_same_set(s, *q)) {
1741             if (s == *q)
1742                 return s;
1743             free_nfa_state(s);
1744             return *q;
1745         }
1746     }
1747
1748     r = array_add(newstates, &ind);
1749     ERR_NOMEM(r < 0, jmt);
1750     *array_elem(*newstates, ind, struct nfa_state *) = s;
1751
1752     if (s->state == NULL) {
1753         s->state = make_state(jmt);
1754         ERR_BAIL(jmt);
1755     }
1756
1757     /* This makes looking at pictures easier */
1758     if (s->set.used == 1)
1759         s->state->num = (*array_elem(s->set, 0, struct state *))->num;
1760
1761     return s;
1762
1763  error:
1764     return NULL;
1765 }
1766
1767 static void det_target(struct jmt *jmt, struct array *newstates,
1768                        struct nfa_state *nfas, ind_t l) {
1769     struct nfa_state *to = NULL;
1770
1771     array_each_elem(s, nfas->set, struct state *) {
1772         for_each_trans(t, *s) {
1773             if (t->lens == l) {
1774                 if (to == NULL) {
1775                     to = make_nfa_state(jmt);
1776                     ERR_RET(jmt);
1777                 }
1778                 nfa_state_add(jmt, to, t->to);
1779                 ERR_RET(jmt);
1780             }
1781         }
1782     }
1783
1784     if (to != NULL) {
1785         to = nfa_uniq(jmt, newstates, to);
1786         ERR_RET(jmt);
1787         add_new_trans(jmt, nfas->state, to->state, l);
1788     }
1789 }
1790
1791 static void determinize(struct jmt *jmt) {
1792     struct nfa_state *ini = NULL;
1793     struct array *newstates = NULL;
1794     int r;
1795     ind_t ind, nlenses;
1796
1797     if (is_deterministic(jmt))
1798         return;
1799
1800     r = ALLOC(newstates);
1801     ERR_NOMEM(r < 0, jmt);
1802     array_init(newstates, sizeof(struct nfa_state *));
1803
1804     nlenses = jmt->lenses.used;
1805
1806     /* The initial state consists of just the start state */
1807     ini = make_nfa_state(jmt);
1808     ERR_BAIL(jmt);
1809     nfa_state_add(jmt, ini, jmt->start);
1810     ERR_BAIL(jmt);
1811
1812     /* Make a new initial state */
1813     ini->state = make_state(jmt);
1814     ini->state->num = jmt->start->num;  /* Makes lokking at pictures easier */
1815     ERR_BAIL(jmt);
1816     jmt->start->next = ini->state->next;
1817     ini->state->next = jmt->start;
1818     jmt->start = ini->state;
1819
1820     r = array_add(newstates, &ind);
1821     ERR_NOMEM(r < 0, jmt);
1822
1823     *array_elem(*newstates, ind, struct nfa_state *) = ini;
1824     ini = NULL;
1825
1826     for (ind_t i = 0; i < newstates->used; i++) {
1827         struct nfa_state *nfas = *array_elem(*newstates, i, struct nfa_state *);
1828
1829         for (int j = 0; j < nfas->set.used; j++) {
1830             struct state *s = *array_elem(nfas->set, j, struct state *);
1831             state_merge_returns(jmt, nfas->state, s);
1832         }
1833
1834         for (ind_t l = 0; l < nlenses; l++) {
1835             det_target(jmt, newstates, nfas, l);
1836             ERR_BAIL(jmt);
1837         }
1838         det_target(jmt, newstates, nfas, CALL);
1839         ERR_BAIL(jmt);
1840     }
1841
1842     collect(jmt);
1843
1844  done:
1845     if (newstates) {
1846         array_each_elem(s, *newstates, struct nfa_state *) {
1847             free_nfa_state(*s);
1848         }
1849         array_release(newstates);
1850         FREE(newstates);
1851     }
1852     free_nfa_state(ini);
1853     return;
1854  error:
1855     goto done;
1856 }
1857
1858 struct jmt *jmt_build(struct lens *lens) {
1859     struct jmt *jmt = NULL;
1860     int r;
1861
1862     r = ALLOC(jmt);
1863     ERR_NOMEM(r < 0, lens->info);
1864
1865     jmt->error = lens->info->error;
1866     array_init(&jmt->lenses, sizeof(struct jmt_lens));
1867
1868     index_lenses(jmt, lens);
1869
1870     if (debugging("cf.jmt"))
1871         print_grammar_top(jmt, lens);
1872
1873     for (ind_t i=0; i < jmt->lenses.used; i++) {
1874         conv_rhs(jmt, i);
1875         ERR_BAIL(jmt);
1876     }
1877
1878     unepsilon(jmt);
1879     ERR_BAIL(jmt);
1880
1881     determinize(jmt);
1882     ERR_BAIL(jmt);
1883
1884     if (debugging("cf.jmt.build"))
1885         jmt_dot(jmt, "jmt_30_dfa.dot");
1886
1887     return jmt;
1888  error:
1889     jmt_free(jmt);
1890     return NULL;
1891 }
1892
1893 void jmt_free(struct jmt *jmt) {
1894     if (jmt == NULL)
1895         return;
1896     array_release(&jmt->lenses);
1897     struct state *s = jmt->start;
1898     while (s != NULL) {
1899         struct state *del = s;
1900         s = del->next;
1901         free_state(del);
1902     }
1903     free(jmt);
1904 }
1905
1906 void jmt_dot(struct jmt *jmt, const char *fname) {
1907     FILE *fp = debug_fopen("%s", fname);
1908     if (fp == NULL)
1909         return;
1910
1911     fprintf(fp, "digraph \"jmt\" {\n");
1912     fprintf(fp, "  rankdir = LR;\n");
1913     list_for_each(s, jmt->start) {
1914         if (is_return(s)) {
1915             fprintf(fp, "  %u [ shape = doublecircle, label = \"%u (",
1916                     s->num, s->num);
1917             flens(fp, s->ret[0]);
1918             for (ind_t i = 1; i < s->nret; i++) {
1919                 fprintf(fp, ", ");
1920                 flens(fp, s->ret[i]);
1921             }
1922             fprintf(fp, ")\" ];\n");
1923         }
1924         for_each_trans(t, s) {
1925             fprintf(fp, "  %u -> %u ", s->num, t->to->num);
1926             if (t->lens == EPS)
1927                 fprintf(fp, ";\n");
1928             else if (t->lens == CALL)
1929                 fprintf(fp, "[ label = \"call\" ];\n");
1930             else if (lens_state(jmt, t->lens) == NULL) {
1931                 struct lens *lens = lens_of_jmt(jmt, t->lens);
1932                 fprintf(fp, "[ label = \"");
1933                 print_regexp(fp, lens->ctype);
1934                 fprintf(fp, "\" ];\n");
1935             } else {
1936                 fprintf(fp, "[ label = \"");
1937                 flens(fp, t->lens);
1938                 fprintf(fp, "\" ];\n");
1939             }
1940         }
1941     }
1942     fprintf(fp, "}\n");
1943     fclose(fp);
1944 }
1945
1946 /*
1947  * Local variables:
1948  *  indent-tabs-mode: nil
1949  *  c-indent-level: 4
1950  *  c-basic-offset: 4
1951  *  tab-width: 4
1952  * End:
1953  */