bookmark_borderImplementing a class at runtime with Reflection.Emit

This is a simple example of how an interface can by dynamically implemented at runtime using the System.Reflection.Emit namespace. We’ll start by defining a dynamic assembly, then defining a class which implements our test interface. This is how frameworks, like Moq, can create interface implementations for you, which is especially powerful for unit testing.

Here is the interface we will be working with.

/// <summary>
/// The test interface to implement.
/// </summary>
/// <remarks>
/// Make this public so that the new assembly can see it.
/// Or set the "InternalsVisibleTo" attribute on this assembly with the name of the new dynamic assembly.
/// </remarks>
public interface ITestInterface
{
    /// <summary>
    /// This method will be implemented as a no-op.
    /// </summary>
    void ImplementMeToDoNothing();

    /// <summary>
    /// This method will return a default integer.
    /// </summary>
    /// <returns>Zero.</returns>
    int ImplementMeToReturnDefaultInt();

    /// <summary>
    /// This method will throw a NotImplementedException.
    /// </summary>
    void ImplementMeToThrowAnException();

    /// <summary>
    /// This method will return the value argument.
    /// </summary>
    /// <param name="argument">The return value.</param>
    /// <returns>The argument.</returns>
    int ImplementMeToReturnMyArgument(int argument);
}

Here are some test method to better explain our goals.

[TestMethod]
public void EnsureDoNothingSucceeds()
{
    ITestInterface instance = CreateMock();
    instance.ImplementMeToDoNothing();
}

[TestMethod]
public void EnsureDefaultReturnsZero()
{
    ITestInterface instance = CreateMock();
    Assert.AreEqual(0, instance.ImplementMeToReturnDefaultInt());
}

[TestMethod]
public void EnsureThrowsNotImplementedException()
{
    ITestInterface instance = CreateMock();
    Assert.ThrowsException<NotImplementedException>(() => instance.ImplementMeToThrowAnException());
}

[TestMethod]
public void EnsureReturnsArgument()
{
    ITestInterface instance = CreateMock();
    Assert.AreEqual(12345, instance.ImplementMeToReturnMyArgument(12345));
}

So lets define the function which will create our mock. This will build a new assembly, and create a class which implements ITestInterface.

private static ITestInterface CreateMock()
{
    // Create a dynamic assembly and module.
    var assemblyName = new AssemblyName("TestAssembly");
    var assemblyBuilder = AssemblyBuilder.DefineDynamicAssembly(name: assemblyName, access: AssemblyBuilderAccess.RunAndCollect);
    var moduleBuilder = assemblyBuilder.DefineDynamicModule(name: assemblyName.Name);

    // Define the class builder for the new type to implement the interface "ITestInterface"
    var classBuilder = moduleBuilder.DefineType(
        name: nameof(ITestInterface) + "_Implementation",
        attr: TypeAttributes.Class | TypeAttributes.Public,
        parent: typeof(object),
        interfaces: new[] { typeof(ITestInterface) });

    // We don't have anything special to do in the constructor, so define a default one.
    classBuilder.DefineDefaultConstructor(MethodAttributes.Public);

    {
        // Lets start with a method which doesn't do anything.
        var parentImplementMeToDoNothing = typeof(ITestInterface).GetMethod(nameof(ITestInterface.ImplementMeToDoNothing));

        // Define the method to implement 'ImplementMeToDoNothing'. It doesn't need to have 
        // the same name, but for simplicity sake, it does.
        var doNothingMethodBuilder = classBuilder.DefineMethod(
            name: nameof(ITestInterface.ImplementMeToDoNothing),
            attributes: MethodAttributes.Public | MethodAttributes.Virtual,
            returnType: typeof(void),
            parameterTypes: Type.EmptyTypes);

        // Get an IL generator and just return.
        var ilGenerator = doNothingMethodBuilder.GetILGenerator();
        ilGenerator.Emit(OpCodes.Ret);

        // Make the method as implementing the definition on the interface.
        classBuilder.DefineMethodOverride(doNothingMethodBuilder, parentImplementMeToDoNothing);
    }

    {
        // Now lets do the method which returns the default int.
        var parentImplementMeToReturnDefaultInt = typeof(ITestInterface).GetMethod(nameof(ITestInterface.ImplementMeToReturnDefaultInt));
        var defaultIntMethodBuilder = classBuilder.DefineMethod(
            name: nameof(ITestInterface.ImplementMeToReturnDefaultInt), 
            attributes: MethodAttributes.Public | MethodAttributes.Virtual, 
            returnType: typeof(int), 
            parameterTypes: Type.EmptyTypes);

        var ilGenerator = defaultIntMethodBuilder.GetILGenerator();
        ilGenerator.Emit(OpCodes.Ldc_I4_0);
        ilGenerator.Emit(OpCodes.Ret);

        classBuilder.DefineMethodOverride(defaultIntMethodBuilder, parentImplementMeToReturnDefaultInt);
    }

    {
        // Implement a method which throws a "NotImplementedException".
        var parentImplementMeToThrowAnException = typeof(ITestInterface).GetMethod(nameof(ITestInterface.ImplementMeToThrowAnException));
        var throwExceptionBuilder = classBuilder.DefineMethod(nameof(ITestInterface.ImplementMeToThrowAnException), MethodAttributes.Public | MethodAttributes.Virtual, typeof(void), Type.EmptyTypes);
        var ilGenerator = throwExceptionBuilder.GetILGenerator();

        // Load the string we are going to pass into the constructor of "NotImplementedException" onto the execution stack.
        ilGenerator.Emit(OpCodes.Ldstr, $"The method ImplementMeToThrowAnException is not implemented.");

        // Create a new NotImplementedException(string)
        ilGenerator.Emit(OpCodes.Newobj, typeof(NotImplementedException).GetConstructor(new[] { typeof(string) }));

        // Throw the exception
        ilGenerator.Emit(OpCodes.Throw);
        ilGenerator.Emit(OpCodes.Ret);

        classBuilder.DefineMethodOverride(throwExceptionBuilder, parentImplementMeToThrowAnException);
    }

    {
        // Implement a method which returns the argument.
        var parentImplementMeToReturnMyArgument = typeof(ITestInterface).GetMethod(nameof(ITestInterface.ImplementMeToReturnMyArgument));
        var implementReturnArgument = classBuilder.DefineMethod(nameof(ITestInterface.ImplementMeToReturnMyArgument), MethodAttributes.Public | MethodAttributes.Virtual, typeof(int), new[] { typeof(int) });
        var ilGenerator = implementReturnArgument.GetILGenerator();

        // Since this is a class method, arg0 is always "this". So arg1 is the first argument.
        ilGenerator.Emit(OpCodes.Ldarg_1);
        ilGenerator.Emit(OpCodes.Ret);

        classBuilder.DefineMethodOverride(implementReturnArgument, parentImplementMeToReturnMyArgument);
    }

    // Finish the type.
    var createdType = classBuilder.CreateType();

    // Create a new instance of the type we just created.
    return (ITestInterface)Activator.CreateInstance(createdType);
}

There it is, the implementation provides four different examples. Another implementation strategy is to create the implementations to execute a delegate, so that you can execute whatever you like.

bookmark_borderReflection.Emit Hello World for Beginners

Lets start by saying the Reflection.Emit is inherently one of the most complex portions of the C# language. You’ll be able to undermine everything that the .Net designers intended and create complex difficult to debug code which your coworkers will hate. This article demonstrates a simple “Hello World” program.

Here is a little background before getting started.

  • Intermediate Language: In the java world, this is called “byte code”. It is a high level assembly language, which .Net code is translated into, before being compiled into machine code.
  • Execution Stack: This is where .Net does it’s work. Variables and references are pushed onto and popped off of the execution stack during execution. This is how arguments are passed to method calls. The method arguments are pushed onto the execution stack, and popped off by the method call.

Lets get started with a simple demonstration of a new Assembly, new Module, and a simple global method which prints out “Hello World Global Method!”

// Define a new assembly, named "TestAssembly".
var assemblyName = new AssemblyName("TestAssembly");
var assemblyBuilder = AssemblyBuilder.DefineDynamicAssembly(assemblyName, AssemblyBuilderAccess.RunAndCollect);
var moduleBuilder = assemblyBuilder.DefineDynamicModule(assemblyName.Name);

// Define a new global method named "HelloWorld".
var globalMethod = moduleBuilder.DefineGlobalMethod(
    name: "HelloWorld",
    attributes: MethodAttributes.Public | MethodAttributes.Static,
    returnType: typeof(void),
    parameterTypes: Type.EmptyTypes);

// Get the IL (intermediate language) generator for the method, so we can start working with intermediate language.
var ilGenerator = globalMethod.GetILGenerator();

// Get the method info for "Console.WriteLine(string)";
var writeLine = typeof(Console).GetMethod(
    name: nameof(Console.WriteLine),
    bindingAttr: BindingFlags.Static | BindingFlags.Public,
    binder: Type.DefaultBinder,
    types: new[] { typeof(string) },
    modifiers: null);

// Load the string "Hello World Global Method!" onto the execution stack.
ilGenerator.Emit(OpCodes.Ldstr, "Hello World Global Method!");

// Call Console.Writeline(string). This will pop off the string we just loaded onto the execution stack.
ilGenerator.Emit(OpCodes.Call, writeLine);

// Return.
ilGenerator.Emit(OpCodes.Ret);

// Global functions must be "done" before the module can be officially created.
// This call will create/compile them all.
moduleBuilder.CreateGlobalFunctions();

// Get the method we just created
var resultingMethod = moduleBuilder.GetMethod("HelloWorld");

// Create a delegate. This method takes no arguments and doesn't return a value, so its the same as an "Action".
var resultingDelegate = (Action)resultingMethod.CreateDelegate(typeof(Action));

// Call it.
resultingDelegate();

This was a very simple method and creating a dynamic assembly was too much work. So here is an example of the same thing, but using the “DynamicMethod” class. “DynamicMethod” is powerful in those sort of scenario, when creating simple static methods.

// Define a new assembly, named "TestAssembly".
var assemblyName = new AssemblyName("TestAssembly");
var assemblyBuilder = AssemblyBuilder.DefineDynamicAssembly(assemblyName, AssemblyBuilderAccess.RunAndCollect);
var moduleBuilder = assemblyBuilder.DefineDynamicModule(assemblyName.Name);

// Define a new global method named "HelloWorld".
var globalMethod = moduleBuilder.DefineGlobalMethod(
    name: "HelloWorld",
    attributes: MethodAttributes.Public | MethodAttributes.Static,
    returnType: typeof(void),
    parameterTypes: Type.EmptyTypes);

// Get the IL (intermediate language) generator for the method, so we can start working with intermediate language.
var ilGenerator = globalMethod.GetILGenerator();

// Get the method info for "Console.WriteLine(string)";
var writeLine = typeof(Console).GetMethod(
    name: nameof(Console.WriteLine),
    bindingAttr: BindingFlags.Static | BindingFlags.Public,
    binder: Type.DefaultBinder,
    types: new[] { typeof(string) },
    modifiers: null);

// Load the string "Hello World Global Method!" onto the execution stack.
ilGenerator.Emit(OpCodes.Ldstr, "Hello World Global Method!");

// Call Console.Writeline(string). This will pop off the string we just loaded onto the execution stack.
ilGenerator.Emit(OpCodes.Call, writeLine);

// Return.
ilGenerator.Emit(OpCodes.Ret);

// Global functions must be "done" before the module can be officially created.
// This call will create/compile them all.
moduleBuilder.CreateGlobalFunctions();

// Get the method we just created
var resultingMethod = moduleBuilder.GetMethod("HelloWorld");

// Create a delegate. This method takes no arguments and doesn't return a value, so its the same as an "Action".
var resultingDelegate = (Action)resultingMethod.CreateDelegate(typeof(Action));

// Call it.
resultingDelegate();

Another option to consider, if your use case is just simple static methods, is to use the System.Linq.Expressions namespace. This will create much more readable code, with much better supported debugging ability. An Expression tree will also show you the C# code which is generated behind the scenes, so you don’t need to work in IL.

// Get the method info for "Console.WriteLine(string)";
var writeLine = typeof(Console).GetMethod(
    name: nameof(Console.WriteLine),
    bindingAttr: BindingFlags.Static | BindingFlags.Public,
    binder: Type.DefaultBinder,
    types: new[] { typeof(string) },
    modifiers: null);

// Generate a lamba expression, which calls writeline, passing a single constant argument.
var lambdaExpression = Expression.Lambda(
    body: Expression.Call(
        method: writeLine, 
        arg0: Expression.Constant("Hello World Expression!")
    ));

var resultingMethod = (Action)lambdaExpression.Compile();
resultingMethod();

Take a look at “lambdaExpression.ToString()”. In the debugger, you will see that the underlying code generated is: “{() => WriteLine(“Hello World Expression!”)}”

Theres a quick tutorial on Reflection.Emit! In most code, using this functionality of .Net is overkill, and will cause maintainability nightmares. The best way to learn this stuff is to write some C# code, which looks like the code you’re trying to generate, and use a decompiler to look at the resulting IL.

bookmark_borderPowershell Variable Scoping

Confusion caused by variable scoping is a constant source of errors in Powershell. Most importantly, when is a variable visible, but any changes aren’t visible outside of the current scope. This is especially common with inner functions.

Here is an example, declaring a variable in an outer function makes it visible to the inner function. But it is passed by copy, so updating it in the inner function does not make changes visible to the outer function.

function Outer
{
    $var1 = 1;
    
    function Inner
    {
        Write-Output "Inner: $var1"

        # This change will not be visible in the outer function
        $var1++;
        Write-Output "Inner: $var1"
    }

    Write-Output "Outer: $var1"
    Inner
    Write-Output "Outer: $var1"
}
Outer

# Output: 
# Outer: 1
# Inner: 1
# Inner: 2
# Outer: 1

One way to fix that, is to declare the variable either “AllScope”, or in the global namespace. “AllScope” would be more advisable, since AllScope variables are available in all child scopes, as opposed to everywhere.

function Outer
{
    $var1 = 1
    Set-Variable -Name allscope -Value 1 -Option AllScope
    $global:var3 = 1
    
    function Inner
    {
        Write-Output "Inner: var1:$var1 allscope:$allscope var3:$global:var3"

        # This change will not be visible in the outer function
        $var1++;
        $allscope++;
        $global:var3++;
        Write-Output "Inner: var1:$var1 allscope:$allscope var3:$global:var3"
    }

    Write-Output "Outer: var1:$var1 allscope:$allscope var3:$global:var3"
    Inner
    Write-Output "Outer: var:$var1 allscope:$allscope var3:$global:var3"
}
Outer

# Outputs:
# Outer: var1:1 allscope:1 var3:1
# Inner: var1:1 allscope:1 var3:1
# Inner: var1:2 allscope:2 var3:2
# Outer: var:1 allscope:2 var3:2

Here is a program which executes to show a bunch of other behaviors when it commends to appending values to an array.

$Global:GlobalLevelArray = @("Script!");
$ScriptLevelArray = @("Script!");

function OuterFunc
{
    param
    (
        $OuterFuncArrayArg
    )

    process
    {
        # Changes to global variables will always be visible
        $Global:GlobalLevelArray = $Global:GlobalLevelArray + "OuterFunc";

        # Notice that this will update the array at this scope,
        # but not outside of this function.
        $ScriptLevelArray = $ScriptLevelArray + "OuterFunc";

        # This will update the array at this scope,
        # but changes will not be accessible to the caller.
        $OuterFuncArrayArg = $OuterFuncArrayArg + "OuterFunc";

        # This variable is visible at this level, and to child functions.
        $OuterFuncArray = @("OuterFunc");

        # A variable at the local scope is the current scope, but will not be available to the child scope.
        $local:OuterFuncLocalArray = @("OuterFunc");

        # This variable is available an modifieable to all child functions
        # Changes by the child will be reflected in here.
        Set-Variable -Name OuterFuncAllScopes -Value @("OuterFunc") -Option AllScope

        function NestedFunc
        {
            param
            (
            )
            process
            {
                $Global:GlobalLevelArray = $Global:GlobalLevelArray + "NestedFunc";
                $ScriptLevelArray = $ScriptLevelArray + "NestedFunc";
                $OuterFuncArrayArg = $OuterFuncArrayArg + "NestedFunc";
                $OuterFuncArray = $OuterFuncArray + "NestedFunc";
                $local:OuterFuncLocalArray = $local:OuterFuncLocalArray + "NestedFunc";
                $OuterFuncAllScopes = $OuterFuncAllScopes + "NestedFunc";

                # This, even though its declared all the way down in this nested func, will be available everywhere.
                $global:NestedFuncGlobalArray = @("NestedFunc")

                Write-Output "`t`tNestedFunc:GlobalLevelArray -> $($Global:GlobalLevelArray -join ',')"
                Write-Output "`t`tNestedFunc:ScriptLevelArray -> $($ScriptLevelArray -join ',')"
                Write-Output "`t`tNestedFunc:OuterFuncArrayArg -> $($OuterFuncArrayArg -join ',')"
                Write-Output "`t`tNestedFunc:OuterFuncArray -> $($OuterFuncArray -join ',')"
                Write-Output "`t`tNestedFunc:OuterFuncLocalArray -> $($local:OuterFuncLocalArray -join ',')"
                Write-Output "`t`tNestedFunc:OuterFuncAllScopes -> $($OuterFuncAllScopes -join ',')"
                Write-Output "`t`tNestedFunc:NestedFuncGlobalArray -> $($global:NestedFuncGlobalArray -join ',')"
            }
        }

        NestedFunc

        $global:NestedFuncGlobalArray = $global:NestedFuncGlobalArray + "OuterFunc";

        Write-Output "`tOuterFunc:ScriptLevelArray -> $($ScriptLevelArray -join ',')"
        Write-Output "`tOuterFunc:OuterFuncArrayArg -> $($OuterFuncArrayArg -join ',')"
        Write-Output "`tOuterFunc:GlobalLevelArray -> $($Global:GlobalLevelArray -join ',')"
        Write-Output "`tOuterFunc:OuterFuncArray -> $($OuterFuncArray -join ',')"
        Write-Output "`tOuterFunc:OuterFuncLocalArray -> $($local:OuterFuncArray -join ',')"
        Write-Output "`tOuterFunc:OuterFuncAllScopes -> $($OuterFuncAllScopes -join ',')"
        Write-Output "`tOuterFunc:NestedFuncGlobalArray -> $($global:NestedFuncGlobalArray -join ',')"
    }
}


OuterFunc -OuterFuncArray $ScriptLevelArray

$global:NestedFuncGlobalArray = $global:NestedFuncGlobalArray + "Script!";


Write-Output "Script:ScriptLevelArray -> $($ScriptLevelArray -join ',')"
Write-Output "Script:GlobalLevelArray -> $($GlobalLevelArray -join ',')"

Write-Output "Script:OuterFuncLocalArray -> $($local:OuterFuncArray -join ',')"

# An AllScopes variable in a child scope will not be visible in the parent scope
Write-Output "Script:OuterFuncAllScopes -> $($OuterFuncAllScopes -join ',')"
Write-Output "Script:NestedFuncGlobalArray -> $($global:NestedFuncGlobalArray -join ',')"

The output of this progrom:

		NestedFunc:GlobalLevelArray -> Script!,OuterFunc,NestedFunc
		NestedFunc:ScriptLevelArray -> Script!,OuterFunc,NestedFunc
		NestedFunc:OuterFuncArrayArg -> Script!,OuterFunc,NestedFunc
		NestedFunc:OuterFuncArray -> OuterFunc,NestedFunc
		NestedFunc:OuterFuncLocalArray -> NestedFunc
		NestedFunc:OuterFuncAllScopes -> OuterFunc,NestedFunc
		NestedFunc:NestedFuncGlobalArray -> NestedFunc
	OuterFunc:ScriptLevelArray -> Script!,OuterFunc
	OuterFunc:OuterFuncArrayArg -> Script!,OuterFunc
	OuterFunc:GlobalLevelArray -> Script!,OuterFunc,NestedFunc
	OuterFunc:OuterFuncArray -> OuterFunc
	OuterFunc:OuterFuncLocalArray -> OuterFunc
	OuterFunc:OuterFuncAllScopes -> OuterFunc,NestedFunc
	OuterFunc:NestedFuncGlobalArray -> NestedFunc,OuterFunc
Script:ScriptLevelArray -> Script!
Script:GlobalLevelArray -> Script!,OuterFunc,NestedFunc
Script:OuterFuncLocalArray -> 
Script:OuterFuncAllScopes -> 
Script:NestedFuncGlobalArray -> NestedFunc,OuterFunc,Script!

bookmark_borderPowershell Infix to Postfix Conversion

A common programming problem and interview question is to take an equation in “infix” notation, and transform it into “postfix” notation.

Lets take this for example:
Infix: (1+2)*(3+4)
Postfix: 1 2 + 3 4 + *

There are a few cases to consider:

  • Numbers
  • Operators
  • Parenthesis

Numbers always appear in the same order which they are processed between infix and postfix, so not much special needs to happen there. Operators are a little more complicated,

Operators are a little more complex. They need to appear in the order which they should be evaluated. There are two things which affect this… parenthesis and the order of operations.

Take the example: 1 + 2 * 3. We always need the multiplication to be evaluated before the addition. There is a simple rule. Every time you encounter an operator, push it onto a stack. At the next operator, if the top of the stack is of greater value, then the stack can be emptied into the output. If the top of the stack is of the same or lesser value, then add the current operator to the stack. This ensures that we will always append the operators which come earlier in the order of operations first.

A walkthrough of 1 + 2 * 3 - 4

Token | Stack | Output
  1   |       |                 <- 1 is a number, can go directly to output
  +   |       |   1             <- + is an operator, and the stack is empty, so push it onto the stack
  2   |   +   |   1             <- 2 is a number, can go directly to output
  *   |   +   |  1 2            <- * is an operator, but the operator on the top of the stack is less important
  3   |  * +  |  1 2            <- 3 is a number, it can go directly to output
  -   |  * +  | 1 2 3           <- - is an operator, less important than '*' which is on top of the stack,
                                    so empty the stack, and add the '-' onto the stack
  4   |   -   | 1 2 3 * +       <- 4 is a number, it can go directly to output
      |   -   | 1 2 3 * + 4     <- We're out of tokens, so empty the stack
      |       | 1 2 3 * + 4 -

Parenthesis can just be handle recursively. When a parenthesis is encountered, everything on the inside should be processed and sent to the output before continuing forward.

A walkthrough of 1 * (2 + 3)

Token | Stack | Output
  1   |       |             <- 1 is a number, can go directly to output
  *   |       |   1         <- + is an operator, and the stack is empty, so push it onto the stack
  (   |   *   |   1             <- Hit a parenthesis, so recurse and process the inside
  
  2   |          |          <- 2 is a number, can go directly to the output
  +   |       |   2         <- + is an operator, and the stack is empty, so push it.
  3   |   +   |   2         <- 3 is a number, can go directly to output
  )   |   +   |  2 3        <- Hit a close parenthesis, so empty the stack and unwinde from recursion
      |       | 2 3 +  
  
      |   *   | 1 2 3 +     <- Append the result of the recursive call
      |       | 1 2 3 + *   <- We're out of tokens, to empty the stack into the output

Here is some poweshell which takes this approach.

#
# Converts an infix expression into a postfix style expression
#
function InfixTo-Postfix
{
    [CmdletBinding()]
    param
    (
        [Parameter(Mandatory=$true, ValueFromPipeline = $true)][String]$InfixString
    )

    process
    {
        # Queue of all of the tokens we split the input string into
        # Numbers, operators, parenthesis
        $tokenQueue = [System.Collections.Queue]::new();

        # To build up numbers, in case they are more than a single digit.
        $currentNumber = '';

        # Go through each chacter in the string, and split it into tokens
        foreach($c in $InfixString.ToCharArray())
        {
            if ([char]::IsDigit($c))
            {
                # Build up the current digit/number
                $currentNumber += $c;
            }
            else
            {
                # Enqueue the current number into the token queue.
                if ($currentNumber  -ne '')
                {
                    $tokenQueue.Enqueue($currentNumber);
                    $currentNumber = '';
                }

                # Anything else which isn't whitespace is an operator (or a variable: a*b)
                if (-not [char]::IsWhiteSpace($c))
                {
                    $tokenQueue.Enqueue($c);
                }
            }
        }
        
        # If theres anything in the number we're working on, add that as well.
        if ($currentNumber  -ne '')
        {
            $tokenQueue.Enqueue($currentNumber);
        }       

        # Define the supported operators
        # Give each operator a weight, following the order of operations.
        $operators = @{};
        $operators[[char]'^'] = 2;
        $operators[[char]'*'] = 1;
        $operators[[char]'/'] = 1;
        $operators[[char]'+'] = 0;
        $operators[[char]'-'] = 0;

        # Helper function to handle everything underneath a set of parenthesis
        # Assumes that the open parenthsis has been removed from the token queue.
        function HandleParenthesis
        {
            # The output queue, this is where we'll write the result.
            $outQueue = @();

            # The operator stack.
            $operatorStack = [System.Collections.Stack]::new();

            # When the token queue is not empty
            while ($tokenQueue.Count -gt 0)
            {
                # Take the next item from the queue
                $item = $tokenQueue.Dequeue();
                
                if ($item -eq '(')
                {
                    # If it is an open parenthesis, we shoudl recurse.
                    $outQueue += HandleParenthesis
                }
                elseif ($item -eq ')')
                {
                    # On a close parenthesis, we're all done.
                    break;
                }
                elseif($operators.ContainsKey($item))
                {
                    # On an operator. Check to see if the top operator on the stack has a higher value than the current one.
                    # For example, if a '+' follows a '*', we need to do the '*' before the '+'.
                    if ($operatorStack.Count -gt 0 -and $operators[$operatorStack.Peek()] -gt $operators[$item])
                    {
                        while ($operatorStack.Count -gt 0)
                        {
                            $outQueue += $operatorStack.Pop();
                        }
                    }

                    # Push the current operator onto the stack
                    $operatorStack.Push($item);
                }
                else
                {
                    # Anything else, just append to the output.
                    $outQueue += $item;
                }
            }

            # If we have read all of the tokens we need to read, but there are still operators on the stack, finish popping them off.
            while ($operatorStack.Count -gt 0)
            {
                $outQueue += $operatorStack.Pop();
            }

            # Return the output.
            return $outQueue
        }   

        # Proecess the equation
        $outQueue = HandleParenthesis

        # The output queue is an array, so just turn it into a string
        return ($outQueue -join ' ');
    }
}
InfixTo-Postfix "x ^ y / (5 * z) + 10"
InfixTo-Postfix "(1+2)*(3+4)"
InfixTo-Postfix "1 ^ 2 ^ 3 ^ 4 ^ 5 * 6"

x y ^ 5 z * / 10 +
1 2 + 3 4 + *
1 2 3 4 5 ^ ^ ^ ^ 6 *

While we’re here lets do some golf.

function InfixTo-PostfixGolf($i){Set-Variable q -Value([regex]'([\d]+)|([\(\)\S])').Matches($i).Value -Option AllScope;function F{$o=@();$s=@();$e=@{'-'=0;'+'=0;'/'=1;'*'=1;'^'=2;};while($q){$t,$q=$q;switch($t){'('{$o+=F}')'{return $o+$s}({$e.ContainsKey($t)}){if($s-and$e[$s[0]]-gt$e[$t]){$o+=$s;$s=@()}$s=,$t+$s;}default{$o+=$t}}}$o+$s}(F)-join' '}

That’s 351 characters. It definitely seems like a sub-par solution, so I’ll be back.

It’s important to note that this solution takes a recursive approach to handling parenthesis. Another option is to push the parenthesis onto the stack, and use them as barriers when popping off operators. Aka, pop until you get back to the open parenthesis.

bookmark_borderSafely SetResult in TaskCompletionSource

tl/dr; When writing a library, or you don’t have control over the users, queue TaskCompletionSource.SetResult(…) calls in a new threadpool work item or inside of Task.Run. Since SetResult will execute anything awaiting it inline.

The C# TaskCompletionSource is an incredibly powerful part of the Task Parallel library. It’s an incredibly low level building block for asynchronous design, allowing for the creation of more advanced async structures. Its default behavior though, is unexpected and can lead to non trivial program bugs, performance issues, and deadlocks.

var source = new TaskCompletionSource<bool>();

// ...

source.SetResult(true);

An issue could arise when SetResult is called. By default, a TaskCompletionSource executes all continuations inline, when SetResult is called. This would be any case of (await, .ContinueWith). In the usual case, this is fine, but there are some scenarios when this is not expected.

The code sample below creates several tasks (Writer), which each create a “WorkItem”, and place it into a queue. The work item has a task completion source on it. Once the work item is enqueued, they each wait for the task completion source to be completed. Then They sleep for 1 second. Another task is spun up (Reader) which just waits for a WorkItem to be enqueued, dequeues it, and sets a result on the TaskCompletionSource. Ideally, the Reader should be able to dequeue every item very quickly, as its not really doing any work.

// main
TaskCompletionSourceThroughput.Run(
                
TaskCompletionSourceThroughput.TaskCompletionMode.PlainSetResult,
                count).Wait();
namespace Badflyer.TCSDeadlock
{
    using System;
    using System.Collections.Concurrent;
    using System.Diagnostics;
    using System.Linq;
    using System.Threading;
    using System.Threading.Tasks;

    internal class TaskCompletionSourceThroughput
    {
        public enum TaskCompletionMode
        {
            /// <summary>
            /// Just use regular old set result on a task completion source.
            /// </summary>
            PlainSetResult,

            /// <summary>
            /// Call set result, but create the TCS with TaskCreationOptions.RunContinuationsAsynchronously 
            /// </summary>
            SetResultWithAsyncContinuations,

            /// <summary>
            /// Call set result in a new threadpool action:  Task.Run(() => item.Completion.TrySetResult(item.Value));
            /// </summary>
            SetResultInTaskRun
        }

        private readonly int count;
        private readonly TaskCompletionMode mode;
        private readonly CancellationTokenSource cancellation;
        private readonly SemaphoreSlim gate;
        private readonly Stopwatch stopWatch;
        private readonly ConcurrentQueue<WorkItem<string>> workItems;

        private TaskCompletionSourceThroughput(TaskCompletionMode mode, int count)
        {
            this.count = count;
            this.mode = mode;
            this.cancellation = new CancellationTokenSource();
            this.gate = new SemaphoreSlim(0);
            this.stopWatch = Stopwatch.StartNew();
            this.workItems = new ConcurrentQueue<WorkItem<string>>();
        }

        /// <summary>
        /// Runs the test.
        /// </summary>
        /// <param name="mode">How to complet the task completion source during the test.</param>
        /// <param name="numberOfItems">The number of items to run with.</param>
        /// <returns>A task when the test is completed.</returns>
        internal static Task Run(TaskCompletionMode mode, int numberOfItems)
        {
            var test = new TaskCompletionSourceThroughput(mode, numberOfItems);
            return test.Run();
        }

        /// <summary>
        /// Run the test.
        /// </summary>
        /// <returns>An async that completes when the test does.</returns>
        private async Task Run()
        {
            // Start up these worker tasks which enqueue work items.
            var tasks = Enumerable.Range(0, count)
                .Select(i => Task.Run(() => Writer(i))).ToList();

            // Start up the reader task, which dequeues work items and complets them.
            var reader = Task.Run(Reader);

            await Task.WhenAll(tasks);
            this.cancellation.Cancel();
        }

        /// <summary>
        /// Reads each item from the workitems list, and completes it as quickly as it can.
        /// </summary>
        private async Task Reader()
        {
            var token = this.cancellation.Token;
            this.LogMessage("Starting Reader.");
            while (false == token.IsCancellationRequested)
            {
                try
                {
                    await gate.WaitAsync(token);
                }
                catch (OperationCanceledException)
                {
                    break;
                }

                this.workItems.TryDequeue(out var item);

                if (this.mode == TaskCompletionMode.SetResultInTaskRun)
                {
                    _ = Task.Run(() => item.Completion.TrySetResult(item.Value));
                }
                else
                {
                    item.Completion.TrySetResult(item.Value);
                }
            }

            this.LogMessage("Finished reader.");
        }

        /// <summary>
        /// Creates a new work item, enqueues it to the work items list, and waits for the reader task to complete the item.
        /// After the item is completed, it sleeps for 1 second.
        /// </summary>
        private async Task Writer(int index)
        {
            var item = new WorkItem<string>(this.mode, $"Finished Item {index}");
            this.workItems.Enqueue(item);
            this.gate.Release();

            var text = await item.Completion.Task;

            this.LogMessage(text);

            Thread.Sleep(1000);
        }

        /// <summary>
        /// Logs a message.
        /// </summary>
        /// <param name="message">The message.</param>
        private void LogMessage(string message)
        {
            Console.WriteLine("{0:0.000} [{1}] -> {2}", stopWatch.Elapsed.TotalSeconds, this.mode, message);
        }

        /// <summary>
        /// A simple work item class.
        /// </summary>
        /// <typeparam name="T">The type of the item result.</typeparam>
        private class WorkItem<T>
        {
            public WorkItem(TaskCompletionMode mode, T value)
            {
                this.Value = value;

                if (mode == TaskCompletionMode.SetResultWithAsyncContinuations)
                {
                    this.Completion = new TaskCompletionSource<T>(TaskContinuationOptions.RunContinuationsAsynchronously);
                }
                else
                {
                    this.Completion = new TaskCompletionSource<T>();
                }
            }

            public T Value { get; }

            public TaskCompletionSource<T> Completion;
        }
    }
}

The issue here will be caused in “Writer” during Thread.Sleep(1000). Its not exactly obvious, but since the TaskCompletionSource was being await, this part of the method is being run as a continuation to the completion source. Since by default, the TaskCompletionSource will queue and run everything inline when SetResult is called, this is actually running in the same thread as “Reader”.

TaskCompletionSource.SetResult doesn’t seem like it should be an expensive call, but it could be, depending on what the child decides to do. So in this case, Reader, which should be a super fast loop releasing a bunch of other threads, actually serializes the execution of all of the work items.

// Here is the output of the program
1.212 [PlainSetResult] -> Finished Item 2
2.214 [PlainSetResult] -> Finished Item 0
3.220 [PlainSetResult] -> Finished Item 3
4.222 [PlainSetResult] -> Finished Item 4
5.236 [PlainSetResult] -> Finished reader.

Now, task completion source does provide an option to specify TaskContinuationOptions. One of which is RunContinuationsAsynchronously. This does not seem to work as expected. This program can run with different arguments to utilize this feature.

// main

// This will create the TaskCompletionSource with the RunContinuationsAsynchronously parameter. 
// aka: new TaskCompletionSource(TaskCreationOptions.RunContinuationsAsynchronously)

TaskCompletionSourceThroughput.Run(TaskCompletionSourceThroughput.TaskCompletionMode.SetResultWithAsyncContinuations).Wait();
// The results still show the output running serialized.

0.008 [SetResultWithAsyncContinuations] -> Starting Reader.
0.008 [SetResultWithAsyncContinuations] -> Finished Item 0
1.010 [SetResultWithAsyncContinuations] -> Finished Item 1
2.013 [SetResultWithAsyncContinuations] -> Finished Item 2
3.016 [SetResultWithAsyncContinuations] -> Finished Item 3
4.018 [SetResultWithAsyncContinuations] -> Finished Item 4
5.020 [SetResultWithAsyncContinuations] -> Finished reader.

For best performance, if you know that your continuations will be running lots of work, and you don’t want them to be serialized. You can always force the continuations to run in a different threadpool work item.

// Always run in a new threadpool thread.
Task.Run(() => taskCompletionSource.TrySetResult(result));

Doing this will add a lot of overhead if continuations are really quick, but will drastically improve performance if they are slow.

// main

// This will complete the task completion source task in a new threadpool thread.

TaskCompletionSourceThroughput.Run(TaskCompletionSourceThroughput.TaskCompletionMode.SetResultInTaskRun).Wait();
// Results

0.034 [SetResultInTaskRun] -> Starting Reader.
0.036 [SetResultInTaskRun] -> Finished Item 1
0.036 [SetResultInTaskRun] -> Finished Item 0
0.037 [SetResultInTaskRun] -> Finished Item 2
0.039 [SetResultInTaskRun] -> Finished Item 3
0.040 [SetResultInTaskRun] -> Finished Item 4
1.188 [SetResultInTaskRun] -> Finished reader

As you can see, these actually ended up running in a parallel nature.

The takeaway from this is that if you know that the functions awaiting your TaskCompletionSource are going to be doing heavy, slow work, or if you have no control over what they could be then be sure to call SetResult in a new threadpool thread. Another good example of this is Sytem.Net.Threading.SemaphoreSlim, which will always completion its waiting TaskCompletionSource in a new threadpool thread. https://referencesource.microsoft.com/#mscorlib/system/threading/SemaphoreSlim.cs,117283ce80a6dfb9