1 /*
   2  * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
   3  */
   4 /*
   5  * Licensed to the Apache Software Foundation (ASF) under one or more
   6  * contributor license agreements.  See the NOTICE file distributed with
   7  * this work for additional information regarding copyright ownership.
   8  * The ASF licenses this file to You under the Apache License, Version 2.0
   9  * (the "License"); you may not use this file except in compliance with
  10  * the License.  You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  */
  20 
  21 package com.sun.org.apache.xalan.internal.xsltc.compiler;
  22 
  23 import com.sun.org.apache.bcel.internal.generic.ALOAD;
  24 import com.sun.org.apache.bcel.internal.generic.BranchHandle;
  25 import com.sun.org.apache.bcel.internal.generic.ConstantPoolGen;
  26 import com.sun.org.apache.bcel.internal.generic.IF_ICMPEQ;
  27 import com.sun.org.apache.bcel.internal.generic.ILOAD;
  28 import com.sun.org.apache.bcel.internal.generic.INVOKEINTERFACE;
  29 import com.sun.org.apache.bcel.internal.generic.INVOKEVIRTUAL;
  30 import com.sun.org.apache.bcel.internal.generic.InstructionHandle;
  31 import com.sun.org.apache.bcel.internal.generic.InstructionList;
  32 import com.sun.org.apache.bcel.internal.generic.PUSH;
  33 import com.sun.org.apache.xalan.internal.xsltc.compiler.util.ClassGenerator;
  34 import com.sun.org.apache.xalan.internal.xsltc.compiler.util.ErrorMsg;
  35 import com.sun.org.apache.xalan.internal.xsltc.compiler.util.MethodGenerator;
  36 import com.sun.org.apache.xalan.internal.xsltc.compiler.util.Type;
  37 import com.sun.org.apache.xalan.internal.xsltc.compiler.util.TypeCheckError;
  38 import com.sun.org.apache.xalan.internal.xsltc.compiler.util.Util;
  39 import java.util.ArrayList;
  40 import java.util.List;
  41 import java.util.StringTokenizer;
  42 
  43 /**
  44  * @author Morten Jorgensen
  45  * @LastModified: Oct 2017
  46  */
  47 final class Whitespace extends TopLevelElement {
  48     // Three possible actions for the translet:
  49     public static final int USE_PREDICATE  = 0;
  50     public static final int STRIP_SPACE    = 1;
  51     public static final int PRESERVE_SPACE = 2;
  52 
  53     // The 3 different categories of strip/preserve rules (order important)
  54     public static final int RULE_NONE      = 0;
  55     public static final int RULE_ELEMENT   = 1; // priority 0
  56     public static final int RULE_NAMESPACE = 2; // priority -1/4
  57     public static final int RULE_ALL       = 3; // priority -1/2
  58 
  59     private String _elementList;
  60     private int    _action;
  61     private int    _importPrecedence;
  62 
  63     /**
  64      * Auxillary class for encapsulating a single strip/preserve rule
  65      */
  66     final static class WhitespaceRule {
  67         private final int _action;
  68         private String _namespace; // Should be replaced by NS type (int)
  69         private String _element;   // Should be replaced by node type (int)
  70         private int    _type;
  71         private int    _priority;
  72 
  73         /**
  74          * Strip/preserve rule constructor
  75          */
  76         public WhitespaceRule(int action, String element, int precedence) {
  77             // Determine the action (strip or preserve) for this rule
  78             _action = action;
  79 
  80             // Get the namespace and element name for this rule
  81             final int colon = element.lastIndexOf(':');
  82             if (colon >= 0) {
  83                 _namespace = element.substring(0,colon);
  84                 _element = element.substring(colon+1,element.length());
  85             }
  86             else {
  87                 _namespace = Constants.EMPTYSTRING;
  88                 _element = element;
  89             }
  90 
  91             // Determine the initial priority for this rule
  92             _priority = precedence << 2;
  93 
  94             // Get the strip/preserve type; either "NS:EL", "NS:*" or "*"
  95             if (_element.equals("*")) {
  96                 if (_namespace == Constants.EMPTYSTRING) {
  97                     _type = RULE_ALL;       // Strip/preserve _all_ elements
  98                     _priority += 2;         // Lowest priority
  99                 }
 100                 else {
 101                     _type = RULE_NAMESPACE; // Strip/reserve elements within NS
 102                     _priority += 1;         // Medium priority
 103                 }
 104             }
 105             else {
 106                 _type = RULE_ELEMENT;       // Strip/preserve single element
 107             }
 108         }
 109 
 110         /**
 111          * For sorting rules depending on priority
 112          */
 113         public int compareTo(WhitespaceRule other) {
 114             return _priority < other._priority
 115                 ? -1
 116                 : _priority > other._priority ? 1 : 0;
 117         }
 118 
 119         public int getAction() { return _action; }
 120         public int getStrength() { return _type; }
 121         public int getPriority() { return _priority; }
 122         public String getElement() { return _element; }
 123         public String getNamespace() { return _namespace; }
 124     }
 125 
 126     /**
 127      * Parse the attributes of the xsl:strip/preserve-space element.
 128      * The element should have not contents (ignored if any).
 129      */
 130     public void parseContents(Parser parser) {
 131         // Determine if this is an xsl:strip- or preserve-space element
 132         _action = _qname.getLocalPart().endsWith("strip-space")
 133             ? STRIP_SPACE : PRESERVE_SPACE;
 134 
 135         // Determine the import precedence
 136         _importPrecedence = parser.getCurrentImportPrecedence();
 137 
 138         // Get the list of elements to strip/preserve
 139         _elementList = getAttribute("elements");
 140         if (_elementList == null || _elementList.length() == 0) {
 141             reportError(this, parser, ErrorMsg.REQUIRED_ATTR_ERR, "elements");
 142             return;
 143         }
 144 
 145         final SymbolTable stable = parser.getSymbolTable();
 146         StringTokenizer list = new StringTokenizer(_elementList);
 147         StringBuffer elements = new StringBuffer(Constants.EMPTYSTRING);
 148 
 149         while (list.hasMoreElements()) {
 150             String token = list.nextToken();
 151             String prefix;
 152             String namespace;
 153             int col = token.indexOf(':');
 154 
 155             if (col != -1) {
 156                 namespace = lookupNamespace(token.substring(0,col));
 157                 if (namespace != null) {
 158                     elements.append(namespace).append(':').append(token.substring(col + 1));
 159                 } else {
 160                     elements.append(token);
 161                 }
 162             } else {
 163                 elements.append(token);
 164             }
 165 
 166             if (list.hasMoreElements())
 167                 elements.append(" ");
 168         }
 169         _elementList = elements.toString();
 170     }
 171 
 172 
 173     /**
 174      * De-tokenize the elements listed in the 'elements' attribute and
 175      * instanciate a set of strip/preserve rules.
 176      */
 177     public List<WhitespaceRule> getRules() {
 178         final List<WhitespaceRule> rules = new ArrayList<>();
 179         // Go through each element and instanciate strip/preserve-object
 180         final StringTokenizer list = new StringTokenizer(_elementList);
 181         while (list.hasMoreElements()) {
 182             rules.add(new WhitespaceRule(_action,
 183                                          list.nextToken(),
 184                                          _importPrecedence));
 185         }
 186         return rules;
 187     }
 188 
 189 
 190     /**
 191      * Scans through the rules vector and looks for a rule of higher
 192      * priority that contradicts the current rule.
 193      */
 194     @SuppressWarnings("fallthrough") // case RULE_NAMESPACE
 195     private static WhitespaceRule findContradictingRule(List<WhitespaceRule> rules,
 196                                                         WhitespaceRule rule) {
 197         for (WhitespaceRule currentRule : rules) {
 198             // We only consider rules with higher priority
 199             if (currentRule == rule) {
 200                 return null;
 201             }
 202 
 203             /*
 204             * See if there is a contradicting rule with higher priority.
 205             * If the rules has the same action then this rule is redundant,
 206             * if they have different action then this rule will never win.
 207             */
 208             switch (currentRule.getStrength()) {
 209                 case RULE_ALL:
 210                     return currentRule;
 211 
 212                 case RULE_ELEMENT:
 213                     if (!rule.getElement().equals(currentRule.getElement())) {
 214                         break;
 215                     }
 216                 // intentional fall-through
 217                 case RULE_NAMESPACE:
 218                     if (rule.getNamespace().equals(currentRule.getNamespace())) {
 219                         return currentRule;
 220                     }
 221                     break;
 222             }
 223         }
 224         return null;
 225     }
 226 
 227 
 228     /**
 229      * Orders a set or rules by priority, removes redundant rules and rules
 230      * that are shadowed by stronger, contradicting rules.
 231      */
 232     private static int prioritizeRules(List<WhitespaceRule> rules) {
 233         WhitespaceRule currentRule;
 234         int defaultAction = PRESERVE_SPACE;
 235 
 236         // Sort all rules with regard to priority
 237         quicksort(rules, 0, rules.size()-1);
 238 
 239         // Check if there are any "xsl:strip-space" elements at all.
 240         // If there are no xsl:strip elements we can ignore all xsl:preserve
 241         // elements and signal that all whitespaces should be preserved
 242         boolean strip = false;
 243         for (int i = 0; i < rules.size(); i++) {
 244             currentRule = rules.get(i);
 245             if (currentRule.getAction() == STRIP_SPACE) {
 246                 strip = true;
 247             }
 248         }
 249         // Return with default action: PRESERVE_SPACE
 250         if (!strip) {
 251             rules.clear();
 252             return PRESERVE_SPACE;
 253         }
 254 
 255         // Remove all rules that are contradicted by rules with higher priority
 256         for (int idx = 0; idx < rules.size(); ) {
 257             currentRule = rules.get(idx);
 258 
 259             // Remove this single rule if it has no purpose
 260             if (findContradictingRule(rules,currentRule) != null) {
 261                 rules.remove(idx);
 262             }
 263             else {
 264                 // Remove all following rules if this one overrides all
 265                 if (currentRule.getStrength() == RULE_ALL) {
 266                     defaultAction = currentRule.getAction();
 267                     for (int i = idx; i < rules.size(); i++) {
 268                         rules.remove(i);
 269                     }
 270                 }
 271                 // Skip to next rule (there might not be any)...
 272                 idx++;
 273             }
 274         }
 275 
 276         // The rules vector could be empty if first rule has strength RULE_ALL
 277         if (rules.isEmpty()) {
 278             return defaultAction;
 279         }
 280 
 281         // Now work backwards and strip away all rules that have the same
 282         // action as the default rule (no reason the check them at the end).
 283         do {
 284             currentRule = rules.get(rules.size() - 1);
 285             if (currentRule.getAction() == defaultAction) {
 286                 rules.remove(rules.size() - 1);
 287             }
 288             else {
 289                 break;
 290             }
 291         } while (rules.size() > 0);
 292 
 293         // Signal that whitespace detection predicate must be used.
 294         return defaultAction;
 295     }
 296 
 297     public static void compileStripSpace(BranchHandle strip[],
 298                                          int sCount,
 299                                          InstructionList il) {
 300         final InstructionHandle target = il.append(ICONST_1);
 301         il.append(IRETURN);
 302         for (int i = 0; i < sCount; i++) {
 303             strip[i].setTarget(target);
 304         }
 305     }
 306 
 307     public static void compilePreserveSpace(BranchHandle preserve[],
 308                                             int pCount,
 309                                             InstructionList il) {
 310         final InstructionHandle target = il.append(ICONST_0);
 311         il.append(IRETURN);
 312         for (int i = 0; i < pCount; i++) {
 313             preserve[i].setTarget(target);
 314         }
 315     }
 316 
 317     /*
 318     private static void compileDebug(ClassGenerator classGen,
 319                                      InstructionList il) {
 320         final ConstantPoolGen cpg = classGen.getConstantPool();
 321         final int prt = cpg.addMethodref("java/lang/System/out",
 322                                          "println",
 323                                          "(Ljava/lang/String;)V");
 324         il.append(DUP);
 325         il.append(new INVOKESTATIC(prt));
 326     }
 327     */
 328 
 329     /**
 330      * Compiles the predicate method
 331      */
 332     private static void compilePredicate(List<WhitespaceRule> rules,
 333                                          int defaultAction,
 334                                          ClassGenerator classGen) {
 335         final ConstantPoolGen cpg = classGen.getConstantPool();
 336         final InstructionList il = new InstructionList();
 337         final XSLTC xsltc = classGen.getParser().getXSLTC();
 338 
 339         // private boolean Translet.stripSpace(int type) - cannot be static
 340         final MethodGenerator stripSpace =
 341             new MethodGenerator(ACC_PUBLIC | ACC_FINAL ,
 342                         com.sun.org.apache.bcel.internal.generic.Type.BOOLEAN,
 343                         new com.sun.org.apache.bcel.internal.generic.Type[] {
 344                             Util.getJCRefType(DOM_INTF_SIG),
 345                             com.sun.org.apache.bcel.internal.generic.Type.INT,
 346                             com.sun.org.apache.bcel.internal.generic.Type.INT
 347                         },
 348                         new String[] { "dom","node","type" },
 349                         "stripSpace",classGen.getClassName(),il,cpg);
 350 
 351         classGen.addInterface("com/sun/org/apache/xalan/internal/xsltc/StripFilter");
 352 
 353         final int paramDom = stripSpace.getLocalIndex("dom");
 354         final int paramCurrent = stripSpace.getLocalIndex("node");
 355         final int paramType = stripSpace.getLocalIndex("type");
 356 
 357         BranchHandle strip[] = new BranchHandle[rules.size()];
 358         BranchHandle preserve[] = new BranchHandle[rules.size()];
 359         int sCount = 0;
 360         int pCount = 0;
 361 
 362         // Traverse all strip/preserve rules
 363         for (int i = 0; i<rules.size(); i++) {
 364             // Get the next rule in the prioritised list
 365             WhitespaceRule rule = rules.get(i);
 366 
 367             // Returns the namespace for a node in the DOM
 368             final int gns = cpg.addInterfaceMethodref(DOM_INTF,
 369                                                       "getNamespaceName",
 370                                                       "(I)Ljava/lang/String;");
 371 
 372             final int strcmp = cpg.addMethodref("java/lang/String",
 373                                                 "compareTo",
 374                                                 "(Ljava/lang/String;)I");
 375 
 376             // Handle elements="ns:*" type rule
 377             if (rule.getStrength() == RULE_NAMESPACE) {
 378                 il.append(new ALOAD(paramDom));
 379                 il.append(new ILOAD(paramCurrent));
 380                 il.append(new INVOKEINTERFACE(gns,2));
 381                 il.append(new PUSH(cpg, rule.getNamespace()));
 382                 il.append(new INVOKEVIRTUAL(strcmp));
 383                 il.append(ICONST_0);
 384 
 385                 if (rule.getAction() == STRIP_SPACE) {
 386                     strip[sCount++] = il.append(new IF_ICMPEQ(null));
 387                 }
 388                 else {
 389                     preserve[pCount++] = il.append(new IF_ICMPEQ(null));
 390                 }
 391             }
 392             // Handle elements="ns:el" type rule
 393             else if (rule.getStrength() == RULE_ELEMENT) {
 394                 // Create the QName for the element
 395                 final Parser parser = classGen.getParser();
 396                 QName qname;
 397                 if (rule.getNamespace() != Constants.EMPTYSTRING )
 398                     qname = parser.getQName(rule.getNamespace(), null,
 399                                             rule.getElement());
 400                 else
 401                     qname = parser.getQName(rule.getElement());
 402 
 403                 // Register the element.
 404                 final int elementType = xsltc.registerElement(qname);
 405                 il.append(new ILOAD(paramType));
 406                 il.append(new PUSH(cpg, elementType));
 407 
 408                 // Compare current node type with wanted element type
 409                 if (rule.getAction() == STRIP_SPACE)
 410                     strip[sCount++] = il.append(new IF_ICMPEQ(null));
 411                 else
 412                     preserve[pCount++] = il.append(new IF_ICMPEQ(null));
 413             }
 414         }
 415 
 416         if (defaultAction == STRIP_SPACE) {
 417             compileStripSpace(strip, sCount, il);
 418             compilePreserveSpace(preserve, pCount, il);
 419         }
 420         else {
 421             compilePreserveSpace(preserve, pCount, il);
 422             compileStripSpace(strip, sCount, il);
 423         }
 424 
 425         classGen.addMethod(stripSpace);
 426     }
 427 
 428     /**
 429      * Compiles the predicate method
 430      */
 431     private static void compileDefault(int defaultAction,
 432                                        ClassGenerator classGen) {
 433         final ConstantPoolGen cpg = classGen.getConstantPool();
 434         final InstructionList il = new InstructionList();
 435         final XSLTC xsltc = classGen.getParser().getXSLTC();
 436 
 437         // private boolean Translet.stripSpace(int type) - cannot be static
 438         final MethodGenerator stripSpace =
 439             new MethodGenerator(ACC_PUBLIC | ACC_FINAL ,
 440                         com.sun.org.apache.bcel.internal.generic.Type.BOOLEAN,
 441                         new com.sun.org.apache.bcel.internal.generic.Type[] {
 442                             Util.getJCRefType(DOM_INTF_SIG),
 443                             com.sun.org.apache.bcel.internal.generic.Type.INT,
 444                             com.sun.org.apache.bcel.internal.generic.Type.INT
 445                         },
 446                         new String[] { "dom","node","type" },
 447                         "stripSpace",classGen.getClassName(),il,cpg);
 448 
 449         classGen.addInterface("com/sun/org/apache/xalan/internal/xsltc/StripFilter");
 450 
 451         if (defaultAction == STRIP_SPACE)
 452             il.append(ICONST_1);
 453         else
 454             il.append(ICONST_0);
 455         il.append(IRETURN);
 456 
 457         classGen.addMethod(stripSpace);
 458     }
 459 
 460 
 461     /**
 462      * Takes a vector of WhitespaceRule objects and generates a predicate
 463      * method. This method returns the translets default action for handling
 464      * whitespace text-nodes:
 465      *    - USE_PREDICATE  (run the method generated by this method)
 466      *    - STRIP_SPACE    (always strip whitespace text-nodes)
 467      *    - PRESERVE_SPACE (always preserve whitespace text-nodes)
 468      */
 469     public static int translateRules(List<WhitespaceRule> rules,
 470                                      ClassGenerator classGen) {
 471         // Get the core rules in prioritized order
 472         final int defaultAction = prioritizeRules(rules);
 473         // The rules vector may be empty after prioritising
 474         if (rules.size() == 0) {
 475             compileDefault(defaultAction,classGen);
 476             return defaultAction;
 477         }
 478         // Now - create a predicate method and sequence through rules...
 479         compilePredicate(rules, defaultAction, classGen);
 480         // Return with the translets required action (
 481         return USE_PREDICATE;
 482     }
 483 
 484     /**
 485      * Sorts a range of rules with regard to PRIORITY only
 486      */
 487     private static void quicksort(List<WhitespaceRule> rules, int p, int r) {
 488         while (p < r) {
 489             final int q = partition(rules, p, r);
 490             quicksort(rules, p, q);
 491             p = q + 1;
 492         }
 493     }
 494 
 495     /**
 496      * Used with quicksort method above
 497      */
 498     private static int partition(List<WhitespaceRule> rules, int p, int r) {
 499         final WhitespaceRule x = rules.get((p+r) >>> 1);
 500         int i = p - 1, j = r + 1;
 501         while (true) {
 502             while (x.compareTo(rules.get(--j)) < 0) {
 503             }
 504             while (x.compareTo(rules.get(++i)) > 0) {
 505             }
 506             if (i < j) {
 507                 final WhitespaceRule tmp = rules.get(i);
 508                 rules.set(i, rules.get(j));
 509                 rules.set(j, tmp);
 510             }
 511             else {
 512                 return j;
 513             }
 514         }
 515     }
 516 
 517     /**
 518      * Type-check contents/attributes - nothing to do...
 519      */
 520     public Type typeCheck(SymbolTable stable) throws TypeCheckError {
 521         return Type.Void; // We don't return anything.
 522     }
 523 
 524     /**
 525      * This method should not produce any code
 526      */
 527     public void translate(ClassGenerator classGen, MethodGenerator methodGen) {
 528     }
 529 }