gt:             PathMapArc thisArc = (PathMapArc)node.arcs.get(i);
context: /**
  * Copyright (C) 2010 Orbeon, Inc.
  *
  * This program is free software; you can redistribute it and/or modify it under the terms of the
  * GNU Lesser General Public License as published by the Free Software Foundation; either version
  * 2.1 of the License, or (at your option) any later version.
  *
  * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  * See the GNU Lesser General Public License for more details.
  *
  * The full text of the license is available at http://www.gnu.org/copyleft/lesser.html
  */
  package org.orbeon.saxon.expr;
  
  import org.orbeon.saxon.Configuration;
  import org.orbeon.saxon.functions.*;
  import org.orbeon.saxon.om.Axis;
  import org.orbeon.saxon.pattern.AnyNodeTest;
  import org.orbeon.saxon.pattern.NodeKindTest;
  import org.orbeon.saxon.query.StaticQueryContext;
  import org.orbeon.saxon.query.XQueryExpression;
  import org.orbeon.saxon.sxpath.XPathEvaluator;
  import org.orbeon.saxon.sxpath.XPathExpression;
  import org.orbeon.saxon.trans.XPathException;
  
  import java.io.*;
  import java.net.URI;
  import java.net.URISyntaxException;
  import java.util.*;
  
  /**
  * A PathMap is a description of all the paths followed by an expression.
  * It is a set of trees. Each tree contains as its root an expression that selects
  * nodes without any dependency on the context. The arcs in the tree are axis steps.
  * So the expression doc('a.xml')/a[b=2]/c has a single root (the call on doc()), with
  * a single arc representing child::a, this leads to a node which has two further arcs
  * representing child::b and child::c. Because element b is atomized, there will also be
  * an arc for the step descendant::text() indicating the requirement to access the text
  * nodes of the element.
  *
  * <p>The current implementation works only for XPath 2.0 expressions (for example, constructs
  * like xsl:for-each-group are not handled.)</p>
  *
  * <p>This class, together with the overloaded method
  * {@link Expression#addToPathMap(PathMap, org.orbeon.saxon.expr.PathMap.PathMapNodeSet)} can be
  * seen as an implementation of the static path analysis algorithm given in section 4 of
  * <a href="http://www-db.research.bell-labs.com/user/simeon/xml_projection.pdf">A. Marian and J. Simeon,
  * Projecting XML Documents, VLDB 2003</a>.</p>
  */
  
  public class PathMap implements Cloneable {
  
      private List<PathMapRoot> pathMapRoots = new ArrayList<PathMapRoot>();        // a list of PathMapRoot objects
      private HashMap<Binding, PathMapNodeSet> pathsForVariables = new HashMap<Binding, PathMapNodeSet>();  // a map from a variable Binding to a PathMapNodeSet
  
      // ORBEON
      private Map<String, PathMap> inScopeVariables;
  
      public void setInScopeVariables(Map<String, PathMap> inScopeVariables) {
          this.inScopeVariables = inScopeVariables;
      }
  
      private Object pathMapContext;
  
      public Object getPathMapContext() {
          return pathMapContext;
      }
  
      public void setPathMapContext(Object pathMapContext) {
          this.pathMapContext = pathMapContext;
      }
  
      private boolean invalidated;    // whether during PathMap construction it is found that we cannot produce a meaningful result
  
      /**
       * A node in the path map. A node holds a set of arcs, each representing a link to another
       * node in the path map.
       */
  
      public static class PathMapNode implements Cloneable {
          List<PathMapArc> arcs;              // a list of PathMapArcs
          private boolean returnable;
          private boolean atomized;
          private boolean hasUnknownDependencies;
  
          // ORBEON
          @Override
          public PathMapNode clone() throws CloneNotSupportedException {
              final PathMapNode cloned = (PathMapNode) super.clone();
  
              if (arcs != null) {
                  cloned.arcs = new ArrayList<PathMapArc>(arcs.size());
                  for (final PathMapArc arc: arcs) {
                      cloned.arcs.add(arc.clone());
                  }
              }
  
              return cloned;
          }
  
          /**
           * Create a node in the PathMap (initially with no arcs)
           */
  
          private PathMapNode() {
              arcs = new ArrayList<PathMapArc>();
          }
  
          /**
           * Create a new arc
           * @param step the AxisExpression representing this step
           * @return the newly-constructed target of the new arc
           */
  
          public PathMapNode createArc(AxisExpression step) {
              for (int i=0; i<arcs.size(); i++) {
                  PathMapArc a = (PathMapArc)arcs.get(i);
                  if (a.getStep().equals(step)) {
                      return a.getTarget();
                  }
              }
              PathMapNode target = new PathMapNode();
              PathMapArc arc = new PathMapArc(step, target);
              arcs.add(arc);
              return target;
          }
  
          /**
           * Create a new arc to an existing target
           * @param step the AxisExpression representing this step
           * @param target the target node of the new arc
           */
  
          public void createArc(AxisExpression step, PathMapNode target) {
              for (int i=0; i<arcs.size(); i++) {
                  PathMapArc a = (PathMapArc)arcs.get(i);
                  if (a.getStep().equals(step) && a.getTarget() == target) {
                      // TODO: if it's a different target, then merge the two targets into one. XMark Q8
                      a.getTarget().setReturnable(a.getTarget().isReturnable() || target.isReturnable());
                      if (target.isAtomized()) {
                          a.getTarget().setAtomized();
                      }
                      return;
                  }
              }
              PathMapArc arc = new PathMapArc(step, target);
              arcs.add(arc);
          }
  
          /**
           * Get the arcs emanating from this node in the PathMap
           * @return the arcs, each representing an AxisStep. The order of arcs in the array is undefined.
           */
  
          public PathMapArc[] getArcs() {
              return (PathMapArc[])arcs.toArray(new PathMapArc[arcs.size()]);
          }
  
          // ORBEON
          public void addArcs(List<PathMapArc> arcs) {
              this.arcs.addAll(arcs);
          }
  
          // ORBEON
          public void addArcs(PathMapArc[] arcs) {
              this.arcs.addAll(Arrays.asList(arcs));
          }
  
          // ORBEON
          public void removeArc(PathMapArc arc) {
              this.arcs.remove(arc);
          }
  
          /**
           * Indicate that the node represents a value that is returnable as the result of the
           * supplied expression, rather than merely a node that is visited en route
           * @param returnable true if the node represents a final result of the expression
           */
  
          public void setReturnable(boolean returnable) {
              this.returnable = returnable;
          }
  
          /**
           * Ask whether the node represents a value that is returnable as the result of the
           * supplied expression, rather than merely a node that is visited en route
           * @return true if the node represents a final result of the expression
           */
  
          public boolean isReturnable() {
              return returnable;
          }
  
          /**
           * Indicate that the typed value or string value of the node reached by this path
           * will be used.
           */
  
          public void setAtomized() {
              this.atomized = true;
          }
  
          /**
           * Ask whether the typed value (or string value) of the node reached by this path
           * will be required.
           * @return true if the typed value or string value of the node is required
           */
  
          public boolean isAtomized() {
              return atomized;
          }
  
          /**
           * Indicate that the path has unknown dependencies, typically because a node reached
           * by the path is supplied as an argument to a user-defined function
           */
  
          public void setHasUnknownDependencies() {
              hasUnknownDependencies = true;
          }
  
          /**
           * Ask whether the path has unknown dependencies, typically because a node reached
           * by the path is supplied as an argument to a user-defined function
           * @return true if the path has unknown dependencies
           */
  
          public boolean hasUnknownDependencies() {
              return hasUnknownDependencies;
          }
      }
  
      /**
       * A root node in the path map. A root node represents either (a) a subexpression that is the first step in
       * a path expression, or (b) a subexpression that is not the first step in a path, but which returns nodes
       * (for example, a call on the doc() function).
       */
  
      public static class PathMapRoot extends PathMapNode {
  
          private Expression rootExpression;
          private boolean isDownwardsOnly;
  
          /**
           * Create a PathMapRoot
           * @param root the expression at the root of a path
           */
          private PathMapRoot(Expression root) {
              this.rootExpression = root;
          }
  
          /**
           * Get the root expression
           * @return the expression at the root of the path
           */
          public Expression getRootExpression() {
              return rootExpression;
          }
  
          // ORBEON
          @Override
          public PathMapRoot clone() throws CloneNotSupportedException {
              return (PathMapRoot) super.clone();
          }
      }
  
      /**
       * An arc joining two nodes in the path map. The arc has a target (destination) node, and is
       * labelled with an AxisExpression representing a step in a path expression
       */
  
      public static class PathMapArc implements Cloneable {
          private PathMapNode target;
          private AxisExpression step;
  
          /**
           * Create a PathMapArc
           * @param step the axis step, represented by an AxisExpression
           * @param target the node reached by following this arc
           */
          private PathMapArc(AxisExpression step, PathMapNode target) {
              this.step = step;
              this.target = target;
          }
  
          /**
           * Get the AxisExpression associated with this arc
           * @return the AxisExpression
           */
  
          public AxisExpression getStep() {
              return step;
          }
  
          /**
           * Get the target node representing the destination of this arc
           * @return the target node
           */
  
          public PathMapNode getTarget() {
              return target;
          }
  
          // ORBEON
          @Override
          public PathMapArc clone() throws CloneNotSupportedException {
              final PathMapArc cloned = (PathMapArc) super.clone();
              if (target != null) {
                  cloned.target = target.clone();
              }
  
              return cloned;
          }
      }
  
      /**
       * A (mutable) set of nodes in the path map
       */
  
      public static class PathMapNodeSet extends HashSet<PathMapNode> {
  
          /**
           * Create an initially-empty set of path map nodes
           */
  
          public PathMapNodeSet() {}
  
          /**
           * Create a set of path map nodes that initially contains a single node
           * @param singleton the single node to act as the initial content
           */
  
          public PathMapNodeSet(PathMapNode singleton) {
              add(singleton);
          }
  
          /**
           * Create an arc from each node in this node set to a corresponding newly-created
           * target node
           * @param step the AxisExpression defining the transition
           * @return the set of new target nodes
           */
  
          public PathMapNodeSet createArc(AxisExpression step) {
              PathMapNodeSet targetSet = new PathMapNodeSet();
              for (Iterator it=iterator(); it.hasNext();) {
                  PathMapNode node = (PathMapNode)it.next();
                  targetSet.add(node.createArc(step));
              }
              return targetSet;
          }
  
          /**
           * Combine two node sets into one
           * @param nodes the set of nodes to be added to this set
           */
  
          public void addNodeSet(PathMapNodeSet nodes) {
              if (nodes != null) {
                  for (Iterator it=nodes.iterator(); it.hasNext();) {
                      PathMapNode node = (PathMapNode)it.next();
                      add(node);
                  }
              }
          }
  
          /**
           * Set the atomized property on all nodes in this nodeset
           */
  
          public void setAtomized() {
              for (Iterator it=iterator(); it.hasNext();) {
                  PathMapNode node = (PathMapNode)it.next();
                  node.setAtomized();
              }
          }
  
          /**
           * Indicate that all the descendants of the nodes in this nodeset are required
           */
  
          public void addDescendants() {
              for (Iterator it=iterator(); it.hasNext();) {
                  PathMapNode node = (PathMapNode)it.next();
                  AxisExpression down = new AxisExpression(Axis.DESCENDANT, AnyNodeTest.getInstance());
                  node.createArc(down);
              }
          }
  
          /**
           * Indicate that all the nodes have unknown dependencies
           */
  
          public void setHasUnknownDependencies() {
              for (Iterator it=iterator(); it.hasNext();) {
                  PathMapNode node = (PathMapNode)it.next();
                  node.setHasUnknownDependencies();
              }
          }
  
      }
  
      /**
       * Create the PathMap for an expression
       * @param exp the expression whose PathMap is required
       */
  
      public PathMap(Expression exp) {
          final PathMapNodeSet finalNodes = exp.addToPathMap(this, null);
          updateFinalNodes(finalNodes);
      }
  
      // ORBEON
      public PathMap(Expression exp, Map<String, PathMap> inScopeVariables, Object pathMapContext) {
  
          setInScopeVariables(inScopeVariables);
          setPathMapContext(pathMapContext);
  
          final PathMapNodeSet finalNodes = exp.addToPathMap(this, null);
          updateFinalNodes(finalNodes);
      }
  
      /**
       * Make a new root node in the path map. However, if there is already a root for the same
       * expression, the existing root for that expression is returned.
       * @param exp the expression represented by this root node
       * @return the new root node
       */
  
      public PathMapRoot makeNewRoot(Expression exp) {
          for (int i=0; i<pathMapRoots.size(); i++) {
              PathMapRoot r = (PathMapRoot)pathMapRoots.get(i);
              if (exp.equals(r.getRootExpression())) {
                  return r;
              }
          }
          PathMapRoot root = new PathMapRoot(exp);
          pathMapRoots.add(root);
          return root;
      }
  
      /**
       * Get all the root expressions from the path map
       * @return an array containing the root expressions
       */
  
      public PathMapRoot[] getPathMapRoots() {
          return (PathMapRoot[])pathMapRoots.toArray(new PathMapRoot[pathMapRoots.size()]);
      }
  
      /**
       * Register the path used when evaluating a given variable binding
       * @param binding the variable binding
       * @param nodeset the set of PathMap nodes reachable when evaluating that variable
       */
  
      public void registerPathForVariable(Binding binding, PathMapNodeSet nodeset) {
          pathsForVariables.put(binding, nodeset);
      }
  
      /**
       * Get the path used when evaluating a given variable binding
       * @param binding the variable binding
       * @return the set of PathMap nodes reachable when evaluating that variable
       */
  
      public PathMapNodeSet getPathForVariable(Binding binding) {
          // Check local variables
          final PathMapNodeSet localResult = pathsForVariables.get(binding);
          if (localResult != null)
              return localResult;
  
          // ORBEON
          if (pathMapContext != null) {
              // Check external variables
              // Clone the PathMap first because the nodes returned must belong to this PathMap
              final PathMap variablePathMap = inScopeVariables.get(binding.getVariableQName().getDisplayName());
              if (variablePathMap != null) {
                  final PathMap clonedVariablePathMap = variablePathMap.clone();
                  addRoots(clonedVariablePathMap.getPathMapRoots());
                  return clonedVariablePathMap.findFinalNodes();
              } else {
                  // TODO: when can this happen? it does seem to happen, e.g. w/ names like zz:zz1303689357 for internal LetExpression
  
                  // Only invalidate if this is not a local variable, i.e. if this is a reference to an external variable. In
                  // this case, there is no local slot number.
                  if (binding.getLocalSlotNumber() == -1)
                      invalidated = true;
  
                  return null;
              }
          } else
              throw new IllegalStateException("No PathMapContext set to obtain variable binding: " + binding.getVariableQName().getDisplayName());
      }
  
      public boolean isInvalidated() {
          return invalidated;
      }
  
      public void setInvalidated(boolean invalidated) {
          this.invalidated = invalidated;
      }
  
      /**
       * Get the path map root for the context document
       * @return the path map root for the context document if there is one, or null if none is found.
       * @throws IllegalStateException if there is more than one path map root for the context document
       */
  
      public PathMapRoot getContextRoot() {
          //System.err.println("BEFORE REDUCTION:");
          //map.diagnosticDump(System.err);
          PathMap.PathMapRoot[] roots = getPathMapRoots();
          PathMapRoot contextRoot = null;
          for (int r=0; r<roots.length; r++) {
              PathMap.PathMapRoot newRoot = reduceToDownwardsAxes(roots[r]);
              if (newRoot.getRootExpression() instanceof RootExpression) {
                  if (contextRoot != null) {
                      throw new IllegalStateException("More than one context document root found in path map");
                  } else {
                      contextRoot = newRoot;
                  }
              }
          }
          //System.err.println("AFTER REDUCTION:");
          //map.diagnosticDump(System.err);
          return contextRoot;
      }
  
      /**
       * Get the path map root for a call on the doc() or document() function with a given literal argument
       * @param requiredUri the literal argument we are looking for
       * @return the path map root for the specified document if there is one, or null if none is found.
       * @throws IllegalStateException if there is more than one path map root for the specified document
       */
  
      public PathMapRoot getRootForDocument(String requiredUri) {
          //System.err.println("BEFORE REDUCTION:");
          //map.diagnosticDump(System.err);
          PathMap.PathMapRoot[] roots = getPathMapRoots();
          PathMapRoot requiredRoot = null;
          for (int r=0; r<roots.length; r++) {
              PathMap.PathMapRoot newRoot = reduceToDownwardsAxes(roots[r]);
              Expression exp = newRoot.getRootExpression();
              String baseUri = null;
              if (exp instanceof Doc) {
                  baseUri = ((Doc)exp).getStaticBaseURI();
              } else if (exp instanceof Document) {
                  baseUri = ((Document)exp).getStaticBaseURI();
              }
              // Latest Saxon 9.2 has this
  //            } else {
  //                continue;
  //            }
              Expression arg = ((SystemFunction)exp).getArguments()[0];
              String suppliedUri = null;
              if (arg instanceof Literal) {
                  try {
                      String argValue = ((Literal)arg).getValue().getStringValue();
                      if (baseUri == null) {
                          if (new URI(argValue).isAbsolute()) {
                              suppliedUri = argValue;
                          } else {
                              suppliedUri = null;
                          }
                      } else {
                          suppliedUri = Configuration.getPlatform().makeAbsolute(argValue, baseUri).toString();
                      }
                  } catch (URISyntaxException err) {
                      suppliedUri = null;
                  } catch (XPathException err) {
                      suppliedUri = null;
                  }
              }
              if (requiredUri.equals(suppliedUri)) {
                  if (requiredRoot != null) {
                      throw new IllegalStateException("More than one document root found in path map for " + requiredUri);
                  } else {
                      requiredRoot = newRoot;
                  }
              }
          }
          //System.err.println("AFTER REDUCTION:");
          //map.diagnosticDump(System.err);
          return requiredRoot;
      }
  
      /**
       * Given a PathMapRoot, simplify the tree rooted at this node so that
       * it only contains downwards selections: specifically, so that the only axes
       * used are child, attribute, namespace, and descendant. If the root expression
       * is a ContextItemExpression (that is, the path can start at any node) then it is rebased
       * to start at a root node, which means in effect that a path such as a/b/c is treated
       * as //a/b/c.
       * @param root the root of the path to be simplified
       * @return the path map root after converting the tree to use downwards axes only
       */
  
      public PathMapRoot reduceToDownwardsAxes(PathMapRoot root) {
          // If the path is rooted at an arbitrary context node, we rebase it to be rooted at the
          // document root. This involves changing the root to a RootExpression, and changing the axis
          // for initial steps from child to descendant where necessary
          if (root.isDownwardsOnly) {
              return root;
          }
          PathMapRoot newRoot = root;
          if (root.getRootExpression() instanceof ContextItemExpression) {
              RootExpression slash = new RootExpression();
              slash.setContainer(root.getRootExpression().getContainer());
              //root.setRootExpression(slash);
              newRoot = makeNewRoot(slash);
              for (int i=root.arcs.size()-1; i>=0; i--) {
                  PathMapArc arc = (PathMapArc)root.arcs.get(i);
                  byte axis = arc.getStep().getAxis();
                  switch (axis) {
                      case Axis.ATTRIBUTE:
                      case Axis.NAMESPACE: {
                          AxisExpression newStep = new AxisExpression(Axis.DESCENDANT, NodeKindTest.ELEMENT);
                          PathMapNode newTarget = new PathMapNode();
                          newTarget.arcs.add(arc);
                          newRoot.createArc(newStep, newTarget);
                          break;
                      }
                      default: {
                          AxisExpression newStep = new AxisExpression(
                                  Axis.DESCENDANT_OR_SELF, arc.getStep().getNodeTest());
                          newRoot.createArc(newStep, arc.getTarget());
                          break;
                      }
                  }
              }
              for (int i=0; i<pathMapRoots.size(); i++) {
                  if (pathMapRoots.get(i) == root) {
                      pathMapRoots.remove(i); break;
                  }
              }
          }
          // Now process the tree of paths recursively, rewriting all axes in terms of downwards
          // selections, if necessary as downward selections from the root
          Stack nodeStack = new Stack();
          nodeStack.push(newRoot);
          reduceToDownwardsAxes(newRoot, nodeStack);
          newRoot.isDownwardsOnly = true;
          return newRoot;
      }
  
      /**
       * Supporting method for {@link #reduceToDownwardsAxes(org.orbeon.saxon.expr.PathMap.PathMapRoot)}
       * @param root the root of the path being simplified
       * @param nodeStack the sequence of nodes by which the current node in the path map was reached.
       * The node at the bottom of the stack is the root.
       */
  
      private void reduceToDownwardsAxes(PathMapRoot root, Stack nodeStack) {
          //PathMapArc lastArc = (PathMapArc)arcStack.peek();
          //byte lastAxis = lastArc.getStep().getAxis();
          PathMapNode node = (PathMapNode)nodeStack.peek();
          if (node.hasUnknownDependencies()) {
              root.setHasUnknownDependencies();
          }
  
          for (int i=0; i<node.arcs.size(); i++) {
              nodeStack.push(((PathMapArc)node.arcs.get(i)).getTarget());
              reduceToDownwardsAxes(root, nodeStack);
              nodeStack.pop();
          }
  
          for (int i=node.arcs.size()-1; i>=0; i--) {
  