//
// Author:
// Martin Baulig (martin@ximian.com)
+// Raja R Harinath (rharinath@novell.com)
//
// (C) 2001, 2002, 2003 Ximian, Inc.
//
// A loop block.
Loop,
+ // The statement embedded inside a loop
+ Embedded,
+
+ // part of a block headed by a jump target
+ Labeled,
+
// Try/Catch block.
Exception,
Switch,
// Switch section.
- SwitchSection
+ SwitchSection,
+
+ // The toplevel block of a function
+ Toplevel
}
// <summary>
Finally
}
- // <summary>
- // This is used in the control flow analysis code to specify whether the
- // current code block may return to its enclosing block before reaching
- // its end.
- // </summary>
- public enum FlowReturns : byte {
- Undefined = 0,
-
- // It can never return.
- Never,
-
- // This means that the block contains a conditional return statement
- // somewhere.
- Sometimes,
-
- // The code always returns, ie. there's an unconditional return / break
- // statement in it.
- Always
- }
-
- public sealed class Reachability
- {
- FlowReturns returns, breaks, throws, barrier;
-
- public FlowReturns Returns {
- get { return returns; }
- }
- public FlowReturns Breaks {
- get { return breaks; }
- }
- public FlowReturns Throws {
- get { return throws; }
- }
- public FlowReturns Barrier {
- get { return barrier; }
- }
- public Reachability (FlowReturns returns, FlowReturns breaks,
- FlowReturns throws, FlowReturns barrier)
- {
- this.returns = returns;
- this.breaks = breaks;
- this.throws = throws;
- this.barrier = barrier;
- }
-
- public Reachability Clone ()
- {
- return new Reachability (returns, breaks, throws, barrier);
- }
-
- // <summary>
- // Performs an `And' operation on the FlowReturns status
- // (for instance, a block only returns Always if all its siblings
- // always return).
- // </summary>
- public static FlowReturns AndFlowReturns (FlowReturns a, FlowReturns b)
- {
- if (a == FlowReturns.Undefined)
- return b;
-
- switch (a) {
- case FlowReturns.Never:
- if (b == FlowReturns.Never)
- return FlowReturns.Never;
- else
- return FlowReturns.Sometimes;
-
- case FlowReturns.Sometimes:
- return FlowReturns.Sometimes;
-
- case FlowReturns.Always:
- if (b == FlowReturns.Always)
- return FlowReturns.Always;
- else
- return FlowReturns.Sometimes;
-
- default:
- throw new ArgumentException ();
- }
- }
-
- public static FlowReturns OrFlowReturns (FlowReturns a, FlowReturns b)
- {
- if (a == FlowReturns.Undefined)
- return b;
-
- switch (a) {
- case FlowReturns.Never:
- return b;
-
- case FlowReturns.Sometimes:
- if (b == FlowReturns.Always)
- return FlowReturns.Always;
- else
- return FlowReturns.Sometimes;
-
- case FlowReturns.Always:
- return FlowReturns.Always;
-
- default:
- throw new ArgumentException ();
- }
- }
-
- public static void And (ref Reachability a, Reachability b, bool do_break)
- {
- if (a == null) {
- a = b.Clone ();
- return;
- }
-
- a.And (b, do_break);
- }
-
- public void And (Reachability b, bool do_break)
- {
- //
- // `break' does not "break" in a Switch or a LoopBlock
- //
- bool a_breaks = do_break && AlwaysBreaks;
- bool b_breaks = do_break && b.AlwaysBreaks;
-
- bool a_has_barrier, b_has_barrier;
- if (do_break) {
- //
- // This is the normal case: the code following a barrier
- // cannot be reached.
- //
- a_has_barrier = AlwaysHasBarrier;
- b_has_barrier = b.AlwaysHasBarrier;
- } else {
- //
- // Special case for Switch and LoopBlocks: we can reach the
- // code after the barrier via the `break'.
- //
- a_has_barrier = !AlwaysBreaks && AlwaysHasBarrier;
- b_has_barrier = !b.AlwaysBreaks && b.AlwaysHasBarrier;
- }
-
- bool a_unreachable = a_breaks || AlwaysThrows || a_has_barrier;
- bool b_unreachable = b_breaks || b.AlwaysThrows || b_has_barrier;
-
- //
- // Do all code paths always return ?
- //
- if (AlwaysReturns) {
- if (b.AlwaysReturns || b_unreachable)
- returns = FlowReturns.Always;
- else
- returns = FlowReturns.Sometimes;
- } else if (b.AlwaysReturns) {
- if (AlwaysReturns || a_unreachable)
- returns = FlowReturns.Always;
- else
- returns = FlowReturns.Sometimes;
- } else if (!MayReturn) {
- if (b.MayReturn)
- returns = FlowReturns.Sometimes;
- else
- returns = FlowReturns.Never;
- } else if (!b.MayReturn) {
- if (MayReturn)
- returns = FlowReturns.Sometimes;
- else
- returns = FlowReturns.Never;
- }
-
- breaks = AndFlowReturns (breaks, b.breaks);
- throws = AndFlowReturns (throws, b.throws);
- barrier = AndFlowReturns (barrier, b.barrier);
-
- if (a_unreachable && b_unreachable)
- barrier = FlowReturns.Always;
- else if (a_unreachable || b_unreachable)
- barrier = FlowReturns.Sometimes;
- else
- barrier = FlowReturns.Never;
- }
-
- public void Or (Reachability b)
- {
- returns = OrFlowReturns (returns, b.returns);
- breaks = OrFlowReturns (breaks, b.breaks);
- throws = OrFlowReturns (throws, b.throws);
- barrier = OrFlowReturns (barrier, b.barrier);
- }
-
- public static Reachability Never ()
- {
- return new Reachability (
- FlowReturns.Never, FlowReturns.Never,
- FlowReturns.Never, FlowReturns.Never);
- }
-
- public FlowReturns Reachable {
- get {
- if ((returns == FlowReturns.Always) ||
- (breaks == FlowReturns.Always) ||
- (throws == FlowReturns.Always) ||
- (barrier == FlowReturns.Always))
- return FlowReturns.Never;
- else if ((returns == FlowReturns.Never) &&
- (breaks == FlowReturns.Never) &&
- (throws == FlowReturns.Never) &&
- (barrier == FlowReturns.Never))
- return FlowReturns.Always;
- else
- return FlowReturns.Sometimes;
- }
- }
-
- public bool AlwaysBreaks {
- get { return breaks == FlowReturns.Always; }
- }
-
- public bool MayBreak {
- get { return breaks != FlowReturns.Never; }
- }
-
- public bool AlwaysReturns {
- get { return returns == FlowReturns.Always; }
- }
-
- public bool MayReturn {
- get { return returns != FlowReturns.Never; }
- }
-
- public bool AlwaysThrows {
- get { return throws == FlowReturns.Always; }
- }
-
- public bool MayThrow {
- get { return throws != FlowReturns.Never; }
- }
-
- public bool AlwaysHasBarrier {
- get { return barrier == FlowReturns.Always; }
- }
-
- public bool MayHaveBarrier {
- get { return barrier != FlowReturns.Never; }
- }
-
- public bool IsUnreachable {
- get { return Reachable == FlowReturns.Never; }
- }
-
- public void SetReturns ()
- {
- returns = FlowReturns.Always;
- }
-
- public void SetReturnsSometimes ()
- {
- returns = FlowReturns.Sometimes;
- }
-
- public void SetBreaks ()
- {
- breaks = FlowReturns.Always;
- }
-
- public void ResetBreaks ()
- {
- breaks = FlowReturns.Never;
- }
-
- public void SetThrows ()
- {
- throws = FlowReturns.Always;
- }
-
- public void SetThrowsSometimes ()
- {
- throws = FlowReturns.Sometimes;
- }
-
- public void SetBarrier ()
- {
- barrier = FlowReturns.Always;
- }
-
- public void ResetBarrier ()
- {
- barrier = FlowReturns.Never;
- }
-
- static string ShortName (FlowReturns returns)
- {
- switch (returns) {
- case FlowReturns.Never:
- return "N";
- case FlowReturns.Sometimes:
- return "S";
- default:
- return "A";
- }
- }
-
- public override string ToString ()
- {
- return String.Format ("[{0}:{1}:{2}:{3}:{4}]",
- ShortName (returns), ShortName (breaks),
- ShortName (throws), ShortName (barrier),
- ShortName (Reachable));
- }
- }
-
public static FlowBranching CreateBranching (FlowBranching parent, BranchingType type, Block block, Location loc)
{
switch (type) {
case BranchingType.Exception:
+ case BranchingType.Labeled:
+ case BranchingType.Toplevel:
throw new InvalidOperationException ();
case BranchingType.Switch:
- return new FlowBranchingSwitch (parent, block, loc);
+ return new FlowBranchingBreakable (parent, type, SiblingType.SwitchSection, block, loc);
case BranchingType.SwitchSection:
return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
return new FlowBranchingBlock (parent, type, SiblingType.Block, block, loc);
case BranchingType.Loop:
- return new FlowBranchingLoop (parent, block, loc);
+ return new FlowBranchingBreakable (parent, type, SiblingType.Conditional, block, loc);
+
+ case BranchingType.Embedded:
+ return new FlowBranchingContinuable (parent, type, SiblingType.Conditional, block, loc);
default:
return new FlowBranchingBlock (parent, type, SiblingType.Conditional, block, loc);
// </summary>
public readonly Location Location;
- // <summary>
- // If this is an infinite loop.
- // </summary>
- public bool Infinite;
-
- //
- // Private
- //
- VariableMap param_map, local_map;
+ protected VariableMap param_map, local_map;
static int next_id = 0;
int id;
// <summary>
// Start location of this branching.
// </summary>
- public readonly Location Location;
+ public Location Location;
// <summary>
// This is only valid for SwitchSection, Try, Catch and Finally.
// </summary>
public readonly Block Block;
- // <summary>
- // If this is true, then the usage vector has been modified and must be
- // merged when we're done with this branching.
- // </summary>
- public bool IsDirty;
-
// <summary>
// The number of parameters in this block.
// </summary>
// Private.
//
MyBitVector locals, parameters;
- Reachability reachability;
+ bool is_unreachable;
static int next_id = 0;
int id;
//
// Normally, you should not use any of these constructors.
//
- public UsageVector (SiblingType type, UsageVector parent,
- Block block, Location loc,
- int num_params, int num_locals)
+ public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc, int num_params, int num_locals)
{
this.Type = type;
this.Block = block;
this.CountParameters = num_params;
this.CountLocals = num_locals;
- if (parent != null) {
- if (num_locals > 0)
- locals = new MyBitVector (parent.locals, CountLocals);
-
- if (num_params > 0)
- parameters = new MyBitVector (parent.parameters, num_params);
+ locals = num_locals == 0
+ ? MyBitVector.Empty
+ : new MyBitVector (parent == null ? MyBitVector.Empty : parent.locals, num_locals);
- reachability = parent.Reachability.Clone ();
- } else {
- if (num_locals > 0)
- locals = new MyBitVector (null, CountLocals);
-
- if (num_params > 0)
- parameters = new MyBitVector (null, num_params);
+ parameters = num_params == 0
+ ? MyBitVector.Empty
+ : new MyBitVector (parent == null ? MyBitVector.Empty : parent.parameters, num_params);
- reachability = Reachability.Never ();
- }
+ if (parent != null)
+ is_unreachable = parent.is_unreachable;
id = ++next_id;
+
}
- public UsageVector (SiblingType type, UsageVector parent,
- Block block, Location loc)
- : this (type, parent, block, loc,
- parent.CountParameters, parent.CountLocals)
+ public UsageVector (SiblingType type, UsageVector parent, Block block, Location loc)
+ : this (type, parent, block, loc, parent.CountParameters, parent.CountLocals)
{ }
- public UsageVector (MyBitVector parameters, MyBitVector locals,
- Reachability reachability, Block block,
- Location loc)
+ private UsageVector (MyBitVector parameters, MyBitVector locals, bool is_unreachable, Block block, Location loc)
{
this.Type = SiblingType.Block;
this.Location = loc;
this.Block = block;
- this.reachability = reachability;
+ this.is_unreachable = is_unreachable;
+
this.parameters = parameters;
this.locals = locals;
id = ++next_id;
+
}
// <summary>
// </summary>
public UsageVector Clone ()
{
- UsageVector retval = new UsageVector (
- Type, null, Block, Location,
- CountParameters, CountLocals);
+ UsageVector retval = new UsageVector (Type, null, Block, Location, CountParameters, CountLocals);
- if (retval.locals != null)
- retval.locals = locals.Clone ();
-
- if (parameters != null)
- retval.parameters = parameters.Clone ();
-
- retval.reachability = reachability.Clone ();
+ retval.locals = locals.Clone ();
+ retval.parameters = parameters.Clone ();
+ retval.is_unreachable = is_unreachable;
return retval;
}
- public bool IsAssigned (VariableInfo var)
+ public bool IsAssigned (VariableInfo var, bool ignoreReachability)
{
- if (!var.IsParameter && Reachability.IsUnreachable)
+ if (!ignoreReachability && !var.IsParameter && IsUnreachable)
return true;
return var.IsAssigned (var.IsParameter ? parameters : locals);
public void SetAssigned (VariableInfo var)
{
- if (!var.IsParameter && Reachability.IsUnreachable)
+ if (!var.IsParameter && IsUnreachable)
return;
- IsDirty = true;
var.SetAssigned (var.IsParameter ? parameters : locals);
}
public bool IsFieldAssigned (VariableInfo var, string name)
{
- if (!var.IsParameter && Reachability.IsUnreachable)
+ if (!var.IsParameter && IsUnreachable)
return true;
return var.IsFieldAssigned (var.IsParameter ? parameters : locals, name);
public void SetFieldAssigned (VariableInfo var, string name)
{
- if (!var.IsParameter && Reachability.IsUnreachable)
+ if (!var.IsParameter && IsUnreachable)
return;
- IsDirty = true;
var.SetFieldAssigned (var.IsParameter ? parameters : locals, name);
}
- public Reachability Reachability {
- get {
- return reachability;
- }
+ public bool IsUnreachable {
+ get { return is_unreachable; }
}
- public void Return ()
+ public void ResetBarrier ()
{
- if (!reachability.IsUnreachable) {
- IsDirty = true;
- reachability.SetReturns ();
- }
+ is_unreachable = false;
}
- public void Break ()
+ public void Goto ()
{
- if (!reachability.IsUnreachable) {
- IsDirty = true;
- reachability.SetBreaks ();
- }
+ is_unreachable = true;
}
- public void Throw ()
+ public static UsageVector MergeSiblings (UsageVector sibling_list, Location loc)
{
- if (!reachability.IsUnreachable) {
- IsDirty = true;
- reachability.SetThrows ();
+ if (sibling_list.Next == null)
+ return sibling_list;
+
+ MyBitVector locals = null;
+ MyBitVector parameters = null;
+ bool is_unreachable = sibling_list.is_unreachable;
+
+ if (!sibling_list.IsUnreachable) {
+ locals &= sibling_list.locals;
+ parameters &= sibling_list.parameters;
}
- }
- public void Goto ()
- {
- if (!reachability.IsUnreachable) {
- IsDirty = true;
- reachability.SetBarrier ();
+ for (UsageVector child = sibling_list.Next; child != null; child = child.Next) {
+ is_unreachable &= child.is_unreachable;
+
+ if (!child.IsUnreachable) {
+ locals &= child.locals;
+ parameters &= child.parameters;
+ }
}
+
+ return new UsageVector (parameters, locals, is_unreachable, null, loc);
}
// <summary>
// Merges a child branching.
// </summary>
- public UsageVector MergeChild (FlowBranching branching)
+ public UsageVector MergeChild (UsageVector child, bool overwrite)
{
- UsageVector result = branching.Merge ();
-
- Report.Debug (2, " MERGING CHILD", this, branching, IsDirty,
- result.ParameterVector, result.LocalVector,
- result.Reachability, reachability, Type);
-
- Reachability new_r = result.Reachability;
-
- if (branching.Type == BranchingType.Loop) {
- bool may_leave_loop = new_r.MayBreak;
- new_r.ResetBreaks ();
-
- if (branching.Infinite && !may_leave_loop) {
- if (new_r.Returns == FlowReturns.Sometimes) {
- // If we're an infinite loop and do not break,
- // the code after the loop can never be reached.
- // However, if we may return from the loop,
- // then we do always return (or stay in the
- // loop forever).
- new_r.SetReturns ();
- }
-
- new_r.SetBarrier ();
- }
+ Report.Debug (2, " MERGING CHILD EFFECTS", this, child, Type);
- if (may_leave_loop)
- new_r.ResetBarrier ();
- } else if (branching.Type == BranchingType.Switch) {
- if (new_r.MayBreak || new_r.MayReturn)
- new_r.ResetBarrier ();
-
- new_r.ResetBreaks ();
- }
+ bool new_isunr = child.is_unreachable;
//
// We've now either reached the point after the branching or we will
// we need to look at (see above).
//
- if ((Type == SiblingType.SwitchSection) && !new_r.IsUnreachable) {
+ if ((Type == SiblingType.SwitchSection) && !new_isunr) {
Report.Error (163, Location,
"Control cannot fall through from one " +
"case label to another");
- return result;
+ return child;
}
- if (locals != null && result.LocalVector != null)
- locals.Or (result.LocalVector);
-
- if (result.ParameterVector != null)
- parameters.Or (result.ParameterVector);
+ locals |= child.locals;
+ parameters |= child.parameters;
- if ((branching.Type == BranchingType.Block) && branching.Block.Implicit)
- reachability = new_r.Clone ();
+ if (overwrite)
+ is_unreachable = new_isunr;
else
- reachability.Or (new_r);
-
- Report.Debug (2, " MERGING CHILD DONE", this, result,
- new_r, reachability);
-
- IsDirty = true;
-
- return result;
- }
-
- protected void MergeFinally (FlowBranching branching, UsageVector f_origins,
- MyBitVector f_params)
- {
- for (UsageVector vector = f_origins; vector != null; vector = vector.Next) {
- MyBitVector temp_params = f_params.Clone ();
- temp_params.Or (vector.Parameters);
- }
- }
-
- public void MergeFinally (FlowBranching branching, UsageVector f_vector,
- UsageVector f_origins)
- {
- if (parameters != null) {
- if (f_vector != null) {
- MergeFinally (branching, f_origins, f_vector.Parameters);
- MyBitVector.Or (ref parameters, f_vector.ParameterVector);
- } else
- MergeFinally (branching, f_origins, parameters);
- }
-
- if (f_vector != null && f_vector.LocalVector != null)
- MyBitVector.Or (ref locals, f_vector.LocalVector);
- }
-
- // <summary>
- // Tells control flow analysis that the current code position may be reached with
- // a forward jump from any of the origins listed in `origin_vectors' which is a
- // list of UsageVectors.
- //
- // This is used when resolving forward gotos - in the following example, the
- // variable `a' is uninitialized in line 8 becase this line may be reached via
- // the goto in line 4:
- //
- // 1 int a;
- //
- // 3 if (something)
- // 4 goto World;
- //
- // 6 a = 5;
- //
- // 7 World:
- // 8 Console.WriteLine (a);
- //
- // </summary>
- public void MergeJumpOrigins (UsageVector o_vectors)
- {
- Report.Debug (1, " MERGING JUMP ORIGINS", this);
-
- reachability = Reachability.Never ();
-
- if (o_vectors == null) {
- reachability.SetBarrier ();
- return;
- }
-
- bool first = true;
-
- for (UsageVector vector = o_vectors; vector != null;
- vector = vector.Next) {
- Report.Debug (1, " MERGING JUMP ORIGIN", vector,
- first, locals, vector.Locals);
-
- if (first) {
- if (locals != null && vector.Locals != null)
- locals.Or (vector.locals);
-
- if (parameters != null)
- parameters.Or (vector.parameters);
- first = false;
- } else {
- if (locals != null)
- locals.And (vector.locals);
- if (parameters != null)
- parameters.And (vector.parameters);
- }
-
- Reachability.And (ref reachability, vector.Reachability, true);
-
- Report.Debug (1, " MERGING JUMP ORIGIN #1", vector);
- }
-
- Report.Debug (1, " MERGING JUMP ORIGINS DONE", this);
- }
-
- // <summary>
- // This is used at the beginning of a finally block if there were
- // any return statements in the try block or one of the catch blocks.
- // </summary>
- public void MergeFinallyOrigins (UsageVector f_origins)
- {
- Report.Debug (1, " MERGING FINALLY ORIGIN", this);
+ is_unreachable |= new_isunr;
- reachability = Reachability.Never ();
-
- for (UsageVector vector = f_origins; vector != null; vector = vector.Next) {
- Report.Debug (1, " MERGING FINALLY ORIGIN", vector);
-
- if (parameters != null)
- parameters.And (vector.parameters);
-
- Reachability.And (ref reachability, vector.Reachability, true);
- }
-
- Report.Debug (1, " MERGING FINALLY ORIGIN DONE", this);
+ return child;
}
- public void MergeBreakOrigins (FlowBranching branching, UsageVector o_vectors)
+ public void MergeOrigins (UsageVector o_vectors)
{
Report.Debug (1, " MERGING BREAK ORIGINS", this);
if (o_vectors == null)
return;
- bool first = branching.Infinite;
-
- for (UsageVector vector = o_vectors; vector != null;
- vector = vector.Next) {
- Report.Debug (1, " MERGING BREAK ORIGIN", vector, first);
-
- if (first) {
- if (locals != null && vector.Locals != null)
- locals.Or (vector.locals);
-
- if (parameters != null)
- parameters.Or (vector.parameters);
- first = false;
- } else {
- if (locals != null && vector.Locals != null)
- locals.And (vector.locals);
- if (parameters != null)
- parameters.And (vector.parameters);
- }
-
- reachability.And (vector.Reachability, false);
- }
-
- Report.Debug (1, " MERGING BREAK ORIGINS DONE", this);
- }
-
- public void CheckOutParameters (FlowBranching branching)
- {
- if (parameters != null)
- branching.CheckOutParameters (parameters, branching.Location);
- }
-
- // <summary>
- // Performs an `or' operation on the locals and the parameters.
- // </summary>
- public void Or (UsageVector new_vector)
- {
- IsDirty = true;
- locals.Or (new_vector.locals);
- if (parameters != null)
- parameters.Or (new_vector.parameters);
- }
-
- // <summary>
- // Performs an `and' operation on the locals.
- // </summary>
- public void AndLocals (UsageVector new_vector)
- {
- IsDirty = true;
- locals.And (new_vector.locals);
- }
-
- public bool HasParameters {
- get {
- return parameters != null;
- }
- }
-
- public bool HasLocals {
- get {
- return locals != null;
- }
- }
-
- // <summary>
- // Returns a deep copy of the parameters.
- // </summary>
- public MyBitVector Parameters {
- get {
- if (parameters != null)
- return parameters.Clone ();
- else
- return null;
- }
- }
-
- // <summary>
- // Returns a deep copy of the locals.
- // </summary>
- public MyBitVector Locals {
- get {
+ if (IsUnreachable) {
if (locals != null)
- return locals.Clone ();
- else
- return null;
+ locals.SetAll (true);
+ if (parameters != null)
+ parameters.SetAll (true);
}
- }
- public MyBitVector ParameterVector {
- get {
- return parameters;
+ for (UsageVector vector = o_vectors; vector != null; vector = vector.Next) {
+ Report.Debug (1, " MERGING BREAK ORIGIN", vector);
+ if (vector.IsUnreachable)
+ continue;
+ locals &= vector.locals;
+ parameters &= vector.parameters;
+ is_unreachable &= vector.is_unreachable;
}
- }
- public MyBitVector LocalVector {
- get {
- return locals;
- }
+ Report.Debug (1, " MERGING BREAK ORIGINS DONE", this);
}
//
public override string ToString ()
{
- StringBuilder sb = new StringBuilder ();
-
- sb.Append ("Vector (");
- sb.Append (Type);
- sb.Append (",");
- sb.Append (id);
- sb.Append (",");
- sb.Append (IsDirty);
- sb.Append (",");
- sb.Append (reachability);
- if (parameters != null) {
- sb.Append (" - ");
- sb.Append (parameters);
- }
- sb.Append (" - ");
- sb.Append (locals);
- sb.Append (")");
-
- return sb.ToString ();
+ return String.Format ("Vector ({0},{1},{2}-{3}-{4})", Type, id, is_unreachable, parameters, locals);
}
}
protected abstract void AddSibling (UsageVector uv);
- public virtual LabeledStatement LookupLabel (string name, Location loc)
- {
- if (Parent != null)
- return Parent.LookupLabel (name, loc);
-
- Report.Error (
- 159, loc,
- "No such label `" + name + "' in this scope");
- return null;
- }
-
- public abstract void Label (UsageVector origin_vectors);
-
- // <summary>
- // Check whether all `out' parameters have been assigned.
- // </summary>
- public void CheckOutParameters (MyBitVector parameters, Location loc)
- {
- for (int i = 0; i < param_map.Count; i++) {
- VariableInfo var = param_map [i];
-
- if (var == null)
- continue;
-
- if (var.IsAssigned (parameters))
- continue;
-
- Report.Error (177, loc, "The out parameter `{0}' must be assigned to before control leaves the current method",
- var.Name);
- }
- }
-
- protected UsageVector Merge (UsageVector sibling_list)
- {
- if (sibling_list.Next == null)
- return sibling_list;
-
- MyBitVector locals = null;
- MyBitVector parameters = null;
-
- Reachability reachability = null;
-
- Report.Debug (2, " MERGING SIBLINGS", this, Name);
-
- for (UsageVector child = sibling_list; child != null; child = child.Next) {
- bool do_break = (Type != BranchingType.Switch) &&
- (Type != BranchingType.Loop);
-
- Report.Debug (2, " MERGING SIBLING ", child,
- child.ParameterVector, child.LocalVector,
- reachability, child.Reachability, do_break);
-
- Reachability.And (ref reachability, child.Reachability, do_break);
-
- // A local variable is initialized after a flow branching if it
- // has been initialized in all its branches which do neither
- // always return or always throw an exception.
- //
- // If a branch may return, but does not always return, then we
- // can treat it like a never-returning branch here: control will
- // only reach the code position after the branching if we did not
- // return here.
- //
- // It's important to distinguish between always and sometimes
- // returning branches here:
- //
- // 1 int a;
- // 2 if (something) {
- // 3 return;
- // 4 a = 5;
- // 5 }
- // 6 Console.WriteLine (a);
- //
- // The if block in lines 3-4 always returns, so we must not look
- // at the initialization of `a' in line 4 - thus it'll still be
- // uninitialized in line 6.
- //
- // On the other hand, the following is allowed:
- //
- // 1 int a;
- // 2 if (something)
- // 3 a = 5;
- // 4 else
- // 5 return;
- // 6 Console.WriteLine (a);
- //
- // Here, `a' is initialized in line 3 and we must not look at
- // line 5 since it always returns.
- //
- bool do_break_2 = (child.Type != SiblingType.Block) &&
- (child.Type != SiblingType.SwitchSection);
- bool always_throws = (child.Type != SiblingType.Try) &&
- child.Reachability.AlwaysThrows;
- bool unreachable = always_throws ||
- (do_break_2 && child.Reachability.AlwaysBreaks) ||
- child.Reachability.AlwaysReturns ||
- child.Reachability.AlwaysHasBarrier;
-
- Report.Debug (2, " MERGING SIBLING #1", reachability,
- Type, child.Type, child.Reachability.IsUnreachable,
- do_break_2, always_throws, unreachable);
-
- if (!unreachable && (child.LocalVector != null))
- MyBitVector.And (ref locals, child.LocalVector);
-
- // An `out' parameter must be assigned in all branches which do
- // not always throw an exception.
- if ((child.ParameterVector != null) && !child.Reachability.AlwaysThrows)
- MyBitVector.And (ref parameters, child.ParameterVector);
-
- Report.Debug (2, " MERGING SIBLING #2", parameters, locals);
- }
-
- if (reachability == null)
- reachability = Reachability.Never ();
-
- Report.Debug (2, " MERGING SIBLINGS DONE", parameters, locals,
- reachability, Infinite);
-
- return new UsageVector (
- parameters, locals, reachability, null, Location);
- }
-
protected abstract UsageVector Merge ();
// <summary>
// </summary>
public UsageVector MergeChild (FlowBranching child)
{
- return CurrentUsageVector.MergeChild (child);
+ bool overwrite = child.Type == BranchingType.Labeled ||
+ (child.Type == BranchingType.Block && child.Block.Implicit);
+ Report.Debug (2, " MERGING CHILD", this, child);
+ UsageVector result = CurrentUsageVector.MergeChild (child.Merge (), overwrite);
+ Report.Debug (2, " MERGING CHILD DONE", this, result);
+ return result;
}
- // <summary>
- // Does the toplevel merging.
- // </summary>
- public Reachability MergeTopBlock ()
- {
- if ((Type != BranchingType.Block) || (Block == null))
- throw new NotSupportedException ();
-
- UsageVector vector = new UsageVector (
- SiblingType.Block, null, Block, Location,
- param_map.Length, local_map.Length);
-
- UsageVector result = vector.MergeChild (this);
-
- Report.Debug (4, "MERGE TOP BLOCK", Location, vector, result.Reachability);
-
- if ((vector.Reachability.Throws != FlowReturns.Always) &&
- (vector.Reachability.Barrier != FlowReturns.Always))
- CheckOutParameters (vector.Parameters, Location);
-
- return result.Reachability;
- }
-
- //
- // Checks whether we're in a `try' block.
- //
- public virtual bool InTryOrCatch (bool is_return)
- {
- if ((Block != null) && Block.IsDestructor)
- return true;
- else if (!is_return &&
- ((Type == BranchingType.Loop) || (Type == BranchingType.Switch)))
- return false;
- else if (Parent != null)
- return Parent.InTryOrCatch (is_return);
- else
- return false;
- }
-
- public virtual bool InTryWithCatch ()
- {
- if (Parent != null)
- return Parent.InTryWithCatch ();
- return false;
- }
-
- public virtual bool InLoop ()
+ public virtual bool InTryWithCatch ()
{
- if (Type == BranchingType.Loop)
- return true;
- else if (Parent != null)
- return Parent.InLoop ();
- else
- return false;
+ return Parent.InTryWithCatch ();
}
- public virtual bool InSwitch ()
+ // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
+ public virtual bool AddBreakOrigin (UsageVector vector, Location loc)
{
- if (Type == BranchingType.Switch)
- return true;
- else if (Parent != null)
- return Parent.InSwitch ();
- else
- return false;
+ return Parent.AddBreakOrigin (vector, loc);
}
- public virtual bool BreakCrossesTryCatchBoundary ()
+ // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
+ public virtual bool AddContinueOrigin (UsageVector vector, Location loc)
{
- if ((Type == BranchingType.Loop) || (Type == BranchingType.Switch))
- return false;
- else if (Parent != null)
- return Parent.BreakCrossesTryCatchBoundary ();
- else
- return false;
+ return Parent.AddContinueOrigin (vector, loc);
}
- public virtual void AddFinallyVector (UsageVector vector)
+ // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
+ public virtual bool AddReturnOrigin (UsageVector vector, Location loc)
{
- if (Parent != null)
- Parent.AddFinallyVector (vector);
- else if ((Block == null) || !Block.IsDestructor)
- throw new NotSupportedException ();
+ return Parent.AddReturnOrigin (vector, loc);
}
- public virtual void AddBreakVector (UsageVector vector)
+ // returns true if we crossed an unwind-protected region (try/catch/finally, lock, using, ...)
+ public virtual bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
{
- if (Parent != null)
- Parent.AddBreakVector (vector);
- else if ((Block == null) || !Block.IsDestructor)
- throw new NotSupportedException ();
+ return Parent.AddGotoOrigin (vector, goto_stmt);
}
public virtual void StealFinallyClauses (ref ArrayList list)
{
- if (Parent != null)
- Parent.StealFinallyClauses (ref list);
+ Parent.StealFinallyClauses (ref list);
}
public bool IsAssigned (VariableInfo vi)
{
- return CurrentUsageVector.IsAssigned (vi);
+ return CurrentUsageVector.IsAssigned (vi, false);
}
public bool IsFieldAssigned (VariableInfo vi, string field_name)
{
- if (CurrentUsageVector.IsAssigned (vi))
- return true;
-
- return CurrentUsageVector.IsFieldAssigned (vi, field_name);
+ return CurrentUsageVector.IsAssigned (vi, false) || CurrentUsageVector.IsFieldAssigned (vi, field_name);
}
public void SetAssigned (VariableInfo vi)
}
public string Name {
- get {
- return String.Format ("{0} ({1}:{2}:{3})",
- GetType (), id, Type, Location);
- }
+ get { return String.Format ("{0} ({1}:{2}:{3})", GetType (), id, Type, Location); }
}
}
sibling_list = sibling;
}
- public override LabeledStatement LookupLabel (string name, Location loc)
- {
- if (Block == null)
- return base.LookupLabel (name, loc);
-
- LabeledStatement s = Block.LookupLabel (name);
- if (s != null)
- return s;
-
- return base.LookupLabel (name, loc);
- }
-
- public override void Label (UsageVector origin_vectors)
+ public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
{
- if (!CurrentUsageVector.Reachability.IsUnreachable) {
- UsageVector vector = CurrentUsageVector.Clone ();
- vector.Next = origin_vectors;
- origin_vectors = vector;
- }
+ LabeledStatement stmt = Block == null ? null : Block.LookupLabel (goto_stmt.Target);
+ if (stmt == null)
+ return Parent.AddGotoOrigin (vector, goto_stmt);
- CurrentUsageVector.MergeJumpOrigins (origin_vectors);
+ // forward jump
+ goto_stmt.SetResolvedTarget (stmt);
+ stmt.AddUsageVector (vector);
+ return false;
}
protected override UsageVector Merge ()
{
- return Merge (sibling_list);
+ Report.Debug (2, " MERGING SIBLINGS", Name);
+ UsageVector vector = UsageVector.MergeSiblings (sibling_list, Location);
+ Report.Debug (2, " MERGING SIBLINGS DONE", Name, vector);
+ return vector;
}
}
- public class FlowBranchingLoop : FlowBranchingBlock
+ public class FlowBranchingBreakable : FlowBranchingBlock
{
UsageVector break_origins;
- public FlowBranchingLoop (FlowBranching parent, Block block, Location loc)
- : base (parent, BranchingType.Loop, SiblingType.Conditional, block, loc)
+ public FlowBranchingBreakable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
+ : base (parent, type, stype, block, loc)
{ }
- public override void AddBreakVector (UsageVector vector)
+ public override bool AddBreakOrigin (UsageVector vector, Location loc)
{
vector = vector.Clone ();
vector.Next = break_origins;
break_origins = vector;
+ return false;
}
protected override UsageVector Merge ()
{
UsageVector vector = base.Merge ();
-
- vector.MergeBreakOrigins (this, break_origins);
-
+ vector.MergeOrigins (break_origins);
return vector;
}
}
- public class FlowBranchingSwitch : FlowBranchingBlock
+ public class FlowBranchingContinuable : FlowBranchingBlock
{
- UsageVector break_origins;
+ UsageVector continue_origins;
- public FlowBranchingSwitch (FlowBranching parent, Block block, Location loc)
- : base (parent, BranchingType.Switch, SiblingType.SwitchSection, block, loc)
+ public FlowBranchingContinuable (FlowBranching parent, BranchingType type, SiblingType stype, Block block, Location loc)
+ : base (parent, type, stype, block, loc)
{ }
- public override void AddBreakVector (UsageVector vector)
+ public override bool AddContinueOrigin (UsageVector vector, Location loc)
{
vector = vector.Clone ();
- vector.Next = break_origins;
- break_origins = vector;
+ vector.Next = continue_origins;
+ continue_origins = vector;
+ return false;
+ }
+
+ protected override UsageVector Merge ()
+ {
+ UsageVector vector = base.Merge ();
+ vector.MergeOrigins (continue_origins);
+ return vector;
+ }
+ }
+
+ public class FlowBranchingLabeled : FlowBranchingBlock
+ {
+ LabeledStatement stmt;
+ UsageVector actual;
+
+ public FlowBranchingLabeled (FlowBranching parent, LabeledStatement stmt)
+ : base (parent, BranchingType.Labeled, SiblingType.Conditional, null, stmt.loc)
+ {
+ this.stmt = stmt;
+ CurrentUsageVector.MergeOrigins (stmt.JumpOrigins);
+ actual = CurrentUsageVector.Clone ();
+
+ // stand-in for backward jumps
+ CurrentUsageVector.ResetBarrier ();
+ }
+
+ public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
+ {
+ if (goto_stmt.Target != stmt.Name)
+ return Parent.AddGotoOrigin (vector, goto_stmt);
+
+ // backward jump
+ goto_stmt.SetResolvedTarget (stmt);
+ actual.MergeOrigins (vector.Clone ());
+
+ return false;
}
protected override UsageVector Merge ()
{
UsageVector vector = base.Merge ();
- vector.MergeBreakOrigins (this, break_origins);
+ if (actual.IsUnreachable)
+ Report.Warning (162, 2, stmt.loc, "Unreachable code detected");
+
+ actual.MergeChild (vector, false);
+ return actual;
+ }
+ }
+
+ public class FlowBranchingToplevel : FlowBranchingBlock
+ {
+ UsageVector return_origins;
+
+ public FlowBranchingToplevel (FlowBranching parent, ToplevelBlock stmt)
+ : base (parent, BranchingType.Toplevel, SiblingType.Conditional, stmt, stmt.loc)
+ {
+ }
+
+ // <summary>
+ // Check whether all `out' parameters have been assigned.
+ // </summary>
+ void CheckOutParameters (UsageVector vector, Location loc)
+ {
+ if (vector.IsUnreachable)
+ return;
+ for (int i = 0; i < param_map.Count; i++) {
+ VariableInfo var = param_map [i];
+
+ if (var == null)
+ continue;
+
+ if (vector.IsAssigned (var, false))
+ continue;
+
+ Report.Error (177, loc, "The out parameter `{0}' must be assigned to before control leaves the current method",
+ var.Name);
+ }
+ }
+
+ public override bool InTryWithCatch ()
+ {
+ return false;
+ }
+
+ public override bool AddBreakOrigin (UsageVector vector, Location loc)
+ {
+ Report.Error (139, loc, "No enclosing loop out of which to break or continue");
+ return false;
+ }
+
+ public override bool AddContinueOrigin (UsageVector vector, Location loc)
+ {
+ Report.Error (139, loc, "No enclosing loop out of which to break or continue");
+ return false;
+ }
+
+ public override bool AddReturnOrigin (UsageVector vector, Location loc)
+ {
+ vector = vector.Clone ();
+ vector.Location = loc;
+ vector.Next = return_origins;
+ return_origins = vector;
+ return false;
+ }
+
+ public override void StealFinallyClauses (ref ArrayList list)
+ {
+ // nothing to do
+ }
+
+ public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
+ {
+ string name = goto_stmt.Target;
+ LabeledStatement s = Block.LookupLabel (name);
+ if (s != null)
+ throw new InternalErrorException ("Shouldn't get here");
+
+ if (Parent == null) {
+ Report.Error (159, goto_stmt.loc, "No such label `{0}' in this scope", name);
+ return false;
+ }
+
+ int errors = Report.Errors;
+ Parent.AddGotoOrigin (vector, goto_stmt);
+ if (errors == Report.Errors)
+ Report.Error (1632, goto_stmt.loc, "Control cannot leave the body of an anonymous method");
+ return false;
+ }
+
+ protected override UsageVector Merge ()
+ {
+ for (UsageVector origin = return_origins; origin != null; origin = origin.Next)
+ CheckOutParameters (origin, origin.Location);
+ UsageVector vector = base.Merge ();
+ CheckOutParameters (vector, Block.loc);
+ // Note: we _do_not_ merge in the return origins
return vector;
}
+
+ public bool End ()
+ {
+ return Merge ().IsUnreachable;
+ }
}
public class FlowBranchingException : FlowBranching
UsageVector current_vector;
UsageVector catch_vectors;
UsageVector finally_vector;
- UsageVector finally_origins;
+
+ UsageVector break_origins;
+ UsageVector continue_origins;
+ UsageVector return_origins;
+ GotoOrigin goto_origins;
+
+ class GotoOrigin {
+ public GotoOrigin Next;
+ public Goto GotoStmt;
+ public UsageVector Vector;
+
+ public GotoOrigin (UsageVector vector, Goto goto_stmt, GotoOrigin next)
+ {
+ Vector = vector;
+ GotoStmt = goto_stmt;
+ Next = next;
+ }
+ }
+
bool emit_finally;
public FlowBranchingException (FlowBranching parent,
protected override void AddSibling (UsageVector sibling)
{
- if (sibling.Type == SiblingType.Try) {
- sibling.Next = catch_vectors;
- catch_vectors = sibling;
- } else if (sibling.Type == SiblingType.Catch) {
+ switch (sibling.Type) {
+ case SiblingType.Try:
+ case SiblingType.Catch:
sibling.Next = catch_vectors;
catch_vectors = sibling;
- } else if (sibling.Type == SiblingType.Finally) {
- sibling.MergeFinallyOrigins (finally_origins);
+ break;
+ case SiblingType.Finally:
finally_vector = sibling;
- } else
+ break;
+ default:
throw new InvalidOperationException ();
-
+ }
current_vector = sibling;
}
get { return current_vector; }
}
- public override bool InTryOrCatch (bool is_return)
- {
- return finally_vector == null;
- }
-
public override bool InTryWithCatch ()
{
if (finally_vector == null) {
return true;
}
- if (Parent != null)
- return Parent.InTryWithCatch ();
+ return base.InTryWithCatch ();
+ }
- return false;
+ public override bool AddBreakOrigin (UsageVector vector, Location loc)
+ {
+ vector = vector.Clone ();
+ if (finally_vector != null) {
+ vector.MergeChild (finally_vector, false);
+ int errors = Report.Errors;
+ Parent.AddBreakOrigin (vector, loc);
+ if (errors == Report.Errors)
+ Report.Error (157, loc, "Control cannot leave the body of a finally clause");
+ } else {
+ vector.Location = loc;
+ vector.Next = break_origins;
+ break_origins = vector;
+ }
+ return true;
+ }
+
+ public override bool AddContinueOrigin (UsageVector vector, Location loc)
+ {
+ vector = vector.Clone ();
+ if (finally_vector != null) {
+ vector.MergeChild (finally_vector, false);
+ int errors = Report.Errors;
+ Parent.AddContinueOrigin (vector, loc);
+ if (errors == Report.Errors)
+ Report.Error (157, loc, "Control cannot leave the body of a finally clause");
+ } else {
+ vector.Location = loc;
+ vector.Next = continue_origins;
+ continue_origins = vector;
+ }
+ return true;
}
- public override bool BreakCrossesTryCatchBoundary ()
+ public override bool AddReturnOrigin (UsageVector vector, Location loc)
{
+ vector = vector.Clone ();
+ if (finally_vector != null) {
+ vector.MergeChild (finally_vector, false);
+ int errors = Report.Errors;
+ Parent.AddReturnOrigin (vector, loc);
+ if (errors == Report.Errors)
+ Report.Error (157, loc, "Control cannot leave the body of a finally clause");
+ } else {
+ vector.Location = loc;
+ vector.Next = return_origins;
+ return_origins = vector;
+ }
return true;
}
- public override void AddFinallyVector (UsageVector vector)
+ public override bool AddGotoOrigin (UsageVector vector, Goto goto_stmt)
{
+ LabeledStatement s = current_vector.Block == null ? null : current_vector.Block.LookupLabel (goto_stmt.Target);
+ if (s != null)
+ throw new InternalErrorException ("Shouldn't get here");
+
vector = vector.Clone ();
- vector.Next = finally_origins;
- finally_origins = vector;
+ if (finally_vector != null) {
+ vector.MergeChild (finally_vector, false);
+ int errors = Report.Errors;
+ Parent.AddGotoOrigin (vector, goto_stmt);
+ if (errors == Report.Errors)
+ Report.Error (157, goto_stmt.loc, "Control cannot leave the body of a finally clause");
+ } else {
+ goto_origins = new GotoOrigin (vector, goto_stmt, goto_origins);
+ }
+ return true;
}
public override void StealFinallyClauses (ref ArrayList list)
get { return emit_finally; }
}
- public override LabeledStatement LookupLabel (string name, Location loc)
+ protected override UsageVector Merge ()
{
- if (current_vector.Block == null)
- return base.LookupLabel (name, loc);
+ Report.Debug (2, " MERGING TRY/CATCH", Name);
+ UsageVector vector = UsageVector.MergeSiblings (catch_vectors, Location);
+ Report.Debug (2, " MERGING TRY/CATCH DONE", vector);
- LabeledStatement s = current_vector.Block.LookupLabel (name);
- if (s != null)
- return s;
+ if (finally_vector != null)
+ vector.MergeChild (finally_vector, false);
- if (finally_vector != null) {
- Report.Error (157, loc,
- "Control cannot leave the body of a finally clause");
- return null;
+ for (UsageVector origin = break_origins; origin != null; origin = origin.Next) {
+ if (finally_vector != null)
+ origin.MergeChild (finally_vector, false);
+ Parent.AddBreakOrigin (origin, origin.Location);
}
- return base.LookupLabel (name, loc);
- }
-
- public override void Label (UsageVector origin_vectors)
- {
- CurrentUsageVector.MergeJumpOrigins (origin_vectors);
- }
+ for (UsageVector origin = continue_origins; origin != null; origin = origin.Next) {
+ if (finally_vector != null)
+ origin.MergeChild (finally_vector, false);
+ Parent.AddContinueOrigin (origin, origin.Location);
+ }
- protected override UsageVector Merge ()
- {
- UsageVector vector = Merge (catch_vectors);
+ for (UsageVector origin = return_origins; origin != null; origin = origin.Next) {
+ if (finally_vector != null)
+ origin.MergeChild (finally_vector, false);
+ Parent.AddReturnOrigin (origin, origin.Location);
+ }
- vector.MergeFinally (this, finally_vector, finally_origins);
+ for (GotoOrigin origin = goto_origins; origin != null; origin = origin.Next) {
+ if (finally_vector != null)
+ origin.Vector.MergeChild (finally_vector, false);
+ Parent.AddGotoOrigin (origin.Vector, origin.GotoStmt);
+ }
return vector;
}
ArrayList non_public_fields = new ArrayList ();
if (fields != null) {
- foreach (FieldMember field in fields) {
+ foreach (FieldBase field in fields) {
if ((field.ModFlags & Modifiers.STATIC) != 0)
continue;
if ((field.ModFlags & Modifiers.PUBLIC) != 0)
Fields = new FieldInfo [Count];
public_fields.CopyTo (Fields, 0);
non_public_fields.CopyTo (Fields, CountPublic);
+#if GMCS_SOURCE
+ } else if (type is GenericTypeParameterBuilder) {
+ CountPublic = CountNonPublic = Count = 0;
+
+ Fields = new FieldInfo [0];
+#endif
} else {
FieldInfo[] public_fields = type.GetFields (
BindingFlags.Instance|BindingFlags.Public);
public bool IsAssigned (MyBitVector vector)
{
+ if (vector == null)
+ return true;
+
if (vector [Offset])
return true;
// </summary>
public class MyBitVector {
public readonly int Count;
- public readonly MyBitVector InheritsFrom;
+ public static readonly MyBitVector Empty = new MyBitVector ();
- bool is_dirty;
- BitArray vector;
+ // Invariant: vector != null => vector.Count == Count
+ // Invariant: vector == null || shared == null
+ // i.e., at most one of 'vector' and 'shared' can be non-null. They can both be null -- that means all-ones
+ // The object in 'shared' cannot be modified, while 'vector' can be freely modified
+ BitArray vector, shared;
- public MyBitVector (int Count)
- : this (null, Count)
- { }
+ MyBitVector ()
+ {
+ shared = new BitArray (0, false);
+ }
public MyBitVector (MyBitVector InheritsFrom, int Count)
{
- this.InheritsFrom = InheritsFrom;
+ if (InheritsFrom != null)
+ shared = InheritsFrom.Shared;
+
this.Count = Count;
}
- // <summary>
- // Checks whether this bit vector has been modified. After setting this to true,
- // we won't use the inherited vector anymore, but our own copy of it.
- // </summary>
- public bool IsDirty {
+ // Use this accessor to get a shareable copy of the underlying BitArray representation
+ BitArray Shared {
get {
- return is_dirty;
- }
-
- set {
- if (!is_dirty)
- initialize_vector ();
+ // Post-condition: vector == null
+ if (shared == null) {
+ shared = vector;
+ vector = null;
+ }
+ return shared;
}
}
// <summary>
// Get/set bit `index' in the bit vector.
// </summary>
- public bool this [int index]
- {
+ public bool this [int index] {
get {
- if (index > Count)
+ if (index >= Count)
throw new ArgumentOutOfRangeException ();
- // We're doing a "copy-on-write" strategy here; as long
- // as nobody writes to the array, we can use our parent's
- // copy instead of duplicating the vector.
-
if (vector != null)
return vector [index];
- else if (InheritsFrom != null) {
- BitArray inherited = InheritsFrom.Vector;
-
- if (index < inherited.Count)
- return inherited [index];
- else
- return false;
- } else
- return false;
+ if (shared == null)
+ return true;
+ if (index < shared.Count)
+ return shared [index];
+ return false;
}
set {
- if (index > Count)
- throw new ArgumentOutOfRangeException ();
-
// Only copy the vector if we're actually modifying it.
-
if (this [index] != value) {
- initialize_vector ();
-
+ if (vector == null)
+ initialize_vector ();
vector [index] = value;
}
}
}
- // <summary>
- // If you explicitly convert the MyBitVector to a BitArray, you will get a deep
- // copy of the bit vector.
- // </summary>
- public static explicit operator BitArray (MyBitVector vector)
- {
- vector.initialize_vector ();
- return vector.Vector;
- }
-
// <summary>
// Performs an `or' operation on the bit vector. The `new_vector' may have a
// different size than the current one.
// </summary>
- public void Or (MyBitVector new_vector)
+ private MyBitVector Or (MyBitVector new_vector)
{
- BitArray new_array = new_vector.Vector;
+ if (Count == 0 || new_vector.Count == 0)
+ return this;
- initialize_vector ();
+ BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
- int upper;
- if (vector.Count < new_array.Count)
- upper = vector.Count;
- else
- upper = new_array.Count;
+ if (o == null) {
+ int n = new_vector.Count;
+ if (n < Count) {
+ for (int i = 0; i < n; ++i)
+ this [i] = true;
+ } else {
+ SetAll (true);
+ }
+ return this;
+ }
+
+ if (Count == o.Count) {
+ if (vector == null) {
+ if (shared == null)
+ return this;
+ initialize_vector ();
+ }
+ vector.Or (o);
+ return this;
+ }
+
+ int min = o.Count;
+ if (Count < min)
+ min = Count;
+
+ for (int i = 0; i < min; i++) {
+ if (o [i])
+ this [i] = true;
+ }
- for (int i = 0; i < upper; i++)
- vector [i] = vector [i] | new_array [i];
+ return this;
}
// <summary>
- // Perfonrms an `and' operation on the bit vector. The `new_vector' may have
+ // Performs an `and' operation on the bit vector. The `new_vector' may have
// a different size than the current one.
// </summary>
- public void And (MyBitVector new_vector)
+ private MyBitVector And (MyBitVector new_vector)
{
- BitArray new_array;
+ if (Count == 0)
+ return this;
- if (new_vector != null)
- new_array = new_vector.Vector;
- else
- new_array = new BitArray (Count, false);
+ BitArray o = new_vector.vector != null ? new_vector.vector : new_vector.shared;
+
+ if (o == null) {
+ for (int i = new_vector.Count; i < Count; ++i)
+ this [i] = false;
+ return this;
+ }
+
+ if (o.Count == 0) {
+ SetAll (false);
+ return this;
+ }
+
+ if (Count == o.Count) {
+ if (vector == null) {
+ if (shared == null) {
+ shared = new_vector.Shared;
+ return this;
+ }
+ initialize_vector ();
+ }
+ vector.And (o);
+ return this;
+ }
- initialize_vector ();
+ int min = o.Count;
+ if (Count < min)
+ min = Count;
- int lower, upper;
- if (vector.Count < new_array.Count)
- lower = upper = vector.Count;
- else {
- lower = new_array.Count;
- upper = vector.Count;
+ for (int i = 0; i < min; i++) {
+ if (! o [i])
+ this [i] = false;
}
- for (int i = 0; i < lower; i++)
- vector [i] = vector [i] & new_array [i];
+ for (int i = min; i < Count; i++)
+ this [i] = false;
- for (int i = lower; i < upper; i++)
- vector [i] = false;
+ return this;
}
- public static void And (ref MyBitVector target, MyBitVector vector)
+ public static MyBitVector operator & (MyBitVector a, MyBitVector b)
{
- if (target != null)
- target.And (vector);
+ if (a == b)
+ return a;
+ if (a == null)
+ return b.Clone ();
+ if (b == null)
+ return a.Clone ();
+ if (a.Count > b.Count)
+ return a.Clone ().And (b);
else
- target = vector.Clone ();
+ return b.Clone ().And (a);
}
- public static void Or (ref MyBitVector target, MyBitVector vector)
+ public static MyBitVector operator | (MyBitVector a, MyBitVector b)
{
- if (target != null)
- target.Or (vector);
+ if (a == b)
+ return a;
+ if (a == null)
+ return new MyBitVector (null, b.Count);
+ if (b == null)
+ return new MyBitVector (null, a.Count);
+ if (a.Count > b.Count)
+ return a.Clone ().Or (b);
else
- target = vector.Clone ();
+ return b.Clone ().Or (a);
}
- // <summary>
- // This does a deep copy of the bit vector.
- // </summary>
public MyBitVector Clone ()
{
- MyBitVector retval = new MyBitVector (Count);
-
- retval.Vector = Vector;
-
- return retval;
+ return Count == 0 ? Empty : new MyBitVector (this, Count);
}
- BitArray Vector {
- get {
- if (vector != null)
- return vector;
- else if (!is_dirty && (InheritsFrom != null))
- return InheritsFrom.Vector;
-
- initialize_vector ();
-
- return vector;
- }
-
- set {
- initialize_vector ();
-
- for (int i = 0; i < System.Math.Min (vector.Count, value.Count); i++)
- vector [i] = value [i];
- }
+ public void SetAll (bool value)
+ {
+ // Don't clobber Empty
+ if (Count == 0)
+ return;
+ shared = value ? null : Empty.Shared;
+ vector = null;
}
void initialize_vector ()
{
- if (vector != null)
+ // Post-condition: vector != null
+ if (shared == null) {
+ vector = new BitArray (Count, true);
return;
-
- vector = new BitArray (Count, false);
- if (InheritsFrom != null)
- Vector = InheritsFrom.Vector;
+ }
- is_dirty = true;
+ vector = new BitArray (shared);
+ if (Count != vector.Count)
+ vector.Length = Count;
+ shared = null;
}
- public override string ToString ()
+ StringBuilder Dump (StringBuilder sb)
{
- StringBuilder sb = new StringBuilder ("{");
-
- BitArray vector = Vector;
- if (!IsDirty)
+ BitArray dump = vector == null ? shared : vector;
+ if (dump == null)
+ return sb.Append ("/");
+ if (dump == shared)
sb.Append ("=");
- for (int i = 0; i < vector.Count; i++) {
- sb.Append (vector [i] ? "1" : "0");
- }
-
- sb.Append ("}");
- return sb.ToString ();
+ for (int i = 0; i < dump.Count; i++)
+ sb.Append (dump [i] ? "1" : "0");
+ return sb;
+ }
+
+ public override string ToString ()
+ {
+ return Dump (new StringBuilder ("{")).Append ("}").ToString ();
}
}
}