Mercurial > cpython-lru_cache-weakref

annotate Parser/firstsets.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 cab14be0ada1
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 /* Computation of FIRST stets */
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 #include "pgenheaders.h"
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
5 #include "grammar.h"
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
6 #include "token.h"
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
7
5379
1c9a84e0981d Another directory quickly renamed.
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
8 extern int Py_DebugFlag;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
9
86
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
10 /* Forward */
13447
a89f7f268de4 Nuke all remaining occurrences of Py_PROTO and Py_FPROTO.
Tim Peters <tim.peters@gmail.com>
parents: 13256
diff changeset
11 static void calcfirstset(grammar *, dfa *);
86
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
12
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
13 void
13659
e78153e179fb Mass ANSIfication.
Thomas Wouters <thomas@python.org>
parents: 13447
diff changeset
14 addfirstsets(grammar *g)
86
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
15 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
16 int i;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
17 dfa *d;
19867
5780724470ee Silence parser generator output.
Guido van Rossum <guido@python.org>
parents: 14375
diff changeset
18
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
19 if (Py_DebugFlag)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
20 printf("Adding FIRST sets ...\n");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
21 for (i = 0; i < g->g_ndfas; i++) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
22 d = &g->g_dfa[i];
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
23 if (d->d_first == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
24 calcfirstset(g, d);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
25 }
86
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
26 }
a6934380c6e7 "Compiling" version
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
27
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
28 static void
13659
e78153e179fb Mass ANSIfication.
Thomas Wouters <thomas@python.org>
parents: 13447
diff changeset
29 calcfirstset(grammar *g, dfa *d)
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
30 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
31 int i, j;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
32 state *s;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
33 arc *a;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
34 int nsyms;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
35 int *sym;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
36 int nbits;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
37 static bitset dummy;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
38 bitset result;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
39 int type;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
40 dfa *d1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
41 label *l0;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
42
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
43 if (Py_DebugFlag)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
44 printf("Calculate FIRST set for '%s'\n", d->d_name);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
45
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
46 if (dummy == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
47 dummy = newbitset(1);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
48 if (d->d_first == dummy) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
49 fprintf(stderr, "Left-recursion for '%s'\n", d->d_name);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
50 return;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
51 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
52 if (d->d_first != NULL) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
53 fprintf(stderr, "Re-calculating FIRST set for '%s' ???\n",
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
54 d->d_name);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
55 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
56 d->d_first = dummy;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
57
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
58 l0 = g->g_ll.ll_label;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
59 nbits = g->g_ll.ll_nlabels;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
60 result = newbitset(nbits);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
61
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
62 sym = (int *)PyObject_MALLOC(sizeof(int));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
63 if (sym == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
64 Py_FatalError("no mem for new sym in calcfirstset");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
65 nsyms = 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
66 sym[0] = findlabel(&g->g_ll, d->d_type, (char *)NULL);
36877
e9a7a2784e17 SF #1444030: Fix several potential defects found by Coverity.
Hye-Shik Chang <hyeshik@gmail.com>
parents: 19867
diff changeset
67
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
68 s = &d->d_state[d->d_initial];
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
69 for (i = 0; i < s->s_narcs; i++) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
70 a = &s->s_arc[i];
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
71 for (j = 0; j < nsyms; j++) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
72 if (sym[j] == a->a_lbl)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
73 break;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
74 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
75 if (j >= nsyms) { /* New label */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
76 sym = (int *)PyObject_REALLOC(sym,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
77 sizeof(int) * (nsyms + 1));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
78 if (sym == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
79 Py_FatalError(
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
80 "no mem to resize sym in calcfirstset");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
81 sym[nsyms++] = a->a_lbl;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
82 type = l0[a->a_lbl].lb_type;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
83 if (ISNONTERMINAL(type)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
84 d1 = PyGrammar_FindDFA(g, type);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
85 if (d1->d_first == dummy) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
86 fprintf(stderr,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
87 "Left-recursion below '%s'\n",
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
88 d->d_name);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
89 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
90 else {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
91 if (d1->d_first == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
92 calcfirstset(g, d1);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
93 mergebitset(result,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
94 d1->d_first, nbits);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
95 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
96 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
97 else if (ISTERMINAL(type)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
98 addbit(result, a->a_lbl);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
99 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
100 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
101 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
102 d->d_first = result;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
103 if (Py_DebugFlag) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
104 printf("FIRST set for '%s': {", d->d_name);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
105 for (i = 0; i < nbits; i++) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
106 if (testbit(result, i))
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
107 printf(" %s", PyGrammar_LabelRepr(&l0[i]));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
108 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
109 printf(" }\n");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
110 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
111
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 37879
diff changeset
112 PyObject_FREE(sym);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
113 }