/***************************************************************
  CLOSURE.C

     This file containts CLOSURE routine of ZUBR.

     PART OF : ZUBR - Parsers generator for multiple syntax
                      language compilers .

     COMPILE : .

     NOTE    : NONE .

     Copyright (C) 1995 - 2026  by Andrey V.Kosteltsev.
     All Rights Reserved.
 ***************************************************************/
/*
  This file contant RUSSIAN letters( code-page: UTF-8 )
 ***************************************************************/

#include <defs.h>

#ifndef __NO_COMPILE


int      *itemset;     /* use in lr0.c */
int      *itemsetend;  /* use in lr0.c */
unsigned *ruleset;     /* use in lr0.c */

static unsigned *first_derives;
static unsigned *EFF;

/**************  Start of functions for debuging  **************/

#ifdef _DEBUG
void print_closure( int n )
/***************************************************************

 Description        : print closure

 Concepts           : print_closure() is used for debugging

 Use Global Variable: int *itemset;                | this file
                      int *itemsetend;             | this file

 Use Functions      :

 Parameters         : int n

 Return             : [void]

 ***************************************************************/
{
  register int *isp;

  mpu_fprintf( mpu_stdout, MPU_UCS2( "\n\nn = %d\n\n" ), n );
  for( isp = itemset; isp < itemsetend; isp++ )
    mpu_fprintf( mpu_stdout, MPU_UCS2( "   %d\n" ), *isp );

} /*******  End of print_closure( int n )  *********************/


void print_EFF( void )
/***************************************************************

 Description        : print EFF

 Concepts           : print_EFF() is used for debugging

 Use Global Variable: int    nsyms;                | main.c
                      int    nvars;                | main.c
                      int    start_symbol;         | main.c
                      char **symbol_name;          | main.c

 Use Functions      :

 Parameters         : [void]

 Return             : [void]

 ***************************************************************/
{
  register int       i, j;
  register unsigned *rowp;
  register unsigned  word;
  register unsigned  mask;

  mpu_fprintf( mpu_stdout,
               MPU_UCS2( "\n\nEpsilon Free Firsts\n" ) );

  for( i = start_symbol; i < nsyms; i++ )
  {
    mpu_fprintf( mpu_stdout,
                 MPU_UCS2( "\n%s" ), symbol_name[i] );
    rowp = EFF + ((i - start_symbol) * SIZE_IN_INT( nvars ));
    word = *rowp++;

    mask = 1;
    for( j = 0; j < nvars; j++ )
    {
      if( word & mask )
        mpu_fprintf( mpu_stdout,
                     MPU_UCS2( "  %s" ),
                     symbol_name[start_symbol + j] );

      mask <<= 1;
      if( mask == 0 )
      {
        word = *rowp++;
        mask = 1;
      }

    } /*  End of for( j = 0; j < nvars; j++ )  */
  } /*  End of for( i = start_symbol; i < nsyms; i++ )  */

} /*******  End of print_EFF( void )  **************************/


void print_first_derives( void )
/***************************************************************

 Description        : print first derives

 Concepts           : print_first_derives() is used for debugging

 Use Global Variable: int               nrules;    | main.c
                      int               nsyms;     | main.c
                      int               start_symbol; | main.c
                      char            **symbol_name; | main.c
                      static unsigned  *first_derives; | this file

 Use Functions      :

 Parameters         : [void]

 Return             : [void]

 ***************************************************************/
{
  register int       i;
  register int       j;
  register unsigned *rp;
  register unsigned  cword;
  register unsigned  mask;

  mpu_fprintf( mpu_stdout,
               MPU_UCS2( "\n\n\nFirst Derives\n" ) );

  for( i = start_symbol; i < nsyms; i++ )
  {
    mpu_fprintf( mpu_stdout,
                 MPU_UCS2( "\n%s derives\n" ), symbol_name[i] );
    rp = first_derives + i * SIZE_IN_INT( nrules );
    cword = *rp++;
    mask = 1;
    for( j = 0; j <= nrules; j++ )
    {
      if( cword & mask )
        mpu_fprintf( mpu_stdout, MPU_UCS2( "   %d\n" ), j );
      mask <<= 1;
      if( mask == 0 )
      {
        cword = *rp++;
        mask = 1;
      }
    } /*  End of for( j = 0; j <= nrules; j++ )  */
  } /*  End of for( i = start_symbol; i < nsyms; i++ )  */
  mpu_fflush( mpu_stdout );  /* stdio.h */

} /*******  End of print_first_derives( void )  ****************/

#endif

/***************  End of functions for debuging  ***************/


void set_EFF( void )
/***************************************************************

 Description        : set EFF

 Concepts           :

 Use Global Variable: int               nsyms;     | main.c
                      int               nvars;     | main.c
                      int               start_symbol; | main.c
                      int              *ritem;     | main.c
                      int              *rrhs;      | main.c
                      int             **derives;   | main.c
                      static unsigned  *EFF;       | this file

 Use Functions      : reflexive_transitive_closure (unsigned *, int);
                                                   | warshall.c
 Parameters         : [void]

 Return             : [void]

 ***************************************************************/
{
  register unsigned *row;
  register int       symbol;
  register int      *sp;
  register int       rowsize, i, rule;

  rowsize = SIZE_IN_INT( nvars );
  EFF = NEW2( nvars * rowsize, unsigned );

  row = EFF;
  for( i = start_symbol; i < nsyms; i++ )
  {
    sp = derives[i];
    for( rule = *sp; rule > 0; rule = *++sp )
    {
      symbol = ritem[rrhs[rule]];
      if( ISVAR(symbol) )
      {
        symbol -= start_symbol;
        SETBIT( row, symbol );
      }
    }
    row += rowsize;
  }
  reflexive_transitive_closure( EFF, nvars );

#ifdef _DEBUG
  print_EFF();
#endif

} /*******  End of set_EFF( void )  ****************************/


void set_first_derives( void )
/***************************************************************

 Description        : set first derives

 Concepts           :

 Use Global Variable: int               nrules;    | main.c
                      int               nsyms;     | main.c
                      int               ntokens;   | main.c
                      int               nvars;     | main.c
                      int               start_symbol; | main.c
                      int             **derives;   | main.c
                      static unsigned  *first_derives; | this file

 Use Functions      : void set_EFF( void );        | this file

 Parameters         : [void]

 Return             : [void]

 ***************************************************************/
{
  register unsigned *rrow;
  register unsigned *vrow;
  register int       j;
  register unsigned  mask;
  register unsigned  cword;
  register int      *rp;

  int rule;
  int i;
  int rulesetsize;
  int varsetsize;

  rulesetsize   = SIZE_IN_INT( nrules );
  varsetsize    = SIZE_IN_INT( nvars );
  first_derives = NEW2( nvars * rulesetsize, unsigned ) -
                 ntokens * rulesetsize;

  set_EFF();

  rrow = first_derives + ntokens * rulesetsize;
  for( i = start_symbol; i < nsyms; i++ )
  {
    vrow = EFF + ((i - ntokens) * varsetsize);
    cword = *vrow++;
    mask = 1;
    for( j = start_symbol; j < nsyms; j++ )
    {
      if( cword & mask )
      {
        rp = derives[j];
        while( (rule = *rp++) >= 0 )
        {
          SETBIT( rrow, rule );
        }
      }

      mask <<= 1;
      if( mask == 0 )
      {
        cword = *vrow++;
        mask = 1;
      }
    }

    vrow += varsetsize;
    rrow += rulesetsize;
  }

#ifdef _DEBUG
  print_first_derives();
#endif

  FREE( EFF );

} /*******  End of set_first_derives( void )  ******************/


void closure( int *nucleus, int n )
/***************************************************************

 Description        : closure

 Concepts           :

 Use Global Variable: int              nrules;     | main.c
                      int             *ritem;      | main.c
                      int             *rrhs;       | main.c
                      int             *itemset;    | this file
                      int             *itemsetend; | this file
                      unsigned        *ruleset;    | this file
                      static unsigned *first_derives; | this file

 Use Functions      :

 Parameters         : int *nucleus, int n

 Return             : [void]

 ***************************************************************/
{
  register int       ruleno;
  register unsigned  word;
  register unsigned  mask;
  register int      *csp;
  register unsigned *dsp;
  register unsigned *rsp;
  register int       rulesetsize;

  int      *csend;
  unsigned *rsend;
  int       symbol;
  int       itemno;

  rulesetsize = SIZE_IN_INT( nrules );
  rsp = ruleset;
  rsend = ruleset + rulesetsize;
  for( rsp = ruleset; rsp < rsend; rsp++ ) *rsp = 0;

  csend = nucleus + n;
  for( csp = nucleus; csp < csend; ++csp )
  {
    symbol = ritem[*csp];
    if( ISVAR(symbol) )
    {
      dsp = first_derives + symbol * rulesetsize;
      rsp = ruleset;
      while( rsp < rsend ) *rsp++ |= *dsp++;
    }
  }

  ruleno = 0;
  itemsetend = itemset;
  csp = nucleus;
  for( rsp = ruleset; rsp < rsend; ++rsp )
  {
    word = *rsp;
    if( word == 0 ) ruleno += ZUBR_BITS_PER_INT;
    else
    {
      mask = 1;
      while( mask )
      {
        if( word & mask )
        {
          itemno = rrhs[ruleno];
          while( csp < csend && *csp < itemno )
            *itemsetend++ = *csp++;
          *itemsetend++ = itemno;
          while( csp < csend && *csp == itemno ) ++csp;
        }
        mask <<= 1;
        ++ruleno;
      }
    }
  }

  while( csp < csend ) *itemsetend++ = *csp++;

#ifdef _DEBUG
  print_closure( n );
#endif

} /*******  End of closure( int *nucleus, int n )  *************/


void finalize_closure( void )
/***************************************************************

 Description        : finalize closure

 Concepts           :

 Use Global Variable: int              nrules;     | main.c
                      int              ntokens;    | main.c
                      int             *itemset;    | this file
                      unsigned        *ruleset;    | this file
                      static unsigned *first_derives; | this file

 Use Functions      :

 Parameters         :

 Return             : [void]

 ***************************************************************/
{
  FREE( itemset );
  FREE( ruleset);
  FREE( first_derives + ntokens * SIZE_IN_INT(nrules) );

} /*******  End of finalize_closure( void )  *******************/

#endif /* __NO_COMPILE */

/*******************  END OF FILE CLOSURE.C  *******************/