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