← Back to branch summary

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

« back to all changes in this revision

Viewing changes to external/nrefactory/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:
external/nrefactory/ICSharpCode.NRefactory.CSharp/Analysis/DefiniteAssignmentAnalysis.cs
 
1
// Copyright (c) 2010-2013 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
                                for (AstNode child = node.FirstChild; child != null; child = child.NextSibling) {
 
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.FalseExpression.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
}