path: root/src/bsr.c

#include "list.h"
#include "splist.h"
#include "util.h"
#include "ht.h"
#include "tuple.h"
#include "bsr.h"
#include <stdio.h>
#include <string.h>
#include <stdarg.h>

typedef luple5 first_type_bsr;
typedef luple6 second_type_bsr;

struct bsr_s {
  first_type_bsr *f;
  second_type_bsr *s;
};

bsr *
new_bsr(Grammar *g, NUM input_len, BOOL * const restrict errorp)
{
  NUM left_len = grammar_left_len(g);

  NUM max_alt_len = 0, max_rule_len = 0;

  for (NUM i = 0; i < left_len; i++) {
    NUM alt_len = rg_len(grammar_rule(g, i));
    if (alt_len > max_rule_len) max_rule_len = alt_len;
    for (NUM j = 0; j < alt_len; j++) {
      NUM jth_len = list_length(rg_nth(grammar_rule(g, i), j));
      if (jth_len > max_alt_len) max_alt_len = jth_len;
    }
  }

  bsr *bsrp = NULL;
  SAFE_MALLOC(bsr, bsrp, 1, *errorp = 1; return NULL;);

  NUM *first_lengths = NULL, *second_lengths = NULL;

  SAFE_MALLOC(NUM, first_lengths, 5, goto cleanup;);
  SAFE_MALLOC(NUM, second_lengths, 6, goto cleanup;);

  *(first_lengths) = left_len;
  *(first_lengths+1) = input_len;
  *(first_lengths+2) = input_len;
  *(first_lengths+3) = max_rule_len;
  *(first_lengths+4) = input_len;

  *(second_lengths) = left_len;
  *(second_lengths+1) = max_rule_len;
  *(second_lengths+2) = max_alt_len;
  *(second_lengths+3) = input_len;
  *(second_lengths+4) = input_len;
  *(second_lengths+5) = input_len;

  bsrp->f = new_luple5(first_lengths);

  if (bsrp->f == NULL) {
    fleprintf0("Fail to create luple5\n");
    goto cleanup;
  }

  first_lengths = NULL;

  bsrp->s = new_luple6(second_lengths);

  if (bsrp->s == NULL) {
    fleprintf0("Fail to create luple6\n");
    goto cleanup;
  }

  return bsrp;

 cleanup:
  *errorp = 1;

  if (first_lengths) free(first_lengths);
  if (second_lengths) free(second_lengths);

  if (bsrp->f) destroy_luple5(bsrp->f);
  if (bsrp->s) destroy_luple6(bsrp->s);
  if (bsrp) free(bsrp);

  return NULL;
}

void
destroy_bsr(bsr * const restrict bsrp)
{
  if (bsrp == NULL) return;

  /* destroy first type */
  destroy_luple5(bsrp->f);

  /* destroy second type */
  destroy_luple6(bsrp->s);

  free(bsrp);
}

/* X = non-terminal index, a = index of alternate, c = length of
   prefix */

/* i = left-extent of X, and j = right-extent.  k = the left-extent of
   the right-most terminal or non-terminal in the alternate
   corresponding to a. */

H_ATTR
BOOL
bsr_add(CCR_MOD(Grammar *) g, bsr * const restrict b, pair6 p6)
{
  NUM X = p6.x;
  NUM a = p6.y;
  NUM c = p6.z;
  NUM i = p6.u;
  NUM k = p6.v;
  NUM j = p6.w;

  if (X < 0 || X >= grammar_left_len(g)) {
    fleprintf("Invalid X: %ld\n", X);
    return 1;
  }

  if (a < 0 || a >= rg_len(grammar_rule(g, X))) {
    fleprintf("Invalid a: %ld\n", a);
    return 1;
  }

  if (c > list_length(rg_nth(grammar_rule(g, X), a)) || c < 0) {
    fleprintf("Invalid c: %ld\n", c);
    return 1;
  }

  BOOL errorp = 0;

  if (c == list_length(rg_nth(grammar_rule(g, X), a))) {
    /* first type BSR */
    /* fleprintf0("First type\n"); */
    if (add_to_luple5(b->f, (pair5) { X, i, j, a, k }, 1)) {
      fleprintf0("Fail to add to first type\n");
      goto cleanup;
    }
  } else {
    /* second type BSR */
    /* fleprintf0("Second type\n"); */
    if (add_to_luple6(b->s, (pair6) { X, a, c, i, j, k }, 1)) {
      fleprintf0("Fail to add to second type\n");
      goto cleanup;
    }
  }

  goto success;

 cleanup:
  errorp = 1;

 success:

  return errorp;
}

BOOL
bsr_find(CCR_MOD(bsr *) b, CCR_MOD(Grammar *) g,
         BOOL * const restrict errorp, pair6 p6)
{
  *errorp = 0;
  BOOL result = 0;
  NUM *resultp = NULL;

  NUM X = p6.x;
  NUM a = p6.y;
  NUM c = p6.z;
  NUM i = p6.u;
  NUM k = p6.v;
  NUM j = p6.w;

  if (X < 0 || X >= grammar_left_len(g)) {
    fleprintf("Invalid X: %ld\n", X);
    goto cleanup;
  }

  if (a < 0 || a >= rg_len(grammar_rule(g, X))) {
    fleprintf("Invalid a: %ld\n", a);
    goto cleanup;
  }

  if (c < 0 || c > list_length(rg_nth(grammar_rule(g, X), a))) {
    fleprintf("Invalid c: %ld\n", c);
    goto cleanup;
  }

  if (c == list_length(rg_nth(grammar_rule(g, X), a))) {
    /* first type */
    resultp = luple5_find(b->f, (pair5) { X, i, j, a, k });
    result = (resultp && *resultp) ? 1 : 0;
  } else {
    /* second type */
    resultp = luple6_find(b->s, (pair6) { X, a, c, i, j, k});
    result = (resultp && *resultp) ? 1 : 0;
  }

  goto success;

 cleanup:
  *errorp = 1;

 success:
  return result;
}

P_ATTR
BOOL
bsr_lookup(bsr * b, NUM X, NUM i, NUM j)
{
  return luple5_pf_3(b->f, (pair3) { X, i, j });
}

UNUSED
static void
print_sep()
{
  printf(" ");
}

static BOOL bsr_print_should_initialize_counter = 0;
static NUM bsr_print_line_len = 0;
static Grammar *bsr_print_grammar = NULL;

static void
print_bsr_f(pair5 label)
{
  static int counter = 0;

  if (bsr_print_should_initialize_counter) {
    counter = 0;
    bsr_print_should_initialize_counter = 0;
  }

  counter++;

  printf("(");
  print_name(list_nth(grammar_names(bsr_print_grammar),
                      label.x));
  printf(" := ");
  map_list_between
    (rg_nth (grammar_rule(bsr_print_grammar, label.x), label.u),
     print_tnt, print_sep);
  printf(", %ld, %ld, %ld)", label.y, label.v, label.z);

  if (counter == bsr_print_line_len) {
    counter = 0;
    printf("\n");
  } else {
    printf(", ");
  }
}

static void
print_bsr_s(pair6 label)
{
  static int counter = 0;

  if (bsr_print_should_initialize_counter) {
    counter = 0;
    bsr_print_should_initialize_counter = 0;
  }

  counter++;

  printf("(");
  print_name(list_nth(grammar_names(bsr_print_grammar),
                      label.x));
  printf(" := ");

#define RGLS rg_nth(grammar_rule(bsr_print_grammar, label.x),   \
                    label.y)

  for (NUM k = 0; k < label.z; k++) {
    print_tnt(*(list_array(RGLS)+k));
    if (k+1<label.z) printf(" ");
  }

  printf(" · ");

  for (NUM k = label.z; k < list_length(RGLS); k++) {
    print_tnt(*(list_array(RGLS)+k));
    if (k+1<list_length(RGLS)) printf(" ");
  }

  printf(", %ld, %ld, %ld)", label.u, label.w, label.v);

  if (counter == bsr_print_line_len) {
    counter = 0;
    printf("\n");
  } else {
    printf(", ");
  }

#undef RGLS

}

void
bsr_print(bsr *b, Grammar *g, NUM line_len)
{
  printf("Printing a BSR set...\n");

  bsr_print_grammar = g;
  bsr_print_should_initialize_counter = 1;
  bsr_print_line_len = line_len;

  printf("Printing the first type nodes...\n");

  NUM *len = NULL;

  len = luple5_len(b->f);

  for (NUM i = 0; i < *len; i++)
    for (NUM j = 0; j < *(len+1); j++)
      for (NUM k = 0; k < *(len+2); k++) {
        luple5_map_3(b->f, (pair3) { i, j, k }, print_bsr_f);
      }

  printf("\n\nPrinting the second type nodes...\n");

  bsr_print_should_initialize_counter = 1;

  len = luple6_len(b->s);

  for (NUM i = 0; i < *len; i++)
    for (NUM j = 0; j < *(len+1); j++)
      luple6_map_2(b->s, (pair2) { i, j }, -1, print_bsr_s);

  printf("\n");

  bsr_print_grammar = NULL;
  bsr_print_line_len = 0;
}