Mercurial > cpython-lru_cache-weakref
annotate Parser/acceler.c @ 58765:2ba7677bfa95 legacy-trunk
testCopysign was defined twice in test_math; combine the definitions
| author | Mark Dickinson <dickinsm@gmail.com> |
|---|---|
| date | Sat, 06 Feb 2010 23:11:25 +0000 |
| parents | 5adca58149ff |
| children | fd25030223b0 |
| rev | line source |
|---|---|
| 145 | 1 |
| 6 | 2 /* Parser accelerator module */ |
| 3 | |
| 86 | 4 /* The parser as originally conceived had disappointing performance. |
| 5 This module does some precomputation that speeds up the selection | |
| 6 of a DFA based upon a token, turning a search through an array | |
| 7 into a simple indexing operation. The parser now cannot work | |
| 8 without the accelerators installed. Note that the accelerators | |
| 9 are installed dynamically when the parser is initialized, they | |
| 10 are not part of the static data structure written on graminit.[ch] | |
| 11 by the parser generator. */ | |
| 6 | 12 |
| 86 | 13 #include "pgenheaders.h" |
| 6 | 14 #include "grammar.h" |
|
1848
b724599401ff
Merge back to main trunk
Guido van Rossum <guido@python.org>
parents:
1257
diff
changeset
|
15 #include "node.h" |
| 6 | 16 #include "token.h" |
| 86 | 17 #include "parser.h" |
| 18 | |
| 19 /* Forward references */ | |
|
13447
a89f7f268de4
Nuke all remaining occurrences of Py_PROTO and Py_FPROTO.
Tim Peters <tim.peters@gmail.com>
parents:
13256
diff
changeset
|
20 static void fixdfa(grammar *, dfa *); |
|
a89f7f268de4
Nuke all remaining occurrences of Py_PROTO and Py_FPROTO.
Tim Peters <tim.peters@gmail.com>
parents:
13256
diff
changeset
|
21 static void fixstate(grammar *, state *); |
| 86 | 22 |
| 23 void | |
| 13659 | 24 PyGrammar_AddAccelerators(grammar *g) |
| 86 | 25 { |
| 26 dfa *d; | |
| 27 int i; | |
| 28 d = g->g_dfa; | |
| 29 for (i = g->g_ndfas; --i >= 0; d++) | |
| 30 fixdfa(g, d); | |
| 31 g->g_accel = 1; | |
| 32 } | |
| 33 | |
|
5924
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
34 void |
| 13659 | 35 PyGrammar_RemoveAccelerators(grammar *g) |
|
5924
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
36 { |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
37 dfa *d; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
38 int i; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
39 g->g_accel = 0; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
40 d = g->g_dfa; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
41 for (i = g->g_ndfas; --i >= 0; d++) { |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
42 state *s; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
43 int j; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
44 s = d->d_state; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
45 for (j = 0; j < d->d_nstates; j++, s++) { |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
46 if (s->s_accel) |
|
24529
3444005b6527
SF patch #578297:
Andrew MacIntyre <andymac@bullseye.apana.org.au>
parents:
24189
diff
changeset
|
47 PyObject_FREE(s->s_accel); |
|
5924
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
48 s->s_accel = NULL; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
49 } |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
50 } |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
51 } |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
52 |
| 86 | 53 static void |
| 13659 | 54 fixdfa(grammar *g, dfa *d) |
| 86 | 55 { |
| 56 state *s; | |
| 57 int j; | |
| 58 s = d->d_state; | |
| 59 for (j = 0; j < d->d_nstates; j++, s++) | |
| 737 | 60 fixstate(g, s); |
| 86 | 61 } |
| 6 | 62 |
| 63 static void | |
| 13659 | 64 fixstate(grammar *g, state *s) |
| 6 | 65 { |
| 66 arc *a; | |
| 67 int k; | |
| 68 int *accel; | |
| 69 int nl = g->g_ll.ll_nlabels; | |
| 70 s->s_accept = 0; | |
|
24529
3444005b6527
SF patch #578297:
Andrew MacIntyre <andymac@bullseye.apana.org.au>
parents:
24189
diff
changeset
|
71 accel = (int *) PyObject_MALLOC(nl * sizeof(int)); |
|
32445
5adca58149ff
[Patch #974633] Check PyObject_MALLOC return for error
Andrew M. Kuchling <amk@amk.ca>
parents:
30968
diff
changeset
|
72 if (accel == NULL) { |
|
5adca58149ff
[Patch #974633] Check PyObject_MALLOC return for error
Andrew M. Kuchling <amk@amk.ca>
parents:
30968
diff
changeset
|
73 fprintf(stderr, "no mem to build parser accelerators\n"); |
|
5adca58149ff
[Patch #974633] Check PyObject_MALLOC return for error
Andrew M. Kuchling <amk@amk.ca>
parents:
30968
diff
changeset
|
74 exit(1); |
|
5adca58149ff
[Patch #974633] Check PyObject_MALLOC return for error
Andrew M. Kuchling <amk@amk.ca>
parents:
30968
diff
changeset
|
75 } |
| 6 | 76 for (k = 0; k < nl; k++) |
| 77 accel[k] = -1; | |
| 78 a = s->s_arc; | |
| 79 for (k = s->s_narcs; --k >= 0; a++) { | |
| 80 int lbl = a->a_lbl; | |
| 81 label *l = &g->g_ll.ll_label[lbl]; | |
| 82 int type = l->lb_type; | |
| 83 if (a->a_arrow >= (1 << 7)) { | |
| 84 printf("XXX too many states!\n"); | |
| 85 continue; | |
| 86 } | |
| 87 if (ISNONTERMINAL(type)) { | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
88 dfa *d1 = PyGrammar_FindDFA(g, type); |
| 6 | 89 int ibit; |
| 90 if (type - NT_OFFSET >= (1 << 7)) { | |
| 91 printf("XXX too high nonterminal number!\n"); | |
| 92 continue; | |
| 93 } | |
| 94 for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) { | |
| 95 if (testbit(d1->d_first, ibit)) { | |
| 96 if (accel[ibit] != -1) | |
| 97 printf("XXX ambiguity!\n"); | |
| 98 accel[ibit] = a->a_arrow | (1 << 7) | | |
| 99 ((type - NT_OFFSET) << 8); | |
| 100 } | |
| 101 } | |
| 102 } | |
| 103 else if (lbl == EMPTY) | |
| 104 s->s_accept = 1; | |
| 105 else if (lbl >= 0 && lbl < nl) | |
| 106 accel[lbl] = a->a_arrow; | |
| 107 } | |
| 108 while (nl > 0 && accel[nl-1] == -1) | |
| 109 nl--; | |
| 110 for (k = 0; k < nl && accel[k] == -1;) | |
| 111 k++; | |
| 112 if (k < nl) { | |
| 113 int i; | |
|
24529
3444005b6527
SF patch #578297:
Andrew MacIntyre <andymac@bullseye.apana.org.au>
parents:
24189
diff
changeset
|
114 s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int)); |
| 6 | 115 if (s->s_accel == NULL) { |
| 116 fprintf(stderr, "no mem to add parser accelerators\n"); | |
| 117 exit(1); | |
| 118 } | |
| 119 s->s_lower = k; | |
| 120 s->s_upper = nl; | |
| 121 for (i = 0; k < nl; i++, k++) | |
| 122 s->s_accel[i] = accel[k]; | |
| 123 } | |
|
24529
3444005b6527
SF patch #578297:
Andrew MacIntyre <andymac@bullseye.apana.org.au>
parents:
24189
diff
changeset
|
124 PyObject_FREE(accel); |
| 6 | 125 } |