<commit_before>/*
 *  eXist Open Source Native XML Database
 *  Copyright (C) 2001-2015 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 library; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
package org.exist.storage.structural;

import org.exist.dom.TypedQNameComparator;
import org.exist.dom.persistent.AttrImpl;
import org.exist.dom.persistent.NodeProxy;
import org.exist.dom.QName;
import org.exist.dom.persistent.ElementImpl;
import org.exist.dom.persistent.DocumentSet;
import org.exist.dom.persistent.DocumentImpl;
import org.exist.dom.persistent.IStoredNode;
import org.exist.dom.persistent.SymbolTable;
import org.exist.dom.persistent.NewArrayNodeSet;
import org.exist.dom.persistent.ExtNodeSet;
import org.exist.dom.persistent.NodeSet;
import org.exist.collections.Collection;
import org.exist.indexing.*;
import org.exist.numbering.NodeId;
import org.exist.storage.*;
import org.exist.storage.btree.BTree;
import org.exist.storage.btree.BTreeCallback;
import org.exist.storage.btree.IndexQuery;
import org.exist.storage.btree.Value;
import org.exist.storage.lock.Lock;
import org.exist.storage.txn.Txn;
import org.exist.util.ByteConversion;
import org.exist.util.DatabaseConfigurationException;
import org.exist.util.LockException;
import org.exist.util.Occurrences;
import org.exist.xquery.*;
import org.exist.xquery.NodeTest;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;

import java.util.*;
import org.exist.security.PermissionDeniedException;

/**
 * Internal default implementation of the structural index. It uses a single btree, in which
 * each key represents a sequence of: [type, qname, documentId, nodeId]. The btree value is just a
 * long pointing to the storage address of the actual node in dom.dbx.
 */
public class NativeStructuralIndexWorker implements IndexWorker, StructuralIndex {

    private NativeStructuralIndex index;
    private int mode = 0;
    private DocumentImpl document;

    //TODO throw away this Comparator or use a different data struct here when we have moved
    //nameType out of QName
    private Map<QName, List<NodeProxy>> pending = new TreeMap<>(new TypedQNameComparator());

    public NativeStructuralIndexWorker(NativeStructuralIndex index) {
        this.index = index;
    }

    public boolean matchElementsByTagName(byte type, DocumentSet docs, QName qname, NodeSelector selector) {
        return false;
    }

    public boolean matchDescendantsByTagName(byte type, QName qname, int axis, DocumentSet docs, ExtNodeSet contextSet, int contextId) {
        return false;
    }

    /**
     * Find all nodes in the index matching a given QName. If a match is selected and returned depends on
     * the specified {@link org.exist.xquery.NodeSelector}.
     *
     * This implementation does a scan through the index for a range of document ids in the input set.
     * It will be fast for bulk-loading a large node set, but slow if you need to operate on a small
     * context set.
     *
     * @param type
     * @param docs
     * @param qname
     * @param selector
     * @return nodeset
     */
    public NodeSet findElementsByTagName(byte type, DocumentSet docs, QName qname, NodeSelector selector) {
        return findElementsByTagName(type, docs, qname, selector, null);
    }

    public NodeSet findElementsByTagName(byte type, DocumentSet docs, QName qname, NodeSelector selector, Expression parent) {
        final Lock lock = index.btree.getLock();
        final NewArrayNodeSet result = new NewArrayNodeSet();
        final FindElementsCallback callback = new FindElementsCallback(type, result, docs, selector, parent);

        // for each document id range, scan the index to find matches
        for (final Range range : getDocIdRanges(docs)) {
            final byte[] fromKey = computeKey(type, qname, range.start);
            final byte[] toKey = computeKey(type, qname, range.end + 1);
            final IndexQuery query = new IndexQuery(IndexQuery.RANGE, new Value(fromKey), new Value(toKey));
            try {
                lock.acquire(Lock.READ_LOCK);
                index.btree.query(query, callback);
            } catch (final LockException e) {
                NativeStructuralIndex.LOG.warn("Lock problem while searching structural index: " + e.getMessage(), e);
            } catch (final TerminatedException e) {
                NativeStructuralIndex.LOG.warn("Query was terminated while searching structural index: " + e.getMessage(), e);
            } catch (final Exception e) {
                NativeStructuralIndex.LOG.error("Error while searching structural index: " + e.getMessage(), e);
            } finally {
                lock.release(Lock.READ_LOCK);
            }
        }
        return result;
    }

    /**
     * Scan the document set to find document id ranges to query
     *
     * @param docs
     * @return List of contiguous document id ranges
     */
    List<Range> getDocIdRanges(final DocumentSet docs) {
        final List<Range> ranges = new ArrayList<>();
        Range next = null;
        for (final Iterator<DocumentImpl> i = docs.getDocumentIterator(); i.hasNext(); ) {
            final DocumentImpl doc = i.next();
            if (next == null) {
                next = new Range(doc.getDocId());
            } else if (next.end + 1 == doc.getDocId()) {
                next.end++;
            } else {
                ranges.add(next);
                next = new Range(doc.getDocId());
            }
        }
        if (next != null) {
            ranges.add(next);
        }

        return ranges;
    }

    /**
     * Internal helper class used by
     * {@link NativeStructuralIndexWorker#findElementsByTagName(byte, org.exist.dom.persistent.DocumentSet, org.exist.dom.QName, org.exist.xquery.NodeSelector)}.
     */
    static class Range {
        int start = -1;
        int end = -1;

        private Range(int start) {
            this.start = start;
            this.end = start;
        }
    }
    
    /**
     * Find all descendants (or children) of the specified node set matching the given QName.
     *
     * This implementation does one btree lookup for every node in contextSet. It offers superior performance
     * if the number of nodes in contextSet is rather small compared to the overall number of nodes in
     * the index.
     */
    public NodeSet findDescendantsByTagName(byte type, QName qname, int axis, DocumentSet docs, NodeSet contextSet, int contextId) {
        return findDescendantsByTagName(type, qname, axis, docs, contextSet, contextId, null);
    }

    public NodeSet findDescendantsByTagName(byte type, QName qname, int axis, DocumentSet docs, NodeSet contextSet, int contextId, Expression parent) {
        final Lock lock = index.btree.getLock();
        final NewArrayNodeSet result = new NewArrayNodeSet();
        final FindDescendantsCallback callback = new FindDescendantsCallback(type, axis, contextId, result, parent);
        try {
            lock.acquire(Lock.READ_LOCK);
            for (final NodeProxy ancestor : contextSet) {
                final DocumentImpl doc = ancestor.getOwnerDocument();
                final NodeId ancestorId = ancestor.getNodeId();
                callback.setAncestor(doc, ancestor);
                byte[] fromKey, toKey;
                if (ancestorId == NodeId.DOCUMENT_NODE) {
                    fromKey = computeKey(type, qname, doc.getDocId());
                    toKey = computeKey(type, qname, doc.getDocId() + 1);
                } else {
                    fromKey = computeKey(type, qname, doc.getDocId(), ancestorId);
                    toKey = computeKey(type, qname, doc.getDocId(), ancestorId.nextSibling());
                }
                final IndexQuery query = new IndexQuery(IndexQuery.RANGE, new Value(fromKey), new Value(toKey));
                try {
                    index.btree.query(query, callback);
                } catch (final Exception e) {
                    NativeStructuralIndex.LOG.error("Error while searching structural index: " + e.getMessage(), e);
                }
            }
        } catch (final LockException e) {
            NativeStructuralIndex.LOG.warn("Lock problem while searching structural index: " + e.getMessage(), e);
        } finally {
            lock.release(Lock.READ_LOCK);
        }
        result.updateNoSort();
        return result;
    }

    public NodeSet findAncestorsByTagName(byte type, QName qname, int axis, DocumentSet docs, NodeSet contextSet,
                                          int contextId) {
        final Lock lock = index.btree.getLock();
        final NewArrayNodeSet result = new NewArrayNodeSet();
        try {
            lock.acquire(Lock.READ_LOCK);
            for (final NodeProxy descendant : contextSet) {
                NodeId parentId;
                if (axis == Constants.ANCESTOR_SELF_AXIS || axis == Constants.SELF_AXIS)
                    {parentId = descendant.getNodeId();}
                else
                    {parentId = descendant.getNodeId().getParentId();}
                final DocumentImpl doc = descendant.getOwnerDocument();
                while (parentId != NodeId.DOCUMENT_NODE) {
                    final byte[] key = computeKey(type, qname, doc.getDocId(), parentId);
                    final long address = index.btree.findValue(new Value(key));
                    if (address != -1) {
                        final NodeProxy storedNode = new NodeProxy(doc, parentId,
                            type == ElementValue.ATTRIBUTE ? Node.ATTRIBUTE_NODE : Node.ELEMENT_NODE, address);
                        result.add(storedNode);
                        if (Expression.NO_CONTEXT_ID != contextId) {
                            storedNode.deepCopyContext(descendant, contextId);
                        } else
                            {storedNode.copyContext(descendant);}
                        if (contextSet.getTrackMatches())
                        	{storedNode.addMatches(descendant);}
                    }
                    // stop after first iteration if we are on the self axis
                    if (axis == Constants.SELF_AXIS || axis == Constants.PARENT_AXIS)
                        {break;}
                    // continue with the parent of the parent
                    parentId = parentId.getParentId();
                }
            }
        } catch (final LockException e) {
            NativeStructuralIndex.LOG.warn("Lock problem while searching structural index: " + e.getMessage(), e);
        } catch (final Exception e) {
            NativeStructuralIndex.LOG.error("Error while searching structural index: " + e.getMessage(), e);
        } finally {
            lock.release(Lock.READ_LOCK);
        }
        result.sort(true);
        return result;
    }

    public NodeSet scanByType(byte type, int axis, NodeTest test, boolean useSelfAsContext, DocumentSet docs, 
    		NodeSet contextSet, int contextId) {
        final Lock lock = index.btree.getLock();
        final NewArrayNodeSet result = new NewArrayNodeSet();
        final FindDescendantsCallback callback = new FindDescendantsCallback(type, axis, contextId, useSelfAsContext, result, null);
        for (final NodeProxy ancestor : contextSet) {
            final DocumentImpl doc = ancestor.getOwnerDocument();
            final NodeId ancestorId = ancestor.getNodeId();
            final List<QName> qnames = getQNamesForDoc(doc);
            try {
	            lock.acquire(Lock.READ_LOCK);
	            for (final QName qname : qnames) {
	            	if (test.getName() == null || test.matches(qname)) {
	            		callback.setAncestor(doc, ancestor);
	            		byte[] fromKey, toKey;
	                    if (ancestorId == NodeId.DOCUMENT_NODE) {
	                        fromKey = computeKey(type, qname, doc.getDocId());
	                        toKey = computeKey(type, qname, doc.getDocId() + 1);
	                    } else {
	                        fromKey = computeKey(type, qname, doc.getDocId(), ancestorId);
	                        toKey = computeKey(type, qname, doc.getDocId(), ancestorId.nextSibling());
	                    }
	                    final IndexQuery query = new IndexQuery(IndexQuery.RANGE, new Value(fromKey), new Value(toKey));
	                    try {
	                        index.btree.query(query, callback);
	                    } catch (final Exception e) {
	                        NativeStructuralIndex.LOG.error("Error while searching structural index: " + e.getMessage(), e);
	                    }
	            	}
	            }
            } catch (final LockException e) {
                NativeStructuralIndex.LOG.warn("Lock problem while searching structural index: " + e.getMessage(), e);
            } finally {
                lock.release(Lock.READ_LOCK);
            }
        }
//        result.updateNoSort();
        return result;
    }
    
    private class FindElementsCallback implements BTreeCallback {
        byte type;
        DocumentSet docs;
        NewArrayNodeSet result;
        NodeSelector selector;
        Expression parent;

        FindElementsCallback(byte type, NewArrayNodeSet result, DocumentSet docs, NodeSelector selector, Expression parent) {
            this.type = type;
            this.result = result;
            this.docs = docs;
            this.selector = selector;
            this.parent = parent;
        }

        public boolean indexInfo(Value value, long pointer) throws TerminatedException {
            if (parent != null) {
                parent.getContext().proceed(parent);
            }
            final byte[] key = value.getData();
            final NodeId nodeId = readNodeId(key, pointer);
            final DocumentImpl doc = docs.getDoc(readDocId(key));
            if (doc != null) {
                if (selector == null) {
                    final NodeProxy storedNode = new NodeProxy(doc, nodeId,
                        type == ElementValue.ATTRIBUTE ? Node.ATTRIBUTE_NODE : Node.ELEMENT_NODE, pointer);
                    result.add(storedNode);
                } else {
                    final NodeProxy storedNode = selector.match(doc, nodeId);
                    if (storedNode != null) {
                        storedNode.setNodeType(type == ElementValue.ATTRIBUTE ? Node.ATTRIBUTE_NODE : Node.ELEMENT_NODE);
                        storedNode.setInternalAddress(pointer);
                        result.add(storedNode);
                    }
                }
            }
            return true;
        }
    }

    private class FindDescendantsCallback implements BTreeCallback {
        int axis;
        byte type;
        NodeProxy ancestor;
        DocumentImpl doc;
        int contextId;
        NewArrayNodeSet result;
        boolean selfAsContext = false;
        Expression parent;

        FindDescendantsCallback(byte type, int axis, int contextId, NewArrayNodeSet result, Expression parent) {
        	this(type, axis, contextId, false, result, parent);
        };
        
        FindDescendantsCallback(byte type, int axis, int contextId, boolean selfAsContext, NewArrayNodeSet result, Expression parent) {
            this.type = type;
            this.axis = axis;
            this.contextId = contextId;
            this.result = result;
            this.selfAsContext = selfAsContext;
            this.parent = parent;
        }

        void setAncestor(DocumentImpl doc, NodeProxy ancestor) {
            this.doc = doc;
            this.ancestor = ancestor;
        }

        public boolean indexInfo(Value value, long pointer) throws TerminatedException {
            if (parent != null) {
                parent.getContext().proceed(parent);
            }
            final NodeId nodeId = readNodeId(value.getData(), pointer);

            boolean match = axis == Constants.DESCENDANT_SELF_AXIS || axis == Constants.DESCENDANT_ATTRIBUTE_AXIS;
            if (!match) {
                final int relation = nodeId.computeRelation(ancestor.getNodeId());
                match = (((axis == Constants.CHILD_AXIS) || (axis == Constants.ATTRIBUTE_AXIS)) && (relation == NodeId.IS_CHILD)) ||
                    ((axis == Constants.DESCENDANT_AXIS) && ((relation == NodeId.IS_DESCENDANT) || (relation == NodeId.IS_CHILD)));
            }
            if (match) {
                final NodeProxy storedNode =
                    new NodeProxy(doc, nodeId, type == ElementValue.ATTRIBUTE ? Node.ATTRIBUTE_NODE : Node.ELEMENT_NODE, pointer);
                result.add(storedNode);
                if (Expression.NO_CONTEXT_ID != contextId) {
                	if (selfAsContext)
                		{storedNode.addContextNode(contextId, storedNode);}
                	else
                		{storedNode.deepCopyContext(ancestor, contextId);}
                } else {
            		storedNode.copyContext(ancestor);
                }
                storedNode.addMatches(ancestor);
            }
            return true;
        }
    }
    
    public String getIndexId() {
        return NativeStructuralIndex.ID;<commit_msg>[performance] Preserve node name information if known during structural index lookup.<commit_after>/*
 *  eXist Open Source Native XML Database
 *  Copyright (C) 2001-2015 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 library; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
package org.exist.storage.structural;

import org.exist.dom.TypedQNameComparator;
import org.exist.dom.persistent.AttrImpl;
import org.exist.dom.persistent.NodeProxy;
import org.exist.dom.QName;
import org.exist.dom.persistent.ElementImpl;
import org.exist.dom.persistent.DocumentSet;
import org.exist.dom.persistent.DocumentImpl;
import org.exist.dom.persistent.IStoredNode;
import org.exist.dom.persistent.SymbolTable;
import org.exist.dom.persistent.NewArrayNodeSet;
import org.exist.dom.persistent.ExtNodeSet;
import org.exist.dom.persistent.NodeSet;
import org.exist.collections.Collection;
import org.exist.indexing.*;
import org.exist.numbering.NodeId;
import org.exist.storage.*;
import org.exist.storage.btree.BTree;
import org.exist.storage.btree.BTreeCallback;
import org.exist.storage.btree.IndexQuery;
import org.exist.storage.btree.Value;
import org.exist.storage.lock.Lock;
import org.exist.storage.txn.Txn;
import org.exist.util.ByteConversion;
import org.exist.util.DatabaseConfigurationException;
import org.exist.util.LockException;
import org.exist.util.Occurrences;
import org.exist.xquery.*;
import org.exist.xquery.NodeTest;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;

import java.util.*;
import org.exist.security.PermissionDeniedException;

/**
 * Internal default implementation of the structural index. It uses a single btree, in which
 * each key represents a sequence of: [type, qname, documentId, nodeId]. The btree value is just a
 * long pointing to the storage address of the actual node in dom.dbx.
 */
public class NativeStructuralIndexWorker implements IndexWorker, StructuralIndex {

    private NativeStructuralIndex index;
    private int mode = 0;
    private DocumentImpl document;

    //TODO throw away this Comparator or use a different data struct here when we have moved
    //nameType out of QName
    private Map<QName, List<NodeProxy>> pending = new TreeMap<>(new TypedQNameComparator());

    public NativeStructuralIndexWorker(NativeStructuralIndex index) {
        this.index = index;
    }

    public boolean matchElementsByTagName(byte type, DocumentSet docs, QName qname, NodeSelector selector) {
        return false;
    }

    public boolean matchDescendantsByTagName(byte type, QName qname, int axis, DocumentSet docs, ExtNodeSet contextSet, int contextId) {
        return false;
    }

    /**
     * Find all nodes in the index matching a given QName. If a match is selected and returned depends on
     * the specified {@link org.exist.xquery.NodeSelector}.
     *
     * This implementation does a scan through the index for a range of document ids in the input set.
     * It will be fast for bulk-loading a large node set, but slow if you need to operate on a small
     * context set.
     *
     * @param type
     * @param docs
     * @param qname
     * @param selector
     * @return nodeset
     */
    public NodeSet findElementsByTagName(byte type, DocumentSet docs, QName qname, NodeSelector selector) {
        return findElementsByTagName(type, docs, qname, selector, null);
    }

    public NodeSet findElementsByTagName(byte type, DocumentSet docs, QName qname, NodeSelector selector, Expression parent) {
        final Lock lock = index.btree.getLock();
        final NewArrayNodeSet result = new NewArrayNodeSet();
        final FindElementsCallback callback = new FindElementsCallback(type, qname, result, docs, selector, parent);

        // for each document id range, scan the index to find matches
        for (final Range range : getDocIdRanges(docs)) {
            final byte[] fromKey = computeKey(type, qname, range.start);
            final byte[] toKey = computeKey(type, qname, range.end + 1);
            final IndexQuery query = new IndexQuery(IndexQuery.RANGE, new Value(fromKey), new Value(toKey));
            try {
                lock.acquire(Lock.READ_LOCK);
                index.btree.query(query, callback);
            } catch (final LockException e) {
                NativeStructuralIndex.LOG.warn("Lock problem while searching structural index: " + e.getMessage(), e);
            } catch (final TerminatedException e) {
                NativeStructuralIndex.LOG.warn("Query was terminated while searching structural index: " + e.getMessage(), e);
            } catch (final Exception e) {
                NativeStructuralIndex.LOG.error("Error while searching structural index: " + e.getMessage(), e);
            } finally {
                lock.release(Lock.READ_LOCK);
            }
        }
        return result;
    }

    /**
     * Scan the document set to find document id ranges to query
     *
     * @param docs
     * @return List of contiguous document id ranges
     */
    List<Range> getDocIdRanges(final DocumentSet docs) {
        final List<Range> ranges = new ArrayList<>();
        Range next = null;
        for (final Iterator<DocumentImpl> i = docs.getDocumentIterator(); i.hasNext(); ) {
            final DocumentImpl doc = i.next();
            if (next == null) {
                next = new Range(doc.getDocId());
            } else if (next.end + 1 == doc.getDocId()) {
                next.end++;
            } else {
                ranges.add(next);
                next = new Range(doc.getDocId());
            }
        }
        if (next != null) {
            ranges.add(next);
        }

        return ranges;
    }

    /**
     * Internal helper class used by
     * {@link NativeStructuralIndexWorker#findElementsByTagName(byte, org.exist.dom.persistent.DocumentSet, org.exist.dom.QName, org.exist.xquery.NodeSelector)}.
     */
    static class Range {
        int start = -1;
        int end = -1;

        private Range(int start) {
            this.start = start;
            this.end = start;
        }
    }
    
    /**
     * Find all descendants (or children) of the specified node set matching the given QName.
     *
     * This implementation does one btree lookup for every node in contextSet. It offers superior performance
     * if the number of nodes in contextSet is rather small compared to the overall number of nodes in
     * the index.
     */
    public NodeSet findDescendantsByTagName(byte type, QName qname, int axis, DocumentSet docs, NodeSet contextSet, int contextId) {
        return findDescendantsByTagName(type, qname, axis, docs, contextSet, contextId, null);
    }

    public NodeSet findDescendantsByTagName(byte type, QName qname, int axis, DocumentSet docs, NodeSet contextSet, int contextId, Expression parent) {
        final Lock lock = index.btree.getLock();
        final NewArrayNodeSet result = new NewArrayNodeSet();
        final FindDescendantsCallback callback = new FindDescendantsCallback(type, axis, qname, contextId, result, parent);
        try {
            lock.acquire(Lock.READ_LOCK);
            for (final NodeProxy ancestor : contextSet) {
                final DocumentImpl doc = ancestor.getOwnerDocument();
                final NodeId ancestorId = ancestor.getNodeId();
                callback.setAncestor(doc, ancestor);
                byte[] fromKey, toKey;
                if (ancestorId == NodeId.DOCUMENT_NODE) {
                    fromKey = computeKey(type, qname, doc.getDocId());
                    toKey = computeKey(type, qname, doc.getDocId() + 1);
                } else {
                    fromKey = computeKey(type, qname, doc.getDocId(), ancestorId);
                    toKey = computeKey(type, qname, doc.getDocId(), ancestorId.nextSibling());
                }
                final IndexQuery query = new IndexQuery(IndexQuery.RANGE, new Value(fromKey), new Value(toKey));
                try {
                    index.btree.query(query, callback);
                } catch (final Exception e) {
                    NativeStructuralIndex.LOG.error("Error while searching structural index: " + e.getMessage(), e);
                }
            }
        } catch (final LockException e) {
            NativeStructuralIndex.LOG.warn("Lock problem while searching structural index: " + e.getMessage(), e);
        } finally {
            lock.release(Lock.READ_LOCK);
        }
        result.updateNoSort();
        return result;
    }

    public NodeSet findAncestorsByTagName(byte type, QName qname, int axis, DocumentSet docs, NodeSet contextSet,
                                          int contextId) {
        final Lock lock = index.btree.getLock();
        final NewArrayNodeSet result = new NewArrayNodeSet();
        try {
            lock.acquire(Lock.READ_LOCK);
            for (final NodeProxy descendant : contextSet) {
                NodeId parentId;
                if (axis == Constants.ANCESTOR_SELF_AXIS || axis == Constants.SELF_AXIS)
                    {parentId = descendant.getNodeId();}
                else
                    {parentId = descendant.getNodeId().getParentId();}
                final DocumentImpl doc = descendant.getOwnerDocument();
                while (parentId != NodeId.DOCUMENT_NODE) {
                    final byte[] key = computeKey(type, qname, doc.getDocId(), parentId);
                    final long address = index.btree.findValue(new Value(key));
                    if (address != -1) {
                        final NodeProxy storedNode = new NodeProxy(doc, parentId,
                            type == ElementValue.ATTRIBUTE ? Node.ATTRIBUTE_NODE : Node.ELEMENT_NODE, address);
                        result.add(storedNode);
                        if (Expression.NO_CONTEXT_ID != contextId) {
                            storedNode.deepCopyContext(descendant, contextId);
                        } else
                            {storedNode.copyContext(descendant);}
                        if (contextSet.getTrackMatches())
                        	{storedNode.addMatches(descendant);}
                    }
                    // stop after first iteration if we are on the self axis
                    if (axis == Constants.SELF_AXIS || axis == Constants.PARENT_AXIS)
                        {break;}
                    // continue with the parent of the parent
                    parentId = parentId.getParentId();
                }
            }
        } catch (final LockException e) {
            NativeStructuralIndex.LOG.warn("Lock problem while searching structural index: " + e.getMessage(), e);
        } catch (final Exception e) {
            NativeStructuralIndex.LOG.error("Error while searching structural index: " + e.getMessage(), e);
        } finally {
            lock.release(Lock.READ_LOCK);
        }
        result.sort(true);
        return result;
    }

    public NodeSet scanByType(byte type, int axis, NodeTest test, boolean useSelfAsContext, DocumentSet docs, 
    		NodeSet contextSet, int contextId) {
        final Lock lock = index.btree.getLock();
        final NewArrayNodeSet result = new NewArrayNodeSet();
        final FindDescendantsCallback callback = new FindDescendantsCallback(type, axis, null, contextId, useSelfAsContext, result, null);
        for (final NodeProxy ancestor : contextSet) {
            final DocumentImpl doc = ancestor.getOwnerDocument();
            final NodeId ancestorId = ancestor.getNodeId();
            final List<QName> qnames = getQNamesForDoc(doc);
            try {
	            lock.acquire(Lock.READ_LOCK);
	            for (final QName qname : qnames) {
	            	if (test.getName() == null || test.matches(qname)) {
	            		callback.setAncestor(doc, ancestor);
	            		byte[] fromKey, toKey;
	                    if (ancestorId == NodeId.DOCUMENT_NODE) {
	                        fromKey = computeKey(type, qname, doc.getDocId());
	                        toKey = computeKey(type, qname, doc.getDocId() + 1);
	                    } else {
	                        fromKey = computeKey(type, qname, doc.getDocId(), ancestorId);
	                        toKey = computeKey(type, qname, doc.getDocId(), ancestorId.nextSibling());
	                    }
	                    final IndexQuery query = new IndexQuery(IndexQuery.RANGE, new Value(fromKey), new Value(toKey));
	                    try {
	                        index.btree.query(query, callback);
	                    } catch (final Exception e) {
	                        NativeStructuralIndex.LOG.error("Error while searching structural index: " + e.getMessage(), e);
	                    }
	            	}
	            }
            } catch (final LockException e) {
                NativeStructuralIndex.LOG.warn("Lock problem while searching structural index: " + e.getMessage(), e);
            } finally {
                lock.release(Lock.READ_LOCK);
            }
        }
//        result.updateNoSort();
        return result;
    }
    
    private class FindElementsCallback implements BTreeCallback {
        byte type;
        QName qname;
        DocumentSet docs;
        NewArrayNodeSet result;
        NodeSelector selector;
        Expression parent;

        FindElementsCallback(byte type, QName qname, NewArrayNodeSet result, DocumentSet docs, NodeSelector selector, Expression parent) {
            this.type = type;
            this.result = result;
            this.docs = docs;
            this.selector = selector;
            this.parent = parent;
            if (qname.getNameType() != type) {
                this.qname = new QName(qname.getLocalPart(), qname.getNamespaceURI(), qname.getPrefix(), type);
            } else {
                this.qname = qname;
            }
        }

        public boolean indexInfo(Value value, long pointer) throws TerminatedException {
            if (parent != null) {
                parent.getContext().proceed(parent);
            }
            final byte[] key = value.getData();
            final NodeId nodeId = readNodeId(key, pointer);
            final DocumentImpl doc = docs.getDoc(readDocId(key));
            if (doc != null) {
                if (selector == null) {
                    final NodeProxy storedNode = new NodeProxy(doc, nodeId,
                        type == ElementValue.ATTRIBUTE ? Node.ATTRIBUTE_NODE : Node.ELEMENT_NODE, pointer);
                    if (qname != null) {
                        storedNode.setQName(qname);
                    }
                    result.add(storedNode);
                } else {
                    final NodeProxy storedNode = selector.match(doc, nodeId);
                    if (storedNode != null) {
                        storedNode.setNodeType(type == ElementValue.ATTRIBUTE ? Node.ATTRIBUTE_NODE : Node.ELEMENT_NODE);
                        storedNode.setInternalAddress(pointer);
                        if (qname != null) {
                            storedNode.setQName(qname);
                        }
                        result.add(storedNode);
                    }
                }
            }
            return true;
        }
    }

    private class FindDescendantsCallback implements BTreeCallback {
        int axis;
        byte type;
        QName qname;
        NodeProxy ancestor;
        DocumentImpl doc;
        int contextId;
        NewArrayNodeSet result;
        boolean selfAsContext = false;
        Expression parent;

        FindDescendantsCallback(byte type, int axis, QName qname, int contextId, NewArrayNodeSet result, Expression parent) {
        	this(type, axis, qname, contextId, false, result, parent);
        }
        
        FindDescendantsCallback(byte type, int axis, QName qname, int contextId, boolean selfAsContext, NewArrayNodeSet result, Expression parent) {
            this.type = type;
            this.axis = axis;
            this.contextId = contextId;
            this.result = result;
            this.selfAsContext = selfAsContext;
            this.parent = parent;
            if (qname.getNameType() != type) {
                this.qname = new QName(qname.getLocalPart(), qname.getNamespaceURI(), qname.getPrefix(), type);
            } else {
                this.qname = qname;
            }
        }

        void setAncestor(DocumentImpl doc, NodeProxy ancestor) {
            this.doc = doc;
            this.ancestor = ancestor;
        }

        public boolean indexInfo(Value value, long pointer) throws TerminatedException {
            if (parent != null) {
                parent.getContext().proceed(parent);
            }
            final NodeId nodeId = readNodeId(value.getData(), pointer);

            boolean match = axis == Constants.DESCENDANT_SELF_AXIS || axis == Constants.DESCENDANT_ATTRIBUTE_AXIS;
            if (!match) {
                final int relation = nodeId.computeRelation(ancestor.getNodeId());
                match = (((axis == Constants.CHILD_AXIS) || (axis == Constants.ATTRIBUTE_AXIS)) && (relation == NodeId.IS_CHILD)) ||
                    ((axis == Constants.DESCENDANT_AXIS) && ((relation == NodeId.IS_DESCENDANT) || (relation == NodeId.IS_CHILD)));
            }
            if (match) {
                final NodeProxy storedNode =
                    new NodeProxy(doc, nodeId, type == ElementValue.ATTRIBUTE ? Node.ATTRIBUTE_NODE : Node.ELEMENT_NODE, pointer);
                if (qname != null) {
                    storedNode.setQName(qname);
                }
                result.add(storedNode);
                if (Expression.NO_CONTEXT_ID != contextId) {
                	if (selfAsContext)
                		{storedNode.addContextNode(contextId, storedNode);}
                	else
                		{storedNode.deepCopyContext(ancestor, contextId);}
                } else {
            		storedNode.copyContext(ancestor);
                }
                storedNode.addMatches(ancestor);
            }
            return true;
        }
    }
    
    public String getIndexId() {
        return NativeStructuralIndex.ID;
{'fraction_non_alphanumeric': 0.0893345737112838, 'fraction_numerical': 0.0016416766991353836, 'mean_word_length': 2.0564475664826896, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6439948', 'n_tokens_mistral': 9723, 'n_tokens_neox': 9380, 'n_words': 2673}