1 | /*
|
---|
2 | * Copyright (c) 2010 Jiri Svoboda
|
---|
3 | * All rights reserved.
|
---|
4 | *
|
---|
5 | * Redistribution and use in source and binary forms, with or without
|
---|
6 | * modification, are permitted provided that the following conditions
|
---|
7 | * are met:
|
---|
8 | *
|
---|
9 | * - Redistributions of source code must retain the above copyright
|
---|
10 | * notice, this list of conditions and the following disclaimer.
|
---|
11 | * - Redistributions in binary form must reproduce the above copyright
|
---|
12 | * notice, this list of conditions and the following disclaimer in the
|
---|
13 | * documentation and/or other materials provided with the distribution.
|
---|
14 | * - The name of the author may not be used to endorse or promote products
|
---|
15 | * derived from this software without specific prior written permission.
|
---|
16 | *
|
---|
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
|
---|
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
|
---|
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
|
---|
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
|
---|
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
|
---|
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
|
---|
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
|
---|
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
---|
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
|
---|
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
---|
27 | */
|
---|
28 |
|
---|
29 | /** @file Ancestry resolver.
|
---|
30 | *
|
---|
31 | * A chicken-and-egg problem is that in order to match identifiers to CSI
|
---|
32 | * definitions we need to know CSI ancestry. To know CSI ancestry we need
|
---|
33 | * to match identifiers to CSI definitions. Thus both must be done at the
|
---|
34 | * same time. Once we know the ancestry of some CSI, we are able to resolve
|
---|
35 | * symbols referenced within the scope of that CSI (but not in nested scopes).
|
---|
36 | *
|
---|
37 | * Here lies probably the most complicated (although not so complicated)
|
---|
38 | * algorithm. To process node N we must first process outer(N). This allows
|
---|
39 | * us to find all base(N) nodes and process them.
|
---|
40 | *
|
---|
41 | * To ensure all nodes get processed correctly, we use a two-layer walk.
|
---|
42 | * In the lower layer (ancr_csi_process) we follow the dependencies.
|
---|
43 | * ancr_csi_process(N) ensures N (and possibly other nodes) get resolved.
|
---|
44 | *
|
---|
45 | * In the second layer we simply do a DFS of the CSI tree, calling
|
---|
46 | * ancr_csi_process() on each node. This ensures that eventually all
|
---|
47 | * nodes get processed.
|
---|
48 | */
|
---|
49 |
|
---|
50 | #include <stdlib.h>
|
---|
51 | #include <assert.h>
|
---|
52 | #include "builtin.h"
|
---|
53 | #include "cspan.h"
|
---|
54 | #include "list.h"
|
---|
55 | #include "mytypes.h"
|
---|
56 | #include "stree.h"
|
---|
57 | #include "strtab.h"
|
---|
58 | #include "symbol.h"
|
---|
59 |
|
---|
60 | #include "ancr.h"
|
---|
61 |
|
---|
62 | static void ancr_csi_dfs(stree_program_t *prog, stree_csi_t *csi);
|
---|
63 | static void ancr_csi_process(stree_program_t *prog, stree_csi_t *node);
|
---|
64 | static stree_csi_t *ancr_csi_get_pred(stree_program_t *prog, stree_csi_t *csi,
|
---|
65 | stree_texpr_t *pred_ref);
|
---|
66 | static void ancr_csi_print_cycle(stree_program_t *prog, stree_csi_t *node);
|
---|
67 |
|
---|
68 | /** Process ancestry of all CSIs in a module.
|
---|
69 | *
|
---|
70 | * Note that currently we expect there to be exactly one module in the
|
---|
71 | * whole program.
|
---|
72 | *
|
---|
73 | * @param prog Program being processed.
|
---|
74 | * @param module Module to process.
|
---|
75 | */
|
---|
76 | void ancr_module_process(stree_program_t *prog, stree_module_t *module)
|
---|
77 | {
|
---|
78 | list_node_t *node;
|
---|
79 | stree_modm_t *modm;
|
---|
80 |
|
---|
81 | (void) module;
|
---|
82 | node = list_first(&prog->module->members);
|
---|
83 |
|
---|
84 | while (node != NULL) {
|
---|
85 | modm = list_node_data(node, stree_modm_t *);
|
---|
86 |
|
---|
87 | switch (modm->mc) {
|
---|
88 | case mc_csi:
|
---|
89 | ancr_csi_dfs(prog, modm->u.csi);
|
---|
90 | break;
|
---|
91 | case mc_enum:
|
---|
92 | break;
|
---|
93 | }
|
---|
94 |
|
---|
95 | node = list_next(&prog->module->members, node);
|
---|
96 | }
|
---|
97 | }
|
---|
98 |
|
---|
99 | /** Walk CSI node tree depth-first.
|
---|
100 | *
|
---|
101 | * This is the outer depth-first walk whose purpose is to eventually
|
---|
102 | * process all CSI nodes by calling ancr_csi_process() on them.
|
---|
103 | * (Which causes that and possibly some other nodes to be processed).
|
---|
104 | *
|
---|
105 | * @param prog Program being processed.
|
---|
106 | * @param csi CSI node to visit.
|
---|
107 | */
|
---|
108 | static void ancr_csi_dfs(stree_program_t *prog, stree_csi_t *csi)
|
---|
109 | {
|
---|
110 | list_node_t *node;
|
---|
111 | stree_csimbr_t *csimbr;
|
---|
112 |
|
---|
113 | /* Process this node first. */
|
---|
114 | ancr_csi_process(prog, csi);
|
---|
115 |
|
---|
116 | /* Now visit all children. */
|
---|
117 | node = list_first(&csi->members);
|
---|
118 | while (node != NULL) {
|
---|
119 | csimbr = list_node_data(node, stree_csimbr_t *);
|
---|
120 | if (csimbr->cc == csimbr_csi)
|
---|
121 | ancr_csi_dfs(prog, csimbr->u.csi);
|
---|
122 |
|
---|
123 | node = list_next(&csi->members, node);
|
---|
124 | }
|
---|
125 | }
|
---|
126 |
|
---|
127 | /** Process csi node.
|
---|
128 | *
|
---|
129 | * Fist processes the pre-required nodes (outer CSI and base CSIs),
|
---|
130 | * then processes @a node. This is the core 'outward-and-baseward' walk.
|
---|
131 | *
|
---|
132 | * @param prog Program being processed.
|
---|
133 | * @param csi CSI node to process.
|
---|
134 | */
|
---|
135 | static void ancr_csi_process(stree_program_t *prog, stree_csi_t *csi)
|
---|
136 | {
|
---|
137 | stree_csi_t *base_csi, *outer_csi;
|
---|
138 | stree_csi_t *gf_class;
|
---|
139 |
|
---|
140 | list_node_t *pred_n;
|
---|
141 | stree_texpr_t *pred;
|
---|
142 | stree_csi_t *pred_csi;
|
---|
143 |
|
---|
144 | if (csi->ancr_state == ws_visited) {
|
---|
145 | /* Node already processed */
|
---|
146 | return;
|
---|
147 | }
|
---|
148 |
|
---|
149 | if (csi->ancr_state == ws_active) {
|
---|
150 | /* Error, closed reference loop. */
|
---|
151 | printf("Error: Circular class, struct or interface chain: ");
|
---|
152 | ancr_csi_print_cycle(prog, csi);
|
---|
153 | printf(".\n");
|
---|
154 | exit(1);
|
---|
155 | }
|
---|
156 |
|
---|
157 | csi->ancr_state = ws_active;
|
---|
158 |
|
---|
159 | outer_csi = csi_to_symbol(csi)->outer_csi;
|
---|
160 | gf_class = builtin_get_gf_class(prog->builtin);
|
---|
161 |
|
---|
162 | if (csi != gf_class) {
|
---|
163 | /* Implicit inheritance from grandfather class. */
|
---|
164 | base_csi = gf_class;
|
---|
165 | } else {
|
---|
166 | /* Grandfather class has no base class. */
|
---|
167 | base_csi = NULL;
|
---|
168 | }
|
---|
169 |
|
---|
170 | /* Process outer CSI */
|
---|
171 | if (outer_csi != NULL)
|
---|
172 | ancr_csi_process(prog, outer_csi);
|
---|
173 |
|
---|
174 | /*
|
---|
175 | * Process inheritance list.
|
---|
176 | */
|
---|
177 | pred_n = list_first(&csi->inherit);
|
---|
178 |
|
---|
179 | /* For a class node, the first entry can be a class. */
|
---|
180 | if (csi->cc == csi_class && pred_n != NULL) {
|
---|
181 | pred = list_node_data(pred_n, stree_texpr_t *);
|
---|
182 | pred_csi = ancr_csi_get_pred(prog, csi, pred);
|
---|
183 | assert(pred_csi != NULL);
|
---|
184 |
|
---|
185 | if (pred_csi->cc == csi_class) {
|
---|
186 | /* Process base class */
|
---|
187 | base_csi = pred_csi;
|
---|
188 | ancr_csi_process(prog, pred_csi);
|
---|
189 |
|
---|
190 | pred_n = list_next(&csi->inherit, pred_n);
|
---|
191 | }
|
---|
192 | }
|
---|
193 |
|
---|
194 | /* Following entires can only be interfaces. */
|
---|
195 | while (pred_n != NULL) {
|
---|
196 | pred = list_node_data(pred_n, stree_texpr_t *);
|
---|
197 | pred_csi = ancr_csi_get_pred(prog, csi, pred);
|
---|
198 | assert(pred_csi != NULL);
|
---|
199 |
|
---|
200 | /* Process implemented or accumulated interface. */
|
---|
201 | ancr_csi_process(prog, pred_csi);
|
---|
202 |
|
---|
203 | switch (pred_csi->cc) {
|
---|
204 | case csi_class:
|
---|
205 | switch (csi->cc) {
|
---|
206 | case csi_class:
|
---|
207 | cspan_print(csi->name->cspan);
|
---|
208 | printf(" Error: Only the first predecessor "
|
---|
209 | "can be a class. ('");
|
---|
210 | symbol_print_fqn(csi_to_symbol(csi));
|
---|
211 | printf("' deriving from '");
|
---|
212 | symbol_print_fqn(csi_to_symbol(pred_csi));
|
---|
213 | printf("').\n");
|
---|
214 | exit(1);
|
---|
215 | break;
|
---|
216 | case csi_struct:
|
---|
217 | assert(b_false); /* XXX */
|
---|
218 | break;
|
---|
219 | case csi_interface:
|
---|
220 | cspan_print(csi->name->cspan);
|
---|
221 | printf(" Error: Interface predecessor must be "
|
---|
222 | "an interface ('");
|
---|
223 | symbol_print_fqn(csi_to_symbol(csi));
|
---|
224 | printf("' deriving from '");
|
---|
225 | symbol_print_fqn(csi_to_symbol(pred_csi));
|
---|
226 | printf("').\n");
|
---|
227 | exit(1);
|
---|
228 | break;
|
---|
229 | }
|
---|
230 | break;
|
---|
231 | case csi_struct:
|
---|
232 | assert(b_false); /* XXX */
|
---|
233 | break;
|
---|
234 | case csi_interface:
|
---|
235 | break;
|
---|
236 | }
|
---|
237 |
|
---|
238 | pred_n = list_next(&csi->inherit, pred_n);
|
---|
239 | }
|
---|
240 |
|
---|
241 | /* Store base CSI and update node state. */
|
---|
242 | csi->ancr_state = ws_visited;
|
---|
243 | csi->base_csi = base_csi;
|
---|
244 | }
|
---|
245 |
|
---|
246 | /** Resolve CSI predecessor reference.
|
---|
247 | *
|
---|
248 | * Returns the CSI predecessor referenced by @a pred_ref.
|
---|
249 | * If the referenced CSI does not exist, an error is generated.
|
---|
250 | *
|
---|
251 | * @param prog Program being processed.
|
---|
252 | * @param csi CSI node to process.
|
---|
253 | * @param pred_ref Type expression referencing the predecessor.
|
---|
254 | * @return Predecessor CSI.
|
---|
255 | */
|
---|
256 | static stree_csi_t *ancr_csi_get_pred(stree_program_t *prog, stree_csi_t *csi,
|
---|
257 | stree_texpr_t *pred_ref)
|
---|
258 | {
|
---|
259 | stree_csi_t *outer_csi;
|
---|
260 | stree_symbol_t *pred_sym;
|
---|
261 | stree_csi_t *pred_csi;
|
---|
262 |
|
---|
263 | outer_csi = csi_to_symbol(csi)->outer_csi;
|
---|
264 | pred_sym = symbol_xlookup_in_csi(prog, outer_csi, pred_ref);
|
---|
265 | pred_csi = symbol_to_csi(pred_sym);
|
---|
266 | assert(pred_csi != NULL); /* XXX */
|
---|
267 |
|
---|
268 | return pred_csi;
|
---|
269 | }
|
---|
270 |
|
---|
271 | /** Print loop in CSI ancestry.
|
---|
272 | *
|
---|
273 | * We have detected a loop in CSI ancestry. Traverse it (by following the
|
---|
274 | * nodes in ws_active state and print it.
|
---|
275 | *
|
---|
276 | * @param prog Program.
|
---|
277 | * @param node CSI node participating in an ancestry cycle.
|
---|
278 | */
|
---|
279 | static void ancr_csi_print_cycle(stree_program_t *prog, stree_csi_t *node)
|
---|
280 | {
|
---|
281 | stree_csi_t *n;
|
---|
282 | stree_symbol_t *pred_sym, *node_sym;
|
---|
283 | stree_csi_t *pred_csi, *outer_csi;
|
---|
284 | stree_texpr_t *pred;
|
---|
285 | list_node_t *pred_n;
|
---|
286 |
|
---|
287 | n = node;
|
---|
288 | do {
|
---|
289 | node_sym = csi_to_symbol(node);
|
---|
290 | symbol_print_fqn(node_sym);
|
---|
291 | printf(", ");
|
---|
292 |
|
---|
293 | outer_csi = node_sym->outer_csi;
|
---|
294 |
|
---|
295 | if (outer_csi != NULL && outer_csi->ancr_state == ws_active) {
|
---|
296 | node = outer_csi;
|
---|
297 | } else {
|
---|
298 | node = NULL;
|
---|
299 |
|
---|
300 | pred_n = list_first(&node->inherit);
|
---|
301 | while (pred_n != NULL) {
|
---|
302 | pred = list_node_data(pred_n, stree_texpr_t *);
|
---|
303 | pred_sym = symbol_xlookup_in_csi(prog,
|
---|
304 | outer_csi, pred);
|
---|
305 | pred_csi = symbol_to_csi(pred_sym);
|
---|
306 | assert(pred_csi != NULL);
|
---|
307 |
|
---|
308 | if (pred_csi->ancr_state == ws_active) {
|
---|
309 | node = pred_csi;
|
---|
310 | break;
|
---|
311 | }
|
---|
312 | }
|
---|
313 |
|
---|
314 | assert(node != NULL);
|
---|
315 | }
|
---|
316 | } while (n != node);
|
---|
317 |
|
---|
318 | node_sym = csi_to_symbol(node);
|
---|
319 | symbol_print_fqn(node_sym);
|
---|
320 | }
|
---|