5
// Mike KrĆ¼ger <mkrueger@novell.com>
7
// Copyright (c) 2009 Novell, Inc (http://www.novell.com)
9
// Permission is hereby granted, free of charge, to any person obtaining a copy
10
// of this software and associated documentation files (the "Software"), to deal
11
// in the Software without restriction, including without limitation the rights
12
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13
// copies of the Software, and to permit persons to whom the Software is
14
// furnished to do so, subject to the following conditions:
16
// The above copyright notice and this permission notice shall be included in
17
// all copies or substantial portions of the Software.
19
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
27
using System.Collections;
28
using System.Collections.Generic;
29
using System.Diagnostics;
32
using System.Threading;
34
namespace ICSharpCode.NRefactory.CSharp
36
public abstract class AstNode : AbstractAnnotatable, ICSharpCode.NRefactory.TypeSystem.IFreezable, PatternMatching.INode
38
// the Root role must be available when creating the null nodes, so we can't put it in the Roles class
39
internal static readonly Role<AstNode> RootRole = new Role<AstNode> ("Root");
42
public static readonly AstNode Null = new NullAstNode ();
44
sealed class NullAstNode : AstNode
46
public override NodeType NodeType {
48
return NodeType.Unknown;
52
public override bool IsNull {
58
public override void AcceptVisitor (IAstVisitor visitor)
62
public override T AcceptVisitor<T> (IAstVisitor<T> visitor)
67
public override S AcceptVisitor<T, S> (IAstVisitor<T, S> visitor, T data)
72
protected internal override bool DoMatch (AstNode other, PatternMatching.Match match)
74
return other == null || other.IsNull;
79
#region PatternPlaceholder
80
public static implicit operator AstNode (PatternMatching.Pattern pattern)
82
return pattern != null ? new PatternPlaceholder (pattern) : null;
85
sealed class PatternPlaceholder : AstNode, PatternMatching.INode
87
readonly PatternMatching.Pattern child;
89
public PatternPlaceholder (PatternMatching.Pattern child)
94
public override NodeType NodeType {
95
get { return NodeType.Pattern; }
98
public override void AcceptVisitor (IAstVisitor visitor)
100
visitor.VisitPatternPlaceholder (this, child);
103
public override T AcceptVisitor<T> (IAstVisitor<T> visitor)
105
return visitor.VisitPatternPlaceholder (this, child);
108
public override S AcceptVisitor<T, S> (IAstVisitor<T, S> visitor, T data)
110
return visitor.VisitPatternPlaceholder (this, child, data);
113
protected internal override bool DoMatch (AstNode other, PatternMatching.Match match)
115
return child.DoMatch (other, match);
118
bool PatternMatching.INode.DoMatchCollection (Role role, PatternMatching.INode pos, PatternMatching.Match match, PatternMatching.BacktrackingInfo backtrackingInfo)
120
return child.DoMatchCollection (role, pos, match, backtrackingInfo);
131
// Flags, from least significant to most significant bits:
132
// - Role.RoleIndexBits: role index
134
protected uint flags = RootRole.Index;
135
// Derived classes may also use a few bits,
136
// for example Identifier uses 1 bit for IsVerbatim
138
const uint roleIndexMask = (1u << Role.RoleIndexBits) - 1;
139
const uint frozenBit = 1u << Role.RoleIndexBits;
140
protected const int AstNodeFlagsUsedBits = Role.RoleIndexBits + 1;
148
public bool IsFrozen {
149
get { return (flags & frozenBit) != 0; }
155
for (AstNode child = firstChild; child != null; child = child.nextSibling)
161
protected void ThrowIfFrozen()
164
throw new InvalidOperationException("Cannot mutate frozen " + GetType().Name);
167
public abstract NodeType NodeType {
171
public virtual bool IsNull {
177
public virtual TextLocation StartLocation {
179
var child = firstChild;
181
return TextLocation.Empty;
182
return child.StartLocation;
186
public virtual TextLocation EndLocation {
188
var child = lastChild;
190
return TextLocation.Empty;
191
return child.EndLocation;
196
/// Gets the region from StartLocation to EndLocation for this node.
197
/// The file name of the region is set based on the parent CompilationUnit's file name.
198
/// If this node is not connected to a whole compilation, the file name will be null.
200
public ICSharpCode.NRefactory.TypeSystem.DomRegion GetRegion()
202
var cu = (this.Ancestors.LastOrDefault() ?? this) as CompilationUnit;
203
string fileName = (cu != null ? cu.FileName : null);
204
return new ICSharpCode.NRefactory.TypeSystem.DomRegion(fileName, this.StartLocation, this.EndLocation);
207
public AstNode Parent {
208
get { return parent; }
213
return Role.GetByIndex(flags & roleIndexMask);
217
throw new ArgumentNullException("value");
218
if (!value.IsValid(this))
219
throw new ArgumentException("This node is not valid in the new role.");
225
void SetRole(Role role)
227
flags = (flags & ~roleIndexMask) | role.Index;
230
public AstNode NextSibling {
231
get { return nextSibling; }
234
public AstNode PrevSibling {
235
get { return prevSibling; }
238
public AstNode FirstChild {
239
get { return firstChild; }
242
public AstNode LastChild {
243
get { return lastChild; }
246
public bool HasChildren {
248
return firstChild != null;
252
public IEnumerable<AstNode> Children {
255
for (AstNode cur = firstChild; cur != null; cur = next) {
256
Debug.Assert (cur.parent == this);
257
// Remember next before yielding cur.
258
// This allows removing/replacing nodes while iterating through the list.
259
next = cur.nextSibling;
266
/// Gets the ancestors of this node (excluding this node itself)
268
public IEnumerable<AstNode> Ancestors {
270
for (AstNode cur = parent; cur != null; cur = cur.parent) {
277
/// Gets the ancestors of this node (including this node itself)
279
public IEnumerable<AstNode> AncestorsAndSelf {
281
for (AstNode cur = this; cur != null; cur = cur.parent) {
288
/// Gets all descendants of this node (excluding this node itself).
290
public IEnumerable<AstNode> Descendants {
292
return Utils.TreeTraversal.PreOrder (this.Children, n => n.Children);
297
/// Gets all descendants of this node (including this node itself).
299
public IEnumerable<AstNode> DescendantsAndSelf {
301
return Utils.TreeTraversal.PreOrder (this, n => n.Children);
306
/// Gets the first child with the specified role.
307
/// Returns the role's null object if the child is not found.
309
public T GetChildByRole<T>(Role<T> role) where T : AstNode
312
throw new ArgumentNullException ("role");
313
uint roleIndex = role.Index;
314
for (var cur = firstChild; cur != null; cur = cur.nextSibling) {
315
if ((cur.flags & roleIndexMask) == roleIndex)
318
return role.NullObject;
321
public T GetParent<T>() where T : AstNode
323
return Ancestors.OfType<T>().FirstOrDefault();
326
public AstNodeCollection<T> GetChildrenByRole<T> (Role<T> role) where T : AstNode
328
return new AstNodeCollection<T> (this, role);
331
protected void SetChildByRole<T> (Role<T> role, T newChild) where T : AstNode
333
AstNode oldChild = GetChildByRole (role);
335
AddChild (newChild, role);
337
oldChild.ReplaceWith (newChild);
340
public void AddChild<T> (T child, Role<T> role) where T : AstNode
343
throw new ArgumentNullException ("role");
344
if (child == null || child.IsNull)
347
if (child.parent != null)
348
throw new ArgumentException ("Node is already used in another tree.", "child");
350
throw new ArgumentException ("Cannot add a frozen node.", "child");
351
AddChildUnsafe (child, role);
355
/// Adds a child without performing any safety checks.
357
void AddChildUnsafe (AstNode child, Role role)
361
if (firstChild == null) {
362
lastChild = firstChild = child;
364
lastChild.nextSibling = child;
365
child.prevSibling = lastChild;
370
public void InsertChildsBefore<T>(AstNode nextSibling, Role<T> role, params T[] child) where T : AstNode
372
foreach (var cur in child) {
373
InsertChildBefore(nextSibling, cur, role);
377
public void InsertChildBefore<T> (AstNode nextSibling, T child, Role<T> role) where T : AstNode
380
throw new ArgumentNullException ("role");
381
if (nextSibling == null || nextSibling.IsNull) {
382
AddChild (child, role);
386
if (child == null || child.IsNull)
389
if (child.parent != null)
390
throw new ArgumentException ("Node is already used in another tree.", "child");
392
throw new ArgumentException ("Cannot add a frozen node.", "child");
393
if (nextSibling.parent != this)
394
throw new ArgumentException ("NextSibling is not a child of this node.", "nextSibling");
395
// No need to test for "Cannot add children to null nodes",
396
// as there isn't any valid nextSibling in null nodes.
397
InsertChildBeforeUnsafe (nextSibling, child, role);
400
void InsertChildBeforeUnsafe (AstNode nextSibling, AstNode child, Role role)
404
child.nextSibling = nextSibling;
405
child.prevSibling = nextSibling.prevSibling;
407
if (nextSibling.prevSibling != null) {
408
Debug.Assert (nextSibling.prevSibling.nextSibling == nextSibling);
409
nextSibling.prevSibling.nextSibling = child;
411
Debug.Assert (firstChild == nextSibling);
414
nextSibling.prevSibling = child;
417
public void InsertChildAfter<T> (AstNode prevSibling, T child, Role<T> role) where T : AstNode
419
InsertChildBefore ((prevSibling == null || prevSibling.IsNull) ? firstChild : prevSibling.nextSibling, child, role);
423
/// Removes this node from its parent.
425
public void Remove ()
427
if (parent != null) {
429
if (prevSibling != null) {
430
Debug.Assert (prevSibling.nextSibling == this);
431
prevSibling.nextSibling = nextSibling;
433
Debug.Assert (parent.firstChild == this);
434
parent.firstChild = nextSibling;
436
if (nextSibling != null) {
437
Debug.Assert (nextSibling.prevSibling == this);
438
nextSibling.prevSibling = prevSibling;
440
Debug.Assert (parent.lastChild == this);
441
parent.lastChild = prevSibling;
450
/// Replaces this node with the new node.
452
public void ReplaceWith (AstNode newNode)
454
if (newNode == null || newNode.IsNull) {
459
return; // nothing to do...
460
if (parent == null) {
461
throw new InvalidOperationException (this.IsNull ? "Cannot replace the null nodes" : "Cannot replace the root node");
464
// Because this method doesn't statically check the new node's type with the role,
465
// we perform a runtime test:
466
if (!this.Role.IsValid (newNode)) {
467
throw new ArgumentException (string.Format ("The new node '{0}' is not valid in the role {1}", newNode.GetType ().Name, this.Role.ToString ()), "newNode");
469
if (newNode.parent != null) {
470
// newNode is used within this tree?
471
if (newNode.Ancestors.Contains (this)) {
472
// e.g. "parenthesizedExpr.ReplaceWith(parenthesizedExpr.Expression);"
473
// enable automatic removal
476
throw new ArgumentException ("Node is already used in another tree.", "newNode");
479
if (newNode.IsFrozen)
480
throw new ArgumentException ("Cannot add a frozen node.", "newNode");
482
newNode.parent = parent;
483
newNode.SetRole(this.Role);
484
newNode.prevSibling = prevSibling;
485
newNode.nextSibling = nextSibling;
487
if (prevSibling != null) {
488
Debug.Assert (prevSibling.nextSibling == this);
489
prevSibling.nextSibling = newNode;
491
Debug.Assert (parent.firstChild == this);
492
parent.firstChild = newNode;
494
if (nextSibling != null) {
495
Debug.Assert (nextSibling.prevSibling == this);
496
nextSibling.prevSibling = newNode;
498
Debug.Assert (parent.lastChild == this);
499
parent.lastChild = newNode;
506
public AstNode ReplaceWith (Func<AstNode, AstNode> replaceFunction)
508
if (replaceFunction == null)
509
throw new ArgumentNullException ("replaceFunction");
510
if (parent == null) {
511
throw new InvalidOperationException (this.IsNull ? "Cannot replace the null nodes" : "Cannot replace the root node");
513
AstNode oldParent = parent;
514
AstNode oldSuccessor = nextSibling;
515
Role oldRole = this.Role;
517
AstNode replacement = replaceFunction (this);
518
if (oldSuccessor != null && oldSuccessor.parent != oldParent)
519
throw new InvalidOperationException ("replace function changed nextSibling of node being replaced?");
520
if (!(replacement == null || replacement.IsNull)) {
521
if (replacement.parent != null)
522
throw new InvalidOperationException ("replace function must return the root of a tree");
523
if (!oldRole.IsValid (replacement)) {
524
throw new InvalidOperationException (string.Format ("The new node '{0}' is not valid in the role {1}", replacement.GetType ().Name, oldRole.ToString ()));
527
if (oldSuccessor != null)
528
oldParent.InsertChildBeforeUnsafe (oldSuccessor, replacement, oldRole);
530
oldParent.AddChildUnsafe (replacement, oldRole);
536
/// Clones the whole subtree starting at this AST node.
538
/// <remarks>Annotations are copied over to the new nodes; and any annotations implementing ICloneable will be cloned.</remarks>
539
public AstNode Clone ()
541
AstNode copy = (AstNode)MemberwiseClone ();
542
// First, reset the shallow pointer copies
544
copy.firstChild = null;
545
copy.lastChild = null;
546
copy.prevSibling = null;
547
copy.nextSibling = null;
548
copy.flags &= ~frozenBit; // unfreeze the copy
550
// Then perform a deep copy:
551
for (AstNode cur = firstChild; cur != null; cur = cur.nextSibling) {
552
copy.AddChildUnsafe (cur.Clone (), cur.Role);
555
// Finally, clone the annotation, if necessary
556
copy.CloneAnnotations();
561
public abstract void AcceptVisitor (IAstVisitor visitor);
563
public abstract T AcceptVisitor<T> (IAstVisitor<T> visitor);
565
public abstract S AcceptVisitor<T, S> (IAstVisitor<T, S> visitor, T data);
567
#region Pattern Matching
568
protected static bool MatchString (string pattern, string text)
570
return PatternMatching.Pattern.MatchString(pattern, text);
573
protected internal abstract bool DoMatch (AstNode other, PatternMatching.Match match);
575
bool PatternMatching.INode.DoMatch (PatternMatching.INode other, PatternMatching.Match match)
577
AstNode o = other as AstNode;
578
// try matching if other is null, or if other is an AstNode
579
return (other == null || o != null) && DoMatch (o, match);
582
bool PatternMatching.INode.DoMatchCollection (Role role, PatternMatching.INode pos, PatternMatching.Match match, PatternMatching.BacktrackingInfo backtrackingInfo)
584
AstNode o = pos as AstNode;
585
return (pos == null || o != null) && DoMatch (o, match);
588
PatternMatching.INode PatternMatching.INode.NextSibling {
589
get { return nextSibling; }
592
PatternMatching.INode PatternMatching.INode.FirstChild {
593
get { return firstChild; }
598
public AstNode GetNextNode ()
600
if (NextSibling != null)
603
return Parent.GetNextNode ();
607
public AstNode GetPrevNode ()
609
if (PrevSibling != null)
612
return Parent.GetPrevNode ();
615
// filters all non c# nodes (comments, white spaces or pre processor directives)
616
public AstNode GetCSharpNodeBefore (AstNode node)
618
var n = node.PrevSibling;
620
if (n.Role != Roles.Comment)
622
n = n.GetPrevNode ();
629
/// Gets the node specified by T at the location line, column. This is useful for getting a specific node from the tree. For example searching
630
/// the current method declaration.
633
public AstNode GetNodeAt (int line, int column, Predicate<AstNode> pred = null)
635
return GetNodeAt (new TextLocation (line, column), pred);
639
/// Gets the node specified by pred at location. This is useful for getting a specific node from the tree. For example searching
640
/// the current method declaration.
643
public AstNode GetNodeAt (TextLocation location, Predicate<AstNode> pred = null)
645
AstNode result = null;
647
while (node.FirstChild != null) {
648
var child = node.FirstChild;
649
while (child != null) {
650
if (child.StartLocation <= location && location < child.EndLocation) {
651
if (pred == null || pred (child))
656
child = child.NextSibling;
658
// found no better child node - therefore the parent is the right one.
666
/// Gets the node specified by T at the location line, column. This is useful for getting a specific node from the tree. For example searching
667
/// the current method declaration.
670
public T GetNodeAt<T> (int line, int column) where T : AstNode
672
return GetNodeAt<T> (new TextLocation (line, column));
676
/// Gets the node specified by T at location. This is useful for getting a specific node from the tree. For example searching
677
/// the current method declaration.
680
public T GetNodeAt<T> (TextLocation location) where T : AstNode
684
while (node.FirstChild != null) {
685
var child = node.FirstChild;
686
while (child != null) {
687
if (child.StartLocation <= location && location < child.EndLocation) {
693
child = child.NextSibling;
695
// found no better child node - therefore the parent is the right one.
704
#region GetAdjacentNodeAt
706
/// Gets the node specified by pred at the location line, column. This is useful for getting a specific node from the tree. For example searching
707
/// the current method declaration.
710
public AstNode GetAdjacentNodeAt(int line, int column, Predicate<AstNode> pred = null)
712
return GetAdjacentNodeAt (new TextLocation (line, column), pred);
716
/// Gets the node specified by pred at location. This is useful for getting a specific node from the tree. For example searching
717
/// the current method declaration.
720
public AstNode GetAdjacentNodeAt (TextLocation location, Predicate<AstNode> pred = null)
722
AstNode result = null;
724
while (node.FirstChild != null) {
725
var child = node.FirstChild;
726
while (child != null) {
727
if (child.StartLocation <= location && location <= child.EndLocation) {
728
if (pred == null || pred (child))
733
child = child.NextSibling;
735
// found no better child node - therefore the parent is the right one.
743
/// Gets the node specified by T at the location line, column. This is useful for getting a specific node from the tree. For example searching
744
/// the current method declaration.
747
public T GetAdjacentNodeAt<T>(int line, int column) where T : AstNode
749
return GetAdjacentNodeAt<T> (new TextLocation (line, column));
753
/// Gets the node specified by T at location. This is useful for getting a specific node from the tree. For example searching
754
/// the current method declaration.
757
public T GetAdjacentNodeAt<T> (TextLocation location) where T : AstNode
761
while (node.FirstChild != null) {
762
var child = node.FirstChild;
763
while (child != null) {
764
if (child.StartLocation <= location && location < child.EndLocation) {
770
child = child.NextSibling;
772
// found no better child node - therefore the parent is the right one.
782
/// Gets the node that fully contains the range from startLocation to endLocation.
784
public AstNode GetNodeContaining(TextLocation startLocation, TextLocation endLocation)
786
for (AstNode child = firstChild; child != null; child = child.nextSibling) {
787
if (child.StartLocation <= startLocation && endLocation <= child.EndLocation)
788
return child.GetNodeContaining(startLocation, endLocation);
793
public IEnumerable<AstNode> GetNodesBetween (int startLine, int startColumn, int endLine, int endColumn)
795
return GetNodesBetween (new TextLocation (startLine, startColumn), new TextLocation (endLine, endColumn));
798
public IEnumerable<AstNode> GetNodesBetween (TextLocation start, TextLocation end)
801
while (node != null) {
803
if (start <= node.StartLocation && node.EndLocation <= end) {
804
// Remember next before yielding node.
805
// This allows iteration to continue when the caller removes/replaces the node.
806
next = node.NextSibling;
809
if (node.EndLocation <= start) {
810
next = node.NextSibling;
812
next = node.FirstChild;
816
if (next != null && next.StartLocation > end)
823
/// Gets the node as formatted C# output.
825
/// <param name='formattingOptions'>
826
/// Formatting options.
828
public virtual string GetText (CSharpFormattingOptions formattingOptions = null)
832
var w = new StringWriter ();
833
AcceptVisitor (new CSharpOutputVisitor (w, formattingOptions ?? FormattingOptionsFactory.CreateMono ()));
834
return w.ToString ();
838
/// Returns true, if the given coordinates (line, column) are in the node.
841
/// True, if the given coordinates are between StartLocation and EndLocation (exclusive); otherwise, false.
843
public bool Contains (int line, int column)
845
return Contains (new TextLocation (line, column));
849
/// Returns true, if the given coordinates are in the node.
852
/// True, if location is between StartLocation and EndLocation (exclusive); otherwise, false.
854
public bool Contains (TextLocation location)
856
return this.StartLocation <= location && location < this.EndLocation;
860
/// Returns true, if the given coordinates (line, column) are in the node.
863
/// True, if the given coordinates are between StartLocation and EndLocation (inclusive); otherwise, false.
865
public bool IsInside (int line, int column)
867
return IsInside (new TextLocation (line, column));
871
/// Returns true, if the given coordinates are in the node.
874
/// True, if location is between StartLocation and EndLocation (inclusive); otherwise, false.
876
public bool IsInside (TextLocation location)
878
return this.StartLocation <= location && location <= this.EndLocation;
881
public override void AddAnnotation (object annotation)
884
throw new InvalidOperationException ("Cannot add annotations to the null node");
885
base.AddAnnotation (annotation);
888
internal string DebugToString()
892
string text = GetText();
893
text = text.TrimEnd().Replace("\t", "").Replace(Environment.NewLine, " ");
894
if (text.Length > 100)
895
return text.Substring(0, 97) + "...";