Kaleidoscope Abstract Syntax Tree
As with many language parsing systems Kaleidoscope leverages an Abstract Syntax Tree (AST) to simplify generating code from the parsed language. Each type of node in the tree implements the IAstNode interface
This interface provides the basic properties of any node in the tree for common uses. The Kaleidoscope language is a simple one and, therefore, has only a few kinds of nodes. The AST consist of the following basic categories of nodes:
Root Node
The AstNode class forms the common base for all AST nodes, it provides the common location support for all nodes.
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using System.Collections.Generic;
using System.Collections.Immutable;
using Ubiquity.NET.Runtime.Utils;
using Ubiquity.NET.TextUX;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>Root node for the Kaleidoscope AST</summary>
public sealed class RootNode
: AstNode
, IAstNode
{
/// <summary>Initializes a new instance of the <see cref="RootNode"/> class.</summary>
/// <param name="location">Location of the node in the source input</param>
/// <param name="child">Child node</param>
public RootNode( SourceRange location, IAstNode child )
: this( location, [ child ] )
{
}
/// <summary>Initializes a new instance of the <see cref="RootNode"/> class.</summary>
/// <param name="location">Location of the node in the source input</param>
/// <param name="children">Child nodes of the root</param>
public RootNode( SourceRange location, IEnumerable<IAstNode> children )
: base( location )
{
ChildNodes = [ .. children ];
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult}(IAstVisitor{TResult})"/>
public override TResult? Accept<TResult>( IAstVisitor<TResult> visitor )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult> klsVisitor
? klsVisitor.Visit( this )
: visitor.Visit( this );
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult, TArg>( IAstVisitor<TResult, TArg> visitor, ref readonly TArg arg )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult, TArg> klsVisitor
? klsVisitor.Visit( this, in arg )
: visitor.Visit( this, in arg );
}
/// <inheritdoc/>
public override IEnumerable<IAstNode> Children => ChildNodes;
/// <inheritdoc/>
public override string ToString( )
{
return string.Join( ' ', Children );
}
private readonly ImmutableArray<IAstNode> ChildNodes;
}
}
Function Definition
FunctionDefinition, as the name implies, contains the definition of a function. This includes the signature and the full body of the function.
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using System.Collections.Generic;
using System.Collections.Immutable;
using Ubiquity.NET.Runtime.Utils;
using Ubiquity.NET.TextUX;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>AST type for a function definition</summary>
/// <remarks>
/// This supports construction of anonymous functions
/// that do not have an explicit prototype in the source language
/// </remarks>
public sealed class FunctionDefinition
: AstNode
, IAstNode
{
/// <summary>Initializes a new instance of the <see cref="FunctionDefinition"/> class.</summary>
/// <param name="location">Location of the node in the input source</param>
/// <param name="signature">Signature of the definition</param>
/// <param name="body">Expression for the body of the function</param>
/// <param name="isAnonymous">Flag to indicate whether this function is anonymous</param>
public FunctionDefinition( SourceRange location
, Prototype signature
, IExpression body
, bool isAnonymous = false
)
: this( location, signature, body, ImmutableArray.Create<LocalVariableDeclaration>(), isAnonymous )
{
}
/// <summary>Initializes a new instance of the <see cref="FunctionDefinition"/> class.</summary>
/// <param name="location">Location of the node in the input source</param>
/// <param name="signature">Signature of the definition</param>
/// <param name="body">Expression for the body of the function</param>
/// <param name="localVariables">Local variables for this function</param>
/// <param name="isAnonymous">Flag to indicate whether this function is anonymous</param>
public FunctionDefinition( SourceRange location
, Prototype signature
, IExpression body
, IImmutableList<LocalVariableDeclaration> localVariables
, bool isAnonymous = false
)
: base( location )
{
Signature = signature;
Body = body;
IsAnonymous = isAnonymous;
LocalVariables = localVariables;
}
/// <summary>Gets the prototype signature for the function</summary>
public Prototype Signature { get; }
/// <summary>Gets the body of the function as an expression tree</summary>
public IExpression Body { get; }
/// <summary>Gets a value indicating whether this function is an anonymous top level expression</summary>
/// <remarks>
/// This is useful during generation as anonymous expressions are discardable once they are generated and invoked
/// or inlined/merged in AOT scenarios.
/// </remarks>
public bool IsAnonymous { get; }
/// <summary>Gets the name of this function definition</summary>
public string Name => Signature.Name;
/// <summary>Gets the parameters for this function definition</summary>
public IReadOnlyList<ParameterDeclaration> Parameters => Signature.Parameters;
/// <summary>Gets the local variables for this function definition</summary>
public IReadOnlyList<LocalVariableDeclaration> LocalVariables { get; }
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult}(IAstVisitor{TResult})"/>
public override TResult? Accept<TResult>( IAstVisitor<TResult> visitor )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult> klsVisitor
? klsVisitor.Visit( this )
: visitor.Visit( this );
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult, TArg>( IAstVisitor<TResult, TArg> visitor, ref readonly TArg arg )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult, TArg> klsVisitor
? klsVisitor.Visit( this, in arg )
: visitor.Visit( this, in arg );
}
/// <inheritdoc/>
public override IEnumerable<IAstNode> Children
{
get
{
yield return Signature;
yield return Body;
}
}
/// <inheritdoc/>
public override string ToString( )
{
return $"{Signature}{{{Body}}}";
}
}
}
Function Declaration
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Ubiquity.NET.Runtime.Utils;
using Ubiquity.NET.TextUX;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>Encapsulates data describing a function signature</summary>
/// <remarks>
/// This is used to enable consistent representation when the prototype
/// is synthesized during code generation (i.e. Anonymous expressions)
/// </remarks>
public sealed class Prototype
: AstNode
, IAstNode
{
/// <summary>Initializes a new instance of the <see cref="Prototype"/> class.</summary>
/// <param name="location">Source location covering the complete signature</param>
/// <param name="name"><see cref="Name"/> containing the name of the function</param>
/// <param name="parameters">Collection of <see cref="Name"/>s for the names of each parameter</param>
public Prototype( SourceRange location, string name, params ParameterDeclaration[] parameters )
: this( location, name, false, false, parameters )
{
}
/// <summary>Initializes a new instance of the <see cref="Prototype"/> class.</summary>
/// <param name="location">Source location covering the complete signature</param>
/// <param name="name"><see cref="Name"/> containing the name of the function</param>
/// <param name="parameters">Collection of <see cref="Name"/>s for the names of each parameter</param>
public Prototype( SourceRange location, string name, IEnumerable<ParameterDeclaration> parameters )
: this( location, name, false, false, parameters )
{
}
/// <summary>Initializes a new instance of the <see cref="Prototype"/> class.</summary>
/// <param name="name">Name of the function</param>
/// <param name="parameters">Names of each parameter</param>
/// <remarks>
/// This version of the constructor is used to create synthetic prototypes that don't
/// exist within the original source.
/// </remarks>
public Prototype( string name, params string[] parameters )
: this( default, name, false, false, parameters.Select( ( n, i ) => new ParameterDeclaration( default, name, i ) ) )
{
}
/// <summary>Initializes a new instance of the <see cref="Prototype"/> class.</summary>
/// <param name="location">Source location covering the complete signature</param>
/// <param name="name">name of the function</param>
/// <param name="isCompilerGenerated">Indicates if this is a compiler generated prototype</param>
public Prototype( SourceRange location, string name, bool isCompilerGenerated )
: this( location, name, isCompilerGenerated, false, [] )
{
}
/// <summary>Initializes a new instance of the <see cref="Prototype"/> class.</summary>
/// <param name="location">Source location covering the complete signature</param>
/// <param name="name">name of the function</param>
/// <param name="isCompilerGenerated">Indicates if this is a compiler generated prototype</param>
/// <param name="isExtern">Indicates if this is an external prototype</param>
/// <param name="parameters">names of each parameter</param>
public Prototype(
SourceRange location,
string name,
bool isCompilerGenerated,
bool isExtern,
IEnumerable<ParameterDeclaration> parameters
)
: base( location )
{
Name = name;
Parameters = [ .. parameters ];
IsCompilerGenerated = isCompilerGenerated;
IsExtern = isExtern;
}
/// <summary>Gets the name of the function</summary>
public string Name { get; }
/// <summary>Gets a value indicating whether the function prototype is an extern declaration</summary>
public bool IsExtern { get; }
/// <summary>Gets a value indicating whether the function prototype is generated internally by compiler</summary>
public bool IsCompilerGenerated { get; }
/// <summary>Gets the parameters for the function</summary>
public IReadOnlyList<ParameterDeclaration> Parameters { get; }
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult}(IAstVisitor{TResult})"/>
public override TResult? Accept<TResult>( IAstVisitor<TResult> visitor )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult> klsVisitor
? klsVisitor.Visit( this )
: visitor.Visit( this );
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult, TArg>( IAstVisitor<TResult, TArg> visitor, ref readonly TArg arg )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult, TArg> klsVisitor
? klsVisitor.Visit( this, in arg )
: visitor.Visit( this, in arg );
}
/// <inheritdoc/>
public override IEnumerable<IAstNode> Children => Parameters;
/// <inheritdoc/>
public override string ToString( )
{
var bldr = new StringBuilder( );
if(IsExtern)
{
bldr.Append( "[extern]" );
}
if(IsCompilerGenerated)
{
bldr.Append( "[CompilerGenerated]" );
}
bldr.Append( Name );
bldr.Append( '(' );
if(Parameters.Count > 0)
{
bldr.Append( string.Join( ", ", Parameters.Select( p => p.ToString() ) ) );
}
bldr.Append( ')' );
return bldr.ToString();
}
}
}
Variable Declaration
IVariableDeclaration is implemented by local variable declarations and parameter declarations. The interface abstracts the differences between the two types of variable declarations for most common cases. Most code generation or AST consumers don't care about the differences (i.e. Parameters have an index but locals don't)
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using Ubiquity.NET.Runtime.Utils;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>Interface for a variable declaration</summary>
/// <remarks>
/// There are multiple forms of variable declarations (local, parameter, etc...).
/// This interface provides the common implementation for any such variables.
/// </remarks>
public interface IVariableDeclaration
: IAstNode
{
/// <summary>Gets the name of the variable</summary>
string Name { get; }
/// <summary>Gets a value indicating whether this variable is generated by the compiler/language</summary>
bool CompilerGenerated { get; }
}
}
Local Variable
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using System;
using System.Collections.Generic;
using System.Text;
using Ubiquity.NET.Runtime.Utils;
using Ubiquity.NET.TextUX;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>Local variable declaration AST node</summary>
public sealed class LocalVariableDeclaration
: AstNode
, IVariableDeclaration
{
/// <summary>Initializes a new instance of the <see cref="LocalVariableDeclaration"/> class.</summary>
/// <param name="location">Location of the node in the input source</param>
/// <param name="name">Name of the variable</param>
/// <param name="initializer">initializer for the expression</param>
/// <param name="compilerGenerated">flag to indicate if this variable is generated by the parsing of the language</param>
public LocalVariableDeclaration( SourceRange location, string name, IExpression? initializer, bool compilerGenerated = false )
: base( location )
{
ArgumentException.ThrowIfNullOrWhiteSpace(name);
Name = name;
Initializer = initializer;
CompilerGenerated = compilerGenerated;
}
/// <inheritdoc/>
public string Name { get; }
/// <summary>Gets the initializer for this declaration (if any)</summary>
public IExpression? Initializer { get; }
/// <inheritdoc/>
public bool CompilerGenerated { get; }
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult>( IAstVisitor<TResult> visitor )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult> klsVisitor
? klsVisitor.Visit( this )
: visitor.Visit( this );
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult, TArg>( IAstVisitor<TResult, TArg> visitor, ref readonly TArg arg )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult, TArg> klsVisitor
? klsVisitor.Visit( this, in arg )
: visitor.Visit( this, in arg );
}
/// <inheritdoc/>
public override IEnumerable<IAstNode> Children
{
get
{
if(Initializer != null)
{
yield return Initializer;
}
}
}
/// <inheritdoc/>
public override string ToString( )
{
var bldr = new StringBuilder();
if(CompilerGenerated)
{
bldr.Append( "[CompilerGenerated]" );
}
bldr.Append( "Declare(" );
bldr.Append( Name );
if(Initializer != null)
{
bldr.Append( ", " );
bldr.Append( Initializer );
}
bldr.Append( ')' );
return bldr.ToString();
}
}
}
Function Parameter
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using System.Collections.Generic;
using Ubiquity.NET.Runtime.Utils;
using Ubiquity.NET.TextUX;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>AST Node for a parameter declaration</summary>
public sealed class ParameterDeclaration
: AstNode
, IVariableDeclaration
{
/// <summary>Initializes a new instance of the <see cref="ParameterDeclaration"/> class.</summary>
/// <param name="location">Location of the source of the node in the input</param>
/// <param name="name">Name of the parameter</param>
/// <param name="index">Index of the parameter in the function signature</param>
public ParameterDeclaration( SourceRange location, string name, int index )
: base( location )
{
Name = name;
Index = index;
}
/// <inheritdoc/>
public string Name { get; }
/// <summary>Gets the index of the parameter in the parameter list it belongs too.</summary>
public int Index { get; }
/// <inheritdoc/>
public bool CompilerGenerated => false;
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult}(IAstVisitor{TResult})"/>
public override TResult? Accept<TResult>( IAstVisitor<TResult> visitor )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult> klsVisitor
? klsVisitor.Visit( this )
: visitor.Visit( this );
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult, TArg>( IAstVisitor<TResult, TArg> visitor, ref readonly TArg arg )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult, TArg> klsVisitor
? klsVisitor.Visit( this, in arg )
: visitor.Visit( this, in arg );
}
/// <inheritdoc/>
public override IEnumerable<IAstNode> Children => [];
/// <inheritdoc/>
public override string ToString( )
{
return Name;
}
}
}
Expression
Kaleidoscope is a functional language, all expressions produce a value, even if it is always zero. There are no statements in the language. Expressions form the core of the language and the bulk of the AST.
The IExpression interface forms the common interface for all AST expression nodes
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using Ubiquity.NET.Runtime.Utils;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>This is a grouping interface for all AST nodes that are valid expressions</summary>
/// <remarks>
/// This is a grouping interface to allow other parts of the system to distinguish between
/// an arbitrary node and one that is ultimately an expression. This helps to ensure correctness
/// (e.g. a function declaration is not valid as an argument to an operator, only an expression is.
/// </remarks>
public interface IExpression
: IAstNode
{
}
}
While this is an empty interface, it serves to distinguish between AST nodes that are not expressions. Thus providing some type safety for consumers. (i.e. it makes no sense to have a prototype as the operand for a binary operator so only nodes that implement the IExpression tag interface are allowed) This isn't a common or generally recommended pattern for interfaces but makes sense here since some form of differentiation is needed.
Unary Operator
Unary operators are all user defined, so the AST simply represents them as a Function Definition. No additional node types are needed for unary operators in the AST.
Binary Operator
BinaryOperatorExpression covers the built-in operators, any user defined binary operators are transformed to a function declaration/definition
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using System.Collections.Generic;
using Ubiquity.NET.Runtime.Utils;
using Ubiquity.NET.TextUX;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>Identifier for the kinds of built-in operators</summary>
public enum BuiltInOperatorKind
{
/// <summary>Default value (Invalid)</summary>
Invalid,
/// <summary>Assignment operator</summary>
Assign,
/// <summary>Addition operator</summary>
Add,
/// <summary>Subtraction operator</summary>
Subtract,
/// <summary>Multiplication operator</summary>
Multiply,
/// <summary>Division operator</summary>
Divide,
/// <summary>Comparison operator (less)</summary>
Less,
/// <summary>Exponentiation operator</summary>
Pow
}
/// <summary>AST Expression node for a binary operator</summary>
public sealed class BinaryOperatorExpression
: AstNode
, IExpression
{
/// <summary>Initializes a new instance of the <see cref="BinaryOperatorExpression"/> class.</summary>
/// <param name="location">Source location of the operator expression</param>
/// <param name="lhs">Left hand side expression for the operator</param>
/// <param name="op">Operator type</param>
/// <param name="rhs">Right hand side expression for the operator</param>
public BinaryOperatorExpression( SourceRange location, IExpression lhs, BuiltInOperatorKind op, IExpression rhs )
: base( location )
{
Left = lhs;
Op = op;
Right = rhs;
}
/// <summary>Gets the left hand side expression</summary>
public IExpression Left { get; }
/// <summary>Gets the operator kind for this operator</summary>
public BuiltInOperatorKind Op { get; }
/// <summary>Gets the Operator name for this expression</summary>
public string Name => Op.ToString();
/// <summary>Gets the Right hand side expression</summary>
public IExpression Right { get; }
/// <inheritdoc/>
public sealed override IEnumerable<IAstNode> Children
{
get
{
yield return Left;
yield return Right;
}
}
/// <summary>Visitor pattern 'Accept' of a visitors that don't need a parameter</summary>
/// <typeparam name="TResult">Type of the result from the visitor</typeparam>
/// <param name="visitor">Visitor to apply for each node in this expression</param>
/// <returns>Result of visiting this expression</returns>
public override TResult? Accept<TResult>( IAstVisitor<TResult> visitor )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult> klsVisitor
? klsVisitor.Visit( this )
: visitor.Visit( this );
}
/// <summary>Visitor pattern 'Accept' of a visitors that need a parameter</summary>
/// <typeparam name="TResult">Type of the result from the visitor</typeparam>
/// <typeparam name="TArg">Type of the argument for the visit</typeparam>
/// <param name="visitor">Visitor to apply for each node in this expression</param>
/// <param name="arg">Argument to pass to each method of the visit</param>
/// <returns>Result of visiting this expression</returns>
public override TResult? Accept<TResult, TArg>( IAstVisitor<TResult, TArg> visitor, ref readonly TArg arg )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult, TArg> klsVisitor
? klsVisitor.Visit( this, in arg )
: visitor.Visit( this, in arg );
}
/// <inheritdoc/>
public override string ToString( )
{
return $"{Name}({Left},{Right})";
}
}
}
The properties are fairly self explanatory, including the kind of operator and the left and right sides of the operator. The normal code generator pattern for the binary operators is:
- Generate code for the left side expression to a new value
- Generate code for the right side expression to a new value
- Apply the operator to the generated left and right values
- Return the result
Assignment
Assignment is a special kind of binary operator to represent "store" semantics for a variable. (e.g. mutable variables). Code generation for the assignment must handle the left side operand with a slightly different pattern. In particular, the left hand side is not an evaluated expression. Instead, it is the variable to assign the right hand value to. Thus, there isn't anything to evaluate for the left hand side as it is always a Variable Reference for the variable to assign the value to.
Function Call
Calls to functions (extern, user defined operators, or user defined functions) are represented in the AST as a FunctionCallExpression. The FunctionCallExpression contains the declaration of the function to call along with expressions for all of the arguments to the function.
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using System.Collections.Generic;
using System.Linq;
using Ubiquity.NET.Runtime.Utils;
using Ubiquity.NET.TextUX;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>Kaleidoscope AST Node for a function call expression</summary>
public sealed class FunctionCallExpression
: AstNode
, IExpression
{
/// <summary>Initializes a new instance of the <see cref="FunctionCallExpression"/> class.</summary>
/// <param name="location">Location of the node in the source input</param>
/// <param name="functionPrototype">Prototype of the function to call</param>
/// <param name="args">Arguments to provide to the function</param>
public FunctionCallExpression( SourceRange location, Prototype functionPrototype, params IEnumerable<IExpression> args )
: base( location )
{
FunctionPrototype = functionPrototype;
Arguments = [ .. args ];
}
/// <summary>Gets the prototype of the function to call</summary>
public Prototype FunctionPrototype { get; }
/// <summary>Gets the arguments to provide to the function</summary>
public IReadOnlyList<IExpression> Arguments { get; }
/// <inheritdoc/>
public override IEnumerable<IAstNode> Children
{
get
{
yield return FunctionPrototype;
}
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult}(IAstVisitor{TResult})"/>
public override TResult? Accept<TResult>( IAstVisitor<TResult> visitor )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult> klsVisitor
? klsVisitor.Visit( this )
: visitor.Visit( this );
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult, TArg>( IAstVisitor<TResult, TArg> visitor, ref readonly TArg arg )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult, TArg> klsVisitor
? klsVisitor.Visit( this, in arg )
: visitor.Visit( this, in arg );
}
/// <inheritdoc/>
public override string ToString( )
{
return Arguments.Count == 0
? $"Call({FunctionPrototype})"
: $"Call({FunctionPrototype}, {string.Join( ",", Arguments.Select( a => a.ToString() ) )})";
}
}
}
Variable Reference
A variable reference is used to refer to a variable. In most cases this represents implicit "load" semantics for a variable. However, when used as the left hand side of an assignment operator, it has "store" semantics.
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using System.Collections.Generic;
using Ubiquity.NET.Runtime.Utils;
using Ubiquity.NET.TextUX;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>Kaleidoscope AST node for a reference to a variable</summary>
public sealed class VariableReferenceExpression
: AstNode
, IExpression
{
/// <summary>Initializes a new instance of the <see cref="VariableReferenceExpression"/> class.</summary>
/// <param name="location">Location of the node in the input source</param>
/// <param name="declaration">Declaration of the variable referenced</param>
public VariableReferenceExpression( SourceRange location, IVariableDeclaration declaration )
: base( location )
{
Declaration = declaration;
}
/// <summary>Gets the declaration this reference refers to</summary>
public IVariableDeclaration Declaration { get; }
/// <summary>Gets the name of the variable referenced</summary>
public string Name => Declaration.Name;
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult>( IAstVisitor<TResult> visitor )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult> klsVisitor
? klsVisitor.Visit( this )
: visitor.Visit( this );
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult, TArg>( IAstVisitor<TResult, TArg> visitor, ref readonly TArg arg )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult, TArg> klsVisitor
? klsVisitor.Visit( this, in arg )
: visitor.Visit( this, in arg );
}
/// <inheritdoc/>
public override IEnumerable<IAstNode> Children
{
get
{
yield return Declaration;
}
}
/// <inheritdoc/>
public override string ToString( )
{
return $"Load({Name})";
}
}
}
Conditional
In Kaleidoscope conditional expressions follow the familiar if/then/else form, even though they are really more
like the ternary operator expression ( x ? y : z ) in C and related languages.
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using System.Collections.Generic;
using Ubiquity.NET.Runtime.Utils;
using Ubiquity.NET.TextUX;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>AST node for a conditional expression</summary>
/// <remarks>
/// A conditional expression is the language equivalent of a conditional operator in most "C" like languages (ternary operator).
/// </remarks>
public sealed class ConditionalExpression
: AstNode
, IExpression
{
/// <summary>Initializes a new instance of the <see cref="ConditionalExpression"/> class.</summary>
/// <param name="location">Location of the expression in the source input</param>
/// <param name="condition">Expression for the condition</param>
/// <param name="thenExpression">Expression for the `then` clause of the conditional expression</param>
/// <param name="elseExpression">Expression for the `else` clause of the conditional expression</param>
/// <param name="resultVar"><see cref="LocalVariableDeclaration"/> to represent the results of the expression</param>
public ConditionalExpression( SourceRange location
, IExpression condition
, IExpression thenExpression
, IExpression elseExpression
, LocalVariableDeclaration resultVar
)
: base( location )
{
Condition = condition;
ThenExpression = thenExpression;
ElseExpression = elseExpression;
ResultVariable = resultVar;
}
/// <summary>Gets the expression for the condition</summary>
public IExpression Condition { get; }
/// <summary>Gets the expression for the `then` clause</summary>
public IExpression ThenExpression { get; }
/// <summary>Gets the expression for the `else` clause</summary>
public IExpression ElseExpression { get; }
/// <summary>Gets the result of the expression as a <see cref="LocalVariableDeclaration"/></summary>
/// <remarks>
/// Compiler generated result variable supports building conditional
/// expressions without the need for SSA form in the AST/Code generation
/// by using mutable variables. The result is assigned a value from both
/// sides of the branch. In pure SSA form this isn't needed as a PHI node
/// would be used instead.
/// </remarks>
public LocalVariableDeclaration ResultVariable { get; }
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult}(IAstVisitor{TResult})"/>
public override TResult? Accept<TResult>( IAstVisitor<TResult> visitor )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult> klsVisitor
? klsVisitor.Visit( this )
: visitor.Visit( this );
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult, TArg>( IAstVisitor<TResult, TArg> visitor, ref readonly TArg arg )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult, TArg> klsVisitor
? klsVisitor.Visit( this, in arg )
: visitor.Visit( this, in arg );
}
/// <inheritdoc/>
public override IEnumerable<IAstNode> Children
{
get
{
yield return Condition;
yield return ThenExpression;
yield return ElseExpression;
}
}
/// <inheritdoc/>
public override string ToString( )
{
return $"Conditional({Condition}, {ThenExpression}, {ElseExpression})";
}
}
}
For-In
The for in expression is used to implement loops in Kaleidoscope.
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using System.Collections.Generic;
using Ubiquity.NET.Runtime.Utils;
using Ubiquity.NET.TextUX;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>Kaleidoscope AST node for a <c>ForIn</c> expression</summary>
public sealed class ForInExpression
: AstNode
, IExpression
{
/// <summary>Initializes a new instance of the <see cref="ForInExpression"/> class.</summary>
/// <param name="location">Location of the expression in the source input</param>
/// <param name="loopVariable">Declaration of the variable to use for the loop</param>
/// <param name="condition">Exit Condition for the loop</param>
/// <param name="step">Step value to increment <paramref name="loopVariable"/> by with each iteration of the loop</param>
/// <param name="body">The body of the loop to invoke on each iteration</param>
public ForInExpression( SourceRange location
, LocalVariableDeclaration loopVariable
, IExpression condition
, IExpression step
, IExpression body
)
: base( location )
{
LoopVariable = loopVariable;
Condition = condition;
Step = step;
Body = body;
}
/// <summary>Gets the declaration of the variable to use for the loop</summary>
public LocalVariableDeclaration LoopVariable { get; }
/// <summary>Gets the exit Condition for the loop</summary>
public IExpression Condition { get; }
/// <summary>Gets the step value to increment <see cref="LoopVariable"/> by with each iteration of the loop</summary>
public IExpression Step { get; }
/// <summary>Gets the body of the loop to invoke on each iteration</summary>
public IExpression Body { get; }
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult}(IAstVisitor{TResult})"/>
public override TResult? Accept<TResult>( IAstVisitor<TResult> visitor )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult> klsVisitor
? klsVisitor.Visit( this )
: visitor.Visit( this );
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult, TArg>( IAstVisitor<TResult, TArg> visitor, ref readonly TArg arg )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult, TArg> klsVisitor
? klsVisitor.Visit( this, in arg )
: visitor.Visit( this, in arg );
}
/// <inheritdoc/>
public override IEnumerable<IAstNode> Children
{
get
{
yield return LoopVariable;
yield return Condition;
yield return Step;
yield return Body;
}
}
/// <inheritdoc/>
public override string ToString( )
{
return $"for({LoopVariable}, {Condition}, {Step}, {Body})";
}
}
}
Var-In
Var-In Expression is used to provide, potentially nested, local scopes for variables
// Copyright (c) Ubiquity.NET Contributors. All rights reserved.
// Licensed under the Apache-2.0 WITH LLVM-exception license. See the LICENSE.md file in the project root for full license information.
using System.Collections.Generic;
using System.Text;
using Ubiquity.NET.Runtime.Utils;
using Ubiquity.NET.TextUX;
namespace Kaleidoscope.Grammar.AST
{
/// <summary>Kaleidoscope AST node for a <c>Var-In</c> expression</summary>
public sealed class VarInExpression
: AstNode
, IExpression
{
/// <summary>Initializes a new instance of the <see cref="VarInExpression"/> class.</summary>
/// <param name="location">Location of the node in the input source</param>
/// <param name="localVariables">Local variables for the expression</param>
/// <param name="body">Body of the expression</param>
public VarInExpression( SourceRange location, IEnumerable<LocalVariableDeclaration> localVariables, IExpression body )
: base( location )
{
LocalVariables = localVariables;
Body = body;
}
/// <summary>Gets the local variables for the expression</summary>
public IEnumerable<LocalVariableDeclaration> LocalVariables { get; }
/// <summary>Gets the body for the expression</summary>
public IExpression Body { get; }
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult>( IAstVisitor<TResult> visitor )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult> klsVisitor
? klsVisitor.Visit( this )
: visitor.Visit( this );
}
/// <inheritdoc cref="BinaryOperatorExpression.Accept{TResult, TArg}(IAstVisitor{TResult, TArg}, ref readonly TArg)"/>
public override TResult? Accept<TResult, TArg>( IAstVisitor<TResult, TArg> visitor, ref readonly TArg arg )
where TResult : default
{
return visitor is IKaleidoscopeAstVisitor<TResult, TArg> klsVisitor
? klsVisitor.Visit( this, in arg )
: visitor.Visit( this, in arg );
}
/// <inheritdoc/>
public override IEnumerable<IAstNode> Children
{
get
{
foreach(var local in LocalVariables)
{
yield return local;
}
yield return Body;
}
}
/// <inheritdoc/>
public override string ToString( )
{
var bldr = new StringBuilder( "VarIn{" );
bldr.AppendJoin( ',', LocalVariables )
.Append( "}(" )
.Append( Body )
.Append( ')' );
return bldr.ToString();
}
}
}