Mercurial > cpython-lru_cache-weakref
annotate Parser/acceler.c @ 25838:8540887bcec6 2.2
Backport of 2.183:
Fix memory leak in add_subclass() found by NealN with valgrind.
| author | Guido van Rossum <guido@python.org> |
|---|---|
| date | Fri, 18 Oct 2002 13:42:21 +0000 |
| parents | 6f6f965c5e2d |
| children | cce9316a62f8 |
| 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; | |
|
4839
4567e158d20c
Rename DEBUG macro to Py_DEBUG
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
28 #ifdef Py_DEBUG |
|
1025
f993197c3a47
Print warnings to stderr and correct spelling
Guido van Rossum <guido@python.org>
parents:
795
diff
changeset
|
29 fprintf(stderr, "Adding parser accelerators ...\n"); |
| 86 | 30 #endif |
| 31 d = g->g_dfa; | |
| 32 for (i = g->g_ndfas; --i >= 0; d++) | |
| 33 fixdfa(g, d); | |
| 34 g->g_accel = 1; | |
|
4839
4567e158d20c
Rename DEBUG macro to Py_DEBUG
Guido van Rossum <guido@python.org>
parents:
4503
diff
changeset
|
35 #ifdef Py_DEBUG |
|
1025
f993197c3a47
Print warnings to stderr and correct spelling
Guido van Rossum <guido@python.org>
parents:
795
diff
changeset
|
36 fprintf(stderr, "Done.\n"); |
| 86 | 37 #endif |
| 38 } | |
| 39 | |
|
5924
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
40 void |
| 13659 | 41 PyGrammar_RemoveAccelerators(grammar *g) |
|
5924
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
42 { |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
43 dfa *d; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
44 int i; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
45 g->g_accel = 0; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
46 d = g->g_dfa; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
47 for (i = g->g_ndfas; --i >= 0; d++) { |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
48 state *s; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
49 int j; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
50 s = d->d_state; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
51 for (j = 0; j < d->d_nstates; j++, s++) { |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
52 if (s->s_accel) |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
53 PyMem_DEL(s->s_accel); |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
54 s->s_accel = NULL; |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
55 } |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
56 } |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
57 } |
|
08b1e9d847e6
Added finalization routines.
Guido van Rossum <guido@python.org>
parents:
5379
diff
changeset
|
58 |
| 86 | 59 static void |
| 13659 | 60 fixdfa(grammar *g, dfa *d) |
| 86 | 61 { |
| 62 state *s; | |
| 63 int j; | |
| 64 s = d->d_state; | |
| 65 for (j = 0; j < d->d_nstates; j++, s++) | |
| 737 | 66 fixstate(g, s); |
| 86 | 67 } |
| 6 | 68 |
| 69 static void | |
| 13659 | 70 fixstate(grammar *g, state *s) |
| 6 | 71 { |
| 72 arc *a; | |
| 73 int k; | |
| 74 int *accel; | |
| 75 int nl = g->g_ll.ll_nlabels; | |
| 76 s->s_accept = 0; | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
77 accel = PyMem_NEW(int, nl); |
| 6 | 78 for (k = 0; k < nl; k++) |
| 79 accel[k] = -1; | |
| 80 a = s->s_arc; | |
| 81 for (k = s->s_narcs; --k >= 0; a++) { | |
| 82 int lbl = a->a_lbl; | |
| 83 label *l = &g->g_ll.ll_label[lbl]; | |
| 84 int type = l->lb_type; | |
| 85 if (a->a_arrow >= (1 << 7)) { | |
| 86 printf("XXX too many states!\n"); | |
| 87 continue; | |
| 88 } | |
| 89 if (ISNONTERMINAL(type)) { | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
90 dfa *d1 = PyGrammar_FindDFA(g, type); |
| 6 | 91 int ibit; |
| 92 if (type - NT_OFFSET >= (1 << 7)) { | |
| 93 printf("XXX too high nonterminal number!\n"); | |
| 94 continue; | |
| 95 } | |
| 96 for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) { | |
| 97 if (testbit(d1->d_first, ibit)) { | |
|
368
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
98 #ifdef applec |
|
1848
b724599401ff
Merge back to main trunk
Guido van Rossum <guido@python.org>
parents:
1257
diff
changeset
|
99 #define MPW_881_BUG /* Undefine if bug below is fixed */ |
|
368
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
100 #endif |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
101 #ifdef MPW_881_BUG |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
102 /* In 881 mode MPW 3.1 has a code |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
103 generation bug which seems to |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
104 set the upper bits; fix this by |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
105 explicitly masking them off */ |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
106 int temp; |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
107 #endif |
| 6 | 108 if (accel[ibit] != -1) |
| 109 printf("XXX ambiguity!\n"); | |
|
368
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
110 #ifdef MPW_881_BUG |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
111 temp = 0xFFFF & |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
112 (a->a_arrow | (1 << 7) | |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
113 ((type - NT_OFFSET) << 8)); |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
114 accel[ibit] = temp; |
|
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
115 #else |
| 6 | 116 accel[ibit] = a->a_arrow | (1 << 7) | |
| 117 ((type - NT_OFFSET) << 8); | |
|
368
0927bdb816a0
Added work-arounds for MPW 3.{1,2?} code generation bug.
Guido van Rossum <guido@python.org>
parents:
145
diff
changeset
|
118 #endif |
| 6 | 119 } |
| 120 } | |
| 121 } | |
| 122 else if (lbl == EMPTY) | |
| 123 s->s_accept = 1; | |
| 124 else if (lbl >= 0 && lbl < nl) | |
| 125 accel[lbl] = a->a_arrow; | |
| 126 } | |
| 127 while (nl > 0 && accel[nl-1] == -1) | |
| 128 nl--; | |
| 129 for (k = 0; k < nl && accel[k] == -1;) | |
| 130 k++; | |
| 131 if (k < nl) { | |
| 132 int i; | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
133 s->s_accel = PyMem_NEW(int, nl-k); |
| 6 | 134 if (s->s_accel == NULL) { |
| 135 fprintf(stderr, "no mem to add parser accelerators\n"); | |
| 136 exit(1); | |
| 137 } | |
| 138 s->s_lower = k; | |
| 139 s->s_upper = nl; | |
| 140 for (i = 0; k < nl; i++, k++) | |
| 141 s->s_accel[i] = accel[k]; | |
| 142 } | |
|
5379
1c9a84e0981d
Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents:
4839
diff
changeset
|
143 PyMem_DEL(accel); |
| 6 | 144 } |