(** Context analysis: find declarations of used variables and functions. *)

(** {2 Overview }

    The desugared CiviC code contains [Var], [FunCall] and [Assign] nodes. These
    all use variables or functions identified by a [string] name. The context
    analysis phase links each variable occurrence to its declaration: a
    [VarDec], [Param], [Dim], [GlobalDe[cf]], [FunDe[cf]] or [For] node. Since
    the original nodes only have a [string] field to save the declaration, new
    node types have been added which replace the name with a declaration node:
    [VarUse], [FunUse], and [VarLet].

    Context analysis can be broken down into the following steps: {ol
    {li Find all function declarations in the current scope. }
    {li Traverse the current scope without traversing into nested functions,
        adding variable declarations as they are declared, and applying renaming
        rules as described below. Error messages for duplicate varaible
        declarations, undefined variable uses, and assignments to loop induction
        variables are generated here. }
    {li Traverse into (nested) functions and go to step 1, while copying the
        current scope for each function (so that the higher scope is not
        polluted with local variables of the nested function). }
    }

    {2 Renaming variables }

    One task of context analysis is resolvement of scoping conclicts.
    Specifically, when a function parameter or local variable shadows a variable
    in a higher scope (either an ancestor function or the global scope),
    initializations in the corresponding function that reference the shadowed
    variable will be invalidated when the initialization is moved down during
    desugaring. This fixed by first traversing into the initialization part of a
    variable declaration before adding the newly declared variable to the scope,
    and then renaming the declared variable and all of its future uses. An
    example follows:

{v int a = 1;
int foo() \{
  int a = a + 1;  // 'a' is already in the scope, so rename it
  return a;
\} v}
    becomes:
{v int a = 1;
int foo() \{
  int _a_1 = a + 1;
  return _a_1;    // uses of local 'a' must be renamed as well
\} v}

    Note that the renaming scheme also solves the case in which a variable with
    the name of another local variable that is declared later on, is referenced
    in an initialization expression:

{v int a = 1;
int foo() \{
  int b = a + 1;  // should reference global 'a', not local 'a' below
  int a = 2;      // 'a' is already in the scope, so rename it
  return a;
\} v}
    After desugaring, this becomes:
{v int a = 1;
int foo() \{
  int b;
  int _a_1;
  b = a + 1;      // 'a' correctly references to global variable
  _a_1 = 2;
  return _a_1;
\} v}

    {3 For-loop counters }

    Induction variables in for-loop counters form a special case since they may
    shadow a local variable in the current scope, and even the induction
    variable of a parent for-loop. Since for-loops will be rewritten to
    while-loops during desugaring and these semantics only apply to for-loops,
    induction variables are renamed to fresh variables as needed to avoid
    scoping conflicts:
{v
void foo() \{                     |   void foo() \{
    int i;                       |       int i;
    printInt(i);                 |       printInt(i);
    for (int i = 1, 10) \{        |       for (int _i_1 = 1, 10) \{
        printInt(i);             |           printInt(_i_1);
        for (int i = 1, 10) \{    |           for (int _i_2 = 1, 10) \{
            printInt(i);         |               printInt(_i_2);
        \}                        |           \}
        printInt(i);             |           printInt(_i_1);
    \}                            |       \}
    printInt(i);                 |       printInt(i);
\}                                |   \} v}

    {3 Imported array dimensions }

    Another special case are dimensions of imported arrays. In [extern int[n]
    a], [n] is just a name given locally to the first dimension of [a]. Since
    this name is unknown the module where the dimension is exported, this needs
    to be consistently transformed into a format which both modules can decide
    on independently.

    Our implementation changes the snippet into [extern int[__a_0] a], where the
    [__] prefix indicates an array dimension and [a_0] indicates the first
    dimension of [a]. The double underscore prefix is necessary to assert
    uniqueness of the variable, since the suffix is based on the dimension index
    rather than the global counter that is used for other generated variables
    (we cannot use this global counter since it may differ between compilation
    instances of the different modules).

    This way, exporting dimensions global arrays in another module can be done
    in the same way while asserting uniqeness of the imported/exported
    variables.

    For exported variables, this renaming is done in the {!Desug} phase. The
    reason for this is that no separate variable exist yet for exported array
    dimensions at this stage, they are generated during desugaring.
    *)

(** Traversal that replaces names with declarations. Exported for use in other
    phases. The boolean argument toggles renaming, which is only [true] the
    first time the phase is run (after that it is not necessary since the
    compiler does not generate conflicting variables). *)
val analyse : bool -> Types.node -> Types.node

(** Main phase function, called by {!Main}. Calls {!analyse}. *)
val phase : Main.phase_func