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

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