← Back to branch summary

~ubuntu-branches/ubuntu/trusty/monodevelop/trusty-proposed

« back to all changes in this revision

Viewing changes to contrib/ICSharpCode.NRefactory.CSharp/Analysis/DefiniteAssignmentAnalysis.cs

  • Committer: Package Import Robot
  • Author(s): Jo Shields
  • Date: 2013-05-12 09:46:03 UTC
  • mto: This revision was merged to the branch mainline in revision 29.
  • Revision ID: package-import@ubuntu.com-20130512094603-mad323bzcxvmcam0
Tags: upstream-4.0.5+dfsg
Import upstream version 4.0.5+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/ICSharpCode.NRefactory.CSharp/Analysis/DefiniteAssignmentAnalysis.cs
1
 
// Copyright (c) AlphaSierraPapa for the SharpDevelop Team
2
 
// 
3
 
// Permission is hereby granted, free of charge, to any person obtaining a copy of this
4
 
// software and associated documentation files (the "Software"), to deal in the Software
5
 
// without restriction, including without limitation the rights to use, copy, modify, merge,
6
 
// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
7
 
// to whom the Software is furnished to do so, subject to the following conditions:
8
 
// 
9
 
// The above copyright notice and this permission notice shall be included in all copies or
10
 
// substantial portions of the Software.
11
 
// 
12
 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
13
 
// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
14
 
// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
15
 
// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
16
 
// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
17
 
// DEALINGS IN THE SOFTWARE.
18
 
 
19
 
using System;
20
 
using System.Collections.Generic;
21
 
using System.Diagnostics;
22
 
using System.Linq;
23
 
using System.Threading;
24
 
 
25
 
using ICSharpCode.NRefactory.CSharp.Resolver;
26
 
using ICSharpCode.NRefactory.Semantics;
27
 
using ICSharpCode.NRefactory.TypeSystem;
28
 
using ICSharpCode.NRefactory.TypeSystem.Implementation;
29
 
using ICSharpCode.NRefactory.Utils;
30
 
 
31
 
namespace ICSharpCode.NRefactory.CSharp.Analysis
32
 
{
33
 
        /// <summary>
34
 
        /// Represents the definite assignment status of a variable at a specific location.
35
 
        /// </summary>
36
 
        public enum DefiniteAssignmentStatus
37
 
        {
38
 
                /// <summary>
39
 
                /// The variable might be assigned or unassigned.
40
 
                /// </summary>
41
 
                PotentiallyAssigned,
42
 
                /// <summary>
43
 
                /// The variable is definitely assigned.
44
 
                /// </summary>
45
 
                DefinitelyAssigned,
46
 
                /// <summary>
47
 
                /// The variable is definitely assigned iff the expression results in the value 'true'.
48
 
                /// </summary>
49
 
                AssignedAfterTrueExpression,
50
 
                /// <summary>
51
 
                /// The variable is definitely assigned iff the expression results in the value 'false'.
52
 
                /// </summary>
53
 
                AssignedAfterFalseExpression,
54
 
                /// <summary>
55
 
                /// The code is unreachable.
56
 
                /// </summary>
57
 
                CodeUnreachable
58
 
        }
59
 
        
60
 
        /// <summary>
61
 
        /// Implements the C# definite assignment analysis (C# 4.0 Spec: §5.3 Definite assignment)
62
 
        /// </summary>
63
 
        public class DefiniteAssignmentAnalysis
64
 
        {
65
 
                sealed class DefiniteAssignmentNode : ControlFlowNode
66
 
                {
67
 
                        public int Index;
68
 
                        public DefiniteAssignmentStatus NodeStatus;
69
 
                        
70
 
                        public DefiniteAssignmentNode(Statement previousStatement, Statement nextStatement, ControlFlowNodeType type)
71
 
                                : base(previousStatement, nextStatement, type)
72
 
                        {
73
 
                        }
74
 
                }
75
 
                
76
 
                sealed class DerivedControlFlowGraphBuilder : ControlFlowGraphBuilder
77
 
                {
78
 
                        protected override ControlFlowNode CreateNode(Statement previousStatement, Statement nextStatement, ControlFlowNodeType type)
79
 
                        {
80
 
                                return new DefiniteAssignmentNode(previousStatement, nextStatement, type);
81
 
                        }
82
 
                }
83
 
                
84
 
                readonly DefiniteAssignmentVisitor visitor = new DefiniteAssignmentVisitor();
85
 
                readonly List<DefiniteAssignmentNode> allNodes = new List<DefiniteAssignmentNode>();
86
 
                readonly Dictionary<Statement, DefiniteAssignmentNode> beginNodeDict = new Dictionary<Statement, DefiniteAssignmentNode>();
87
 
                readonly Dictionary<Statement, DefiniteAssignmentNode> endNodeDict = new Dictionary<Statement, DefiniteAssignmentNode>();
88
 
                readonly Dictionary<Statement, DefiniteAssignmentNode> conditionNodeDict = new Dictionary<Statement, DefiniteAssignmentNode>();
89
 
                readonly CSharpAstResolver resolver;
90
 
                Dictionary<ControlFlowEdge, DefiniteAssignmentStatus> edgeStatus = new Dictionary<ControlFlowEdge, DefiniteAssignmentStatus>();
91
 
                
92
 
                string variableName;
93
 
                List<IdentifierExpression> unassignedVariableUses = new List<IdentifierExpression>();
94
 
                int analyzedRangeStart, analyzedRangeEnd;
95
 
                CancellationToken analysisCancellationToken;
96
 
                
97
 
                Queue<DefiniteAssignmentNode> nodesWithModifiedInput = new Queue<DefiniteAssignmentNode>();
98
 
                
99
 
                public DefiniteAssignmentAnalysis(Statement rootStatement, CancellationToken cancellationToken)
100
 
                        : this(rootStatement,
101
 
                               new CSharpAstResolver(new CSharpResolver(MinimalCorlib.Instance.CreateCompilation()), rootStatement),
102
 
                               cancellationToken)
103
 
                {
104
 
                }
105
 
                
106
 
                public DefiniteAssignmentAnalysis(Statement rootStatement, CSharpAstResolver resolver, CancellationToken cancellationToken)
107
 
                {
108
 
                        if (rootStatement == null)
109
 
                                throw new ArgumentNullException("rootStatement");
110
 
                        if (resolver == null)
111
 
                                throw new ArgumentNullException("resolver");
112
 
                        this.resolver = resolver;
113
 
                        
114
 
                        visitor.analysis = this;
115
 
                        DerivedControlFlowGraphBuilder cfgBuilder = new DerivedControlFlowGraphBuilder();
116
 
                        if (resolver.TypeResolveContext.Compilation.MainAssembly.UnresolvedAssembly is MinimalCorlib) {
117
 
                                cfgBuilder.EvaluateOnlyPrimitiveConstants = true;
118
 
                        }
119
 
                        allNodes.AddRange(cfgBuilder.BuildControlFlowGraph(rootStatement, resolver, cancellationToken).Cast<DefiniteAssignmentNode>());
120
 
                        for (int i = 0; i < allNodes.Count; i++) {
121
 
                                DefiniteAssignmentNode node = allNodes[i];
122
 
                                node.Index = i; // assign numbers to the nodes
123
 
                                if (node.Type == ControlFlowNodeType.StartNode || node.Type == ControlFlowNodeType.BetweenStatements) {
124
 
                                        // Anonymous methods have separate control flow graphs, but we also need to analyze those.
125
 
                                        // Iterate backwards so that anonymous methods are inserted in the correct order
126
 
                                        for (AstNode child = node.NextStatement.LastChild; child != null; child = child.PrevSibling) {
127
 
                                                InsertAnonymousMethods(i + 1, child, cfgBuilder, cancellationToken);
128
 
                                        }
129
 
                                }
130
 
                                // Now register the node in the dictionaries:
131
 
                                if (node.Type == ControlFlowNodeType.StartNode || node.Type == ControlFlowNodeType.BetweenStatements)
132
 
                                        beginNodeDict.Add(node.NextStatement, node);
133
 
                                if (node.Type == ControlFlowNodeType.BetweenStatements || node.Type == ControlFlowNodeType.EndNode)
134
 
                                        endNodeDict.Add(node.PreviousStatement, node);
135
 
                                if (node.Type == ControlFlowNodeType.LoopCondition)
136
 
                                        conditionNodeDict.Add(node.NextStatement, node);
137
 
                        }
138
 
                        // Verify that we created nodes for all statements:
139
 
                        Debug.Assert(!rootStatement.DescendantsAndSelf.OfType<Statement>().Except(allNodes.Select(n => n.NextStatement)).Any());
140
 
                        // Verify that we put all nodes into the dictionaries:
141
 
                        Debug.Assert(rootStatement.DescendantsAndSelf.OfType<Statement>().All(stmt => beginNodeDict.ContainsKey(stmt)));
142
 
                        Debug.Assert(rootStatement.DescendantsAndSelf.OfType<Statement>().All(stmt => endNodeDict.ContainsKey(stmt)));
143
 
                        
144
 
                        this.analyzedRangeStart = 0;
145
 
                        this.analyzedRangeEnd = allNodes.Count - 1;
146
 
                }
147
 
                
148
 
                void InsertAnonymousMethods(int insertPos, AstNode node, ControlFlowGraphBuilder cfgBuilder, CancellationToken cancellationToken)
149
 
                {
150
 
                        // Ignore any statements, as those have their own ControlFlowNode and get handled separately
151
 
                        if (node is Statement)
152
 
                                return;
153
 
                        AnonymousMethodExpression ame = node as AnonymousMethodExpression;
154
 
                        if (ame != null) {
155
 
                                allNodes.InsertRange(insertPos, cfgBuilder.BuildControlFlowGraph(ame.Body, resolver, cancellationToken).Cast<DefiniteAssignmentNode>());
156
 
                                return;
157
 
                        }
158
 
                        LambdaExpression lambda = node as LambdaExpression;
159
 
                        if (lambda != null && lambda.Body is Statement) {
160
 
                                allNodes.InsertRange(insertPos, cfgBuilder.BuildControlFlowGraph((Statement)lambda.Body, resolver, cancellationToken).Cast<DefiniteAssignmentNode>());
161
 
                                return;
162
 
                        }
163
 
                        // Descend into child expressions
164
 
                        // Iterate backwards so that anonymous methods are inserted in the correct order
165
 
                        for (AstNode child = node.LastChild; child != null; child = child.PrevSibling) {
166
 
                                InsertAnonymousMethods(insertPos, child, cfgBuilder, cancellationToken);
167
 
                        }
168
 
                }
169
 
                
170
 
                /// <summary>
171
 
                /// Gets the unassigned usages of the previously analyzed variable.
172
 
                /// </summary>
173
 
                public IList<IdentifierExpression> UnassignedVariableUses {
174
 
                        get {
175
 
                                return unassignedVariableUses.AsReadOnly();
176
 
                        }
177
 
                }
178
 
                
179
 
                /// <summary>
180
 
                /// Sets the range of statements to be analyzed.
181
 
                /// This method can be used to restrict the analysis to only a part of the method.
182
 
                /// Only the control flow paths that are fully contained within the selected part will be analyzed.
183
 
                /// </summary>
184
 
                /// <remarks>By default, both 'start' and 'end' are inclusive.</remarks>
185
 
                public void SetAnalyzedRange(Statement start, Statement end, bool startInclusive = true, bool endInclusive = true)
186
 
                {
187
 
                        var dictForStart = startInclusive ? beginNodeDict : endNodeDict;
188
 
                        var dictForEnd = endInclusive ? endNodeDict : beginNodeDict;
189
 
                        Debug.Assert(dictForStart.ContainsKey(start) && dictForEnd.ContainsKey(end));
190
 
                        int startIndex = dictForStart[start].Index;
191
 
                        int endIndex = dictForEnd[end].Index;
192
 
                        if (startIndex > endIndex)
193
 
                                throw new ArgumentException("The start statement must be lexically preceding the end statement");
194
 
                        this.analyzedRangeStart = startIndex;
195
 
                        this.analyzedRangeEnd = endIndex;
196
 
                }
197
 
                
198
 
                public void Analyze(string variable, DefiniteAssignmentStatus initialStatus = DefiniteAssignmentStatus.PotentiallyAssigned, CancellationToken cancellationToken = default(CancellationToken))
199
 
                {
200
 
                        this.analysisCancellationToken = cancellationToken;
201
 
                        this.variableName = variable;
202
 
                        try {
203
 
                                // Reset the status:
204
 
                                unassignedVariableUses.Clear();
205
 
                                foreach (DefiniteAssignmentNode node in allNodes) {
206
 
                                        node.NodeStatus = DefiniteAssignmentStatus.CodeUnreachable;
207
 
                                        foreach (ControlFlowEdge edge in node.Outgoing)
208
 
                                                edgeStatus[edge] = DefiniteAssignmentStatus.CodeUnreachable;
209
 
                                }
210
 
                                
211
 
                                ChangeNodeStatus(allNodes[analyzedRangeStart], initialStatus);
212
 
                                // Iterate as long as the input status of some nodes is changing:
213
 
                                while (nodesWithModifiedInput.Count > 0) {
214
 
                                        DefiniteAssignmentNode node = nodesWithModifiedInput.Dequeue();
215
 
                                        DefiniteAssignmentStatus inputStatus = DefiniteAssignmentStatus.CodeUnreachable;
216
 
                                        foreach (ControlFlowEdge edge in node.Incoming) {
217
 
                                                inputStatus = MergeStatus(inputStatus, edgeStatus[edge]);
218
 
                                        }
219
 
                                        ChangeNodeStatus(node, inputStatus);
220
 
                                }
221
 
                        } finally {
222
 
                                this.analysisCancellationToken = CancellationToken.None;
223
 
                                this.variableName = null;
224
 
                        }
225
 
                }
226
 
                
227
 
                public DefiniteAssignmentStatus GetStatusBefore(Statement statement)
228
 
                {
229
 
                        return beginNodeDict[statement].NodeStatus;
230
 
                }
231
 
                
232
 
                public DefiniteAssignmentStatus GetStatusAfter(Statement statement)
233
 
                {
234
 
                        return endNodeDict[statement].NodeStatus;
235
 
                }
236
 
                
237
 
                public DefiniteAssignmentStatus GetStatusBeforeLoopCondition(Statement statement)
238
 
                {
239
 
                        return conditionNodeDict[statement].NodeStatus;
240
 
                }
241
 
                
242
 
                /// <summary>
243
 
                /// Exports the CFG. This method is intended to help debugging issues related to definite assignment.
244
 
                /// </summary>
245
 
                public GraphVizGraph ExportGraph()
246
 
                {
247
 
                        GraphVizGraph g = new GraphVizGraph();
248
 
                        g.Title = "DefiniteAssignment - " + variableName;
249
 
                        for (int i = 0; i < allNodes.Count; i++) {
250
 
                                string name = "#" + i + " = " + allNodes[i].NodeStatus.ToString() + Environment.NewLine;
251
 
                                switch (allNodes[i].Type) {
252
 
                                        case ControlFlowNodeType.StartNode:
253
 
                                        case ControlFlowNodeType.BetweenStatements:
254
 
                                                name += allNodes[i].NextStatement.ToString();
255
 
                                                break;
256
 
                                        case ControlFlowNodeType.EndNode:
257
 
                                                name += "End of " + allNodes[i].PreviousStatement.ToString();
258
 
                                                break;
259
 
                                        case ControlFlowNodeType.LoopCondition:
260
 
                                                name += "Condition in " + allNodes[i].NextStatement.ToString();
261
 
                                                break;
262
 
                                        default:
263
 
                                                name += allNodes[i].Type.ToString();
264
 
                                                break;
265
 
                                }
266
 
                                g.AddNode(new GraphVizNode(i) { label = name });
267
 
                                foreach (ControlFlowEdge edge in allNodes[i].Outgoing) {
268
 
                                        GraphVizEdge ge = new GraphVizEdge(i, ((DefiniteAssignmentNode)edge.To).Index);
269
 
                                        if (edgeStatus.Count > 0)
270
 
                                                ge.label = edgeStatus[edge].ToString();
271
 
                                        if (edge.IsLeavingTryFinally)
272
 
                                                ge.style = "dashed";
273
 
                                        switch (edge.Type) {
274
 
                                                case ControlFlowEdgeType.ConditionTrue:
275
 
                                                        ge.color = "green";
276
 
                                                        break;
277
 
                                                case ControlFlowEdgeType.ConditionFalse:
278
 
                                                        ge.color = "red";
279
 
                                                        break;
280
 
                                                case ControlFlowEdgeType.Jump:
281
 
                                                        ge.color = "blue";
282
 
                                                        break;
283
 
                                        }
284
 
                                        g.AddEdge(ge);
285
 
                                }
286
 
                        }
287
 
                        return g;
288
 
                }
289
 
                
290
 
                static DefiniteAssignmentStatus MergeStatus(DefiniteAssignmentStatus a, DefiniteAssignmentStatus b)
291
 
                {
292
 
                        // The result will be DefinitelyAssigned if at least one incoming edge is DefinitelyAssigned and all others are unreachable.
293
 
                        // The result will be DefinitelyUnassigned if at least one incoming edge is DefinitelyUnassigned and all others are unreachable.
294
 
                        // The result will be Unreachable if all incoming edges are unreachable.
295
 
                        // Otherwise, the result will be PotentiallyAssigned.
296
 
                        
297
 
                        if (a == b)
298
 
                                return a;
299
 
                        else if (a == DefiniteAssignmentStatus.CodeUnreachable)
300
 
                                return b;
301
 
                        else if (b == DefiniteAssignmentStatus.CodeUnreachable)
302
 
                                return a;
303
 
                        else
304
 
                                return DefiniteAssignmentStatus.PotentiallyAssigned;
305
 
                }
306
 
                
307
 
                void ChangeNodeStatus (DefiniteAssignmentNode node, DefiniteAssignmentStatus inputStatus)
308
 
                {
309
 
                        if (node.NodeStatus == inputStatus)
310
 
                                return;
311
 
                        node.NodeStatus = inputStatus;
312
 
                        DefiniteAssignmentStatus outputStatus;
313
 
                        switch (node.Type) {
314
 
                        case ControlFlowNodeType.StartNode:
315
 
                        case ControlFlowNodeType.BetweenStatements:
316
 
                                if (node.NextStatement is IfElseStatement) {
317
 
                                        // Handle if-else as a condition node
318
 
                                                goto case ControlFlowNodeType.LoopCondition;
319
 
                                }
320
 
                                if (inputStatus == DefiniteAssignmentStatus.DefinitelyAssigned) {
321
 
                                        // There isn't any way to un-assign variables, so we don't have to check the expression
322
 
                                        // if the status already is definitely assigned.
323
 
                                        outputStatus = DefiniteAssignmentStatus.DefinitelyAssigned;
324
 
                                } else {
325
 
                                        outputStatus = CleanSpecialValues (node.NextStatement.AcceptVisitor (visitor, inputStatus));
326
 
                                }
327
 
                                break;
328
 
                        case ControlFlowNodeType.EndNode:
329
 
                                outputStatus = inputStatus;
330
 
                                if (node.PreviousStatement.Role == TryCatchStatement.FinallyBlockRole
331
 
                                        && (outputStatus == DefiniteAssignmentStatus.DefinitelyAssigned || outputStatus == DefiniteAssignmentStatus.PotentiallyAssigned)) {
332
 
                                        TryCatchStatement tryFinally = (TryCatchStatement)node.PreviousStatement.Parent;
333
 
                                        // Changing the status on a finally block potentially changes the status of all edges leaving that finally block:
334
 
                                        foreach (ControlFlowEdge edge in allNodes.SelectMany(n => n.Outgoing)) {
335
 
                                                if (edge.IsLeavingTryFinally && edge.TryFinallyStatements.Contains (tryFinally)) {
336
 
                                                        DefiniteAssignmentStatus s = edgeStatus [edge];
337
 
                                                        if (s == DefiniteAssignmentStatus.PotentiallyAssigned) {
338
 
                                                                ChangeEdgeStatus (edge, outputStatus);
339
 
                                                        }
340
 
                                                }
341
 
                                        }
342
 
                                }
343
 
                                break;
344
 
                        case ControlFlowNodeType.LoopCondition:
345
 
                                ForeachStatement foreachStmt = node.NextStatement as ForeachStatement;
346
 
                                if (foreachStmt != null) {
347
 
                                        outputStatus = CleanSpecialValues (foreachStmt.InExpression.AcceptVisitor (visitor, inputStatus));
348
 
                                        if (foreachStmt.VariableName == this.variableName)
349
 
                                                outputStatus = DefiniteAssignmentStatus.DefinitelyAssigned;
350
 
                                        break;
351
 
                                } else {
352
 
                                        Debug.Assert (node.NextStatement is IfElseStatement || node.NextStatement is WhileStatement || node.NextStatement is ForStatement || node.NextStatement is DoWhileStatement);
353
 
                                        Expression condition = node.NextStatement.GetChildByRole (Roles.Condition);
354
 
                                                if (condition.IsNull)
355
 
                                                        outputStatus = inputStatus;
356
 
                                                else
357
 
                                                        outputStatus = condition.AcceptVisitor(visitor, inputStatus);
358
 
                                                foreach (ControlFlowEdge edge in node.Outgoing) {
359
 
                                                        if (edge.Type == ControlFlowEdgeType.ConditionTrue && outputStatus == DefiniteAssignmentStatus.AssignedAfterTrueExpression) {
360
 
                                                                ChangeEdgeStatus(edge, DefiniteAssignmentStatus.DefinitelyAssigned);
361
 
                                                        } else if (edge.Type == ControlFlowEdgeType.ConditionFalse && outputStatus == DefiniteAssignmentStatus.AssignedAfterFalseExpression) {
362
 
                                                                ChangeEdgeStatus(edge, DefiniteAssignmentStatus.DefinitelyAssigned);
363
 
                                                        } else {
364
 
                                                                ChangeEdgeStatus(edge, CleanSpecialValues(outputStatus));
365
 
                                                        }
366
 
                                                }
367
 
                                                return;
368
 
                                        }
369
 
                                default:
370
 
                                        throw new InvalidOperationException();
371
 
                        }
372
 
                        foreach (ControlFlowEdge edge in node.Outgoing) {
373
 
                                ChangeEdgeStatus(edge, outputStatus);
374
 
                        }
375
 
                }
376
 
                
377
 
                void ChangeEdgeStatus(ControlFlowEdge edge, DefiniteAssignmentStatus newStatus)
378
 
                {
379
 
                        DefiniteAssignmentStatus oldStatus = edgeStatus[edge];
380
 
                        if (oldStatus == newStatus)
381
 
                                return;
382
 
                        // Ensure that status can cannot change back to CodeUnreachable after it once was reachable.
383
 
                        // Also, don't ever use AssignedAfter... for statements.
384
 
                        if (newStatus == DefiniteAssignmentStatus.CodeUnreachable
385
 
                            || newStatus == DefiniteAssignmentStatus.AssignedAfterFalseExpression
386
 
                            || newStatus == DefiniteAssignmentStatus.AssignedAfterTrueExpression)
387
 
                        {
388
 
                                throw new InvalidOperationException();
389
 
                        }
390
 
                        // Note that the status can change from DefinitelyAssigned
391
 
                        // back to PotentiallyAssigned as unreachable input edges are
392
 
                        // discovered to be reachable.
393
 
                        
394
 
                        edgeStatus[edge] = newStatus;
395
 
                        DefiniteAssignmentNode targetNode = (DefiniteAssignmentNode)edge.To;
396
 
                        if (analyzedRangeStart <= targetNode.Index && targetNode.Index <= analyzedRangeEnd) {
397
 
                                // TODO: potential optimization: visit previously unreachable nodes with higher priority
398
 
                                // (e.g. use Deque and enqueue previously unreachable nodes at the front, but
399
 
                                // other nodes at the end)
400
 
                                nodesWithModifiedInput.Enqueue(targetNode);
401
 
                        }
402
 
                }
403
 
                
404
 
                /// <summary>
405
 
                /// Evaluates an expression.
406
 
                /// </summary>
407
 
                /// <returns>The constant value of the expression; or null if the expression is not a constant.</returns>
408
 
                ResolveResult EvaluateConstant(Expression expr)
409
 
                {
410
 
                        return resolver.Resolve(expr, analysisCancellationToken);
411
 
                }
412
 
                
413
 
                /// <summary>
414
 
                /// Evaluates an expression.
415
 
                /// </summary>
416
 
                /// <returns>The value of the constant boolean expression; or null if the value is not a constant boolean expression.</returns>
417
 
                bool? EvaluateCondition(Expression expr)
418
 
                {
419
 
                        ResolveResult rr = EvaluateConstant(expr);
420
 
                        if (rr != null && rr.IsCompileTimeConstant)
421
 
                                return rr.ConstantValue as bool?;
422
 
                        else
423
 
                                return null;
424
 
                }
425
 
                
426
 
                static DefiniteAssignmentStatus CleanSpecialValues(DefiniteAssignmentStatus status)
427
 
                {
428
 
                        if (status == DefiniteAssignmentStatus.AssignedAfterTrueExpression)
429
 
                                return DefiniteAssignmentStatus.PotentiallyAssigned;
430
 
                        else if (status == DefiniteAssignmentStatus.AssignedAfterFalseExpression)
431
 
                                return DefiniteAssignmentStatus.PotentiallyAssigned;
432
 
                        else
433
 
                                return status;
434
 
                }
435
 
                
436
 
                sealed class DefiniteAssignmentVisitor : DepthFirstAstVisitor<DefiniteAssignmentStatus, DefiniteAssignmentStatus>
437
 
                {
438
 
                        internal DefiniteAssignmentAnalysis analysis;
439
 
                        
440
 
                        // The general approach for unknown nodes is to pass the status through all child nodes in order
441
 
                        protected override DefiniteAssignmentStatus VisitChildren(AstNode node, DefiniteAssignmentStatus data)
442
 
                        {
443
 
                                // the special values are valid as output only, not as input
444
 
                                Debug.Assert(data == CleanSpecialValues(data));
445
 
                                DefiniteAssignmentStatus status = data;
446
 
                                foreach (AstNode child in node.Children) {
447
 
                                        analysis.analysisCancellationToken.ThrowIfCancellationRequested();
448
 
                                        
449
 
                                        Debug.Assert(!(child is Statement)); // statements are visited with the CFG, not with the visitor pattern
450
 
                                        status = child.AcceptVisitor(this, status);
451
 
                                        status = CleanSpecialValues(status);
452
 
                                }
453
 
                                return status;
454
 
                        }
455
 
                        
456
 
                        #region Statements
457
 
                        // For statements, the visitor only describes the effect of the statement itself;
458
 
                        // we do not consider the effect of any nested statements.
459
 
                        // This is done because the nested statements will be reached using the control flow graph.
460
 
                        
461
 
                        // In fact, these methods are present so that the default logic in VisitChildren does not try to visit the nested statements.
462
 
                        
463
 
                        public override DefiniteAssignmentStatus VisitBlockStatement(BlockStatement blockStatement, DefiniteAssignmentStatus data)
464
 
                        {
465
 
                                return data;
466
 
                        }
467
 
                        
468
 
                        public override DefiniteAssignmentStatus VisitCheckedStatement(CheckedStatement checkedStatement, DefiniteAssignmentStatus data)
469
 
                        {
470
 
                                return data;
471
 
                        }
472
 
                        
473
 
                        public override DefiniteAssignmentStatus VisitUncheckedStatement(UncheckedStatement uncheckedStatement, DefiniteAssignmentStatus data)
474
 
                        {
475
 
                                return data;
476
 
                        }
477
 
                        
478
 
                        // ExpressionStatement handled by default logic
479
 
                        // VariableDeclarationStatement handled by default logic
480
 
                        
481
 
                        public override DefiniteAssignmentStatus VisitVariableInitializer(VariableInitializer variableInitializer, DefiniteAssignmentStatus data)
482
 
                        {
483
 
                                if (variableInitializer.Initializer.IsNull) {
484
 
                                        return data;
485
 
                                } else {
486
 
                                        DefiniteAssignmentStatus status = variableInitializer.Initializer.AcceptVisitor(this, data);
487
 
                                        if (variableInitializer.Name == analysis.variableName)
488
 
                                                return DefiniteAssignmentStatus.DefinitelyAssigned;
489
 
                                        else
490
 
                                                return status;
491
 
                                }
492
 
                        }
493
 
                        
494
 
                        // IfStatement not handled by visitor, but special-cased in the code consuming the control flow graph
495
 
                        
496
 
                        public override DefiniteAssignmentStatus VisitSwitchStatement(SwitchStatement switchStatement, DefiniteAssignmentStatus data)
497
 
                        {
498
 
                                return switchStatement.Expression.AcceptVisitor(this, data);
499
 
                        }
500
 
                        
501
 
                        public override DefiniteAssignmentStatus VisitWhileStatement(WhileStatement whileStatement, DefiniteAssignmentStatus data)
502
 
                        {
503
 
                                return data; // condition is handled by special condition CFG node
504
 
                        }
505
 
                        
506
 
                        public override DefiniteAssignmentStatus VisitDoWhileStatement(DoWhileStatement doWhileStatement, DefiniteAssignmentStatus data)
507
 
                        {
508
 
                                return data; // condition is handled by special condition CFG node
509
 
                        }
510
 
                        
511
 
                        public override DefiniteAssignmentStatus VisitForStatement(ForStatement forStatement, DefiniteAssignmentStatus data)
512
 
                        {
513
 
                                return data; // condition is handled by special condition CFG node; initializer and iterator statements are handled by CFG
514
 
                        }
515
 
                        
516
 
                        // Break/Continue/Goto: handled by default logic
517
 
                        
518
 
                        // ThrowStatement: handled by default logic (just visit the expression)
519
 
                        // ReturnStatement: handled by default logic (just visit the expression)
520
 
                        
521
 
                        public override DefiniteAssignmentStatus VisitTryCatchStatement(TryCatchStatement tryCatchStatement, DefiniteAssignmentStatus data)
522
 
                        {
523
 
                                return data; // no special logic when entering the try-catch-finally statement
524
 
                                // TODO: where to put the special logic when exiting the try-finally statement?
525
 
                        }
526
 
                        
527
 
                        public override DefiniteAssignmentStatus VisitForeachStatement(ForeachStatement foreachStatement, DefiniteAssignmentStatus data)
528
 
                        {
529
 
                                return data; // assignment of the foreach loop variable is done when handling the condition node
530
 
                        }
531
 
                        
532
 
                        public override DefiniteAssignmentStatus VisitUsingStatement(UsingStatement usingStatement, DefiniteAssignmentStatus data)
533
 
                        {
534
 
                                if (usingStatement.ResourceAcquisition is Expression)
535
 
                                        return usingStatement.ResourceAcquisition.AcceptVisitor(this, data);
536
 
                                else
537
 
                                        return data; // don't handle resource acquisition statements, as those are connected in the control flow graph
538
 
                        }
539
 
                        
540
 
                        public override DefiniteAssignmentStatus VisitLockStatement(LockStatement lockStatement, DefiniteAssignmentStatus data)
541
 
                        {
542
 
                                return lockStatement.Expression.AcceptVisitor(this, data);
543
 
                        }
544
 
                        
545
 
                        // Yield statements use the default logic
546
 
                        
547
 
                        public override DefiniteAssignmentStatus VisitUnsafeStatement(UnsafeStatement unsafeStatement, DefiniteAssignmentStatus data)
548
 
                        {
549
 
                                return data;
550
 
                        }
551
 
                        
552
 
                        public override DefiniteAssignmentStatus VisitFixedStatement(FixedStatement fixedStatement, DefiniteAssignmentStatus data)
553
 
                        {
554
 
                                DefiniteAssignmentStatus status = data;
555
 
                                foreach (var variable in fixedStatement.Variables)
556
 
                                        status = variable.AcceptVisitor(this, status);
557
 
                                return status;
558
 
                        }
559
 
                        #endregion
560
 
                        
561
 
                        #region Expressions
562
 
                        public override DefiniteAssignmentStatus VisitDirectionExpression(DirectionExpression directionExpression, DefiniteAssignmentStatus data)
563
 
                        {
564
 
                                if (directionExpression.FieldDirection == FieldDirection.Out) {
565
 
                                        return HandleAssignment(directionExpression.Expression, null, data);
566
 
                                } else {
567
 
                                        // use default logic for 'ref'
568
 
                                        return VisitChildren(directionExpression, data);
569
 
                                }
570
 
                        }
571
 
                        
572
 
                        public override DefiniteAssignmentStatus VisitAssignmentExpression(AssignmentExpression assignmentExpression, DefiniteAssignmentStatus data)
573
 
                        {
574
 
                                if (assignmentExpression.Operator == AssignmentOperatorType.Assign) {
575
 
                                        return HandleAssignment(assignmentExpression.Left, assignmentExpression.Right, data);
576
 
                                } else {
577
 
                                        // use default logic for compound assignment operators
578
 
                                        return VisitChildren(assignmentExpression, data);
579
 
                                }
580
 
                        }
581
 
                        
582
 
                        DefiniteAssignmentStatus HandleAssignment(Expression left, Expression right, DefiniteAssignmentStatus initialStatus)
583
 
                        {
584
 
                                IdentifierExpression ident = left as IdentifierExpression;
585
 
                                if (ident != null && ident.Identifier == analysis.variableName) {
586
 
                                        // right==null is special case when handling 'out' expressions
587
 
                                        if (right != null)
588
 
                                                right.AcceptVisitor(this, initialStatus);
589
 
                                        return DefiniteAssignmentStatus.DefinitelyAssigned;
590
 
                                } else {
591
 
                                        DefiniteAssignmentStatus status = left.AcceptVisitor(this, initialStatus);
592
 
                                        if (right != null)
593
 
                                                status = right.AcceptVisitor(this, CleanSpecialValues(status));
594
 
                                        return CleanSpecialValues(status);
595
 
                                }
596
 
                        }
597
 
                        
598
 
                        public override DefiniteAssignmentStatus VisitParenthesizedExpression(ParenthesizedExpression parenthesizedExpression, DefiniteAssignmentStatus data)
599
 
                        {
600
 
                                // Don't use the default logic here because we don't want to clean up the special values.
601
 
                                return parenthesizedExpression.Expression.AcceptVisitor(this, data);
602
 
                        }
603
 
                        
604
 
                        public override DefiniteAssignmentStatus VisitCheckedExpression(CheckedExpression checkedExpression, DefiniteAssignmentStatus data)
605
 
                        {
606
 
                                return checkedExpression.Expression.AcceptVisitor(this, data);
607
 
                        }
608
 
                        
609
 
                        public override DefiniteAssignmentStatus VisitUncheckedExpression(UncheckedExpression uncheckedExpression, DefiniteAssignmentStatus data)
610
 
                        {
611
 
                                return uncheckedExpression.Expression.AcceptVisitor(this, data);
612
 
                        }
613
 
                        
614
 
                        public override DefiniteAssignmentStatus VisitBinaryOperatorExpression(BinaryOperatorExpression binaryOperatorExpression, DefiniteAssignmentStatus data)
615
 
                        {
616
 
                                if (binaryOperatorExpression.Operator == BinaryOperatorType.ConditionalAnd) {
617
 
                                        // Handle constant left side of && expressions (not in the C# spec, but done by the MS compiler)
618
 
                                        bool? cond = analysis.EvaluateCondition(binaryOperatorExpression.Left);
619
 
                                        if (cond == true)
620
 
                                                return binaryOperatorExpression.Right.AcceptVisitor(this, data); // right operand gets evaluated unconditionally
621
 
                                        else if (cond == false)
622
 
                                                return data; // right operand never gets evaluated
623
 
                                        // C# 4.0 spec: §5.3.3.24 Definite Assignment for && expressions
624
 
                                        DefiniteAssignmentStatus afterLeft = binaryOperatorExpression.Left.AcceptVisitor(this, data);
625
 
                                        DefiniteAssignmentStatus beforeRight;
626
 
                                        if (afterLeft == DefiniteAssignmentStatus.AssignedAfterTrueExpression)
627
 
                                                beforeRight = DefiniteAssignmentStatus.DefinitelyAssigned;
628
 
                                        else if (afterLeft == DefiniteAssignmentStatus.AssignedAfterFalseExpression)
629
 
                                                beforeRight = DefiniteAssignmentStatus.PotentiallyAssigned;
630
 
                                        else
631
 
                                                beforeRight = afterLeft;
632
 
                                        DefiniteAssignmentStatus afterRight = binaryOperatorExpression.Right.AcceptVisitor(this, beforeRight);
633
 
                                        if (afterLeft == DefiniteAssignmentStatus.DefinitelyAssigned)
634
 
                                                return DefiniteAssignmentStatus.DefinitelyAssigned;
635
 
                                        else if (afterRight == DefiniteAssignmentStatus.DefinitelyAssigned && afterLeft == DefiniteAssignmentStatus.AssignedAfterFalseExpression)
636
 
                                                return DefiniteAssignmentStatus.DefinitelyAssigned;
637
 
                                        else if (afterRight == DefiniteAssignmentStatus.DefinitelyAssigned || afterRight == DefiniteAssignmentStatus.AssignedAfterTrueExpression)
638
 
                                                return DefiniteAssignmentStatus.AssignedAfterTrueExpression;
639
 
                                        else if (afterLeft == DefiniteAssignmentStatus.AssignedAfterFalseExpression && afterRight == DefiniteAssignmentStatus.AssignedAfterFalseExpression)
640
 
                                                return DefiniteAssignmentStatus.AssignedAfterFalseExpression;
641
 
                                        else
642
 
                                                return DefiniteAssignmentStatus.PotentiallyAssigned;
643
 
                                } else if (binaryOperatorExpression.Operator == BinaryOperatorType.ConditionalOr) {
644
 
                                        // C# 4.0 spec: §5.3.3.25 Definite Assignment for || expressions
645
 
                                        bool? cond = analysis.EvaluateCondition(binaryOperatorExpression.Left);
646
 
                                        if (cond == false)
647
 
                                                return binaryOperatorExpression.Right.AcceptVisitor(this, data); // right operand gets evaluated unconditionally
648
 
                                        else if (cond == true)
649
 
                                                return data; // right operand never gets evaluated
650
 
                                        DefiniteAssignmentStatus afterLeft = binaryOperatorExpression.Left.AcceptVisitor(this, data);
651
 
                                        DefiniteAssignmentStatus beforeRight;
652
 
                                        if (afterLeft == DefiniteAssignmentStatus.AssignedAfterTrueExpression)
653
 
                                                beforeRight = DefiniteAssignmentStatus.PotentiallyAssigned;
654
 
                                        else if (afterLeft == DefiniteAssignmentStatus.AssignedAfterFalseExpression)
655
 
                                                beforeRight = DefiniteAssignmentStatus.DefinitelyAssigned;
656
 
                                        else
657
 
                                                beforeRight = afterLeft;
658
 
                                        DefiniteAssignmentStatus afterRight = binaryOperatorExpression.Right.AcceptVisitor(this, beforeRight);
659
 
                                        if (afterLeft == DefiniteAssignmentStatus.DefinitelyAssigned)
660
 
                                                return DefiniteAssignmentStatus.DefinitelyAssigned;
661
 
                                        else if (afterRight == DefiniteAssignmentStatus.DefinitelyAssigned && afterLeft == DefiniteAssignmentStatus.AssignedAfterTrueExpression)
662
 
                                                return DefiniteAssignmentStatus.DefinitelyAssigned;
663
 
                                        else if (afterRight == DefiniteAssignmentStatus.DefinitelyAssigned || afterRight == DefiniteAssignmentStatus.AssignedAfterFalseExpression)
664
 
                                                return DefiniteAssignmentStatus.AssignedAfterFalseExpression;
665
 
                                        else if (afterLeft == DefiniteAssignmentStatus.AssignedAfterTrueExpression && afterRight == DefiniteAssignmentStatus.AssignedAfterTrueExpression)
666
 
                                                return DefiniteAssignmentStatus.AssignedAfterTrueExpression;
667
 
                                        else
668
 
                                                return DefiniteAssignmentStatus.PotentiallyAssigned;
669
 
                                } else if (binaryOperatorExpression.Operator == BinaryOperatorType.NullCoalescing) {
670
 
                                        // C# 4.0 spec: §5.3.3.27 Definite assignment for ?? expressions
671
 
                                        ResolveResult crr = analysis.EvaluateConstant(binaryOperatorExpression.Left);
672
 
                                        if (crr != null && crr.IsCompileTimeConstant && crr.ConstantValue == null)
673
 
                                                return binaryOperatorExpression.Right.AcceptVisitor(this, data);
674
 
                                        DefiniteAssignmentStatus status = CleanSpecialValues(binaryOperatorExpression.Left.AcceptVisitor(this, data));
675
 
                                        binaryOperatorExpression.Right.AcceptVisitor(this, status);
676
 
                                        return status;
677
 
                                } else {
678
 
                                        // use default logic for other operators
679
 
                                        return VisitChildren(binaryOperatorExpression, data);
680
 
                                }
681
 
                        }
682
 
                        
683
 
                        public override DefiniteAssignmentStatus VisitUnaryOperatorExpression(UnaryOperatorExpression unaryOperatorExpression, DefiniteAssignmentStatus data)
684
 
                        {
685
 
                                if (unaryOperatorExpression.Operator == UnaryOperatorType.Not) {
686
 
                                        // C# 4.0 spec: §5.3.3.26 Definite assignment for ! expressions
687
 
                                        DefiniteAssignmentStatus status = unaryOperatorExpression.Expression.AcceptVisitor(this, data);
688
 
                                        if (status == DefiniteAssignmentStatus.AssignedAfterFalseExpression)
689
 
                                                return DefiniteAssignmentStatus.AssignedAfterTrueExpression;
690
 
                                        else if (status == DefiniteAssignmentStatus.AssignedAfterTrueExpression)
691
 
                                                return DefiniteAssignmentStatus.AssignedAfterFalseExpression;
692
 
                                        else
693
 
                                                return status;
694
 
                                } else {
695
 
                                        // use default logic for other operators
696
 
                                        return VisitChildren(unaryOperatorExpression, data);
697
 
                                }
698
 
                        }
699
 
                        
700
 
                        public override DefiniteAssignmentStatus VisitConditionalExpression(ConditionalExpression conditionalExpression, DefiniteAssignmentStatus data)
701
 
                        {
702
 
                                // C# 4.0 spec: §5.3.3.28 Definite assignment for ?: expressions
703
 
                                bool? cond = analysis.EvaluateCondition(conditionalExpression.Condition);
704
 
                                if (cond == true) {
705
 
                                        return conditionalExpression.TrueExpression.AcceptVisitor(this, data);
706
 
                                } else if (cond == false) {
707
 
                                        return conditionalExpression.FalseExpression.AcceptVisitor(this, data);
708
 
                                } else {
709
 
                                        DefiniteAssignmentStatus afterCondition = conditionalExpression.Condition.AcceptVisitor(this, data);
710
 
                                        
711
 
                                        DefiniteAssignmentStatus beforeTrue, beforeFalse;
712
 
                                        if (afterCondition == DefiniteAssignmentStatus.AssignedAfterTrueExpression) {
713
 
                                                beforeTrue = DefiniteAssignmentStatus.DefinitelyAssigned;
714
 
                                                beforeFalse = DefiniteAssignmentStatus.PotentiallyAssigned;
715
 
                                        } else if (afterCondition == DefiniteAssignmentStatus.AssignedAfterFalseExpression) {
716
 
                                                beforeTrue = DefiniteAssignmentStatus.PotentiallyAssigned;
717
 
                                                beforeFalse = DefiniteAssignmentStatus.DefinitelyAssigned;
718
 
                                        } else {
719
 
                                                beforeTrue = afterCondition;
720
 
                                                beforeFalse = afterCondition;
721
 
                                        }
722
 
                                        
723
 
                                        DefiniteAssignmentStatus afterTrue = conditionalExpression.TrueExpression.AcceptVisitor(this, beforeTrue);
724
 
                                        DefiniteAssignmentStatus afterFalse = conditionalExpression.TrueExpression.AcceptVisitor(this, beforeFalse);
725
 
                                        return MergeStatus(CleanSpecialValues(afterTrue), CleanSpecialValues(afterFalse));
726
 
                                }
727
 
                        }
728
 
                        
729
 
                        public override DefiniteAssignmentStatus VisitAnonymousMethodExpression(AnonymousMethodExpression anonymousMethodExpression, DefiniteAssignmentStatus data)
730
 
                        {
731
 
                                BlockStatement body = anonymousMethodExpression.Body;
732
 
                                analysis.ChangeNodeStatus(analysis.beginNodeDict[body], data);
733
 
                                return data;
734
 
                        }
735
 
                        
736
 
                        public override DefiniteAssignmentStatus VisitLambdaExpression(LambdaExpression lambdaExpression, DefiniteAssignmentStatus data)
737
 
                        {
738
 
                                Statement body = lambdaExpression.Body as Statement;
739
 
                                if (body != null) {
740
 
                                        analysis.ChangeNodeStatus(analysis.beginNodeDict[body], data);
741
 
                                } else {
742
 
                                        lambdaExpression.Body.AcceptVisitor(this, data);
743
 
                                }
744
 
                                return data;
745
 
                        }
746
 
                        
747
 
                        public override DefiniteAssignmentStatus VisitIdentifierExpression(IdentifierExpression identifierExpression, DefiniteAssignmentStatus data)
748
 
                        {
749
 
                                if (data != DefiniteAssignmentStatus.DefinitelyAssigned
750
 
                                    && identifierExpression.Identifier == analysis.variableName && identifierExpression.TypeArguments.Count == 0)
751
 
                                {
752
 
                                        analysis.unassignedVariableUses.Add(identifierExpression);
753
 
                                }
754
 
                                return data;
755
 
                        }
756
 
                        #endregion
757
 
                }
758
 
        }
759
 
}