← 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/Parser/mcs/flowanalysis.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/Parser/mcs/flowanalysis.cs
 
1
//
 
2
// flowanalyis.cs: The control flow analysis code
 
3
//
 
4
// Authors:
 
5
//   Martin Baulig (martin@ximian.com)
 
6
//   Raja R Harinath (rharinath@novell.com)
 
7
//   Marek Safar (marek.safar@gmail.com)
 
8
//
 
9
// Copyright 2001, 2002, 2003 Ximian, Inc.
 
10
// Copyright 2003-2008 Novell, Inc.
 
11
// Copyright 2011 Xamarin, Inc.
 
12
//
 
13
 
 
14
using System;
 
15
using System.Text;
 
16
using System.Collections.Generic;
 
17
 
 
18
namespace Mono.CSharp
 
19
{
 
20
        // <summary>
 
21
        //   A new instance of this class is created every time a new block is resolved
 
22
        //   and if there's branching in the block's control flow.
 
23
        // </summary>
 
24
        public abstract class FlowBranching
 
25
        {
 
26
                // <summary>
 
27
                //   The type of a FlowBranching.
 
28
                // </summary>
 
29
                public enum BranchingType : byte {
 
30
                        // Normal (conditional or toplevel) block.
 
31
                        Block,
 
32
 
 
33
                        // Conditional.
 
34
                        Conditional,
 
35
 
 
36
                        // A loop block.
 
37
                        Loop,
 
38
 
 
39
                        // The statement embedded inside a loop
 
40
                        Embedded,
 
41
 
 
42
                        // part of a block headed by a jump target
 
43
                        Labeled,
 
44
 
 
45
                        // TryCatch block.
 
46
                        TryCatch,
 
47
 
 
48
                        // TryFinally, Using, Lock, CollectionForeach
 
49
                        Exception,
 
50
 
 
51
                        // Switch block.
 
52
                        Switch,
 
53
 
 
54
                        // The toplevel block of a function
 
55
                        Toplevel,
 
56
 
 
57
                        // An iterator block
 
58
                        Iterator
 
59
                }
 
60
 
 
61
                // <summary>
 
62
                //   The type of one sibling of a branching.
 
63
                // </summary>
 
64
                public enum SiblingType : byte {
 
65
                        Block,
 
66
                        Conditional,
 
67
                        SwitchSection,
 
68
                        Try,
 
69
                        Catch,
 
70
                        Finally
 
71
                }
 
72
 
 
73
                public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
 
74
                {
 
75
                        switch (type) {
 
76
                        case BranchingType.Exception:
 
77
                        case BranchingType.Labeled:
 
78
                        case BranchingType.Toplevel:
 
79
                        case BranchingType.TryCatch:
 
80
                                throw new InvalidOperationException ();
 
81
 
 
82
                        case BranchingType.Switch:
 
83
                                return new FlowBranchingBreakable (parent, type, SiblingType.SwitchSection, block, loc);
 
84
 
 
85
                        case BranchingType.Block:
 
86
                                return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
 
87
 
 
88
                        case BranchingType.Loop:
 
89
                                return new FlowBranchingBreakable (parent, type, SiblingType.Conditional, block, loc);
 
90
 
 
91
                        case BranchingType.Embedded:
 
92
                                return new FlowBranchingContinuable (parent, type, SiblingType.Conditional, block, loc);
 
93
 
 
94
                        default:
 
95
                                return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
 
96
                        }
 
97
                }
 
98
 
 
99
                // <summary>
 
100
                //   The type of this flow branching.
 
101
                // </summary>
 
102
                public readonly BranchingType Type;
 
103
 
 
104
                // <summary>
 
105
                //   The block this branching is contained in.  This may be null if it's not
 
106
                //   a top-level block and it doesn't declare any local variables.
 
107
                // </summary>
 
108
                public readonly Block Block;
 
109
 
 
110
                // <summary>
 
111
                //   The parent of this branching or null if this is the top-block.
 
112
                // </summary>
 
113
                public readonly FlowBranching Parent;
 
114
 
 
115
                // <summary>
 
116
                //   Start-Location of this flow branching.
 
117
                // </summary>
 
118
                public readonly Location Location;
 
119
 
 
120
                static int next_id;
 
121
                int id;
 
122
 
 
123
                // <summary>
 
124
                //   The vector contains a BitArray with information about which local variables
 
125
                //   and parameters are already initialized at the current code position.
 
126
                // </summary>
 
127
                public class UsageVector {
 
128
                        // <summary>
 
129
                        //   The type of this branching.
 
130
                        // </summary>
 
131
                        public readonly SiblingType Type;
 
132
 
 
133
                        // <summary>
 
134
                        //   Start location of this branching.
 
135
                        // </summary>
 
136
                        public Location Location;
 
137
 
 
138
                        // <summary>
 
139
                        //   This is only valid for SwitchSection, Try, Catch and Finally.
 
140
                        // </summary>
 
141
                        public readonly Block Block;
 
142
 
 
143
                        // <summary>
 
144
                        //   The number of locals in this block.
 
145
                        // </summary>
 
146
                        public readonly int CountLocals;
 
147
 
 
148
                        // <summary>
 
149
                        //   If not null, then we inherit our state from this vector and do a
 
150
                        //   copy-on-write.  If null, then we're the first sibling in a top-level
 
151
                        //   block and inherit from the empty vector.
 
152
                        // </summary>
 
153
                        public readonly UsageVector InheritsFrom;
 
154
 
 
155
                        // <summary>
 
156
                        //   This is used to construct a list of UsageVector's.
 
157
                        // </summary>
 
158
                        public UsageVector Next;
 
159
 
 
160
                        //
 
161
                        // Private.
 
162
                        //
 
163
                        MyBitVector locals;
 
164
                        bool is_unreachable;
 
165
 
 
166
                        static int next_id;
 
167
                        int id;
 
168
 
 
169
                        //
 
170
                        // Normally, you should not use any of these constructors.
 
171
                        //
 
172
                        public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc, int num_locals)
 
173
                        {
 
174
                                this.Type = type;
 
175
                                this.Block = block;
 
176
                                this.Location = loc;
 
177
                                this.InheritsFrom = parent;
 
178
                                this.CountLocals = num_locals;
 
179
 
 
180
                                locals = num_locals == 0 
 
181
                                        ? MyBitVector.Empty
 
182
                                        : new MyBitVector (parent == null ? MyBitVector.Empty : parent.locals, num_locals);
 
183
 
 
184
                                if (parent != null)
 
185
                                        is_unreachable = parent.is_unreachable;
 
186
 
 
187
                                id = ++next_id;
 
188
 
 
189
                        }
 
190
 
 
191
                        public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc)
 
192
                                : this (type, parent, block, loc, parent.CountLocals)
 
193
                        { }
 
194
 
 
195
                        private UsageVector (MyBitVector locals, bool is_unreachable, Block block, Location loc)
 
196
                        {
 
197
                                this.Type = SiblingType.Block;
 
198
                                this.Location = loc;
 
199
                                this.Block = block;
 
200
 
 
201
                                this.is_unreachable = is_unreachable;
 
202
 
 
203
                                this.locals = locals;
 
204
 
 
205
                                id = ++next_id;
 
206
 
 
207
                        }
 
208
 
 
209
                        // <summary>
 
210
                        //   This does a deep copy of the usage vector.
 
211
                        // </summary>
 
212
                        public UsageVector Clone ()
 
213
                        {
 
214
                                UsageVector retval = new UsageVector (Type, null, Block, Location, CountLocals);
 
215
 
 
216
                                retval.locals = locals.Clone ();
 
217
                                retval.is_unreachable = is_unreachable;
 
218
 
 
219
                                return retval;
 
220
                        }
 
221
 
 
222
                        public bool IsAssigned (VariableInfo var, bool ignoreReachability)
 
223
                        {
 
224
                                if (!ignoreReachability && !var.IsParameter && IsUnreachable)
 
225
                                        return true;
 
226
 
 
227
                                return var.IsAssigned (locals);
 
228
                        }
 
229
 
 
230
                        public void SetAssigned (VariableInfo var)
 
231
                        {
 
232
                                if (!var.IsParameter && IsUnreachable)
 
233
                                        return;
 
234
 
 
235
                                var.SetAssigned (locals);
 
236
                        }
 
237
 
 
238
                        public bool IsFieldAssigned (VariableInfo var, string name)
 
239
                        {
 
240
                                if (/*!var.IsParameter &&*/ IsUnreachable)
 
241
                                        return true;
 
242
 
 
243
                                return var.IsStructFieldAssigned (locals, name);
 
244
                        }
 
245
 
 
246
                        public void SetFieldAssigned (VariableInfo var, string name)
 
247
                        {
 
248
                                if (/*!var.IsParameter &&*/ IsUnreachable)
 
249
                                        return;
 
250
 
 
251
                                var.SetStructFieldAssigned (locals, name);
 
252
                        }
 
253
 
 
254
                        public bool IsUnreachable {
 
255
                                get {
 
256
                                        return is_unreachable;
 
257
                                }
 
258
                                set {
 
259
                                        is_unreachable = value;
 
260
                                }
 
261
                        }
 
262
 
 
263
                        public void ResetBarrier ()
 
264
                        {
 
265
                                is_unreachable = false;
 
266
                        }
 
267
 
 
268
                        public void Goto ()
 
269
                        {
 
270
                                is_unreachable = true;
 
271
                        }
 
272
 
 
273
                        public static UsageVector MergeSiblings (UsageVector sibling_list, Location loc)
 
274
                        {
 
275
                                if (sibling_list.Next == null)
 
276
                                        return sibling_list;
 
277
 
 
278
                                MyBitVector locals = null;
 
279
                                bool is_unreachable = sibling_list.is_unreachable;
 
280
 
 
281
                                if (!sibling_list.IsUnreachable)
 
282
                                        locals &= sibling_list.locals;
 
283
 
 
284
                                for (UsageVector child = sibling_list.Next; child != null; child = child.Next) {
 
285
                                        is_unreachable &= child.is_unreachable;
 
286
 
 
287
                                        if (!child.IsUnreachable)
 
288
                                                locals &= child.locals;
 
289
                                }
 
290
 
 
291
                                return new UsageVector (locals, is_unreachable, null, loc);
 
292
                        }
 
293
 
 
294
                        // <summary>
 
295
                        //   Merges a child branching.
 
296
                        // </summary>
 
297
                        public UsageVector MergeChild (UsageVector child, bool overwrite)
 
298
                        {
 
299
                                Report.Debug (2, "    MERGING CHILD EFFECTS", this, child, Type);
 
300
 
 
301
                                bool new_isunr = child.is_unreachable;
 
302
 
 
303
                                //
 
304
                                // We've now either reached the point after the branching or we will
 
305
                                // never get there since we always return or always throw an exception.
 
306
                                //
 
307
                                // If we can reach the point after the branching, mark all locals and
 
308
                                // parameters as initialized which have been initialized in all branches
 
309
                                // we need to look at (see above).
 
310
                                //
 
311
 
 
312
                                if ((Type == SiblingType.SwitchSection) && !new_isunr) {
 
313
                                        Report.Error (163, Location,
 
314
                                                      "Control cannot fall through from one " +
 
315
                                                      "case label to another");
 
316
                                        return child;
 
317
                                }
 
318
 
 
319
                                locals |= child.locals;
 
320
 
 
321
                                // throw away un-necessary information about variables in child blocks
 
322
                                if (locals.Count != CountLocals)
 
323
                                        locals = new MyBitVector (locals, CountLocals);
 
324
 
 
325
                                if (overwrite)
 
326
                                        is_unreachable = new_isunr;
 
327
                                else
 
328
                                        is_unreachable |= new_isunr;
 
329
 
 
330
                                return child;
 
331
                        }
 
332
 
 
333
                        public void MergeOrigins (UsageVector o_vectors)
 
334
                        {
 
335
                                Report.Debug (1, "  MERGING BREAK ORIGINS", this);
 
336
 
 
337
                                if (o_vectors == null)
 
338
                                        return;
 
339
 
 
340
                                if (IsUnreachable && locals != null)
 
341
                                        locals.SetAll (true);
 
342
 
 
343
                                for (UsageVector vector = o_vectors; vector != null; vector = vector.Next) {
 
344
                                        Report.Debug (1, "    MERGING BREAK ORIGIN", vector);
 
345
                                        if (vector.IsUnreachable)
 
346
                                                continue;
 
347
                                        locals &= vector.locals;
 
348
                                        is_unreachable &= vector.is_unreachable;
 
349
                                }
 
350
 
 
351
                                Report.Debug (1, "  MERGING BREAK ORIGINS DONE", this);
 
352
                        }
 
353
 
 
354
                        //
 
355
                        // Debugging stuff.
 
356
                        //
 
357
 
 
358
                        public override string ToString ()
 
359
                        {
 
360
                                return String.Format ("Vector ({0},{1},{2}-{3})", Type, id, is_unreachable, locals);
 
361
                        }
 
362
                }
 
363
 
 
364
                // <summary>
 
365
                //   Creates a new flow branching which is contained in `parent'.
 
366
                //   You should only pass non-null for the `block' argument if this block
 
367
                //   introduces any new variables - in this case, we need to create a new
 
368
                //   usage vector with a different size than our parent's one.
 
369
                // </summary>
 
370
                protected FlowBranching (FlowBranching parent, BranchingType type, SiblingType stype,
 
371
                                         Block block, Location loc)
 
372
                {
 
373
                        Parent = parent;
 
374
                        Block = block;
 
375
                        Location = loc;
 
376
                        Type = type;
 
377
                        id = ++next_id;
 
378
 
 
379
                        UsageVector vector;
 
380
                        if (Block != null) {
 
381
                                UsageVector parent_vector = parent != null ? parent.CurrentUsageVector : null;
 
382
                                vector = new UsageVector (stype, parent_vector, Block, loc, Block.AssignableSlots);
 
383
                        } else {
 
384
                                vector = new UsageVector (stype, Parent.CurrentUsageVector, null, loc);
 
385
                        }
 
386
 
 
387
                        AddSibling (vector);
 
388
                }
 
389
 
 
390
                public abstract UsageVector CurrentUsageVector {
 
391
                        get;
 
392
                }                               
 
393
 
 
394
                // <summary>
 
395
                //   Creates a sibling of the current usage vector.
 
396
                // </summary>
 
397
                public void CreateSibling (Block block, SiblingType type)
 
398
                {
 
399
                        UsageVector vector = new UsageVector (
 
400
                                type, Parent.CurrentUsageVector, block, Location);
 
401
                        AddSibling (vector);
 
402
 
 
403
                        Report.Debug (1, "  CREATED SIBLING", CurrentUsageVector);
 
404
                }
 
405
 
 
406
                public void CreateSibling ()
 
407
                {
 
408
                        CreateSibling (null, SiblingType.Conditional);
 
409
                }
 
410
 
 
411
                protected abstract void AddSibling (UsageVector uv);
 
412
 
 
413
                protected abstract UsageVector Merge ();
 
414
 
 
415
                public UsageVector MergeChild (FlowBranching child)
 
416
                {
 
417
                        return CurrentUsageVector.MergeChild (child.Merge (), true);
 
418
                }
 
419
 
 
420
                public virtual bool CheckRethrow (Location loc)
 
421
                {
 
422
                        return Parent.CheckRethrow (loc);
 
423
                }
 
424
 
 
425
                public virtual bool AddResumePoint (ResumableStatement stmt, ResumableStatement current, out int pc)
 
426
                {
 
427
                        return Parent.AddResumePoint (stmt, current, out pc);
 
428
                }
 
429
 
 
430
                // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
 
431
                public virtual bool AddBreakOrigin (UsageVector vector, Location loc)
 
432
                {
 
433
                        return Parent.AddBreakOrigin (vector, loc);
 
434
                }
 
435
 
 
436
                // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
 
437
                public virtual bool AddContinueOrigin (UsageVector vector, Location loc)
 
438
                {
 
439
                        return Parent.AddContinueOrigin (vector, loc);
 
440
                }
 
441
 
 
442
                // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
 
443
                public virtual bool AddReturnOrigin (UsageVector vector, ExitStatement stmt)
 
444
                {
 
445
                        return Parent.AddReturnOrigin (vector, stmt);
 
446
                }
 
447
 
 
448
                // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
 
449
                public virtual bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 
450
                {
 
451
                        return Parent.AddGotoOrigin (vector, goto_stmt);
 
452
                }
 
453
 
 
454
                public bool IsAssigned (VariableInfo vi)
 
455
                {
 
456
                        return CurrentUsageVector.IsAssigned (vi, false);
 
457
                }
 
458
 
 
459
                public bool IsStructFieldAssigned (VariableInfo vi, string field_name)
 
460
                {
 
461
                        return CurrentUsageVector.IsAssigned (vi, false) || CurrentUsageVector.IsFieldAssigned (vi, field_name);
 
462
                }
 
463
 
 
464
                protected static Report Report {
 
465
                        get { return RootContext.ToplevelTypes.Compiler.Report; }
 
466
                }
 
467
 
 
468
                public void SetAssigned (VariableInfo vi)
 
469
                {
 
470
                        CurrentUsageVector.SetAssigned (vi);
 
471
                }
 
472
 
 
473
                public void SetFieldAssigned (VariableInfo vi, string name)
 
474
                {
 
475
                        CurrentUsageVector.SetFieldAssigned (vi, name);
 
476
                }
 
477
 
 
478
#if DEBUG
 
479
                public override string ToString ()
 
480
                {
 
481
                        StringBuilder sb = new StringBuilder ();
 
482
                        sb.Append (GetType ());
 
483
                        sb.Append (" (");
 
484
 
 
485
                        sb.Append (id);
 
486
                        sb.Append (",");
 
487
                        sb.Append (Type);
 
488
                        if (Block != null) {
 
489
                                sb.Append (" - ");
 
490
                                sb.Append (Block.ID);
 
491
                                sb.Append (" - ");
 
492
                                sb.Append (Block.StartLocation);
 
493
                        }
 
494
                        sb.Append (" - ");
 
495
                        // sb.Append (Siblings.Length);
 
496
                        // sb.Append (" - ");
 
497
                        sb.Append (CurrentUsageVector);
 
498
                        sb.Append (")");
 
499
                        return sb.ToString ();
 
500
                }
 
501
#endif
 
502
 
 
503
                public string Name {
 
504
                        get { return String.Format ("{0} ({1}:{2}:{3})", GetType (), id, Type, Location); }
 
505
                }
 
506
        }
 
507
 
 
508
        public class FlowBranchingBlock : FlowBranching
 
509
        {
 
510
                UsageVector sibling_list = null;
 
511
 
 
512
                public FlowBranchingBlock (FlowBranching parent, BranchingType type,
 
513
                                           SiblingType stype, Block block, Location loc)
 
514
                        : base (parent, type, stype, block, loc)
 
515
                { }
 
516
 
 
517
                public override UsageVector CurrentUsageVector {
 
518
                        get { return sibling_list; }
 
519
                }
 
520
 
 
521
                protected override void AddSibling (UsageVector sibling)
 
522
                {
 
523
                        if (sibling_list != null && sibling_list.Type == SiblingType.Block)
 
524
                                throw new InternalErrorException ("Blocks don't have sibling flow paths");
 
525
                        sibling.Next = sibling_list;
 
526
                        sibling_list = sibling;
 
527
                }
 
528
 
 
529
                public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 
530
                {
 
531
                        LabeledStatement stmt = Block == null ? null : Block.LookupLabel (goto_stmt.Target);
 
532
                        if (stmt == null)
 
533
                                return Parent.AddGotoOrigin (vector, goto_stmt);
 
534
 
 
535
                        // forward jump
 
536
                        goto_stmt.SetResolvedTarget (stmt);
 
537
                        stmt.AddUsageVector (vector);
 
538
                        return false;
 
539
                }
 
540
                
 
541
                public static void Error_UnknownLabel (Location loc, string label, Report Report)
 
542
                {
 
543
                        Report.Error(159, loc, "The label `{0}:' could not be found within the scope of the goto statement",
 
544
                                label);
 
545
                }
 
546
 
 
547
                protected override UsageVector Merge ()
 
548
                {
 
549
                        Report.Debug (2, "  MERGING SIBLINGS", Name);
 
550
                        UsageVector vector = UsageVector.MergeSiblings (sibling_list, Location);
 
551
                        Report.Debug (2, "  MERGING SIBLINGS DONE", Name, vector);
 
552
                        return vector;
 
553
                }
 
554
        }
 
555
 
 
556
        public class FlowBranchingBreakable : FlowBranchingBlock
 
557
        {
 
558
                UsageVector break_origins;
 
559
 
 
560
                public FlowBranchingBreakable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
 
561
                        : base (parent, type, stype, block, loc)
 
562
                { }
 
563
 
 
564
                public override bool AddBreakOrigin (UsageVector vector, Location loc)
 
565
                {
 
566
                        vector = vector.Clone ();
 
567
                        vector.Next = break_origins;
 
568
                        break_origins = vector;
 
569
                        return false;
 
570
                }
 
571
 
 
572
                protected override UsageVector Merge ()
 
573
                {
 
574
                        UsageVector vector = base.Merge ();
 
575
                        vector.MergeOrigins (break_origins);
 
576
                        return vector;
 
577
                }
 
578
        }
 
579
 
 
580
        public class FlowBranchingContinuable : FlowBranchingBlock
 
581
        {
 
582
                UsageVector continue_origins;
 
583
 
 
584
                public FlowBranchingContinuable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
 
585
                        : base (parent, type, stype, block, loc)
 
586
                { }
 
587
 
 
588
                public override bool AddContinueOrigin (UsageVector vector, Location loc)
 
589
                {
 
590
                        vector = vector.Clone ();
 
591
                        vector.Next = continue_origins;
 
592
                        continue_origins = vector;
 
593
                        return false;
 
594
                }
 
595
 
 
596
                protected override UsageVector Merge ()
 
597
                {
 
598
                        UsageVector vector = base.Merge ();
 
599
                        vector.MergeOrigins (continue_origins);
 
600
                        return vector;
 
601
                }
 
602
        }
 
603
 
 
604
        public class FlowBranchingLabeled : FlowBranchingBlock
 
605
        {
 
606
                LabeledStatement stmt;
 
607
                UsageVector actual;
 
608
 
 
609
                public FlowBranchingLabeled (FlowBranching parent, LabeledStatement stmt)
 
610
                        : base (parent, BranchingType.Labeled, SiblingType.Conditional, null, stmt.loc)
 
611
                {
 
612
                        this.stmt = stmt;
 
613
                        CurrentUsageVector.MergeOrigins (stmt.JumpOrigins);
 
614
                        actual = CurrentUsageVector.Clone ();
 
615
 
 
616
                        // stand-in for backward jumps
 
617
                        CurrentUsageVector.ResetBarrier ();
 
618
                }
 
619
 
 
620
                public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 
621
                {
 
622
                        if (goto_stmt.Target != stmt.Name)
 
623
                                return Parent.AddGotoOrigin (vector, goto_stmt);
 
624
 
 
625
                        // backward jump
 
626
                        goto_stmt.SetResolvedTarget (stmt);
 
627
                        actual.MergeOrigins (vector.Clone ());
 
628
 
 
629
                        return false;
 
630
                }
 
631
 
 
632
                protected override UsageVector Merge ()
 
633
                {
 
634
                        UsageVector vector = base.Merge ();
 
635
 
 
636
                        if (actual.IsUnreachable)
 
637
                                Report.Warning (162, 2, stmt.loc, "Unreachable code detected");
 
638
 
 
639
                        actual.MergeChild (vector, false);
 
640
                        return actual;
 
641
                }
 
642
        }
 
643
 
 
644
        public class FlowBranchingIterator : FlowBranchingBlock
 
645
        {
 
646
                readonly Iterator iterator;
 
647
 
 
648
                public FlowBranchingIterator (FlowBranching parent, Iterator iterator)
 
649
                        : base (parent, BranchingType.Iterator, SiblingType.Block, iterator.Block, iterator.Location)
 
650
                {
 
651
                        this.iterator = iterator;
 
652
                }
 
653
 
 
654
                public override bool AddResumePoint (ResumableStatement stmt, ResumableStatement current, out int pc)
 
655
                {
 
656
                        pc = iterator.AddResumePoint (current);
 
657
                        return false;
 
658
                }
 
659
        }
 
660
 
 
661
        public class FlowBranchingToplevel : FlowBranchingBlock
 
662
        {
 
663
                UsageVector return_origins;
 
664
 
 
665
                public FlowBranchingToplevel (FlowBranching parent, ParametersBlock stmt)
 
666
                        : base (parent, BranchingType.Toplevel, SiblingType.Conditional, stmt, stmt.loc)
 
667
                {
 
668
                }
 
669
 
 
670
                public override bool CheckRethrow (Location loc)
 
671
                {
 
672
                        Report.Error (156, loc, "A throw statement with no arguments is not allowed outside of a catch clause");
 
673
                        return false;
 
674
                }
 
675
 
 
676
                public override bool AddResumePoint (ResumableStatement stmt, ResumableStatement current, out int pc)
 
677
                {
 
678
                        throw new InternalErrorException ("A yield in a non-iterator block");
 
679
                }
 
680
 
 
681
                public override bool AddBreakOrigin (UsageVector vector, Location loc)
 
682
                {
 
683
                        Report.Error (139, loc, "No enclosing loop out of which to break or continue");
 
684
                        return false;
 
685
                }
 
686
 
 
687
                public override bool AddContinueOrigin (UsageVector vector, Location loc)
 
688
                {
 
689
                        Report.Error (139, loc, "No enclosing loop out of which to break or continue");
 
690
                        return false;
 
691
                }
 
692
 
 
693
                public override bool AddReturnOrigin (UsageVector vector, ExitStatement stmt)
 
694
                {
 
695
                        vector = vector.Clone ();
 
696
                        vector.Location = stmt.loc;
 
697
                        vector.Next = return_origins;
 
698
                        return_origins = vector;
 
699
                        return false;
 
700
                }
 
701
 
 
702
                public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 
703
                {
 
704
                        string name = goto_stmt.Target;
 
705
                        LabeledStatement s = Block.LookupLabel (name);
 
706
                        if (s != null)
 
707
                                throw new InternalErrorException ("Shouldn't get here");
 
708
 
 
709
                        if (Parent == null) {
 
710
                                Error_UnknownLabel (goto_stmt.loc, name, Report);
 
711
                                return false;
 
712
                        }
 
713
 
 
714
                        int errors = Report.Errors;
 
715
                        Parent.AddGotoOrigin (vector, goto_stmt);
 
716
                        if (errors == Report.Errors)
 
717
                                Report.Error (1632, goto_stmt.loc, "Control cannot leave the body of an anonymous method");
 
718
                        return false;
 
719
                }
 
720
 
 
721
                protected override UsageVector Merge ()
 
722
                {
 
723
                        for (UsageVector origin = return_origins; origin != null; origin = origin.Next)
 
724
                                Block.ParametersBlock.CheckOutParameters (origin);
 
725
 
 
726
                        UsageVector vector = base.Merge ();
 
727
                        Block.ParametersBlock.CheckOutParameters (vector);
 
728
                        // Note: we _do_not_ merge in the return origins
 
729
                        return vector;
 
730
                }
 
731
 
 
732
                public bool End ()
 
733
                {
 
734
                        return Merge ().IsUnreachable;
 
735
                }
 
736
        }
 
737
 
 
738
        public class FlowBranchingTryCatch : FlowBranchingBlock
 
739
        {
 
740
                readonly TryCatch tc;
 
741
 
 
742
                public FlowBranchingTryCatch (FlowBranching parent, TryCatch stmt)
 
743
                        : base (parent, BranchingType.Block, SiblingType.Try, null, stmt.loc)
 
744
                {
 
745
                        this.tc = stmt;
 
746
                }
 
747
 
 
748
                public override bool CheckRethrow (Location loc)
 
749
                {
 
750
                        return CurrentUsageVector.Next != null || Parent.CheckRethrow (loc);
 
751
                }
 
752
 
 
753
                public override bool AddResumePoint (ResumableStatement stmt, ResumableStatement current, out int pc)
 
754
                {
 
755
                        int errors = Report.Errors;
 
756
                        Parent.AddResumePoint (stmt, tc.IsTryCatchFinally ? current : tc, out pc);
 
757
                        if (errors == Report.Errors) {
 
758
                                if (stmt is AwaitStatement) {
 
759
                                        if (CurrentUsageVector.Next != null) {
 
760
                                                Report.Error (1985, stmt.loc, "The `await' operator cannot be used in the body of a catch clause");
 
761
                                        } else {
 
762
                                                this.tc.AddResumePoint (current, pc);
 
763
                                        }
 
764
                                } else {
 
765
                                        if (CurrentUsageVector.Next == null)
 
766
                                                Report.Error (1626, stmt.loc, "Cannot yield a value in the body of a try block with a catch clause");
 
767
                                        else
 
768
                                                Report.Error (1631, stmt.loc, "Cannot yield a value in the body of a catch clause");
 
769
                                }
 
770
                        }
 
771
 
 
772
                        return true;
 
773
                }
 
774
 
 
775
                public override bool AddBreakOrigin (UsageVector vector, Location loc)
 
776
                {
 
777
                        Parent.AddBreakOrigin (vector, loc);
 
778
                        tc.SomeCodeFollows ();
 
779
                        return true;
 
780
                }
 
781
 
 
782
                public override bool AddContinueOrigin (UsageVector vector, Location loc)
 
783
                {
 
784
                        Parent.AddContinueOrigin (vector, loc);
 
785
                        tc.SomeCodeFollows ();
 
786
                        return true;
 
787
                }
 
788
 
 
789
                public override bool AddReturnOrigin (UsageVector vector, ExitStatement exit_stmt)
 
790
                {
 
791
                        Parent.AddReturnOrigin (vector, exit_stmt);
 
792
                        tc.SomeCodeFollows ();
 
793
                        return true;
 
794
                }
 
795
 
 
796
                public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 
797
                {
 
798
                        Parent.AddGotoOrigin (vector, goto_stmt);
 
799
                        return true;
 
800
                }
 
801
        }
 
802
 
 
803
        public  class FlowBranchingAsync : FlowBranchingBlock
 
804
        {
 
805
                readonly AsyncInitializer async_init;
 
806
 
 
807
                public FlowBranchingAsync (FlowBranching parent, AsyncInitializer async_init)
 
808
                        : base (parent, BranchingType.Block, SiblingType.Try, null, async_init.Location)
 
809
                {
 
810
                        this.async_init = async_init;
 
811
                }
 
812
/*
 
813
                public override bool CheckRethrow (Location loc)
 
814
                {
 
815
                        return CurrentUsageVector.Next != null || Parent.CheckRethrow (loc);
 
816
                }
 
817
*/
 
818
                public override bool AddResumePoint (ResumableStatement stmt, ResumableStatement current, out int pc)
 
819
                {
 
820
                        pc = async_init.AddResumePoint (current);
 
821
                        return true;
 
822
                }
 
823
 
 
824
                public override bool AddBreakOrigin (UsageVector vector, Location loc)
 
825
                {
 
826
                        Parent.AddBreakOrigin (vector, loc);
 
827
                        return true;
 
828
                }
 
829
 
 
830
                public override bool AddContinueOrigin (UsageVector vector, Location loc)
 
831
                {
 
832
                        Parent.AddContinueOrigin (vector, loc);
 
833
                        return true;
 
834
                }
 
835
 
 
836
                public override bool AddReturnOrigin (UsageVector vector, ExitStatement exit_stmt)
 
837
                {
 
838
                        Parent.AddReturnOrigin (vector, exit_stmt);
 
839
                        return true;
 
840
                }
 
841
 
 
842
                public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 
843
                {
 
844
                        Parent.AddGotoOrigin (vector, goto_stmt);
 
845
                        return true;
 
846
                }
 
847
        }
 
848
 
 
849
        public class FlowBranchingTryFinally : FlowBranching
 
850
        {
 
851
                ExceptionStatement stmt;
 
852
                UsageVector current_vector;
 
853
                UsageVector try_vector;
 
854
                UsageVector finally_vector;
 
855
 
 
856
                abstract class SavedOrigin {
 
857
                        public readonly SavedOrigin Next;
 
858
                        public readonly UsageVector Vector;
 
859
 
 
860
                        protected SavedOrigin (SavedOrigin next, UsageVector vector)
 
861
                        {
 
862
                                Next = next;
 
863
                                Vector = vector.Clone ();
 
864
                        }
 
865
 
 
866
                        protected abstract void DoPropagateFinally (FlowBranching parent);
 
867
                        public void PropagateFinally (UsageVector finally_vector, FlowBranching parent)
 
868
                        {
 
869
                                if (finally_vector != null)
 
870
                                        Vector.MergeChild (finally_vector, false);
 
871
                                DoPropagateFinally (parent);
 
872
                        }
 
873
                }
 
874
 
 
875
                class BreakOrigin : SavedOrigin {
 
876
                        Location Loc;
 
877
                        public BreakOrigin (SavedOrigin next, UsageVector vector, Location loc)
 
878
                                : base (next, vector)
 
879
                        {
 
880
                                Loc = loc;
 
881
                        }
 
882
 
 
883
                        protected override void DoPropagateFinally (FlowBranching parent)
 
884
                        {
 
885
                                parent.AddBreakOrigin (Vector, Loc);
 
886
                        }
 
887
                }
 
888
 
 
889
                class ContinueOrigin : SavedOrigin {
 
890
                        Location Loc;
 
891
                        public ContinueOrigin (SavedOrigin next, UsageVector vector, Location loc)
 
892
                                : base (next, vector)
 
893
                        {
 
894
                                Loc = loc;
 
895
                        }
 
896
 
 
897
                        protected override void DoPropagateFinally (FlowBranching parent)
 
898
                        {
 
899
                                parent.AddContinueOrigin (Vector, Loc);
 
900
                        }
 
901
                }
 
902
 
 
903
                class ReturnOrigin : SavedOrigin {
 
904
                        public ExitStatement Stmt;
 
905
 
 
906
                        public ReturnOrigin (SavedOrigin next, UsageVector vector, ExitStatement stmt)
 
907
                                : base (next, vector)
 
908
                        {
 
909
                                Stmt = stmt;
 
910
                        }
 
911
 
 
912
                        protected override void DoPropagateFinally (FlowBranching parent)
 
913
                        {
 
914
                                parent.AddReturnOrigin (Vector, Stmt);
 
915
                        }
 
916
                }
 
917
 
 
918
                class GotoOrigin : SavedOrigin {
 
919
                        public Goto Stmt;
 
920
 
 
921
                        public GotoOrigin (SavedOrigin next, UsageVector vector, Goto stmt)
 
922
                                : base (next, vector)
 
923
                        {
 
924
                                Stmt = stmt;
 
925
                        }
 
926
 
 
927
                        protected override void DoPropagateFinally (FlowBranching parent)
 
928
                        {
 
929
                                parent.AddGotoOrigin (Vector, Stmt);
 
930
                        }
 
931
                }
 
932
 
 
933
                SavedOrigin saved_origins;
 
934
 
 
935
                public FlowBranchingTryFinally (FlowBranching parent,
 
936
                                               ExceptionStatement stmt)
 
937
                        : base (parent, BranchingType.Exception, SiblingType.Try,
 
938
                                null, stmt.loc)
 
939
                {
 
940
                        this.stmt = stmt;
 
941
                }
 
942
 
 
943
                protected override void AddSibling (UsageVector sibling)
 
944
                {
 
945
                        switch (sibling.Type) {
 
946
                        case SiblingType.Try:
 
947
                                try_vector = sibling;
 
948
                                break;
 
949
                        case SiblingType.Finally:
 
950
                                finally_vector = sibling;
 
951
                                break;
 
952
                        default:
 
953
                                throw new InvalidOperationException ();
 
954
                        }
 
955
                        current_vector = sibling;
 
956
                }
 
957
 
 
958
                public override UsageVector CurrentUsageVector {
 
959
                        get { return current_vector; }
 
960
                }
 
961
 
 
962
                public override bool CheckRethrow (Location loc)
 
963
                {
 
964
                        if (!Parent.CheckRethrow (loc))
 
965
                                return false;
 
966
                        if (finally_vector == null)
 
967
                                return true;
 
968
                        Report.Error (724, loc, "A throw statement with no arguments is not allowed inside of a finally clause nested inside of the innermost catch clause");
 
969
                        return false;
 
970
                }
 
971
 
 
972
                public override bool AddResumePoint (ResumableStatement stmt, ResumableStatement current, out int pc)
 
973
                {
 
974
                        int errors = Report.Errors;
 
975
                        Parent.AddResumePoint (stmt, this.stmt, out pc);
 
976
                        if (errors == Report.Errors) {
 
977
                                if (finally_vector == null)
 
978
                                        this.stmt.AddResumePoint (current, pc);
 
979
                                else {
 
980
                                        if (stmt is AwaitStatement) {
 
981
                                                Report.Error (1984, stmt.loc, "The `await' operator cannot be used in the body of a finally clause");
 
982
                                        } else {
 
983
                                                Report.Error (1625, stmt.loc, "Cannot yield in the body of a finally clause");
 
984
                                        }
 
985
                                }
 
986
                        }
 
987
                        return true;
 
988
                }
 
989
 
 
990
                public override bool AddBreakOrigin (UsageVector vector, Location loc)
 
991
                {
 
992
                        if (finally_vector != null) {
 
993
                                int errors = Report.Errors;
 
994
                                Parent.AddBreakOrigin (vector, loc);
 
995
                                if (errors == Report.Errors)
 
996
                                        Report.Error (157, loc, "Control cannot leave the body of a finally clause");
 
997
                        } else {
 
998
                                saved_origins = new BreakOrigin (saved_origins, vector, loc);
 
999
                        }
 
1000
 
 
1001
                        // either the loop test or a back jump will follow code
 
1002
                        stmt.SomeCodeFollows ();
 
1003
                        return true;
 
1004
                }
 
1005
 
 
1006
                public override bool AddContinueOrigin (UsageVector vector, Location loc)
 
1007
                {
 
1008
                        if (finally_vector != null) {
 
1009
                                int errors = Report.Errors;
 
1010
                                Parent.AddContinueOrigin (vector, loc);
 
1011
                                if (errors == Report.Errors)
 
1012
                                        Report.Error (157, loc, "Control cannot leave the body of a finally clause");
 
1013
                        } else {
 
1014
                                saved_origins = new ContinueOrigin (saved_origins, vector, loc);
 
1015
                        }
 
1016
 
 
1017
                        // either the loop test or a back jump will follow code
 
1018
                        stmt.SomeCodeFollows ();
 
1019
                        return true;
 
1020
                }
 
1021
 
 
1022
                public override bool AddReturnOrigin (UsageVector vector, ExitStatement exit_stmt)
 
1023
                {
 
1024
                        if (finally_vector != null) {
 
1025
                                int errors = Report.Errors;
 
1026
                                Parent.AddReturnOrigin (vector, exit_stmt);
 
1027
                                if (errors == Report.Errors)
 
1028
                                        exit_stmt.Error_FinallyClause (Report);
 
1029
                        } else {
 
1030
                                saved_origins = new ReturnOrigin (saved_origins, vector, exit_stmt);
 
1031
                        }
 
1032
 
 
1033
                        // sets ec.NeedReturnLabel()
 
1034
                        stmt.SomeCodeFollows ();
 
1035
                        return true;
 
1036
                }
 
1037
 
 
1038
                public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
 
1039
                {
 
1040
                        LabeledStatement s = current_vector.Block == null ? null : current_vector.Block.LookupLabel (goto_stmt.Target);
 
1041
                        if (s != null)
 
1042
                                throw new InternalErrorException ("Shouldn't get here");
 
1043
 
 
1044
                        if (finally_vector != null) {
 
1045
                                int errors = Report.Errors;
 
1046
                                Parent.AddGotoOrigin (vector, goto_stmt);
 
1047
                                if (errors == Report.Errors)
 
1048
                                        Report.Error (157, goto_stmt.loc, "Control cannot leave the body of a finally clause");
 
1049
                        } else {
 
1050
                                saved_origins = new GotoOrigin (saved_origins, vector, goto_stmt);
 
1051
                        }
 
1052
                        return true;
 
1053
                }
 
1054
 
 
1055
                protected override UsageVector Merge ()
 
1056
                {
 
1057
                        UsageVector vector = try_vector.Clone ();
 
1058
 
 
1059
                        if (finally_vector != null)
 
1060
                                vector.MergeChild (finally_vector, false);
 
1061
 
 
1062
                        for (SavedOrigin origin = saved_origins; origin != null; origin = origin.Next)
 
1063
                                origin.PropagateFinally (finally_vector, Parent);
 
1064
 
 
1065
                        return vector;
 
1066
                }
 
1067
        }
 
1068
 
 
1069
        // <summary>
 
1070
        //   This is used by the flow analysis code to keep track of the type of local variables.
 
1071
        //
 
1072
        //   The flow code uses a BitVector to keep track of whether a variable has been assigned
 
1073
        //   or not.  This is easy for fundamental types (int, char etc.) or reference types since
 
1074
        //   you can only assign the whole variable as such.
 
1075
        //
 
1076
        //   For structs, we also need to keep track of all its fields.  To do this, we allocate one
 
1077
        //   bit for the struct itself (it's used if you assign/access the whole struct) followed by
 
1078
        //   one bit for each of its fields.
 
1079
        //
 
1080
        //   This class computes this `layout' for each type.
 
1081
        // </summary>
 
1082
        public class TypeInfo
 
1083
        {
 
1084
                // <summary>
 
1085
                //   Total number of bits a variable of this type consumes in the flow vector.
 
1086
                // </summary>
 
1087
                public readonly int TotalLength;
 
1088
 
 
1089
                // <summary>
 
1090
                //   Number of bits the simple fields of a variable of this type consume
 
1091
                //   in the flow vector.
 
1092
                // </summary>
 
1093
                public readonly int Length;
 
1094
 
 
1095
                // <summary>
 
1096
                //   This is only used by sub-structs.
 
1097
                // </summary>
 
1098
                public readonly int Offset;
 
1099
 
 
1100
                // <summary>
 
1101
                //   If this is a struct.
 
1102
                // </summary>
 
1103
                public readonly bool IsStruct;
 
1104
 
 
1105
                // <summary>
 
1106
                //   If this is a struct, all fields which are structs theirselves.
 
1107
                // </summary>
 
1108
                public TypeInfo[] SubStructInfo;
 
1109
 
 
1110
                readonly StructInfo struct_info;
 
1111
                private static Dictionary<TypeSpec, TypeInfo> type_hash;
 
1112
 
 
1113
                static readonly TypeInfo simple_type = new TypeInfo (1);
 
1114
                
 
1115
                static TypeInfo ()
 
1116
                {
 
1117
                        Reset ();
 
1118
                }
 
1119
                
 
1120
                public static void Reset ()
 
1121
                {
 
1122
                        type_hash = new Dictionary<TypeSpec, TypeInfo> ();
 
1123
                        StructInfo.field_type_hash = new Dictionary<TypeSpec, StructInfo> ();
 
1124
                }
 
1125
 
 
1126
                TypeInfo (int totalLength)
 
1127
                {
 
1128
                        this.TotalLength = totalLength;
 
1129
                }
 
1130
                
 
1131
                TypeInfo (StructInfo struct_info, int offset)
 
1132
                {
 
1133
                        this.struct_info = struct_info;
 
1134
                        this.Offset = offset;
 
1135
                        this.Length = struct_info.Length;
 
1136
                        this.TotalLength = struct_info.TotalLength;
 
1137
                        this.SubStructInfo = struct_info.StructFields;
 
1138
                        this.IsStruct = true;
 
1139
                }
 
1140
                
 
1141
                public int GetFieldIndex (string name)
 
1142
                {
 
1143
                        if (struct_info == null)
 
1144
                                return 0;
 
1145
 
 
1146
                        return struct_info [name];
 
1147
                }
 
1148
 
 
1149
                public TypeInfo GetStructField (string name)
 
1150
                {
 
1151
                        if (struct_info == null)
 
1152
                                return null;
 
1153
 
 
1154
                        return struct_info.GetStructField (name);
 
1155
                }
 
1156
 
 
1157
                public static TypeInfo GetTypeInfo (TypeSpec type)
 
1158
                {
 
1159
                        if (!type.IsStruct)
 
1160
                                return simple_type;
 
1161
 
 
1162
                        TypeInfo info;
 
1163
                        if (type_hash.TryGetValue (type, out info))
 
1164
                                return info;
 
1165
 
 
1166
                        var struct_info = StructInfo.GetStructInfo (type);
 
1167
                        if (struct_info != null) {
 
1168
                                info = new TypeInfo (struct_info, 0);
 
1169
                        } else {
 
1170
                                info = simple_type;
 
1171
                        }
 
1172
 
 
1173
                        type_hash.Add (type, info);
 
1174
                        return info;
 
1175
                }
 
1176
 
 
1177
                // <summary>
 
1178
                //   A struct's constructor must always assign all fields.
 
1179
                //   This method checks whether it actually does so.
 
1180
                // </summary>
 
1181
                public bool IsFullyInitialized (BlockContext ec, VariableInfo vi, Location loc)
 
1182
                {
 
1183
                        if (struct_info == null)
 
1184
                                return true;
 
1185
 
 
1186
                        bool ok = true;
 
1187
                        FlowBranching branching = ec.CurrentBranching;
 
1188
                        for (int i = 0; i < struct_info.Count; i++) {
 
1189
                                var field = struct_info.Fields [i];
 
1190
 
 
1191
                                if (!branching.IsStructFieldAssigned (vi, field.Name)) {
 
1192
                                        if (field.MemberDefinition is Property.BackingField) {
 
1193
                                                ec.Report.Error (843, loc,
 
1194
                                                        "An automatically implemented property `{0}' must be fully assigned before control leaves the constructor. Consider calling the default struct contructor from a constructor initializer",
 
1195
                                                        field.GetSignatureForError ());
 
1196
                                        } else {
 
1197
                                                ec.Report.Error (171, loc,
 
1198
                                                        "Field `{0}' must be fully assigned before control leaves the constructor",
 
1199
                                                        field.GetSignatureForError ());
 
1200
                                        }
 
1201
                                        ok = false;
 
1202
                                }
 
1203
                        }
 
1204
 
 
1205
                        return ok;
 
1206
                }
 
1207
 
 
1208
                public override string ToString ()
 
1209
                {
 
1210
                        return String.Format ("TypeInfo ({0}:{1}:{2})",
 
1211
                                              Offset, Length, TotalLength);
 
1212
                }
 
1213
 
 
1214
                class StructInfo
 
1215
                {
 
1216
                        readonly List<FieldSpec> fields;
 
1217
                        public readonly TypeInfo[] StructFields;
 
1218
                        public readonly int Length;
 
1219
                        public readonly int TotalLength;
 
1220
 
 
1221
                        public static Dictionary<TypeSpec, StructInfo> field_type_hash;
 
1222
                        private Dictionary<string, TypeInfo> struct_field_hash;
 
1223
                        private Dictionary<string, int> field_hash;
 
1224
 
 
1225
                        bool InTransit;
 
1226
 
 
1227
                        //
 
1228
                        // We only need one instance per type
 
1229
                        //
 
1230
                        StructInfo (TypeSpec type)
 
1231
                        {
 
1232
                                field_type_hash.Add (type, this);
 
1233
 
 
1234
                                fields = MemberCache.GetAllFieldsForDefiniteAssignment (type);
 
1235
 
 
1236
                                struct_field_hash = new Dictionary<string, TypeInfo> ();
 
1237
                                field_hash = new Dictionary<string, int> (fields.Count);
 
1238
 
 
1239
                                StructFields = new TypeInfo[fields.Count];
 
1240
                                StructInfo[] sinfo = new StructInfo[fields.Count];
 
1241
 
 
1242
                                InTransit = true;
 
1243
 
 
1244
                                for (int i = 0; i < fields.Count; i++) {
 
1245
                                        var field = fields [i];
 
1246
 
 
1247
                                        if (field.MemberType.IsStruct)
 
1248
                                                sinfo [i] = GetStructInfo (field.MemberType);
 
1249
 
 
1250
                                        if (sinfo [i] == null)
 
1251
                                                field_hash.Add (field.Name, ++Length);
 
1252
                                        else if (sinfo [i].InTransit) {
 
1253
                                                sinfo [i] = null;
 
1254
                                                return;
 
1255
                                        }
 
1256
                                }
 
1257
 
 
1258
                                InTransit = false;
 
1259
 
 
1260
                                TotalLength = Length + 1;
 
1261
                                for (int i = 0; i < fields.Count; i++) {
 
1262
                                        var field = fields [i];
 
1263
 
 
1264
                                        if (sinfo [i] == null)
 
1265
                                                continue;
 
1266
 
 
1267
                                        field_hash.Add (field.Name, TotalLength);
 
1268
 
 
1269
                                        StructFields [i] = new TypeInfo (sinfo [i], TotalLength);
 
1270
                                        struct_field_hash.Add (field.Name, StructFields [i]);
 
1271
                                        TotalLength += sinfo [i].TotalLength;
 
1272
                                }
 
1273
                        }
 
1274
 
 
1275
                        public int Count {
 
1276
                                get {
 
1277
                                        return fields.Count;
 
1278
                                }
 
1279
                        }
 
1280
 
 
1281
                        public List<FieldSpec> Fields {
 
1282
                                get {
 
1283
                                        return fields;
 
1284
                                }
 
1285
                        }
 
1286
 
 
1287
                        public int this [string name] {
 
1288
                                get {
 
1289
                                        int val;
 
1290
                                        if (!field_hash.TryGetValue (name, out val))
 
1291
                                                return 0;
 
1292
 
 
1293
                                        return val;
 
1294
                                }
 
1295
                        }
 
1296
 
 
1297
                        public TypeInfo GetStructField (string name)
 
1298
                        {
 
1299
                                TypeInfo ti;
 
1300
                                if (struct_field_hash.TryGetValue (name, out ti))
 
1301
                                        return ti;
 
1302
 
 
1303
                                return null;
 
1304
                        }
 
1305
 
 
1306
                        public static StructInfo GetStructInfo (TypeSpec type)
 
1307
                        {
 
1308
                                if (type.BuiltinType > 0)
 
1309
                                        return null;
 
1310
 
 
1311
                                StructInfo info;
 
1312
                                if (field_type_hash.TryGetValue (type, out info))
 
1313
                                        return info;
 
1314
 
 
1315
                                return new StructInfo (type);
 
1316
                        }
 
1317
                }
 
1318
        }
 
1319
 
 
1320
        // <summary>
 
1321
        //   This is used by the flow analysis code to store information about a single local variable
 
1322
        //   or parameter.  Depending on the variable's type, we need to allocate one or more elements
 
1323
        //   in the BitVector - if it's a fundamental or reference type, we just need to know whether
 
1324
        //   it has been assigned or not, but for structs, we need this information for each of its fields.
 
1325
        // </summary>
 
1326
        public class VariableInfo {
 
1327
                readonly string Name;
 
1328
                readonly TypeInfo TypeInfo;
 
1329
 
 
1330
                // <summary>
 
1331
                //   The bit offset of this variable in the flow vector.
 
1332
                // </summary>
 
1333
                readonly int Offset;
 
1334
 
 
1335
                // <summary>
 
1336
                //   The number of bits this variable needs in the flow vector.
 
1337
                //   The first bit always specifies whether the variable as such has been assigned while
 
1338
                //   the remaining bits contain this information for each of a struct's fields.
 
1339
                // </summary>
 
1340
                public readonly int Length;
 
1341
 
 
1342
                // <summary>
 
1343
                //   If this is a parameter of local variable.
 
1344
                // </summary>
 
1345
                public readonly bool IsParameter;
 
1346
 
 
1347
                VariableInfo[] sub_info;
 
1348
 
 
1349
                VariableInfo (string name, TypeSpec type, int offset)
 
1350
                {
 
1351
                        this.Name = name;
 
1352
                        this.Offset = offset;
 
1353
                        this.TypeInfo = TypeInfo.GetTypeInfo (type);
 
1354
 
 
1355
                        Length = TypeInfo.TotalLength;
 
1356
 
 
1357
                        Initialize ();
 
1358
                }
 
1359
 
 
1360
                VariableInfo (VariableInfo parent, TypeInfo type)
 
1361
                {
 
1362
                        this.Name = parent.Name;
 
1363
                        this.TypeInfo = type;
 
1364
                        this.Offset = parent.Offset + type.Offset;
 
1365
                        this.Length = type.TotalLength;
 
1366
 
 
1367
                        this.IsParameter = parent.IsParameter;
 
1368
 
 
1369
                        Initialize ();
 
1370
                }
 
1371
 
 
1372
                protected void Initialize ()
 
1373
                {
 
1374
                        TypeInfo[] sub_fields = TypeInfo.SubStructInfo;
 
1375
                        if (sub_fields != null) {
 
1376
                                sub_info = new VariableInfo [sub_fields.Length];
 
1377
                                for (int i = 0; i < sub_fields.Length; i++) {
 
1378
                                        if (sub_fields [i] != null)
 
1379
                                                sub_info [i] = new VariableInfo (this, sub_fields [i]);
 
1380
                                }
 
1381
                        } else
 
1382
                                sub_info = new VariableInfo [0];
 
1383
                }
 
1384
 
 
1385
                public VariableInfo (LocalVariable local_info, int offset)
 
1386
                        : this (local_info.Name, local_info.Type, offset)
 
1387
                {
 
1388
                        this.IsParameter = false;
 
1389
                }
 
1390
 
 
1391
                public VariableInfo (ParametersCompiled ip, int i, int offset)
 
1392
                        : this (ip.FixedParameters [i].Name, ip.Types [i], offset)
 
1393
                {
 
1394
                        this.IsParameter = true;
 
1395
                }
 
1396
 
 
1397
                public bool IsAssigned (ResolveContext ec)
 
1398
                {
 
1399
                        return !ec.DoFlowAnalysis || ec.CurrentBranching.IsAssigned (this);
 
1400
                }
 
1401
 
 
1402
                public bool IsAssigned (MyBitVector vector)
 
1403
                {
 
1404
                        if (vector == null)
 
1405
                                return true;
 
1406
 
 
1407
                        if (vector [Offset])
 
1408
                                return true;
 
1409
 
 
1410
                        // Unless this is a struct
 
1411
                        if (!TypeInfo.IsStruct)
 
1412
                                return false;
 
1413
 
 
1414
                        //
 
1415
                        // Following case cannot be handled fully by SetStructFieldAssigned
 
1416
                        // because we may encounter following case
 
1417
                        // 
 
1418
                        // struct A { B b }
 
1419
                        // struct B { int value; }
 
1420
                        //
 
1421
                        // setting a.b.value is propagated only to B's vector and not upwards to possible parents
 
1422
                        //
 
1423
                        //
 
1424
                        // Each field must be assigned
 
1425
                        //
 
1426
                        for (int i = Offset + 1; i <= TypeInfo.Length + Offset; i++) {
 
1427
                                if (!vector[i])
 
1428
                                        return false;
 
1429
                        }
 
1430
 
 
1431
                        // Ok, now check all fields which are structs.
 
1432
                        for (int i = 0; i < sub_info.Length; i++) {
 
1433
                                VariableInfo sinfo = sub_info[i];
 
1434
                                if (sinfo == null)
 
1435
                                        continue;
 
1436
 
 
1437
                                if (!sinfo.IsAssigned (vector))
 
1438
                                        return false;
 
1439
                        }
 
1440
                        
 
1441
                        vector [Offset] = true;
 
1442
                        return true;
 
1443
                }
 
1444
 
 
1445
                public bool IsEverAssigned { get; set; }
 
1446
 
 
1447
                public bool IsStructFieldAssigned (ResolveContext ec, string name)
 
1448
                {
 
1449
                        return !ec.DoFlowAnalysis || ec.CurrentBranching.IsStructFieldAssigned (this, name);
 
1450
                }
 
1451
 
 
1452
                public bool IsFullyInitialized (BlockContext bc, Location loc)
 
1453
                {
 
1454
                        return TypeInfo.IsFullyInitialized (bc, this, loc);
 
1455
                }
 
1456
 
 
1457
                public bool IsStructFieldAssigned (MyBitVector vector, string field_name)
 
1458
                {
 
1459
                        int field_idx = TypeInfo.GetFieldIndex (field_name);
 
1460
 
 
1461
                        if (field_idx == 0)
 
1462
                                return true;
 
1463
 
 
1464
                        return vector [Offset + field_idx];
 
1465
                }
 
1466
 
 
1467
                public void SetStructFieldAssigned (ResolveContext ec, string name)
 
1468
                {
 
1469
                        if (ec.DoFlowAnalysis)
 
1470
                                ec.CurrentBranching.SetFieldAssigned (this, name);
 
1471
                }
 
1472
 
 
1473
                public void SetAssigned (ResolveContext ec)
 
1474
                {
 
1475
                        if (ec.DoFlowAnalysis)
 
1476
                                ec.CurrentBranching.SetAssigned (this);
 
1477
                }
 
1478
 
 
1479
                public void SetAssigned (MyBitVector vector)
 
1480
                {
 
1481
                        if (Length == 1)
 
1482
                                vector[Offset] = true;
 
1483
                        else
 
1484
                                vector.SetRange (Offset, Length);
 
1485
 
 
1486
                        IsEverAssigned = true;
 
1487
                }
 
1488
 
 
1489
                public void SetStructFieldAssigned (MyBitVector vector, string field_name)
 
1490
                {
 
1491
                        if (vector[Offset])
 
1492
                                return;
 
1493
 
 
1494
                        int field_idx = TypeInfo.GetFieldIndex (field_name);
 
1495
 
 
1496
                        if (field_idx == 0)
 
1497
                                return;
 
1498
 
 
1499
                        var complex_field = TypeInfo.GetStructField (field_name);
 
1500
                        if (complex_field != null) {
 
1501
                                vector.SetRange (Offset + complex_field.Offset, complex_field.TotalLength);
 
1502
                        } else {
 
1503
                                vector[Offset + field_idx] = true;
 
1504
                        }
 
1505
 
 
1506
                        IsEverAssigned = true;
 
1507
 
 
1508
                        //
 
1509
                        // Each field must be assigned
 
1510
                        //
 
1511
                        for (int i = Offset + 1; i < TypeInfo.TotalLength + Offset; i++) {
 
1512
                                if (!vector[i])
 
1513
                                        return;
 
1514
                        }
 
1515
 
 
1516
                        //
 
1517
                        // Set master struct flag to assigned when all tested struct
 
1518
                        // fields have been assigned
 
1519
                        //
 
1520
                        vector[Offset] = true;
 
1521
                }
 
1522
 
 
1523
                public VariableInfo GetStructFieldInfo (string fieldName)
 
1524
                {
 
1525
                        TypeInfo type = TypeInfo.GetStructField (fieldName);
 
1526
 
 
1527
                        if (type == null)
 
1528
                                return null;
 
1529
 
 
1530
                        return new VariableInfo (this, type);
 
1531
                }
 
1532
 
 
1533
                public override string ToString ()
 
1534
                {
 
1535
                        return String.Format ("VariableInfo ({0}:{1}:{2}:{3}:{4})",
 
1536
                                              Name, TypeInfo, Offset, Length, IsParameter);
 
1537
                }
 
1538
        }
 
1539
 
 
1540
        // <summary>
 
1541
        //   This is a special bit vector which can inherit from another bit vector doing a
 
1542
        //   copy-on-write strategy.  The inherited vector may have a smaller size than the
 
1543
        //   current one.
 
1544
        // </summary>
 
1545
        public class MyBitVector {
 
1546
                public readonly int Count;
 
1547
                public static readonly MyBitVector Empty = new MyBitVector ();
 
1548
 
 
1549
                // Invariant: vector != null => vector.Count == Count
 
1550
                // Invariant: vector == null || shared == null
 
1551
                //            i.e., at most one of 'vector' and 'shared' can be non-null.  They can both be null -- that means all-ones
 
1552
                // The object in 'shared' cannot be modified, while 'vector' can be freely modified
 
1553
                System.Collections.BitArray vector, shared;
 
1554
 
 
1555
                MyBitVector ()
 
1556
                {
 
1557
                        shared = new System.Collections.BitArray (0, false);
 
1558
                }
 
1559
 
 
1560
                public MyBitVector (MyBitVector InheritsFrom, int Count)
 
1561
                {
 
1562
                        if (InheritsFrom != null)
 
1563
                                shared = InheritsFrom.MakeShared (Count);
 
1564
 
 
1565
                        this.Count = Count;
 
1566
                }
 
1567
 
 
1568
                System.Collections.BitArray MakeShared (int new_count)
 
1569
                {
 
1570
                        // Post-condition: vector == null
 
1571
 
 
1572
                        // ensure we don't leak out dirty bits from the BitVector we inherited from
 
1573
                        if (new_count > Count &&
 
1574
                            ((shared != null && shared.Count > Count) ||
 
1575
                             (shared == null && vector == null)))
 
1576
                                initialize_vector ();
 
1577
 
 
1578
                        if (vector != null) {
 
1579
                                shared = vector;
 
1580
                                vector = null;
 
1581
                        }
 
1582
 
 
1583
                        return shared;
 
1584
                }
 
1585
 
 
1586
                // <summary>
 
1587
                //   Get/set bit `index' in the bit vector.
 
1588
                // </summary>
 
1589
                public bool this [int index] {
 
1590
                        get {
 
1591
                                if (index >= Count)
 
1592
                                        // FIXME: Disabled due to missing anonymous method flow analysis
 
1593
                                        // throw new ArgumentOutOfRangeException ();
 
1594
                                        return true; 
 
1595
 
 
1596
                                if (vector != null)
 
1597
                                        return vector [index];
 
1598
                                if (shared == null)
 
1599
                                        return true;
 
1600
                                if (index < shared.Count)
 
1601
                                        return shared [index];
 
1602
                                return false;
 
1603
                        }
 
1604
 
 
1605
                        set {
 
1606
                                // Only copy the vector if we're actually modifying it.
 
1607
                                if (this [index] != value) {
 
1608
                                        if (vector == null)
 
1609
                                                initialize_vector ();
 
1610
                                        vector [index] = value;
 
1611
                                }
 
1612
                        }
 
1613
                }
 
1614
 
 
1615
                // <summary>
 
1616
                //   Performs an `or' operation on the bit vector.  The `new_vector' may have a
 
1617
                //   different size than the current one.
 
1618
                // </summary>
 
1619
                private MyBitVector Or (MyBitVector new_vector)
 
1620
                {
 
1621
                        if (Count == 0 || new_vector.Count == 0)
 
1622
                                return this;
 
1623
 
 
1624
                        var o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
 
1625
 
 
1626
                        if (o == null) {
 
1627
                                int n = new_vector.Count;
 
1628
                                if (n < Count) {
 
1629
                                        for (int i = 0; i < n; ++i)
 
1630
                                                this [i] = true;
 
1631
                                } else {
 
1632
                                        SetAll (true);
 
1633
                                }
 
1634
                                return this;
 
1635
                        }
 
1636
 
 
1637
                        if (Count == o.Count) {
 
1638
                                if (vector == null) {
 
1639
                                        if (shared == null)
 
1640
                                                return this;
 
1641
                                        initialize_vector ();
 
1642
                                }
 
1643
                                vector.Or (o);
 
1644
                                return this;
 
1645
                        }
 
1646
 
 
1647
                        int min = o.Count;
 
1648
                        if (Count < min)
 
1649
                                min = Count;
 
1650
 
 
1651
                        for (int i = 0; i < min; i++) {
 
1652
                                if (o [i])
 
1653
                                        this [i] = true;
 
1654
                        }
 
1655
 
 
1656
                        return this;
 
1657
                }
 
1658
 
 
1659
                // <summary>
 
1660
                //   Performs an `and' operation on the bit vector.  The `new_vector' may have
 
1661
                //   a different size than the current one.
 
1662
                // </summary>
 
1663
                private MyBitVector And (MyBitVector new_vector)
 
1664
                {
 
1665
                        if (Count == 0)
 
1666
                                return this;
 
1667
 
 
1668
                        var o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
 
1669
 
 
1670
                        if (o == null) {
 
1671
                                for (int i = new_vector.Count; i < Count; ++i)
 
1672
                                        this [i] = false;
 
1673
                                return this;
 
1674
                        }
 
1675
 
 
1676
                        if (o.Count == 0) {
 
1677
                                SetAll (false);
 
1678
                                return this;
 
1679
                        }
 
1680
 
 
1681
                        if (Count == o.Count) {
 
1682
                                if (vector == null) {
 
1683
                                        if (shared == null) {
 
1684
                                                shared = new_vector.MakeShared (Count);
 
1685
                                                return this;
 
1686
                                        }
 
1687
                                        initialize_vector ();
 
1688
                                }
 
1689
                                vector.And (o);
 
1690
                                return this;
 
1691
                        }
 
1692
 
 
1693
                        int min = o.Count;
 
1694
                        if (Count < min)
 
1695
                                min = Count;
 
1696
 
 
1697
                        for (int i = 0; i < min; i++) {
 
1698
                                if (! o [i])
 
1699
                                        this [i] = false;
 
1700
                        }
 
1701
 
 
1702
                        for (int i = min; i < Count; i++)
 
1703
                                this [i] = false;
 
1704
 
 
1705
                        return this;
 
1706
                }
 
1707
 
 
1708
                public static MyBitVector operator & (MyBitVector a, MyBitVector b)
 
1709
                {
 
1710
                        if (a == b)
 
1711
                                return a;
 
1712
                        if (a == null)
 
1713
                                return b.Clone ();
 
1714
                        if (b == null)
 
1715
                                return a.Clone ();
 
1716
                        if (a.Count > b.Count)
 
1717
                                return a.Clone ().And (b);
 
1718
                        else
 
1719
                                return b.Clone ().And (a);                                      
 
1720
                }
 
1721
 
 
1722
                public static MyBitVector operator | (MyBitVector a, MyBitVector b)
 
1723
                {
 
1724
                        if (a == b)
 
1725
                                return a;
 
1726
                        if (a == null)
 
1727
                                return new MyBitVector (null, b.Count);
 
1728
                        if (b == null)
 
1729
                                return new MyBitVector (null, a.Count);
 
1730
                        if (a.Count > b.Count)
 
1731
                                return a.Clone ().Or (b);
 
1732
                        else
 
1733
                                return b.Clone ().Or (a);
 
1734
                }
 
1735
 
 
1736
                public MyBitVector Clone ()
 
1737
                {
 
1738
                        return Count == 0 ? Empty : new MyBitVector (this, Count);
 
1739
                }
 
1740
 
 
1741
                public void SetRange (int offset, int length)
 
1742
                {
 
1743
                        if (offset > Count || offset + length > Count)
 
1744
                                throw new ArgumentOutOfRangeException ("flow-analysis");
 
1745
 
 
1746
                        if (shared == null && vector == null)
 
1747
                                return;
 
1748
 
 
1749
                        int i = 0;
 
1750
                        if (shared != null) {
 
1751
                                if (offset + length <= shared.Count) {
 
1752
                                        for (; i < length; ++i)
 
1753
                                                if (!shared [i+offset])
 
1754
                                                    break;
 
1755
                                        if (i == length)
 
1756
                                                return;
 
1757
                                }
 
1758
                                initialize_vector ();
 
1759
                        }
 
1760
                        for (; i < length; ++i)
 
1761
                                vector [i+offset] = true;
 
1762
 
 
1763
                }
 
1764
 
 
1765
                public void SetAll (bool value)
 
1766
                {
 
1767
                        // Don't clobber Empty
 
1768
                        if (Count == 0)
 
1769
                                return;
 
1770
                        shared = value ? null : Empty.MakeShared (Count);
 
1771
                        vector = null;
 
1772
                }
 
1773
 
 
1774
                void initialize_vector ()
 
1775
                {
 
1776
                        // Post-condition: vector != null
 
1777
                        if (shared == null) {
 
1778
                                vector = new System.Collections.BitArray (Count, true);
 
1779
                                return;
 
1780
                        }
 
1781
 
 
1782
                        vector = new System.Collections.BitArray (shared);
 
1783
                        if (Count != vector.Count)
 
1784
                                vector.Length = Count;
 
1785
                        shared = null;
 
1786
                }
 
1787
 
 
1788
                StringBuilder Dump (StringBuilder sb)
 
1789
                {
 
1790
                        var dump = vector == null ? shared : vector;
 
1791
                        if (dump == null)
 
1792
                                return sb.Append ("/");
 
1793
                        if (dump == shared)
 
1794
                                sb.Append ("=");
 
1795
                        for (int i = 0; i < dump.Count; i++)
 
1796
                                sb.Append (dump [i] ? "1" : "0");
 
1797
                        return sb;
 
1798
                }
 
1799
 
 
1800
                public override string ToString ()
 
1801
                {
 
1802
                        return Dump (new StringBuilder ("{")).Append ("}").ToString ();
 
1803
                }
 
1804
        }
 
1805
}