Mercurial > cpython-lru_cache-weakref

annotate Parser/acceler.c @ 80661:94de77bd0b4b 2.7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Issue #16194: document imp.load_dynamic problems when read several extension modules from the same binary object file.
author Andrew Svetlov <andrew.svetlov@gmail.com>
date Thu, 29 Nov 2012 19:51:28 +0200
parents fd25030223b0
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
145
853b736a6a9e Added copyright notice.
Guido van Rossum <guido@python.org>
parents: 86
diff changeset
1
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
2 /* Parser accelerator module */
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
3
86
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
4 /* The parser as originally conceived had disappointing performance.
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
5 This module does some precomputation that speeds up the selection
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
6 of a DFA based upon a token, turning a search through an array
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
7 into a simple indexing operation. The parser now cannot work
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
8 without the accelerators installed. Note that the accelerators
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
9 are installed dynamically when the parser is initialized, they
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
10 are not part of the static data structure written on graminit.[ch]
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
11 by the parser generator. */
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
12
86
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
13 #include "pgenheaders.h"
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
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
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
16 #include "token.h"
86
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
17 #include "parser.h"
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
18
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
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
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
22
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
23 void
13659
e78153e179fb Mass ANSIfication.
Thomas Wouters <thomas@python.org>
parents: 13447
diff changeset
24 PyGrammar_AddAccelerators(grammar *g)
86
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
25 {
61463
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
26 dfa *d;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
27 int i;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
28 d = g->g_dfa;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
29 for (i = g->g_ndfas; --i >= 0; d++)
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
30 fixdfa(g, d);
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
31 g->g_accel = 1;
86
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
32 }
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
33
5924
08b1e9d847e6 Added finalization routines.
Guido van Rossum <guido@python.org>
parents: 5379
diff changeset
34 void
13659
e78153e179fb Mass ANSIfication.
Thomas Wouters <thomas@python.org>
parents: 13447
diff changeset
35 PyGrammar_RemoveAccelerators(grammar *g)
5924
08b1e9d847e6 Added finalization routines.
Guido van Rossum <guido@python.org>
parents: 5379
diff changeset
36 {
61463
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
37 dfa *d;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
38 int i;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
39 g->g_accel = 0;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
40 d = g->g_dfa;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
41 for (i = g->g_ndfas; --i >= 0; d++) {
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
42 state *s;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
43 int j;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
44 s = d->d_state;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
45 for (j = 0; j < d->d_nstates; j++, s++) {
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
46 if (s->s_accel)
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
47 PyObject_FREE(s->s_accel);
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
48 s->s_accel = NULL;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
49 }
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
50 }
5924
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
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
53 static void
13659
e78153e179fb Mass ANSIfication.
Thomas Wouters <thomas@python.org>
parents: 13447
diff changeset
54 fixdfa(grammar *g, dfa *d)
86
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
55 {
61463
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
56 state *s;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
57 int j;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
58 s = d->d_state;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
59 for (j = 0; j < d->d_nstates; j++, s++)
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
60 fixstate(g, s);
86
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
61 }
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
62
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
63 static void
13659
e78153e179fb Mass ANSIfication.
Thomas Wouters <thomas@python.org>
parents: 13447
diff changeset
64 fixstate(grammar *g, state *s)
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
65 {
61463
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
66 arc *a;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
67 int k;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
68 int *accel;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
69 int nl = g->g_ll.ll_nlabels;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
70 s->s_accept = 0;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
71 accel = (int *) PyObject_MALLOC(nl * sizeof(int));
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
72 if (accel == NULL) {
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
73 fprintf(stderr, "no mem to build parser accelerators\n");
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
74 exit(1);
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
75 }
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
76 for (k = 0; k < nl; k++)
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
77 accel[k] = -1;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
78 a = s->s_arc;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
79 for (k = s->s_narcs; --k >= 0; a++) {
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
80 int lbl = a->a_lbl;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
81 label *l = &g->g_ll.ll_label[lbl];
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
82 int type = l->lb_type;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
83 if (a->a_arrow >= (1 << 7)) {
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
84 printf("XXX too many states!\n");
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
85 continue;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
86 }
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
87 if (ISNONTERMINAL(type)) {
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
88 dfa *d1 = PyGrammar_FindDFA(g, type);
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
89 int ibit;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
90 if (type - NT_OFFSET >= (1 << 7)) {
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
91 printf("XXX too high nonterminal number!\n");
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
92 continue;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
93 }
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
94 for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
95 if (testbit(d1->d_first, ibit)) {
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
96 if (accel[ibit] != -1)
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
97 printf("XXX ambiguity!\n");
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
98 accel[ibit] = a->a_arrow | (1 << 7) |
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
99 ((type - NT_OFFSET) << 8);
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
100 }
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
101 }
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
102 }
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
103 else if (lbl == EMPTY)
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
104 s->s_accept = 1;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
105 else if (lbl >= 0 && lbl < nl)
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
106 accel[lbl] = a->a_arrow;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
107 }
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
108 while (nl > 0 && accel[nl-1] == -1)
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
109 nl--;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
110 for (k = 0; k < nl && accel[k] == -1;)
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
111 k++;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
112 if (k < nl) {
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
113 int i;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
114 s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int));
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
115 if (s->s_accel == NULL) {
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
116 fprintf(stderr, "no mem to add parser accelerators\n");
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
117 exit(1);
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
118 }
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
119 s->s_lower = k;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
120 s->s_upper = nl;
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
121 for (i = 0; k < nl; i++, k++)
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
122 s->s_accel[i] = accel[k];
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
123 }
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 32445
diff changeset
124 PyObject_FREE(accel);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
125 }