design.tex

\documentclass[thesis]{subfiles}
\begin{document}

\chapter{Design and Implementation}%
\vspace*{-1em}
In \autoref{sec:intro} the basics of \gls{skill} and Rust were explained.
This section will feature the design and implementation of the common and generated Rust code.
The first sections will present problems that arise from Rusts type system.
Afterwards the solution for them will be presented.
These sections are the most elaborate ones as the decisions have far reaching consequences and differ the most from the other implementations.
Lastly the generated code and the resulting architecture will be covered.
The covered parts mostly follow the reference implementations.

\section{Cyclic Graphs in Rust}\label{sec:graph}
  \gls{skill} allows the creation of graphs with its references~\autocite[9]{skill-dis} as most languages do.
  This is generally not a problem and sometimes needed to express the required data structure.
  Rust however prevents the creation of cycles with references, which will be demonstrated in the following sections.
  In this section different approaches are explored that produce cyclic graphs in Rust.
  It will roughly follow the recommendation of \citetitle{rust-faq}\autocite{rust-faq} and will show the problems that arise in combination with \gls{skill}.

  \subsection{Native Cycles}
    In \autoref{lst:cyclesOne} a na\"ive implementation of a \Node containing another \Node is shown.
    This looks simple but it is what a cyclic graph boils down to.
    There has to be an object that doesn't exclusively own memory but references it.
    Without that detail it would only be possible to create a tree.
    This example fails as there is no \Node object before the root \Node~\codr{x}.

    \LstTikzBox{\cyclesOne}[.35\linewidth]{data/cycle_1.rs}
    \LstTikzBox{\cyclesTwo}[.5\linewidth]{data/cycle_2.rs}

    \begin{figure}[ht]
      \captionsetup{type=lstlisting}
      \subfloat[Na\"ive Implementation]{\usebox{\cyclesOne}\label{lst:cyclesOne}} \hfill%
      \subfloat[Defered Next]{\usebox{\cyclesTwo}\label{lst:cyclesTwo}}
      \caption{Rust, no Cycles Allowed}\label{lst:cycles}
    \end{figure}

    \autoref{lst:cyclesTwo} uses the \codr{Option} wrapper introduced in \autoref{sec:rustErr}.
    This allows the creation of the initial \Node object \codr{x}.
    It is further possible to assign the root object \codr{x} to the child object \codr{y}.
    But from that point on problems appear.
    First of all, \codr{y} does not live long enough -- this is the direct result of the lifetime specifier.
    Secondly, \codr{y} has to be assigned to \codr{x.next} and with that \codr{x} needs to be mutable.
    This should sound familiar to the problems shown in \autoref{sec:rustBorr}.
    Since \codr{x} is already borrowed by \codr{y.next}, \codr{x} can't be borrowed mutable again to assign \codr{y} to it.

  \subsection{Pointers in Rust}
    Coming from a C++ background the next thing that comes to mind would be (raw) pointers.
    Pointers were not introduced in \autoref{sec:rust} and the reason for that is, that they are not a type commonly used in Rust~\autocite[Raw Pointers]{rust-book1}.
    In \autoref{lst:pointers} it can be seen why this is the case.

    \autoref{lst:pointersOne} shows the basic usage of pointers, also named `raw pointers'.
    Raw pointers differ from references and smart pointers in the following points~\autocite[Unsafe Rust]{rust-book}: Pointers~\ldots
    \begin{itemize}
      \item are allowed to ignore the borrowing rules by having both immutable and mutable pointers or multiple mutable pointers to the same location
      \item aren't guaranteed to point to valid memory
      \item are allowed to be null
      \item don’t implement any automatic cleanup
    \end{itemize}
    A pointer to the \String \codr{s} is assigned to \codr{ps} in line 3.
    In line 6 \codr{s} is accessed through \codr{ps}.
    To do this \codr{unsafe} code is involved.
    Unsafe code allows the following~\autocite[Unsafe Rust]{rust-book}:
    \begin{itemize}
      \item Dereference a raw pointer
      \item Call an unsafe function or method
      \item Access or modify a mutable static variable
      \item Implement an unsafe trait
    \end{itemize}

    \LstTikzBox{\pointersOne}[.41\linewidth]{data/pointer_1.rs}
    \LstTikzBox{\pointersTwo}[.46\linewidth]{data/pointer_2.rs}
    \begin{figure}[ht]
      \captionsetup{type=lstlisting}
      \subfloat[Pointers in Rust]{\usebox{\pointersOne}\label{lst:pointersOne}} \hfill%
      \subfloat[Problems with Pointers in Rust]{\usebox{\pointersTwo}\label{lst:pointersTwo}}
      \caption{Rust Pointers and Unsafe Code}\label{lst:pointers}
    \end{figure}

    Why pointers are not the solution for our graph problem and why they are uncommon in Rust code, becomes apparent in \autoref{lst:pointersTwo}.
    A pointer \codr{ps} is created that points to the mutable \String \codr{s}.
    Line 4 and 5 indicate that there might be an issue -- it is possible to create two \emph{mutable} references to the same value.
    Line 6 and 7 prove that the safety rules of Rust have been broken, as it is possible to use both \codr{rsm1} and \codr{rsm2} in methods that mutate \codr{s}.
    With these rules broken also thread safety comes undone and with that most of the incentive to use Rust is lost.
    % TODO if Ptr<T> would use pointers for the internal bookkeeping ... would that be faster?

  \subsection{Memory Arenas and Cells}\label{sec:memoryArena}
    The \autoref{sec:cell} introduced \UnsafeCellT and companion types.
    This section will explore an option to use these to create a cyclic graph.
    In line 8 of \autoref{lst:memoryArena} a mutable \Vec is created with two instances of \Node.
    In line 12 a new string literal is assigned to the first instance.
    In line 13 and 14 a reference cycle is created between the two \Foo instances.
    This is in contrast to \autoref{lst:cyclesTwo}, which failed.
    Apart from \UnsafeCellT, which solves the borrowing error, here a vector is used to store the \Node instances.
    This small detail fixes the lifetime issue.
    In line 15 a compiler error is raised as the second \Node instance is already borrowed immutable in line 13.
    That means that fields from the objects can't be modified if they are not also wrapped by a \UnsafeCellT.
    But that would defeat the purpose of the borrow rules.

    \LstTikzFig{data/unsafecell.rs}{Breaking Mutability Rules}{lst:memoryArena}

  \subsection{Smart Pointer}
    The term smart pointer might be familiar from C++.
    In Rust there is \RcT which is a reference counting wrapper that acts as pointer and it is comparable to \codr{std::shared_ptr<T>} from C++.
    This smart pointer uses two integers to count how many \emph{weak} and \emph{strong} references there are to the owned data.
    If the strong counter reaches zero the destructor of the contained value is called by \RcTs destructor.
    The memory is released once the weak counter reaches zero too.
    This means there is only one memory allocation which leads to better cache locality and this increases speed.
    But it also means that the memory can only be freed once the last weak pointer is destructed, which might be unwanted.%
    ~\autocite[std::rc::Rc]{rust-doc}

    The semantics of \RcT are the following.
    It is possible to have any number of \RcTs and \WeakTs to the same \T.
    If there is more than one \RcT or a \WeakT to the same \T it is only possible to access \T in an immutable way.
    Further can \RcT instances be downgraded to \WeakT and if the strong count has not yet reached zero it is possible to upgrade \WeakT instances to \RcT.
    This means that this approach suffers from the same issue that was encountered in \autoref{sec:memoryArena}.%
    ~\autocite[std::rc::Rc]{rust-doc}

    The solution to this issue is to use an additional wrapper \RcRefCellT.
    \RefCellT uses internally \codr{UnsafeCell<T>} and provides the means to enforce the borrowing rules at runtime by using an integer counter.
    When calling \codr{borrow()} or \codr{borrow_mut()} on \RefCellT it will not return a \codr{&T} or \codr{&mut T}, instead \RefT and \RefMutT are returned.
    These wrappers will increment the appropriate counters on construction and decrement them on release.
    If the borrow rules would be violated, by returning a \RefT or \RefMutT, the afore mentioned functions cause a \panic.
    Alternatively there are \codr{try_*} versions of the functions that return \codr{Result<T, E>}.%
    ~\autocite[std::cell::RefCell]{rust-doc}

    \LstTikzFig{data/rcrefcell.rs}{Smart Pointer to Cell to Value}{lst:rcrefcell}

    \autoref{lst:rcrefcell} shows a working example that solves the encountered problems so far.
    Now \Node contains a \codr{Vec<T>} that stores \WeakT.
    It is very important that it is \WeakT and not \RcT as \RcT would result in a memory leak.
    This is the case as \codr{a} and \codr{b} would keep the strong counter above zero for each other.

  \subsection{Indices as Pointers Replacement}
    Another solution for graphs is something that is similar to \glspl{ecs}.
    In an \gls{ecs} an `object' is represented through an entity that is an identifier, e.g.~an integer.
    Components contain the data of entities and are stored usually in an indexable, continuous structure.
    Systems are responsible to use and modify components, based on logic that uses other components and entities.%
    ~\autocite[209]{sfml}
    The \gls{ecs} pattern provides composition over inheritance as the entity has no information about the systems using it and the assigned components.
    \glspl{ecs} are most commonly used by game engines as they result in fast code and it is easier to write reusable code with them~\autocites[209]{sfml}{ecs-acc-game}{ecs-hash}.

    In the rust community \gls{ecs} like structures are in discussion as possible solutions to cycles and graphs~\autocites{rust-graph-r4cpp}{rust-graph-leipzig}{rust-graph-niko}{rust-graph-exyr}.
    An prominent example for an implementation of an \gls{ecs} is the \emph{specs}\autocite{rust-specs} library that is used for a \gls{gui}\autocite{rust-xi} and small engines~\autocites{rust-amethyst}{rust-rhusics}.

    In \citetitle{skill-scala}\autocite{skill-scala} a similar approach to the components of an \gls{ecs} is explored.
    Here each field is stored in a continuous container, one container per field for read objects and one for new ones.
    Through testing of the changed architecture it was found that reading and writing was fast but the access of fields in objects were slower.
    The reason for that is that the fields are not necessarily close in memory to the proxy objects, leading to cache misses.%
    ~\autocite{skill-scala}

    While an \gls{ecs} or the optimisation in \citetitle{skill-scala}\autocite{skill-scala} seems favorable to the previous solutions it was ruled out by supervisor Timm Felden.
    His main argument is that an identifier like an index into a container is worse than a pointer.
    If a container is resized, all indices have to be updated.
    That, however, is only possible if all identifiers, that are using the indices, are known and accessible by the system, which can not be guaranteed.
    In case that an proxy object would be used, as in \citetitle{skill-scala}\autocite{skill-scala}, it would prompt a similar problem to the one discussed in this section.
    All proxy objects would need to be able to access the container that store their field data.
    These containers would have to be modified in case that an object is added and the data in the containers would also have to be modified through the proxy objects.
    That results in a conflict with Rusts borrow rules.

\section{Inheritance in Rust}\label{sec:inheritance}
  \LstTikzBox{\inheritanceJava}[.25\linewidth]{data/inheritanceE.java}[language=Java]
  \begin{wrapfigure}{r}{0.38\textwidth}
    \vspace*{-1.825\baselineskip}% This sucks
    \captionsetup{type=lstlisting}
    \begin{center}
      \usebox{\inheritanceJava}
    \end{center}
    \vspace*{-\baselineskip}% this sucks too
    \caption{Inheritance in Java}\label{lst:inheritanceJava}%
    \vspace*{-\baselineskip}% I hate wrapfig so much
  \end{wrapfigure}
  Rusts inheritance differs from common \gls{oop} languages.
  In Rust \structs are just a collection of data and can not inherit other \structs or make use of code reuse through inheritance.
  \traits  on the other hand can inherit multiple \traits, as can be seen in \autoref{lst:inheritance}.
  \codr{trait B} \emph{requires} that \codr{trait A} is implemented for whatever type \codr{B} is implemented for.
  That makes it also possible to call methods from \codr{A} on instances of type \codr{B}.
  However it is not possible to assign a variable of type \codr{&B} to a variable that expects a type of \codr{&A}.
  The need for a reference (\codr{&}) comes from the fact that \codr{B} is just a \trait and can't be instantiated.
  A data pointer to a \struct instance is required to create a trait object of type \codr{B}, seen in line 11.

  \gls{skill} uses single inheritance~\autocite{skill-tr} as present in the Java example seen in \autoref{lst:inheritanceJava}.
  In this section techniques are explored that can be used to mimic single inheritance in Rust.

  \LstTikzBox{\inheritanceOne}[.445\linewidth]{data/inheritance.rs}[lastline=7]
  \LstTikzBox{\inheritanceTwo}[.44\linewidth]{data/inheritance.rs}[firstline=9,firstnumber=9]
  \begin{figure}[ht]
    \captionsetup{type=lstlisting}
    \usebox{\inheritanceOne}\hfill
    \usebox{\inheritanceTwo}
    \caption{Trait Inheritance}\label{lst:inheritance}
  \end{figure}

  \subsection{Inheritance through Composition}%
    \LstTikzBox{\inheritanceComposition}[.25\linewidth]{data/inheritanceComposition.rs}
    \begin{wrapfigure}{r}{0.38\textwidth}%
      \vspace*{-\baselineskip}% This sucks
      \captionsetup{type=lstlisting}%
      \begin{center}%
        \usebox{\inheritanceComposition}%
      \end{center}%
      \vspace*{-\baselineskip}% this sucks too
      \caption{Inheritance emulated with Composition}\label{lst:inheritanceComposition}%
    \end{wrapfigure}%
    Instead of inheritance Rust advocates composition.
    From that perspective the code from \autoref{lst:inheritanceComposition} would represent the type hierarchy present in \autoref{lst:inheritanceJava}.
    This has a few nice properties.
    The user would be working with types and not trait objects and thus the code would not use virtual functions.
    Further can up casts be performed by returning a borrow to the contained super type, but on the other hand, down casting becomes impossible as the super component has no knowledge about the child component.
    Since the memory layout of \structs is undefined no assumption about a pointer offset can be made~\autocite[0079-undefined-struct-layout]{rust-rfc}.
    As alternative an option from \autoref{sec:graph} could be used e.g. \codr{Option<Rc<RefCell<T>>>} to create inheritance cycles.
    That would however degrade the usability and require linear time or memory to perform the casts.

  \subsection{Inheritance through Traits}\label{sec:magic}
    If a type hierarchy like \autoref{lst:inheritanceJava} has to be realized in Rust another option is to use \traits, which would result in something akin to \autoref{lst:inheritanceTrait}.
    The `real' types have the suffix \codr{Proper} and the access \traits have the original type name.
    This naming scheme improves the usability for the user of the code as the user will most of the time have to use trait objects.
    While inheritance can be expressed this way it has a few quirks that have to be improved upon.
    \begin{itemize}
      \item Down casting is impossible as there is no cast function or keyword in the language to go from a \trait to a \struct, or to a \trait.
      \item Up casting only works for the `proper' type and not the access \trait that emulates inheritance -- review \autoref{lst:coercionTwo}.
    \end{itemize}

    \LstTikzBox{\inheritanceTraitOne}[.25\linewidth]{data/inheritanceTrait.rs}[lastline=7]
    \LstTikzBox{\inheritanceTraitTwo}[.6\linewidth]{data/inheritanceTrait.rs}[firstline=9,firstnumber=9]
    \begin{figure}[ht]
      \captionsetup{type=lstlisting}
      \usebox{\inheritanceTraitOne}\hfill%
      \usebox{\inheritanceTraitTwo}
      \caption{Emulated Inheritance with Traits}\label{lst:inheritanceTrait}
    \end{figure}

    To solve these two issues a \cast function has to be created that is able to create a trait object from another.
    In \autoref{sec:stg} trait objects were introduced as fat pointer and this property can be abused to implement the \cast function.
    The first field of a trait object is the data pointer to the \struct and copying the pointer is no issue.
    However the second field is more difficult to fill as the correct vtable pointer has to be created.
    Fortunately, Rust allows the creation of a trait object from a \codr{null} pointer which can be seen in \autoref{lst:nullTraitObject}~\autocite[2.2. Exotically Sized Types]{rust-nom}.%
    ~\autocite{rust-digg}

    \LstTikzFig{data/nullTraitObject.rs }{Obtaining a VTable from \codr{null}}{lst:nullTraitObject}

    \autoref{lst:nullTraitObject} shows how to obtain the vtable pointer.
    There is a \codr{Proper struct} and a \codr{trait Object} that is implemented for \codr{Proper}.
    Apart from Rusts memory layout, where the compiler may reorder and add padding to fields, Rust also supports C-style memory layout with the \codr{#[repr(C)]} annotation.
    This is needed for the \TraitObject \struct which allows casting trait objects to it and thereby accessing the two pointers.
    \codr{()} is the \emph{unit type} comparable to \codc{void}\autocites[repr(C)]{rust-nom}[Defining and Instantiating Structs]{rust-book}.
    In line 13 a \codr{null} pointer is created with the type of \codr{Proper} and then casted to a trait object of type \codr{Object}.
    This trait object is then \codr{transmuted} to a \TraitObject instance.
    \codr{_} is replaced by the compiler with the type of the parameter.
    Through the interface of \TraitObject the vtable pointer can be accessed easily.

    Once the vtable pointer has been obtained the two pointers can be used to create a \TraitObject object.
    This object can be transmuted to a normal trait object as if it was created by the \struct through an implicit cast.
    The last detail for the \cast function would be a way to determine which type to get the vtable from.
    This can be done by either a lookup table realized through an array or a function with conditional branches.
    Both can be generated through the code generator.

    The outstanding issue with this approach is that it has to be applied to the values themself.
    Any normal wrapper would inhibit the ability to perform these casts.

  \subsection{C-Style Memory Layout}
    Similarly to the previous section is the C-memory layout used to allow for casts not otherwise possible, like it is shown in \autoref{lst:inheritanceStruct}.
    The field definitions have to appear in the same order, to create the same memory layout, for all types in a type hierarchy~\autocite[repr(C)]{rust-nom}.
    This approach has the issue that functions still wouldn't be inherited and would have to be implemented by the user, repeatedly, for all valid \structs.
    Similarly to the \traits there is an issue with casting if the memory of the \struct is managed by a wrapper type.
    A nice property about this approach is that it fits better in normal Rust code and implicit casts to \codr{traits} can still happen as the proper type is used.

    \LstTikzFig{data/inheritanceStruct.rs}{Inheritance with C-Memory layout and Structs}{lst:inheritanceStruct}

\section{Support Cyclic Graphs and Struct Inheritance}
  This section will focus on the implementation of the discussed solutions of \autoref{sec:graph} and \autoref{sec:inheritance}.
  The wrapper is named \PtrT since it provides the functionality of working with the type \T almost as if it was being pointed to by a pointer without restrictions.
  More concrete means this that this wrapper enables \T to be passed around with reference counting and runtime borrow rules checking while being able to be cast to different types and trait objects.

  \subsection{Memory Layout}
    The majority of the \PtrT type consists of \RcT and \RefCellT, combined into one cohesive wrapper.
    That means the original source code was copied and combined.
    This was needed as this type is supposed to be able to be castable, meaning that the contained value should be able to represent a \struct or trait object.
    Without this manual combination the reference counting and mutability state enforcement would inhibit proper casting.

    \LstTikzBox{\ptrStruct}[.42\linewidth]{data/ptrStruct.rs}
    \LstTikzBox{\rcRefCellStruct}[.42\linewidth]{data/rcRefCellStruct.rs}
    \begin{figure}[ht]
      \captionsetup{type=lstlisting}
      \subfloat[Memory Layout from \PtrT\label{lst:ptrStruct}]{\usebox{\ptrStruct}}\hfill%
      \subfloat[Memory Layout from \RcT and \RefCellT\label{lst:rcRefCellStruct}]{\usebox{\rcRefCellStruct}}
      \caption{Memory Layout Comparison}\label{lst:memoryLayout}
    \end{figure}

    Merging of the to types results in the memory layout seen in \autoref{lst:ptrStruct}.
    Compared to \autoref{lst:rcRefCellStruct} this uses one additional pointer.
    \RcT only needs one pointer for the \codr{RcBox<T>} that contains the meta data as well as the value.
    The \codr{PhantomData<T>} is there to provide the compiler with information which \enquote{is used when computing certain safety properties.}\autocite[std::marker::PhantomData]{rust-doc}.
    \RefCellT doesn't need any pointers whatsoever.
    Since there can be many \PtrTs that point to the same data but have a different views\footnote{
      The data pointer is not so much the problem, but the vtable pointers from trait objects are.
    } the value can not be shared between the \PtrT instances.
    The type parameter \T is bound by \codr{?Sized}, which means that \T can be a type of known size, like a \struct and \T can also be of unknown size, like a dynamic array \codr{[usize]} where \codr{usize} is the unsigned integer as element type~\autocite[std::marker::Sized]{rust-doc}.

  \subsection{Casting with \texttt{Ptr<T>}}
    The implementation of casting for \PtrT uses the trait object casting as well as the C-style memory layout casting that was introduced in \autoref{sec:inheritance}.
    That means that for every \struct of type \T there is an accessor \trait that inherits all super accessor \traits.
    This combination provides the user with high flexibility of trait objects while keeping the non virtual function calls in most cases.
    This is the case as the user can work with \structs instead of trait objects in most places.
    It also means that the user can use the accessor \traits as bound to implement the logic for all types without manual code duplication.

    \LstTikzFig{data/cast.rs}{Cast method of \PtrT}{lst:cast}

    \autoref{lst:cast} shows the commented code to cast any \PtrT to \codr{Ptr<U>}, where \T and \U can each be a \struct type or a \trait type.
    The \CastAble trait bound is needed to call \codr{cast_id()} on \U.
    With both \ids the lookup table can be accessed and depending on the value of \OptionT (\SomeT or \None) the cast will be performed or not.
    The lookup table is implemented as a $N \times M$ matrix, where the elements are an \codr{Option<VTable>}, which means that the \struct and accessor \trait are handled equally.
    What is interesting about this function and Rusts generics is, that the code does the same thing for every \T and every \U.
    That means that even if a \struct is cast to another \struct a trait object is created and the vtable will be inserted into it as if \U was the accessor trait.
    Fortunately the vtable is at index 1 and data at index 0 because \codr{transmute} will cut the additional pointer off in case \U is a \struct type.

  \subsection{Consequences of \texttt{Ptr<T>}}\label{sec:badptr}
    \PtrT is slower than a raw pointer.
    This slowdown can be attributed to the enforcement of the borrow rules and the memory fragmentation that is created through the small allocations.

    Using \PtrT means also that the code using \PtrT and its companion types can't be parallelized.
    The issue is that \PtrT is reference counting to enforce borrow rules as well as the lifetime of the managed memory.
    That means that both, borrowing and cloning has to happen in a synchronized way to achieve object parallelism.
    But, the parallelism benefits can only be gained if the fields of the objects can be serialized in parallel.
    The binary format is designed in such a way that the field data can be read in parallel.
    With a little extra work parallel writing is also possible.
    To support that kind of parallelism at a field level, all fields in the objects would have to be enclosed in something like an \UnsafeCellT for interior mutability.

    \PtrT would have to be made from a \ArcT and \RwLockT, instead of \RcT and \RefCellT, to allow for object parallelism.
    Which means that every object access would be behind a mutex and multiple atomic operations~\autocite[std::sync::Arc, std::sync::RwLock]{rust-doc}.
    To achieve field parallelism fields have to be wrapped in \UnsafeCellT for interior mutability, since threads are involved that means that either \MutexT or \RwLockT\footnote{
      \MutexT and \RwLockT are both using \UnsafeCellT internally.%
      ~\autocite[std::sync::Mutex, std::sync::RwLock]{rust-doc}
    } have to be used.
    Leading to possible two mutex locks per field access when serialisation of the value and also for all accesses the users does.
    Apart from the objective to use Rusts \emph{type system} for the thread safety guarantees it is further highly unlikely that the mutex locks do not ruin the performance.

    Another consequence of \PtrT is, that the specification independent code can not be contained in a standalone create which can be used as library.
    \PtrT depends on the lookup table which has to be generated.

  \subsection{Optimisations}
    Since \PtrT is used in many components some time was spent to see how it could be made faster.
    The next sections will present optimisations that were thought of.

    \vspace*{-.25em}
    \subsubsection{Lookup vs Conditionals}
      The initial version of \PtrT used conditionals to check whether the cast is valid to make or not.
      It would then create the vtable pointer as introduced in \autoref{sec:magic}.
      The conditional logic was contained in a \trait that was implemented by a macro that only needed the valid type names.
      That made \PtrT reusable in other projects not related to \gls{skill}.

      In an attempt to improve the performance of \cast the final implementation uses a lookup table.
      The lookup table contains the vtable pointers and absence of a pointer indicates an invalid cast.
      A performance improvement could however not be measured.
      An explanation for that is, that the trait objects are still created and that branch-prediction was in this case roughly as efficient as an access into a 2D array.

      \vspace*{-.25em}
    \subsubsection{Disabling Reference Counting and Borrow Checking}
      A more brutal optimisation was an additional type to \PtrT.
      It was named \HazardPtrT as there was nothing safe about that type.
      \HazardPtrT is constructed from a \PtrT and because it was declared in the same module as \PtrT it is able to access the private fields of \PtrT.
      In the constructor \HazardPtrT would then take the pointer to the value of \PtrT.
      This allowed to skip the reference counting and the borrow rules checking.
      Additionally were the bounds on \HazardPtrT changed to include only \structs.
      With that it was possible to create a \cast function that only casts a pointer to another pointer -- no support for trait object casts is necessary in the internal code.
      Further were these casts unchecked.
      \HazardPtrT was then applied to internal code that used \PtrT to serialise field data.
      In performance tests the use of \HazardPtrT resulted in a speed up of $\times 1.2$ compared to \PtrT.

      \HazardPtrT was not kept however, as its unsafe nature goes strongly against the values that Rust represents.
      This experiment showed that the wrapper types used throughout the code base (\RcT, \RefCellT) do inflict a significant performance penalty.
      \PtrT instances are used by pools that contain a shared vector of \PtrT instances (\codr{Rc<RefCell<Vec<Ptr<T >>>>}\footnote{
        \codr{Rc<RefCell<Vec<Ptr<T>>>>} $\approx$ \codr{Rc<RefCell<Vec<Rc<RefCell<T>>>>>}
      }) which means that another speedup could be gained if these wrappers were unnecessary.
      \vspace*{-.25em}

\section{Binding Architecture}
  This section will discuss the created architecture of generated bindings and the changes made to the one introduced in \autoref{sec:skillArch}.
  While the generated code is a central point of this thesis, the generator itself is not so much.
  The reason for that is, that the generator differs in a few points from the reference generators of other languages.
  This is the case as the same infrastructure was used and no modifications had to be made to support Rust.

  \autoref{fig:archActual} shows the actual architecture of the generated code.
  Additionally to the relationships seen in the previous architecture this diagram features \emph{traits}, \emph{usage}, if they were generated or not and what kind of type they are.
  This means that more types and relationships are featured, making this diagram more complicated.

  \begin{figure}[H]
    \centering
    \input{data/actualArch}
    \caption{Binding Architecture}\label{fig:archActual}
  \end{figure}

  Not depicted in the image are:
  \begin{itemize}
    \item \ForeignPool, \ForeignObject and \ForeignFieldDeclaration as they have the same relationships as the \UserType equivalent.
    \item Convenience types like strongly typed integer or magic numbers.
    \item \StringBlock as it is composed into \StringPool and only \FileReader and \FileWriter use it internally.
    \item Iterators that are used to iterate over instances of type hierarchies and pools.
    \item \SkillString, \SkillFail, \PtrT and \PtrT companion types like \WeakT, as they are used, had, and created by most components.
  \end{itemize}

  \subsection{Rust Integration}
    Cargo uses a manifest file named \cod{Cargo.toml}.
    In this file the binary or library is described.
    This includes dependencies, build settings, versions, tests configurations and benchmarks configurations.
    The file is of utmost importance for the user of the generated code as this will allow the easy inclusion in the target project.%
    ~\autocite[The Manifest Format]{rust-cargo}

    Accompanying there are \cod{mod.rs} and \cod{lib.rs} or \cod{main.rs} files.
    These files regulate the visibility of the different modules -- where each file and folder is a module.
    \cod{mod.rs} files are used in directories to specify the visibility of the contained files as well as to flatten the module hierarchy.
    \cod{lib.rs} or \cod{main.rs} files are at the root of the \cod{src} directory and mark the begin of a library or executable.
    These files allow additionally to specify external crates, enable features and mute warnings.
    Further can additional modules be declared in the files to allow for fine granular visibility.%
    ~\autocite[7. Modules]{rust-book}

    The \cod{Cargo.toml} and \cod{lib.rs} files are quite easy to generate.
    For \cod{Cargo.toml} only the library name has to be substituted.
    And for the \cod{lib.rs} file the flattening of the module structure has to be performed.
    This is done to allow users to access \Foos pool with \codr{use user_project::FooPool} instead of \codr{use user_project::foo::FooPool}.

  \subsection{\glsentrytext{skill} File}
    \SkillFile is the root of the \gls{api} for the user.
    \SkillFile provides functions to create and open \gls{skill} files.
    An instance of \SkillFile is also the place where the user is able to interact with \UserTypePools and \StringPool.
    This type is straight forward to generate, as it is mostly a composite type that provides access to its components.
    Components are \UserTypePools and \StringPool.
    Only these components have to be inserted in otherwise static code.

    However, \SkillFile is constructed by a \SkillFileBuilder.
    This separation is necessary since all attributes have to be initialized on construction.
    That is not possible without a wrapper like \OptionT.

    Additionally there is the \PoolMaker \trait.
    This \trait is used by the \FileReader and is only needed for a better separation of specification independent, and generated code.
    This separation is kept to allow for a common standalone crate of the specification independent code if a casting method is found that allows that.

  \subsection{User Definitions}
    For the user defined types a few types have to be generated that work closely together to provide the user with a convenient \gls{api}.
    Since there is no benefit towards compile time, by splitting code into multiple files\footnote{
      For example benefit C and C++ from forward declarations of types instead of including the header files.
    }, each of these types reside in one file per user type definition.

    \subsubsection{User Type}
      Type definitions are translated to \structs and \traits.
      The \structs contain fields that were specified for its super types as well as the fields that were specified for itself.
      The accessor \traits for the \structs contain, for every field that is not a super field, an accessor method and inherits its super accessor \traits and interfaces.
      These methods are different depending on the kind of accessed type.
      Types that are not trivial to copy (e.g. \HashMap) are passed by reference.
      Since a borrow occurs in that case there have to be three methods.
      Two getters, one that returns a reference to an immutable value and another that returns a reference to a mutable value.
      The third method is the setter that accepts a value that replaces the original one.
      Copyable types are accessed through functions that use the plain value.
      All super accessor \traits and interfaces, as well as \SkillObject, \ForeignObject and \Deleteable are then implemented for the \struct.

      \autoref{lst:userType} shows generated code of the \UserType named \Age.
      The fields in \Age, that are prefixed with \codr{z_}, are internal fields.
      Fields that the user named with a leading \codr{z} and non alphabetic or numeric characters are escaped with an additional \codr{z}.
      The \skillid is used as id for the object at the serialization phase or for the user to access a particular object.
      The \typeid is the index into the vtable lookup table which is used to cast the objects.
      \foreigndata is a vector that stores data of fields that were not known at generation time.
      As previously mentioned is this data inaccessible for the user.
      Finally is \age the field that the user specified in the specification.

      \age needs accessors to be accessible outside of this module which are declared in the \AgeObject \trait.
      \AgeObject also inherits \SkillObject and therefore has to implement it and also the \Deleteable \trait.
      The \Deleteable trait provides an interface that allows the objects to be marked for deletion.
      This interface should not be visible to the user but there is no way to do that in Rust.

      Additionally to the types present in the users specification \Age also implements \ForeignObject that belongs to the \Foreign \struct.
      The \Foreign type is exclusively used to create an interface that allows the serialization of types and fields that were not known at generation time.

      \LstTikzFig{data/userType.rs}{Generated User Type Age}{lst:userType}

    \subsubsection{Type Pools}
      The biggest change compared to \autoref{fig:archDesire} appears around the \UserTypePool.
      This type had to be split up into five.
      The \Pool type is needed for code reuse as Rust doesn't provide inheritance.
      Most of the code that is needed for \UserTypePools is specification independent and can be reused without issue.
      The problem with code reuse through composition is that it is difficult to provide the general, contained type with the containing \struct's data or special functions.
      In case that the containing \struct calls the functions of \Pool data and special functions can be made available.
      But if the contained \struct is called by something else a dependency cycle occurs that has to be broken with options from \autoref{sec:graph}, which can lead to violations of borrow rules.
      The \Pool is used by other objects than the \UserTypePools that do not know of the \UserTypePools.
      Because of that \UserPartsMaker exists which externalizes the special functions of \UserTypePool so that they are callable by \Pool.
      Since \UserTypePools are not a \Pool and because they have to be able to be stored in a container the \PoolProxy \trait was created.
      \PoolProxy is an interface for \UserTypePools that provides access to the \Pool component in \UserTypePools as well as the ability to store \UserTypePools of different \UserTypes in containers.

      Further are \PoolProxy and \PartsMaker responsible to create \UserFieldDeclaration instances.
      \PartsMaker is used by \Pool to create \UserFieldDeclaration instances that are to be read.
      \PoolProxy on the other hand is needed to create \UserFieldDeclaration instances that are missing from the serialized data but were present in the specification.

    \subsubsection{Field Declarations}
      Lastly there are \FieldDeclarations, which are responsible for the serialisation of fields from \UserTypes.
      For each field a \FieldDeclaration is generated that implements how the field data is read and written.
      They also handle the setup of the different chunks that are involved if the file that is read has multiple blocks.

  \subsection{VTable-Lookup-Table}
    The lookup table is implemented as a $N \times M$ matrix, where $M$ is the amount of types $+1$ to accommodate the foreign type.
    $N=M+1$ to additionally accommodate the shared \trait \SkillObject.
    The memory footprint could be reduced by using a sparse array at the trade-off for lookup speed.
    The matrix uses \codr{Option<VTable>} instances as elements -- if the value is \codr{None} the cast is invalid, otherwise the correct vtable is obtained.
    The generator produces the correct vtables with the technique introduced in \autoref{sec:magic}.
    For the lookup to be efficient\footnote{
      \codr{HashMap} was testes as replacement for an array but was found to be inefficient.
    } all user types as well as \codr{Foreign} and \SkillObject have to be assigned an index into the matrix.
    This is done by the generator and the reason to why there is not a common crate that contains specification independent code.

  \subsection{Specification Independent Code}
    Most of the architecture is separate from the specification and doesn't have to be generated by a generator.
    This includes the reading and writing of the build in types, the parsing and writing of the files, the string pool and the traits that need to be implemented.
    As the lookup table has to be generated which means that \PtrT is dependent on generated code and in turn most of the specification independent code as well.
    This section focuses on some of more interesting parts of these types.

    \subsubsection{Strings and their Pool}
      Strings have to be managed and known by the \StringPool.
      That means that a \String may not be modified by the user directly.
      The reason for that is, that type and field names are managed strings too.
      A direct modification from the user might inadvertently change the representation of the type system.

      To conform to these requirements and the need for an id for each string -- that is obtainable through the string -- a wrapper is needed for \String.
      Since inheritance is not an option \String was made a component of \SkillString.
      \SkillString has to provide a method to obtain an immutable reference to the contained \String to be somewhat compatible with other libraries.
      Since the removal of a \SkillString that represents a literal used by a type would lead to problems there is no way for the user to delete a \SkillString explicitly.
      The explicit deletion is replaced with automatic pruning on writing.
      Since all \SkillString have to be wrapped in an \RcT the counters can be used to check whether the \SkillString has to be serialized or can be discarded.

    \subsubsection{Foreign Types and Fields}
      Special types are used if the field or type encountered upon deserialisation was not known at the time the code was generated.
      The fields themself are represented through a Rust \enum which can be thought of as a tagged \codc{union}.
      The foreign field definitions are special in that they deserialise their data only if it has to be written.
      This is possible as the user has no way to interact with the foreign types or fields in the Rust implementation\footnote{%
        In \citetitle{skill-tr13}\autocite{skill-tr13} the \gls{api} to access foreign types and fields was a feature, in \citetitle{skill-tr}\autocite{skill-tr} it was changed to be a core requirement. For this thesis supervisor Timm Felden said to treat it as feature.
      }.

      If a type has a known ancestor in a type hierarchy that type will be used instead to represent the foreign one.
      That way the user's code can work with the known fields without knowing anything about the foreign type.
      In turn that means that every user type has to have an array of \ForeignFieldData.
      In case that there is no known ancestor type the \Foreign type is used to represent the type.
      This type is not accessible by the user and only contains \ForeignFieldData.

    \subsubsection{Error and Handling}
      Return codes are the predominant way in Rust to report issue, which was introduced in \autoref{sec:rustErr}.
      The issue with return codes is that they are unsafe, as they can be ignored, and that they do not provide a lot of context by themself for debugging purposes.
      To improve the usability of these return codes the \codr{failure} crate~\autocite{rust-failure} has been chosen to enhance the error codes.
      The crate provides macros that extend the codes with the option to provide a backtrace.
      Additionally it allows for error messages that are created and formatted at runtime and are able to provide more context than a string literal.

      The error codes are implemented through 3 \enums.
      \SkillFail is the main \enum that the user interacts with.
      It can either contain a \codr{UserFail} \enum value or a \codr{InternalFail} \enum value.
      This distinction was made to further enhance the context of the error while keeping the amount of errors that the user has to react to at a minimum.

\end{document}