Back to index...

	/*
	* Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
	*/
	/*
	* Licensed to the Apache Software Foundation (ASF) under one or more
	* contributor license agreements. See the NOTICE file distributed with
	* this work for additional information regarding copyright ownership.
	* The ASF licenses this file to You 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 com.sun.org.apache.xml.internal.utils;

	import com.sun.org.apache.xml.internal.dtm.ref.DTMNodeProxy;
	import org.w3c.dom.Attr;
	import org.w3c.dom.NamedNodeMap;
	import org.w3c.dom.Node;


	/**
	* This class provides a DOM level 2 "helper", which provides several services.
	*
	* The original class extended DOMHelper that was deprecated and then removed.
	*/
	public final class DOM2Helper {

	/**
	* Construct an instance.
	*/
	private DOM2Helper() {
	}

	/**
	* Returns the local name of the given node, as defined by the XML
	* Namespaces specification. This is prepared to handle documents built
	* using DOM Level 1 methods by falling back upon explicitly parsing the
	* node name.
	*
	* @param n Node to be examined
	*
	* @return String containing the local name, or null if the node was not
	* assigned a Namespace.
	*/
	public static String getLocalNameOfNode(Node n) {

	String name = n.getLocalName();

	return (null == name) ? getLocalNameOfNodeFallback(n) : name;
	}

	/**
	* Returns the local name of the given node. If the node's name begins with
	* a namespace prefix, this is the part after the colon; otherwise it's the
	* full node name.
	*
	* This method is copied from
	* com.sun.org.apache.xml.internal.utils.DOMHelper
	*
	* @param n the node to be examined.
	*
	* @return String containing the Local Name
	*/
	private static String getLocalNameOfNodeFallback(Node n) {

	String qname = n.getNodeName();
	int index = qname.indexOf(':');

	return (index < 0) ? qname : qname.substring(index + 1);
	}

	/**
	* Returns the Namespace Name (Namespace URI) for the given node. In a Level
	* 2 DOM, you can ask the node itself. Note, however, that doing so
	* conflicts with our decision in getLocalNameOfNode not to trust the that
	* the DOM was indeed created using the Level 2 methods. If Level 1 methods
	* were used, these two functions will disagree with each other.
	* <p>
	* TODO: Reconcile with getLocalNameOfNode.
	*
	* @param n Node to be examined
	*
	* @return String containing the Namespace URI bound to this DOM node at the
	* time the Node was created.
	*/
	public static String getNamespaceOfNode(Node n) {
	return n.getNamespaceURI();
	}

	/**
	* Figure out whether node2 should be considered as being later in the
	* document than node1, in Document Order as defined by the XPath model.
	* This may not agree with the ordering defined by other XML applications.
	* <p>
	* There are some cases where ordering isn't defined, and neither are the
	* results of this function -- though we'll generally return true.
	*
	* @param node1 DOM Node to perform position comparison on.
	* @param node2 DOM Node to perform position comparison on .
	*
	* @return false if node2 comes before node1, otherwise return true. You can
	* think of this as
	* {@code (node1.documentOrderPosition <= node2.documentOrderPosition)}.
	*/
	public static boolean isNodeAfter(Node node1, Node node2) {
	if (node1 == node2 \|\| isNodeTheSame(node1, node2)) {
	return true;
	}

	// Default return value, if there is no defined ordering
	boolean isNodeAfter = true;

	Node parent1 = getParentOfNode(node1);
	Node parent2 = getParentOfNode(node2);

	// Optimize for most common case
	if (parent1 == parent2 \|\| isNodeTheSame(parent1, parent2)) // then we know they are siblings
	{
	if (null != parent1) {
	isNodeAfter = isNodeAfterSibling(parent1, node1, node2);
	}
	} else {
	// General strategy: Figure out the lengths of the two
	// ancestor chains, reconcile the lengths, and look for
	// the lowest common ancestor. If that ancestor is one of
	// the nodes being compared, it comes before the other.
	// Otherwise perform a sibling compare.
	//
	// NOTE: If no common ancestor is found, ordering is undefined
	// and we return the default value of isNodeAfter.
	// Count parents in each ancestor chain
	int nParents1 = 2, nParents2 = 2; // include node & parent obtained above

	while (parent1 != null) {
	nParents1++;

	parent1 = getParentOfNode(parent1);
	}

	while (parent2 != null) {
	nParents2++;

	parent2 = getParentOfNode(parent2);
	}

	// Initially assume scan for common ancestor starts with
	// the input nodes.
	Node startNode1 = node1, startNode2 = node2;

	// If one ancestor chain is longer, adjust its start point
	// so we're comparing at the same depths
	if (nParents1 < nParents2) {
	// Adjust startNode2 to depth of startNode1
	int adjust = nParents2 - nParents1;

	for (int i = 0; i < adjust; i++) {
	startNode2 = getParentOfNode(startNode2);
	}
	} else if (nParents1 > nParents2) {
	// adjust startNode1 to depth of startNode2
	int adjust = nParents1 - nParents2;

	for (int i = 0; i < adjust; i++) {
	startNode1 = getParentOfNode(startNode1);
	}
	}

	Node prevChild1 = null, prevChild2 = null; // so we can "back up"

	// Loop up the ancestor chain looking for common parent
	while (null != startNode1) {
	if (startNode1 == startNode2 \|\| isNodeTheSame(startNode1, startNode2)) // common parent?
	{
	if (null == prevChild1) // first time in loop?
	{

	// Edge condition: one is the ancestor of the other.
	isNodeAfter = (nParents1 < nParents2) ? true : false;

	break; // from while loop
	} else {
	// Compare ancestors below lowest-common as siblings
	isNodeAfter = isNodeAfterSibling(startNode1, prevChild1,
	prevChild2);

	break; // from while loop
	}
	} // end if(startNode1 == startNode2)

	// Move up one level and try again
	prevChild1 = startNode1;
	startNode1 = getParentOfNode(startNode1);
	prevChild2 = startNode2;
	startNode2 = getParentOfNode(startNode2);
	} // end while(parents exist to examine)
	} // end big else (not immediate siblings)

	return isNodeAfter;
	} // end isNodeAfter(Node node1, Node node2)

	/**
	* Use DTMNodeProxy to determine whether two nodes are the same.
	*
	* @param node1 The first DOM node to compare.
	* @param node2 The second DOM node to compare.
	* @return true if the two nodes are the same.
	*/
	public static boolean isNodeTheSame(Node node1, Node node2) {
	if (node1 instanceof DTMNodeProxy && node2 instanceof DTMNodeProxy) {
	return ((DTMNodeProxy) node1).equals((DTMNodeProxy) node2);
	} else {
	return (node1 == node2);
	}
	}

	/**
	* Get the XPath-model parent of a node. This version takes advantage of the
	* DOM Level 2 Attr.ownerElement() method; the base version we would
	* otherwise inherit is prepared to fall back on exhaustively walking the
	* document to find an Attr's parent.
	*
	* @param node Node to be examined
	*
	* @return the DOM parent of the input node, if there is one, or the
	* ownerElement if the input node is an Attr, or null if the node is a
	* Document, a DocumentFragment, or an orphan.
	*/
	public static Node getParentOfNode(Node node) {
	Node parent = node.getParentNode();
	if (parent == null && (Node.ATTRIBUTE_NODE == node.getNodeType())) {
	parent = ((Attr) node).getOwnerElement();
	}
	return parent;
	}

	/**
	* Figure out if child2 is after child1 in document order.
	* <p>
	* Warning: Some aspects of "document order" are not well defined. For
	* example, the order of attributes is considered meaningless in XML, and
	* the order reported by our model will be consistent for a given invocation
	* but may not match that of either the source file or the serialized
	* output.
	*
	* @param parent Must be the parent of both child1 and child2.
	* @param child1 Must be the child of parent and not equal to child2.
	* @param child2 Must be the child of parent and not equal to child1.
	* @return true if child 2 is after child1 in document order.
	*/
	private static boolean isNodeAfterSibling(Node parent, Node child1,
	Node child2) {

	boolean isNodeAfterSibling = false;
	short child1type = child1.getNodeType();
	short child2type = child2.getNodeType();

	if ((Node.ATTRIBUTE_NODE != child1type)
	&& (Node.ATTRIBUTE_NODE == child2type)) {

	// always sort attributes before non-attributes.
	isNodeAfterSibling = false;
	} else if ((Node.ATTRIBUTE_NODE == child1type)
	&& (Node.ATTRIBUTE_NODE != child2type)) {

	// always sort attributes before non-attributes.
	isNodeAfterSibling = true;
	} else if (Node.ATTRIBUTE_NODE == child1type) {
	NamedNodeMap children = parent.getAttributes();
	int nNodes = children.getLength();
	boolean found1 = false, found2 = false;

	// Count from the start until we find one or the other.
	for (int i = 0; i < nNodes; i++) {
	Node child = children.item(i);

	if (child1 == child \|\| isNodeTheSame(child1, child)) {
	if (found2) {
	isNodeAfterSibling = false;

	break;
	}

	found1 = true;
	} else if (child2 == child \|\| isNodeTheSame(child2, child)) {
	if (found1) {
	isNodeAfterSibling = true;

	break;
	}

	found2 = true;
	}
	}
	} else {
	// TODO: Check performance of alternate solution:
	// There are two choices here: Count from the start of
	// the document until we find one or the other, or count
	// from one until we find or fail to find the other.
	// Either can wind up scanning all the siblings in the worst
	// case, which on a wide document can be a lot of work but
	// is more typically is a short list.
	// Scanning from the start involves two tests per iteration,
	// but it isn't clear that scanning from the middle doesn't
	// yield more iterations on average.
	// We should run some testcases.
	Node child = parent.getFirstChild();
	boolean found1 = false, found2 = false;

	while (null != child) {

	// Node child = children.item(i);
	if (child1 == child \|\| isNodeTheSame(child1, child)) {
	if (found2) {
	isNodeAfterSibling = false;

	break;
	}

	found1 = true;
	} else if (child2 == child \|\| isNodeTheSame(child2, child)) {
	if (found1) {
	isNodeAfterSibling = true;

	break;
	}

	found2 = true;
	}

	child = child.getNextSibling();
	}
	}

	return isNodeAfterSibling;
	} // end isNodeAfterSibling(Node parent, Node child1, Node child2)
	}

Back to index...