source: doc/rob_thesis/ctordtor.tex @ fbd7ad6

Last change on this file since fbd7ad6 was 7493339, checked in by Rob Schluntz <rschlunt@…>, 7 years ago

incorporate Peter's feedback, handle many TODOs

  • Property mode set to 100644
File size: 78.4 KB
2\chapter{Constructors and Destructors}
5% TODO: as an experiment, implement Andrei Alexandrescu's ScopeGuard
6% doesn't seem possible to do this without allowing ttype on generic structs?
8% If a Cforall constructor is in scope, C style initialization is
9% disabled by default.
10% * initialization rule: if any constructor is in scope for type T, try
11%   to find a matching constructor for the call. If there are no
12%   constructors in scope for type T, then attempt to fall back on
13%   C-style initialization.
14% + if this rule was not in place, it would be easy to accidentally
15%   use C-style initialization in certain cases, which could lead to
16%   subtle errors [2]
17% - this means we need special syntax if we want to allow users to force
18%   a C-style initialization (to give users more control)
19% - two different declarations in the same scope can be implicitly
20%   initialized differently. That is, there may be two objects of type
21%   T that are initialized differently because there is a constructor
22%   definition between them. This is not technically specific to
23%   constructors.
25% C-style initializers can be accessed with @= syntax
26% + provides a way to get around the requirement of using a constructor
27%   (for advanced programmers only)
28% - can break invariants in the type => unsafe
29% * provides a way of asserting that a variable is an instance of a
30%   C struct (i.e. a POD struct), and so will not be implicitly
31%   destructed (this can be useful at times, maybe mitigates the need
32%   for move semantics?) [3]
33% + can modernize a code base one step at a time
35% Cforall constructors can be used in expressions to initialize any
36% piece of memory.
37% + malloc() { ... } calls the appropriate constructor on the newly
38%   allocated space; the argument is moved into the constructor call
39%   without taking its address [4]
40% - with the above form, there is still no way to ensure that
41%   dynamically allocated objects are constructed. To resolve this,
42%   we might want a stronger "new" function which always calls the
43%   constructor, although how we accomplish that is currently still
44%   unresolved (compiler magic vs. better variadic functions?)
45% + This can be used as a placement syntax [5]
46% - can call the constructor on an object more than once, which could
47%   cause resource leaks and reinitialize const fields (can try to
48%   detect and prevent this in some cases)
49%   * compiler always tries to implicitly insert a ctor/dtor pair for
50%     non-@= objects.
51%     * For POD objects, this will resolve to an autogenerated or
52%       intrinsic function.
53%     * Intrinsic functions are not automatically called. Autogenerated
54%       are, because they may call a non-autogenerated function.
55%     * destructors are automatically inserted at appropriate branches
56%       (e.g. return, break, continue, goto) and at the end of the block
57%       in which they are declared.
58%   * For @= objects, the compiler never tries to interfere and insert
59%     constructor and destructor calls for that object. Copy constructor
60%     calls do not count, because the object is not the target of the copy
61%     constructor.
63% A constructor is declared with the name ?{}
64% + combines the look of C initializers with the precedent of ?() being
65%   the name for the function call operator
66% + it is possible to easily search for all constructors in a project
67%   and immediately know that a function is a constructor by seeing the
68%   name "?{}"
70% A destructor is declared with the name ^?{}
71% + name mirrors a constructor's name, with an extra symbol to
72%   distinguish it
73% - the symbol '~' cannot be used due to parsing conflicts with the
74%   unary '~' (bitwise negation) operator - this conflict exists because
75%   we want to allow users to write ^x{}; to destruct x, rather than
76%   ^?{}(&x);
78% The first argument of a constructor must be a pointer. The constructed
79% type is the base type of the pointer. E.g. void ?{}(T *) is a default
80% constructor for a T.
81% + can name the argument whatever you like, so not constrained by
82%   language keyword "this" or "self", etc.
83% - have to explicitly qualify all object members to initialize them
84%   (e.g. this->x = 0, rather than just x = 0)
86% Destructors can take arguments other than just the destructed pointer
87% * open research problem: not sure how useful this is
89% Pointer constructors
90% + can construct separately compiled objects (opaque types) [6]
91% + orthogonal design, follows directly from the definition of the first
92%   argument of a constructor
93% - may require copy constructor or move constructor (or equivalent)
94%   for correct implementation, which may not be obvious to everyone
95% + required feature for the prelude to specify as much behavior as possible
96%   (similar to pointer assignment operators in this respect)
98% Designations can only be used for C-style initialization
99% * designation for constructors is equivalent to designation for any
100%   general function call. Since a function prototype can be redeclared
101%   many times, with arguments named differently each time (or not at
102%   all!), this is considered to be an undesirable feature. We could
103%   construct some set of rules to allow this behaviour, but it is
104%   probably more trouble than it's worth, and no matter what we choose,
105%   it is not likely to be obvious to most people.
107% Constructing an anonymous member [7]
108% + same as with calling any other function on an anonymous member
109%   (implicit conversion by the compiler)
110% - may be some cases where this is ambiguous => clarify with a cast
111%   (try to design APIs to avoid sharing function signatures between
112%   composed types to avoid this)
114% Default Constructors and Destructors are called implicitly
115% + cannot forget to construct or destruct an object
116% - requires special syntax to specify that an object is not to be
117%   constructed (@=)
118% * an object will not be implicitly constructed OR destructed if
119%   explicitly initialized like a C object (@= syntax)
120% * an object will be destructed if there are no constructors in scope
121%   (even though it is initialized like a C object) [8]
123% An object which changes from POD type to non POD type will not change
124% the semantics of a type containing it by composition
125% * That is, constructors will not be regenerated at the point where
126%   an object changes from POD type to non POD type, because this could
127%   cause a cascade of constructors being regenerated for many other
128%   types. Further, there is precedence for this behaviour in other
129%   facets of Cforall's design, such as how nested functions interact.
130% * This behaviour can be simplified in a language without declaration
131%   before use, because a type can be classified as POD or non POD
132%   (rather than potentially changing between the two at some point) at
133%   at the global scope (which is likely the most common case)
134% * [9]
136% Changes to polymorphic type classes
137% * dtype and ftype remain the same
138% * forall(otype T) is currently essentially the same as
139%   forall(dtype T | { @size(T); void ?=?(T *, T); }).
140%   The big addition is that you can declare an object of type T, rather
141%   than just a pointer to an object of type T since you know the size,
142%   and you can assign into a T.
143%   * this definition is changed to add default constructor and
144%     destructor declarations, to remain consistent with what type meant
145%     before the introduction of constructors and destructors.
146%     * that is, forall(type T) is now essentially the same as
147%       forall(dtype T | { @size(T); void ?=?(T *, T);
148%                          void ?{}(T *); void ^?{}(T *); })
149%     + this is required to make generic types work correctly in
150%       polymorphic functions
151%     ? since declaring a constructor invalidates the autogenerated
152%       routines, it is possible for a type to have constructors, but
153%       not default constructors. That is, it might be the case that
154%       you want to write a polymorphic function for a type which has
155%       a size, but non-default constructors? Some options:
156%       * declaring a constructor as a part of the assertions list for
157%         a type declaration invalidates the default, so
158%         forall(otype T | { void ?{}(T *, int); })
159%         really means
160%         forall(dtype T | { @size(T); void ?=?(T *, T);
161%                            void ?{}(T *, int); void ^?{}(T *); })
162%       * force users to fully declare the assertions list like the
163%         above in this case (this seems very undesirable)
164%       * add another type class with the current desugaring of type
165%         (just size and assignment)
166%       * provide some way of subtracting from an existing assertions
167%         list (this might be useful to have in general)
169% Implementation issues:
170% Changes to prelude/autogen or built in defaults?
171% * pointer ctors/dtors [prelude]
172%   * other pointer type routines are declared in the prelude, and this
173%     doesn't seem like it should be any different
174% * basic type ctors/dtors [prelude]
175%   * other basic type routines are declared in the prelude, and this
176%     doesn't seem like it should be any different
177% ? aggregate types [undecided, but leaning towards autogenerate]
178%   * prelude
179%     * routines specific to aggregate types cannot be predeclared in
180%       the prelude because we don't know the name of every
181%       aggregate type in the entire program
182%   * autogenerate
183%     + default assignment operator is already autogenerated for
184%       aggregate types
185%       * this seems to lead us in the direction of autogenerating,
186%         because we may have a struct which contains other objects
187%         that require construction [10]. If we choose not to
188%         autogenerate in this case, then objects which are part of
189%         other objects by composition will not be constructed unless
190%         a constructor for the outer type is explicitly defined
191%       * in this case, we would always autogenerate the appropriate
192%         constructor(s) for an aggregate type, but just like with
193%         basic types, pointer types, and enum types, the constructor
194%         call can be elided when when it is not necessary.
195%     + constructors will have to be explicitly autogenerated
196%       in the case where they are required for a polymorphic function,
197%       when no user defined constructor is in scope, which may make it
198%       easiest to always autogenerate all appropriate constructors
199%     - n+2 constructors would have to be generated for a POD type
200%       * one constructor for each number of valid arguments [0, n],
201%         plus the copy constructor
202%         * this is taking a simplified approach: in C, it is possible
203%           to omit the enclosing braces in a declaration, which would
204%           lead to a combinatorial explosion of generated constructors.
205%           In the interest of keeping things tractable, Cforall may be
206%           incompatible with C in this case. [11]
207%       * for non-POD types, only autogenerate the default and copy
208%         constructors
209%       * alternative: generate only the default constructor and
210%         special case initialization for any other constructor when
211%         only the autogenerated one exists
212%         - this is not very sensible, as by the previous point, these
213%           constructors may be needed for polymorphic functions
214%           anyway.
215%     - must somehow distinguish in resolver between autogenerated and
216%       user defined constructors (autogenerated should never be chosen
217%       when a user defined option exists [check first parameter], even
218%       if full signature differs) (this may also have applications
219%       to other autogenerated routines?)
220%     - this scheme does not naturally support designation (i.e. general
221%       functions calls do not support designation), thus these cases
222%       will have to be treated specially in either case
223%   * defaults
224%     * i.e. hardcode a new set of rules for some "appropriate" default
225%       behaviour for
226%     + when resolving an initialization expression, explicitly check to
227%       see if any constructors are in scope. If yes, attempt to resolve
228%       to a constructor, and produce an error message if a match is not
229%       found. If there are no constructors in scope, resolve to
230%       initializing each field individually (C-style)
231%     + does not attempt to autogenerate constructors for POD types,
232%       which can be seen as a space optimization for the program
233%       binary
234%     - as stated previously, a polymorphic routine may require these
235%       autogenerated constructors, so this doesn't seem like a big win,
236%       because this leads to more complicated logic and tracking of
237%       which constructors have already been generated
238%     - even though a constructor is not explicitly declared or used
239%       polymorphically, we might still need one for all uses of a
240%       struct (e.g. in the case of composition).
241%   * the biggest tradeoff in autogenerating vs. defaulting appears to
242%     be in where and how the special code to check if constructors are
243%     present is handled. It appears that there are more reasons to
244%     autogenerate than not.
246% --- examples
247% [1] As an example of using constructors polymorphically, consider a
248% slight modification on the foldl example I put on the mailing list a
249% few months ago:
251% context iterable(type collection, type element, type iterator) {
252%   void ?{}(iterator *, collection); // used to be makeIterator, but can
253%                             // idiomatically use constructor
254%   int hasNext(iterator);
255%   iterator ++?(iterator *);
256%   lvalue element *?(iterator);
257% };
260% forall(type collection, type element, type result, type iterator
261%   | iterable(collection, element, iterator))
262% result foldl(collection c, result acc,
263%     result (*reduce)(result, element)) {
264%   iterator it = { c };
265%   while (hasNext(it)) {
266%     acc = reduce(acc, *it);
267%     ++it;
268%   }
269%   return acc;
270% }
272% Now foldl makes use of the knowledge that the iterator type has a
273% single argument constructor which takes the collection to iterate
274% over. This pattern allows polymorphic code to look more natural
275% (constructors are generally preferred to named initializer/creation
276% routines, e.g. "makeIterator")
278% [2] An example of some potentially dangerous code that we don't want
279% to let easily slip through the cracks - if this is really what you
280% want, then use @= syntax for the second declaration to quiet the
281% compiler.
283% struct A { int x, y, z; }
284% ?{}(A *, int);
285% ?{}(A *, int, int, int);
287% A a1 = { 1 };         // uses ?{}(A *, int);
288% A a2 = { 2, 3 };      // C-style initialization -> no invariants!
289% A a3 = { 4, 5, 6 };   // uses ?{}(A *, int, int, int);
291% [3] Since @= syntax creates a C object (essentially a POD, as far as
292% the compiler is concerned), the object will not be destructed
293% implicitly when it leaves scope, nor will it be copy constructed when
294% it is returned. In this case, a memcpy should be equivalent to a move.
296% // Box.h
297% struct Box;
298% void ?{}(Box **, int};
299% void ^?{}(Box **);
300% Box * make_fortytwo();
302% //
303% Box * make_fortytwo() {
304%   Box *b @= {};
305%   (&b){ 42 }; // construct explicitly
306%   return b; // no destruction, essentially a move?
307% }
309% [4] Cforall's typesafe malloc can be composed with constructor
310% expressions. It is possible for a user to define their own functions
311% similar to malloc and achieve the same effects (e.g. Aaron's example
312% of an arena allocator)
314% // CFA malloc
315% forall(type T)
316% T * malloc() { return (T *)malloc(sizeof(T)); }
318% struct A { int x, y, z; };
319% void ?{}(A *, int);
321% int foo(){
322%   ...
323%   // desugars to:
324%   // A * a = ?{}(malloc(), 123);
325%   A * a = malloc() { 123 };
326%   ...
327% }
329% [5] Aaron's example of combining function calls with constructor
330% syntax to perform an operation similar to C++'s std::vector::emplace
331% (i.e. to construct a new element in place, without the need to
332% copy)
334% forall(type T)
335% struct vector {
336%   T * elem;
337%   int len;
338%   ...
339% };
341% ...
342% forall(type T)
343% T * vector_new(vector(T) * v) {
344%   // reallocate if needed
345%   return &v->elem[len++];
346% }
348% int main() {
349%   vector(int) * v = ...
350%   vector_new(v){ 42 };  // add element to the end of vector
351% }
353% [6] Pointer Constructors. It could be useful to use the existing
354% constructor syntax even more uniformly for ADTs. With this, ADTs can
355% be initialized in the same manor as any other object in a polymorphic
356% function.
358% // vector.h
359% forall(type T) struct vector;
360% forall(type T) void ?{}(vector(T) **);
361% // adds an element to the end
362% forall(type T) vector(T) * ?+?(vector(T) *, T);
364% //
365% // don't want to expose the implementation to the user and/or don't
366% // want to recompile the entire program if the struct definition
367% // changes
369% forall(type T) struct vector {
370%   T * elem;
371%   int len;
372%   int capacity;
373% };
375% forall(type T) void resize(vector(T) ** v) { ... }
377% forall(type T) void ?{}(vector(T) ** v) {
378%   vector(T) * vect = *v = malloc();
379%   vect->capacity = 10;
380%   vect->len = 0;
381%   vect->elem = malloc(vect->capacity);
382% }
384% forall(type T) vector(T) * ?+?(vector(T) *v, T elem) {
385%   if (v->len == v->capacity) resize(&v);
386%   v->elem[v->len++] = elem;
387% }
389% //
390% #include "adt.h"
391% forall(type T | { T ?+?(T, int); }
392% T sumRange(int lower, int upper) {
393%   T x;    // default construct
394%   for (int i = lower; i <= upper; i++) {
395%     x = x + i;
396%   }
397%   return x;
398% }
400% int main() {
401%   vector(int) * numbers = sumRange(1, 10);
402%   // numbers is now a vector containing [1..10]
404%   int sum = sumRange(1, 10);
405%   // sum is now an int containing the value 55
406% }
408% [7] The current proposal is to use the plan 9 model of inheritance.
409% Under this model, all of the members of an unnamed struct instance
410% become members of the containing struct. In addition, an object
411% can be passed as an argument to a function expecting one of its
412% base structs.
414% struct Point {
415%   double x;
416%   double y;
417% };
419% struct ColoredPoint {
420%   Point;        // anonymous member (no identifier)
421%                 // => a ColoredPoint has an x and y of type double
422%   int color;
423% };
425% ColoredPoint cp = ...;
426% cp.x = 10.3;    // x from Point is accessed directly
427% cp.color = 0x33aaff; // color is accessed normally
428% foo(cp);        // cp can be used directly as a Point
430% void ?{}(Point *p, double x, double y) {
431%   p->x = x;
432%   p->y = y;
433% }
435% void ?{}(ColoredPoint *cp, double x, double y, int color) {
436%   (&cp){ x, y };  // unambiguous, no ?{}(ColoredPoint*,double,double)
437%   cp->color = color;
438% }
440% struct Size {
441%   double width;
442%   double height;
443% };
445% void ?{}(Size *s, double w, double h) {
446%   p->width = w;
447%   p->height = h;
448% }
450% struct Foo {
451%   Point;
452%   Size;
453% }
455% ?{}(Foo &f, double x, double y, double w, double h) {
456%   // (&F,x,y) is ambiguous => is it ?{}(Point*,double,double) or
457%   // ?{}(Size*,double,double)? Solve with a cast:
458%   ((Point*)&F){ x, y };
459%   ((Size*)&F){ w, h };
460% }
462% [8] Destructors will be called on objects that were not constructed.
464% struct A { ... };
465% ^?{}(A *);
466% {
467%   A x;
468%   A y @= {};
469% } // x is destructed, even though it wasn't constructed
470%   // y is not destructed, because it is explicitly a C object
473% [9] A type's constructor is generated at declaration time using
474% current information about an object's members. This is analogous to
475% the treatment of other operators. For example, an object's assignment
476% operator will not change to call the override of a member's assignment
477% operator unless the object's assignment is also explicitly overridden.
478% This problem can potentially be treated differently in Do, since each
479% compilation unit is passed over at least twice (once to gather
480% symbol information, once to generate code - this is necessary to
481% achieve the "No declarations" goal)
483% struct A { ... };
484% struct B { A x; };
485% ...
486% void ?{}(A *);  // from this point on, A objects will be constructed
487% B b1;           // b1 and b1.x are both NOT constructed, because B
488%                 // objects are not constructed
489% void ?{}(B *);  // from this point on, B objects will be constructed
490% B b2;           // b2 and b2.x are both constructed
492% struct C { A x; };
493% // implicit definition of ?{}(C*), because C is not a POD type since
494% // it contains a non-POD type by composition
495% C c;            // c and c.x are both constructed
497% [10] Requiring construction by composition
499% struct A {
500%   ...
501% };
503% // declared ctor disables default c-style initialization of
504% // A objects; A is no longer a POD type
505% void ?{}(A *);
507% struct B {
508%   A x;
509% };
511% // B objects can not be C-style initialized, because A objects
512% // must be constructed => B objects are transitively not POD types
513% B b; // b.x must be constructed, but B is not constructible
514%      // => must autogenerate ?{}(B *) after struct B definition,
515%      // which calls ?{}(&b.x)
517% [11] Explosion in the number of generated constructors, due to strange
518% C semantics.
520% struct A { int x, y; };
521% struct B { A u, v, w; };
523% A a = { 0, 0 };
525% // in C, you are allowed to do this
526% B b1 = { 1, 2, 3, 4, 5, 6 };
527% B b2 = { 1, 2, 3 };
528% B b3 = { a, a, a };
529% B b4 = { a, 5, 4, a };
530% B b5 = { 1, 2, a, 3 };
532% // we want to disallow b1, b2, b4, and b5 in Cforall.
533% // In particular, we will autogenerate these constructors:
534% void ?{}(A *);             // default/0 parameters
535% void ?{}(A *, int);        // 1 parameter
536% void ?{}(A *, int, int);   // 2 parameters
537% void ?{}(A *, const A *);  // copy constructor
539% void ?{}(B *);             // default/0 parameters
540% void ?{}(B *, A);          // 1 parameter
541% void ?{}(B *, A, A);       // 2 parameters
542% void ?{}(B *, A, A, A);    // 3 parameters
543% void ?{}(B *, const B *);  // copy constructor
545% // we will not generate constructors for every valid combination
546% // of members in C. For example, we will not generate
547% void ?{}(B *, int, int, int, int, int, int);   // b1 would need this
548% void ?{}(B *, int, int, int);                  // b2 would need this
549% void ?{}(B *, A, int, int, A);                 // b4 would need this
550% void ?{}(B *, int, int, A, int);               // b5 would need this
551% // and so on
553Since \CFA is a true systems language, it does not provide a garbage collector.
554As well, \CFA is not an object-oriented programming language, i.e., structures cannot have routine members.
555Nevertheless, one important goal is to reduce programming complexity and increase safety.
556To that end, \CFA provides support for implicit pre/post-execution of routines for objects, via constructors and destructors.
558This chapter details the design of constructors and destructors in \CFA, along with their current implementation in the translator.
559Generated code samples have been edited to provide comments for clarity and to save on space.
561\section{Design Criteria}
563In designing constructors and destructors for \CFA, the primary goals were ease of use and maintaining backwards compatibility.
565In C, when a variable is defined, its value is initially undefined unless it is explicitly initialized or allocated in the static area.
567int main() {
568  int x;        // uninitialized
569  int y = 5;    // initialized to 5
570  x = y;        // assigned 5
571  static int z; // initialized to 0
574In the example above, @x@ is defined and left uninitialized, while @y@ is defined and initialized to 5.
575Next, @x@ is assigned the value of @y@.
576In the last line, @z@ is implicitly initialized to 0 since it is marked @static@.
577The key difference between assignment and initialization being that assignment occurs on a live object (i.e., an object that contains data).
578It is important to note that this means @x@ could have been used uninitialized prior to being assigned, while @y@ could not be used uninitialized.
579Use of uninitialized variables yields undefined behaviour, which is a common source of errors in C programs.
581Declaration initialization is insufficient, because it permits uninitialized variables to exist and because it does not allow for the insertion of arbitrary code before a variable is live.
582Many C compilers give good warnings for uninitialized variables most of the time, but they cannot in all cases.
584int f(int *);  // output parameter: never reads, only writes
585int g(int *);  // input parameter: never writes, only reads,
586               // so requires initialized variable
588int x, y;
589f(&x);  // okay - only writes to x
590g(&y);  // uses y uninitialized
592Other languages are able to give errors in the case of uninitialized variable use, but due to backwards compatibility concerns, this is not the case in \CFA.
594In C, constructors and destructors are often mimicked by providing routines that create and teardown objects, where the teardown function is typically only necessary if the type modifies the execution environment.
596struct array_int {
597  int * x;
599struct array_int create_array(int sz) {
600  return (struct array_int) { calloc(sizeof(int)*sz) };
602void destroy_rh(struct resource_holder * rh) {
603  free(rh->x);
606This idiom does not provide any guarantees unless the structure is opaque, which then requires that all objects are heap allocated.
608struct opqaue_array_int;
609struct opqaue_array_int * create_opqaue_array(int sz);
610void destroy_opaque_array(opaque_array_int *);
611int opaque_get(opaque_array_int *);  // subscript
613opaque_array_int * x = create_opaque_array(10);
614int x2 = opaque_get(x, 2);
616This pattern is cumbersome to use since every access becomes a function call.
617While useful in some situations, this compromise is too restrictive.
618Furthermore, even with this idiom it is easy to make mistakes, such as forgetting to destroy an object or destroying it multiple times.
620A constructor provides a way of ensuring that the necessary aspects of object initialization is performed, from setting up invariants to providing compile-time checks for appropriate initialization parameters.
621This goal is achieved through a guarantee that a constructor is called implicitly after every object is allocated from a type with associated constructors, as part of an object's definition.
622Since a constructor is called on every object of a managed type, it is impossible to forget to initialize such objects, as long as all constructors perform some sensible form of initialization.
624In \CFA, a constructor is a function with the name @?{}@.
625Like other operators in \CFA, the name represents the syntax used to call the constructor, e.g., @struct S = { ... };@.
626Every constructor must have a return type of @void@ and at least one parameter, the first of which is colloquially referred to as the \emph{this} parameter, as in many object-oriented programming-languages (however, a programmer can give it an arbitrary name).
627The @this@ parameter must have a pointer type, whose base type is the type of object that the function constructs.
628There is precedence for enforcing the first parameter to be the @this@ parameter in other operators, such as the assignment operator, where in both cases, the left-hand side of the equals is the first parameter.
629There is currently a proposal to add reference types to \CFA.
630Once this proposal has been implemented, the @this@ parameter will become a reference type with the same restrictions.
632Consider the definition of a simple type encapsulating a dynamic array of @int@s.
635struct Array {
636  int * data;
637  int len;
641In C, if the user creates an @Array@ object, the fields @data@ and @len@ are uninitialized, unless an explicit initializer list is present.
642It is the user's responsibility to remember to initialize both of the fields to sensible values, since there are no implicit checks for invalid values or reasonable defaults.
643In \CFA, the user can define a constructor to handle initialization of @Array@ objects.
646void ?{}(Array * arr){
647  arr->len = 10;    // default size
648  arr->data = malloc(sizeof(int)*arr->len);
649  for (int i = 0; i < arr->len; ++i) {
650    arr->data[i] = 0;
651  }
653Array x;  // allocates storage for Array and calls ?{}(&x)
656This constructor initializes @x@ so that its @length@ field has the value 10, and its @data@ field holds a pointer to a block of memory large enough to hold 10 @int@s, and sets the value of each element of the array to 0.
657This particular form of constructor is called the \emph{default constructor}, because it is called on an object defined without an initializer.
658In other words, a default constructor is a constructor that takes a single argument: the @this@ parameter.
660In \CFA, a destructor is a function much like a constructor, except that its name is \lstinline!^?{}!.
661A destructor for the @Array@ type can be defined as such.
663void ^?{}(Array * arr) {
664  free(arr->data);
667The destructor is automatically called at deallocation for all objects of type @Array@.
668Hence, the memory associated with an @Array@ is automatically freed when the object's lifetime ends.
669The exact guarantees made by \CFA with respect to the calling of destructors are discussed in section \ref{sub:implicit_dtor}.
671As discussed previously, the distinction between initialization and assignment is important.
672Consider the following example.
674Array x, y;
675Array z = x;  // initialization
676y = x;        // assignment
678By the previous definition of the default constructor for @Array@, @x@ and @y@ are initialized to valid arrays of length 10 after their respective definitions.
679On line 2, @z@ is initialized with the value of @x@, while on line 3, @y@ is assigned the value of @x@.
680The key distinction between initialization and assignment is that a value to be initialized does not hold any meaningful values, whereas an object to be assigned might.
681In particular, these cases cannot be handled the same way because in the former case @z@ does not currently own an array, while @y@ does.
683\begin{cfacode}[emph={other}, emphstyle=\color{red}]
684void ?{}(Array * arr, Array other) {  // copy constructor
685  arr->len = other.len;               // initialization
686  arr->data = malloc(sizeof(int)*arr->len)
687  for (int i = 0; i < arr->len; ++i) {
688    arr->data[i] =[i];     // copy from other object
689  }
691Array ?=?(Array * arr, Array other) { // assignment
692  ^?{}(arr);                          // explicitly call destructor
693  ?{}(arr, other);                    // explicitly call constructor
694  return *arr;
697The two functions above handle these cases.
698The first function is called a \emph{copy constructor}, because it constructs its argument by copying the values from another object of the same type.
699The second function is the standard copy-assignment operator.
700The four functions (default constructor, destructor, copy constructor, and assignment operator) are special in that they safely control the state of most objects.
702It is possible to define a constructor that takes any combination of parameters to provide additional initialization options.
703For example, a reasonable extension to the array type would be a constructor that allocates the array to a given initial capacity and initializes the array to a given @fill@ value.
705void ?{}(Array * arr, int capacity, int fill) {
706  arr->len = capacity;
707  arr->data = malloc(sizeof(int)*arr->len);
708  for (int i = 0; i < arr->len; ++i) {
709    arr->data[i] = fill;
710  }
713In \CFA, constructors are called implicitly in initialization contexts.
715Array x, y = { 20, 0xdeadbeef }, z = y;
718In \CFA, constructor calls look just like C initializers, which allows them to be inserted into legacy C code with minimal code changes, and also provides a very simple syntax that veteran C programmers are familiar with.
719One downside of reusing C initialization syntax is that it isn't possible to determine whether an object is constructed just by looking at its declaration, since that requires knowledge of whether the type is managed at that point.
721This example generates the following code
723Array x;
724?{}(&x);                  // implicit default construct
725Array y;
726?{}(&y, 20, 0xdeadbeef);  // explicit fill construct
727Array z;
728?{}(&z, y);               // copy construct
729^?{}(&z);                 // implicit destruct
730^?{}(&y);                 // implicit destruct
731^?{}(&x);                 // implicit destruct
733Due to the way that constructor calls are interleaved, it is impossible for @y@ to be referenced before it is initialized, except in its own constructor.
734This loophole is minor and exists in \CC as well.
735Destructors are implicitly called in reverse declaration-order so that objects with dependencies are destructed before the objects they are dependent on.
737\subsection{Calling Syntax}
739There are several ways to construct an object in \CFA.
740As previously introduced, every variable is automatically constructed at its definition, which is the most natural way to construct an object.
742struct A { ... };
743void ?{}(A *);
744void ?{}(A *, A);
745void ?{}(A *, int, int);
747A a1;             // default constructed
748A a2 = { 0, 0 };  // constructed with 2 ints
749A a3 = a1;        // copy constructed
750// implicitly destruct a3, a2, a1, in that order
752Since constructors and destructors are just functions, the second way is to call the function directly.
754struct A { int a; };
755void ?{}(A *);
756void ?{}(A *, A);
757void ^?{}(A *);
759A x;               // implicitly default constructed: ?{}(&x)
760A * y = malloc();  // copy construct: ?{}(&y, malloc())
762?{}(&x);    // explicit construct x, second construction
763?{}(y, x);  // explit construct y from x, second construction
764^?{}(&x);   // explicit destroy x, in different order
765^?{}(y);    // explicit destroy y
767// implicit ^?{}(&y);
768// implicit ^?{}(&x);
770Calling a constructor or destructor directly is a flexible feature that allows complete control over the management of storage.
771In particular, constructors double as a placement syntax.
773struct A { ... };
774struct memory_pool { ... };
775void ?{}(memory_pool *, size_t);
777memory_pool pool = { 1024 };  // create an arena of size 1024
779A * a = allocate(&pool);      // allocate from memory pool
780?{}(a);                       // construct an A in place
782for (int i = 0; i < 10; i++) {
783  // reuse storage rather than reallocating
784  ^?{}(a);
785  ?{}(a);
786  // use a ...
789deallocate(&pool, a);         // return to memory pool
791Finally, constructors and destructors support \emph{operator syntax}.
792Like other operators in \CFA, the function name mirrors the use-case, in that the first $N$ arguments fill in the place of the question mark.
793This syntactic form is similar to the new initialization syntax in \CCeleven, except that it is used in expression contexts, rather than declaration contexts.
795struct A { ... };
796struct B { A a; };
798A x, y, * z = &x;
799(&x){}          // default construct
800(&x){ y }       // copy construct
801(&x){ 1, 2, 3 } // construct with 3 arguments
802z{ y };         // copy construct x through a pointer
803^(&x){}         // destruct
805void ?{}(B * b) {
806  (&b->a){ 11, 17, 13 };  // construct a member
809Constructor operator syntax has relatively high precedence, requiring parentheses around an address-of expression.
810Destructor operator syntax is actually an statement, and requires parentheses for symmetry with constructor syntax.
812One of these three syntactic forms should appeal to either C or \CC programmers using \CFA.
814\subsection{Function Generation}
815In \CFA, every type is defined to have the core set of four functions described previously.
816Having these functions exist for every type greatly simplifies the semantics of the language, since most operations can simply be defined directly in terms of function calls.
817In addition to simplifying the definition of the language, it also simplifies the analysis that the translator must perform.
818If the translator can expect these functions to exist, then it can unconditionally attempt to resolve them.
819Moreover, the existence of a standard interface allows polymorphic code to interoperate with new types seamlessly.
821To mimic the behaviour of standard C, the default constructor and destructor for all of the basic types and for all pointer types are defined to do nothing, while the copy constructor and assignment operator perform a bitwise copy of the source parameter (as in \CC).
823There are several options for user-defined types: structures, unions, and enumerations.
824To aid in ease of use, the standard set of four functions is automatically generated for a user-defined type after its definition is completed.
825By auto-generating these functions, it is ensured that legacy C code continues to work correctly in every context where \CFA expects these functions to exist, since they are generated for every complete type.
827The generated functions for enumerations are the simplest.
828Since enumerations in C are essentially just another integral type, the generated functions behave in the same way that the builtin functions for the basic types work.
829For example, given the enumeration
831enum Colour {
832  R, G, B
835The following functions are automatically generated.
837void ?{}(enum Colour *_dst){
838  // default constructor does nothing
840void ?{}(enum Colour *_dst, enum Colour _src){
841  (*_dst)=_src;  // bitwise copy
843void ^?{}(enum Colour *_dst){
844  // destructor does nothing
846enum Colour ?=?(enum Colour *_dst, enum Colour _src){
847  return (*_dst)=_src; // bitwise copy
850In the future, \CFA will introduce strongly-typed enumerations, like those in \CC.
851The existing generated routines are sufficient to express this restriction, since they are currently set up to take in values of that enumeration type.
852Changes related to this feature only need to affect the expression resolution phase, where more strict rules will be applied to prevent implicit conversions from integral types to enumeration types, but should continue to permit conversions from enumeration types to @int@.
853In this way, it is still possible to add an @int@ to an enumeration, but the resulting value is an @int@, meaning it cannot be reassigned to an enumeration without a cast.
855For structures, the situation is more complicated.
856Given a structure @S@ with members @M$_0$@, @M$_1$@, ... @M$_{N-1}$@, each function @f@ in the standard set calls \lstinline{f(s->M$_i$, ...)} for each @$i$@.
857That is, a default constructor for @S@ default constructs the members of @S@, the copy constructor copy constructs them, and so on.
858For example, given the structure definition
860struct A {
861  B b;
862  C c;
865The following functions are implicitly generated.
867void ?{}(A * this) {
868  ?{}(&this->b);  // default construct each field
869  ?{}(&this->c);
871void ?{}(A * this, A other) {
872  ?{}(&this->b, other.b);  // copy construct each field
873  ?{}(&this->c, other.c);
875A ?=?(A * this, A other) {
876  ?=?(&this->b, other.b);  // assign each field
877  ?=?(&this->c, other.c);
879void ^?{}(A * this) {
880  ^?{}(&this->c);  // destruct each field
881  ^?{}(&this->b);
884It is important to note that the destructors are called in reverse declaration order to prevent conflicts in the event there are dependencies among members.
886In addition to the standard set, a set of \emph{field constructors} is also generated for structures.
887The field constructors are constructors that consume a prefix of the structure's member-list.
888That is, $N$ constructors are built of the form @void ?{}(S *, T$_{\text{M}_0}$)@, @void ?{}(S *, T$_{\text{M}_0}$, T$_{\text{M}_1}$)@, ..., @void ?{}(S *, T$_{\text{M}_0}$, T$_{\text{M}_1}$, ..., T$_{\text{M}_{N-1}}$)@, where members are copy constructed if they have a corresponding positional argument and are default constructed otherwise.
889The addition of field constructors allows structures in \CFA to be used naturally in the same ways as used in C (i.e., to initialize any prefix of the structure), e.g., @A a0 = { b }, a1 = { b, c }@.
890Extending the previous example, the following constructors are implicitly generated for @A@.
892void ?{}(A * this, B b) {
893  ?{}(&this->b, b);
894  ?{}(&this->c);
896void ?{}(A * this, B b, C c) {
897  ?{}(&this->b, b);
898  ?{}(&this->c, c);
902For unions, the default constructor and destructor do nothing, as it is not obvious which member, if any, should be constructed.
903For copy constructor and assignment operations, a bitwise @memcpy@ is applied.
904In standard C, a union can also be initialized using a value of the same type as its first member, and so a corresponding field constructor is generated to perform a bitwise @memcpy@ of the object.
905An alterantive to this design is to always construct and destruct the first member of a union, to match with the C semantics of initializing the first member of the union.
906This approach ultimately feels subtle and unsafe.
907Another option is to, like \CC, disallow unions from containing members that are themselves managed types.
908This restriction is a reasonable approach from a safety standpoint, but is not very C-like.
909Since the primary purpose of a union is to provide low-level memory optimization, it is assumed that the user has a certain level of maturity.
910It is therefore the responsibility of the user to define the special functions explicitly if they are appropriate, since it is impossible to accurately predict the ways that a union is intended to be used at compile-time.
912For example, given the union
914union X {
915  Y y;
916  Z z;
919The following functions are automatically generated.
921void ?{}(union X *_dst){  // default constructor
923void ?{}(union X *_dst, union X _src){  // copy constructor
924  __builtin_memcpy(_dst, &_src, sizeof(union X ));
926void ^?{}(union X *_dst){  // destructor
928union X ?=?(union X *_dst, union X _src){  // assignment
929  __builtin_memcpy(_dst, &_src, sizeof(union X));
930  return _src;
932void ?{}(union X *_dst, struct Y src){  // construct first field
933  __builtin_memcpy(_dst, &src, sizeof(struct Y));
937% This feature works in the \CFA model, since constructors are simply special functions and can be called explicitly, unlike in \CC. % this sentence isn't really true => placement new
938In \CCeleven, unions may have managed members, with the caveat that if there are any members with a user-defined operation, then that operation is not implicitly defined, forcing the user to define the operation if necessary.
939This restriction could easily be added into \CFA once \emph{deleted} functions are added.
941\subsection{Using Constructors and Destructors}
942Implicitly generated constructor and destructor calls ignore the outermost type qualifiers, e.g. @const@ and @volatile@, on a type by way of a cast on the first argument to the function.
943For example,
945struct S { int i; };
946void ?{}(S *, int);
947void ?{}(S *, S);
949const S s = { 11 };
950volatile S s2 = s;
952Generates the following code
954const struct S s;
955?{}((struct S *)&s, 11);
956volatile struct S s2;
957?{}((struct S *)&s2, s);
959Here, @&s@ and @&s2@ are cast to unqualified pointer types.
960This mechanism allows the same constructors and destructors to be used for qualified objects as for unqualified objects.
961This applies only to implicitly generated constructor calls.
962Hence, explicitly re-initializing qualified objects with a constructor requires an explicit cast.
964As discussed in Section \ref{sub:c_background}, compound literals create unnamed objects.
965This mechanism can continue to be used seamlessly in \CFA with managed types to create temporary objects.
966The object created by a compound literal is constructed using the provided brace-enclosed initializer-list, and is destructed at the end of the scope it is used in.
967For example,
969struct A { int x; };
970void ?{}(A *, int, int);
972  int x = (A){ 10, 20 }.x;
975is equivalent to
977struct A { int x, y; };
978void ?{}(A *, int, int);
980  A _tmp;
981  ?{}(&_tmp, 10, 20);
982  int x = _tmp.x;
983  ^?{}(&tmp);
987Unlike \CC, \CFA provides an escape hatch that allows a user to decide at an object's definition whether it should be managed or not.
988An object initialized with \ateq is guaranteed to be initialized like a C object, and has no implicit destructor call.
989This feature provides all of the freedom that C programmers are used to having to optimize a program, while maintaining safety as a sensible default.
991struct A { int * x; };
992// RAII
993void ?{}(A * a) { a->x = malloc(sizeof(int)); }
994void ^?{}(A * a) { free(a->x); }
996A a1;           // managed
997A a2 @= { 0 };  // unmanaged
999In this example, @a1@ is a managed object, and thus is default constructed and destructed at the start/end of @a1@'s lifetime, while @a2@ is an unmanaged object and is not implicitly constructed or destructed.
1000Instead, @a2->x@ is initialized to @0@ as if it were a C object, because of the explicit initializer.
1002In addition to freedom, \ateq provides a simple path to migrating legacy C code to Cforall, in that objects can be moved from C-style initialization to \CFA gradually and individually.
1003It is worth noting that the use of unmanaged objects can be tricky to get right, since there is no guarantee that the proper invariants are established on an unmanaged object.
1004It is recommended that most objects be managed by sensible constructors and destructors, except where absolutely necessary.
1006When a user declares any constructor or destructor, the corresponding intrinsic/generated function and all field constructors for that type are hidden, so that they are not found during expression resolution until the user-defined function goes out of scope.
1007Furthermore, if the user declares any constructor, then the intrinsic/generated default constructor is also hidden, precluding default construction.
1008These semantics closely mirror the rule for implicit declaration of constructors in \CC, wherein the default constructor is implicitly declared if there is no user-declared constructor \cite[p.~186]{ANSI98:C++}.
1010struct S { int x, y; };
1012void f() {
1013  S s0, s1 = { 0 }, s2 = { 0, 2 }, s3 = s2;  // okay
1014  {
1015    void ?{}(S * s, int i) { s->x = i*2; } // locally hide autogen constructors
1016    S s4;  // error
1017    S s5 = { 3 };  // okay
1018    S s6 = { 4, 5 };  // error
1019    S s7 = s5; // okay
1020  }
1021  S s8, s9 = { 6 }, s10 = { 7, 8 }, s11 = s10;  // okay
1024In this example, the inner scope declares a constructor from @int@ to @S@, which hides the default constructor and field constructors until the end of the scope.
1026When defining a constructor or destructor for a struct @S@, any members that are not explicitly constructed or destructed are implicitly constructed or destructed automatically.
1027If an explicit call is present, then that call is taken in preference to any implicitly generated call.
1028A consequence of this rule is that it is possible, unlike \CC, to precisely control the order of construction and destruction of subobjects on a per-constructor basis, whereas in \CC subobject initialization and destruction is always performed based on the declaration order.
1030struct A {
1031  B w, x, y, z;
1033void ?{}(A * a, int i) {
1034  (&a->x){ i };
1035  (&a->z){ a->y };
1038Generates the following
1040void ?{}(A * a, int i) {
1041  (&a->w){};   // implicit default ctor
1042  (&a->y){};   // implicit default ctor
1043  (&a->x){ i };
1044  (&a->z){ a->y };
1047Finally, it is illegal for a subobject to be explicitly constructed for the first time after it is used for the first time.
1048If the translator cannot be reasonably sure that an object is constructed prior to its first use, but is constructed afterward, an error is emitted.
1049More specifically, the translator searches the body of a constructor to ensure that every subobject is initialized.
1051void ?{}(A * a, double x) {
1052  f(a->x);
1053  (&a->x){ (int)x }; // error, used uninitialized on previous line
1056However, if the translator sees a subobject used within the body of a constructor, but does not see a constructor call that uses the subobject as the target of a constructor, then the translator assumes the object is to be implicitly constructed (copy constructed in a copy constructor and default constructed in any other constructor).
1058void ?{}(A * a) {
1059  // default constructs all members
1060  f(a->x);
1063void ?{}(A * a, A other) {
1064  // copy constructs all members
1065  f(a->y);
1068void ^?{}(A * a) {
1069  ^(&a->x){}; // explicit destructor call
1070} // z, y, w implicitly destructed, in this order
1072If at any point, the @this@ parameter is passed directly as the target of another constructor, then it is assumed that constructor handles the initialization of all of the object's members and no implicit constructor calls are added. % TODO: this is basically always wrong. if anything, I should check that such a constructor does not initialize any members, otherwise it'll always initialize the member twice (once locally, once by the called constructor). This might be okay in some situations, but it deserves a warning at the very least.
1073To override this rule, \ateq can be used to force the translator to trust the programmer's discretion.
1074This form of \ateq is not yet implemented.
1076Despite great effort, some forms of C syntax do not work well with constructors in \CFA.
1077In particular, constructor calls cannot contain designations (see \ref{sub:c_background}), since this is equivalent to allowing designations on the arguments to arbitrary function calls.
1079// all legal forward declarations in C
1080void f(int, int, int);
1081void f(int a, int b, int c);
1082void f(int b, int c, int a);
1083void f(int c, int a, int b);
1084void f(int x, int y, int z);
1086f(b:10, a:20, c:30);  // which parameter is which?
1088In C, function prototypes are permitted to have arbitrary parameter names, including no names at all, which may have no connection to the actual names used at function definition.
1089Furthermore, a function prototype can be repeated an arbitrary number of times, each time using different names.
1090As a result, it was decided that any attempt to resolve designated function calls with C's function prototype rules would be brittle, and thus it is not sensible to allow designations in constructor calls.
1092In addition, constructor calls do not support unnamed nesting.
1094struct B { int x; };
1095struct C { int y; };
1096struct A { B b; C c; };
1097void ?{}(A *, B);
1098void ?{}(A *, C);
1100A a = {
1101  { 10 },  // construct B? - invalid
1104In C, nesting initializers means that the programmer intends to initialize subobjects with the nested initializers.
1105The reason for this omission is to both simplify the mental model for using constructors, and to make initialization simpler for the expression resolver.
1106If this were allowed, it would be necessary for the expression resolver to decide whether each argument to the constructor call could initialize to some argument in one of the available constructors, making the problem highly recursive and potentially much more expensive.
1107That is, in the previous example the line marked as an error could mean construct using @?{}(A *, B)@ or with @?{}(A *, C)@, since the inner initializer @{ 10 }@ could be taken as an intermediate object of type @B@ or @C@.
1108In practice, however, there could be many objects that can be constructed from a given @int@ (or, indeed, any arbitrary parameter list), and thus a complete solution to this problem would require fully exploring all possibilities.
1110More precisely, constructor calls cannot have a nesting depth greater than the number of array components in the type of the initialized object, plus one.
1111For example,
1113struct A;
1114void ?{}(A *, int);
1115void ?{}(A *, A, A);
1117A a1[3] = { { 3 }, { 4 }, { 5 } };
1118A a2[2][2] = {
1119  { { 9 }, { 10 } },  // a2[0]
1120  { {14 }, { 15 } }   // a2[1]
1122A a3[4] = {
1123  { { 11 }, { 12 } },  // error
1124  { 80 }, { 90 }, { 100 }
1127% TODO: in CFA if the array dimension is empty, no object constructors are added -- need to fix this.
1128The body of @A@ has been omitted, since only the constructor interfaces are important.
1130It should be noted that unmanaged objects can still make use of designations and nested initializers in \CFA.
1131It is simple to overcome this limitation for managed objects by making use of compound literals, so that the arguments to the constructor call are explicitly typed.
1133\subsection{Implicit Destructors}
1135Destructors are automatically called at the end of the block in which the object is declared.
1136In addition to this, destructors are automatically called when statements manipulate control flow to leave a block in which the object is declared, e.g., with return, break, continue, and goto statements.
1137The example below demonstrates a simple routine with multiple return statements.
1139struct A;
1140void ^?{}(A *);
1142void f(int i) {
1143  A x;  // construct x
1144  {
1145    A y; // construct y
1146    {
1147      A z; // construct z
1148      {
1149        if (i == 0) return; // destruct x, y, z
1150      }
1151      if (i == 1) return; // destruct x, y, z
1152    } // destruct z
1153    if (i == 2) return; // destruct x, y
1154  } // destruct y
1158The next example illustrates the use of simple continue and break statements and the manner that they interact with implicit destructors.
1160for (int i = 0; i < 10; i++) {
1161  A x;
1162  if (i == 2) {
1163    continue;  // destruct x
1164  } else if (i == 3) {
1165    break;     // destruct x
1166  }
1167} // destruct x
1169Since a destructor call is automatically inserted at the end of the block, nothing special needs to happen to destruct @x@ in the case where control reaches the end of the loop.
1170In the case where @i@ is @2@, the continue statement runs the loop update expression and attempts to begin the next iteration of the loop.
1171Since continue is a C statement, which does not understand destructors, a destructor call is added just before the continue statement to ensure that @x@ is destructed.
1172When @i@ is @3@, the break statement moves control to just past the end of the loop.
1173Like the previous case, a destructor call for @x@ is inserted just before the break statement.
1175\CFA also supports labelled break and continue statements, which allow more precise manipulation of control flow.
1176Labelled break and continue allow the programmer to specify which control structure to target by using a label attached to a control structure.
1177\begin{cfacode}[emph={L1,L2}, emphstyle=\color{red}]
1178L1: for (int i = 0; i < 10; i++) {
1179  A x;
1180  for (int j = 0; j < 10; j++) {
1181    A y;
1182    if (i == 1) {
1183      continue L1; // destruct y
1184    } else if (i == 2) {
1185      break L1;    // destruct x,y
1186    }
1187  } // destruct y
1188} // destruct X
1190The statement @continue L1@ begins the next iteration of the outer for-loop.
1191Since the semantics of continue require the loop update expression to execute, control branches to the \emph{end} of the outer for loop, meaning that the block destructor for @x@ can be reused, and it is only necessary to generate the destructor for @y@.
1192% TODO: "why not do this all the time? fix or justify"
1193Break, on the other hand, requires jumping out of the loop, so the destructors for both @x@ and @y@ are generated and inserted before the @break L1@ statement.
1195Finally, an example which demonstrates goto.
1196Since goto is a general mechanism for jumping to different locations in the program, a more comprehensive approach is required.
1197For each goto statement $G$ and each target label $L$, let $S_G$ be the set of all managed variables alive at $G$, and let $S_L$ be the set of all managed variables alive at $L$.
1198If at any $G$, $S_L \setminus S_G = \emptyset$, then the translator emits an error, because control flow branches from a point where the object is not yet live to a point where it is live, skipping the object's constructor.
1199Then, for every $G$, the destructors for each variable in the set $S_G \setminus S_L$ is inserted directly before $G$, which ensures each object that is currently live at $G$, but not at $L$, is destructed before control branches.
1201int i = 0;
1203  L0: ;     // S_L0 = { x }
1204    A y;
1205  L1: ;     // S_L1 = { x }
1206    A x;
1207  L2: ;     // S_L2 = { y, x }
1208    if (i == 0) {
1209      ++i;
1210      goto L1;    // S_G = { y, x }
1211      // S_G-S_L1 = { x } => destruct x
1212    } else if (i == 1) {
1213      ++i;
1214      goto L2;    // S_G = { y, x }
1215      // S_G-S_L2 = {} => destruct nothing
1216    } else if (i == 2) {
1217      ++i;
1218      goto L3;    // S_G = { y, x }
1219      // S_G-S_L3 = {}
1220    } else if (false) {
1221      ++i;
1222      A z;
1223      goto L3;    // S_G = { z, y, x }
1224      // S_G-S_L3 = { z } => destruct z
1225    } else {
1226      ++i;
1227      goto L4;    // S_G = { y, x }
1228      // S_G-S_L4 = { y, x } => destruct y, x
1229    }
1230  L3: ;    // S_L3 = { y, x }
1231    goto L2;      // S_G = { y, x }
1232    // S_G-S_L2 = {}
1234L4: ;  // S_L4 = {}
1235if (i == 4) {
1236  goto L0;        // S_G = {}
1237  // S_G-S_L0 = {}
1240Labelled break and continue are implemented in \CFA in terms of goto statements, so the more constrained forms are precisely goverened by these rules.
1242The next example demonstrates the error case.
1245    goto L1; // S_G = {}
1246    // S_L1-S_G = { y } => error
1247    A y;
1248  L1: ; // S_L1 = { y }
1249    A x;
1250  L2: ; // S_L2 = { y, x }
1252goto L2; // S_G = {}
1253// S_L2-S_G = { y, x } => error
1256\subsection{Implicit Copy Construction}
1257When a function is called, the arguments supplied to the call are subject to implicit copy construction (and destruction of the generated temporary), and the return value is subject to destruction.
1258When a value is returned from a function, the copy constructor is called to pass the value back to the call site.
1259Exempt from these rules are intrinsic and builtin functions.
1260It should be noted that unmanaged objects are subject to copy constructor calls when passed as arguments to a function or when returned from a function, since they are not the \emph{target} of the copy constructor call.
1261That is, since the parameter is not marked as an unmanaged object using \ateq, it will be copy constructed if it is returned by value or passed as an argument to another function, so to guarantee consistent behaviour, unmanaged objects must be copy constructed when passed as arguments.
1262This is an important detail to bear in mind when using unmanaged objects, and could produce unexpected results when mixed with objects that are explicitly constructed.
1264struct A;
1265void ?{}(A *);
1266void ?{}(A *, A);
1267void ^?{}(A *);
1269A identity(A x) { // pass by value => need local copy
1270  return x;       // return by value => make call-site copy
1273A y, z @= {};
1274identity(y);  // copy construct y into x
1275identity(z);  // copy construct z into x
1277Note that @z@ is copy constructed into a temporary variable to be passed as an argument, which is also destructed after the call.
1279This generates the following
1281struct A f(struct A x){
1282  struct A _retval_f;    // return value
1283  ?{}((&_retval_f), x);  // copy construct return value
1284  return _retval_f;
1287struct A y;
1288?{}(&y);                 // default construct
1289struct A z = { 0 };      // C default
1291struct A _tmp_cp1;       // argument 1
1292struct A _tmp_cp_ret0;   // return value
1294  (?{}(&_tmp_cp1, y) , _tmp_cp1)  // argument is a comma expression
1295), _tmp_cp_ret0;         // return value for cascading
1296^?{}(&_tmp_cp_ret0);     // destruct return value
1297^?{}(&_tmp_cp1);         // destruct argument 1
1299struct A _tmp_cp2;       // argument 1
1300struct A _tmp_cp_ret1;   // return value
1302  (?{}(&_tmp_cp2, z), _tmp_cp2)  // argument is a common expression
1303), _tmp_cp_ret1;         // return value for cascading
1304^?{}(&_tmp_cp_ret1);     // destruct return value
1305^?{}(&_tmp_cp2);         // destruct argument 1
1309A special syntactic form, such as a variant of \ateq, can be implemented to specify at the call site that an argument should not be copy constructed, to regain some control for the C programmer.
1311identity(z@);  // do not copy construct argument
1312               // - will copy construct/destruct return value
1313A@ identity_nocopy(A @ x) {  // argument not copy constructed or destructed
1314  return x;  // not copy constructed
1315             // return type marked @ => not destructed
1318It should be noted that reference types will allow specifying that a value does not need to be copied, however reference types do not provide a means of preventing implicit copy construction from uses of the reference, so the problem is still present when passing or returning the reference by value.
1320A known issue with this implementation is that the return value of a function is not guaranteed to have the same address for its entire lifetime.
1321Specifically, since @_retval_f@ is allocated and constructed in @f@ then returned by value, the internal data is bitwise copied into the caller's stack frame.
1322This approach works out most of the time, because typically destructors need to only access the fields of the object and recursively destroy.
1323It is currently the case that constructors and destructors that use the @this@ pointer as a unique identifier to store data externally do not work correctly for return value objects.
1324Thus, it is not safe to rely on an object's @this@ pointer to remain constant throughout execution of the program.
1326A * external_data[32];
1327int ext_count;
1328struct A;
1329void ?{}(A * a) {
1330  // ...
1331  external_data[ext_count++] = a;
1333void ^?{}(A * a) {
1334  for (int i = 0; i < ext_count) {
1335    if (a == external_data[i]) { // may never be true
1336      // ...
1337    }
1338  }
1341A makeA() {
1342  A x;  // stores &x in external_data
1343  return x;
1345makeA();  // return temporary has a different address than x
1346// equivalent to:
1347//   A _tmp;
1348//   _tmp = makeA(), _tmp;
1349//   ^?{}(&_tmp);
1351In the above example, a global array of pointers is used to keep track of all of the allocated @A@ objects.
1352Due to copying on return, the current object being destructed does not exist in the array if an @A@ object is ever returned by value from a function.
1354This problem could be solved in the translator by changing the function signatures so that the return value is moved into the parameter list.
1355For example, the translator could restructure the code like so
1357void f(struct A x, struct A * _retval_f){
1358  ?{}(_retval_f, x);  // construct directly into caller's stack frame
1361struct A y;
1363struct A z = { 0 };
1365struct A _tmp_cp1;     // argument 1
1366struct A _tmp_cp_ret0; // return value
1367f((?{}(&_tmp_cp1, y) , _tmp_cp1), &_tmp_cp_ret0), _tmp_cp_ret0;
1368^?{}(&_tmp_cp_ret0);   // return value
1369^?{}(&_tmp_cp1);       // argument 1
1371This transformation provides @f@ with the address of the return variable so that it can be constructed into directly.
1372It is worth pointing out that this kind of signature rewriting already occurs in polymorphic functions that return by value, as discussed in \cite{Bilson03}.
1373A key difference in this case is that every function would need to be rewritten like this, since types can switch between managed and unmanaged at different scope levels, e.g.
1375struct A { int v; };
1376A x; // unmanaged, since only trivial constructors are available
1378  void ?{}(A * a) { ... }
1379  void ^?{}(A * a) { ... }
1380  A y; // managed
1382A z; // unmanaged
1384Hence there is not enough information to determine at function declaration whether a type is managed or not, and thus it is the case that all signatures have to be rewritten to account for possible copy constructor and destructor calls.
1385Even with this change, it would still be possible to declare backwards compatible function prototypes with an @extern "C"@ block, which allows for the definition of C-compatible functions within \CFA code, however this would require actual changes to the way code inside of an @extern "C"@ function is generated as compared with normal code generation.
1386Furthermore, it is not possible to overload C functions, so using @extern "C"@ to declare functions is of limited use.
1388It would be possible to regain some control by adding an attribute to structs that specifies whether they can be managed or not (perhaps \emph{manageable} or \emph{unmanageable}), and to emit an error in the case that a constructor or destructor is declared for an unmanageable type.
1389Ideally, structs should be manageable by default, since otherwise the default case becomes more verbose.
1390This means that in general, function signatures would have to be rewritten, and in a select few cases the signatures would not be rewritten.
1392__attribute__((manageable)) struct A { ... };   // can declare constructors
1393__attribute__((unmanageable)) struct B { ... }; // cannot declare constructors
1394struct C { ... };                               // can declare constructors
1396A f();  // rewritten void f(A *);
1397B g();  // not rewritten
1398C h();  // rewritten void h(C *);
1400An alternative is to instead make the attribute \emph{identifiable}, which states that objects of this type use the @this@ parameter as an identity.
1401This strikes more closely to the visibile problem, in that only types marked as identifiable would need to have the return value moved into the parameter list, and every other type could remain the same.
1402Furthermore, no restrictions would need to be placed on whether objects can be constructed.
1404__attribute__((identifiable)) struct A { ... };  // can declare constructors
1405struct B { ... };                                // can declare constructors
1407A f();  // rewritten void f(A *);
1408B g();  // not rewritten
1411Ultimately, this is the type of transformation that a real compiler would make when generating assembly code.
1412Since a compiler has full control over its calling conventions, it can seamlessly allow passing the return parameter without outwardly changing the signature of a routine.
1413As such, it has been decided that this issue is not currently a priority.
1416\subsection{Array Initialization}
1417Arrays are a special case in the C type-system.
1418C arrays do not carry around their size, making it impossible to write a standalone \CFA function that constructs or destructs an array while maintaining the standard interface for constructors and destructors.
1419Instead, \CFA defines the initialization and destruction of an array recursively.
1420That is, when an array is defined, each of its elements is constructed in order from element 0 up to element $n-1$.
1421When an array is to be implicitly destructed, each of its elements is destructed in reverse order from element $n-1$ down to element 0.
1422As in C, it is possible to explicitly provide different initializers for each element of the array through array initialization syntax.
1423In this case, each of the initializers is taken in turn to construct a subsequent element of the array.
1424If too many initializers are provided, only the initializers up to N are actually used.
1425If too few initializers are provided, then the remaining elements are default constructed.
1427For example, given the following code.
1429struct X {
1430  int x, y, z;
1432void f() {
1433  X x[10] = { { 1, 2, 3 }, { 4 }, { 7, 8 } };
1436The following code is generated for @f@.
1438void f(){
1439  struct X x[((long unsigned int )10)];
1440  // construct x
1441  {
1442    int _index0 = 0;
1443    // construct with explicit initializers
1444    {
1445      if (_index0<10) ?{}(&x[_index0], 1, 2, 3);
1446      ++_index0;
1447      if (_index0<10) ?{}(&x[_index0], 4);
1448      ++_index0;
1449      if (_index0<10) ?{}(&x[_index0], 7, 8);
1450      ++_index0;
1451    }
1453    // default construct remaining elements
1454    for (;_index0<10;++_index0) {
1455      ?{}(&x[_index0]);
1456    }
1457  }
1458  // destruct x
1459  {
1460    int _index1 = 10-1;
1461    for (;_index1>=0;--_index1) {
1462      ^?{}(&x[_index1]);
1463    }
1464  }
1467Multidimensional arrays require more complexity.
1468For example, a two dimensional array
1470void g() {
1471  X x[10][10] = {
1472    { { 1, 2, 3 }, { 4 } }, // x[0]
1473    { { 7, 8 } }            // x[1]
1474  };
1476Generates the following
1478void g(){
1479  struct X x[10][10];
1480  // construct x
1481  {
1482    int _index0 = 0;
1483    for (;_index0<10;++_index0) {
1484      {
1485        int _index1 = 0;
1486        // construct with explicit initializers
1487        {
1488          switch ( _index0 ) {
1489            case 0:
1490              // construct first array
1491              if ( _index1<10 ) ?{}(&x[_index0][_index1], 1, 2, 3);
1492              ++_index1;
1493              if ( _index1<10 ) ?{}(&x[_index0][_index1], 4);
1494              ++_index1;
1495              break;
1496            case 1:
1497              // construct second array
1498              if ( _index1<10 ) ?{}(&x[_index0][_index1], 7, 8);
1499              ++_index1;
1500              break;
1501          }
1502        }
1503        // default construct remaining elements
1504        for (;_index1<10;++_index1) {
1505            ?{}(&x[_index0][_index1]);
1506        }
1507      }
1508    }
1509  }
1510  // destruct x
1511  {
1512    int _index2 = 10-1;
1513    for (;_index2>=0;--_index2) {
1514      {
1515        int _index3 = 10-1;
1516        for (;_index3>=0;--_index3) {
1517            ^?{}(&x[_index2][_index3]);
1518        }
1519      }
1520    }
1521  }
1524% It is possible to generate slightly simpler code for the switch cases, since the value of @_index1@ is known at compile-time within each case, however the procedure for generating constructor calls is complicated.
1525% It is simple to remove the increment statements for @_index1@, but it is not simple to remove the
1526%% technically, it's not hard either. I could easily downcast and change the second argument to ?[?], but is it really necessary/worth it??
1528\subsection{Global Initialization}
1529In standard C, global variables can only be initialized to compile-time constant expressions.
1530This places strict limitations on the programmer's ability to control the default values of objects.
1531In \CFA, constructors and destructors are guaranteed to be run on global objects, allowing arbitrary code to be run before and after the execution of the main routine.
1532By default, objects within a translation unit are constructed in declaration order, and destructed in the reverse order.
1533The default order of construction of objects amongst translation units is unspecified.
1534It is, however, guaranteed that any global objects in the standard library are initialized prior to the initialization of any object in the user program.
1536This feature is implemented in the \CFA translator by grouping every global constructor call into a function with the GCC attribute \emph{constructor}, which performs most of the heavy lifting. % TODO: CITE:
1537A similar function is generated with the \emph{destructor} attribute, which handles all global destructor calls.
1538At the time of writing, initialization routines in the library are specified with priority \emph{101}, which is the highest priority level that GCC allows, whereas initialization routines in the user's code are implicitly given the default priority level, which ensures they have a lower priority than any code with a specified priority level.
1539This mechanism allows arbitrarily complicated initialization to occur before any user code runs, making it possible for library designers to initialize their modules without requiring the user to call specific startup or teardown routines.
1541For example, given the following global declarations.
1543struct X {
1544  int y, z;
1546void ?{}(X *);
1547void ?{}(X *, int, int);
1548void ^?{}(X *);
1550X a;
1551X b = { 10, 3 };
1553The following code is generated.
1555__attribute__ ((constructor)) static void _init_global_ctor(void){
1556  ?{}(&a);
1557  ?{}(&b, 10, 3);
1559__attribute__ ((destructor)) static void _destroy_global_ctor(void){
1560  ^?{}(&b);
1561  ^?{}(&a);
1566% suggestion: implement this in CFA by picking objects with a specified priority and pulling them into their own init functions (could even group them by priority level -> map<int, list<ObjectDecl*>>) and pull init_priority forward into constructor and destructor attributes with the same priority level
1567GCC provides an attribute @init_priority@, which specifies allows specifying the relative priority for initialization of global objects on a per-object basis in \CC.
1568A similar attribute can be implemented in \CFA by pulling marked objects into global constructor/destructor-attribute functions with the specified priority.
1569For example,
1571struct A { ... };
1572void ?{}(A *, int);
1573void ^?{}(A *);
1574__attribute__((init_priority(200))) A x = { 123 };
1576would generate
1578A x;
1579__attribute__((constructor(200))) __init_x() {
1580  ?{}(&x, 123);  // construct x with priority 200
1582__attribute__((destructor(200))) __destroy_x() {
1583  ?{}(&x);       // destruct x with priority 200
1587\subsection{Static Local Variables}
1588In standard C, it is possible to mark variables that are local to a function with the @static@ storage class.
1589Unlike normal local variables, a @static@ local variable is defined to live for the entire duration of the program, so that each call to the function has access to the same variable with the same address and value as it had in the previous call to the function. % TODO: mention dynamic loading caveat??
1590Much like global variables, in C @static@ variables can only be initialized to a \emph{compile-time constant value} so that a compiler is able to create storage for the variable and initialize it at compile-time.
1592Yet again, this rule is too restrictive for a language with constructors and destructors.
1593Instead, \CFA modifies the definition of a @static@ local variable so that objects are guaranteed to be live from the time control flow reaches their declaration, until the end of the program, since the initializer expression is not necessarily a compile-time constant, but can depend on the current execution state of the function.
1594Since standard C does not allow access to a @static@ local variable before the first time control flow reaches the declaration, this restriction does not preclude any valid C code.
1595Local objects with @static@ storage class are only implicitly constructed and destructed once for the duration of the program.
1596The object is constructed when its declaration is reached for the first time.
1597The object is destructed once at the end of the program.
1599Construction of @static@ local objects is implemented via an accompanying @static bool@ variable, which records whether the variable has already been constructed.
1600A conditional branch checks the value of the companion @bool@, and if the variable has not yet been constructed then the object is constructed.
1601The object's destructor is scheduled to be run when the program terminates using @atexit@, and the companion @bool@'s value is set so that subsequent invocations of the function do not reconstruct the object.
1602Since the parameter to @atexit@ is a parameter-less function, some additional tweaking is required.
1603First, the @static@ variable must be hoisted up to global scope and uniquely renamed to prevent name clashes with other global objects.
1604Second, a function is built which calls the destructor for the newly hoisted variable.
1605Finally, the newly generated function is registered with @atexit@, instead of registering the destructor directly.
1606Since @atexit@ calls functions in the reverse order in which they are registered, @static@ local variables are guaranteed to be destructed in the reverse order that they are constructed, which may differ between multiple executions of the same program.
1608Extending the previous example
1610int f(int x) {
1611  static X a;
1612  static X b = { x, x };  // depends on parameter value
1613  static X c = b;         // depends on local variable
1616Generates the following.
1618static struct X a_static_var0;
1619static void __a_dtor_atexit0(void){
1620  ((void)^?{}(((struct X *)(&a_static_var0))));
1622static struct X b_static_var1;
1623static void __b_dtor_atexit1(void){
1624  ((void)^?{}(((struct X *)(&b_static_var1))));
1626static struct X c_static_var2;
1627static void __c_dtor_atexit2(void){
1628  ((void)^?{}(((struct X *)(&c_static_var2))));
1630int f(int x){
1631  int _retval_f;
1632  __attribute__ ((unused)) static void *_dummy0;
1633  static _Bool __a_uninitialized = 1;
1634  if ( __a_uninitialized ) {
1635    ((void)?{}(((struct X *)(&a_static_var0))));
1636    ((void)(__a_uninitialized=0));
1637    ((void)atexit(__a_dtor_atexit0));
1638  }
1640  __attribute__ ((unused)) static void *_dummy1;
1641  static _Bool __b_uninitialized = 1;
1642  if ( __b_uninitialized ) {
1643    ((void)?{}(((struct X *)(&b_static_var1)), x, x));
1644    ((void)(__b_uninitialized=0));
1645    ((void)atexit(__b_dtor_atexit1));
1646  }
1648  __attribute__ ((unused)) static void *_dummy2;
1649  static _Bool __c_uninitialized = 1;
1650  if ( __c_uninitialized ) {
1651    ((void)?{}(((struct X *)(&c_static_var2)), b_static_var1));
1652    ((void)(__c_uninitialized=0));
1653    ((void)atexit(__c_dtor_atexit2));
1654  }
1658% TODO: move this section forward?? maybe just after constructor syntax? would need to remove _tmp_cp_ret0, since copy constructors are not discussed yet, but this might not be a big issue.
1659\subsection{Constructor Expressions}
1660In \CFA, it is possible to use a constructor as an expression.
1661Like other operators, the function name @?{}@ matches its operator syntax.
1662For example, @(&x){}@ calls the default constructor on the variable @x@, and produces @&x@ as a result.
1663A key example for this capability is the use of constructor expressions to initialize the result of a call to standard C routine @malloc@.
1665struct X { ... };
1666void ?{}(X *, double);
1667X * x = malloc(sizeof(X)){ 1.5 };
1669In this example, @malloc@ dynamically allocates storage and initializes it using a constructor, all before assigning it into the variable @x@.
1670If this extension is not present, constructing dynamically allocated objects is much more cumbersome, requiring separate initialization of the pointer and initialization of the pointed-to memory.
1672X * x = malloc(sizeof(X));
1673x{ 1.5 };
1675Not only is this verbose, but it is also more error prone, since this form allows maintenance code to easily sneak in between the initialization of @x@ and the initialization of the memory that @x@ points to.
1676This feature is implemented via a transformation produceing the value of the first argument of the constructor, since constructors do not themslves have a return value.
1677Since this transformation results in two instances of the subexpression, care is taken to allocate a temporary variable to hold the result of the subexpression in the case where the subexpression may contain side effects.
1678The previous example generates the following code.
1680struct X *_tmp_ctor;
1681struct X *x = ?{}((_tmp_ctor=((_tmp_cp_ret0=
1682  malloc(sizeof(struct X))), _tmp_cp_ret0))), 1.5), _tmp_ctor);
1684It should be noted that this technique is not exclusive to @malloc@, and allows a user to write a custom allocator that can be idiomatically used in much the same way as a constructed @malloc@ call.
1686It is also possible to use operator syntax with destructors.
1687Unlike constructors, operator syntax with destructors is a statement and thus does not produce a value, since the destructed object is invalidated by the use of a destructor.
1688For example, \lstinline!^(&x){}! calls the destructor on the variable @x@.
Note: See TracBrowser for help on using the repository browser.