path: root/mcs/class/referencesource/System.Data.SqlXml/System/Xml/Xsl/Xslt/MatcherBuilder.cs

//------------------------------------------------------------------------------
// <copyright file="MatcherBuilder.cs" company="Microsoft">
//     Copyright (c) Microsoft Corporation.  All rights reserved.
// </copyright>
// <owner current="true" primary="true">Microsoft</owner>
//------------------------------------------------------------------------------

using System.Collections.Generic;
using System.Diagnostics;
using System.Xml.Xsl.Qil;
using System.Xml.Xsl.XPath;

namespace System.Xml.Xsl.Xslt {
    using T = XmlQueryTypeFactory;

    #region Comments
    /*  The MatcherBuilder class implements xsl:apply-templates/imports logic, grouping patterns
     *  first by node type, then by node name of their last StepPattern. For example, suppose that
     *  we are given the following patterns, listed in order of decreasing generalized priority
     *  (3-tuple (import precedence, priority, order number in the stylesheet)):
     *
     *                          Generalized
     *      Pattern             Priority
     *      -------------------------------
     *      pattern7/foo        7
     *      pattern6/bar        6
     *      pattern5/*          5
     *      pattern4/node()     4
     *      pattern3/foo        3
     *      pattern2/bar        2
     *      pattern1/*          1
     *      pattern0/node()     0
     *      -------------------------------
     *
     *  The following code will be generated to find a first match amongst them ($it denotes a test
     *  node, and =~ denotes the match operation):
     *
     *  (: First check patterns which match only one fixed node type. :)
     *  (: Switch on the node type of the test node.                  :)
     *  let $pt :=
     *      typeswitch($it)
     *      case element() return
     *          (: First check patterns which match only one fixed node name. :)
     *          (: Switch on the node name of the test node.                  :)
     *          let $pe :=
     *              typeswitch($it)
     *              (: One case for every unique element name occurred in patterns :)
     *              case element(foo) return
     *                  if ($it =~ pattern7/foo) then 7 else
     *                  if ($it =~ pattern3/foo) then 3 else
     *                  -1                 (: -1 is used as "no match found" value :)
     *              case element(bar) return
     *                  if ($it =~ pattern6/bar) then 6 else
     *                  if ($it =~ pattern2/bar) then 2 else
     *                  -1
     *              default return
     *                  -1
     *
     *          (: Now check patterns which may match multiple node names, taking :)
     *          (: into account the priority of the previously found match        :)
     *          return
     *              if ($pe > 5)           then $pe else
     *              if ($it =~ pattern5/*) then   5 else
     *              if ($pe > 1)           then $pe else
     *              if ($it =~ pattern1/*) then   1 else
     *              if ($pe > -1)          then $pe else
     *              -1
     *
     *      (: In the general case check all other node types ocurred in patterns :)
     *      (: case attribute()...              :)
     *      (: case text()...                   :)
     *      (: case document-node()...          :)
     *      (: case comment()...                :)
     *      (: case processing-instruction()... :)
     *
     *      default return
     *          -1
     *
     *  (: Now check patterns which may match multiple node types, taking :)
     *  (: into account the priority of the previously found match        :)
     *  return
     *      if ($pt > 4)         then $pt else
     *      if (pattern4/node()) then   4 else
     *      if ($pt > 0)         then $pt else
     *      if (pattern0/node()) then   0 else
     *      if ($pt > -1)        then $pt else
     *      -1
     */
    #endregion

    internal class TemplateMatch {
        public readonly static TemplateMatchComparer Comparer = new TemplateMatchComparer();

        private Template          template;
        private double            priority;
        private XmlNodeKindFlags  nodeKind;
        private QilName           qname;
        private QilIterator       iterator;
        private QilNode           condition;    // null means f.True()

        public XmlNodeKindFlags NodeKind {
            get { return nodeKind; }
        }

        public QilName QName {
            get { return qname; }
        }

        public QilIterator Iterator {
            get { return iterator; }
        }

        public QilNode Condition {
            get { return condition; }
        }

        public QilFunction TemplateFunction {
            get { return template.Function; }
        }

        public TemplateMatch(Template template, QilLoop filter) {
            this.template   = template;
            this.priority   = double.IsNaN(template.Priority) ? XPathPatternBuilder.GetPriority(filter) : template.Priority;
            this.iterator   = filter.Variable;
            this.condition  = filter.Body;

            XPathPatternBuilder.CleanAnnotation(filter);
            NipOffTypeNameCheck();

            Debug.Assert(
                qname == null ||
                nodeKind == XmlNodeKindFlags.Element || nodeKind == XmlNodeKindFlags.Attribute || nodeKind == XmlNodeKindFlags.PI,
                "qname may be not null only for element, attribute, or PI patterns"
            );
        }

        /*  NOTE: This code depends on the form of Qil expressions generated by XPathPatternBuilder.
         *  More specifically, it recognizes the following two patterns:
         *
         *  A) /, *, @*, text(), comment(), processing-instruction():
         *      (And* $x:(IsType RefTo LiteralType))
         *
         *  B) foo, @ns:foo, processing-instruction('foo'):
         *      (And* $x:(And (IsType RefTo LiteralType) (Eq (NameOf RefTo) LiteralQName)))
         *
         *  where all RefTo refer to 'it', and LiteralType has exactly one NodeKind bit set.
         *
         *  If one of patterns recognized, we nip $x off of the nested And sequence:
         *      (And* (And2 (And1 $x:* $y:*) $z:*))  =>  (And* (And2 $y:* $z:*))
         */
        private void NipOffTypeNameCheck() {
            QilBinary[] leftPath  = new QilBinary[4];   // Circular buffer for last 4 And nodes
            int         idx       = -1;                 // Index of last element in leftPath
            QilNode     node      = condition;          // Walker through left path of the tree

            nodeKind = XmlNodeKindFlags.None;
            qname    = null;

            while (node.NodeType == QilNodeType.And) {
                node = (leftPath[++idx & 3] = (QilBinary)node).Left;
            }

            // Recognizing (IsType RefTo LiteralType)
            if (!(node.NodeType == QilNodeType.IsType)) {
                return;
            }

            QilBinary isType = (QilBinary)node;
            if (!(isType.Left == iterator && isType.Right.NodeType == QilNodeType.LiteralType)) {
                return;
            }

            XmlNodeKindFlags nodeKinds = isType.Right.XmlType.NodeKinds;
            if (!Bits.ExactlyOne((uint)nodeKinds)) {
                return;
            }

            // Recognized pattern A, check for B
            QilNode x = isType;
            nodeKind = nodeKinds;
            QilBinary lastAnd = leftPath[idx & 3];

            if (lastAnd != null && lastAnd.Right.NodeType == QilNodeType.Eq) {
                QilBinary eq = (QilBinary)lastAnd.Right;

                // Recognizing (Eq (NameOf RefTo) LiteralQName)
                if (eq.Left.NodeType == QilNodeType.NameOf &&
                    ((QilUnary)eq.Left).Child == iterator && eq.Right.NodeType == QilNodeType.LiteralQName
                ) {
                    // Recognized pattern B
                    x = lastAnd;
                    qname = (QilName)((QilLiteral)eq.Right).Value;
                    idx--;
                }
            }

            // Nip $x off the condition
            QilBinary and1 = leftPath[idx & 3];
            QilBinary and2 = leftPath[--idx & 3];

            if (and2 != null) {
                and2.Left = and1.Right;
            } else if (and1 != null) {
                condition = and1.Right;
            } else {
                condition = null;
            }
        }

        internal class TemplateMatchComparer : IComparer<TemplateMatch> {
            // TemplateMatch x is "greater" than TemplateMatch y iff
            // * x's priority is greater than y's priority, or
            // * x's priority is equal to y's priority, and x occurs later in the stylesheet than y.
            // Order of TemplateMatch'es from the same xsl:template/@match attribute does not matter.

            public int Compare(TemplateMatch x, TemplateMatch y) {
                Debug.Assert(!double.IsNaN(x.priority));
                Debug.Assert(!double.IsNaN(y.priority));
                return (
                    x.priority > y.priority ?  1 :
                    x.priority < y.priority ? -1 :
                    x.template.OrderNumber - y.template.OrderNumber
                );
            }
        }
    }

    internal struct Pattern {
        public readonly TemplateMatch Match;

        // Generalized priority of 'match' for the xsl:apply-templates/imports currently being processed
        public readonly int Priority;

        public Pattern(TemplateMatch match, int priority) {
            this.Match    = match;
            this.Priority = priority;
        }
    }

    internal class PatternBag {
        public Dictionary<QilName, List<Pattern>> FixedNamePatterns = new Dictionary<QilName, List<Pattern>>();
        public List<QilName> FixedNamePatternsNames = new List<QilName>();  // Needed only to guarantee a stable order
        public List<Pattern> NonFixedNamePatterns   = new List<Pattern>();

        public void Clear() {
            FixedNamePatterns.Clear();
            FixedNamePatternsNames.Clear();
            NonFixedNamePatterns.Clear();
        }

        public void Add(Pattern pattern) {
            QilName qname = pattern.Match.QName;
            List<Pattern> list;

            if (qname == null) {
                list = NonFixedNamePatterns;
            } else {
                if (!FixedNamePatterns.TryGetValue(qname, out list)) {
                    FixedNamePatternsNames.Add(qname);
                    list = FixedNamePatterns[qname] = new List<Pattern>();
                }
            }
            list.Add(pattern);
        }
    }

    internal class MatcherBuilder {
        private XPathQilFactory     f;
        private ReferenceReplacer   refReplacer;
        private InvokeGenerator     invkGen;

        private const int           NoMatch = -1;

        public MatcherBuilder(XPathQilFactory f, ReferenceReplacer refReplacer, InvokeGenerator invkGen) {
            this.f           = f;
            this.refReplacer = refReplacer;
            this.invkGen     = invkGen;
        }

        private int priority = -1;

        private PatternBag    elementPatterns       = new PatternBag();
        private PatternBag    attributePatterns     = new PatternBag();
        private List<Pattern> textPatterns          = new List<Pattern>();
        private List<Pattern> documentPatterns      = new List<Pattern>();
        private List<Pattern> commentPatterns       = new List<Pattern>();
        private PatternBag    piPatterns            = new PatternBag();
        private List<Pattern> heterogenousPatterns  = new List<Pattern>();

        private List<List<TemplateMatch>> allMatches = new List<List<TemplateMatch>>();

        private void Clear() {
            priority = -1;

            elementPatterns.Clear();
            attributePatterns.Clear();
            textPatterns.Clear();
            documentPatterns.Clear();
            commentPatterns.Clear();
            piPatterns.Clear();
            heterogenousPatterns.Clear();

            allMatches.Clear();
        }

        private void AddPatterns(List<TemplateMatch> matches) {
            // Process templates in the straight order, since their order will be reverted in the result tree
            foreach (TemplateMatch match in matches) {
                Pattern pattern = new Pattern(match, ++priority);

                switch (match.NodeKind) {
                case XmlNodeKindFlags.Element   : elementPatterns     .Add(pattern); break;
                case XmlNodeKindFlags.Attribute : attributePatterns   .Add(pattern); break;
                case XmlNodeKindFlags.Text      : textPatterns        .Add(pattern); break;
                case XmlNodeKindFlags.Document  : documentPatterns    .Add(pattern); break;
                case XmlNodeKindFlags.Comment   : commentPatterns     .Add(pattern); break;
                case XmlNodeKindFlags.PI        : piPatterns          .Add(pattern); break;
                default                         : heterogenousPatterns.Add(pattern); break;
                }
            }
        }

        private void CollectPatternsInternal(Stylesheet sheet, QilName mode) {
            // Process imported stylesheets in the straight order, since their order will be reverted in the result tree
            foreach (Stylesheet import in sheet.Imports) {
                CollectPatternsInternal(import, mode);
            }

            List<TemplateMatch> matchesForMode;
            if (sheet.TemplateMatches.TryGetValue(mode, out matchesForMode)) {
                AddPatterns(matchesForMode);
                allMatches.Add(matchesForMode);
            }
        }

        public void CollectPatterns(StylesheetLevel sheet, QilName mode) {
            Clear();
            foreach (Stylesheet import in sheet.Imports) {
                CollectPatternsInternal(import, mode);
            }
        }

        private QilNode MatchPattern(QilIterator it, TemplateMatch match) {
            QilNode cond = match.Condition;
            if (cond == null) {
                return f.True();
            } else {
                // We have to clone, because the same pattern may be used
                // in many different xsl:apply-templates/imports functions
                cond = cond.DeepClone(f.BaseFactory);
                return refReplacer.Replace(cond, match.Iterator, it);
            }
        }

        private QilNode MatchPatterns(QilIterator it, List<Pattern> patternList) {
            Debug.Assert(patternList.Count > 0);
            QilNode result = f.Int32(NoMatch);

            foreach (Pattern pattern in patternList) {
                // if ($it =~ pattern.Match) then pattern.Priority else...
                result = f.Conditional(MatchPattern(it, pattern.Match), f.Int32(pattern.Priority), result);
            }

            return result;
        }

        private QilNode MatchPatterns(QilIterator it, XmlQueryType xt, List<Pattern> patternList, QilNode otherwise) {
            if (patternList.Count == 0) {
                return otherwise;
            }
            return f.Conditional(f.IsType(it, xt), MatchPatterns(it, patternList), otherwise);
        }

        private bool IsNoMatch(QilNode matcher) {
            if (matcher.NodeType == QilNodeType.LiteralInt32) {
                Debug.Assert((int)(QilLiteral)matcher == NoMatch);
                return true;
            }
            return false;
        }

        private QilNode MatchPatternsWhosePriorityGreater(QilIterator it, List<Pattern> patternList, QilNode matcher) {
            if (patternList.Count == 0) {
                return matcher;
            }
            if (IsNoMatch(matcher)) {
                return MatchPatterns(it, patternList);
            }

            QilIterator stopPriority = f.Let(matcher);
            QilNode result = f.Int32(NoMatch);
            int lastPriority = NoMatch;

            foreach (Pattern pattern in patternList) {
                // if (stopPriority > pattern.Priority) then stopPriority     else
                // if ($it =~ pattern.Match)            then pattern.Priority else...

                // First 'if' is generated lazily since it is not needed if priorities are consecutive numbers
                Debug.Assert(pattern.Priority > lastPriority);
                if (pattern.Priority > lastPriority + 1) {
                    result = f.Conditional(f.Gt(stopPriority, f.Int32(lastPriority)), stopPriority, result);
                }

                result = f.Conditional(MatchPattern(it, pattern.Match), f.Int32(pattern.Priority), result);
                lastPriority = pattern.Priority;
            }

            // If the last pattern has the highest priority, the check can be eliminated
            if (lastPriority != this.priority) {
                result = f.Conditional(f.Gt(stopPriority, f.Int32(lastPriority)), stopPriority, result);
            }

            return f.Loop(stopPriority, result);
        }

        private QilNode MatchPatterns(QilIterator it, XmlQueryType xt, PatternBag patternBag, QilNode otherwise) {
            if (patternBag.FixedNamePatternsNames.Count == 0) {
                return MatchPatterns(it, xt, patternBag.NonFixedNamePatterns, otherwise);
            }

            QilNode matcher = f.Int32(NoMatch);

            foreach (QilName qname in patternBag.FixedNamePatternsNames) {
                matcher = f.Conditional(f.Eq(f.NameOf(it), qname.ShallowClone(f.BaseFactory)),
                    MatchPatterns(it, patternBag.FixedNamePatterns[qname]),
                    matcher
                );
            }

            matcher = MatchPatternsWhosePriorityGreater(it, patternBag.NonFixedNamePatterns, matcher);
            return f.Conditional(f.IsType(it, xt), matcher, otherwise);
        }

#if !DISABLE_MATCH_OPTIMIZATION
        public QilNode BuildMatcher(QilIterator it, IList<XslNode> actualArgs, QilNode otherwise) {
            QilNode matcher = f.Int32(NoMatch);

            matcher = MatchPatterns(it, T.PI       , piPatterns       , matcher);
            matcher = MatchPatterns(it, T.Comment  , commentPatterns  , matcher);
            matcher = MatchPatterns(it, T.Document , documentPatterns , matcher);
            matcher = MatchPatterns(it, T.Text     , textPatterns     , matcher);
            matcher = MatchPatterns(it, T.Attribute, attributePatterns, matcher);
            matcher = MatchPatterns(it, T.Element  , elementPatterns  , matcher);

            matcher = MatchPatternsWhosePriorityGreater(it, heterogenousPatterns, matcher);

            if (IsNoMatch(matcher)) {
                return otherwise;
            }

#if !DISABLE_SWITCH
            QilNode[] branches = new QilNode[this.priority + 2];
            int priority = -1;

            foreach (List<TemplateMatch> list in allMatches) {
                foreach (TemplateMatch match in list) {
                    branches[++priority] = invkGen.GenerateInvoke(match.TemplateFunction, actualArgs);
                }
            }

            branches[++priority] = otherwise;
            Debug.Assert(priority == branches.Length - 1);
            return f.Choice(matcher, f.BranchList(branches));
#else
            QilIterator p = f.Let(matcher);
            QilNode result = otherwise;
            int priority = 0;

            foreach (List<TemplateMatch> list in allMatches) {
                foreach (TemplateMatch match in list) {
                    result = f.Conditional(f.Eq(p, f.Int32(priority++)),
                        invkGen.GenerateInvoke(match.TemplateFunction, actualArgs),
                        result
                    );
                }
            }

            return f.Loop(p, result);
#endif
        }
#else
        public QilNode BuildMatcher(QilIterator it, IList<XslNode> actualArgs, QilNode otherwise) {
            QilNode result = otherwise;

            foreach (List<TemplateMatch> list in allMatches) {
                foreach (TemplateMatch match in list) {
                    XmlNodeKindFlags nodeKind = match.NodeKind;
                    QilName qname = match.QName;
                    QilNode cond = match.Condition;

                    if (cond != null) {
                        // We have to clone, because the same pattern may be used
                        // in many different xsl:apply-templates/imports functions
                        cond = cond.DeepClone(f.BaseFactory);
                        cond = refReplacer.Replace(cond, match.Iterator, it);
                    }

                    if (nodeKind != 0) {
                        XmlQueryType nodeType;
                        switch (nodeKind) {
                        case XmlNodeKindFlags.Element   : nodeType = T.Element  ;  break;
                        case XmlNodeKindFlags.Attribute : nodeType = T.Attribute;  break;
                        case XmlNodeKindFlags.Text      : nodeType = T.Text     ;  break;
                        case XmlNodeKindFlags.Document  : nodeType = T.Document ;  break;
                        case XmlNodeKindFlags.Comment   : nodeType = T.Comment  ;  break;
                        case XmlNodeKindFlags.PI        : nodeType = T.PI       ;  break;
                        default                         : nodeType = null       ;  break;
                        }

                        Debug.Assert(nodeType != null, "Unexpected nodeKind: " + nodeKind);
                        QilNode typeNameCheck = f.IsType(it, nodeType);

                        if (qname != null) {
                            typeNameCheck = f.And(typeNameCheck, f.Eq(f.NameOf(it), qname.ShallowClone(f.BaseFactory)));
                        }

                        cond = (cond == null) ? typeNameCheck : f.And(typeNameCheck, cond);
                    }

                    result = f.Conditional(cond,
                        invkGen.GenerateInvoke(match.TemplateFunction, actualArgs),
                        result
                    );
                }
            }
            return result;
        }
#endif
    }
}