/tmp/build/foma/foma-0.10.0+g279~a2d32b38/apply.c

Bug Summary

File:	apply.c
Warning:	line 489, column 43 Array access (via field 'flagstates') results in a null pointer dereference
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name apply.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/tmp/build/foma/foma-0.10.0+g279~a2d32b38 -resource-dir /usr/lib/llvm-16/lib/clang/16 -D _GNU_SOURCE -D foma_shared_EXPORTS -I /tmp/build/foma/foma-0.10.0+g279~a2d32b38 -internal-isystem /usr/lib/llvm-16/lib/clang/16/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -Wno-missing-field-initializers -Wno-deprecated -Wno-unused-parameter -std=c18 -fdebug-compilation-dir=/tmp/build/foma/foma-0.10.0+g279~a2d32b38 -ferror-limit 19 -fvisibility=hidden -fgnuc-version=4.2.1 -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/build/foma/scan-build/2024-09-11-155945-2678-1 -x c /tmp/build/foma/foma-0.10.0+g279~a2d32b38/apply.c
1/*   Foma: a finite-state toolkit and library.                                 */
2/*   Copyright © 2008-2021 Mans Hulden                                         */

4/*   This file is part of foma.                                                */

6/*   Licensed under the Apache License, Version 2.0 (the "License");           */
7/*   you may not use this file except in compliance with the License.          */
8/*   You may obtain a copy of the License at                                   */

10/*      http://www.apache.org/licenses/LICENSE-2.0                             */

12/*   Unless required by applicable law or agreed to in writing, software       */
13/*   distributed under the License is distributed on an "AS IS" BASIS,         */
14/*   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  */
15/*   See the License for the specific language governing permissions and       */
16/*   limitations under the License.                                            */

18#include <stdio.h>
19#include <stdlib.h>
20#include <time.h>
21#include <string.h>
22#include <limits.h>
23#include "foma.h"

25#define RANDOM1 1
26#define ENUMERATE2 2
27#define MATCH4 4
28#define UP8 8
29#define DOWN16 16
30#define LOWER32 32
31#define UPPER64 64
32#define SPACE128 128

34#define FAIL0 0
35#define SUCCEED1 1

37#define DEFAULT_OUTSTRING_SIZE4096 4096
38#define DEFAULT_STACK_SIZE128 128

40#define APPLY_BINSEARCH_THRESHOLD10 10

42#define BITMASK(b)(1 << ((b) & 7)) (1 << ((b) & 7))
43#define BITSLOT(b)((b) >> 3) ((b) >> 3)
44#define BITSET(a,b)((a)[((b) >> 3)] |= (1 << ((b) & 7))) ((a)[BITSLOT(b)((b) >> 3)] |= BITMASK(b)(1 << ((b) & 7)))
45#define BITCLEAR(a,b)((a)[((b) >> 3)] &= ~(1 << ((b) & 7))) ((a)[BITSLOT(b)((b) >> 3)] &= ~BITMASK(b)(1 << ((b) & 7)))
46#define BITTEST(a,b)((a)[((b) >> 3)] & (1 << ((b) & 7))) ((a)[BITSLOT(b)((b) >> 3)] & BITMASK(b)(1 << ((b) & 7)))
47#define BITNSLOTS(nb)((nb + 8 - 1) / 8) ((nb + CHAR_BIT8 - 1) / CHAR_BIT8)



51static int apply_append(struct apply_handle *h, int cptr, int sym);
52static char *apply_net(struct apply_handle *h);
53static void apply_create_statemap(struct apply_handle *h,struct fsm *net);
54static void apply_create_sigarray(struct apply_handle *h,struct fsm *net);
55static void apply_create_sigmatch(struct apply_handle *h);
56int apply_match_length(struct apply_handle *h, int symbol);
57static int apply_match_str(struct apply_handle *h,int symbol, int position);
58static void apply_add_flag(struct apply_handle *h,char *name);
59static int apply_check_flag(struct apply_handle *h,int type, char *name, char *value);
60static void apply_clear_flags(struct apply_handle *h);
61void apply_set_iptr(struct apply_handle *h);
62void apply_mark_flagstates(struct apply_handle *h);
63void apply_clear_index(struct apply_handle *h);

65static void apply_stack_clear(struct apply_handle *h);
66static int apply_stack_isempty(struct apply_handle *h);
67static void apply_stack_pop (struct apply_handle *h);
68static void apply_stack_push (struct apply_handle *h, int vmark, char *sflagname, char *sflagvalue, int sflagneg);
69static void apply_force_clear_stack(struct apply_handle *h);


72void apply_set_obey_flags(struct apply_handle *h, int value) {
  h->obey_flags = value;
74}

76void apply_set_show_flags(struct apply_handle *h, int value) {
  h->show_flags = value;
78}

80void apply_set_print_space(struct apply_handle *h, int value) {
  h->print_space = value;
  h->space_symbol = strdup(" ");
83}

85void apply_set_separator(struct apply_handle *h, char *symbol) {
  h->separator = strdup(symbol);
87}

89void apply_set_epsilon(struct apply_handle *h, char *symbol) {
  free(h->epsilon_symbol);
  h->epsilon_symbol = strdup(symbol);
  (h->sigs+EPSILON0)->symbol = h->epsilon_symbol;
  (h->sigs+EPSILON0)->length =  strlen(h->epsilon_symbol);
94}

96void apply_set_space_symbol(struct apply_handle *h, char *space) {
  h->space_symbol = strdup(space);
  h->print_space = 1;
99}

101void apply_set_print_pairs(struct apply_handle *h, int value) {
  h->print_pairs = value;
103}

105static void apply_force_clear_stack(struct apply_handle *h) {
  /* Make sure stack is empty and marks reset */
  if (!apply_stack_isempty(h)) {
*(h->marks+(h->gstates+h->ptr)->state_no) = 0;
while (!apply_stack_isempty(h)) {
   apply_stack_pop(h);
   *(h->marks+(h->gstates+h->ptr)->state_no) = 0;
}
h->iterator = 0;
h->iterate_old = 0;
apply_stack_clear(h);
  }
117}

119char *apply_enumerate(struct apply_handle *h) {

  char *result = NULL((void*)0);

  if (h->last_net == NULL((void*)0) || h->last_net->finalcount == 0) {
return (NULL((void*)0));
  }
  h->binsearch = 0;
  if (h->iterator == 0) {
      h->iterate_old = 0;
apply_force_clear_stack(h);
      result = apply_net(h);
if ((h->mode & RANDOM1) != RANDOM1)
 (h->iterator)++;
  } else {
      h->iterate_old = 1;
      result = apply_net(h);
  }
  return(result);
138}

140char *apply_words(struct apply_handle *h) {
  h->mode = DOWN16 + ENUMERATE2 + LOWER32 + UPPER64;
  return(apply_enumerate(h));
143}

145char *apply_upper_words(struct apply_handle *h) {
  h->mode = DOWN16 + ENUMERATE2 + UPPER64;
  return(apply_enumerate(h));
148}

150char *apply_lower_words(struct apply_handle *h) {
  h->mode = DOWN16 + ENUMERATE2 + LOWER32;
  return(apply_enumerate(h));
153}

155char *apply_random_words(struct apply_handle *h) {
  apply_clear_flags(h);
  h->mode = DOWN16 + ENUMERATE2 + LOWER32 + UPPER64 + RANDOM1;
  return(apply_enumerate(h));
159}

161char *apply_random_lower(struct apply_handle *h) {
  apply_clear_flags(h);
  h->mode = DOWN16 + ENUMERATE2 + LOWER32 + RANDOM1;
  return(apply_enumerate(h));
165}

167char *apply_random_upper(struct apply_handle *h) {
  apply_clear_flags(h);
  h->mode = DOWN16 + ENUMERATE2 + UPPER64 + RANDOM1;
  return(apply_enumerate(h));
171}

173/* Frees memory associated with applies */
174void apply_clear(struct apply_handle *h) {
  struct sigma_trie_arrays *sta, *stap;
  for (sta = h->sigma_trie_arrays; sta != NULL((void*)0); ) {
stap = sta;
free(sta->arr);
sta = sta->next;
free(stap);
  }
  h->sigma_trie_arrays = NULL((void*)0);
  if (h->statemap != NULL((void*)0)) {
      free(h->statemap);
      h->statemap = NULL((void*)0);
  }
  if (h->numlines != NULL((void*)0)) {
      free(h->numlines);
      h->numlines = NULL((void*)0);
  }
  if (h->marks != NULL((void*)0)) {
      free(h->marks);
      h->marks = NULL((void*)0);
  }
  if (h->searchstack != NULL((void*)0)) {
      free(h->searchstack);
      h->searchstack = NULL((void*)0);
  }
  if (h->sigs != NULL((void*)0)) {
      free(h->sigs);
      h->sigs = NULL((void*)0);
  }
  if (h->flag_lookup != NULL((void*)0)) {
      free(h->flag_lookup);
      h->flag_lookup = NULL((void*)0);
  }
  if (h->sigmatch_array != NULL((void*)0)) {
free(h->sigmatch_array);
h->sigmatch_array = NULL((void*)0);
  }
  if (h->flagstates != NULL((void*)0)) {
free(h->flagstates);
h->flagstates = NULL((void*)0);
  }
  apply_clear_index(h);
  h->last_net = NULL((void*)0);
  h->iterator = 0;
  free(h->outstring);
  free(h->separator);
  free(h->epsilon_symbol);
  free(h);
222}

224char *apply_updown(struct apply_handle *h, char *word) {

  char *result = NULL((void*)0);

  if (h->last_net == NULL((void*)0) || h->last_net->finalcount == 0)
      return (NULL((void*)0));

  if (word == NULL((void*)0)) {
      h->iterate_old = 1;
      result = apply_net(h);
  }
  else if (word != NULL((void*)0)) {
      h->iterate_old = 0;
      h->instring = word;
      apply_create_sigmatch(h);

/* Remove old marks if necessary TODO: only pop marks */
apply_force_clear_stack(h);
      result = apply_net(h);
  }
  return(result);
245}

247char *apply_down(struct apply_handle *h, char *word) {

  h->mode = DOWN16;
  if (h->index_in) {
h->indexed = 1;
  } else {
h->indexed = 0;
  }
  h->binsearch = (h->last_net->arcs_sorted_in == 1) ? 1 : 0;
  return(apply_updown(h, word));
257}

259char *apply_up(struct apply_handle *h, char *word) {

  h->mode = UP8;
  if (h->index_out) {
h->indexed = 1;
  } else {
h->indexed = 0;
  }
  h->binsearch = (h->last_net->arcs_sorted_out == 1) ? 1 : 0;
  return(apply_updown(h, word));
269}

271struct apply_handle *apply_init(struct fsm *net) {
  struct apply_handle *h;

  srand((unsigned int) time(NULL((void*)0)));
  h = calloc(1,sizeof(struct apply_handle));
  /* Init */

  h->iterate_old = 0;
  h->iterator = 0;
  h->instring = NULL((void*)0);
  h->flag_list = NULL((void*)0);
  h->flag_lookup = NULL((void*)0);
  h->obey_flags = 1;
  h->show_flags = 0;
  h->print_space = 0;
  h->print_pairs = 0;
  h->separator = strdup(":");
  h->epsilon_symbol = strdup("0");
  h->last_net = net;
  h->outstring = malloc(sizeof(char)*DEFAULT_OUTSTRING_SIZE4096);
  h->outstringtop = DEFAULT_OUTSTRING_SIZE4096;
  *(h->outstring) = '\0';
  h->gstates = net->states;
  h->gsigma = net->sigma;
  h->printcount = 1;
  apply_create_statemap(h, net);
  h->searchstack = malloc(sizeof(struct searchstack) * DEFAULT_STACK_SIZE128);
  h->apply_stack_top = DEFAULT_STACK_SIZE128;
  apply_stack_clear(h);
  apply_create_sigarray(h, net);
  return(h);
302}

304int apply_stack_isempty (struct apply_handle *h) {
  if (h->apply_stack_ptr == 0) {
return 1;
  }
  return 0;
309}

311void apply_stack_clear (struct apply_handle *h) {
  h->apply_stack_ptr = 0;
313}

315void apply_stack_pop (struct apply_handle *h) {
  struct flag_list *flist;
  struct searchstack *ss;
  (h->apply_stack_ptr)--;
  ss = h->searchstack+h->apply_stack_ptr;

  h->iptr =  ss->iptr;
  h->ptr  =  ss->offset;
  h->ipos =  ss->ipos;
  h->opos =  ss->opos;
  h->state_has_index = ss->state_has_index;
  /* Restore mark */
  *(h->marks+(h->gstates+h->ptr)->state_no) = ss->visitmark;

  if (h->has_flags && ss->flagname != NULL((void*)0)) {
/* Restore flag */
for (flist = h->flag_list; flist != NULL((void*)0); flist = flist->next) {
   if (strcmp(flist->name, ss->flagname) == 0) {
break;
   }
}
if (flist == NULL((void*)0))
   perror("***Nothing to pop\n");
flist->value = ss->flagvalue;
flist->neg = ss->flagneg;
  }
341}

343static void apply_stack_push (struct apply_handle *h, int vmark, char *sflagname, char *sflagvalue, int sflagneg) {
  struct searchstack *ss;
  if (h->apply_stack_ptr == h->apply_stack_top) {
h->searchstack = realloc(h->searchstack, sizeof(struct searchstack)* ((h->apply_stack_top)*2));
if (h->searchstack == NULL((void*)0)) {
 perror("Apply stack full!!!\n");
 exit(0);
}
h->apply_stack_top *= 2;
  }
  ss = h->searchstack+h->apply_stack_ptr;
  ss->offset     = h->curr_ptr;
  ss->ipos       = h->ipos;
  ss->opos       = h->opos;
  ss->visitmark  = vmark;
  ss->iptr       = h->iptr;
  ss->state_has_index = h->state_has_index;
  if (h->has_flags) {
ss->flagname   = sflagname;
ss->flagvalue  = sflagvalue;
ss->flagneg    = sflagneg;
  }
  (h->apply_stack_ptr)++;
366}

368void apply_reset_enumerator(struct apply_handle *h) {
  int statecount, i;
  statecount = h->last_net->statecount;
  for (i=0; i < statecount; i++) {
*(h->marks+i) = 0;
  }
  h->iterator = 0;
  h->iterate_old = 0;
376}

378void apply_clear_index_list(struct apply_handle *h, struct apply_state_index **index) {
  int i, j, statecount;
  struct apply_state_index *iptr, *iptr_tmp, *iptr_zero;
  if (index == NULL((void*)0))
return;
  statecount = h->last_net->statecount;
  for (i = 0; i < statecount; i++) {
iptr = *(index+i);
if (iptr == NULL((void*)0)) {
   continue;
}
iptr_zero = *(index+i);
for (j = h->sigma_size - 1 ; j >= 0; j--) { /* Make sure to not free the list in EPSILON    */
   iptr = *(index+i) + j;                  /* as the other states lists' tails point to it */
   for (iptr = iptr->next ; iptr != NULL((void*)0) && iptr != iptr_zero; iptr = iptr_tmp) {
iptr_tmp = iptr->next;
free(iptr);
   }
}
free(*(index+i));
  }
399}

401void apply_clear_index(struct apply_handle *h) {
  if (h->index_in) {
apply_clear_index_list(h, h->index_in);
free(h->index_in);
h->index_in = NULL((void*)0);
  }
  if (h->index_out) {
apply_clear_index_list(h, h->index_out);
free(h->index_out);
h->index_out = NULL((void*)0);
  }
412}

414void apply_index(struct apply_handle *h, int inout, int densitycutoff, int mem_limit, int flags_only) {
  struct fsm_state *fsm;
  unsigned int cnt = 0;
  int i, j, maxtrans, numtrans, laststate, sym;
  fsm = h->gstates;

  struct apply_state_index **indexptr, *iptr, *tempiptr;

  struct pre_index {
int state_no;
struct pre_index *next;
  } *pre_index, *tp, *tpp;
  if (flags_only && !h->has_flags) {
1
Assuming 'flags_only' is not equal to 0→
2
←
Assuming field 'has_flags' is not equal to 0→
3
←
Taking false branch→
return;
  }
  /* get numtrans */
  for (i=0, laststate = 0, maxtrans = 0, numtrans = 0; (fsm+i)->state_no != -1; i++) {
4
←
Assuming the condition is true→
5
←
Loop condition is true.  Entering loop body→
11
←
Assuming the condition is false→
12
←
Loop condition is false. Execution continues on line 441→
if ((fsm+i)->state_no != laststate) {
6
←
Assuming 'laststate' is not equal to field 'state_no'→
   maxtrans = numtrans7.1
'numtrans' is <= 'maxtrans'
 > maxtrans ? numtrans : maxtrans;
7
←
Taking true branch→
8
←
'?' condition is false→
   numtrans = 0;
}
if ((fsm+i)->target != -1) {
9
←
Assuming the condition is false→
10
←
Taking false branch→
   numtrans++;
}
laststate = (fsm+i)->state_no;
  }

  pre_index = calloc(maxtrans+1, sizeof(struct pre_index));
  for (i = 0; i <= maxtrans; i++) {
13
←
Loop condition is true.  Entering loop body→
14
←
Loop condition is false. Execution continues on line 450→
(pre_index+i)->state_no = -1;
  }

  /* We create an array of states, indexed by how many transitions they have */
  /* so that later, we can traverse them in order densest first, in case we  */
  /* only want to index to some predefined maximum memory usage.             */

  for (i = 0, laststate = 0, maxtrans = 0, numtrans = 0; (fsm+i)->state_no != -1; i++) {
15
←
Loop condition is true.  Entering loop body→
20
←
Loop condition is false. Execution continues on line 468→
if ((fsm+i)->state_no != laststate15.1
'laststate' is not equal to field 'state_no'
) {
16
←
Taking true branch→
   if ((pre_index+numtrans)->state_no == -1) {
17
←
Taking true branch→
(pre_index+numtrans)->state_no = laststate;
   } else {
tp = calloc(1, sizeof(struct pre_index));
tp->state_no = laststate;
tp->next = (pre_index+numtrans)->next;
(pre_index+numtrans)->next = tp;
   }
   maxtrans = numtrans17.1
'numtrans' is <= 'maxtrans'
 > maxtrans ? numtrans : maxtrans;
18
←
'?' condition is false→
   numtrans = 0;
}
if ((fsm+i)->target != -1) {
19
←
Taking false branch→
   numtrans++;
}
laststate = (fsm+i)->state_no;
  }
  indexptr = NULL((void*)0);
  cnt += round_up_to_power_of_two(h->last_net->statecount*sizeof(struct apply_state_index *));

  if (cnt > mem_limit) {
21
←
Assuming 'cnt' is <= 'mem_limit'→
22
←
Taking false branch→
cnt -= round_up_to_power_of_two(h->last_net->statecount*sizeof(struct apply_state_index *));
goto memlimitnoindex;
  }

  indexptr = calloc(h->last_net->statecount, sizeof(struct apply_state_index *));

  if (h->has_flags22.1
Field 'has_flags' is not equal to 0
 && flags_only22.2
'flags_only' is not equal to 0
) {
23
←
Taking true branch→
/* Mark states that have flags */
if (!(h->flagstates)) {
24
←
Assuming field 'flagstates' is null→
25
←
Taking true branch→
   apply_mark_flagstates(h);
}
  }

  for (i = maxtrans; i >= 0; i--) {
26
←
Loop condition is true.  Entering loop body→
for (tp = pre_index+i; tp26.1
'tp' is not equal to NULL
 != NULL((void*)0); tp = tp->next) {
27
←
Loop condition is true.  Entering loop body→
   if (tp->state_no27.1
Field 'state_no' is >= 0
 >= 0) {
28
←
Taking true branch→
if (i < densitycutoff) {
29
←
Assuming 'i' is < 'densitycutoff'→
    if (!(h->has_flags29.1
Field 'has_flags' is not equal to 0
 && flags_only29.2
'flags_only' is not equal to 0
 && BITTEST(h->flagstates, tp->state_no)((h->flagstates)[((tp->state_no) >> 3)] & (1 <<
 ((tp->state_no) & 7))))) {
30
←
Array access (via field 'flagstates') results in a null pointer dereference
	continue;
    }
}
cnt += round_up_to_power_of_two(h->sigma_size*sizeof(struct apply_state_index));
if (cnt > mem_limit) {
    cnt -= round_up_to_power_of_two(h->sigma_size*sizeof(struct apply_state_index));
    goto memlimit;
}
*(indexptr + tp->state_no) = malloc(h->sigma_size*sizeof(struct apply_state_index));

/* We make the tail of all index linked lists point to the index  */
/* for EPSILON, so that we automatically when EPSILON transitions */
/* also when traversing an index.                                 */

for (j = 0; j < h->sigma_size; j++) {
    (*(indexptr + tp->state_no) + j)->fsmptr = -1;
    if (j == EPSILON0)
	(*(indexptr + tp->state_no) + j)->next = NULL((void*)0);
    else
	(*(indexptr + tp->state_no) + j)->next = (*(indexptr + tp->state_no)); /* all tails point to epsilon */
}
   }
}
  }

memlimit:

  for (i=0; (fsm+i)->state_no != -1; i++) {
iptr = *(indexptr + (fsm+i)->state_no);
if (iptr == NULL((void*)0) || (fsm+i)->target == -1) {
   continue;
}
sym = inout == APPLY_INDEX_INPUT1 ? (fsm+i)->in : (fsm+i)->out;

if (h->has_flags && (h->flag_lookup+sym)->type) {
   sym = EPSILON0;
}
if (sym == UNKNOWN1) {  /* We make the index of UNKNOWN point to IDENTITY */
   sym = IDENTITY2;    /* since these are really the same symbol         */
}
if ((iptr+sym)->fsmptr == -1) {
   (iptr+sym)->fsmptr = i;
} else {
   cnt += round_up_to_power_of_two(sizeof(struct apply_state_index));
   tempiptr = calloc(1, sizeof(struct apply_state_index));

   tempiptr->next = (iptr+sym)->next;
   tempiptr->fsmptr =  i;
   (iptr+sym)->next = tempiptr;
}
  }

  /* Free preindex */

memlimitnoindex:

  for (i = maxtrans; i >= 0; i--) {
for (tp = (pre_index+i)->next; tp != NULL((void*)0); tp = tpp) {
   tpp = tp->next;
   free(tp);
}
  }
  free(pre_index);

  if (inout == APPLY_INDEX_INPUT1) {
h->index_in = indexptr;
  } else {
h->index_out = indexptr;
  }
559}

561int apply_binarysearch(struct apply_handle *h) {
  int thisstate, nextsym, seeksym, thisptr, lastptr, midptr;

  thisptr = h->curr_ptr = h->ptr;
  nextsym  = (((h->mode) & DOWN16) == DOWN16) ? (h->gstates+h->curr_ptr)->in  : (h->gstates+h->curr_ptr)->out;
  if (nextsym == EPSILON0)
return 1;
  if (nextsym == -1)
return 0;
  if (h->ipos >= h->current_instring_length) {
return 0;
  }
  seeksym = (h->sigmatch_array+h->ipos)->signumber;
  if (seeksym == nextsym || (nextsym == UNKNOWN1 && seeksym == IDENTITY2))
return 1;

  thisstate = (h->gstates+thisptr)->state_no;
  lastptr = *(h->statemap+thisstate)+*(h->numlines+thisstate)-1;
  thisptr++;

  if (seeksym == IDENTITY2 || lastptr - thisptr < APPLY_BINSEARCH_THRESHOLD10) {
for ( ; thisptr <= lastptr; thisptr++) {
   nextsym = (((h->mode) & DOWN16) == DOWN16) ? (h->gstates+thisptr)->in : (h->gstates+thisptr)->out;
   if ((nextsym == seeksym) || (nextsym == UNKNOWN1 && seeksym == IDENTITY2)) {
h->curr_ptr = thisptr;
return 1;
   }
   if (nextsym > seeksym || nextsym == -1) {
return 0;
   }
}
return 0;
  }

  for (;;)  {
if (thisptr > lastptr) { return 0; }
midptr = (thisptr+lastptr)/2;
nextsym = (((h->mode) & DOWN16) == DOWN16) ? (h->gstates+midptr)->in : (h->gstates+midptr)->out;
if (seeksym < nextsym) {
   lastptr = midptr - 1;
   continue;
} else if (seeksym > nextsym) {
   thisptr = midptr + 1;
   continue;
} else {

   while (((((h->mode) & DOWN16) == DOWN16) ? (h->gstates+(midptr-1))->in : (h->gstates+(midptr-1))->out) == seeksym) {
midptr--; /* Find first match in case of ties */
   }
   h->curr_ptr = midptr;
   return 1;
}
  }
614}

616int apply_follow_next_arc(struct apply_handle *h) {
  char *fname, *fvalue;
  int eatupi, eatupo, symin, symout, fneg;
  int vcount, marksource, marktarget;

  /* Here we follow three possible search strategies:        */
  /* (1) if the state in question has an index, we use that  */
  /* (2) if the state is binary searchable, we use that      */
  /* (3) otherwise we traverse arc-by-arc                    */
  /*     Condition (2) needs arcs to be sorted in the proper */
  /*     direction, and requires that the state be flag-free */
  /*     For those states that aren't flag-free, (3) is used */

  if (h->state_has_index) {
for ( ; h->iptr != NULL((void*)0) && h->iptr->fsmptr != -1; ) {

   h->ptr = h->curr_ptr = h->iptr->fsmptr;
   if (((h->mode) & DOWN16) == DOWN16) {
symin = (h->gstates+h->curr_ptr)->in;
symout = (h->gstates+h->curr_ptr)->out;
   } else {
symin = (h->gstates+h->curr_ptr)->out;
symout = (h->gstates+h->curr_ptr)->in;
   }

   marksource = *(h->marks+(h->gstates+h->ptr)->state_no);
   marktarget = *(h->marks+(h->gstates+(*(h->statemap+(h->gstates+h->curr_ptr)->target)))->state_no);
   eatupi = apply_match_length(h, symin);
   if (!(eatupi == -1 || -1-(h->ipos)-eatupi == marktarget)) {     /* input 2x EPSILON loop check */
if ((eatupi = apply_match_str(h, symin, h->ipos)) != -1) {
    eatupo = apply_append(h, h->curr_ptr, symout);
    if (h->obey_flags && h->has_flags && ((h->flag_lookup+symin)->type & (FLAG_UNIFY1|FLAG_CLEAR2|FLAG_POSITIVE16|FLAG_NEGATIVE8))) {
	fname = (h->flag_lookup+symin)->name;
	fvalue = h->oldflagvalue;
	fneg = h->oldflagneg;
    } else {
	fname = fvalue = NULL((void*)0);
	fneg = 0;
    }
    /* Push old position */
    apply_stack_push(h, marksource, fname, fvalue, fneg);
    h->ptr = *(h->statemap+(h->gstates+h->curr_ptr)->target);
    h->ipos += eatupi;
    h->opos += eatupo;
    apply_set_iptr(h);
    return 1;
}
   }
   h->iptr = h->iptr->next;
}
return 0;
  } else if ((h->binsearch && !(h->has_flags)) || (h->binsearch && !(BITTEST(h->flagstates, (h->gstates+h->ptr)->state_no)((h->flagstates)[(((h->gstates+h->ptr)->state_no)
 >> 3)] & (1 << (((h->gstates+h->ptr)->
state_no) & 7)))))) {
for (;;) {
   if (apply_binarysearch(h)) {
if (((h->mode) & DOWN16) == DOWN16) {
    symin = (h->gstates+h->curr_ptr)->in;
    symout = (h->gstates+h->curr_ptr)->out;
} else {
    symin = (h->gstates+h->curr_ptr)->out;
    symout = (h->gstates+h->curr_ptr)->in;
}

marksource = *(h->marks+(h->gstates+h->ptr)->state_no);
marktarget = *(h->marks+(h->gstates+(*(h->statemap+(h->gstates+h->curr_ptr)->target)))->state_no);

eatupi = apply_match_length(h, symin);
if (eatupi != -1 && -1-(h->ipos)-eatupi != marktarget) {
    if ((eatupi = apply_match_str(h, symin, h->ipos)) != -1) {
	eatupo = apply_append(h, h->curr_ptr, symout);

	/* Push old position */
	apply_stack_push(h, marksource, NULL((void*)0), NULL((void*)0), 0);

	/* Follow arc */
	h->ptr = *(h->statemap+(h->gstates+h->curr_ptr)->target);
	h->ipos += eatupi;
	h->opos += eatupo;
	apply_set_iptr(h);
	return 1;
    }
}
if ((h->gstates+h->curr_ptr)->state_no == (h->gstates+h->curr_ptr+1)->state_no) {
    h->curr_ptr++;
    h->ptr = h->curr_ptr;
    if ((h->gstates+h->curr_ptr)-> target == -1) {
	return 0;
    }
    continue;
}
   }
   return 0;
}
  } else {
for (h->curr_ptr = h->ptr; (h->gstates+h->curr_ptr)->state_no == (h->gstates+h->ptr)->state_no && (h->gstates+h->curr_ptr)-> in != -1; (h->curr_ptr)++) {

   /* Select one random arc to follow out of all outgoing arcs */
   if ((h->mode & RANDOM1) == RANDOM1) {
vcount = 0;
for (h->curr_ptr = h->ptr;  (h->gstates+h->curr_ptr)->state_no == (h->gstates+h->ptr)->state_no && (h->gstates+h->curr_ptr)-> in != -1; (h->curr_ptr)++) {
    vcount++;
}
if (vcount > 0) {
    h->curr_ptr = h->ptr + (rand() % vcount);
} else {
    h->curr_ptr = h->ptr;
}
   }

   if (((h->mode) & DOWN16) == DOWN16) {
symin = (h->gstates+h->curr_ptr)->in;
symout = (h->gstates+h->curr_ptr)->out;
   } else {
symin = (h->gstates+h->curr_ptr)->out;
symout = (h->gstates+h->curr_ptr)->in;
   }

   marksource = *(h->marks+(h->gstates+h->ptr)->state_no);
   marktarget = *(h->marks+(h->gstates+(*(h->statemap+(h->gstates+h->curr_ptr)->target)))->state_no);

   eatupi = apply_match_length(h, symin);

   if (eatupi == -1 || -1-(h->ipos)-eatupi == marktarget) { continue; } /* loop check */
   if ((eatupi = apply_match_str(h, symin, h->ipos)) != -1) {
eatupo = apply_append(h, h->curr_ptr, symout);
if (h->obey_flags && h->has_flags && ((h->flag_lookup+symin)->type & (FLAG_UNIFY1|FLAG_CLEAR2|FLAG_POSITIVE16|FLAG_NEGATIVE8))) {

    fname = (h->flag_lookup+symin)->name;
    fvalue = h->oldflagvalue;
    fneg = h->oldflagneg;
} else {
    fname = fvalue = NULL((void*)0);
    fneg = 0;
}

/* Push old position */
apply_stack_push(h, marksource, fname, fvalue, fneg);

/* Follow arc */
h->ptr = *(h->statemap+(h->gstates+h->curr_ptr)->target);
h->ipos += eatupi;
h->opos += eatupo;
apply_set_iptr(h);
return(1);
   }
}
return(0);
  }
763}

765char *apply_return_string(struct apply_handle *h) {
  /* Stick a 0 to endpos to avoid getting old accumulated gunk strings printed */
  *(h->outstring+h->opos) = '\0';
  if (((h->mode) & RANDOM1) == RANDOM1) {
/* To end or not to end */
if (!(rand() % 2)) {
   apply_stack_clear(h);
   h->iterator = 0;
   h->iterate_old = 0;
   return(h->outstring);
}
  } else {
return(h->outstring);
  }
  return(NULL((void*)0));
780}

782void apply_mark_state(struct apply_handle *h) {

  /* This controls the how epsilon-loops are traversed.  Such loops can    */
  /* only be followed once to reach a state already visited in the DFS.    */
  /* This requires that we store the number of input symbols consumed      */
  /* whenever we enter a new state.  If we enter the same state twice      */
  /* with the same number of input symbols consumed, we abandon the search */
  /* for that branch. Flags are epsilons from this point of view.          */
  /* The encoding of h->marks is:                                          */
  /* 0 = unseen, +ipos = seen at ipos, -ipos = seen second time at ipos    */

  if ((h->mode & RANDOM1) != RANDOM1) {
if (*(h->marks+(h->gstates+h->ptr)->state_no) == h->ipos+1) {
   *(h->marks+(h->gstates+h->ptr)->state_no) = -(h->ipos+1);
} else {
   *(h->marks+(h->gstates+h->ptr)->state_no) = h->ipos+1;
}
  }
800}

802void apply_skip_this_arc(struct apply_handle *h) {
  /* If we have index ptr */
  if (h->iptr) {
h->ptr = h->iptr->fsmptr;
h->iptr = h->iptr->next;
/* Otherwise */
  } else {
(h->ptr)++;
  }
811}

813int apply_at_last_arc(struct apply_handle *h) {
  int seeksym, nextsym;
  if (h->state_has_index) {
if (h->iptr->next == NULL((void*)0) || h->iptr->next->fsmptr == -1) {
   return 1;
}
  } else {
if  ((h->binsearch && !(h->has_flags)) || (h->binsearch && !(BITTEST(h->flagstates, (h->gstates+h->ptr)->state_no)((h->flagstates)[(((h->gstates+h->ptr)->state_no)
 >> 3)] & (1 << (((h->gstates+h->ptr)->
state_no) & 7)))))) {
   if ((h->gstates+h->ptr)->state_no != (h->gstates+h->ptr+1)->state_no) {
return 1;
   }
   seeksym = (h->sigmatch_array+h->ipos)->signumber;
   nextsym  = (((h->mode) & DOWN16) == DOWN16) ? (h->gstates+h->ptr)->in  : (h->gstates+h->ptr)->out;
   if (nextsym == -1 || seeksym < nextsym) {
return 1;
   }
} else {
   if ((h->gstates+h->ptr)->state_no != (h->gstates+h->ptr+1)->state_no) {
return 1;
   }
}
  }
  return 0;
836}

838/* map h->ptr (line pointer) to h->iptr (index pointer) */
839void apply_set_iptr(struct apply_handle *h) {
  struct apply_state_index **idx, *sidx;
  int stateno, seeksym;
  /* Check if state has index */
  if ((idx = ((h->mode) & DOWN16) == DOWN16 ? (h->index_in) : (h->index_out)) == NULL((void*)0)) {
return;
  }

  h->iptr = NULL((void*)0);
  h->state_has_index = 0;
  stateno = (h->gstates+h->ptr)->state_no;
  if (stateno < 0) {
return;
  }

  sidx = *(idx + stateno);
  if (sidx == NULL((void*)0)) { return; }
  seeksym = (h->sigmatch_array+h->ipos)->signumber;
  h->state_has_index = 1;
  sidx = sidx + seeksym;
  if (sidx->fsmptr == -1) {
if (sidx->next == NULL((void*)0)) {
   return;
} else {
   sidx = sidx->next;
}
  }
  h->iptr = sidx;
  if (sidx->fsmptr == -1) {
h->iptr = NULL((void*)0);
  }
  h->state_has_index = 1;
871}

873char *apply_net(struct apply_handle *h) {

875/*     We perform a basic DFS on the graph, with two minor complications:       */

877/*     1. We keep a mark for each state which indicates how many input symbols  */
878/*        we had consumed the last time we entered that state on the current    */
879/*        "run."  If we reach a state seen twice without consuming input, we    */
880/*        terminate that branch of the search.                                  */
881/*        As we pop a position, we also unmark the state we came from.          */

883/*     2. If the graph has flags, we push the previous flag value when          */
884/*        traversing a flag-modifying arc (P,U,N, or C).  This is because a     */
885/*        flag may have been set during the previous "run" and may not apply.   */
886/*        Since we're doing a DFS, we can be sure to return to the previous     */
887/*        global flag state by just remembering that last flag change.          */

889/*     3. The whole system needs to work as an iterator, meaning we need to     */
890/*        store the global state of the search so we can resume it later to     */
891/*        to yield more possible output words with the same input string.       */

  char *returnstring;

  if (h->iterate_old == 1) {     /* If called with NULL as the input word, this will be set */
      goto resume;
  }

  h->iptr = NULL((void*)0); h->ptr = 0; h->ipos = 0; h->opos = 0;
  apply_set_iptr(h);

  apply_stack_clear(h);

  if (h->has_flags) {
apply_clear_flags(h);
  }

  /* "The use of four-letter words like goto can occasionally be justified */
  /*  even in the best of company." Knuth (1974).                          */

  goto L2;

  while(!apply_stack_isempty(h)) {
apply_stack_pop(h);
/* If last line was popped */
if (apply_at_last_arc(h)) {
   *(h->marks+(h->gstates+h->ptr)->state_no) = 0; /* Unmark   */
   continue;                                      /* pop next */
}
apply_skip_this_arc(h);                            /* skip old pushed arc */
  L1:
if (!apply_follow_next_arc(h)) {
   *(h->marks+(h->gstates+h->ptr)->state_no) = 0; /* Unmark   */
   continue;                                      /* pop next */
}
  L2:
/* Print accumulated string upon entry to state */
if ((h->gstates+h->ptr)->final_state == 1 && (h->ipos == h->current_instring_length || ((h->mode) & ENUMERATE2) == ENUMERATE2)) {
   if ((returnstring = (apply_return_string(h))) != NULL((void*)0)) {
return(returnstring);
   }
}

  resume:
     	apply_mark_state(h);  /* Mark upon arrival to new state */
goto L1;
  }
  if ((h->mode & RANDOM1) == RANDOM1) {
        apply_stack_clear(h);
        h->iterator = 0;
        h->iterate_old = 0;
        return(h->outstring);
  }
  apply_stack_clear(h);
  return NULL((void*)0);
946}

948int apply_append(struct apply_handle *h, int cptr, int sym) {

  char *astring, *bstring, *pstring;
  int symin, symout, len, alen, blen, idlen;

  symin = (h->gstates+cptr)->in;
  symout = (h->gstates+cptr)->out;
  astring = ((h->sigs)+symin)->symbol;
  alen =  ((h->sigs)+symin)->length;
  bstring = ((h->sigs)+symout)->symbol;
  blen =  ((h->sigs)+symout)->length;

  while (alen + blen + h->opos + 2 + strlen(h->separator) >= h->outstringtop) {
//    while (alen + blen + h->opos + 3 >= h->outstringtop) {
h->outstring = realloc(h->outstring, sizeof(char) * ((h->outstringtop) * 2));
(h->outstringtop) *= 2;
  }

  if ((h->has_flags) && !h->show_flags && (h->flag_lookup+symin)->type) {
astring = ""; alen = 0;
  }
  if (h->has_flags && !h->show_flags && (h->flag_lookup+symout)->type) {
bstring = ""; blen = 0;
  }
  if (((h->mode) & ENUMERATE2) == ENUMERATE2) {
/* Print both sides separated by colon */
/* if we're printing "words" */
if (((h->mode) & (UPPER64 | LOWER32)) == (UPPER64|LOWER32)) {

   if (astring == bstring) {
strcpy(h->outstring+h->opos, astring);
len = alen;
   } else {
strcpy(h->outstring+h->opos, astring);
//		strcpy(h->outstring+h->opos+alen,":");
strcpy(h->outstring+h->opos+alen,h->separator);
//strcpy(h->outstring+h->opos+alen+1,bstring);
strcpy(h->outstring+h->opos+alen+strlen(h->separator),bstring);
//		len = alen+blen+1;
len = alen+blen+strlen(h->separator);
   }
}

/* Print one side only */
if (((h->mode) & (UPPER64|LOWER32)) != (UPPER64|LOWER32)) {

   if (symin == EPSILON0) {
astring = ""; alen = 0;
   }
   if (symout == EPSILON0) {
bstring = ""; blen = 0;
   }
   if (((h->mode) & (UPPER64|LOWER32)) == UPPER64) {
pstring = astring;
len = alen;
   } else {
pstring = bstring;
len = blen;
   }
   //strcpy(h->outstring+h->opos, pstring);
   memcpy(h->outstring+h->opos, pstring, len);
}
  }
  if (((h->mode) & ENUMERATE2) != ENUMERATE2) {
/* Print pairs is ON and symbols are different */
if (h->print_pairs && (symin != symout)) {

   if (symin == UNKNOWN1 && ((h->mode) & DOWN16) == DOWN16)
strncpy(astring, h->instring+h->ipos, 1);
   if (symout == UNKNOWN1 && ((h->mode) & UP8) == UP8)
strncpy(bstring, h->instring+h->ipos, 1);
   strcpy(h->outstring+h->opos, "<");
   strcpy(h->outstring+h->opos+1, astring);
   //strcpy(h->outstring+h->opos+alen+1,":");
   strcpy(h->outstring+h->opos+alen+1,h->separator);
   //strcpy(h->outstring+h->opos+alen+2,bstring);
   strcpy(h->outstring+h->opos+alen+1+strlen(h->separator), bstring);
   //strcpy(h->outstring+h->opos+alen+blen+2,">");
   strcpy(h->outstring+h->opos+alen+blen+1+strlen(h->separator),">");
   //len = alen+blen+3;
   len = alen+blen+2+strlen(h->separator);
}

else if (sym == IDENTITY2) {
   /* Apply up/down */
   //idlen = utf8skip(h->instring+h->ipos)+1;
   idlen = (h->sigmatch_array+h->ipos)->consumes; // here
   strncpy(h->outstring+h->opos, h->instring+h->ipos, idlen);
   strncpy(h->outstring+h->opos+idlen,"", 1);
   len = idlen;
} else if (sym == EPSILON0) {
   return(0);
} else {
   if (((h->mode) & DOWN16) == DOWN16) {
pstring = bstring;
len = blen;
   } else {
pstring = astring;
len = alen;
   }
   memcpy(h->outstring+h->opos, pstring, len);
}
  }
  if (h->print_space && len > 0) {
strcpy(h->outstring+h->opos+len, h->space_symbol);
len++;
  }
  return(len);
1056}

1058int apply_match_length(struct apply_handle *h, int symbol) {
  if (symbol == EPSILON0) {
return 0;
  }
  if (h->has_flags && (h->flag_lookup+symbol)->type) {
return 0;
  }
  if (((h->mode) & ENUMERATE2) == ENUMERATE2) {
return 0;
  }
  if (h->ipos >= h->current_instring_length) {
return -1;
  }
  if ((h->sigmatch_array+(h->ipos))->signumber == symbol) {
   return((h->sigmatch_array+(h->ipos))->consumes);
  }
  if ((symbol == IDENTITY2) || (symbol == UNKNOWN1)) {
if ((h->sigmatch_array+h->ipos)->signumber == IDENTITY2) {
   return((h->sigmatch_array+(h->ipos))->consumes);
}
  }
  return -1;
1080}

1082/* Match a symbol from sigma against the current position in string */
1083/* Return the number of symbols consumed in input string            */
1084/* For flags, we consume 0 symbols of the input string, naturally   */

1086int apply_match_str(struct apply_handle *h, int symbol, int position) {
  if (((h->mode) & ENUMERATE2) == ENUMERATE2) {
if (h->has_flags && (h->flag_lookup+symbol)->type) {
   if (!h->obey_flags) {
return 0;
   }
   if (apply_check_flag(h,(h->flag_lookup+symbol)->type, (h->flag_lookup+symbol)->name, (h->flag_lookup+symbol)->value) == SUCCEED1) {
return 0;
   } else {
return -1;
   }
}
return(0);
  }


  if (symbol == EPSILON0) {
return 0;
  }

  /* If symbol is a flag, we need to check consistency */
  if (h->has_flags && (h->flag_lookup+symbol)->type) {
if (!h->obey_flags) {
   return 0;
}
if (apply_check_flag(h,(h->flag_lookup+symbol)->type, (h->flag_lookup+symbol)->name, (h->flag_lookup+symbol)->value) == SUCCEED1) {
   return 0;
} else {
   return -1;
}
  }

  if (position >= h->current_instring_length) {
return -1;
  }
  if ((h->sigmatch_array+position)->signumber == symbol) {
return((h->sigmatch_array+position)->consumes);
  }
  if ((symbol == IDENTITY2) || (symbol == UNKNOWN1)) {
if ((h->sigmatch_array+position)->signumber == IDENTITY2) {
   return((h->sigmatch_array+position)->consumes);
}
  }
  return -1;
1130}

1132void apply_create_statemap(struct apply_handle *h, struct fsm *net) {
  int i;
  struct fsm_state *fsm;
  fsm = net->states;
  h->statemap = malloc(sizeof(int)*net->statecount);
  h->marks = malloc(sizeof(int)*net->statecount);
  h->numlines = malloc(sizeof(int)*net->statecount);

  for (i=0; i < net->statecount; i++) {
*(h->numlines+i) = 0;  /* Only needed in binary search */
*(h->statemap+i) = -1;
*(h->marks+i) = 0;
  }
  for (i=0; (fsm+i)->state_no != -1; i++) {
*(h->numlines+(fsm+i)->state_no) = *(h->numlines+(fsm+i)->state_no)+1;
if (*(h->statemap+(fsm+i)->state_no) == -1) {
   *(h->statemap+(fsm+i)->state_no) = i;
}
  }
1151}

1153void apply_add_sigma_trie(struct apply_handle *h, int number, char *symbol, int len) {

  /* Create a trie of sigma symbols (prefixes) so we can    */
  /* quickly (in O(n)) tokenize an arbitrary string into    */
  /* integer sequences representing symbols, using longest- */
  /* leftmost factorization.                                */

  int i;
  struct sigma_trie *st;
  struct sigma_trie_arrays *sta;

  st = h->sigma_trie;
  for (i = 0; i < len; i++) {
st = st+(unsigned char)*(symbol+i);
if (i == (len-1)) {
   st->signum = number;
} else {
   if (st->next == NULL((void*)0)) {
st->next = calloc(256,sizeof(struct sigma_trie));
st = st->next;
/* store these arrays to free them later */
sta = malloc(sizeof(struct sigma_trie_arrays));
sta->arr = st;
sta->next = h->sigma_trie_arrays;
h->sigma_trie_arrays = sta;
   } else {
st = st->next;
   }
}
  }
1183}

1185void apply_mark_flagstates(struct apply_handle *h) {
  int i;
  struct fsm_state *fsm;

  /* Create bitarray with those states that have a flag symbol on an arc */
  /* This is needed to decide whether we can perform a binary search.    */

  if (!h->has_flags || h->flag_lookup == NULL((void*)0)) {
return;
  }
  if (h->flagstates) {
free(h->flagstates);
  }
  h->flagstates = calloc(BITNSLOTS(h->last_net->statecount)((h->last_net->statecount + 8 - 1) / 8), sizeof(uint8_t));
  fsm = h->last_net->states;
  for (i=0; (fsm+i)->state_no != -1; i++) {
if ((fsm+i)->target == -1) {
   continue;
}
if ((h->flag_lookup+(fsm+i)->in)->type) {
   BITSET(h->flagstates,(fsm+i)->state_no)((h->flagstates)[(((fsm+i)->state_no) >> 3)] |= (
<< (((fsm+i)->state_no) & 7)));
}
if ((h->flag_lookup+(fsm+i)->out)->type) {
   BITSET(h->flagstates,(fsm+i)->state_no)((h->flagstates)[(((fsm+i)->state_no) >> 3)] |= (
<< (((fsm+i)->state_no) & 7)));
}
  }
1211}

1213void apply_create_sigarray(struct apply_handle *h, struct fsm *net) {
  struct sigma *sig;
  int i, maxsigma;

  maxsigma = sigma_max(net->sigma);
  h->sigma_size = maxsigma+1;
  // Default size created at init, resized later if necessary
  h->sigmatch_array = calloc(1024,sizeof(struct sigmatch_array));
  h->sigmatch_array_size = 1024;

  h->sigs = malloc(sizeof(struct sigs)*(maxsigma+1));
  h->has_flags = 0;
  h->flag_list = NULL((void*)0);

  /* Malloc first array of trie and store trie ptrs to be able to free later */
  /* when apply_clear() is called.                                           */

  h->sigma_trie = calloc(256,sizeof(struct sigma_trie));
  h->sigma_trie_arrays = malloc(sizeof(struct sigma_trie_arrays));
  h->sigma_trie_arrays->arr = h->sigma_trie;
  h->sigma_trie_arrays->next = NULL((void*)0);

  for (i=0;i<256;i++)
(h->sigma_trie+i)->next = NULL((void*)0);
  for (sig = h->gsigma; sig != NULL((void*)0) && sig->number != -1; sig = sig->next) {
if (flag_check(sig->symbol)) {
   h->has_flags = 1;
   apply_add_flag(h, flag_get_name(sig->symbol));
}
(h->sigs+(sig->number))->symbol = sig->symbol;
(h->sigs+(sig->number))->length = strlen(sig->symbol);
/* Add sigma entry to trie */
if (sig->number > IDENTITY2) {
   apply_add_sigma_trie(h, sig->number, sig->symbol, (h->sigs+(sig->number))->length);
}
  }
  if (maxsigma >= IDENTITY2) {
(h->sigs+EPSILON0)->symbol = h->epsilon_symbol;
(h->sigs+EPSILON0)->length =  strlen(h->epsilon_symbol);
(h->sigs+UNKNOWN1)->symbol = "?";
(h->sigs+UNKNOWN1)->length =  1;
(h->sigs+IDENTITY2)->symbol = "@";
(h->sigs+IDENTITY2)->length =  1;
  }
  if (h->has_flags) {

h->flag_lookup = malloc(sizeof(struct flag_lookup)*(maxsigma+1));
for (i=0; i <= maxsigma; i++) {
   (h->flag_lookup+i)->type = 0;
   (h->flag_lookup+i)->name = NULL((void*)0);
   (h->flag_lookup+i)->value = NULL((void*)0);
}
for (sig = h->gsigma; sig != NULL((void*)0) ; sig = sig->next) {
   if (flag_check(sig->symbol)) {
(h->flag_lookup+sig->number)->type = flag_get_type(sig->symbol);
(h->flag_lookup+sig->number)->name = flag_get_name(sig->symbol);
(h->flag_lookup+sig->number)->value = flag_get_value(sig->symbol);
   }
}
apply_mark_flagstates(h);
  }
1274}

1276/* We need to know which symbols in sigma we can match for all positions           */
1277/* in the input string.  Alternatively, if there is no input string as is the case */
1278/* when we just list the words or randomly search the graph, we can match          */
1279/* any symbol in sigma.                                                            */

1281/* We create an array that for each position in the input string        */
1282/* has information on which symbol we can match at that position        */
1283/* as well as how many symbols matching consumes                        */

1285void apply_create_sigmatch(struct apply_handle *h) {
  char *symbol;
  struct sigma_trie *st;
  int i, j, inlen, lastmatch, consumes, cons;
  /* We create a sigmatch array only in case we match against a real string */
  if (((h->mode) & ENUMERATE2) == ENUMERATE2) {
return;
  }
  symbol = h->instring;
  inlen = strlen(symbol);
  h->current_instring_length = inlen;
  if (inlen >= h->sigmatch_array_size) {
free(h->sigmatch_array);
h->sigmatch_array = malloc(sizeof(struct sigmatch_array)*(inlen));
h->sigmatch_array_size = inlen;
  }
  /* Find longest match in alphabet at current position */
  /* by traversing the trie of alphabet symbols         */
  for (i=0; i < inlen; i += consumes ) {
st = h->sigma_trie;
for (j=0, lastmatch = 0; ; j++) {
   if (*(symbol+i+j) == '\0') {
break;
   }
   st = st+(unsigned char)*(symbol+i+j);
   if (st->signum != 0) {
lastmatch = st->signum;
if (st->next == NULL((void*)0))
    break;
st = st->next;
   } else if (st->next != NULL((void*)0)) {
st = st->next;
   } else {
break;
   }
}
if (lastmatch != 0) {
   (h->sigmatch_array+i)->signumber = lastmatch;
   consumes = (h->sigs+lastmatch)->length;
} else {
   /* Not found in trie */
   (h->sigmatch_array+i)->signumber = IDENTITY2;
   consumes = utf8skip(symbol+i)+1;
}

/* If we now find trailing unicode combining characters (0300-036F):      */
/* (1) Merge them all with current symbol                                 */
/* (2) Declare the whole sequence one ? (IDENTITY) symbol                 */
      /*     Step 2 is motivated by the fact that                               */
/*     if the input is S(symbol) + D(diacritic)                           */
      /*     and SD were a symbol in the alphabet, then this would have been    */
      /*     found when searching the alphabet symbols earlier, so SD+ => ?     */
      /*     Note that this means that a multi-char symbol followed by a        */
      /*     diacritic gets converted to a single ?, e.g.                       */
      /*     [TAG] + D => ? if [TAG] is in the alphabet, but [TAG]+D isn't.     */

for (  ; (cons = utf8iscombining((unsigned char *)(symbol+i+consumes))); consumes += cons) {
   (h->sigmatch_array+i)->signumber = IDENTITY2;
}
(h->sigmatch_array+i)->consumes = consumes;
  }
1346}

1348void apply_add_flag(struct apply_handle *h, char *name) {
  struct flag_list *flist, *flist_prev;
  if (h->flag_list == NULL((void*)0)) {
flist = h->flag_list = malloc(sizeof(struct flag_list));
  } else {
for (flist = h->flag_list; flist != NULL((void*)0); flist_prev = flist, flist = flist->next) {
   if (strcmp(flist->name, name) == 0) {
return;
   }
}
flist = malloc(sizeof(struct flag_list));
flist_prev->next = flist;
  }
  flist->name = name;
  flist->value = NULL((void*)0);
  flist->neg = 0;
  flist->next = NULL((void*)0);
  return;
1366}

1368void apply_clear_flags(struct apply_handle *h) {
  struct flag_list *flist;
  for (flist = h->flag_list; flist != NULL((void*)0); flist = flist->next) {
flist->value = NULL((void*)0);
flist->neg = 0;
  }
  return;
1375}

1377/* Check for flag consistency by looking at the current states of */
1378/* flags in flist */

1380int apply_check_flag(struct apply_handle *h, int type, char *name, char *value) {
  struct flag_list *flist, *flist2;
  for (flist = h->flag_list; flist != NULL((void*)0); flist = flist->next) {
if (strcmp(flist->name, name) == 0) {
   break;
}
  }
  h->oldflagvalue = flist->value;
  h->oldflagneg = flist->neg;

  if (type == FLAG_UNIFY1) {
if (flist->value == NULL((void*)0)) {
   flist->value = strdup(value);
   return SUCCEED1;
}
else if (strcmp(value, flist->value) == 0 && flist->neg == 0) {
   return SUCCEED1;
} else if (strcmp(value, flist->value) != 0 && flist->neg == 1) {
   flist->value = strdup(value);
   flist->neg = 0;
   return SUCCEED1;
}
return FAIL0;
  }

  if (type == FLAG_CLEAR2) {
flist->value = NULL((void*)0);
flist->neg = 0;
return SUCCEED1;
  }

  if (type == FLAG_DISALLOW4) {
if (flist->value == NULL((void*)0)) {
   return SUCCEED1;
}
if (value == NULL((void*)0) && flist->value != NULL((void*)0)) {
   return FAIL0;
}
if (strcmp(value, flist->value) != 0) {
          if (flist->neg == 1)
              return FAIL0;
          return SUCCEED1;
}
if (strcmp(value, flist->value) == 0 && flist->neg == 1) {
          return SUCCEED1;
      }
      return FAIL0;
  }

  if (type == FLAG_NEGATIVE8) {
flist->value = value;
flist->neg = 1;
return SUCCEED1;
  }

  if (type == FLAG_POSITIVE16) {
flist->value = value;
flist->neg = 0;
return SUCCEED1;
  }

  if (type == FLAG_REQUIRE32) {

if (value == NULL((void*)0)) {
   if (flist->value == NULL((void*)0)) {
return FAIL0;
   } else {
return SUCCEED1;
   }
} else {
   if (flist->value == NULL((void*)0)) {
return FAIL0;
   }
   if (strcmp(value, flist->value) != 0) {
return FAIL0;
   } else {
              if (flist->neg == 1) {
                  return FAIL0;
              }
return SUCCEED1;
   }
}
  }

  if (type == FLAG_EQUAL64) {
for (flist2 = h->flag_list; flist2 != NULL((void*)0); flist2 = flist2->next) {
   if (strcmp(flist2->name, value) == 0) {
break;
   }
}

if (flist2 == NULL((void*)0) && flist->value != NULL((void*)0))
   return FAIL0;
if (flist2 == NULL((void*)0) && flist->value == NULL((void*)0)) {
   return SUCCEED1;
}
if (flist2->value == NULL((void*)0) || flist->value == NULL((void*)0)) {
   if (flist2->value == NULL((void*)0) && flist->value == NULL((void*)0) && flist->neg == flist2->neg) {
return SUCCEED1;
   } else {
return FAIL0;
   }
}  else if (strcmp(flist2->value, flist->value) == 0 && flist->neg == flist2->neg) {
   return SUCCEED1;
}
return FAIL0;
  }
  fprintf(stderrstderr,"***Don't know what do with flag [%i][%s][%s]\n", type, name, value);
  return FAIL0;
1489}