<commit_before>\makeatletter \@ifundefined{rootpath}{\input{../../setup/preamble.tex}}\makeatother
\worksheetstart{Roslyn Extension}{0}{Februar 10, 2015}{}{../../}
The chapter describes how the Roslyn C\# compiler was extended to support the constructs of \stmname described in \bsref{chap:stm_design}. \bsref{sec:roslyn_extension_strategy} describes the overall strategy, \bsref{sec:roslyn_lexer_parser_changes} describes the changes made to the lexer and parser while \bsref{sec:syntax_tree_transformations} presents examples of the transformations made on the syntax tree by the extension.
\label{chap:roslyn_extension}
\section{Extension Strategy}
\label{sec:roslyn_extension_strategy}
The Roslyn C\# compiler was extended by modifying the lexing and parsing phases with support for the language construct described in \bsref{chap:stm_design}. The extended parsing phase outputs an extended syntax tree containing direct representations of the language changes provided by \stmname. The syntax tree is then analyzed by identifying \stmnamesp constructs, followed by a transformation where any language extension is transformed into equivalent C\# code utilizing the \ac{STM} library described in \bsref{chap:implementation}. 

The transformation phase outputs a syntax tree containing only standard C\# code, executing the described \ac{STM} operations. This syntax tree is then passed to the remaining C\# compiler phases, utilizing its semantic analysis and code generation implementations. The approach is visualized in \bsref{fig:compiler_pipeline_extension}. The parser has been extended to output an extended syntax tree and transformation of this tree occurs before the binding and IL emission phases. The transformation phase utilizes both the extended syntax tree and symbol information gather through the Roslyn \ac{API}.
\begin{figure}[htbp]
\centering
 \includegraphics[width=1\textwidth]{\rootpath/worksheets/roslyn_extension/figures/compiler_pipeline_extension} 
 \caption{Extension occurs at the syntax tree and symbol level.}
\label{fig:compiler_pipeline_extension}
\end{figure}

The described approach was selected due to the following reasons:
\begin{enumerate}
\item As described in \bsref{subsec:roslyn_first_phase} the C\# lexer  uses a simple \bscode{switch} case to identify tokens by choosing the type of token to identify based on the first character of the token, while the parser uses a recursive descent technique, both of which are implemented by hand. Such techniques have a low degree of complexity compared to strategies such as \ac{LALR}. As such modifying the lexer and parser is simpler than would be the case if more complex techniques had been employed.
\item The Roslyn compiler generates the nodes composing its syntax tree along with factory methods and visitor pattern implementations based on the contents of an \ac{XML} file. Therefore adding new nodes to represents the extended language constructs, such as the \bscode{atomic} block and \bscode{retry} statement, amounts to adding definitions for theses nodes to the \ac{XML}, allowing the employed tool to generate source code for the new nodes.
\item As described in \bsref{sec:syntax_trees} Roslyn's syntax trees are designed to be fast to modify by reusing underlying green nodes instead of creating complete copies\cite[p. 6]{ng2012roslyn}. This speaks for conducting transformation on the level of the syntax tree despite its immutable implementation.
\item The Roslyn project has been designed to allow programmers to utilize the information gather during the compilation process by analyzing the syntax tree as well as the information in the symbol table and the results of semantics analysis. These parts of the compiler are exposed as a public \ac{API} allowing access to both syntactical and semantic information. Utilizing this \ac{API} during the transformation phases allows the transformation to draw on the existing semantical analysis to answer questions such as, what method is the target of a method invocation, without the need for implementing complex analysis.
\item By parsing a extended syntax tree and transforming it into a regular C\# syntax tree the existing semantical analysis and code emission implementations can be utilized.
\end{enumerate}

\section{Lexing \& Parsing Phases}
This section describes the changes conducted in order to extend the lexing and parsing phases of the Roslyn C\# compiler to support the constructs described in \bsref{chap:stm_design}.
\label{sec:roslyn_lexer_parser_changes}
\andreas[inline]{Should contain lexer and parser changes, and the modifications to the syntax tree, and how it is made (XML changes)}	
\subsection{Lexer Changes}
As described in \bsref{chap:stm_design} \stmnamesp introduces the three new \bscode{atomic}, \bscode{orelse} and \bscode{retry} keywords. As a result the lexer component has been extended to identify these keyword as tokens with the correct kind. The C\# lexer initially lexes keyword tokens as if they where identifies. If a identifies token can be determined to correspond to a keyword, a keyword token with the correct kind is returned instead. 

Allowing the lexer to identify the the new keywords required adding their definition to the lookup methods of the \bscode{SyntaxKindFacts} class. The \bscode{SyntaxKindFacts} class defines the \bscode{GetKeywordKind} which the lexer uses to identify the keyword kind of a identifier, if the identifier represents a keyword. Additionally the \bscode{SyntaxKindFacts} class defines the \bscode{GetText} method for determining the string representation of a keyword based on its kind, to which a definition of the new keywords where added.

To allow a token to represent the new keywords, the \bscode{AtomicKeyword}, \bscode{OrelseKeyowrd} and \bscode{RetryKeyword} entries where added to the \bscode{SyntaxKind} enumeration. As described in \bsref{subsubsec:roslyn_kinds}, the \bscode{SyntaxKind} enumeration contains a entry for each type of node, token, or trivia in C\#. Whenever the lexer identifies a occurrence of one of the new keywords, with the corresponding kind is return. For example a occurrence of the \bscode{atomic} keyword result in a token with the kind \bscode{AtomicKeyword} being returned.

\subsection{Syntax Tree Extension}
The design described in adds the \bscode{atomic}, \bscode{orelse} and \bscode{retry} constructs which the existing syntax tree can not express. Therefore the syntax tree must be extended to support these language constructs. As described in \bsref{subsec:roslyn_syntax_tree_generation} nodes composing the syntax tree, along with factory methods and the visitor pattern implementation, are generated on the basis of an \ac{XML} file. Adding additional nodes to the the syntax tree therefore amounts to definition them in the \ac{XML} notation, which has been done for the three previously mentioned constructs. \bsref{lst:roslyn_extension_tre_xml} shows the \ac{XML} defining the \bscode{AtomicStatementSyntax} node which represents a \bscode{atomic} block in the syntax tree. Line 1 defines the name and base class of the the node while line 2 defines its kind. The \bscode{AtomicStatement} kind has been added to the \bscode{SyntaxKind} enumeration as described previously. Line 3 defines a property on the node which holds the token representing the \bscode{AtomicKeyword} which starts the definition of the atomic blocks. The property has a constraint specifying the kind of on the token that can be associated with the property which is defined on line 4 as well as a comment given on lines 5-6. Line 11 defines a statement property which holds the block of statements associated with the defined \bscode{atomic} block. Line 18 defines a property containing a \bscode{SyntaxList} of \bscode{orelse} blocks associated with the \bscode{atomic} block. This relation ship has been modeled after the relationship between a C\# \bscode{try} statement and its \bscode{catch} clauses, as both have a zero to many association. Finally lines 25-29 defines a comment for the \bscode{AtomicStatementSyntax}, while lines 30-32 defines a comment for the factory method.

\begin{lstlisting}[label=lst:roslyn_extension_tre_xml,
  caption={AtomicStatement \ac{XML} definition},
  language=XML,  
  showspaces=false,
  showtabs=false,
  breaklines=true,
  showstringspaces=false,
  breakatwhitespace=true,
  morekeywords={Name, Base, Type}]  % Start your code-block

  <Node Name="AtomicStatementSyntax" Base="StatementSyntax">
    <Kind Name="AtomicStatement"/>
    <Field Name="AtomicKeyword" Type="SyntaxToken">
      <Kind Name="AtomicKeyword"/>
      <PropertyComment>
        <summary>
          Gets a SyntaxToken that represents the atomic keyword.
        </summary>
      </PropertyComment>
    </Field>
    <Field Name="Statement" Type="StatementSyntax">
      <PropertyComment>
        <summary>
          Gets a StatementSyntax the represents the statement to be executed when the condition is true.
        </summary>
      </PropertyComment>
    </Field>
    <Field Name="Orelses" Type="SyntaxList&lt;OrelseSyntax&gt;">
      <PropertyComment>
        <summary>
          Gets a SyntaxList containing the orelse blocks associated with the atomic statement.
        </summary>
      </PropertyComment>
    </Field>
    <TypeComment>
      <summary>Represents an atomic block.</summary>
    </TypeComment>
    <FactoryComment>
      <summary>Creates an AtomicStatementSyntax node</summary>
    </FactoryComment>
  </Node>
\end{lstlisting}

Declaration of transactional local variables, fields and parameters does not require modifications to the syntax tree as the standard nodes for these constructs allow a collection of modifiers to be associated with the declaration. Any atomic modifiers are simply added to the collection along with any other modifiers. 


\subsection{Parser Changes}
%error codes, const atomic, readonly atomic


\section{Syntax Tree Transformations}
\label{sec:syntax_tree_transformations}
%HUSK
\toby[i]{Evt. til valg af implementerings strategi: refer til at syntax træer kan blive modificeret hurtigt og med et lille memory overhead (den tredje key attribut omkring syntax træer)}
\kasper[inline]{Implementerings beskrivelse: error codes, lexer, parser, tvars, atomic block, replacement}

\subsection{Atomic Block}
Atomic and orElse block replacement

\subsection{Field Types}
\subsection{Properties}
\subsection{Local variables}
With or without type inference

\subsection{Member Accesses}
Accessing the .Value instead of the object directly

\subsection{Parameters}
Could also contain method and constructor argument replacement.<commit_msg>Section on parser changes<commit_after>\makeatletter \@ifundefined{rootpath}{\input{../../setup/preamble.tex}}\makeatother
\worksheetstart{Roslyn Extension}{0}{Februar 10, 2015}{}{../../}
The chapter describes how the Roslyn C\# compiler was extended to support the constructs of \stmname described in \bsref{chap:stm_design}. \bsref{sec:roslyn_extension_strategy} describes the overall strategy, \bsref{sec:roslyn_lexer_parser_changes} describes the changes made to the lexer and parser while \bsref{sec:syntax_tree_transformations} presents examples of the transformations made on the syntax tree by the extension.
\label{chap:roslyn_extension}
\section{Extension Strategy}
\label{sec:roslyn_extension_strategy}
The Roslyn C\# compiler was extended by modifying the lexing and parsing phases with support for the language construct described in \bsref{chap:stm_design}. The extended parsing phase outputs an extended syntax tree containing direct representations of the language changes provided by \stmname. The syntax tree is then analyzed by identifying \stmnamesp constructs, followed by a transformation where any language extension is transformed into equivalent C\# code utilizing the \ac{STM} library described in \bsref{chap:implementation}. 

The transformation phase outputs a syntax tree containing only standard C\# code, executing the described \ac{STM} operations. This syntax tree is then passed to the remaining C\# compiler phases, utilizing its semantic analysis and code generation implementations. The approach is visualized in \bsref{fig:compiler_pipeline_extension}. The parser has been extended to output an extended syntax tree and transformation of this tree occurs before the binding and IL emission phases. The transformation phase utilizes both the extended syntax tree and symbol information gather through the Roslyn \ac{API}.
\begin{figure}[htbp]
\centering
 \includegraphics[width=1\textwidth]{\rootpath/worksheets/roslyn_extension/figures/compiler_pipeline_extension} 
 \caption{Extension occurs at the syntax tree and symbol level.}
\label{fig:compiler_pipeline_extension}
\end{figure}

The described approach was selected due to the following reasons:
\begin{enumerate}
\item As described in \bsref{subsec:roslyn_first_phase} the C\# lexer  uses a simple \bscode{switch} case to identify tokens by choosing the type of token to identify based on the first character of the token, while the parser uses a recursive descent technique, both of which are implemented by hand. Such techniques have a low degree of complexity compared to strategies such as \ac{LALR}. As such modifying the lexer and parser is simpler than would be the case if more complex techniques had been employed.
\item The Roslyn compiler generates the nodes composing its syntax tree along with factory methods and visitor pattern implementations based on the contents of an \ac{XML} file. Therefore adding new nodes to represents the extended language constructs, such as the \bscode{atomic} block and \bscode{retry} statement, amounts to adding definitions for theses nodes to the \ac{XML}, allowing the employed tool to generate source code for the new nodes.
\item As described in \bsref{sec:syntax_trees} Roslyn's syntax trees are designed to be fast to modify by reusing underlying green nodes instead of creating complete copies\cite[p. 6]{ng2012roslyn}. This speaks for conducting transformation on the level of the syntax tree despite its immutable implementation.
\item The Roslyn project has been designed to allow programmers to utilize the information gather during the compilation process by analyzing the syntax tree as well as the information in the symbol table and the results of semantics analysis. These parts of the compiler are exposed as a public \ac{API} allowing access to both syntactical and semantic information. Utilizing this \ac{API} during the transformation phases allows the transformation to draw on the existing semantical analysis to answer questions such as, what method is the target of a method invocation, without the need for implementing complex analysis.
\item By parsing a extended syntax tree and transforming it into a regular C\# syntax tree the existing semantical analysis and code emission implementations can be utilized.
\end{enumerate}

\section{Lexing \& Parsing Phases}
This section describes the changes conducted in order to extend the lexing and parsing phases of the Roslyn C\# compiler to support the constructs described in \bsref{chap:stm_design}.
\label{sec:roslyn_lexer_parser_changes}
\andreas[inline]{Should contain lexer and parser changes, and the modifications to the syntax tree, and how it is made (XML changes)}	
\subsection{Lexer Changes}
As described in \bsref{chap:stm_design} \stmnamesp introduces the three new \bscode{atomic}, \bscode{orelse} and \bscode{retry} keywords. As a result the lexer component has been extended to identify these keyword as tokens with the correct kind. The C\# lexer initially lexes keyword tokens as if they where identifies. If a identifies token can be determined to correspond to a keyword, a keyword token with the correct kind is returned instead. 

Allowing the lexer to identify the the new keywords required adding their definition to the lookup methods of the \bscode{SyntaxKindFacts} class. The \bscode{SyntaxKindFacts} class defines the \bscode{GetKeywordKind} which the lexer uses to identify the keyword kind of a identifier, if the identifier represents a keyword. Additionally the \bscode{SyntaxKindFacts} class defines the \bscode{GetText} method for determining the string representation of a keyword based on its kind, to which a definition of the new keywords where added.

To allow a token to represent the new keywords, the \bscode{AtomicKeyword}, \bscode{OrelseKeyowrd} and \bscode{RetryKeyword} entries where added to the \bscode{SyntaxKind} enumeration. As described in \bsref{subsubsec:roslyn_kinds}, the \bscode{SyntaxKind} enumeration contains a entry for each type of node, token, or trivia in C\#. Whenever the lexer identifies a occurrence of one of the new keywords, with the corresponding kind is return. For example a occurrence of the \bscode{atomic} keyword result in a token with the kind \bscode{AtomicKeyword} being returned.

\subsection{Syntax Tree Extension}
The design described in adds the \bscode{atomic}, \bscode{orelse} and \bscode{retry} constructs which the existing syntax tree can not express. Therefore the syntax tree must be extended to support these language constructs. As described in \bsref{subsec:roslyn_syntax_tree_generation} nodes composing the syntax tree, along with factory methods and the visitor pattern implementation, are generated on the basis of an \ac{XML} file. Adding additional nodes to the the syntax tree therefore amounts to definition them in the \ac{XML} notation, which has been done for the three previously mentioned constructs. \bsref{lst:roslyn_extension_tre_xml} shows the \ac{XML} defining the \bscode{AtomicStatementSyntax} node which represents a \bscode{atomic} block in the syntax tree. Line 1 defines the name and base class of the the node while line 2 defines its kind. The \bscode{AtomicStatement} kind has been added to the \bscode{SyntaxKind} enumeration as described previously. Line 3 defines a property on the node which holds the token representing the \bscode{AtomicKeyword} which starts the definition of the atomic blocks. The property has a constraint specifying the kind of on the token that can be associated with the property which is defined on line 4 as well as a comment given on lines 5-6. Line 11 defines a statement property which holds the block of statements associated with the defined \bscode{atomic} block. Line 18 defines a property containing a \bscode{SyntaxList} of \bscode{orelse} blocks associated with the \bscode{atomic} block. This relation ship has been modeled after the relationship between a C\# \bscode{try} statement and its \bscode{catch} clauses, as both have a zero to many association. Finally lines 25-29 defines a comment for the \bscode{AtomicStatementSyntax}, while lines 30-32 defines a comment for the factory method.

\begin{lstlisting}[label=lst:roslyn_extension_tre_xml,
  caption={AtomicStatement \ac{XML} definition},
  language=XML,  
  showspaces=false,
  showtabs=false,
  breaklines=true,
  showstringspaces=false,
  breakatwhitespace=true,
  morekeywords={Name, Base, Type}]  % Start your code-block

  <Node Name="AtomicStatementSyntax" Base="StatementSyntax">
    <Kind Name="AtomicStatement"/>
    <Field Name="AtomicKeyword" Type="SyntaxToken">
      <Kind Name="AtomicKeyword"/>
      <PropertyComment>
        <summary>
          Gets a SyntaxToken that represents the atomic keyword.
        </summary>
      </PropertyComment>
    </Field>
    <Field Name="Statement" Type="StatementSyntax">
      <PropertyComment>
        <summary>
          Gets a StatementSyntax the represents the statement to be executed when the condition is true.
        </summary>
      </PropertyComment>
    </Field>
    <Field Name="Orelses" Type="SyntaxList&lt;OrelseSyntax&gt;">
      <PropertyComment>
        <summary>
          Gets a SyntaxList containing the orelse blocks associated with the atomic statement.
        </summary>
      </PropertyComment>
    </Field>
    <TypeComment>
      <summary>Represents an atomic block.</summary>
    </TypeComment>
    <FactoryComment>
      <summary>Creates an AtomicStatementSyntax node</summary>
    </FactoryComment>
  </Node>
\end{lstlisting}

Declaration of transactional local variables, fields and parameters does not require modifications to the syntax tree as the standard nodes for these constructs allow a collection of modifiers to be associated with the declaration. Any atomic modifiers are simply added to the collection along with any other modifiers. 


\subsection{Parser Changes}
As described in \bsref{subsec:roslyn_first_phase} the C\# parser uses a recursive decent strategy implemented by hand. As it is customary for recursive decent implementations, each construct has a method responsible for parsing that particular construct. For the new \bscode{atomic}, \bscode{orelse} and \bscode{retry} such a method has been added, while the methods for parsing local variable, field, parameters and properties have been modified to allow for a atomic modifier, as well as generating error messages for any unsupported modifier combinations such as \bscode{atomic const} and \bscode{readonly const}. Error are associated with the erroneous nodes as it is customary for the compiler. A later compilation phase generates error messages and cancels code emission if any errors where present.

\bsref{lst:parse_atomic_block} shows the \bscode{ParseAtomicBlock} method responsible for parsing a \bscode{atomic}. Line \ref{line:ab_keyword} parses a \bscode{atomic} keyword returning a token representing the keyword. Line \ref{line:ab_block} parses the block of statements representing the transaction body. Lines \ref{line:ab_orelse_start} to line \ref{line:ab_orelse_end} parses any \bscode{orelse} blocks associated with the \bscode{atomic} statement, if any are present. Line \ref{line:ab_allocate} allocates a \bscode{SyntaxListBuilder}. The \bscode{Allocate} method reuses existing space if possible, in order to limit the overhead of allocation. Line \ref{line:ab_parse_orelse} delegates the parsing of the actual \bscode{orelse} block to its corresponding method. Line \ref{line:ab_free} frees the space allocated by the call on on line \ref{line:ab_allocate}. The \bscode{try finally} construct ensures that the space is freed in case of an exception. Finally on line \ref{line:ab_return} the syntax factory is used to create the \bscode{AtomicStatementSyntax} that is returned.

\begin{lstlisting}[label=lst:parse_atomic_block,
  caption={Method for parsing \bscode{atomic} block},
  language=Java,  
  showspaces=false,
  showtabs=false,
  breaklines=true,
  showstringspaces=false,
  breakatwhitespace=true,
  commentstyle=\color{greencomments},
  keywordstyle=\color{bluekeywords},
  stringstyle=\color{redstrings},
  escapechar=~,
  morekeywords={atomic, retry, orElse, var, get, set}]  % Start your code-block

  private StatementSyntax ParseAtomicBlock()
  { 
    var atomicKeyword = this.EatToken(SyntaxKind.AtomicKeyword);~\label{line:ab_keyword}~
    var block = this.ParseEmbeddedStatement(false);~\label{line:ab_block}~

    var orelses = SyntaxFactory.List<OrelseSyntax>();~\label{line:ab_orelse_start}~
    var orelseBuilder = _pool.Allocate<OrelseSyntax>();
    ~\label{line:ab_allocate}~
    try
    {
      while (this.CurrentToken.Kind == SyntaxKind.OrelseKeyword)
      {
        var clause = ParseOrelse();~\label{line:ab_parse_orelse}~
        orelseBuilder.Add(clause);
      }

      orelses = orelseBuilder.ToList();~\label{line:ab_tolist}~
    }
    finally
    {
      _pool.Free(orelseBuilder);~\label{line:ab_free}~
    }~\label{line:ab_orelse_end}~

    return _syntaxFactory.AtomicStatement(atomicKeyword, block, orelses);~\label{line:ab_return}~
  }
\end{lstlisting}
%error codes, const atomic, readonly atomic


\section{Syntax Tree Transformations}
\label{sec:syntax_tree_transformations}
%HUSK
\toby[i]{Evt. til valg af implementerings strategi: refer til at syntax træer kan blive modificeret hurtigt og med et lille memory overhead (den tredje key attribut omkring syntax træer)}
\kasper[inline]{Implementerings beskrivelse: error codes, lexer, parser, tvars, atomic block, replacement}

\subsection{Atomic Block}
Atomic and orElse block replacement

\subsection{Field Types}
\subsection{Properties}
\subsection{Local variables}
With or without type inference

\subsection{Member Accesses}
Accessing the .Value instead of the object directly

\subsection{Parameters}
Could also contain method and constructor argument replacement.
{'fraction_non_alphanumeric': 0.06243381933697157, 'fraction_numerical': 0.002525046835546143, 'mean_word_length': 5.046540261019453, 'pattern_counts': {'":': 0, '<': 65, '<?xml version=': 0, '>': 65, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 4}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '412800', 'n_tokens_mistral': 6348, 'n_tokens_neox': 6097, 'n_words': 2966}