source: doc/theses/mike_brooks_MMath/background.tex

Last change on this file was 43d9679, checked in by Peter A. Buhr <pabuhr@…>, 2 months ago

move section from into to background

  • Property mode set to 100644
File size: 51.2 KB
Line 
1\chapter{Background}
2
3Since this work builds on C, it is necessary to explain the C mechanisms and their shortcomings for array, linked list, and string.
4
5
6\section{Ill-typed expressions}
7
8C reports many ill-typed expressions as warnings.
9For example, these attempts to assign @y@ to @x@ and vice-versa are obviously ill-typed.
10\lstinput{12-15}{bkgd-c-tyerr.c}
11with warnings:
12\begin{cfa}
13warning: assignment to 'float *' from incompatible pointer type 'void (*)(void)'
14warning: assignment to 'void (*)(void)' from incompatible pointer type 'float *'
15\end{cfa}
16Similarly,
17\lstinput{17-19}{bkgd-c-tyerr.c}
18with warning:
19\begin{cfa}
20warning: passing argument 1 of 'f' from incompatible pointer type
21note: expected 'void (*)(void)' but argument is of type 'float *'
22\end{cfa}
23with a segmentation fault at runtime.
24Clearly, @gcc@ understands these ill-typed case, and yet allows the program to compile, which seems inappropriate.
25Compiling with flag @-Werror@, which turns warnings into errors, is often too strong, because some warnings are just warnings, \eg unused variable.
26In the following discussion, ``ill-typed'' means giving a nonzero @gcc@ exit condition with a message that discusses typing.
27Note, \CFA's type-system rejects all these ill-typed cases as type mismatch errors.
28
29% That @f@'s attempt to call @g@ fails is not due to 3.14 being a particularly unlucky choice of value to put in the variable @pi@.
30% Rather, it is because obtaining a program that includes this essential fragment, yet exhibits a behaviour other than "doomed to crash," is a matter for an obfuscated coding competition.
31
32% A "tractable syntactic method for proving the absence of certain program behaviours by classifying phrases according to the kinds of values they compute"*1 rejected the program.
33% The behaviour (whose absence is unprovable) is neither minor nor unlikely.
34% The rejection shows that the program is ill-typed.
35%
36% Yet, the rejection presents as a GCC warning.
37% *1  TAPL-pg1 definition of a type system
38
39
40\section{Array}
41
42At the start, the C programming language made a significant design mistake.
43\begin{quote}
44In C, there is a strong relationship between pointers and arrays, strong enough that pointers and arrays really should be treated simultaneously.
45Any operation which can be achieved by array subscripting can also be done with pointers.~\cite[p.~93]{C:old}
46\end{quote}
47Accessing any storage requires pointer arithmetic, even if it is just base-displacement addressing in an instruction.
48The conjoining of pointers and arrays could also be applied to structures, where a pointer references a structure field like an array element.
49Finally, while subscripting involves pointer arithmetic (as does field references @x.y.z@), the computation is very complex for multi-dimensional arrays and requires array descriptors to know stride lengths along dimensions.
50Many C errors result from performing pointer arithmetic instead of using subscripting;
51some C textbooks teach pointer arithmetic erroneously suggesting it is faster than subscripting.
52A sound and efficient C program does not require explicit pointer arithmetic.
53
54C semantics want a programmer to \emph{believe} an array variable is a ``pointer to its first element.''
55This desire becomes apparent by a detailed inspection of an array declaration.
56\lstinput{34-34}{bkgd-carray-arrty.c}
57The inspection begins by using @sizeof@ to provide definite program semantics for the intuition of an expression's type.
58\lstinput{35-36}{bkgd-carray-arrty.c}
59Now consider the sizes of expressions derived from @ar@, modified by adding ``pointer to'' and ``first element'' (and including unnecessary parentheses to avoid confusion about precedence).
60\lstinput{37-40}{bkgd-carray-arrty.c}
61Given the size of @float@ is 4, the size of @ar@ with 10 floats being 40 bytes is common reasoning for C programmers.
62Equally, C programmers know the size of a \emph{pointer} to the first array element is 8 (or 4 depending on the addressing architecture).
63% Now, set aside for a moment the claim that this first assertion is giving information about a type.
64Clearly, an array and a pointer to its first element are different.
65
66In fact, the idea that there is such a thing as a pointer to an array may be surprising and it is not the same thing as a pointer to the first element.
67\lstinput{42-45}{bkgd-carray-arrty.c}
68The first assignment gets
69\begin{cfa}
70warning: assignment to `float (*)[10]' from incompatible pointer type `float *'
71\end{cfa}
72and the second assignment gets the opposite.
73
74The inspection now refutes any suggestion that @sizeof@ is informing about allocation rather than type information.
75Note, @sizeof@ has two forms, one operating on an expression and the other on a type.
76Using the type form yields the same results as the prior expression form.
77\lstinput{46-49}{bkgd-carray-arrty.c}
78The results are also the same when there is \emph{no allocation} using a pointer-to-array type.
79\lstinput{51-57}{bkgd-carray-arrty.c}
80Hence, in all cases, @sizeof@ is informing about type information.
81
82So, thinking of an array as a pointer to its first element is too simplistic an analogue and it is not backed up by the type system.
83This misguided analogue works for a single-dimension array but there is no advantage other than possibly teaching beginning programmers about basic runtime array-access.
84
85Continuing, a short form for declaring array variables exists using length information provided implicitly by an initializer.
86\lstinput{59-62}{bkgd-carray-arrty.c}
87The compiler counts the number of initializer elements and uses this value as the first dimension.
88Unfortunately, the implicit element counting does not extend to dimensions beyond the first.
89\lstinput{64-67}{bkgd-carray-arrty.c}
90
91My contribution is recognizing:
92\begin{itemize}
93        \item There is value in using a type that knows its size.
94        \item The type pointer to (first) element does not.
95        \item C \emph{has} a type that knows the whole picture: array, e.g. @T[10]@.
96        \item This type has all the usual derived forms, which also know the whole picture.
97        A usefully noteworthy example is pointer to array, e.g. @T (*)[10]@.\footnote{
98        The parenthesis are necessary because subscript has higher priority than pointer in C declarations.
99        (Subscript also has higher priority than dereference in C expressions.)}
100\end{itemize}
101
102
103\section{Reading declarations}
104
105A significant area of confusion for reading C declarations results from embedding a declared variable in a declaration, mimicking the way the variable is used in executable statements.
106\begin{cquote}
107\begin{tabular}{@{}ll@{}}
108\multicolumn{1}{@{}c}{\textbf{Array}} & \multicolumn{1}{c@{}}{\textbf{Function Pointer}} \\
109\begin{cfa}
110int @(*@ar@)[@5@]@; // definition
111  ... @(*@ar@)[@3@]@ += 1; // usage
112\end{cfa}
113&
114\begin{cfa}
115int @(*@f@())[@5@]@ { ... }; // definition
116  ... @(*@f@())[@3@]@ += 1; // usage
117\end{cfa}
118\end{tabular}
119\end{cquote}
120Essentially, the type is wrapped around the name in successive layers (like an \Index{onion}).
121While attempting to make the two contexts consistent is a laudable goal, it has not worked out in practice, even though Dennis Richie believed otherwise:
122\begin{quote}
123In spite of its difficulties, I believe that the C's approach to declarations remains plausible, and am comfortable with it; it is a useful unifying principle.~\cite[p.~12]{Ritchie93}
124\end{quote}
125After 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!
126
127\CFA provides its own type, variable and routine declarations, using a simpler syntax.
128The new declarations place qualifiers to the left of the base type, while C declarations place qualifiers to the right of the base type.
129The qualifiers have the same syntax and semantics in \CFA as in C.
130Then, a \CFA declaration is read left to right, where a function return type is enclosed in brackets @[@\,@]@.
131\begin{cquote}
132\begin{tabular}{@{}l@{\hspace{3em}}ll@{}}
133\multicolumn{1}{c@{\hspace{3em}}}{\textbf{C}}   & \multicolumn{1}{c}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{read left to right}}   \\
134\begin{cfa}
135int @*@ x1 @[5]@;
136int @(*@x2@)[5]@;
137int @(*@f( int p )@)[5]@;
138\end{cfa}
139&
140\begin{cfa}
141@[5] *@ int x1;
142@* [5]@ int x2;
143@[ * [5] int ]@ f( int p );
144\end{cfa}
145&
146\begin{cfa}
147// array of 5 pointers to int
148// pointer to array of 5 int
149// function returning pointer to array of 5 ints
150\end{cfa}
151\\
152& &
153\LstCommentStyle{//\ \ \ and taking an int argument}
154\end{tabular}
155\end{cquote}
156As declaration size increases, it becomes corresponding difficult to read and understand the C declaration form, whereas reading and understanding a \CFA declaration has linear complexity as the declaration size increases.
157Note, writing declarations left to right is common in other programming languages, where the function return-type is often placed after the parameter declarations.
158
159\VRef[Table]{bkgd:ar:usr:avp} introduces the many layers of the C and \CFA array story, where the \CFA story is discussion in \VRef[Chapter]{c:Array}.
160The \CFA-thesis column shows the new array declaration form, which is my contributed improvements for safety and ergonomics.
161The table shows there are multiple yet equivalent forms for the array types under discussion, and subsequent discussion shows interactions with orthogonal (but easily confused) language features.
162Each row of the table shows alternate syntactic forms.
163The simplest occurrences of types distinguished in the preceding discussion are marked with $\triangleright$.
164Removing the declared variable @x@, gives the type used for variable, structure field, cast or error messages \PAB{(though note Section TODO points out that some types cannot be casted to)}.
165Unfortunately, parameter declarations \PAB{(section TODO)} have more syntactic forms and rules.
166
167\begin{table}
168\centering
169\caption{Syntactic Reference for Array vs Pointer. Includes interaction with \lstinline{const}ness.}
170\label{bkgd:ar:usr:avp}
171\begin{tabular}{ll|l|l|l}
172        & Description & \multicolumn{1}{c|}{C} & \multicolumn{1}{c|}{\CFA}  & \multicolumn{1}{c}{\CFA-thesis} \\
173        \hline
174$\triangleright$ & value & @T x;@ & @T x;@ & \\
175        \hline
176        & immutable value & @const T x;@ & @const T x;@ & \\
177        & & @T const x;@ & @T const x;@ & \\
178        \hline \hline
179$\triangleright$ & pointer to value & @T * x;@ & @* T x;@ & \\
180        \hline
181        & immutable ptr. to val. & @T * const x;@ & @const * T x;@ & \\
182        \hline
183        & ptr. to immutable val. & @const T * x;@ & @* const T x;@ & \\
184        & & @T const * x;@ & @* T const x;@ & \\
185        \hline \hline
186$\triangleright$ & array of value & @T x[10];@ & @[10] T x@ & @array(T, 10) x@ \\
187        \hline
188        & ar.\ of immutable val. & @const T x[10];@ & @[10] const T x@ & @const array(T, 10) x@ \\
189        & & @T const x[10];@ & @[10] T const x@ & @array(T, 10) const x@ \\
190        \hline
191        & ar.\ of ptr.\ to value & @T * x[10];@ & @[10] * T x@ & @array(T *, 10) x@ \\
192        & & & & @array(* T, 10) x@ \\
193        \hline
194        & ar.\ of imm. ptr.\ to val. & @T * const x[10];@ & @[10] const * T x@ & @array(* const T, 10) x@ \\
195        & & & & @array(const * T, 10) x@ \\
196        \hline
197        & ar.\ of ptr.\ to imm. val. & @const T * x[10];@ & @[10] * const T x@ & @array(const T *, 10) x@ \\
198        & & @T const * x[10];@ & @[10] * T const x@ & @array(* const T, 10) x@ \\
199        \hline \hline
200$\triangleright$ & ptr.\ to ar.\ of value & @T (*x)[10];@ & @* [10] T x@ & @* array(T, 10) x@ \\
201        \hline
202        & imm. ptr.\ to ar.\ of val. & @T (* const x)[10];@ & @const * [10] T x@ & @const * array(T, 10) x@ \\
203        \hline
204        & ptr.\ to ar.\ of imm. val. & @const T (*x)[10];@ & @* [10] const T x@ & @* const array(T, 10) x@ \\
205        & & @T const (*x)[10];@ & @* [10] T const x@ & @* array(T, 10) const x@ \\
206        \hline
207        & ptr.\ to ar.\ of ptr.\ to val. & @T *(*x)[10];@ & @* [10] * T x@ & @* array(T *, 10) x@ \\
208        & & & & @* array(* T, 10) x@ \\
209        \hline
210\end{tabular}
211\end{table}
212
213TODO: Address these parked unfortunate syntaxes
214\begin{itemize}
215        \item static
216        \item star as dimension
217        \item under pointer decay: @int p1[const 3]@ being @int const *p1@
218\end{itemize}
219
220
221\subsection{Arrays decay and pointers diffract}
222
223The last section established the difference between these four types:
224\lstinput{3-6}{bkgd-carray-decay.c}
225But the expression used for obtaining the pointer to the first element is pedantic.
226The root of all C programmer experience with arrays is the shortcut
227\lstinput{8-8}{bkgd-carray-decay.c}
228which reproduces @pa0@, in type and value:
229\lstinput{9-9}{bkgd-carray-decay.c}
230The validity of this initialization is unsettling, in the context of the facts established in the last section.
231Notably, it initializes name @pa0x@ from expression @ar@, when they are not of the same type:
232\lstinput{10-10}{bkgd-carray-decay.c}
233
234So, C provides an implicit conversion from @float[10]@ to @float *@.
235\begin{quote}
236Except when it is the operand of the @sizeof@ operator, or the unary @&@ operator, or is a string literal used to
237initialize an array an expression that has type ``array of \emph{type}'' is converted to an expression with type
238``pointer to \emph{type}'' that points to the initial element of the array object~\cite[\S~6.3.2.1.3]{C11}
239\end{quote}
240This phenomenon is the famous \newterm{pointer decay}, which is a decay of an array-typed expression into a pointer-typed one.
241It is worthy to note that the list of exception cases does not feature the occurrence of @ar@ in @ar[i]@.
242Thus, subscripting happens on pointers not arrays.
243
244Subscripting proceeds first with pointer decay, if needed.  Next, \cite[\S~6.5.2.1.2]{C11} explains that @ar[i]@ is treated as if it were @(*((a)+(i)))@.
245\cite[\S~6.5.6.8]{C11} 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 @ar@ is big enough and @i@ is small enough.
246Finally, \cite[\S~6.5.3.2.4]{C11} explains that the @*@ operator's result is the referenced element.
247Taken together, these rules illustrate that @ar[i]@ and @i[a]@ mean the same thing!
248
249Subscripting a pointer when the target is standard inappropriate is still practically well-defined.
250While the standard affords a C compiler freedom about the meaning of an out-of-bound access, or of subscripting a pointer that does not refer to an array element at all,
251the fact that C is famously both generally high-performance, and specifically not bound-checked, leads to an expectation that the runtime handling is uniform across legal and illegal accesses.
252Moreover, consider the common pattern of subscripting on a @malloc@ result:
253\begin{cfa}
254float * fs = malloc( 10 * sizeof(float) );
255fs[5] = 3.14;
256\end{cfa}
257The @malloc@ behaviour is specified as returning a pointer to ``space for an object whose size is'' as requested (\cite[\S~7.22.3.4.2]{C11}).
258But \emph{nothing} more is said about this pointer value, specifically that its referent might \emph{be} an array allowing subscripting.
259
260Under this assumption, a pointer being subscripted (or added to, then dereferenced) by any value (positive, zero, or negative), gives a view of the program's entire address space, centred around the @p@ address, divided into adjacent @sizeof(*p)@ chunks, each potentially (re)interpreted as @typeof(*p)@.
261I call this phenomenon \emph{array diffraction}, which is a diffraction of a single-element pointer into the assumption that its target is in the middle of an array whose size is unlimited in both directions.
262No pointer is exempt from array diffraction.
263No array shows its elements without pointer decay.
264
265A further pointer--array confusion, closely related to decay, occurs in parameter declarations.
266\cite[\S~6.7.6.3.7]{C11} explains that when an array type is written for a parameter,
267the parameter's type becomes a type that can be summarized as the array-decayed type.
268The respective handling of the following two parameter spellings shows that the array-spelled one is really, like the other, a pointer.
269\lstinput{12-16}{bkgd-carray-decay.c}
270As the @sizeof(x)@ meaning changed, compared with when run on a similarly-spelled local variable declaration,
271@gcc@ also gives this code the warning for the first assertion:
272\begin{cfa}
273warning: 'sizeof' on array function parameter 'x' will return size of 'float *'
274\end{cfa}
275The caller of such a function is left with the reality that a pointer parameter is a pointer, no matter how it is spelled:
276\lstinput{18-21}{bkgd-carray-decay.c}
277This fragment gives the warning for the first argument, in the second call.
278\begin{cfa}
279warning: 'f' accessing 40 bytes in a region of size 4
280\end{cfa}
281
282The shortened parameter syntax @T x[]@ is a further way to spell ``pointer.''
283Note the opposite meaning of this spelling now, compared with its use in local variable declarations.
284This point of confusion is illustrated in:
285\lstinput{23-30}{bkgd-carray-decay.c}
286Note, \CC gives a warning for the initialization of @cp@.
287\begin{cfa}
288warning: ISO C++ forbids converting a string constant to 'char*'
289\end{cfa}
290and C gives a warning at the call of @edit@, if @const@ is added to the declaration of @cp@.
291\begin{cfa}
292warning: passing argument 1 of 'edit' discards 'const' qualifier from pointer target type
293\end{cfa}
294The basic two meanings, with a syntactic difference helping to distinguish,
295are illustrated in the declarations of @ca@ \vs @cp@,
296whose subsequent @edit@ calls behave differently.
297The syntax-caused confusion is in the comparison of the first and last lines,
298both of which use a literal to initialize an object declared with spelling @T x[]@.
299But these initialized declarations get opposite meanings,
300depending on whether the object is a local variable or a parameter.
301
302In summary, when a function is written with an array-typed parameter,
303\begin{itemize}
304        \item an appearance of passing an array by value is always an incorrect understanding
305        \item a dimension value, if any is present, is ignored
306        \item pointer decay is forced at the call site and the callee sees the parameter having the decayed type
307\end{itemize}
308
309Pointer decay does not affect pointer-to-array types, because these are already pointers, not arrays.
310As a result, a function with a pointer-to-array parameter sees the parameter exactly as the caller does:
311\lstinput{32-42}{bkgd-carray-decay.c}
312\VRef[Table]{bkgd:ar:usr:decay-parm} gives the reference for the decay phenomenon seen in parameter declarations.
313
314\begin{table}
315\caption{Syntactic Reference for Decay during Parameter-Passing.
316Includes interaction with \lstinline{const}ness, where ``immutable'' refers to a restriction on the callee's ability.}
317\label{bkgd:ar:usr:decay-parm}
318\centering
319\begin{tabular}{llllll}
320        & Description & Type & Parameter Declaration & \CFA  \\
321        \hline
322        & & & @T * x,@ & @* T x,@ \\
323$\triangleright$ & pointer to value & @T *@ & @T x[10],@ & @[10] T x,@ \\
324        & & & @T x[],@ & @[] T x,@ \\
325        \hline
326        & & & @T * const x,@ & @const * T x@ \\
327        & immutable ptr.\ to val. & @T * const@ & @T x[const 10],@ & @[const 10] T x,@ \\
328        & & & @T x[const],@ & @[const] T x,@\\
329        \hline
330        & & & @const T * x,@ & @ * const T x,@ \\
331        & &     & @T const * x,@ & @ * T const x,@ \\
332        & ptr.\ to immutable val. & @const T *@ & @const T x[10],@ & @[10] const T x,@ \\
333        & & @T const *@ & @T const x[10],@ &  @[10] T const x,@ \\
334        & & & @const T x[],@ & @[] const T x,@ \\
335        & & & @T const x[],@ & @[] T const x,@ \\
336        \hline \hline
337        & & & @T (*x)[10],@ & @* [10] T x,@ \\
338$\triangleright$ & ptr.\ to ar.\ of val. & @T(*)[10]@ & @T x[3][10],@ & @[3][10] T x,@ \\
339        & & & @T x[][10],@ & @[][10] T x,@ \\
340        \hline
341        & & & @T ** x,@ & @** T x,@ \\
342        & ptr.\ to ptr.\ to val. & @T **@ & @T * x[10],@ & @[10] * T x,@ \\
343        & & & @T * x[],@ & @[] * T x,@ \\
344        \hline
345        & ptr.\ to ptr.\ to imm.\ val. & @const char **@ & @const char * argv[],@ & @[] * const char argv,@ \\
346        & & & \emph{others elided} & \emph{others elided} \\
347        \hline
348\end{tabular}
349\end{table}
350
351
352\subsection{Multi-dimensional}
353
354As in the last section, multi-dimensional array declarations are examined.
355\lstinput{16-18}{bkgd-carray-mdim.c}
356The significant axis of deriving expressions from @ar@ is now ``itself,'' ``first element'' or ``first grand-element (meaning, first element of first element).''
357\lstinput{20-44}{bkgd-carray-mdim.c}
358
359
360\subsection{Lengths may vary, checking does not}
361
362When the desired number of elements is unknown at compile time, a variable-length array is a solution:
363\begin{cfa}
364int main( int argc, const char * argv[] ) {
365        assert( argc == 2 );
366        size_t n = atol( argv[1] );
367        assert( 0 < n );
368        float ar[n];
369        float b[10];
370        // ... discussion continues here
371}
372\end{cfa}
373This arrangement allocates @n@ elements on the @main@ stack frame for @ar@, called a \newterm{variable length array} (VLA), as well as 10 elements in the same stack frame for @b@.
374The variable-sized allocation of @ar@ is provided by the @alloca@ routine, which bumps the stack pointer.
375Note, the C standard supports VLAs~\cite[\S~6.7.6.2.4]{C11} as a conditional feature, but the \CC standard does not;
376both @gcc@ and @g++@ support VLAs.
377As well, there is misinformation about VLAs, \eg the stack size is limited (small), or VLAs cause stack failures or are inefficient.
378VLAs exist as far back as Algol W~\cite[\S~5.2]{AlgolW} and are a sound and efficient data type.
379
380For high-performance applications, the stack size can be fixed and small (coroutines or user-level threads).
381Here, VLAs can overflow the stack without appropriately sizing the stack, so a heap allocation is used.
382\begin{cfa}
383float * ax1 = malloc( sizeof( float[n] ) );
384float * ax2 = malloc( n * sizeof( float ) );    $\C{// arrays}$
385float * bx1 = malloc( sizeof( float[1000000] ) );
386float * bx2 = malloc( 1000000 * sizeof( float ) );
387\end{cfa}
388
389Parameter dependency
390
391Checking is best-effort / unsound
392
393Limited special handling to get the dimension value checked (static)
394
395
396\subsection{Dynamically sized, multidimensional arrays}
397
398In C and \CC, ``multidimensional array'' means ``array of arrays.''  Other meanings are discussed in TODO.
399
400Just as an array's element type can be @float@, so can it be @float[10]@.
401
402While any of @float*@, @float[10]@ and @float(*)[10]@ are easy to tell apart from @float@, telling them apart from each other may need occasional reference back to TODO intro section.
403The sentence derived by wrapping each type in @-[3]@ follows.
404
405While any of @float*[3]@, @float[3][10]@ and @float(*)[3][10]@ are easy to tell apart from @float[3]@,
406telling them apart from each other is what it takes to know what ``array of arrays'' really means.
407
408Pointer decay affects the outermost array only
409
410TODO: unfortunate syntactic reference with these cases:
411
412\begin{itemize}
413        \item ar. of ar. of val (be sure about ordering of dimensions when the declaration is dropped)
414        \item ptr. to ar. of ar. of val
415\end{itemize}
416
417
418\subsection{Arrays are (but) almost values}
419
420Has size; can point to
421
422Can't cast to
423
424Can't pass as value
425
426Can initialize
427
428Can wrap in aggregate
429
430Can't assign
431
432
433\subsection{Returning an array is (but) almost possible}
434
435
436\subsection{The pointer-to-array type has been noticed before}
437
438
439\section{Linked List}
440
441Linked-lists are blocks of storage connected using one or more pointers.
442The storage block is logically divided into data (user payload) and links (list pointers), where the links are the only component used by the list structure.
443Since the data is opaque, list structures are often polymorphic over the data, which is often homogeneous.
444
445Storage linking is used to build data structures, which are a group of nodes, containing data and links, organized in a particular format, with specific operations peculiar to that format, \eg queue, tree, hash table, \etc.
446Because a node's existence is independent of the data structure that organizes it, all nodes are manipulated by address not value;
447hence, all data structure routines take and return pointers to nodes and not the nodes themselves.
448
449
450\subsection{Design issues}
451\label{toc:lst:issue}
452
453This section introduces the design space for linked lists that target \emph{system programmers}.
454Within this restricted target, all design-issue discussions assume the following invariants.
455Alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}).
456\begin{itemize}
457        \item A doubly-linked list is being designed.
458                Generally, the discussed issues apply similarly for singly-linked lists.
459                Circular \vs ordered linking is discussed under List identity (Section~\ref{toc:lst:issue:ident}).
460        \item Link fields are system-managed.
461                The user works with the system-provided API to query and modify list membership.
462                The system has freedom over how to represent these links.
463        \item The user data must provide storage for the list link-fields.
464                Hence, a list node is \emph{statically} defined as data and links \vs a node that is \emph{dynamically} constructed from data and links \see{\VRef{toc:lst:issue:attach}}.
465\end{itemize}
466
467
468\subsection{Preexisting linked-list libraries}
469
470Two preexisting linked-list libraries are used throughout, to show examples of the concepts being defined,
471and further libraries are introduced as needed.
472\begin{enumerate}
473        \item Linux Queue library\cite{lst:linuxq} (LQ) of @<sys/queue.h>@.
474        \item \CC Standard Template Library's (STL)\footnote{The term STL is contentious as some people prefer the term standard library.} @std::list@\cite{lst:stl}
475\end{enumerate}
476%A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}).
477For the discussion, assume the fictional type @req@ (request) is the user's payload in examples.
478As well, the list library is helping the user manage (organize) requests, \eg a request can be work on the level of handling a network arrival event or scheduling a thread.
479
480
481\subsection{Link attachment: intrusive vs.\ wrapped}
482\label{toc:lst:issue:attach}
483
484Link attachment deals with the question:
485Where are the libraries' inter-element link fields stored, in relation to the user's payload data fields?
486\VRef[Figure]{fig:lst-issues-attach} shows three basic styles.
487\VRef[Figure]{f:Intrusive} shows the \newterm{intrusive} style, placing the link fields inside the payload structure.
488\VRef[Figures]{f:WrappedRef} and \subref*{f:WrappedValue} show the two \newterm{wrapped} styles, which place the payload inside a generic library-provided structure that then defines the link fields.
489The wrapped style distinguishes between wrapping a reference and wrapping a value, \eg @list<req *>@ or @list<req>@.
490(For this discussion, @list<req &>@ is similar to @list<req *>@.)
491This difference is one of user style, not framework capability.
492Library LQ is intrusive; STL is wrapped with reference and value.
493
494\begin{comment}
495\begin{figure}
496        \begin{tabularx}{\textwidth}{Y|Y|Y}
497                \lstinput[language=C]{20-39}{lst-issues-intrusive.run.c}
498                &\lstinputlisting[language=C++]{20-39}{lst-issues-wrapped-byref.run.cpp}
499                &\lstinputlisting[language=C++]{20-39}{lst-issues-wrapped-emplaced.run.cpp}
500          \\ & &
501          \\
502                \includegraphics[page=1]{lst-issues-attach.pdf}
503                &
504                \includegraphics[page=2]{lst-issues-attach.pdf}
505                &
506                \includegraphics[page=3]{lst-issues-attach.pdf}
507          \\ & &
508          \\
509                (a) & (b) & (c)
510        \end{tabularx}
511\caption{
512                Three styles of link attachment: (a)~intrusive, (b)~wrapped reference, and (c)~wrapped value.
513                The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
514                head objects are discussed in Section~\ref{toc:lst:issue:ident}.
515                In (a), the field \lstinline{req.x} names a list direction;
516                these are discussed in Section~\ref{toc:lst:issue:simultaneity}.
517                In (b) and (c), the type \lstinline{node} represents a system-internal type,
518                which is \lstinline{std::_List_node} in the GNU implementation.
519                (TODO: cite? found in  /usr/include/c++/7/bits/stl\_list.h )
520        }
521         \label{fig:lst-issues-attach}
522\end{figure}
523\end{comment}
524
525\begin{figure}
526\centering
527\newsavebox{\myboxA}                                    % used with subfigure
528\newsavebox{\myboxB}
529\newsavebox{\myboxC}
530
531\begin{lrbox}{\myboxA}
532\begin{tabular}{@{}l@{}}
533\lstinput[language=C]{20-35}{lst-issues-intrusive.run.c} \\
534\includegraphics[page=1]{lst-issues-attach.pdf}
535\end{tabular}
536\end{lrbox}
537
538\begin{lrbox}{\myboxB}
539\begin{tabular}{@{}l@{}}
540\lstinput[language=C++]{20-35}{lst-issues-wrapped-byref.run.cpp} \\
541\includegraphics[page=2]{lst-issues-attach.pdf}
542\end{tabular}
543\end{lrbox}
544
545\begin{lrbox}{\myboxC}
546\begin{tabular}{@{}l@{}}
547\lstinput[language=C++]{20-35}{lst-issues-wrapped-emplaced.run.cpp} \\
548\includegraphics[page=3]{lst-issues-attach.pdf}
549\end{tabular}
550\end{lrbox}
551
552\subfloat[Intrusive]{\label{f:Intrusive}\usebox\myboxA}
553\hspace{6pt}
554\vrule
555\hspace{6pt}
556\subfloat[Wrapped reference]{\label{f:WrappedRef}\usebox\myboxB}
557\hspace{6pt}
558\vrule
559\hspace{6pt}
560\subfloat[Wrapped value]{\label{f:WrappedValue}\usebox\myboxC}
561
562\caption{
563                Three styles of link attachment:
564                % \protect\subref*{f:Intrusive}~intrusive, \protect\subref*{f:WrappedRef}~wrapped reference, and \protect\subref*{f:WrappedValue}~wrapped value.
565                The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
566                head objects are discussed in Section~\ref{toc:lst:issue:ident}.
567                In \protect\subref*{f:Intrusive}, the field \lstinline{req.d} names a list direction;
568                these are discussed in Section~\ref{toc:lst:issue:simultaneity}.
569                In \protect\subref*{f:WrappedRef} and \protect\subref*{f:WrappedValue}, the type \lstinline{node} represents a
570                library-internal type, which is \lstinline{std::_List_node} in the GNU implementation
571                \see{\lstinline{/usr/include/c++/X/bits/stl_list.h}, where \lstinline{X} is the \lstinline{g++} version number}.
572        }
573        \label{fig:lst-issues-attach}
574\end{figure}
575
576Each diagrammed example is using the fewest dynamic allocations for its respective style:
577in intrusive, here is no dynamic allocation, in wrapped reference only the linked fields are dynamically allocated, and in wrapped value the copied data and linked fields are dynamically allocated.
578The advantage of intrusive is the control in memory layout and storage placement.
579Both wrapped styles have independent storage layout and imply library-induced heap allocations, with lifetime that matches the item's membership in the list.
580In all three cases, a @req@ object can enter and leave a list many times.
581However, in intrusive a @req@ can only be on one list at a time, unless there are separate link-fields for each simultaneous list.
582In wrapped reference, a @req@ can appear multiple times on the same or different lists simultaneously, but since @req@ is shared via the pointer, care must be taken if updating data also occurs simultaneously, \eg concurrency.
583In wrapped value, the @req@ is copied, which increases storage usage, but allows independent simultaneous changes;
584however, knowing which of the @req@ object is the ``true'' object becomes complex.
585\see*{\VRef{toc:lst:issue:simultaneity} for further discussion.}
586
587The implementation of @LIST_ENTRY@ uses a trick to find the links and the node containing the links.
588The macro @LIST_INSERT_HEAD(&reqs, &r2, d);@ takes the list header, a pointer to the node, and the offset of the link fields in the node.
589One of the fields generated by @LIST_ENTRY@ is a pointer to the node, which is set to the node address, \eg @r2@.
590Hence, the offset to the link fields provides an access to the entire node, \ie the node points at itself.
591For list traversal, @LIST_FOREACH(cur, &reqs_pri, by_pri)@, there is the node cursor, the list, and the offset of the link fields within the node.
592The traversal actually moves from link fields to link fields within a node and sets the node cursor from the pointer within the link fields back to the node.
593
594A further aspect of layout control is allowing the user to explicitly specify link fields controlling attributes and placement within the @req@ object.
595LQ allows this ability through the @LIST_ENTRY@ macro;\footnote{It is possible to have multiple named linked fields allowing a node to appear on multiple lists simultaneously.}
596supplying the link fields by inheritance makes them implicit and relies on compiler placement, such as the start or end of @req@.
597An example of an explicit attribute is cache alignment of the link fields in conjunction with other @req@ fields, improving locality and/or avoiding false sharing.
598Wrapped reference has no control over the link fields, but the separate data allows some control;
599wrapped value has no control over data or links.
600
601Another subtle advantage of intrusive arrangement is that a reference to a user-level item (@req@) is sufficient to navigate or manage the item's membership.
602In LQ, the intrusive @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
603there is no distinguishing a @req@ from ``a @req@ in a list.''
604The same is not true of STL, wrapped reference or value.
605There, the analogous operations, @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@, work on a parameter of type @list<T>::iterator@;
606There is no mapping from @req &@ to @list<req>::iterator@. %, for linear search.
607
608The advantage of wrapped is the abstraction of a data item from its list membership(s).
609In the wrapped style, the @req@ type can come from a library that serves many independent uses,
610which generally have no need for listing.
611Then, a novel use can put a @req@ in a list, without requiring any upstream change in the @req@ library.
612In intrusive, the ability to be listed must be planned during the definition of @req@.
613
614\begin{figure}
615        \lstinput[language=C++]{100-117}{lst-issues-attach-reduction.hpp}
616        \lstinput[language=C++]{150-150}{lst-issues-attach-reduction.hpp}
617        \caption{
618                Simulation of wrapped using intrusive.
619                Illustrated by pseudocode implementation of an STL-compatible API fragment using LQ as the underlying implementation.
620                The gap that makes it pseudocode is that
621                the LQ C macros do not expand to valid C++ when instantiated with template parameters---there is no \lstinline{struct El}.
622                When using a custom-patched version of LQ to work around this issue,
623                the programs of Figure~\ref{f:WrappedRef} and wrapped value work with this shim in place of real STL.
624                Their executions lead to the same memory layouts.
625        }
626        \label{fig:lst-issues-attach-reduction}
627\end{figure}
628
629It is possible to simulate wrapped using intrusive, illustrated in Figure~\ref{fig:lst-issues-attach-reduction}.
630This shim layer performs the implicit dynamic allocations that pure intrusion avoids.
631But there is no reduction going the other way.
632No shimming can cancel the allocations to which wrapped membership commits.
633
634Because intrusion is a lower-level listing primitive, the system design choice is not between forcing users to use intrusion or wrapping.
635The choice is whether or not to provide access to an allocation-free layer of functionality.
636An intrusive-primitive library like LQ lets users choose when to make this tradeoff.
637A wrapped-primitive library like STL forces users to incur the costs of wrapping, whether or not they access its benefits.
638
639
640\subsection{Simultaneity: single vs.\ multi-static vs.\ dynamic}
641\label{toc:lst:issue:simultaneity}
642
643\begin{figure}
644        \parbox[t]{3.5in} {
645                \lstinput[language=C++]{20-60}{lst-issues-multi-static.run.c}
646        }\parbox[t]{20in} {
647                ~\\
648                \includegraphics[page=1]{lst-issues-direct.pdf} \\
649                ~\\
650                \hspace*{1.5in}\includegraphics[page=2]{lst-issues-direct.pdf}
651        }
652        \caption{
653                Example of simultaneity using LQ lists.
654                The zoomed-out diagram (right/top) shows the complete multi-linked data structure.
655                This structure can navigate all requests in priority order ({\color{blue}blue}), and navigate among requests with a common request value ({\color{orange}orange}).
656                The zoomed-in diagram (right/bottom) shows how the link fields connect the nodes on different lists.
657        }
658        \label{fig:lst-issues-multi-static}
659\end{figure}
660
661\newterm{Simultaneity} deals with the question:
662In how many different lists can a node be stored, at the same time?
663Figure~\ref{fig:lst-issues-multi-static} shows an example that can traverse all requests in priority order (field @pri@) or navigate among requests with the same request value (field @rqr@).
664Each of ``by priority'' and ``by common request value'' is a separate list.
665For example, there is a single priority-list linked in order [1, 2, 2, 3, 3, 4], where nodes may have the same priority, and there are three common request-value lists combining requests with the same values: [42, 42], [17, 17, 17], and [99], giving four head nodes one for each list.
666The example shows a list can encompass all the nodes (by-priority) or only a subset of the nodes (three request-value lists).
667
668As stated, the limitation of intrusive is knowing apriori how many groups of links are needed for the maximum number of simultaneous lists.
669Thus, the intrusive LQ example supports multiple, but statically many, link lists.
670Note, it is possible to reuse links for different purposes, \eg if a list in linked one way at one time and another way at another time, and these times do not overlap, the two different linkings can use the same link fields.
671This feature is used in the \CFA runtime where a thread node may be on a blocked or running list, both never on both simultaneously.
672
673Now consider the STL in the wrapped-reference arrangement of Figure~\ref{f:WrappedRef}.
674Here it is possible to construct the same simultaneity by creating multiple STL lists, each pointing at the appropriate nodes.
675Each group of intrusive links become the links for each separate STL list.
676The upside is the unlimited number of a lists a node can be associated with simultaneously, any number of STL lists can be created dynamically.
677The downside is the dynamic allocation of the link nodes and managing multiple lists.
678Note, it might be possible to wrap the multiple lists in another type to hide this implementation issue.
679
680Now consider the STL in the wrapped-value arrangement of Figure~\ref{f:WrappedValue}.
681Again, it is possible to construct the same simultaneity by creating multiple STL lists, each copying the appropriate nodes, where the intrusive links become the links for each separate STL list.
682The upside is the same as for wrapped-reference arrangement with an unlimited number of a list bindings.
683The downside is the dynamic allocation and significant storage usage due to node copying.
684As well, it is unclear how node updates work in this scenario, without some notation of ultimately merging node information.
685
686% https://www.geeksforgeeks.org/introduction-to-multi-linked-list/ -- example of building a bespoke multi-linked list out of STL primitives (providing indication that STL doesn't offer one); offers dynamic directionality by embedding `vector<struct node*> pointers;`
687
688% When allowing multiple static directions, frameworks differ in their ergonomics for
689% the typical case: when the user needs only one direction, vs.\ the atypical case, when the user needs several.
690% LQ's ergonomics are well-suited to the uncommon case of multiple list directions.
691% Its intrusion declaration and insertion operation both use a mandatory explicit parameter naming the direction.
692% This decision works well in Figure~\ref{fig:lst-issues-multi-static}, where the names @by_pri@ and @by_rqr@ work well,
693% but it clutters Figure~\ref{f:Intrusive}, where a contrived name must be invented and used.
694% The example uses @x@; @reqs@ would be a more readily ignored choice. \PAB{wording?}
695
696\uCpp is a concurrent extension of \CC, which provides a basic set of intrusive lists~\cite[appx.~F]{uC++}, where the link fields are defined with the data fields using inheritance.
697\begin{cquote}
698\setlength{\tabcolsep}{15pt}
699\begin{tabular}{@{}ll@{}}
700\multicolumn{1}{c}{singly-linked list} & \multicolumn{1}{c}{doubly-linked list} \\
701\begin{c++}
702struct Node : public uColable {
703        int i;  // data
704        Node( int i ) : i{ i } {}
705};
706\end{c++}
707&
708\begin{c++}
709struct Node : public uSeqable {
710        int i;  // data
711        Node( int i ) : i{ i } {}
712};
713\end{c++}
714\end{tabular}
715\end{cquote}
716A node can be placed in the following data structures depending on its link fields: @uStack@ and @uQueue@ (singly linked), and @uSequence@ (doubly linked).
717A node inheriting from @uSeqable@ can appear in a singly or doubly linked structure.
718Structure operations implicitly know the link-field location through the inheritance.
719\begin{c++}
720uStack<Node> stack;
721Node node;
722stack.push( node );  // link fields at beginning of node
723\end{c++}
724
725Simultaneity cannot be done with multiple inheritance, because there is no mechanism to either know the order of inheritance fields or name each inheritance.
726Instead, a special type is require that contains the link fields and points at the node.
727\begin{cquote}
728\setlength{\tabcolsep}{10pt}
729\begin{tabular}{@{}ll@{}}
730\begin{c++}
731struct NodeDL : public uSeqable {
732        @Node & node;@  // node pointer
733        NodeDL( Node & node ) : node( node ) {}
734        Node & get() const { return node; }
735};
736\end{c++}
737&
738\begin{c++}
739struct Node : public uColable {
740        int i;  // data
741        @NodeDL nodeseq;@  // embedded intrusive links
742        Node( int i ) : i{ i }, @nodeseq{ this }@ {}
743};
744\end{c++}
745\end{tabular}
746\end{cquote}
747This node can now be inserted into a doubly-linked list through the embedded intrusive links.
748\begin{c++}
749uSequence<NodeDL> sequence;
750sequence.add_front( @node.nodeseq@ );   $\C{// link fields in embedded type}$
751NodeDL nodedl = sequence.remove( @node.nodeseq@ );
752int i = nodedl.@get()@.i;                               $\C{// indirection to node}$
753\end{c++}
754Hence, the \uCpp approach optimizes one set of intrusive links through the \CC inheritance mechanism, and falls back onto the LQ approach of explicit declarations for additional intrusive links.
755However, \uCpp cannot apply the LQ trick for finding the links and node.
756
757The major ergonomic difference among the approaches is naming and name usage.
758The intrusive model requires naming each set of intrusive links, \eg @by_pri@ and @by_rqr@ in \VRef[Figure]{fig:lst-issues-multi-static}.
759\uCpp cheats by using inheritance for the first intrusive links, after which explicit naming of intrusive links is required.
760Furthermore, these link names must be used in all list operations, including iterating, whereas wrapped reference and value hide the list names in the implicit dynamically-allocated node-structure.
761At issue is whether an API for simultaneity can support one list (when several are not wanted) to be \emph{implicit}.
762\uCpp allows it, LQ does not, and the STL does not have this question.
763
764
765\subsection{User integration: preprocessed vs.\ type-system mediated}
766
767% example of poor error message due to LQ's preprocessed integration
768% programs/lst-issues-multi-static.run.c:46:1: error: expected identifier or '(' before 'do'
769%    46 | LIST_INSERT_HEAD(&reqs_rtr_42, &r42b, by_rqr);
770%       | ^~~~~~~~~~~~~~~~
771%
772% ... not a wonderful example; it was a missing semicolon on the preceding line; but at least real
773
774
775\subsection{List identity: headed vs.\ ad-hoc}
776\label{toc:lst:issue:ident}
777
778All examples so far have used distinct user-facing types:
779an item found in a list (type @req@, of variables like @r1@), and
780a list (type @reql@ or @list<req>@, of variables like @reqs@ or @reqs_rqr_42@).
781\see{Figure~\ref{fig:lst-issues-attach} and Figure~\ref{fig:lst-issues-multi-static}}
782The latter type is a head, and these examples are of headed lists.
783
784A bespoke ``pointer to next @req@'' implementation often omits the latter type.
785The resulting identity model is ad-hoc.
786
787\begin{figure}
788        \centering
789        \includegraphics{lst-issues-ident.pdf}
790        \caption{
791                Comparison of headed and ad-hoc list identities, for various list lengths.
792                Pointers are logical, meaning that no claim is intended about which part of an object is being targeted.
793        }
794        \label{fig:lst-issues-ident}
795\end{figure}
796
797Figure~\ref{fig:lst-issues-ident} shows the identity model's impact on
798the existence of certain conceptual constructs, like zero-lengths lists and unlisted elements.
799In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
800In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
801
802By omitting the head, elements can enter into an adjacency relationship,
803without requiring that someone allocate room for the head of the possibly-resulting list,
804or being able to find a correct existing head.
805
806A head defines one or more element roles, among elements that share a transitive adjacency.
807``First'' and ``last'' are element roles.
808One moment's ``first'' need not be the next moment's.
809
810There is a cost to maintaining these roles.
811A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ vs.~@TAILQ@.
812Its @LIST@ maintains a ``first,'' but not a ``last;'' its @TAILQ@ maintains both roles.
813(Both types are doubly linked and an analogous choice is available for singly linked.)
814
815TODO: finish making this point
816
817See WIP in lst-issues-adhoc-*.ignore.*.
818
819The code-complexity component of the cost ...
820
821Ability to offer heads is good.  Point: Does maintaining a head mean that the user has to provide more state when manipulating the list?  Requiring the user to do so is bad, because the user may have lots of "list" typed variables in scope, and detecting that the user passed the wrong one requires testing all the listing edge cases.
822
823
824\subsection{End treatment: cased vs.\ uniform }
825
826This issue is implementation-level, relevant to achieving high performance.
827
828A linear (non-circular), nonempty linked list has a first element and a last element, whether or not the list is headed.
829A first element has no predecessor and a last element has no successor.
830
831\begin{figure}
832        \centering
833        \includegraphics{lst-issues-end.pdf}
834        \caption{
835                LQ sub-object-level representation of links and ends.
836                Each object's memory is pictured as a vertical strip.
837                Pointers' target locations, within these strips, are significant.
838                Uniform treatment of the first-end is evident from an assertion like \lstinline{(**this.pred == this)} holding for all nodes \lstinline{this}, including the first one.
839                Cased treatment of the last-end is evident from the symmetric proposition, \lstinline{(this.succ.pred == &this.succ)}, failing when \lstinline{this} is the last node.
840        }
841        \label{fig:lst-issues-end}
842\end{figure}
843
844End treatment refers to how the list represents the lack of a predecessor/successor.
845The following elaboration refers to the LQ representations, detailed in Figure~\ref{fig:lst-issues-end}.
846
847The most obvious representation, a null pointer, mandates a cased end treatment.
848LQ uses this representation for its successor/last.
849Consider the operation of inserting after a given element.
850A doubly-linked list must update the given node's successor, to make its predecessor-pointer to refer to the new node.
851This step must happen when the given node has a successor (when its successor pointer is non-null),
852and must be skipped when it does not (when its successor pointer cannot be navigated).
853So this operation contains a branch, to decide which case is happening.
854All branches have pathological cases where branch prediction's success rate is low and the execution pipeline is stalling often.
855
856This branch is sometimes avoidable; the result is a uniform end treatment.
857Here is one example of such an implementation; it works for a headed list.
858LQ uses uses this representation for its predecessor/first.  (All LQ offerings are headed at the front.)
859For predecessor/first navigation, the relevant operation is inserting before a given element.
860LQ's predecessor representation is not a pointer to a node, but a pointer to a pseudo-successor pointer.
861When there is a predecessor node, that node contains a real-successor pointer; it is the target of the reference node's predecessor pointer.
862When there is no predecessor node, the reference node (now known to be first node) acts as the pseudo-successor of the list head.
863The list head contains a pointer to the first node.
864When inserting before the first node, the list head's first-pointer is the one that must change.
865So, the first node's ``predecessor'' pointer (to a pseudo-successor pointer) is set as the list head's first-pointer.
866Now, inserting before a given element does the same logic in both cases:
867follow the guaranteed-non-null predecessor pointer, and update what you find there to refer to the new node.
868Applying this trick makes it possible to have list management routines that are completely free of control flow.
869Considering a path length of only a few instructions (less than the processor's pipeline length),
870such list management operations are often practically free,
871with all the variance being due to the (inevitable) cache status of the nodes being managed.
872
873\section{String}
874
875A string is a sequence of symbols, where the form of a symbol can vary significantly: 7/8-bit characters (ASCII/Latin-1), or 2/4/8-byte (UNICODE) characters/symbols or variable length (UTF-8/16/32) characters.
876A string can be read left-to-right, right-to-left, top-to-bottom, and have stacked elements (Arabic).
877
878A C character constant is an ASCII/Latin-1 character enclosed in single-quotes, \eg @'x'@, @'@\textsterling@'@.
879A wide C character constant is the same, except prefixed by the letter @L@, @u@, or @U@, \eg @u'\u25A0'@ (black square), where the @\u@ identifies a universal character name.
880A character can be formed from an escape sequence, which expresses a non-typable character @'\f'@ form feed, a delimiter character @'\''@ embedded single quote, or a raw character @'\xa3'@ \textsterling.
881
882A C character string is zero or more regular, wide, or escape characters enclosed in double-quotes @"xyz\n"@.
883The kind of characters in the string is denoted by a prefix: UTF-8 characters are prefixed by @u8@, wide characters are prefixed by @L@, @u@, or @U@.
884
885For UTF-8 string literals, the array elements have type @char@ and are initialized with the characters of the multibyte character sequences, \eg @u8"\xe1\x90\x87"@ (Canadian syllabics Y-Cree OO).
886For wide string literals prefixed by the letter @L@, the array elements have type @wchar_t@ and are initialized with the wide characters corresponding to the multibyte character sequence, \eg @L"abc@$\mu$@"@ and are read/printed using @wsanf@/@wprintf@.
887The value of a wide-character is implementation-defined, usually a UTF-16 character.
888For wide string literals prefixed by the letter @u@ or @U@, the array elements have type @char16_t@ or @char32_t@, respectively, and are initialized with wide characters corresponding to the multibyte character sequence, \eg @u"abc@$\mu$@"@, @U"abc@$\mu$@"@.
889The value of a @"u"@ character is an UTF-16 character;
890the value of a @"U"@ character is an UTF-32 character.
891The value of a string literal containing a multibyte character or escape sequence not represented in the execution character set is implementation-defined.
892
893C strings are null-terminated rather than maintaining a separate string length.
894\begin{quote}
895Technically, a string is an array whose elements are single characters.
896The compiler automatically places the null character @\0@ at the end of each such string, so programs can conveniently find the end.
897This representation means that there is no real limit to how long a string can be, but programs have to scan one completely to determine its length.~\cite[p.~36]{C:old}
898\end{quote}
899Unfortunately, this design decision is both unsafe and inefficient.
900It is common error in C to forget the storage in a character array for the terminator or overwrite the terminator, resulting in array overruns in string operations.
901The need to repeatedly scan an entire string to determine its length can result in significant cost, as it is impossible to cache the length in many cases.
902
903C strings are fixed size because arrays are used for the implementation.
904However, string manipulation commonly results in dynamically-sized temporary and final string values, \eg @strcpy@, @strcat@, @strcmp@, @strlen@, @strstr@, \etc.
905As a result, storage management for C strings is a nightmare, quickly resulting in array overruns and incorrect results.
906
907Collectively, these design decisions make working with strings in C, awkward, time consuming, and unsafe.
908While there are companion string routines that take the maximum lengths of strings to prevent array overruns, \eg @strncpy@, @strncat@, @strncpy@, that means the semantics of the operation can fail because strings are truncated.
909Suffice it to say, C is not a go-to language for string applications, which is why \CC introduced the dynamically-sized @string@ type.
Note: See TracBrowser for help on using the repository browser.