libjava/classpath/gnu/xml/xpath/Selector.java

   1 /* Selector.java --
   2    Copyright (C) 2004 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38 package gnu.xml.xpath;
  39
  40 import java.util.ArrayList;
  41 import java.util.Collection;
  42 import java.util.Iterator;
  43 import java.util.LinkedHashSet;
  44 import java.util.List;
  45 import java.util.Set;
  46 import javax.xml.XMLConstants;
  47 import javax.xml.namespace.QName;
  48 import org.w3c.dom.Attr;
  49 import org.w3c.dom.NamedNodeMap;
  50 import org.w3c.dom.Node;
  51
  52 /**
  53  * A single component of a location path.
  54  *
  55  * @author <a href='mailto:dog@gnu.org'>Chris Burdess</a>
  56  */
  57 public final class Selector
  58   extends Path
  59 {
  60
  61   public static final int ANCESTOR = 0;
  62   public static final int ANCESTOR_OR_SELF = 1;
  63   public static final int ATTRIBUTE = 2;
  64   public static final int CHILD = 3;
  65   public static final int DESCENDANT = 4;
  66   public static final int DESCENDANT_OR_SELF = 5;
  67   public static final int FOLLOWING = 6;
  68   public static final int FOLLOWING_SIBLING = 7;
  69   public static final int NAMESPACE = 8;
  70   public static final int PARENT = 9;
  71   public static final int PRECEDING = 10;
  72   public static final int PRECEDING_SIBLING = 11;
  73   public static final int SELF = 12;
  74
  75   /**
  76    * Axis to select nodes in.
  77    */
  78   final int axis;
  79
  80   /**
  81    * List of tests to perform on candidates.
  82    */
  83   final Test[] tests;
  84
  85   public Selector(int axis, List tests)
  86   {
  87     this.axis = axis;
  88     this.tests = new Test[tests.size()];
  89     tests.toArray(this.tests);
  90     if (axis == NAMESPACE &&
  91         this.tests.length > 0 &&
  92         this.tests[0] instanceof NameTest)
  93       {
  94         NameTest nt = (NameTest) this.tests[0];
  95         this.tests[0] = new NamespaceTest(nt.qName, nt.anyLocalName, nt.any);
  96       }
  97   }
  98
  99   /**
 100    * Returns the list of tests to perform on candidates.
 101    */
 102   public Test[] getTests()
 103   {
 104     return tests;
 105   }
 106
 107   public boolean matches(Node context)
 108   {
 109     short nodeType = context.getNodeType();
 110     switch (axis)
 111       {
 112       case CHILD:
 113         if (nodeType == Node.ATTRIBUTE_NODE)
 114           {
 115             return false;
 116           }
 117         break;
 118       case ATTRIBUTE:
 119       case NAMESPACE:
 120         if (nodeType != Node.ATTRIBUTE_NODE)
 121           {
 122             return false;
 123           }
 124         break;
 125       case DESCENDANT_OR_SELF:
 126         return true;
 127       default:
 128         return false;
 129       }
 130     int tlen = tests.length;
 131     if (tlen > 0)
 132       {
 133         int pos = getContextPosition(context);
 134         int len = getContextSize(context);
 135         for (int j = 0; j < tlen && len > 0; j++)
 136           {
 137             Test test = tests[j];
 138             if (!test.matches(context, pos, len))
 139               {
 140                 return false;
 141               }
 142           }
 143       }
 144     return true;
 145   }
 146
 147   private int getContextPosition(Node ctx)
 148   {
 149     int pos = 1;
 150     for (ctx = ctx.getPreviousSibling(); ctx != null;
 151          ctx = ctx.getPreviousSibling())
 152       {
 153         pos++;
 154       }
 155     return pos;
 156   }
 157
 158   private int getContextSize(Node ctx)
 159   {
 160     if (ctx.getNodeType() == Node.ATTRIBUTE_NODE)
 161       {
 162         Node parent = ((Attr) ctx).getOwnerElement();
 163         return parent.getAttributes().getLength();
 164       }
 165     Node parent = ctx.getParentNode();
 166     if (parent != null)
 167       {
 168         return parent.getChildNodes().getLength();
 169       }
 170     return 1;
 171   }
 172
 173   public Object evaluate(Node context, int pos, int len)
 174   {
 175     Set acc = new LinkedHashSet();
 176     addCandidates(context, acc);
 177     List candidates = new ArrayList(acc);
 178     //Collections.sort(candidates, documentOrderComparator);
 179     List ret = filterCandidates(candidates, false);
 180     return ret;
 181   }
 182
 183   Collection evaluate(Node context, Collection ns)
 184   {
 185     Set acc = new LinkedHashSet();
 186     for (Iterator i = ns.iterator(); i.hasNext(); )
 187       {
 188         addCandidates((Node) i.next(), acc);
 189       }
 190     List candidates = new ArrayList(acc);
 191     //Collections.sort(candidates, documentOrderComparator);
 192     List ret = filterCandidates(candidates, true);
 193     return ret;
 194   }
 195
 196   /**
 197    * Filter the given list of candidates according to the node tests.
 198    */
 199   List filterCandidates(List candidates, boolean cascade)
 200   {
 201     int len = candidates.size();
 202     int tlen = tests.length;
 203     if (tlen > 0 && len > 0)
 204       {
 205         // Present the result of each successful generation to the next test
 206         for (int j = 0; j < tlen && len > 0; j++)
 207           {
 208             Test test = tests[j];
 209             List successful = new ArrayList(len);
 210             for (int i = 0; i < len; i++)
 211               {
 212                 Node node = (Node) candidates.get(i);
 213                 if (cascade)
 214                   {
 215                     // Documents and DocumentFragments should be considered
 216                     // if part of a location path where the axis involves
 217                     // the SELF concept
 218                     short nodeType = node.getNodeType();
 219                     if ((nodeType == Node.DOCUMENT_NODE ||
 220                          nodeType == Node.DOCUMENT_FRAGMENT_NODE) &&
 221                         (axis == DESCENDANT_OR_SELF ||
 222                          axis == ANCESTOR_OR_SELF ||
 223                          axis == SELF) &&
 224                         (tests.length == 1 &&
 225                          tests[0] instanceof NodeTypeTest &&
 226                          ((NodeTypeTest) tests[0]).type == (short) 0))
 227                       {
 228                         successful.add(node);
 229                         continue;
 230                       }
 231                   }
 232                 if (test.matches(node, i + 1, len))
 233                   {
 234                     successful.add(node);
 235                   }
 236                 /*
 237                    System.err.println("Testing "+node);
 238                    int p = getContextPosition(node);
 239                    int l = getContextSize(node);
 240                    if (test.matches(node, p, l))
 241                    {
 242                    successful.add(node);
 243                    }*/
 244               }
 245             candidates = successful;
 246             len = candidates.size();
 247           }
 248       }
 249     return candidates;
 250   }
 251
 252   void addCandidates(Node context, Collection candidates)
 253   {
 254     // Build list of candidates
 255     switch (axis)
 256       {
 257       case CHILD:
 258         addChildNodes(context, candidates, false);
 259         break;
 260       case DESCENDANT:
 261         addChildNodes(context, candidates, true);
 262         break;
 263       case DESCENDANT_OR_SELF:
 264         candidates.add (context);
 265         addChildNodes(context, candidates, true);
 266         break;
 267       case PARENT:
 268         addParentNode(context, candidates, false);
 269         break;
 270       case ANCESTOR:
 271         addParentNode(context, candidates, true);
 272         break;
 273       case ANCESTOR_OR_SELF:
 274         candidates.add(context);
 275         addParentNode(context, candidates, true);
 276         break;
 277       case FOLLOWING_SIBLING:
 278         addFollowingNodes(context, candidates, false);
 279         break;
 280       case PRECEDING_SIBLING:
 281         addPrecedingNodes(context, candidates, false);
 282         break;
 283       case FOLLOWING:
 284         addFollowingNodes(context, candidates, true);
 285         break;
 286       case PRECEDING:
 287         addPrecedingNodes(context, candidates, true);
 288         break;
 289       case ATTRIBUTE:
 290         addAttributes(context, candidates);
 291         break;
 292       case NAMESPACE:
 293         addNamespaceAttributes(context, candidates);
 294         break;
 295       case SELF:
 296         candidates.add(context);
 297         break;
 298       }
 299   }
 300
 301   void addChildNodes(Node context, Collection acc, boolean recurse)
 302   {
 303     Node child = context.getFirstChild();
 304     while (child != null)
 305       {
 306         acc.add(child);
 307         if (recurse)
 308           {
 309             addChildNodes(child, acc, recurse);
 310           }
 311         child = child.getNextSibling();
 312       }
 313   }
 314
 315   void addParentNode(Node context, Collection acc, boolean recurse)
 316   {
 317     Node parent = (context.getNodeType() == Node.ATTRIBUTE_NODE) ?
 318       ((Attr) context).getOwnerElement() : context.getParentNode();
 319     if (parent != null)
 320       {
 321         acc.add(parent);
 322         if (recurse)
 323           {
 324             addParentNode(parent, acc, recurse);
 325           }
 326       }
 327   }
 328
 329   void addFollowingNodes(Node context, Collection acc, boolean recurse)
 330   {
 331     Node cur = context.getNextSibling();
 332     while (cur != null)
 333       {
 334         acc.add(cur);
 335         if (recurse)
 336           {
 337             addChildNodes(cur, acc, true);
 338           }
 339         cur = cur.getNextSibling();
 340       }
 341     if (recurse)
 342       {
 343         context = (context.getNodeType() == Node.ATTRIBUTE_NODE) ?
 344           ((Attr) context).getOwnerElement() : context.getParentNode();
 345         if (context != null)
 346           {
 347             addFollowingNodes(context, acc, recurse);
 348           }
 349       }
 350   }
 351
 352   void addPrecedingNodes(Node context, Collection acc, boolean recurse)
 353   {
 354     Node cur = context.getPreviousSibling();
 355     while (cur != null)
 356       {
 357         acc.add(cur);
 358         if (recurse)
 359           {
 360             addChildNodes(cur, acc, true);
 361           }
 362         cur = cur.getPreviousSibling();
 363       }
 364     if (recurse)
 365       {
 366         context = (context.getNodeType() == Node.ATTRIBUTE_NODE) ?
 367           ((Attr) context).getOwnerElement() : context.getParentNode();
 368         if (context != null)
 369           {
 370             addPrecedingNodes(context, acc, recurse);
 371           }
 372       }
 373   }
 374
 375   void addAttributes(Node context, Collection acc)
 376   {
 377     NamedNodeMap attrs = context.getAttributes();
 378     if (attrs != null)
 379       {
 380         int attrLen = attrs.getLength();
 381         for (int i = 0; i < attrLen; i++)
 382           {
 383             Node attr = attrs.item(i);
 384             if (!isNamespaceAttribute(attr))
 385               {
 386                 acc.add(attr);
 387               }
 388           }
 389       }
 390   }
 391
 392   void addNamespaceAttributes(Node context, Collection acc)
 393   {
 394     NamedNodeMap attrs = context.getAttributes();
 395     if (attrs != null)
 396       {
 397         int attrLen = attrs.getLength();
 398         for (int i = 0; i < attrLen; i++)
 399           {
 400             Node attr = attrs.item(i);
 401             if (isNamespaceAttribute(attr))
 402               {
 403                 acc.add(attr);
 404               }
 405           }
 406       }
 407   }
 408
 409   final boolean isNamespaceAttribute(Node node)
 410   {
 411     String uri = node.getNamespaceURI();
 412     return (XMLConstants.XMLNS_ATTRIBUTE_NS_URI.equals(uri) ||
 413             XMLConstants.XMLNS_ATTRIBUTE.equals(node.getPrefix()) ||
 414             XMLConstants.XMLNS_ATTRIBUTE.equals(node.getNodeName()));
 415   }
 416
 417   public Expr clone(Object context)
 418   {
 419     int len = tests.length;
 420     List tests2 = new ArrayList(len);
 421     for (int i = 0; i < len; i++)
 422       {
 423         tests2.add(tests[i].clone(context));
 424       }
 425     return new Selector(axis, tests2);
 426   }
 427
 428   public boolean references(QName var)
 429   {
 430     for (int i = 0; i < tests.length; i++)
 431       {
 432         if (tests[i].references(var))
 433           {
 434             return true;
 435           }
 436       }
 437     return false;
 438   }
 439
 440   public String toString()
 441   {
 442     StringBuffer buf = new StringBuffer();
 443     switch (axis)
 444       {
 445       case ANCESTOR:
 446         buf.append("ancestor::");
 447         break;
 448       case ANCESTOR_OR_SELF:
 449         buf.append("ancestor-or-self::");
 450         break;
 451       case ATTRIBUTE:
 452         if (tests.length == 0 ||
 453             (tests[0] instanceof NameTest))
 454           {
 455             buf.append('@');
 456           }
 457         else
 458           {
 459             buf.append("attribute::");
 460           }
 461         break;
 462       case CHILD:
 463         //buf.append("child::");
 464         break;
 465       case DESCENDANT:
 466         buf.append("descendant::");
 467         break;
 468       case DESCENDANT_OR_SELF:
 469         buf.append("descendant-or-self::");
 470         break;
 471       case FOLLOWING:
 472         buf.append("following::");
 473         break;
 474       case FOLLOWING_SIBLING:
 475         buf.append("following-sibling::");
 476         break;
 477       case NAMESPACE:
 478         buf.append("namespace::");
 479         break;
 480       case PARENT:
 481         if (tests.length == 0 ||
 482             (tests[0] instanceof NodeTypeTest &&
 483              ((NodeTypeTest) tests[0]).type == 0))
 484           {
 485             return "..";
 486           }
 487         buf.append("parent::");
 488         break;
 489       case PRECEDING:
 490         buf.append("preceding::");
 491         break;
 492       case PRECEDING_SIBLING:
 493         buf.append("preceding-sibling::");
 494         break;
 495       case SELF:
 496         if (tests.length == 0 ||
 497             (tests[0] instanceof NodeTypeTest &&
 498              ((NodeTypeTest) tests[0]).type == 0))
 499           {
 500             return ".";
 501           }
 502         buf.append("self::");
 503         break;
 504       }
 505     if (tests.length == 0)
 506       {
 507         buf.append('*');
 508       }
 509     else
 510       {
 511         for (int i = 0; i < tests.length; i++)
 512           {
 513             buf.append(tests[i]);
 514           }
 515       }
 516     return buf.toString();
 517   }
 518
 519 }