<commit_before>/*
 * eXist Open Source Native XML Database
 * Copyright (C) 2001-2007 The eXist Project
 * http://exist-db.org
 *
 * 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
 * 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.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software Foundation
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *  
 *  $Id$
 */
package org.exist.dom;

import java.util.Iterator;

import org.exist.numbering.NodeId;
import org.exist.xquery.Constants;
import org.exist.xquery.Expression;
import org.exist.xquery.NodeTest;
import org.exist.xquery.XPathException;
import org.exist.xquery.value.Item;
import org.exist.xquery.value.SequenceIterator;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;

/**
 * This node set is called virtual because it is just a placeholder for
 * the set of relevant nodes. For XPath expressions like //* or //node(), 
 * it would be totally unefficient to actually retrieve all descendant nodes.
 * In many cases, the expression can be resolved at a later point in time
 * without retrieving the whole node set. 
 *
 * VirtualNodeSet basically provides method getFirstParent to retrieve the first
 * matching descendant of its context according to the primary type axis.
 *
 * Class LocationStep will always return an instance of VirtualNodeSet
 * if it finds something like descendant::* etc..
 *
 * @author <NAME>
 * @author <NAME>
 */
public class VirtualNodeSet extends AbstractNodeSet {

    protected int axis = Constants.UNKNOWN_AXIS;
    protected NodeTest test;
    protected NodeSet context;
    protected NodeSet realSet = null;
    protected boolean realSetIsComplete = false;
    protected boolean inPredicate = false;
    protected boolean useSelfAsContext = false;
    protected int contextId = Expression.NO_CONTEXT_ID;
    private static final int MAX_CHILD_COUNT_FOR_OPTIMIZE = 5;
    private DocumentSet realDocumentSet = null; 
    
    private boolean knownIsEmptyCardinality = false;
    private boolean knownHasOneCardinality = false;
    private boolean knownHasManyCardinality = false;
    private boolean isEmpty = true;
    private boolean hasOne = false;    
    private boolean hasMany = false;    

    /**
     * Creates a new <code>VirtualNodeSet</code> instance.
     *
     * @param axis an <code>int</code> value
     * @param test a <code>NodeTest</code> value
     * @param contextId an <code>int</code> value
     * @param context a <code>NodeSet</code> value
     */
    public VirtualNodeSet(int axis, NodeTest test, int contextId, NodeSet context) {
        this.axis = axis;
        this.test = test;
        this.context = context;
        this.contextId = contextId;
    }

    /**
     * The method <code>contains</code>
     *
     * @param p a <code>NodeProxy</code> value
     * @return a <code>boolean</code> value
     */
    public boolean contains(NodeProxy p) {
        NodeProxy first = getFirstParent(p, null, (axis == Constants.SELF_AXIS), 0);
        // Timo Boehme: getFirstParent returns now only real parents
        //              therefore test if node is child of context
        if (first != null) {
            return true;
        }
        //	if (context.get(p.getDocument(), p.getNodeId().getParentId()) != null) {
        //            return true;
        //	}
        return false; 
    }

    /**
     * The method <code>setInPredicate</code>
     *
     * @param predicate a <code>boolean</code> value
     */
    public void setInPredicate(boolean predicate) {
        inPredicate = predicate;
    }

    /* (non-Javadoc)
     * @see org.exist.dom.AbstractNodeSet#getDocumentSet()
     */
    public DocumentSet getDocumentSet() {
    	//If we know what are our documents, return them...
    	if (realDocumentSet != null)
    		return realDocumentSet;
    	//... otherwise, we default to every *ptotentially* concerned document
        return context.getDocumentSet();
    }

    /**
     * The method <code>getCollectionIterator</code>
     *
     * @return an <code>Iterator</code> value
     */
    public Iterator getCollectionIterator() {
        return context.getCollectionIterator();
    }

    /**
     * The method <code>getFirstParent</code>
     *
     * @param node a <code>NodeProxy</code> value
     * @param first a <code>NodeProxy</code> value
     * @param includeSelf a <code>boolean</code> value
     * @param recursions an <code>int</code> value
     * @return a <code>NodeProxy</code> value
     */
    private NodeProxy getFirstParent(NodeProxy node, NodeProxy first,
                                     boolean includeSelf, int recursions) {
        return getFirstParent(node, first, includeSelf, true, recursions);
    }

    /**
     * The method <code>getFirstParent</code>
     *
     * @param node a <code>NodeProxy</code> value
     * @param first a <code>NodeProxy</code> value
     * @param includeSelf a <code>boolean</code> value
     * @param directParent a <code>boolean</code> value
     * @param recursions an <code>int</code> value
     * @return a <code>NodeProxy</code> value
     */
    private NodeProxy getFirstParent(NodeProxy node, NodeProxy first,
                                     boolean includeSelf, boolean directParent, int recursions) {
        
        NodeId pid = node.getNodeId().getParentId();
        
        /* if the node has no parent, i.e. pid == -1, we still need to 
         * complete this method to check if we have found a potential parent
         * in one of the iterations before.
         */
        NodeProxy parent;
        // check if the start-node should be included, e.g. to process an
        // expression like *[. = 'xxx']
        if (recursions == 0 && includeSelf && test.matches(node)) {
            if (axis == Constants.CHILD_AXIS) {
                // if we're on the child axis, test if
                // the node is a direct child of the context node
                parent = context.get(node.getDocument(), pid);
                if (parent != null) {
                    node.copyContext(parent);
                    if (useSelfAsContext && inPredicate) {
                        node.addContextNode(contextId, node);
                    } else if (inPredicate)
                        node.addContextNode(contextId, parent);
                    return node;
                }
            } else {
                // descendant axis: remember the node and continue 
                first = node;
            }
        }
        
        // if this is the first call to this method, remember the first 
        // parent node and re-evaluate the method. We can't just return 
        // the first parent as we need a parent that is actually contained 
        // in the context set. We thus call the method again to complete.
        if (first == null) {
            if (pid == NodeId.DOCUMENT_NODE) {
                // given node was already document element -> no parent
                return null;
            }
            first = new NodeProxy(node.getDocument(), pid, Node.ELEMENT_NODE, 
                                  StoredNode.UNKNOWN_NODE_IMPL_ADDRESS);
            // if we are on the self axis, check if the first parent can be selected
            if (axis == Constants.DESCENDANT_SELF_AXIS) {
                parent = context.get(first.getDocument(), pid);
                if (parent != null && test.matches(parent)) {
                    first.copyContext(parent);
                    if (useSelfAsContext && inPredicate) {
                        first.addContextNode(contextId, first);
                    } else if (inPredicate)
                        first.addContextNode(contextId, parent);
                    return first;
                }
            }
            // <NAME>: we need a real parent (child from context)
            return getFirstParent(first, first, false, directParent, recursions + 1);
        }
        
        // is pid member of the context set?
        parent = context.get(node.getDocument(), pid);

        if (parent != null && test.matches(node)) {
            if (axis != Constants.CHILD_AXIS) {
                // if we are on the descendant-axis, we return the first node 
                // we found while walking bottom-up.
                // Otherwise, we return the last one (which is node)
                node = first;
            }
            node.copyContext(parent);
            if (useSelfAsContext && inPredicate) {
                node.addContextNode(contextId, node);
            } else if (inPredicate) {
                node.addContextNode(contextId, parent);
            }
            // <NAME>: we return the ancestor which is child of context			
            return node;
        } else if (pid == NodeId.DOCUMENT_NODE) {
            // no matching node has been found in the context
            return null;
        } else if (directParent && axis == Constants.CHILD_AXIS && recursions == 1) {
            // break here if the expression is like /*/n          
            return null;        
        } else {
            // continue for expressions like //*/n or /*//n
            parent = new NodeProxy(node.getDocument(), pid, Node.ELEMENT_NODE, 
                                   StoredNode.UNKNOWN_NODE_IMPL_ADDRESS);
            return getFirstParent(parent, first, false, false, recursions + 1);
        }
    }

    private void addInternal(NodeProxy p) {
        if (realSet == null)
            realSet = new ExtArrayNodeSet(256);
        knownIsEmptyCardinality = true;
        if (isEmpty) {
            isEmpty = false;
            knownHasOneCardinality = true;
            hasOne= true;
        } else if (hasOne) {
            hasOne = false;
            knownHasManyCardinality = true;
            hasMany = true;	
        }
        realSet.add(p);
        //Reset the real document set
        //TODO : use realDocumentSet.add(p.getDocument()) ?
        realDocumentSet = null;
        realSetIsComplete = false;
    }

    /**
     * The method <code>parentWithChild</code>
     *
     * @param proxy a <code>NodeProxy</code> value
     * @param directParent a <code>boolean</code> value
     * @param includeSelf a <code>boolean</code> value
     * @param level an <code>int</code> value
     * @return a <code>NodeProxy</code> value
     */
    public NodeProxy parentWithChild(NodeProxy proxy, boolean directParent, boolean includeSelf,
                                     int level) {
        NodeProxy first = getFirstParent(proxy, null, includeSelf, directParent, 0);
        if (first != null)
            //TODO : should we set an empty cardinality here ?
            addInternal(first);
        return first;
    }

    /**
     * The method <code>parentWithChild</code>
     *
     * @param doc a <code>DocumentImpl</code> value
     * @param nodeId a <code>NodeId</code> value
     * @param directParent a <code>boolean</code> value
     * @param includeSelf a <code>boolean</code> value
     * @return a <code>NodeProxy</code> value
     */
    public NodeProxy parentWithChild(DocumentImpl doc, NodeId nodeId, boolean directParent, boolean includeSelf) {
    	NodeProxy first = getFirstParent(new NodeProxy(doc, nodeId), null, includeSelf, directParent, 0);
        if (first != null)
            //TODO : should we set an empty cardinality here ?
            addInternal(first);
        return first;
    }

    /**
     * The method <code>getNodes</code>
     *
     * @return a <code>NodeSet</code> value
     */
    private final NodeSet getNodes() {
        ExtArrayNodeSet result = new ExtArrayNodeSet();
        for (Iterator i = context.iterator(); i.hasNext();) {
            NodeProxy proxy = (NodeProxy) i.next();            
            if (proxy.getNodeId() == NodeId.DOCUMENT_NODE) {
                if(proxy.getDocument().getResourceType() == DocumentImpl.BINARY_FILE) {<commit_msg>Renamed some variables in VirtualNodeSet now that my understanding is better. Added some comments also.<commit_after>/*
 * eXist Open Source Native XML Database
 * Copyright (C) 2001-2007 The eXist Project
 * http://exist-db.org
 *
 * 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
 * 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.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software Foundation
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *  
 *  $Id$
 */
package org.exist.dom;

import java.util.Iterator;

import org.exist.numbering.NodeId;
import org.exist.xquery.Constants;
import org.exist.xquery.Expression;
import org.exist.xquery.NodeTest;
import org.exist.xquery.XPathException;
import org.exist.xquery.value.Item;
import org.exist.xquery.value.SequenceIterator;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;

/**
 * This node set is called virtual because it is just a placeholder for
 * the set of relevant nodes. For XPath expressions like //* or //node(), 
 * it would be totally unefficient to actually retrieve all descendant nodes.
 * In many cases, the expression can be resolved at a later point in time
 * without retrieving the whole node set. 
 *
 * VirtualNodeSet basically provides method getFirstParent to retrieve the first
 * matching descendant of its context according to the primary type axis.
 *
 * Class LocationStep will always return an instance of VirtualNodeSet
 * if it finds something like descendant::* etc..
 *
 * @author <NAME>
 * @author <NAME>
 */
public class VirtualNodeSet extends AbstractNodeSet {

    protected int axis = Constants.UNKNOWN_AXIS;
    protected NodeTest test;
    protected NodeSet context;
    protected NodeSet realSet = null;
    protected boolean realSetIsComplete = false;
    protected boolean inPredicate = false;
    protected boolean useSelfAsContext = false;
    protected int contextId = Expression.NO_CONTEXT_ID;
    private static final int MAX_CHILD_COUNT_FOR_OPTIMIZE = 5;
    private DocumentSet realDocumentSet = null; 
    
    private boolean knownIsEmptyCardinality = false;
    private boolean knownHasOneCardinality = false;
    private boolean knownHasManyCardinality = false;
    private boolean isEmpty = true;
    private boolean hasOne = false;    
    private boolean hasMany = false;    

    /**
     * Creates a new <code>VirtualNodeSet</code> instance.
     *
     * @param axis an <code>int</code> value
     * @param test a <code>NodeTest</code> value
     * @param contextId an <code>int</code> value
     * @param context a <code>NodeSet</code> value
     */
    public VirtualNodeSet(int axis, NodeTest test, int contextId, NodeSet context) {
        this.axis = axis;
        this.test = test;
        this.context = context;
        this.contextId = contextId;
    }

    /**
     * The method <code>contains</code>
     *
     * @param p a <code>NodeProxy</code> value
     * @return a <code>boolean</code> value
     */
    public boolean contains(NodeProxy p) {
        NodeProxy firstParent = getFirstParent(p, null, (axis == Constants.SELF_AXIS), 0);
        // <NAME>: getFirstParent returns now only real parents
        // therefore test if node is child of context
        if (firstParent != null) {
            return true;
        }
        //	if (context.get(p.getDocument(), p.getNodeId().getParentId()) != null) {
        //      return true;
        //	}
        return false; 
    }

    /**
     * The method <code>setInPredicate</code>
     *
     * @param predicate a <code>boolean</code> value
     */
    public void setInPredicate(boolean predicate) {
        inPredicate = predicate;
    }

    /* (non-Javadoc)
     * @see org.exist.dom.AbstractNodeSet#getDocumentSet()
     */
    public DocumentSet getDocumentSet() {
    	//If we know what are our documents, return them...
    	if (realDocumentSet != null)
    		return realDocumentSet;
    	//... otherwise, we default to every *ptotentially* concerned document
        return context.getDocumentSet();
    }

    /**
     * The method <code>getCollectionIterator</code>
     *
     * @return an <code>Iterator</code> value
     */
    public Iterator getCollectionIterator() {
        return context.getCollectionIterator();
    }

    /**
     * The method <code>getFirstParent</code>
     *
     * @param node a <code>NodeProxy</code> value
     * @param first a <code>NodeProxy</code> value
     * @param includeSelf a <code>boolean</code> value
     * @param recursions an <code>int</code> value
     * @return a <code>NodeProxy</code> value
     */
    private NodeProxy getFirstParent(NodeProxy self, NodeProxy firstParent,
                                     boolean includeSelf, int recursions) {
        return getFirstParent(self, firstParent, includeSelf, true, recursions);
    }

    /**
     * The method <code>getFirstParent</code>
     *
     * @param node a <code>NodeProxy</code> value
     * @param first a <code>NodeProxy</code> value
     * @param includeSelf a <code>boolean</code> value
     * @param directParent a <code>boolean</code> value
     * @param recursions an <code>int</code> value
     * @return a <code>NodeProxy</code> value
     */
    private NodeProxy getFirstParent(NodeProxy self, NodeProxy candidateFirstParent,
                                     boolean includeSelf, boolean restrictToDirectParent, int recursions) {
        
        /* if the node has is a doument node we still need to 
         * complete this method to check if we have found a potential parent
         * in one of the iterations before.
         */
        NodeId parentOfSelfId = self.getNodeId().getParentId();

        // check if the start-node should be included, e.g. to process an
        // expression like *[. = 'xxx']
        //TODO : investigate on expression like *[.//* = 'xxx']
        if (recursions == 0 && includeSelf && test.matches(self)) {
            // if we're on the child axis, test if
            // the node is a direct child of the context node
            if (axis == Constants.CHILD_AXIS) {
            	//WARNING : get() realizes virtual node sets
            	//TODO : investigate more efficent solutions
            	NodeProxy parent = context.get(self.getDocument(), parentOfSelfId);
                if (parent != null) {
                	self.copyContext(parent);
                    if (useSelfAsContext && inPredicate) {
                    	self.addContextNode(contextId, self);
                    } else if (inPredicate)
                    	self.addContextNode(contextId, parent);
                    return self;
                }
            } else {
                // descendant axis: remember the node and continue 
            	candidateFirstParent = self;
            }
        }
        
        // if this is the first call to this method, remember the first 
        // parent node and continue to evaluate the method. We can't just return 
        // the first parent as we need a parent that is *actually* contained 
        // in the context set. We will thus call the method again to complete.
        if (candidateFirstParent == null) {
        	//given node was already document element -> no parent
            if (parentOfSelfId == NodeId.DOCUMENT_NODE) {                
                return null;
            }
            candidateFirstParent = new NodeProxy(self.getDocument(), parentOfSelfId, Node.ELEMENT_NODE);
            // if we are on the self axis, check if the first parent can be selected
            if (axis == Constants.DESCENDANT_SELF_AXIS) {
            	//WARNING : get() realizes virtual node sets
            	//TODO : investigate more efficent solutions
                NodeProxy parent = context.get(candidateFirstParent.getDocument(), parentOfSelfId);
                if (parent != null && test.matches(parent)) {
                	candidateFirstParent.copyContext(parent);
                    if (useSelfAsContext && inPredicate) {
                    	candidateFirstParent.addContextNode(contextId, candidateFirstParent);
                    } else if (inPredicate)
                    	candidateFirstParent.addContextNode(contextId, parent);
                    return candidateFirstParent;
                }
            }
            // We need a real parent : keep the candidate and continue to ierate from this one
            return getFirstParent(candidateFirstParent, candidateFirstParent, false, restrictToDirectParent, recursions + 1);
        }
        
        // is the node's parent in the context set?
    	//WARNING : get() realizes virtual node sets
    	//TODO : investigate more efficent solutions
        NodeProxy parentOfSelf = context.get(self.getDocument(), parentOfSelfId);

        if (parentOfSelf != null && test.matches(self)) {
            if (axis != Constants.CHILD_AXIS) {
                // if we are on the descendant axis, we return the first node 
                // we found while walking bottom-up.
                // Otherwise, we return the last one (which is node)
            	self = candidateFirstParent;
            }
            self.copyContext(parentOfSelf);
            if (useSelfAsContext && inPredicate) {
            	self.addContextNode(contextId, self);
            } else if (inPredicate) {
            	self.addContextNode(contextId, parentOfSelf);
            }
            // <NAME>: we return the ancestor which is child of context			
            return self;
        } else if (parentOfSelfId == NodeId.DOCUMENT_NODE) {
            // no matching node has been found in the context
            return null;
        } else if (restrictToDirectParent && axis == Constants.CHILD_AXIS && recursions == 1) {
            // break here if the expression is like /*/n          
            return null;        
        } else {
            // continue for expressions like //*/n or /*//n
        	parentOfSelf = new NodeProxy(self.getDocument(), parentOfSelfId, Node.ELEMENT_NODE);
            return getFirstParent(parentOfSelf, candidateFirstParent, false, false, recursions + 1);
        }
    }

    private void addInternal(NodeProxy p) {
        if (realSet == null)
            realSet = new ExtArrayNodeSet(256);
        knownIsEmptyCardinality = true;
        if (isEmpty) {
            isEmpty = false;
            knownHasOneCardinality = true;
            hasOne= true;
        } else if (hasOne) {
            hasOne = false;
            knownHasManyCardinality = true;
            hasMany = true;	
        }
        realSet.add(p);
        //Reset the real document set
        //TODO : use realDocumentSet.add(p.getDocument()) ?
        realDocumentSet = null;
        realSetIsComplete = false;
    }

    /**
     * The method <code>parentWithChild</code>
     *
     * @param proxy a <code>NodeProxy</code> value
     * @param directParent a <code>boolean</code> value
     * @param includeSelf a <code>boolean</code> value
     * @param level an <code>int</code> value
     * @return a <code>NodeProxy</code> value
     */
    public NodeProxy parentWithChild(NodeProxy proxy, boolean restrictToDirectParent, boolean includeSelf,
                                     int level) {
        NodeProxy first = getFirstParent(proxy, null, includeSelf, restrictToDirectParent, 0);
        if (first != null)
            //TODO : should we set an empty cardinality here ?
            addInternal(first);
        return first;
    }

    /**
     * The method <code>parentWithChild</code>
     *
     * @param doc a <code>DocumentImpl</code> value
     * @param nodeId a <code>NodeId</code> value
     * @param directParent a <code>boolean</code> value
     * @param includeSelf a <code>boolean</code> value
     * @return a <code>NodeProxy</code> value
     */
    public NodeProxy parentWithChild(DocumentImpl doc, NodeId nodeId, boolean restrictToDirectParent, boolean includeSelf) {
    	NodeProxy first = getFirstParent(new NodeProxy(doc, nodeId), null, includeSelf, restrictToDirectParent, 0);
        if (first != null)
            //TODO : should we set an empty cardinality here ?
            addInternal(first);
        return first;
    }

    /**
     * The method <code>getNodes</code>
     *
     * @return a <code>NodeSet</code> value
     */
    private final NodeSet getNodes() {
        ExtArrayNodeSet result = new ExtArrayNodeSet();
        for (Iterator i = context.iterator(); i.hasNext();) {
            NodeProxy proxy = (NodeProxy) i.next();            
            if (proxy.getNodeId() == NodeId.DOCUMENT_NODE) {
                if(proxy.getDocument().getResourceType() == DocumentImpl.BINARY_FILE) {
{'fraction_non_alphanumeric': 0.09223529411764705, 'fraction_numerical': 0.0026274509803921567, 'mean_word_length': 2.1721607165070282, 'pattern_counts': {'":': 0, '<': 167, '<?xml version=': 0, '>': 169, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3000397', 'n_tokens_mistral': 6881, 'n_tokens_neox': 6667, 'n_words': 2241}