1 // $Id: depend.cpp,v 1.42 2004/04/07 13:08:20 ericb 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://ibm.com/developerworks/opensource/jikes.
6 // Copyright (C) 1996, 2004 IBM Corporation and others. All Rights Reserved.
7 // You must accept the terms of that agreement to use this software.
8 //
9
10 #include "depend.h"
11 #include "control.h"
12 #include "ast.h"
13 #include "semantic.h"
14 #include "option.h"
15 #include "stream.h"
16
17 #ifdef HAVE_JIKES_NAMESPACE
18 namespace Jikes { // Open namespace Jikes block
19 #endif
20
21 //
22 // Note that the types are ordered based on on the subtype relationship. We
23 // reverse the order here because the desired order for processing is the
24 // supertype relationship.
25 //
ReverseTypeList()26 inline void TypeCycleChecker::ReverseTypeList()
27 {
28 for (int head = 0, tail = type_list.Length() - 1;
29 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
37
PartialOrder(Tuple<Semantic * > & semantic,int start)38 void TypeCycleChecker::PartialOrder(Tuple<Semantic*>& semantic, int start)
39 {
40 type_list.Reset();
41
42 //
43 // assert that the "index" of all types that should be checked is initially
44 // set to OMEGA
45 //
46 for (unsigned i = start; i < semantic.Length(); i++)
47 {
48 Semantic* sem = semantic[i];
49 for (unsigned k = 0;
50 k < sem -> compilation_unit -> NumTypeDeclarations(); k++)
51 {
52 AstDeclaredType* declared =
53 sem -> compilation_unit -> TypeDeclaration(k);
54 if (declared -> EmptyDeclarationCast())
55 continue;
56 SemanticEnvironment* env =
57 declared -> class_body -> semantic_environment;
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
70
PartialOrder(SymbolSet & types)71 void TypeCycleChecker::PartialOrder(SymbolSet& types)
72 {
73 //
74 // assert that the "index" of all types that should be checked is initially
75 // set to OMEGA
76 //
77 for (TypeSymbol* type = (TypeSymbol*) types.FirstElement();
78 type; type = (TypeSymbol*) types.NextElement())
79 {
80 if (type -> index == OMEGA)
81 ProcessSubtypes(type);
82 }
83
84 ReverseTypeList();
85 }
86
87
ProcessSubtypes(TypeSymbol * type)88 void TypeCycleChecker::ProcessSubtypes(TypeSymbol* type)
89 {
90 stack.Push(type);
91 int indx = stack.Size();
92 type -> index = indx;
93
94 type -> subtypes_closure = new SymbolSet;
95 type -> subtypes_closure -> Union(*(type -> subtypes));
96 TypeSymbol* subtype;
97 for (subtype = (TypeSymbol*) type -> subtypes -> FirstElement();
98 subtype;
99 subtype = (TypeSymbol*) type -> subtypes -> NextElement())
100 {
101 //
102 // Only worry about top-level types.
103 //
104 if (subtype -> outermost_type != subtype)
105 continue;
106 if (subtype -> index == OMEGA)
107 ProcessSubtypes(subtype);
108 type -> index = Min(type -> index, subtype -> index);
109 type -> subtypes_closure -> Union(*(subtype -> subtypes_closure));
110 }
111
112 if (type -> index == indx)
113 {
114 TypeSymbol* scc_subtype;
115 do
116 {
117 scc_subtype = stack.Top();
118 scc_subtype -> index = CYCLE_INFINITY;
119 *(scc_subtype -> subtypes_closure) = *(type -> subtypes_closure);
120 type_list.Next() = scc_subtype;
121 stack.Pop();
122 } while (scc_subtype != type);
123 }
124 }
125
126
ConstructorCycleChecker(AstClassBody * class_body)127 ConstructorCycleChecker::ConstructorCycleChecker(AstClassBody* class_body)
128 {
129 for (unsigned k = 0; k < class_body -> NumConstructors(); k++)
130 {
131 AstConstructorDeclaration* constructor_declaration =
132 class_body -> Constructor(k);
133 if (constructor_declaration -> index == OMEGA)
134 CheckConstructorCycles(constructor_declaration);
135 }
136 }
137
138
CheckConstructorCycles(AstConstructorDeclaration * constructor_declaration)139 void ConstructorCycleChecker::CheckConstructorCycles(AstConstructorDeclaration* constructor_declaration)
140 {
141 stack.Push(constructor_declaration);
142 int indx = stack.Size();
143 constructor_declaration -> index = indx;
144
145 AstConstructorDeclaration* called_constructor_declaration = NULL;
146
147 AstMethodBody* constructor_block =
148 constructor_declaration -> constructor_body;
149 if (constructor_block -> explicit_constructor_opt)
150 {
151 AstThisCall* this_call =
152 constructor_block -> explicit_constructor_opt -> ThisCallCast();
153 MethodSymbol* called_constructor =
154 (MethodSymbol*) (this_call ? this_call -> symbol : NULL);
155
156 if (called_constructor)
157 {
158 called_constructor_declaration =
159 (AstConstructorDeclaration*) called_constructor -> declaration;
160
161 if (called_constructor_declaration -> index == OMEGA)
162 CheckConstructorCycles(called_constructor_declaration);
163 constructor_declaration -> index =
164 Min(constructor_declaration -> index,
165 called_constructor_declaration -> index);
166 }
167 }
168
169 if (constructor_declaration -> index == indx)
170 {
171 //
172 // If the constructor_declaration is alone in its strongly connected
173 // component (SCC), and it does not form a trivial cycle with itself,
174 // pop it, mark it and return.
175 //
176 if (constructor_declaration == stack.Top() &&
177 constructor_declaration != called_constructor_declaration)
178 {
179 stack.Pop();
180 constructor_declaration -> index = CYCLE_INFINITY;
181 }
182 //
183 // Otherwise, all elements in the stack up to (and including)
184 // constructor_declaration form an SCC. Pop them off the stack, in
185 // turn, mark them and issue the appropriate error message.
186 //
187 else
188 {
189 do
190 {
191 called_constructor_declaration = stack.Top();
192 stack.Pop();
193 called_constructor_declaration -> index = CYCLE_INFINITY;
194
195 constructor_block =
196 (AstMethodBody*) called_constructor_declaration ->
197 constructor_body;
198 AstMethodDeclarator* constructor_declarator =
199 called_constructor_declaration -> constructor_declarator;
200
201 Semantic* sem = called_constructor_declaration ->
202 constructor_symbol -> containing_type ->
203 semantic_environment -> sem;
204 sem -> ReportSemError(SemanticError::CIRCULAR_THIS_CALL,
205 constructor_block -> explicit_constructor_opt,
206 sem -> lex_stream -> NameString(constructor_declarator -> identifier_token));
207 } while (called_constructor_declaration != constructor_declaration);
208 }
209 }
210 }
211
212
213 //
214 // assert that the "index" of all types that should be checked is initially
215 // set to OMEGA
216 //
PartialOrder()217 void TypeDependenceChecker::PartialOrder()
218 {
219 for (FileSymbol* file_symbol = (FileSymbol*) file_set.FirstElement();
220 file_symbol;
221 file_symbol = (FileSymbol*) file_set.NextElement())
222 {
223 for (unsigned j = 0; j < file_symbol -> types.Length(); j++)
224 {
225 TypeSymbol* type = file_symbol -> types[j];
226 if (type -> incremental_index == OMEGA)
227 ProcessType(type);
228 }
229 }
230
231 for (unsigned k = 0; k < type_trash_bin.Length(); k++)
232 {
233 TypeSymbol* type = type_trash_bin[k];
234 if (type -> incremental_index == OMEGA)
235 ProcessType(type);
236 }
237 }
238
239
ProcessType(TypeSymbol * type)240 void TypeDependenceChecker::ProcessType(TypeSymbol* type)
241 {
242 stack.Push(type);
243 int indx = stack.Size();
244 type -> incremental_index = indx;
245
246 // if dependents is reflexive make it non-reflexive - saves time !!!
247 type -> dependents -> RemoveElement(type);
248 type -> dependents_closure = new SymbolSet;
249 // compute reflexive transitive closure
250 type -> dependents_closure -> AddElement(type);
251 TypeSymbol* dependent;
252 for (dependent = (TypeSymbol*) type -> dependents -> FirstElement();
253 dependent;
254 dependent = (TypeSymbol*) type -> dependents -> NextElement())
255 {
256 if (dependent -> incremental_index == OMEGA)
257 ProcessType(dependent);
258 type -> incremental_index = Min(type -> incremental_index,
259 dependent -> incremental_index);
260 type -> dependents_closure ->
261 Union(*(dependent -> dependents_closure));
262 }
263
264 if (type -> incremental_index == indx)
265 {
266 TypeSymbol* scc_dependent;
267 do
268 {
269 scc_dependent = stack.Top();
270 scc_dependent -> incremental_index = CYCLE_INFINITY;
271 *(scc_dependent -> dependents_closure) =
272 *(type -> dependents_closure);
273 type_list.Next() = scc_dependent;
274 stack.Pop();
275 } while (scc_dependent != type);
276 }
277 }
278
279
OutputMake(FILE * outfile,char * output_name,Tuple<FileSymbol * > & file_list)280 void TypeDependenceChecker::OutputMake(FILE* outfile, char* output_name,
281 Tuple<FileSymbol*>& file_list)
282 {
283 assert(outfile);
284
285 for (unsigned i = 0; i < file_list.Length(); i++)
286 {
287 FileSymbol* file_symbol = file_list[i];
288 char* name = file_symbol -> FileName();
289 int length = file_symbol -> FileNameLength() -
290 (file_symbol -> IsJava() ? FileSymbol::java_suffix_length
291 : FileSymbol::class_suffix_length);
292
293 char* class_name = new char[length + FileSymbol::class_suffix_length +
294 1];
295 char* java_name =
296 new char[length + FileSymbol::java_suffix_length + 1];
297
298 strncpy(class_name, name, length);
299 strcpy(&class_name[length], FileSymbol::class_suffix);
300 strncpy(java_name, name, length);
301 strcpy(&java_name[length], FileSymbol::java_suffix);
302
303 fprintf(outfile, "%s : %s\n", output_name, java_name);
304
305 if (i > 0) // Not the first file in the list
306 {
307 fprintf(outfile, "%s : %s\n", output_name, class_name);
308 }
309
310 delete [] class_name;
311 delete [] java_name;
312 }
313 }
314
315
OutputMake(FileSymbol * file_symbol)316 void TypeDependenceChecker::OutputMake(FileSymbol* file_symbol)
317 {
318 //
319 //
320 //
321 const char* name;
322 char* buf = NULL;
323 int length;
324
325 if (control -> option.directory == NULL)
326 {
327 name = file_symbol -> FileName();
328 length = file_symbol -> FileNameLength() -
329 (file_symbol -> IsJava() ? FileSymbol::java_suffix_length
330 : FileSymbol::class_suffix_length);
331 }
332 else
333 {
334 name = file_symbol -> Utf8Name();
335 length = strlen(name);
336
337 DirectorySymbol* dir_symbol = file_symbol -> OutputDirectory();
338 char* dir_name = dir_symbol -> DirectoryName();
339 int dir_length = strlen(dir_name);
340
341 buf = new char[length + FileSymbol::class_suffix_length + dir_length +
342 2];
343 strcpy(buf, dir_name);
344
345 #ifdef UNIX_FILE_SYSTEM
346 buf[dir_length] = (char)U_SLASH;
347 #elif defined(WIN32_FILE_SYSTEM)
348 buf[dir_length] = (char)U_BACKSLASH;
349 #endif
350
351 strcpy(&buf[dir_length+1], name);
352 name = buf;
353 length = dir_length + 1 + length;
354 }
355
356
357
358 char* output_name = new char[length + FileSymbol::class_suffix_length + 1];
359 char* u_name = new char[length + strlen(StringConstant::U8S_DO_u) + 1];
360
361 strncpy(output_name, name, length);
362 strncpy(u_name, name, length);
363 strcpy(&output_name[length], FileSymbol::class_suffix);
364 strcpy(&u_name[length], StringConstant::U8S_DO_u);
365
366 //
367 //
368 //
369 SymbolSet file_set;
370 for (unsigned i = 0; i < file_symbol -> types.Length(); i++)
371 {
372 TypeSymbol* type = file_symbol -> types[i];
373 TypeSymbol* parent;
374 for (parent = (TypeSymbol*) type -> parents_closure -> FirstElement();
375 parent;
376 parent = (TypeSymbol*) type -> parents_closure -> NextElement())
377 {
378 FileSymbol* symbol = parent -> file_symbol;
379 if (symbol && (! symbol -> IsZip()))
380 file_set.AddElement(symbol);
381 }
382 }
383 file_set.RemoveElement(file_symbol);
384
385 //
386 //
387 //
388 Tuple<FileSymbol*> file_list(file_set.Size());
389 file_list.Next() = file_symbol;
390 for (FileSymbol* symbol = (FileSymbol*) file_set.FirstElement();
391 symbol; symbol = (FileSymbol*) file_set.NextElement())
392 file_list.Next() = symbol;
393
394 FILE* outfile = SystemFopen(u_name, "w");
395 if (outfile == NULL)
396 Coutput << "*** Cannot open output Makefile " << u_name << endl;
397 else
398 {
399 OutputMake(outfile, output_name, file_list);
400 fclose(outfile);
401 }
402
403 delete [] output_name;
404 delete [] u_name;
405 if (control -> option.directory)
406 delete [] buf;
407 }
408
409
OutputDependences()410 void TypeDependenceChecker::OutputDependences()
411 {
412 SymbolSet new_file_set;
413 unsigned i;
414 for (i = 0; i < type_list.Length(); i++)
415 {
416 TypeSymbol* type = type_list[i];
417 type -> parents_closure = new SymbolSet;
418
419 FileSymbol* file_symbol = type -> file_symbol;
420 if (file_symbol && (! file_symbol -> IsZip()))
421 new_file_set.AddElement(file_symbol);
422 }
423
424 for (i = 0; i < type_list.Length(); i++)
425 {
426 TypeSymbol* parent = type_list[i];
427 TypeSymbol* dependent;
428 for (dependent = (TypeSymbol*) parent -> dependents_closure -> FirstElement();
429 dependent;
430 dependent = (TypeSymbol*) parent -> dependents_closure -> NextElement())
431 {
432 dependent -> parents_closure -> AddElement(parent);
433 }
434 }
435
436 for (FileSymbol* symbol = (FileSymbol*) new_file_set.FirstElement();
437 symbol; symbol = (FileSymbol*) new_file_set.NextElement())
438 {
439 OutputMake(symbol);
440 }
441
442 for (i = 0; i < type_list.Length(); i++)
443 {
444 TypeSymbol* type = type_list[i];
445 delete type -> parents_closure;
446 type -> parents_closure = NULL;
447 }
448 }
449
450
Process(TypeSymbol * type)451 void TopologicalSort::Process(TypeSymbol* type)
452 {
453 pending -> AddElement(type);
454
455 TypeSymbol* super_type;
456 for (super_type = (TypeSymbol*) type -> supertypes_closure -> FirstElement();
457 super_type;
458 super_type = (TypeSymbol*) type -> supertypes_closure -> NextElement())
459 {
460 if (type_collection.IsElement(super_type))
461 {
462 if (! pending -> IsElement(super_type))
463 Process(super_type);
464 }
465 }
466
467 type_list.Next() = type;
468 }
469
470
Sort()471 void TopologicalSort::Sort()
472 {
473 type_list.Reset();
474
475 for (TypeSymbol* type = (TypeSymbol*) type_collection.FirstElement();
476 type; type = (TypeSymbol*) type_collection.NextElement())
477 {
478 if (! pending -> IsElement(type))
479 Process(type);
480 }
481
482 pending -> SetEmpty();
483 }
484
485
TopologicalSort(SymbolSet & type_collection_,Tuple<TypeSymbol * > & type_list_)486 TopologicalSort::TopologicalSort(SymbolSet& type_collection_,
487 Tuple<TypeSymbol*>& type_list_)
488 : type_collection(type_collection_)
489 , type_list(type_list_)
490 {
491 pending = new SymbolSet(type_collection.Size());
492 }
493
494
~TopologicalSort()495 TopologicalSort::~TopologicalSort()
496 {
497 delete pending;
498 }
499
500
501 //
502 // Depend on the base enclosing class. For example, with class A { class B{} },
503 // using the type A.B[] will add a dependence on A, because it is A.java that
504 // must exist for the compiler to redefine B.class, and B.class that will be
505 // used by the VM to define B[]. We cannot add dependences on the primitive
506 // types, because there is no .java file that defines them.
507 //
AddDependence(TypeSymbol * base_type,TypeSymbol * parent_type,bool static_access)508 void Semantic::AddDependence(TypeSymbol* base_type, TypeSymbol* parent_type,
509 bool static_access)
510 {
511 assert(! base_type -> IsArray() && ! base_type -> Primitive());
512 if (parent_type -> IsArray())
513 {
514 parent_type = parent_type -> base_type;
515 }
516 if (base_type -> Bad() || parent_type -> Bad() ||
517 parent_type == control.null_type || parent_type -> Primitive())
518 {
519 return;
520 }
521 base_type = base_type -> outermost_type;
522 parent_type = parent_type -> outermost_type;
523 parent_type -> dependents -> AddElement(base_type);
524 if (static_access)
525 base_type -> static_parents -> AddElement(parent_type);
526 else base_type -> parents -> AddElement(parent_type);
527
528 //
529 // It is not possible to import from the unnamed package, and without
530 // imports, it is impossible to reference a class in the unnamed
531 // package from a package.
532 //
533 assert(parent_type -> ContainingPackage() != control.UnnamedPackage() ||
534 base_type -> ContainingPackage() == control.UnnamedPackage());
535 }
536
537
538 #ifdef HAVE_JIKES_NAMESPACE
539 } // Close namespace Jikes block
540 #endif
541