mono/mcs/class/referencesource/System.ServiceModel/System/ServiceModel/Dispatcher/QueryBranchOp.cs

//------------------------------------------------------------
// Copyright (c) Microsoft Corporation.  All rights reserved.
//------------------------------------------------------------
namespace System.ServiceModel.Dispatcher
{
    using System.Collections.Generic;
    using System.Runtime;

    abstract class JumpOpcode : Opcode
    {
        Opcode jump;

        internal JumpOpcode(OpcodeID id, Opcode jump)
            : base(id)
        {
            this.Jump = jump;
            this.flags |= OpcodeFlags.Jump;
        }

        internal Opcode Jump
        {
            get
            {
                return this.jump;
            }
            set
            {
                Fx.Assert(value.ID == OpcodeID.BlockEnd, "");
                this.AddJump((BlockEndOpcode)value);
            }
        }

        internal void AddJump(BlockEndOpcode jumpTo)
        {
            bool conditional = this.IsReachableFromConditional();
            if (conditional)
            {
                this.prev.DelinkFromConditional(this);
            }

            if (null == this.jump)
            {
                this.jump = jumpTo;
            }
            else
            {
                BranchOpcode jumpBranch;
                if (this.jump.ID == OpcodeID.Branch)
                {
                    // already a branch
                    jumpBranch = (BranchOpcode)this.jump;
                }
                else
                {
                    BlockEndOpcode currentJump = (BlockEndOpcode)this.jump;
                    jumpBranch = new BranchOpcode();
                    jumpBranch.Branches.Add(currentJump);
                    this.jump = jumpBranch;
                }
                jumpBranch.Branches.Add(jumpTo);
            }
            jumpTo.LinkJump(this);

            if (conditional && null != this.jump)
            {
                this.prev.LinkToConditional(this);
            }
        }

        internal override void Remove()
        {
            if (null == this.jump)
            {
                base.Remove();
            }
        }

        internal void RemoveJump(BlockEndOpcode jumpTo)
        {
            Fx.Assert(null != this.jump, "");

            bool conditional = this.IsReachableFromConditional();
            if (conditional)
            {
                this.prev.DelinkFromConditional(this);
            }

            if (this.jump.ID == OpcodeID.Branch)
            {
                BranchOpcode jumpBranch = (BranchOpcode)this.jump;
                jumpTo.DeLinkJump(this);
                jumpBranch.RemoveChild(jumpTo);
                if (0 == jumpBranch.Branches.Count)
                {
                    this.jump = null;
                }
            }
            else
            {
                Fx.Assert(object.ReferenceEquals(jumpTo, this.jump), "");
                jumpTo.DeLinkJump(this);
                this.jump = null;
            }

            if (conditional && null != this.jump)
            {
                this.prev.LinkToConditional(this);
            }
        }

        internal override void Trim()
        {
            if (this.jump.ID == OpcodeID.Branch)
            {
                this.jump.Trim();
            }
        }

    }

    class JumpIfOpcode : JumpOpcode
    {
        protected bool test;

        internal JumpIfOpcode(Opcode jump, bool test)
            : this(OpcodeID.JumpIfNot, jump, test)
        {
        }

        protected JumpIfOpcode(OpcodeID id, Opcode jump, bool test)
            : base(id, jump)
        {
            this.test = test;
        }

        internal bool Test
        {
            get
            {
                return this.test;
            }
        }

        internal override bool Equals(Opcode op)
        {
            if (base.Equals(op))
            {
                return (this.test == ((JumpIfOpcode)op).test);
            }

            return false;
        }

        internal override Opcode Eval(ProcessingContext context)
        {
            Fx.Assert(null != context, "");

            StackFrame arg = context.TopArg;
            for (int i = arg.basePtr; i <= arg.endPtr; ++i)
            {
                Fx.Assert(context.Values[i].IsType(ValueDataType.Boolean), "");
                if (this.test == context.Values[i].Boolean)
                {
                    // At least one result satisfies the test. Don't branch
                    return this.next;
                }
            }

            // Jump, since no result is satisfactory..
            return this.Jump;
        }

#if DEBUG_FILTER
        public override string ToString()
        {
            return string.Format("{0} {1}", base.ToString(), this.test);
        }
#endif
    }

    class ApplyBooleanOpcode : JumpIfOpcode
    {
        internal ApplyBooleanOpcode(Opcode jump, bool test)
            : this(OpcodeID.ApplyBoolean, jump, test)
        {
        }

        protected ApplyBooleanOpcode(OpcodeID id, Opcode jump, bool test)
            : base(id, jump, test)
        {
        }

        internal override Opcode Eval(ProcessingContext context)
        {
            int matchCount = this.UpdateResultMask(context);
            context.PopFrame();
            if (0 == matchCount)
            {
                return this.Jump;
            }

            return this.next;
        }

        protected int UpdateResultMask(ProcessingContext context)
        {
            StackFrame results = context.TopArg;
            StackFrame resultMask = context.SecondArg;
            Value[] values = context.Values;
            int testCount = 0;

            for (int maskIndex = resultMask.basePtr, resultIndex = results.basePtr; maskIndex <= resultMask.endPtr; ++maskIndex)
            {
                if (this.test == values[maskIndex].Boolean)
                {
                    bool boolResult = values[resultIndex].Boolean;
                    if (this.test == boolResult)
                    {
                        testCount++;
                    }
                    values[maskIndex].Boolean = boolResult;
                    ++resultIndex;
                }
            }
            return testCount;
        }

#if DEBUG_FILTER
        public override string ToString()
        {
            return string.Format("{0} {1}", base.ToString(), this.test);
        }
#endif
    }

    // 'And' booleans: test is true
    // 'Or' booleans: test is false
    class StartBooleanOpcode : Opcode
    {
        bool test;

        internal StartBooleanOpcode(bool test)
            : base(OpcodeID.StartBoolean)
        {
            this.test = test;
        }

        internal override bool Equals(Opcode op)
        {
            if (base.Equals(op))
            {
                return (((StartBooleanOpcode)op).test == this.test);
            }

            return false;
        }

        internal override Opcode Eval(ProcessingContext context)
        {
            StackFrame sequences = context.TopSequenceArg;
            Value[] values = context.Values;
            StackFrame resultMask = context.TopArg;
            Value[] sequenceBuffer = context.Sequences;

            context.PushSequenceFrame();
            for (int seqIndex = sequences.basePtr; seqIndex <= sequences.endPtr; ++seqIndex)
            {
                NodeSequence sourceSeq = sequenceBuffer[seqIndex].Sequence;
                if (sourceSeq.Count > 0)
                {
                    NodeSequenceItem[] items = sourceSeq.Items;
                    NodeSequence newSeq = null;
                    // Loop over the sequence, selecting those items for which the previous expression returned a result that
                    // matches the test value. Only those items will be processed further
                    // Note that the original position and size information is retained.
                    for (int i = resultMask.basePtr, n = 0; i <= resultMask.endPtr; ++i, ++n)
                    {
                        if (this.test == values[i].Boolean)
                        {
                            if (null == newSeq)
                            {
                                newSeq = context.CreateSequence();
                            }
                            newSeq.AddCopy(ref items[n], NodeSequence.GetContextSize(sourceSeq, n));
                        }
                        else
                        {
                            if (items[n].Last && null != newSeq)
                            {
                                newSeq.Items[newSeq.Count - 1].Last = true; // maintain nodeset boundaries...
                            }
                        }
                    }
                    context.PushSequence((null == newSeq) ? NodeSequence.Empty : newSeq);
                    newSeq = null;
                }
            }

            return this.next;
        }

#if DEBUG_FILTER
        public override string ToString()
        {
            return string.Format("{0} {1}", base.ToString(), this.test);
        }
#endif
    }

    // 'And' booleans: test is true
    // 'Or' booleans: test is false
    class EndBooleanOpcode : ApplyBooleanOpcode
    {
        internal EndBooleanOpcode(Opcode jump, bool test)
            : base(OpcodeID.EndBoolean, jump, test)
        {
        }

        internal override Opcode Eval(ProcessingContext context)
        {
            int matchCount = this.UpdateResultMask(context);
            context.PopFrame();
            context.PopSequenceFrame();
            if (0 == matchCount)
            {
                return this.Jump;
            }

            return this.next;
        }
    }

    class NoOpOpcode : Opcode
    {
        internal NoOpOpcode(OpcodeID id)
            : base(id)
        {
        }
    }

    class BlockEndOpcode : Opcode
    {
        QueryBuffer<Opcode> sourceJumps;

        internal BlockEndOpcode()
            : base(OpcodeID.BlockEnd)
        {
            this.sourceJumps = new QueryBuffer<Opcode>(1);
        }

        internal void DeLinkJump(Opcode jump)
        {
            this.sourceJumps.Remove(jump);
        }

        internal void LinkJump(Opcode jump)
        {
            this.sourceJumps.Add(jump);
        }

        internal override void Remove()
        {
            // Before we can remove this blockEnd from the query tree, we have delink all jumps to it
            while (this.sourceJumps.Count > 0)
            {
                ((JumpOpcode)this.sourceJumps[0]).RemoveJump(this);
            }
            base.Remove();
        }

    }

    class TypecastOpcode : Opcode
    {
        ValueDataType newType;
#if NO
        internal TypecastOpcode(OpcodeID opcode, ValueDataType newType)
            : base(opcode)
        {
            this.newType = newType;
        }
#endif
        internal TypecastOpcode(ValueDataType newType)
            : base(OpcodeID.Cast)
        {
            this.newType = newType;
        }

        internal override bool Equals(Opcode op)
        {
            if (base.Equals(op))
            {
                return (this.newType == ((TypecastOpcode)op).newType);
            }

            return false;
        }

        internal override Opcode Eval(ProcessingContext context)
        {
            StackFrame frame = context.TopArg;
            Value[] values = context.Values;
            for (int i = frame.basePtr; i <= frame.endPtr; ++i)
            {
                values[i].ConvertTo(context, newType);
            }

            return this.next;
        }

#if DEBUG_FILTER
        public override string ToString()
        {
            return string.Format("{0} {1}", base.ToString(), this.newType.ToString());
        }
#endif
    }

    struct BranchContext
    {
        ProcessingContext branchContext;
        ProcessingContext sourceContext;

        internal BranchContext(ProcessingContext context)
        {
            this.sourceContext = context;
            this.branchContext = null;
        }

        internal ProcessingContext Create()
        {
            if (null == this.branchContext)
            {
                this.branchContext = this.sourceContext.Clone();
            }
            else
            {
                this.branchContext.CopyFrom(this.sourceContext);
            }
            return this.branchContext;
        }

        internal void Release()
        {
            if (null != this.branchContext)
            {
                this.branchContext.Release();
            }
        }
    }

    class QueryBranch
    {
        internal Opcode branch;
        internal int id;
#if NO
        internal QueryBranch(Opcode branch)
            : this(branch, int.MinValue)
        {
        }
#endif
        internal QueryBranch(Opcode branch, int id)
        {
            this.branch = branch;
            this.id = id;
        }

        internal Opcode Branch
        {
            get
            {
                return this.branch;
            }
#if NO
            set
            {
                this.branch = value;
            }
#endif
        }

        internal int ID
        {
            get
            {
                return this.id;
            }
        }
    }

    class QueryBranchTable
    {
        int count;
        QueryBranch[] branches;

        internal QueryBranchTable()
            : this(1)
        {
        }

        internal QueryBranchTable(int capacity)
        {
            this.branches = new QueryBranch[capacity];
        }

        internal int Count
        {
            get
            {
                return this.count;
            }
        }

        internal QueryBranch this[int index]
        {
            get
            {
                return this.branches[index];
            }
        }
#if NO
        internal void Add(QueryBranch entry)
        {
            Fx.Assert(null != entry, "");
            this.InsertAt(this.count, entry);
        }
#endif
        internal void AddInOrder(QueryBranch branch)
        {
            // Insert in sorted order always
            int index;
            for (index = 0; index < this.count; ++index)
            {
                // if current node is >= key, we've found the spot
                if (this.branches[index].ID >= branch.ID)
                {
                    break;
                }
            }

            this.InsertAt(index, branch);
        }

        void Grow()
        {
            QueryBranch[] branches = new QueryBranch[this.branches.Length + 1];
            Array.Copy(this.branches, branches, this.branches.Length);
            this.branches = branches;
        }

        public int IndexOf(Opcode opcode)
        {
            for (int i = 0; i < this.count; ++i)
            {
                if (object.ReferenceEquals(opcode, this.branches[i].Branch))
                {
                    return i;
                }
            }
            return -1;
        }

        public int IndexOfID(int id)
        {
            for (int i = 0; i < this.count; ++i)
            {
                if (this.branches[i].ID == id)
                {
                    return i;
                }
            }
            return -1;
        }

#if NO
        public int IndexOfEquals(Opcode opcode)
        {
            for (int i = 0; i < this.count; ++i)
            {
                if (this.branches[i].Branch.Equals(opcode))
                {
                    return i;
                }
            }
            return -1;
        }
#endif
        internal void InsertAt(int index, QueryBranch branch)
        {
            if (this.count == this.branches.Length)
            {
                this.Grow();
            }
            if (index < this.count)
            {
                Array.Copy(this.branches, index, this.branches, index + 1, this.count - index);
            }
            this.branches[index] = branch;
            this.count++;
        }

        internal bool Remove(Opcode branch)
        {
            Fx.Assert(null != branch, "");
            int index = this.IndexOf(branch);
            if (index >= 0)
            {
                this.RemoveAt(index);
                return true;
            }

            return false;
        }

        internal void RemoveAt(int index)
        {
            Fx.Assert(index < this.count, "");
            if (index < this.count - 1)
            {
                Array.Copy(this.branches, index + 1, this.branches, index, this.count - index - 1);
            }
            else
            {
                this.branches[index] = null;
            }
            this.count--;
        }

        internal void Trim()
        {
            if (this.count < this.branches.Length)
            {
                QueryBranch[] branches = new QueryBranch[this.count];
                Array.Copy(this.branches, branches, this.count);
                this.branches = branches;
            }

            for (int i = 0; i < this.branches.Length; ++i)
            {
                if (this.branches[i] != null && this.branches[i].Branch != null)
                {
                    this.branches[i].Branch.Trim();
                }
            }
        }
    }

    class BranchOpcode : Opcode
    {
        OpcodeList branches;

        internal BranchOpcode()
            : this(OpcodeID.Branch)
        {
        }

        internal BranchOpcode(OpcodeID id)
            : base(id)
        {
            this.flags |= OpcodeFlags.Branch;
            this.branches = new OpcodeList(2);
        }

        internal OpcodeList Branches
        {
            get
            {
                return this.branches;
            }
        }

        internal override void Add(Opcode opcode)
        {
            // Add with maximum affinity.. find a similar opcode, if we can, and call its Add method
            for (int i = 0; i < this.branches.Count; ++i)
            {
                if (this.branches[i].IsEquivalentForAdd(opcode))
                {
                    this.branches[i].Add(opcode);
                    return;
                }
            }

            // Ok.. no similar opcode. Add it just like any other branch
            this.AddBranch(opcode);
        }

        internal override void AddBranch(Opcode opcode)
        {
            Fx.Assert(null != opcode, "");

            // Make sure the same opcode doesn't already exist..
            Fx.Assert(-1 == this.branches.IndexOf(opcode), "");
            this.branches.Add(opcode);
            opcode.Prev = this;

            // If this branch is in a conditional, then this new opcode must be added to that conditional..
            if (this.IsInConditional())
            {
                this.LinkToConditional(opcode);
            }
        }

        internal override void CollectXPathFilters(ICollection<MessageFilter> filters)
        {
            for (int i = 0; i < this.branches.Count; ++i)
            {
                this.branches[i].CollectXPathFilters(filters);
            }
        }

        internal override void DelinkFromConditional(Opcode child)
        {
            if (null != this.prev)
            {
                this.prev.DelinkFromConditional(child);
            }
        }
        internal override Opcode Eval(ProcessingContext context)
        {
            QueryProcessor processor = context.Processor;
            SeekableXPathNavigator contextNode = processor.ContextNode;
            int marker = processor.CounterMarker;
            long pos = contextNode.CurrentPosition;
            Opcode branch;
            int i = 0;
            int branchCount = this.branches.Count;
            try
            {
                if (context.StacksInUse)
                {
                    // If we have N branches, eval N-1 in a cloned context and the remainder in the
                    // original one
                    if (--branchCount > 0)
                    {
                        // Evaluate all but the first branch with a clone of the current context
                        // The first branch (right most) can be evaluated with the current context                        
                        BranchContext branchContext = new BranchContext(context); // struct. fast
                        for (; i < branchCount; ++i)
                        {
                            branch = this.branches[i];
                            if (0 != (branch.Flags & OpcodeFlags.Fx))
                            {
                                branch.Eval(context);
                            }
                            else
                            {
                                // This allocates a solitary context and then reuses it repeatedly
                                ProcessingContext newContext = branchContext.Create();
                                while (null != branch)
                                {
                                    branch = branch.Eval(newContext);
                                }
                            }
                            contextNode.CurrentPosition = pos;  // restore the navigator to its original position
                            processor.CounterMarker = marker;   // and the node count marker
                        }
                        branchContext.Release();
                    }

                    // Do the final branch with the existing context
                    branch = branches[i];
                    while (null != branch)
                    {
                        branch = branch.Eval(context);
                    }
                }
                else // since there is nothing on the stack, there is nothing to clone
                {
                    int nodeCountSav = context.NodeCount;
                    for (; i < branchCount; ++i)
                    {
                        branch = branches[i];
                        // Evaluate this branch
                        while (null != branch)
                        {
                            branch = branch.Eval(context);
                        }
                        // Restore the current context to its pristine state, so we can reuse it
                        context.ClearContext();
                        context.NodeCount = nodeCountSav;
                        contextNode.CurrentPosition = pos;
                        processor.CounterMarker = marker;
                    }
                }
            }
            catch (XPathNavigatorException e)
            {
                throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(branches[i]));
            }
            catch (NavigatorInvalidBodyAccessException e)
            {
                throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(branches[i]));
            }
            processor.CounterMarker = marker;

            return this.next;
        }

        internal override bool IsInConditional()
        {
            if (null != this.prev)
            {
                return this.prev.IsInConditional();
            }

            return true;
        }

        internal override void LinkToConditional(Opcode child)
        {
            if (null != this.prev)
            {
                this.prev.LinkToConditional(child);
            }
        }

        /// <summary>
        /// Loop over all branches, trying to locate one that is equal to the given opcode
        /// If the branch is a branch itself, perform the locate recursively.
        /// </summary>
        /// <param name="opcode"></param>
        /// <returns></returns>
        internal override Opcode Locate(Opcode opcode)
        {
            Fx.Assert(!opcode.TestFlag(OpcodeFlags.Branch), "");

            for (int i = 0, count = this.branches.Count; i < count; ++i)
            {
                Opcode branch = this.branches[i];
                if (branch.TestFlag(OpcodeFlags.Branch))
                {
                    // The branch is itself a branch. Since branch opcodes serve as branches in the exection
                    // path for a query, but don't comprise one of the opcodes used to actually perform it, we
                    // recursively try to locate an equivalent opcode inside the branch
                    Opcode subBranch = branch.Locate(opcode);
                    if (null != subBranch)
                    {
                        return subBranch;
                    }
                }
                else if (branch.Equals(opcode))
                {
                    return branch;
                }
            }

            return null;
        }

        internal override void Remove()
        {
            if (0 == this.branches.Count)
            {
                base.Remove();
            }
        }

        internal override void RemoveChild(Opcode opcode)
        {
            Fx.Assert(null != opcode, "");

            if (this.IsInConditional())
            {
                this.DelinkFromConditional(opcode);
            }
            this.branches.Remove(opcode);
            this.branches.Trim();
        }

        internal override void Replace(Opcode replace, Opcode with)
        {
            int i = this.branches.IndexOf(replace);
            if (i >= 0)
            {
                replace.Prev = null;
                this.branches[i] = with;
                with.Prev = this;
            }
        }

        internal override void Trim()
        {
            this.branches.Trim();
            for (int i = 0; i < this.branches.Count; ++i)
            {
                this.branches[i].Trim();
            }
        }
    }

    struct QueryBranchResult
    {
        internal QueryBranch branch;
        int valIndex;

        internal QueryBranchResult(QueryBranch branch, int valIndex)
        {
            this.branch = branch;
            this.valIndex = valIndex;
        }

        internal QueryBranch Branch
        {
            get
            {
                return this.branch;
            }
        }

        internal int ValIndex
        {
            get
            {
                return this.valIndex;
            }
        }
#if NO
        internal void Set(QueryBranch branch, int valIndex)
        {
            this.branch = branch;
            this.valIndex = valIndex;
        }
#endif
    }

    internal class QueryBranchResultSet
    {
        QueryBuffer<QueryBranchResult> results;
        QueryBranchResultSet next;
        internal static SortComparer comparer = new SortComparer();

        internal QueryBranchResultSet()
            : this(2)
        {
        }

        internal QueryBranchResultSet(int capacity)
        {
            this.results = new QueryBuffer<QueryBranchResult>(capacity);
        }

        internal int Count
        {
            get
            {
                return this.results.count;
            }
        }

        internal QueryBranchResult this[int index]
        {
            get
            {
                return this.results[index];
            }
        }

        internal QueryBranchResultSet Next
        {
            get
            {
                return this.next;
            }
            set
            {
                this.next = value;
            }
        }

        internal void Add(QueryBranch branch, int valIndex)
        {
            this.results.Add(new QueryBranchResult(branch, valIndex));
        }

        internal void Clear()
        {
            this.results.count = 0;
        }

        internal void Sort()
        {
            this.results.Sort(QueryBranchResultSet.comparer);
        }

        internal class SortComparer : IComparer<QueryBranchResult>
        {
            public bool Equals(QueryBranchResult x, QueryBranchResult y)
            {
                return x.branch.id == y.branch.id;
            }
            public int Compare(QueryBranchResult x, QueryBranchResult y)
            {
                return x.branch.id - y.branch.id;
            }

            public int GetHashCode(QueryBranchResult obj)
            {
                return obj.branch.id;
            }
        }
    }

    struct BranchMatcher
    {
        int resultCount;
        QueryBranchResultSet resultTable;

        internal BranchMatcher(int resultCount, QueryBranchResultSet resultTable)
        {
            this.resultCount = resultCount;
            this.resultTable = resultTable;
        }

        internal QueryBranchResultSet ResultTable
        {
            get
            {
                return this.resultTable;
            }
        }

        void InitResults(ProcessingContext context)
        {
            context.PushFrame();
            // Push this.resultsCount booleans onto the stack, all set to false
            context.Push(false, this.resultCount);
        }

        internal void InvokeMatches(ProcessingContext context)
        {
            Fx.Assert(null != context, "");

            switch (this.resultTable.Count)
            {
                default:
                    this.InvokeMultiMatch(context);
                    break;

                case 0:
                    break;

                case 1:
                    this.InvokeSingleMatch(context);
                    break;
            }
        }

        void InvokeMultiMatch(ProcessingContext context)
        {
            int marker = context.Processor.CounterMarker;
            BranchContext branchContext = new BranchContext(context);   // struct. quick.
            int resultTableCount = this.resultTable.Count;
            for (int i = 0; i < resultTableCount; )
            {
                QueryBranchResult result = this.resultTable[i];
                QueryBranch branch = result.Branch;
                // Branches can arbitrarily alter context stacks, rendering them unuseable to other branches. 
                // Therefore, before following a branch, we have to clone the context. Cloning is relatively efficient because
                // can avoid allocating memory in most cases. We cannot, unfortunately, avoid Array copies. 
                //
                // Optimization: 
                // We can avoid cloning altogether when we can predict that the branch does NOT tamper with the stack,
                // or does so in a predictable way. If we are sure that we can restore the stack easily after the branch
                // completes, we have no reason to copy the stack.
                ProcessingContext newContext;
                Opcode nextOpcode = branch.Branch.Next;
                if (nextOpcode.TestFlag(OpcodeFlags.NoContextCopy))
                {
                    newContext = context;
                }
                else
                {
                    newContext = branchContext.Create();
                }

                this.InitResults(newContext);

                //
                // Matches are sorted by their branch ID.
                // It is very possible that the a literal matches multiple times, especially when the value being 
                // compared is a sequence. A literal may match multiple items in a single sequence 
                // OR multiple items in multiple sequences. If there were 4 context sequences, the literal may have 
                // matched one item each in 3 of them. The branchID for that literal will be present 3 times in the
                // resultTable.
                // Sorting the matches groups them by their branch Ids. We only want to take the branch ONCE, so now we
                // iterate over all the duplicate matches..
                // result.ValIndex will give us the index of the value that was matched. Thus if the 3rd sequence 
                // matched, ValIndex == 2 (0 based)
                newContext.Values[newContext.TopArg[result.ValIndex]].Boolean = true;
                while (++i < resultTableCount)
                {
                    result = this.resultTable[i];
                    if (branch.ID == result.Branch.ID)
                    {
                        newContext.Values[newContext.TopArg[result.ValIndex]].Boolean = true;
                    }
                    else
                    {
                        break;
                    }
                }
                try
                {
                    newContext.EvalCodeBlock(nextOpcode);
                }
                catch (XPathNavigatorException e)
                {
                    throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(nextOpcode));
                }
                catch (NavigatorInvalidBodyAccessException e)
                {
                    throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(nextOpcode));
                }
                context.Processor.CounterMarker = marker;
            }
            branchContext.Release();
        }

        internal void InvokeNonMatches(ProcessingContext context, QueryBranchTable nonMatchTable)
        {
            Fx.Assert(null != context && null != nonMatchTable, "");

            int marker = context.Processor.CounterMarker;
            BranchContext branchContext = new BranchContext(context);
            int nonMatchIndex = 0;
            int matchIndex = 0;
            while (matchIndex < this.resultTable.Count && nonMatchIndex < nonMatchTable.Count)
            {
                int compare = this.resultTable[matchIndex].Branch.ID - nonMatchTable[nonMatchIndex].ID;
                if (compare > 0)
                {
                    // Nonmatch < match
                    // Invoke..
                    ProcessingContext newContext = branchContext.Create();
                    this.InvokeNonMatch(newContext, nonMatchTable[nonMatchIndex]);
                    context.Processor.CounterMarker = marker;
                    ++nonMatchIndex;
                }
                else if (0 == compare)
                {
                    ++nonMatchIndex;
                }
                else
                {
                    ++matchIndex;
                }
            }
            // Add remaining
            while (nonMatchIndex < nonMatchTable.Count)
            {
                ProcessingContext newContext = branchContext.Create();
                this.InvokeNonMatch(newContext, nonMatchTable[nonMatchIndex]);
                context.Processor.CounterMarker = marker;
                ++nonMatchIndex;
            }
            branchContext.Release();
        }

        void InvokeNonMatch(ProcessingContext context, QueryBranch branch)
        {
            context.PushFrame();
            context.Push(false, this.resultCount);
            try
            {
                context.EvalCodeBlock(branch.Branch);
            }
            catch (XPathNavigatorException e)
            {
                throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(branch.Branch));
            }
            catch (NavigatorInvalidBodyAccessException e)
            {
                throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(branch.Branch));
            }
        }

        void InvokeSingleMatch(ProcessingContext context)
        {
            int marker = context.Processor.CounterMarker;
            QueryBranchResult result = this.resultTable[0];
            this.InitResults(context);
            context.Values[context.TopArg[result.ValIndex]].Boolean = true;

            try
            {
                context.EvalCodeBlock(result.Branch.Branch.Next);
            }
            catch (XPathNavigatorException e)
            {
                throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(result.Branch.Branch.Next));
            }
            catch (NavigatorInvalidBodyAccessException e)
            {
                throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(e.Process(result.Branch.Branch.Next));
            }

            context.Processor.CounterMarker = marker;
        }

        internal void Release(ProcessingContext context)
        {
            context.Processor.ReleaseResults(this.resultTable);
        }
    }

    abstract class QueryBranchIndex
    {
        internal abstract int Count
        {
            get;
        }
        internal abstract QueryBranch this[object key]
        {
            get;
            set;
        }

        internal abstract void CollectXPathFilters(ICollection<MessageFilter> filters);

#if NO
        internal abstract IEnumerator GetEnumerator();
#endif
        internal abstract void Match(int valIndex, ref Value val, QueryBranchResultSet results);
        internal abstract void Remove(object key);

        internal abstract void Trim();
    }

    class QueryConditionalBranchOpcode : Opcode
    {
        QueryBranchTable alwaysBranches;
        QueryBranchIndex branchIndex;
        int nextID;

        internal QueryConditionalBranchOpcode(OpcodeID id, QueryBranchIndex branchIndex)
            : base(id)
        {
            Fx.Assert(null != branchIndex, "");
            this.flags |= OpcodeFlags.Branch;
            this.branchIndex = branchIndex;
            this.nextID = 0;
        }

        internal QueryBranchTable AlwaysBranches
        {
            get
            {
                if (null == this.alwaysBranches)
                {
                    this.alwaysBranches = new QueryBranchTable();
                }
                return this.alwaysBranches;
            }
        }
#if NO
        internal QueryBranchIndex BranchIndex
        {
            get
            {
                return this.branchIndex;
            }
        }
#endif
        internal override void Add(Opcode opcode)
        {
            LiteralRelationOpcode literal = this.ValidateOpcode(opcode);
            if (null == literal)
            {
                base.Add(opcode);
                return;
            }

            // Was this literal already added to the index?
            QueryBranch queryBranch = this.branchIndex[literal.Literal];
            if (null == queryBranch)
            {
                // First time. New branch
                this.nextID++;
                queryBranch = new QueryBranch(literal, this.nextID);
                literal.Prev = this;
                this.branchIndex[literal.Literal] = queryBranch;
            }
            else
            {
                Fx.Assert(!object.ReferenceEquals(queryBranch.Branch, literal), "");
                Fx.Assert(literal.ID == queryBranch.Branch.ID, "");
                // literal already exists.. but what follows the literal must be branched
                // Should never get here, but just in case
                queryBranch.Branch.Next.Add(literal.Next);
            }
            literal.Flags |= OpcodeFlags.InConditional;

            this.AddAlwaysBranch(queryBranch, literal.Next);
        }

        internal void AddAlwaysBranch(Opcode literal, Opcode next)
        {
            LiteralRelationOpcode literalOp = this.ValidateOpcode(literal);
            Fx.Assert(null != literalOp, "");
            if (null != literalOp)
            {
                this.AddAlwaysBranch(literalOp, next);
            }
        }

        // Whether or not the given literal matches, we must always take the branch rooted at 'next'
        // Add to the AlwaysBranches table if not already there..
        internal void AddAlwaysBranch(LiteralRelationOpcode literal, Opcode next)
        {
            Fx.Assert(null != literal && null != next, "");

            QueryBranch literalBranch = this.branchIndex[literal.Literal];
            Fx.Assert(null != literalBranch, "");

            this.AddAlwaysBranch(literalBranch, next);
        }

        void AddAlwaysBranch(QueryBranch literalBranch, Opcode next)
        {
            if (OpcodeID.Branch == next.ID)
            {
                BranchOpcode opcode = (BranchOpcode)next;
                OpcodeList branches = opcode.Branches;
                for (int i = 0; i < branches.Count; ++i)
                {
                    Opcode branch = branches[i];
                    if (this.IsAlwaysBranch(branch))
                    {
                        this.AlwaysBranches.AddInOrder(new QueryBranch(branch, literalBranch.ID));
                    }
                    else
                    {
                        branch.Flags |= OpcodeFlags.NoContextCopy;
                    }
                }
            }
            else
            {
                Fx.Assert(!next.TestFlag(OpcodeFlags.Branch), "");
                if (this.IsAlwaysBranch(next))
                {
                    this.AlwaysBranches.AddInOrder(new QueryBranch(next, literalBranch.ID));
                }
                else
                {
                    next.Flags |= OpcodeFlags.NoContextCopy;
                }
            }
        }

        internal virtual void CollectMatches(int valIndex, ref Value val, QueryBranchResultSet results)
        {
            this.branchIndex.Match(valIndex, ref val, results);
        }

        internal override void CollectXPathFilters(ICollection<MessageFilter> filters)
        {
            if (this.alwaysBranches != null)
            {
                for (int i = 0; i < this.alwaysBranches.Count; ++i)
                {
                    this.alwaysBranches[i].Branch.CollectXPathFilters(filters);
                }
            }

            this.branchIndex.CollectXPathFilters(filters);
        }

        internal override Opcode Eval(ProcessingContext context)
        {
            StackFrame arg = context.TopArg;
            int argCount = arg.Count;

            if (argCount > 0)
            {
                QueryBranchResultSet resultSet = context.Processor.CreateResultSet();
                BranchMatcher matcher = new BranchMatcher(argCount, resultSet);
                // Operate on values at the the top frame of the value stack
                // For each source value, find the branch that could be taken
                for (int i = 0; i < argCount; ++i)
                {
                    this.CollectMatches(i, ref context.Values[arg[i]], resultSet);
                }
                // Done with whatever we were testing equality against
                context.PopFrame();
                if (resultSet.Count > 1)
                {
                    // Sort results
                    resultSet.Sort();
                }

                // First, do non-true branches..
                if (null != this.alwaysBranches && this.alwaysBranches.Count > 0)
                {
                    matcher.InvokeNonMatches(context, this.alwaysBranches);
                }

                // Iterate through matches, invoking each matched branch
                matcher.InvokeMatches(context);

                matcher.Release(context);
            }
            else
            {
                context.PopFrame();
            }
            return this.next;
        }

        internal QueryBranch GetBranch(Opcode op)
        {
            if (op.TestFlag(OpcodeFlags.Literal))
            {
                LiteralRelationOpcode relOp = this.ValidateOpcode(op);
                if (null != relOp)
                {
                    QueryBranch branch = this.branchIndex[relOp.Literal];
                    if (null != branch && branch.Branch.ID == op.ID)
                    {
                        return branch;
                    }
                }
            }

            return null;
        }

        bool IsAlwaysBranch(Opcode next)
        {
            Fx.Assert(null != next, "");

            // Opcodes subsequent to matching literals must obviously be branched to.
            // The question is whether we should branch to the opcodes following those literals that do *not* match.
            // Naturally, the answer depends on the sort of opcode that succeeds the literal.
            //
            // If the literal is within a boolean conjunction, the succeeding opcode will either be a JumpIfNot
            // Or a BlockEnd.
            // 
            // -If the JumpIfNot is multiway, then always evaluate if it contains ANY non-result only opcodes.
            // -If JumpIfNot(False) -i.e. AND - only evaluate if the opcode succeeding the jump is NOT a result opcode.
            // -If JumpIfNot(True) - i.e. OR - always evaluate
            // 
            // -If BlockEnd - evaluate only if not followed by a result
            //
            // When branching for matching literals, we push trues onto the ValueStack corresponding to the items that 
            // matched. When branching for non-matching literals, we push ALL FALSE values... and then eval.

            // is it a the termination of a conditional?
            JumpIfOpcode jump = next as JumpIfOpcode;
            if (null != jump)
            {
                // Is the conditional JumpIfNot(False) = i.e. OR? 
                if (!jump.Test)
                {
                    return true;
                }

                // Does the conditional actually jump to anything? Should never be the case, but paranoia demands..
                Opcode jumpTo = jump.Jump;
                if (null == jumpTo)
                {
                    return false;
                }

                // Lets see where the jump will take us
                Opcode postJump;
                if (jumpTo.TestFlag(OpcodeFlags.Branch))
                {
                    // Multiway jump
                    OpcodeList branches = ((BranchOpcode)jumpTo).Branches;
                    for (int i = 0; i < branches.Count; ++i)
                    {
                        postJump = branches[i].Next;
                        if (null != postJump && !postJump.TestFlag(OpcodeFlags.Result))
                        {
                            // There is at least one jump here that leads to a non-result.
                            // For now, this dooms everybody to being branched to, whether or not their respective literals
                            // matched
                            return true;
                        }
                    }
                    return false;
                }

                // single jump
                postJump = jump.Jump.Next;
                if (null != postJump && postJump.TestFlag(OpcodeFlags.Result))
                {
                    return false;
                }

                return true;
            }

            // If the next opcode is a BlockEnd, then only bother processing if what follows the block is not a result
            if (OpcodeID.BlockEnd == next.ID)
            {
                Fx.Assert(null != next.Next, "");
                return (!next.Next.TestFlag(OpcodeFlags.Result));
            }

            // The literal is not inside a boolean conjunction
            // If the literal is not followed by a result, then we must do further processing after the branch
            return (!next.TestFlag(OpcodeFlags.Result));
        }

        /// <summary>
        /// Returns true if this branch can accept 'opcode' being added to it
        /// </summary>
        internal override bool IsEquivalentForAdd(Opcode opcode)
        {
            if (null != this.ValidateOpcode(opcode))
            {
                return true;
            }

            return base.IsEquivalentForAdd(opcode);
        }

        internal override Opcode Locate(Opcode opcode)
        {
            QueryBranch queryBranch = this.GetBranch(opcode);
            if (null != queryBranch)
            {
                return queryBranch.Branch;
            }

            return null;
        }

        internal override void Remove()
        {
            if (null == this.branchIndex || 0 == this.branchIndex.Count)
            {
                base.Remove();
            }
        }

        internal override void RemoveChild(Opcode opcode)
        {
            LiteralRelationOpcode literal = this.ValidateOpcode(opcode);
            Fx.Assert(null != literal, "");

            QueryBranch branch = this.branchIndex[literal.Literal];
            Fx.Assert(null != branch, "");
            this.branchIndex.Remove(literal.Literal);
            branch.Branch.Flags &= (~OpcodeFlags.NoContextCopy);
            if (null != this.alwaysBranches)
            {
                int removeAt = this.alwaysBranches.IndexOfID(branch.ID);
                if (removeAt >= 0)
                {
                    this.alwaysBranches.RemoveAt(removeAt);
                    if (0 == this.alwaysBranches.Count)
                    {
                        this.alwaysBranches = null;
                    }
                }
            }
        }

        internal void RemoveAlwaysBranch(Opcode opcode)
        {
            if (null == this.alwaysBranches)
            {
                return;
            }

            // Note: if the opcodes below are not in the alwaysBranches table, nothing will happen
            // So arbitrary calls are safe - just makes the removal processor slower (we'll speed it up if necessary)
            if (OpcodeID.Branch == opcode.ID)
            {
                OpcodeList branches = ((BranchOpcode)opcode).Branches;
                for (int i = 0; i < branches.Count; ++i)
                {
                    this.alwaysBranches.Remove(branches[i]);
                }
            }
            else
            {
                this.alwaysBranches.Remove(opcode);
            }
            if (0 == this.alwaysBranches.Count)
            {
                this.alwaysBranches = null;
            }
        }

        internal override void Replace(Opcode replace, Opcode with)
        {
            throw DiagnosticUtility.ExceptionUtility.ThrowHelperCritical(new NotImplementedException(SR.GetString(SR.FilterUnexpectedError)));
        }

        internal override void Trim()
        {
            if (this.alwaysBranches != null)
            {
                this.alwaysBranches.Trim();
            }
            this.branchIndex.Trim();
        }

        internal virtual LiteralRelationOpcode ValidateOpcode(Opcode opcode)
        {
            return opcode as LiteralRelationOpcode;
        }
    }
}