Mercurial > cpython-lru_cache-weakref

annotate Parser/acceler.c @ 87690:66c1c9f32567 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add use_weakref option to functools.lru_cache The use_weakref option makes lru_cache create weak references to the function arguments when creating the cache key, which prevents them from staying in the memory forever even after all other references to them are gone. This is a proof of concept for http://bugs.python.org/issue19859
author Radomir Dopieralski <devel@sheep.art.pl>
date Tue, 03 Dec 2013 16:02:48 +0100
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 }