source: src/SymTab/Validate.cc @ e563edf

ADTast-experimental
Last change on this file since e563edf was e563edf, checked in by Andrew Beach <ajbeach@…>, 14 months ago

Header Clean-up: Clearing out typeops, moving things to Unify because that header already exist.

  • Property mode set to 100644
File size: 52.2 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// Validate.cc --
8//
9// Author           : Richard C. Bilson
10// Created On       : Sun May 17 21:50:04 2015
11// Last Modified By : Andrew Beach
12// Last Modified On : Tue Jul 12 15:00:00 2022
13// Update Count     : 367
14//
15
16// The "validate" phase of translation is used to take a syntax tree and convert it into a standard form that aims to be
17// as regular in structure as possible.  Some assumptions can be made regarding the state of the tree after this pass is
18// complete, including:
19//
20// - No nested structure or union definitions; any in the input are "hoisted" to the level of the containing struct or
21//   union.
22//
23// - All enumeration constants have type EnumInstType.
24//
25// - The type "void" never occurs in lists of function parameter or return types.  A function
26//   taking no arguments has no argument types.
27//
28// - No context instances exist; they are all replaced by the set of declarations signified by the context, instantiated
29//   by the particular set of type arguments.
30//
31// - Every declaration is assigned a unique id.
32//
33// - No typedef declarations or instances exist; the actual type is substituted for each instance.
34//
35// - Each type, struct, and union definition is followed by an appropriate assignment operator.
36//
37// - Each use of a struct or union is connected to a complete definition of that struct or union, even if that
38//   definition occurs later in the input.
39
40#include "Validate.h"
41
42#include <cassert>                     // for assertf, assert
43#include <cstddef>                     // for size_t
44#include <list>                        // for list
45#include <string>                      // for string
46#include <unordered_map>               // for unordered_map
47#include <utility>                     // for pair
48
49#include "CodeGen/CodeGenerator.h"     // for genName
50#include "CodeGen/OperatorTable.h"     // for isCtorDtor, isCtorDtorAssign
51#include "ControlStruct/Mutate.h"      // for ForExprMutator
52#include "Common/CodeLocation.h"       // for CodeLocation
53#include "Common/Stats.h"              // for Stats::Heap
54#include "Common/PassVisitor.h"        // for PassVisitor, WithDeclsToAdd
55#include "Common/ScopedMap.h"          // for ScopedMap
56#include "Common/SemanticError.h"      // for SemanticError
57#include "Common/UniqueName.h"         // for UniqueName
58#include "Common/utility.h"            // for operator+, cloneAll, deleteAll
59#include "CompilationState.h"          // skip some passes in new-ast build
60#include "Concurrency/Keywords.h"      // for applyKeywords
61#include "FixFunction.h"               // for FixFunction
62#include "Indexer.h"                   // for Indexer
63#include "InitTweak/GenInit.h"         // for fixReturnStatements
64#include "InitTweak/InitTweak.h"       // for isCtorDtorAssign
65#include "ResolvExpr/typeops.h"        // for extractResultType
66#include "ResolvExpr/Unify.h"          // for typesCompatible
67#include "ResolvExpr/Resolver.h"       // for findSingleExpression
68#include "ResolvExpr/ResolveTypeof.h"  // for resolveTypeof
69#include "SymTab/Autogen.h"            // for SizeType
70#include "SymTab/ValidateType.h"       // for decayEnumsAndPointers, decayFo...
71#include "SynTree/LinkageSpec.h"       // for C
72#include "SynTree/Attribute.h"         // for noAttributes, Attribute
73#include "SynTree/Constant.h"          // for Constant
74#include "SynTree/Declaration.h"       // for ObjectDecl, DeclarationWithType
75#include "SynTree/Expression.h"        // for CompoundLiteralExpr, Expressio...
76#include "SynTree/Initializer.h"       // for ListInit, Initializer
77#include "SynTree/Label.h"             // for operator==, Label
78#include "SynTree/Mutator.h"           // for Mutator
79#include "SynTree/Type.h"              // for Type, TypeInstType, EnumInstType
80#include "SynTree/TypeSubstitution.h"  // for TypeSubstitution
81#include "SynTree/Visitor.h"           // for Visitor
82#include "Validate/HandleAttributes.h" // for handleAttributes
83#include "Validate/FindSpecialDecls.h" // for FindSpecialDecls
84
85class CompoundStmt;
86class ReturnStmt;
87class SwitchStmt;
88
89#define debugPrint( x ) if ( doDebug ) x
90
91namespace SymTab {
92        /// hoists declarations that are difficult to hoist while parsing
93        struct HoistTypeDecls final : public WithDeclsToAdd {
94                void previsit( SizeofExpr * );
95                void previsit( AlignofExpr * );
96                void previsit( UntypedOffsetofExpr * );
97                void previsit( CompoundLiteralExpr * );
98                void handleType( Type * );
99        };
100
101        struct FixQualifiedTypes final : public WithIndexer {
102                FixQualifiedTypes() : WithIndexer(false) {}
103                Type * postmutate( QualifiedType * );
104        };
105
106        struct HoistStruct final : public WithDeclsToAdd, public WithGuards {
107                /// Flattens nested struct types
108                static void hoistStruct( std::list< Declaration * > &translationUnit );
109
110                void previsit( StructDecl * aggregateDecl );
111                void previsit( UnionDecl * aggregateDecl );
112                void previsit( StaticAssertDecl * assertDecl );
113                void previsit( StructInstType * type );
114                void previsit( UnionInstType * type );
115                void previsit( EnumInstType * type );
116
117          private:
118                template< typename AggDecl > void handleAggregate( AggDecl * aggregateDecl );
119
120                AggregateDecl * parentAggr = nullptr;
121        };
122
123        /// Fix return types so that every function returns exactly one value
124        struct ReturnTypeFixer {
125                static void fix( std::list< Declaration * > &translationUnit );
126
127                void postvisit( FunctionDecl * functionDecl );
128                void postvisit( FunctionType * ftype );
129        };
130
131        /// Does early resolution on the expressions that give enumeration constants their values
132        struct ResolveEnumInitializers final : public WithIndexer, public WithGuards, public WithVisitorRef<ResolveEnumInitializers>, public WithShortCircuiting {
133                ResolveEnumInitializers( const Indexer * indexer );
134                void postvisit( EnumDecl * enumDecl );
135
136          private:
137                const Indexer * local_indexer;
138
139        };
140
141        /// Replaces array and function types in forall lists by appropriate pointer type and assigns each Object and Function declaration a unique ID.
142        struct ForallPointerDecay_old final {
143                void previsit( ObjectDecl * object );
144                void previsit( FunctionDecl * func );
145                void previsit( FunctionType * ftype );
146                void previsit( StructDecl * aggrDecl );
147                void previsit( UnionDecl * aggrDecl );
148        };
149
150        struct ReturnChecker : public WithGuards {
151                /// Checks that return statements return nothing if their return type is void
152                /// and return something if the return type is non-void.
153                static void checkFunctionReturns( std::list< Declaration * > & translationUnit );
154
155                void previsit( FunctionDecl * functionDecl );
156                void previsit( ReturnStmt * returnStmt );
157
158                typedef std::list< DeclarationWithType * > ReturnVals;
159                ReturnVals returnVals;
160        };
161
162        struct ReplaceTypedef final : public WithVisitorRef<ReplaceTypedef>, public WithGuards, public WithShortCircuiting, public WithDeclsToAdd {
163                ReplaceTypedef() : scopeLevel( 0 ) {}
164                /// Replaces typedefs by forward declarations
165                static void replaceTypedef( std::list< Declaration * > &translationUnit );
166
167                void premutate( QualifiedType * );
168                Type * postmutate( QualifiedType * qualType );
169                Type * postmutate( TypeInstType * aggregateUseType );
170                Declaration * postmutate( TypedefDecl * typeDecl );
171                void premutate( TypeDecl * typeDecl );
172                void premutate( FunctionDecl * funcDecl );
173                void premutate( ObjectDecl * objDecl );
174                DeclarationWithType * postmutate( ObjectDecl * objDecl );
175
176                void premutate( CastExpr * castExpr );
177
178                void premutate( CompoundStmt * compoundStmt );
179
180                void premutate( StructDecl * structDecl );
181                void premutate( UnionDecl * unionDecl );
182                void premutate( EnumDecl * enumDecl );
183                void premutate( TraitDecl * );
184
185                void premutate( FunctionType * ftype );
186
187          private:
188                template<typename AggDecl>
189                void addImplicitTypedef( AggDecl * aggDecl );
190                template< typename AggDecl >
191                void handleAggregate( AggDecl * aggr );
192
193                typedef std::unique_ptr<TypedefDecl> TypedefDeclPtr;
194                typedef ScopedMap< std::string, std::pair< TypedefDeclPtr, int > > TypedefMap;
195                typedef ScopedMap< std::string, TypeDecl * > TypeDeclMap;
196                TypedefMap typedefNames;
197                TypeDeclMap typedeclNames;
198                int scopeLevel;
199                bool inFunctionType = false;
200        };
201
202        struct EliminateTypedef {
203                /// removes TypedefDecls from the AST
204                static void eliminateTypedef( std::list< Declaration * > &translationUnit );
205
206                template<typename AggDecl>
207                void handleAggregate( AggDecl * aggregateDecl );
208
209                void previsit( StructDecl * aggregateDecl );
210                void previsit( UnionDecl * aggregateDecl );
211                void previsit( CompoundStmt * compoundStmt );
212        };
213
214        struct VerifyCtorDtorAssign {
215                /// ensure that constructors, destructors, and assignment have at least one
216                /// parameter, the first of which must be a pointer, and that ctor/dtors have no
217                /// return values.
218                static void verify( std::list< Declaration * > &translationUnit );
219
220                void previsit( FunctionDecl * funcDecl );
221        };
222
223        /// ensure that generic types have the correct number of type arguments
224        struct ValidateGenericParameters {
225                void previsit( StructInstType * inst );
226                void previsit( UnionInstType * inst );
227        };
228
229        /// desugar declarations and uses of dimension paramaters like [N],
230        /// from type-system managed values, to tunnneling via ordinary types,
231        /// as char[-] in and sizeof(-) out
232        struct TranslateDimensionGenericParameters : public WithIndexer, public WithGuards {
233                static void translateDimensions( std::list< Declaration * > &translationUnit );
234                TranslateDimensionGenericParameters();
235
236                bool nextVisitedNodeIsChildOfSUIT = false; // SUIT = Struct or Union -Inst Type
237                bool visitingChildOfSUIT = false;
238                void changeState_ChildOfSUIT( bool newVal );
239                void premutate( StructInstType * sit );
240                void premutate( UnionInstType * uit );
241                void premutate( BaseSyntaxNode * node );
242
243                TypeDecl * postmutate( TypeDecl * td );
244                Expression * postmutate( DimensionExpr * de );
245                Expression * postmutate( Expression * e );
246        };
247
248        struct FixObjectType : public WithIndexer {
249                /// resolves typeof type in object, function, and type declarations
250                static void fix( std::list< Declaration * > & translationUnit );
251
252                void previsit( ObjectDecl * );
253                void previsit( FunctionDecl * );
254                void previsit( TypeDecl * );
255        };
256
257        struct InitializerLength {
258                /// for array types without an explicit length, compute the length and store it so that it
259                /// is known to the rest of the phases. For example,
260                ///   int x[] = { 1, 2, 3 };
261                ///   int y[][2] = { { 1, 2, 3 }, { 1, 2, 3 } };
262                /// here x and y are known at compile-time to have length 3, so change this into
263                ///   int x[3] = { 1, 2, 3 };
264                ///   int y[3][2] = { { 1, 2, 3 }, { 1, 2, 3 } };
265                static void computeLength( std::list< Declaration * > & translationUnit );
266
267                void previsit( ObjectDecl * objDecl );
268        };
269
270        struct ArrayLength : public WithIndexer {
271                static void computeLength( std::list< Declaration * > & translationUnit );
272
273                void previsit( ArrayType * arrayType );
274        };
275
276        struct CompoundLiteral final : public WithDeclsToAdd, public WithVisitorRef<CompoundLiteral> {
277                Type::StorageClasses storageClasses;
278
279                void premutate( ObjectDecl * objectDecl );
280                Expression * postmutate( CompoundLiteralExpr * compLitExpr );
281        };
282
283        struct LabelAddressFixer final : public WithGuards {
284                std::set< Label > labels;
285
286                void premutate( FunctionDecl * funcDecl );
287                Expression * postmutate( AddressExpr * addrExpr );
288        };
289
290        void validate( std::list< Declaration * > &translationUnit, __attribute__((unused)) bool doDebug ) {
291                PassVisitor<HoistTypeDecls> hoistDecls;
292                {
293                        Stats::Heap::newPass("validate-A");
294                        Stats::Time::BlockGuard guard("validate-A");
295                        VerifyCtorDtorAssign::verify( translationUnit );  // must happen before autogen, because autogen examines existing ctor/dtors
296                        acceptAll( translationUnit, hoistDecls );
297                        ReplaceTypedef::replaceTypedef( translationUnit );
298                        ReturnTypeFixer::fix( translationUnit ); // must happen before autogen
299                        decayEnumsAndPointers( translationUnit ); // must happen before VerifyCtorDtorAssign, because void return objects should not exist; before LinkReferenceToTypes_old because it is an indexer and needs correct types for mangling
300                }
301                PassVisitor<FixQualifiedTypes> fixQual;
302                {
303                        Stats::Heap::newPass("validate-B");
304                        Stats::Time::BlockGuard guard("validate-B");
305                        linkReferenceToTypes( translationUnit ); // Must happen before auto-gen, because it uses the sized flag.
306                        mutateAll( translationUnit, fixQual ); // must happen after LinkReferenceToTypes_old, because aggregate members are accessed
307                        HoistStruct::hoistStruct( translationUnit );
308                        EliminateTypedef::eliminateTypedef( translationUnit );
309                }
310                PassVisitor<ValidateGenericParameters> genericParams;
311                PassVisitor<ResolveEnumInitializers> rei( nullptr );
312                {
313                        Stats::Heap::newPass("validate-C");
314                        Stats::Time::BlockGuard guard("validate-C");
315                        Stats::Time::TimeBlock("Validate Generic Parameters", [&]() {
316                                acceptAll( translationUnit, genericParams );  // check as early as possible - can't happen before LinkReferenceToTypes_old; observed failing when attempted before eliminateTypedef
317                        });
318                        Stats::Time::TimeBlock("Translate Dimensions", [&]() {
319                                TranslateDimensionGenericParameters::translateDimensions( translationUnit );
320                        });
321                        if (!useNewAST) {
322                        Stats::Time::TimeBlock("Resolve Enum Initializers", [&]() {
323                                acceptAll( translationUnit, rei ); // must happen after translateDimensions because rei needs identifier lookup, which needs name mangling
324                        });
325                        }
326                        Stats::Time::TimeBlock("Check Function Returns", [&]() {
327                                ReturnChecker::checkFunctionReturns( translationUnit );
328                        });
329                        Stats::Time::TimeBlock("Fix Return Statements", [&]() {
330                                InitTweak::fixReturnStatements( translationUnit ); // must happen before autogen
331                        });
332                }
333                {
334                        Stats::Heap::newPass("validate-D");
335                        Stats::Time::BlockGuard guard("validate-D");
336                        Stats::Time::TimeBlock("Apply Concurrent Keywords", [&]() {
337                                Concurrency::applyKeywords( translationUnit );
338                        });
339                        Stats::Time::TimeBlock("Forall Pointer Decay", [&]() {
340                                decayForallPointers( translationUnit ); // must happen before autogenerateRoutines, after Concurrency::applyKeywords because uniqueIds must be set on declaration before resolution
341                        });
342                        Stats::Time::TimeBlock("Hoist Control Declarations", [&]() {
343                                ControlStruct::hoistControlDecls( translationUnit );  // hoist initialization out of for statements; must happen before autogenerateRoutines
344                        });
345                        Stats::Time::TimeBlock("Generate Autogen routines", [&]() {
346                                autogenerateRoutines( translationUnit ); // moved up, used to be below compoundLiteral - currently needs EnumAndPointerDecay_old
347                        });
348                }
349                PassVisitor<CompoundLiteral> compoundliteral;
350                {
351                        Stats::Heap::newPass("validate-E");
352                        Stats::Time::BlockGuard guard("validate-E");
353                        Stats::Time::TimeBlock("Implement Mutex Func", [&]() {
354                                Concurrency::implementMutexFuncs( translationUnit );
355                        });
356                        Stats::Time::TimeBlock("Implement Thread Start", [&]() {
357                                Concurrency::implementThreadStarter( translationUnit );
358                        });
359                        Stats::Time::TimeBlock("Compound Literal", [&]() {
360                                mutateAll( translationUnit, compoundliteral );
361                        });
362                        if (!useNewAST) {
363                                Stats::Time::TimeBlock("Resolve With Expressions", [&]() {
364                                        ResolvExpr::resolveWithExprs( translationUnit ); // must happen before FixObjectType because user-code is resolved and may contain with variables
365                                });
366                        }
367                }
368                PassVisitor<LabelAddressFixer> labelAddrFixer;
369                {
370                        Stats::Heap::newPass("validate-F");
371                        Stats::Time::BlockGuard guard("validate-F");
372                        if (!useNewAST) {
373                                Stats::Time::TimeCall("Fix Object Type",
374                                        FixObjectType::fix, translationUnit);
375                        }
376                        Stats::Time::TimeCall("Initializer Length",
377                                InitializerLength::computeLength, translationUnit);
378                        if (!useNewAST) {
379                                Stats::Time::TimeCall("Array Length",
380                                        ArrayLength::computeLength, translationUnit);
381                        }
382                        Stats::Time::TimeCall("Find Special Declarations",
383                                Validate::findSpecialDecls, translationUnit);
384                        Stats::Time::TimeCall("Fix Label Address",
385                                mutateAll<LabelAddressFixer>, translationUnit, labelAddrFixer);
386                        if (!useNewAST) {
387                                Stats::Time::TimeCall("Handle Attributes",
388                                        Validate::handleAttributes, translationUnit);
389                        }
390                }
391        }
392
393        void HoistTypeDecls::handleType( Type * type ) {
394                // some type declarations are buried in expressions and not easy to hoist during parsing; hoist them here
395                AggregateDecl * aggr = nullptr;
396                if ( StructInstType * inst = dynamic_cast< StructInstType * >( type ) ) {
397                        aggr = inst->baseStruct;
398                } else if ( UnionInstType * inst = dynamic_cast< UnionInstType * >( type ) ) {
399                        aggr = inst->baseUnion;
400                } else if ( EnumInstType * inst = dynamic_cast< EnumInstType * >( type ) ) {
401                        aggr = inst->baseEnum;
402                }
403                if ( aggr && aggr->body ) {
404                        declsToAddBefore.push_front( aggr );
405                }
406        }
407
408        void HoistTypeDecls::previsit( SizeofExpr * expr ) {
409                handleType( expr->type );
410        }
411
412        void HoistTypeDecls::previsit( AlignofExpr * expr ) {
413                handleType( expr->type );
414        }
415
416        void HoistTypeDecls::previsit( UntypedOffsetofExpr * expr ) {
417                handleType( expr->type );
418        }
419
420        void HoistTypeDecls::previsit( CompoundLiteralExpr * expr ) {
421                handleType( expr->result );
422        }
423
424
425        Type * FixQualifiedTypes::postmutate( QualifiedType * qualType ) {
426                Type * parent = qualType->parent;
427                Type * child = qualType->child;
428                if ( dynamic_cast< GlobalScopeType * >( qualType->parent ) ) {
429                        // .T => lookup T at global scope
430                        if ( TypeInstType * inst = dynamic_cast< TypeInstType * >( child ) ) {
431                                auto td = indexer.globalLookupType( inst->name );
432                                if ( ! td ) {
433                                        SemanticError( qualType->location, toString("Use of undefined global type ", inst->name) );
434                                }
435                                auto base = td->base;
436                                assert( base );
437                                Type * ret = base->clone();
438                                ret->get_qualifiers() = qualType->get_qualifiers();
439                                return ret;
440                        } else {
441                                // .T => T is not a type name
442                                assertf( false, "unhandled global qualified child type: %s", toCString(child) );
443                        }
444                } else {
445                        // S.T => S must be an aggregate type, find the declaration for T in S.
446                        AggregateDecl * aggr = nullptr;
447                        if ( StructInstType * inst = dynamic_cast< StructInstType * >( parent ) ) {
448                                aggr = inst->baseStruct;
449                        } else if ( UnionInstType * inst = dynamic_cast< UnionInstType * > ( parent ) ) {
450                                aggr = inst->baseUnion;
451                        } else {
452                                SemanticError( qualType->location, toString("Qualified type requires an aggregate on the left, but has: ", parent) );
453                        }
454                        assert( aggr ); // TODO: need to handle forward declarations
455                        for ( Declaration * member : aggr->members ) {
456                                if ( TypeInstType * inst = dynamic_cast< TypeInstType * >( child ) ) {
457                                        // name on the right is a typedef
458                                        if ( NamedTypeDecl * aggr = dynamic_cast< NamedTypeDecl * > ( member ) ) {
459                                                if ( aggr->name == inst->name ) {
460                                                        assert( aggr->base );
461                                                        Type * ret = aggr->base->clone();
462                                                        ret->get_qualifiers() = qualType->get_qualifiers();
463                                                        TypeSubstitution sub = parent->genericSubstitution();
464                                                        sub.apply(ret);
465                                                        return ret;
466                                                }
467                                        }
468                                } else {
469                                        // S.T - S is not an aggregate => error
470                                        assertf( false, "unhandled qualified child type: %s", toCString(qualType) );
471                                }
472                        }
473                        // failed to find a satisfying definition of type
474                        SemanticError( qualType->location, toString("Undefined type in qualified type: ", qualType) );
475                }
476
477                // ... may want to link canonical SUE definition to each forward decl so that it becomes easier to lookup?
478        }
479
480
481        void HoistStruct::hoistStruct( std::list< Declaration * > &translationUnit ) {
482                PassVisitor<HoistStruct> hoister;
483                acceptAll( translationUnit, hoister );
484        }
485
486        bool shouldHoist( Declaration * decl ) {
487                return dynamic_cast< StructDecl * >( decl ) || dynamic_cast< UnionDecl * >( decl ) || dynamic_cast< StaticAssertDecl * >( decl );
488        }
489
490        namespace {
491                void qualifiedName( AggregateDecl * aggr, std::ostringstream & ss ) {
492                        if ( aggr->parent ) qualifiedName( aggr->parent, ss );
493                        ss << "__" << aggr->name;
494                }
495
496                // mangle nested type names using entire parent chain
497                std::string qualifiedName( AggregateDecl * aggr ) {
498                        std::ostringstream ss;
499                        qualifiedName( aggr, ss );
500                        return ss.str();
501                }
502        }
503
504        template< typename AggDecl >
505        void HoistStruct::handleAggregate( AggDecl * aggregateDecl ) {
506                if ( parentAggr ) {
507                        aggregateDecl->parent = parentAggr;
508                        aggregateDecl->name = qualifiedName( aggregateDecl );
509                        // Add elements in stack order corresponding to nesting structure.
510                        declsToAddBefore.push_front( aggregateDecl );
511                } else {
512                        GuardValue( parentAggr );
513                        parentAggr = aggregateDecl;
514                } // if
515                // Always remove the hoisted aggregate from the inner structure.
516                GuardAction( [aggregateDecl]() { filter( aggregateDecl->members, shouldHoist, false ); } );
517        }
518
519        void HoistStruct::previsit( StaticAssertDecl * assertDecl ) {
520                if ( parentAggr ) {
521                        declsToAddBefore.push_back( assertDecl );
522                }
523        }
524
525        void HoistStruct::previsit( StructDecl * aggregateDecl ) {
526                handleAggregate( aggregateDecl );
527        }
528
529        void HoistStruct::previsit( UnionDecl * aggregateDecl ) {
530                handleAggregate( aggregateDecl );
531        }
532
533        void HoistStruct::previsit( StructInstType * type ) {
534                // need to reset type name after expanding to qualified name
535                assert( type->baseStruct );
536                type->name = type->baseStruct->name;
537        }
538
539        void HoistStruct::previsit( UnionInstType * type ) {
540                assert( type->baseUnion );
541                type->name = type->baseUnion->name;
542        }
543
544        void HoistStruct::previsit( EnumInstType * type ) {
545                assert( type->baseEnum );
546                type->name = type->baseEnum->name;
547        }
548
549
550        bool isTypedef( Declaration * decl ) {
551                return dynamic_cast< TypedefDecl * >( decl );
552        }
553
554        void EliminateTypedef::eliminateTypedef( std::list< Declaration * > &translationUnit ) {
555                PassVisitor<EliminateTypedef> eliminator;
556                acceptAll( translationUnit, eliminator );
557                filter( translationUnit, isTypedef, true );
558        }
559
560        template< typename AggDecl >
561        void EliminateTypedef::handleAggregate( AggDecl * aggregateDecl ) {
562                filter( aggregateDecl->members, isTypedef, true );
563        }
564
565        void EliminateTypedef::previsit( StructDecl * aggregateDecl ) {
566                handleAggregate( aggregateDecl );
567        }
568
569        void EliminateTypedef::previsit( UnionDecl * aggregateDecl ) {
570                handleAggregate( aggregateDecl );
571        }
572
573        void EliminateTypedef::previsit( CompoundStmt * compoundStmt ) {
574                // remove and delete decl stmts
575                filter( compoundStmt->kids, [](Statement * stmt) {
576                        if ( DeclStmt * declStmt = dynamic_cast< DeclStmt * >( stmt ) ) {
577                                if ( dynamic_cast< TypedefDecl * >( declStmt->decl ) ) {
578                                        return true;
579                                } // if
580                        } // if
581                        return false;
582                }, true);
583        }
584
585        // expand assertions from trait instance, performing the appropriate type variable substitutions
586        template< typename Iterator >
587        void expandAssertions( TraitInstType * inst, Iterator out ) {
588                assertf( inst->baseTrait, "Trait instance not linked to base trait: %s", toCString( inst ) );
589                std::list< DeclarationWithType * > asserts;
590                for ( Declaration * decl : inst->baseTrait->members ) {
591                        asserts.push_back( strict_dynamic_cast<DeclarationWithType *>( decl->clone() ) );
592                }
593                // substitute trait decl parameters for instance parameters
594                applySubstitution( inst->baseTrait->parameters.begin(), inst->baseTrait->parameters.end(), inst->parameters.begin(), asserts.begin(), asserts.end(), out );
595        }
596
597        ResolveEnumInitializers::ResolveEnumInitializers( const Indexer * other_indexer ) : WithIndexer( true ) {
598                if ( other_indexer ) {
599                        local_indexer = other_indexer;
600                } else {
601                        local_indexer = &indexer;
602                } // if
603        }
604
605        void ResolveEnumInitializers::postvisit( EnumDecl * enumDecl ) {
606                if ( enumDecl->body ) {
607                        for ( Declaration * member : enumDecl->members ) {
608                                ObjectDecl * field = strict_dynamic_cast<ObjectDecl *>( member );
609                                if ( field->init ) {
610                                        // need to resolve enumerator initializers early so that other passes that determine if an expression is constexpr have the appropriate information.
611                                        SingleInit * init = strict_dynamic_cast<SingleInit *>( field->init );
612                                        if ( !enumDecl->base || dynamic_cast<BasicType *>(enumDecl->base))
613                                                ResolvExpr::findSingleExpression( init->value, new BasicType( Type::Qualifiers(), BasicType::SignedInt ), indexer );
614                                        else {
615                                                if (dynamic_cast<PointerType *>(enumDecl->base)) {
616                                                        auto typePtr = dynamic_cast<PointerType *>(enumDecl->base);
617                                                        ResolvExpr::findSingleExpression( init->value,
618                                                         new PointerType( Type::Qualifiers(), typePtr->base ), indexer );
619                                                } else {
620                                                        ResolvExpr::findSingleExpression( init->value, new BasicType( Type::Qualifiers(), BasicType::SignedInt ), indexer );
621                                                }
622                                        }
623                                }
624                        }
625
626                } // if
627        }
628
629        /// Fix up assertions - flattens assertion lists, removing all trait instances
630        void forallFixer( std::list< TypeDecl * > & forall, BaseSyntaxNode * node ) {
631                for ( TypeDecl * type : forall ) {
632                        std::list< DeclarationWithType * > asserts;
633                        asserts.splice( asserts.end(), type->assertions );
634                        // expand trait instances into their members
635                        for ( DeclarationWithType * assertion : asserts ) {
636                                if ( TraitInstType * traitInst = dynamic_cast< TraitInstType * >( assertion->get_type() ) ) {
637                                        // expand trait instance into all of its members
638                                        expandAssertions( traitInst, back_inserter( type->assertions ) );
639                                        delete traitInst;
640                                } else {
641                                        // pass other assertions through
642                                        type->assertions.push_back( assertion );
643                                } // if
644                        } // for
645                        // apply FixFunction to every assertion to check for invalid void type
646                        for ( DeclarationWithType *& assertion : type->assertions ) {
647                                bool isVoid = fixFunction( assertion );
648                                if ( isVoid ) {
649                                        SemanticError( node, "invalid type void in assertion of function " );
650                                } // if
651                        } // for
652                        // normalizeAssertions( type->assertions );
653                } // for
654        }
655
656        /// Replace all traits in assertion lists with their assertions.
657        void expandTraits( std::list< TypeDecl * > & forall ) {
658                for ( TypeDecl * type : forall ) {
659                        std::list< DeclarationWithType * > asserts;
660                        asserts.splice( asserts.end(), type->assertions );
661                        // expand trait instances into their members
662                        for ( DeclarationWithType * assertion : asserts ) {
663                                if ( TraitInstType * traitInst = dynamic_cast< TraitInstType * >( assertion->get_type() ) ) {
664                                        // expand trait instance into all of its members
665                                        expandAssertions( traitInst, back_inserter( type->assertions ) );
666                                        delete traitInst;
667                                } else {
668                                        // pass other assertions through
669                                        type->assertions.push_back( assertion );
670                                } // if
671                        } // for
672                }
673        }
674
675        /// Fix each function in the assertion list and check for invalid void type.
676        void fixAssertions(
677                        std::list< TypeDecl * > & forall, BaseSyntaxNode * node ) {
678                for ( TypeDecl * type : forall ) {
679                        for ( DeclarationWithType *& assertion : type->assertions ) {
680                                bool isVoid = fixFunction( assertion );
681                                if ( isVoid ) {
682                                        SemanticError( node, "invalid type void in assertion of function " );
683                                } // if
684                        } // for
685                }
686        }
687
688        void ForallPointerDecay_old::previsit( ObjectDecl * object ) {
689                // ensure that operator names only apply to functions or function pointers
690                if ( CodeGen::isOperator( object->name ) && ! dynamic_cast< FunctionType * >( object->type->stripDeclarator() ) ) {
691                        SemanticError( object->location, toCString( "operator ", object->name.c_str(), " is not a function or function pointer." )  );
692                }
693                object->fixUniqueId();
694        }
695
696        void ForallPointerDecay_old::previsit( FunctionDecl * func ) {
697                func->fixUniqueId();
698        }
699
700        void ForallPointerDecay_old::previsit( FunctionType * ftype ) {
701                forallFixer( ftype->forall, ftype );
702        }
703
704        void ForallPointerDecay_old::previsit( StructDecl * aggrDecl ) {
705                forallFixer( aggrDecl->parameters, aggrDecl );
706        }
707
708        void ForallPointerDecay_old::previsit( UnionDecl * aggrDecl ) {
709                forallFixer( aggrDecl->parameters, aggrDecl );
710        }
711
712        void ReturnChecker::checkFunctionReturns( std::list< Declaration * > & translationUnit ) {
713                PassVisitor<ReturnChecker> checker;
714                acceptAll( translationUnit, checker );
715        }
716
717        void ReturnChecker::previsit( FunctionDecl * functionDecl ) {
718                GuardValue( returnVals );
719                returnVals = functionDecl->get_functionType()->get_returnVals();
720        }
721
722        void ReturnChecker::previsit( ReturnStmt * returnStmt ) {
723                // Previously this also checked for the existence of an expr paired with no return values on
724                // the  function return type. This is incorrect, since you can have an expression attached to
725                // a return statement in a void-returning function in C. The expression is treated as if it
726                // were cast to void.
727                if ( ! returnStmt->get_expr() && returnVals.size() != 0 ) {
728                        SemanticError( returnStmt, "Non-void function returns no values: " );
729                }
730        }
731
732
733        void ReplaceTypedef::replaceTypedef( std::list< Declaration * > &translationUnit ) {
734                PassVisitor<ReplaceTypedef> eliminator;
735                mutateAll( translationUnit, eliminator );
736                if ( eliminator.pass.typedefNames.count( "size_t" ) ) {
737                        // grab and remember declaration of size_t
738                        Validate::SizeType = eliminator.pass.typedefNames["size_t"].first->base->clone();
739                } else {
740                        // xxx - missing global typedef for size_t - default to long unsigned int, even though that may be wrong
741                        // eventually should have a warning for this case.
742                        Validate::SizeType = new BasicType( Type::Qualifiers(), BasicType::LongUnsignedInt );
743                }
744        }
745
746        void ReplaceTypedef::premutate( QualifiedType * ) {
747                visit_children = false;
748        }
749
750        Type * ReplaceTypedef::postmutate( QualifiedType * qualType ) {
751                // replacing typedefs only makes sense for the 'oldest ancestor' of the qualified type
752                qualType->parent = qualType->parent->acceptMutator( * visitor );
753                return qualType;
754        }
755
756        static bool isNonParameterAttribute( Attribute * attr ) {
757                static const std::vector<std::string> bad_names = {
758                        "aligned", "__aligned__",
759                };
760                for ( auto name : bad_names ) {
761                        if ( name == attr->name ) {
762                                return true;
763                        }
764                }
765                return false;
766        }
767
768        Type * ReplaceTypedef::postmutate( TypeInstType * typeInst ) {
769                // instances of typedef types will come here. If it is an instance
770                // of a typdef type, link the instance to its actual type.
771                TypedefMap::const_iterator def = typedefNames.find( typeInst->name );
772                if ( def != typedefNames.end() ) {
773                        Type * ret = def->second.first->base->clone();
774                        ret->location = typeInst->location;
775                        ret->get_qualifiers() |= typeInst->get_qualifiers();
776                        // GCC ignores certain attributes if they arrive by typedef, this mimics that.
777                        if ( inFunctionType ) {
778                                ret->attributes.remove_if( isNonParameterAttribute );
779                        }
780                        ret->attributes.splice( ret->attributes.end(), typeInst->attributes );
781                        // place instance parameters on the typedef'd type
782                        if ( ! typeInst->parameters.empty() ) {
783                                ReferenceToType * rtt = dynamic_cast<ReferenceToType *>(ret);
784                                if ( ! rtt ) {
785                                        SemanticError( typeInst->location, "Cannot apply type parameters to base type of " + typeInst->name );
786                                }
787                                rtt->parameters.clear();
788                                cloneAll( typeInst->parameters, rtt->parameters );
789                                mutateAll( rtt->parameters, * visitor );  // recursively fix typedefs on parameters
790                        } // if
791                        delete typeInst;
792                        return ret;
793                } else {
794                        TypeDeclMap::const_iterator base = typedeclNames.find( typeInst->name );
795                        if ( base == typedeclNames.end() ) {
796                                SemanticError( typeInst->location, toString("Use of undefined type ", typeInst->name) );
797                        }
798                        typeInst->set_baseType( base->second );
799                        return typeInst;
800                } // if
801                assert( false );
802        }
803
804        struct VarLenChecker : WithShortCircuiting {
805                void previsit( FunctionType * ) { visit_children = false; }
806                void previsit( ArrayType * at ) {
807                        isVarLen |= at->isVarLen;
808                }
809                bool isVarLen = false;
810        };
811
812        bool isVariableLength( Type * t ) {
813                PassVisitor<VarLenChecker> varLenChecker;
814                maybeAccept( t, varLenChecker );
815                return varLenChecker.pass.isVarLen;
816        }
817
818        Declaration * ReplaceTypedef::postmutate( TypedefDecl * tyDecl ) {
819                if ( typedefNames.count( tyDecl->name ) == 1 && typedefNames[ tyDecl->name ].second == scopeLevel ) {
820                        // typedef to the same name from the same scope
821                        // must be from the same type
822
823                        Type * t1 = tyDecl->base;
824                        Type * t2 = typedefNames[ tyDecl->name ].first->base;
825                        if ( ! ResolvExpr::typesCompatible( t1, t2, Indexer() ) ) {
826                                SemanticError( tyDecl->location, "Cannot redefine typedef: " + tyDecl->name );
827                        }
828                        // Cannot redefine VLA typedefs. Note: this is slightly incorrect, because our notion of VLAs
829                        // at this point in the translator is imprecise. In particular, this will disallow redefining typedefs
830                        // with arrays whose dimension is an enumerator or a cast of a constant/enumerator. The effort required
831                        // to fix this corner case likely outweighs the utility of allowing it.
832                        if ( isVariableLength( t1 ) || isVariableLength( t2 ) ) {
833                                SemanticError( tyDecl->location, "Cannot redefine typedef: " + tyDecl->name );
834                        }
835                } else {
836                        typedefNames[ tyDecl->name ] = std::make_pair( TypedefDeclPtr( tyDecl ), scopeLevel );
837                } // if
838
839                // When a typedef is a forward declaration:
840                //    typedef struct screen SCREEN;
841                // the declaration portion must be retained:
842                //    struct screen;
843                // because the expansion of the typedef is:
844                //    void rtn( SCREEN * p ) => void rtn( struct screen * p )
845                // hence the type-name "screen" must be defined.
846                // Note, qualifiers on the typedef are superfluous for the forward declaration.
847
848                Type * designatorType = tyDecl->base->stripDeclarator();
849                if ( StructInstType * aggDecl = dynamic_cast< StructInstType * >( designatorType ) ) {
850                        declsToAddBefore.push_back( new StructDecl( aggDecl->name, AggregateDecl::Struct, noAttributes, tyDecl->linkage ) );
851                } else if ( UnionInstType * aggDecl = dynamic_cast< UnionInstType * >( designatorType ) ) {
852                        declsToAddBefore.push_back( new UnionDecl( aggDecl->name, noAttributes, tyDecl->linkage ) );
853                } else if ( EnumInstType * enumInst = dynamic_cast< EnumInstType * >( designatorType ) ) {
854                        if ( enumInst->baseEnum ) {
855                                const EnumDecl * enumDecl = enumInst->baseEnum;
856                                declsToAddBefore.push_back( new EnumDecl( enumDecl->name, noAttributes, enumDecl->isTyped, tyDecl->linkage, enumDecl->base ) );
857                        } else {
858                                declsToAddBefore.push_back( new EnumDecl( enumInst->name, noAttributes, tyDecl->linkage ) );
859                        }
860                } // if
861                return tyDecl->clone();
862        }
863
864        void ReplaceTypedef::premutate( TypeDecl * typeDecl ) {
865                TypedefMap::iterator i = typedefNames.find( typeDecl->name );
866                if ( i != typedefNames.end() ) {
867                        typedefNames.erase( i ) ;
868                } // if
869
870                typedeclNames.insert( typeDecl->name, typeDecl );
871        }
872
873        void ReplaceTypedef::premutate( FunctionDecl * ) {
874                GuardScope( typedefNames );
875                GuardScope( typedeclNames );
876        }
877
878        void ReplaceTypedef::premutate( ObjectDecl * ) {
879                GuardScope( typedefNames );
880                GuardScope( typedeclNames );
881        }
882
883        DeclarationWithType * ReplaceTypedef::postmutate( ObjectDecl * objDecl ) {
884                if ( FunctionType * funtype = dynamic_cast<FunctionType *>( objDecl->type ) ) { // function type?
885                        // replace the current object declaration with a function declaration
886                        FunctionDecl * newDecl = new FunctionDecl( objDecl->name, objDecl->get_storageClasses(), objDecl->linkage, funtype, 0, objDecl->attributes, objDecl->get_funcSpec() );
887                        objDecl->attributes.clear();
888                        objDecl->set_type( nullptr );
889                        delete objDecl;
890                        return newDecl;
891                } // if
892                return objDecl;
893        }
894
895        void ReplaceTypedef::premutate( CastExpr * ) {
896                GuardScope( typedefNames );
897                GuardScope( typedeclNames );
898        }
899
900        void ReplaceTypedef::premutate( CompoundStmt * ) {
901                GuardScope( typedefNames );
902                GuardScope( typedeclNames );
903                scopeLevel += 1;
904                GuardAction( [this](){ scopeLevel -= 1; } );
905        }
906
907        template<typename AggDecl>
908        void ReplaceTypedef::addImplicitTypedef( AggDecl * aggDecl ) {
909                if ( typedefNames.count( aggDecl->get_name() ) == 0 ) {
910                        Type * type = nullptr;
911                        if ( StructDecl * newDeclStructDecl = dynamic_cast< StructDecl * >( aggDecl ) ) {
912                                type = new StructInstType( Type::Qualifiers(), newDeclStructDecl->get_name() );
913                        } else if ( UnionDecl * newDeclUnionDecl = dynamic_cast< UnionDecl * >( aggDecl ) ) {
914                                type = new UnionInstType( Type::Qualifiers(), newDeclUnionDecl->get_name() );
915                        } else if ( EnumDecl * newDeclEnumDecl = dynamic_cast< EnumDecl * >( aggDecl )  ) {
916                                type = new EnumInstType( Type::Qualifiers(), newDeclEnumDecl->get_name() );
917                        } // if
918                        TypedefDeclPtr tyDecl( new TypedefDecl( aggDecl->get_name(), aggDecl->location, Type::StorageClasses(), type, aggDecl->get_linkage() ) );
919                        typedefNames[ aggDecl->get_name() ] = std::make_pair( std::move( tyDecl ), scopeLevel );
920                        // add the implicit typedef to the AST
921                        declsToAddBefore.push_back( new TypedefDecl( aggDecl->get_name(), aggDecl->location, Type::StorageClasses(), type->clone(), aggDecl->get_linkage() ) );
922                } // if
923        }
924
925        template< typename AggDecl >
926        void ReplaceTypedef::handleAggregate( AggDecl * aggr ) {
927                SemanticErrorException errors;
928
929                ValueGuard< std::list<Declaration * > > oldBeforeDecls( declsToAddBefore );
930                ValueGuard< std::list<Declaration * > > oldAfterDecls ( declsToAddAfter  );
931                declsToAddBefore.clear();
932                declsToAddAfter.clear();
933
934                GuardScope( typedefNames );
935                GuardScope( typedeclNames );
936                mutateAll( aggr->parameters, * visitor );
937                mutateAll( aggr->attributes, * visitor );
938
939                // unroll mutateAll for aggr->members so that implicit typedefs for nested types are added to the aggregate body.
940                for ( std::list< Declaration * >::iterator i = aggr->members.begin(); i != aggr->members.end(); ++i ) {
941                        if ( !declsToAddAfter.empty() ) { aggr->members.splice( i, declsToAddAfter ); }
942
943                        try {
944                                * i = maybeMutate( * i, * visitor );
945                        } catch ( SemanticErrorException &e ) {
946                                errors.append( e );
947                        }
948
949                        if ( !declsToAddBefore.empty() ) { aggr->members.splice( i, declsToAddBefore ); }
950                }
951
952                if ( !declsToAddAfter.empty() ) { aggr->members.splice( aggr->members.end(), declsToAddAfter ); }
953                if ( !errors.isEmpty() ) { throw errors; }
954        }
955
956        void ReplaceTypedef::premutate( StructDecl * structDecl ) {
957                visit_children = false;
958                addImplicitTypedef( structDecl );
959                handleAggregate( structDecl );
960        }
961
962        void ReplaceTypedef::premutate( UnionDecl * unionDecl ) {
963                visit_children = false;
964                addImplicitTypedef( unionDecl );
965                handleAggregate( unionDecl );
966        }
967
968        void ReplaceTypedef::premutate( EnumDecl * enumDecl ) {
969                addImplicitTypedef( enumDecl );
970        }
971
972        void ReplaceTypedef::premutate( FunctionType * ) {
973                GuardValue( inFunctionType );
974                inFunctionType = true;
975        }
976
977        void ReplaceTypedef::premutate( TraitDecl * ) {
978                GuardScope( typedefNames );
979                GuardScope( typedeclNames);
980        }
981
982        void VerifyCtorDtorAssign::verify( std::list< Declaration * > & translationUnit ) {
983                PassVisitor<VerifyCtorDtorAssign> verifier;
984                acceptAll( translationUnit, verifier );
985        }
986
987        void VerifyCtorDtorAssign::previsit( FunctionDecl * funcDecl ) {
988                FunctionType * funcType = funcDecl->get_functionType();
989                std::list< DeclarationWithType * > &returnVals = funcType->get_returnVals();
990                std::list< DeclarationWithType * > &params = funcType->get_parameters();
991
992                if ( CodeGen::isCtorDtorAssign( funcDecl->get_name() ) ) { // TODO: also check /=, etc.
993                        if ( params.size() == 0 ) {
994                                SemanticError( funcDecl->location, "Constructors, destructors, and assignment functions require at least one parameter." );
995                        }
996                        ReferenceType * refType = dynamic_cast< ReferenceType * >( params.front()->get_type() );
997                        if ( ! refType ) {
998                                SemanticError( funcDecl->location, "First parameter of a constructor, destructor, or assignment function must be a reference." );
999                        }
1000                        if ( CodeGen::isCtorDtor( funcDecl->get_name() ) && returnVals.size() != 0 ) {
1001                                if(!returnVals.front()->get_type()->isVoid()) {
1002                                        SemanticError( funcDecl->location, "Constructors and destructors cannot have explicit return values." );
1003                                }
1004                        }
1005                }
1006        }
1007
1008        // Test for special name on a generic parameter.  Special treatment for the
1009        // special name is a bootstrapping hack.  In most cases, the worlds of T's
1010        // and of N's don't overlap (normal treamtemt).  The foundations in
1011        // array.hfa use tagging for both types and dimensions.  Tagging treats
1012        // its subject parameter even more opaquely than T&, which assumes it is
1013        // possible to have a pointer/reference to such an object.  Tagging only
1014        // seeks to identify the type-system resident at compile time.  Both N's
1015        // and T's can make tags.  The tag definition uses the special name, which
1016        // is treated as "an N or a T."  This feature is not inteded to be used
1017        // outside of the definition and immediate uses of a tag.
1018        static inline bool isReservedTysysIdOnlyName( const std::string & name ) {
1019                // name's prefix was __CFA_tysys_id_only, before it got wrapped in __..._generic
1020                int foundAt = name.find("__CFA_tysys_id_only");
1021                if (foundAt == 0) return true;
1022                if (foundAt == 2 && name[0] == '_' && name[1] == '_') return true;
1023                return false;
1024        }
1025
1026        template< typename Aggr >
1027        void validateGeneric( Aggr * inst ) {
1028                std::list< TypeDecl * > * params = inst->get_baseParameters();
1029                if ( params ) {
1030                        std::list< Expression * > & args = inst->get_parameters();
1031
1032                        // insert defaults arguments when a type argument is missing (currently only supports missing arguments at the end of the list).
1033                        // A substitution is used to ensure that defaults are replaced correctly, e.g.,
1034                        //   forall(otype T, otype alloc = heap_allocator(T)) struct vector;
1035                        //   vector(int) v;
1036                        // after insertion of default values becomes
1037                        //   vector(int, heap_allocator(T))
1038                        // and the substitution is built with T=int so that after substitution, the result is
1039                        //   vector(int, heap_allocator(int))
1040                        TypeSubstitution sub;
1041                        auto paramIter = params->begin();
1042                        auto argIter = args.begin();
1043                        for ( ; paramIter != params->end(); ++paramIter, ++argIter ) {
1044                                if ( argIter != args.end() ) {
1045                                        TypeExpr * expr = dynamic_cast< TypeExpr * >( * argIter );
1046                                        if ( expr ) {
1047                                                sub.add( (* paramIter)->get_name(), expr->get_type()->clone() );
1048                                        }
1049                                } else {
1050                                        Type * defaultType = (* paramIter)->get_init();
1051                                        if ( defaultType ) {
1052                                                args.push_back( new TypeExpr( defaultType->clone() ) );
1053                                                sub.add( (* paramIter)->get_name(), defaultType->clone() );
1054                                                argIter = std::prev(args.end());
1055                                        } else {
1056                                                SemanticError( inst, "Too few type arguments in generic type " );
1057                                        }
1058                                }
1059                                assert( argIter != args.end() );
1060                                bool typeParamDeclared = (*paramIter)->kind != TypeDecl::Kind::Dimension;
1061                                bool typeArgGiven;
1062                                if ( isReservedTysysIdOnlyName( (*paramIter)->name ) ) {
1063                                        // coerce a match when declaration is reserved name, which means "either"
1064                                        typeArgGiven = typeParamDeclared;
1065                                } else {
1066                                        typeArgGiven = dynamic_cast< TypeExpr * >( * argIter );
1067                                }
1068                                if ( ! typeParamDeclared &&   typeArgGiven ) SemanticError( inst, "Type argument given for value parameter: " );
1069                                if (   typeParamDeclared && ! typeArgGiven ) SemanticError( inst, "Expression argument given for type parameter: " );
1070                        }
1071
1072                        sub.apply( inst );
1073                        if ( args.size() > params->size() ) SemanticError( inst, "Too many type arguments in generic type " );
1074                }
1075        }
1076
1077        void ValidateGenericParameters::previsit( StructInstType * inst ) {
1078                validateGeneric( inst );
1079        }
1080
1081        void ValidateGenericParameters::previsit( UnionInstType * inst ) {
1082                validateGeneric( inst );
1083        }
1084
1085        void TranslateDimensionGenericParameters::translateDimensions( std::list< Declaration * > &translationUnit ) {
1086                PassVisitor<TranslateDimensionGenericParameters> translator;
1087                mutateAll( translationUnit, translator );
1088        }
1089
1090        TranslateDimensionGenericParameters::TranslateDimensionGenericParameters() : WithIndexer( false ) {}
1091
1092        // Declaration of type variable:           forall( [N] )          ->  forall( N & | sized( N ) )
1093        TypeDecl * TranslateDimensionGenericParameters::postmutate( TypeDecl * td ) {
1094                if ( td->kind == TypeDecl::Dimension ) {
1095                        td->kind = TypeDecl::Dtype;
1096                        if ( ! isReservedTysysIdOnlyName( td->name ) ) {
1097                                td->sized = true;
1098                        }
1099                }
1100                return td;
1101        }
1102
1103        // Situational awareness:
1104        // array( float, [[currentExpr]]     )  has  visitingChildOfSUIT == true
1105        // array( float, [[currentExpr]] - 1 )  has  visitingChildOfSUIT == false
1106        // size_t x =    [[currentExpr]]        has  visitingChildOfSUIT == false
1107        void TranslateDimensionGenericParameters::changeState_ChildOfSUIT( bool newVal ) {
1108                GuardValue( nextVisitedNodeIsChildOfSUIT );
1109                GuardValue( visitingChildOfSUIT );
1110                visitingChildOfSUIT = nextVisitedNodeIsChildOfSUIT;
1111                nextVisitedNodeIsChildOfSUIT = newVal;
1112        }
1113        void TranslateDimensionGenericParameters::premutate( StructInstType * sit ) {
1114                (void) sit;
1115                changeState_ChildOfSUIT(true);
1116        }
1117        void TranslateDimensionGenericParameters::premutate( UnionInstType * uit ) {
1118                (void) uit;
1119                changeState_ChildOfSUIT(true);
1120        }
1121        void TranslateDimensionGenericParameters::premutate( BaseSyntaxNode * node ) {
1122                (void) node;
1123                changeState_ChildOfSUIT(false);
1124        }
1125
1126        // Passing values as dimension arguments:  array( float,     7 )  -> array( float, char[             7 ] )
1127        // Consuming dimension parameters:         size_t x =    N - 1 ;  -> size_t x =          sizeof(N) - 1   ;
1128        // Intertwined reality:                    array( float, N     )  -> array( float,              N        )
1129        //                                         array( float, N - 1 )  -> array( float, char[ sizeof(N) - 1 ] )
1130        // Intertwined case 1 is not just an optimization.
1131        // Avoiding char[sizeof(-)] is necessary to enable the call of f to bind the value of N, in:
1132        //   forall([N]) void f( array(float, N) & );
1133        //   array(float, 7) a;
1134        //   f(a);
1135
1136        Expression * TranslateDimensionGenericParameters::postmutate( DimensionExpr * de ) {
1137                // Expression de is an occurrence of N in LHS of above examples.
1138                // Look up the name that de references.
1139                // If we are in a struct body, then this reference can be to an entry of the stuct's forall list.
1140                // Whether or not we are in a struct body, this reference can be to an entry of a containing function's forall list.
1141                // If we are in a struct body, then the stuct's forall declarations are innermost (functions don't occur in structs).
1142                // Thus, a potential struct's declaration is highest priority.
1143                // A struct's forall declarations are already renamed with _generic_ suffix.  Try that name variant first.
1144
1145                std::string useName = "__" + de->name + "_generic_";
1146                TypeDecl * namedParamDecl = const_cast<TypeDecl *>( strict_dynamic_cast<const TypeDecl *, nullptr >( indexer.lookupType( useName ) ) );
1147
1148                if ( ! namedParamDecl ) {
1149                        useName = de->name;
1150                        namedParamDecl = const_cast<TypeDecl *>( strict_dynamic_cast<const TypeDecl *, nullptr >( indexer.lookupType( useName ) ) );
1151                }
1152
1153                // Expect to find it always.  A misspelled name would have been parsed as an identifier.
1154                assert( namedParamDecl && "Type-system-managed value name not found in symbol table" );
1155
1156                delete de;
1157
1158                TypeInstType * refToDecl = new TypeInstType( 0, useName, namedParamDecl );
1159
1160                if ( visitingChildOfSUIT ) {
1161                        // As in postmutate( Expression * ), topmost expression needs a TypeExpr wrapper
1162                        // But avoid ArrayType-Sizeof
1163                        return new TypeExpr( refToDecl );
1164                } else {
1165                        // the N occurrence is being used directly as a runtime value,
1166                        // if we are in a type instantiation, then the N is within a bigger value computation
1167                        return new SizeofExpr( refToDecl );
1168                }
1169        }
1170
1171        Expression * TranslateDimensionGenericParameters::postmutate( Expression * e ) {
1172                if ( visitingChildOfSUIT ) {
1173                        // e is an expression used as an argument to instantiate a type
1174                        if (! dynamic_cast< TypeExpr * >( e ) ) {
1175                                // e is a value expression
1176                                // but not a DimensionExpr, which has a distinct postmutate
1177                                Type * typeExprContent = new ArrayType( 0, new BasicType( 0, BasicType::Char ), e, true, false );
1178                                TypeExpr * result = new TypeExpr( typeExprContent );
1179                                return result;
1180                        }
1181                }
1182                return e;
1183        }
1184
1185        void CompoundLiteral::premutate( ObjectDecl * objectDecl ) {
1186                storageClasses = objectDecl->get_storageClasses();
1187        }
1188
1189        Expression * CompoundLiteral::postmutate( CompoundLiteralExpr * compLitExpr ) {
1190                // transform [storage_class] ... (struct S){ 3, ... };
1191                // into [storage_class] struct S temp =  { 3, ... };
1192                static UniqueName indexName( "_compLit" );
1193
1194                ObjectDecl * tempvar = new ObjectDecl( indexName.newName(), storageClasses, LinkageSpec::C, nullptr, compLitExpr->get_result(), compLitExpr->get_initializer() );
1195                compLitExpr->set_result( nullptr );
1196                compLitExpr->set_initializer( nullptr );
1197                delete compLitExpr;
1198                declsToAddBefore.push_back( tempvar );                                  // add modified temporary to current block
1199                return new VariableExpr( tempvar );
1200        }
1201
1202        void ReturnTypeFixer::fix( std::list< Declaration * > &translationUnit ) {
1203                PassVisitor<ReturnTypeFixer> fixer;
1204                acceptAll( translationUnit, fixer );
1205        }
1206
1207        void ReturnTypeFixer::postvisit( FunctionDecl * functionDecl ) {
1208                FunctionType * ftype = functionDecl->get_functionType();
1209                std::list< DeclarationWithType * > & retVals = ftype->get_returnVals();
1210                assertf( retVals.size() == 0 || retVals.size() == 1, "Function %s has too many return values: %zu", functionDecl->get_name().c_str(), retVals.size() );
1211                if ( retVals.size() == 1 ) {
1212                        // ensure all function return values have a name - use the name of the function to disambiguate (this also provides a nice bit of help for debugging).
1213                        // ensure other return values have a name.
1214                        DeclarationWithType * ret = retVals.front();
1215                        if ( ret->get_name() == "" ) {
1216                                ret->set_name( toString( "_retval_", CodeGen::genName( functionDecl ) ) );
1217                        }
1218                        ret->get_attributes().push_back( new Attribute( "unused" ) );
1219                }
1220        }
1221
1222        void ReturnTypeFixer::postvisit( FunctionType * ftype ) {
1223                // xxx - need to handle named return values - this information needs to be saved somehow
1224                // so that resolution has access to the names.
1225                // Note that this pass needs to happen early so that other passes which look for tuple types
1226                // find them in all of the right places, including function return types.
1227                std::list< DeclarationWithType * > & retVals = ftype->get_returnVals();
1228                if ( retVals.size() > 1 ) {
1229                        // generate a single return parameter which is the tuple of all of the return values
1230                        TupleType * tupleType = strict_dynamic_cast< TupleType * >( ResolvExpr::extractResultType( ftype ) );
1231                        // ensure return value is not destructed by explicitly creating an empty ListInit node wherein maybeConstruct is false.
1232                        ObjectDecl * newRet = new ObjectDecl( "", Type::StorageClasses(), LinkageSpec::Cforall, 0, tupleType, new ListInit( std::list<Initializer *>(), noDesignators, false ) );
1233                        deleteAll( retVals );
1234                        retVals.clear();
1235                        retVals.push_back( newRet );
1236                }
1237        }
1238
1239        void FixObjectType::fix( std::list< Declaration * > & translationUnit ) {
1240                PassVisitor<FixObjectType> fixer;
1241                acceptAll( translationUnit, fixer );
1242        }
1243
1244        void FixObjectType::previsit( ObjectDecl * objDecl ) {
1245                Type * new_type = ResolvExpr::resolveTypeof( objDecl->get_type(), indexer );
1246                objDecl->set_type( new_type );
1247        }
1248
1249        void FixObjectType::previsit( FunctionDecl * funcDecl ) {
1250                Type * new_type = ResolvExpr::resolveTypeof( funcDecl->type, indexer );
1251                funcDecl->set_type( new_type );
1252        }
1253
1254        void FixObjectType::previsit( TypeDecl * typeDecl ) {
1255                if ( typeDecl->get_base() ) {
1256                        Type * new_type = ResolvExpr::resolveTypeof( typeDecl->get_base(), indexer );
1257                        typeDecl->set_base( new_type );
1258                } // if
1259        }
1260
1261        void InitializerLength::computeLength( std::list< Declaration * > & translationUnit ) {
1262                PassVisitor<InitializerLength> len;
1263                acceptAll( translationUnit, len );
1264        }
1265
1266        void ArrayLength::computeLength( std::list< Declaration * > & translationUnit ) {
1267                PassVisitor<ArrayLength> len;
1268                acceptAll( translationUnit, len );
1269        }
1270
1271        void InitializerLength::previsit( ObjectDecl * objDecl ) {
1272                if ( ArrayType * at = dynamic_cast< ArrayType * >( objDecl->type ) ) {
1273                        if ( at->dimension ) return;
1274                        if ( ListInit * init = dynamic_cast< ListInit * >( objDecl->init ) ) {
1275                                at->dimension = new ConstantExpr( Constant::from_ulong( init->initializers.size() ) );
1276                        }
1277                }
1278        }
1279
1280        void ArrayLength::previsit( ArrayType * type ) {
1281                if ( type->dimension ) {
1282                        // need to resolve array dimensions early so that constructor code can correctly determine
1283                        // if a type is a VLA (and hence whether its elements need to be constructed)
1284                        ResolvExpr::findSingleExpression( type->dimension, Validate::SizeType->clone(), indexer );
1285
1286                        // must re-evaluate whether a type is a VLA, now that more information is available
1287                        // (e.g. the dimension may have been an enumerator, which was unknown prior to this step)
1288                        type->isVarLen = ! InitTweak::isConstExpr( type->dimension );
1289                }
1290        }
1291
1292        struct LabelFinder {
1293                std::set< Label > & labels;
1294                LabelFinder( std::set< Label > & labels ) : labels( labels ) {}
1295                void previsit( Statement * stmt ) {
1296                        for ( Label & l : stmt->labels ) {
1297                                labels.insert( l );
1298                        }
1299                }
1300        };
1301
1302        void LabelAddressFixer::premutate( FunctionDecl * funcDecl ) {
1303                GuardValue( labels );
1304                PassVisitor<LabelFinder> finder( labels );
1305                funcDecl->accept( finder );
1306        }
1307
1308        Expression * LabelAddressFixer::postmutate( AddressExpr * addrExpr ) {
1309                // convert &&label into label address
1310                if ( AddressExpr * inner = dynamic_cast< AddressExpr * >( addrExpr->arg ) ) {
1311                        if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( inner->arg ) ) {
1312                                if ( labels.count( nameExpr->name ) ) {
1313                                        Label name = nameExpr->name;
1314                                        delete addrExpr;
1315                                        return new LabelAddressExpr( name );
1316                                }
1317                        }
1318                }
1319                return addrExpr;
1320        }
1321
1322} // namespace SymTab
1323
1324// Local Variables: //
1325// tab-width: 4 //
1326// mode: c++ //
1327// compile-command: "make install" //
1328// End: //
Note: See TracBrowser for help on using the repository browser.