lex.c

/*
  Copyright 2002-2004 John Plevyak, All Rights Reserved
*/

#include "d.h"

typedef struct NFAState {
  uint			index;
  Vec(struct NFAState*)	chars[256];
  Vec(struct NFAState*)	epsilon;
  Vec(Action*)		accepts;
  Vec(Action*)		live;
} NFAState;

typedef struct DFAState {
  Vec(struct NFAState*)	states;
  struct DFAState	*chars[256];	
  ScanState		*scan;
} DFAState;

typedef Vec(DFAState *) VecDFAState;
typedef Vec(NFAState *) VecNFAState;

typedef struct LexState {
  uint nfa_index;
  VecNFAState allnfas;
  uint transitions;
  uint scanners;
  uint ignore_case;
} LexState;

static NFAState *
new_NFAState(LexState *ls) {
  NFAState *n = MALLOC(sizeof(NFAState));
  memset(n, 0, sizeof(NFAState));
  n->index = ls->nfa_index++;
  vec_add(&ls->allnfas, n);
  return n;
}

static DFAState *
new_DFAState() {
  DFAState *n = MALLOC(sizeof(DFAState));
  memset(n, 0, sizeof(DFAState));
  return n;
}

static void
free_DFAState(DFAState *y) {
  vec_free(&y->states);
  FREE(y);
}

static void
free_VecDFAState(VecDFAState *dfas) {
  uint i;
  for (i = 0; i < dfas->n; i++)
    free_DFAState(dfas->v[i]);
  vec_free(dfas);
}

static void
free_NFAState(NFAState *y) {
  uint i;
  for (i = 0; i < 256; i++)
    vec_free(&y->chars[i]);
  vec_free(&y->epsilon);
  vec_free(&y->accepts);
  FREE(y);
}

static void
free_VecNFAState(VecNFAState *nfas) {
  uint i;
  for (i = 0; i < nfas->n; i++)
    free_NFAState(nfas->v[i]);
  vec_free(nfas);
}

static ScanState *
new_ScanState() {
  ScanState *n = MALLOC(sizeof(ScanState));
  memset(n, 0, sizeof(ScanState));
  return n;
}

static int 
nfacmp(const void *ai, const void *aj) {
  uint32 i = (*(NFAState**)ai)->index;
  uint32 j = (*(NFAState**)aj)->index;
  return (i > j) ? 1 : ((i < j) ? -1 : 0);
}

static void
nfa_closure(DFAState *x) {
  uint i, j, k;

  for (i = 0; i < x->states.n; i++)
    for (j = 0; j < x->states.v[i]->epsilon.n; j++) {
	  NFAState *s;
      for (k = 0; k < x->states.n; k++)
	if (x->states.v[i]->epsilon.v[j] == x->states.v[k])
	  goto Lbreak;
      s = x->states.v[i];
      vec_add(&x->states, s->epsilon.v[j]);
    Lbreak:;
    }
  qsort(x->states.v, x->states.n, sizeof(x->states.v[0]), nfacmp);
}

static int
eq_dfa_state(DFAState *x, DFAState *y) {
  uint i;

  if (x->states.n != y->states.n)
    return 0;
  for (i = 0; i < x->states.n; i++)
    if (x->states.v[i] != y->states.v[i])
      return 0;
  return 1;
}

static void
dfa_to_scanner(VecDFAState *alldfas, VecScanState *scanner) {
  uint i, j, k;
  int highest, p;

  vec_clear(scanner);
  for (i = 0; i < alldfas->n; i++) {
    alldfas->v[i]->scan = new_ScanState();
    alldfas->v[i]->scan->index = i;
    vec_add(scanner, alldfas->v[i]->scan);
  }
  for (i = 0; i < alldfas->n; i++) {
    for (j = 0; j < 256; j++)
      if (alldfas->v[i]->chars[j])
	alldfas->v[i]->scan->chars[j] = alldfas->v[i]->chars[j]->scan;
    highest = INT_MIN;
    for (j = 0; j < alldfas->v[i]->states.n; j++)
      for (k = 0; k < alldfas->v[i]->states.v[j]->accepts.n; k++) {
	p = alldfas->v[i]->states.v[j]->accepts.v[k]->term->term_priority;
	if (highest < p)
	  highest = p;
      }
    for (j = 0; j < alldfas->v[i]->states.n; j++)
      for (k = 0; k < alldfas->v[i]->states.v[j]->accepts.n; k++) {
	p = alldfas->v[i]->states.v[j]->accepts.v[k]->term->term_priority;
	if (p == highest)
	  vec_add(&alldfas->v[i]->scan->accepts,
		  alldfas->v[i]->states.v[j]->accepts.v[k]);
      }
  }
}

static void
nfa_to_scanner(NFAState *n, Scanner *s) {
  DFAState *x = new_DFAState(), *y;
  VecDFAState alldfas;
  uint i, i_alldfas, i_states, i_char;
  VecScanState *scanner = &s->states;
  
  memset(&alldfas, 0, sizeof(alldfas));
  vec_add(&x->states, n);
  nfa_closure(x);
  vec_add(&alldfas, x);
  for (i_alldfas = 0; i_alldfas < alldfas.n; i_alldfas++) {
    x = alldfas.v[i_alldfas];
    for (i_char = 0; i_char < 256; i_char++) {
      y = NULL;
      for (i_states = 0; i_states < x->states.n; i_states++) {
	for (i = 0; i < x->states.v[i_states]->chars[i_char].n; i++) {
	  if (!y)
	    y = new_DFAState();
	  set_add(&y->states, x->states.v[i_states]->chars[i_char].v[i]);
	}
      }
      if (y) {
	set_to_vec(&y->states);
	nfa_closure(y);
	for (i = 0; i < alldfas.n; i++)
	  if (eq_dfa_state(y, alldfas.v[i])) {
            free_DFAState(y);
	    y = alldfas.v[i];
	    goto Lnext;
	  }
	vec_add(&alldfas, y);
      Lnext:
	x->chars[i_char] = y;
      }
    }
  }
  dfa_to_scanner(&alldfas, scanner);
  free_VecDFAState(&alldfas);
}

/* build a NFA for the regular expression */
static int
build_regex_nfa(LexState *ls, uint8 **areg, NFAState *pp, NFAState *nn, Action *trailing) {
  uint8 c, pc, *reg = *areg;
  NFAState *p = pp, *s, *x, *n = nn;
  int reversed, i, has_trailing = 0;
  uint8 mark[256];

  s = p;
  while ((c = *reg++)) {
    switch(c) {
      case '(':
	has_trailing = build_regex_nfa(ls, &reg, s, (x = new_NFAState(ls)), trailing) ||
	  has_trailing;
	p = s;
	s = x;
	break;
      case ')':
	goto Lreturn;
      case '|':
	vec_add(&s->epsilon, nn);
	vec_add(&pp->epsilon, (s = new_NFAState(ls)));
	break;
      case '[':
	if (*reg == '^') {
	  reg++;
	  reversed = 1;
	} else
	  reversed = 0;
	memset(mark, 0, sizeof(mark));
	pc = UCHAR_MAX;
	while ((c = *reg++)) {
	  switch(c) {
	    case ']':
	      goto Lsetdone;
	    case '-':
	      c = *reg++;
	      if (!c)
		goto Lerror;
	      if (c == '\\')
		c = *reg++;
	      if (!c)
		goto Lerror;
	      for (;pc <= c; pc++)
		mark[pc] = 1;
	      break;
	    case '\\':
	      c = *reg++;
	      /* fall through */
	    default:
	      pc = c;
	      mark[c] = 1;
	      break;
	  }
	}
    Lsetdone:
	x = new_NFAState(ls);
	for (i = 1; i < 256; i++)
	  if ((!reversed && mark[i]) || (reversed && !mark[i]))
	    vec_add(&s->chars[i], x);
	p = s;
	s = x;
	break;
      case '?':
	vec_add(&p->epsilon, s);
	break;
      case '*':
	vec_add(&p->epsilon, s);
	vec_add(&s->epsilon, p);
	break;
      case '+':
	vec_add(&s->epsilon, p);
	break;
      case '/':
	vec_add(&s->accepts, trailing);
	has_trailing = 1;
	break;
      case '\\':
	c = *reg++;
	if (!c)	
	  goto Lerror;
	/* fall through */
      default:
	if (!ls->ignore_case || !isalpha(c))
	  vec_add(&s->chars[c], (x = new_NFAState(ls))); 
	else {
	  vec_add(&s->chars[tolower(c)], (x = new_NFAState(ls))); 
	  vec_add(&s->chars[toupper(c)], x);
	}
	p = s;
	s = x;
	break;
    }
  }
 Lreturn:
  vec_add(&s->epsilon, n);
  *areg = reg;
  return has_trailing;
 Lerror:
  d_fail("bad (part of) regex: %s\n", *areg);
  return has_trailing;
}

static void
action_diff(VecAction *a, VecAction *b, VecAction *c) {
  uint bb = 0, cc = 0;
  while (1) {
    if (bb >= b->n)
      break;
  Lagainc:
    if (cc >= c->n) {
      while (bb < b->n)
	vec_add(a, b->v[bb++]);
      break;
    }
  Lagainb:
    if (b->v[bb]->index == c->v[cc]->index) {
      bb++;
      cc++;
      continue;
    }
    if (b->v[bb]->index < c->v[cc]->index) {
      vec_add(a, b->v[bb++]);
      if (bb >= b->n)
	break;
      goto Lagainb;
    }
    cc++;
    goto Lagainc;
  }
}

static void
action_intersect(VecAction *a, VecAction *b, VecAction *c) {
  uint bb = 0, cc = 0;
  while (1) {
    if (bb >= b->n)
      break;
  Lagainc:
    if (cc >= c->n)
      break;
  Lagainb:
    if (b->v[bb]->index == c->v[cc]->index) {
      vec_add(a, b->v[bb++]);
      cc++;
      continue;
    }
    if (b->v[bb]->index < c->v[cc]->index) {
      bb++;
      if (bb >= b->n)
	break;
      goto Lagainb;
    }
    cc++;
    goto Lagainc;
  }
}

static void
compute_liveness(Scanner *scanner) {
  uint i, j, changed = 1;
  ScanState *ss, *sss;
  VecScanState *states = &scanner->states;

  /* basis */
  for (i = 0; i < states->n; i++) {
    ss = states->v[i];
    set_union(&ss->live, &ss->accepts);
  }
  while (changed) {
    changed = 0;
    for (i = 0; i < states->n; i++) {
      ss = states->v[i];
      for (j = 0; j < 256; j++) {
	if ((sss = ss->chars[j])) {
	  if (ss != sss)
	    if (set_union(&ss->live, &sss->live))
	      changed = 1;
	}
      }
    }
  }
  for (i = 0; i < states->n; i++) {
    ss = states->v[i];
    set_to_vec(&ss->live);
    sort_VecAction(&ss->live);
  }
}

static uint32
trans_hash_fn(ScanStateTransition *a, hash_fns_t *fns) {
  uint h = 0, i;

  if (!fns->data[0])
    for (i = 0; i < a->live_diff.n; i++)
      h += 3 * a->live_diff.v[i]->index;
  for (i = 0; i < a->accepts_diff.n; i++)
    h += 3 * a->accepts_diff.v[i]->index;
  return h;
}

static int
trans_cmp_fn(ScanStateTransition *a, ScanStateTransition *b, hash_fns_t *fns) {
  uint i;
  
  if (!fns->data[0])
    if (a->live_diff.n != b->live_diff.n)
      return 1;
  if (a->accepts_diff.n != b->accepts_diff.n)
    return 1;
  if (!fns->data[0])
    for (i = 0; i < a->live_diff.n; i++)
      if (a->live_diff.v[i] != b->live_diff.v[i])
	return 1;
  for (i = 0; i < a->accepts_diff.n; i++)
    if (a->accepts_diff.v[i] != b->accepts_diff.v[i])
      return 1;
  return 0;
}

static hash_fns_t trans_hash_fns = {
  (hash_fn_t)trans_hash_fn,
  (cmp_fn_t)trans_cmp_fn,
  { 0, 0 }
};

static void
build_transitions(LexState *ls, Scanner *s) {
  uint i, j;
  ScanState *ss;
  ScanStateTransition *trans = NULL, *x;
  VecScanState *states = &s->states;

#ifdef LIVE_DIFF_IN_TRANSITIONS 
  trans_hash_fns.data[0] = (void*)0;
#else
  trans_hash_fns.data[0] = (void*)1;
#endif
  for (i = 0; i < states->n; i++) {
    ss = states->v[i];
    for (j = 0; j < 256; j++) {
      if (!trans) {
	trans = MALLOC(sizeof(*trans));
	memset(trans, 0, sizeof(*trans));
      }
      if (ss->chars[j]) {
	action_diff(&trans->live_diff, &ss->live, &ss->chars[j]->live);
	action_intersect(&trans->accepts_diff, &ss->accepts, 
			 &trans->live_diff);
      }
      if ((x = set_add_fn(&s->transitions, trans, &trans_hash_fns)) == trans)
	trans = NULL;
      else {
	vec_free(&trans->live_diff); 
	vec_free(&trans->accepts_diff);
      }
      ss->transition[j] = x;
    }
  }
  if (trans)
    FREE(trans);
  j = 0;
  set_to_vec(&s->transitions);
  for (i = 0; i < s->transitions.n; i++)
    s->transitions.v[i]->index = i;
  ls->transitions += s->transitions.n;
}

static void
compute_transitions(LexState *ls, Scanner *s) {
  compute_liveness(s);
  build_transitions(ls, s);
}

static void
build_state_scanner(Grammar *g, LexState *ls, State *s) {
  NFAState *n, *nn, *nnn;
  Action *a;
  uint8 *c, *reg; 
  uint j, one;

  one = 0;
  n = new_NFAState(ls);
  /* first strings since they can be trivially combined as a tree */
  for (j = 0; j < s->shift_actions.n; j++) {
    a = s->shift_actions.v[j];
    if (a->kind == ACTION_ACCEPT) {
      one = 1;
      if (!n->chars[0].n) 
	vec_add(&n->chars[0], (nnn = new_NFAState(ls)));
      else
	nnn = n->chars[0].v[0];
      vec_add(&nnn->accepts, a);
    } else if (a->kind == ACTION_SHIFT && a->term->kind == TERM_STRING) {
      one = 1;
      nn = n;
      if (!a->term->ignore_case) {
	for (c = (uint8*)a->term->string; *c; c++) {
	  if (!nn->chars[*c].n) 
	    vec_add(&nn->chars[*c], (nnn = new_NFAState(ls)));
	  else
	    nnn = nn->chars[*c].v[0];
	  nn = nnn;
	}
      } else { /* use new states */
	for (c = (uint8*)a->term->string; *c; c++) {
	  if (isalpha(*c)) {
	    vec_add(&nn->chars[toupper(*c)], (nnn = new_NFAState(ls)));
	    vec_add(&nn->chars[tolower(*c)], nnn);
	  } else
	    vec_add(&nn->chars[*c], (nnn = new_NFAState(ls)));
	  nn = nnn;
	}
      }
      vec_add(&nn->accepts, a);
    }
  }
  /* now regexes */
  for (j = 0; j < s->shift_actions.n; j++) {
    a = s->shift_actions.v[j];
    if (a->kind == ACTION_SHIFT && a->term->kind == TERM_REGEX) {
      Action *trailing_context = (Action *)MALLOC(sizeof(Action));
      memcpy(trailing_context, a, sizeof(Action));
      trailing_context->kind = ACTION_SHIFT_TRAILING;
      trailing_context->index = g->action_count++;
      one = 1;
      reg = (uint8*)a->term->string;
      vec_add(&n->epsilon, (nnn = new_NFAState(ls)));
      nn = new_NFAState(ls);
      ls->ignore_case = a->term->ignore_case;
      if (build_regex_nfa(ls, &reg, nnn, nn, trailing_context)) {
	a->term->trailing_context = 1;
	s->trailing_context = 1;
	vec_add(&g->actions, trailing_context);
      } else
	FREE(trailing_context);
      vec_add(&nn->accepts, a);
    }
  }
  if (one) {
    nfa_to_scanner(n, &s->scanner);
    compute_transitions(ls, &s->scanner);
  }
  free_VecNFAState(&ls->allnfas);
  ls->scanners++;
}

static LexState *
new_LexState() {
  LexState *ls = MALLOC(sizeof(LexState));
  memset(ls, 0, sizeof(LexState));
  vec_clear(&ls->allnfas);
  return ls;
}

void 
build_scanners(Grammar *g) {
  uint i, j, k;
  State *s;
  LexState *ls = new_LexState();

  /* detect identical scanners */
  for (i = 0; i < g->states.n; i++) {
    s = g->states.v[i];
    if (s->same_shifts)
      continue;
    for (j = 0; j < i; j++) {
      if (g->states.v[j]->same_shifts)
	continue;
      if (g->states.v[j]->shift_actions.n != s->shift_actions.n)
	continue;
      if (g->states.v[j]->scan_kind != s->scan_kind)
	continue;
      for (k = 0; k < g->states.v[j]->shift_actions.n; k++)
	if (s->shift_actions.v[k]->term != 
	    g->states.v[j]->shift_actions.v[k]->term)
	  break;
      if (k >= g->states.v[j]->shift_actions.n) {
	s->same_shifts = g->states.v[j];
	break;
      }
    }
  }
  /* build scanners */
  for (i = 0; i < g->states.n; i++) {
    s = g->states.v[i];
    if (s->shift_actions.n) {
      if (s->same_shifts)
	s->scanner = s->same_shifts->scanner;
      else 
	build_state_scanner(g, ls, s);
    }
  }
  if (d_verbose_level)
    printf("%d scanners %d transitions\n", ls->scanners, ls->transitions);
  FREE(ls);
}