Changeset 67d2b97 for src

Timestamp:

Jun 24, 2019, 2:24:57 PM (5 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

093a5d7, da7454c

Parents:

70a141d4 (diff), 08c0780 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:

src

Files:

• AST/Convert.cpp (modified) (1 diff)
• AST/Fwd.hpp (modified) (2 diffs)
• AST/Node.hpp (modified) (2 diffs)
• AST/TypeSubstitution.hpp (modified) (1 diff)
• ResolvExpr/CandidateFinder.cpp (modified) (2 diffs)
• ResolvExpr/ConversionCost.cc (modified) (2 diffs)
• ResolvExpr/ConversionCost.h (modified) (3 diffs)
• ResolvExpr/PtrsAssignable.cc (modified) (2 diffs)
• ResolvExpr/Resolver.cc (modified) (2 diffs)
• ResolvExpr/Resolver.h (modified) (2 diffs)
• ResolvExpr/typeops.h (modified) (1 diff)
• SymTab/Validate.cc (modified) (3 diffs)
• SymTab/Validate.h (modified) (2 diffs)

src/AST/Convert.cpp

@@ -1895 +1895 @@
                 };
                 stmt->orElse = {
-                        GET_ACCEPT_1(timeout.statement, Stmt),
-                        GET_ACCEPT_1(timeout.condition, Expr),
+                        GET_ACCEPT_1(orelse.statement, Stmt),
+                        GET_ACCEPT_1(orelse.condition, Expr),
                 };
 

src/AST/Fwd.hpp

@@ -10 +10 @@
 // Created On       : Wed May  8 16:05:00 2019
 // Last Modified By : Andrew Beach
-// Last Modified On : Thr May  9 13:09:00 2019
-// Update Count     : 0
+// Last Modified On : Mon Jun 24 09:48:00 2019
+// Update Count     : 1
 //
 
@@ -129 +129 @@
 class Attribute;
 
+class SymbolTable;
+class TypeEnvironment;
 class TypeSubstitution;
 

src/AST/Node.hpp

@@ -100 +100 @@
 
 /// Mutate a node field (only clones if not equal to existing value)
-template<typename node_t, typename field_t, typename assn_t>
-const node_t * mutate_field( const node_t * node, field_t node_t::* field, assn_t && val ) {
+template<typename node_t, typename parent_t, typename field_t, typename assn_t>
+const node_t * mutate_field( const node_t * node, field_t parent_t::* field, assn_t && val ) {
         // skip mutate if equivalent
         if ( node->*field == val ) return node;
@@ -112 +112 @@
 
 /// Mutate a single index of a node field (only clones if not equal to existing value)
-template<typename node_t, typename coll_t, typename ind_t, typename field_t>
+template<typename node_t, typename parent_t, typename coll_t, typename ind_t, typename field_t>
 const node_t * mutate_field_index(
-        const node_t * node, coll_t node_t::* field, ind_t i, field_t && val
+        const node_t * node, coll_t parent_t::* field, ind_t i, field_t && val
 ) {
         // skip mutate if equivalent

src/AST/TypeSubstitution.hpp

@@ -200 +200 @@
 }
 
-/// Instantiate each member of the context given the actual parameters specified, and store the
-/// instantiations for use by the indexer
-template< typename FormalIterator, typename ActualIterator, typename MemberIterator, typename OutputIterator >
-void applySubstitution( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actual, MemberIterator memberBegin, MemberIterator memberEnd, OutputIterator out ) {
-        TypeSubstitution sub = TypeSubstitution( formalBegin, formalEnd, actual );
-        for ( auto i = memberBegin; i != memberEnd; ++i ) {
-                sub.apply( *i );
-                *out++ = *i;
-        } // for
-}
-
 } // namespace ast
 

src/ResolvExpr/CandidateFinder.cpp

@@ -1003 +1003 @@
                         assert( toType );
                         toType = resolveTypeof( toType, symtab );
-                        toType = SymTab::validateType( toType, symtab );
+                        toType = SymTab::validateType( castExpr->location, toType, symtab );
                         toType = adjustExprType( toType, tenv, symtab );
 
@@ -1410 +1410 @@
                                 // calculate target type
                                 const ast::Type * toType = resolveTypeof( initAlt.type, symtab );
-                                toType = SymTab::validateType( toType, symtab );
+                                toType = SymTab::validateType( initExpr->location, toType, symtab );
                                 toType = adjustExprType( toType, tenv, symtab );
                                 // The call to find must occur inside this loop, otherwise polymorphic return 

src/ResolvExpr/ConversionCost.cc

@@ -9 +9 @@
 // Author           : Richard C. Bilson
 // Created On       : Sun May 17 07:06:19 2015
-// Last Modified By : Peter A. Buhr
-// Last Modified On : Mon May  6 14:18:22 2019
-// Update Count     : 25
+// Last Modified By : Andrew Beach
+// Last Modified On : Mon Jun 24 13:33:00 2019
+// Update Count     : 26
 //
 
@@ -489 +489 @@
         }
 
-        Cost conversionCost( 
-                const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab, 
-                const ast::TypeEnvironment & env
-        ) {
-                #warning unimplemented
-                (void)src; (void)dst; (void)symtab; (void)env;
-                assert(false);
+static int localPtrsAssignable(const ast::Type * t1, const ast::Type * t2,
+                const ast::SymbolTable &, const ast::TypeEnvironment & env ) {
+        return ptrsAssignable( t1, t2, env );
+}
+
+// TODO: This is used for overload resolution. It might be able to be dropped once the old system
+// is removed.
+static Cost localConversionCost(
+        const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
+        const ast::TypeEnvironment & env
+) { return conversionCost( src, dst, symtab, env ); }
+
+Cost conversionCost(
+        const ast::Type * src, const ast::Type * dst, const ast::SymbolTable & symtab,
+        const ast::TypeEnvironment & env
+) {
+        if ( const ast::TypeInstType * inst = dynamic_cast< const ast::TypeInstType * >( dst ) ) {
+                if ( const ast::EqvClass * eqv = env.lookup( inst->name ) ) {
+                        if ( eqv->bound ) {
+                                return conversionCost(src, eqv->bound, symtab, env );
+                        } else {
+                                return Cost::infinity;
+                        }
+                } else if ( const ast::NamedTypeDecl * named = symtab.lookupType( inst->name ) ) {
+                        const ast::TypeDecl * type = dynamic_cast< const ast::TypeDecl * >( named );
+                        assertf( type, "Unexpected typedef." );
+                        if ( type->base ) {
+                                return conversionCost( src, type->base, symtab, env ) + Cost::safe;
+                        }
+                }
+        }
+        if ( typesCompatibleIgnoreQualifiers( src, dst, symtab, env ) ) {
                 return Cost::zero;
-        }
+        } else if ( dynamic_cast< const ast::VoidType * >( dst ) ) {
+                return Cost::safe;
+        } else if ( const ast::ReferenceType * refType =
+                         dynamic_cast< const ast::ReferenceType * >( dst ) ) {
+                return convertToReferenceCost( src, refType, symtab, env, localPtrsAssignable );
+        } else {
+                ast::Pass<ConversionCost_new> converter( dst, symtab, env, localConversionCost );
+                src->accept( converter );
+                return converter.pass.cost;
+        }
+}
+
+Cost convertToReferenceCost( const ast::Type * src, const ast::Type * dst, int diff,
+                const ast::SymbolTable & symtab, const ast::TypeEnvironment & env,
+                NumCostCalculation func ) {
+        if ( 0 < diff ) {
+                Cost cost = convertToReferenceCost(
+                        strict_dynamic_cast< const ast::ReferenceType * >( src )->base,
+                        dst, (diff - 1), symtab, env, func );
+                cost.incReference();
+                return cost;
+        } else if ( diff < -1 ) {
+                Cost cost = convertToReferenceCost(
+                        src, strict_dynamic_cast< const ast::ReferenceType * >( dst )->base,
+                        (diff + 1), symtab, env, func );
+                cost.incReference();
+                return cost;
+        } else if ( 0 == diff ) {
+                const ast::ReferenceType * srcAsRef = dynamic_cast< const ast::ReferenceType * >( src );
+                const ast::ReferenceType * dstAsRef = dynamic_cast< const ast::ReferenceType * >( dst );
+                if ( srcAsRef && dstAsRef ) {
+                        ast::CV::Qualifiers tq1 = srcAsRef->base->qualifiers;
+                        ast::CV::Qualifiers tq2 = dstAsRef->base->qualifiers;
+                        if ( tq1 <= tq2 && typesCompatibleIgnoreQualifiers(
+                                        srcAsRef->base, dstAsRef->base, symtab, env ) ) {
+                                if ( tq1 == tq2 ) {
+                                        return Cost::zero;
+                                } else {
+                                        return Cost::safe;
+                                }
+                        } else {
+                                int assignResult = func( srcAsRef->base, dstAsRef->base, symtab, env );
+                                if ( 0 < assignResult ) {
+                                        return Cost::safe;
+                                } else if ( assignResult < 0 ) {
+                                        return Cost::unsafe;
+                                }
+                        }
+                } else {
+                        ast::Pass<ConversionCost_new> converter( dst, symtab, env, localConversionCost );
+                        src->accept( converter );
+                        return converter.pass.cost;
+                }
+        } else {
+                assert( -1 == diff );
+                const ast::ReferenceType * dstAsRef = dynamic_cast< const ast::ReferenceType * >( dst );
+                assert( dstAsRef );
+                if ( typesCompatibleIgnoreQualifiers( src, dstAsRef->base, symtab, env ) ) {
+                        if ( src->is_lvalue() ) {
+                                if ( src->qualifiers == dstAsRef->base->qualifiers ) {
+                                        return Cost::reference;
+                                } else if ( src->qualifiers < dstAsRef->base->qualifiers ) {
+                                        return Cost::safe;
+                                } else {
+                                        return Cost::unsafe;
+                                }
+                        } else if ( dstAsRef->base->is_const() ) {
+                                return Cost::safe;
+                        } else {
+                                return Cost::unsafe;
+                        }
+                }
+        }
+        return Cost::infinity;
+}
+
+Cost convertToReferenceCost( const ast::Type * src, const ast::ReferenceType * dst,
+            const ast::SymbolTable & symtab, const ast::TypeEnvironment & env,
+                NumCostCalculation func ) {
+        int sdepth = src->referenceDepth(), ddepth = dst->referenceDepth();
+        return convertToReferenceCost( src, dst, sdepth - ddepth, symtab, env, func );
+}
+
+void ConversionCost_new::postvisit( const ast::VoidType * voidType ) {
+        (void)voidType;
+        cost = Cost::infinity;
+}
+
+void ConversionCost_new::postvisit( const ast::BasicType * basicType ) {
+        if ( const ast::BasicType * dstAsBasic = dynamic_cast< const ast::BasicType * >( dst ) ) {
+                int tableResult = costMatrix[ basicType->kind ][ dstAsBasic->kind ];
+                if ( tableResult == -1 ) {
+                        cost = Cost::unsafe;
+                } else {
+                        cost = Cost::zero;
+                        cost.incSafe( tableResult );
+                        cost.incSign( signMatrix[ basicType->kind ][ dstAsBasic->kind ] );
+                }
+        } else if ( dynamic_cast< const ast::EnumInstType * >( dst ) ) {
+                // xxx - not positive this is correct, but appears to allow casting int => enum
+                cost = Cost::unsafe;
+        }
+}
+
+void ConversionCost_new::postvisit( const ast::PointerType * pointerType ) {
+        if ( const ast::PointerType * dstAsPtr = dynamic_cast< const ast::PointerType * >( dst ) ) {
+                ast::CV::Qualifiers tq1 = pointerType->base->qualifiers;
+                ast::CV::Qualifiers tq2 = dstAsPtr->base->qualifiers;
+                if ( tq1 <= tq2 && typesCompatibleIgnoreQualifiers(
+                                pointerType->base, dstAsPtr->base, symtab, env ) ) {
+                        if ( tq1 == tq2 ) {
+                                cost = Cost::zero;
+                        } else {
+                                cost = Cost::safe;
+                        }
+                } else {
+                        int assignResult = ptrsAssignable( pointerType->base, dstAsPtr->base, env );
+                        if ( 0 < assignResult && tq1 <= tq2 ) {
+                                if ( tq1 == tq2 ) {
+                                        cost = Cost::safe;
+                                } else {
+                                        cost = Cost::safe + Cost::safe;
+                                }
+                        } else if ( assignResult < 0 ) {
+                                cost = Cost::unsafe;
+                        } // else Cost::infinity
+                }
+        }
+}
+
+void ConversionCost_new::postvisit( const ast::ArrayType * arrayType ) {
+        (void)arrayType;
+}
+
+void ConversionCost_new::postvisit( const ast::ReferenceType * refType ) {
+        assert( nullptr == dynamic_cast< const ast::ReferenceType * >( dst ) );
+
+        cost = costCalc( refType->base, dst, symtab, env );
+        if ( refType->base->qualifiers == dst->qualifiers ) {
+                cost.incReference();
+        } else if ( refType->base->qualifiers < dst->qualifiers ) {
+                cost.incSafe();
+        } else {
+                cost.incUnsafe();
+        }
+}
+
+void ConversionCost_new::postvisit( const ast::FunctionType * functionType ) {
+        (void)functionType;
+}
+
+void ConversionCost_new::postvisit( const ast::StructInstType * structInstType ) {
+        if ( const ast::StructInstType * dstAsInst =
+                        dynamic_cast< const ast::StructInstType * >( dst ) ) {
+                if ( structInstType->name == dstAsInst->name ) {
+                        cost = Cost::zero;
+                }
+        }
+}
+
+void ConversionCost_new::postvisit( const ast::UnionInstType * unionInstType ) {
+        if ( const ast::UnionInstType * dstAsInst =
+                        dynamic_cast< const ast::UnionInstType * >( dst ) ) {
+                if ( unionInstType->name == dstAsInst->name ) {
+                        cost = Cost::zero;
+                }
+        }
+}
+
+void ConversionCost_new::postvisit( const ast::EnumInstType * enumInstType ) {
+        (void)enumInstType;
+        static const ast::BasicType integer( ast::BasicType::SignedInt );
+        cost = costCalc( &integer, dst, symtab, env );
+        if ( cost < Cost::unsafe ) {
+                cost.incSafe();
+        }
+}
+
+void ConversionCost_new::postvisit( const ast::TraitInstType * traitInstType ) {
+        (void)traitInstType;
+}
+
+void ConversionCost_new::postvisit( const ast::TypeInstType * typeInstType ) {
+        if ( const ast::EqvClass * eqv = env.lookup( typeInstType->name ) ) {
+                cost = costCalc( eqv->bound, dst, symtab, env );
+        } else if ( const ast::TypeInstType * dstAsInst =
+                        dynamic_cast< const ast::TypeInstType * >( dst ) ) {
+                if ( typeInstType->name == dstAsInst->name ) {
+                        cost = Cost::zero;
+                }
+        } else if ( const ast::NamedTypeDecl * namedType = symtab.lookupType( typeInstType->name ) ) {
+                const ast::TypeDecl * type = dynamic_cast< const ast::TypeDecl * >( namedType );
+                assertf( type, "Unexpected typedef.");
+                if ( type->base ) {
+                        cost = costCalc( type->base, dst, symtab, env ) + Cost::safe;
+                }
+        }
+}
+
+void ConversionCost_new::postvisit( const ast::TupleType * tupleType ) {
+        Cost c = Cost::zero;
+        if ( const ast::TupleType * dstAsTuple = dynamic_cast< const ast::TupleType * >( dst ) ) {
+                auto srcIt = tupleType->types.begin();
+                auto dstIt = dstAsTuple->types.begin();
+                auto srcEnd = tupleType->types.end();
+                auto dstEnd = dstAsTuple->types.end();
+                while ( srcIt != srcEnd && dstIt != dstEnd ) {
+                        Cost newCost = costCalc( *srcIt++, *dstIt++, symtab, env );
+                        if ( newCost == Cost::infinity ) {
+                                return;
+                        }
+                        c += newCost;
+                }
+                if ( dstIt != dstEnd ) {
+                        cost = Cost::infinity;
+                } else {
+                        cost = c;
+                }
+        }
+}
+
+void ConversionCost_new::postvisit( const ast::VarArgsType * varArgsType ) {
+        (void)varArgsType;
+        if ( dynamic_cast< const ast::VarArgsType * >( dst ) ) {
+                cost = Cost::zero;
+        }
+}
+
+void ConversionCost_new::postvisit( const ast::ZeroType * zeroType ) {
+        (void)zeroType;
+        if ( dynamic_cast< const ast::ZeroType * >( dst ) ) {
+                cost = Cost::zero;
+        } else if ( const ast::BasicType * dstAsBasic =
+                        dynamic_cast< const ast::BasicType * >( dst ) ) {
+                int tableResult = costMatrix[ ast::BasicType::SignedInt ][ dstAsBasic->kind ];
+                if ( -1 == tableResult ) {
+                        cost = Cost::unsafe;
+                } else {
+                        cost = Cost::zero;
+                        cost.incSafe( tableResult + 1 );
+                        cost.incSign( signMatrix[ ast::BasicType::SignedInt ][ dstAsBasic->kind ] );
+                }
+        }
+}
+
+void ConversionCost_new::postvisit( const ast::OneType * oneType ) {
+        (void)oneType;
+        if ( dynamic_cast< const ast::OneType * >( dst ) ) {
+                cost = Cost::zero;
+        } else if ( const ast::BasicType * dstAsBasic =
+                        dynamic_cast< const ast::BasicType * >( dst ) ) {
+                int tableResult = costMatrix[ ast::BasicType::SignedInt ][ dstAsBasic->kind ];
+                if ( -1 == tableResult ) {
+                        cost = Cost::unsafe;
+                } else {
+                        cost = Cost::zero;
+                        cost.incSafe( tableResult + 1 );
+                        cost.incSign( signMatrix[ ast::BasicType::SignedInt ][ dstAsBasic->kind ] );
+                }
+        } else if ( dynamic_cast< const ast::PointerType * >( dst ) ) {
+                cost = Cost::zero;
+                cost.incSafe( maxIntCost + 2 );
+        }
+}
+
+
 } // namespace ResolvExpr
 

src/ResolvExpr/ConversionCost.h

@@ -9 +9 @@
 // Author           : Richard C. Bilson
 // Created On       : Sun May 17 09:37:28 2015
-// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Jul 22 09:38:24 2017
-// Update Count     : 4
+// Last Modified By : Andrew Beach
+// Last Modified On : Mon Jun 24 10:00:00 2019
+// Update Count     : 5
 //
 
@@ -20 +20 @@
 #include "Cost.h"             // for Cost
 
+#include "AST/Fwd.hpp"
+#include "AST/Pass.hpp"       // for WithShortCircuiting
 #include "Common/PassVisitor.h"
 #include "SynTree/Visitor.h"  // for Visitor
@@ -65 +67 @@
         typedef std::function<int(Type *, Type *, const SymTab::Indexer &, const TypeEnvironment &)> PtrsFunction;
         Cost convertToReferenceCost( Type * src, ReferenceType * dest, const SymTab::Indexer & indexer, const TypeEnvironment & env, PtrsFunction func );
+
+// Some function pointer types, differ in return type.
+using CostCalculation = std::function<Cost(const ast::Type *, const ast::Type *,
+        const ast::SymbolTable &, const ast::TypeEnvironment &)>;
+using NumCostCalculation = std::function<int(const ast::Type *, const ast::Type *,
+        const ast::SymbolTable &, const ast::TypeEnvironment &)>;
+
+// TODO: When the old ConversionCost is removed, get ride of the _new suffix.
+class ConversionCost_new : public ast::WithShortCircuiting {
+        const ast::Type * dst;
+        const ast::SymbolTable & symtab;
+        const ast::TypeEnvironment & env;
+        CostCalculation costCalc;
+public:
+        Cost cost;
+
+        ConversionCost_new( const ast::Type * dst, const ast::SymbolTable & symtab,
+                        const ast::TypeEnvironment & env, CostCalculation costCalc ) :
+                dst( dst ), symtab( symtab ), env( env ), costCalc( costCalc ), cost( Cost::infinity )
+        {}
+
+        void previsit( const ast::Node * ) { visit_children = false; }
+
+        void postvisit( const ast::VoidType * voidType );
+        void postvisit( const ast::BasicType * basicType );
+        void postvisit( const ast::PointerType * pointerType );
+        void postvisit( const ast::ArrayType * arrayType );
+        void postvisit( const ast::ReferenceType * refType );
+        void postvisit( const ast::FunctionType * functionType );
+        void postvisit( const ast::StructInstType * structInstType );
+        void postvisit( const ast::UnionInstType * unionInstType );
+        void postvisit( const ast::EnumInstType * enumInstType );
+        void postvisit( const ast::TraitInstType * traitInstType );
+        void postvisit( const ast::TypeInstType * typeInstType );
+        void postvisit( const ast::TupleType * tupleType );
+        void postvisit( const ast::VarArgsType * varArgsType );
+        void postvisit( const ast::ZeroType * zeroType );
+        void postvisit( const ast::OneType * oneType );
+};
+
+Cost convertToReferenceCost( const ast::Type * src, const ast::ReferenceType * dest,
+        const ast::SymbolTable & indexer, const ast::TypeEnvironment & env, NumCostCalculation func );
+
 } // namespace ResolvExpr
 

src/ResolvExpr/PtrsAssignable.cc

@@ -14 +14 @@
 //
 
+#include "AST/Fwd.hpp"
 #include "Common/PassVisitor.h"
 #include "ResolvExpr/TypeEnvironment.h"  // for EqvClass, TypeEnvironment
@@ -107 +108 @@
         void PtrsAssignable::postvisit(  __attribute__((unused)) OneType *oneType ) {}
 
+int ptrsAssignable( const ast::Type * src, const ast::Type * dst,
+                const ast::TypeEnvironment & env ) {
+        #warning unimplemented
+        (void)src;
+        (void)dst;
+        (void)env;
+        assert(0);
+        return 0;
+}
+
 } // namespace ResolvExpr
 

src/ResolvExpr/Resolver.cc

@@ -1154 +1154 @@
                         return findKindExpression( untyped, symtab );
                 }
-
-                /// Resolve `untyped` to the single expression whose candidate is the best match for the 
-                /// given type.
+        } // anonymous namespace
+
                 ast::ptr< ast::Expr > findSingleExpression(
                         const ast::Expr * untyped, const ast::Type * type, const ast::SymbolTable & symtab
@@ -1167 +1166 @@
                 }
 
+        namespace {
                 /// Predicate for "Candidate has integral type"
                 bool hasIntegralType( const Candidate & i ) {

src/ResolvExpr/Resolver.h

@@ -35 +35 @@
         class StmtExpr;
         class SymbolTable;
+        class Type;
         class TypeEnvironment;
 } // namespace ast
@@ -61 +62 @@
         ast::ptr< ast::Expr > resolveInVoidContext(
                 const ast::Expr * expr, const ast::SymbolTable & symtab, ast::TypeEnvironment & env );
+        /// Resolve `untyped` to the single expression whose candidate is the best match for the 
+        /// given type.
+        ast::ptr< ast::Expr > findSingleExpression(
+                const ast::Expr * untyped, const ast::Type * type, const ast::SymbolTable & symtab );
         /// Resolves a constructor init expression
         ast::ptr< ast::Init > resolveCtorInit( 

src/ResolvExpr/typeops.h

@@ -94 +94 @@
         // in PtrsAssignable.cc
         int ptrsAssignable( Type *src, Type *dest, const TypeEnvironment &env );
+        int ptrsAssignable( const ast::Type * src, const ast::Type * dst,
+                const ast::TypeEnvironment & env );
 
         // in PtrsCastable.cc

src/SymTab/Validate.cc

@@ -44 +44 @@
 #include <list>                        // for list
 #include <string>                      // for string
+#include <unordered_map>               // for unordered_map
 #include <utility>                     // for pair
 
+#include "AST/Chain.hpp"
 #include "AST/Decl.hpp"
 #include "AST/Node.hpp"
@@ -51 +53 @@
 #include "AST/SymbolTable.hpp"
 #include "AST/Type.hpp"
+#include "AST/TypeSubstitution.hpp"
 #include "CodeGen/CodeGenerator.h"     // for genName
 #include "CodeGen/OperatorTable.h"     // for isCtorDtor, isCtorDtorAssign
 #include "ControlStruct/Mutate.h"      // for ForExprMutator
+#include "Common/CodeLocation.h"       // for CodeLocation
 #include "Common/Stats.h"              // for Stats::Heap
 #include "Common/PassVisitor.h"        // for PassVisitor, WithDeclsToAdd
@@ -1427 +1431 @@
         };
 
+        /// expand assertions from a trait instance, performing appropriate type variable substitutions
+        void expandAssertions( 
+                const ast::TraitInstType * inst, std::vector< ast::ptr< ast::DeclWithType > > & out 
+        ) {
+                assertf( inst->base, "Trait instance not linked to base trait: %s", toCString( inst ) );
+
+                // build list of trait members, substituting trait decl parameters for instance parameters
+                ast::TypeSubstitution sub{ 
+                        inst->base->params.begin(), inst->base->params.end(), inst->params.begin() };
+                // deliberately take ast::ptr by-value to ensure this does not mutate inst->base
+                for ( ast::ptr< ast::Decl > decl : inst->base->members ) {
+                        auto member = decl.strict_as< ast::DeclWithType >();
+                        sub.apply( member );
+                        out.emplace_back( member );
+                }
+        }
+
         /// Associates forward declarations of aggregates with their definitions
-        struct LinkReferenceToTypes_new final 
+        class LinkReferenceToTypes_new final 
         : public ast::WithSymbolTable, public ast::WithGuards, public 
           ast::WithVisitorRef<LinkReferenceToTypes_new>, public ast::WithShortCircuiting {
                 
-                const ast::SymbolTable * localSyms;
-
-                LinkReferenceToTypes_new( const ast::SymbolTable & syms ) : localSyms( &syms ) {}
-
-                #warning incomplete
+                // these maps of uses of forward declarations of types need to have the actual type 
+                // declaration switched in *after* they have been traversed. To enable this in the 
+                // ast::Pass framework, any node that needs to be so mutated has mutate() called on it 
+                // before it is placed in the map, properly updating its parents in the usual traversal, 
+                // then can have the actual mutation applied later
+                using ForwardEnumsType = std::unordered_multimap< std::string, ast::EnumInstType * >;
+                using ForwardStructsType = std::unordered_multimap< std::string, ast::StructInstType * >;
+                using ForwardUnionsType = std::unordered_multimap< std::string, ast::UnionInstType * >;
+                
+                const CodeLocation & location;
+                const ast::SymbolTable * localSymtab;
+                
+                ForwardEnumsType forwardEnums;
+                ForwardStructsType forwardStructs;
+                ForwardUnionsType forwardUnions;
+
+                /// true if currently in a generic type body, so that type parameter instances can be 
+                /// renamed appropriately
+                bool inGeneric = false;
+
+        public:
+                /// contstruct using running symbol table
+                LinkReferenceToTypes_new( const CodeLocation & loc ) 
+                : location( loc ), localSymtab( &symtab ) {}
+                
+                /// construct using provided symbol table
+                LinkReferenceToTypes_new( const CodeLocation & loc, const ast::SymbolTable & syms ) 
+                : location( loc ), localSymtab( &syms ) {}
+
+                const ast::Type * postvisit( const ast::TypeInstType * typeInst ) {
+                        // ensure generic parameter instances are renamed like the base type
+                        if ( inGeneric && typeInst->base ) {
+                                typeInst = ast::mutate_field( 
+                                        typeInst, &ast::TypeInstType::name, typeInst->base->name );
+                        }
+
+                        if ( 
+                                auto typeDecl = dynamic_cast< const ast::TypeDecl * >( 
+                                        localSymtab->lookupType( typeInst->name ) ) 
+                        ) {
+                                typeInst = ast::mutate_field( typeInst, &ast::TypeInstType::kind, typeDecl->kind );
+                        }
+
+                        return typeInst;
+                }
+
+                const ast::Type * postvisit( const ast::EnumInstType * inst ) {
+                        const ast::EnumDecl * decl = localSymtab->lookupEnum( inst->name );
+                        // not a semantic error if the enum is not found, just an implicit forward declaration
+                        if ( decl ) {
+                                inst = ast::mutate_field( inst, &ast::EnumInstType::base, decl );
+                        }
+                        if ( ! decl || ! decl->body ) {
+                                // forward declaration
+                                auto mut = mutate( inst );
+                                forwardEnums.emplace( inst->name, mut );
+                                inst = mut;
+                        }
+                        return inst;
+                }
+
+                void checkGenericParameters( const ast::ReferenceToType * inst ) {
+                        for ( const ast::Expr * param : inst->params ) {
+                                if ( ! dynamic_cast< const ast::TypeExpr * >( param ) ) {
+                                        SemanticError( 
+                                                location, inst, "Expression parameters for generic types are currently "
+                                                "unsupported: " );
+                                }
+                        }
+                }
+
+                const ast::StructInstType * postvisit( const ast::StructInstType * inst ) {
+                        const ast::StructDecl * decl = localSymtab->lookupStruct( inst->name );
+                        // not a semantic error if the struct is not found, just an implicit forward declaration
+                        if ( decl ) {
+                                inst = ast::mutate_field( inst, &ast::StructInstType::base, decl );
+                        }
+                        if ( ! decl || ! decl->body ) {
+                                // forward declaration
+                                auto mut = mutate( inst );
+                                forwardStructs.emplace( inst->name, mut );
+                                inst = mut;
+                        }
+                        checkGenericParameters( inst );
+                        return inst;
+                }
+
+                const ast::UnionInstType * postvisit( const ast::UnionInstType * inst ) {
+                        const ast::UnionDecl * decl = localSymtab->lookupUnion( inst->name );
+                        // not a semantic error if the struct is not found, just an implicit forward declaration
+                        if ( decl ) {
+                                inst = ast::mutate_field( inst, &ast::UnionInstType::base, decl );
+                        }
+                        if ( ! decl || ! decl->body ) {
+                                // forward declaration
+                                auto mut = mutate( inst );
+                                forwardUnions.emplace( inst->name, mut );
+                                inst = mut;
+                        }
+                        checkGenericParameters( inst );
+                        return inst;
+                }
+
+                const ast::Type * postvisit( const ast::TraitInstType * traitInst ) {
+                        // handle other traits
+                        const ast::TraitDecl * traitDecl = localSymtab->lookupTrait( traitInst->name );
+                        if ( ! traitDecl )       {
+                                SemanticError( location, "use of undeclared trait " + traitInst->name );
+                        }
+                        if ( traitDecl->params.size() != traitInst->params.size() ) {
+                                SemanticError( location, traitInst, "incorrect number of trait parameters: " );
+                        }
+                        traitInst = ast::mutate_field( traitInst, &ast::TraitInstType::base, traitDecl );
+
+                        // need to carry over the "sized" status of each decl in the instance
+                        for ( unsigned i = 0; i < traitDecl->params.size(); ++i ) {
+                                auto expr = traitInst->params[i].as< ast::TypeExpr >();
+                                if ( ! expr ) {
+                                        SemanticError( 
+                                                traitInst->params[i].get(), "Expression parameters for trait instances "
+                                                "are currently unsupported: " );
+                                }
+
+                                if ( auto inst = expr->type.as< ast::TypeInstType >() ) {
+                                        if ( traitDecl->params[i]->sized && ! inst->base->sized ) {
+                                                // traitInst = ast::mutate_field_index(
+                                                //      traitInst, &ast::TraitInstType::params, i,
+                                                //      ...
+                                                // );
+                                                ast::TraitInstType * mut = ast::mutate( traitInst );
+                                                ast::chain_mutate( mut->params[i] )
+                                                        ( &ast::TypeExpr::type )
+                                                                ( &ast::TypeInstType::base )->sized = true;
+                                                traitInst = mut;
+                                        }
+                                }
+                        }
+
+                        return traitInst;
+                }
+                
+                void previsit( const ast::QualifiedType * ) { visit_children = false; }
+                
+                const ast::Type * postvisit( const ast::QualifiedType * qualType ) {
+                        // linking only makes sense for the "oldest ancestor" of the qualified type
+                        return ast::mutate_field( 
+                                qualType, &ast::QualifiedType::parent, qualType->parent->accept( *visitor ) );
+                }
+
+                const ast::Decl * postvisit( const ast::EnumDecl * enumDecl ) {
+                        // visit enum members first so that the types of self-referencing members are updated 
+                        // properly
+                        if ( ! enumDecl->body ) return enumDecl;
+
+                        // update forward declarations to point here
+                        auto fwds = forwardEnums.equal_range( enumDecl->name );
+                        if ( fwds.first != fwds.second ) {
+                                auto inst = fwds.first;
+                                do {
+                                        // forward decl is stored *mutably* in map, can thus be updated
+                                        inst->second->base = enumDecl;
+                                } while ( ++inst != fwds.second );
+                                forwardEnums.erase( fwds.first, fwds.second );
+                        }
+                        
+                        // ensure that enumerator initializers are properly set
+                        for ( unsigned i = 0; i < enumDecl->members.size(); ++i ) {
+                                auto field = enumDecl->members[i].strict_as< ast::ObjectDecl >();
+                                if ( field->init ) {
+                                        // need to resolve enumerator initializers early so that other passes that 
+                                        // determine if an expression is constexpr have appropriate information
+                                        auto init = field->init.strict_as< ast::SingleInit >();
+                                        
+                                        enumDecl = ast::mutate_field_index( 
+                                                enumDecl, &ast::EnumDecl::members, i, 
+                                                ast::mutate_field( field, &ast::ObjectDecl::init, 
+                                                        ast::mutate_field( init, &ast::SingleInit::value,
+                                                                ResolvExpr::findSingleExpression( 
+                                                                        init->value, new ast::BasicType{ ast::BasicType::SignedInt },
+                                                                        symtab ) ) ) );
+                                }
+                        }
+
+                        return enumDecl;
+                }
+
+                /// rename generic type parameters uniquely so that they do not conflict with user defined 
+                /// function forall parameters, e.g. the T in Box and the T in f, below
+                ///   forall(otype T)
+                ///   struct Box {
+                ///     T x;
+                ///   };
+                ///   forall(otype T)
+                ///   void f(Box(T) b) {
+                ///     ...
+                ///   }
+                template< typename AggrDecl >
+                const AggrDecl * renameGenericParams( const AggrDecl * aggr ) {
+                        GuardValue( inGeneric );
+                        inGeneric = ! aggr->params.empty();
+
+                        for ( unsigned i = 0; i < aggr->params.size(); ++i ) {
+                                const ast::TypeDecl * td = aggr->params[i];
+
+                                aggr = ast::mutate_field_index( 
+                                        aggr, &AggrDecl::params, i, 
+                                        ast::mutate_field( td, &ast::TypeDecl::name, "__" + td->name + "_generic_" ) );
+                        }
+                        return aggr;
+                }
+
+                const ast::StructDecl * previsit( const ast::StructDecl * structDecl ) {
+                        return renameGenericParams( structDecl );
+                }
+
+                void postvisit( const ast::StructDecl * structDecl ) {
+                        // visit struct members first so that the types of self-referencing members are 
+                        // updated properly
+                        if ( ! structDecl->body ) return;
+
+                        // update forward declarations to point here
+                        auto fwds = forwardStructs.equal_range( structDecl->name );
+                        if ( fwds.first != fwds.second ) {
+                                auto inst = fwds.first;
+                                do {
+                                        // forward decl is stored *mutably* in map, can thus be updated
+                                        inst->second->base = structDecl;
+                                } while ( ++inst != fwds.second );
+                                forwardStructs.erase( fwds.first, fwds.second );
+                        }
+                }
+
+                const ast::UnionDecl * previsit( const ast::UnionDecl * unionDecl ) {
+                        return renameGenericParams( unionDecl );
+                }
+
+                void postvisit( const ast::UnionDecl * unionDecl ) {
+                        // visit union members first so that the types of self-referencing members are updated 
+                        // properly
+                        if ( ! unionDecl->body ) return;
+
+                        // update forward declarations to point here
+                        auto fwds = forwardUnions.equal_range( unionDecl->name );
+                        if ( fwds.first != fwds.second ) {
+                                auto inst = fwds.first;
+                                do {
+                                        // forward decl is stored *mutably* in map, can thus be updated
+                                        inst->second->base = unionDecl;
+                                } while ( ++inst != fwds.second );
+                                forwardUnions.erase( fwds.first, fwds.second );
+                        }
+                }
+
+                const ast::Decl * postvisit( const ast::TraitDecl * traitDecl ) {
+                        // set the "sized" status for the special "sized" trait
+                        if ( traitDecl->name == "sized" ) {
+                                assertf( traitDecl->params.size() == 1, "Built-in trait 'sized' has incorrect "
+                                        "number of parameters: %zd", traitDecl->params.size() );
+
+                                traitDecl = ast::mutate_field_index( 
+                                        traitDecl, &ast::TraitDecl::params, 0, 
+                                        ast::mutate_field( 
+                                                traitDecl->params.front().get(), &ast::TypeDecl::sized, true ) );
+                        }
+
+                        // move assertions from type parameters into the body of the trait
+                        std::vector< ast::ptr< ast::DeclWithType > > added;
+                        for ( const ast::TypeDecl * td : traitDecl->params ) {
+                                for ( const ast::DeclWithType * assn : td->assertions ) {
+                                        auto inst = dynamic_cast< const ast::TraitInstType * >( assn->get_type() );
+                                        if ( inst ) {
+                                                expandAssertions( inst, added );
+                                        } else {
+                                                added.emplace_back( assn );
+                                        }
+                                }
+                        }
+                        if ( ! added.empty() ) {
+                                auto mut = mutate( traitDecl );
+                                for ( const ast::DeclWithType * decl : added ) {
+                                        mut->members.emplace_back( decl );
+                                }
+                                traitDecl = mut;
+                        }
+                        
+                        return traitDecl;
+                }
         };
 
         /// Replaces array and function types in forall lists by appropriate pointer type and assigns 
         /// each object and function declaration a unique ID
-        struct ForallPointerDecay_new {
-                #warning incomplete
+        class ForallPointerDecay_new {
+                const CodeLocation & location;
+        public:
+                ForallPointerDecay_new( const CodeLocation & loc ) : location( loc ) {}
+
+                const ast::ObjectDecl * previsit( const ast::ObjectDecl * obj ) {
+                        // ensure that operator names only apply to functions or function pointers
+                        if ( 
+                                CodeGen::isOperator( obj->name ) 
+                                && ! dynamic_cast< const ast::FunctionType * >( obj->type->stripDeclarator() )
+                        ) {
+                                SemanticError( obj->location, toCString( "operator ", obj->name.c_str(), " is not "
+                                        "a function or function pointer." )  );
+                        }
+
+                        // ensure object has unique ID
+                        if ( obj->uniqueId ) return obj;
+                        auto mut = mutate( obj );
+                        mut->fixUniqueId();
+                        return mut;
+                }
+
+                const ast::FunctionDecl * previsit( const ast::FunctionDecl * func ) {
+                        // ensure function has unique ID
+                        if ( func->uniqueId ) return func;
+                        auto mut = mutate( func );
+                        mut->fixUniqueId();
+                        return mut;
+                }
+
+                /// Fix up assertions -- flattens assertion lists, removing all trait instances
+                template< typename node_t, typename parent_t >
+                static const node_t * forallFixer( 
+                        const CodeLocation & loc, const node_t * node, 
+                        ast::ParameterizedType::ForallList parent_t::* forallField
+                ) {
+                        for ( unsigned i = 0; i < (node->*forallField).size(); ++i ) {
+                                const ast::TypeDecl * type = (node->*forallField)[i];
+                                if ( type->assertions.empty() ) continue;
+
+                                std::vector< ast::ptr< ast::DeclWithType > > asserts;
+                                asserts.reserve( type->assertions.size() );
+
+                                // expand trait instances into their members
+                                for ( const ast::DeclWithType * assn : type->assertions ) {
+                                        auto traitInst = 
+                                                dynamic_cast< const ast::TraitInstType * >( assn->get_type() ); 
+                                        if ( traitInst ) {
+                                                // expand trait instance to all its members
+                                                expandAssertions( traitInst, asserts );
+                                        } else {
+                                                // pass other assertions through
+                                                asserts.emplace_back( assn );
+                                        }
+                                }
+
+                                // apply FixFunction to every assertion to check for invalid void type
+                                for ( ast::ptr< ast::DeclWithType > & assn : asserts ) {
+                                        bool isVoid = false;
+                                        assn = fixFunction( assn, isVoid );
+                                        if ( isVoid ) {
+                                                SemanticError( loc, node, "invalid type void in assertion of function " );
+                                        }
+                                }
+
+                                // place mutated assertion list in node
+                                auto mut = mutate( type );
+                                mut->assertions = move( asserts );
+                                node = ast::mutate_field_index( node, forallField, i, mut );
+                        }
+                        return node;
+                }
+
+                const ast::FunctionType * previsit( const ast::FunctionType * ftype ) {
+                        return forallFixer( location, ftype, &ast::FunctionType::forall );
+                }
+
+                const ast::StructDecl * previsit( const ast::StructDecl * aggrDecl ) {
+                        return forallFixer( aggrDecl->location, aggrDecl, &ast::StructDecl::params );
+                }
+
+                const ast::UnionDecl * previsit( const ast::UnionDecl * aggrDecl ) {
+                        return forallFixer( aggrDecl->location, aggrDecl, &ast::UnionDecl::params );
+                }
         };
 } // anonymous namespace
 
-const ast::Type * validateType( const ast::Type * type, const ast::SymbolTable & symtab ) {
+const ast::Type * validateType( 
+                const CodeLocation & loc, const ast::Type * type, const ast::SymbolTable & symtab ) {
         ast::Pass< EnumAndPointerDecay_new > epc;
-        ast::Pass< LinkReferenceToTypes_new > lrt{ symtab };
-        ast::Pass< ForallPointerDecay_new > fpd;
+        ast::Pass< LinkReferenceToTypes_new > lrt{ loc, symtab };
+        ast::Pass< ForallPointerDecay_new > fpd{ loc };
 
         return type->accept( epc )->accept( lrt )->accept( fpd );

src/SymTab/Validate.h

@@ -19 +19 @@
 #include <list>  // for list
 
+class CodeLocation;
 class Declaration;
 class Type;
@@ -34 +35 @@
         void validateType( Type *type, const Indexer *indexer );
 
-        const ast::Type * validateType( const ast::Type * type, const ast::SymbolTable & symtab );
+        const ast::Type * validateType( 
+                const CodeLocation & loc, const ast::Type * type, const ast::SymbolTable & symtab );
 } // namespace SymTab