symbol.c

Go to the documentation of this file.

   /*+------- <| --------------------------------------------------------**
    **         A                     Clan                                **
    **---     /.\   -----------------------------------------------------**
    **   <|  [""M#                 symbol.c                              **
    **-   A   | #   -----------------------------------------------------**
    **   /.\ [""M#         First version: 01/05/2008                     **
    **- [""M# | #  U"U#U  -----------------------------------------------**
         | #  | #  \ .:/
         | #  | #___| #
 ******  | "--'     .-"  ******************************************************
 *     |"-"-"-"-"-#-#-##   Clan : the Chunky Loop Analyzer (experimental)     *
 ****  |     # ## ######  *****************************************************
 *      \       .::::'/                                                       *
 *       \      ::::'/     Copyright (C) 2008 University Paris-Sud 11         *
 *     :8a|    # # ##                                                         *
 *     ::88a      ###      This is free software; you can redistribute it     *
 *    ::::888a  8a ##::.   and/or modify it under the terms of the GNU Lesser *
 *  ::::::::888a88a[]:::   General Public License as published by the Free    *
 *::8:::::::::SUNDOGa8a::. Software Foundation, either version 2.1 of the     *
 *::::::::8::::888:Y8888:: License, or (at your option) any later version.    *
 *::::':::88::::888::Y88a::::::::::::...                                      *
 *::'::..    .   .....   ..   ...  .                                          *
 * This software is distributed in the hope that it will be useful, but       *
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License   *
 * for more details.                                                          *
 *                                                                            *
 * You should have received a copy of the GNU Lesser General Public License   *
 * along with software; if not, write to the Free Software Foundation, Inc.,  *
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA                     *
 *                                                                            *
 * Clan, the Chunky Loop Analyzer                                             *
 * Written by Cedric Bastoul, Cedric.Bastoul@u-psud.fr                        *
 *                                                                            *
 ******************************************************************************/


#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>

#include <osl/macros.h>
#include <osl/strings.h>
#include <osl/generic.h>
#include <osl/relation.h>
#include <osl/relation_list.h>
#include <osl/extensions/arrays.h>
#include <clan/macros.h>
#include <clan/symbol.h>


void yyerror(char*);


/*+****************************************************************************
 *                          Structure display function                        *
 ******************************************************************************/


void clan_symbol_print_structure(FILE* file, clan_symbol_p symbol, int level) {
  int i, j, first = 1, number = 1;

  if (symbol != NULL) {
    // Go to the right level.
    for(j = 0; j < level; j++)
      fprintf(file, "|\t");
    fprintf(file, "+-- clan_symbol_t (node %d)\n", number);
  } else {
    // Go to the right level.
    for(j = 0; j < level; j++)
      fprintf(file, "|\t");
    fprintf(file, "+-- NULL symbol\n");
  }

  while (symbol != NULL) {
    if (!first) {
      // Go to the right level.
      for (j = 0; j < level; j++)
        fprintf(file, "|\t");
      fprintf(file, "|   clan_symbol_t (node %d)\n", number);
    } else {
      first = 0;
    }

    // A blank line.
    for (j = 0; j <= level + 1; j++)
      fprintf(file, "|\t");
    fprintf(file, "\n");

    // Go to the right level and print the key.
    for (j = 0; j <= level; j++)
      fprintf(file, "|\t");
    fprintf(file, "Key: %d\n", symbol->key);

    // A blank line.
    for (j = 0; j <= level+1; j++)
      fprintf(file, "|\t");
    fprintf(file, "\n");

    // Print the identifier.
    for (i = 0; i <= level; i++)
      fprintf(file, "|\t");
    if (symbol->identifier != NULL)
      fprintf(file, "+-- Identifier: %s\n", symbol->identifier);
    else
      fprintf(file, "+-- No identifier\n");

    // A blank line.
    for(j = 0; j <= level + 1; j++)
      fprintf(file, "|\t") ;
    fprintf(file, "\n") ;

    // Go to the right level and print the type.
    for (j = 0; j <= level; j++)
      fprintf(file, "|\t") ;
    fprintf(file, "Type: ") ;
    switch (symbol->type) {
      case CLAN_TYPE_ITERATOR : fprintf(file, "Iterator\n");  break;
      case CLAN_TYPE_PARAMETER: fprintf(file, "Parameter\n"); break;
      case CLAN_TYPE_ARRAY    : fprintf(file, "Array\n");     break;
      case CLAN_TYPE_FUNCTION : fprintf(file, "Function\n");  break;
      default : fprintf(file, "Unknown\n") ;
    }

    // A blank line.
    for (j = 0; j <= level + 1; j++)
      fprintf(file, "|\t");
    fprintf(file, "\n");

    // Go to the right level and print the rank.
    for (j = 0; j <= level; j++)
      fprintf(file, "|\t");
    fprintf(file, "Rank: %d\n", symbol->rank);

    // A blank line.
    for (j = 0; j <= level + 1; j++)
      fprintf(file, "|\t");
    fprintf(file, "\n");

    symbol = symbol->next;
    number++;

    // Next line.
    if (symbol != NULL) {
      for (j = 0; j <= level; j++)
        fprintf(file, "|\t");
      fprintf(file, "V\n");
    }
  }

  // The last line.
  for(j = 0; j <= level; j++)
    fprintf(file, "|\t");
  fprintf(file, "\n");
}


void clan_symbol_print(FILE* file, clan_symbol_p symbol) {
  clan_symbol_print_structure(file, symbol, 0);
}


/*+****************************************************************************
 *                    Memory allocation/deallocation function                 *
 ******************************************************************************/


clan_symbol_p clan_symbol_malloc() {
  clan_symbol_p symbol;

  CLAN_malloc(symbol, clan_symbol_p, sizeof(clan_symbol_t));
  symbol->key        = CLAN_UNDEFINED;
  symbol->identifier = NULL;
  symbol->type       = CLAN_UNDEFINED;
  symbol->rank       = CLAN_UNDEFINED;
  symbol->next       = NULL;

  return symbol;
}


void clan_symbol_free(clan_symbol_p symbol) {
  clan_symbol_p next;

  while (symbol != NULL) {
    next = symbol->next;
    free(symbol->identifier);
    free(symbol);
    symbol = next;
  }
}


/*+****************************************************************************
 *                            Processing functions                            *
 ******************************************************************************/


clan_symbol_p clan_symbol_lookup(clan_symbol_p symbol, char* identifier) {
  while (symbol != NULL) {
    if (strcmp(symbol->identifier, identifier) == 0)
      return symbol;
    else
      symbol = symbol->next;
  }
  return NULL;
}

  
clan_symbol_p clan_symbol_lookup_by_key(clan_symbol_p symbol, int key) {
  while (symbol != NULL) {
    if (symbol->key == key)
      return symbol;
    else
      symbol = symbol->next;
  }
  return NULL;
}


static
int clan_symbol_generate_new_key(clan_symbol_p table) {
  int key = CLAN_KEY_START;
  
  while (table != NULL) {
    if (table->key >= key)
      key = table->key + 1;
    table = table->next;
  }
  return key;
}


clan_symbol_p clan_symbol_add(clan_symbol_p* table, char* identifier,
                              int type) {
  clan_symbol_p symbol, tmp = *table;

  // If the identifier is already in the table, do nothing.
  symbol = clan_symbol_lookup(*table, identifier);
  if (symbol != NULL)
    return symbol;

  // Else, we allocate and fill a new clan_symbol_t node.
  symbol = clan_symbol_malloc();
  symbol->key = clan_symbol_generate_new_key(*table);
  symbol->identifier = strdup(identifier);
  symbol->type = type;

  // We put the new symbol at the end of the table.
  if (*table == NULL) {
    *table = symbol;
  } else {
    while (tmp->next != NULL)
      tmp = tmp->next;
    tmp->next = symbol;
  }

  return symbol;
}


int clan_symbol_get_key(clan_symbol_p symbol, char* identifier) {
  while (symbol != NULL) {
    if (strcmp(symbol->identifier,identifier) == 0)
      return symbol->key;
    else
      symbol = symbol->next;
  }
  return CLAN_UNDEFINED;
}


int clan_symbol_get_rank(clan_symbol_p symbol, char* identifier) {
  while (symbol != NULL) {
    if (strcmp(symbol->identifier,identifier) == 0)
      return symbol->rank;
    else
      symbol = symbol->next;
  }
  return CLAN_UNDEFINED;
}


int clan_symbol_get_type(clan_symbol_p symbol, char* identifier) {
  while (symbol != NULL) {
    if (strcmp(symbol->identifier,identifier) == 0)
      return symbol->type;
    else
      symbol = symbol->next;
  }
  return CLAN_UNDEFINED;
}


osl_strings_p clan_symbol_array_to_strings(clan_symbol_p* sarray, int size) {
  int i, length;
  char** identifiers = NULL;
  osl_strings_p strings;

  // Allocate, initialize and NULL-terminate the array of strings.
  CLAN_malloc(identifiers, char**, (size + 1) * sizeof(char *));
  for (i = 0; i <= size; i++)
    identifiers[i] = NULL;

  // Fill the array of strings.
  for (i = 0; i < size; i++) {
    length = strlen((sarray[i])->identifier) + 1;
    CLAN_malloc(identifiers[i], char*, length * sizeof(char));
    strcpy(identifiers[i], (sarray[i])->identifier);
  }

  // Build the osl_strings_t container.
  strings = osl_strings_malloc();
  strings->string = identifiers;

  return strings;
}


int clan_symbol_nb_of_type(clan_symbol_p symbol, int type) {
  int nb = 0;
  
  while (symbol != NULL) {
    if (symbol->type == type)
      nb++;
    symbol = symbol->next;
  }

  return nb;
}


osl_generic_p clan_symbol_to_strings(clan_symbol_p symbol, int type) {
  int i, length, nb_identifiers = 0;
  char** identifiers = NULL;
  osl_strings_p strings;
  osl_generic_p generic;

  nb_identifiers = clan_symbol_nb_of_type(symbol, type);
  if (nb_identifiers == 0)
    return NULL;

  // Allocate, initialize and NULL-terminate the array.
  CLAN_malloc(identifiers, char**, (nb_identifiers + 1) * sizeof(char *));
  for (i = 0; i <= nb_identifiers; i++)
    identifiers[i] = NULL;

  // We scan the table a second time to fill the identifier array
  // Not optimal to act this way but overkills are worse!
  i = 0;
  while (symbol != NULL) {
    if (symbol->type == type) {
      length = strlen(symbol->identifier) + 1;
      CLAN_malloc(identifiers[i], char*, length * sizeof(char));
      strcpy(identifiers[i], symbol->identifier);
      i++;
    }
    symbol = symbol->next;
  }

  // Build the osl_strings_t container.
  strings = osl_strings_malloc();
  strings->string = identifiers;

  // Embed the strings in a generic shell.
  generic = osl_generic_shell(strings, osl_strings_interface());
  return generic;
}


clan_symbol_p clan_symbol_clone_one(clan_symbol_p symbol) {
  clan_symbol_p clone = clan_symbol_malloc();

  if (symbol->identifier != NULL)
    clone->identifier = strdup(symbol->identifier);
  clone->type = symbol->type;
  clone->rank = symbol->rank;

  return clone;
}


osl_generic_p clan_symbol_to_arrays(clan_symbol_p symbol) {
  int i;
  int nb_arrays = 0;
  osl_arrays_p arrays = NULL;
  osl_generic_p generic = NULL;
  clan_symbol_p top = symbol;

  // A first scan to know how many arrays there are.
  while (symbol != NULL) {
    nb_arrays++;
    symbol = symbol->next;
  }

  // Build the arrays extension.
  if (nb_arrays > 0) {
    arrays = osl_arrays_malloc();
    CLAN_malloc(arrays->id, int*, nb_arrays * sizeof(int));
    CLAN_malloc(arrays->names, char**, nb_arrays * sizeof(char *));
    arrays->nb_names = nb_arrays;
    symbol = top;
    i = 0;
    while (symbol != NULL) {
      arrays->id[i] = symbol->key;
      CLAN_strdup(arrays->names[i], symbol->identifier);
      i++;
      symbol = symbol->next;
    }
    
    // Embed the arrays in a generic shell.
    generic = osl_generic_shell(arrays, osl_arrays_interface());
  }

  return generic;
}


int clan_symbol_new_iterator(clan_symbol_p* table, clan_symbol_p* array,
                             char* id, int depth) {
  clan_symbol_p symbol;
  symbol = clan_symbol_add(table, id, CLAN_TYPE_ITERATOR);

  // Ensure that the returned symbol was either a new one, or of the same type.
  if (symbol->type != CLAN_TYPE_ITERATOR) {
    yyerror("a loop iterator was previously used for something else");
    return 0;
  }
  
  // Update the rank, in case the symbol already exists.
  if (symbol->rank != depth + 1)
    symbol->rank = depth + 1;

  array[depth] = clan_symbol_clone_one(symbol);
  return 1;
}


int clan_symbol_update_type(clan_symbol_p table, osl_relation_list_p access,
                            int type) {
  int key;
  int relation_type;
  clan_symbol_p symbol;
  
  if (table == NULL)
    CLAN_error("cannot even try to update type: NULL symbol table");
  if (access == NULL)
    CLAN_error("cannot even try to update type: NULL access list");

  // We will only consider the last reference in the list.
  while (access->next != NULL)
    access = access->next;

  // Get the key (with some cheating with the relation type to be able to use
  // osl_relation_get_array_id), find the corresponding symbol and update.
  relation_type = access->elt->type;
  access->elt->type = OSL_TYPE_READ;
  key = osl_relation_get_array_id(access->elt);
  access->elt->type = relation_type;
  symbol = clan_symbol_lookup_by_key(table, key);
  if (symbol == NULL)
    CLAN_error("no symbol corresponding to the key");

  if ((symbol->type == CLAN_TYPE_ITERATOR) && (type != CLAN_TYPE_ITERATOR)) {
    yyerror("illegal use of an iterator (update or reference) in a statement");
    return 0;
  }

  if ((symbol->type == CLAN_TYPE_PARAMETER) && (type != CLAN_TYPE_PARAMETER)) {
    yyerror("illegal use of a parameter (update or reference) in a statement");
    return 0;
  }

  symbol->type = type;
  return 1;
}