src/jmt.c

   1 /*
   2  * jmt.c: Earley parser for lenses based on Jim/Mandelbaum transducers
   3  *
   4  * Copyright (C) 2009-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 <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             char *s = format_lens(lens);
1113             printf("add_lens: ");
1114             print_regexp(stdout, lens->ctype);
1115             printf(" %s\n", s);
1116             free(s);
1117         } else {
1118             char *s = format_lens(lens);
1119             printf("add_lens: ");
1120             flens(stdout, l);
1121             printf(" %u %s\n", sA->num, s);
1122             if (nullable) {
1123                 printf("add_lens: // %s\n", s);
1124             }
1125             free(s);
1126         }
1127     }
1128
1129     return l;
1130  error:
1131     return IND_MAX;
1132 }
1133
1134 static struct trans *
1135 add_new_trans(struct jmt *jmt,
1136               struct state *from, struct state *to, ind_t lens) {
1137     struct trans *t;
1138     ind_t i;
1139     int r;
1140
1141     if (from == NULL || to == NULL)
1142         return NULL;
1143
1144     r = array_add(&from->trans, &i);
1145     ERR_NOMEM(r < 0, jmt);
1146     t = array_elem(from->trans, i, struct trans);
1147     t->to = to;
1148     t->lens = lens;
1149     return t;
1150  error:
1151     return NULL;
1152 }
1153
1154 static struct trans *
1155 add_eps_trans(struct jmt *jmt, struct state *from, struct state *to) {
1156     return add_new_trans(jmt, from, to, EPS);
1157 }
1158
1159 static struct lens *lens_of_jmt(struct jmt *jmt, ind_t l) {
1160     return array_elem(jmt->lenses, l, struct jmt_lens)->lens;
1161 }
1162
1163 static ind_t lens_index(struct jmt *jmt, struct lens *lens) {
1164     array_for_each(i, jmt->lenses)
1165         if (lens_of_jmt(jmt, i) == lens)
1166             return i;
1167     return IND_MAX;
1168 }
1169
1170 static struct state *lens_state(struct jmt *jmt, ind_t l) {
1171     return array_elem(jmt->lenses, l, struct jmt_lens)->state;
1172 }
1173
1174 static void print_lens_symbol(FILE *fp, struct jmt *jmt, struct lens *lens) {
1175     ind_t l = lens_index(jmt, lens);
1176     struct state *sA = lens_state(jmt, l);
1177
1178     if (sA == NULL)
1179         print_regexp(fp, lens->ctype);
1180     else
1181         flens(fp, l);
1182 }
1183
1184 static void print_grammar(struct jmt *jmt, struct lens *lens) {
1185     ind_t l = lens_index(jmt, lens);
1186     struct state *sA = lens_state(jmt, l);
1187
1188     if (sA == NULL || (lens->tag == L_REC && lens->rec_internal))
1189         return;
1190
1191     printf("  ");
1192     print_lens_symbol(stdout, jmt, lens);
1193     printf(" := ");
1194
1195     if (! lens->recursive) {
1196         /* Nullable regexps */
1197         print_regexp(stdout, lens->ctype);
1198         printf("\n");
1199         return;
1200     }
1201
1202     switch (lens->tag) {
1203     case L_CONCAT:
1204         print_lens_symbol(stdout, jmt, lens->children[0]);
1205         for (int i=1; i < lens->nchildren; i++) {
1206             printf(" . ");
1207             print_lens_symbol(stdout, jmt, lens->children[i]);
1208         }
1209         printf("\n");
1210         for (int i=0; i < lens->nchildren; i++)
1211             print_grammar(jmt, lens->children[i]);
1212         break;
1213     case L_UNION:
1214         print_lens_symbol(stdout, jmt, lens->children[0]);
1215         for (int i=1; i < lens->nchildren; i++) {
1216             printf(" | ");
1217             print_lens_symbol(stdout, jmt, lens->children[i]);
1218         }
1219         printf("\n");
1220         for (int i=0; i < lens->nchildren; i++)
1221             print_grammar(jmt, lens->children[i]);
1222         break;
1223     case L_SUBTREE:
1224         print_lens_symbol(stdout, jmt, lens->child);
1225         printf("\n");
1226         print_grammar(jmt, lens->child);
1227         break;
1228     case L_STAR:
1229         print_lens_symbol(stdout, jmt, lens->child);
1230         printf("*\n");
1231         print_grammar(jmt, lens->child);
1232         break;
1233     case L_MAYBE:
1234         print_lens_symbol(stdout, jmt, lens->child);
1235         printf("?\n");
1236         print_grammar(jmt, lens->child);
1237         break;
1238     case L_REC:
1239         print_lens_symbol(stdout, jmt, lens->body);
1240         printf("\n");
1241         print_grammar(jmt, lens->body);
1242         break;
1243     case L_SQUARE:
1244        print_lens_symbol(stdout, jmt, lens->child);
1245        printf("\n");
1246        print_grammar(jmt, lens->child);
1247        break;
1248     default:
1249         BUG_ON(true, jmt, "Unexpected lens tag %d", lens->tag);
1250         break;
1251     }
1252  error:
1253     return;
1254 }
1255
1256 static void print_grammar_top(struct jmt *jmt, struct lens *lens) {
1257     printf("Grammar:\n");
1258     print_grammar(jmt, lens);
1259     if (lens->tag == L_REC) {
1260         printf("  ");
1261         print_lens_symbol(stdout, jmt, lens->alias);
1262         printf(" := ");
1263         print_lens_symbol(stdout, jmt, lens->alias->body);
1264         printf("\n");
1265     }
1266 }
1267
1268 static void index_lenses(struct jmt *jmt, struct lens *lens) {
1269     ind_t l;
1270
1271     l = lens_index(jmt, lens);
1272     if (l == IND_MAX) {
1273         l = add_lens(jmt, lens);
1274         ERR_BAIL(jmt);
1275     }
1276
1277     if (! lens->recursive)
1278         return;
1279
1280     switch (lens->tag) {
1281     case L_CONCAT:
1282     case L_UNION:
1283         for (int i=0; i < lens->nchildren; i++)
1284             index_lenses(jmt, lens->children[i]);
1285         break;
1286     case L_SUBTREE:
1287     case L_STAR:
1288     case L_MAYBE:
1289     case L_SQUARE:
1290         index_lenses(jmt, lens->child);
1291         break;
1292     case L_REC:
1293         if (! lens->rec_internal)
1294             index_lenses(jmt, lens->body);
1295         break;
1296     default:
1297         BUG_ON(true, jmt, "Unexpected lens tag %d", lens->tag);
1298         break;
1299     }
1300  error:
1301     return;
1302 }
1303
1304 static void thompson(struct jmt *jmt, struct lens *lens,
1305                      struct state **s, struct state **f) {
1306     ind_t l = lens_index(jmt, lens);
1307     struct state *sA = lens_state(jmt, l);
1308     ensure(l < jmt->lenses.used, jmt);
1309
1310     *s = make_state(jmt);
1311     *f = make_state(jmt);
1312     ERR_BAIL(jmt);
1313
1314     if (lens->recursive) {
1315         /* A nonterminal */
1316         add_new_trans(jmt, *s, *f, l);
1317         add_new_trans(jmt, *s, sA, CALL);
1318     } else if (sA == NULL) {
1319         /* A terminal that never matches epsilon */
1320         add_new_trans(jmt, *s, *f, l);
1321     } else {
1322         /* A terminal that matches epsilon */
1323         add_new_trans(jmt, *s, *f, l);
1324         add_new_trans(jmt, *s, sA, CALL);
1325         add_new_trans(jmt, *s, *f, l+1);
1326     }
1327  error:
1328     return;
1329 }
1330
1331 static void conv(struct jmt *jmt, struct lens *lens,
1332                  struct state **s, struct state **e,
1333                  struct state **f) {
1334     ind_t l = lens_index(jmt, lens);
1335     ensure(l < jmt->lenses.used, jmt);
1336     struct state *sA = lens_state(jmt, l);
1337
1338     *s = NULL;
1339     *e = NULL;
1340     *f = NULL;
1341
1342     if (lens->recursive) {
1343         /* A nonterminal */
1344         *s = make_state(jmt);
1345         *f = make_state(jmt);
1346         ERR_BAIL(jmt);
1347         add_new_trans(jmt, *s, *f, l);
1348         ERR_BAIL(jmt);
1349         ensure(sA != NULL, jmt);
1350         add_new_trans(jmt, *s, sA, EPS);
1351         ERR_BAIL(jmt);
1352     } else if (sA == NULL) {
1353         /* A terminal that never matches epsilon */
1354         *s = make_state(jmt);
1355         *f = make_state(jmt);
1356         ERR_BAIL(jmt);
1357         add_new_trans(jmt, *s, *f, l);
1358         ERR_BAIL(jmt);
1359     } else {
1360         /* A terminal that matches epsilon */
1361         *s = make_state(jmt);
1362         *f = make_state(jmt);
1363         ERR_BAIL(jmt);
1364         add_new_trans(jmt, *s, *f, l);
1365         add_new_trans(jmt, *s, *f, l+1);
1366         add_new_trans(jmt, *s, sA, EPS);
1367         ERR_BAIL(jmt);
1368     }
1369  error:
1370     return;
1371 }
1372
1373 static void conv_concat(struct jmt *jmt, struct lens *lens,
1374                         struct state **s, struct state **e,
1375                         struct state **f) {
1376     struct state *s2, *f2, *e2;
1377
1378     conv(jmt, lens->children[0], &s2, &e2, &f2);
1379     *s = make_state(jmt);
1380     add_new_trans(jmt, *s, s2, EPS);
1381
1382     for (int i=1; i < lens->nchildren; i++) {
1383         struct state *s3, *e3, *f3, *scall, *fcall;
1384         conv(jmt, lens->children[i], &s3, &e3, &f3);
1385         thompson(jmt, lens->children[i], &scall, &fcall);
1386         ERR_BAIL(jmt);
1387         add_eps_trans(jmt, f2, scall);
1388         add_eps_trans(jmt, e2, s3);
1389         *f = make_state(jmt);
1390         add_eps_trans(jmt, f3, *f);
1391         add_eps_trans(jmt, fcall, *f);
1392         *e = make_state(jmt);
1393         add_eps_trans(jmt, e3, *e);
1394         f2 = *f;
1395         e2 = *e;
1396     }
1397  error:
1398     return;
1399 }
1400
1401 static void conv_union(struct jmt *jmt, struct lens *lens,
1402                         struct state **s, struct state **e,
1403                         struct state **f) {
1404
1405     *s = make_state(jmt);
1406     *e = make_state(jmt);
1407     *f = make_state(jmt);
1408     ERR_BAIL(jmt);
1409
1410     for (int i = 0; i < lens->nchildren; i++) {
1411         struct state *s2, *e2, *f2;
1412
1413         conv(jmt, lens->children[i], &s2, &e2, &f2);
1414         ERR_BAIL(jmt);
1415
1416         add_eps_trans(jmt, *s, s2);
1417         add_eps_trans(jmt, e2, *e);
1418         add_eps_trans(jmt, f2, *f);
1419     }
1420
1421  error:
1422     return;
1423 }
1424
1425 static void conv_star(struct jmt *jmt, struct lens *lens,
1426                       struct state **s, struct state **e,
1427                       struct state **f) {
1428
1429     *s = make_state(jmt);
1430     *e = make_state(jmt);
1431     *f = make_state(jmt);
1432     ERR_BAIL(jmt);
1433
1434     struct state *si, *ei, *fi, *scall, *fcall;
1435     conv(jmt, lens->child, &si, &ei, &fi);
1436     thompson(jmt, lens->child, &scall, &fcall);
1437     ERR_BAIL(jmt);
1438
1439     add_eps_trans(jmt, *s, si);
1440     add_eps_trans(jmt, ei, si);
1441     add_eps_trans(jmt, *s, *e);
1442     add_eps_trans(jmt, ei, *e);
1443     add_eps_trans(jmt, fi, scall);
1444     add_eps_trans(jmt, fcall, scall);
1445     add_eps_trans(jmt, fi, *f);
1446     add_eps_trans(jmt, fcall, *f);
1447     ERR_BAIL(jmt);
1448
1449  error:
1450     return;
1451 }
1452
1453 static void conv_rhs(struct jmt *jmt, ind_t l) {
1454     struct lens *lens = lens_of_jmt(jmt, l);
1455     struct state *s = NULL, *e = NULL, *f = NULL;
1456     struct state *sA = lens_state(jmt, l);
1457
1458     if (! lens->recursive) {
1459         /* Nothing to do for terminals that do not match epsilon */
1460         if (sA != NULL)
1461             state_add_return(jmt, sA, l);
1462         return;
1463     }
1464
1465     /* All other nonterminals/recursive lenses */
1466
1467     /* Maintain P1 */
1468     if (lens->ctype_nullable)
1469         state_add_return(jmt, sA, l);
1470
1471     switch (lens->tag) {
1472     case L_REC:
1473         conv(jmt, lens->body, &s, &e, &f);
1474         break;
1475     case L_CONCAT:
1476         conv_concat(jmt, lens, &s, &e, &f);
1477         break;
1478     case L_UNION:
1479         conv_union(jmt, lens, &s, &e, &f);
1480         break;
1481     case L_SUBTREE:
1482         conv(jmt, lens->child, &s, &e, &f);
1483         break;
1484     case L_STAR:
1485         conv_star(jmt, lens, &s, &e, &f);
1486         break;
1487     case L_MAYBE:
1488         conv(jmt, lens->child, &s, &e, &f);
1489         add_new_trans(jmt, s, e, EPS);
1490         break;
1491     case L_SQUARE:
1492        conv(jmt, lens->child, &s, &e, &f);
1493        break;
1494     default:
1495         BUG_ON(true, jmt, "Unexpected lens tag %d", lens->tag);
1496     }
1497
1498     ensure(sA != NULL, jmt);
1499
1500     add_eps_trans(jmt, sA, s);
1501     state_add_return(jmt, e, l);
1502     state_add_return(jmt, f, l);
1503
1504  error:
1505     return;
1506 }
1507
1508 ATTRIBUTE_RETURN_CHECK
1509 static int push_state(struct array *worklist, struct state *s) {
1510     int r;
1511     ind_t ind;
1512
1513     r = array_add(worklist, &ind);
1514     if (r < 0)
1515         return -1;
1516     *array_elem(*worklist, ind, struct state *) = s;
1517     return 0;
1518 }
1519
1520 static struct state *pop_state(struct array *worklist) {
1521     if (worklist->used > 0) {
1522         worklist->used -= 1;
1523         return *array_elem(*worklist, worklist->used, struct state *);
1524     } else {
1525         return NULL;
1526     }
1527 }
1528
1529 static void free_state(struct state *s) {
1530     if (s == NULL)
1531         return;
1532     free(s->ret);
1533     array_release(&s->trans);
1534     free(s);
1535 }
1536
1537 static void collect(struct jmt *jmt) {
1538     struct array worklist;
1539     size_t count, removed;
1540     int r;
1541
1542     count = 0;
1543     list_for_each(s, jmt->start) {
1544         s->live = 0;
1545         s->reachable = 0;
1546         count += 1;
1547     }
1548
1549     array_init(&worklist, sizeof(struct state *));
1550     jmt->start->reachable = 1;
1551     for (struct state *s = jmt->start;
1552          s != NULL;
1553          s = pop_state(&worklist)) {
1554         for_each_trans(t, s) {
1555             if (! t->to->reachable) {
1556                 t->to->reachable = 1;
1557                 r = push_state(&worklist, t->to);
1558                 ERR_NOMEM(r < 0, jmt);
1559             }
1560         }
1561     }
1562
1563     list_for_each(s, jmt->start)
1564         if (s->reachable && is_return(s))
1565             s->live = 1;
1566
1567     bool changed;
1568     do {
1569         changed = false;
1570         list_for_each(s, jmt->start) {
1571             if (! s->live && s->reachable) {
1572                 for_each_trans(t, s) {
1573                     if (t->lens != CALL && t->to->live) {
1574                         s->live = 1;
1575                         changed = true;
1576                         break;
1577                     }
1578                 }
1579             }
1580         }
1581     } while (changed);
1582
1583     list_for_each(s, jmt->start) {
1584         if (s->live && s->reachable) {
1585             for (ind_t i = 0; i < s->trans.used; ) {
1586                 struct trans *t = state_trans(s, i);
1587                 if (! (t->to->live && t->to->reachable))
1588                     array_remove(&s->trans, i);
1589                 else
1590                     i += 1;
1591             }
1592         }
1593     }
1594
1595     removed = 0;
1596     for (struct state *s = jmt->start;
1597          s->next != NULL; ) {
1598         struct state *p = s->next;
1599         if (p->live && p->reachable) {
1600             s = p;
1601         } else {
1602             s->next = p->next;
1603             free_state(p);
1604             removed += 1;
1605         }
1606     }
1607
1608  error:
1609     array_release(&worklist);
1610     return;
1611 }
1612
1613 static void dedup(struct state *s) {
1614     array_for_each(i, s->trans) {
1615         struct trans *t = state_trans(s, i);
1616         for (ind_t j = i+1; j < s->trans.used;) {
1617             struct trans *u = state_trans(s, j);
1618             if (t->to == u->to && t->lens == u->lens)
1619                 array_remove(&s->trans, j);
1620             else
1621                 j += 1;
1622         }
1623     }
1624 }
1625
1626 static void unepsilon(struct jmt *jmt) {
1627     int r;
1628
1629     if (debugging("cf.jmt.build"))
1630         jmt_dot(jmt, "jmt_10_raw.dot");
1631     collect(jmt);
1632
1633     /* Get rid of epsilon transitions */
1634     bool changed;
1635     do {
1636         changed = false;
1637         list_for_each(s, jmt->start) {
1638             array_for_each(i , s->trans) {
1639                 struct trans *t = state_trans(s, i);
1640                 if (t->lens == EPS) {
1641                     struct state *to = t->to;
1642                     array_remove(&s->trans, i);
1643                     r = array_join(&s->trans, &to->trans);
1644                     ERR_NOMEM(r < 0, jmt);
1645                     state_merge_returns(jmt, s, to);
1646                     dedup(s);
1647                     changed = true;
1648                 }
1649             }
1650         }
1651     } while (changed);
1652
1653     collect(jmt);
1654     if (debugging("cf.jmt.build"))
1655         jmt_dot(jmt, "jmt_20_uneps.dot");
1656  error:
1657     return;
1658 }
1659
1660 static bool is_deterministic(struct jmt *jmt) {
1661     list_for_each(s, jmt->start) {
1662         array_for_each(i, s->trans) {
1663             struct trans *t = state_trans(s, i);
1664             for (ind_t j = i+1; j < s->trans.used; j++) {
1665                 struct trans *u = state_trans(s, j);
1666                 if (t->lens == u->lens)
1667                     return false;
1668             }
1669         }
1670     }
1671     return true;
1672 }
1673
1674 static void free_nfa_state(struct nfa_state *s) {
1675     if (s == NULL)
1676         return;
1677     array_release(&s->set);
1678     free(s);
1679 }
1680
1681 static struct nfa_state *make_nfa_state(struct jmt *jmt) {
1682     struct nfa_state *result = NULL;
1683     int r;
1684
1685     r = ALLOC(result);
1686     ERR_NOMEM(r < 0, jmt);
1687
1688     array_init(&result->set, sizeof(struct state *));
1689
1690     return result;
1691  error:
1692     FREE(result);
1693     return NULL;
1694 }
1695
1696 static ind_t nfa_state_add(struct jmt *jmt, struct nfa_state *nfa,
1697                            struct state *s) {
1698     ind_t i;
1699     int r;
1700
1701     array_for_each(j, nfa->set) {
1702         struct state *q = *array_elem(nfa->set, j, struct state *);
1703         if (q == s)
1704             return j;
1705     }
1706
1707     /* Keep the list of states sorted */
1708     i = nfa->set.used;
1709     for (int j=0; j + 1 < nfa->set.used; j++) {
1710         if (s < *array_elem(nfa->set, j, struct state *)) {
1711             i = j;
1712             break;
1713         }
1714     }
1715     r = array_insert(&nfa->set, i);
1716     ERR_NOMEM(r < 0, jmt);
1717
1718     *array_elem(nfa->set, i, struct state *) = s;
1719     return i;
1720  error:
1721     return IND_MAX;
1722 }
1723
1724 static bool nfa_same_set(struct nfa_state *s1, struct nfa_state *s2) {
1725     if (s1->set.used != s2->set.used)
1726         return false;
1727
1728     array_for_each(i, s1->set) {
1729         struct state *q1 = *array_elem(s1->set, i, struct state *);
1730         struct state *q2 = *array_elem(s2->set, i, struct state *);
1731         if (q1 != q2)
1732             return false;
1733     }
1734
1735     return true;
1736 }
1737
1738 static struct nfa_state *nfa_uniq(struct jmt *jmt, struct array *newstates,
1739                                   struct nfa_state *s) {
1740     ind_t ind;
1741     int r;
1742
1743     array_each_elem(q, *newstates, struct nfa_state *) {
1744         if (nfa_same_set(s, *q)) {
1745             if (s == *q)
1746                 return s;
1747             free_nfa_state(s);
1748             return *q;
1749         }
1750     }
1751
1752     r = array_add(newstates, &ind);
1753     ERR_NOMEM(r < 0, jmt);
1754     *array_elem(*newstates, ind, struct nfa_state *) = s;
1755
1756     if (s->state == NULL) {
1757         s->state = make_state(jmt);
1758         ERR_BAIL(jmt);
1759     }
1760
1761     /* This makes looking at pictures easier */
1762     if (s->set.used == 1)
1763         s->state->num = (*array_elem(s->set, 0, struct state *))->num;
1764
1765     return s;
1766
1767  error:
1768     return NULL;
1769 }
1770
1771 static void det_target(struct jmt *jmt, struct array *newstates,
1772                        struct nfa_state *nfas, ind_t l) {
1773     struct nfa_state *to = NULL;
1774
1775     array_each_elem(s, nfas->set, struct state *) {
1776         for_each_trans(t, *s) {
1777             if (t->lens == l) {
1778                 if (to == NULL) {
1779                     to = make_nfa_state(jmt);
1780                     ERR_RET(jmt);
1781                 }
1782                 nfa_state_add(jmt, to, t->to);
1783                 ERR_RET(jmt);
1784             }
1785         }
1786     }
1787
1788     if (to != NULL) {
1789         to = nfa_uniq(jmt, newstates, to);
1790         ERR_RET(jmt);
1791         add_new_trans(jmt, nfas->state, to->state, l);
1792     }
1793 }
1794
1795 static void determinize(struct jmt *jmt) {
1796     struct nfa_state *ini = NULL;
1797     struct array *newstates = NULL;
1798     int r;
1799     ind_t ind, nlenses;
1800
1801     if (is_deterministic(jmt))
1802         return;
1803
1804     r = ALLOC(newstates);
1805     ERR_NOMEM(r < 0, jmt);
1806     array_init(newstates, sizeof(struct nfa_state *));
1807
1808     nlenses = jmt->lenses.used;
1809
1810     /* The initial state consists of just the start state */
1811     ini = make_nfa_state(jmt);
1812     ERR_BAIL(jmt);
1813     nfa_state_add(jmt, ini, jmt->start);
1814     ERR_BAIL(jmt);
1815
1816     /* Make a new initial state */
1817     ini->state = make_state(jmt);
1818     ini->state->num = jmt->start->num;  /* Makes lokking at pictures easier */
1819     ERR_BAIL(jmt);
1820     jmt->start->next = ini->state->next;
1821     ini->state->next = jmt->start;
1822     jmt->start = ini->state;
1823
1824     r = array_add(newstates, &ind);
1825     ERR_NOMEM(r < 0, jmt);
1826
1827     *array_elem(*newstates, ind, struct nfa_state *) = ini;
1828     ini = NULL;
1829
1830     for (ind_t i = 0; i < newstates->used; i++) {
1831         struct nfa_state *nfas = *array_elem(*newstates, i, struct nfa_state *);
1832
1833         for (int j = 0; j < nfas->set.used; j++) {
1834             struct state *s = *array_elem(nfas->set, j, struct state *);
1835             state_merge_returns(jmt, nfas->state, s);
1836         }
1837
1838         for (ind_t l = 0; l < nlenses; l++) {
1839             det_target(jmt, newstates, nfas, l);
1840             ERR_BAIL(jmt);
1841         }
1842         det_target(jmt, newstates, nfas, CALL);
1843         ERR_BAIL(jmt);
1844     }
1845
1846     collect(jmt);
1847
1848  done:
1849     if (newstates) {
1850         array_each_elem(s, *newstates, struct nfa_state *) {
1851             free_nfa_state(*s);
1852         }
1853         array_release(newstates);
1854         FREE(newstates);
1855     }
1856     free_nfa_state(ini);
1857     return;
1858  error:
1859     goto done;
1860 }
1861
1862 struct jmt *jmt_build(struct lens *lens) {
1863     struct jmt *jmt = NULL;
1864     int r;
1865
1866     r = ALLOC(jmt);
1867     ERR_NOMEM(r < 0, lens->info);
1868
1869     jmt->error = lens->info->error;
1870     array_init(&jmt->lenses, sizeof(struct jmt_lens));
1871
1872     index_lenses(jmt, lens);
1873
1874     if (debugging("cf.jmt"))
1875         print_grammar_top(jmt, lens);
1876
1877     for (ind_t i=0; i < jmt->lenses.used; i++) {
1878         conv_rhs(jmt, i);
1879         ERR_BAIL(jmt);
1880     }
1881
1882     unepsilon(jmt);
1883     ERR_BAIL(jmt);
1884
1885     determinize(jmt);
1886     ERR_BAIL(jmt);
1887
1888     if (debugging("cf.jmt.build"))
1889         jmt_dot(jmt, "jmt_30_dfa.dot");
1890
1891     return jmt;
1892  error:
1893     jmt_free(jmt);
1894     return NULL;
1895 }
1896
1897 void jmt_free(struct jmt *jmt) {
1898     if (jmt == NULL)
1899         return;
1900     array_release(&jmt->lenses);
1901     struct state *s = jmt->start;
1902     while (s != NULL) {
1903         struct state *del = s;
1904         s = del->next;
1905         free_state(del);
1906     }
1907     free(jmt);
1908 }
1909
1910 void jmt_dot(struct jmt *jmt, const char *fname) {
1911     FILE *fp = debug_fopen("%s", fname);
1912     if (fp == NULL)
1913         return;
1914
1915     fprintf(fp, "digraph \"jmt\" {\n");
1916     fprintf(fp, "  rankdir = LR;\n");
1917     list_for_each(s, jmt->start) {
1918         if (is_return(s)) {
1919             fprintf(fp, "  %u [ shape = doublecircle, label = \"%u (",
1920                     s->num, s->num);
1921             flens(fp, s->ret[0]);
1922             for (ind_t i = 1; i < s->nret; i++) {
1923                 fprintf(fp, ", ");
1924                 flens(fp, s->ret[i]);
1925             }
1926             fprintf(fp, ")\" ];\n");
1927         }
1928         for_each_trans(t, s) {
1929             fprintf(fp, "  %u -> %u ", s->num, t->to->num);
1930             if (t->lens == EPS)
1931                 fprintf(fp, ";\n");
1932             else if (t->lens == CALL)
1933                 fprintf(fp, "[ label = \"call\" ];\n");
1934             else if (lens_state(jmt, t->lens) == NULL) {
1935                 struct lens *lens = lens_of_jmt(jmt, t->lens);
1936                 fprintf(fp, "[ label = \"");
1937                 print_regexp(fp, lens->ctype);
1938                 fprintf(fp, "\" ];\n");
1939             } else {
1940                 fprintf(fp, "[ label = \"");
1941                 flens(fp, t->lens);
1942                 fprintf(fp, "\" ];\n");
1943             }
1944         }
1945     }
1946     fprintf(fp, "}\n");
1947     fclose(fp);
1948 }
1949
1950 /*
1951  * Local variables:
1952  *  indent-tabs-mode: nil
1953  *  c-indent-level: 4
1954  *  c-basic-offset: 4
1955  *  tab-width: 4
1956  * End:
1957  */