Source for gnu.xml.xpath.Selector

   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: }