add ydb deps

1 files changed, 125 insertions, 0 deletions

diff --git a/contrib/tools/python/src/Parser/acceler.c b/contrib/tools/python/src/Parser/acceler.c
new file mode 100644
index 0000000000..9b14263b46
--- /dev/null
+++ b/contrib/tools/python/src/Parser/acceler.c
@@ -0,0 +1,125 @@
+
+/* Parser accelerator module */
+
+/* The parser as originally conceived had disappointing performance.
+   This module does some precomputation that speeds up the selection
+   of a DFA based upon a token, turning a search through an array
+   into a simple indexing operation.  The parser now cannot work
+   without the accelerators installed.  Note that the accelerators
+   are installed dynamically when the parser is initialized, they
+   are not part of the static data structure written on graminit.[ch]
+   by the parser generator. */
+
+#include "pgenheaders.h"
+#include "grammar.h"
+#include "node.h"
+#include "token.h"
+#include "parser.h"
+
+/* Forward references */
+static void fixdfa(grammar *, dfa *);
+static void fixstate(grammar *, state *);
+
+void
+PyGrammar_AddAccelerators(grammar *g)
+{
+    dfa *d;
+    int i;
+    d = g->g_dfa;
+    for (i = g->g_ndfas; --i >= 0; d++)
+        fixdfa(g, d);
+    g->g_accel = 1;
+}
+
+void
+PyGrammar_RemoveAccelerators(grammar *g)
+{
+    dfa *d;
+    int i;
+    g->g_accel = 0;
+    d = g->g_dfa;
+    for (i = g->g_ndfas; --i >= 0; d++) {
+        state *s;
+        int j;
+        s = d->d_state;
+        for (j = 0; j < d->d_nstates; j++, s++) {
+            if (s->s_accel)
+                PyObject_FREE(s->s_accel);
+            s->s_accel = NULL;
+        }
+    }
+}
+
+static void
+fixdfa(grammar *g, dfa *d)
+{
+    state *s;
+    int j;
+    s = d->d_state;
+    for (j = 0; j < d->d_nstates; j++, s++)
+        fixstate(g, s);
+}
+
+static void
+fixstate(grammar *g, state *s)
+{
+    arc *a;
+    int k;
+    int *accel;
+    int nl = g->g_ll.ll_nlabels;
+    s->s_accept = 0;
+    accel = (int *) PyObject_MALLOC(nl * sizeof(int));
+    if (accel == NULL) {
+        fprintf(stderr, "no mem to build parser accelerators\n");
+        exit(1);
+    }
+    for (k = 0; k < nl; k++)
+        accel[k] = -1;
+    a = s->s_arc;
+    for (k = s->s_narcs; --k >= 0; a++) {
+        int lbl = a->a_lbl;
+        label *l = &g->g_ll.ll_label[lbl];
+        int type = l->lb_type;
+        if (a->a_arrow >= (1 << 7)) {
+            printf("XXX too many states!\n");
+            continue;
+        }
+        if (ISNONTERMINAL(type)) {
+            dfa *d1 = PyGrammar_FindDFA(g, type);
+            int ibit;
+            if (type - NT_OFFSET >= (1 << 7)) {
+                printf("XXX too high nonterminal number!\n");
+                continue;
+            }
+            for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
+                if (testbit(d1->d_first, ibit)) {
+                    if (accel[ibit] != -1)
+                        printf("XXX ambiguity!\n");
+                    accel[ibit] = a->a_arrow | (1 << 7) |
+                        ((type - NT_OFFSET) << 8);
+                }
+            }
+        }
+        else if (lbl == EMPTY)
+            s->s_accept = 1;
+        else if (lbl >= 0 && lbl < nl)
+            accel[lbl] = a->a_arrow;
+    }
+    while (nl > 0 && accel[nl-1] == -1)
+        nl--;
+    for (k = 0; k < nl && accel[k] == -1;)
+        k++;
+    if (k < nl) {
+        int i;
+        s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int));
+        if (s->s_accel == NULL) {
+            fprintf(stderr, "no mem to add parser accelerators\n");
+            exit(1);
+        }
+        s->s_lower = k;
+        s->s_upper = nl;
+        for (i = 0; k < nl; i++, k++)
+            s->s_accel[i] = accel[k];
+    }
+    PyObject_FREE(accel);
+}