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

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

    internal class TrieSegmentComparer : IComparer<TrieSegment>
    {
        public int Compare(TrieSegment t1, TrieSegment t2)
        {
            return ((int)t1.FirstChar) - ((int)t2.FirstChar);
        }

        public bool Equals(TrieSegment t1, TrieSegment t2)
        {
            return t1.FirstChar == t2.FirstChar;
        }

        public int GetHashCode(TrieSegment t)
        {
            return t.GetHashCode();
        }
    }

    internal class TrieSegmentKeyComparer : IItemComparer<char, TrieSegment>
    {
        public int Compare(char c, TrieSegment t)
        {
            return ((int)c) - ((int)t.FirstChar);
        }
    }

    internal class TrieSegment
    {
        static readonly TrieSegmentKeyComparer SegKeyComparer = new TrieSegmentKeyComparer();
        static readonly TrieSegmentComparer SegComparer = new TrieSegmentComparer();

        SortedBuffer<TrieSegment, TrieSegmentComparer> children;
        QueryBranch data;
        TrieSegment parent; // segment's parent
        char segmentFirstChar; // this segment's first character
        string segmentTail; // this segment's tail
        int segmentLength;

        internal TrieSegment()
            : this(char.MinValue)
        {
        }

        internal TrieSegment(char firstChar)
            : this(firstChar, string.Empty)
        {
        }

        internal TrieSegment(char firstChar, string segmentTail)
        {
            Fx.Assert(null != segmentTail, "");
            this.SetSegment(firstChar, segmentTail);
            this.children = new SortedBuffer<TrieSegment, TrieSegmentComparer>(SegComparer);
        }

        internal TrieSegment(string sourceSegment, int offset, int length)
        {
            Fx.Assert(null != sourceSegment && length > 0, "");
            this.SetSegmentString(sourceSegment, offset, length);
            this.children = new SortedBuffer<TrieSegment, TrieSegmentComparer>(SegComparer);
        }

        internal bool CanMerge
        {
            get
            {
                return (null == this.data && 1 == this.children.Count);
            }
        }

        internal bool CanPrune
        {
            get
            {
                return (null == this.data && 0 == this.children.Count);
            }
        }
#if NO
        internal int ChildCount
        {
            get
            {
                return this.children.Count;
            }
        }
#endif
        internal void CollectXPathFilters(ICollection<MessageFilter> filters)
        {
            if (this.data != null)
            {
                (this.data).Branch.CollectXPathFilters(filters);
            }

            for (int i = 0; i < this.children.Count; ++i)
            {
                this.children[i].CollectXPathFilters(filters);
            }
        }

        internal QueryBranch Data
        {
            get
            {
                return this.data;
            }
            set
            {
                this.data = value;
            }
        }

        internal char FirstChar
        {
            get
            {
                return this.segmentFirstChar;
            }
        }

        internal bool HasChildren
        {
            get
            {
                return (this.children.Count > 0);
            }
        }

        internal int Length
        {
            get
            {
                //return (this.segmentFirstChar == char.MinValue) ? 0 : this.segmentTail.Length + 1;
                return this.segmentLength;
            }
        }
#if NO
        internal string Tail
        {
            get
            {
                return this.segmentTail;
            }
        }
#endif
        internal TrieSegment AddChild(TrieSegment segment)
        {
            Fx.Assert(null != segment, "");

            this.children.Insert(segment);
            segment.parent = this;

            return segment;
        }
#if NO
        internal TrieSegment[] CopyChildren()
        {
            return this.children.ToArray();
        }
#endif
        internal int FindDivergence(string compareString, int offset, int length)
        {
            Fx.Assert(null != compareString && length > 0, "");

            if (compareString[offset] != this.segmentFirstChar)
            {
                return 0;
            }

            --length;
            ++offset;

            int charCount = (length <= this.segmentTail.Length) ? length : this.segmentTail.Length;
            for (int iSegment = 0, iCompare = offset; iSegment < charCount; ++iSegment, ++iCompare)
            {
                if (compareString[iCompare] != this.segmentTail[iSegment])
                {
                    return iSegment + 1;
                }
            }

            if (length < this.segmentTail.Length)
            {
                return length + 1;
            }

            return -1;
        }

        internal TrieSegment GetChild(int index)
        {
            Fx.Assert(this.HasChildren, "");
            return this.children[index];
        }

        /// <summary>
        /// Return the index of the child such that matchString == the string segment stored at that child
        /// i.e. matchString[0] == child.segmentFirstChar and matchString[1 -> length] == child.segmentTail[0 -> length]
        /// </summary>
        internal int GetChildPosition(string matchString, int offset, int length)
        {
            Fx.Assert(null != matchString, "");

            if (this.HasChildren)
            {
                char matchChar = matchString[offset];
                int tailLength = length - 1;
                int tailOffset = offset + 1;
                int index = this.children.IndexOfKey(matchChar, SegKeyComparer);
                if (index >= 0)
                {
                    TrieSegment child = this.children[index];
                    if (tailLength >= child.segmentTail.Length && (0 == child.segmentTail.Length || 0 == string.CompareOrdinal(matchString, tailOffset, child.segmentTail, 0, child.segmentTail.Length)))
                    {
                        return index;
                    }
                }
            }
            return -1;
        }

        /// <summary>
        /// Return the index of the child such that child.segmentFirstChar == ch
        /// </summary>
        internal int GetChildPosition(char ch)
        {
            return this.children.IndexOfKey(ch, SegKeyComparer);
        }

        internal int IndexOf(TrieSegment segment)
        {
            return this.children.IndexOf(segment);
        }

        internal void MergeChild(TrieSegment segment)
        {
            int childIndex = this.IndexOf(segment);
            if (childIndex > -1)
            {
                this.MergeChild(childIndex);
            }
        }

        /// <summary>
        /// If the child node has no data associated with it and but one child of its own, it can be
        /// merged with the child, reducing the path by 1
        /// </summary>
        internal void MergeChild(int childIndex)
        {
            Fx.Assert(this.HasChildren, "");

            TrieSegment child = this.children[childIndex];
            if (child.CanMerge)
            {
                TrieSegment grandchild = child.children[0];

                StringBuilder newTail = new StringBuilder();
                newTail.Append(child.segmentTail);
                newTail.Append(grandchild.segmentFirstChar);
                newTail.Append(grandchild.segmentTail);

                grandchild.SetSegment(child.segmentFirstChar, newTail.ToString());
                grandchild.parent = this;

                this.children.Exchange(child, grandchild);
                child.parent = null;
            }
        }

        internal void Remove()
        {
            if (null != this.parent)
            {
                this.parent.RemoveChild(this);
            }
        }

        /// <summary>
        /// Remove the child == segment, and prune the tree
        /// </summary>
        void RemoveChild(TrieSegment segment)
        {
            Fx.Assert(null != segment, "");
            int childIndex = this.IndexOf(segment);
            if (childIndex >= 0)
            {
                this.RemoveChild(childIndex, true);
            }
        }

        /// <summary>
        /// Remove the child at index childIndex.
        /// If fixupTree is true, traverse back up the tree, removing prunable nodes or merging mergable nodes
        /// as appropriate
        /// </summary>
        internal void RemoveChild(int childIndex, bool fixupTree)
        {
            Fx.Assert(this.HasChildren && childIndex >= 0, "");

            TrieSegment child = this.children[childIndex];

            child.parent = null;
            this.children.RemoveAt(childIndex);

            if (0 == this.children.Count)
            {
                if (fixupTree && this.CanPrune)
                {
                    this.Remove();
                }
            }
            else
            {
                if (fixupTree && this.CanMerge && null != this.parent)
                {
                    this.parent.MergeChild(this);
                }
            }
        }

        void SetSegment(char firstChar, string segmentTail)
        {
            this.segmentFirstChar = firstChar;
            this.segmentTail = segmentTail;
            this.segmentLength = firstChar == char.MinValue ? 0 : 1 + segmentTail.Length;
        }

        void SetSegmentString(string segmentString, int offset, int length)
        {
            this.segmentFirstChar = segmentString[offset];
            if (length > 1)
            {
                this.segmentTail = segmentString.Substring(offset + 1, length - 1);
            }
            else
            {
                this.segmentTail = string.Empty;
            }
            this.segmentLength = length;
        }

        TrieSegment SplitAt(int charIndex)
        {
            Fx.Assert(charIndex > 0, "");

            TrieSegment newSegment;
            if (1 == charIndex)
            {
                newSegment = new TrieSegment(this.segmentFirstChar);
            }
            else
            {
                Fx.Assert(this.segmentTail.Length > 0, "");
                newSegment = new TrieSegment(this.segmentFirstChar, this.segmentTail.Substring(0, charIndex - 1));
            }
            --charIndex;
            this.SetSegmentString(this.segmentTail, charIndex, this.segmentTail.Length - charIndex);
            newSegment.AddChild(this);
            return newSegment;
        }

        internal TrieSegment SplitChild(int childIndex, int charIndex)
        {
            Fx.Assert(this.HasChildren, "");

            TrieSegment child = this.children[childIndex];
            this.children.Remove(child);
            TrieSegment newChild = child.SplitAt(charIndex);
            this.children.Insert(newChild);
            newChild.parent = this;
            return newChild;
        }

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

    internal struct TrieTraverser
    {
        int length;
        int offset;
        string prefix;
        TrieSegment rootSegment;
        TrieSegment segment;
        int segmentIndex;

        internal TrieTraverser(TrieSegment root, string prefix)
        {
            Fx.Assert(null != root && null != prefix, "");
            this.prefix = prefix;
            this.rootSegment = root;
            this.segment = null;
            this.segmentIndex = -1;
            this.offset = 0;
            this.length = prefix.Length;
        }

        /// <summary>
        /// What length of segment that matched
        /// </summary>
        internal int Length
        {
            get
            {
                return this.length;
            }
        }

        /// <summary>
        /// The offset within the original segment where the matching part of the source string began
        /// </summary>
        internal int Offset
        {
            get
            {
                return this.offset;
            }
        }

        /// <summary>
        /// The traverser is currently at this segment node
        /// </summary>
        internal TrieSegment Segment
        {
            get
            {
                return this.segment;
            }
            set
            {
                Fx.Assert(null != value, "");
                this.segment = value;
            }
        }

        internal int SegmentIndex
        {
            get
            {
                return this.segmentIndex;
            }
        }

        /// <summary>
        /// Traverse the prefix tree
        /// </summary>
        internal bool MoveNext()
        {
            if (null != this.segment)
            {
                int segmentLength = this.segment.Length;
                this.offset += segmentLength;
                this.length -= segmentLength;

                if (this.length > 0)
                {
                    this.segmentIndex = this.segment.GetChildPosition(this.prefix, this.offset, this.length);
                    if (this.segmentIndex > -1)
                    {
                        this.segment = this.segment.GetChild(this.segmentIndex);
                        return true;
                    }
                }
                else
                {
                    this.segmentIndex = -1;
                }
                this.segment = null;
            }
            else if (null != this.rootSegment)
            {
                this.segment = this.rootSegment;
                this.rootSegment = null;
                return true;
            }
            return false;
        }

        /// <summary>
        /// Traverse the prefix tree.. using only the first character of each segment to jump from
        /// segment to segment
        /// </summary>
        internal bool MoveNextByFirstChar()
        {
            if (null != this.segment)
            {
                int segmentLength = this.segment.Length;
                this.offset += segmentLength;
                this.length -= segmentLength;

                if (this.length > 0)
                {
                    this.segmentIndex = this.segment.GetChildPosition(this.prefix[this.offset]);
                    if (this.segmentIndex > -1)
                    {
                        this.segment = this.segment.GetChild(this.segmentIndex);
                        return true;
                    }
                }
                else
                {
                    this.segmentIndex = -1;
                }
                this.segment = null;
            }
            else if (null != this.rootSegment)
            {
                this.segment = this.rootSegment;
                this.rootSegment = null;
                return true;
            }

            return false;
        }
    }


    internal class Trie
    {
        TrieSegment root; // prefix tree root
        bool hasDescendants;

        internal Trie()
        {
            this.hasDescendants = false;
        }

        bool HasDescendants
        {
            get
            {
                //return (null != this.root && this.root.ChildCount > 0);
                return this.hasDescendants;
            }
        }
#if NO
        internal bool IsEmpty
        {
            get
            {
                return (null == this.root || (null == this.root.Data && 0 == this.root.ChildCount));
            }
        }
#endif
        internal TrieSegment this[string prefix]
        {
            get
            {
                return this.Find(prefix);
            }
        }

        /// <summary>
        /// Tree root segment
        /// </summary>
        internal TrieSegment Root
        {
            get
            {
                this.EnsureRoot();
                return this.root;
            }
        }

        internal TrieSegment Add(string newPrefix)
        {
            if (newPrefix.Length <= 0)
            {
                return this.Root;
            }

            this.EnsureRoot();
            TrieTraverser traverser = new TrieTraverser(this.root, newPrefix); // struct
            TrieSegment parent;
            int indexDivergence;
            while (true)
            {
                parent = traverser.Segment;
                if (traverser.MoveNextByFirstChar())
                {
                    // There is a child segment that starts with the same character as the remainder of newPrefix
                    // We have a shared segment
                    // How much does newPrefix share with the current segment? Find the point at which they diverge
                    if (null != parent && -1 != (indexDivergence = traverser.Segment.FindDivergence(newPrefix, traverser.Offset, traverser.Length)))
                    {
                        // Segments diverge at character # 'indexDivergence'. newPrefix will share the segment upto
                        // that character. Beyond that character, we will now have 2 child segments:
                        // - one for the portion of the current segment that diverged
                        // - one for the portion of the new segment that diverged

                        // Split the current segment into a shared part and a child containing the remainder of the segment..
                        traverser.Segment = parent.SplitChild(traverser.SegmentIndex, indexDivergence);
                    }
                }
                else
                {
                    if (traverser.Length <= 0)
                    {
                        // The entire new prefix has been added to the tree
                        break;
                    }
                    // No existing segment to share. Add a new one
                    traverser.Segment = parent.AddChild(new TrieSegment(newPrefix, traverser.Offset, traverser.Length));
                }
            }

            this.hasDescendants = true;

            return parent;
        }

        void EnsureRoot()
        {
            if (null == this.root)
            {
                this.root = new TrieSegment();
            }
        }

        TrieSegment Find(string prefix)
        {
            Fx.Assert(null != prefix, "");

            if (0 == prefix.Length)
            {
                return this.Root;
            }

            if (!this.HasDescendants)
            {
                return null;
            }

            TrieTraverser traverser = new TrieTraverser(this.root, prefix); // struct
            TrieSegment foundSegment = null;
            while (traverser.MoveNext())
            {
                foundSegment = traverser.Segment;
            }
            if (traverser.Length > 0)
            {
                // We haven't used up the entire prefix in this search. Clearly, we didn't find the matching node
                return null;
            }
            return foundSegment;
        }

        void PruneRoot()
        {
            if (null != this.root && this.root.CanPrune)
            {
                this.root = null;
            }
        }

        internal void Remove(string segment)
        {
            Fx.Assert(null != segment, "");

            TrieSegment trieSegment = this[segment];
            if (null == trieSegment)
            {
                return;
            }

            if (trieSegment.HasChildren)
            {
                trieSegment.Data = null;
                return;
            }

            if (trieSegment == this.root)
            {
                // Remove the entire tree!
                this.root = null;
                this.hasDescendants = false;
                return;
            }

            trieSegment.Remove();
            this.PruneRoot();
        }

        internal void Trim()
        {
            this.root.Trim();
        }
    }

    internal class StringPrefixOpcode : LiteralRelationOpcode
    {
        string literal;

        internal StringPrefixOpcode(string literal)
            : base(OpcodeID.StringPrefix)
        {
            Fx.Assert(null != literal, "");
            this.literal = literal;
        }
#if NO
        internal override ValueDataType DataType
        {
            get
            {
                return ValueDataType.String;
            }
        }
#endif
        internal override object Literal
        {
            get
            {
                return this.literal;
            }
        }

        internal override void Add(Opcode op)
        {
            StringPrefixOpcode prefixOp = op as StringPrefixOpcode;
            if (null == prefixOp)
            {
                base.Add(op);
                return;
            }

            Fx.Assert(null != this.prev, "");

            StringPrefixBranchOpcode branch = new StringPrefixBranchOpcode();
            this.prev.Replace(this, branch);
            branch.Add(this);
            branch.Add(prefixOp);
        }

        internal override bool Equals(Opcode op)
        {
            if (base.Equals(op))
            {
                StringPrefixOpcode prefixOp = (StringPrefixOpcode)op;
                return (prefixOp.literal == this.literal);
            }

            return false;
        }

        internal override Opcode Eval(ProcessingContext context)
        {
            StackFrame arg = context.TopArg;
            if (1 == arg.Count)
            {
                Fx.Assert(context.Values[arg.basePtr].IsType(ValueDataType.String), "");

                string target = context.Values[arg.basePtr].String;
                context.Values[arg.basePtr].Boolean = target.StartsWith(this.literal, StringComparison.Ordinal);
            }
            else
            {
                for (int i = arg.basePtr; i <= arg.endPtr; ++i)
                {
                    Fx.Assert(context.Values[i].IsType(ValueDataType.String), "");
                    string target = context.Values[i].String;
                    context.Values[i].Boolean = target.StartsWith(this.literal, StringComparison.Ordinal);
                }
            }

            return this.next;
        }
    }

    internal class TrieBranchIndex : QueryBranchIndex
    {
        int count;
        Trie trie;

        internal TrieBranchIndex()
        {
            this.count = 0;
            this.trie = new Trie();
        }

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

        internal override QueryBranch this[object key]
        {
            get
            {
                TrieSegment segment = this.trie[(string)key];
                if (null != segment)
                {
                    return segment.Data;
                }
                return null;
            }
            set
            {
                Fx.Assert(null != key, "");
                TrieSegment segment = this.trie.Add((string)key);
                Fx.Assert(null != segment, "");
                this.count++;
                segment.Data = value;
            }
        }

        internal override void CollectXPathFilters(ICollection<MessageFilter> filters)
        {
            this.trie.Root.CollectXPathFilters(filters);
        }

#if NO
        internal override IEnumerator GetEnumerator()
        {
            //return new TrieBreadthFirstEnum(this.trie);
            throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new NotImplementedException("TODO"));
        }
#endif

        void Match(int valIndex, string segment, QueryBranchResultSet results)
        {
            TrieTraverser traverser = new TrieTraverser(this.trie.Root, segment);
            while (traverser.MoveNext())
            {
                object segmentData = traverser.Segment.Data;
                if (null != segmentData)
                {
                    results.Add((QueryBranch)segmentData, valIndex);
                }
            }
        }

        internal override void Match(int valIndex, ref Value val, QueryBranchResultSet results)
        {
            if (ValueDataType.Sequence == val.Type)
            {
                NodeSequence sequence = val.Sequence;
                for (int i = 0; i < sequence.Count; ++i)
                {
                    this.Match(valIndex, sequence.Items[i].StringValue(), results);
                }
            }
            else
            {
                this.Match(valIndex, val.String, results);
            }
        }

        internal override void Remove(object key)
        {
            this.trie.Remove((string)key);
            this.count--;
        }

        internal override void Trim()
        {
            this.trie.Trim();
        }
    }

    internal class StringPrefixBranchOpcode : QueryConditionalBranchOpcode
    {
        internal StringPrefixBranchOpcode()
            : base(OpcodeID.StringPrefixBranch, new TrieBranchIndex())
        {
        }
    }
}