# Changeset 04273e9

Ignore:
Timestamp:
Aug 8, 2016, 5:29:03 PM (5 years ago)
Branches:
aaron-thesis, arm-eh, cleanup-dtors, ctor, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
03da511
Parents:
0853178 (diff), 7bf7fb9 (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' into ctor

Conflicts:

src/SymTab/Autogen.cc

Files:
21 edited

Unmodified
Removed
• ## doc/aaron_comp_II/comp_II.tex

 r0853178 \section{Introduction} \CFA\footnote{Pronounced C-for-all'', and written \CFA, CFA, or \CFL.} is an evolutionary modernization of the C programming language currently being designed and built at the University of Waterloo by a team led by Peter Buhr. \CFA adds multiple features to C, including name overloading, user-defined operators, parametric-polymorphic routines, and type constructors and destructors, among others. These features make \CFA significantly more powerful and expressive than C, but impose a significant compile-time cost to support, particularly in the expression resolver, which must evaluate the typing rules of a much more complex type system. The primary goal of this proposed research project is to develop a sufficiently performant expression resolution algorithm, experimentally validate its performance, and integrate it into \Index*{CFA-CC}, the \CFA reference compiler. Secondary goals of this project include the development of various new language features for \CFA; parametric-polymorphic (generic'') types have already been designed and implemented, and reference types and user-defined conversions are under design consideration. The experimental performance-testing architecture for resolution algorithms will also be used to determine the compile-time cost of adding such new features to the \CFA type system. More broadly, this research should provide valuable data for implementers of compilers for other programming languages with similarly powerful static type systems. \CFA\footnote{Pronounced C-for-all'', and written \CFA or \CFL.} is an evolutionary modernization of the C programming language currently being designed and built at the University of Waterloo by a team led by Peter Buhr. \CFA both fixes existing design problems and adds multiple new features to C, including name overloading, user-defined operators, parametric-polymorphic routines, and type constructors and destructors, among others. The new features make \CFA significantly more powerful and expressive than C, but impose a significant compile-time cost, particularly in the expression resolver, which must evaluate the typing rules of a much more complex type-system. The primary goal of this research project is to develop a sufficiently performant expression resolution algorithm, experimentally validate its performance, and integrate it into CFA, the \CFA reference compiler. Secondary goals of this project include the development of various new language features for \CFA: parametric-polymorphic (generic'') types have already been designed and implemented, and reference types and user-defined conversions are under design consideration. An experimental performance-testing architecture for resolution algorithms is under development to determine the relative performance of different expression resolution algorithms, as well as the compile-time cost of adding various new features to the \CFA type-system. More broadly, this research should provide valuable data for implementers of compilers for other programming languages with similarly powerful static type-systems. \section{\CFA} To make the scope of the proposed expression resolution problem more explicit, it is necessary to define the features of both C and \CFA (both current and proposed) which affect this algorithm. In some cases the interactions of multiple features make expression resolution a significantly more complex problem than any individual feature would; in others a feature which does not by itself add any complexity to expression resolution will trigger previously rare edge cases much more frequently. To make the scope of the proposed expression resolution problem more explicit, it is necessary to define the features of both C and \CFA (both current and proposed) that affect this algorithm. In some cases the interactions of multiple features make expression resolution a significantly more complex problem than any individual feature would; in other cases a feature that does not by itself add any complexity to expression resolution triggers previously rare edge cases more frequently. It is important to note that \CFA is not an object-oriented language. \CFA does have a system of (possibly implicit) type conversions derived from C's type conversions; while these conversions may be thought of as something like an inheritance hierarchy the underlying semantics are significantly different and such an analogy is loose at best. Particularly, \CFA has no concept of subclass'', and thus no need to integrate an inheritance-based form of polymorphism with its parametric and overloading-based polymorphism. The graph structure of the \CFA type conversions is also markedly different than an inheritance graph; it has neither a top nor a bottom type, and does not satisfy the lattice properties typical of inheritance graphs. \subsection{Polymorphic Functions} Such functions are written using a ©forall© clause (which gives the language its name): \begin{lstlisting} forall(otype T) ®forall(otype T)® T identity(T x) { return x; The ©identity© function above can be applied to any complete object type (or ©otype©''). The type variable ©T© is transformed into a set of additional implicit parameters to ©identity© which encode sufficient information about ©T© to create and return a variable of that type. The current \CFA implementation passes the size and alignment of the type represented by an ©otype© parameter, as well as an assignment operator, constructor, copy constructor \& destructor. The current \CFA implementation passes the size and alignment of the type represented by an ©otype© parameter, as well as an assignment operator, constructor, copy constructor and destructor. Since bare polymorphic types do not provide a great range of available operations, \CFA also provides a \emph{type assertion} mechanism to provide further information about a type: \begin{lstlisting} forall(otype T | { T twice(T); }) forall(otype T ®| { T twice(T); }®) T four_times(T x) { return twice( twice(x) ); Finding appropriate functions to satisfy type assertions is essentially a recursive case of expression resolution, as it takes a name (that of the type assertion) and attempts to match it to a suitable declaration in the current scope. If a polymorphic function can be used to satisfy one of its own type assertions, this recursion may not terminate, as it is possible that function will be examined as a candidate for its own type assertion unboundedly repeatedly. To avoid infinite loops, the current \Index*{CFA-CC} compiler imposes a fixed limit on the possible depth of recursion, similar to that employed by most \Index*[C++]{\CC} compilers for template expansion; this restriction means that there are some semantically well-typed expressions which cannot be resolved by {CFA-CC}. To avoid infinite loops, the current CFA compiler imposes a fixed limit on the possible depth of recursion, similar to that employed by most \CC compilers for template expansion; this restriction means that there are some semantically well-typed expressions which cannot be resolved by CFA. One area of potential improvement this project proposes to investigate is the possibility of using the compiler's knowledge of the current set of declarations to more precicely determine when further type assertion satisfaction recursion will not produce a well-typed expression. \subsubsection{Traits} \CFA provides \emph{traits} as a means to name a group of type assertions, as in the example below: \begin{lstlisting} trait has_magnitude(otype T) { bool ?
• ## doc/working/resolver_design.md

 r0853178 An alternate possibility would be to only count two-arg constructors void ?{} ( To*, From ) as unsafe conversions; under this semantics, safe and void ?{} ( To*, From ) as unsafe conversions; under this semantics, safe and explicit conversions should also have a compiler-enforced restriction to ensure that they are two-arg functions (this restriction may be valuable two chains of conversions, one among the signed integral types, another among the unsigned, and to use monomorphic conversions to allow conversions between signed and unsigned integer types). signed and unsigned integer types). ### Implementation Details ### A variant of the above scheme would be to fix a maximum depth of polymorphic type variables (16 seems like a reasonable choice) at which a parameter would be considered to be effectively monomorphic, and to subtract the value be considered to be effectively monomorphic, and to subtract the value described above from that maximum, clamping the result to a minimum of 0. Under this scheme, assuming a maximum value of 4, int has value 0, T has specifying the (completely arbitrary) maximum depth as part of the language or allowing the compiler to refuse to accept otherwise well-typed deeply-nested polymorphic types. polymorphic types. For purposes of determining polymorphism, the list of return types of a sizeof, alignof, and offsetof expressions have at most a single interpretation, of type size_t. sizeof and alignof expressions take either a type or an expression as a an argument; if the argument is a type, it must be a complete type which is not a function type, if an expression, the expression must have a single sizeof and alignof expressions take either a type or an expression as an argument; if the argument is a type, it must be a complete type which is not a function type, if an expression, the expression must have a single interpretation, the type of which conforms to the same rules. offsetof takes two arguments, a type and a member name; the type must be = delete; } ## Appendix E: Features to Add in Resolver Re-write ## * Reference types * Special types for 0 and 1 literals * Expression type for return statement that resolves similarly to ?=? - This is to get rid of the kludge in the box pass that effectively re-implements the resolver poorly.

• ## src/GenPoly/module.mk

 r0853178 GenPoly/CopyParams.cc \ GenPoly/FindFunction.cc \ GenPoly/DeclMutator.cc GenPoly/DeclMutator.cc \ GenPoly/InstantiateGeneric.cc
• ## src/Makefile.in

 r0853178 GenPoly/driver_cfa_cpp-FindFunction.$(OBJEXT) \ GenPoly/driver_cfa_cpp-DeclMutator.$(OBJEXT) \ GenPoly/driver_cfa_cpp-InstantiateGeneric.$(OBJEXT) \ InitTweak/driver_cfa_cpp-GenInit.$(OBJEXT) \ InitTweak/driver_cfa_cpp-FixInit.$(OBJEXT) \ GenPoly/ScrubTyVars.cc GenPoly/Lvalue.cc GenPoly/Specialize.cc \ GenPoly/CopyParams.cc GenPoly/FindFunction.cc \ GenPoly/DeclMutator.cc InitTweak/GenInit.cc \ InitTweak/FixInit.cc InitTweak/FixGlobalInit.cc \ InitTweak/InitTweak.cc Parser/parser.yy Parser/lex.ll \ Parser/TypedefTable.cc Parser/ParseNode.cc \ Parser/DeclarationNode.cc Parser/ExpressionNode.cc \ Parser/StatementNode.cc Parser/InitializerNode.cc \ Parser/TypeData.cc Parser/LinkageSpec.cc \ Parser/parseutility.cc Parser/Parser.cc \ GenPoly/DeclMutator.cc GenPoly/InstantiateGeneric.cc \ InitTweak/GenInit.cc InitTweak/FixInit.cc \ InitTweak/FixGlobalInit.cc InitTweak/InitTweak.cc \ Parser/parser.yy Parser/lex.ll Parser/TypedefTable.cc \ Parser/ParseNode.cc Parser/DeclarationNode.cc \ Parser/ExpressionNode.cc Parser/StatementNode.cc \ Parser/InitializerNode.cc Parser/TypeData.cc \ Parser/LinkageSpec.cc Parser/parseutility.cc Parser/Parser.cc \ ResolvExpr/AlternativeFinder.cc ResolvExpr/Alternative.cc \ ResolvExpr/Unify.cc ResolvExpr/PtrsAssignable.cc \ GenPoly/driver_cfa_cpp-DeclMutator.$(OBJEXT): GenPoly/$(am__dirstamp) \ GenPoly/$(DEPDIR)/$(am__dirstamp) GenPoly/driver_cfa_cpp-InstantiateGeneric.$(OBJEXT):  \ GenPoly/$(am__dirstamp) GenPoly/$(DEPDIR)/$(am__dirstamp) InitTweak/$(am__dirstamp): @$(MKDIR_P) InitTweak -rm -f GenPoly/driver_cfa_cpp-FindFunction.$(OBJEXT) -rm -f GenPoly/driver_cfa_cpp-GenPoly.$(OBJEXT) -rm -f GenPoly/driver_cfa_cpp-InstantiateGeneric.$(OBJEXT) -rm -f GenPoly/driver_cfa_cpp-Lvalue.$(OBJEXT) -rm -f GenPoly/driver_cfa_cpp-PolyMutator.$(OBJEXT) @AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/driver_cfa_cpp-FindFunction.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/driver_cfa_cpp-GenPoly.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/driver_cfa_cpp-Lvalue.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/driver_cfa_cpp-PolyMutator.Po@am__quote@ @am__fastdepCXX_FALSE@$(AM_V_CXX@am__nodep@)$(CXX)$(DEFS) $(DEFAULT_INCLUDES)$(INCLUDES) $(AM_CPPFLAGS)$(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS)$(CXXFLAGS) -c -o GenPoly/driver_cfa_cpp-DeclMutator.obj if test -f 'GenPoly/DeclMutator.cc'; then $(CYGPATH_W) 'GenPoly/DeclMutator.cc'; else$(CYGPATH_W) '$(srcdir)/GenPoly/DeclMutator.cc'; fi GenPoly/driver_cfa_cpp-InstantiateGeneric.o: GenPoly/InstantiateGeneric.cc @am__fastdepCXX_TRUE@$(AM_V_CXX)$(CXX)$(DEFS) $(DEFAULT_INCLUDES)$(INCLUDES) $(AM_CPPFLAGS)$(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS)$(CXXFLAGS) -MT GenPoly/driver_cfa_cpp-InstantiateGeneric.o -MD -MP -MF GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Tpo -c -o GenPoly/driver_cfa_cpp-InstantiateGeneric.o test -f 'GenPoly/InstantiateGeneric.cc' || echo '$(srcdir)/'GenPoly/InstantiateGeneric.cc @am__fastdepCXX_TRUE@   $(AM_V_at)$(am__mv) GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Tpo GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Po @AMDEP_TRUE@@am__fastdepCXX_FALSE@      $(AM_V_CXX)source='GenPoly/InstantiateGeneric.cc' object='GenPoly/driver_cfa_cpp-InstantiateGeneric.o' libtool=no @AMDEPBACKSLASH@ @AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE)$(depcomp) @AMDEPBACKSLASH@ @am__fastdepCXX_FALSE@  $(AM_V_CXX@am__nodep@)$(CXX) $(DEFS)$(DEFAULT_INCLUDES) $(INCLUDES)$(AM_CPPFLAGS) $(CPPFLAGS)$(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -c -o GenPoly/driver_cfa_cpp-InstantiateGeneric.o test -f 'GenPoly/InstantiateGeneric.cc' || echo '$(srcdir)/'GenPoly/InstantiateGeneric.cc GenPoly/driver_cfa_cpp-InstantiateGeneric.obj: GenPoly/InstantiateGeneric.cc @am__fastdepCXX_TRUE@   $(AM_V_CXX)$(CXX) $(DEFS)$(DEFAULT_INCLUDES) $(INCLUDES)$(AM_CPPFLAGS) $(CPPFLAGS)$(driver_cfa_cpp_CXXFLAGS) $(CXXFLAGS) -MT GenPoly/driver_cfa_cpp-InstantiateGeneric.obj -MD -MP -MF GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Tpo -c -o GenPoly/driver_cfa_cpp-InstantiateGeneric.obj if test -f 'GenPoly/InstantiateGeneric.cc'; then $(CYGPATH_W) 'GenPoly/InstantiateGeneric.cc'; else$(CYGPATH_W) '$(srcdir)/GenPoly/InstantiateGeneric.cc'; fi @am__fastdepCXX_TRUE@$(AM_V_at)$(am__mv) GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Tpo GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Po @AMDEP_TRUE@@am__fastdepCXX_FALSE@$(AM_V_CXX)source='GenPoly/InstantiateGeneric.cc' object='GenPoly/driver_cfa_cpp-InstantiateGeneric.obj' libtool=no @AMDEPBACKSLASH@ @AMDEP_TRUE@@am__fastdepCXX_FALSE@      DEPDIR=$(DEPDIR)$(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ @am__fastdepCXX_FALSE@$(AM_V_CXX@am__nodep@)$(CXX)$(DEFS) $(DEFAULT_INCLUDES)$(INCLUDES) $(AM_CPPFLAGS)$(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS)$(CXXFLAGS) -c -o GenPoly/driver_cfa_cpp-InstantiateGeneric.obj if test -f 'GenPoly/InstantiateGeneric.cc'; then $(CYGPATH_W) 'GenPoly/InstantiateGeneric.cc'; else$(CYGPATH_W) '$(srcdir)/GenPoly/InstantiateGeneric.cc'; fi InitTweak/driver_cfa_cpp-GenInit.o: InitTweak/GenInit.cc @am__fastdepCXX_TRUE@$(AM_V_CXX)$(CXX)$(DEFS) $(DEFAULT_INCLUDES)$(INCLUDES) $(AM_CPPFLAGS)$(CPPFLAGS) $(driver_cfa_cpp_CXXFLAGS)$(CXXFLAGS) -MT InitTweak/driver_cfa_cpp-GenInit.o -MD -MP -MF InitTweak/$(DEPDIR)/driver_cfa_cpp-GenInit.Tpo -c -o InitTweak/driver_cfa_cpp-GenInit.o test -f 'InitTweak/GenInit.cc' || echo '$(srcdir)/'InitTweak/GenInit.cc
• ## src/Parser/DeclarationNode.cc

 r0853178 // Created On       : Sat May 16 12:34:05 2015 // Last Modified By : Peter A. Buhr // Last Modified On : Tue Jul 12 20:49:31 2016 // Update Count     : 164 // Last Modified On : Sun Aug  7 08:01:55 2016 // Update Count     : 165 // newnode->name = name; newnode->storageClasses = storageClasses; newnode->bitfieldWidth = maybeClone( bitfieldWidth ); //PAB   newnode->bitfieldWidth = maybeClone( bitfieldWidth ); newnode->bitfieldWidth = bitfieldWidth; newnode->hasEllipsis = hasEllipsis; newnode->initializer = initializer;

• ## src/Parser/ParseNode.cc

 r0853178 // Created On       : Sat May 16 13:26:29 2015 // Last Modified By : Peter A. Buhr // Last Modified On : Sun Jul 24 02:17:01 2016 // Update Count     : 90 // Last Modified On : Sat Aug  6 08:26:11 2016 // Update Count     : 93 // #include #include "ParseNode.h" using namespace std; // Difficult to separate extra parts of constants during lexing because actions are not allow in the middle of patterns: // //              prefix action constant action suffix // // Alternatively, breaking a pattern using BEGIN does not work if the following pattern can be empty: // //              constant BEGIN CONT ... //              (...)? BEGIN 0 ... // possible empty suffix // // because the CONT rule is NOT triggered if the pattern is empty. Hence, constants are reparsed here to determine their // type. static Type::Qualifiers emptyQualifiers;                                // no qualifiers on constants static inline bool checkU( char c ) { return c == 'u' || c == 'U'; } static inline bool checkL( char c ) { return c == 'l' || c == 'L'; } static inline bool checkF( char c ) { return c == 'f' || c == 'F'; } static inline bool checkD( char c ) { return c == 'd' || c == 'D'; } static inline bool checkI( char c ) { return c == 'i' || c == 'I'; } static inline bool checkX( char c ) { return c == 'x' || c == 'X'; } ConstantNode *makeConstantInteger( std::string & str ) { static const BasicType::Kind kind[2][3] = { { BasicType::SignedInt, BasicType::LongSignedInt, BasicType::LongLongSignedInt }, { BasicType::UnsignedInt, BasicType::LongUnsignedInt, BasicType::LongLongUnsignedInt }, }; bool dec = true, Unsigned = false;                                      // decimal, unsigned constant int size;                                                                                       // 0 => int, 1 => long, 2 => long long unsigned long long v;                                                           // converted integral value size_t last = str.length() - 1;                                         // last character of constant if ( str[0] == '0' ) {                                                          // octal/hex constant ? dec = false; if ( last != 0 && checkX( str[1] ) ) {                  // hex constant ? sscanf( (char *)str.c_str(), "%llx", &v ); //printf( "%llx %llu\n", v, v ); } else {                                                                                // octal constant sscanf( (char *)str.c_str(), "%llo", &v ); //printf( "%llo %llu\n", v, v ); } // if } else {                                                                                        // decimal constant ? sscanf( (char *)str.c_str(), "%llu", &v ); //printf( "%llu %llu\n", v, v ); } // if if ( v <= INT_MAX ) {                                                           // signed int size = 0; } else if ( v <= UINT_MAX && ! dec ) {                          // unsigned int size = 0; Unsigned = true;                                                                // unsigned } else if ( v <= LONG_MAX ) {                                           // signed long int size = 1; } else if ( v <= ULONG_MAX && ( ! dec || LONG_MAX == LLONG_MAX ) ) { // signed long int size = 1; Unsigned = true;                                                                // unsigned long int } else if ( v <= LLONG_MAX ) {                                          // signed long long int size = 2; } else {                                                                                        // unsigned long long int size = 2; Unsigned = true;                                                                // unsigned long long int } // if if ( checkU( str[last] ) ) {                                            // suffix 'u' ? Unsigned = true; if ( last > 0 && checkL( str[last - 1] ) ) {    // suffix 'l' ? size = 1; if ( last > 1 && checkL( str[last - 2] ) ) { // suffix 'll' ? size = 2; } // if } // if } else if ( checkL( str[ last ] ) ) {                           // suffix 'l' ? size = 1; if ( last > 0 && checkL( str[last - 1] ) ) { // suffix 'll' ? size = 2; if ( last > 1 && checkU( str[last - 2] ) ) { // suffix 'u' ? Unsigned = true; } // if } else { if ( last > 0 && checkU( str[last - 1] ) ) { // suffix 'u' ? Unsigned = true; } // if } // if } // if return new ConstantNode( new ConstantExpr( Constant( new BasicType( emptyQualifiers, kind[Unsigned][size] ), str ), nullptr ) ); } // makeConstantInteger ConstantNode *makeConstantFloat( std::string & str ) { static const BasicType::Kind kind[2][3] = { { BasicType::Float, BasicType::Double, BasicType::LongDouble }, { BasicType::FloatComplex, BasicType::DoubleComplex, BasicType::LongDoubleComplex }, }; bool complx = false;                                                            // real, complex int size = 1;                                                                           // 0 => float, 1 => double (default), 2 => long double // floating-point constant has minimum of 2 characters: 1. or .1 size_t last = str.length() - 1; if ( checkI( str[last] ) ) {                                            // imaginary ? complx = true; last -= 1;                                                                              // backup one character } // if if ( checkF( str[last] ) ) {                                            // float ? size = 0; } else if ( checkD( str[last] ) ) {                                     // double ? size = 1; } else if ( checkL( str[last] ) ) {                                     // long double ? size = 2; } // if if ( ! complx && checkI( str[last - 1] ) ) {            // imaginary ? complx = true; } // if return new ConstantNode( new ConstantExpr( Constant( new BasicType( emptyQualifiers, kind[complx][size] ), str ), nullptr ) ); } // makeConstantFloat ConstantNode *makeConstantChar( std::string & str ) { return new ConstantNode( new ConstantExpr( Constant( new BasicType( emptyQualifiers, BasicType::Char ), str ), nullptr ) ); } // makeConstantChar ConstantNode *makeConstantStr( std::string & str ) { // string should probably be a primitive type ArrayType *at = new ArrayType( emptyQualifiers, new BasicType( emptyQualifiers, BasicType::Char ), new ConstantExpr( Constant( new BasicType( emptyQualifiers, BasicType::UnsignedInt ), toString( str.size()+1-2 ) ) ),  // +1 for '\0' and -2 for '"' false, false ); return new ConstantNode( new ConstantExpr( Constant( at, str ), nullptr ) ); } // makeConstantStr // Builder