% T I T L E   P A G E
% -------------------
% Last updated August 16, 2022, by IST-Client Services
% The title page is counted as page `i' but we need to suppress the
% page number. Also, we don't want any headers or footers.
\pagestyle{empty}
\pagenumbering{roman}

% The contents of the title page are specified in the "titlepage"
% environment.
\begin{titlepage}
        \begin{center}
        \vspace*{1.0cm}

  % TODO: punch up the title, thinking getting interest in the department-wide posting of my presentation
  % Modern collections for C
        {\Huge\bf \CFA Container Library}

        \vspace*{1.0cm}

        by \\

        \vspace*{1.0cm}

        {\Large Michael Leslie Brooks} \\

        \vspace*{3.0cm}

        A thesis \\
        presented to the University of Waterloo \\
        in fulfillment of the \\
        thesis requirement for the degree of \\
        Master of Mathematics \\
        in \\
        Computer Science \\

        \vspace*{2.0cm}

        Waterloo, Ontario, Canada, \the\year \\

        \vspace*{1.0cm}

        \copyright{} Michael Leslie Brooks \the\year \\
        \end{center}
\end{titlepage}

% The rest of the front pages should contain no headers and be numbered using Roman numerals starting with `ii'
\pagestyle{plain}
\setcounter{page}{2}

\cleardoublepage % Ends the current page and causes all figures and tables that have so far appeared in the input to be printed.
% In a two-sided printing style, it also makes the next page a right-hand (odd-numbered) page, producing a blank page if necessary.
\phantomsection    % allows hyperref to link to the correct page

\begin{comment}
% E X A M I N I N G   C O M M I T T E E (Required for Ph.D. theses only)
% Remove or comment out the lines below to remove this page
\addcontentsline{toc}{chapter}{Examining Committee}
\begin{center}\textbf{Examining Committee Membership}\end{center}
  \noindent
The following served on the Examining Committee for this thesis. The decision of the Examining Committee is by majority vote.
  \bigskip

  \noindent
\begin{tabbing}
Internal-External Member: \=  \kill % using longest text to define tab length
External Examiner: \>  Bruce Bruce \\
\> Professor, Dept. of Philosophy of Zoology, University of Waterloo \\
\end{tabbing}
  \bigskip

  \noindent
\begin{tabbing}
Internal-External Member: \=  \kill % using longest text to define tab length
Supervisor(s): \> Ann Elk \\
\> Professor, Dept. of Zoology, University of Waterloo \\
\> Andrea Anaconda \\
\> Professor Emeritus, Dept. of Zoology, University of Waterloo \\
\end{tabbing}
  \bigskip

  \noindent
  \begin{tabbing}
Internal-External Member: \=  \kill % using longest text to define tab length
Internal Member: \> Pamela Python \\
\> Professor, Dept. of Zoology, University of Waterloo \\
\end{tabbing}
  \bigskip

  \noindent
\begin{tabbing}
Internal-External Member: \=  \kill % using longest text to define tab length
Internal-External Member: \> Meta Meta \\
\> Professor, Dept. of Philosophy, University of Waterloo \\
\end{tabbing}
  \bigskip

  \noindent
\begin{tabbing}
Internal-External Member: \=  \kill % using longest text to define tab length
Other Member(s): \> Leeping Fang \\
\> Professor, Dept. of Fine Art, University of Waterloo \\
\end{tabbing}

\cleardoublepage
\end{comment}

% D E C L A R A T I O N   P A G E
% -------------------------------
  % The following is a sample Declaration Page as provided by the GSO
  % December 13th, 2006.  It is designed for an electronic thesis.
 \addcontentsline{toc}{chapter}{Author's Declaration}
 \begin{center}\textbf{Author's Declaration}\end{center}

 \noindent
I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners.

  \bigskip

  \noindent
I understand that my thesis may be made electronically available to the public.

\cleardoublepage
\phantomsection    % allows hyperref to link to the correct page

% A B S T R A C T
% ---------------
\addcontentsline{toc}{chapter}{Abstract}
\begin{center}\textbf{Abstract}\end{center}

\CFA strives to fix issues in C, chief among them safety.
This thesis presents a significant step forward in \CFA's goal to remove unsafe pointer operations.
It describes improvements to the \CFA language design to support advanced container features.
These features are implemented across the \CFA compiler and runtime libraries.
The results maintain another \CFA goal of offering strong backwards compatibility with C.
To achieve these goals, this work leverages preexisting \CFA contributions by prior students, particularly novel applications of the compiler's type system.

All modern programming languages provide these three high-level containers (collections): array, linked-list, and string.
Often, the array is part of the programming language, while linked lists are built from (recursive) pointer types, and strings from arrays and/or linked lists.
For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component levels, such as copying, slicing, extracting, and iterating among elements.
Unfortunately, typical implementations for the these key types in C cause 60\%--70\% of the reported software vulnerabilities involving memory errors, where 70\%--80\% of hacker attack-vectors target these types.
Therefore, hardening these three C types and suggesting programers use them as their default types goes a long way to increase memory safety in the majority of C programs.

Specifically, an array is provided that tracks its length internally, relieving the user and implementor from managing explicit length arguments/parameters and stopping buffer-overrun errors.
This feature requires augmenting the \CFA type system, making array length available at compile and runtime.
A linked-list utility is provided that obviates many user-managed recursive pointers, while catering directly to system-programming using intrusive linking.
Finally, a string utility is provided with implicit memory management of text in a specialized heap, removing error-prone buffer management, including overrun, and providing a copy-on-write speed boost.
For all three utilities, performance is argued to be on-par or surpass those in other comparable languages.
With the array, this case is made by showing complete erasure down to a naked C array, modulo runtime bound checks, which are removable more often than with Java-style length management.
With the linked list and string, empirical measures are compared with C and \CC comparable libraries.
These containers offer programmers workable alternatives to hand-rolling specialized libraries, which is a huge safety benefit, eliminating many system vulnerabilities.
The results establish \CFA's position as a safety-forward programming alternative.

\cleardoublepage
\phantomsection    % allows hyperref to link to the correct page

% A C K N O W L E D G E M E N T S
% -------------------------------
\addcontentsline{toc}{chapter}{Acknowledgements}
\begin{center}\textbf{Acknowledgements}\end{center}

I would like to thank all the little people who made this thesis possible.

Finally, a special thank you to Huawei Canada for funding this work.
\cleardoublepage
\phantomsection    % allows hyperref to link to the correct page

\begin{comment}
% D E D I C A T I O N
% -------------------
\addcontentsline{toc}{chapter}{Dedication}
\begin{center}\textbf{Dedication}\end{center}

This is dedicated to the one I love.
\cleardoublepage
\end{comment}

% T A B L E   O F   C O N T E N T S
% ---------------------------------
\renewcommand\contentsname{Table of Contents}
\tableofcontents
\cleardoublepage
\phantomsection    % allows hyperref to link to the correct page

% L I S T   O F   F I G U R E S
% -----------------------------
\addcontentsline{toc}{chapter}{List of Figures}
\listoffigures
\cleardoublepage
\phantomsection		% allows hyperref to link to the correct page

% L I S T   O F   T A B L E S
% ---------------------------
\addcontentsline{toc}{chapter}{List of Tables}
\listoftables
\cleardoublepage
\phantomsection		% allows hyperref to link to the correct page

\begin{comment}
% L I S T   O F   A B B R E V I A T I O N S
% ---------------------------
\renewcommand*{\abbreviationsname}{List of Abbreviations}
\printglossary[type=abbreviations]
\cleardoublepage
\phantomsection		% allows hyperref to link to the correct page

% L I S T   O F   S Y M B O L S
% ---------------------------
\printglossary[type=symbols]
\cleardoublepage
\phantomsection		% allows hyperref to link to the correct page
\end{comment}

% Change page numbering back to Arabic numerals
\pagenumbering{arabic}