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

Bug Summary

File:	minimize.c
Warning:	line 155, column 24 Access to field 'index' results in a dereference of a null pointer (loaded from variable 'Agenda_head')

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 minimize.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/minimize.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 <stdlib.h>
19#include <assert.h>
20#include <limits.h>
21#include <stdint.h>
22#include "foma.h"

24static struct fsm *fsm_minimize_brz(struct fsm *net);
25static struct fsm *fsm_minimize_hop(struct fsm *net);
26static struct fsm *rebuild_machine(struct fsm *net);

28static int *single_sigma_array, *double_sigma_array, *memo_table, *temp_move, *temp_group, maxsigma, epsilon_symbol, num_states, num_symbols, num_finals, mainloop, total_states;

30static _Bool *finals;

32struct statesym {
  int target;
  unsigned short int symbol;
  struct state_list *states;
  struct statesym *next;
37};

39struct state_list {
  int state;
  struct state_list *next;
42};

44struct p {
  struct e *first_e;
  struct e *last_e;
  struct p *current_split;
  struct p *next;
  struct agenda *agenda;
  int count;
  int t_count;
  int inv_count;
  int inv_t_count;
54};

56struct e {
struct p *group;
struct e *left;
struct e *right;
int inv_count;
61};

63struct agenda {
struct p *p;
struct agenda *next;
_Bool index;
67};

69struct trans_list {
  int inout;
  int source;
72} *trans_list_minimize;

74struct trans_array {
  struct trans_list *transitions;
  unsigned int size;
  unsigned int tail;
78} *trans_array_minimize;



82static struct p *P, *Phead, *Pnext, *current_w;
83static struct e *E;
84static struct agenda *Agenda_head, *Agenda_top, *Agenda_next, *Agenda;

86static INLINEinline int refine_states(int sym);
87static void init_PE();
88static void agenda_add(struct p *pptr, int start);
89static void sigma_to_pairs(struct fsm *net);
90/* static void single_symbol_to_symbol_pair(int symbol, int *symbol_in, int *symbol_out); */
91static INLINEinline int symbol_pair_to_single_symbol(int in, int out);
92static void generate_inverse(struct fsm *net);

94struct fsm *fsm_minimize(struct fsm *net) {
  extern int g_minimal;
  extern int g_minimize_hopcroft;

  if (net == NULL((void*)0)) { return NULL((void*)0); }
1
Assuming 'net' is not equal to NULL→
2
←
Taking false branch→
  /* The network needs to be deterministic and trim before we minimize */
  if (net->is_deterministic != YES1)
3
←
Assuming field 'is_deterministic' is equal to YES→
4
←
Taking false branch→
      net = fsm_determinize(net);
  if (net->is_pruned != YES1)
5
←
Assuming field 'is_pruned' is equal to YES→
      net = fsm_coaccessible(net);
  if (net->is_minimized != YES1 && g_minimal == 1) {
6
←
Assuming field 'is_minimized' is not equal to YES→
7
←
Assuming 'g_minimal' is equal to 1→
8
←
Taking true branch→
      if (g_minimize_hopcroft != 0) {
9
←
Assuming 'g_minimize_hopcroft' is not equal to 0→
10
←
Taking true branch→
          net = fsm_minimize_hop(net);
11
←
Calling 'fsm_minimize_hop'→
      }
      else
          net = fsm_minimize_brz(net);
      fsm_update_flags(net,YES1,YES1,YES1,YES1,UNK2,UNK2);
  }
  return(net);
113}

115static struct fsm *fsm_minimize_brz(struct fsm *net) {
  return(fsm_determinize(fsm_reverse(fsm_determinize(fsm_reverse(net)))));
117}

119static struct fsm *fsm_minimize_hop(struct fsm *net) {

  struct e *temp_E;
  struct trans_array *tptr;
  struct trans_list *transitions;
  int i,j,minsym,next_minsym,current_i, stateno, thissize, source;
  unsigned int tail;

  fsm_count(net);
  if (net->finalcount == 0)  {
12
←
Assuming field 'finalcount' is not equal to 0→
13
←
Taking false branch→
fsm_destroy(net);
return(fsm_empty_set());
  }

  num_states = net->statecount;

  P = NULL((void*)0);

  /*
     1. generate the inverse lookup table
     2. generate P and E (partitions, states linked list)
     3. Init Agenda = {Q, Q-F}
     4. Split until Agenda is empty
  */

  sigma_to_pairs(net);

  init_PE();
14
←
Calling 'init_PE'→
22
←
Returning from 'init_PE'→

  if (total_states22.1
'total_states' is not equal to 'num_states'
 == num_states) {
23
←
Taking false branch→
      goto bail;
  }

  generate_inverse(net);


  Agenda_head->index = 0;
24
←
Access to field 'index' results in a dereference of a null pointer (loaded from variable 'Agenda_head')
  if (Agenda_head->next != NULL((void*)0))
      Agenda_head->next->index = 0;

  for (Agenda = Agenda_head; Agenda != NULL((void*)0); ) {
      /* Remove current_w from agenda */
      current_w = Agenda->p;
      current_i = Agenda->index;
      Agenda->p->agenda = NULL((void*)0);
      Agenda = Agenda->next;

      /* Store current group state number in tmp_group */
      /* And figure out minsym */
      /* If index is 0 we start splitting from the first symbol */
      /* Otherwise we split from where we left off last time */

      thissize = 0;
      minsym = INT_MAX2147483647;
      for (temp_E = current_w->first_e; temp_E != NULL((void*)0); temp_E = temp_E->right) {
          stateno = temp_E - E;
          *(temp_group+thissize) = stateno;
          thissize++;
          tptr = trans_array_minimize+stateno;
          /* Clear tails if symloop should start from 0 */
          if (current_i == 0)
              tptr->tail = 0;

          tail = tptr->tail;
          transitions = (tptr->transitions)+tail;
          if (tail < tptr->size && transitions->inout < minsym) {
              minsym = transitions->inout;
          }
      }

      for (next_minsym = INT_MAX2147483647; minsym != INT_MAX2147483647 ; minsym = next_minsym, next_minsym = INT_MAX2147483647) {

          /* Add states to temp_move */
          for (i = 0, j = 0; i < thissize; i++) {
              tptr = trans_array_minimize+*(temp_group+i);
              tail = tptr->tail;
              transitions = (tptr->transitions)+tail;
              while (tail < tptr->size && transitions->inout == minsym) {
                  source = transitions->source;
                  if (*(memo_table+(source)) != mainloop) {
                      *(memo_table+(source)) = mainloop;
                      *(temp_move+j) = source;
                      j++;
                  }
                  tail++;
                  transitions++;
              }
              tptr->tail = tail;
              if (tail < tptr->size && transitions->inout < next_minsym) {
                  next_minsym = transitions->inout;
              }
          }
          if (j == 0) {
              continue;
          }
          mainloop++;
          if (refine_states(j) == 1) {
              break; /* break loop if we split current_w */
          }
      }
      if (total_states == num_states) {
          break;
      }
  }

  net = rebuild_machine(net);

  free(trans_array_minimize);
  free(trans_list_minimize);

bail:

  free(Agenda_top);

  free(memo_table);
  free(temp_move);
  free(temp_group);


  free(finals);
  free(E);
  free(Phead);
  free(single_sigma_array);
  free(double_sigma_array);

  return(net);
245}

247static struct fsm *rebuild_machine(struct fsm *net) {
int i,j, group_num, source, target, new_linecount = 0, arccount = 0;
struct fsm_state *fsm;
struct p *myp;
struct e *thise;

if (net->statecount == total_states) {
    return(net);
}
fsm = net->states;

/* We need to make sure state 0 is first in its group */
/* to get the proper numbering of states */

if (E->group->first_e != E) {
  E->group->first_e = E;
}

/* Recycling t_count for group numbering use here */

group_num = 1;
myp = P;
while (myp != NULL((void*)0)) {
  myp->count = 0;
  myp = myp->next;
}

for (i=0; (fsm+i)->state_no != -1; i++) {
  thise = E+((fsm+i)->state_no);
  if (thise->group->first_e == thise) {
    new_linecount++;
    if ((fsm+i)->start_state == 1) {
thise->group->t_count = 0;
thise->group->count = 1;
    } else if (thise->group->count == 0) {
thise->group->t_count = group_num++;
thise->group->count = 1;
    }
  }
}

for (i=0, j=0; (fsm+i)->state_no != -1; i++) {
  thise = E+((fsm+i)->state_no);
  if (thise->group->first_e == thise) {
    source = thise->group->t_count;
    target = ((fsm+i)->target == -1) ? -1 : (E+((fsm+i)->target))->group->t_count;
    add_fsm_arc(fsm, j, source, (fsm+i)->in, (fsm+i)->out, target, finals[(fsm+i)->state_no], (fsm+i)->start_state);
    arccount = ((fsm+i)->target == -1) ? arccount : arccount+1;
    j++;
  }
}

add_fsm_arc(fsm, j, -1, -1, -1, -1, -1, -1);
fsm = realloc(fsm,sizeof(struct fsm_state)*(new_linecount+1));
net->states = fsm;
net->linecount = j+1;
net->arccount = arccount;
net->statecount = total_states;
return(net);
306}

308static INLINEinline int refine_states(int invstates) {
  int i, selfsplit;
  struct e *thise;
  struct p *tP, *newP = NULL((void*)0);

/*
   1. add inverse(P,a) to table of inverses, disallowing duplicates
   2. first pass on S, touch each state once, increasing P->t_count
   3. for each P where counter != count, split and add to agenda
*/

/* Inverse to table of inverses */
selfsplit = 0;

/* touch and increase P->counter */
for (i=0; i < invstates; i++) {
  ((E+(*(temp_move+i)))->group)->t_count++;
  ((E+(*(temp_move+i)))->group)->inv_t_count += ((E+(*(temp_move+i)))->inv_count);
  assert((E+(*(temp_move+i)))->group->t_count <= (E+(*(temp_move+i)))->group->count)(((E+(*(temp_move+i)))->group->t_count <= (E+(*(temp_move
+i)))->group->count) ? (void) (0) : __assert_fail ("(E+(*(temp_move+i)))->group->t_count <= (E+(*(temp_move+i)))->group->count"
, "/tmp/build/foma/foma-0.10.0+g279~a2d32b38/minimize.c", 326
, __extension__ __PRETTY_FUNCTION__));
}

/* Split (this is the tricky part) */

for (i=0; i < invstates; i++) {

  thise = E+*(temp_move+i);
  tP = thise->group;

  /* Do we need to split?
     if we've touched as many states as there are in the partition
     we don't split */

  if (tP->t_count == tP->count) {
    tP->t_count = 0;
    tP->inv_t_count = 0;
    continue;
  }

  if ((tP->t_count != tP->count) && (tP->count > 1) && (tP->t_count > 0)) {

      /* Check if we already split this */
      newP = tP->current_split;
      if (newP == NULL((void*)0)) {
          /* printf("tP [%i] newP [%i]\n",tP->inv_count,tP->inv_t_count); */
          /* Create new group newP */
          total_states++;
          if (total_states == num_states)
              return(1); /* Abort now, machine is already minimal */
          tP->current_split = Pnext++;
          newP = tP->current_split;
          newP->first_e = newP->last_e = thise;
          newP->count = 0;
          newP->inv_count = tP->inv_t_count;
          newP->inv_t_count = 0;
          newP->t_count = 0;
          newP->current_split = NULL((void*)0);
          newP->agenda = NULL((void*)0);

          /* Add to agenda */

          /* If the current block (tP) is on the agenda, we add both back */
          /* to the agenda */
          /* In practice we need only add newP since tP stays where it is */
          /* However, we mark the larger one as not starting the symloop */
          /* from zero */
          if (tP->agenda != NULL((void*)0)) {
              /* Is tP smaller */
              if (tP->inv_count < tP->inv_t_count) {
                  agenda_add(newP, 1);
                  tP->agenda->index = 0;
              }
              else {
                  agenda_add(newP, 0);
              }
              /* In the event that we're splitting the partition we're currently */
              /* splitting with, we can simply add both new partitions to the agenda */
              /* and break out of the entire sym loop after we're */
              /* done with the current sym and move on with the agenda */
              /* We process the larger one for all symbols */
              /* and the smaller one for only the ones remaining in this symloop */

          } else if (tP == current_w) {
              agenda_add(((tP->inv_count < tP->inv_t_count) ? tP : newP),0);
              agenda_add(((tP->inv_count >= tP->inv_t_count) ? tP : newP),1);
              selfsplit = 1;
          } else {
              /* If the block is not on the agenda, we add */
              /* the smaller of tP, newP and start the symloop from 0 */
              agenda_add((tP->inv_count < tP->inv_t_count ? tP : newP),0);
          }
          /* Add to middle of P-chain */
          newP->next = P->next;
          P->next = newP;
      }

      thise->group = newP;
      newP->count++;

      /* need to make tP->last_e point to the last untouched e */
      if (thise == tP->last_e)
          tP->last_e = thise->left;
      if (thise == tP->first_e)
          tP->first_e = thise->right;

      /* Adjust links */
      if (thise->left != NULL((void*)0))
          thise->left->right = thise->right;
      if (thise->right != NULL((void*)0))
          thise->right->left = thise->left;

      if (newP->last_e != thise) {
          newP->last_e->right = thise;
          thise->left = newP->last_e;
          newP->last_e = thise;
      }

      thise->right = NULL((void*)0);
      if (newP->first_e == thise)
          thise->left = NULL((void*)0);

      /* Are we done for this block? Adjust counters */
      if (newP->count == tP->t_count) {
          tP->count = tP->count - newP->count;
          tP->inv_count = tP->inv_count - tP->inv_t_count;
          tP->current_split = NULL((void*)0);
          tP->t_count = 0;
          tP->inv_t_count = 0;
      }
  }
}
/* We return 1 if we just split the partition we were working with */
return (selfsplit);
440}

442static void agenda_add(struct p *pptr, int start) {

/* Use FILO strategy here */

struct agenda *ag;
//ag = malloc(sizeof(struct agenda));
ag = Agenda_next++;
if (Agenda != NULL((void*)0))
  ag->next = Agenda;
else
  ag->next = NULL((void*)0);
ag->p = pptr;
ag->index = start;
Agenda = ag;
pptr->agenda = ag;
457}

459static void init_PE() {
/* Create two members of P
   (nonfinals,finals)
   and put both of them on the agenda
*/

int i;
struct e *last_f, *last_nonf;
struct p *nonFP, *FP;
struct agenda *ag;

mainloop = 1;
memo_table = calloc(num_states,sizeof(int));
temp_move = calloc(num_states,sizeof(int));
temp_group = calloc(num_states,sizeof(int));
Phead = P = Pnext = calloc(num_states+1, sizeof(struct p));
nonFP = Pnext++;
FP = Pnext++;
nonFP->next = FP;
nonFP->count = num_states-num_finals;
FP->next = NULL((void*)0);
FP->count = num_finals;
FP->t_count = 0;
nonFP->t_count = 0;
FP->current_split = NULL((void*)0);
nonFP->current_split = NULL((void*)0);
FP->inv_count = nonFP->inv_count = FP->inv_t_count = nonFP->inv_t_count = 0;

/* How many groups can we put on the agenda? */
Agenda_top = Agenda_next = calloc(num_states*2, sizeof(struct agenda));
Agenda_head = NULL((void*)0);
15
←
Null pointer value stored to 'Agenda_head'→

P = NULL((void*)0);
total_states = 0;

if (num_finals15.1
'num_finals' is <= 0
 > 0) {
16
←
Taking false branch→
    ag = Agenda_next++;
    FP->agenda = ag;
    P = FP;
    P->next = NULL((void*)0);
    ag->p = FP;
    Agenda_head = ag;
    ag->next = NULL((void*)0);
    total_states++;
}
if (num_states - num_finals > 0) {
17
←
Assuming the condition is false→
18
←
Taking false branch→
    ag = Agenda_next++;
    nonFP->agenda = ag;
    ag->p = nonFP;
    ag->next = NULL((void*)0);
    total_states++;
    if (Agenda_head != NULL((void*)0)) {
        Agenda_head->next = ag;
        P->next = nonFP;
        P->next->next = NULL((void*)0);
    } else {
        P = nonFP;
        P->next = NULL((void*)0);
        Agenda_head = ag;
    }
}

/* Initialize doubly linked list E */
E = calloc(num_states,sizeof(struct e));

last_f = NULL((void*)0);
last_nonf = NULL((void*)0);

for (i=0; i18.1
'i' is >= 'num_states'
 < num_states; i++) {
19
←
Loop condition is false. Execution continues on line 550→
  if (finals[i]) {
    (E+i)->group = FP;
    (E+i)->left = last_f;
    if (i > 0 && last_f != NULL((void*)0))
last_f->right = (E+i);
    if (last_f == NULL((void*)0))
FP->first_e = (E+i);
    last_f = (E+i);
    FP->last_e = (E+i);
  } else {
    (E+i)->group = nonFP;
    (E+i)->left = last_nonf;
    if (i > 0 && last_nonf != NULL((void*)0))
last_nonf->right = (E+i);
    if (last_nonf == NULL((void*)0))
nonFP->first_e = (E+i);
    last_nonf = (E+i);
    nonFP->last_e = (E+i);
  }
  (E+i)->inv_count = 0;
}

if (last_f19.1
'last_f' is equal to NULL
 != NULL((void*)0))
20
←
Taking false branch→
  last_f->right = NULL((void*)0);
if (last_nonf20.1
'last_nonf' is equal to NULL
 != NULL((void*)0))
21
←
Taking false branch→
  last_nonf->right = NULL((void*)0);
554}

556static int trans_sort_cmp(const void *a, const void *b) {
return (((const struct trans_list *)a)->inout - ((const struct trans_list *)b)->inout);
558}

560static void generate_inverse(struct fsm *net) {

  struct fsm_state *fsm;
  struct trans_array *tptr;
  struct trans_list *listptr;

  int i, source, target, offsetcount, symbol, size;
  fsm = net->states;
  trans_array_minimize = calloc(net->statecount, sizeof(struct trans_array));
  trans_list_minimize = calloc(net->arccount, sizeof(struct trans_list));

  /* Figure out the number of transitions each one has */
  for (i=0; (fsm+i)->state_no != -1; i++) {
      if ((fsm+i)->target == -1) {
          continue;
      }
      target = (fsm+i)->target;
      (E+target)->inv_count++;
      (E+target)->group->inv_count++;
      (trans_array_minimize+target)->size++;
  }
  offsetcount = 0;
  for (i=0; i < net->statecount; i++) {
      (trans_array_minimize+i)->transitions = trans_list_minimize + offsetcount;
      offsetcount += (trans_array_minimize+i)->size;
  }
  for (i=0; (fsm+i)->state_no != -1; i++) {
      if ((fsm+i)->target == -1) {
          continue;
      }
      symbol = symbol_pair_to_single_symbol((fsm+i)->in,(fsm+i)->out);
      source = (fsm+i)->state_no;
      target = (fsm+i)->target;
      tptr = trans_array_minimize + target;
      ((tptr->transitions)+(tptr->tail))->inout = symbol;
      ((tptr->transitions)+(tptr->tail))->source = source;
      tptr->tail++;
  }
  /* Sort arcs */
  for (i=0; i < net->statecount; i++) {
      listptr = (trans_array_minimize+i)->transitions;
      size = (trans_array_minimize+i)->size;
      if (size > 1)
          qsort(listptr, size, sizeof(struct trans_list), trans_sort_cmp);
  }
605}

607static void sigma_to_pairs(struct fsm *net) {

int i, j, x, y, z, next_x = 0;
struct fsm_state *fsm;

fsm = net->states;

epsilon_symbol = -1;
maxsigma = sigma_max(net->sigma);

maxsigma++;

single_sigma_array = malloc(2*maxsigma*maxsigma*sizeof(int));
double_sigma_array = malloc(maxsigma*maxsigma*sizeof(int));

for (i=0; i < maxsigma; i++) {
  for (j=0; j< maxsigma; j++) {
    *(double_sigma_array+maxsigma*i+j) = -1;
  }
}

/* f(x) -> y,z sigma pair */
/* f(y,z) -> x simple entry */
/* if exists f(n) <-> EPSILON, EPSILON, save n */
/* symbol(x) x>=1 */

/* Forward mapping: */
/* *(double_sigma_array+maxsigma*in+out) */

/* Backmapping: */
/* *(single_sigma_array+(symbol*2) = in(symbol) */
/* *(single_sigma_array+(symbol*2+1) = out(symbol) */

/* Table for checking whether a state is final */

finals = calloc(num_states, sizeof(_Bool));
x = 0; num_finals = 0;
net->arity = 1;
for (i=0; (fsm+i)->state_no != -1; i++) {
  if ((fsm+i)->final_state == 1 && finals[(fsm+i)->state_no] != 1) {
    num_finals++;
    finals[(fsm+i)->state_no] = 1;
  }
  y = (fsm+i)->in;
  z = (fsm+i)->out;
  if (y != z || y == UNKNOWN1 || z == UNKNOWN1)
      net->arity = 2;
  if ((y == -1) || (z == -1))
    continue;
  if (*(double_sigma_array+maxsigma*y+z) == -1) {
    *(double_sigma_array+maxsigma*y+z) = x;
    *(single_sigma_array+next_x) = y;
    next_x++;
    *(single_sigma_array+next_x) = z;
    next_x++;
    if (y == EPSILON0 && z == EPSILON0) {
epsilon_symbol = x;
    }
    x++;
  }
}
num_symbols = x;
669}

671static INLINEinline int symbol_pair_to_single_symbol(int in, int out) {
return(*(double_sigma_array+maxsigma*in+out));
673}