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

   1 /* Selector.java --
   2    Copyright (C) 2004,2006 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 gnu.java.lang.CPStringBuilder;
  41
  42 import java.util.ArrayList;
  43 import java.util.Collection;
  44 import java.util.Iterator;
  45 import java.util.LinkedHashSet;
  46 import java.util.List;
  47 import java.util.Set;
  48 import javax.xml.XMLConstants;
  49 import javax.xml.namespace.QName;
  50 import org.w3c.dom.Attr;
  51 import org.w3c.dom.NamedNodeMap;
  52 import org.w3c.dom.Node;
  53
  54 /**
  55  * A single component of a location path.
  56  *
  57  * @author <a href='mailto:dog@gnu.org'>Chris Burdess</a>
  58  */
  59 public final class Selector
  60   extends Path
  61 {
  62
  63   public static final int ANCESTOR = 0;
  64   public static final int ANCESTOR_OR_SELF = 1;
  65   public static final int ATTRIBUTE = 2;
  66   public static final int CHILD = 3;
  67   public static final int DESCENDANT = 4;
  68   public static final int DESCENDANT_OR_SELF = 5;
  69   public static final int FOLLOWING = 6;
  70   public static final int FOLLOWING_SIBLING = 7;
  71   public static final int NAMESPACE = 8;
  72   public static final int PARENT = 9;
  73   public static final int PRECEDING = 10;
  74   public static final int PRECEDING_SIBLING = 11;
  75   public static final int SELF = 12;
  76
  77   /**
  78    * Axis to select nodes in.
  79    */
  80   final int axis;
  81
  82   /**
  83    * List of tests to perform on candidates.
  84    */
  85   final Test[] tests;
  86
  87   public Selector(int axis, List<? extends Test> tests)
  88   {
  89     this.axis = axis;
  90     int len = tests.size();
  91     this.tests = new Test[(len == 0) ? 1 : len];
  92     if (len > 0)
  93       tests.toArray(this.tests);
  94     else
  95       this.tests[0] = new NodeTypeTest((short) 0);
  96     if (axis == NAMESPACE && this.tests[0] instanceof NameTest)
  97       {
  98         NameTest nt = (NameTest) this.tests[0];
  99         this.tests[0] = new NamespaceTest(nt.qName, nt.anyLocalName, nt.any);
 100       }
 101   }
 102
 103   /**
 104    * Returns the list of tests to perform on candidates.
 105    */
 106   public Test[] getTests()
 107   {
 108     return tests;
 109   }
 110
 111   public boolean matches(Node context)
 112   {
 113     // If called directly, selector is the top level of the path
 114     return matches(context,
 115                    getContextPosition(context),
 116                    getContextSize(context));
 117   }
 118
 119   boolean matches(Node context, int pos, int len)
 120   {
 121     short nodeType = context.getNodeType();
 122     switch (axis)
 123       {
 124       case CHILD:
 125         if (nodeType == Node.ATTRIBUTE_NODE)
 126           return false;
 127         break;
 128       case ATTRIBUTE:
 129       case NAMESPACE:
 130         if (nodeType != Node.ATTRIBUTE_NODE)
 131           return false;
 132         break;
 133       case DESCENDANT_OR_SELF:
 134         return true;
 135       default:
 136         return false;
 137       }
 138     for (int j = 0; j < tests.length && len > 0; j++)
 139       {
 140         Test test = tests[j];
 141         if (!test.matches(context, pos, len))
 142           return false;
 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         if (tests[0].matches(ctx, 1, 1))
 154           pos++;
 155       }
 156     return pos;
 157   }
 158
 159   private int getContextSize(Node ctx)
 160   {
 161     if (ctx.getNodeType() == Node.ATTRIBUTE_NODE)
 162       {
 163         Node owner = ((Attr) ctx).getOwnerElement();
 164         return owner.getAttributes().getLength();
 165       }
 166     int count = 1;
 167     Node sib = ctx.getPreviousSibling();
 168     for (; sib != null; sib = sib.getPreviousSibling())
 169       {
 170         if (tests[0].matches(ctx, 1, 1))
 171           count++;
 172       }
 173     sib = ctx.getNextSibling();
 174     for (; sib != null; sib = sib.getNextSibling())
 175       {
 176         if (tests[0].matches(ctx, 1, 1))
 177           count++;
 178       }
 179     return count;
 180   }
 181
 182
 183   @Override
 184   public Object evaluate(Node context, int pos, int len)
 185   {
 186     Set<Node> acc = new LinkedHashSet<Node>();
 187     addCandidates(context, acc);
 188     List<Node> candidates = new ArrayList<Node>(acc);
 189     List<Node> ret = filterCandidates(candidates, false);
 190     return ret;
 191   }
 192
 193   Collection<Node> evaluate(Node context, Collection<Node> ns)
 194   {
 195     Set<Node> acc = new LinkedHashSet<Node>();
 196     for (Iterator<Node> i = ns.iterator(); i.hasNext(); )
 197       addCandidates(i.next(), acc);
 198     List<Node> candidates = new ArrayList<Node>(acc);
 199     List<Node> ret = filterCandidates(candidates, true);
 200     return ret;
 201   }
 202
 203   /**
 204    * Filter the given list of candidates according to the node tests.
 205    */
 206   List<Node> filterCandidates(List<Node> candidates, boolean cascade)
 207   {
 208     int len = candidates.size();
 209     int tlen = tests.length;
 210     if (tlen > 0 && len > 0)
 211       {
 212         // Present the result of each successful generation to the next test
 213         for (int j = 0; j < tlen && len > 0; j++)
 214           {
 215             Test test = tests[j];
 216             List<Node> successful = new ArrayList<Node>(len);
 217             for (int i = 0; i < len; i++)
 218               {
 219                 Node node = candidates.get(i);
 220                 if (cascade)
 221                   {
 222                     // Documents and DocumentFragments should be considered
 223                     // if part of a location path where the axis involves
 224                     // the SELF concept
 225                     short nodeType = node.getNodeType();
 226                     if ((nodeType == Node.DOCUMENT_NODE ||
 227                          nodeType == Node.DOCUMENT_FRAGMENT_NODE) &&
 228                         (axis == DESCENDANT_OR_SELF ||
 229                          axis == ANCESTOR_OR_SELF ||
 230                          axis == SELF) &&
 231                         (tests.length == 1 &&
 232                          tests[0] instanceof NodeTypeTest &&
 233                          ((NodeTypeTest) tests[0]).type == (short) 0))
 234                       {
 235                         successful.add(node);
 236                         continue;
 237                       }
 238                   }
 239                 if (test.matches(node, i + 1, len))
 240                   successful.add(node);
 241               }
 242             candidates = successful;
 243             len = candidates.size();
 244           }
 245       }
 246     return candidates;
 247   }
 248
 249   void addCandidates(Node context, Collection<Node> candidates)
 250   {
 251     // Build list of candidates
 252     switch (axis)
 253       {
 254       case CHILD:
 255         addChildNodes(context, candidates, false);
 256         break;
 257       case DESCENDANT:
 258         addChildNodes(context, candidates, true);
 259         break;
 260       case DESCENDANT_OR_SELF:
 261         candidates.add (context);
 262         addChildNodes(context, candidates, true);
 263         break;
 264       case PARENT:
 265         addParentNode(context, candidates, false);
 266         break;
 267       case ANCESTOR:
 268         addParentNode(context, candidates, true);
 269         break;
 270       case ANCESTOR_OR_SELF:
 271         candidates.add(context);
 272         addParentNode(context, candidates, true);
 273         break;
 274       case FOLLOWING_SIBLING:
 275         addFollowingNodes(context, candidates, false);
 276         break;
 277       case PRECEDING_SIBLING:
 278         addPrecedingNodes(context, candidates, false);
 279         break;
 280       case FOLLOWING:
 281         addFollowingNodes(context, candidates, true);
 282         break;
 283       case PRECEDING:
 284         addPrecedingNodes(context, candidates, true);
 285         break;
 286       case ATTRIBUTE:
 287         addAttributes(context, candidates);
 288         break;
 289       case NAMESPACE:
 290         addNamespaceAttributes(context, candidates);
 291         break;
 292       case SELF:
 293         candidates.add(context);
 294         break;
 295       }
 296   }
 297
 298   void addChildNodes(Node context, Collection<Node> acc, boolean recurse)
 299   {
 300     Node child = context.getFirstChild();
 301     while (child != null)
 302       {
 303         acc.add(child);
 304         if (recurse)
 305           addChildNodes(child, acc, recurse);
 306         child = child.getNextSibling();
 307       }
 308   }
 309
 310   void addParentNode(Node context, Collection<Node> acc, boolean recurse)
 311   {
 312     Node parent = (context.getNodeType() == Node.ATTRIBUTE_NODE) ?
 313       ((Attr) context).getOwnerElement() : context.getParentNode();
 314     if (parent != null)
 315       {
 316         acc.add(parent);
 317         if (recurse)
 318           addParentNode(parent, acc, recurse);
 319       }
 320   }
 321
 322   void addFollowingNodes(Node context, Collection<Node> acc, boolean recurse)
 323   {
 324     if (context != null && recurse)
 325       addChildNodes(context, acc, true);
 326     Node cur = (context.getNodeType() == Node.ATTRIBUTE_NODE) ? null :
 327       context.getNextSibling();
 328     while (cur != null)
 329       {
 330         acc.add(cur);
 331         if (recurse)
 332           addChildNodes(cur, acc, true);
 333         cur = cur.getNextSibling();
 334       }
 335     if (recurse)
 336       {
 337         while (context != null)
 338           {
 339             context = (context.getNodeType() == Node.ATTRIBUTE_NODE) ?
 340               ((Attr) context).getOwnerElement() : context.getParentNode();
 341             if (context != null)
 342               {
 343                 cur = context.getNextSibling();
 344                 while (cur != null)
 345                   {
 346                     acc.add(cur);
 347                     if (recurse)
 348                       addChildNodes(cur, acc, true);
 349                     cur = cur.getNextSibling();
 350                   }
 351               }
 352           }
 353       }
 354   }
 355
 356   void addPrecedingNodes(Node context, Collection<Node> acc, boolean recurse)
 357   {
 358     Node cur = (context.getNodeType() == Node.ATTRIBUTE_NODE) ? null :
 359       context.getPreviousSibling();
 360     while (cur != null)
 361       {
 362         acc.add(cur);
 363         if (recurse)
 364           addChildNodes(cur, acc, true);
 365         cur = cur.getPreviousSibling();
 366       }
 367     if (recurse)
 368       {
 369         cur = context;
 370         cur = (cur.getNodeType() == Node.ATTRIBUTE_NODE) ?
 371           ((Attr) cur).getOwnerElement() : cur.getParentNode();
 372         if (cur != null)
 373           addPrecedingNodes(cur, acc, recurse);
 374       }
 375   }
 376
 377   void addAttributes(Node context, Collection<Node> acc)
 378   {
 379     NamedNodeMap attrs = context.getAttributes();
 380     if (attrs != null)
 381       {
 382         int attrLen = attrs.getLength();
 383         for (int i = 0; i < attrLen; i++)
 384           {
 385             Node attr = attrs.item(i);
 386             if (!isNamespaceAttribute(attr))
 387               {
 388                 acc.add(attr);
 389               }
 390           }
 391       }
 392   }
 393
 394   void addNamespaceAttributes(Node context, Collection<Node> acc)
 395   {
 396     NamedNodeMap attrs = context.getAttributes();
 397     if (attrs != null)
 398       {
 399         int attrLen = attrs.getLength();
 400         for (int i = 0; i < attrLen; i++)
 401           {
 402             Node attr = attrs.item(i);
 403             if (isNamespaceAttribute(attr))
 404               acc.add(attr);
 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<Test> tests2 = new ArrayList<Test>(len);
 421     for (int i = 0; i < len; i++)
 422       tests2.add(tests[i].clone(context));
 423     return new Selector(axis, tests2);
 424   }
 425
 426   public boolean references(QName var)
 427   {
 428     for (int i = 0; i < tests.length; i++)
 429       {
 430         if (tests[i].references(var))
 431           return true;
 432       }
 433     return false;
 434   }
 435
 436   public String toString()
 437   {
 438     CPStringBuilder buf = new CPStringBuilder();
 439     switch (axis)
 440       {
 441       case ANCESTOR:
 442         buf.append("ancestor::");
 443         break;
 444       case ANCESTOR_OR_SELF:
 445         buf.append("ancestor-or-self::");
 446         break;
 447       case ATTRIBUTE:
 448         if (tests.length == 0 ||
 449             (tests[0] instanceof NameTest))
 450           buf.append('@');
 451         else
 452           buf.append("attribute::");
 453         break;
 454       case CHILD:
 455         //buf.append("child::");
 456         break;
 457       case DESCENDANT:
 458         buf.append("descendant::");
 459         break;
 460       case DESCENDANT_OR_SELF:
 461         buf.append("descendant-or-self::");
 462         break;
 463       case FOLLOWING:
 464         buf.append("following::");
 465         break;
 466       case FOLLOWING_SIBLING:
 467         buf.append("following-sibling::");
 468         break;
 469       case NAMESPACE:
 470         buf.append("namespace::");
 471         break;
 472       case PARENT:
 473         if (tests.length == 0 ||
 474             (tests[0] instanceof NodeTypeTest &&
 475              ((NodeTypeTest) tests[0]).type == 0))
 476           return "..";
 477         buf.append("parent::");
 478         break;
 479       case PRECEDING:
 480         buf.append("preceding::");
 481         break;
 482       case PRECEDING_SIBLING:
 483         buf.append("preceding-sibling::");
 484         break;
 485       case SELF:
 486         if (tests.length == 0 ||
 487             (tests[0] instanceof NodeTypeTest &&
 488              ((NodeTypeTest) tests[0]).type == 0))
 489           return ".";
 490         buf.append("self::");
 491         break;
 492       }
 493     if (tests.length == 0)
 494       buf.append("[error]");
 495     else
 496       {
 497         for (int i = 0; i < tests.length; i++)
 498           buf.append(tests[i]);
 499       }
 500     return buf.toString();
 501   }
 502
 503 }