uspace/app/sbi/src/ancr.c

   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 }