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

   1 /* Steps.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 gnu.java.lang.CPStringBuilder;
  41
  42 import java.util.Collection;
  43 import java.util.Collections;
  44 import java.util.Iterator;
  45 import java.util.LinkedHashSet;
  46 import java.util.LinkedList;
  47 import java.util.Set;
  48 import javax.xml.namespace.QName;
  49 import org.w3c.dom.Attr;
  50 import org.w3c.dom.Node;
  51
  52 /**
  53  * A list of transitions between components in a location path.
  54  *
  55  * @author <a href='mailto:dog@gnu.org'>Chris Burdess</a>
  56  */
  57 public final class Steps
  58   extends Path
  59 {
  60
  61   final LinkedList<Expr> path;
  62
  63   public Steps()
  64   {
  65     this(new LinkedList<Expr>());
  66   }
  67
  68   Steps(LinkedList<Expr> path)
  69   {
  70     this.path = path;
  71   }
  72
  73   public boolean matches(Node context)
  74   {
  75     // Right to left
  76     return matches(context, path.size() - 1);
  77   }
  78
  79   boolean matches(Node context, int pos)
  80   {
  81     Pattern right = (Pattern) path.get(pos);
  82     if (!right.matches(context))
  83       {
  84         return false;
  85       }
  86     if (pos > 0)
  87       {
  88         Pattern left = (Pattern) path.get(pos - 1);
  89         for (Node candidate : possibleContexts(right, context))
  90           {
  91             if (left.matches(candidate) &&
  92                 matches(candidate, pos - 1))
  93               {
  94                 return true;
  95               }
  96             // keep going, there may be another candidate
  97           }
  98         return false;
  99       }
 100     return true;
 101   }
 102
 103   /**
 104    * Essentially the reverse of Selector.addCandidates.
 105    * The idea is to determine possible context nodes for a match.
 106    */
 107   Collection<Node> possibleContexts(Pattern pattern, Node context)
 108   {
 109     if (pattern instanceof Selector)
 110       {
 111         Selector s = (Selector) pattern;
 112         Collection<Node> candidates = new LinkedHashSet<Node>();
 113         switch (s.axis)
 114           {
 115           case Selector.PARENT:
 116             s.addChildNodes(context, candidates, false);
 117             break;
 118           case Selector.ANCESTOR:
 119             s.addChildNodes(context, candidates, true);
 120             break;
 121           case Selector.ANCESTOR_OR_SELF:
 122             candidates.add (context);
 123             s.addChildNodes(context, candidates, true);
 124             break;
 125           case Selector.CHILD:
 126             s.addParentNode(context, candidates, false);
 127             break;
 128           case Selector.DESCENDANT:
 129             s.addParentNode(context, candidates, true);
 130             break;
 131           case Selector.DESCENDANT_OR_SELF:
 132             candidates.add(context);
 133             s.addParentNode(context, candidates, true);
 134             break;
 135           case Selector.PRECEDING_SIBLING:
 136             s.addFollowingNodes(context, candidates, false);
 137             break;
 138           case Selector.FOLLOWING_SIBLING:
 139             s.addPrecedingNodes(context, candidates, false);
 140             break;
 141           case Selector.PRECEDING:
 142             s.addFollowingNodes(context, candidates, true);
 143             break;
 144           case Selector.FOLLOWING:
 145             s.addPrecedingNodes(context, candidates, true);
 146             break;
 147           case Selector.ATTRIBUTE:
 148           case Selector.NAMESPACE:
 149             if (context.getNodeType() == Node.ATTRIBUTE_NODE)
 150               {
 151                 candidates.add(((Attr) context).getOwnerElement());
 152               }
 153             break;
 154           case Selector.SELF:
 155             candidates.add(context);
 156             break;
 157           }
 158         return candidates;
 159       }
 160     return Collections.emptySet();
 161   }
 162
 163   @Override
 164   public Object evaluate(Node context, int pos, int len)
 165   {
 166     //System.err.println(toString()+" evaluate");
 167     // Left to right
 168     Iterator<Expr> i = path.iterator();
 169     Expr lhs = i.next();
 170     Object val = lhs.evaluate(context, pos, len);
 171     //System.err.println("\tevaluate "+lhs+" = "+val);
 172     while (val instanceof Collection && i.hasNext())
 173       {
 174         Path rhs = (Path) i.next();
 175         /* Suppression is safe, as we know context produces Collection<Node> */
 176         @SuppressWarnings("unchecked")
 177           Collection<Node> nodes = (Collection<Node>) val;
 178         val = rhs.evaluate(context, nodes);
 179         //System.err.println("\tevaluate "+rhs+" = "+val);
 180       }
 181     return val;
 182   }
 183
 184   @Override
 185   Collection<Node> evaluate(Node context, Collection<Node> ns)
 186   {
 187     // Left to right
 188     Iterator<Expr> i = path.iterator();
 189     Expr lhs = i.next();
 190     if (lhs instanceof Path)
 191       {
 192         ns = ((Path) lhs).evaluate(context, ns);
 193       }
 194     else
 195       {
 196         Set<Node> acc = new LinkedHashSet<Node>();
 197         int pos = 1, len = ns.size();
 198         for (Node node : ns)
 199           {
 200             Object ret = lhs.evaluate(node, pos++, len);
 201             if (ret instanceof Collection)
 202               {
 203                 /* Suppression is safe, as we know context produces Collection<Node> */
 204                 @SuppressWarnings("unchecked")
 205                   Collection<Node> nodes = (Collection<Node>) ret;
 206                 acc.addAll(nodes);
 207               }
 208           }
 209         ns = acc;
 210       }
 211     while (i.hasNext())
 212       {
 213         Path rhs = (Path) i.next();
 214         ns = rhs.evaluate(context, ns);
 215       }
 216     return ns;
 217   }
 218
 219   public Expr clone(Object context)
 220   {
 221     int len = path.size();
 222     LinkedList<Expr> path2 = new LinkedList<Expr>();
 223     for (int i = 0; i < len; i++)
 224       {
 225         path2.add(path.get(i).clone(context));
 226       }
 227     return new Steps(path2);
 228   }
 229
 230   public boolean references(QName var)
 231   {
 232     for (Iterator<Expr> i = path.iterator(); i.hasNext(); )
 233       {
 234         if (i.next().references(var))
 235           {
 236             return true;
 237           }
 238       }
 239     return false;
 240   }
 241
 242   public String toString()
 243   {
 244     CPStringBuilder buf = new CPStringBuilder();
 245     Iterator<Expr> i = path.iterator();
 246     Expr expr = i.next();
 247     if (!(expr instanceof Root))
 248       {
 249         buf.append(expr);
 250       }
 251     while (i.hasNext())
 252       {
 253         expr = i.next();
 254         buf.append('/');
 255         buf.append(expr);
 256       }
 257     return buf.toString();
 258   }
 259
 260 }