Changeset f02f546 for src

Timestamp:

Jun 21, 2023, 1:28:09 PM (2 years ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

6065281f

Parents:

2de175ce

Message:

Implement new rules for array dimension expression matching.

Core changes:
src/ResolvExpr/Unify.cc: add sense of "these two expressions unify"
src/InitTweak/GenInit.cc: make hoisting happen more often
tests/array-container/*: reconfigure the array-dimension test to use non-"classic" expectation rules

Misc contributors and noise:
libcfa/src/parseargs.cfa: ,ake a parameter, that's used as a length expression, constant (example of an array user following new rules)
src/ResolvExpr/ResolveTypeof.h: make fixArrayType public
src/Validate/GenericParameter.cpp: do the array-type desugaring in both AST corners that forall-variables can be found (not just in one of them)
tests/.expect/typedefRedef-ERR1.txt: old one was "expecting" a bug, that new array rules handle correctly

Location:

src

Files:

• InitTweak/GenInit.cc (modified) (1 diff)
• ResolvExpr/ResolveTypeof.h (modified) (1 diff)
• ResolvExpr/Unify.cc (modified) (3 diffs)
• Validate/GenericParameter.cpp (modified) (5 diffs)

src/InitTweak/GenInit.cc

@@ -300 +300 @@
 
 #       warning Remove the _New suffix after the conversion is complete.
+
+        // Outer pass finds declarations, for their type could wrap a type that needs hoisting
         struct HoistArrayDimension_NoResolve_New final :
                         public ast::WithDeclsToAdd<>, public ast::WithShortCircuiting,
                         public ast::WithGuards, public ast::WithConstTranslationUnit,
-                        public ast::WithVisitorRef<HoistArrayDimension_NoResolve_New> {
-                void previsit( const ast::ObjectDecl * decl );
-                const ast::DeclWithType * postvisit( const ast::ObjectDecl * decl );
-                // Do not look for objects inside there declarations (and type).
-                void previsit( const ast::AggregateDecl * ) { visit_children = false; }
-                void previsit( const ast::NamedTypeDecl * ) { visit_children = false; }
-                void previsit( const ast::FunctionType * ) { visit_children = false; }
-
-                const ast::Type * hoist( const ast::Type * type );
+                        public ast::WithVisitorRef<HoistArrayDimension_NoResolve_New>,
+                        public ast::WithSymbolTableX<ast::SymbolTable::ErrorDetection::IgnoreErrors> {
+
+                // Inner pass looks within a type, for a part that depends on an expression
+                struct HoistDimsFromTypes final :
+                                public ast::WithShortCircuiting, public ast::WithGuards {
+
+                        HoistArrayDimension_NoResolve_New * outer;
+                        HoistDimsFromTypes( HoistArrayDimension_NoResolve_New * outer ) : outer(outer) {}
+
+                        // Only intended for visiting through types.
+                        // Tolerate, and short-circuit at, the dimension expression of an array type.
+                        //    (We'll operate on the dimension expression of an array type directly
+                        //    from the parent type, not by visiting through it)
+                        // Look inside type exprs.
+                        void previsit( const ast::Node * ) {
+                                assert( false && "unsupported node type" );
+                        };
+                        const ast::Expr * allowedExpr = nullptr;
+                        void previsit( const ast::Type * ) {
+                                GuardValue( allowedExpr ) = nullptr;
+                        }
+                        void previsit( const ast::ArrayType * t ) {
+                                GuardValue( allowedExpr ) = t->dimension.get();
+                        }
+                        void previsit( const ast::PointerType * t ) {
+                                GuardValue( allowedExpr ) = t->dimension.get();
+                        }
+                        void previsit( const ast::TypeofType * t ) {
+                                GuardValue( allowedExpr ) = t->expr.get();
+                        }
+                        void previsit( const ast::Expr * e ) {
+                                assert( e == allowedExpr &&
+                                    "only expecting to visit exprs that are dimension exprs or typeof(-) inner exprs" );
+
+                                // Skip the tolerated expressions
+                                visit_children = false;
+                        }
+                        void previsit( const ast::TypeExpr * ) {}
+
+                        const ast::Type * postvisit(
+                                        const ast::ArrayType * arrayType ) {
+                                static UniqueName dimensionName( "_array_dim" );
+
+                                if ( nullptr == arrayType->dimension ) {  // if no dimension is given, don't presume to invent one
+                                        return arrayType;
+                                }
+
+                                // find size_t; use it as the type for a dim expr
+                                ast::ptr<ast::Type> dimType = outer->transUnit().global.sizeType;
+                                assert( dimType );
+                                add_qualifiers( dimType, ast::CV::Qualifiers( ast::CV::Const ) );
+
+                                // Special-case handling: leave the user's dimension expression alone
+                                // - requires the user to have followed a careful convention
+                                // - may apply to extremely simple applications, but only as windfall
+                                // - users of advanced applications will be following the convention on purpose
+                                // - CFA maintainers must protect the criteria against leaving too much alone
+
+                                // Actual leave-alone cases following are conservative approximations of "cannot vary"
+
+                                // Leave alone: literals and enum constants
+                                if ( dynamic_cast< const ast::ConstantExpr * >( arrayType->dimension.get() ) ) {
+                                        return arrayType;
+                                }
+
+                                // Leave alone: direct use of an object declared to be const
+                                const ast::NameExpr * dimn = dynamic_cast< const ast::NameExpr * >( arrayType->dimension.get() );
+                                if ( dimn ) {
+                                        std::vector<ast::SymbolTable::IdData> dimnDefs = outer->symtab.lookupId( dimn->name );
+                                        if ( dimnDefs.size() == 1 ) {
+                                                const ast::DeclWithType * dimnDef = dimnDefs[0].id.get();
+                                                assert( dimnDef && "symbol table binds a name to nothing" );
+                                                const ast::ObjectDecl * dimOb = dynamic_cast< const ast::ObjectDecl * >( dimnDef );
+                                                if( dimOb ) {
+                                                        const ast::Type * dimTy = dimOb->type.get();
+                                                        assert( dimTy && "object declaration bearing no type" );
+                                                        // must not hoist some: size_t
+                                                        // must hoist all: pointers and references
+                                                        // the analysis is conservative; BasicType is a simple approximation
+                                                        if ( dynamic_cast< const ast::BasicType * >( dimTy ) ||
+                                                             dynamic_cast< const ast::SueInstType<ast::EnumDecl> * >( dimTy ) ) {
+                                                                if ( dimTy->is_const() ) {
+                                                                        // The dimension is certainly re-evaluable, giving the same answer each time.
+                                                                        // Our user might be hoping to write the array type in multiple places, having them unify.
+                                                                        // Leave the type alone.
+
+                                                                        // We believe the new criterion leaves less alone than the old criterion.
+                                                                        // Thus, the old criterion should have left the current case alone.
+                                                                        // Catch cases that weren't thought through.
+                                                                        assert( !Tuples::maybeImpure( arrayType->dimension ) );
+
+                                                                        return arrayType;
+                                                                }
+                                                        };
+                                                }
+                                        }
+                                }
+
+                                // Leave alone: any sizeof expression (answer cannot vary during current lexical scope)
+                                const ast::SizeofExpr * sz = dynamic_cast< const ast::SizeofExpr * >( arrayType->dimension.get() );
+                                if ( sz ) {
+                                        return arrayType;
+                                }
+
+                                // General-case handling: change the array-type's dim expr (hoist the user-given content out of the type)
+                                // - always safe
+                                // - user-unnoticeable in common applications (benign noise in -CFA output)
+                                // - may annoy a responsible user of advanced applications (but they can work around)
+                                // - protects against misusing advanced features
+                                //
+                                // The hoist, by example, is:
+                                // FROM USER:  float a[ rand() ];
+                                // TO GCC:     const size_t __len_of_a = rand(); float a[ __len_of_a ];
+
+                                ast::ObjectDecl * arrayDimension = new ast::ObjectDecl(
+                                        arrayType->dimension->location,
+                                        dimensionName.newName(),
+                                        dimType,
+                                        new ast::SingleInit(
+                                                arrayType->dimension->location,
+                                                arrayType->dimension
+                                        )
+                                );
+
+                                ast::ArrayType * mutType = ast::mutate( arrayType );
+                                mutType->dimension = new ast::VariableExpr(
+                                                arrayDimension->location, arrayDimension );
+                                outer->declsToAddBefore.push_back( arrayDimension );
+
+                                return mutType;
+                        }  // postvisit( const ast::ArrayType * )
+                }; // struct HoistDimsFromTypes
 
                 ast::Storage::Classes storageClasses;
+                void previsit(
+                                const ast::ObjectDecl * decl ) {
+                        GuardValue( storageClasses ) = decl->storage;
+                }
+
+                const ast::DeclWithType * postvisit(
+                                const ast::ObjectDecl * objectDecl ) {
+
+                        if ( !isInFunction() || storageClasses.is_static ) {
+                                return objectDecl;
+                        }
+
+                        const ast::Type * mid = objectDecl->type;
+
+                        ast::Pass<HoistDimsFromTypes> hoist{this};
+                        const ast::Type * result = mid->accept( hoist );
+
+                        return mutate_field( objectDecl, &ast::ObjectDecl::type, result );
+                }
         };
 
-        void HoistArrayDimension_NoResolve_New::previsit(
-                        const ast::ObjectDecl * decl ) {
-                GuardValue( storageClasses ) = decl->storage;
-        }
-
-        const ast::DeclWithType * HoistArrayDimension_NoResolve_New::postvisit(
-                        const ast::ObjectDecl * objectDecl ) {
-                return mutate_field( objectDecl, &ast::ObjectDecl::type,
-                                hoist( objectDecl->type ) );
-        }
-
-        const ast::Type * HoistArrayDimension_NoResolve_New::hoist(
-                        const ast::Type * type ) {
-                static UniqueName dimensionName( "_array_dim" );
-
-                if ( !isInFunction() || storageClasses.is_static ) {
-                        return type;
-                }
-
-                if ( auto arrayType = dynamic_cast< const ast::ArrayType * >( type ) ) {
-                        if ( nullptr == arrayType->dimension ) {
-                                return type;
-                        }
-
-                        if ( !Tuples::maybeImpure( arrayType->dimension ) ) {
-                                return type;
-                        }
-
-                        ast::ptr<ast::Type> dimType = transUnit().global.sizeType;
-                        assert( dimType );
-                        add_qualifiers( dimType, ast::CV::Qualifiers( ast::CV::Const ) );
-
-                        ast::ObjectDecl * arrayDimension = new ast::ObjectDecl(
-                                arrayType->dimension->location,
-                                dimensionName.newName(),
-                                dimType,
-                                new ast::SingleInit(
-                                        arrayType->dimension->location,
-                                        arrayType->dimension
-                                )
-                        );
-
-                        ast::ArrayType * mutType = ast::mutate( arrayType );
-                        mutType->dimension = new ast::VariableExpr(
-                                        arrayDimension->location, arrayDimension );
-                        declsToAddBefore.push_back( arrayDimension );
-
-                        mutType->base = hoist( mutType->base );
-                        return mutType;
-                }
-                return type;
-        }
+
+
 
         struct ReturnFixer_New final :

src/ResolvExpr/ResolveTypeof.h

@@ -30 +30 @@
         Type *resolveTypeof( Type*, const SymTab::Indexer &indexer );
         const ast::Type * resolveTypeof( const ast::Type *, const ResolveContext & );
+        const ast::Type * fixArrayType( const ast::Type *, const ResolveContext & );
         const ast::ObjectDecl * fixObjectType( const ast::ObjectDecl * decl , const ResolveContext & );
 } // namespace ResolvExpr

src/ResolvExpr/Unify.cc

@@ -32 +32 @@
 #include "AST/Type.hpp"
 #include "AST/TypeEnvironment.hpp"
+#include "Common/Eval.h"            // for eval
 #include "Common/PassVisitor.h"     // for PassVisitor
 #include "CommonType.hpp"           // for commonType
@@ -779 +780 @@
         }
 
+        // Unification of Expressions
+        //
+        // Boolean outcome (obvious):  Are they basically spelled the same?
+        // Side effect of binding variables (subtle):  if `sizeof(int)` ===_expr `sizeof(T)` then `int` ===_ty `T`
+        //
+        // Context:  if `float[VAREXPR1]` ===_ty `float[VAREXPR2]` then `VAREXPR1` ===_expr `VAREXPR2`
+        // where the VAREXPR are meant as notational metavariables representing the fact that unification always
+        // sees distinct ast::VariableExpr objects at these positions
+
+        static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env,
+                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
+                WidenMode widen );
+
+        class UnifyExpr final : public ast::WithShortCircuiting {
+                const ast::Expr * e2;
+                ast::TypeEnvironment & tenv;
+                ast::AssertionSet & need;
+                ast::AssertionSet & have;
+                const ast::OpenVarSet & open;
+                WidenMode widen;
+        public:
+                bool result;
+
+        private:
+
+                void tryMatchOnStaticValue( const ast::Expr * e1 ) {
+                        Evaluation r1 = eval(e1);
+                        Evaluation r2 = eval(e2);
+
+                        if ( ! r1.hasKnownValue ) return;
+                        if ( ! r2.hasKnownValue ) return;
+
+                        if (r1.knownValue != r2.knownValue) return;
+
+                        visit_children = false;
+                        result = true;
+                }
+
+        public:
+
+                void previsit( const ast::Node * ) { assert(false); }
+
+                void previsit( const ast::Expr * e1 ) {
+                        tryMatchOnStaticValue( e1 );
+                        visit_children = false;
+                }
+
+                void previsit( const ast::CastExpr * e1 ) {
+                        tryMatchOnStaticValue( e1 );
+
+                        if (result) {
+                                assert (visit_children == false);
+                        } else {
+                                assert (visit_children == true);
+                                visit_children = false;
+
+                                auto e2c = dynamic_cast< const ast::CastExpr * >( e2 );
+                                if ( ! e2c ) return;
+
+                                // inspect casts' target types
+                                if ( ! unifyExact(
+                                        e1->result, e2c->result, tenv, need, have, open, widen ) ) return;
+
+                                // inspect casts' inner expressions
+                                result = unify( e1->arg, e2c->arg, tenv, need, have, open, widen );
+                        }
+                }
+
+                void previsit( const ast::VariableExpr * e1 ) {
+                        tryMatchOnStaticValue( e1 );
+
+                        if (result) {
+                                assert (visit_children == false);
+                        } else {
+                                assert (visit_children == true);
+                                visit_children = false;
+
+                                auto e2v = dynamic_cast< const ast::VariableExpr * >( e2 );
+                                if ( ! e2v ) return;
+
+                                assert(e1->var);
+                                assert(e2v->var);
+
+                                // conservative: variable exprs match if their declarations are represented by the same C++ AST object
+                                result = (e1->var == e2v->var);
+                        }
+                }
+
+                void previsit( const ast::SizeofExpr * e1 ) {
+                        tryMatchOnStaticValue( e1 );
+
+                        if (result) {
+                                assert (visit_children == false);
+                        } else {
+                                assert (visit_children == true);
+                                visit_children = false;
+
+                                auto e2so = dynamic_cast< const ast::SizeofExpr * >( e2 );
+                                if ( ! e2so ) return;
+
+                                assert((e1->type != nullptr) ^ (e1->expr != nullptr));
+                                assert((e2so->type != nullptr) ^ (e2so->expr != nullptr));
+                                if ( ! (e1->type && e2so->type) )  return;
+
+                                // expression unification calls type unification (mutual recursion)
+                                result = unifyExact( e1->type, e2so->type, tenv, need, have, open, widen );
+                        }
+                }
+
+                UnifyExpr( const ast::Expr * e2, ast::TypeEnvironment & env, ast::AssertionSet & need,
+                        ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen )
+                : e2( e2 ), tenv(env), need(need), have(have), open(open), widen(widen), result(false) {}
+        };
+
+        static bool unify( const ast::Expr * e1, const ast::Expr * e2, ast::TypeEnvironment & env,
+                ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open,
+                WidenMode widen ) {
+                assert( e1 && e2 );
+                return ast::Pass<UnifyExpr>::read( e1, e2, env, need, have, open, widen );
+        }
+
         class Unify_new final : public ast::WithShortCircuiting {
                 const ast::Type * type2;
@@ -820 +942 @@
                         if ( ! array2 ) return;
 
-                        // to unify, array types must both be VLA or both not VLA and both must have a
-                        // dimension expression or not have a dimension
                         if ( array->isVarLen != array2->isVarLen ) return;
-                        if ( ! array->isVarLen && ! array2->isVarLen
-                                        && array->dimension && array2->dimension ) {
-                                auto ce1 = array->dimension.as< ast::ConstantExpr >();
-                                auto ce2 = array2->dimension.as< ast::ConstantExpr >();
-
-                                // see C11 Reference Manual 6.7.6.2.6
-                                // two array types with size specifiers that are integer constant expressions are
-                                // compatible if both size specifiers have the same constant value
-                                if ( ce1 && ce2 && ce1->intValue() != ce2->intValue() ) return;
+                        if ( (array->dimension != nullptr) != (array2->dimension != nullptr) ) return;
+
+                        if ( array->dimension ) {
+                                assert( array2->dimension );
+                                // type unification calls expression unification (mutual recursion)
+                                if ( ! unify(array->dimension, array2->dimension,
+                                    tenv, need, have, open, widen) ) return;
                         }
 

src/Validate/GenericParameter.cpp

@@ -16 +16 @@
 #include "GenericParameter.hpp"
 
-#include "AST/Copy.hpp"
 #include "AST/Decl.hpp"
 #include "AST/Expr.hpp"
@@ -165 +164 @@
 
 struct TranslateDimensionCore :
-                public WithNoIdSymbolTable, public ast::WithGuards {
+                public WithNoIdSymbolTable, public ast::WithGuards,
+                public ast::WithVisitorRef<TranslateDimensionCore> {
 
         // SUIT: Struct- or Union- InstType
@@ -190 +190 @@
 
         const ast::TypeDecl * postvisit( const ast::TypeDecl * decl );
+        const ast::Type * postvisit( const ast::FunctionType * type );
+        const ast::Type * postvisit( const ast::TypeInstType * type );
+
         const ast::Expr * postvisit( const ast::DimensionExpr * expr );
         const ast::Expr * postvisit( const ast::Expr * expr );
@@ -195 +198 @@
 };
 
+// Declaration of type variable: forall( [N] )  ->  forall( N & | sized( N ) )
 const ast::TypeDecl * TranslateDimensionCore::postvisit(
                 const ast::TypeDecl * decl ) {
@@ -206 +210 @@
         }
         return decl;
+}
+
+// Makes postvisit( TypeInstType ) get called on the entries of the function declaration's type's forall list.
+// Pass.impl.hpp's visit( FunctionType ) does not consider the forall entries to be child nodes.
+// Workaround is: during the current TranslateDimension pass, manually visit down there.
+const ast::Type * TranslateDimensionCore::postvisit(
+                const ast::FunctionType * type ) {
+        visitor->maybe_accept( type, &ast::FunctionType::forall );
+        return type;
+}
+
+// Use of type variable, assuming `forall( [N] )` in scope:  void (*)( foo( /*dimension*/ N ) & )  ->  void (*)( foo( /*dtype*/ N ) & )
+const ast::Type * TranslateDimensionCore::postvisit(
+                const ast::TypeInstType * type ) {
+        if ( type->kind == ast::TypeDecl::Dimension ) {
+                auto mutType = ast::mutate( type );
+                mutType->kind = ast::TypeDecl::Dtype;
+                return mutType;
+        }
+        return type;
 }