source: mainline/uspace/app/sbi/src/ancr.c

Last change on this file was c8c418cf, checked in by Martin Decky <martin@…>, 7 years ago

add explicit breaks that do not hurt anybody

  • Property mode set to 100644
File size: 9.0 KB
Line 
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
62static void ancr_csi_dfs(stree_program_t *prog, stree_csi_t *csi);
63static void ancr_csi_process(stree_program_t *prog, stree_csi_t *node);
64static stree_csi_t *ancr_csi_get_pred(stree_program_t *prog, stree_csi_t *csi,
65 stree_texpr_t *pred_ref);
66static 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 */
76void 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 */
108static 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 */
135static 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 */
256static 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 */
279static 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}
Note: See TracBrowser for help on using the repository browser.