The Labs \ Source Viewer \ SSCLI \ System.Xml.Xsl.Xslt \ MatcherBuilder

  1. //------------------------------------------------------------------------------
  2. // <copyright file="MatcherBuilder.cs" company="Microsoft">
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. // </copyright>
  14. //------------------------------------------------------------------------------
  15. using System.Collections.Generic;
  16. using System.Diagnostics;
  17. using System.Xml.Xsl.Qil;
  18. using System.Xml.Xsl.XPath;
  19. namespace System.Xml.Xsl.Xslt
  20. {
  21.     using T = XmlQueryTypeFactory;
  22.    
  23.     #region Comments
  24. /*  The MatcherBuilder class implements xsl:apply-templates/imports logic, grouping patterns
  25.     *  first by node type, then by node name of their last StepPattern. For example, suppose that
  26.     *  we are given the following patterns, listed in order of decreasing generalized priority
  27.     *  (3-tuple (import precedence, priority, order number in the stylesheet)):
  28.     *
  29.     *                          Generalized
  30.     *      Pattern            Priority
  31.     *      -------------------------------
  32.     *      pattern7/foo        7
  33.     *      pattern6/bar        6
  34.     *      pattern5/*          5
  35.     *      pattern4/node()    4
  36.     *      pattern3/foo        3
  37.     *      pattern2/bar        2
  38.     *      pattern1/*          1
  39.     *      pattern0/node()    0
  40.     *      -------------------------------
  41.     *
  42.     *  The following code will be generated to find a first match amongst them ($it denotes a test
  43.     *  node, and =~ denotes the match operation):
  44.     *
  45.     *  (: First check patterns which match only one fixed node type. :)
  46.     *  (: Switch on the node type of the test node.                  :)
  47.     *  let $pt :=
  48.     *      typeswitch($it)
  49.     *      case element() return
  50.     *          (: First check patterns which match only one fixed node name. :)
  51.     *          (: Switch on the node name of the test node.                  :)
  52.     *          let $pe :=
  53.     *              typeswitch($it)
  54.     *              (: One case for every unique element name occurred in patterns :)
  55.     *              case element(foo) return
  56.     *                  if ($it =~ pattern7/foo) then 7 else
  57.     *                  if ($it =~ pattern3/foo) then 3 else
  58.     *                  -1                (: -1 is used as "no match found" value :)
  59.     *              case element(bar) return
  60.     *                  if ($it =~ pattern6/bar) then 6 else
  61.     *                  if ($it =~ pattern2/bar) then 2 else
  62.     *                  -1
  63.     *              default return
  64.     *                  -1
  65.     *
  66.     *          (: Now check patterns which may match multiple node names, taking :)
  67.     *          (: into account the priority of the previously found match        :)
  68.     *          return
  69.     *              if ($pe > 5)          then $pe else
  70.     *              if ($it =~ pattern5/*) then  5 else
  71.     *              if ($pe > 1)          then $pe else
  72.     *              if ($it =~ pattern1/*) then  1 else
  73.     *              if ($pe > -1)          then $pe else
  74.     *              -1
  75.     *
  76.     *      (: In the general case check all other node types ocurred in patterns :)
  77.     *      (: case attribute()...              :)
  78.     *      (: case text()...                  :)
  79.     *      (: case document-node()...          :)
  80.     *      (: case comment()...                :)
  81.     *      (: case processing-instruction()... :)
  82.     *
  83.     *      default return
  84.     *          -1
  85.     *
  86.     *  (: Now check patterns which may match multiple node types, taking :)
  87.     *  (: into account the priority of the previously found match        :)
  88.     *  return
  89.     *      if ($pt > 4)        then $pt else
  90.     *      if (pattern4/node()) then  4 else
  91.     *      if ($pt > 0)        then $pt else
  92.     *      if (pattern0/node()) then  0 else
  93.     *      if ($pt > -1)        then $pt else
  94.     *      -1
  95.     */   
  96.     #endregion
  97.    
  98.     internal class TemplateMatch
  99.     {
  100.         public static readonly TemplateMatchComparer Comparer = new TemplateMatchComparer();
  101.        
  102.         private Template template;
  103.         private double priority;
  104.         private XmlNodeKindFlags nodeKind;
  105.         private QilName qname;
  106.         private QilIterator iterator;
  107.         private QilNode condition;
  108.         // null means f.True()
  109.         public XmlNodeKindFlags NodeKind {
  110.             get { return nodeKind; }
  111.         }
  112.        
  113.         public QilName QName {
  114.             get { return qname; }
  115.         }
  116.        
  117.         public QilIterator Iterator {
  118.             get { return iterator; }
  119.         }
  120.        
  121.         public QilNode Condition {
  122.             get { return condition; }
  123.         }
  124.        
  125.         public QilFunction TemplateFunction {
  126.             get { return template.Function; }
  127.         }
  128.        
  129.         public TemplateMatch(Template template, QilLoop filter)
  130.         {
  131.             this.template = template;
  132.             this.priority = double.IsNaN(template.Priority) ? XPathPatternBuilder.GetPriority(filter) : template.Priority;
  133.             this.iterator = filter.Variable;
  134.             this.condition = filter.Body;
  135.            
  136.             XPathPatternBuilder.CleanAnnotation(filter);
  137.             NipOffTypeNameCheck();
  138.            
  139.             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");
  140.         }
  141.        
  142. /*  NOTE: This code depends on the form of Qil expressions generated by XPathPatternBuilder.
  143.         *  More specifically, it recognizes the following two patterns:
  144.         *
  145.         *  A) /, *, @*, text(), comment(), processing-instruction():
  146.         *      (And* $x:(IsType RefTo LiteralType))
  147.         *
  148.         *  B) foo, @ns:foo, processing-instruction('foo'):
  149.         *      (And* $x:(And (IsType RefTo LiteralType) (Eq (NameOf RefTo) LiteralQName)))
  150.         *
  151.         *  where all RefTo refer to 'it', and LiteralType has exactly one NodeKind bit set.
  152.         *
  153.         *  If one of patterns recognized, we nip $x off of the nested And sequence:
  154.         *      (And* (And2 (And1 $x:* $y:*) $z:*))  =>  (And* (And2 $y:* $z:*))
  155.         */       
  156.         private void NipOffTypeNameCheck()
  157.         {
  158.             QilBinary[] leftPath = new QilBinary[4];
  159.             // Circular buffer for last 4 And nodes
  160.             int idx = -1;
  161.             // Index of last element in leftPath
  162.             QilNode node = condition;
  163.             // Walker through left path of the tree
  164.             nodeKind = XmlNodeKindFlags.None;
  165.             qname = null;
  166.            
  167.             while (node.NodeType == QilNodeType.And) {
  168.                 node = (leftPath[++idx & 3] = (QilBinary)node).Left;
  169.             }
  170.            
  171.             // Recognizing (IsType RefTo LiteralType)
  172.             if (!(node.NodeType == QilNodeType.IsType)) {
  173.                 return;
  174.             }
  175.            
  176.             QilBinary isType = (QilBinary)node;
  177.             if (!(isType.Left == iterator && isType.Right.NodeType == QilNodeType.LiteralType)) {
  178.                 return;
  179.             }
  180.            
  181.             XmlNodeKindFlags nodeKinds = isType.Right.XmlType.NodeKinds;
  182.             if (!Bits.ExactlyOne((uint)nodeKinds)) {
  183.                 return;
  184.             }
  185.            
  186.             // Recognized pattern A, check for B
  187.             QilNode x = isType;
  188.             nodeKind = nodeKinds;
  189.             QilBinary lastAnd = leftPath[idx & 3];
  190.            
  191.             if (lastAnd != null && lastAnd.Right.NodeType == QilNodeType.Eq) {
  192.                 QilBinary eq = (QilBinary)lastAnd.Right;
  193.                
  194.                 // Recognizing (Eq (NameOf RefTo) LiteralQName)
  195.                 if (eq.Left.NodeType == QilNodeType.NameOf && ((QilUnary)eq.Left).Child == iterator && eq.Right.NodeType == QilNodeType.LiteralQName) {
  196.                     // Recognized pattern B
  197.                     x = lastAnd;
  198.                     qname = (QilName)((QilLiteral)eq.Right).Value;
  199.                     idx--;
  200.                 }
  201.             }
  202.            
  203.             // Nip $x off the condition
  204.             QilBinary and1 = leftPath[idx & 3];
  205.             QilBinary and2 = leftPath[--idx & 3];
  206.            
  207.             if (and2 != null) {
  208.                 and2.Left = and1.Right;
  209.             }
  210.             else if (and1 != null) {
  211.                 condition = and1.Right;
  212.             }
  213.             else {
  214.                 condition = null;
  215.             }
  216.         }
  217.        
  218.         internal class TemplateMatchComparer : IComparer<TemplateMatch>
  219.         {
  220.             // TemplateMatch x is "greater" than TemplateMatch y iff
  221.             // * x's priority is greater than y's priority, or
  222.             // * x's priority is equal to y's priority, and x occurs later in the stylesheet than y.
  223.             // Order of TemplateMatch'es from the same xsl:template/@match attribute does not matter.
  224.            
  225.             public int Compare(TemplateMatch x, TemplateMatch y)
  226.             {
  227.                 Debug.Assert(!double.IsNaN(x.priority));
  228.                 Debug.Assert(!double.IsNaN(y.priority));
  229.                 return (x.priority > y.priority ? 1 : x.priority < y.priority ? -1 : x.template.OrderNumber - y.template.OrderNumber);
  230.             }
  231.         }
  232.     }
  233.    
  234.     internal struct Pattern
  235.     {
  236.         public readonly TemplateMatch Match;
  237.        
  238.         // Generalized priority of 'match' for the xsl:apply-templates/imports currently being processed
  239.         public readonly int Priority;
  240.        
  241.         public Pattern(TemplateMatch match, int priority)
  242.         {
  243.             this.Match = match;
  244.             this.Priority = priority;
  245.         }
  246.     }
  247.    
  248.     internal class PatternBag
  249.     {
  250.         public Dictionary<QilName, List<Pattern>> FixedNamePatterns = new Dictionary<QilName, List<Pattern>>();
  251.         public List<QilName> FixedNamePatternsNames = new List<QilName>();
  252.         // Needed only to guarantee a stable order
  253.         public List<Pattern> NonFixedNamePatterns = new List<Pattern>();
  254.        
  255.         public void Clear()
  256.         {
  257.             FixedNamePatterns.Clear();
  258.             FixedNamePatternsNames.Clear();
  259.             NonFixedNamePatterns.Clear();
  260.         }
  261.        
  262.         public void Add(Pattern pattern)
  263.         {
  264.             QilName qname = pattern.Match.QName;
  265.             List<Pattern> list;
  266.            
  267.             if (qname == null) {
  268.                 list = NonFixedNamePatterns;
  269.             }
  270.             else {
  271.                 if (!FixedNamePatterns.TryGetValue(qname, out list)) {
  272.                     FixedNamePatternsNames.Add(qname);
  273.                     list = FixedNamePatterns[qname] = new List<Pattern>();
  274.                 }
  275.             }
  276.             list.Add(pattern);
  277.         }
  278.     }
  279.    
  280.     internal class MatcherBuilder
  281.     {
  282.         private XPathQilFactory f;
  283.         private ReferenceReplacer refReplacer;
  284.         private InvokeGenerator invkGen;
  285.        
  286.         private const int NoMatch = -1;
  287.        
  288.         public MatcherBuilder(XPathQilFactory f, ReferenceReplacer refReplacer, InvokeGenerator invkGen)
  289.         {
  290.             this.f = f;
  291.             this.refReplacer = refReplacer;
  292.             this.invkGen = invkGen;
  293.         }
  294.        
  295.         private int priority = -1;
  296.        
  297.         private PatternBag elementPatterns = new PatternBag();
  298.         private PatternBag attributePatterns = new PatternBag();
  299.         private List<Pattern> textPatterns = new List<Pattern>();
  300.         private List<Pattern> documentPatterns = new List<Pattern>();
  301.         private List<Pattern> commentPatterns = new List<Pattern>();
  302.         private PatternBag piPatterns = new PatternBag();
  303.         private List<Pattern> heterogenousPatterns = new List<Pattern>();
  304.        
  305.         private List<List<TemplateMatch>> allMatches = new List<List<TemplateMatch>>();
  306.        
  307.         private void Clear()
  308.         {
  309.             priority = -1;
  310.            
  311.             elementPatterns.Clear();
  312.             attributePatterns.Clear();
  313.             textPatterns.Clear();
  314.             documentPatterns.Clear();
  315.             commentPatterns.Clear();
  316.             piPatterns.Clear();
  317.             heterogenousPatterns.Clear();
  318.            
  319.             allMatches.Clear();
  320.         }
  321.        
  322.         private void AddPatterns(List<TemplateMatch> matches)
  323.         {
  324.             // Process templates in the straight order, since their order will be reverted in the result tree
  325.             foreach (TemplateMatch match in matches) {
  326.                 Pattern pattern = new Pattern(match, ++priority);
  327.                
  328.                 switch (match.NodeKind) {
  329.                     case XmlNodeKindFlags.Element:
  330.                         elementPatterns.Add(pattern);
  331.                         break;
  332.                     case XmlNodeKindFlags.Attribute:
  333.                         attributePatterns.Add(pattern);
  334.                         break;
  335.                     case XmlNodeKindFlags.Text:
  336.                         textPatterns.Add(pattern);
  337.                         break;
  338.                     case XmlNodeKindFlags.Document:
  339.                         documentPatterns.Add(pattern);
  340.                         break;
  341.                     case XmlNodeKindFlags.Comment:
  342.                         commentPatterns.Add(pattern);
  343.                         break;
  344.                     case XmlNodeKindFlags.PI:
  345.                         piPatterns.Add(pattern);
  346.                         break;
  347.                     default:
  348.                         heterogenousPatterns.Add(pattern);
  349.                         break;
  350.                 }
  351.             }
  352.         }
  353.        
  354.         private void CollectPatterns(Stylesheet sheet, QilName mode)
  355.         {
  356.             // Process imported stylesheets in the straight order, since their order will be reverted in the result tree
  357.             foreach (Stylesheet import in sheet.Imports) {
  358.                 CollectPatterns(import, mode);
  359.             }
  360.            
  361.             List<TemplateMatch> matchesForMode;
  362.             if (sheet.TemplateMatches.TryGetValue(mode, out matchesForMode)) {
  363.                 AddPatterns(matchesForMode);
  364.                 allMatches.Add(matchesForMode);
  365.             }
  366.         }
  367.        
  368.         public void CollectPatterns(Stylesheet sheet, QilName mode, bool applyImports)
  369.         {
  370.             Clear();
  371.             if (applyImports) {
  372.                 foreach (Stylesheet import in sheet.Imports) {
  373.                     CollectPatterns(import, mode);
  374.                 }
  375.             }
  376.             else {
  377.                 CollectPatterns(sheet, mode);
  378.             }
  379.         }
  380.        
  381.         private QilNode MatchPattern(QilIterator it, TemplateMatch match)
  382.         {
  383.             QilNode cond = match.Condition;
  384.             if (cond == null) {
  385.                 return f.True();
  386.             }
  387.             else {
  388.                 // We have to clone, because the same pattern may be used
  389.                 // in many different xsl:apply-templates/imports functions
  390.                 cond = cond.DeepClone(f.BaseFactory);
  391.                 return refReplacer.Replace(cond, match.Iterator, it);
  392.             }
  393.         }
  394.        
  395.         private QilNode MatchPatterns(QilIterator it, List<Pattern> patternList)
  396.         {
  397.             Debug.Assert(patternList.Count > 0);
  398.             QilNode result = f.Int32(NoMatch);
  399.            
  400.             foreach (Pattern pattern in patternList) {
  401.                 // if ($it =~ pattern.Match) then pattern.Priority else...
  402.                 result = f.Conditional(MatchPattern(it, pattern.Match), f.Int32(pattern.Priority), result);
  403.             }
  404.            
  405.             return result;
  406.         }
  407.        
  408.         private QilNode MatchPatterns(QilIterator it, XmlQueryType xt, List<Pattern> patternList, QilNode otherwise)
  409.         {
  410.             if (patternList.Count == 0) {
  411.                 return otherwise;
  412.             }
  413.             return f.Conditional(f.IsType(it, xt), MatchPatterns(it, patternList), otherwise);
  414.         }
  415.        
  416.         private bool IsNoMatch(QilNode matcher)
  417.         {
  418.             if (matcher.NodeType == QilNodeType.LiteralInt32) {
  419.                 Debug.Assert((int)(QilLiteral)matcher == NoMatch);
  420.                 return true;
  421.             }
  422.             return false;
  423.         }
  424.        
  425.         private QilNode MatchPatternsWhosePriorityGreater(QilIterator it, List<Pattern> patternList, QilNode matcher)
  426.         {
  427.             if (patternList.Count == 0) {
  428.                 return matcher;
  429.             }
  430.             if (IsNoMatch(matcher)) {
  431.                 return MatchPatterns(it, patternList);
  432.             }
  433.            
  434.             QilIterator stopPriority = f.Let(matcher);
  435.             QilNode result = f.Int32(NoMatch);
  436.             int lastPriority = NoMatch;
  437.            
  438.             foreach (Pattern pattern in patternList) {
  439.                 // if (stopPriority > pattern.Priority) then stopPriority else
  440.                 // if ($it =~ pattern.Match) then pattern.Priority else...
  441.                
  442.                 // First 'if' is generated lazily since it is not needed if priorities are consecutive numbers
  443.                 Debug.Assert(pattern.Priority > lastPriority);
  444.                 if (pattern.Priority > lastPriority + 1) {
  445.                     result = f.Conditional(f.Gt(stopPriority, f.Int32(lastPriority)), stopPriority, result);
  446.                 }
  447.                
  448.                 result = f.Conditional(MatchPattern(it, pattern.Match), f.Int32(pattern.Priority), result);
  449.                 lastPriority = pattern.Priority;
  450.             }
  451.            
  452.             // If the last pattern has the highest priority, the check can be eliminated
  453.             if (lastPriority != this.priority) {
  454.                 result = f.Conditional(f.Gt(stopPriority, f.Int32(lastPriority)), stopPriority, result);
  455.             }
  456.            
  457.             return f.Loop(stopPriority, result);
  458.         }
  459.        
  460.         private QilNode MatchPatterns(QilIterator it, XmlQueryType xt, PatternBag patternBag, QilNode otherwise)
  461.         {
  462.             if (patternBag.FixedNamePatternsNames.Count == 0) {
  463.                 return MatchPatterns(it, xt, patternBag.NonFixedNamePatterns, otherwise);
  464.             }
  465.            
  466.             QilNode matcher = f.Int32(NoMatch);
  467.            
  468.             foreach (QilName qname in patternBag.FixedNamePatternsNames) {
  469.                 matcher = f.Conditional(f.Eq(f.NameOf(it), qname.ShallowClone(f.BaseFactory)), MatchPatterns(it, patternBag.FixedNamePatterns[qname]), matcher);
  470.             }
  471.            
  472.             matcher = MatchPatternsWhosePriorityGreater(it, patternBag.NonFixedNamePatterns, matcher);
  473.             return f.Conditional(f.IsType(it, xt), matcher, otherwise);
  474.         }
  475.        
  476.         public QilNode BuildMatcher(QilIterator it, IList<XslNode> actualArgs, QilNode otherwise)
  477.         {
  478.             QilNode matcher = f.Int32(NoMatch);
  479.            
  480.             matcher = MatchPatterns(it, T.PI, piPatterns, matcher);
  481.             matcher = MatchPatterns(it, T.Comment, commentPatterns, matcher);
  482.             matcher = MatchPatterns(it, T.Document, documentPatterns, matcher);
  483.             matcher = MatchPatterns(it, T.Text, textPatterns, matcher);
  484.             matcher = MatchPatterns(it, T.Attribute, attributePatterns, matcher);
  485.             matcher = MatchPatterns(it, T.Element, elementPatterns, matcher);
  486.            
  487.             matcher = MatchPatternsWhosePriorityGreater(it, heterogenousPatterns, matcher);
  488.            
  489.             if (IsNoMatch(matcher)) {
  490.                 return otherwise;
  491.             }
  492.            
  493.             QilNode[] branches = new QilNode[this.priority + 2];
  494.             int priority = -1;
  495.            
  496.             foreach (List<TemplateMatch> list in allMatches) {
  497.                 foreach (TemplateMatch match in list) {
  498.                     branches[++priority] = invkGen.GenerateInvoke(match.TemplateFunction, actualArgs);
  499.                 }
  500.             }
  501.            
  502.             branches[++priority] = otherwise;
  503.             Debug.Assert(priority == branches.Length - 1);
  504.             return f.Choice(matcher, f.BranchList(branches));
  505.         }
  506.     }
  507. }

Developer Fusion