Sawmill

Class Cursor<T>

A Cursor<T> is a mutable view of a location in a T-structure, allowing efficient access to (and editing of) a node and its parent, siblings, and immediate children.

You can think of a Cursor<T> as being focused on a particular node. After zooming in on a node, you can efficiently go up to the node's parent, down to the node's first child, or left or right to the node's immediate siblings.

Cursor<T> is generally not as efficient or useful as the SelfAndDescendantsInContext<T>(IRewriter<T>, T) family for replacing single nodes, but it efficiently supports longer sequences of edits to a location and its neighbours.

Inheritance
Declaration
public sealed class Cursor<T> : Object
Type Parameters
Name Description

T

Examples

Here we traverse to, and replace, the right child of a binary node.

Expr expr = new Add(new Lit(1), new Neg(new Lit(2)));
var cursor = expr.Cursor();
cursor.Down();
cursor.Right();

Assert.Equal(new Neg(new Lit(2)), cursor.Focus);

cursor.Focus = new Lit(10);
cursor.Top();

Assert.Equal(new Add(new Lit(1), new Lit(10)), cursor.Focus);

Properties

Focus

Gets or sets the current focus of the Cursor<T>

Declaration
public T Focus { get; set; }
Property Value
Type Description

T

The current focus of the Cursor<T>

Methods

Bottom()

Move the current Focus to the bottom-left of the tree. Do nothing if the current Focus has no children.

Declaration
public void Bottom()

Down()

Focus the Cursor<T> on the current Focus's first child.

This operation "opens a hole" in the current node, descending to the children so you can replace them one at a time.

Declaration
public void Down()
Exceptions
Type Condition

InvalidOperationException

The current Focus's has no children.

Down(Int32)

Go Down() count times.

This operation "opens a hole" in the current node and its count first descendants.

Declaration
public void Down(int count)
Parameters
Type Name Description

Int32

count

Exceptions
Type Condition

InvalidOperationException

The Cursor<T> reached a node with no children. The Cursor<T> is left in the last good state, that is, at the bottom of the tree.

ArgumentOutOfRangeException

count was negative

DownWhile(Func<T, Boolean>)

Go Down() as long as predicate returns true for the current Focus. In other words, find the first leftmost descendant of Focus (including itself) which does not satisfy predicate.

Declaration
public void DownWhile(Func<T, bool> predicate)
Parameters
Type Name Description

Func<T, Boolean>

predicate

The predicate to invoke on the current focus and its leftmost descendants

Exceptions
Type Condition

InvalidOperationException

The Cursor<T> reached the root node. The Cursor<T> is left in the last good state, that is, at the bottom of the tree.

Follow(IEnumerable<Direction>)

Follow a path.

Declaration
public void Follow(IEnumerable<Direction> path)
Parameters
Type Name Description

IEnumerable<Direction>

path

The path to follow

Exceptions
Type Condition

InvalidOperationException

Thrown when path leads off the edge of the tree. The Cursor<T> is left in the last known good state.

GetPath()

Yields a sequence of Directions describing how to get from the Top() of the tree to the current Focus. The resulting path can be Follow(IEnumerable<Direction>)ed by a Cursor<T>. This is useful if, for example, you need to compare the nodes at a given position in two different trees.

Declaration
public IEnumerable<Direction> GetPath()
Returns
Type Description

IEnumerable<Direction>

A sequence of Directions

Left()

Focus the Cursor<T> on the current Focus's immediate predecessor sibling.

Declaration
public void Left()
Exceptions
Type Condition

InvalidOperationException

The Cursor<T> is already focused on the leftmost sibling

Left(Int32)

Go Left() count times.

Declaration
public void Left(int count)
Parameters
Type Name Description

Int32

count

Exceptions
Type Condition

InvalidOperationException

The Cursor<T> reached the leftmost sibling. The Cursor<T> is left in the last good state, that is, focused on the leftmost sibling.

ArgumentOutOfRangeException

count was negative

Leftmost()

Focus the Cursor<T> on the current Focus's leftmost sibling. Do nothing if the Cursor<T> is already focused on the leftmost sibling.

Declaration
public void Leftmost()

LeftWhile(Func<T, Boolean>)

Go Left() as long as predicate returns true for the current Focus. In other words, find the first left sibling of Focus (including itself) which does not satisfy predicate.

Declaration
public void LeftWhile(Func<T, bool> predicate)
Parameters
Type Name Description

Func<T, Boolean>

predicate

The predicate to invoke on the current focus and its ancestors

Exceptions
Type Condition

InvalidOperationException

The Cursor<T> reached the root node. The Cursor<T> is left in the last good state, that is, at the leftmost sibling.

Move(Direction)

Move in a given Direction

Declaration
public void Move(Direction direction)
Parameters
Type Name Description

Direction

direction

The Direction to move in

Exceptions
Type Condition

InvalidOperationException

Thrown when the direction leads off the edge of the tree. The Cursor<T> is left in the last known good state.

ArgumentOutOfRangeException

Thrown when direction is not a valid Direction

ReleaseOldVersions()

Release old versions of the tree for garbage collection. The Cursor<T> is left focused on the current node.

Typically you won't need to call this method yourself - just call Top() at the end of your sequence of edits to get the new tree back. (This method is equivalent to calling Top() and then returning to where you were.)

The worst-case scenario for Cursor<T>'s memory usage is code which traverses a large tree and alternates Down() calls with setting the Focus, without any calls to Up() in between. If this is a typical usage pattern for your application, and you find that Cursor<T> is causing high memory usage because it's holding on to old trees, some infrequent calls to this method (say, every 1000 edits) should improve the memory usage (at the cost of some speed).

Declaration
public void ReleaseOldVersions()

Right()

Focus the Cursor<T> on the current Focus's immediate successor sibling.

Declaration
public void Right()
Exceptions
Type Condition

InvalidOperationException

The Cursor<T> is already focused on the rightmost sibling

Right(Int32)

Go Right() count times.

Declaration
public void Right(int count)
Parameters
Type Name Description

Int32

count

Exceptions
Type Condition

InvalidOperationException

The Cursor<T> reached the rightmost sibling. The Cursor<T> is left in the last good state, that is, focused on the rightmost sibling.

ArgumentOutOfRangeException

count was negative

Rightmost()

Focus the Cursor<T> on the current Focus's rightmost sibling. Do nothing if the Cursor<T> is already focused on the rightmost sibling.

Declaration
public void Rightmost()

RightWhile(Func<T, Boolean>)

Go Right() as long as predicate returns true for the current Focus. In other words, find the first Right sibling of Focus (including itself) which does not satisfy predicate.

Declaration
public void RightWhile(Func<T, bool> predicate)
Parameters
Type Name Description

Func<T, Boolean>

predicate

The predicate to invoke on the current focus and its ancestors

Exceptions
Type Condition

InvalidOperationException

The Cursor<T> reached the root node. The Cursor<T> is Right in the last good state, that is, at the Rightmost sibling.

SearchDownAndRight(Func<T, Boolean>)

Focus the current focus's first descendant or right sibling's descendant which satisfies , searching descendants before siblings and ending at the current node's rightmost sibling.

This function searches the bottom-left part of the tree first, so will typically end up focusing a node lower down than SearchRightAndDown(Func<T, Boolean>).

SelfAndDescendants<T>(IRewriter<T>, T)
Declaration
public bool SearchDownAndRight(Func<T, bool> predicate)
Parameters
Type Name Description

Func<T, Boolean>

predicate

A predicate which returns true when the search should stop

Returns
Type Description

Boolean

True if a matching focus was found, false if the search was exhaustive

SearchRightAndDown(Func<T, Boolean>)

Focus the current focus's first descendant or right sibling's descendant which satisfies , searching siblings before descendants and ending at the current node's lowest leftmost descendant.

This function searches the top-right part of the tree first, so will typically end up focusing a node higher up than SearchDownAndRight(Func<T, Boolean>).

Declaration
public bool SearchRightAndDown(Func<T, bool> predicate)
Parameters
Type Name Description

Func<T, Boolean>

predicate

A predicate which returns true when the search should stop

Returns
Type Description

Boolean

True if a matching focus was found, false if the search was exhaustive

Top()

Move the Cursor<T> to the top of the tree.

This operation "plugs the hole" in all of the current node's ancestors, replacing their children as necessary. Going to the Top() releases old versions of the tree so that they can be garbage collected.

Declaration
public void Top()

TryDown()

Try to focus the Cursor<T> on the current Focus's first child.

This operation "opens a hole" in the current node, descending to the children so you can replace them one at a time.

Declaration
public bool TryDown()
Returns
Type Description

Boolean

True if the operation was successful, false if the current Focus has no children

TryDown(Int32)

Go Down() count times, stopping if you reach a node with no children.

This operation "opens a hole" in the current node and its count first descendants.

Declaration
public bool TryDown(int count)
Parameters
Type Name Description

Int32

count

Returns
Type Description

Boolean

True if the operation was successful, false if the cursor went Down() fewer than count times.

Exceptions
Type Condition

ArgumentOutOfRangeException

count was negative

TryDownWhile(Func<T, Boolean>)

Go Down() as long as predicate returns true for the current Focus, stopping if you reach the bottom. In other words, find the first leftmost descendant of Focus (including itself) which does not satisfy predicate.

Declaration
public bool TryDownWhile(Func<T, bool> predicate)
Parameters
Type Name Description

Func<T, Boolean>

predicate

The predicate to invoke on the current focus and its leftmost descendants

Returns
Type Description

Boolean

True if a leftmost descendant not satisfying predicate was found, false if the Cursor<T> reached the bottom.

TryFollow(IEnumerable<Direction>)

Follow a path.

Declaration
public bool TryFollow(IEnumerable<Direction> path)
Parameters
Type Name Description

IEnumerable<Direction>

path

The path to follow

Returns
Type Description

Boolean

True if the path was successfully followed in full, false if the path led off the edge of the tree.

TryLeft()

Try to focus the Cursor<T> on the current Focus's immediate predecessor sibling.

Declaration
public bool TryLeft()
Returns
Type Description

Boolean

True if the operation was successful, false if the Cursor<T> is already focused on the leftmost sibling

TryLeft(Int32)

Go Left() count times, stopping if you reach the leftmost sibling.

Declaration
public bool TryLeft(int count)
Parameters
Type Name Description

Int32

count

Returns
Type Description

Boolean

True if the operation was successful, false if the cursor went Left() fewer than count times.

Exceptions
Type Condition

ArgumentOutOfRangeException

count was negative

TryLeftWhile(Func<T, Boolean>)

Go Left() as long as predicate returns true for the current Focus, stopping if you reach the leftmost sibling. In other words, find the left sibling of Focus (including itself) which does not satisfy predicate.

Declaration
public bool TryLeftWhile(Func<T, bool> predicate)
Parameters
Type Name Description

Func<T, Boolean>

predicate

The predicate to invoke on the current focus and its ancestors

Returns
Type Description

Boolean

True if an ancestor not satisfying predicate was found, false if the Cursor<T> reached the leftmost sibling.

TryMove(Direction)

Try to move in a given Direction

Declaration
public bool TryMove(Direction direction)
Parameters
Type Name Description

Direction

direction

The Direction to move in

Returns
Type Description

Boolean

True if the operation was successful, false if the direction leads off the edge of the tree.

Exceptions
Type Condition

ArgumentOutOfRangeException

Thrown when direction is not a valid Direction

TryRight()

Try to focus the Cursor<T> on the current Focus's immediate successor sibling.

Declaration
public bool TryRight()
Returns
Type Description

Boolean

True if the operation was successful, false if the Cursor<T> is already focused on the rightmost sibling

TryRight(Int32)

Go Right() count times, stopping if you reach the rightmost sibling.

Declaration
public bool TryRight(int count)
Parameters
Type Name Description

Int32

count

Returns
Type Description

Boolean

True if the operation was successful, false if the cursor went Right() fewer than count times.

Exceptions
Type Condition

ArgumentOutOfRangeException

count was negative

TryRightWhile(Func<T, Boolean>)

Go Right() as long as predicate returns true for the current Focus, stopping if you reach the Rightmost sibling. In other words, find the Right sibling of Focus (including itself) which does not satisfy predicate.

Declaration
public bool TryRightWhile(Func<T, bool> predicate)
Parameters
Type Name Description

Func<T, Boolean>

predicate

The predicate to invoke on the current focus and its ancestors

Returns
Type Description

Boolean

True if an ancestor not satisfying predicate was found, false if the Cursor<T> reached the Rightmost sibling.

TryUp()

Try to focus the Cursor<T> on the current Focus's parent.

This operation "plugs the hole" in the parent, replacing the parent's children as necessary. This releases old versions of the current Focus and its children, so that they can be garbage collected.

Declaration
public bool TryUp()
Returns
Type Description

Boolean

True if the operation was successful, false if the Cursor<T> is already focused on the root node

TryUp(Int32)

Go Up() count times, stopping if you reach the top.

This operation "plugs the hole" in the parent, replacing the parent's children as necessary. This releases old versions of the ancestors and their children, so that they can be garbage collected.

Declaration
public bool TryUp(int count)
Parameters
Type Name Description

Int32

count

Returns
Type Description

Boolean

True if the operation was successful, false if the cursor went Up() fewer than count times.

Exceptions
Type Condition

ArgumentOutOfRangeException

count was negative

TryUpWhile(Func<T, Boolean>)

Go Up() as long as predicate returns true for the current Focus, stopping if you reach the top. In other words, find the first ancestor of Focus (including itself) which does not satisfy predicate.

This operation "plugs the hole" in the ancestors, replacing their children as necessary. This releases old versions of the ancestors and their children, so that they can be garbage collected.

Declaration
public bool TryUpWhile(Func<T, bool> predicate)
Parameters
Type Name Description

Func<T, Boolean>

predicate

The predicate to invoke on the current focus and its ancestors

Returns
Type Description

Boolean

True if an ancestor not satisfying predicate was found, false if the Cursor<T> reached the top.

Up()

Focus the Cursor<T> on the current Focus's parent.

Going Up() "plugs the hole" in the parent, replacing the parent's children as necessary. This releases old versions of the current Focus and its children so that they can be garbage collected.

Declaration
public void Up()
Exceptions
Type Condition

InvalidOperationException

The Cursor<T> is already focused on the root node.

Up(Int32)

Go Up() count times.

Going Up(Int32) "plugs the hole" in the ancestors, replacing their children as necessary. This releases old versions of the ancestors and their children, so that they can be garbage collected.

Declaration
public void Up(int count)
Parameters
Type Name Description

Int32

count

Exceptions
Type Condition

InvalidOperationException

The Cursor<T> reached the root node. The Cursor<T> is left in the last good state, that is, at the top of the tree.

ArgumentOutOfRangeException

count was negative

UpWhile(Func<T, Boolean>)

Go Up() as long as predicate returns true for the current Focus. In other words, find the first ancestor of Focus (including itself) which does not satisfy predicate.

This operation "plugs the hole" in the ancestors, replacing their children as necessary. This releases old versions of the ancestors and their children, so that they can be garbage collected.

Declaration
public void UpWhile(Func<T, bool> predicate)
Parameters
Type Name Description

Func<T, Boolean>

predicate

The predicate to invoke on the current focus and its ancestors

Exceptions
Type Condition

InvalidOperationException

The Cursor<T> reached the root node. The Cursor<T> is left in the last good state, that is, at the top of the tree.