harec

[hare] Hare compiler, written in C11 for POSIX OSs
Log | Files | Refs | README | LICENSE

declaration_solver.txt (4788B)


      1 First thing harec does after parsing the inputs is making sure all the global
      2 declarations are valid. A constraint unique to this compilation step is that
      3 unlike with sequential bindings in a compound expression, there is no explicit
      4 order in which the declarations should be traversed to validate them, the
      5 correct traversal order is given by the contents of declarations themselves. To
      6 make things even more complex, interdependent declarations may reside in
      7 different subunits, so there is quite a bit of scope juggling involved to
      8 achieve correct scope shadowing.
      9 
     10 Declarations come in five flavours - functions, constants, type aliases, global
     11 variables and enum fields.
     12 
     13 First, the constants defined upon harec invocation are checked and put into a
     14 dedicated scope. Then the imports for each subunit are loaded. This step requires
     15 the command line defines to already be in place. After the imports of a
     16 subunit are loaded, all of its declarations except enums are marked
     17 incomplete and put into the unit scope. Duplicate declarations are caught and
     18 reported at this step. Enum types are treated separately from enum values
     19 in this algorithm. Enum types never have dependencies and can be completed
     20 on the spot. Enum values are put into a special scope that is created for each
     21 enum type and marked incomplete.
     22 
     23 At this point the defines can be copied from the dedicated scope into the unit
     24 scope, shadowing the declarations from the source files.
     25 
     26 Next, aliases of enum types are detected and taken care of. Because an enum
     27 alias only depends on the underlying enum type, its entire dependency tree
     28 is known immediately when it is detected, so it can be completed right away.
     29 For values of enum aliases we need to cover three possible configurations:
     30 	(a) An alias to an enum whose values are already completed at this
     31 	    stage. This happens when the underlying enum was imported from
     32 	    another module. This is the easiest case to handle, we can just
     33 	    copy it's values to the alias immediately.
     34 	(b) An enum alias whose underlying enum is defined in the same unit
     35 	    this case is handled by the general resolution algorithm described
     36 	    below.
     37 
     38 With everything but the declarations in place, the core part of the algorithm
     39 is started:
     40 
     41 For each incomplete declaration:
     42     (1) Save previous enum and subunit context, and load subunit context for
     43         current declaration.
     44     (2) If this declaration is marked as in-progress, error out because the
     45         declaration part of a dependency cycle, otherwise mark this
     46         declaration as in progress.
     47     (3) Disambiguate between different declaration flavours:
     48         - for functions, constants and globals and enum fields:
     49             Check and evaluate as if all the dependencies are already resolved.
     50             For enum fields, the relevant enum context has to be loaded and
     51             implicit values need to be taken care of.
     52 
     53             If an incomplete dependency is encountered along the way, first
     54             resolve that dependency recursively and then continue with
     55             resolution. When the check is done, insert the declaration into the
     56             unit scope. Declaration is now considered complete.
     57         - for type aliases:
     58             Types have two distinct properties that both have to be computed
     59             before a type is complete, their dimensions and their
     60             representation. The approach taken can be summarized as follows:
     61 
     62             (a) Compute secondary type's dimensions by traversing just enough
     63                 of its constituent types to be able to do so.  If an incomplete
     64                 type alias is encountered, first compute that type's dimensions
     65                 recursively and then continue.
     66             (b) Insert the complete alias into the type store and into the unit
     67                 scope.
     68             (c) Compute secondary type's representation by traversing all of
     69                 its constituent types and repeating this entire process on
     70                 those that are still incomplete.
     71 
     72             A valid type alias never references itself during (a), because such
     73             a type would not be storable in memory.  Types may reference
     74             themselves during (c). Such types are called self-referential
     75             types. Self-references during (c) require no special treatment,
     76             because from step (b) onwards the type we are currently declaring
     77             can be treated as a regular complete type.
     78     (4) Remove the in progress mark
     79     (5) Restore the saved subunit and enum context
     80 
     81 At this point all the incomplete declarations in the unit scope are shadowed by
     82 their complete counterparts. From here on, no special considerations regarding
     83 incomplete declarations apply and check can proceed accordingly.