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