trunk/src/org/apache/ws/security/util/NSStack.java - ws-wss4j - Git at Google

 /*
  * Copyright  2003-2004 The Apache Software Foundation.
  *
  *  Licensed under the Apache License, Version 2.0 (the "License");
  *  you may not use this file except in compliance with the License.
  *  You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  *  Unless required by applicable law or agreed to in writing, software
  *  distributed under the License is distributed on an "AS IS" BASIS,
  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  *  See the License for the specific language governing permissions and
  *  limitations under the License.
  *
  */

 package org.apache.ws.security.util;

 import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;

 import java.util.ArrayList;

 /**
  * The abstraction this class provides is a push down stack of variable
  * length frames of prefix to namespace mappings.  Used for keeping track
  * of what namespaces are active at any given point as an XML document is
  * traversed or produced.
  * <p/>
  * From a performance point of view, this data will both be modified frequently
  * (at a minimum, there will be one push and pop per XML element processed),
  * and scanned frequently (many of the "good" mappings will be at the bottom
  * of the stack).  The one saving grace is that the expected maximum
  * cardinalities of the number of frames and the number of total mappings
  * is only in the dozens, representing the nesting depth of an XML document
  * and the number of active namespaces at any point in the processing.
  * <p/>
  * Accordingly, this stack is implemented as a single array, will null
  * values used to indicate frame boundaries.
  *
  * @author James Snell
  * @author Glen Daniels (gdaniels@apache.org)
  * @author Sam Ruby (rubys@us.ibm.com)
  */
 public class NSStack {
     protected static Log log =
             LogFactory.getLog(NSStack.class.getName());

     private Mapping[] stack;
     private int top = 0;
     private int iterator = 0;
     private int currentDefaultNS = -1;
     // invariant member variable to track low-level logging requirements
     // we cache this once per instance lifecycle to avoid repeated lookups
     // in heavily used code.
     private final boolean traceEnabled = log.isTraceEnabled();

     public NSStack() {
         stack = new Mapping[32];
         stack[0] = null;
     }

     /**
      * Create a new frame at the top of the stack.
      */
     public void push() {
         top++;
         if (top >= stack.length) {
             Mapping newstack[] = new Mapping[stack.length * 2];
             System.arraycopy(stack, 0, newstack, 0, stack.length);
             stack = newstack;
         }
         if (traceEnabled)
             log.trace("NSPush (" + stack.length + ")");
         stack[top] = null;
     }

     /**
      * Remove the top frame from the stack.
      */
     public void pop() {
         clearFrame();
         top--;

         // If we've moved below the current default NS, figure out the new
         // default (if any)
         if (top < currentDefaultNS) {
             // Reset the currentDefaultNS to ignore the frame just removed.
             currentDefaultNS = top;
             while (currentDefaultNS > 0) {
                 if (stack[currentDefaultNS] != null &&
                         stack[currentDefaultNS].getPrefix().length() == 0)
                     break;
                 currentDefaultNS--;
             }
         }
         if (top == 0) {
             if (traceEnabled)
                 log.trace("NSPop (empty)");
             return;
         }
         if (traceEnabled) {
             log.trace("NSPop (" + stack.length + ")");
         }
     }

     /**
      * Return a copy of the current frame.  Returns null if none are present.
      */
     public ArrayList cloneFrame() {
         if (stack[top] == null) return null;
         ArrayList clone = new ArrayList();
         for (Mapping map = topOfFrame(); map != null; map = next()) {
             clone.add(map);
         }
         return clone;
     }

     /**
      * Remove all mappings from the current frame.
      */
     private void clearFrame() {
         while (stack[top] != null) top--;
     }

     /**
      * Reset the embedded iterator in this class to the top of the current
      * (i.e., last) frame.  Note that this is not threadsafe, nor does it
      * provide multiple iterators, so don't use this recursively.  Nor
      * should you modify the stack while iterating over it.
      */
     public Mapping topOfFrame() {
         iterator = top;
         while (stack[iterator] != null) iterator--;
         iterator++;
         return next();
     }

     /**
      * Return the next namespace mapping in the top frame.
      */
     public Mapping next() {
         if (iterator > top) {
             return null;
         } else {
             return stack[iterator++];
         }
     }

     /**
      * Add a mapping for a namespaceURI to the specified prefix to the top
      * frame in the stack.  If the prefix is already mapped in that frame,
      * remap it to the (possibly different) namespaceURI.
      */
     public void add(String namespaceURI, String prefix) {
         int idx = top;
         try {
             // Replace duplicate prefixes (last wins - this could also fault)
             for (int cursor = top; stack[cursor] != null; cursor--) {
                 if (stack[cursor].getPrefix().equals(prefix)) {
                     stack[cursor].setNamespaceURI(namespaceURI);
                     idx = cursor;
                     return;
                 }
             }
             push();
             stack[top] = new Mapping(namespaceURI, prefix);
             idx = top;
         } finally {
             // If this is the default namespace, note the new in-scope
             // default is here.
             if (prefix.length() == 0) {
                 currentDefaultNS = idx;
             }
         }
     }

     /**
      * Return an active prefix for the given namespaceURI.  NOTE : This
      * may return null even if the namespaceURI was actually mapped further
      * up the stack IF the prefix which was used has been repeated further
      * down the stack.  I.e.:
      * <p/>
      * <pre:outer xmlns:pre="namespace">
      * <pre:inner xmlns:pre="otherNamespace">
      * *here's where we're looking*
      * </pre:inner>
      * </pre:outer>
      * <p/>
      * If we look for a prefix for "namespace" at the indicated spot, we won't
      * find one because "pre" is actually mapped to "otherNamespace"
      */
     public String getPrefix(String namespaceURI, boolean noDefault) {
         if ((namespaceURI == null) || (namespaceURI.equals("")))
             return null;
         int hash = namespaceURI.hashCode();

         // If defaults are OK, and the given NS is the current default,
         // return "" as the prefix to favor defaults where possible.
         if (!noDefault && currentDefaultNS > 0 && stack[currentDefaultNS] != null &&
                 namespaceURI.equals(stack[currentDefaultNS].getNamespaceURI()))
             return "";
         for (int cursor = top; cursor > 0; cursor--) {
             Mapping map = stack[cursor];
             if (map == null) continue;
             if (map.getNamespaceHash() == hash &&
                     map.getNamespaceURI().equals(namespaceURI)) {
                 String possiblePrefix = map.getPrefix();
                 if (noDefault && possiblePrefix.length() == 0) continue;

                 // now make sure that this is the first occurance of this
                 // particular prefix
                 int ppHash = possiblePrefix.hashCode();
                 for (int cursor2 = top; true; cursor2--) {
                     if (cursor2 == cursor) return possiblePrefix;
                     map = stack[cursor2];
                     if (map == null) continue;
                     if (ppHash == map.getPrefixHash() &&
                             possiblePrefix.equals(map.getPrefix()))
                         break;
                 }
             }
         }
         return null;
     }

     /**
      * Return an active prefix for the given namespaceURI, including
      * the default prefix ("").
      */
     public String getPrefix(String namespaceURI) {
         return getPrefix(namespaceURI, false);
     }

     /**
      * Given a prefix, return the associated namespace (if any).
      */
     public String getNamespaceURI(String prefix) {
         if (prefix == null)
             prefix = "";
         int hash = prefix.hashCode();
         for (int cursor = top; cursor > 0; cursor--) {
             Mapping map = stack[cursor];
             if (map == null) continue;
             if (map.getPrefixHash() == hash && map.getPrefix().equals(prefix))
                 return map.getNamespaceURI();
         }
         return null;
     }

     /**
      * Produce a trace dump of the entire stack, starting from the top and
      * including frame markers.
      */
     public void dump(String dumpPrefix) {
         for (int cursor = top; cursor > 0; cursor--) {
             Mapping map = stack[cursor];
             if (map == null) {
                 log.trace(dumpPrefix + "stackFrame00");
             } else {
                 log.trace(dumpPrefix + map.getNamespaceURI() + " -> " + map.getPrefix());
             }
         }
     }
 }
	/*
	* Copyright 2003-2004 The Apache Software Foundation.
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*
	*/

	package org.apache.ws.security.util;

	import org.apache.commons.logging.Log;
	import org.apache.commons.logging.LogFactory;

	import java.util.ArrayList;

	/**
	* The abstraction this class provides is a push down stack of variable
	* length frames of prefix to namespace mappings. Used for keeping track
	* of what namespaces are active at any given point as an XML document is
	* traversed or produced.
	* <p/>
	* From a performance point of view, this data will both be modified frequently
	* (at a minimum, there will be one push and pop per XML element processed),
	* and scanned frequently (many of the "good" mappings will be at the bottom
	* of the stack). The one saving grace is that the expected maximum
	* cardinalities of the number of frames and the number of total mappings
	* is only in the dozens, representing the nesting depth of an XML document
	* and the number of active namespaces at any point in the processing.
	* <p/>
	* Accordingly, this stack is implemented as a single array, will null
	* values used to indicate frame boundaries.
	*
	* @author James Snell
	* @author Glen Daniels (gdaniels@apache.org)
	* @author Sam Ruby (rubys@us.ibm.com)
	*/
	public class NSStack {
	protected static Log log =
	LogFactory.getLog(NSStack.class.getName());

	private Mapping[] stack;
	private int top = 0;
	private int iterator = 0;
	private int currentDefaultNS = -1;
	// invariant member variable to track low-level logging requirements
	// we cache this once per instance lifecycle to avoid repeated lookups
	// in heavily used code.
	private final boolean traceEnabled = log.isTraceEnabled();

	public NSStack() {
	stack = new Mapping[32];
	stack[0] = null;
	}

	/**
	* Create a new frame at the top of the stack.
	*/
	public void push() {
	top++;
	if (top >= stack.length) {
	Mapping newstack[] = new Mapping[stack.length * 2];
	System.arraycopy(stack, 0, newstack, 0, stack.length);
	stack = newstack;
	}
	if (traceEnabled)
	log.trace("NSPush (" + stack.length + ")");
	stack[top] = null;
	}

	/**
	* Remove the top frame from the stack.
	*/
	public void pop() {
	clearFrame();
	top--;

	// If we've moved below the current default NS, figure out the new
	// default (if any)
	if (top < currentDefaultNS) {
	// Reset the currentDefaultNS to ignore the frame just removed.
	currentDefaultNS = top;
	while (currentDefaultNS > 0) {
	if (stack[currentDefaultNS] != null &&
	stack[currentDefaultNS].getPrefix().length() == 0)
	break;
	currentDefaultNS--;
	}
	}
	if (top == 0) {
	if (traceEnabled)
	log.trace("NSPop (empty)");
	return;
	}
	if (traceEnabled) {
	log.trace("NSPop (" + stack.length + ")");
	}
	}

	/**
	* Return a copy of the current frame. Returns null if none are present.
	*/
	public ArrayList cloneFrame() {
	if (stack[top] == null) return null;
	ArrayList clone = new ArrayList();
	for (Mapping map = topOfFrame(); map != null; map = next()) {
	clone.add(map);
	}
	return clone;
	}

	/**
	* Remove all mappings from the current frame.
	*/
	private void clearFrame() {
	while (stack[top] != null) top--;
	}

	/**
	* Reset the embedded iterator in this class to the top of the current
	* (i.e., last) frame. Note that this is not threadsafe, nor does it
	* provide multiple iterators, so don't use this recursively. Nor
	* should you modify the stack while iterating over it.
	*/
	public Mapping topOfFrame() {
	iterator = top;
	while (stack[iterator] != null) iterator--;
	iterator++;
	return next();
	}

	/**
	* Return the next namespace mapping in the top frame.
	*/
	public Mapping next() {
	if (iterator > top) {
	return null;
	} else {
	return stack[iterator++];
	}
	}

	/**
	* Add a mapping for a namespaceURI to the specified prefix to the top
	* frame in the stack. If the prefix is already mapped in that frame,
	* remap it to the (possibly different) namespaceURI.
	*/
	public void add(String namespaceURI, String prefix) {
	int idx = top;
	try {
	// Replace duplicate prefixes (last wins - this could also fault)
	for (int cursor = top; stack[cursor] != null; cursor--) {
	if (stack[cursor].getPrefix().equals(prefix)) {
	stack[cursor].setNamespaceURI(namespaceURI);
	idx = cursor;
	return;
	}
	}
	push();
	stack[top] = new Mapping(namespaceURI, prefix);
	idx = top;
	} finally {
	// If this is the default namespace, note the new in-scope
	// default is here.
	if (prefix.length() == 0) {
	currentDefaultNS = idx;
	}
	}
	}

	/**
	* Return an active prefix for the given namespaceURI. NOTE : This
	* may return null even if the namespaceURI was actually mapped further
	* up the stack IF the prefix which was used has been repeated further
	* down the stack. I.e.:
	* <p/>
	* <pre:outer xmlns:pre="namespace">
	* <pre:inner xmlns:pre="otherNamespace">
	* here's where we're looking
	* </pre:inner>
	* </pre:outer>
	* <p/>
	* If we look for a prefix for "namespace" at the indicated spot, we won't
	* find one because "pre" is actually mapped to "otherNamespace"
	*/
	public String getPrefix(String namespaceURI, boolean noDefault) {
	if ((namespaceURI == null) \|\| (namespaceURI.equals("")))
	return null;
	int hash = namespaceURI.hashCode();

	// If defaults are OK, and the given NS is the current default,
	// return "" as the prefix to favor defaults where possible.
	if (!noDefault && currentDefaultNS > 0 && stack[currentDefaultNS] != null &&
	namespaceURI.equals(stack[currentDefaultNS].getNamespaceURI()))
	return "";
	for (int cursor = top; cursor > 0; cursor--) {
	Mapping map = stack[cursor];
	if (map == null) continue;
	if (map.getNamespaceHash() == hash &&
	map.getNamespaceURI().equals(namespaceURI)) {
	String possiblePrefix = map.getPrefix();
	if (noDefault && possiblePrefix.length() == 0) continue;

	// now make sure that this is the first occurance of this
	// particular prefix
	int ppHash = possiblePrefix.hashCode();
	for (int cursor2 = top; true; cursor2--) {
	if (cursor2 == cursor) return possiblePrefix;
	map = stack[cursor2];
	if (map == null) continue;
	if (ppHash == map.getPrefixHash() &&
	possiblePrefix.equals(map.getPrefix()))
	break;
	}
	}
	}
	return null;
	}

	/**
	* Return an active prefix for the given namespaceURI, including
	* the default prefix ("").
	*/
	public String getPrefix(String namespaceURI) {
	return getPrefix(namespaceURI, false);
	}

	/**
	* Given a prefix, return the associated namespace (if any).
	*/
	public String getNamespaceURI(String prefix) {
	if (prefix == null)
	prefix = "";
	int hash = prefix.hashCode();
	for (int cursor = top; cursor > 0; cursor--) {
	Mapping map = stack[cursor];
	if (map == null) continue;
	if (map.getPrefixHash() == hash && map.getPrefix().equals(prefix))
	return map.getNamespaceURI();
	}
	return null;
	}

	/**
	* Produce a trace dump of the entire stack, starting from the top and
	* including frame markers.
	*/
	public void dump(String dumpPrefix) {
	for (int cursor = top; cursor > 0; cursor--) {
	Mapping map = stack[cursor];
	if (map == null) {
	log.trace(dumpPrefix + "stackFrame00");
	} else {
	log.trace(dumpPrefix + map.getNamespaceURI() + " -> " + map.getPrefix());
	}
	}
	}
	}