home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 20 / AACD20.BIN / AACD / Programming / Jikes / Source / src / depend.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2001-03-03  |  15.3 KB  |  485 lines
  1. // $Id: depend.cpp,v 1.21 2001/01/10 16:49:44 mdejong Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1998, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #include "depend.h"
  11. #include "control.h"
  12. #include "ast.h"
  13. #include "semantic.h"
  14.  
  15. #ifdef HAVE_TIME_H
  16. #include <time.h>
  17. #endif
  18.  
  19. #ifdef    HAVE_JIKES_NAMESPACE
  20. namespace Jikes {    // Open namespace Jikes block
  21. #endif
  22.  
  23. //
  24. // Note that the types are ordered based on on the subtype relationship. We reverse
  25. // the order here because the desired order for processing is the supertype relationship.
  26. //
  27. inline void TypeCycleChecker::ReverseTypeList()
  28. {
  29.     for (int head = 0, tail = type_list.Length() - 1; head < tail; head++, tail--)
  30.     {
  31.         TypeSymbol *temp = type_list[head];
  32.         type_list[head] = type_list[tail];
  33.         type_list[tail] = temp;
  34.     }
  35.  
  36.     return;
  37. }
  38.  
  39.  
  40. void TypeCycleChecker::PartialOrder(Tuple<Semantic *> &semantic, int start)
  41. {
  42.     type_list.Reset();
  43.  
  44.     //
  45.     // assert that the "index" of all types that should be checked is initially set to OMEGA
  46.     //
  47.     for (int i = start; i < semantic.Length(); i++)
  48.     {
  49.         Semantic *sem = semantic[i];
  50.  
  51.         for (int k = 0; k < sem -> compilation_unit -> NumTypeDeclarations(); k++)
  52.         {
  53.             AstClassDeclaration *class_declaration = sem -> compilation_unit -> TypeDeclaration(k) -> ClassDeclarationCast();
  54.             AstInterfaceDeclaration *interface_declaration = sem -> compilation_unit -> TypeDeclaration(k) -> InterfaceDeclarationCast();
  55.             SemanticEnvironment *env = (class_declaration ? class_declaration -> semantic_environment
  56.                                                           : (interface_declaration ? interface_declaration -> semantic_environment
  57.                                                                                    : (SemanticEnvironment *) NULL));
  58.             if (env) // type was successfully compiled thus far?
  59.             {
  60.                 TypeSymbol *type = env -> Type();
  61.                 if (type -> index == OMEGA)
  62.                    ProcessSubtypes(type);
  63.             }
  64.         }
  65.     }
  66.  
  67.     ReverseTypeList();
  68.  
  69.     return;
  70. }
  71.  
  72.  
  73. void TypeCycleChecker::PartialOrder(SymbolSet &types)
  74. {
  75.     //
  76.     // assert that the "index" of all types that should be checked is initially set to OMEGA
  77.     //
  78.     for (TypeSymbol *type = (TypeSymbol *) types.FirstElement(); type; type = (TypeSymbol *) types.NextElement())
  79.     {
  80.         if (type -> index == OMEGA)
  81.             ProcessSubtypes(type);
  82.     }
  83.  
  84.     ReverseTypeList();
  85.  
  86.     return;
  87. }
  88.  
  89.  
  90. void TypeCycleChecker::ProcessSubtypes(TypeSymbol *type)
  91. {
  92.     stack.Push(type);
  93.     int indx = stack.Size();
  94.     type -> index = indx;
  95.  
  96.     type -> subtypes_closure = new SymbolSet;
  97.     type -> subtypes_closure -> Union(*(type -> subtypes));
  98.     for (TypeSymbol *subtype = (TypeSymbol *) type -> subtypes -> FirstElement();
  99.                      subtype;
  100.                      subtype = (TypeSymbol *) type -> subtypes -> NextElement())
  101.     {
  102.         if (subtype -> index == OMEGA)
  103.              ProcessSubtypes(subtype);
  104.         type -> index = Min(type -> index, subtype -> index);
  105.         type -> subtypes_closure -> Union(*(subtype -> subtypes_closure));
  106.     }
  107.  
  108.     if (type -> index == indx)
  109.     {
  110.         TypeSymbol *scc_subtype;
  111.         do
  112.         {
  113.             scc_subtype = stack.Top();
  114.             scc_subtype -> index = CYCLE_INFINITY;
  115.             *(scc_subtype -> subtypes_closure) = *(type -> subtypes_closure);
  116.             type_list.Next() = scc_subtype;
  117.             stack.Pop();
  118.         } while (scc_subtype != type);
  119.     }
  120.  
  121.     return;
  122. }
  123.  
  124.  
  125. ConstructorCycleChecker::ConstructorCycleChecker(AstClassBody *class_body)
  126. {
  127.     for (int k = 0; k < class_body -> NumConstructors(); k++)
  128.     {
  129.         AstConstructorDeclaration *constructor_declaration = class_body -> Constructor(k);
  130.         if (constructor_declaration -> index == OMEGA)
  131.             CheckConstructorCycles(constructor_declaration);
  132.     }
  133.  
  134.     return;
  135. }
  136.  
  137.  
  138. void ConstructorCycleChecker::CheckConstructorCycles(AstConstructorDeclaration *constructor_declaration)
  139. {
  140.     stack.Push(constructor_declaration);
  141.     int indx = stack.Size();
  142.     constructor_declaration -> index = indx;
  143.  
  144.     AstConstructorDeclaration *called_constructor_declaration = NULL;
  145.  
  146.     AstConstructorBlock *constructor_block = constructor_declaration -> constructor_body;
  147.     if (constructor_block -> explicit_constructor_invocation_opt)
  148.     {
  149.         AstThisCall *this_call = constructor_block -> explicit_constructor_invocation_opt -> ThisCallCast();
  150.         MethodSymbol *called_constructor = (MethodSymbol *) (this_call ? this_call -> symbol : NULL);
  151.  
  152.         if (called_constructor)
  153.         {
  154.             called_constructor_declaration = (AstConstructorDeclaration *) called_constructor -> method_or_constructor_declaration;
  155.  
  156.             if (called_constructor_declaration -> index == OMEGA)
  157.                 CheckConstructorCycles(called_constructor_declaration);
  158.             constructor_declaration -> index = Min(constructor_declaration -> index, called_constructor_declaration -> index);
  159.         }
  160.     }
  161.  
  162.     if (constructor_declaration -> index == indx)
  163.     {
  164.         //
  165.         // If the constructor_declaration is alone in its strongly connected component (SCC),
  166.         // and it does not form a trivial cycle with itsself, pop it, mark it and return;
  167.         //
  168.         if (constructor_declaration == stack.Top() && constructor_declaration != called_constructor_declaration)
  169.         {
  170.             stack.Pop();
  171.             constructor_declaration -> index = CYCLE_INFINITY;
  172.         }
  173.         //
  174.         // Otherwise, all elements in the stack up to (and including) constructor_declaration form an SCC.
  175.         // Pop them off the stack, in turn, mark them and issue the appropriate error message.
  176.         //
  177.         else
  178.         {
  179.             do
  180.             {
  181.                 called_constructor_declaration = stack.Top();
  182.                 stack.Pop();
  183.                 called_constructor_declaration -> index = CYCLE_INFINITY;
  184.  
  185.                 constructor_block = (AstConstructorBlock *) called_constructor_declaration -> constructor_body;
  186.                 AstMethodDeclarator *constructor_declarator = called_constructor_declaration -> constructor_declarator;
  187.  
  188.                 Semantic *sem = called_constructor_declaration -> constructor_symbol
  189.                                                                -> containing_type -> semantic_environment -> sem;
  190.                 sem -> ReportSemError(SemanticError::CIRCULAR_THIS_CALL,
  191.                                        constructor_block -> explicit_constructor_invocation_opt -> LeftToken(),
  192.                                        constructor_block -> explicit_constructor_invocation_opt -> RightToken(),
  193.                                        sem -> lex_stream -> NameString(constructor_declarator -> identifier_token));
  194.             } while (called_constructor_declaration != constructor_declaration);
  195.         }
  196.     }
  197.  
  198.     return;
  199. }
  200.  
  201.  
  202. //
  203. // assert that the "index" of all types that should be checked is initially set to OMEGA
  204. //
  205. void TypeDependenceChecker::PartialOrder()
  206. {
  207.     for (FileSymbol *file_symbol = (FileSymbol *) file_set.FirstElement();
  208.                      file_symbol;
  209.                      file_symbol = (FileSymbol *) file_set.NextElement())
  210.     {
  211.         for (int j = 0; j < file_symbol -> types.Length(); j++)
  212.         {
  213.             TypeSymbol *type = file_symbol -> types[j];
  214.             if (type -> incremental_index == OMEGA)
  215.                 ProcessType(type);
  216.         }
  217.     }
  218.  
  219.     for (int k = 0; k < type_trash_bin.Length(); k++)
  220.     {
  221.         TypeSymbol *type = type_trash_bin[k];
  222.         if (type -> incremental_index == OMEGA)
  223.             ProcessType(type);
  224.     }
  225.  
  226.     return;
  227. }
  228.  
  229.  
  230. void TypeDependenceChecker::ProcessType(TypeSymbol *type)
  231. {
  232.     stack.Push(type);
  233.     int indx = stack.Size();
  234.     type -> incremental_index = indx;
  235.  
  236.     type -> dependents -> RemoveElement(type); // if dependents is reflexive make it non-reflexive - saves time !!!
  237.     type -> dependents_closure = new SymbolSet;
  238.     type -> dependents_closure -> AddElement(type); // compute reflexive transitive closure
  239.     for (TypeSymbol *dependent = (TypeSymbol *) type -> dependents -> FirstElement();
  240.                      dependent;
  241.                      dependent = (TypeSymbol *) type -> dependents -> NextElement())
  242.     {
  243.         if (dependent -> incremental_index == OMEGA)
  244.              ProcessType(dependent);
  245.         type -> incremental_index = Min(type -> incremental_index, dependent -> incremental_index);
  246.         type -> dependents_closure -> Union(*(dependent -> dependents_closure));
  247.     }
  248.  
  249.     if (type -> incremental_index == indx)
  250.     {
  251.         TypeSymbol *scc_dependent;
  252.         do
  253.         {
  254.             scc_dependent = stack.Top();
  255.             scc_dependent -> incremental_index = CYCLE_INFINITY;
  256.             *(scc_dependent -> dependents_closure) = *(type -> dependents_closure);
  257.             type_list.Next() = scc_dependent;
  258.             stack.Pop();
  259.         } while (scc_dependent != type);
  260.     }
  261.  
  262.     return;
  263. }
  264.  
  265.  
  266. void TypeDependenceChecker::OutputMake(FILE *outfile, char *output_name, Tuple<FileSymbol *> &file_list)
  267. {
  268.     assert(outfile);
  269.  
  270.     for (int i = 0; i < file_list.Length(); i++)
  271.     {
  272.         FileSymbol *file_symbol = file_list[i];
  273.         char *name = file_symbol -> FileName();
  274.         int length = file_symbol -> FileNameLength() - (file_symbol -> IsJava() ? FileSymbol::java_suffix_length
  275.                                                                                 : FileSymbol::class_suffix_length);
  276.  
  277.         char *class_name = new char[length + FileSymbol::class_suffix_length + 1],
  278.              *java_name = new char[length + FileSymbol::java_suffix_length + 1];
  279.  
  280.         strncpy(class_name, name, length);
  281.         strcpy(&class_name[length], FileSymbol::class_suffix);
  282.         strncpy(java_name, name, length);
  283.         strcpy(&java_name[length], FileSymbol::java_suffix);
  284.  
  285.         fprintf(outfile, "%s : %s\n", output_name, java_name);
  286.  
  287.         if (i > 0) // Not the first file in the list
  288.         {
  289.             fprintf(outfile, "%s : %s\n", output_name, class_name);
  290.         }
  291.  
  292.         delete [] class_name;
  293.         delete [] java_name;
  294.     }
  295.  
  296.     return;
  297. }
  298.  
  299.  
  300. void TypeDependenceChecker::OutputMake(FileSymbol *file_symbol)
  301. {
  302.     //
  303.     //
  304.     //
  305.     char *name;
  306.     char *buf;
  307.     int length;
  308.  
  309.     if (control -> option.directory == NULL)
  310.     {
  311.         name = file_symbol -> FileName();
  312.         length = file_symbol -> FileNameLength() - (file_symbol -> IsJava() ? FileSymbol::java_suffix_length
  313.                                                                                 : FileSymbol::class_suffix_length);
  314.     }
  315.     else
  316.     {
  317.         name = file_symbol -> Utf8Name();
  318.         length = strlen(name);
  319.  
  320.         DirectorySymbol *dir_symbol = file_symbol -> OutputDirectory();
  321.         char *dir_name = dir_symbol -> DirectoryName();
  322.         int dir_length = strlen(dir_name);
  323.         
  324.         buf = new char[length + FileSymbol::class_suffix_length + dir_length + 2];
  325.         strcpy(buf, dir_name);
  326.  
  327. #if defined(UNIX_FILE_SYSTEM) || AMIGAOS_FILE_SYSTEM
  328.         buf[dir_length] = (char)U_SLASH;
  329. #elif defined(WIN32_FILE_SYSTEM)
  330.         buf[dir_length] = (char)U_BACKSLASH;
  331. #endif
  332.  
  333.         strcpy(&buf[dir_length+1], name);
  334.         name = buf;
  335.         length = dir_length + 1 + length;
  336.     }
  337.  
  338.  
  339.  
  340.     char *output_name = new char[length + FileSymbol::class_suffix_length + 1],
  341.          *u_name = new char[length + strlen(StringConstant::U8S__DO_u) + 1];
  342.  
  343.     strncpy(output_name, name, length);
  344.     strncpy(u_name, name, length);
  345.     strcpy(&output_name[length], FileSymbol::class_suffix);
  346.     strcpy(&u_name[length], StringConstant::U8S__DO_u);
  347.  
  348.     //
  349.     //
  350.     //
  351.     SymbolSet file_set;
  352.     for (int i = 0; i < file_symbol -> types.Length(); i++)
  353.     {
  354.         TypeSymbol *type = file_symbol -> types[i];
  355.         for (TypeSymbol *parent = (TypeSymbol *) type -> parents_closure -> FirstElement();
  356.                          parent;
  357.                          parent = (TypeSymbol *) type -> parents_closure -> NextElement())
  358.         {
  359.             FileSymbol *symbol = parent -> file_symbol;
  360.             if (symbol && (! symbol -> IsZip()))
  361.                 file_set.AddElement(symbol);
  362.         }
  363.     }
  364.     file_set.RemoveElement(file_symbol);
  365.  
  366.     //
  367.     //
  368.     //
  369.     Tuple<FileSymbol *> file_list(file_set.Size());
  370.     file_list.Next() = file_symbol;
  371.     for (FileSymbol *symbol = (FileSymbol *) file_set.FirstElement(); symbol; symbol = (FileSymbol *) file_set.NextElement())
  372.         file_list.Next() = symbol;
  373.  
  374.     FILE *outfile = SystemFopen(u_name, "w");
  375.     if (outfile == NULL)
  376.         Coutput << "*** Cannot open file " << u_name << "\n";
  377.     else
  378.     {
  379.         OutputMake(outfile, output_name, file_list);
  380.         fclose(outfile);
  381.     }
  382.  
  383.     delete [] output_name;
  384.     delete [] u_name;
  385.     if (control -> option.directory)
  386.         delete [] buf;
  387.  
  388.     return;
  389. }
  390.  
  391.  
  392. void TypeDependenceChecker::OutputDependences()
  393. {
  394.     SymbolSet new_file_set;
  395.  
  396.     for (int i = 0; i < type_list.Length(); i++)
  397.     {
  398.         TypeSymbol *type = type_list[i];
  399.         type -> parents_closure = new SymbolSet;
  400.  
  401.         FileSymbol *file_symbol = type -> file_symbol;
  402.         if (file_symbol && (! file_symbol -> IsZip()))
  403.             new_file_set.AddElement(file_symbol);
  404.     }
  405.  
  406.     for (int l = 0; l < type_list.Length(); l++)
  407.     {
  408.         TypeSymbol *parent = type_list[l];
  409.  
  410.         for (TypeSymbol *dependent = (TypeSymbol *) parent -> dependents_closure -> FirstElement();
  411.                          dependent;
  412.                          dependent = (TypeSymbol *) parent -> dependents_closure -> NextElement())
  413.                 dependent -> parents_closure -> AddElement(parent);
  414.     }
  415.  
  416.     for (FileSymbol *symbol = (FileSymbol *) new_file_set.FirstElement(); symbol; symbol = (FileSymbol *) new_file_set.NextElement())
  417.         OutputMake(symbol);
  418.  
  419.     for (int n = 0; n < type_list.Length(); n++)
  420.     {
  421.         TypeSymbol *type = type_list[n];
  422.         delete type -> parents_closure;
  423.         type -> parents_closure = NULL;
  424.     }
  425.  
  426.     return;
  427. }
  428.  
  429.  
  430. void TopologicalSort::Process(TypeSymbol *type)
  431. {
  432.     pending -> AddElement(type);
  433.  
  434.     for (TypeSymbol *super_type = (TypeSymbol *) type -> supertypes_closure -> FirstElement();
  435.                      super_type;
  436.                      super_type = (TypeSymbol *) type -> supertypes_closure -> NextElement())
  437.     {
  438.         if (type_collection.IsElement(super_type))
  439.         {
  440.             if (! pending -> IsElement(super_type))
  441.                 Process(super_type);
  442.         }
  443.     }
  444.  
  445.     type_list.Next() = type;
  446.  
  447.     return;
  448. }
  449.  
  450.  
  451. void TopologicalSort::Sort()
  452. {
  453.     type_list.Reset();
  454.  
  455.     for (TypeSymbol *type = (TypeSymbol *) type_collection.FirstElement(); type; type = (TypeSymbol *) type_collection.NextElement())
  456.     {
  457.         if (! pending -> IsElement(type))
  458.             Process(type);
  459.     }
  460.  
  461.     pending -> SetEmpty();
  462.  
  463.     return;
  464. }
  465.  
  466.  
  467. TopologicalSort::TopologicalSort(SymbolSet &type_collection_, Tuple<TypeSymbol *> &type_list_) : type_collection(type_collection_),
  468.                                                                                                  type_list(type_list_)
  469. {
  470.     pending = new SymbolSet(type_collection.Size());
  471.  
  472.     return;
  473. }
  474.  
  475.  
  476. TopologicalSort::~TopologicalSort()
  477. {
  478.     delete pending;
  479. }
  480.  
  481. #ifdef    HAVE_JIKES_NAMESPACE
  482. }            // Close namespace Jikes block
  483. #endif
  484.  
  485.