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