BSR

A prototype of BSR is roughly finished.

1 files changed, 601 insertions, 1 deletions

diff --git a/src/bsr.c b/src/bsr.c
index 908309f..e737d7a 100644
--- a/src/bsr.c
+++ b/src/bsr.c
@@ -1,3 +1,603 @@
+#include "list.h"
+#include "util.h"
+#include "ht.h"
 #include "bsr.h"
+#include <stdio.h>
+#include <string.h>
+#include <stdarg.h>
 
-int place(int x) { return x; }
+typedef struct first_type_bsr_s first_type_bsr;
+typedef struct second_type_bsr_s second_type_bsr;
+
+typedef struct first_type_array_element_s first_type_array_element;
+
+/* The keys of the table are (i, k) and values are hash tables whose
+   keys are (a, j) such that (X, a, i, j, k) belongs to the set. */
+struct first_type_array_element_s {
+  ht *table;
+  BOOL initialized;
+};
+
+struct first_type_bsr_s {
+  NUM len;
+  first_type_array_element *array;
+};
+
+/* Arrrrgh! */
+typedef struct second_arrarrarr_element_s second_arrarrarr_element;
+
+/* The keys are (i, k) and the values are hash tables whose keys are
+   those j such that
+
+   (X, a, c, i, j, k)
+
+   belongs to the set. */
+struct second_arrarrarr_element_s {
+  ht *table;
+  BOOL initialized;
+};
+
+typedef struct second_array_array_element_s \
+second_array_array_element;
+
+struct second_array_array_element_s {
+  NUM len;
+  second_arrarrarr_element *array;
+  BOOL initialized;
+};
+
+typedef struct second_type_array_element_s second_type_array_element;
+
+struct second_type_array_element_s {
+  NUM len;
+  second_array_array_element *array;
+  BOOL initialized;
+};
+
+struct second_type_bsr_s {
+  NUM len;
+  second_type_array_element *array;
+};
+
+struct bsr_s {
+   /* bsr_type type; */
+  /* union { */
+  first_type_bsr f;
+  second_type_bsr s;
+  /* } data; */
+};
+
+bsr *
+new_bsr(BOOL * const restrict errorp, Grammar *g)
+{
+  NUM left_len = grammar_left_len(g);
+
+  bsr *bsrp = NULL;
+  SAFE_MALLOC(bsr, bsrp, 1, *errorp = 1; return NULL;);
+
+  /* first type */
+  bsrp->f.len = left_len;
+  SAFE_MALLOC(first_type_array_element,
+              bsrp->f.array, bsrp->f.len, goto cleanup;);
+
+  /* ensure every bit is zero, including the initialized field */
+  memset(bsrp->f.array, 0,
+         sizeof(first_type_array_element) * bsrp->f.len);
+
+  /* second type */
+  bsrp->s.len = left_len;
+  SAFE_MALLOC(second_type_array_element,
+              bsrp->s.array, bsrp->s.len, goto cleanup;);
+  memset(bsrp->s.array, 0,
+         sizeof(second_type_array_element) * bsrp->s.len);
+
+  for (NUM i = 0; i < left_len; i++)
+    (bsrp->s.array+i)->len = rg_len(grammar_rule(g, i));
+
+  return bsrp;
+
+ cleanup:
+  *errorp = 1;
+
+  if (bsrp->f.array) free(bsrp->f.array);
+  if (bsrp->s.array) free(bsrp->s.array);
+  if (bsrp) free(bsrp);
+
+  return NULL;
+}
+
+void
+destroy_bsr(bsr * const restrict bsrp)
+{
+  /* destroy first type */
+  for (NUM i = 0; i < bsrp->f.len; i++) {
+#define ELEMENT (bsrp->f.array+i)
+    if (ELEMENT->initialized) {
+      /* destroy every hash table values as well */
+
+#define HTS ((ht **) ht_values(ELEMENT->table))
+
+      for (NUM j = 0; j < ht_size(ELEMENT->table); j++)
+        destroy_ht(*(HTS+j), DESTROY_KEY_SELF);
+
+      destroy_ht(ELEMENT->table, DESTROY_KEY_SELF);
+    }
+  }
+
+#undef ELEMENT
+#undef HTS
+
+  free(bsrp->f.array);
+
+  /* destroy second type */
+
+  for (NUM i = 0; i < bsrp->s.len; i++) {
+
+#define ELEMENT (bsrp->s.array+i)
+
+    if (ELEMENT->initialized) {
+      for (NUM j = 0; j < ELEMENT->len; j++) {
+
+#define SELE (ELEMENT->array+j)
+
+        if (SELE->initialized) {
+          for (NUM k = 0; k < SELE->len; k++) {
+
+#define HELE (SELE->array+k)
+
+            if (HELE->initialized) {
+
+#define HTS ((ht **) ht_values(HELE->table))
+
+              for (NUM ell = 0; ell < ht_size(HELE->table); ell++)
+                destroy_ht(*(HTS+ell), DESTROY_KEY_SELF);
+
+              destroy_ht(HELE->table, DESTROY_KEY_SELF);
+            }
+          }
+
+          free(SELE->array);
+        }
+      }
+
+      free(ELEMENT->array);
+    }
+  }
+
+#undef ELEMENT
+#undef SELE
+#undef HELE
+#undef HTS
+
+  free(bsrp->s.array);
+
+  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. */
+
+BOOL
+bsr_add(CCR_MOD(Grammar *) g, bsr * const restrict b,
+        NUM X, NUM a, NUM c, NUM i, NUM k, NUM j)
+{
+  if (X < 0 || X >= b->f.len) {
+    fleprintf("Invalid X: %ld\n", X);
+    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;
+
+  ht *value_table = NULL;
+
+  pair2 *p2 = NULL, p21 = { 0 }, p22 = { 0 };
+
+  NUM *p1 = NULL, p11 = 0;
+
+  if (c == list_length(rg_nth(grammar_rule(g, X), a))) {
+    /* first type BSR */
+    /* fleprintf0("First type\n"); */
+
+#define ARR (b->f.array+X)
+
+    if (!(ARR->initialized)) {
+      ARR->initialized = 1;
+      ARR->table = new_ht2(HT_INIT_CAP);
+
+      if (ARR->table == NULL) {
+        fleprintf0("Fail to get new ht\n");
+        goto cleanup;
+      }
+
+      value_table = new_ht2(HT_INIT_CAP);
+
+      if (value_table == NULL) {
+        fleprintf0("Fail to get new ht\n");
+        goto cleanup;
+      }
+
+      NEW_P2(p2, a, k, goto cleanup;);
+      if (ht_insert(value_table, p2, (void*)1)) goto cleanup;
+
+      NEW_P2(p2, i, j, goto cleanup;);
+
+      if (ht_insert(ARR->table, p2, value_table)) goto cleanup;
+      /* don't destroy the pointers once they have been inserted */
+      value_table = NULL;
+      p2 = NULL;
+    } else {
+      p21.x = i;
+      p21.y = j;
+
+      if (ht_find(ARR->table, &p21) == NULL) {
+        value_table = new_ht2(HT_INIT_CAP);
+
+        if (value_table == NULL) {
+          fleprintf0("Fail to get new ht\n");
+          goto cleanup;
+        }
+
+        NEW_P2(p2, a, k, goto cleanup;);
+        if (ht_insert(value_table, p2, (void*)1)) goto cleanup;
+
+        NEW_P2(p2, i, j, goto cleanup;);
+        if (ht_insert(ARR->table, p2, value_table)) goto cleanup;
+
+        /* don't destroy the pointers once they have been inserted */
+        value_table = NULL;
+        p2 = NULL;
+      } else {
+        p22.x = a;
+        p22.y = k;
+
+        if (ht_find(ht_find(ARR->table, &p21), &p22) == NULL) {
+          NEW_P2(p2, a, k, goto cleanup;);
+          if (ht_insert(ht_find(ARR->table, &p21), p2, (void*)1))
+            goto cleanup;
+
+          /* don't destroy the pointer once it has been inserted */
+          p2 = NULL;
+        } else {
+          /* this element is already present */
+        }
+      }
+    }
+
+#undef ARR
+
+  } else {
+    /* second type BSR */
+    /* fleprintf0("Second type\n"); */
+
+#define AR (b->s.array+X)
+
+    if (!(AR->initialized)) {
+      SAFE_MALLOC(second_array_array_element,
+                  AR->array, AR->len,
+                  goto cleanup;);
+      memset(AR->array, 0,
+             sizeof(second_array_array_element)*(AR->len));
+      AR->initialized = 1;
+    }
+
+#define ARR (AR->array+a)
+
+    if (a < 0 || a >= rg_len(grammar_rule(g, X))) {
+      fleprintf("Invalid a: %ld\n", a);
+      goto cleanup;
+    }
+
+    ARR->len = list_length(rg_nth(grammar_rule(g, X), a));
+
+    if (!(ARR->initialized)) {
+      SAFE_MALLOC(second_arrarrarr_element,
+                  ARR->array, ARR->len,
+                  goto cleanup;);
+      memset(ARR->array, 0,
+             sizeof(second_arrarrarr_element)*(ARR->len));
+      ARR->initialized = 1;
+    }
+
+#define ARRR (ARR->array+c)
+
+    if (!(ARRR->initialized)) {
+      ARRR->table = new_ht2(HT_INIT_CAP);
+
+      if (ARRR->table == NULL) {
+        fleprintf0("Fail to get new ht\n");
+        goto cleanup;
+      }
+
+      ARRR->initialized = 1;
+    }
+
+    p21.x = i;
+    p21.y = j;
+
+    if (ht_find(ARRR->table, &p21) == NULL) {
+      value_table = new_ht(HT_INIT_CAP, 0);
+
+      if (value_table == NULL) {
+        fleprintf0("Fail to get new ht\n");
+        goto cleanup;
+      }
+
+      NEW_P2(p2, i, j, goto cleanup;);
+
+      if (ht_insert(ARRR->table, p2, value_table)) {
+        fleprintf0("Fail to insert into table\n");
+        goto cleanup;
+      }
+      value_table = NULL;
+      p2 = NULL;
+    }
+
+    p11 = k;
+
+    if (ht_find(ht_find(ARRR->table, &p21),
+                &p11) == NULL) {
+      SAFE_MALLOC(NUM, p1, 1, goto cleanup;);
+      *p1 = k;
+      if (ht_insert(ht_find(ARRR->table, &p21),
+                    p1, (void *)1)) {
+        fleprintf0("Fail to insert into table\n");
+        goto cleanup;
+      }
+      p1 = NULL;
+    }
+
+#undef AR
+#undef ARR
+#undef ARRR
+  }
+
+  goto success;
+
+ cleanup:
+  errorp = 1;
+
+ success:
+
+  if (value_table) destroy_ht(value_table, DESTROY_KEY_SELF);
+  if (p2) free(p2);
+  if (p1) free(p1);
+
+  return errorp;
+}
+
+BOOL
+bsr_find(CCR_MOD(bsr *) b, CCR_MOD(Grammar *) g,
+         BOOL * const restrict errorp,
+         NUM X, NUM a, NUM c, NUM i, NUM k, NUM j)
+{
+  *errorp = 0;
+  BOOL result = 0;
+
+  if (X < 0 || X >= b->f.len) {
+    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;
+  }
+
+  pair2 p21 = { 0 }, p22 = { 0 };
+  NUM p11 = 0;
+
+  if (c == list_length(rg_nth(grammar_rule(g, X), a))) {
+    /* first type */
+#define ARR (b->f.array+X)
+
+    if (!(ARR->initialized)) {
+      goto success;
+    } else {
+      p21.x = i;
+      p21.y = j;
+
+      if (ht_find(ARR->table, &p21) == NULL) {
+        goto success;
+      } else {
+        p22.x = a;
+        p22.y = k;
+
+        if (ht_find(ht_find(ARR->table, &p21), &p22) == NULL) {
+          goto success;
+        } else {
+          result = 1;
+          goto success;
+        }
+      }
+    }
+
+#undef ARR
+
+  } else {
+    /* second type */
+
+#define AR (b->s.array+X)
+
+    if (!(AR->initialized)) {
+      goto success;
+    }
+
+#define ARR (AR->array+a)
+
+    ARR->len = list_length(rg_nth(grammar_rule(g, X), a));
+
+    if (!(ARR->initialized)) goto success;
+
+#define ARRR (ARR->array+c)
+
+    if (!(ARRR->initialized)) goto success;
+
+    p21.x = i;
+    p21.y = j;
+
+    if (ht_find(ARRR->table, &p21) == NULL) goto success;
+
+    p11 = k;
+
+    if (ht_find(ht_find(ARRR->table, &p21), &p11) == NULL)
+      goto success;
+
+    result = 1;
+
+    goto success;
+
+    #undef AR
+    #undef ARR
+    #undef ARRR
+  }
+
+ cleanup:
+  *errorp = 1;
+
+ success:
+  return result;
+}
+
+void
+bsr_print(CCR_MOD(bsr *) b, CCR_MOD(Grammar *) g, NUM line_len)
+{
+  printf("Printing a BSR set...\n");
+
+  NUM count = 0;
+
+  /* print first type BSR */
+  for (NUM i = 0; i < b->f.len; i++) {
+
+#define ELEMENT (b->f.array+i)
+
+    if (ELEMENT->initialized) {
+
+#define KEYS ((pair2 **) ht_keys(ELEMENT->table))
+#define VALUES ((ht **) ht_values(ELEMENT->table))
+#define SIZE (ht_size(ELEMENT->table))
+
+      for (NUM j = 0; j < SIZE; j++) {
+
+#define VALUE_TABLE (*(VALUES+j))
+#define VALUE_TABLE_KEYS ((pair2 **) ht_keys(VALUE_TABLE))
+
+        for (NUM k = 0; k < ht_size(VALUE_TABLE); k++) {
+          count++;
+          printf("(");
+          print_name(list_nth(grammar_names(g), i));
+          printf(" := ");
+          map_list
+            (rg_nth
+             (grammar_rule(g, i),
+              (*(VALUE_TABLE_KEYS+k))->x),
+             print_tnt);
+          printf(", %ld, %ld, %ld)",
+                 (*(KEYS+j))->x,
+                 (*(VALUE_TABLE_KEYS+k))->y,
+                 (*(KEYS+j))->y);
+
+          if (count == line_len) {
+            count = 0;
+            printf("\n");
+          } else {
+            printf(", ");
+          }
+        }
+      }
+    }
+  }
+
+#undef ELEMENT
+#undef KEYS
+#undef VALUES
+#undef SIZE
+#undef VALUE_TABLE
+#undef VALUE_TABLE_KEYS
+
+  for (NUM i = 0; i < b->s.len; i++) {
+
+#define ELEMENT (b->s.array+i)
+
+    if (!(ELEMENT->initialized)) continue;
+
+    for (NUM j = 0; j < ELEMENT->len; j++) {
+
+#define SELE (ELEMENT->array+j)
+
+      if (!(SELE->initialized)) continue;
+
+      for (NUM k = 0; k < SELE->len; k++) {
+
+#define HELE (SELE->array+k)
+
+        if (!(HELE->initialized)) continue;
+
+#define KEYS ((pair2 **) ht_keys(HELE->table))
+#define VALUES ((ht **) ht_values(HELE->table))
+
+        for (NUM n = 0; n < ht_size(HELE->table); n++) {
+          for (NUM ell = 0; ell < ht_size(*(VALUES+n)); ell++) {
+
+#define VALUE_KEYS ((NUM **) ht_keys(*(VALUES+n)))
+
+            count++;
+            printf("(");
+            print_name(list_nth(grammar_names(g), i));
+            printf(" := ");
+
+#define LS rg_nth(grammar_rule(g, i), j)
+
+            for (NUM m = 0; m < k; m++) {
+              print_tnt(*(list_array(LS)+m));
+              if (m+1<k) printf(" ");
+            }
+
+            printf(" · ");
+
+            for (NUM m = k; m < list_length(LS); m++) {
+              print_tnt(*(list_array(LS)+m));
+              if (m+1<list_length(LS)) printf(" ");
+            }
+
+            printf(", %ld, %ld, %ld)",
+                   (*(KEYS+n))->x,
+                   **(VALUE_KEYS+ell),
+                   (*(KEYS+n))->y);
+
+            if (count == line_len) {
+              count = 0;
+              printf("\n");
+            } else {
+              printf(", ");
+            }
+          }
+        }
+      }
+    }
+  }
+  
+  printf("\n");
+
+#undef ELEMENT
+#undef SELE
+#undef HELE
+#undef KEYS
+#undef VALUES
+#undef VALUE_KEYS
+#undef LS
+
+}