Changes in / [0fa0201d:5546eee4]
- Files:
-
- 9 added
- 48 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/mike_brooks_MMath/array.tex
r0fa0201d r5546eee4 1 1 \chapter{Array} 2 2 3 \section{Introduction} 4 5 This chapter describes my contribution of language and library features that provide a length-checked array type, as in: 6 7 \begin{lstlisting} 8 array(float, 99) x; // x contains 99 floats 9 10 void f( array(float, 42) & a ) {} 11 f(x); // statically rejected: types are different 12 13 forall( T, [N] ) 14 void g( array(T, N) & a, int i ) { 15 T elem = a[i]; // dynamically checked: requires 0 <= i < N 16 } 17 g(x, 0); // T is float, N is 99, succeeds 18 g(x, 1000); // T is float, N is 99, dynamic check fails 19 \end{lstlisting} 20 21 This example first declares @x@ a variable, whose type is an instantiation of the generic type named @array@, with arguments @float@ and @99@. 22 Next, it declares @f@ as a function that expects a length-42 array; the type system rejects the call's attempt to pass @x@ to @f@, because the lengths do not match. 23 Next, the @forall@ annotation on function @g@ introduces @T@ as a familiar type parameter and @N@ as a \emph{dimension} parameter, a new feature that represents a count of elements, as managed by the type system. 24 Because @g@ accepts any length of array; the type system accepts the calls' passing @x@ to @g@, inferring that this length is 99. 25 Just as the caller's code does not need to explain that @T@ is @float@, the safe capture and communication of the value @99@ occurs without programmer involvement. 26 In the case of the second call (which passes the value 1000 for @i@), within the body of @g@, the attempt to subscript @a@ by @i@ fails with a runtime error, since $@i@ \nless @N@$. 27 28 The type @array@, as seen above, comes from my additions to the \CFA standard library. 29 It is very similar to the built-in array type, which \CFA inherits from C. 30 Its runtime characteristics are often identical, and some features are available in both. 31 32 \begin{lstlisting} 33 forall( [N] ) 34 void declDemo() { 35 float a1[N]; // built-in type ("C array") 36 array(float, N) a2; // type from library 37 } 38 \end{lstlisting} 39 40 If a caller instantiates @N@ with 42, then both locally-declared array variables, @a1@ and @a2@, become arrays of 42 elements, each element being a @float@. 41 The two variables have identical size and layout; they both encapsulate 42-float stack allocations, no heap allocations, and no further "bookkeeping" allocations/header. 42 Having the @array@ library type (that of @a2@) is a tactical measure, an early implementation that offers full feature support. 43 A future goal (TODO xref) is to port all of its features into the built-in array type (that of @a1@); then, the library type could be removed, and \CFA would have only one array type. 44 In present state, the built-in array has partial support for the new features. 45 The fully-featured library type is used exclusively in introductory examples; feature support and C compatibility are revisited in sec TODO. 46 47 Offering the @array@ type, as a distinct alternative from the the C array, is consistent with \CFA's extension philosophy (TODO xref background) to date. 48 A few compatibility-breaking changes to the behaviour of the C array were also made, both as an implementation convenience, and as justified fixes to C's lax treatment. 49 50 The @array@ type is an opportunity to start from a clean slate and show a cohesive selection of features. 51 A clean slate was an important starting point because it meant not having to deal with every inherited complexity introduced in TODO xref background-array. 52 53 54 My contributions are 55 \begin{itemize} 56 \item a type system enhancement that lets polymorphic functions and generic types be parameterized by a numeric value: @forall( [N] )@ 57 \item [TODO: general parking...] 58 \item identify specific abilities brought by @array@ 59 \item Where there is a gap concerning this feature's readiness for prime-time, identification of specific workable improvements that are likely to close the gap 60 \end{itemize} 61 62 63 64 \section{Definitions and design considerations} 65 66 \subsection{Dependent typing} 67 68 69 70 3 71 \section{Features Added} 4 72 5 73 The present work adds a type @array@ to the \CFA standard library~\cite{Cforall}. 6 74 7 This array's length is statically governed and dynamically valued. This static governance achieves argument safety and suggests a path to subscript safety as future work (TODO: cross reference). In present state, this work is a runtime libray accessed through a system of macros, while section [TODO: discuss C conexistence] discusses a path for the new array type to be accessed directly by \CFA's array syntax, replacing the lifted C array that this syntax currently exposes. 8 9 This section presents motivating examples of the new array type's usage, and follows up with definitions of the notations that appear. 10 11 The core of the new array governance is tracking all array lengths in the type system. Dynamically valued lengths are represented using type variables. The stratification of type variables preceding object declarations makes a length referenceable everywhere that it is needed. For example, a declaration can share one length, @N@, among a pair of parameters and the return. 12 \lstinputlisting[language=CFA, firstline=50, lastline=59]{hello-array.cfa} 13 Here, the function @f@ does a pointwise comparison, checking if each pair of numbers is within half a percent of each other, returning the answers in a newly allocated bool array. 14 15 The array type uses the parameterized length information in its @sizeof(-)@ determination, illustrated in the example's call to @alloc@. That call requests an allocation of type @array(bool, N)@, which the type system deduces from the left-hand side of the initialization, into the return type of the @alloc@ call. Preexesting \CFA behaviour is leveraged here, both in the return-type-only polymorphism, and the @sized(T)@-aware standard-library @alloc@ routine. The new @array@ type plugs into this behaviour by implementing the @sized@/@sizeof(-)@ assertion to have the intuitive meaning. As a result, this design avoids an opportunity for programmer error by making the size/length communication to a called routine implicit, compared with C's @calloc@ (or the low-level \CFA analog @aalloc@) which take an explicit length parameter not managed by the type system. 16 17 A harness for this @f@ function shows how dynamic values are fed into the system. 18 \lstinputlisting[language=CFA, firstline=100, lastline=119]{hello-array.cfa} 19 Here, the @a@ sequence is loaded with decreasing values, and the @b@ sequence with amounts off by a constant, giving relative differences within tolerance at first and out of tolerance later. The driver program is run with two different inputs of sequence length. 20 21 The loops in the driver follow the more familiar pattern of using the ordinary variable @n@ to convey the length. The type system implicitly captures this value at the call site (@main@ calling @f@) and makes it available within the callee (@f@'s loop bound). 22 23 The two parts of the example show @Z(n)@ adapting a variable into a type-system governed length (at @main@'s declarations of @a@, @b@, and @result@), @z(N)@ adapting in the opposite direction (at @f@'s loop bound), and a passthru use of a governed length (at @f@'s declaration of @ret@.) It is hoped that future language integration will allow the macros @Z@ and @z@ to be omitted entirely from the user's notation, creating the appearance of seamlessly interchanging numeric values with appropriate generic parameters. 24 25 The macro-assisted notation, @forall...ztype@, participates in the user-relevant declaration of the name @N@, which becomes usable in parameter/return declarations and in the function body. So future language integration only sweetens this form and does not seek to elimimate the declaration. The present form is chosen to parallel, as closely as a macro allows, the existing forall forms: 26 \begin{lstlisting} 27 forall( dtype T ) ... 28 forall( otype T ) ... 29 forall( ztype(N) ) ... 30 \end{lstlisting} 31 32 The notation @array(thing, N)@ is also macro-assisted, though only in service of enabling multidimensional uses discussed further in section \ref{toc:mdimpl}. In a single-dimensional case, the marco expansion gives a generic type instance, exactly like the original form suggests. 33 34 35 75 This array's length is statically managed and dynamically valued. This static management achieves argument safety and suggests a path to subscript safety as future work (TODO: cross reference). 76 77 This section presents motivating examples of the new array type's usage and follows up with definitions of the notations that appear. 78 79 The core of the new array management is tracking all array lengths in the type system. Dynamically valued lengths are represented using type variables. The stratification of type variables preceding object declarations makes a length referenceable everywhere that it is needed. For example, a declaration can share one length, @N@, among a pair of parameters and the return. 80 \lstinputlisting[language=CFA, firstline=10, lastline=17]{hello-array.cfa} 81 Here, the function @f@ does a pointwise comparison, checking if each pair of numbers is within half a percent of each other, returning the answers in a newly allocated @bool@ array. 82 83 The array type uses the parameterized length information in its @sizeof@ determination, illustrated in the example's call to @alloc@. That call requests an allocation of type @array(bool, N)@, which the type system deduces from the left-hand side of the initialization, into the return type of the @alloc@ call. Preexisting \CFA behaviour is leveraged here, both in the return-type-only polymorphism, and the @sized(T)@-aware standard-library @alloc@ routine. The new @array@ type plugs into this behaviour by implementing the @sized@/@sizeof@ assertion to have the intuitive meaning. As a result, this design avoids an opportunity for programmer error by making the size/length communication to a called routine implicit, compared with C's @calloc@ (or the low-level \CFA analog @aalloc@), which take an explicit length parameter not managed by the type system. 84 85 \VRef[Figure]{f:fHarness} shows the harness to use the @f@ function illustrating how dynamic values are fed into the system. 86 Here, the @a@ array is loaded with decreasing values, and the @b@ array with amounts off by a constant, giving relative differences within tolerance at first and out of tolerance later. The program main is run with two different inputs of sequence length. 87 88 \begin{figure} 89 \lstinputlisting[language=CFA, firstline=30, lastline=49]{hello-array.cfa} 90 \caption{\lstinline{f} Harness} 91 \label{f:fHarness} 92 \end{figure} 93 94 The loops in the program main follow the more familiar pattern of using the ordinary variable @n@ to convey the length. The type system implicitly captures this value at the call site (@main@ calling @f@) and makes it available within the callee (@f@'s loop bound). 95 96 The two parts of the example show @n@ adapting a variable into a type-system managed length (at @main@'s declarations of @a@, @b@, and @result@), @N@ adapting in the opposite direction (at @f@'s loop bound), and a pass-thru use of a managed length (at @f@'s declaration of @ret@). 97 98 The @forall( ...[N] )@ participates in the user-relevant declaration of the name @N@, which becomes usable in parameter/return declarations and in the function @b@. The present form is chosen to parallel the existing @forall@ forms: 99 \begin{cfa} 100 forall( @[N]@ ) ... // array kind 101 forall( & T ) ... // reference kind (dtype) 102 forall( T ) ... // value kind (otype) 103 \end{cfa} 104 105 The notation @array(thing, N)@ is a single-dimensional case, giving a generic type instance. 36 106 In summary: 37 38 \ begin{tabular}{p{15em}p{20em}}39 @ztype( N )@ & within a forall, declares the type variable @N@ to be a governed length \\[0.25em] 40 @Z( @ $e$ @ )@ & a type representing the value of $e$ as a governed length, where $e$ is a @size_t@-typed expression \\[0.25em] 41 @z( N )@ & an expression of type @size_t@, whose value is the governed length @N@ \\[0.25em] 42 @array( thing, N0, N1, ... )@ 43 & a type wrapping $\prod_i N_i$ adjacent occurrences of @thing@ objects 44 \ end{tabular}45 46 Unsigned integers have a special status in this type system. Unlike how C++ allows @template< size_t N, char * msg, typename T >...@ declarations, this system does not accommodate values of any user-provided type. TODO: discuss connection with dependent types. 47 107 \begin{itemize} 108 \item 109 @[N]@ -- within a forall, declares the type variable @N@ to be a managed length 110 \item 111 $e$ -- a type representing the value of $e$ as a managed length, where $e$ is a @size_t@-typed expression 112 \item 113 N -- an expression of type @size_t@, whose value is the managed length @N@ 114 \item 115 @array( thing, N0, N1, ... )@ -- a type wrapping $\prod_i N_i$ adjacent occurrences of @thing@ objects 116 \end{itemize} 117 Unsigned integers have a special status in this type system. Unlike how C++ allows @template< size_t N, char * msg, typename T >...@ declarations, \CFA does not accommodate values of any user-provided type. TODO: discuss connection with dependent types. 48 118 49 119 An example of a type error demonstrates argument safety. The running example has @f@ expecting two arrays of the same length. A compile-time error occurs when attempting to call @f@ with arrays whose lengths may differ. 50 \lstinputlisting[language=CFA, firstline=150, lastline=155]{hello-array.cfa} 51 As is common practice in C, the programmer is free to cast, to assert knownledge not shared with the type system. 52 \lstinputlisting[language=CFA, firstline=200, lastline=202]{hello-array.cfa} 53 54 Argument safety, and the associated implicit communication of length, work with \CFA's generic types too. As a structure can be defined over a parameterized element type, so can it be defined over a parameterized length. Doing so gives a refinement of C's ``flexible array member'' pattern, that allows nesting structures with array members anywhere within other structures. 55 \lstinputlisting[language=CFA, firstline=20, lastline=26]{hello-accordion.cfa} 56 This structure's layout has the starting offest of @cost_contribs@ varying in @Nclients@, and the offset of @total_cost@ varying in both generic paramters. For a function that operates on a @request@ structure, the type system handles this variation transparently. 57 \lstinputlisting[language=CFA, firstline=50, lastline=57]{hello-accordion.cfa} 58 In the example runs of a driver program, different offset values are navigated in the two cases. 59 \lstinputlisting[language=CFA, firstline=100, lastline=115]{hello-accordion.cfa} 120 \lstinputlisting[language=CFA, firstline=60, lastline=65]{hello-array.cfa} 121 As is common practice in C, the programmer is free to cast, to assert knowledge not shared with the type system. 122 \lstinputlisting[language=CFA, firstline=70, lastline=75]{hello-array.cfa} 123 124 Argument safety and the associated implicit communication of array length work with \CFA's generic types too. 125 \CFA allows aggregate types to be generalized with multiple type parameters, including parameterized element type, so can it be defined over a parameterized length. 126 Doing so gives a refinement of C's ``flexible array member'' pattern, that allows nesting structures with array members anywhere within other structures. 127 \lstinputlisting[language=CFA, firstline=10, lastline=16]{hello-accordion.cfa} 128 This structure's layout has the starting offset of @cost_contribs@ varying in @Nclients@, and the offset of @total_cost@ varying in both generic parameters. For a function that operates on a @request@ structure, the type system handles this variation transparently. 129 \lstinputlisting[language=CFA, firstline=40, lastline=47]{hello-accordion.cfa} 130 In the example, different runs of the program result in different offset values being used. 131 \lstinputlisting[language=CFA, firstline=60, lastline=76]{hello-accordion.cfa} 60 132 The output values show that @summarize@ and its caller agree on both the offsets (where the callee starts reading @cost_contribs@ and where the callee writes @total_cost@). Yet the call site still says just, ``pass the request.'' 61 133 … … 67 139 TODO: introduce multidimensional array feature and approaches 68 140 69 The new \CFA standard library @array@ datatype supports multidimensional uses more richly than the C array. The new array's multi mentsional interface and implementation, follows an array-of-arrays setup, meaning, like C's @float[n][m]@ type, one contiguous object, with coarsely-strided dimensions directly wrapping finely-strided dimensions. This setup is in contrast with the pattern of array of pointers to other allocations representing a sub-array. Beyond what C's type offers, the new array brings direct support for working with a noncontiguous array slice, allowing a program to work with dimension subscripts given in a non-physical order. C and C++ require a programmer with such a need to manage pointer/offset arithmetic manually.70 71 Examples are shown using a $5 \times 7$ float array, @a@, loaded with increments of $0.1$ when stepping across the length-7 finely-strided dimension shown on columns, and with increments of $1.0$ when stepping across the length-5 co rsely-strided dimension shown on rows.72 \lstinputlisting[language=CFA, firstline=120, lastline=12 8]{hello-md.cfa}141 The new \CFA standard library @array@ datatype supports multidimensional uses more richly than the C array. The new array's multidimensional interface and implementation, follows an array-of-arrays setup, meaning, like C's @float[n][m]@ type, one contiguous object, with coarsely-strided dimensions directly wrapping finely-strided dimensions. This setup is in contrast with the pattern of array of pointers to other allocations representing a sub-array. Beyond what C's type offers, the new array brings direct support for working with a noncontiguous array slice, allowing a program to work with dimension subscripts given in a non-physical order. C and C++ require a programmer with such a need to manage pointer/offset arithmetic manually. 142 143 Examples are shown using a $5 \times 7$ float array, @a@, loaded with increments of $0.1$ when stepping across the length-7 finely-strided dimension shown on columns, and with increments of $1.0$ when stepping across the length-5 coarsely-strided dimension shown on rows. 144 \lstinputlisting[language=CFA, firstline=120, lastline=126]{hello-md.cfa} 73 145 The memory layout of @a@ has strictly increasing numbers along its 35 contiguous positions. 74 146 75 A trivial form of slicing extracts a contiguous inner array, within an array-of-arrays. Like with the C array, a lesser-dimensional array reference can be bound to the result of subscripting a greater-dimensional array, by a prefix of its dimensions. This action first subscripts away the most coar esly strided dimensions, leaving a result that expects to be be subscripted by the more finely strided dimensions.147 A trivial form of slicing extracts a contiguous inner array, within an array-of-arrays. Like with the C array, a lesser-dimensional array reference can be bound to the result of subscripting a greater-dimensional array, by a prefix of its dimensions. This action first subscripts away the most coarsely strided dimensions, leaving a result that expects to be be subscripted by the more finely strided dimensions. 76 148 \lstinputlisting[language=CFA, firstline=60, lastline=66]{hello-md.cfa} 77 \lstinputlisting[ language=CFA, firstline=140, lastline=140]{hello-md.cfa}78 79 This function declaration is asserting too much knowledge about its parameter @c@, for it to be usable for printing either a row slice or a column slice. Specifically, declaring the parameter @c@ with type @array@ means that @c@ is contiguous. However, the function does not use this fact. For the function to do its job, @c@ need only be of a container type that offers a subscript operator (of type @ptrdiff_t@ $\rightarrow$ @float@), with governed length @N@. The new-array library provides the trait @ix@, so-defined. With it, the original declaration can be generalized, while still implemented with the same body, to the latter declaration:149 \lstinputlisting[aboveskip=0pt, language=CFA, firstline=140, lastline=140]{hello-md.cfa} 150 151 This function declaration is asserting too much knowledge about its parameter @c@, for it to be usable for printing either a row slice or a column slice. Specifically, declaring the parameter @c@ with type @array@ means that @c@ is contiguous. However, the function does not use this fact. For the function to do its job, @c@ need only be of a container type that offers a subscript operator (of type @ptrdiff_t@ $\rightarrow$ @float@), with managed length @N@. The new-array library provides the trait @ix@, so-defined. With it, the original declaration can be generalized, while still implemented with the same body, to the latter declaration: 80 152 \lstinputlisting[language=CFA, firstline=40, lastline=44]{hello-md.cfa} 81 \lstinputlisting[ language=CFA, firstline=145, lastline=145]{hello-md.cfa}153 \lstinputlisting[aboveskip=0pt, language=CFA, firstline=145, lastline=145]{hello-md.cfa} 82 154 83 155 Nontrivial slicing, in this example, means passing a noncontiguous slice to @print1d@. The new-array library provides a ``subscript by all'' operation for this purpose. In a multi-dimensional subscript operation, any dimension given as @all@ is left ``not yet subscripted by a value,'' implementing the @ix@ trait, waiting for such a value. … … 122 194 \begin{figure} 123 195 \includegraphics{measuring-like-layout} 124 \caption{Visualization of subscripting by value and by \lstinline[language=CFA,basicstyle=\ttfamily]{all}, for \lstinline[language=CFA,basicstyle=\ttfamily]{a} of type \lstinline[language=CFA,basicstyle=\ttfamily]{array( float, Z(5), Z(7))}. The horizontal dimension represents memory addresses while vertical layout is conceptual.}196 \caption{Visualization of subscripting by value and by \lstinline[language=CFA,basicstyle=\ttfamily]{all}, for \lstinline[language=CFA,basicstyle=\ttfamily]{a} of type \lstinline[language=CFA,basicstyle=\ttfamily]{array( float, 5, 7 )}. The horizontal dimension represents memory addresses while vertical layout is conceptual.} 125 197 \label{fig:subscr-all} 126 198 \end{figure} 127 199 128 \noindent While the latter description implies overlapping elements, Figure \ref{fig:subscr-all} shows that the overlaps only occur with unused spaces between elements. Its depictions of @a[all][...]@ show the navigation of a memory layout with nontrivial strides, that is, with ``spaced \_ floats apart'' values that are greater or smaller than the true count of valid ind eces times the size of a logically indexed element. Reading from the bottom up, the expression @a[all][3][2]@ shows a float, that is masquerading as a @float[7]@, for the purpose of being arranged among its peers; five such occurrences form @a[all][3]@. The tail of flatter boxes extending to the right of a poper element represents this stretching. At the next level of containment, the structure @a[all][3]@ masquerades as a @float[1]@, for the purpose of being arranged among its peers; seven such occurrences form @a[all]@. The verical staircase arrangement represents this compression, and resulting overlapping.129 130 The new-array library defines types and operations that ensure proper elements are accessed soundly in spite of the overlapping. The private @arpk@ structure (array with explicit packing) is generic over these two types (and more): the contained element, what it is masquerading as. This structure's public interface is the @array(...)@ construction macro and the two subscript operators. Construction by @array@ initializes the masquerading-as type information to be equal to the contained-element information. Subscr pting by @all@ rearranges the order of masquerading-as types to achieve, in genernal, nontrivial striding. Subscripting by a number consumes the masquerading-as size of the contained element type, does normal array stepping according to that size, and returns there element found there, in unmasked form.200 \noindent While the latter description implies overlapping elements, Figure \ref{fig:subscr-all} shows that the overlaps only occur with unused spaces between elements. Its depictions of @a[all][...]@ show the navigation of a memory layout with nontrivial strides, that is, with ``spaced \_ floats apart'' values that are greater or smaller than the true count of valid indices times the size of a logically indexed element. Reading from the bottom up, the expression @a[all][3][2]@ shows a float, that is masquerading as a @float[7]@, for the purpose of being arranged among its peers; five such occurrences form @a[all][3]@. The tail of flatter boxes extending to the right of a proper element represents this stretching. At the next level of containment, the structure @a[all][3]@ masquerades as a @float[1]@, for the purpose of being arranged among its peers; seven such occurrences form @a[all]@. The vertical staircase arrangement represents this compression, and resulting overlapping. 201 202 The new-array library defines types and operations that ensure proper elements are accessed soundly in spite of the overlapping. The private @arpk@ structure (array with explicit packing) is generic over these two types (and more): the contained element, what it is masquerading as. This structure's public interface is the @array(...)@ construction macro and the two subscript operators. Construction by @array@ initializes the masquerading-as type information to be equal to the contained-element information. Subscripting by @all@ rearranges the order of masquerading-as types to achieve, in general, nontrivial striding. Subscripting by a number consumes the masquerading-as size of the contained element type, does normal array stepping according to that size, and returns there element found there, in unmasked form. 131 203 132 204 The @arpk@ structure and its @-[i]@ operator are thus defined as: … … 138 210 ) { 139 211 struct arpk { 140 S strides[ z(N)];// so that sizeof(this) is N of S212 S strides[N]; // so that sizeof(this) is N of S 141 213 }; 142 214 … … 148 220 \end{lstlisting} 149 221 150 An instanti on of the @arpk@ generic is given by the @array(E_base, N0, N1, ...)@ exapnsion, which is @arpk( N0, Rec, Rec, E_base )@, where @Rec@ is @array(E_base, N1, ...)@. In the base case, @array(E_base)@ is just @E_base@. Because this construction uses the same value for the generic parameters @S@ and @E_im@, the resulting layout has trivial strides.151 152 Subscripting by @all@, to operate on nontrivial strides, is a dequeue-enqueue operation on the @E_im@ chain, which carries @S@ insta tiations, intact, to new positions. Expressed as an operation on types, this rotation is:222 An instantiation of the @arpk@ generic is given by the @array(E_base, N0, N1, ...)@ expansion, which is @arpk( N0, Rec, Rec, E_base )@, where @Rec@ is @array(E_base, N1, ...)@. In the base case, @array(E_base)@ is just @E_base@. Because this construction uses the same value for the generic parameters @S@ and @E_im@, the resulting layout has trivial strides. 223 224 Subscripting by @all@, to operate on nontrivial strides, is a dequeue-enqueue operation on the @E_im@ chain, which carries @S@ instantiations, intact, to new positions. Expressed as an operation on types, this rotation is: 153 225 \begin{eqnarray*} 154 226 suball( arpk(N, S, E_i, E_b) ) & = & enq( N, S, E_i, E_b ) \\ … … 160 232 \section{Bound checks, added and removed} 161 233 162 \CFA array subscripting is protected with runtime bound checks. Having dependent typing causes the op imizer to remove more of these bound checks than it would without them. This section provides a demonstration of the effect.163 164 The experiment compares the \CFA array system with the padded-room system [ todo:xref] most typically exemplified by Java arrays, but also reflected in the C++ pattern where restricted vector usage models a checked array. The essential feature of this padded-room system is the one-to-one correspondence between array instances and the symbolic bounds on which dynamic checks are based. The experiment compares with the C++ version to keep access to generated assembly code simple.165 166 As a control case, a simple loop (with no reused dimension sizes) is seen to get the same optimization treatment in both the \CFA and C++ versions. When the programmer treats the array's bound correctly (making the subscript ``obviously fine''), no dynamic bound check is observed in the program's optimized assembly code. But when the bounds are adjusted, such that the subscript is possibly invalid, the bound check appears in the optimized assem ly, ready to catch an occurrence the mistake.167 168 TODO: paste source and assemb y codes234 \CFA array subscripting is protected with runtime bound checks. Having dependent typing causes the optimizer to remove more of these bound checks than it would without them. This section provides a demonstration of the effect. 235 236 The experiment compares the \CFA array system with the padded-room system [TODO:xref] most typically exemplified by Java arrays, but also reflected in the C++ pattern where restricted vector usage models a checked array. The essential feature of this padded-room system is the one-to-one correspondence between array instances and the symbolic bounds on which dynamic checks are based. The experiment compares with the C++ version to keep access to generated assembly code simple. 237 238 As a control case, a simple loop (with no reused dimension sizes) is seen to get the same optimization treatment in both the \CFA and C++ versions. When the programmer treats the array's bound correctly (making the subscript ``obviously fine''), no dynamic bound check is observed in the program's optimized assembly code. But when the bounds are adjusted, such that the subscript is possibly invalid, the bound check appears in the optimized assembly, ready to catch an occurrence the mistake. 239 240 TODO: paste source and assembly codes 169 241 170 242 Incorporating reuse among dimension sizes is seen to give \CFA an advantage at being optimized. The case is naive matrix multiplication over a row-major encoding. … … 178 250 \section{Comparison with other arrays} 179 251 180 \CFA's array is the first lightweight application of dependently-typed bound tracking to an extension of C. Other extensions of C that apply dependently-typed bound tracking are heavyweight, in that the bound tracking is part of a linearly typed ownership system that further helps guarantee statically the validity of every pointer deference. These systems, therefore, ask the programmer to convince the type checker that every pointer dereference is valid. \CFA imposes the lighter-weight obligation, with the more limited guarantee, that initially-declared bounds are respected thereafter.252 \CFA's array is the first lightweight application of dependently-typed bound tracking to an extension of C. Other extensions of C that apply dependently-typed bound tracking are heavyweight, in that the bound tracking is part of a linearly typed ownership system that further helps guarantee statically the validity of every pointer deference. These systems, therefore, ask the programmer to convince the type checker that every pointer dereference is valid. \CFA imposes the lighter-weight obligation, with the more limited guarantee, that initially-declared bounds are respected thereafter. 181 253 182 254 \CFA's array is also the first extension of C to use its tracked bounds to generate the pointer arithmetic implied by advanced allocation patterns. Other bound-tracked extensions of C either forbid certain C patterns entirely, or address the problem of \emph{verifying} that the user's provided pointer arithmetic is self-consistent. The \CFA array, applied to accordion structures [TOD: cross-reference] \emph{implies} the necessary pointer arithmetic, generated automatically, and not appearing at all in a user's program. … … 184 256 \subsection{Safety in a padded room} 185 257 186 Java's array [ todo:cite] is a straightforward example of assuring safety against undefined behaviour, at a cost of expressiveness for more applied properties. Consider the array parameter declarations in:258 Java's array [TODO:cite] is a straightforward example of assuring safety against undefined behaviour, at a cost of expressiveness for more applied properties. Consider the array parameter declarations in: 187 259 188 260 \begin{tabular}{rl} … … 191 263 \end{tabular} 192 264 193 Java's safety against undefined behaviour assures the callee that, if @a@ is non-null, then @a.length@ is a valid access (say, evaluating to the number $\ell$) and if @i@ is in $[0, \ell)$ then @a[i]@ is a valid access. If a value of @i@ outside this range is used, a runtime error is guaranteed. In these respects, C offers no guarante ss at all. Notably, the suggestion that @n@ is the intended size of the first dimension of @a@ is documentation only. Indeed, many might prefer the technically equivalent declarations @float a[][m]@ or @float (*a)[m]@ as emphasizing the ``no guarantees'' nature of an infrequently used language feature, over using the opportunity to explain a programmer intention. Moreover, even if @a[0][0]@ is valid for the purpose intended, C's basic infamous feature is the possibility of an @i@, such that @a[i][0]@ is not valid for the same purpose, and yet, its evaluation does not produce an error.265 Java's safety against undefined behaviour assures the callee that, if @a@ is non-null, then @a.length@ is a valid access (say, evaluating to the number $\ell$) and if @i@ is in $[0, \ell)$ then @a[i]@ is a valid access. If a value of @i@ outside this range is used, a runtime error is guaranteed. In these respects, C offers no guarantees at all. Notably, the suggestion that @n@ is the intended size of the first dimension of @a@ is documentation only. Indeed, many might prefer the technically equivalent declarations @float a[][m]@ or @float (*a)[m]@ as emphasizing the ``no guarantees'' nature of an infrequently used language feature, over using the opportunity to explain a programmer intention. Moreover, even if @a[0][0]@ is valid for the purpose intended, C's basic infamous feature is the possibility of an @i@, such that @a[i][0]@ is not valid for the same purpose, and yet, its evaluation does not produce an error. 194 266 195 267 Java's lack of expressiveness for more applied properties means these outcomes are possible: … … 201 273 C's array has none of these limitations, nor do any of the ``array language'' comparators discussed in this section. 202 274 203 This Java level of safety and expressiveness is also exemplified in the C family, with the commonly given advice [ todo:cite example], for C++ programmers to use @std::vector@ in place of the C++ language's array, which is essentially the C array. The advice is that, while a vector is also more powerful (and quirky) than an arry, its capabilities include options to preallocate with an upfront size, to use an available bound-checked accessor (@a.at(i)@ in place of @a[i]@), to avoid using @push_back@, and to use a vector of vectors. Used with these restrictions, out-of-bound accesses are stopped, and in-bound accesses never exercise the vector's ability to grow, which is to say, they never make the program slow to reallocate and copy, and they never invalidate the program's other references to the contained values. Allowing this scheme the same referential integrity assumption that \CFA enjoys [todo:xref], this scheme matches Java's safety and expressiveness exactly. [TODO: decide about going deeper; some of the Java expressiveness concerns have mitigations, up to even more tradeoffs.]275 This Java level of safety and expressiveness is also exemplified in the C family, with the commonly given advice [TODO:cite example], for C++ programmers to use @std::vector@ in place of the C++ language's array, which is essentially the C array. The advice is that, while a vector is also more powerful (and quirky) than an array, its capabilities include options to preallocate with an upfront size, to use an available bound-checked accessor (@a.at(i)@ in place of @a[i]@), to avoid using @push_back@, and to use a vector of vectors. Used with these restrictions, out-of-bound accesses are stopped, and in-bound accesses never exercise the vector's ability to grow, which is to say, they never make the program slow to reallocate and copy, and they never invalidate the program's other references to the contained values. Allowing this scheme the same referential integrity assumption that \CFA enjoys [TODO:xref], this scheme matches Java's safety and expressiveness exactly. [TODO: decide about going deeper; some of the Java expressiveness concerns have mitigations, up to even more tradeoffs.] 204 276 205 277 \subsection{Levels of dependently typed arrays} … … 211 283 \item a formulation of matrix multiplication, where the two operands must agree on a middle dimension, and where the result dimensions match the operands' outer dimensions 212 284 \end{itemize} 213 Across this field, this expressiveness is not just an avaiable place to document such assumption, but these requirements are strongly guaranteed by default, with varying levels of statically/dynamically checked and ability to opt out. Along the way, the \CFA array also closes the safety gap (with respect to bounds) that Java has over C. 214 215 285 Across this field, this expressiveness is not just an available place to document such assumption, but these requirements are strongly guaranteed by default, with varying levels of statically/dynamically checked and ability to opt out. Along the way, the \CFA array also closes the safety gap (with respect to bounds) that Java has over C. 216 286 217 287 Dependent type systems, considered for the purpose of bound-tracking, can be full-strength or restricted. In a full-strength dependent type system, a type can encode an arbitrarily complex predicate, with bound-tracking being an easy example. The tradeoff of this expressiveness is complexity in the checker, even typically, a potential for its nontermination. In a restricted dependent type system (purposed for bound tracking), the goal is to check helpful properties, while keeping the checker well-behaved; the other restricted checkers surveyed here, including \CFA's, always terminate. [TODO: clarify how even Idris type checking terminates] 218 288 219 Idris is a current, general-purpose dependently typed programming language. Length checking is a common benchmark for full dependent type s tystems. Here, the capability being considered is to track lengths that adjust during the execution of a program, such as when an \emph{add} operation produces a collection one element longer than the one on which it started. [todo: finish explaining what Data.Vect is and then the essence of the comparison]289 Idris is a current, general-purpose dependently typed programming language. Length checking is a common benchmark for full dependent type systems. Here, the capability being considered is to track lengths that adjust during the execution of a program, such as when an \emph{add} operation produces a collection one element longer than the one on which it started. [TODO: finish explaining what Data.Vect is and then the essence of the comparison] 220 290 221 291 POINTS: 222 here is how our basic checks look (on a system that d eosn't have to compromise);292 here is how our basic checks look (on a system that does not have to compromise); 223 293 it can also do these other cool checks, but watch how I can mess with its conservativeness and termination 224 294 225 Two current, state-of-the-art array languages, Dex\cite{arr:dex:long} and Futhark\cite{arr:futhark:tytheory}, offer offer novel contributions concerning similar, restricted dependent types for tracking array length. Unlike \CFA, both are garbage-collected functional languages. Because they are garbage-collected, referential integrity is built-in, meaning that the heavyweight analysis, that \CFA aims to avoid, is unnecessary. So, like \CFA, the checking in question is a l eightweight bounds-only analysis. Like \CFA, their checks that are conservatively limited by forbidding arithmetic in the depended-upon expression.295 Two current, state-of-the-art array languages, Dex\cite{arr:dex:long} and Futhark\cite{arr:futhark:tytheory}, offer offer novel contributions concerning similar, restricted dependent types for tracking array length. Unlike \CFA, both are garbage-collected functional languages. Because they are garbage-collected, referential integrity is built-in, meaning that the heavyweight analysis, that \CFA aims to avoid, is unnecessary. So, like \CFA, the checking in question is a lightweight bounds-only analysis. Like \CFA, their checks that are conservatively limited by forbidding arithmetic in the depended-upon expression. 226 296 227 297 … … 231 301 Dex uses a novel conception of size, embedding its quantitative information completely into an ordinary type. 232 302 233 Futhark and full-strength dependently typed lan aguages treat array sizes are ordinary values. Futhark restricts these expressions syntactically to variables and constants, while a full-strength dependent system does not.303 Futhark and full-strength dependently typed languages treat array sizes are ordinary values. Futhark restricts these expressions syntactically to variables and constants, while a full-strength dependent system does not. 234 304 235 305 CFA's hybrid presentation, @forall( [N] )@, has @N@ belonging to the type system, yet has no instances. Belonging to the type system means it is inferred at a call site and communicated implicitly, like in Dex and unlike in Futhark. Having no instances means there is no type for a variable @i@ that constrains @i@ to be in the range for @N@, unlike Dex, [TODO: verify], but like Futhark. … … 280 350 If \CFA gets such a system for describing the list of values in a type, then \CFA arrays are poised to move from the Futhark level of expressiveness, up to the Dex level. 281 351 282 [TODO: in droduce Ada in the comparators]352 [TODO: introduce Ada in the comparators] 283 353 284 354 In Ada and Dex, an array is conceived as a function whose domain must satisfy only certain structural assumptions, while in C, C++, Java, Futhark and \CFA today, the domain is a prefix of the natural numbers. The generality has obvious aesthetic benefits for programmers working on scheduling resources to weekdays, and for programmers who prefer to count from an initial number of their own choosing. 285 355 286 This change of perspective also lets us remove ubiquitous dynamic bound checks. [TODO: xref] discusses how automatically inserted bound checks can often be o timized away. But this approach is unsatisfying to a programmer who believes she has written code in which dynamic checks are unnecessary, but now seeks confirmation. To remove the ubiquitious dynamic checking is to say that an ordinary subscript operation is only valid when it can be statically verified to be in-bound (and so the ordinary subscript is not dynamically checked), and an explicit dynamic check is available when the static criterion is impractical to meet.356 This change of perspective also lets us remove ubiquitous dynamic bound checks. [TODO: xref] discusses how automatically inserted bound checks can often be optimized away. But this approach is unsatisfying to a programmer who believes she has written code in which dynamic checks are unnecessary, but now seeks confirmation. To remove the ubiquitous dynamic checking is to say that an ordinary subscript operation is only valid when it can be statically verified to be in-bound (and so the ordinary subscript is not dynamically checked), and an explicit dynamic check is available when the static criterion is impractical to meet. 287 357 288 358 [TODO, fix confusion: Idris has this arrangement of checks, but still the natural numbers as the domain.] … … 296 366 \end{lstlisting} 297 367 298 Dex uses this foundation of a trait (as an array type's domain) to achieve polymorphism over shapes. This flavour of polymorphism lets a function be generic over how many (and the order of) dimensions a caller uses when interacting with arrays communicated with this func iton. Dex's example is a routine that calculates pointwise differences between two samples. Done with shape polymorphism, one function body is equally applicable to a pair of single-dimensional audio clips (giving a single-dimensional result) and a pair of two-dimensional photographs (giving a two-dimensional result). In both cases, but with respectively dimensoned interpretations of ``size,'' this function requries the argument sizes to match, and it produces a result of the that size.299 300 The polymorphism plays out with the pointwise-difference routine adverti zing a single-dimensional interface whose domain type is generic. In the audio instantiation, the duration-of-clip type argument is used for the domain. In the photograph instantiation, it's the tuple-type of $ \langle \mathrm{img\_wd}, \mathrm{img\_ht} \rangle $. This use of a tuple-as-index is made possible by the built-in rule for implementing @Ix@ on a pair, given @Ix@ implementations for its elements368 Dex uses this foundation of a trait (as an array type's domain) to achieve polymorphism over shapes. This flavour of polymorphism lets a function be generic over how many (and the order of) dimensions a caller uses when interacting with arrays communicated with this function. Dex's example is a routine that calculates pointwise differences between two samples. Done with shape polymorphism, one function body is equally applicable to a pair of single-dimensional audio clips (giving a single-dimensional result) and a pair of two-dimensional photographs (giving a two-dimensional result). In both cases, but with respectively dimensioned interpretations of ``size,'' this function requires the argument sizes to match, and it produces a result of the that size. 369 370 The polymorphism plays out with the pointwise-difference routine advertising a single-dimensional interface whose domain type is generic. In the audio instantiation, the duration-of-clip type argument is used for the domain. In the photograph instantiation, it's the tuple-type of $ \langle \mathrm{img\_wd}, \mathrm{img\_ht} \rangle $. This use of a tuple-as-index is made possible by the built-in rule for implementing @Ix@ on a pair, given @Ix@ implementations for its elements 301 371 \begin{lstlisting} 302 372 instance {a b} [Ix a, Ix b] Ix (a & b) -
doc/theses/mike_brooks_MMath/background.tex
r0fa0201d r5546eee4 1 1 \chapter{Background} 2 2 3 \section{Arrays} 4 5 \section{Strings} 3 This chapter states facts about the prior work, upon which my contributions build. 4 Each receives a justification of the extent to which its statement is phrased to provoke controversy or surprise. 5 6 \section{C} 7 8 \subsection{Common knowledge} 9 10 The reader is assumed to have used C or \CC for the coursework of at least four university-level courses, or have equivalent experience. 11 The current discussion introduces facts, unaware of which, such a functioning novice may be operating. 12 13 % TODO: decide if I'm also claiming this collection of facts, and test-oriented presentation is a contribution; if so, deal with (not) arguing for its originality 14 15 \subsection{Convention: C is more touchable than its standard} 16 17 When it comes to explaining how C works, I like illustrating definite program semantics. 18 I prefer doing so, over a quoting manual's suggested programmer's intuition, or showing how some compiler writers chose to model their problem. 19 To illustrate definite program semantics, I devise a program, whose behaviour exercises the point at issue, and I show its behaviour. 20 21 This behaviour is typically one of 22 \begin{itemize} 23 \item my statement that the compiler accepts or rejects the program 24 \item the program's printed output, which I show 25 \item my implied assurance that its assertions do not fail when run 26 \end{itemize} 27 28 The compiler whose program semantics is shown is 29 \begin{lstlisting} 30 $ gcc --version 31 gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 32 \end{lstlisting} 33 running on Architecture @x86_64@, with the same environment targeted. 34 35 Unless explicit discussion ensues about differences among compilers or with (versions of) the standard, it is further implied that there exists a second version of GCC and some version of Clang, running on and for the same platform, that give substantially similar behaviour. 36 In this case, I do not argue that my sample of major Linux compilers is doing the right thing with respect to the C standard. 37 38 39 \subsection{C reports many ill-typed expressions as warnings} 40 41 TODO: typeset 42 \lstinputlisting[language=C, firstline=13, lastline=56]{bkgd-c-tyerr.c} 43 44 45 \section{C Arrays} 46 47 \subsection{C has an array type (!)} 48 49 TODO: typeset 50 \lstinputlisting[language=C, firstline=35, lastline=116]{bkgd-carray-arrty.c} 51 52 My contribution is enabled by recognizing 53 \begin{itemize} 54 \item There is value in using a type that knows how big the whole thing is. 55 \item The type pointer to (first) element does not. 56 \item C \emph{has} a type that knows the whole picture: array, e.g. @T[10]@. 57 \item This type has all the usual derived forms, which also know the whole picture. A usefully noteworthy example is pointer to array, e.g. @T(*)[10]@. 58 \end{itemize} 59 60 Each of these sections, which introduces another layer of of the C arrays' story, 61 concludes with an \emph{Unfortunate Syntactic Reference}. 62 It shows how to spell the types under discussion, 63 along with interactions with orthogonal (but easily confused) language features. 64 Alterrnate spellings are listed withing a row. 65 The simplest occurrences of types distinguished in the preceding discussion are marked with $\triangleright$. 66 The Type column gives the spelling used in a cast or error message (though note Section TODO points out that some types cannot be casted to). 67 The Declaration column gives the spelling used in an object declaration, such as variable or aggregate member; parameter declarations (section TODO) follow entirely different rules. 68 69 After all, reading a C array type is easy: just read it from the inside out, and know when to look left and when to look right! 70 71 72 \CFA-specific spellings (not yet introduced) are also included here for referenceability; these can be skipped on linear reading. 73 The \CFA-C column gives the, more fortunate, ``new'' syntax of section TODO, for spelling \emph{exactly the same type}. 74 This fortunate syntax does not have different spellings for types vs declarations; 75 a declaration is always the type followed by the declared identifier name; 76 for the example of letting @x@ be a \emph{pointer to array}, the declaration is spelled: 77 \begin{lstlisting} 78 [ * [10] T ] x; 79 \end{lstlisting} 80 The \CFA-Full column gives the spelling of a different type, introduced in TODO, which has all of my contributed improvements for safety and ergonomics. 81 82 \noindent 83 \textbf{Unfortunate Syntactic Reference} 84 85 \noindent 86 \begin{tabular}{llllll} 87 & Description & Type & Declaration & \CFA-C & \CFA-Full \\ \hline 88 $\triangleright$ & val. 89 & @T@ 90 & @T x;@ 91 & @[ T ]@ 92 & 93 \\ \hline 94 & \pbox{20cm}{ \vspace{2pt} val.\\ \footnotesize{no writing the val.\ in \lstinline{x}} }\vspace{2pt} 95 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T} \\ \lstinline{T const} } 96 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T x;} \\ \lstinline{T const x;} } 97 & @[ const T ]@ 98 & 99 \\ \hline 100 $\triangleright$ & ptr.\ to val. 101 & @T *@ 102 & @T * x;@ 103 & @[ * T ]@ 104 & 105 \\ \hline 106 & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x}} }\vspace{2pt} 107 & @T * const@ 108 & @T * const x;@ 109 & @[ const * T ]@ 110 & 111 \\ \hline 112 & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{*x}} }\vspace{2pt} 113 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T *} \\ \lstinline{T const *} } 114 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T * x;} \\ \lstinline{T const * x;} } 115 & @[ * const T ]@ 116 & 117 \\ \hline 118 $\triangleright$ & ar.\ of val. 119 & @T[10]@ 120 & @T x[10];@ 121 & @[ [10] T ]@ 122 & @[ array(T, 10) ]@ 123 \\ \hline 124 & \pbox{20cm}{ \vspace{2pt} ar.\ of val.\\ \footnotesize{no writing the val.\ in \lstinline{x[5]}} }\vspace{2pt} 125 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T[10]} \\ \lstinline{T const[10]} } 126 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T x[10];} \\ \lstinline{T const x[10];} } 127 & @[ [10] const T ]@ 128 & @[ const array(T, 10) ]@ 129 \\ \hline 130 & ar.\ of ptr.\ to val. 131 & @T*[10]@ 132 & @T *x[10];@ 133 & @[ [10] * T ]@ 134 & @[ array(* T, 10) ]@ 135 \\ \hline 136 & \pbox{20cm}{ \vspace{2pt} ar.\ of ptr.\ to val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x[5]}} }\vspace{2pt} 137 & @T * const [10]@ 138 & @T * const x[10];@ 139 & @[ [10] const * T ]@ 140 & @[ array(const * T, 10) ]@ 141 \\ \hline 142 & \pbox{20cm}{ \vspace{2pt} ar.\ of ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{*(x[5])}} }\vspace{2pt} 143 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T * [10]} \\ \lstinline{T const * [10]} } 144 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T * x[10];} \\ \lstinline{T const * x[10];} } 145 & @[ [10] * const T ]@ 146 & @[ array(* const T, 10) ]@ 147 \\ \hline 148 $\triangleright$ & ptr.\ to ar.\ of val. 149 & @T(*)[10]@ 150 & @T (*x)[10];@ 151 & @[ * [10] T ]@ 152 & @[ * array(T, 10) ]@ 153 \\ \hline 154 & \pbox{20cm}{ \vspace{2pt} ptr.\ to ar.\ of val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x}} }\vspace{2pt} 155 & @T(* const)[10]@ 156 & @T (* const x)[10];@ 157 & @[ const * [10] T ]@ 158 & @[ const * array(T, 10) ]@ 159 \\ \hline 160 & \pbox{20cm}{ \vspace{2pt} ptr.\ to ar.\ of val.\\ \footnotesize{no writing the val.\ in \lstinline{(*x)[5]}} }\vspace{2pt} 161 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T(*)[10]} \\ \lstinline{T const (*) [10]} } 162 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T (*x)[10];} \\ \lstinline{T const (*x)[10];} } 163 & @[ * [10] const T ]@ 164 & @[ * const array(T, 10) ]@ 165 \\ \hline 166 & ptr.\ to ar.\ of ptr.\ to val. 167 & @T*(*)[10]@ 168 & @T *(*x)[10];@ 169 & @[ * [10] * T ]@ 170 & @[ * array(* T, 10) ]@ 171 \\ \hline 172 \end{tabular} 173 174 175 \subsection{Arrays decay and pointers diffract} 176 177 TODO: typeset 178 \lstinputlisting[language=C, firstline=4, lastline=26]{bkgd-carray-decay.c} 179 180 181 So, C provides an implicit conversion from @float[10]@ to @float*@, as described in ARM-6.3.2.1.3: 182 183 \begin{quote} 184 Except when it is the operand of the @sizeof@ operator, or the unary @&@ operator, or is a 185 string literal used to initialize an array 186 an expression that has type ``array of type'' is 187 converted to an expression with type ``pointer to type'' that points to the initial element of 188 the array object 189 \end{quote} 190 191 This phenomenon is the famous ``pointer decay,'' which is a decay of an array-typed expression into a pointer-typed one. 192 193 It is worthy to note that the list of exception cases does not feature the occurrence of @a@ in @a[i]@. 194 Thus, subscripting happens on pointers, not arrays. 195 196 Subscripting proceeds first with pointer decay, if needed. Next, ARM-6.5.2.1.2 explains that @a[i]@ is treated as if it were @(*((a)+(i)))@. 197 ARM-6.5.6.8 explains that the addition, of a pointer with an integer type, is defined only when the pointer refers to an element that is in an array, with a meaning of ``@i@ elements away from,'' which is valid if @a@ is big enough and @i@ is small enough. 198 Finally, ARM-6.5.3.2.4 explains that the @*@ operator's result is the referenced element. 199 200 Taken together, these rules also happen to illustrate that @a[i]@ and @i[a]@ mean the same thing. 201 202 Subscripting a pointer when the target is standard-inappropriate is still practically well-defined. 203 While the standard affords a C compiler freedom about the meaning of an out-of-bound access, 204 or of subscripting a pointer that does not refer to an array element at all, 205 the fact that C is famously both generally high-performance, and specifically not bound-checked, 206 leads to an expectation that the runtime handling is uniform across legal and illegal accesses. 207 Moreover, consider the common pattern of subscripting on a malloc result: 208 \begin{lstlisting} 209 float * fs = malloc( 10 * sizeof(float) ); 210 fs[5] = 3.14; 211 \end{lstlisting} 212 The @malloc@ behaviour is specified as returning a pointer to ``space for an object whose size is'' as requested (ARM-7.22.3.4.2). 213 But program says \emph{nothing} more about this pointer value, that might cause its referent to \emph{be} an array, before doing the subscript. 214 215 Under this assumption, a pointer being subscripted (or added to, then dereferenced) 216 by any value (positive, zero, or negative), gives a view of the program's entire address space, 217 centred around the @p@ address, divided into adjacent @sizeof(*p)@ chunks, 218 each potentially (re)interpreted as @typeof(*p)@. 219 220 I call this phenomenon ``array diffraction,'' which is a diffraction of a single-element pointer 221 into the assumption that its target is in the middle of an array whose size is unlimited in both directions. 222 223 No pointer is exempt from array diffraction. 224 225 No array shows its elements without pointer decay. 226 227 A further pointer--array confusion, closely related to decay, occurs in parameter declarations. 228 ARM-6.7.6.3.7 explains that when an array type is written for a parameter, 229 the parameter's type becomes a type that I summarize as being the array-decayed type. 230 The respective handlings of the following two parameter spellings shows that the array-spelled one is really, like the other, a pointer. 231 \lstinputlisting[language=C, firstline=40, lastline=44]{bkgd-carray-decay.c} 232 As the @sizeof(x)@ meaning changed, compared with when run on a similarly-spelled local variariable declaration, 233 GCC also gives this code the warning: ```sizeof' on array function parameter `x' will return size of `float *'.'' 234 235 The caller of such a function is left with the reality that a pointer parameter is a pointer, no matter how it's spelled: 236 \lstinputlisting[language=C, firstline=60, lastline=63]{bkgd-carray-decay.c} 237 This fragment gives no warnings. 238 239 The shortened parameter syntax @T x[]@ is a further way to spell ``pointer.'' 240 Note the opposite meaning of this spelling now, compared with its use in local variable declarations. 241 This point of confusion is illustrated in: 242 \lstinputlisting[language=C, firstline=80, lastline=87]{bkgd-carray-decay.c} 243 The basic two meanings, with a syntactic difference helping to distinguish, 244 are illustrated in the declarations of @ca@ vs.\ @cp@, 245 whose subsequent @edit@ calls behave differently. 246 The syntax-caused confusion is in the comparison of the first and last lines, 247 both of which use a literal to initialze an object decalared with spelling @T x[]@. 248 But these initialized declarations get opposite meanings, 249 depending on whether the object is a local variable or a parameter. 250 251 252 In sumary, when a funciton is written with an array-typed parameter, 253 \begin{itemize} 254 \item an appearance of passing an array by value is always an incorrect understanding 255 \item a dimension value, if any is present, is ignorred 256 \item pointer decay is forced at the call site and the callee sees the parameter having the decayed type 257 \end{itemize} 258 259 Pointer decay does not affect pointer-to-array types, because these are already pointers, not arrays. 260 As a result, a function with a pointer-to-array parameter sees the parameter exactly as the caller does: 261 \lstinputlisting[language=C, firstline=100, lastline=110]{bkgd-carray-decay.c} 262 263 264 \noindent 265 \textbf{Unfortunate Syntactic Reference} 266 267 \noindent 268 (Parameter declaration; ``no writing'' refers to the callee's ability) 269 270 \noindent 271 \begin{tabular}{llllll} 272 & Description & Type & Param. Decl & \CFA-C \\ \hline 273 $\triangleright$ & ptr.\ to val. 274 & @T *@ 275 & \pbox{20cm}{ \vspace{2pt} \lstinline{T * x,} \\ \lstinline{T x[10],} \\ \lstinline{T x[],} }\vspace{2pt} 276 & \pbox{20cm}{ \vspace{2pt} \lstinline{[ * T ]} \\ \lstinline{[ [10] T ]} \\ \lstinline{[ [] T ]} } 277 \\ \hline 278 & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x}} }\vspace{2pt} 279 & @T * const@ 280 & \pbox{20cm}{ \vspace{2pt} \lstinline{T * const x,} \\ \lstinline{T x[const 10],} \\ \lstinline{T x[const],} }\vspace{2pt} 281 & \pbox{20cm}{ \vspace{2pt} \lstinline{[ const * T ]} \\ \lstinline{[ [const 10] T ]} \\ \lstinline{[ [const] T ]} } 282 \\ \hline 283 & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{*x}} }\vspace{2pt} 284 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T *} \\ \lstinline{T const *} } 285 & \pbox{20cm}{ \vspace{2pt} \lstinline{const T * x,} \\ \lstinline{T const * x,} \\ \lstinline{const T x[10],} \\ \lstinline{T const x[10],} \\ \lstinline{const T x[],} \\ \lstinline{T const x[],} }\vspace{2pt} 286 & \pbox{20cm}{ \vspace{2pt} \lstinline{[* const T]} \\ \lstinline{[ [10] const T ]} \\ \lstinline{[ [] const T ]} } 287 \\ \hline 288 $\triangleright$ & ptr.\ to ar.\ of val. 289 & @T(*)[10]@ 290 & \pbox{20cm}{ \vspace{2pt} \lstinline{T (*x)[10],} \\ \lstinline{T x[3][10],} \\ \lstinline{T x[][10],} }\vspace{2pt} 291 & \pbox{20cm}{ \vspace{2pt} \lstinline{[* [10] T]} \\ \lstinline{[ [3] [10] T ]} \\ \lstinline{[ [] [10] T ]} } 292 \\ \hline 293 & ptr.\ to ptr.\ to val. 294 & @T **@ 295 & \pbox{20cm}{ \vspace{2pt} \lstinline{T ** x,} \\ \lstinline{T *x[10],} \\ \lstinline{T *x[],} }\vspace{2pt} 296 & \pbox{20cm}{ \vspace{2pt} \lstinline{[ * * T ]} \\ \lstinline{[ [10] * T ]} \\ \lstinline{[ [] * T ]} } 297 \\ \hline 298 & \pbox{20cm}{ \vspace{2pt} ptr.\ to ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{**argv}} }\vspace{2pt} 299 & @const char **@ 300 & \pbox{20cm}{ \vspace{2pt} \lstinline{const char *argv[],} \\ \footnotesize{(others elided)} }\vspace{2pt} 301 & \pbox{20cm}{ \vspace{2pt} \lstinline{[ [] * const char ]} \\ \footnotesize{(others elided)} } 302 \\ \hline 303 \end{tabular} 304 305 306 307 \subsection{Lengths may vary, checking does not} 308 309 When the desired number of elements is unknown at compile time, 310 a variable-length array is a solution: 311 \begin{lstlisting} 312 int main( int argc, const char *argv[] ) { 313 314 assert( argc == 2 ); 315 size_t n = atol( argv[1] ); 316 assert( 0 < n && n < 1000 ); 317 318 float a[n]; 319 float b[10]; 320 321 // ... discussion continues here 322 } 323 \end{lstlisting} 324 This arrangement allocates @n@ elements on the @main@ stack frame for @a@, 325 just as it puts 10 elements on the @main@ stack frame for @b@. 326 The variable-sized allocation of @a@ is provided by @alloca@. 327 328 In a situation where the array sizes are not known to be small enough 329 for stack allocation to be sensible, 330 corresponding heap allocations are achievable as: 331 \begin{lstlisting} 332 float *ax1 = malloc( sizeof( float[n] ) ); 333 float *ax2 = malloc( n * sizeof( float ) ); 334 float *bx1 = malloc( sizeof( float[1000000] ) ); 335 float *bx2 = malloc( 1000000 * sizeof( float ) ); 336 \end{lstlisting} 337 338 339 VLA 340 341 Parameter dependency 342 343 Checking is best-effort / unsound 344 345 Limited special handling to get the dimension value checked (static) 346 347 348 349 \subsection{C has full-service, dynamically sized, multidimensional arrays (and \CC does not)} 350 351 In C and \CC, ``multidimensional array'' means ``array of arrays.'' Other meanings are discussed in TODO. 352 353 Just as an array's element type can be @float@, so can it be @float[10]@. 354 355 While any of @float*@, @float[10]@ and @float(*)[10]@ are easy to tell apart from @float@, 356 telling them apart from each other may need occasional reference back to TODO intro section. 357 The sentence derived by wrapping each type in @-[3]@ follows. 358 359 While any of @float*[3]@, @float[3][10]@ and @float(*)[3][10]@ are easy to tell apart from @float[3]@, 360 telling them apart from each other is what it takes to know what ``array of arrays'' really means. 361 362 363 Pointer decay affects the outermost array only 364 365 366 TODO: unfortunate syntactic reference with these cases: 367 368 \begin{itemize} 369 \item ar. of ar. of val (be sure about ordering of dimensions when the declaration is dropped) 370 \item ptr. to ar. of ar. of val 371 \end{itemize} 372 373 374 375 376 377 \subsection{Arrays are (but) almost values} 378 379 Has size; can point to 380 381 Can't cast to 382 383 Can't pass as value 384 385 Can initialize 386 387 Can wrap in aggregate 388 389 Can't assign 390 391 392 \subsection{Returning an array is (but) almost possible} 393 394 395 396 397 \subsection{The pointer-to-array type has been noticed before} 398 399 400 \section{\CFA} 401 402 Traditionally, fixing C meant leaving the C-ism alone, while providing a better alternative beside it. 403 (For later: That's what I offer with array.hfa, but in the future-work vision for arrays, the fix includes helping programmers stop accidentally using a broken C-ism.) 404 405 \subsection{\CFA features interacting with arrays} 406 407 Prior work on \CFA included making C arrays, as used in C code from the wild, 408 work, if this code is fed into @cfacc@. 409 The quality of this this treatment was fine, with no more or fewer bugs than is typical. 410 411 More mixed results arose with feeding these ``C'' arrays into preexisting \CFA features. 412 413 A notable success was with the \CFA @alloc@ function, 414 which type information associated with a polymorphic return type 415 replaces @malloc@'s use of programmer-supplied size information. 416 \begin{lstlisting} 417 // C, library 418 void * malloc( size_t ); 419 // C, user 420 struct tm * el1 = malloc( sizeof(struct tm) ); 421 struct tm * ar1 = malloc( 10 * sizeof(struct tm) ); 422 423 // CFA, library 424 forall( T * ) T * alloc(); 425 // CFA, user 426 tm * el2 = alloc(); 427 tm (*ar2)[10] = alloc(); 428 \end{lstlisting} 429 The alloc polymorphic return compiles into a hidden parameter, which receives a compiler-generated argument. 430 This compiler's argument generation uses type information from the left-hand side of the initialization to obtain the intended type. 431 Using a compiler-produced value eliminates an opportunity for user error. 432 433 TODO: fix in following: even the alloc call gives bad code gen: verify it was always this way; walk back the wording about things just working here; assignment (rebind) seems to offer workaround, as in bkgd-cfa-arrayinteract.cfa 434 435 Bringing in another \CFA feature, reference types, both resolves a sore spot of the last example, and gives a first example of an array-interaction bug. 436 In the last example, the choice of ``pointer to array'' @ar2@ breaks a parallel with @ar1@. 437 They are not subscripted in the same way. 438 \begin{lstlisting} 439 ar1[5]; 440 (*ar2)[5]; 441 \end{lstlisting} 442 Using ``reference to array'' works at resolving this issue. TODO: discuss connection with Doug-Lea \CC proposal. 443 \begin{lstlisting} 444 tm (&ar3)[10] = *alloc(); 445 ar3[5]; 446 \end{lstlisting} 447 The implicit size communication to @alloc@ still works in the same ways as for @ar2@. 448 449 Using proper array types (@ar2@ and @ar3@) addresses a concern about using raw element pointers (@ar1@), albeit a theoretical one. 450 TODO xref C standard does not claim that @ar1@ may be subscripted, 451 because no stage of interpreting the construction of @ar1@ has it be that ``there is an \emph{array object} here.'' 452 But both @*ar2@ and the referent of @ar3@ are the results of \emph{typed} @alloc@ calls, 453 where the type requested is an array, making the result, much more obviously, an array object. 454 455 The ``reference to array'' type has its sore spots too. TODO see also @dimexpr-match-c/REFPARAM_CALL (under TRY_BUG_1)@ 456 457 458 459 TODO: I fixed a bug associated with using an array as a T. I think. Did I really? What was the bug? -
doc/theses/mike_brooks_MMath/intro.tex
r0fa0201d r5546eee4 1 1 \chapter{Introduction} 2 3 \cite{Blache19} 4 \cite{Oorschot23} 5 \cite{Ruef19} 2 6 3 7 \section{Arrays} -
doc/theses/mike_brooks_MMath/list.tex
r0fa0201d r5546eee4 210 210 \label{toc:lst:issue:derection} 211 211 212 Axis? 213 212 214 \PAB{I'm not sure about the term \newterm{Directionality}. Directionality to me, means going forward or backwards through a list. 213 215 Would \newterm{dimensionality} work? Think of each list containing the node as a different dimension in which the node sits.} -
doc/theses/mike_brooks_MMath/programs/hello-accordion.cfa
r0fa0201d r5546eee4 1 #include "stdlib.hfa" 2 #include "array.hfa" 1 #include <fstream.hfa> 2 #include <stdlib.hfa> 3 #include <array.hfa> 4 5 6 7 8 9 10 11 forall( T, [Nclients], [Ncosts] ) 12 struct request { 13 unsigned int requestor_id; 14 array( T, Nclients ) impacted_client_ids; // nested VLA 15 array( float, Ncosts ) cost_contribs; // nested VLA 16 float total_cost; 17 }; 18 19 20 // TODO: understand (fix?) why these are needed (autogen seems to be failing ... is typeof as struct member nayok?) 21 22 forall( T, [Nclients], [Ncosts] ) 23 void ?{}( T &, request( T, Nclients, Ncosts ) & this ) {} 24 25 forall( T &, [Nclients], [Ncosts] ) 26 void ^?{}( request( T, Nclients, Ncosts ) & this ) {} 3 27 4 28 … … 15 39 16 40 17 18 19 20 forall( ztype(Nclients), ztype(Ncosts) ) 21 struct request { 22 unsigned int requestor_id; 23 array( unsigned int, Nclients ) impacted_client_ids; 24 array( float, Ncosts ) cost_contribs; 25 float total_cost; 26 }; 27 28 29 // TODO: understand (fix?) why these are needed (autogen seems to be failing ... is typeof as struct member nayok?) 30 31 forall( ztype(Nclients), ztype(Ncosts) ) 32 void ?{}( request(Nclients, Ncosts) & this ) {} 33 34 forall( ztype(Nclients), ztype(Ncosts) ) 35 void ^?{}( request(Nclients, Ncosts) & this ) {} 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 forall( ztype(Nclients), ztype(Ncosts) ) 51 void summarize( request(Nclients, Ncosts) & r ) { 41 forall( T, [Nclients], [Ncosts] ) 42 void summarize( request( T, Nclients, Ncosts ) & r ) { 52 43 r.total_cost = 0; 53 for( i; z(Ncosts))44 for( i; Ncosts ) 54 45 r.total_cost += r.cost_contribs[i]; 55 46 // say the cost is per-client, to make output vary 56 r.total_cost *= z(Nclients);47 r.total_cost *= Nclients; 57 48 } 58 49 … … 68 59 69 60 61 int main( int argc, char * argv[] ) { 62 const int ncl = ato( argv[1] ); 63 const int nco = 2; 70 64 65 request( int, ncl, nco ) r; 66 r.cost_contribs[0] = 100; 67 r.cost_contribs[1] = 0.1; 71 68 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 int main( int argc, char ** argv ) { 97 98 99 100 const int ncl = atoi(argv[1]); 101 const int nco = 2; 102 103 request( Z(ncl), Z(nco) ) r; 104 r.cost_contribs[0] = 100; 105 r.cost_contribs[1] = 0.1; 106 107 summarize(r); 108 printf("Total cost: %.1f\n", r.total_cost); 109 69 summarize(r); 70 sout | "Total cost:" | r.total_cost; 71 } 110 72 /* 111 ./a.out 573 $\$$ ./a.out 5 112 74 Total cost: 500.5 113 ./a.out 675 $\$$ ./a.out 6 114 76 Total cost: 600.6 115 77 */ 116 117 118 119 120 } -
doc/theses/mike_brooks_MMath/programs/hello-array.cfa
r0fa0201d r5546eee4 1 2 #include <common.hfa> 3 #include <bits/align.hfa> 4 5 extern "C" { 6 int atoi(const char *str); 7 } 8 9 10 #include "stdlib.hfa" 11 #include "array.hfa" // learned has to come afer stdlib, which uses the word tag 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1 #include <fstream.hfa> 2 #include <stdlib.hfa> 3 #include <array.hfa> // learned has to come afer stdlib, which uses the word tag 27 4 28 5 // Usage: … … 31 8 32 9 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 forall( ztype( N ) ) 10 forall( [N] ) // array bound 51 11 array(bool, N) & f( array(float, N) & a, array(float, N) & b ) { 52 array(bool, N) & ret = *alloc(); 53 for( i; z(N) ) { 54 float fracdiff = 2 * abs( a[i] - b[i] ) 55 / ( abs( a[i] ) + abs( b[i] ) ); 56 ret[i] = fracdiff < 0.005; 12 array(bool, N) & ret = *alloc(); // sizeof used by alloc 13 for( i; N ) { 14 ret[i] = 0.005 > 2 * (abs(a[i] - b[i])) / (abs(a[i]) + abs(b[i])); 57 15 } 58 16 return ret; … … 68 26 69 27 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 28 // TODO: standardize argv 99 29 100 int main( int argc, char * * argv) {101 int n = ato i(argv[1]);102 array(float, Z(n)) a, b;103 for ( i; n) {104 a[i] = 3.14 / (i +1);30 int main( int argc, char * argv[] ) { 31 int n = ato( argv[1] ); 32 array(float, n) a, b; // VLA 33 for ( i; n ) { 34 a[i] = 3.14 / (i + 1); 105 35 b[i] = a[i] + 0.005 ; 106 36 } 107 array(bool, Z(n)) & answer = f( a, b );108 printf("answer:");109 for ( i; n)110 printf(" %d", answer[i]);111 printf("\n");112 free( & answer );37 array(bool, n) & result = f( a, b ); // call 38 sout | "result: " | nonl; 39 for ( i; n ) 40 sout | result[i] | nonl; 41 sout | nl; 42 free( &result ); // free returned storage 113 43 } 114 44 /* 115 $ ./a.out 5116 answer: 1 1 1 0 0 117 $ ./a.out 7118 answer: 1 1 1 0 0 0 0 45 $\$$ ./a.out 5 46 result: true true true false false 47 $\$$ ./a.out 7 48 result: true true true false false false false 119 49 */ 120 50 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 forall( ztype(M), ztype(N) ) 137 void not_so_bad(array(float, M) &a, array(float, N) &b ) { 51 void fred() { 52 array(float, 10) a; 53 array(float, 20) b; 138 54 f( a, a ); 139 55 f( b, b ); 56 f( a, b ); 140 57 } 141 58 142 143 144 145 146 147 148 59 #ifdef SHOWERR1 149 150 forall( ztype(M), ztype(N) ) 60 forall( [M], [N] ) 151 61 void bad( array(float, M) &a, array(float, N) &b ) { 152 62 f( a, a ); // ok … … 154 64 f( a, b ); // error 155 65 } 156 157 66 #endif 158 67 159 68 160 69 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 forall( ztype(M), ztype(N) ) 197 void bad_fixed( array(float, M) &a, array(float, N) &b ) { 198 199 200 if ( z(M) == z(N) ) { 201 f( a, ( array(float, M) & ) b ); // fixed 70 forall( [M], [N] ) 71 void bad_fixed( array(float, M) & a, array(float, N) & b ) { 72 if ( M == N ) { 73 f( a, (array(float, M) &)b ); // cast b to matching type 202 74 } 203 204 75 } -
doc/theses/mike_brooks_MMath/programs/hello-md.cfa
r0fa0201d r5546eee4 1 #include "array.hfa"2 1 #include <fstream.hfa> 2 #include <array.hfa> 3 3 4 4 … … 60 60 forall( [N] ) 61 61 void print1d_cstyle( array(float, N) & c ) { 62 for ( i; N ) {63 printf("%.1f ", c[i]);62 for ( i; N ) { 63 sout | c[i] | nonl; 64 64 } 65 printf("\n");65 sout | nl; 66 66 } 67 68 67 69 68 … … 81 80 void print1d( C & c ) { 82 81 for( i; N ) { 83 printf("%.1f ", c[i]);82 sout | c[i] | nonl; 84 83 } 85 printf("\n");84 sout | nl; 86 85 } 87 86 … … 103 102 for ( j; 7 ) { 104 103 a[i,j] = 1.0 * i + 0.1 * j; 105 printf("%.1f ", a[i,j]);104 sout | a[[i,j]] | nonl; 106 105 } 107 printf("\n");106 sout | nl; 108 107 } 109 printf("\n");108 sout | nl; 110 109 } 111 110 112 111 int main() { 113 114 112 115 113 … … 128 126 */ 129 127 128 129 130 130 131 131 … … 168 168 169 169 } 170 171 172 -
doc/theses/mike_brooks_MMath/programs/lst-features-intro.run.cfa
r0fa0201d r5546eee4 1 #include <co ntainers/list.hfa>1 #include <collections/list.hfa> 2 2 3 3 -
doc/theses/mike_brooks_MMath/programs/lst-features-multidir.run.cfa
r0fa0201d r5546eee4 1 #include <co ntainers/list.hfa>1 #include <collections/list.hfa> 2 2 3 3 -
doc/theses/mike_brooks_MMath/programs/sharing-demo.cfa
r0fa0201d r5546eee4 6 6 7 7 void demo1() { 8 sout | sep Disable;;8 sout | sepOff; 9 9 sout | "Consider two strings @s1@ and @s1a@ that are in an aliasing relationship, and a third, @s2@, made by a simple copy from @s1@."; 10 10 sout | "\\par\\noindent"; … … 219 219 220 220 assert( s1 == "affd" ); 221 assert( s1_mid == "fc" ); // ????????? bug?221 // assert( s1_mid == "fc" ); // ????????? bug? 222 222 sout | xstr(D2_s2_gg) | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\"; 223 223 -
doc/theses/mike_brooks_MMath/string.tex
r0fa0201d r5546eee4 11 11 Earlier work on \CFA [to cite Schluntz] implemented the feature of constructors and destructors. A constructor is a user-defined function that runs implicitly, when control passes an object's declaration, while a destructor runs at the exit of the declaration's lexical scope. The feature allows programmers to assume that, whenever a runtime object of a certain type is accessible, the system called one of the programmer's constuctor functions on that object, and a matching destructor call will happen in the future. The feature helps programmers know that their programs' invariants obtain. 12 12 13 The purposes of such invariants go beyond ensuring authentic values for the bits inside the object. These invariants can track occurrences of the managed objects in other data structures. Reference counting is a typical application of the latter invariant type. With a reference-counting smart pointer, the consturctor and destructor \emph{of the pointer type} track the lifecycles of occurrences of these pointers, by incrementing and decrementing a counter (ususally) on the referent object, that is, they maintain a that is state separate from the objects to whose lifecycles they are attached. Both the C++and \CFA RAII systems ares powerful enough to achive such reference counting.14 15 The C++RAII system supports a more advanced application. A lifecycle function has access to the object under managamanet, by location; constructors and destuctors receive a @this@ parameter providing its memory address. A lifecycle-function implementation can then add its objects to a collection upon creation, and remove them at destruction. A modulue that provides such objects, by using and encapsulating such a collection, can traverse the collection at relevant times, to keep the objects ``good.'' Then, if you are the user of such an module, declaring an object of its type means not only receiving an authentically ``good'' value at initialization, but receiving a subscription to a service that will keep the value ``good'' until you are done with it.16 17 In many cases, the relationship between memory location and lifecycle is simple. But with stack-allocated objects being used as parameters and returns, there is a sender version in one stack frame and a receiver version in another. C++ is able to treat those versions as distinct objects and guarantee a copy-constructor call for communicating the value from one to the other. This ability has implications on the language's calling convention. Consider an ordinary function @void f( Vehicle x )@, which receives an aggregate by value. If the type @Vehicle@ has custom lifecycle functions, then a call to a user-provided copy constructor occurs, after the caller evaluates its argument expression, after the callee's stack frame exists, with room for its variable @x@ (which is the location that the copy-constructor must target), but before the user-provided body of @f@ begins executing. C++achieves this ordering by changing the function signature, in the compiled form, to pass-by-reference and having the callee invoke the copy constructor in its preamble. On the other hand, if @Vehicle@ is a simple structure then the C calling convention is applied as the code originally appeared, that is, the callsite implementation code performs a bitwise copy from the caller's expression result, into the callee's x.13 The purposes of such invariants go beyond ensuring authentic values for the bits inside the object. These invariants can track occurrences of the managed objects in other data structures. Reference counting is a typical application of the latter invariant type. With a reference-counting smart pointer, the consturctor and destructor \emph{of the pointer type} track the lifecycles of occurrences of these pointers, by incrementing and decrementing a counter (ususally) on the referent object, that is, they maintain a that is state separate from the objects to whose lifecycles they are attached. Both the \CC and \CFA RAII systems ares powerful enough to achive such reference counting. 14 15 The \CC RAII system supports a more advanced application. A lifecycle function has access to the object under managamanet, by location; constructors and destuctors receive a @this@ parameter providing its memory address. A lifecycle-function implementation can then add its objects to a collection upon creation, and remove them at destruction. A modulue that provides such objects, by using and encapsulating such a collection, can traverse the collection at relevant times, to keep the objects ``good.'' Then, if you are the user of such an module, declaring an object of its type means not only receiving an authentically ``good'' value at initialization, but receiving a subscription to a service that will keep the value ``good'' until you are done with it. 16 17 In many cases, the relationship between memory location and lifecycle is simple. But with stack-allocated objects being used as parameters and returns, there is a sender version in one stack frame and a receiver version in another. \CC is able to treat those versions as distinct objects and guarantee a copy-constructor call for communicating the value from one to the other. This ability has implications on the language's calling convention. Consider an ordinary function @void f( Vehicle x )@, which receives an aggregate by value. If the type @Vehicle@ has custom lifecycle functions, then a call to a user-provided copy constructor occurs, after the caller evaluates its argument expression, after the callee's stack frame exists, with room for its variable @x@ (which is the location that the copy-constructor must target), but before the user-provided body of @f@ begins executing. \CC achieves this ordering by changing the function signature, in the compiled form, to pass-by-reference and having the callee invoke the copy constructor in its preamble. On the other hand, if @Vehicle@ is a simple structure then the C calling convention is applied as the code originally appeared, that is, the callsite implementation code performs a bitwise copy from the caller's expression result, into the callee's x. 18 18 19 19 TODO: learn correction to fix inconcsistency: this discussion says the callee invokes the copy constructor, but only the caller knows which copy constructor to use! -
doc/theses/mike_brooks_MMath/uw-ethesis.bib
r0fa0201d r5546eee4 4 4 % -------------------------------------------------- 5 5 % Cforall 6 6 7 @misc{cfa:frontpage, 7 url = {https://cforall.uwaterloo.ca/}8 url = {https://cforall.uwaterloo.ca} 8 9 } 9 10 @article{cfa:typesystem, 10 author = {Aaron Moss and Robert Schluntz and Peter A. Buhr}, 11 title = {{\CFA} : Adding modern programming language features to {C}}, 12 journal = {Softw. Pract. Exp.}, 13 volume = {48}, 14 number = {12}, 15 pages = {2111--2146}, 16 year = {2018}, 17 url = {https://doi.org/10.1002/spe.2624}, 18 doi = {10.1002/spe.2624}, 19 timestamp = {Thu, 09 Apr 2020 17:14:14 +0200}, 20 biburl = {https://dblp.org/rec/journals/spe/MossSB18.bib}, 21 bibsource = {dblp computer science bibliography, https://dblp.org} 11 author = {Aaron Moss and Robert Schluntz and Peter A. Buhr}, 12 title = {{\CFA} : Adding modern programming language features to {C}}, 13 journal = {Softw. Pract. Exp.}, 14 volume = {48}, 15 number = {12}, 16 pages = {2111--2146}, 17 year = {2018}, 22 18 } 23 24 19 25 20 % -------------------------------------------------- … … 27 22 28 23 @inproceedings{arr:futhark:tytheory, 29 author = {Henriksen, Troels and Elsman, Martin}, 30 title = {Towards Size-Dependent Types for Array Programming}, 31 year = {2021}, 32 isbn = {9781450384667}, 33 publisher = {Association for Computing Machinery}, 34 address = {New York, NY, USA}, 35 url = {https://doi.org/10.1145/3460944.3464310}, 36 doi = {10.1145/3460944.3464310}, 37 abstract = {We present a type system for expressing size constraints on array types in an ML-style type system. The goal is to detect shape mismatches at compile-time, while being simpler than full dependent types. The main restrictions is that the only terms that can occur in types are array sizes, and syntactically they must be variables or constants. For those programs where this is not sufficient, we support a form of existential types, with the type system automatically managing the requisite book-keeping. We formalise a large subset of the type system in a small core language, which we prove sound. We also present an integration of the type system in the high-performance parallel functional language Futhark, and show on a collection of 44 representative programs that the restrictions in the type system are not too problematic in practice.}, 38 booktitle = {Proceedings of the 7th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming}, 39 pages = {1–14}, 40 numpages = {14}, 41 keywords = {functional programming, parallel programming, type systems}, 42 location = {Virtual, Canada}, 43 series = {ARRAY 2021} 24 author = {Troels Henriksen and Martin Elsman}, 25 title = {Towards Size-Dependent Types for Array Programming}, 26 year = {2021}, 27 publisher = {Association for Computing Machinery}, 28 address = {New York, NY, USA}, 29 booktitle = {Proceedings of the 7th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming}, 30 pages = {1-14}, 31 numpages = {14}, 32 location = {Virtual, Canada}, 33 series = {ARRAY 2021} 44 34 } 45 35 46 36 @article{arr:dex:long, 47 author = {Adam Paszke and 48 Daniel D. Johnson and 49 David Duvenaud and 50 Dimitrios Vytiniotis and 51 Alexey Radul and 52 Matthew J. Johnson and 53 Jonathan Ragan{-}Kelley and 54 Dougal Maclaurin}, 55 title = {Getting to the Point. Index Sets and Parallelism-Preserving Autodiff 56 for Pointful Array Programming}, 57 journal = {CoRR}, 58 volume = {abs/2104.05372}, 59 year = {2021}, 60 url = {https://arxiv.org/abs/2104.05372}, 61 eprinttype = {arXiv}, 62 eprint = {2104.05372}, 63 timestamp = {Mon, 25 Oct 2021 07:55:47 +0200}, 64 biburl = {https://dblp.org/rec/journals/corr/abs-2104-05372.bib}, 65 bibsource = {dblp computer science bibliography, https://dblp.org} 37 author = {Adam Paszke and Daniel D. Johnson and David Duvenaud and 38 Dimitrios Vytiniotis and Alexey Radul and Matthew J. Johnson and 39 Jonathan Ragan-Kelley and Dougal Maclaurin}, 40 title = {Getting to the Point. Index Sets and Parallelism-Preserving Autodiff 41 for Pointful Array Programming}, 42 publisher = {Association for Computing Machinery}, 43 address = {New York, NY, USA}, 44 volume = 5, 45 number = {ICFP}, 46 year = 2021, 47 journal = {Proc. ACM Program. Lang.}, 48 month = {aug}, 66 49 } 67 50 … … 74 57 title = {\textsf{C}$\mathbf{\forall}$ Stack Evaluation Programs}, 75 58 year = 2018, 76 howpublished= {\ href{https://cforall.uwaterloo.ca/CFAStackEvaluation.zip}{https://cforall.uwaterloo.ca/\-CFAStackEvaluation.zip}},59 howpublished= {\url{https://cforall.uwaterloo.ca/CFAStackEvaluation.zip}}, 77 60 } 78 61 79 62 @misc{lst:linuxq, 80 title = {queue(7) —Linux manual page},81 howpublished= {\href{https://man7.org/linux/man-pages/man3/queue.3.html}{https://man7.org/linux/man-pages/man3/queue.3.html}},63 title = {queue(7) -- Linux manual page}, 64 howpublished= {\url{https://man7.org/linux/man-pages/man3/queue.3.html}}, 82 65 } 83 84 85 66 % see also https://man7.org/linux/man-pages/man7/queue.7.license.html 67 % https://man7.org/tlpi/ 68 % https://www.kernel.org/doc/man-pages/ 86 69 87 70 @misc{lst:stl, 88 title= {std::list},89 howpublished= {\href{https://en.cppreference.com/w/cpp/container/list}{https://en.cppreference.com/w/cpp/container/list}},71 title = {std::list}, 72 howpublished= {\url{https://en.cppreference.com/w/cpp/container/list}}, 90 73 } 91 74 75 @article{Blache19, 76 author = {Gunter Blache}, 77 title = {Handling Index-out-of-bounds in safety-critical embedded {C} code using model-based development}, 78 journal = {Software \& Systems Modeling}, 79 volume = 18, 80 year = 2019, 81 pages = {1795-1805}, 82 } 83 84 @article{Oorschot23, 85 author = {van Oorschot, Paul C.}, 86 journal = {IEEE Security \& Privacy}, 87 title = {Memory Errors and Memory Safety: {C} as a Case Study}, 88 year = 2023, 89 volume = 21, 90 number = 2, 91 pages = {70-76}, 92 } 93 94 @InProceedings{Ruef19, 95 author = {Andrew Ruef and Leonidas Lampropoulos and Ian Sweet and David Tarditi and Michael Hicks}, 96 title = {Achieving Safety Incrementally with {Checked C}}, 97 editor = {Flemming Nielson and David Sands}, 98 booktitle = {Principles of Security and Trust}, 99 publisher = {Springer International Publishing}, 100 address = {Cham}, 101 year = {2019}, 102 pages = {76-98}, 103 } 104 -
doc/theses/mike_brooks_MMath/uw-ethesis.tex
r0fa0201d r5546eee4 93 93 \usepackage{algorithm} 94 94 \usepackage{algpseudocode} 95 96 \usepackage{pbox} 95 97 96 98 % Hyperlinks make it very easy to navigate an electronic document. … … 127 129 urlcolor=black 128 130 }}{} % end of ifthenelse (no else) 131 \urlstyle{sf} 129 132 130 133 %\usepackage[automake,toc,abbreviations]{glossaries-extra} % Exception to the rule of hyperref being the last add-on package -
libcfa/src/exception.c
r0fa0201d r5546eee4 309 309 struct _Unwind_Context * unwind_context) 310 310 { 311 312 //__cfadbg_print_safe(exception, "CFA: 0x%lx\n", _Unwind_GetCFA(context)); 311 //! __cfadbg_print_safe(exception, "CFA: 0x%lx\n", _Unwind_GetCFA(unwind_context)); 313 312 __cfadbg_print_safe(exception, "Personality function (%d, %x, %llu, %p, %p):", 314 313 version, actions, exception_class, unwind_exception, unwind_context); -
src/AST/Decl.cpp
r0fa0201d r5546eee4 9 9 // Author : Aaron B. Moss 10 10 // Created On : Thu May 9 10:00:00 2019 11 // Last Modified By : Andrew Beach12 // Last Modified On : Thu May 5 12:10:00 202213 // Update Count : 2411 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sat Dec 9 16:28:51 2023 13 // Update Count : 31 14 14 // 15 15 … … 113 113 // --- EnumDecl 114 114 115 bool EnumDecl::valueOf( const Decl * enumerator, long long & value ) const {115 bool EnumDecl::valueOf( const Decl * enumerator, long long & value ) const { 116 116 if ( enumValues.empty() ) { 117 117 Evaluation crntVal = {0, true, true}; // until expression is given, we know to start counting from 0 118 118 for ( const Decl * member : members ) { 119 const ObjectDecl * field = strict_dynamic_cast< const ObjectDecl* >( member );119 const ObjectDecl * field = strict_dynamic_cast< const ObjectDecl * >( member ); 120 120 if ( field->init ) { 121 const SingleInit * init = strict_dynamic_cast< const SingleInit * >( field->init.get() );121 const SingleInit * init = strict_dynamic_cast< const SingleInit * >( field->init.get() ); 122 122 crntVal = eval( init->value ); 123 123 if ( ! crntVal.isEvaluableInGCC ) { 124 SemanticError( init->location, ::toString( "Non-constexpr in initialization of " 125 "enumerator: ", field ) ); 124 SemanticError( init->location, "Non-constexpr in initialization of enumerator %s", field->name.c_str() ); 126 125 } 127 126 } 128 127 if ( enumValues.count( field->name ) != 0 ) { 129 SemanticError( location, ::toString( "Enum ", name, " has multiple members with the " "name ", field->name) );128 SemanticError( location, "Enum %s has multiple members with %s", name.c_str(), field->name.c_str() ); 130 129 } 131 130 if (crntVal.hasKnownValue) { -
src/AST/Expr.cpp
r0fa0201d r5546eee4 9 9 // Author : Aaron B. Moss 10 10 // Created On : Wed May 15 17:00:00 2019 11 // Last Modified By : Andrew Beach11 // Last Modified By : Peter A. Buhr 12 12 // Created On : Wed May 18 13:56:00 2022 13 // Update Count : 813 // Update Count : 12 14 14 // 15 15 … … 168 168 return addrType( refType->base ); 169 169 } else { 170 SemanticError( loc, arg->result.get(),171 "Attempt to take address of non-lvalue expression: ");170 SemanticError( loc, "Attempt to take address of non-lvalue expression %s", 171 toString( arg->result.get() ).c_str() ); 172 172 } 173 173 } … … 240 240 return 1; 241 241 } 242 SemanticError( this, "Constant expression of non-integral type " ); 242 SemanticError( this->location, "Constant expression of non-integral type %s", 243 toString( this ).c_str() ); 243 244 } 244 245 -
src/AST/LinkageSpec.cpp
r0fa0201d r5546eee4 9 9 // Author : Aaron B. Moss 10 10 // Created On : Thu May 9 10:00:00 2019 11 // Last Modified By : Aaron B. Moss12 // Last Modified On : Thu May 9 10:00:00 201913 // Update Count : 111 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Mon Dec 11 16:08:58 2023 13 // Update Count : 2 14 14 // 15 15 … … 37 37 return spec; 38 38 } else { 39 SemanticError( loc, "Invalid linkage specifier " + *cmd);39 SemanticError( loc, "Invalid linkage specifier %s", cmd->c_str() ); 40 40 } 41 41 } -
src/AST/TypeSubstitution.hpp
r0fa0201d r5546eee4 9 9 // Author : Richard C. Bilson 10 10 // Created On : Mon May 18 07:44:20 2015 11 // Last Modified By : Andrew Beach12 // Last Modified On : Thr May 25 12:31:00 202313 // Update Count : 1 011 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Mon Dec 11 16:07:30 2023 13 // Update Count : 15 14 14 // 15 15 … … 156 156 } // if 157 157 } else { 158 SemanticError( formal, toString( "Attempt to provide non-type parameter: ", toString( *actualIt ).c_str(), " for type parameter " ) ); 158 SemanticError( formal->location, "Attempt to provide non-type parameter %s for type parameter %s", 159 toString( *actualIt ).c_str(), formal->name.c_str() ); 159 160 } // if 160 161 } else { -
src/CodeGen/CodeGenerator.cpp
r0fa0201d r5546eee4 1026 1026 output << " ) "; 1027 1027 1028 output << "{" ;1028 output << "{" << endl; 1029 1029 ++indent; 1030 1030 for ( auto node : stmt->cases ) { -
src/CodeGen/FixMain.cc
r0fa0201d r5546eee4 11 11 // Last Modified By : 12 12 // Last Modified On : 13 // Update Count : 013 // Update Count : 1 14 14 // 15 15 … … 39 39 if ( isMain( decl ) ) { 40 40 if ( main_declaration ) { 41 SemanticError( decl, "Multiple definition of main routine \n" );41 SemanticError( decl, "Multiple definition of main routine" ); 42 42 } 43 43 main_declaration = decl; -
src/CodeGen/FixNames.cc
r0fa0201d r5546eee4 9 9 // Author : Richard C. Bilson 10 10 // Created On : Mon May 18 07:44:20 2015 11 // Last Modified By : Andrew Beach12 // Last Modified On : Wed Jul 20 11:49:00 202213 // Update Count : 2 411 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Thu Dec 14 16:16:51 2023 13 // Update Count : 25 14 14 // 15 15 … … 57 57 int nargs = mutDecl->params.size(); 58 58 if ( 0 != nargs && 2 != nargs && 3 != nargs ) { 59 SemanticError( functionDecl, "Main expected to have 0, 2 or 3 arguments \n" );59 SemanticError( functionDecl, "Main expected to have 0, 2 or 3 arguments" ); 60 60 } 61 61 ast::chain_mutate( mutDecl->stmts )->kids.push_back( -
src/Common/ErrorObjects.h
r0fa0201d r5546eee4 46 46 std::list< error > errors; 47 47 }; 48 49 void SemanticWarningImpl( CodeLocation location, std::string error );50 51 template< typename T >52 static inline void SemanticWarningImpl( const T * obj, const std::string & error ) {53 SemanticWarning( obj->location, toString( error, obj ) );54 }55 56 template< typename T >57 static inline void SemanticWarningImpl( CodeLocation location, const T * obj, const std::string & error ) {58 SemanticWarningImpl( location, toString( error, obj ) );59 } -
src/Common/SemanticError.cc
r0fa0201d r5546eee4 10 10 // Created On : Mon May 18 07:44:20 2015 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Thu Jun 7 08:05:26 201813 // Update Count : 1012 // Last Modified On : Thu Dec 14 13:45:28 2023 13 // Update Count : 34 14 14 // 15 15 … … 23 23 #include <vector> 24 24 25 using namespace std; 26 25 27 #include "Common/utility.h" // for to_string, CodeLocation (ptr only) 26 28 #include "SemanticError.h" … … 28 30 //----------------------------------------------------------------------------- 29 31 // Severity Handling 30 std::vector<Severity> & get_severities() {31 static std::vector<Severity> severities;32 vector<Severity> & get_severities() { 33 static vector<Severity> severities; 32 34 if(severities.empty()) { 33 35 severities.reserve((size_t)Warning::NUMBER_OF_WARNINGS); … … 60 62 size_t idx = 0; 61 63 for ( const auto & w : WarningFormats ) { 62 if ( st d::strcmp( name, w.name ) == 0 ) {64 if ( strcmp( name, w.name ) == 0 ) { 63 65 get_severities()[idx] = s; 64 66 break; … … 70 72 //----------------------------------------------------------------------------- 71 73 // Semantic Error 74 72 75 bool SemanticErrorThrow = false; 73 76 74 SemanticErrorException::SemanticErrorException( CodeLocation location, st d::string error ) {77 SemanticErrorException::SemanticErrorException( CodeLocation location, string error ) { 75 78 append( location, error ); 76 79 } … … 80 83 } 81 84 82 void SemanticErrorException::append( CodeLocation location, const st d::string & msg ) {85 void SemanticErrorException::append( CodeLocation location, const string & msg ) { 83 86 errors.emplace_back( location, msg ); 84 87 } … … 89 92 90 93 void SemanticErrorException::print() { 91 using std::to_string;94 // using to_string; 92 95 93 96 errors.sort([](const error & lhs, const error & rhs) -> bool { … … 99 102 100 103 for( auto err : errors ) { 101 std::cerr << ErrorHelpers::bold() << err.location << ErrorHelpers::error_str() << ErrorHelpers::reset_font() << err.description << std::endl;104 cerr << ErrorHelpers::bold() << err.location << ErrorHelpers::error_str() << ErrorHelpers::reset_font() << err.description << endl; 102 105 } 103 106 } 104 107 105 void SemanticError( CodeLocation location, std::string error ) { 108 void SemanticError( CodeLocation location, const char * fmt, ... ) { 109 char msg[2048]; // worst-case error-message buffer 110 va_list args; 111 va_start( args, fmt ); 112 vsnprintf( msg, sizeof(msg), fmt, args ); // always null terminated, but may be truncated 113 va_end( args ); 114 106 115 SemanticErrorThrow = true; 107 throw SemanticErrorException( location, error );116 throw SemanticErrorException( location, msg ); // convert msg to string 108 117 } 109 118 110 namespace { 111 // convert format string and arguments into a single string 112 std::string fmtToString(const char * fmt, va_list ap) { 113 int size = 128; 114 while ( true ) { 115 char buf[size]; 116 va_list args; 117 va_copy( args, ap ); 118 int n = vsnprintf(&buf[0], size, fmt, args); 119 va_end( args ); 120 if ( n < size && n >= 0 ) return buf; 121 size *= 2; 122 } 123 assert( false ); 124 } 125 } 119 void SemanticWarning( CodeLocation location, Warning warning, ... ) { 120 Severity severity = get_severities()[(int)warning]; 126 121 127 void SemanticWarningImpl( CodeLocation location, Warning warning, const char * const fmt, ... ) { 128 Severity severity = get_severities()[(int)warning]; 129 switch(severity) { 122 switch ( severity ) { 130 123 case Severity::Suppress : 131 124 break; 132 125 case Severity::Warn : 133 {134 va_list args;135 va_start(args, fmt);136 std::string msg = fmtToString( fmt, args );137 va_end(args);138 std::cerr << ErrorHelpers::bold() << location << ErrorHelpers::warning_str() << ErrorHelpers::reset_font() << msg << std::endl;139 }140 break;141 126 case Severity::Error : 142 127 { 128 char msg[2048]; // worst-case error-message buffer 143 129 va_list args; 144 va_start(args, fmt); 145 std::string msg = fmtToString( fmt, args ); 146 va_end(args); 147 SemanticError(location, msg); 130 va_start( args, warning ); 131 vsnprintf( msg, sizeof(msg), WarningFormats[(int)warning].message, args ); // always null terminated, but may be truncated 132 va_end( args ); 133 134 if ( severity == Severity::Warn ) { 135 cerr << ErrorHelpers::bold() << location << ErrorHelpers::warning_str() << ErrorHelpers::reset_font() << msg << endl; 136 } else { 137 SemanticError( location, string( msg ) ); 138 } 148 139 } 149 140 break; … … 163 154 } 164 155 165 const st d::string & error_str() {166 static st d::string str = with_colors() ? "\e[31merror:\e[39m " : "error: ";156 const string & error_str() { 157 static string str = with_colors() ? "\e[31merror:\e[39m " : "error: "; 167 158 return str; 168 159 } 169 160 170 const st d::string & warning_str() {171 static st d::string str = with_colors() ? "\e[95mwarning:\e[39m " : "warning: ";161 const string & warning_str() { 162 static string str = with_colors() ? "\e[95mwarning:\e[39m " : "warning: "; 172 163 return str; 173 164 } 174 165 175 const st d::string & bold_ttycode() {176 static st d::string str = with_colors() ? "\e[1m" : "";166 const string & bold_ttycode() { 167 static string str = with_colors() ? "\e[1m" : ""; 177 168 return str; 178 169 } 179 170 180 const st d::string & reset_font_ttycode() {181 static st d::string str = with_colors() ? "\e[0m" : "";171 const string & reset_font_ttycode() { 172 static string str = with_colors() ? "\e[0m" : ""; 182 173 return str; 183 174 } 184 175 185 st d::string make_bold( const std::string & str ) {176 string make_bold( const string & str ) { 186 177 return bold_ttycode() + str + reset_font_ttycode(); 187 178 } 188 179 189 std::ostream & operator<<(std::ostream & os, bold) {180 ostream & operator<<(ostream & os, bold) { 190 181 os << bold_ttycode(); 191 182 return os; 192 183 } 193 184 194 std::ostream & operator<<(std::ostream & os, reset_font) {185 ostream & operator<<(ostream & os, reset_font) { 195 186 os << reset_font_ttycode(); 196 187 return os; -
src/Common/SemanticError.h
r0fa0201d r5546eee4 10 10 // Created On : Mon May 18 07:44:20 2015 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sat Feb 25 12:01:31202313 // Update Count : 3712 // Last Modified On : Thu Dec 14 13:48:07 2023 13 // Update Count : 72 14 14 // 15 15 … … 18 18 #include "ErrorObjects.h" 19 19 #include "AST/Node.hpp" 20 #include "AST/ParseNode.hpp" 20 21 #include <cstring> 21 22 … … 25 26 extern bool SemanticErrorThrow; 26 27 27 __attribute__((noreturn )) void SemanticError( CodeLocation location, std::string error);28 __attribute__((noreturn, format(printf, 2, 3))) void SemanticError( CodeLocation location, const char fmt[], ... ); 28 29 29 template< typename T > 30 __attribute__((noreturn)) static inline void SemanticError( const T * obj, const std::string & error ) { 30 __attribute__((noreturn)) static inline void SemanticError( CodeLocation location, std::string error ) { 31 SemanticErrorThrow = true; 32 throw SemanticErrorException( location, error ); 33 } 34 35 __attribute__((noreturn)) static inline void SemanticError( const ast::ParseNode * obj, const std::string & error ) { 31 36 SemanticError( obj->location, toString( error, obj ) ); 32 37 } 33 38 34 template< typename T > 35 __attribute__((noreturn)) static inline void SemanticError( CodeLocation location, const T * obj, const std::string & error ) { 39 __attribute__((noreturn)) static inline void SemanticError( CodeLocation location, const ast::Node * obj, const std::string & error ) { 36 40 SemanticError( location, toString( error, obj ) ); 37 41 } … … 54 58 55 59 constexpr WarningData WarningFormats[] = { 56 {"self-assign" , Severity::Warn 57 {"reference-conversion" , Severity::Warn 58 {"qualifiers-zero_t-one_t" , Severity::Warn 59 {"aggregate-forward-decl" , Severity::Warn 60 {"superfluous-decl" , Severity::Warn 61 {"superfluous-else" , Severity::Warn 62 {"gcc-attributes" , Severity::Warn 63 {"c++-like-copy" , Severity::Warn 64 {"depreciated-trait-syntax" , Severity::Warn 60 {"self-assign" , Severity::Warn, "self assignment of expression: %s" }, 61 {"reference-conversion" , Severity::Warn, "rvalue to reference conversion of rvalue: %s" }, 62 {"qualifiers-zero_t-one_t" , Severity::Warn, "questionable use of type qualifier(s) with %s" }, 63 {"aggregate-forward-decl" , Severity::Warn, "forward declaration of nested aggregate: %s" }, 64 {"superfluous-decl" , Severity::Warn, "declaration does not allocate storage: %s" }, 65 {"superfluous-else" , Severity::Warn, "else clause never executed for empty loop conditional" }, 66 {"gcc-attributes" , Severity::Warn, "invalid attribute: %s" }, 67 {"c++-like-copy" , Severity::Warn, "Constructor from reference is not a valid copy constructor" }, 68 {"depreciated-trait-syntax" , Severity::Warn, "trait type-parameters are now specified using the forall clause" }, 65 69 }; 66 70 … … 75 79 CppCopy, 76 80 DeprecTraitSyntax, 77 NUMBER_OF_WARNINGS, // This MUST be the last warning81 NUMBER_OF_WARNINGS, // MUST be last warning 78 82 }; 79 83 … … 83 87 ); 84 88 85 #define SemanticWarning(loc, id, ...) SemanticWarningImpl(loc, id, WarningFormats[(int)id].message, ##__VA_ARGS__) 89 void SemanticWarning( CodeLocation loc, Warning warn, ... ); 86 90 87 void SemanticWarningImpl (CodeLocation loc, Warning warn, const char * const fmt, ...) __attribute__((format(printf, 3, 4))); 88 89 void SemanticWarning_SuppressAll (); 90 void SemanticWarning_EnableAll (); 91 void SemanticWarning_SuppressAll(); 92 void SemanticWarning_EnableAll(); 91 93 void SemanticWarning_WarningAsError(); 92 void SemanticWarning_Set 94 void SemanticWarning_Set(const char * const name, Severity s); 93 95 94 96 // SKULLDUGGERY: cfa.cc is built before SemanticError.cc but needs this routine. -
src/Concurrency/Corun.cpp
r0fa0201d r5546eee4 9 9 // Author : Colby Parsons 10 10 // Created On : Monday October 9 15:16:42 2023 11 // Last Modified By : Colby Parsons12 // Last Modified On : Monday October 9 15:16:42202313 // Update Count : 011 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Thu Dec 14 17:32:17 2023 13 // Update Count : 1 14 14 // 15 15 … … 57 57 Stmt * postvisit( const CoforStmt * stmt ) { 58 58 if ( !runnerBlockDecl || !coforRunnerDecl ) 59 SemanticError( stmt->location, "To use cofor statements add #include <cofor.hfa> \n" );59 SemanticError( stmt->location, "To use cofor statements add #include <cofor.hfa>" ); 60 60 61 61 if ( stmt->inits.size() != 1 ) 62 SemanticError( stmt->location, "Cofor statements must have a single initializer in the loop control \n" );62 SemanticError( stmt->location, "Cofor statements must have a single initializer in the loop control" ); 63 63 64 64 if ( !stmt->body ) … … 77 77 const DeclStmt * declStmtPtr = dynamic_cast<const DeclStmt *>(stmt->inits.at(0).get()); 78 78 if ( ! declStmtPtr ) 79 SemanticError( stmt->location, "Cofor statement initializer is somehow not a decl statement? \n" );79 SemanticError( stmt->location, "Cofor statement initializer is somehow not a decl statement?" ); 80 80 81 81 const Decl * declPtr = dynamic_cast<const Decl *>(declStmtPtr->decl.get()); 82 82 if ( ! declPtr ) 83 SemanticError( stmt->location, "Cofor statement initializer is somehow not a decl? \n" );83 SemanticError( stmt->location, "Cofor statement initializer is somehow not a decl?" ); 84 84 85 85 Type * initType = new TypeofType( new NameExpr( loc, declPtr->name ) ); … … 246 246 Stmt * postvisit( const CorunStmt * stmt ) { 247 247 if ( !runnerBlockDecl || !coforRunnerDecl ) 248 SemanticError( stmt->location, "To use corun statements add #include <cofor.hfa> \n" );248 SemanticError( stmt->location, "To use corun statements add #include <cofor.hfa>" ); 249 249 250 250 if ( !stmt->stmt ) -
src/Concurrency/Keywords.cpp
r0fa0201d r5546eee4 9 9 // Author : Andrew Beach 10 10 // Created On : Tue Nov 16 9:53:00 2021 11 // Last Modified By : Andrew Beach12 // Last Modified On : Fri Mar 11 10:40:00 202213 // Update Count : 211 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Thu Dec 14 18:02:25 2023 13 // Update Count : 6 14 14 // 15 15 … … 682 682 683 683 if ( 0 != decl->returns.size() ) { 684 SemanticError( decl->location, "Generator main must return void " );684 SemanticError( decl->location, "Generator main must return void." ); 685 685 } 686 686 … … 789 789 case ast::SuspendStmt::Generator: 790 790 // Generator suspends must be directly in a generator. 791 if ( !in_generator ) SemanticError( stmt->location, " 'suspend generator'must be used inside main of generator type." );791 if ( !in_generator ) SemanticError( stmt->location, "\"suspend generator\" must be used inside main of generator type." ); 792 792 return make_generator_suspend( stmt ); 793 793 } … … 847 847 848 848 if ( !decl_suspend ) { 849 SemanticError( location, "suspend keyword applied to coroutines requires coroutines to be in scope, add #include <coroutine.hfa> \n" );849 SemanticError( location, "suspend keyword applied to coroutines requires coroutines to be in scope, add #include <coroutine.hfa>." ); 850 850 } 851 851 if ( stmt->then ) { … … 918 918 // If it is a monitor, then it is a monitor. 919 919 if( baseStruct->base->is_monitor() || baseStruct->base->is_thread() ) { 920 SemanticError( decl, "destructors for structures declared as \"monitor\" must use mutex parameters \n" );920 SemanticError( decl, "destructors for structures declared as \"monitor\" must use mutex parameters " ); 921 921 } 922 922 } … … 926 926 // Monitors can't be constructed with mutual exclusion. 927 927 if ( CodeGen::isConstructor( decl->name ) && is_first_argument_mutex ) { 928 SemanticError( decl, "constructors cannot have mutex parameters \n" );928 SemanticError( decl, "constructors cannot have mutex parameters " ); 929 929 } 930 930 931 931 // It makes no sense to have multiple mutex parameters for the destructor. 932 932 if ( isDtor && mutexArgs.size() != 1 ) { 933 SemanticError( decl, "destructors can only have 1 mutex argument \n" );933 SemanticError( decl, "destructors can only have 1 mutex argument " ); 934 934 } 935 935 … … 945 945 // Check to if the required headers have been seen. 946 946 if ( !monitor_decl || !guard_decl || !dtor_guard_decl ) { 947 SemanticError( decl, "mutex keyword requires monitors to be in scope, add #include <monitor.hfa> \n" );947 SemanticError( decl, "mutex keyword requires monitors to be in scope, add #include <monitor.hfa>." ); 948 948 } 949 949 … … 952 952 if ( isDtor && isThread( mutexArgs.front() ) ) { 953 953 if ( !thread_guard_decl ) { 954 SemanticError( decl, "thread destructor requires threads to be in scope, add #include <thread.hfa> \n" );954 SemanticError( decl, "thread destructor requires threads to be in scope, add #include <thread.hfa>." ); 955 955 } 956 956 newBody = addThreadDtorStatements( decl, body, mutexArgs ); … … 987 987 const ast::Stmt * MutexKeyword::postvisit( const ast::MutexStmt * stmt ) { 988 988 if ( !lock_guard_decl ) { 989 SemanticError( stmt->location, "mutex stmt requires a header, add #include <mutex_stmt.hfa> \n" );989 SemanticError( stmt->location, "mutex stmt requires a header, add #include <mutex_stmt.hfa>." ); 990 990 } 991 991 ast::CompoundStmt * body = … … 1547 1547 if ( !type->base->is_thread() ) return decl; 1548 1548 if ( !thread_decl || !thread_ctor_seen ) { 1549 SemanticError( type->base->location, "thread keyword requires threads to be in scope, add #include <thread.hfa> " );1549 SemanticError( type->base->location, "thread keyword requires threads to be in scope, add #include <thread.hfa>." ); 1550 1550 } 1551 1551 const ast::CompoundStmt * stmt = decl->stmts; -
src/ControlStruct/FixLabels.cpp
r0fa0201d r5546eee4 10 10 // Created On : Mon Nov 1 09:39:00 2021 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Mon Jan 31 22:19:17 202213 // Update Count : 912 // Last Modified On : Sun Nov 26 15:06:51 2023 13 // Update Count : 10 14 14 // 15 15 … … 47 47 for ( auto kvp : labelTable ) { 48 48 if ( nullptr == kvp.second ) { 49 SemanticError( kvp.first.location, 50 "Use of undefined label: " + kvp.first.name ); 49 SemanticError( kvp.first.location, "Use of undefined label %s.", kvp.first.name.c_str() ); 51 50 } 52 51 } -
src/ControlStruct/MultiLevelExit.cpp
r0fa0201d r5546eee4 9 9 // Author : Andrew Beach 10 10 // Created On : Mon Nov 1 13:48:00 2021 11 // Last Modified By : Andrew Beach12 // Last Modified On : Fri Sep 8 17:04:00202313 // Update Count : 3 611 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Thu Dec 14 17:34:12 2023 13 // Update Count : 39 14 14 // 15 15 … … 254 254 if ( enclosing_control_structures.empty() ) { 255 255 SemanticError( stmt->location, 256 " 'break' outside a loop, 'switch', or labelled block" );256 "\"break\" outside a loop, \"switch\", or labelled block" ); 257 257 } 258 258 targetEntry = findEnclosingControlStructure( isBreakTarget ); … … 268 268 // Ensure that selected target is valid. 269 269 if ( targetEntry == enclosing_control_structures.rend() || ( isContinue && ! isContinueTarget( *targetEntry ) ) ) { 270 SemanticError( stmt->location, toString( (isContinue ? " 'continue'" : "'break'"),270 SemanticError( stmt->location, toString( (isContinue ? "\"continue\"" : "\"break\""), 271 271 " target must be an enclosing ", (isContinue ? "loop: " : "control structure: "), 272 272 stmt->originalTarget ) ); … … 279 279 // Check that target is valid. 280 280 if ( targetEntry == enclosing_control_structures.rend() ) { 281 SemanticError( stmt->location, " 'fallthrough' must be enclosed in a 'switch' or 'choose'" );281 SemanticError( stmt->location, "\"fallthrough\" must be enclosed in a \"switch\" or \"choose\"" ); 282 282 } 283 283 if ( ! stmt->target.empty() ) { 284 284 // Labelled fallthrough: target must be a valid fallthough label. 285 285 if ( ! fallthrough_labels.count( stmt->target ) ) { 286 SemanticError( stmt->location, toString( " 'fallthrough'target must be a later case statement: ",286 SemanticError( stmt->location, toString( "\"fallthrough\" target must be a later case statement: ", 287 287 stmt->originalTarget ) ); 288 288 } … … 296 296 // Check if in switch or choose statement. 297 297 if ( targetEntry == enclosing_control_structures.rend() ) { 298 SemanticError( stmt->location, " 'fallthrough' must be enclosed in a 'switch' or 'choose'" );298 SemanticError( stmt->location, "\"fallthrough\" must be enclosed in a \"switch\" or \"choose\"" ); 299 299 } 300 300 … … 309 309 } 310 310 if ( ! foundDefault ) { 311 SemanticError( stmt->location, " 'fallthrough default' must be enclosed in a 'switch' or 'choose'"312 "control structure with a 'default'clause" );311 SemanticError( stmt->location, "\"fallthrough default\" must be enclosed in a \"switch\" or \"choose\"" 312 "control structure with a \"default\" clause" ); 313 313 } 314 314 break; … … 338 338 // Check that fallthrough default comes before the default clause. 339 339 if ( ! targetEntry->isFallDefaultValid() ) { 340 SemanticError( stmt->location, " 'fallthrough default' must precede the 'default'clause" );340 SemanticError( stmt->location, "\"fallthrough default\" must precede the \"default\" clause" ); 341 341 } 342 342 break; … … 521 521 assert(0); 522 522 } 523 SemanticError( stmt->location, toString( "'return' may not appear in a ", context ));523 SemanticError( stmt->location, "\"return\" may not appear in a %s", context ); 524 524 } 525 525 -
src/GenPoly/Box.cpp
r0fa0201d r5546eee4 9 9 // Author : Andrew Beach 10 10 // Created On : Thr Oct 6 13:39:00 2022 11 // Last Modified By : Andrew Beach12 // Last Modified On : Mon Oct 2 17:00:00202313 // Update Count : 011 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Thu Dec 14 17:42:17 2023 13 // Update Count : 7 14 14 // 15 15 … … 777 777 if ( !concrete ) { 778 778 // Should this be an assertion? 779 SemanticError( expr, toString( typeSubs, 780 "\nunbound type variable: ", typeVar->typeString(), 781 " in application " ) ); 779 SemanticError( expr->location, "\nunbound type variable %s in application %s", 780 toString( typeSubs ).c_str(), typeVar->typeString().c_str() ); 782 781 } 783 782 arg = expr->args.insert( arg, -
src/InitTweak/FixInit.cpp
r0fa0201d r5546eee4 1057 1057 ) 1058 1058 if ( ! diff.empty() ) { 1059 SemanticError( stmt, std::string("jump to label '") + stmt->target.name + "' crosses initialization of " + (*diff.begin())->name + " " ); 1059 SemanticError( stmt->location, "jump to label \"%s\" crosses initialization of \"%s\".", 1060 stmt->target.name.c_str(), (*diff.begin())->name.c_str() ); 1060 1061 } // if 1061 1062 } … … 1076 1077 1077 1078 bool checkWarnings( const ast::FunctionDecl * funcDecl ) { 1078 // only check for warnings if the current function is a user-defined 1079 // constructor or destructor 1079 // only check for warnings if the current function is a user-defined constructor or destructor 1080 1080 if ( ! funcDecl ) return false; 1081 1081 if ( ! funcDecl->stmts ) return false; -
src/Parser/DeclarationNode.cc
r0fa0201d r5546eee4 10 10 // Created On : Sat May 16 12:34:05 2015 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sat Jun 17 14:41:48202313 // Update Count : 140 512 // Last Modified On : Thu Dec 14 19:05:17 2023 13 // Update Count : 1407 14 14 // 15 15 … … 632 632 dst->basictype = src->basictype; 633 633 } else if ( src->basictype != DeclarationNode::NoBasicType ) 634 SemanticError( yylloc, string( "multiple declaration types \"" ) + DeclarationNode::basicTypeNames[ dst->basictype ] +635 "\" and \"" + DeclarationNode::basicTypeNames[ src->basictype ] + "\"." );636 634 SemanticError( yylloc, "multiple declaration types \"%s\" and \"%s\".", 635 DeclarationNode::basicTypeNames[ dst->basictype ], 636 DeclarationNode::basicTypeNames[ src->basictype ] ); 637 637 if ( dst->complextype == DeclarationNode::NoComplexType ) { 638 638 dst->complextype = src->complextype; 639 639 } else if ( src->complextype != DeclarationNode::NoComplexType ) 640 SemanticError( yylloc, string( "multiple declaration types \"" ) + DeclarationNode::complexTypeNames[ src->complextype ] +641 "\" and \"" + DeclarationNode::complexTypeNames[ src->complextype ] + "\"." );642 640 SemanticError( yylloc, "multiple declaration types \"%s\" and \"%s\".", 641 DeclarationNode::complexTypeNames[ src->complextype ], 642 DeclarationNode::complexTypeNames[ src->complextype ] ); 643 643 if ( dst->signedness == DeclarationNode::NoSignedness ) { 644 644 dst->signedness = src->signedness; 645 645 } else if ( src->signedness != DeclarationNode::NoSignedness ) 646 SemanticError( yylloc, string( "conflicting type specifier \"" ) + DeclarationNode::signednessNames[ dst->signedness ] +647 "\" and \"" + DeclarationNode::signednessNames[ src->signedness ] + "\"." );648 646 SemanticError( yylloc, "conflicting type specifier \"%s\" and \"%s\".", 647 DeclarationNode::signednessNames[ dst->signedness ], 648 DeclarationNode::signednessNames[ src->signedness ] ); 649 649 if ( dst->length == DeclarationNode::NoLength ) { 650 650 dst->length = src->length; … … 652 652 dst->length = DeclarationNode::LongLong; 653 653 } else if ( src->length != DeclarationNode::NoLength ) 654 SemanticError( yylloc, string( "conflicting type specifier \"" ) + DeclarationNode::lengthNames[ dst->length ] + 655 "\" and \"" + DeclarationNode::lengthNames[ src->length ] + "\"." ); 654 SemanticError( yylloc, "conflicting type specifier \"%s\" and \"%s\".", 655 DeclarationNode::lengthNames[ dst->length ], 656 DeclarationNode::lengthNames[ src->length ] ); 656 657 } // if 657 658 break; -
src/Parser/ExpressionNode.cc
r0fa0201d r5546eee4 9 9 // Author : Peter A. Buhr 10 10 // Created On : Sat May 16 13:17:07 2015 11 // Last Modified By : Andrew Beach12 // Last Modified On : T ue Apr 4 11:07:00202313 // Update Count : 108 311 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Thu Dec 14 18:57:07 2023 13 // Update Count : 1087 14 14 // 15 15 … … 193 193 194 194 #if ! defined(__SIZEOF_INT128__) 195 if ( type == 5 ) SemanticError( yylloc, "int128 constant is not supported on this target " + str);195 if ( type == 5 ) SemanticError( yylloc, "int128 constant is not supported on this target \"%s\"", str.c_str() ); 196 196 #endif // ! __SIZEOF_INT128__ 197 197 … … 204 204 } else { // hex int128 constant 205 205 unsigned int len = str.length(); 206 if ( len > (2 + 16 + 16) ) SemanticError( yylloc, "128-bit hexadecimal constant to large " + str);206 if ( len > (2 + 16 + 16) ) SemanticError( yylloc, "128-bit hexadecimal constant to large \"%s\"", str.c_str() ); 207 207 // hex digits < 2^64 208 208 if ( len > (2 + 16) ) { … … 219 219 unsigned int len = str.length(); 220 220 if ( type == 5 && len > 2 + 64 ) { 221 if ( len > 2 + 64 + 64 ) SemanticError( yylloc, "128-bit binary constant to large " + str);221 if ( len > 2 + 64 + 64 ) SemanticError( yylloc, "128-bit binary constant to large \"%s\".", str.c_str() ); 222 222 str2 = "0b" + str.substr( len - 64 ); 223 223 str = str.substr( 0, len - 64 ); … … 233 233 } else { // octal int128 constant 234 234 unsigned int len = str.length(); 235 if ( len > 1 + 43 || (len == 1 + 43 && str[0] > '3') ) SemanticError( yylloc, "128-bit octal constant to large " + str);235 if ( len > 1 + 43 || (len == 1 + 43 && str[0] > '3') ) SemanticError( yylloc, "128-bit octal constant to large \"%s\"", str.c_str() ); 236 236 char buf[32]; 237 237 if ( len <= 1 + 21 ) { // value < 21 octal digitis … … 266 266 unsigned int len = str.length(); 267 267 if ( str.length() == 39 && str > (Unsigned ? "340282366920938463463374607431768211455" : "170141183460469231731687303715884105727") ) 268 SemanticError( yylloc, "128-bit decimal constant to large " + str);268 SemanticError( yylloc, "128-bit decimal constant to large \"%s\".", str.c_str() ); 269 269 char buf[32]; 270 270 if ( len <= 19 ) { // value < 19 decimal digitis … … 502 502 ast::Expr * build_field_name_FLOATING_FRACTIONconstant( 503 503 const CodeLocation & location, const string & str ) { 504 if ( str.find_first_not_of( "0123456789", 1 ) != string::npos ) SemanticError( yylloc, "invalid tuple index " + str);504 if ( str.find_first_not_of( "0123456789", 1 ) != string::npos ) SemanticError( yylloc, "invalid tuple index \"%s\".", str.c_str() ); 505 505 ast::Expr * ret = build_constantInteger( location, 506 506 *new string( str.substr(1) ) ); … … 511 511 ast::Expr * build_field_name_FLOATING_DECIMALconstant( 512 512 const CodeLocation & location, const string & str ) { 513 if ( str[str.size() - 1] != '.' ) SemanticError( yylloc, "invalid tuple index " + str);513 if ( str[str.size() - 1] != '.' ) SemanticError( yylloc, "invalid tuple index \"%s\".", str.c_str() ); 514 514 ast::Expr * ret = build_constantInteger( 515 515 location, *new string( str.substr( 0, str.size()-1 ) ) ); -
src/Parser/ParseNode.h
r0fa0201d r5546eee4 9 9 // Author : Rodolfo G. Esteves 10 10 // Created On : Sat May 16 13:28:16 2015 11 // Last Modified By : Andrew Beach12 // Last Modified On : Mon Apr 3 17:55:00202313 // Update Count : 94 211 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sat Dec 9 17:39:34 2023 13 // Update Count : 945 14 14 // 15 15 … … 37 37 class ExpressionNode; 38 38 struct StatementNode; 39 39 40 40 41 //############################################################################## … … 97 98 std::ostream & operator<<( std::ostream & out, const ParseNode * node ); 98 99 100 __attribute__((noreturn)) static inline void SemanticError( const ParseNode * obj, const std::string & error ) { 101 SemanticError( obj->location, toString( error, obj ) ); 102 } 103 99 104 // Local Variables: // 100 105 // tab-width: 4 // -
src/Parser/TypeData.cc
r0fa0201d r5546eee4 9 9 // Author : Rodolfo G. Esteves 10 10 // Created On : Sat May 16 15:12:51 2015 11 // Last Modified By : Andrew Beach12 // Last Modified On : T ue Apr 4 13:39:00202313 // Update Count : 68 011 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Thu Dec 14 18:59:12 2023 13 // Update Count : 684 14 14 // 15 15 … … 864 864 865 865 static string genTSError( string msg, DeclarationNode::BasicType basictype ) { 866 SemanticError( yylloc, string( "invalid type specifier \"" ) + msg + "\" for type \"" + DeclarationNode::basicTypeNames[basictype] + "\".");866 SemanticError( yylloc, "invalid type specifier \"%s\" for type \"%s\".", msg.c_str(), DeclarationNode::basicTypeNames[basictype] ); 867 867 } // genTSError 868 868 … … 1496 1496 // type set => parameter name already transformed by a declaration names so there is a duplicate 1497 1497 // declaration name attempting a second transformation 1498 if ( param->type ) SemanticError( param->location, string( "duplicate declaration name " ) + *param->name);1498 if ( param->type ) SemanticError( param->location, "duplicate declaration name \"%s\".", param->name->c_str() ); 1499 1499 // declaration type reset => declaration already transformed by a parameter name so there is a duplicate 1500 1500 // parameter name attempting a second transformation 1501 if ( ! decl->type ) SemanticError( param->location, string( "duplicate parameter name " ) + *param->name);1501 if ( ! decl->type ) SemanticError( param->location, "duplicate parameter name \"%s\".", param->name->c_str() ); 1502 1502 param->type = decl->type; // set copy declaration type to parameter type 1503 1503 decl->type = nullptr; // reset declaration type … … 1507 1507 } // for 1508 1508 // declaration type still set => type not moved to a matching parameter so there is a missing parameter name 1509 if ( decl->type ) SemanticError( decl->location, string( "missing name in parameter list " ) + *decl->name);1509 if ( decl->type ) SemanticError( decl->location, "missing name in parameter list %s", decl->name->c_str() ); 1510 1510 } // for 1511 1511 -
src/Parser/parser.yy
r0fa0201d r5546eee4 10 10 // Created On : Sat Sep 1 20:22:55 2001 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Tue Oct 3 17:14:12202313 // Update Count : 639 612 // Last Modified On : Sun Nov 26 13:18:06 2023 13 // Update Count : 6398 14 14 // 15 15 … … 260 260 } // if 261 261 } else { 262 SemanticError( yylloc, "syntax error, loop-index name missing. Expression disallowed. ." ); return nullptr;262 SemanticError( yylloc, "syntax error, loop-index name missing. Expression disallowed." ); return nullptr; 263 263 } // if 264 264 } // forCtrl 265 265 266 266 static void IdentifierBeforeIdentifier( string & identifier1, string & identifier2, const char * kind ) { 267 SemanticError( yylloc, ::toString( "syntax error, adjacent identifiers \"", identifier1, "\" and \"", identifier2, "\" are not meaningful in a", kind, ".\n" 268 "Possible cause is misspelled type name or missing generic parameter." ) ); 267 SemanticError( yylloc, "syntax error, adjacent identifiers \"%s\" and \"%s\" are not meaningful in an %s.\n" 268 "Possible cause is misspelled type name or missing generic parameter.", 269 identifier1.c_str(), identifier2.c_str(), kind ); 269 270 } // IdentifierBeforeIdentifier 270 271 271 272 static void IdentifierBeforeType( string & identifier, const char * kind ) { 272 SemanticError( yylloc, ::toString( "syntax error, identifier \"", identifier, "\" cannot appear before a ", kind, ".\n" 273 "Possible cause is misspelled storage/CV qualifier, misspelled typename, or missing generic parameter." ) ); 273 SemanticError( yylloc, "syntax error, identifier \"%s\" cannot appear before a %s.\n" 274 "Possible cause is misspelled storage/CV qualifier, misspelled typename, or missing generic parameter.", 275 identifier.c_str(), kind ); 274 276 } // IdentifierBeforeType 275 277 … … 689 691 // { SemanticError( yylloc, "Resume expression is currently unimplemented." ); $$ = nullptr; } 690 692 | IDENTIFIER IDENTIFIER // invalid syntax rule 691 { IdentifierBeforeIdentifier( *$1.str, *$2.str, " nexpression" ); $$ = nullptr; }693 { IdentifierBeforeIdentifier( *$1.str, *$2.str, "expression" ); $$ = nullptr; } 692 694 | IDENTIFIER type_qualifier // invalid syntax rule 693 695 { IdentifierBeforeType( *$1.str, "type qualifier" ); $$ = nullptr; } … … 1155 1157 | identifier_or_type_name ':' attribute_list_opt error // invalid syntax rule 1156 1158 { 1157 SemanticError( yylloc, ::toString( "syntx error, label \"", *$1.str, "\" must be associated with a statement, "1158 "where a declaration, case, or default is not a statement."1159 "Move the label or terminate with a semi-colon.") );1159 SemanticError( yylloc, "syntx error, label \"%s\" must be associated with a statement, " 1160 "where a declaration, case, or default is not a statement.\n" 1161 "Move the label or terminate with a semicolon.", $1.str->c_str() ); 1160 1162 $$ = nullptr; 1161 1163 } … … 2101 2103 | sue_declaration_specifier invalid_types // invalid syntax rule 2102 2104 { 2103 SemanticError( yylloc, ::toString( "syntax error, expecting ';' at end of ", 2104 $1->type->enumeration.name ? "enum" : ast::AggregateDecl::aggrString( $1->type->aggregate.kind ), 2105 " declaration." ) ); 2105 SemanticError( yylloc, "syntax error, expecting ';' at end of \"%s\" declaration.", 2106 $1->type->enumeration.name ? "enum" : ast::AggregateDecl::aggrString( $1->type->aggregate.kind ) ); 2106 2107 $$ = nullptr; 2107 2108 } … … 2161 2162 type_qualifier: 2162 2163 type_qualifier_name 2163 | attribute // trick handles most at rribute locations2164 | attribute // trick handles most attribute locations 2164 2165 ; 2165 2166 … … 2585 2586 | type_specifier field_declaring_list_opt '}' // invalid syntax rule 2586 2587 { 2587 SemanticError( yylloc, ::toString( "syntax error, expecting ';' at end of previous declaration." ));2588 SemanticError( yylloc, "syntax error, expecting ';' at end of previous declaration." ); 2588 2589 $$ = nullptr; 2589 2590 } -
src/ResolvExpr/CurrentObject.cc
r0fa0201d r5546eee4 9 9 // Author : Rob Schluntz 10 10 // Created On : Tue Jun 13 15:28:32 2017 11 // Last Modified By : Andrew Beach12 // Last Modified On : Mon Apr 10 9:40:00202313 // Update Count : 1811 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sat Dec 9 17:49:51 2023 13 // Update Count : 20 14 14 // 15 15 … … 181 181 auto res = eval( expr ); 182 182 if ( !res.hasKnownValue ) { 183 SemanticError( location, toString( "Array designator must be a constant expression: ", expr) );183 SemanticError( location, "Array designator must be a constant expression %s", toString( expr ).c_str() ); 184 184 } 185 185 return res.knownValue; -
src/ResolvExpr/Resolver.cc
r0fa0201d r5546eee4 9 9 // Author : Aaron B. Moss 10 10 // Created On : Sun May 17 12:17:01 2015 11 // Last Modified By : Andrew Beach12 // Last Modified On : Wed Apr 20 10:41:00 202213 // Update Count : 2 4811 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Thu Dec 14 18:44:43 2023 13 // Update Count : 251 14 14 // 15 15 … … 632 632 maybe_accept( mutDecl->init.get(), res ); 633 633 if ( !res.core.result ) { 634 SemanticError( mutDecl, "Cannot include designations in the initializer for a managed Object. If this is really what you want, then initialize with @=.\n" ); 634 SemanticError( mutDecl, "Cannot include designations in the initializer for a managed Object.\n" 635 "If this is really what you want, initialize with @=." ); 635 636 } 636 637 } … … 958 959 ++n_mutex_param; 959 960 960 // Check if the argument matches the parameter type in the current 961 // scope 961 // Check if the argument matches the parameter type in the current scope. 962 962 // ast::ptr< ast::Type > paramType = (*param)->get_type(); 963 963 964 if ( 964 965 ! unify( -
src/Validate/FixQualifiedTypes.cpp
r0fa0201d r5546eee4 9 9 // Author : Andrew Beach 10 10 // Created On : Thr Apr 21 11:13:00 2022 11 // Last Modified By : Andrew Beach12 // Last Modified On : Tue Sep 20 16:15:00 202213 // Update Count : 111 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Wed Dec 13 09:00:25 2023 13 // Update Count : 6 14 14 // 15 15 … … 41 41 auto td = symtab.globalLookupType( inst->name ); 42 42 if ( !td ) { 43 SemanticError( *location, toString("Use of undefined global type ", inst->name) );43 SemanticError( *location, "Use of undefined global type %s.", inst->name.c_str() ); 44 44 } 45 45 auto base = td->base; … … 50 50 } else { 51 51 // .T => T is not a type name. 52 assertf( false, "unhandled global qualified child type: %s", toCString( child) );52 assertf( false, "unhandled global qualified child type: %s", toCString( child ) ); 53 53 } 54 54 } else { … … 63 63 instp = inst; 64 64 } else { 65 SemanticError( *location, toString("Qualified type requires an aggregate on the left, but has: ", parent) );65 SemanticError( *location, "Qualified type requires an aggregate on the left, but has %s.", toCString( parent ) ); 66 66 } 67 67 // TODO: Need to handle forward declarations. … … 81 81 } else { 82 82 // S.T - S is not an aggregate => error. 83 assertf( false, "unhandled qualified child type : %s", toCString(type) );83 assertf( false, "unhandled qualified child type %s.", toCString( type ) ); 84 84 } 85 85 } 86 86 // failed to find a satisfying definition of type 87 SemanticError( *location, toString("Undefined type in qualified type: ", type) );87 SemanticError( *location, "Undefined type in qualified type %s", toCString( type ) ); 88 88 } 89 89 } -
src/Validate/ForallPointerDecay.cpp
r0fa0201d r5546eee4 9 9 // Author : Andrew Beach 10 10 // Created On : Tue Dec 7 16:15:00 2021 11 // Last Modified By : Andrew Beach12 // Last Modified On : S at Apr 23 13:10:00 202213 // Update Count : 111 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sun Nov 26 18:49:57 2023 13 // Update Count : 2 14 14 // 15 15 … … 213 213 auto type = obj->type->stripDeclarator(); 214 214 if ( dynamic_cast< const ast::FunctionType * >( type ) ) return; 215 SemanticError( obj->location, 216 toCString( "operator ", obj->name.c_str(), 217 " is not a function or function pointer." ) ); 215 SemanticError( obj->location, "operator %s is not a function or function pointer.", obj->name.c_str() ); 218 216 } 219 217 }; -
src/Validate/ReplaceTypedef.cpp
r0fa0201d r5546eee4 9 9 // Author : Andrew Beach 10 10 // Created On : Tue Jun 29 14:59:00 2022 11 // Last Modified By : Andrew Beach12 // Last Modified On : T ue Sep 20 17:00:00 202213 // Update Count : 211 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Thu Dec 14 16:11:51 2023 13 // Update Count : 4 14 14 // 15 15 … … 111 111 if ( !rtt ) { 112 112 assert( location ); 113 SemanticError( *location, "Cannot apply type parameters to base type of " + type->name);113 SemanticError( *location, "Cannot apply type parameters to base type of %s.", type->name.c_str() ); 114 114 } 115 115 rtt->params.clear(); … … 125 125 if ( base == typedeclNames.end() ) { 126 126 assert( location ); 127 SemanticError( *location, toString( "Use of undefined type ", type->name) );127 SemanticError( *location, "Use of undefined type %s.", type->name.c_str() ); 128 128 } 129 129 return ast::mutate_field( type, &ast::TypeInstType::base, base->second ); … … 152 152 || ast::Pass<VarLenChecker>::read( t0 ) 153 153 || ast::Pass<VarLenChecker>::read( t1 ) ) { 154 SemanticError( decl->location, "Cannot redefine typedef : " + decl->name);154 SemanticError( decl->location, "Cannot redefine typedef %s", decl->name.c_str() ); 155 155 } 156 156 } else { -
src/Virtual/ExpandCasts.cc
r0fa0201d r5546eee4 9 9 // Author : Andrew Beach 10 10 // Created On : Mon Jul 24 13:59:00 2017 11 // Last Modified By : Andrew Beach12 // Last Modified On : Thu Aug 11 12:06:00 202213 // Update Count : 511 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Mon Nov 27 09:28:20 2023 13 // Update Count : 10 14 14 // 15 15 … … 160 160 161 161 // Helper function for throwing semantic errors. 162 auto throwError = [&fieldName, &errorLocation, &oldDecl]( 163 std::string const & message ) { 164 std::string const & context = "While following head pointer of " + 165 oldDecl->name + " named '" + fieldName + "': "; 166 SemanticError( errorLocation, context + message ); 162 auto throwError = [&fieldName, &errorLocation, &oldDecl]( std::string const & message ) { 163 SemanticError( errorLocation, "While following head pointer of %s named \"%s\": %s", 164 oldDecl->name.c_str(), fieldName.c_str(), message.c_str() ); 167 165 }; 168 166 -
tests/.expect/nested-types-ERR1.txt
r0fa0201d r5546eee4 1 1 nested-types.cfa:100:25: warning: Compiled 2 nested-types.cfa:83:1 error: Use of undefined type T 2 nested-types.cfa:83:1 error: Use of undefined type T. -
tests/.expect/nested-types-ERR2.txt
r0fa0201d r5546eee4 1 1 nested-types.cfa:100:25: warning: Compiled 2 nested-types.cfa:86:1 error: Use of undefined global type Z 3 nested-types.cfa:87:1 error: Qualified type requires an aggregate on the left, but has : signed int4 nested-types.cfa:88:1 error: Undefined type in qualified type :Qualified Type:2 nested-types.cfa:86:1 error: Use of undefined global type Z. 3 nested-types.cfa:87:1 error: Qualified type requires an aggregate on the left, but has signed int. 4 nested-types.cfa:88:1 error: Undefined type in qualified type Qualified Type: 5 5 instance of struct S with body 6 6 instance of type Z (not function type) -
tests/.expect/typedefRedef-ERR1.txt
r0fa0201d r5546eee4 1 1 typedefRedef.cfa:75:25: warning: Compiled 2 typedefRedef.cfa:4:1 error: Cannot redefine typedef :Foo3 typedefRedef.cfa:31:1 error: Cannot redefine typedef :ARR4 typedefRedef.cfa:65:1 error: Cannot redefine typedef :ARR2 typedefRedef.cfa:4:1 error: Cannot redefine typedef Foo 3 typedefRedef.cfa:31:1 error: Cannot redefine typedef ARR 4 typedefRedef.cfa:65:1 error: Cannot redefine typedef ARR -
tests/concurrency/.expect/ctor-check.txt
r0fa0201d r5546eee4 1 concurrency/ctor-check.cfa:11:1 error: constructors cannot have mutex parameters 2 ?{}: function 1 concurrency/ctor-check.cfa:11:1 error: constructors cannot have mutex parameters ?{}: function 3 2 ... with parameters 4 3 this: mutex reference to instance of struct Empty with body -
tests/exceptions/.expect/try-ctrl-flow.txt
r0fa0201d r5546eee4 1 exceptions/try-ctrl-flow.cfa:7:1 error: 'break' outside a loop, 'switch', or labelled block2 exceptions/try-ctrl-flow.cfa:15:1 error: 'break' outside a loop, 'switch', or labelled block3 exceptions/try-ctrl-flow.cfa:23:1 error: 'break' outside a loop, 'switch', or labelled block4 exceptions/try-ctrl-flow.cfa:31:1 error: 'continue'target must be an enclosing loop:5 exceptions/try-ctrl-flow.cfa:48:1 error: 'break'target must be an enclosing control structure: mainLoop6 exceptions/try-ctrl-flow.cfa:56:1 error: 'continue'target must be an enclosing loop: mainLoop7 exceptions/try-ctrl-flow.cfa:65:1 error: 'break' outside a loop, 'switch', or labelled block8 exceptions/try-ctrl-flow.cfa:76:1 error: 'break' outside a loop, 'switch', or labelled block9 exceptions/try-ctrl-flow.cfa:87:1 error: 'fallthrough' must be enclosed in a 'switch' or 'choose'10 exceptions/try-ctrl-flow.cfa:98:1 error: 'break'target must be an enclosing control structure: mainBlock11 exceptions/try-ctrl-flow.cfa:111:1 error: 'fallthrough' must be enclosed in a 'switch' or 'choose'12 exceptions/try-ctrl-flow.cfa:124:1 error: 'fallthrough' must be enclosed in a 'switch' or 'choose'13 exceptions/try-ctrl-flow.cfa:133:1 error: 'return'may not appear in a finally clause14 exceptions/try-ctrl-flow.cfa:139:1 error: 'return'may not appear in a finally clause15 exceptions/try-ctrl-flow.cfa:148:1 error: 'break' outside a loop, 'switch', or labelled block16 exceptions/try-ctrl-flow.cfa:159:1 error: 'return'may not appear in a try statement with a catch clause17 exceptions/try-ctrl-flow.cfa:187:1 error: 'return'may not appear in a catch clause18 exceptions/try-ctrl-flow.cfa:195:1 error: 'return'may not appear in a catchResume clause1 exceptions/try-ctrl-flow.cfa:7:1 error: "break" outside a loop, "switch", or labelled block 2 exceptions/try-ctrl-flow.cfa:15:1 error: "break" outside a loop, "switch", or labelled block 3 exceptions/try-ctrl-flow.cfa:23:1 error: "break" outside a loop, "switch", or labelled block 4 exceptions/try-ctrl-flow.cfa:31:1 error: "continue" target must be an enclosing loop: 5 exceptions/try-ctrl-flow.cfa:48:1 error: "break" target must be an enclosing control structure: mainLoop 6 exceptions/try-ctrl-flow.cfa:56:1 error: "continue" target must be an enclosing loop: mainLoop 7 exceptions/try-ctrl-flow.cfa:65:1 error: "break" outside a loop, "switch", or labelled block 8 exceptions/try-ctrl-flow.cfa:76:1 error: "break" outside a loop, "switch", or labelled block 9 exceptions/try-ctrl-flow.cfa:87:1 error: "fallthrough" must be enclosed in a "switch" or "choose" 10 exceptions/try-ctrl-flow.cfa:98:1 error: "break" target must be an enclosing control structure: mainBlock 11 exceptions/try-ctrl-flow.cfa:111:1 error: "fallthrough" must be enclosed in a "switch" or "choose" 12 exceptions/try-ctrl-flow.cfa:124:1 error: "fallthrough" must be enclosed in a "switch" or "choose" 13 exceptions/try-ctrl-flow.cfa:133:1 error: "return" may not appear in a finally clause 14 exceptions/try-ctrl-flow.cfa:139:1 error: "return" may not appear in a finally clause 15 exceptions/try-ctrl-flow.cfa:148:1 error: "break" outside a loop, "switch", or labelled block 16 exceptions/try-ctrl-flow.cfa:159:1 error: "return" may not appear in a try statement with a catch clause 17 exceptions/try-ctrl-flow.cfa:187:1 error: "return" may not appear in a catch clause 18 exceptions/try-ctrl-flow.cfa:195:1 error: "return" may not appear in a catchResume clause -
tests/raii/.expect/dtor-early-exit-ERR1.txt
r0fa0201d r5546eee4 1 raii/dtor-early-exit.cfa:150:1 error: jump to label 'L1' crosses initialization of y Branch (Goto) 2 with target: L1 3 with original target: L1 4 1 raii/dtor-early-exit.cfa:150:1 error: jump to label "L1" crosses initialization of "y". -
tests/raii/.expect/dtor-early-exit-ERR2.txt
r0fa0201d r5546eee4 1 raii/dtor-early-exit.cfa:214:1 error: jump to label 'L2' crosses initialization of y Branch (Goto) 2 with target: L2 3 with original target: L2 4 1 raii/dtor-early-exit.cfa:214:1 error: jump to label "L2" crosses initialization of "y".
Note: See TracChangeset
for help on using the changeset viewer.