Changes in / [1b0020a:c331406]


Ignore:
Files:
2 added
7 edited

Legend:

Unmodified
Added
Removed
  • doc/aaron_comp_II/comp_II.tex

    r1b0020a rc331406  
    8484\section{Introduction}
    8585
    86 \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.
    87 \CFA adds multiple features to C, including name overloading, user-defined operators, parametric-polymorphic routines, and type constructors and destructors, among others.
    88 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.
    89 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.
    90 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.
    91 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.
    92 More broadly, this research should provide valuable data for implementers of compilers for other programming languages with similarly powerful static type systems.
     86\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.
     87\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.
     88The 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.
     89
     90The 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.
     91Secondary 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.
     92An 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.
     93More broadly, this research should provide valuable data for implementers of compilers for other programming languages with similarly powerful static type-systems.
    9394
    9495\section{\CFA}
    9596
    96 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.
    97 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.
     97To 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.
     98In 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.
     99
     100It is important to note that \CFA is not an object-oriented language.
     101\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.
     102Particularly, \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.
     103The 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.
    98104
    99105\subsection{Polymorphic Functions}
     
    101107Such functions are written using a ©forall© clause (which gives the language its name):
    102108\begin{lstlisting}
    103 forall(otype T)
     109®forall(otype T)®
    104110T identity(T x) {
    105111    return x;
     
    110116The ©identity© function above can be applied to any complete object type (or ``©otype©'').
    111117The 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.
    112 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.
     118The 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.
    113119
    114120Since 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:
    115121\begin{lstlisting}
    116 forall(otype T | { T twice(T); })
     122forall(otype T ®| { T twice(T); }®)
    117123T four_times(T x) {
    118124    return twice( twice(x) );
     
    137143Finding 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.
    138144If 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.
    139 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}.
     145To 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.
    140146One 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.
     147
     148\subsubsection{Traits}
     149\CFA provides \emph{traits} as a means to name a group of type assertions, as in the example below:
     150\begin{lstlisting}
     151trait has_magnitude(otype T) {
     152    bool ?<?(T, T);        // comparison operator for T
     153    T -?(T);               // negation operator for T
     154    void ?{}(T*, zero_t);  // constructor from 0 literal
     155};
     156
     157forall(otype M | has_magnitude(M))
     158M abs( M m ) {
     159    M zero = 0;  // uses zero_t constructor from trait
     160    return m < zero ? -m : m;
     161}
     162
     163forall(otype M | has_magnitude(M))
     164M max_magnitude( M a, M b ) {
     165    M aa = abs(a), ab = abs(b);
     166    return aa < ab ? b : a;
     167}
     168\end{lstlisting}
     169
     170Semantically, a trait is merely a named list of type assertions, but they can be used in many of the same situations where an interface in Java or an abstract base class in \CC would be used.
     171Unlike Java interfaces or \CC base classes, \CFA types do not explicitly state any inheritance relationship to traits they satisfy; this can be considered a form of structural inheritance, similar to interface implementation in Go, as opposed to the nominal inheritance model of Java and \CC.
     172% TODO talk about modelling of nominal inheritance with structural inheritance, possibility of investigating some resolver algorithms that require nominal
    141173
    142174\subsection{Name Overloading}
     
    174206Open research questions on this topic include whether a conversion graph can be generated that represents each allowable conversion in C with a unique minimal-length path, such that the path lengths accurately represent the relative costs of the conversions, whether such a graph representation can be usefully augmented to include user-defined types as well as built-in types, and whether the graph can be efficiently represented and included in the expression resolver.
    175207
    176 \subsection{Constructors \& Destructors}
     208\subsection{Constructors and Destructors}
    177209Rob Shluntz, a current member of the \CFA research team, has added constructors and destructors to \CFA.
    178210Each type has an overridable default-generated zero-argument constructor, copy constructor, assignment operator, and destructor; for struct types these functions each call their equivalents on each field of the struct.
     
    180212
    181213\subsection{Generic Types}
    182 The author has added a generic type capability to \CFA, designed to efficiently and naturally integrate with \CFA's existing polymorphic functions.
     214I have already added a generic type capability to \CFA, designed to efficiently and naturally integrate with \CFA's existing polymorphic functions.
    183215A generic type can be declared by placing a ©forall© specifier on a struct or union declaration, and instantiated using a parenthesized list of types after the type name:
    184216\begin{lstlisting}
     
    195227\end{lstlisting}
    196228For \emph{concrete} generic types, that is, those where none of the type parameters depend on polymorphic type variables (like ©pair(const char*, int)© above), the struct is essentially template expanded to a new struct type; for \emph{polymorphic} generic types (such as ©pair(const char*, T)© above), member access is handled by a runtime calculation of the field offset, based on the size and alignment information of the polymorphic parameter type.
    197 The default-generated constructors, destructor \& assignment operator for a generic type are polymorphic functions with the same list of type parameters as the generic type definition.
    198 
    199 Aside from giving users the ability to create more parameterized types than just the built-in pointer, array \& function types, the combination of generic types with polymorphic functions and implicit conversions makes the edge case where a polymorphic function can match its own assertions much more common, as follows:
     229The default-generated constructors, destructor and assignment operator for a generic type are polymorphic functions with the same list of type parameters as the generic type definition.
     230
     231Aside from giving users the ability to create more parameterized types than just the built-in pointer, array and function types, the combination of generic types with polymorphic functions and implicit conversions makes the edge case where a polymorphic function can match its own assertions much more common, as follows:
    200232\begin{itemize}
    201233\item Given an expression in an untyped context, such as a top-level function call with no assignment of return values, apply a polymorphic implicit conversion to the expression that can produce multiple types (the built-in conversion from ©void*© to any other pointer type is one, but not the only).
     
    221253
    222254\subsection{Reference Types}
    223 The author, in collaboration with the rest of the \CFA research team, has been designing \emph{reference types} for \CFA.
     255I have been designing \emph{reference types} for \CFA, in collaboration with the rest of the \CFA research team.
    224256Given some type ©T©, a ©T&© (``reference to ©T©'') is essentially an automatically dereferenced pointer; with these semantics most of the C standard's discussions of lvalues can be expressed in terms of references instead, with the benefit of being able to express the difference between the reference and non-reference version of a type in user code.
    225257References preserve C's existing qualifier-dropping lvalue-to-rvalue conversion (\eg a ©const volatile int&© can be implicitly converted to a bare ©int©); the reference proposal also adds a rvalue-to-lvalue conversion to \CFA, implemented by storing the value in a new compiler-generated temporary and passing a reference to the temporary.
     
    229261
    230262\subsection{Literal Types}
    231 Another proposal currently under consideration for the \CFA type system is assigning special types to the literal values ©0© and ©1©.%, say ©zero_t© and ©one_t©.
     263Another proposal currently under consideration for the \CFA type-system is assigning special types to the literal values ©0© and ©1©.%, say ©zero_t© and ©one_t©.
    232264Implicit conversions from these types would allow ©0© and ©1© to be considered as values of many different types, depending on context, allowing expression desugarings like ©if ( x ) {}© $\Rightarrow$ ©if ( x != 0 ) {}© to be implemented efficiently and precicely.
    233265This is a generalization of C's existing behaviour of treating ©0© as either an integer zero or a null pointer constant, and treating either of those values as boolean false.
     
    248280Expression resolution is somewhat unavoidably exponential in $p$, the number of function parameters, and $d$, the depth of the expression tree, but these values are fixed by the user programmer, and generally bounded by reasonably small constants.
    249281$k$, on the other hand, is mostly dependent on the representation of types in the system and the efficiency of type assertion checking; if a candidate argument combination can be compared to a function parameter list in linear time in the length of the list (\ie $k = 1$), then the $p^{k \cdot d}$ term is linear in the input size of the source code for the expression, otherwise the resolution algorithm will exibit sub-linear performance scaling on code containing more-deeply nested expressions.
    250 The number of valid interpretations of any subexpression, $i$, is bounded by the number of types in the system, which is possibly infinite, though practical resolution algorithms for \CFA must be able to place some finite bound on $i$, possibly at the expense of type system completeness.
     282The number of valid interpretations of any subexpression, $i$, is bounded by the number of types in the system, which is possibly infinite, though practical resolution algorithms for \CFA must be able to place some finite bound on $i$, possibly at the expense of type-system completeness.
    251283
    252284The research goal of this project is to develop a performant expression resolver for \CFA; this analysis suggests two primary areas of investigation to accomplish that end.
    253 The first is efficient argument-parameter matching; Bilson\cite{Bilson03} mentions significant optimization opportunities available in the current literature to improve on the existing {CFA-CC} compiler.
     285The first is efficient argument-parameter matching; Bilson\cite{Bilson03} mentions significant optimization opportunities available in the current literature to improve on the existing CFA compiler.
    254286%TODO: look up and lit review
    255287The second, and likely more fruitful, area of investigation is heuristics and algorithmic approaches to reduce the number of argument interpretations considered in the common case; given the large ($p+1$) exponent on number of interpretations considered in the runtime analysis, even small reductions here could have a significant effect on overall resolver runtime.
     
    299331Another approach would be to generate a set of possible implicit conversions for each set of interpretations of a given argument.
    300332This would have the benefit of detecting ambiguous interpretations of arguments at the level of the argument rather than its containing call, would also never find more than one interpretation of the argument with a given type, and would re-use calculation of implicit conversions between function candidates.
    301 On the other hand, this approach may unncessarily generate argument interpretations that will never match a parameter, wasting work.
     333On the other hand, this approach may unncessarily generate argument interpretations that will never match a parameter, wasting work.
     334Further, in the presence of tuple types this approach may lead to a combinatorial explosion of argument interpretations considered, unless the tuple can be considered as a sequence of elements rather than a unified whole.
    302335
    303336\subsection{Candidate Set Generation}
    304 Cormack\cite{Cormack81}, Baker\cite{Baker82} \& Bilson\cite{Bilson03} all generate the complete set of candidate argument interpretations before attempting to match the containing function call expression.
     337Cormack\cite{Cormack81}, Baker\cite{Baker82} and Bilson\cite{Bilson03} all generate the complete set of candidate argument interpretations before attempting to match the containing function call expression.
    305338However, given that the top-level expression interpretation that is ultimately chosen will be the minimal-cost valid interpretation, any consideration of non-minimal-cost interpretations is in some sense wasted work.
    306339If we assume that user programmers will generally write function calls with relatively low-cost interpretations, a possible work-saving heuristic is to generate only the lowest-cost argument interpretations first, attempt to find a valid top-level interpretation using them, and only if that fails generate the higher-cost argument interpretations.
    307340
    308341\subsubsection{Eager}
    309 Within the eager approach taken by Cormack, Baker \& Bilson, there are still variants to explore.
    310 Cormack \& Baker do not account for implict conversions, and thus do not account for the possibility of multiple valid interpretations with distinct costs; Bilson, on the other hand, sorts the list of interpretations to aid in finding minimal-cost interpretations.
     342Within the eager approach taken by Cormack, Baker and Bilson, there are still variants to explore.
     343Cormack and Baker do not account for implict conversions, and thus do not account for the possibility of multiple valid interpretations with distinct costs; Bilson, on the other hand, sorts the list of interpretations to aid in finding minimal-cost interpretations.
    311344Sorting the lists of argument or function call interpretations by cost at some point during resolution may provide useful opportunities to short-circuit expression evaluation when a minimal-cost interpretation is found, though it is not clear if this short-circuiting behaviour would justify the cost of the sort.
    312345
     
    315348However, if user programmers actually use relatively few implicit conversions, then the ``on arguments'' approach to implicit conversions will generate a large number of high-cost interpretations which may never be used.
    316349The essence of the lazy approach to candidate set generation is to wrap the matching algorithm into the element generator of a lazy list type, only generating as few elements at a time as possible to ensure that the next-smallest-cost interpretation has been generated.
    317 Assuming that argument interpretations are provided to the parameter matching algorithm in sorted order, a sorted list of function call interpretations can be produced by generating combinations of arguments sorted by total cost\footnote{The author has developed a lazy $n$-way combination generation algorithm that can perform this task.}, then generating function call interpretations in the order suggested by this list.
     350Assuming that argument interpretations are provided to the parameter matching algorithm in sorted order, a sorted list of function call interpretations can be produced by generating combinations of arguments sorted by total cost\footnote{I have already developed a lazy $n$-way combination generation algorithm to perform this task.}, then generating function call interpretations in the order suggested by this list.
    318351Note that the function call interpretation chosen may have costs of its own, for instance polymorphic type binding, so in some cases a number of argument combinations (any combination whose marginal cost does not exceed the cost of the function call interpretation itself) may need to be considered to determine the next-smallest-cost function call interpretation.
    319352Ideally, this candidate generation approach will lead to very few unused candidates being generated (in the expected case where the user programmer has, in fact, provided a validly-typable program), but this research project will need to determine whether or not the overheads of lazy generation exceed the benefit produced from considering fewer interpretations.
     
    333366%\subsection{Parameter-Directed}
    334367%\textbf{TODO: Richard's algorithm isn't Baker (Cormack?), disentangle from this section \ldots}.
    335 %The expression resolution algorithm used by the existing iteration of {CFA-CC} is based on Baker's\cite{Baker82} algorithm for overload resolution in Ada.
     368%The expression resolution algorithm used by the existing iteration of CFA is based on Baker's\cite{Baker82} algorithm for overload resolution in Ada.
    336369%The essential idea of this algorithm is to first find the possible interpretations of the most deeply nested subexpressions, then to use these interpretations to recursively generate valid interpretations of their superexpressions.
    337370%To simplify matters, the only expressions considered in this discussion of the algorithm are function application and literal expressions; other expression types can generally be considered to be variants of one of these for the purposes of the resolver, \eg variables are essentially zero-argument functions.
     
    341374%\textbf{TODO: Figure}
    342375%
    343 %Baker's algorithm was designed to account for name overloading; Richard Bilson\cite{Bilson03} extended this algorithm to also handle polymorphic functions, implicit conversions \& multiple return types when designing the original \CFA compiler.
     376%Baker's algorithm was designed to account for name overloading; Richard Bilson\cite{Bilson03} extended this algorithm to also handle polymorphic functions, implicit conversions and multiple return types when designing the original \CFA compiler.
    344377%The core of the algorithm is a function which Baker refers to as $gen\_calls$.
    345378%$gen\_calls$ takes as arguments the name of a function $f$ and a list containing the set of possible subexpression interpretations $S_j$ for each argument of the function and returns a set of possible interpretations of calling that function on those arguments.
     
    363396\section{Proposal}
    364397Baker\cite{Baker82} discussed various expression resolution algorithms that could handle name overloading, but left experimental comparison of those algorithms to future work; Bilson\cite{Bilson03} described one extension of Baker's algorithm to handle implicit conversions, but did not fully explore the space of algorithmic approaches to handle both overloaded names and implicit conversions.
    365 This project is intended to experimentally test a number of expression resolution algorithms which are powerful enough to handle the \CFA type system, including both name overloading and implicit conversions.
     398This project is intended to experimentally test a number of expression resolution algorithms which are powerful enough to handle the \CFA type-system, including both name overloading and implicit conversions.
    366399This comparison will close Baker's open research question, as well as potentially improving on Bilson's \CFA compiler.
    367400
    368 Rather than testing all of these algorithms in-place in the \CFA compiler, a resolver prototype will be developed which acts on a simplified input language encapsulating the essential details of the \CFA type system\footnote{Note that this simplified input language is not required to be a usable programming language.}.
     401Rather than testing all of these algorithms in-place in the \CFA compiler, a resolver prototype will be developed which acts on a simplified input language encapsulating the essential details of the \CFA type-system\footnote{Note that this simplified input language is not required to be a usable programming language.}.
    369402Multiple variants of this resolver prototype will be implemented, each encapsulating a different expression resolution variant, sharing as much code as feasible.
    370403These variants will be instrumented to test runtime performance, and run on a variety of input files; the input files may be generated programmatically or from exisiting code in \CFA or similar languages.
    371 These experimental results will allow the research team to determine the algorithm likely to be most performant in practical use, and replace {CFA-CC}'s existing expression resolver with that code.
     404These experimental results will allow the research team to determine the algorithm likely to be most performant in practical use, and replace CFA's existing expression resolver with that code.
    372405The experimental results will also provide some empirical sense of the compile-time cost of various language features by comparing the results of the most performant resolver variant that supports the feature with the most performant resolver variant that doesn't, a useful capability to guide language design.
    373406
    374 This proposed project should provide valuable data on how to implement a performant compiler for modern programming languages such as \CFA with powerful static type systems, specifically targeting the feature interaction between name overloading and implicit conversions.
     407This proposed project should provide valuable data on how to implement a performant compiler for modern programming languages such as \CFA with powerful static type-systems, specifically targeting the feature interaction between name overloading and implicit conversions.
    375408
    376409\appendix
     
    379412\begin{center}
    380413\begin{tabular}{ | r @{--} l | p{4in} | }
    381 \hline       May 2015 & April 2016   & Project familiarization and generic types design \& implementation. \\
    382 \hline       May 2016 & April 2017   & Design \& implement resolver prototype and run performance experiments. \\
    383 \hline       May 2017 & August 2017  & Integrate new language features and best-performing resolver prototype into {CFA-CC}. \\
    384 \hline September 2017 & January 2018 & Thesis writing \& defense. \\
     414\hline       May 2015 & April 2016   & Project familiarization and generic types design and implementation. \\
     415\hline       May 2016 & April 2017   & Design and implement resolver prototype and run performance experiments. \\
     416\hline       May 2017 & August 2017  & Integrate new language features and best-performing resolver prototype into CFA. \\
     417\hline September 2017 & January 2018 & Thesis writing and defense. \\
    385418\hline
    386419\end{tabular}
  • doc/working/resolver_design.md

    r1b0020a rc331406  
    3737
    3838An alternate possibility would be to only count two-arg constructors
    39 `void ?{} ( To*, From )` as unsafe conversions; under this semantics, safe and  
     39`void ?{} ( To*, From )` as unsafe conversions; under this semantics, safe and
    4040explicit conversions should also have a compiler-enforced restriction to
    4141ensure that they are two-arg functions (this restriction may be valuable
     
    6969two chains of conversions, one among the signed integral types, another among
    7070the unsigned, and to use monomorphic conversions to allow conversions between
    71 signed and unsigned integer types).   
     71signed and unsigned integer types).
    7272
    7373### Implementation Details ###
     
    509509A variant of the above scheme would be to fix a maximum depth of polymorphic
    510510type variables (16 seems like a reasonable choice) at which a parameter would
    511 be considered to be effectively monomorphic, and to subtract the value  
     511be considered to be effectively monomorphic, and to subtract the value
    512512described above from that maximum, clamping the result to a minimum of 0.
    513513Under this scheme, assuming a maximum value of 4, `int` has value 0, `T` has
     
    577577specifying the (completely arbitrary) maximum depth as part of the language or
    578578allowing the compiler to refuse to accept otherwise well-typed deeply-nested
    579 polymorphic types. 
     579polymorphic types.
    580580
    581581For purposes of determining polymorphism, the list of return types of a
     
    951951`sizeof`, `alignof`, and `offsetof` expressions have at most a single
    952952interpretation, of type `size_t`.
    953 `sizeof` and `alignof` expressions take either a type or an expression as a 
    954 an argument; if the argument is a type, it must be a complete type which is
    955 not a function type, if an expression, the expression must have a single
     953`sizeof` and `alignof` expressions take either a type or an expression as an
     954argument; if the argument is a type, it must be a complete type which is not a
     955function type, if an expression, the expression must have a single
    956956interpretation, the type of which conforms to the same rules.
    957957`offsetof` takes two arguments, a type and a member name; the type must be
     
    16201620                        = delete;
    16211621        }
     1622
     1623## Appendix E: Features to Add in Resolver Re-write ##
     1624* Reference types
     1625* Special types for 0 and 1 literals
     1626* Expression type for return statement that resolves similarly to ?=?
     1627  - This is to get rid of the kludge in the box pass that effectively
     1628    re-implements the resolver poorly.
  • src/GenPoly/Box.cc

    r1b0020a rc331406  
    6262
    6363                FunctionType *makeAdapterType( FunctionType *adaptee, const TyVarMap &tyVars );
    64 
    65                 /// Abstracts type equality for a list of parameter types
    66                 struct TypeList {
    67                         TypeList() : params() {}
    68                         TypeList( const std::list< Type* > &_params ) : params() { cloneAll(_params, params); }
    69                         TypeList( std::list< Type* > &&_params ) : params( _params ) {}
    70 
    71                         TypeList( const TypeList &that ) : params() { cloneAll(that.params, params); }
    72                         TypeList( TypeList &&that ) : params( std::move( that.params ) ) {}
    73 
    74                         /// Extracts types from a list of TypeExpr*
    75                         TypeList( const std::list< TypeExpr* >& _params ) : params() {
    76                                 for ( std::list< TypeExpr* >::const_iterator param = _params.begin(); param != _params.end(); ++param ) {
    77                                         params.push_back( (*param)->get_type()->clone() );
    78                                 }
    79                         }
    80 
    81                         TypeList& operator= ( const TypeList &that ) {
    82                                 deleteAll( params );
    83 
    84                                 params.clear();
    85                                 cloneAll( that.params, params );
    86 
    87                                 return *this;
    88                         }
    89 
    90                         TypeList& operator= ( TypeList &&that ) {
    91                                 deleteAll( params );
    92 
    93                                 params = std::move( that.params );
    94 
    95                                 return *this;
    96                         }
    97 
    98                         ~TypeList() { deleteAll( params ); }
    99 
    100                         bool operator== ( const TypeList& that ) const {
    101                                 if ( params.size() != that.params.size() ) return false;
    102 
    103                                 SymTab::Indexer dummy;
    104                                 for ( std::list< Type* >::const_iterator it = params.begin(), jt = that.params.begin(); it != params.end(); ++it, ++jt ) {
    105                                         if ( ! ResolvExpr::typesCompatible( *it, *jt, dummy ) ) return false;
    106                                 }
    107                                 return true;
    108                         }
    109 
    110                         std::list< Type* > params;  ///< Instantiation parameters
    111                 };
    112 
    113                 /// Maps a key and a TypeList to the some value, accounting for scope
    114                 template< typename Key, typename Value >
    115                 class InstantiationMap {
    116                         /// Wraps value for a specific (Key, TypeList) combination
    117                         typedef std::pair< TypeList, Value* > Instantiation;
    118                         /// List of TypeLists paired with their appropriate values
    119                         typedef std::vector< Instantiation > ValueList;
    120                         /// Underlying map type; maps keys to a linear list of corresponding TypeLists and values
    121                         typedef ScopedMap< Key*, ValueList > InnerMap;
    122 
    123                         InnerMap instantiations;  ///< instantiations
    124 
    125                 public:
    126                         /// Starts a new scope
    127                         void beginScope() { instantiations.beginScope(); }
    128 
    129                         /// Ends a scope
    130                         void endScope() { instantiations.endScope(); }
    131 
    132                         /// Gets the value for the (key, typeList) pair, returns NULL on none such.
    133                         Value *lookup( Key *key, const std::list< TypeExpr* >& params ) const {
    134                                 TypeList typeList( params );
    135 
    136                                 // scan scopes for matches to the key
    137                                 for ( typename InnerMap::const_iterator insts = instantiations.find( key ); insts != instantiations.end(); insts = instantiations.findNext( insts, key ) ) {
    138                                         for ( typename ValueList::const_reverse_iterator inst = insts->second.rbegin(); inst != insts->second.rend(); ++inst ) {
    139                                                 if ( inst->first == typeList ) return inst->second;
    140                                         }
    141                                 }
    142                                 // no matching instantiations found
    143                                 return 0;
    144                         }
    145 
    146                         /// Adds a value for a (key, typeList) pair to the current scope
    147                         void insert( Key *key, const std::list< TypeExpr* > &params, Value *value ) {
    148                                 instantiations[ key ].push_back( Instantiation( TypeList( params ), value ) );
    149                         }
    150                 };
    15164
    15265                /// Adds layout-generation functions to polymorphic types
     
    239152                };
    240153
    241                 /// Mutator pass that replaces concrete instantiations of generic types with actual struct declarations, scoped appropriately
    242                 class GenericInstantiator : public DeclMutator {
    243                         /// Map of (generic type, parameter list) pairs to concrete type instantiations
    244                         InstantiationMap< AggregateDecl, AggregateDecl > instantiations;
    245                         /// Namer for concrete types
    246                         UniqueName typeNamer;
    247 
    248                 public:
    249                         GenericInstantiator() : DeclMutator(), instantiations(), typeNamer("_conc_") {}
    250 
    251                         virtual Type* mutate( StructInstType *inst );
    252                         virtual Type* mutate( UnionInstType *inst );
    253 
    254         //              virtual Expression* mutate( MemberExpr *memberExpr );
    255 
    256                         virtual void doBeginScope();
    257                         virtual void doEndScope();
    258                 private:
    259                         /// Wrap instantiation lookup for structs
    260                         StructDecl* lookup( StructInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (StructDecl*)instantiations.lookup( inst->get_baseStruct(), typeSubs ); }
    261                         /// Wrap instantiation lookup for unions
    262                         UnionDecl* lookup( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs ) { return (UnionDecl*)instantiations.lookup( inst->get_baseUnion(), typeSubs ); }
    263                         /// Wrap instantiation insertion for structs
    264                         void insert( StructInstType *inst, const std::list< TypeExpr* > &typeSubs, StructDecl *decl ) { instantiations.insert( inst->get_baseStruct(), typeSubs, decl ); }
    265                         /// Wrap instantiation insertion for unions
    266                         void insert( UnionInstType *inst, const std::list< TypeExpr* > &typeSubs, UnionDecl *decl ) { instantiations.insert( inst->get_baseUnion(), typeSubs, decl ); }
    267                 };
    268 
    269154                /// Replaces member and size/align/offsetof expressions on polymorphic generic types with calculated expressions.
    270155                /// * Replaces member expressions for polymorphic types with calculated add-field-offset-and-dereference
     
    354239                Pass1 pass1;
    355240                Pass2 pass2;
    356                 GenericInstantiator instantiator;
    357241                PolyGenericCalculator polyCalculator;
    358242                Pass3 pass3;
     
    361245                mutateTranslationUnit/*All*/( translationUnit, pass1 );
    362246                mutateTranslationUnit/*All*/( translationUnit, pass2 );
    363                 instantiator.mutateDeclarationList( translationUnit );
    364247                mutateTranslationUnit/*All*/( translationUnit, polyCalculator );
    365248                mutateTranslationUnit/*All*/( translationUnit, pass3 );
     
    889772                                                arg++;
    890773                                        } else {
    891                                                 /// xxx - should this be an assertion?
     774                                                // xxx - should this be an assertion?
    892775                                                throw SemanticError( "unbound type variable: " + tyParm->first + " in application ", appExpr );
    893776                                        } // if
     
    902785                        std::list< DeclarationWithType* >::const_iterator fnParm = funcType->get_parameters().begin();
    903786                        std::list< Expression* >::const_iterator fnArg = arg;
    904                         std::set< std::string > seenTypes; //< names for generic types we've seen
     787                        std::set< std::string > seenTypes; ///< names for generic types we've seen
    905788
    906789                        // a polymorphic return type may need to be added to the argument list
     
    1042925                /// this gets rid of warnings from gcc.
    1043926                void addCast( Expression *&actual, Type *formal, const TyVarMap &tyVars ) {
    1044                         Type * newType = formal->clone();
    1045                         if ( getFunctionType( newType ) ) {
     927                        if ( getFunctionType( formal ) ) {
     928                                Type * newType = formal->clone();
    1046929                                newType = ScrubTyVars::scrub( newType, tyVars );
    1047930                                actual = new CastExpr( actual, newType );
     
    17751658                }
    17761659
    1777 //////////////////////////////////////// GenericInstantiator //////////////////////////////////////////////////
    1778 
    1779                 /// Makes substitutions of params into baseParams; returns true if all parameters substituted for a concrete type
    1780                 bool makeSubstitutions( const std::list< TypeDecl* >& baseParams, const std::list< Expression* >& params, std::list< TypeExpr* >& out ) {
    1781                         bool allConcrete = true;  // will finish the substitution list even if they're not all concrete
    1782 
    1783                         // substitute concrete types for given parameters, and incomplete types for placeholders
    1784                         std::list< TypeDecl* >::const_iterator baseParam = baseParams.begin();
    1785                         std::list< Expression* >::const_iterator param = params.begin();
    1786                         for ( ; baseParam != baseParams.end() && param != params.end(); ++baseParam, ++param ) {
    1787         //                      switch ( (*baseParam)->get_kind() ) {
    1788         //                      case TypeDecl::Any: {   // any type is a valid substitution here; complete types can be used to instantiate generics
    1789                                         TypeExpr *paramType = dynamic_cast< TypeExpr* >( *param );
    1790                                         assert(paramType && "Aggregate parameters should be type expressions");
    1791                                         out.push_back( paramType->clone() );
    1792                                         // check that the substituted type isn't a type variable itself
    1793                                         if ( dynamic_cast< TypeInstType* >( paramType->get_type() ) ) {
    1794                                                 allConcrete = false;
    1795                                         }
    1796         //                              break;
    1797         //                      }
    1798         //                      case TypeDecl::Dtype:  // dtype can be consistently replaced with void [only pointers, which become void*]
    1799         //                              out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) );
    1800         //                              break;
    1801         //                      case TypeDecl::Ftype:  // pointer-to-ftype can be consistently replaced with void (*)(void) [similar to dtype]
    1802         //                              out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) );
    1803         //                              break;
    1804         //                      }
    1805                         }
    1806 
    1807                         // if any parameters left over, not done
    1808                         if ( baseParam != baseParams.end() ) return false;
    1809         //              // if not enough parameters given, substitute remaining incomplete types for placeholders
    1810         //              for ( ; baseParam != baseParams.end(); ++baseParam ) {
    1811         //                      switch ( (*baseParam)->get_kind() ) {
    1812         //                      case TypeDecl::Any:    // no more substitutions here, fail early
    1813         //                              return false;
    1814         //                      case TypeDecl::Dtype:  // dtype can be consistently replaced with void [only pointers, which become void*]
    1815         //                              out.push_back( new TypeExpr( new VoidType( Type::Qualifiers() ) ) );
    1816         //                              break;
    1817         //                      case TypeDecl::Ftype:  // pointer-to-ftype can be consistently replaced with void (*)(void) [similar to dtype]
    1818         //                              out.push_back( new TypeExpr( new FunctionType( Type::Qualifiers(), false ) ) );
    1819         //                              break;
    1820         //                      }
    1821         //              }
    1822 
    1823                         return allConcrete;
    1824                 }
    1825 
    1826                 /// Substitutes types of members of in according to baseParams => typeSubs, appending the result to out
    1827                 void substituteMembers( const std::list< Declaration* >& in, const std::list< TypeDecl* >& baseParams, const std::list< TypeExpr* >& typeSubs,
    1828                                                                 std::list< Declaration* >& out ) {
    1829                         // substitute types into new members
    1830                         TypeSubstitution subs( baseParams.begin(), baseParams.end(), typeSubs.begin() );
    1831                         for ( std::list< Declaration* >::const_iterator member = in.begin(); member != in.end(); ++member ) {
    1832                                 Declaration *newMember = (*member)->clone();
    1833                                 subs.apply(newMember);
    1834                                 out.push_back( newMember );
    1835                         }
    1836                 }
    1837 
    1838                 Type* GenericInstantiator::mutate( StructInstType *inst ) {
    1839                         // mutate subtypes
    1840                         Type *mutated = Mutator::mutate( inst );
    1841                         inst = dynamic_cast< StructInstType* >( mutated );
    1842                         if ( ! inst ) return mutated;
    1843 
    1844                         // exit early if no need for further mutation
    1845                         if ( inst->get_parameters().empty() ) return inst;
    1846                         assert( inst->get_baseParameters() && "Base struct has parameters" );
    1847 
    1848                         // check if type can be concretely instantiated; put substitutions into typeSubs
    1849                         std::list< TypeExpr* > typeSubs;
    1850                         if ( ! makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ) ) {
    1851                                 deleteAll( typeSubs );
    1852                                 return inst;
    1853                         }
    1854 
    1855                         // make concrete instantiation of generic type
    1856                         StructDecl *concDecl = lookup( inst, typeSubs );
    1857                         if ( ! concDecl ) {
    1858                                 // set concDecl to new type, insert type declaration into statements to add
    1859                                 concDecl = new StructDecl( typeNamer.newName( inst->get_name() ) );
    1860                                 substituteMembers( inst->get_baseStruct()->get_members(), *inst->get_baseParameters(), typeSubs,        concDecl->get_members() );
    1861                                 DeclMutator::addDeclaration( concDecl );
    1862                                 insert( inst, typeSubs, concDecl );
    1863                         }
    1864                         StructInstType *newInst = new StructInstType( inst->get_qualifiers(), concDecl->get_name() );
    1865                         newInst->set_baseStruct( concDecl );
    1866 
    1867                         deleteAll( typeSubs );
    1868                         delete inst;
    1869                         return newInst;
    1870                 }
    1871 
    1872                 Type* GenericInstantiator::mutate( UnionInstType *inst ) {
    1873                         // mutate subtypes
    1874                         Type *mutated = Mutator::mutate( inst );
    1875                         inst = dynamic_cast< UnionInstType* >( mutated );
    1876                         if ( ! inst ) return mutated;
    1877 
    1878                         // exit early if no need for further mutation
    1879                         if ( inst->get_parameters().empty() ) return inst;
    1880                         assert( inst->get_baseParameters() && "Base union has parameters" );
    1881 
    1882                         // check if type can be concretely instantiated; put substitutions into typeSubs
    1883                         std::list< TypeExpr* > typeSubs;
    1884                         if ( ! makeSubstitutions( *inst->get_baseParameters(), inst->get_parameters(), typeSubs ) ) {
    1885                                 deleteAll( typeSubs );
    1886                                 return inst;
    1887                         }
    1888 
    1889                         // make concrete instantiation of generic type
    1890                         UnionDecl *concDecl = lookup( inst, typeSubs );
    1891                         if ( ! concDecl ) {
    1892                                 // set concDecl to new type, insert type declaration into statements to add
    1893                                 concDecl = new UnionDecl( typeNamer.newName( inst->get_name() ) );
    1894                                 substituteMembers( inst->get_baseUnion()->get_members(), *inst->get_baseParameters(), typeSubs, concDecl->get_members() );
    1895                                 DeclMutator::addDeclaration( concDecl );
    1896                                 insert( inst, typeSubs, concDecl );
    1897                         }
    1898                         UnionInstType *newInst = new UnionInstType( inst->get_qualifiers(), concDecl->get_name() );
    1899                         newInst->set_baseUnion( concDecl );
    1900 
    1901                         deleteAll( typeSubs );
    1902                         delete inst;
    1903                         return newInst;
    1904                 }
    1905 
    1906         //      /// Gets the base struct or union declaration for a member expression; NULL if not applicable
    1907         //      AggregateDecl* getMemberBaseDecl( MemberExpr *memberExpr ) {
    1908         //              // get variable for member aggregate
    1909         //              VariableExpr *varExpr = dynamic_cast< VariableExpr* >( memberExpr->get_aggregate() );
    1910         //              if ( ! varExpr ) return NULL;
    1911         //
    1912         //              // get object for variable
    1913         //              ObjectDecl *objectDecl = dynamic_cast< ObjectDecl* >( varExpr->get_var() );
    1914         //              if ( ! objectDecl ) return NULL;
    1915         //
    1916         //              // get base declaration from object type
    1917         //              Type *objectType = objectDecl->get_type();
    1918         //              StructInstType *structType = dynamic_cast< StructInstType* >( objectType );
    1919         //              if ( structType ) return structType->get_baseStruct();
    1920         //              UnionInstType *unionType = dynamic_cast< UnionInstType* >( objectType );
    1921         //              if ( unionType ) return unionType->get_baseUnion();
    1922         //
    1923         //              return NULL;
    1924         //      }
    1925         //
    1926         //      /// Finds the declaration with the given name, returning decls.end() if none such
    1927         //      std::list< Declaration* >::const_iterator findDeclNamed( const std::list< Declaration* > &decls, const std::string &name ) {
    1928         //              for( std::list< Declaration* >::const_iterator decl = decls.begin(); decl != decls.end(); ++decl ) {
    1929         //                      if ( (*decl)->get_name() == name ) return decl;
    1930         //              }
    1931         //              return decls.end();
    1932         //      }
    1933         //
    1934         //      Expression* Instantiate::mutate( MemberExpr *memberExpr ) {
    1935         //              // mutate, exiting early if no longer MemberExpr
    1936         //              Expression *expr = Mutator::mutate( memberExpr );
    1937         //              memberExpr = dynamic_cast< MemberExpr* >( expr );
    1938         //              if ( ! memberExpr ) return expr;
    1939         //
    1940         //              // get declaration of member and base declaration of member, exiting early if not found
    1941         //              AggregateDecl *memberBase = getMemberBaseDecl( memberExpr );
    1942         //              if ( ! memberBase ) return memberExpr;
    1943         //              DeclarationWithType *memberDecl = memberExpr->get_member();
    1944         //              std::list< Declaration* >::const_iterator baseIt = findDeclNamed( memberBase->get_members(), memberDecl->get_name() );
    1945         //              if ( baseIt == memberBase->get_members().end() ) return memberExpr;
    1946         //              DeclarationWithType *baseDecl = dynamic_cast< DeclarationWithType* >( *baseIt );
    1947         //              if ( ! baseDecl ) return memberExpr;
    1948         //
    1949         //              // check if stated type of the member is not the type of the member's declaration; if so, need a cast
    1950         //              // this *SHOULD* be safe, I don't think anything but the void-replacements I put in for dtypes would make it past the typechecker
    1951         //              SymTab::Indexer dummy;
    1952         //              if ( ResolvExpr::typesCompatible( memberDecl->get_type(), baseDecl->get_type(), dummy ) ) return memberExpr;
    1953         //              else return new CastExpr( memberExpr, memberDecl->get_type() );
    1954         //      }
    1955 
    1956                 void GenericInstantiator::doBeginScope() {
    1957                         DeclMutator::doBeginScope();
    1958                         instantiations.beginScope();
    1959                 }
    1960 
    1961                 void GenericInstantiator::doEndScope() {
    1962                         DeclMutator::doEndScope();
    1963                         instantiations.endScope();
    1964                 }
    1965 
    19661660////////////////////////////////////////// PolyGenericCalculator ////////////////////////////////////////////////////
    19671661
     
    21071801                        findGeneric( objectType ); // ensure layout for this type is available
    21081802
     1803                        // replace member expression with dynamically-computed layout expression
    21091804                        Expression *newMemberExpr = 0;
    21101805                        if ( StructInstType *structType = dynamic_cast< StructInstType* >( objectType ) ) {
  • src/GenPoly/module.mk

    r1b0020a rc331406  
    2323       GenPoly/CopyParams.cc \
    2424       GenPoly/FindFunction.cc \
    25        GenPoly/DeclMutator.cc
     25       GenPoly/DeclMutator.cc \
     26       GenPoly/InstantiateGeneric.cc
  • src/Makefile.in

    r1b0020a rc331406  
    121121        GenPoly/driver_cfa_cpp-FindFunction.$(OBJEXT) \
    122122        GenPoly/driver_cfa_cpp-DeclMutator.$(OBJEXT) \
     123        GenPoly/driver_cfa_cpp-InstantiateGeneric.$(OBJEXT) \
    123124        InitTweak/driver_cfa_cpp-GenInit.$(OBJEXT) \
    124125        InitTweak/driver_cfa_cpp-FixInit.$(OBJEXT) \
     
    377378        GenPoly/ScrubTyVars.cc GenPoly/Lvalue.cc GenPoly/Specialize.cc \
    378379        GenPoly/CopyParams.cc GenPoly/FindFunction.cc \
    379         GenPoly/DeclMutator.cc InitTweak/GenInit.cc \
    380         InitTweak/FixInit.cc InitTweak/FixGlobalInit.cc \
    381         InitTweak/InitTweak.cc Parser/parser.yy Parser/lex.ll \
    382         Parser/TypedefTable.cc Parser/ParseNode.cc \
    383         Parser/DeclarationNode.cc Parser/ExpressionNode.cc \
    384         Parser/StatementNode.cc Parser/InitializerNode.cc \
    385         Parser/TypeData.cc Parser/LinkageSpec.cc \
    386         Parser/parseutility.cc Parser/Parser.cc \
     380        GenPoly/DeclMutator.cc GenPoly/InstantiateGeneric.cc \
     381        InitTweak/GenInit.cc InitTweak/FixInit.cc \
     382        InitTweak/FixGlobalInit.cc InitTweak/InitTweak.cc \
     383        Parser/parser.yy Parser/lex.ll Parser/TypedefTable.cc \
     384        Parser/ParseNode.cc Parser/DeclarationNode.cc \
     385        Parser/ExpressionNode.cc Parser/StatementNode.cc \
     386        Parser/InitializerNode.cc Parser/TypeData.cc \
     387        Parser/LinkageSpec.cc Parser/parseutility.cc Parser/Parser.cc \
    387388        ResolvExpr/AlternativeFinder.cc ResolvExpr/Alternative.cc \
    388389        ResolvExpr/Unify.cc ResolvExpr/PtrsAssignable.cc \
     
    585586GenPoly/driver_cfa_cpp-DeclMutator.$(OBJEXT): GenPoly/$(am__dirstamp) \
    586587        GenPoly/$(DEPDIR)/$(am__dirstamp)
     588GenPoly/driver_cfa_cpp-InstantiateGeneric.$(OBJEXT):  \
     589        GenPoly/$(am__dirstamp) GenPoly/$(DEPDIR)/$(am__dirstamp)
    587590InitTweak/$(am__dirstamp):
    588591        @$(MKDIR_P) InitTweak
     
    828831        -rm -f GenPoly/driver_cfa_cpp-FindFunction.$(OBJEXT)
    829832        -rm -f GenPoly/driver_cfa_cpp-GenPoly.$(OBJEXT)
     833        -rm -f GenPoly/driver_cfa_cpp-InstantiateGeneric.$(OBJEXT)
    830834        -rm -f GenPoly/driver_cfa_cpp-Lvalue.$(OBJEXT)
    831835        -rm -f GenPoly/driver_cfa_cpp-PolyMutator.$(OBJEXT)
     
    937941@AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/driver_cfa_cpp-FindFunction.Po@am__quote@
    938942@AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/driver_cfa_cpp-GenPoly.Po@am__quote@
     943@AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Po@am__quote@
    939944@AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/driver_cfa_cpp-Lvalue.Po@am__quote@
    940945@AMDEP_TRUE@@am__include@ @am__quote@GenPoly/$(DEPDIR)/driver_cfa_cpp-PolyMutator.Po@am__quote@
     
    13881393@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`
    13891394
     1395GenPoly/driver_cfa_cpp-InstantiateGeneric.o: GenPoly/InstantiateGeneric.cc
     1396@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
     1397@am__fastdepCXX_TRUE@   $(AM_V_at)$(am__mv) GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Tpo GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Po
     1398@AMDEP_TRUE@@am__fastdepCXX_FALSE@      $(AM_V_CXX)source='GenPoly/InstantiateGeneric.cc' object='GenPoly/driver_cfa_cpp-InstantiateGeneric.o' libtool=no @AMDEPBACKSLASH@
     1399@AMDEP_TRUE@@am__fastdepCXX_FALSE@      DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
     1400@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
     1401
     1402GenPoly/driver_cfa_cpp-InstantiateGeneric.obj: GenPoly/InstantiateGeneric.cc
     1403@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`
     1404@am__fastdepCXX_TRUE@   $(AM_V_at)$(am__mv) GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Tpo GenPoly/$(DEPDIR)/driver_cfa_cpp-InstantiateGeneric.Po
     1405@AMDEP_TRUE@@am__fastdepCXX_FALSE@      $(AM_V_CXX)source='GenPoly/InstantiateGeneric.cc' object='GenPoly/driver_cfa_cpp-InstantiateGeneric.obj' libtool=no @AMDEPBACKSLASH@
     1406@AMDEP_TRUE@@am__fastdepCXX_FALSE@      DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
     1407@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`
     1408
    13901409InitTweak/driver_cfa_cpp-GenInit.o: InitTweak/GenInit.cc
    13911410@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/SymTab/Autogen.cc

    r1b0020a rc331406  
    173173        }
    174174
    175         void makeStructMemberOp( ObjectDecl * dstParam, Expression * src, DeclarationWithType * field, FunctionDecl * func, TypeSubstitution & genericSubs, bool isGeneric, bool forward = true ) {
     175        void makeStructMemberOp( ObjectDecl * dstParam, Expression * src, DeclarationWithType * field, FunctionDecl * func, TypeSubstitution & genericSubs, bool isGeneric, bool isDynamicLayout, bool forward = true ) {
    176176                if ( isGeneric ) {
    177177                        // rewrite member type in terms of the type variables on this operator
     
    197197                genImplicitCall( srcParam, dstselect, func->get_name(), back_inserter( func->get_statements()->get_kids() ), field, forward );
    198198
    199                 if ( isGeneric && returnVal ) {
     199                if ( isDynamicLayout && returnVal ) {
    200200                        UntypedExpr *derefRet = new UntypedExpr( new NameExpr( "*?" ) );
    201201                        derefRet->get_args().push_back( new VariableExpr( returnVal ) );
     
    206206
    207207        template<typename Iterator>
    208         void makeStructFunctionBody( Iterator member, Iterator end, FunctionDecl * func, TypeSubstitution & genericSubs, bool isGeneric, bool forward = true ) {
     208        void makeStructFunctionBody( Iterator member, Iterator end, FunctionDecl * func, TypeSubstitution & genericSubs, bool isGeneric, bool isDynamicLayout, bool forward = true ) {
    209209                for ( ; member != end; ++member ) {
    210210                        if ( DeclarationWithType *field = dynamic_cast< DeclarationWithType * >( *member ) ) { // otherwise some form of type declaration, e.g. Aggregate
     
    242242
    243243                                Expression *srcselect = srcParam ? new MemberExpr( field, new VariableExpr( srcParam ) ) : NULL;
    244                                 makeStructMemberOp( dstParam, srcselect, field, func, genericSubs, isGeneric, forward );
     244                                makeStructMemberOp( dstParam, srcselect, field, func, genericSubs, isGeneric, isDynamicLayout, forward );
    245245                        } // if
    246246                } // for
     
    250250        /// void ?{}(A *, int) and void?{}(A *, int, int) for a struct A which has two int fields.
    251251        template<typename Iterator>
    252         void makeStructFieldCtorBody( Iterator member, Iterator end, FunctionDecl * func, TypeSubstitution & genericSubs, bool isGeneric ) {
     252        void makeStructFieldCtorBody( Iterator member, Iterator end, FunctionDecl * func, TypeSubstitution & genericSubs, bool isGeneric, bool isDynamicLayout ) {
    253253                FunctionType * ftype = func->get_functionType();
    254254                std::list<DeclarationWithType*> & params = ftype->get_parameters();
     
    276276                                        // matching parameter, initialize field with copy ctor
    277277                                        Expression *srcselect = new VariableExpr(*parameter);
    278                                         makeStructMemberOp( dstParam, srcselect, field, func, genericSubs, isGeneric );
     278                                        makeStructMemberOp( dstParam, srcselect, field, func, genericSubs, isGeneric, isDynamicLayout );
    279279                                        ++parameter;
    280280                                } else {
    281281                                        // no matching parameter, initialize field with default ctor
    282                                         makeStructMemberOp( dstParam, NULL, field, func, genericSubs, isGeneric );
     282                                        makeStructMemberOp( dstParam, NULL, field, func, genericSubs, isGeneric, isDynamicLayout );
    283283                                }
    284284                        }
     
    291291                // Make function polymorphic in same parameters as generic struct, if applicable
    292292                bool isGeneric = false;  // NOTE this flag is an incredibly ugly kludge; we should fix the assignment signature instead (ditto for union)
     293                bool isDynamicLayout = false;  // NOTE see above re: kludge
    293294                std::list< TypeDecl* >& genericParams = aggregateDecl->get_parameters();
    294295                std::list< Expression* > structParams;  // List of matching parameters to put on types
     
    296297                for ( std::list< TypeDecl* >::const_iterator param = genericParams.begin(); param != genericParams.end(); ++param ) {
    297298                        isGeneric = true;
     299                        if ( (*param)->get_kind() == TypeDecl::Any ) isDynamicLayout = true;
    298300                        TypeDecl *typeParam = cloneAndRename( *param, "_autoassign_" + aggregateDecl->get_name() + "_" + (*param)->get_name() );
    299301                        assignType->get_forall().push_back( typeParam );
     
    355357                        FunctionDecl * ctor = new FunctionDecl( "?{}", functionNesting > 0 ? DeclarationNode::NoStorageClass : DeclarationNode::Static, LinkageSpec::AutoGen, memCtorType->clone(), new CompoundStmt( noLabels ), true, false );
    356358                        ctor->fixUniqueId();
    357                         makeStructFieldCtorBody( aggregateDecl->get_members().begin(), aggregateDecl->get_members().end(), ctor, genericSubs, isGeneric );
     359                        makeStructFieldCtorBody( aggregateDecl->get_members().begin(), aggregateDecl->get_members().end(), ctor, genericSubs, isGeneric, isDynamicLayout );
    358360                        memCtors.push_back( ctor );
    359361                }
     
    361363
    362364                // generate appropriate calls to member ctor, assignment
    363                 makeStructFunctionBody( aggregateDecl->get_members().begin(), aggregateDecl->get_members().end(), assignDecl, genericSubs, isGeneric );
    364                 makeStructFunctionBody( aggregateDecl->get_members().begin(), aggregateDecl->get_members().end(), ctorDecl, genericSubs, isGeneric );
    365                 makeStructFunctionBody( aggregateDecl->get_members().begin(), aggregateDecl->get_members().end(), copyCtorDecl, genericSubs, isGeneric );
     365                makeStructFunctionBody( aggregateDecl->get_members().begin(), aggregateDecl->get_members().end(), assignDecl, genericSubs, isGeneric, isDynamicLayout );
     366                makeStructFunctionBody( aggregateDecl->get_members().begin(), aggregateDecl->get_members().end(), ctorDecl, genericSubs, isGeneric, isDynamicLayout );
     367                makeStructFunctionBody( aggregateDecl->get_members().begin(), aggregateDecl->get_members().end(), copyCtorDecl, genericSubs, isGeneric, isDynamicLayout );
    366368                // needs to do everything in reverse, so pass "forward" as false
    367                 makeStructFunctionBody( aggregateDecl->get_members().rbegin(), aggregateDecl->get_members().rend(), dtorDecl, genericSubs, isGeneric, false );
     369                makeStructFunctionBody( aggregateDecl->get_members().rbegin(), aggregateDecl->get_members().rend(), dtorDecl, genericSubs, isGeneric, isDynamicLayout, false );
    368370
    369371                if ( ! isGeneric ) assignDecl->get_statements()->get_kids().push_back( new ReturnStmt( noLabels, new VariableExpr( srcParam ) ) );
     
    380382
    381383                // Make function polymorphic in same parameters as generic union, if applicable
    382                 bool isGeneric = false; // NOTE this flag is an incredibly ugly kludge; we should fix the assignment signature instead (ditto for struct)
     384                bool isDynamicLayout = false; // NOTE this flag is an incredibly ugly kludge; we should fix the assignment signature instead (ditto for struct)
    383385                std::list< TypeDecl* >& genericParams = aggregateDecl->get_parameters();
    384386                std::list< Expression* > unionParams;  // List of matching parameters to put on types
    385387                for ( std::list< TypeDecl* >::const_iterator param = genericParams.begin(); param != genericParams.end(); ++param ) {
    386                         isGeneric = true;
     388                        if ( (*param)->get_kind() == TypeDecl::Any ) isDynamicLayout = true;
    387389                        TypeDecl *typeParam = cloneAndRename( *param, "_autoassign_" + aggregateDecl->get_name() + "_" + (*param)->get_name() );
    388390                        assignType->get_forall().push_back( typeParam );
     
    420422
    421423                makeUnionFieldsAssignment( srcParam, dstParam, cloneWithParams( refType, unionParams ), back_inserter( assignDecl->get_statements()->get_kids() ) );
    422                 if ( isGeneric ) makeUnionFieldsAssignment( srcParam, returnVal, cloneWithParams( refType, unionParams ), back_inserter( assignDecl->get_statements()->get_kids() ) );
    423 
    424                 if ( ! isGeneric ) assignDecl->get_statements()->get_kids().push_back( new ReturnStmt( noLabels, new VariableExpr( srcParam ) ) );
     424                if ( isDynamicLayout ) makeUnionFieldsAssignment( srcParam, returnVal, cloneWithParams( refType, unionParams ), back_inserter( assignDecl->get_statements()->get_kids() ) );
     425                else assignDecl->get_statements()->get_kids().push_back( new ReturnStmt( noLabels, new VariableExpr( srcParam ) ) );
    425426
    426427                // body of assignment and copy ctor is the same
  • src/main.cc

    r1b0020a rc331406  
    2828#include "GenPoly/Box.h"
    2929#include "GenPoly/CopyParams.h"
     30#include "GenPoly/InstantiateGeneric.h"
    3031#include "CodeGen/Generate.h"
    3132#include "CodeGen/FixNames.h"
     
    309310                }
    310311
     312                OPTPRINT("instantiateGenerics")
     313                GenPoly::instantiateGeneric( translationUnit );
    311314                OPTPRINT( "copyParams" );
    312315                GenPoly::copyParams( translationUnit );
Note: See TracChangeset for help on using the changeset viewer.