Sawmill

Class Rewriter

Extension methods for IRewriter<T> implementations.

Inheritance
Declaration
public static class Rewriter : Object

Methods

ChildrenInContext<T>(IRewriter<T>, T)

Returns an array containing each immediate child of value paired with a function to replace the child. This is typically useful when you need to replace a node's children one at a time, such as during mutation testing.

The replacement function can be seen as the "context" of the child; calling the function with a new child "plugs the hole" in the context.

SelfAndDescendantsInContext<T>(IRewriter<T>, T) DescendantsAndSelfInContext<T>(IRewriter<T>, T)
Declaration
public static (T, Func<T, T>)[] ChildrenInContext<T>(this IRewriter<T> rewriter, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

T

value

The value to get the contexts for the immediate children

Returns
Type Description

(, )<T, Func<T, T>>[]

Type Parameters
Name Description

T

Cursor<T>(IRewriter<T>, T)

Create a Cursor<T>(IRewriter<T>, T) focused on the root node of value.

Declaration
public static Cursor<T> Cursor<T>(this IRewriter<T> rewriter, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

T

value

The root node on which the newly created Cursor<T>(IRewriter<T>, T) should be focused

Returns
Type Description

Cursor<T>

A Cursor<T>(IRewriter<T>, T) focused on the root node of value

Type Parameters
Name Description

T

DescendantAt<T>(IRewriter<T>, IEnumerable<Direction>, T)

Returns the descendant at a particular location in value

Declaration
public static T DescendantAt<T>(this IRewriter<T> rewriter, IEnumerable<Direction> path, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

IEnumerable<Direction>

path

The route to take to find the descendant

T

value

The rewritable tree type

Returns
Type Description

T

The descendant found by following the directions in path

Type Parameters
Name Description

T

Exceptions
Type Condition

InvalidOperationException

Thrown if path leads off the edge of the tree

DescendantsAndSelf<T>(IRewriter<T>, T)

Yields all of the nodes in the tree represented by value, starting at the bottom.

This is a depth-first post-order traversal.

SelfAndDescendants<T>(IRewriter<T>, T)
Declaration
public static IEnumerable<T> DescendantsAndSelf<T>(this IRewriter<T> rewriter, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

T

value

The value to traverse

Returns
Type Description

IEnumerable<T>

An enumerable containing all of the nodes in the tree represented by value, starting at the bottom.

Type Parameters
Name Description

T

The rewritable tree type

Examples
Expr expr = new Add(
    new Add(
        new Lit(1),
        new Lit(2)
    ),
    new Lit(3)
);
Expr[] expected = new[]
    {
        new Lit(1),
        new Lit(2),
        new Add(new Lit(1), new Lit(2)),
        new Lit(3),
        expr    
    };
Assert.Equal(expected, rewriter.DescendantsAndSelf(expr));

DescendantsAndSelfInContext<T>(IRewriter<T>, T)

Yields each node in the tree represented by value paired with a function to replace the node, starting at the bottom. This is typically useful when you need to replace nodes one at a time, such as during mutation testing.

The replacement function can be seen as the "context" of the node; calling the function with a new node "plugs the hole" in the context.

This is a depth-first post-order traversal.

DescendantsAndSelf<T>(IRewriter<T>, T) ChildrenInContext<T>(IRewriter<T>, T) SelfAndDescendantsInContext<T>(IRewriter<T>, T)
Declaration
public static IEnumerable<(T, Func<T, T>)> DescendantsAndSelfInContext<T>(this IRewriter<T> rewriter, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

T

value

The value to get the contexts for the descendants

Returns
Type Description

IEnumerable<(, )<T, Func<T, T>>>

Type Parameters
Name Description

T

Fold<T, U>(IRewriter<T>, SpanFunc<U, T, U>, T)

Flattens all the nodes in the tree represented by value into a single result, using an aggregation function to combine each node with the results of folding its children.

Declaration
public static U Fold<T, U>(this IRewriter<T> rewriter, SpanFunc<U, T, U> func, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

SpanFunc<U, T, U>

func

The aggregation function

T

value

The value to fold

Returns
Type Description

U

The result of aggregating the tree represented by value.

Type Parameters
Name Description

T

The rewritable tree type

U

The type of the result of aggregation

Fold<T, U>(IRewriter<T>, Func<Memory<U>, T, ValueTask<U>>, T)

Flattens all the nodes in the tree represented by value into a single result, using an asynchronous aggregation function to combine each node with the results of folding its children.

Declaration
public static ValueTask<U> Fold<T, U>(this IRewriter<T> rewriter, Func<Memory<U>, T, ValueTask<U>> func, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

Func<Memory<U>, T, ValueTask<U>>

func

The asynchronous aggregation function

T

value

The value to fold

Returns
Type Description

ValueTask<U>

The result of aggregating the tree represented by value.

Type Parameters
Name Description

T

The rewritable tree type

U

The type of the result of aggregation

Remarks

This method is not available on platforms which do not support ValueTask.

GetChildren<T>(IRewriter<T>, T)

Get the immediate children of the value. GetChildren(Span<T>)

Declaration
public static T[] GetChildren<T>(this IRewriter<T> rewriter, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

T

value

The value

Returns
Type Description

T[]

The immediate children of value

Type Parameters
Name Description

T

The rewritable tree type

Examples

Given a representation of the expression (1+2)+3,

Expr expr = new Add(
    new Add(
        new Lit(1),
        new Lit(2)
    ),
    new Lit(3)
);

GetChildren<T>(IRewriter<T>, T) returns the immediate children of the topmost node.

Expr[] expected = new[]
    {
        new Add(
            new Lit(1),
            new Lit(2)
        ),
        new Lit(3)
    };
Assert.Equal(expected, rewriter.GetChildren(expr));

ReplaceDescendantAt<T>(IRewriter<T>, IEnumerable<Direction>, T, T)

Replaces the descendant at a particular location in value

Declaration
public static T ReplaceDescendantAt<T>(this IRewriter<T> rewriter, IEnumerable<Direction> path, T newDescendant, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

IEnumerable<Direction>

path

The route to take to find the descendant

T

newDescendant

The replacement descendant

T

value

The rewritable tree type

Returns
Type Description

T

A copy of value with newDescendant placed at the location indicated by path

Type Parameters
Name Description

T

Exceptions
Type Condition

InvalidOperationException

Thrown if path leads off the edge of the tree

Rewrite<T>(IRewriter<T>, Func<T, T>, T)

Rebuild a tree by applying a transformation function to every node from bottom to top.

Declaration
public static T Rewrite<T>(this IRewriter<T> rewriter, Func<T, T> transformer, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

Func<T, T>

transformer

The transformation function to apply to every node in the tree

T

value

The value to rewrite

Returns
Type Description

T

The result of applying transformer to every node in the tree represented by value.

Type Parameters
Name Description

T

The rewritable tree type

Examples

Given a representation of the expression (1+2)+3,

Expr expr = new Add(
    new Add(
        new Lit(1),
        new Lit(2)
    ),
    new Lit(3)
);

Rewrite<T>(IRewriter<T>, Func<T, T>, T) replaces the leaves of the tree with the result of calling transformer, then replaces their parents with the result of calling transformer, and so on. By the end, Rewrite<T>(IRewriter<T>, Func<T, T>, T) has traversed the whole tree.

Expr expected = transformer(new Add(
    transformer(new Add(
        transformer(new Lit(1)),
        transformer(new Lit(2))
    )),
    transformer(new Lit(3))
));
Assert.Equal(expected, rewriter.Rewrite(transformer, expr));

Rewrite<T>(IRewriter<T>, Func<T, ValueTask<T>>, T)

Rebuild a tree by applying an asynchronous transformation function to every node from bottom to top.

Declaration
public static ValueTask<T> Rewrite<T>(this IRewriter<T> rewriter, Func<T, ValueTask<T>> transformer, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

Func<T, ValueTask<T>>

transformer

The asynchronous transformation function to apply to every node in the tree

T

value

The value to rewrite

Returns
Type Description

ValueTask<T>

The result of applying transformer to every node in the tree represented by value.

Type Parameters
Name Description

T

The rewritable tree type

Remarks

This method is not available on platforms which do not support ValueTask.

Examples

Given a representation of the expression (1+2)+3,

Expr expr = new Add(
    new Add(
        new Lit(1),
        new Lit(2)
    ),
    new Lit(3)
);

Rewrite<T>(IRewriter<T>, Func<T, ValueTask<T>>, T) replaces the leaves of the tree with the result of calling transformer, then replaces their parents with the result of calling transformer, and so on. By the end, Rewrite<T>(IRewriter<T>, Func<T, ValueTask<T>>, T) has traversed the whole tree.

Expr expected = await transformer(new Add(
    await transformer(new Add(
        await transformer(new Lit(1)),
        await transformer(new Lit(2))
    )),
    await transformer(new Lit(3))
));
Assert.Equal(expected, await rewriter.Rewrite(transformer, expr));

RewriteChildren<T>(IRewriter<T>, Func<T, T>, T)

Update the immediate children of the value by applying a transformation function to each one.

Declaration
public static T RewriteChildren<T>(this IRewriter<T> rewriter, Func<T, T> transformer, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

Func<T, T>

transformer

A transformation function to apply to each of value's immediate children.

T

value

The old value, whose immediate children should be transformed by transformer.

Returns
Type Description

T

A copy of value with updated children.

Type Parameters
Name Description

T

The rewritable tree type

RewriteChildren<T>(IRewriter<T>, Func<T, ValueTask<T>>, T)

Update the immediate children of the value by applying an asynchronous transformation function to each one.

Declaration
public static ValueTask<T> RewriteChildren<T>(this IRewriter<T> rewriter, Func<T, ValueTask<T>> transformer, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

Func<T, ValueTask<T>>

transformer

An asynchronous transformation function to apply to each of value's immediate children.

T

value

The old value, whose immediate children should be transformed by transformer.

Returns
Type Description

ValueTask<T>

A copy of value with updated children.

Type Parameters
Name Description

T

The rewritable tree type

Remarks

This method is not available on platforms which do not support ValueTask.

RewriteDescendantAt<T>(IRewriter<T>, IEnumerable<Direction>, Func<T, T>, T)

Apply a function at a particular location in value

Declaration
public static T RewriteDescendantAt<T>(this IRewriter<T> rewriter, IEnumerable<Direction> path, Func<T, T> transformer, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

IEnumerable<Direction>

path

The route to take to find the descendant

Func<T, T>

transformer

A function to calculate a replacement for the descendant

T

value

The rewritable tree type

Returns
Type Description

T

A copy of value with the result of transformer placed at the location indicated by path

Type Parameters
Name Description

T

Exceptions
Type Condition

InvalidOperationException

Thrown if path leads off the edge of the tree

RewriteDescendantAt<T>(IRewriter<T>, IEnumerable<Direction>, Func<T, ValueTask<T>>, T)

Apply an asynchronous function at a particular location in value

Declaration
public static ValueTask<T> RewriteDescendantAt<T>(this IRewriter<T> rewriter, IEnumerable<Direction> path, Func<T, ValueTask<T>> transformer, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

IEnumerable<Direction>

path

The route to take to find the descendant

Func<T, ValueTask<T>>

transformer

An asynchronous function to calculate a replacement for the descendant

T

value

The rewritable tree type

Returns
Type Description

ValueTask<T>

A copy of value with the result of transformer placed at the location indicated by path

Type Parameters
Name Description

T

Remarks

This method is not available on platforms which do not support ValueTask.

Exceptions
Type Condition

InvalidOperationException

Thrown if path leads off the edge of the tree

RewriteIter<T>(IRewriter<T>, Func<T, T>, T)

Rebuild a tree by repeatedly applying a transformation function to every node in the tree, until a fixed point is reached. transformer should always eventually return its argument unchanged, or this method will loop. That is, x.RewriteIter(transformer).SelfAndDescendants().All(x => transformer(x) == x).

This is typically useful when you want to put your tree into a normal form by applying a collection of rewrite rules until none of them can fire any more.

Declaration
public static T RewriteIter<T>(this IRewriter<T> rewriter, Func<T, T> transformer, T value)
    where T : class
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

Func<T, T>

transformer

A transformation function to apply to every node in value repeatedly.

T

value

The value to rewrite

Returns
Type Description

T

The result of applying transformer to every node in the tree represented by value repeatedly until a fixed point is reached.

Type Parameters
Name Description

T

The rewritable tree type

RewriteIter<T>(IRewriter<T>, Func<T, ValueTask<T>>, T)

Rebuild a tree by repeatedly applying an asynchronous transformation function to every node in the tree, until a fixed point is reached. transformer should always eventually return its argument unchanged, or this method will loop. That is, x.RewriteIter(transformer).SelfAndDescendants().All(x => await transformer(x) == x).

This is typically useful when you want to put your tree into a normal form by applying a collection of rewrite rules until none of them can fire any more.

Declaration
public static ValueTask<T> RewriteIter<T>(this IRewriter<T> rewriter, Func<T, ValueTask<T>> transformer, T value)
    where T : class
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

Func<T, ValueTask<T>>

transformer

An asynchronous transformation function to apply to every node in value repeatedly.

T

value

The value to rewrite

Returns
Type Description

ValueTask<T>

The result of applying transformer to every node in the tree represented by value repeatedly until a fixed point is reached.

Type Parameters
Name Description

T

The rewritable tree type

Remarks

This method is not available on platforms which do not support ValueTask.

SelfAndDescendants<T>(IRewriter<T>, T)

Yields all of the nodes in the tree represented by value, starting at the top.

This is a depth-first pre-order traversal.

DescendantsAndSelf<T>(IRewriter<T>, T)
Declaration
public static IEnumerable<T> SelfAndDescendants<T>(this IRewriter<T> rewriter, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

T

value

The value to traverse

Returns
Type Description

IEnumerable<T>

An enumerable containing all of the nodes in the tree represented by value, starting at the top.

Type Parameters
Name Description

T

The rewritable tree type

Examples
Expr expr = new Add(
    new Add(
        new Lit(1),
        new Lit(2)
    ),
    new Lit(3)
);
Expr[] expected = new[]
    {
        expr,
        new Add(new Lit(1), new Lit(2)),
        new Lit(1),
        new Lit(2),
        new Lit(3),
    };
Assert.Equal(expected, rewriter.SelfAndDescendants(expr));

SelfAndDescendantsBreadthFirst<T>(IRewriter<T>, T)

Yields all of the nodes in the tree represented by value in a breadth-first traversal order.

This is a breadth-first pre-order traversal.

Declaration
public static IEnumerable<T> SelfAndDescendantsBreadthFirst<T>(this IRewriter<T> rewriter, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

T

value

The value to traverse

Returns
Type Description

IEnumerable<T>

An enumerable containing all of the nodes in the tree represented by value in a breadth-first traversal order.

Type Parameters
Name Description

T

The rewritable tree type

SelfAndDescendantsInContext<T>(IRewriter<T>, T)

Yields each node in the tree represented by value paired with a function to replace the node, starting at the top. This is typically useful when you need to replace nodes one at a time, such as during mutation testing.

The replacement function can be seen as the "context" of the node; calling the function with a new node "plugs the hole" in the context.

This is a depth-first pre-order traversal.

SelfAndDescendants<T>(IRewriter<T>, T) ChildrenInContext<T>(IRewriter<T>, T) DescendantsAndSelfInContext<T>(IRewriter<T>, T)
Declaration
public static IEnumerable<(T, Func<T, T>)> SelfAndDescendantsInContext<T>(this IRewriter<T> rewriter, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

T

value

The value to get the contexts for the descendants

Returns
Type Description

IEnumerable<(, )<T, Func<T, T>>>

Type Parameters
Name Description

T

SelfAndDescendantsInContextBreadthFirst<T>(IRewriter<T>, T)

Yields each node in the tree represented by value paired with a function to replace the node, in a breadth-first traversal order. This is typically useful when you need to replace nodes one at a time, such as during mutation testing.

The replacement function can be seen as the "context" of the node; calling the function with a new node "plugs the hole" in the context.

This is a breadth-first pre-order traversal.

SelfAndDescendants<T>(IRewriter<T>, T) ChildrenInContext<T>(IRewriter<T>, T) DescendantsAndSelfInContext<T>(IRewriter<T>, T)
Declaration
public static IEnumerable<(T, Func<T, T>)> SelfAndDescendantsInContextBreadthFirst<T>(this IRewriter<T> rewriter, T value)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

T

value

The value to get the contexts for the descendants

Returns
Type Description

IEnumerable<(, )<T, Func<T, T>>>

Type Parameters
Name Description

T

ZipFold<T, U>(IRewriter<T>, Func<T[], IAsyncEnumerable<U>, ValueTask<U>>, T[])

Flatten all of the nodes in the trees represented by values into a single value at the same time, using an aggregation function to combine nodes with the results of aggregating their children. The trees are iterated in lock-step, much like an n-ary Zip<TFirst,TSecond,TResult>(IEnumerable<TFirst>, IEnumerable<TSecond>, Func<TFirst,TSecond,TResult>).

When trees are not the same size, the larger ones are truncated both horizontally and vertically. That is, if a pair of nodes have a different number of children, the rightmost children of the larger of the two nodes are discarded.

Declaration
public static ValueTask<U> ZipFold<T, U>(this IRewriter<T> rewriter, Func<T[], IAsyncEnumerable<U>, ValueTask<U>> func, params T[] values)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

Func<T[], IAsyncEnumerable<U>, ValueTask<U>>

func

The aggregation function

T[]

values

The trees to fold

Returns
Type Description

ValueTask<U>

The result of aggregating the two trees

Type Parameters
Name Description

T

The rewritable tree type

U

The return type of the aggregation

Remarks

This method is not available on platforms which do not support ValueTask and IAsyncEnumerable<T>.

Examples

Here's an example of using ZipFold<T, U>(IRewriter<T>, Func<T[], IAsyncEnumerable<U>, ValueTask<U>>, T[]) to test if two trees are syntactically equal.

static bool Equals(this Expr left, Expr right)
    => left.ZipFold<Expr, bool>(
        right,
        (xs, results) =>
        {
            switch (xs[0])
            {
                case Add a1 when xs[1] is Add a2:
                    return results.All(x => x);
                case Lit l1 when xs[1] is Lit l2:
                    return l1.Value == l2.Value;
                default:
                    return false;
            }
        }
    );

ZipFold<T, U>(IRewriter<T>, Func<T[], IEnumerable<U>, U>, T[])

Flatten all of the nodes in the trees represented by values into a single value at the same time, using an aggregation function to combine nodes with the results of aggregating their children. The trees are iterated in lock-step, much like an n-ary Zip<TFirst,TSecond,TResult>(IEnumerable<TFirst>, IEnumerable<TSecond>, Func<TFirst,TSecond,TResult>).

When trees are not the same size, the larger ones are truncated both horizontally and vertically. That is, if a pair of nodes have a different number of children, the rightmost children of the larger of the two nodes are discarded.

Declaration
public static U ZipFold<T, U>(this IRewriter<T> rewriter, Func<T[], IEnumerable<U>, U> func, params T[] values)
Parameters
Type Name Description

IRewriter<T>

rewriter

The rewriter

Func<T[], IEnumerable<U>, U>

func

The aggregation function

T[]

values

The trees to fold

Returns
Type Description

U

The result of aggregating the two trees

Type Parameters
Name Description

T

The rewritable tree type

U

The return type of the aggregation

Examples

Here's an example of using ZipFold<T, U>(IRewriter<T>, Func<T[], IEnumerable<U>, U>, T[]) to test if two trees are syntactically equal.

static bool Equals(this Expr left, Expr right)
    => left.ZipFold<Expr, bool>(
        right,
        (xs, results) =>
        {
            switch (xs[0])
            {
                case Add a1 when xs[1] is Add a2:
                    return results.All(x => x);
                case Lit l1 when xs[1] is Lit l2:
                    return l1.Value == l2.Value;
                default:
                    return false;
            }
        }
    );