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

Bug Summary

File:	structures.c
Warning:	line 796, column 5 Potential leak of memory pointed to by 'newstring'

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 structures.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 -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/structures.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 <string.h>
20#include <stdlib.h>
21#include "foma.h"

23static struct defined_quantifiers *quantifiers;
24struct _fsm_options fsm_options;

26char *fsm_get_library_version_string() {
  static char s[20];
  sprintf(s,"%i.%i.%i%s",MAJOR_VERSION0,MINOR_VERSION10,BUILD_VERSION0,STATUS_VERSION"alpha");
  return(s);
30}

32_Bool fsm_set_option(unsigned long long option, void *value) {
switch (option) {
case FSMO_SKIP_WORD_BOUNDARY_MARKER:
fsm_options.skip_word_boundary_marker = *((_Bool*)value);
return 1;
}
return 0;
39}

41void *fsm_get_option(unsigned long long option) {
switch (option) {
case FSMO_SKIP_WORD_BOUNDARY_MARKER:
return &fsm_options.skip_word_boundary_marker;
}
return NULL((void*)0);
47}

49int linesortcompin(struct fsm_state *a, struct fsm_state *b) {
  return (a->in - b->in);
51}

53int linesortcompout(struct fsm_state *a, struct fsm_state *b) {
  return (a->out - b->out);
55}

57void fsm_sort_arcs(struct fsm *net, int direction) {
  /* direction 1 = in, direction = 2, out */
  struct fsm_state *fsm;
  int i, lasthead, numlines;
  int(*scin)() = linesortcompin;
  int(*scout)() = linesortcompout;
  fsm = net->states;
  for (i=0, numlines = 0, lasthead = 0 ; (fsm+i)->state_no != -1; i++) {
if ((fsm+i)->state_no != (fsm+i+1)->state_no || (fsm+i)->target == -1) {
   numlines++;
   if ((fsm+i)->target == -1) {
numlines--;
   }
   if (numlines > 1) {
/* Sort, set numlines = 0 */
if (direction == 1)
    qsort(fsm+lasthead, numlines, sizeof(struct fsm_state), scin);
else
    qsort(fsm+lasthead, numlines, sizeof(struct fsm_state), scout);		
   }
   numlines = 0;
   lasthead = i + 1;
   continue;
}
numlines++;
  }
  if (net->arity == 1) {
net->arcs_sorted_in = 1;
net->arcs_sorted_out = 1;
return;
  }
  if (direction == 1) {
net->arcs_sorted_in = 1;
net->arcs_sorted_out = 0;
  }
  if (direction == 2) {
net->arcs_sorted_out = 1;
net->arcs_sorted_in = 0;
  }    
96}

98struct state_array *map_firstlines(struct fsm *net) {
  struct fsm_state *fsm;
  struct state_array *sa;
  int i, sold;
  sold = -1;
  sa = malloc(sizeof(struct state_array)*((net->statecount)+1));
  fsm = net->states;
  for (i=0; (fsm+i)->state_no != -1; i++) {
      if ((fsm+i)->state_no != sold) {
          (sa+((fsm+i)->state_no))->transitions = fsm+i;
          sold = (fsm+i)->state_no;
      }
  }
  return(sa);
112}

114struct fsm *fsm_boolean(int value) {
  if (value == 0)
      return (fsm_empty_set());
  else
      return(fsm_empty_string());
119}

121struct fsm *fsm_sigma_net(struct fsm *net) {
  /* Extract sigma and create net with one arc            */
  /* from state 0 to state 1 with each (state 1 is final) */
  struct sigma *sig;
  int pathcount;

  if (sigma_size(net->sigma) == 0) {
fsm_destroy(net);
      return(fsm_empty_set());
  }
  
  fsm_state_init(sigma_max(net->sigma));
  fsm_state_set_current_state(0, 0, 1);
  pathcount = 0;
  for (sig = net->sigma; sig != NULL((void*)0); sig = sig->next) {
      if (sig->number >=3 || sig->number == IDENTITY2) {
          pathcount++;
          fsm_state_add_arc(0,sig->number, sig->number, 1, 0, 1);
      }
  }
  fsm_state_end_state();
  fsm_state_set_current_state(1, 1, 0);
  fsm_state_end_state();
  free(net->states);
  fsm_state_close(net);
  net->is_minimized = YES1;
  net->is_loop_free = YES1;
  net->pathcount = pathcount;
  sigma_cleanup(net, 1);
  return(net);
151}

153struct fsm *fsm_sigma_pairs_net(struct fsm *net) {
  /* Create FSM of attested pairs */
  struct fsm_state *fsm;
  char *pairs;
  short int in, out;
  int i, pathcount, smax;
  
  smax = sigma_max(net->sigma)+1;
  pairs = calloc(smax*smax, sizeof(char));

  fsm_state_init(sigma_max(net->sigma));
  fsm_state_set_current_state(0, 0, 1);
  pathcount = 0;
  for (fsm = net->states, i=0; (fsm+i)->state_no != -1; i++) {
      if ((fsm+i)->target == -1)
          continue;
      in = (fsm+i)->in;
      out = (fsm+i)->out;
      if (*(pairs+smax*in+out) == 0) {
          fsm_state_add_arc(0,in,out, 1, 0, 1);
          *(pairs+smax*in+out) = 1;
          pathcount++;
      }
  }
  fsm_state_end_state();
  fsm_state_set_current_state(1, 1, 0);
  fsm_state_end_state();

  free(pairs);
  free(net->states);

  fsm_state_close(net);
  if (pathcount == 0) {
      fsm_destroy(net);
      return(fsm_empty_set());
  }
  net->is_minimized = YES1;
  net->is_loop_free = YES1;
  net->pathcount = pathcount;
  sigma_cleanup(net, 1);
  return(net);
194}

196int fsm_sigma_destroy(struct sigma *sigma) {
  struct sigma *sig, *sigp;
  for (sig = sigma, sigp = NULL((void*)0); sig != NULL((void*)0); sig = sigp) {
sigp = sig->next;
if (sig->symbol != NULL((void*)0)) {
   free(sig->symbol);
   sig->symbol = NULL((void*)0);
}
free(sig);
  }
  return 1;
207}

209int fsm_destroy(struct fsm *net) {
  if (net == NULL((void*)0)) {
      return 0;
  }
  if (net->medlookup != NULL((void*)0) && net->medlookup->confusion_matrix != NULL((void*)0)) {
      free(net->medlookup->confusion_matrix);
net->medlookup->confusion_matrix = NULL((void*)0);
  }
  if (net->medlookup != NULL((void*)0)) {
      free(net->medlookup);
net->medlookup = NULL((void*)0);
  }
  fsm_sigma_destroy(net->sigma);
  net->sigma = NULL((void*)0);
  if (net->states != NULL((void*)0)) {
      free(net->states);
net->states = NULL((void*)0);
  }
  free(net);
  return(1);
229}

231struct fsm *fsm_create (char *name) {
if (strlen(name) > FSM_NAME_LEN40) {
  printf("Network name '%s' should consist of at most %d characters.\n", name, FSM_NAME_LEN40);
}
struct fsm *fsm;
fsm = malloc(sizeof(struct fsm));
strncpy(fsm->name, name, FSM_NAME_LEN40);
fsm->arity = 1;
fsm->arccount = 0;
fsm->is_deterministic = NO0;
fsm->is_pruned = NO0;
fsm->is_minimized = NO0;
fsm->is_epsilon_free = NO0;
fsm->is_loop_free = NO0;
fsm->arcs_sorted_in = NO0;
fsm->arcs_sorted_out = NO0;
fsm->sigma = sigma_create();
fsm->states = NULL((void*)0);
fsm->medlookup = NULL((void*)0);
return(fsm);
251}

253struct fsm *fsm_empty_string() {
struct fsm *net;
net = fsm_create("");
net->states = malloc(sizeof(struct fsm_state)*2);
add_fsm_arc(net->states, 0, 0, -1, -1, -1, 1, 1);
add_fsm_arc(net->states, 1, -1, -1, -1, -1, -1, -1);
fsm_update_flags(net,YES1,YES1,YES1,YES1,YES1,NO0);
net->statecount = 1;
net->finalcount = 1;
net->arccount = 0;
net->linecount = 2;
net->pathcount = 1;
return(net);
266}

268struct fsm *fsm_identity() {
struct fsm *net;
struct sigma *sigma;
net = fsm_create("");
free(net->sigma);
net->states = malloc(sizeof(struct fsm_state)*3);
add_fsm_arc(net->states, 0, 0, 2, 2, 1, 0, 1);
add_fsm_arc(net->states, 1, 1, -1, -1, -1, 1, 0);
add_fsm_arc(net->states, 2, -1, -1, -1, -1, -1, -1);
sigma = malloc(sizeof(struct sigma));
sigma->number = IDENTITY2;
sigma->symbol = strdup("@_IDENTITY_SYMBOL_@");
sigma->next = NULL((void*)0);
net->sigma = sigma;
fsm_update_flags(net,YES1,YES1,YES1,YES1,YES1,NO0);
net->statecount = 2;
net->finalcount = 1;
net->arccount = 1;
net->linecount = 3;
net->pathcount = 1;
return(net);
289}

291struct fsm *fsm_empty_set() {
struct fsm *net;
net = fsm_create("");
net->states = fsm_empty();
fsm_update_flags(net,YES1,YES1,YES1,YES1,YES1,NO0);
net->statecount = 1;
net->finalcount = 0;
net->arccount = 0;
net->linecount = 2;
net->pathcount = 0;
return(net);
302}

304struct fsm_state *fsm_empty() {
struct fsm_state *new_fsm;
new_fsm = malloc(sizeof(struct fsm_state)*2);
add_fsm_arc(new_fsm, 0, 0, -1, -1, -1, 0, 1);
add_fsm_arc(new_fsm, 1, -1, -1, -1, -1, -1, -1);
return(new_fsm);
310}

312int fsm_isuniversal(struct fsm *net) {
  struct fsm_state *fsm;
  net = fsm_minimize(net);
  fsm_compact(net);
  fsm = net->states;
  if ((fsm->target == 0 && fsm->final_state == 1 && (fsm+1)->state_no == 0) && 
      (fsm->in == IDENTITY2 && fsm->out == IDENTITY2) &&
      ((fsm+1)->state_no == -1) &&
      (sigma_max(net->sigma)<3) ) {
      return 1;
  } else {
      return 0;
  }
325}

327int fsm_isempty(struct fsm *net) {
  int result;
  struct fsm *minimal = fsm_minimize(fsm_copy(net));
  struct fsm_state *fsm = minimal->states;
  if (fsm->target == -1 && fsm->final_state == 0 && (fsm+1)->state_no == -1)
      result = 1;
  else 
      result = 0;
  fsm_destroy(minimal);
  return result;
337}

339int fsm_issequential(struct fsm *net) {
  int i, *sigtable, sequential, seentrans, epstrans, laststate, insym;
  struct fsm_state *fsm;
  sigtable = calloc(sigma_max(net->sigma)+1,sizeof(int));
  for (i = 0 ; i < sigma_max(net->sigma)+1; i++) {
sigtable[i] = -2;
  }
  fsm = net->states;
  seentrans = epstrans = 0;
  laststate = -1;
  for (sequential = 1, i = 0; (fsm+i)->state_no != -1 ; i++) {
insym = (fsm+i)->in;
if (insym < 0) {
   continue;
}
if ((fsm+i)->state_no != laststate) {
   laststate = (fsm+i)->state_no;
   epstrans = 0;
   seentrans = 0;
}
if (*(sigtable+insym) == laststate || epstrans == 1) {
   sequential = 0;
   break;
}
if (insym == EPSILON0) {
   if (epstrans == 1 || seentrans == 1) {
sequential = 0;
break;
   }
   epstrans = 1;
}
*(sigtable+insym) = laststate;
seentrans = 1;
  }
  free(sigtable);
  if (!sequential)
printf("fails at state %i\n",(fsm+i)->state_no);
  return(sequential);
377}

379int fsm_isfunctional(struct fsm *net) {
  struct fsm *tmp = fsm_minimize(fsm_compose(fsm_invert(fsm_copy(net)),fsm_copy(net)));
  int result = fsm_isidentity(tmp);
  fsm_destroy(tmp);
  return result;
384}

386int fsm_isunambiguous(struct fsm *net) {
  struct fsm *loweruniqnet, *testnet;
  int ret;
  loweruniqnet = fsm_lowerdet(fsm_copy(net));
  testnet = fsm_minimize(fsm_compose(fsm_invert(fsm_copy(loweruniqnet)),fsm_copy(loweruniqnet)));
  ret = fsm_isidentity(testnet);
  fsm_destroy(loweruniqnet);
  fsm_destroy(testnet);
  return(ret);
395}

397struct fsm *fsm_extract_ambiguous_domain(struct fsm *net) {
  // define AmbiguousDom(T) [_loweruniq(T) .o. _notid(_loweruniq(T).i .o. _loweruniq(T))].u;
  struct fsm *loweruniqnet, *result;
  loweruniqnet = fsm_lowerdet(net);
  result = fsm_topsort(fsm_minimize(fsm_upper(fsm_compose(fsm_copy(loweruniqnet),fsm_extract_nonidentity(fsm_compose(fsm_invert(fsm_copy(loweruniqnet)), fsm_copy(loweruniqnet)))))));
2
←
Calling 'fsm_extract_nonidentity'→
  fsm_destroy(loweruniqnet);
  sigma_cleanup(result,1);
  fsm_compact(result);
  sigma_sort(result);
  return(result);
407}

409struct fsm *fsm_extract_ambiguous(struct fsm *net) {
  struct fsm *result;
  result = fsm_topsort(fsm_minimize(fsm_compose(fsm_extract_ambiguous_domain(fsm_copy(net)), net)));
  return(result);
413}

415struct fsm *fsm_extract_unambiguous(struct fsm *net) {
  struct fsm *result;
  result = fsm_topsort(fsm_minimize(fsm_compose(fsm_complement(fsm_extract_ambiguous_domain(fsm_copy(net))), net)));
1
Calling 'fsm_extract_ambiguous_domain'→
  return(result);
419}

421int fsm_isidentity(struct fsm *net) {

  /* We check whether a given transducer only produces identity relations     */
  /* By doing a DFS on the graph, and storing, for each state a "discrepancy" */
  /* string, showing the current "debt" on the upper or lower side.           */
  /* We immediately fail if: */
  /* a) we encounter an already seen state with a different current           */
  /*    discrepancy than what is stored in the state.                         */
  /* b) when traversing an arc, we encounter a mismatch between the arc and   */
  /*    the current discrepancy.                                              */
  /* c) we encounter a final state and have a non-null current discrepancy.   */
  /* d) we encounter @ with a non-null discrepancy anywhere.                  */
  /* e) we encounter ? anywhere.                                              */
  
  struct discrepancy {
      short int *string;
      short int length;
      _Bool visited;
  };

  struct state_array *state_array;
  struct fsm_state *curr_ptr;
  int i, j, v, vp, num_states, factor = 0, newlength = 1, startfrom;
  short int in, out, *newstring = NULL((void*)0);
  struct discrepancy *discrepancy, *currd, *targetd;
  struct fsm *tmp;

  tmp = fsm_minimize(fsm_copy(net));
  fsm_count(tmp);
  
  num_states = tmp->statecount;
  discrepancy = calloc(num_states,sizeof(struct discrepancy));
  state_array = map_firstlines(tmp);
  ptr_stack_clear();
  ptr_stack_push(state_array->transitions);

  while(!ptr_stack_isempty()) {

      curr_ptr = ptr_stack_pop();

  nopop:
      v = curr_ptr->state_no; /* source state number */
      vp = curr_ptr->target;  /* target state number */
      currd = discrepancy+v;
      if (v != -1)
          currd->visited = 1;
      if (v == -1 || vp == -1)
          continue;
      in = curr_ptr->in;
      out = curr_ptr->out;

      targetd = discrepancy+vp;
      /* Check arc and conditions e) d) b) */
      /* e) */
      if (in == UNKNOWN1 || out == UNKNOWN1)
          goto fail;
      /* d) */
      if (in == IDENTITY2 && currd->length != 0)
          goto fail;
      /* b) */
      if (currd->length != 0) {
          if (currd->length > 0 && out != EPSILON0 && out != *(currd->string))
              goto fail;
          if (currd->length < 0 && in != EPSILON0 && in  != *(currd->string))
              goto fail;
      }
      if (currd->length == 0 && in != out && in != EPSILON0 && out != EPSILON0) {
          goto fail;
      }

      /* Calculate new discrepancy */
      if (currd->length != 0) {
          if (in != EPSILON0 && out != EPSILON0)
              factor = 0;
          else if (in == EPSILON0)
              factor = -1;
          else if (out == EPSILON0)
              factor = 1;
          
          newlength = currd->length + factor;
          startfrom = (abs(newlength) <= abs(currd->length)) ? 1 : 0;

      } else if (currd->length == 0) {
          if (in != EPSILON0 && out != EPSILON0) {
              newlength = 0;
          } else {
              newlength = (out == EPSILON0) ? 1 : -1;
          }
          startfrom = 0;
      }

      if (newstring != NULL((void*)0)) {
          free(newstring);
          newstring = NULL((void*)0);
      }
      newstring = calloc(abs(newlength),sizeof(int));

      for (i = startfrom, j = 0; i < abs(currd->length); i++, j++) {
          *(newstring+j) = *((currd->string)+i);
      }
      if (newlength != 0) {
          if (currd->length > 0 && newlength >= currd->length) {
              *(newstring+j) = in;
          }
          if (currd->length < 0 && newlength <= currd->length) {
              *(newstring+j) = out;
          }
          if (currd->length == 0 && newlength < currd->length) {
              *(newstring+j) = out;
          }
          if (currd->length == 0 && newlength > currd->length) {
              *(newstring+j) = in;
          }
      }

      /* Check target conditions a) c) */
      /* a) */
      if (((state_array+vp)->transitions)->final_state && newlength != 0)
          goto fail;
      if (curr_ptr->state_no == (curr_ptr+1)->state_no) {
          ptr_stack_push(curr_ptr+1);
      }
      if ((discrepancy+vp)->visited) {
          //free(newstring);
          if (targetd->length != newlength)
              goto fail;
          for (i=0 ; i < abs(newlength); i++) {
              if (*((targetd->string)+i) != *(newstring+i))
                  goto fail;
          }
      } else {
          /* Add discrepancy to target state */
          targetd->length = newlength;
          targetd->string = newstring;
          curr_ptr = (state_array+vp)->transitions;
          goto nopop;
      }
  }
  free(state_array);
  free(discrepancy);
  fsm_destroy(tmp);
  if (newstring != NULL((void*)0))
      free(newstring);
  return 1;
fail:
  free(state_array);
  free(discrepancy);
  ptr_stack_clear();
  fsm_destroy(tmp);
  if (newstring != NULL((void*)0))
      free(newstring);
  return 0;
573}

575struct fsm *fsm_markallfinal(struct fsm *net) {
  struct fsm_state *fsm;
  int i;
  fsm = net->states;
  for (i=0; (fsm+i)->state_no != -1; i++) {
      (fsm+i)->final_state = YES1;
  }
  return net;
583}

585struct fsm *fsm_lowerdet(struct fsm *net) {
  unsigned int newsym; /* Running number for new syms */
  struct fsm_state *fsm;
  char repstr[13];
  int i,j,maxsigma,maxarc;
  net = fsm_minimize(net);
  fsm_count(net);
  newsym = 8723643;
  fsm = net->states;
  maxarc = 0;
  maxsigma = sigma_max(net->sigma);

  for (i=0, j=0; (fsm+i)->state_no != -1; i++) {
      if ((fsm+i)->target != -1)
          j++;
      if ((fsm+i+1)->state_no != (fsm+i)->state_no) {
          maxarc = maxarc > j ? maxarc : j;
          j = 0;
      }
  }
  if (maxarc > (maxsigma-2)) {
      for (i=maxarc; i > (maxsigma-2); i--) {
          sprintf(repstr,"%012X",newsym++);        
          sigma_add(repstr, net->sigma);
      }
      sigma_sort(net);
  }
  for (i=0, j=3; (fsm+i)->state_no != -1; i++) {
      if ((fsm+i)->target != -1) {
          (fsm+i)->out = j++;
          (fsm+i)->in = ((fsm+i)->in == IDENTITY2) ? UNKNOWN1 : (fsm+i)->in;
      }
      if ((fsm+i+1)->state_no != (fsm+i)->state_no) {
          j = 3;
      }
  }
  return(net);
622}

624struct fsm *fsm_lowerdeteps(struct fsm *net) {
  unsigned int newsym; /* Running number for new syms */
  struct fsm_state *fsm;
  char repstr[13];
  int i,j,maxsigma,maxarc;
  net = fsm_minimize(net);
  fsm_count(net);
  newsym = 8723643;
  fsm = net->states;
  maxarc = 0;
  maxsigma = sigma_max(net->sigma);

  for (i=0, j=0; (fsm+i)->state_no != -1; i++) {
      if ((fsm+i)->target != -1)
          j++;
      if ((fsm+i+1)->state_no != (fsm+i)->state_no) {
          maxarc = maxarc > j ? maxarc : j;
          j = 0;
      }
  }
  if (maxarc > (maxsigma-2)) {
      for (i=maxarc; i > (maxsigma-2); i--) {
          sprintf(repstr,"%012X",newsym++);        
          sigma_add(repstr, net->sigma);
      }
      sigma_sort(net);
  }
  for (i=0, j=3; (fsm+i)->state_no != -1; i++) {
      if ((fsm+i)->target != -1 && (fsm+i)->out != EPSILON0) {
          (fsm+i)->out = j++;
          (fsm+i)->in = ((fsm+i)->in == IDENTITY2) ? UNKNOWN1 : (fsm+i)->in;
      }
      if ((fsm+i+1)->state_no != (fsm+i)->state_no) {
          j = 3;
      }
  }
  return(net);
661}

663struct fsm *fsm_extract_nonidentity(struct fsm *net) {

  /* Same algorithm as for test identity, except we mark the arcs that cause nonidentity */
  /* Experimental. */

  struct discrepancy {
      short int *string;
      short int length;
      _Bool visited;
  };

  struct state_array *state_array;
  struct fsm_state *curr_ptr;
  struct fsm *net2;
  int i, j, v, vp, num_states, factor = 0, newlength = 1, startfrom, killnum;
  short int in, out, *newstring;
  struct discrepancy *discrepancy, *currd, *targetd;

  fsm_minimize(net);
  fsm_count(net);
  killnum = sigma_add("@KILL@", net->sigma);
  
  num_states = net->statecount;
  discrepancy = calloc(num_states,sizeof(struct discrepancy));
  state_array = map_firstlines(net);
  ptr_stack_push(state_array->transitions);

  while(!ptr_stack_isempty()) {
3
←
Assuming the condition is true→
4
←
Loop condition is true.  Entering loop body→
32
←
 Execution continues on line 690→
33
←
Assuming the condition is false→
34
←
Loop condition is false. Execution continues on line 796→

      curr_ptr = ptr_stack_pop();

  nopop:
      v = curr_ptr->state_no; /* source state number */
      vp = curr_ptr->target;  /* target state number */
      currd = discrepancy+v;
      if (v != -1)
5
←
Assuming the condition is true→
6
←
Taking true branch→
          currd->visited = 1;
      if (v == -1 || vp == -1)
7
←
Assuming the condition is false→
8
←
Taking false branch→
          continue;
      in = curr_ptr->in;
      out = curr_ptr->out;

      targetd = discrepancy+vp;
      /* Check arc and conditions e) d) b) */
      /* e) */
      if (in == UNKNOWN1 || out == UNKNOWN1)
9
←
Assuming 'in' is not equal to UNKNOWN→
10
←
Assuming 'out' is not equal to UNKNOWN→
          goto fail;
      /* d) */
      if (in == IDENTITY2 && currd->length != 0)
11
←
Assuming 'in' is not equal to IDENTITY→
          goto fail;
      /* b) */
      if (currd->length != 0) {
12
←
Assuming field 'length' is equal to 0→
          if (currd->length > 0 && out != EPSILON0 && out != *(currd->string))
              goto fail;
          if (currd->length < 0 && in != EPSILON0 && in  != *(currd->string))
              goto fail;
      }
      if (currd->length == 0 && in != out && in != EPSILON0 && out != EPSILON0) {
13
←
Assuming field 'length' is not equal to 0→
          goto fail;
      }

      /* Calculate new discrepancy */
      if (currd->length != 0) {
14
←
Assuming field 'length' is equal to 0→
15
←
Taking false branch→
          if (in != EPSILON0 && out != EPSILON0)
              factor = 0;
          else if (in == EPSILON0)
              factor = -1;
          else if (out == EPSILON0)
              factor = 1;
          
          newlength = currd->length + factor;
          startfrom = (abs(newlength) <= abs(currd->length)) ? 1 : 0;

      } else if (currd->length == 0) {
16
←
Assuming field 'length' is equal to 0→
          if (in != EPSILON0 && out != EPSILON0) {
17
←
Assuming 'in' is not equal to EPSILON→
18
←
Assuming 'out' is not equal to EPSILON→
19
←
Taking true branch→
              newlength = 0;
          } else {
              newlength = (out == EPSILON0) ? 1 : -1;
          }
          startfrom = 0;
      }

      newstring = calloc(abs(newlength),sizeof(int));
20
←
Memory is allocated→

      for (i = startfrom, j = 0; i < abs(currd->length); i++, j++) {
21
←
Assuming the condition is false→
22
←
Loop condition is false. Execution continues on line 750→
          *(newstring+j) = *((currd->string)+i);
      }
      if (newlength22.1
'newlength' is equal to 0
 != 0) {
          if (currd->length > 0 && newlength >= currd->length) {
              *(newstring+j) = in;
          }
          if (currd->length < 0 && newlength <= currd->length) {
              *(newstring+j) = out;
          }
          if (currd->length == 0 && newlength < currd->length) {
              *(newstring+j) = out;
          }
          if (currd->length == 0 && newlength > currd->length) {
              *(newstring+j) = in;
          }

      }

      /* Check target conditions a) c) */
      /* a) */
      if (((state_array+vp)->transitions)->final_state && newlength != 0)
23
←
Assuming field 'final_state' is 0→
          goto fail;
      if (curr_ptr->state_no == (curr_ptr+1)->state_no) {
24
←
Assuming 'curr_ptr->state_no' is not equal to '(curr_ptr+1)->state_no'→
25
←
Taking false branch→
          ptr_stack_push(curr_ptr+1);
      }

      if ((discrepancy+vp)->visited) {
26
←
Assuming field 'visited' is true→
27
←
Taking true branch→
          //free(newstring);
          if (targetd->length != newlength)
28
←
Assuming 'newlength' is equal to field 'length'→
29
←
Taking false branch→
              goto fail;
          for (i=0 ; i < abs(newlength); i++) {
30
←
Assuming the condition is false→
31
←
Loop condition is false. Execution continues on line 789→
              if (*((targetd->string)+i) != *(newstring+i))
                  goto fail;
          }
      } else {
          /* Add discrepancy to target state */
          targetd->length = newlength;
          targetd->string = newstring;
          curr_ptr = (state_array+vp)->transitions;
          goto nopop;
      }
      continue;
  fail:        
      curr_ptr->out = killnum;
      if (curr_ptr->state_no == (curr_ptr+1)->state_no) {
          ptr_stack_push(curr_ptr+1);
      }        
  }
  ptr_stack_clear();
35
←
Potential leak of memory pointed to by 'newstring'
  sigma_sort(net);
  net2 = fsm_upper(fsm_compose(net,fsm_contains(fsm_symbol("@KILL@"))));
  sigma_remove("@KILL@",net2->sigma);
  sigma_sort(net2);
  free(state_array);
  free(discrepancy);
  return(net2);
804}

806struct fsm *fsm_copy (struct fsm *net) {
  struct fsm *net_copy;
  if (net == NULL((void*)0))
      return net;

  net_copy = malloc(sizeof(struct fsm));
  memcpy(net_copy, net, sizeof(struct fsm));

  fsm_count(net);
  net_copy->sigma = sigma_copy(net->sigma);
  net_copy->states = fsm_state_copy(net->states, net->linecount);      
  return(net_copy);
818}

820struct fsm_state *fsm_state_copy(struct fsm_state *fsm_state, int linecount) {
struct fsm_state *new_fsm_state;

new_fsm_state = malloc(sizeof(struct fsm_state)*(linecount));
memcpy(new_fsm_state, fsm_state, linecount*sizeof(struct fsm_state));
return(new_fsm_state);
826}

828/* TODO: separate linecount and arccount */
829int find_arccount(struct fsm_state *fsm) {
int i;
for (i=0;(fsm+i)->state_no != -1; i++) {
}
return i;
834}

836void clear_quantifiers() {
  quantifiers = NULL((void*)0);
838}

840int count_quantifiers() {
  struct defined_quantifiers *q;
  int i;
  for (i = 0, q = quantifiers; q != NULL((void*)0); q = q->next) {
i++;
  }
  return(i);
847}

849void add_quantifier (char *string) {
  struct defined_quantifiers *q;
  if (quantifiers == NULL((void*)0)) {
q = malloc(sizeof(struct defined_quantifiers));
quantifiers = q;
  } else { 
for (q = quantifiers; q->next != NULL((void*)0); q = q->next) {
   
}
q->next = malloc(sizeof(struct defined_quantifiers));
q = q->next;
  }
  q->name = strdup(string);
  q->next = NULL((void*)0);
863}

865struct fsm *union_quantifiers() {
866/*     We create a FSM that simply accepts the union of all */
867/*     quantifier symbols */
  
  struct fsm *net;
  struct defined_quantifiers *q;
  int i, syms, s, symlo;
  
  net = fsm_create("");
  fsm_update_flags(net, YES1, YES1, YES1, YES1, NO0, NO0);
  
  for (syms = 0, symlo = 0, q = quantifiers; q != NULL((void*)0); q = q->next) {
    s = sigma_add(q->name, net->sigma);
    if (symlo == 0) {
symlo = s;
    }
    syms++;
  }
  net->states = malloc(sizeof(struct fsm_state)*(syms+1));
  for (i = 0; i < syms; i++) {
add_fsm_arc(net->states, i, 0, symlo+i, symlo+i, 0, 1, 1);
  }
  add_fsm_arc(net->states, i, -1, -1, -1, -1 ,-1 ,-1);
  net->arccount = syms;
  net->statecount = net->finalcount = 1;
  net->linecount = syms;
  return(net);
892}

894char *find_quantifier (char *string) {
  struct defined_quantifiers *q;
  for (q = quantifiers; q != NULL((void*)0); q = q->next) {
if (strcmp(string,q->name) == 0)
   return q->name;
  }
  return(NULL((void*)0));
901}

903void purge_quantifier (char *string) {
  struct defined_quantifiers *q, *q_prev;    
  for (q = quantifiers, q_prev = NULL((void*)0); q != NULL((void*)0); q_prev = q, q = q->next) {
if (strcmp(string, q->name) == 0) {
   if (q_prev != NULL((void*)0)) {
q_prev->next = q->next;
   } else {
quantifiers = q->next;
   }
}
  }
914}

916struct fsm *fsm_quantifier(char *string) {

  /* \x* x \x* x \x* */
  return(fsm_concat(fsm_kleene_star(fsm_term_negation(fsm_symbol(string))),fsm_concat(fsm_symbol(string),fsm_concat(fsm_kleene_star(fsm_term_negation(fsm_symbol(string))),fsm_concat(fsm_symbol(string),fsm_kleene_star(fsm_term_negation(fsm_symbol(string))))))));

921}

923struct fsm *fsm_logical_precedence(char *string1, char *string2) {
  /* x < y = \y* x \y* [x | y Q* x] ?* */
  /*          1  2  3        4           5 */
  
  return(fsm_concat(fsm_kleene_star(fsm_term_negation(fsm_symbol(string2))),fsm_concat(fsm_symbol(string1),fsm_concat(fsm_kleene_star(fsm_term_negation(fsm_symbol(string2))),fsm_concat(fsm_union(fsm_symbol(string1),fsm_concat(fsm_symbol(string2),fsm_concat(union_quantifiers(),fsm_symbol(string1)))),fsm_universal())))));

929/*    1,3   fsm_kleene_star(fsm_term_negation(fsm_symbol(string2))) */
930/*        2 = fsm_symbol(string1) */
931/*        5 = fsm_universal() */
932/* 4 =    fsm_union(fsm_symbol(string1),fsm_concat(fsm_symbol(string2),fsm_concat(union_quantifiers(),fsm_symbol(string1)))) */

934}

936/** Logical equivalence, i.e. where two variables span the same substring */
937/** x = y = ?* [x y|y x]/Q ?* [x y|y x]/Q ?* */
938struct fsm *fsm_logical_eq(char *string1, char *string2) {
return(fsm_concat(fsm_universal(),fsm_concat(fsm_ignore(fsm_union(fsm_concat(fsm_symbol(string1),fsm_symbol(string2)),fsm_concat(fsm_symbol(string2),fsm_symbol(string1))),union_quantifiers(),OP_IGNORE_ALL1),fsm_concat(fsm_universal(),fsm_concat(fsm_ignore(fsm_union(fsm_concat(fsm_symbol(string1),fsm_symbol(string2)),fsm_concat(fsm_symbol(string2),fsm_symbol(string1))),union_quantifiers(),OP_IGNORE_ALL1),fsm_universal())))));
940}
