Changes in / [36e05a2:fc19129]

Files:

• doc/generic_types/generic_types.tex (modified) (4 diffs)
• src/GenPoly/InstantiateGeneric.cc (modified) (1 diff)
• src/ResolvExpr/Unify.cc (modified) (2 diffs)

doc/generic_types/generic_types.tex

@@ -123 +123 @@
 \maketitle
 
-
 \section{Introduction \& Background}
 
@@ -146 +145 @@
 int forty_two = identity( 42 );                         $\C{// T is bound to int, forty\_two == 42}$
 \end{lstlisting}
-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@ that encode sufficient information about @T@ to create and return a variable of that type. The \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. If this extra information is not needed, e.g., for a pointer, the type parameter can be declared as @dtype T@, where @dtype@ is short for ``data type''.
+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@ that encode sufficient information about @T@ to create and return a variable of that type. The \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. If this extra information is not needed, \eg for a pointer, the type parameter can be declared as @dtype T@, where @dtype@ is short for ``data type''.
 
 Here, the runtime cost of polymorphism is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experiments have shown this overhead to be similar to \CC virtual function calls. An advantage of this design is that, unlike \CC template functions, \CFA @forall@ functions are compatible with C separate compilation.
@@ -387 +386 @@
 \subsection{Dynamic Generic Types}
 
-Though \CFA implements concrete generic types efficiently, it also has a fully general system for computing with dynamic generic types. As mentioned in Section~\ref{sec:poly-fns}, @otype@ function parameters (in fact all @sized@ polymorphic parameters) come with implicit size and alignment parameters provided by the caller. Dynamic generic structs have the same size and alignment parameter, and also an \emph{offset array} which contains the offsets of each member of the struct\footnote{Dynamic generic unions need no such offset array, as all members are at offset 0; the size and alignment parameters are still provided for dynamic unions, however.}. Access to members\footnote{The \lstinline@offsetof@ macro is implemented similarly.} of a dynamic generic struct is provided by adding the corresponding member of the offset array to the struct pointer at runtime, essentially moving a compile-time offset calculation to runtime where necessary.
+Though \CFA implements concrete generic types efficiently, it also has a fully general system for computing with dynamic generic types. As mentioned in Section~\ref{sec:poly-fns}, @otype@ function parameters (in fact all @sized@ polymorphic parameters) come with implicit size and alignment parameters provided by the caller. Dynamic generic structs also have implicit size and alignment parameters, and also an \emph{offset array} which contains the offsets of each member of the struct\footnote{Dynamic generic unions need no such offset array, as all members are at offset 0; the size and alignment parameters are still provided for dynamic unions, however.}. Access to members\footnote{The \lstinline@offsetof@ macro is implemented similarly.} of a dynamic generic struct is provided by adding the corresponding member of the offset array to the struct pointer at runtime, essentially moving a compile-time offset calculation to runtime where necessary.
 
 These offset arrays are statically generated where possible. If a dynamic generic type is declared to be passed or returned by value from a polymorphic function, the translator can safely assume that the generic type is complete (that is, has a known layout) at any call-site, and the offset array is passed from the caller; if the generic type is concrete at the call site the elements of this offset array can even be statically generated using the C @offsetof@ macro. As an example, @p.second@ in the @value@ function above is implemented as @*(p + _offsetof_pair[1])@, where @p@ is a @void*@, and @_offsetof_pair@ is the offset array passed in to @value@ for @pair(const char*, T)@. The offset array @_offsetof_pair@ is generated at the call site as @size_t _offsetof_pair[] = { offsetof(_pair_conc1, first), offsetof(_pair_conc1, second) };@.
@@ -521 +520 @@
 In \CFA, each of these calls is valid. In the call to @f@, @x@ is implicitly flattened so that the components of @x@ are passed as the two arguments to @f@. For the call to @g@, the values @y@ and @10@ are structured into a single argument of type @[int, int]@ to match the type of the parameter of @g@. Finally, in the call to @h@, @y@ is flattened to yield an argument list of length 3, of which the first component of @x@ is passed as the first parameter of @h@, and the second component of @x@ and @y@ are structured into the second argument of type @[int, int]@. The flexible structure of tuples permits a simple and expressive function call syntax to work seamlessly with both single- and multiple-return-value functions, and with any number of arguments of arbitrarily complex structure.
 
-In {K-W C}~\citep{Buhr94a,Till89}, a precursor to \CFA, there were 4 tuple coercions: opening, closing, flattening, and structuring. Opening coerces a tuple value into a tuple of values, while closing converts a tuple of values into a single tuple value. Flattening coerces a nested tuple into a flat tuple, \ie it takes a tuple with tuple components and expands it into a tuple with only non-tuple components. Structuring moves in the opposite direction, \ie it takes a flat tuple value and provides structure by introducing nested tuple components.
+% In {K-W C} \citep{Buhr94a,Till89}, a precursor to \CFA, there were 4 tuple coercions: opening, closing, flattening, and structuring. Opening coerces a tuple value into a tuple of values, while closing converts a tuple of values into a single tuple value. Flattening coerces a nested tuple into a flat tuple, \ie it takes a tuple with tuple components and expands it into a tuple with only non-tuple components. Structuring moves in the opposite direction, \ie it takes a flat tuple value and provides structure by introducing nested tuple components.
 
 In \CFA, the design has been simplified to require only the two conversions previously described, which trigger only in function call and return situations. Specifically, the expression resolution algorithm examines all of the possible alternatives for an expression to determine the best match. In resolving a function call expression, each combination of function value and list of argument alternatives is examined. Given a particular argument list and function value, the list of argument alternatives is flattened to produce a list of non-tuple valued expressions. Then the flattened list of expressions is compared with each value in the function's parameter list. If the parameter's type is not a tuple type, then the current argument value is unified with the parameter type, and on success the next argument and parameter are examined. If the parameter's type is a tuple type, then the structuring conversion takes effect, recursively applying the parameter matching algorithm using the tuple's component types as the parameter list types. Assuming a successful unification, eventually the algorithm gets to the end of the tuple type, which causes all of the matching expressions to be consumed and structured into a tuple expression. For example, in

src/GenPoly/InstantiateGeneric.cc

@@ -255 +255 @@
                 }
 
-                assert( baseParam == baseParams.end() && param == params.end() && "Type parameters should match type variables" );
+                assertf( baseParam == baseParams.end() && param == params.end(), "Type parameters should match type variables" );
                 return gt;
         }

src/ResolvExpr/Unify.cc

@@ -134 +134 @@
                   case TypeDecl::Ftype:
                         return isFtype( type, indexer );
-                        case TypeDecl::Ttype:
+                  case TypeDecl::Ttype:
                         // ttype unifies with any tuple type
                         return dynamic_cast< TupleType * >( type ) || Tuples::isTtype( type );
@@ -592 +592 @@
                 for ( ; it != params.end() && jt != otherParams.end(); ++it, ++jt ) {
                         TypeExpr *param = dynamic_cast< TypeExpr* >(*it);
-                        assert(param && "Aggregate parameters should be type expressions");
+                        assertf(param, "Aggregate parameters should be type expressions");
                         TypeExpr *otherParam = dynamic_cast< TypeExpr* >(*jt);
-                        assert(otherParam && "Aggregate parameters should be type expressions");
-
-                        if ( ! unifyExact( param->get_type(), otherParam->get_type(), env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
+                        assertf(otherParam, "Aggregate parameters should be type expressions");
+                        
+                        Type* paramTy = param->get_type();
+                        Type* otherParamTy = otherParam->get_type();
+
+                        bool tupleParam = Tuples::isTtype( paramTy );
+                        bool otherTupleParam = Tuples::isTtype( otherParamTy );
+
+                        if ( tupleParam && otherTupleParam ) {
+                                ++it; ++jt;  // skip ttype parameters for break
+                        } else if ( tupleParam ) {
+                                // bundle other parameters into tuple to match
+                                TupleType* binder = new TupleType{ paramTy->get_qualifiers() };
+
+                                do {
+                                        binder->get_types().push_back( otherParam->get_type()->clone() );
+                                        ++jt;
+
+                                        if ( jt == otherParams.end() ) break;
+
+                                        otherParam = dynamic_cast< TypeExpr* >(*jt);
+                                        assertf(otherParam, "Aggregate parameters should be type expressions");
+                                } while (true);
+
+                                otherParamTy = binder;
+                                ++it;  // skip ttype parameter for break
+                        } else if ( otherTupleParam ) {
+                                // bundle parameters into tuple to match other
+                                TupleType* binder = new TupleType{ otherParamTy->get_qualifiers() };
+
+                                do {
+                                        binder->get_types().push_back( param->get_type()->clone() );
+                                        ++it;
+
+                                        if ( it == params.end() ) break;
+
+                                        param = dynamic_cast< TypeExpr* >(*it);
+                                        assertf(param, "Aggregate parameters should be type expressions");
+                                } while (true);
+
+                                paramTy = binder;
+                                ++jt;  // skip ttype parameter for break
+                        }
+
+                        if ( ! unifyExact( paramTy, otherParamTy, env, needAssertions, haveAssertions, openVars, WidenMode(false, false), indexer ) ) {
                                 result = false;
                                 return;
                         }
+
+                        // ttype parameter should be last
+                        if ( tupleParam || otherTupleParam ) break;
                 }
                 result = ( it == params.end() && jt == otherParams.end() );