You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2014/07/20 14:08:33 UTC
svn commit: r1612080 [2/3] - in /lucene/dev/trunk/lucene: ./
codecs/src/java/org/apache/lucene/codecs/blocktreeords/
codecs/src/resources/META-INF/services/
codecs/src/test/org/apache/lucene/codecs/blocktreeords/
core/src/java/org/apache/lucene/codecs/...
Added: lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsIntersectTermsEnum.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsIntersectTermsEnum.java?rev=1612080&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsIntersectTermsEnum.java (added)
+++ lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsIntersectTermsEnum.java Sun Jul 20 12:08:32 2014
@@ -0,0 +1,485 @@
+package org.apache.lucene.codecs.blocktreeords;
+
+/*
+ * 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.
+ */
+
+import java.io.IOException;
+
+import org.apache.lucene.codecs.blocktreeords.FSTOrdsOutputs.Output;
+import org.apache.lucene.index.DocsAndPositionsEnum;
+import org.apache.lucene.index.DocsEnum;
+import org.apache.lucene.index.FieldInfo.IndexOptions;
+import org.apache.lucene.index.TermState;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.store.IndexInput;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.RamUsageEstimator;
+import org.apache.lucene.util.StringHelper;
+import org.apache.lucene.util.automaton.CompiledAutomaton;
+import org.apache.lucene.util.automaton.RunAutomaton;
+import org.apache.lucene.util.fst.FST;
+
+// NOTE: cannot seek!
+final class OrdsIntersectTermsEnum extends TermsEnum {
+ final IndexInput in;
+
+ private OrdsIntersectTermsEnumFrame[] stack;
+
+ @SuppressWarnings({"rawtypes","unchecked"}) private FST.Arc<Output>[] arcs = new FST.Arc[5];
+
+ final RunAutomaton runAutomaton;
+ final CompiledAutomaton compiledAutomaton;
+
+ private OrdsIntersectTermsEnumFrame currentFrame;
+
+ private final BytesRef term = new BytesRef();
+
+ private final FST.BytesReader fstReader;
+
+ final OrdsFieldReader fr;
+
+ private BytesRef savedStartTerm;
+
+ // TODO: in some cases we can filter by length? eg
+ // regexp foo*bar must be at least length 6 bytes
+ public OrdsIntersectTermsEnum(OrdsFieldReader fr, CompiledAutomaton compiled, BytesRef startTerm) throws IOException {
+ // if (DEBUG) {
+ // System.out.println("\nintEnum.init seg=" + segment + " commonSuffix=" + brToString(compiled.commonSuffixRef));
+ // }
+ this.fr = fr;
+ runAutomaton = compiled.runAutomaton;
+ compiledAutomaton = compiled;
+ in = fr.parent.in.clone();
+ stack = new OrdsIntersectTermsEnumFrame[5];
+ for(int idx=0;idx<stack.length;idx++) {
+ stack[idx] = new OrdsIntersectTermsEnumFrame(this, idx);
+ }
+ for(int arcIdx=0;arcIdx<arcs.length;arcIdx++) {
+ arcs[arcIdx] = new FST.Arc<>();
+ }
+
+ if (fr.index == null) {
+ fstReader = null;
+ } else {
+ fstReader = fr.index.getBytesReader();
+ }
+
+ // TODO: if the automaton is "smallish" we really
+ // should use the terms index to seek at least to
+ // the initial term and likely to subsequent terms
+ // (or, maybe just fallback to ATE for such cases).
+ // Else the seek cost of loading the frames will be
+ // too costly.
+
+ final FST.Arc<Output> arc = fr.index.getFirstArc(arcs[0]);
+ // Empty string prefix must have an output in the index!
+ assert arc.isFinal();
+
+ // Special pushFrame since it's the first one:
+ final OrdsIntersectTermsEnumFrame f = stack[0];
+ f.fp = f.fpOrig = fr.rootBlockFP;
+ f.prefix = 0;
+ f.setState(runAutomaton.getInitialState());
+ f.arc = arc;
+ f.outputPrefix = arc.output;
+ f.load(fr.rootCode);
+
+ // for assert:
+ assert setSavedStartTerm(startTerm);
+
+ currentFrame = f;
+ if (startTerm != null) {
+ seekToStartTerm(startTerm);
+ }
+ }
+
+ // only for assert:
+ private boolean setSavedStartTerm(BytesRef startTerm) {
+ savedStartTerm = startTerm == null ? null : BytesRef.deepCopyOf(startTerm);
+ return true;
+ }
+
+ @Override
+ public TermState termState() throws IOException {
+ currentFrame.decodeMetaData();
+ return currentFrame.termState.clone();
+ }
+
+ private OrdsIntersectTermsEnumFrame getFrame(int ord) throws IOException {
+ if (ord >= stack.length) {
+ final OrdsIntersectTermsEnumFrame[] next = new OrdsIntersectTermsEnumFrame[ArrayUtil.oversize(1+ord, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
+ System.arraycopy(stack, 0, next, 0, stack.length);
+ for(int stackOrd=stack.length;stackOrd<next.length;stackOrd++) {
+ next[stackOrd] = new OrdsIntersectTermsEnumFrame(this, stackOrd);
+ }
+ stack = next;
+ }
+ assert stack[ord].ord == ord;
+ return stack[ord];
+ }
+
+ private FST.Arc<Output> getArc(int ord) {
+ if (ord >= arcs.length) {
+ @SuppressWarnings({"rawtypes","unchecked"}) final FST.Arc<Output>[] next =
+ new FST.Arc[ArrayUtil.oversize(1+ord, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
+ System.arraycopy(arcs, 0, next, 0, arcs.length);
+ for(int arcOrd=arcs.length;arcOrd<next.length;arcOrd++) {
+ next[arcOrd] = new FST.Arc<>();
+ }
+ arcs = next;
+ }
+ return arcs[ord];
+ }
+
+ private OrdsIntersectTermsEnumFrame pushFrame(int state) throws IOException {
+ final OrdsIntersectTermsEnumFrame f = getFrame(currentFrame == null ? 0 : 1+currentFrame.ord);
+
+ f.fp = f.fpOrig = currentFrame.lastSubFP;
+ f.prefix = currentFrame.prefix + currentFrame.suffix;
+ // if (DEBUG) System.out.println(" pushFrame state=" + state + " prefix=" + f.prefix);
+ f.setState(state);
+
+ // Walk the arc through the index -- we only
+ // "bother" with this so we can get the floor data
+ // from the index and skip floor blocks when
+ // possible:
+ FST.Arc<Output> arc = currentFrame.arc;
+ int idx = currentFrame.prefix;
+ assert currentFrame.suffix > 0;
+ Output output = currentFrame.outputPrefix;
+ while (idx < f.prefix) {
+ final int target = term.bytes[idx] & 0xff;
+ // TODO: we could be more efficient for the next()
+ // case by using current arc as starting point,
+ // passed to findTargetArc
+ arc = fr.index.findTargetArc(target, arc, getArc(1+idx), fstReader);
+ assert arc != null;
+ output = OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.output);
+ idx++;
+ }
+
+ f.arc = arc;
+ f.outputPrefix = output;
+ assert arc.isFinal();
+ f.load(OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.nextFinalOutput));
+ return f;
+ }
+
+ @Override
+ public BytesRef term() {
+ return term;
+ }
+
+ // TODO: do we need ord() here? OrdsIntersectTermsEnumFrame tracks termOrd but it may be buggy!
+
+ @Override
+ public int docFreq() throws IOException {
+ //if (DEBUG) System.out.println("BTIR.docFreq");
+ currentFrame.decodeMetaData();
+ //if (DEBUG) System.out.println(" return " + currentFrame.termState.docFreq);
+ return currentFrame.termState.docFreq;
+ }
+
+ @Override
+ public long totalTermFreq() throws IOException {
+ currentFrame.decodeMetaData();
+ return currentFrame.termState.totalTermFreq;
+ }
+
+ @Override
+ public DocsEnum docs(Bits skipDocs, DocsEnum reuse, int flags) throws IOException {
+ currentFrame.decodeMetaData();
+ return fr.parent.postingsReader.docs(fr.fieldInfo, currentFrame.termState, skipDocs, reuse, flags);
+ }
+
+ @Override
+ public DocsAndPositionsEnum docsAndPositions(Bits skipDocs, DocsAndPositionsEnum reuse, int flags) throws IOException {
+ if (fr.fieldInfo.getIndexOptions().compareTo(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS) < 0) {
+ // Positions were not indexed:
+ return null;
+ }
+
+ currentFrame.decodeMetaData();
+ return fr.parent.postingsReader.docsAndPositions(fr.fieldInfo, currentFrame.termState, skipDocs, reuse, flags);
+ }
+
+ private int getState() {
+ int state = currentFrame.state;
+ for(int idx=0;idx<currentFrame.suffix;idx++) {
+ state = runAutomaton.step(state, currentFrame.suffixBytes[currentFrame.startBytePos+idx] & 0xff);
+ assert state != -1;
+ }
+ return state;
+ }
+
+ // NOTE: specialized to only doing the first-time
+ // seek, but we could generalize it to allow
+ // arbitrary seekExact/Ceil. Note that this is a
+ // seekFloor!
+ private void seekToStartTerm(BytesRef target) throws IOException {
+ //if (DEBUG) System.out.println("seek to startTerm=" + target.utf8ToString());
+ assert currentFrame.ord == 0;
+ if (term.length < target.length) {
+ term.bytes = ArrayUtil.grow(term.bytes, target.length);
+ }
+ FST.Arc<Output> arc = arcs[0];
+ assert arc == currentFrame.arc;
+
+ for(int idx=0;idx<=target.length;idx++) {
+
+ while (true) {
+ final int savePos = currentFrame.suffixesReader.getPosition();
+ final int saveStartBytePos = currentFrame.startBytePos;
+ final int saveSuffix = currentFrame.suffix;
+ final long saveLastSubFP = currentFrame.lastSubFP;
+ final int saveTermBlockOrd = currentFrame.termState.termBlockOrd;
+
+ final boolean isSubBlock = currentFrame.next();
+
+ //if (DEBUG) System.out.println(" cycle ent=" + currentFrame.nextEnt + " (of " + currentFrame.entCount + ") prefix=" + currentFrame.prefix + " suffix=" + currentFrame.suffix + " isBlock=" + isSubBlock + " firstLabel=" + (currentFrame.suffix == 0 ? "" : (currentFrame.suffixBytes[currentFrame.startBytePos])&0xff));
+ term.length = currentFrame.prefix + currentFrame.suffix;
+ if (term.bytes.length < term.length) {
+ term.bytes = ArrayUtil.grow(term.bytes, term.length);
+ }
+ System.arraycopy(currentFrame.suffixBytes, currentFrame.startBytePos, term.bytes, currentFrame.prefix, currentFrame.suffix);
+
+ if (isSubBlock && StringHelper.startsWith(target, term)) {
+ // Recurse
+ //if (DEBUG) System.out.println(" recurse!");
+ currentFrame = pushFrame(getState());
+ break;
+ } else {
+ final int cmp = term.compareTo(target);
+ if (cmp < 0) {
+ if (currentFrame.nextEnt == currentFrame.entCount) {
+ if (!currentFrame.isLastInFloor) {
+ //if (DEBUG) System.out.println(" load floorBlock");
+ currentFrame.loadNextFloorBlock();
+ continue;
+ } else {
+ //if (DEBUG) System.out.println(" return term=" + brToString(term));
+ return;
+ }
+ }
+ continue;
+ } else if (cmp == 0) {
+ //if (DEBUG) System.out.println(" return term=" + brToString(term));
+ return;
+ } else {
+ // Fallback to prior entry: the semantics of
+ // this method is that the first call to
+ // next() will return the term after the
+ // requested term
+ currentFrame.nextEnt--;
+ currentFrame.lastSubFP = saveLastSubFP;
+ currentFrame.startBytePos = saveStartBytePos;
+ currentFrame.suffix = saveSuffix;
+ currentFrame.suffixesReader.setPosition(savePos);
+ currentFrame.termState.termBlockOrd = saveTermBlockOrd;
+ System.arraycopy(currentFrame.suffixBytes, currentFrame.startBytePos, term.bytes, currentFrame.prefix, currentFrame.suffix);
+ term.length = currentFrame.prefix + currentFrame.suffix;
+ // If the last entry was a block we don't
+ // need to bother recursing and pushing to
+ // the last term under it because the first
+ // next() will simply skip the frame anyway
+ return;
+ }
+ }
+ }
+ }
+
+ assert false;
+ }
+
+ @Override
+ public BytesRef next() throws IOException {
+
+ // if (DEBUG) {
+ // System.out.println("\nintEnum.next seg=" + segment);
+ // System.out.println(" frame ord=" + currentFrame.ord + " prefix=" + brToString(new BytesRef(term.bytes, term.offset, currentFrame.prefix)) + " state=" + currentFrame.state + " lastInFloor?=" + currentFrame.isLastInFloor + " fp=" + currentFrame.fp + " trans=" + (currentFrame.transitions.length == 0 ? "n/a" : currentFrame.transitions[currentFrame.transitionIndex]) + " outputPrefix=" + currentFrame.outputPrefix);
+ // }
+
+ nextTerm:
+ while(true) {
+ // Pop finished frames
+ while (currentFrame.nextEnt == currentFrame.entCount) {
+ if (!currentFrame.isLastInFloor) {
+ //if (DEBUG) System.out.println(" next-floor-block");
+ currentFrame.loadNextFloorBlock();
+ //if (DEBUG) System.out.println("\n frame ord=" + currentFrame.ord + " prefix=" + brToString(new BytesRef(term.bytes, term.offset, currentFrame.prefix)) + " state=" + currentFrame.state + " lastInFloor?=" + currentFrame.isLastInFloor + " fp=" + currentFrame.fp + " trans=" + (currentFrame.transitions.length == 0 ? "n/a" : currentFrame.transitions[currentFrame.transitionIndex]) + " outputPrefix=" + currentFrame.outputPrefix);
+ } else {
+ //if (DEBUG) System.out.println(" pop frame");
+ if (currentFrame.ord == 0) {
+ return null;
+ }
+ final long lastFP = currentFrame.fpOrig;
+ currentFrame = stack[currentFrame.ord-1];
+ assert currentFrame.lastSubFP == lastFP;
+ //if (DEBUG) System.out.println("\n frame ord=" + currentFrame.ord + " prefix=" + brToString(new BytesRef(term.bytes, term.offset, currentFrame.prefix)) + " state=" + currentFrame.state + " lastInFloor?=" + currentFrame.isLastInFloor + " fp=" + currentFrame.fp + " trans=" + (currentFrame.transitions.length == 0 ? "n/a" : currentFrame.transitions[currentFrame.transitionIndex]) + " outputPrefix=" + currentFrame.outputPrefix);
+ }
+ }
+
+ final boolean isSubBlock = currentFrame.next();
+ // if (DEBUG) {
+ // final BytesRef suffixRef = new BytesRef();
+ // suffixRef.bytes = currentFrame.suffixBytes;
+ // suffixRef.offset = currentFrame.startBytePos;
+ // suffixRef.length = currentFrame.suffix;
+ // System.out.println(" " + (isSubBlock ? "sub-block" : "term") + " " + currentFrame.nextEnt + " (of " + currentFrame.entCount + ") suffix=" + brToString(suffixRef));
+ // }
+
+ if (currentFrame.suffix != 0) {
+ final int label = currentFrame.suffixBytes[currentFrame.startBytePos] & 0xff;
+ while (label > currentFrame.curTransitionMax) {
+ if (currentFrame.transitionIndex >= currentFrame.transitionCount-1) {
+ // Stop processing this frame -- no further
+ // matches are possible because we've moved
+ // beyond what the max transition will allow
+ //if (DEBUG) System.out.println(" break: trans=" + (currentFrame.transitions.length == 0 ? "n/a" : currentFrame.transitions[currentFrame.transitionIndex]));
+
+ // sneaky! forces a pop above
+ currentFrame.isLastInFloor = true;
+ currentFrame.nextEnt = currentFrame.entCount;
+ continue nextTerm;
+ }
+ currentFrame.transitionIndex++;
+ compiledAutomaton.automaton.getNextTransition(currentFrame.transition);
+ currentFrame.curTransitionMax = currentFrame.transition.max;
+ //if (DEBUG) System.out.println(" next trans=" + currentFrame.transitions[currentFrame.transitionIndex]);
+ }
+ }
+
+ // First test the common suffix, if set:
+ if (compiledAutomaton.commonSuffixRef != null && !isSubBlock) {
+ final int termLen = currentFrame.prefix + currentFrame.suffix;
+ if (termLen < compiledAutomaton.commonSuffixRef.length) {
+ // No match
+ // if (DEBUG) {
+ // System.out.println(" skip: common suffix length");
+ // }
+ continue nextTerm;
+ }
+
+ final byte[] suffixBytes = currentFrame.suffixBytes;
+ final byte[] commonSuffixBytes = compiledAutomaton.commonSuffixRef.bytes;
+
+ final int lenInPrefix = compiledAutomaton.commonSuffixRef.length - currentFrame.suffix;
+ assert compiledAutomaton.commonSuffixRef.offset == 0;
+ int suffixBytesPos;
+ int commonSuffixBytesPos = 0;
+
+ if (lenInPrefix > 0) {
+ // A prefix of the common suffix overlaps with
+ // the suffix of the block prefix so we first
+ // test whether the prefix part matches:
+ final byte[] termBytes = term.bytes;
+ int termBytesPos = currentFrame.prefix - lenInPrefix;
+ assert termBytesPos >= 0;
+ final int termBytesPosEnd = currentFrame.prefix;
+ while (termBytesPos < termBytesPosEnd) {
+ if (termBytes[termBytesPos++] != commonSuffixBytes[commonSuffixBytesPos++]) {
+ // if (DEBUG) {
+ // System.out.println(" skip: common suffix mismatch (in prefix)");
+ // }
+ continue nextTerm;
+ }
+ }
+ suffixBytesPos = currentFrame.startBytePos;
+ } else {
+ suffixBytesPos = currentFrame.startBytePos + currentFrame.suffix - compiledAutomaton.commonSuffixRef.length;
+ }
+
+ // Test overlapping suffix part:
+ final int commonSuffixBytesPosEnd = compiledAutomaton.commonSuffixRef.length;
+ while (commonSuffixBytesPos < commonSuffixBytesPosEnd) {
+ if (suffixBytes[suffixBytesPos++] != commonSuffixBytes[commonSuffixBytesPos++]) {
+ // if (DEBUG) {
+ // System.out.println(" skip: common suffix mismatch");
+ // }
+ continue nextTerm;
+ }
+ }
+ }
+
+ // TODO: maybe we should do the same linear test
+ // that AutomatonTermsEnum does, so that if we
+ // reach a part of the automaton where .* is
+ // "temporarily" accepted, we just blindly .next()
+ // until the limit
+
+ // See if the term prefix matches the automaton:
+ int state = currentFrame.state;
+ for (int idx=0;idx<currentFrame.suffix;idx++) {
+ state = runAutomaton.step(state, currentFrame.suffixBytes[currentFrame.startBytePos+idx] & 0xff);
+ if (state == -1) {
+ // No match
+ //System.out.println(" no s=" + state);
+ continue nextTerm;
+ } else {
+ //System.out.println(" c s=" + state);
+ }
+ }
+
+ if (isSubBlock) {
+ // Match! Recurse:
+ //if (DEBUG) System.out.println(" sub-block match to state=" + state + "; recurse fp=" + currentFrame.lastSubFP);
+ copyTerm();
+ currentFrame = pushFrame(state);
+ //if (DEBUG) System.out.println("\n frame ord=" + currentFrame.ord + " prefix=" + brToString(new BytesRef(term.bytes, term.offset, currentFrame.prefix)) + " state=" + currentFrame.state + " lastInFloor?=" + currentFrame.isLastInFloor + " fp=" + currentFrame.fp + " trans=" + (currentFrame.transitions.length == 0 ? "n/a" : currentFrame.transitions[currentFrame.transitionIndex]) + " outputPrefix=" + currentFrame.outputPrefix);
+ } else if (runAutomaton.isAccept(state)) {
+ copyTerm();
+ //if (DEBUG) System.out.println(" term match to state=" + state + "; return term=" + brToString(term));
+ assert savedStartTerm == null || term.compareTo(savedStartTerm) > 0: "saveStartTerm=" + savedStartTerm.utf8ToString() + " term=" + term.utf8ToString();
+ return term;
+ } else {
+ //System.out.println(" no s=" + state);
+ }
+ }
+ }
+
+ private void copyTerm() {
+ //System.out.println(" copyTerm cur.prefix=" + currentFrame.prefix + " cur.suffix=" + currentFrame.suffix + " first=" + (char) currentFrame.suffixBytes[currentFrame.startBytePos]);
+ final int len = currentFrame.prefix + currentFrame.suffix;
+ if (term.bytes.length < len) {
+ term.bytes = ArrayUtil.grow(term.bytes, len);
+ }
+ System.arraycopy(currentFrame.suffixBytes, currentFrame.startBytePos, term.bytes, currentFrame.prefix, currentFrame.suffix);
+ term.length = len;
+ }
+
+ @Override
+ public boolean seekExact(BytesRef text) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void seekExact(long ord) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public long ord() {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public SeekStatus seekCeil(BytesRef text) {
+ throw new UnsupportedOperationException();
+ }
+}
Added: lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsIntersectTermsEnumFrame.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsIntersectTermsEnumFrame.java?rev=1612080&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsIntersectTermsEnumFrame.java (added)
+++ lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsIntersectTermsEnumFrame.java Sun Jul 20 12:08:32 2014
@@ -0,0 +1,310 @@
+package org.apache.lucene.codecs.blocktreeords;
+
+/*
+ * 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.
+ */
+
+import java.io.IOException;
+
+import org.apache.lucene.codecs.BlockTermState;
+import org.apache.lucene.codecs.blocktreeords.FSTOrdsOutputs.Output;
+import org.apache.lucene.index.FieldInfo.IndexOptions;
+import org.apache.lucene.store.ByteArrayDataInput;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.automaton.Transition;
+import org.apache.lucene.util.fst.FST;
+
+// TODO: can we share this with the frame in STE?
+final class OrdsIntersectTermsEnumFrame {
+ final int ord;
+ long fp;
+ long fpOrig;
+ long fpEnd;
+ long lastSubFP;
+
+ // State in automaton
+ int state;
+
+ int metaDataUpto;
+
+ byte[] suffixBytes = new byte[128];
+ final ByteArrayDataInput suffixesReader = new ByteArrayDataInput();
+
+ byte[] statBytes = new byte[64];
+ final ByteArrayDataInput statsReader = new ByteArrayDataInput();
+
+ byte[] floorData = new byte[32];
+ final ByteArrayDataInput floorDataReader = new ByteArrayDataInput();
+
+ // Length of prefix shared by all terms in this block
+ int prefix;
+
+ // Number of entries (term or sub-block) in this block
+ int entCount;
+
+ // Which term we will next read
+ int nextEnt;
+
+ // Starting termOrd for this frame, used to reset termOrd in rewind()
+ long termOrdOrig;
+
+ // 1 + ordinal of the current term
+ long termOrd;
+
+ // True if this block is either not a floor block,
+ // or, it's the last sub-block of a floor block
+ boolean isLastInFloor;
+
+ // True if all entries are terms
+ boolean isLeafBlock;
+
+ int numFollowFloorBlocks;
+ int nextFloorLabel;
+
+ Transition transition = new Transition();
+ int curTransitionMax;
+ int transitionIndex;
+ int transitionCount;
+
+ FST.Arc<Output> arc;
+
+ final BlockTermState termState;
+
+ // metadata buffer, holding monotonic values
+ public long[] longs;
+ // metadata buffer, holding general values
+ public byte[] bytes;
+ ByteArrayDataInput bytesReader;
+
+ // Cumulative output so far
+ Output outputPrefix;
+
+ int startBytePos;
+ int suffix;
+
+ private final OrdsIntersectTermsEnum ite;
+
+ public OrdsIntersectTermsEnumFrame(OrdsIntersectTermsEnum ite, int ord) throws IOException {
+ this.ite = ite;
+ this.ord = ord;
+ this.termState = ite.fr.parent.postingsReader.newTermState();
+ this.termState.totalTermFreq = -1;
+ this.longs = new long[ite.fr.longsSize];
+ }
+
+ void loadNextFloorBlock() throws IOException {
+ assert numFollowFloorBlocks > 0;
+ //if (DEBUG) System.out.println(" loadNextFoorBlock trans=" + transitions[transitionIndex]);
+
+ do {
+ fp = fpOrig + (floorDataReader.readVLong() >>> 1);
+ numFollowFloorBlocks--;
+ // if (DEBUG) System.out.println(" skip floor block2! nextFloorLabel=" + (char) nextFloorLabel + " vs target=" + (char) transitions[transitionIndex].getMin() + " newFP=" + fp + " numFollowFloorBlocks=" + numFollowFloorBlocks);
+ if (numFollowFloorBlocks != 0) {
+ nextFloorLabel = floorDataReader.readByte() & 0xff;
+ termOrd += floorDataReader.readVLong();
+ } else {
+ nextFloorLabel = 256;
+ }
+ // if (DEBUG) System.out.println(" nextFloorLabel=" + (char) nextFloorLabel);
+ } while (numFollowFloorBlocks != 0 && nextFloorLabel <= transition.min);
+
+ load(null);
+ }
+
+ public void setState(int state) {
+ this.state = state;
+ transitionIndex = 0;
+ transitionCount = ite.compiledAutomaton.automaton.getNumTransitions(state);
+ if (transitionCount != 0) {
+ ite.compiledAutomaton.automaton.initTransition(state, transition);
+ ite.compiledAutomaton.automaton.getNextTransition(transition);
+ curTransitionMax = transition.max;
+ } else {
+ curTransitionMax = -1;
+ }
+ }
+
+ void load(Output output) throws IOException {
+
+ // if (DEBUG) System.out.println(" load fp=" + fp + " fpOrig=" + fpOrig + " frameIndexData=" + frameIndexData + " trans=" + (transitions.length != 0 ? transitions[0] : "n/a" + " state=" + state));
+
+ if (output != null && output.bytes != null && transitionCount != 0) {
+ BytesRef frameIndexData = output.bytes;
+
+ // Floor frame
+ if (floorData.length < frameIndexData.length) {
+ this.floorData = new byte[ArrayUtil.oversize(frameIndexData.length, 1)];
+ }
+ System.arraycopy(frameIndexData.bytes, frameIndexData.offset, floorData, 0, frameIndexData.length);
+ floorDataReader.reset(floorData, 0, frameIndexData.length);
+ final long code = floorDataReader.readVLong();
+ if ((code & OrdsBlockTreeTermsWriter.OUTPUT_FLAG_IS_FLOOR) != 0) {
+ numFollowFloorBlocks = floorDataReader.readVInt();
+ nextFloorLabel = floorDataReader.readByte() & 0xff;
+
+ termOrd = termOrdOrig + floorDataReader.readVLong();
+
+ // if (DEBUG) System.out.println(" numFollowFloorBlocks=" + numFollowFloorBlocks + " nextFloorLabel=" + nextFloorLabel);
+
+ // If current state is accept, we must process
+ // first block in case it has empty suffix:
+ if (!ite.runAutomaton.isAccept(state)) {
+ // Maybe skip floor blocks:
+ assert transitionIndex == 0: "transitionIndex=" + transitionIndex;
+ while (numFollowFloorBlocks != 0 && nextFloorLabel <= transition.min) {
+ fp = fpOrig + (floorDataReader.readVLong() >>> 1);
+ numFollowFloorBlocks--;
+ // if (DEBUG) System.out.println(" skip floor block! nextFloorLabel=" + (char) nextFloorLabel + " vs target=" + (char) transitions[0].getMin() + " newFP=" + fp + " numFollowFloorBlocks=" + numFollowFloorBlocks);
+ if (numFollowFloorBlocks != 0) {
+ nextFloorLabel = floorDataReader.readByte() & 0xff;
+ termOrd += floorDataReader.readVLong();
+ } else {
+ nextFloorLabel = 256;
+ }
+ }
+ }
+ }
+ }
+
+ ite.in.seek(fp);
+ int code = ite.in.readVInt();
+ entCount = code >>> 1;
+ assert entCount > 0;
+ isLastInFloor = (code & 1) != 0;
+
+ // term suffixes:
+ code = ite.in.readVInt();
+ isLeafBlock = (code & 1) != 0;
+ int numBytes = code >>> 1;
+ // if (DEBUG) System.out.println(" entCount=" + entCount + " lastInFloor?=" + isLastInFloor + " leafBlock?=" + isLeafBlock + " numSuffixBytes=" + numBytes);
+ if (suffixBytes.length < numBytes) {
+ suffixBytes = new byte[ArrayUtil.oversize(numBytes, 1)];
+ }
+ ite.in.readBytes(suffixBytes, 0, numBytes);
+ suffixesReader.reset(suffixBytes, 0, numBytes);
+
+ // stats
+ numBytes = ite.in.readVInt();
+ if (statBytes.length < numBytes) {
+ statBytes = new byte[ArrayUtil.oversize(numBytes, 1)];
+ }
+ ite.in.readBytes(statBytes, 0, numBytes);
+ statsReader.reset(statBytes, 0, numBytes);
+ metaDataUpto = 0;
+
+ termState.termBlockOrd = 0;
+ nextEnt = 0;
+
+ // metadata
+ numBytes = ite.in.readVInt();
+ if (bytes == null) {
+ bytes = new byte[ArrayUtil.oversize(numBytes, 1)];
+ bytesReader = new ByteArrayDataInput();
+ } else if (bytes.length < numBytes) {
+ bytes = new byte[ArrayUtil.oversize(numBytes, 1)];
+ }
+ ite.in.readBytes(bytes, 0, numBytes);
+ bytesReader.reset(bytes, 0, numBytes);
+
+ if (!isLastInFloor) {
+ // Sub-blocks of a single floor block are always
+ // written one after another -- tail recurse:
+ fpEnd = ite.in.getFilePointer();
+ }
+ }
+
+ // TODO: maybe add scanToLabel; should give perf boost
+
+ public boolean next() {
+ return isLeafBlock ? nextLeaf() : nextNonLeaf();
+ }
+
+ // Decodes next entry; returns true if it's a sub-block
+ public boolean nextLeaf() {
+ //if (DEBUG) System.out.println(" frame.next ord=" + ord + " nextEnt=" + nextEnt + " entCount=" + entCount);
+ assert nextEnt != -1 && nextEnt < entCount: "nextEnt=" + nextEnt + " entCount=" + entCount + " fp=" + fp;
+ nextEnt++;
+ suffix = suffixesReader.readVInt();
+ startBytePos = suffixesReader.getPosition();
+ suffixesReader.skipBytes(suffix);
+ return false;
+ }
+
+ public boolean nextNonLeaf() {
+ //if (DEBUG) System.out.println(" frame.next ord=" + ord + " nextEnt=" + nextEnt + " entCount=" + entCount);
+ assert nextEnt != -1 && nextEnt < entCount: "nextEnt=" + nextEnt + " entCount=" + entCount + " fp=" + fp;
+ nextEnt++;
+ final int code = suffixesReader.readVInt();
+ suffix = code >>> 1;
+ startBytePos = suffixesReader.getPosition();
+ suffixesReader.skipBytes(suffix);
+ if ((code & 1) == 0) {
+ // A normal term
+ termState.termBlockOrd++;
+ return false;
+ } else {
+ // A sub-block; make sub-FP absolute:
+ lastSubFP = fp - suffixesReader.readVLong();
+ // Skip term ord
+ suffixesReader.readVLong();
+ return true;
+ }
+ }
+
+ public int getTermBlockOrd() {
+ return isLeafBlock ? nextEnt : termState.termBlockOrd;
+ }
+
+ public void decodeMetaData() throws IOException {
+
+ // lazily catch up on metadata decode:
+ final int limit = getTermBlockOrd();
+ boolean absolute = metaDataUpto == 0;
+ assert limit > 0;
+
+ // TODO: better API would be "jump straight to term=N"???
+ while (metaDataUpto < limit) {
+
+ // TODO: we could make "tiers" of metadata, ie,
+ // decode docFreq/totalTF but don't decode postings
+ // metadata; this way caller could get
+ // docFreq/totalTF w/o paying decode cost for
+ // postings
+
+ // TODO: if docFreq were bulk decoded we could
+ // just skipN here:
+
+ // stats
+ termState.docFreq = statsReader.readVInt();
+ //if (DEBUG) System.out.println(" dF=" + state.docFreq);
+ if (ite.fr.fieldInfo.getIndexOptions() != IndexOptions.DOCS_ONLY) {
+ termState.totalTermFreq = termState.docFreq + statsReader.readVLong();
+ //if (DEBUG) System.out.println(" totTF=" + state.totalTermFreq);
+ }
+ // metadata
+ for (int i = 0; i < ite.fr.longsSize; i++) {
+ longs[i] = bytesReader.readVLong();
+ }
+ ite.fr.parent.postingsReader.decodeTerm(longs, bytesReader, ite.fr.fieldInfo, termState, absolute);
+
+ metaDataUpto++;
+ absolute = false;
+ }
+ termState.termBlockOrd = metaDataUpto;
+ }
+}
Added: lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java?rev=1612080&view=auto
==============================================================================
--- lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java (added)
+++ lucene/dev/trunk/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java Sun Jul 20 12:08:32 2014
@@ -0,0 +1,1186 @@
+package org.apache.lucene.codecs.blocktreeords;
+
+/*
+ * 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.
+ */
+
+//import java.io.*;
+//import java.nio.charset.StandardCharsets;
+
+import java.io.IOException;
+import java.io.PrintStream;
+
+import org.apache.lucene.codecs.BlockTermState;
+import org.apache.lucene.codecs.blocktreeords.FSTOrdsOutputs.Output;
+import org.apache.lucene.index.DocsAndPositionsEnum;
+import org.apache.lucene.index.DocsEnum;
+import org.apache.lucene.index.FieldInfo.IndexOptions;
+import org.apache.lucene.index.TermState;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.store.ByteArrayDataInput;
+import org.apache.lucene.store.IndexInput;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.IntsRef;
+import org.apache.lucene.util.RamUsageEstimator;
+import org.apache.lucene.util.fst.FST;
+import org.apache.lucene.util.fst.Util;
+
+/** Iterates through terms in this field. */
+public final class OrdsSegmentTermsEnum extends TermsEnum {
+
+ // Lazy init:
+ IndexInput in;
+
+ // static boolean DEBUG = true;
+
+ private OrdsSegmentTermsEnumFrame[] stack;
+ private final OrdsSegmentTermsEnumFrame staticFrame;
+ OrdsSegmentTermsEnumFrame currentFrame;
+ boolean termExists;
+ final OrdsFieldReader fr;
+
+ private int targetBeforeCurrentLength;
+
+ private final ByteArrayDataInput scratchReader = new ByteArrayDataInput();
+
+ // What prefix of the current term was present in the index:
+ private int validIndexPrefix;
+
+ // assert only:
+ private boolean eof;
+
+ final BytesRef term = new BytesRef();
+ private final FST.BytesReader fstReader;
+
+ @SuppressWarnings({"rawtypes","unchecked"}) private FST.Arc<Output>[] arcs =
+ new FST.Arc[1];
+
+ boolean positioned;
+
+ OrdsSegmentTermsEnum(OrdsFieldReader fr) throws IOException {
+ this.fr = fr;
+
+ //if (DEBUG) System.out.println("BTTR.init seg=" + segment);
+ stack = new OrdsSegmentTermsEnumFrame[0];
+
+ // Used to hold seek by TermState, or cached seek
+ staticFrame = new OrdsSegmentTermsEnumFrame(this, -1);
+
+ if (fr.index == null) {
+ fstReader = null;
+ } else {
+ fstReader = fr.index.getBytesReader();
+ }
+
+ // Init w/ root block; don't use index since it may
+ // not (and need not) have been loaded
+ for(int arcIdx=0;arcIdx<arcs.length;arcIdx++) {
+ arcs[arcIdx] = new FST.Arc<>();
+ }
+
+ currentFrame = staticFrame;
+ final FST.Arc<Output> arc;
+ if (fr.index != null) {
+ arc = fr.index.getFirstArc(arcs[0]);
+ // Empty string prefix must have an output in the index!
+ assert arc.isFinal();
+ } else {
+ arc = null;
+ }
+ //currentFrame = pushFrame(arc, rootCode, 0);
+ //currentFrame.loadBlock();
+ validIndexPrefix = 0;
+ // if (DEBUG) {
+ // System.out.println("init frame state " + currentFrame.ord);
+ // printSeekState();
+ // }
+
+ //System.out.println();
+ // computeBlockStats().print(System.out);
+ }
+
+ // Not private to avoid synthetic access$NNN methods
+ void initIndexInput() {
+ if (this.in == null) {
+ this.in = fr.parent.in.clone();
+ }
+ }
+
+ private OrdsSegmentTermsEnumFrame getFrame(int ord) throws IOException {
+ if (ord >= stack.length) {
+ final OrdsSegmentTermsEnumFrame[] next = new OrdsSegmentTermsEnumFrame[ArrayUtil.oversize(1+ord, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
+ System.arraycopy(stack, 0, next, 0, stack.length);
+ for(int stackOrd=stack.length;stackOrd<next.length;stackOrd++) {
+ next[stackOrd] = new OrdsSegmentTermsEnumFrame(this, stackOrd);
+ }
+ stack = next;
+ }
+ assert stack[ord].ord == ord;
+ return stack[ord];
+ }
+
+ private FST.Arc<Output> getArc(int ord) {
+ if (ord >= arcs.length) {
+ @SuppressWarnings({"rawtypes","unchecked"}) final FST.Arc<Output>[] next =
+ new FST.Arc[ArrayUtil.oversize(1+ord, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
+ System.arraycopy(arcs, 0, next, 0, arcs.length);
+ for(int arcOrd=arcs.length;arcOrd<next.length;arcOrd++) {
+ next[arcOrd] = new FST.Arc<>();
+ }
+ arcs = next;
+ }
+ return arcs[ord];
+ }
+
+ // Pushes a frame we seek'd to
+ OrdsSegmentTermsEnumFrame pushFrame(FST.Arc<Output> arc, Output frameData, int length) throws IOException {
+ scratchReader.reset(frameData.bytes.bytes, frameData.bytes.offset, frameData.bytes.length);
+ final long code = scratchReader.readVLong();
+ final long fpSeek = code >>> OrdsBlockTreeTermsWriter.OUTPUT_FLAGS_NUM_BITS;
+ // System.out.println(" fpSeek=" + fpSeek);
+ final OrdsSegmentTermsEnumFrame f = getFrame(1+currentFrame.ord);
+ f.hasTerms = (code & OrdsBlockTreeTermsWriter.OUTPUT_FLAG_HAS_TERMS) != 0;
+ f.hasTermsOrig = f.hasTerms;
+ f.isFloor = (code & OrdsBlockTreeTermsWriter.OUTPUT_FLAG_IS_FLOOR) != 0;
+
+ // Must setFloorData before pushFrame in case pushFrame tries to rewind:
+ if (f.isFloor) {
+ f.termOrdOrig = frameData.startOrd;
+ f.setFloorData(scratchReader, frameData.bytes);
+ }
+
+ pushFrame(arc, fpSeek, length, frameData.startOrd);
+
+ return f;
+ }
+
+ // Pushes next'd frame or seek'd frame; we later
+ // lazy-load the frame only when needed
+ OrdsSegmentTermsEnumFrame pushFrame(FST.Arc<Output> arc, long fp, int length, long termOrd) throws IOException {
+ final OrdsSegmentTermsEnumFrame f = getFrame(1+currentFrame.ord);
+ f.arc = arc;
+ // System.out.println("pushFrame termOrd= " + termOrd + " fpOrig=" + f.fpOrig + " fp=" + fp + " nextEnt=" + f.nextEnt);
+ if (f.fpOrig == fp && f.nextEnt != -1) {
+ //if (DEBUG) System.out.println(" push reused frame ord=" + f.ord + " fp=" + f.fp + " isFloor?=" + f.isFloor + " hasTerms=" + f.hasTerms + " pref=" + term + " nextEnt=" + f.nextEnt + " targetBeforeCurrentLength=" + targetBeforeCurrentLength + " term.length=" + term.length + " vs prefix=" + f.prefix);
+ if (f.prefix > targetBeforeCurrentLength) {
+ // System.out.println(" do rewind!");
+ f.rewind();
+ } else {
+ // if (DEBUG) {
+ // System.out.println(" skip rewind!");
+ // }
+ }
+ assert length == f.prefix;
+ } else {
+ f.nextEnt = -1;
+ f.prefix = length;
+ f.state.termBlockOrd = 0;
+ f.termOrdOrig = termOrd;
+ // System.out.println("set termOrdOrig=" + termOrd);
+ f.termOrd = termOrd;
+ f.fpOrig = f.fp = fp;
+ f.lastSubFP = -1;
+ // if (DEBUG) {
+ // final int sav = term.length;
+ // term.length = length;
+ // System.out.println(" push new frame ord=" + f.ord + " fp=" + f.fp + " hasTerms=" + f.hasTerms + " isFloor=" + f.isFloor + " pref=" + brToString(term));
+ // term.length = sav;
+ // }
+ }
+
+ return f;
+ }
+
+ // asserts only
+ private boolean clearEOF() {
+ eof = false;
+ return true;
+ }
+
+ // asserts only
+ private boolean setEOF() {
+ eof = true;
+ return true;
+ }
+
+ // for debugging
+ @SuppressWarnings("unused")
+ static String brToString(BytesRef b) {
+ try {
+ return b.utf8ToString() + " " + b;
+ } catch (Throwable t) {
+ // If BytesRef isn't actually UTF8, or it's eg a
+ // prefix of UTF8 that ends mid-unicode-char, we
+ // fallback to hex:
+ return b.toString();
+ }
+ }
+
+ @Override
+ public boolean seekExact(final BytesRef target) throws IOException {
+
+ if (fr.index == null) {
+ throw new IllegalStateException("terms index was not loaded");
+ }
+
+ if (term.bytes.length <= target.length) {
+ term.bytes = ArrayUtil.grow(term.bytes, 1+target.length);
+ }
+
+ assert clearEOF();
+
+ /*
+ if (DEBUG) {
+ System.out.println("\nBTTR.seekExact seg=" + fr.parent.segment + " target=" + fr.fieldInfo.name + ":" + brToString(target) + " current=" + brToString(term) + " (exists?=" + termExists + ") validIndexPrefix=" + validIndexPrefix);
+ printSeekState(System.out);
+ }
+ */
+
+ FST.Arc<Output> arc;
+ int targetUpto;
+ Output output;
+
+ targetBeforeCurrentLength = currentFrame.ord;
+
+ if (positioned && currentFrame != staticFrame) {
+
+ // We are already seek'd; find the common
+ // prefix of new seek term vs current term and
+ // re-use the corresponding seek state. For
+ // example, if app first seeks to foobar, then
+ // seeks to foobaz, we can re-use the seek state
+ // for the first 5 bytes.
+
+ // if (DEBUG) {
+ // System.out.println(" re-use current seek state validIndexPrefix=" + validIndexPrefix);
+ // }
+
+ arc = arcs[0];
+ assert arc.isFinal();
+ output = arc.output;
+ targetUpto = 0;
+
+ OrdsSegmentTermsEnumFrame lastFrame = stack[0];
+ assert validIndexPrefix <= term.length;
+
+ final int targetLimit = Math.min(target.length, validIndexPrefix);
+
+ int cmp = 0;
+
+ // TODO: reverse vLong byte order for better FST
+ // prefix output sharing
+
+ // First compare up to valid seek frames:
+ while (targetUpto < targetLimit) {
+ cmp = (term.bytes[targetUpto]&0xFF) - (target.bytes[target.offset + targetUpto]&0xFF);
+ // if (DEBUG) {
+ // System.out.println(" cycle targetUpto=" + targetUpto + " (vs limit=" + targetLimit + ") cmp=" + cmp + " (targetLabel=" + (char) (target.bytes[target.offset + targetUpto]) + " vs termLabel=" + (char) (term.bytes[targetUpto]) + ")" + " arc.output=" + arc.output + " output=" + output);
+ // }
+ if (cmp != 0) {
+ break;
+ }
+ arc = arcs[1+targetUpto];
+ assert arc.label == (target.bytes[target.offset + targetUpto] & 0xFF): "arc.label=" + (char) arc.label + " targetLabel=" + (char) (target.bytes[target.offset + targetUpto] & 0xFF);
+ if (arc.output != OrdsBlockTreeTermsWriter.NO_OUTPUT) {
+ output = OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.output);
+ }
+ if (arc.isFinal()) {
+ lastFrame = stack[1+lastFrame.ord];
+ }
+ targetUpto++;
+ }
+
+ if (cmp == 0) {
+ final int targetUptoMid = targetUpto;
+
+ // Second compare the rest of the term, but
+ // don't save arc/output/frame; we only do this
+ // to find out if the target term is before,
+ // equal or after the current term
+ final int targetLimit2 = Math.min(target.length, term.length);
+ while (targetUpto < targetLimit2) {
+ cmp = (term.bytes[targetUpto]&0xFF) - (target.bytes[target.offset + targetUpto]&0xFF);
+ // if (DEBUG) {
+ // System.out.println(" cycle2 targetUpto=" + targetUpto + " (vs limit=" + targetLimit + ") cmp=" + cmp + " (targetLabel=" + (char) (target.bytes[target.offset + targetUpto]) + " vs termLabel=" + (char) (term.bytes[targetUpto]) + ")");
+ // }
+ if (cmp != 0) {
+ break;
+ }
+ targetUpto++;
+ }
+
+ if (cmp == 0) {
+ cmp = term.length - target.length;
+ }
+ targetUpto = targetUptoMid;
+ }
+
+ if (cmp < 0) {
+ // Common case: target term is after current
+ // term, ie, app is seeking multiple terms
+ // in sorted order
+ // if (DEBUG) {
+ // System.out.println(" target is after current (shares prefixLen=" + targetUpto + "); frame.ord=" + lastFrame.ord);
+ // }
+ currentFrame = lastFrame;
+
+ } else if (cmp > 0) {
+ // Uncommon case: target term
+ // is before current term; this means we can
+ // keep the currentFrame but we must rewind it
+ // (so we scan from the start)
+ targetBeforeCurrentLength = lastFrame.ord;
+ // if (DEBUG) {
+ // System.out.println(" target is before current (shares prefixLen=" + targetUpto + "); rewind frame ord=" + lastFrame.ord);
+ // }
+ currentFrame = lastFrame;
+ currentFrame.rewind();
+ } else {
+ // Target is exactly the same as current term
+ assert term.length == target.length;
+ if (termExists) {
+ // if (DEBUG) {
+ // System.out.println(" target is same as current; return true");
+ // }
+ return true;
+ } else {
+ // if (DEBUG) {
+ // System.out.println(" target is same as current but term doesn't exist");
+ // }
+ }
+ //validIndexPrefix = currentFrame.depth;
+ //term.length = target.length;
+ //return termExists;
+ }
+
+ } else {
+
+ targetBeforeCurrentLength = -1;
+ arc = fr.index.getFirstArc(arcs[0]);
+
+ // Empty string prefix must have an output (block) in the index!
+ assert arc.isFinal();
+ assert arc.output != null;
+
+ // if (DEBUG) {
+ // System.out.println(" no seek state; push root frame");
+ // }
+
+ output = arc.output;
+
+ currentFrame = staticFrame;
+
+ //term.length = 0;
+ targetUpto = 0;
+ currentFrame = pushFrame(arc, OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.nextFinalOutput), 0);
+ }
+
+ positioned = true;
+
+ // if (DEBUG) {
+ // System.out.println(" start index loop targetUpto=" + targetUpto + " output=" + output + " currentFrame.ord=" + currentFrame.ord + " targetBeforeCurrentLength=" + targetBeforeCurrentLength);
+ // }
+
+ // We are done sharing the common prefix with the incoming target and where we are currently seek'd; now continue walking the index:
+ while (targetUpto < target.length) {
+
+ final int targetLabel = target.bytes[target.offset + targetUpto] & 0xFF;
+
+ final FST.Arc<Output> nextArc = fr.index.findTargetArc(targetLabel, arc, getArc(1+targetUpto), fstReader);
+
+ if (nextArc == null) {
+
+ // Index is exhausted
+ // if (DEBUG) {
+ // System.out.println(" index: index exhausted label=" + ((char) targetLabel) + " " + toHex(targetLabel));
+ // }
+
+ validIndexPrefix = currentFrame.prefix;
+ //validIndexPrefix = targetUpto;
+
+ currentFrame.scanToFloorFrame(target);
+
+ if (!currentFrame.hasTerms) {
+ termExists = false;
+ term.bytes[targetUpto] = (byte) targetLabel;
+ term.length = 1+targetUpto;
+ // if (DEBUG) {
+ // System.out.println(" FAST NOT_FOUND term=" + brToString(term));
+ // }
+ return false;
+ }
+
+ currentFrame.loadBlock();
+
+ final SeekStatus result = currentFrame.scanToTerm(target, true);
+ if (result == SeekStatus.FOUND) {
+ // if (DEBUG) {
+ // System.out.println(" return FOUND term=" + term.utf8ToString() + " " + term);
+ // }
+ return true;
+ } else {
+ // if (DEBUG) {
+ // System.out.println(" got " + result + "; return NOT_FOUND term=" + brToString(term));
+ // }
+ return false;
+ }
+ } else {
+ // Follow this arc
+ arc = nextArc;
+ term.bytes[targetUpto] = (byte) targetLabel;
+ // Aggregate output as we go:
+ assert arc.output != null;
+ if (arc.output != OrdsBlockTreeTermsWriter.NO_OUTPUT) {
+ output = OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.output);
+ }
+
+ // if (DEBUG) {
+ // System.out.println(" index: follow label=" + toHex(target.bytes[target.offset + targetUpto]&0xff) + " arc.output=" + arc.output + " arc.nfo=" + arc.nextFinalOutput);
+ // }
+ targetUpto++;
+
+ if (arc.isFinal()) {
+ //if (DEBUG) System.out.println(" arc is final!");
+ currentFrame = pushFrame(arc, OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.nextFinalOutput), targetUpto);
+ //if (DEBUG) System.out.println(" curFrame.ord=" + currentFrame.ord + " hasTerms=" + currentFrame.hasTerms);
+ }
+ }
+ }
+
+ //validIndexPrefix = targetUpto;
+ validIndexPrefix = currentFrame.prefix;
+
+ currentFrame.scanToFloorFrame(target);
+
+ // Target term is entirely contained in the index:
+ if (!currentFrame.hasTerms) {
+ termExists = false;
+ term.length = targetUpto;
+ // if (DEBUG) {
+ // System.out.println(" FAST NOT_FOUND term=" + brToString(term));
+ // }
+ return false;
+ }
+
+ currentFrame.loadBlock();
+
+ final SeekStatus result = currentFrame.scanToTerm(target, true);
+ if (result == SeekStatus.FOUND) {
+ // if (DEBUG) {
+ // System.out.println(" return FOUND term=" + term.utf8ToString() + " " + term);
+ // }
+ return true;
+ } else {
+ // if (DEBUG) {
+ // System.out.println(" got result " + result + "; return NOT_FOUND term=" + term.utf8ToString());
+ // }
+
+ return false;
+ }
+ }
+
+ @Override
+ public SeekStatus seekCeil(final BytesRef target) throws IOException {
+ if (fr.index == null) {
+ throw new IllegalStateException("terms index was not loaded");
+ }
+
+ if (term.bytes.length <= target.length) {
+ term.bytes = ArrayUtil.grow(term.bytes, 1+target.length);
+ }
+
+ assert clearEOF();
+
+ //if (DEBUG) {
+ //System.out.println("\nBTTR.seekCeil seg=" + segment + " target=" + fieldInfo.name + ":" + target.utf8ToString() + " " + target + " current=" + brToString(term) + " (exists?=" + termExists + ") validIndexPrefix= " + validIndexPrefix);
+ //printSeekState();
+ //}
+
+ FST.Arc<Output> arc;
+ int targetUpto;
+ Output output;
+
+ targetBeforeCurrentLength = currentFrame.ord;
+
+ if (positioned && currentFrame != staticFrame) {
+
+ // We are already seek'd; find the common
+ // prefix of new seek term vs current term and
+ // re-use the corresponding seek state. For
+ // example, if app first seeks to foobar, then
+ // seeks to foobaz, we can re-use the seek state
+ // for the first 5 bytes.
+
+ //if (DEBUG) {
+ //System.out.println(" re-use current seek state validIndexPrefix=" + validIndexPrefix);
+ //}
+
+ arc = arcs[0];
+ assert arc.isFinal();
+ output = arc.output;
+ targetUpto = 0;
+
+ OrdsSegmentTermsEnumFrame lastFrame = stack[0];
+ assert validIndexPrefix <= term.length;
+
+ final int targetLimit = Math.min(target.length, validIndexPrefix);
+
+ int cmp = 0;
+
+ // TOOD: we should write our vLong backwards (MSB
+ // first) to get better sharing from the FST
+
+ // First compare up to valid seek frames:
+ while (targetUpto < targetLimit) {
+ cmp = (term.bytes[targetUpto]&0xFF) - (target.bytes[target.offset + targetUpto]&0xFF);
+ //if (DEBUG) {
+ //System.out.println(" cycle targetUpto=" + targetUpto + " (vs limit=" + targetLimit + ") cmp=" + cmp + " (targetLabel=" + (char) (target.bytes[target.offset + targetUpto]) + " vs termLabel=" + (char) (term.bytes[targetUpto]) + ")" + " arc.output=" + arc.output + " output=" + output);
+ //}
+ if (cmp != 0) {
+ break;
+ }
+ arc = arcs[1+targetUpto];
+ assert arc.label == (target.bytes[target.offset + targetUpto] & 0xFF): "arc.label=" + (char) arc.label + " targetLabel=" + (char) (target.bytes[target.offset + targetUpto] & 0xFF);
+ // TOOD: we could save the outputs in local
+ // byte[][] instead of making new objs ever
+ // seek; but, often the FST doesn't have any
+ // shared bytes (but this could change if we
+ // reverse vLong byte order)
+ if (arc.output != OrdsBlockTreeTermsWriter.NO_OUTPUT) {
+ output = OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.output);
+ }
+ if (arc.isFinal()) {
+ lastFrame = stack[1+lastFrame.ord];
+ }
+ targetUpto++;
+ }
+
+
+ if (cmp == 0) {
+ final int targetUptoMid = targetUpto;
+ // Second compare the rest of the term, but
+ // don't save arc/output/frame:
+ final int targetLimit2 = Math.min(target.length, term.length);
+ while (targetUpto < targetLimit2) {
+ cmp = (term.bytes[targetUpto]&0xFF) - (target.bytes[target.offset + targetUpto]&0xFF);
+ //if (DEBUG) {
+ //System.out.println(" cycle2 targetUpto=" + targetUpto + " (vs limit=" + targetLimit + ") cmp=" + cmp + " (targetLabel=" + (char) (target.bytes[target.offset + targetUpto]) + " vs termLabel=" + (char) (term.bytes[targetUpto]) + ")");
+ //}
+ if (cmp != 0) {
+ break;
+ }
+ targetUpto++;
+ }
+
+ if (cmp == 0) {
+ cmp = term.length - target.length;
+ }
+ targetUpto = targetUptoMid;
+ }
+
+ if (cmp < 0) {
+ // Common case: target term is after current
+ // term, ie, app is seeking multiple terms
+ // in sorted order
+ //if (DEBUG) {
+ //System.out.println(" target is after current (shares prefixLen=" + targetUpto + "); clear frame.scanned ord=" + lastFrame.ord);
+ //}
+ currentFrame = lastFrame;
+
+ } else if (cmp > 0) {
+ // Uncommon case: target term
+ // is before current term; this means we can
+ // keep the currentFrame but we must rewind it
+ // (so we scan from the start)
+ targetBeforeCurrentLength = 0;
+ //if (DEBUG) {
+ //System.out.println(" target is before current (shares prefixLen=" + targetUpto + "); rewind frame ord=" + lastFrame.ord);
+ //}
+ currentFrame = lastFrame;
+ currentFrame.rewind();
+ } else {
+ // Target is exactly the same as current term
+ assert term.length == target.length;
+ if (termExists) {
+ //if (DEBUG) {
+ //System.out.println(" target is same as current; return FOUND");
+ //}
+ return SeekStatus.FOUND;
+ } else {
+ //if (DEBUG) {
+ //System.out.println(" target is same as current but term doesn't exist");
+ //}
+ }
+ }
+
+ } else {
+
+ targetBeforeCurrentLength = -1;
+ arc = fr.index.getFirstArc(arcs[0]);
+
+ // Empty string prefix must have an output (block) in the index!
+ assert arc.isFinal();
+ assert arc.output != null;
+
+ //if (DEBUG) {
+ //System.out.println(" no seek state; push root frame");
+ //}
+
+ output = arc.output;
+
+ currentFrame = staticFrame;
+
+ //term.length = 0;
+ targetUpto = 0;
+ currentFrame = pushFrame(arc, OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.nextFinalOutput), 0);
+ }
+
+ positioned = true;
+
+ //if (DEBUG) {
+ //System.out.println(" start index loop targetUpto=" + targetUpto + " output=" + output + " currentFrame.ord+1=" + currentFrame.ord + " targetBeforeCurrentLength=" + targetBeforeCurrentLength);
+ //}
+
+ // We are done sharing the common prefix with the incoming target and where we are currently seek'd; now continue walking the index:
+ while (targetUpto < target.length) {
+
+ final int targetLabel = target.bytes[target.offset + targetUpto] & 0xFF;
+
+ final FST.Arc<Output> nextArc = fr.index.findTargetArc(targetLabel, arc, getArc(1+targetUpto), fstReader);
+
+ if (nextArc == null) {
+
+ // Index is exhausted
+ // if (DEBUG) {
+ // System.out.println(" index: index exhausted label=" + ((char) targetLabel) + " " + toHex(targetLabel));
+ // }
+
+ validIndexPrefix = currentFrame.prefix;
+ //validIndexPrefix = targetUpto;
+
+ currentFrame.scanToFloorFrame(target);
+
+ currentFrame.loadBlock();
+
+ final SeekStatus result = currentFrame.scanToTerm(target, false);
+ if (result == SeekStatus.END) {
+ term.copyBytes(target);
+ termExists = false;
+
+ if (next() != null) {
+ //if (DEBUG) {
+ //System.out.println(" return NOT_FOUND term=" + brToString(term) + " " + term);
+ //}
+ return SeekStatus.NOT_FOUND;
+ } else {
+ //if (DEBUG) {
+ //System.out.println(" return END");
+ //}
+ return SeekStatus.END;
+ }
+ } else {
+ //if (DEBUG) {
+ //System.out.println(" return " + result + " term=" + brToString(term) + " " + term);
+ //}
+ return result;
+ }
+ } else {
+ // Follow this arc
+ term.bytes[targetUpto] = (byte) targetLabel;
+ arc = nextArc;
+ // Aggregate output as we go:
+ assert arc.output != null;
+ if (arc.output != OrdsBlockTreeTermsWriter.NO_OUTPUT) {
+ output = OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.output);
+ }
+
+ //if (DEBUG) {
+ //System.out.println(" index: follow label=" + toHex(target.bytes[target.offset + targetUpto]&0xff) + " arc.output=" + arc.output + " arc.nfo=" + arc.nextFinalOutput);
+ //}
+ targetUpto++;
+
+ if (arc.isFinal()) {
+ //if (DEBUG) System.out.println(" arc is final!");
+ currentFrame = pushFrame(arc, OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.nextFinalOutput), targetUpto);
+ //if (DEBUG) System.out.println(" curFrame.ord=" + currentFrame.ord + " hasTerms=" + currentFrame.hasTerms);
+ }
+ }
+ }
+
+ //validIndexPrefix = targetUpto;
+ validIndexPrefix = currentFrame.prefix;
+
+ currentFrame.scanToFloorFrame(target);
+
+ currentFrame.loadBlock();
+
+ final SeekStatus result = currentFrame.scanToTerm(target, false);
+
+ if (result == SeekStatus.END) {
+ term.copyBytes(target);
+ termExists = false;
+ if (next() != null) {
+ //if (DEBUG) {
+ //System.out.println(" return NOT_FOUND term=" + term.utf8ToString() + " " + term);
+ //}
+ return SeekStatus.NOT_FOUND;
+ } else {
+ //if (DEBUG) {
+ //System.out.println(" return END");
+ //}
+ return SeekStatus.END;
+ }
+ } else {
+ return result;
+ }
+ }
+
+ @SuppressWarnings("unused")
+ private void printSeekState(PrintStream out) throws IOException {
+ if (currentFrame == staticFrame) {
+ out.println(" no prior seek");
+ } else {
+ out.println(" prior seek state:");
+ int ord = 0;
+ boolean isSeekFrame = true;
+ while(true) {
+ OrdsSegmentTermsEnumFrame f = getFrame(ord);
+ assert f != null;
+ final BytesRef prefix = new BytesRef(term.bytes, 0, f.prefix);
+ if (f.nextEnt == -1) {
+ out.println(" frame " + (isSeekFrame ? "(seek)" : "(next)") + " ord=" + ord + " fp=" + f.fp + (f.isFloor ? (" (fpOrig=" + f.fpOrig + ")") : "") + " prefixLen=" + f.prefix + " prefix=" + brToString(prefix) + (f.nextEnt == -1 ? "" : (" (of " + f.entCount + ")")) + " hasTerms=" + f.hasTerms + " isFloor=" + f.isFloor + " code=" + ((f.fp<<OrdsBlockTreeTermsWriter.OUTPUT_FLAGS_NUM_BITS) + (f.hasTerms ? OrdsBlockTreeTermsWriter.OUTPUT_FLAG_HAS_TERMS:0) + (f.isFloor ? OrdsBlockTreeTermsWriter.OUTPUT_FLAG_IS_FLOOR:0)) + " isLastInFloor=" + f.isLastInFloor + " mdUpto=" + f.metaDataUpto + " tbOrd=" + f.getTermBlockOrd() + " termOrd=" + f.termOrd);
+ } else {
+ out.println(" frame " + (isSeekFrame ? "(seek, loaded)" : "(next, loaded)") + " ord=" + ord + " fp=" + f.fp + (f.isFloor ? (" (fpOrig=" + f.fpOrig + ")") : "") + " prefixLen=" + f.prefix + " prefix=" + brToString(prefix) + " nextEnt=" + f.nextEnt + (f.nextEnt == -1 ? "" : (" (of " + f.entCount + ")")) + " hasTerms=" + f.hasTerms + " isFloor=" + f.isFloor + " code=" + ((f.fp<<OrdsBlockTreeTermsWriter.OUTPUT_FLAGS_NUM_BITS) + (f.hasTerms ? OrdsBlockTreeTermsWriter.OUTPUT_FLAG_HAS_TERMS:0) + (f.isFloor ? OrdsBlockTreeTermsWriter.OUTPUT_FLAG_IS_FLOOR:0)) + " lastSubFP=" + f.lastSubFP + " isLastInFloor=" + f.isLastInFloor + " mdUpto=" + f.metaDataUpto + " tbOrd=" + f.getTermBlockOrd() + " termOrd=" + f.termOrd);
+ }
+ if (fr.index != null) {
+ assert !isSeekFrame || f.arc != null: "isSeekFrame=" + isSeekFrame + " f.arc=" + f.arc;
+ if (f.prefix > 0 && isSeekFrame && f.arc.label != (term.bytes[f.prefix-1]&0xFF)) {
+ out.println(" broken seek state: arc.label=" + (char) f.arc.label + " vs term byte=" + (char) (term.bytes[f.prefix-1]&0xFF));
+ throw new RuntimeException("seek state is broken");
+ }
+ Output output = Util.get(fr.index, prefix);
+ if (output == null) {
+ out.println(" broken seek state: prefix is not final in index");
+ throw new RuntimeException("seek state is broken");
+ } else if (isSeekFrame && !f.isFloor) {
+ final ByteArrayDataInput reader = new ByteArrayDataInput(output.bytes.bytes, output.bytes.offset, output.bytes.length);
+ final long codeOrig = reader.readVLong();
+ final long code = (f.fp << OrdsBlockTreeTermsWriter.OUTPUT_FLAGS_NUM_BITS) | (f.hasTerms ? OrdsBlockTreeTermsWriter.OUTPUT_FLAG_HAS_TERMS:0) | (f.isFloor ? OrdsBlockTreeTermsWriter.OUTPUT_FLAG_IS_FLOOR:0);
+ if (codeOrig != code) {
+ out.println(" broken seek state: output code=" + codeOrig + " doesn't match frame code=" + code);
+ throw new RuntimeException("seek state is broken");
+ }
+ }
+ }
+ if (f == currentFrame) {
+ break;
+ }
+ if (f.prefix == validIndexPrefix) {
+ isSeekFrame = false;
+ }
+ ord++;
+ }
+ }
+ }
+
+ /* Decodes only the term bytes of the next term. If caller then asks for
+ metadata, ie docFreq, totalTermFreq or pulls a D/&PEnum, we then (lazily)
+ decode all metadata up to the current term. */
+ @Override
+ public BytesRef next() throws IOException {
+
+ if (in == null) {
+ // Fresh TermsEnum; seek to first term:
+ final FST.Arc<Output> arc;
+ if (fr.index != null) {
+ arc = fr.index.getFirstArc(arcs[0]);
+ // Empty string prefix must have an output in the index!
+ assert arc.isFinal();
+ } else {
+ arc = null;
+ }
+ currentFrame = pushFrame(arc, fr.rootCode, 0);
+ currentFrame.loadBlock();
+ positioned = true;
+ }
+
+ targetBeforeCurrentLength = currentFrame.ord;
+
+ assert !eof;
+ //if (DEBUG) {
+ //System.out.println("\nBTTR.next seg=" + segment + " term=" + brToString(term) + " termExists?=" + termExists + " field=" + fieldInfo.name + " termBlockOrd=" + currentFrame.state.termBlockOrd + " validIndexPrefix=" + validIndexPrefix);
+ //printSeekState();
+ //}
+
+ if (currentFrame == staticFrame || positioned == false) {
+ // If seek was previously called and the term was
+ // cached, or seek(TermState) was called, usually
+ // caller is just going to pull a D/&PEnum or get
+ // docFreq, etc. But, if they then call next(),
+ // this method catches up all internal state so next()
+ // works properly:
+ // if (DEBUG) System.out.println(" re-seek to pending term=" + term.utf8ToString() + " " + term);
+ final boolean result = seekExact(term);
+ assert result;
+ }
+
+ // Pop finished blocks
+ while (currentFrame.nextEnt == currentFrame.entCount) {
+ if (!currentFrame.isLastInFloor) {
+ currentFrame.loadNextFloorBlock();
+ } else {
+ //if (DEBUG) System.out.println(" pop frame");
+ if (currentFrame.ord == 0) {
+ //if (DEBUG) System.out.println(" return null");
+ assert setEOF();
+ term.length = 0;
+ validIndexPrefix = 0;
+ currentFrame.rewind();
+ termExists = false;
+ positioned = false;
+ return null;
+ }
+ final long lastFP = currentFrame.fpOrig;
+ currentFrame = stack[currentFrame.ord-1];
+
+ if (currentFrame.nextEnt == -1 || currentFrame.lastSubFP != lastFP) {
+ // We popped into a frame that's not loaded
+ // yet or not scan'd to the right entry
+ currentFrame.scanToFloorFrame(term);
+ currentFrame.loadBlock();
+ currentFrame.scanToSubBlock(lastFP);
+ }
+
+ // Note that the seek state (last seek) has been
+ // invalidated beyond this depth
+ validIndexPrefix = Math.min(validIndexPrefix, currentFrame.prefix);
+ //if (DEBUG) {
+ //System.out.println(" reset validIndexPrefix=" + validIndexPrefix);
+ //}
+ }
+ }
+
+ while(true) {
+ long prevTermOrd = currentFrame.termOrd;
+ if (currentFrame.next()) {
+ // Push to new block:
+ //if (DEBUG) System.out.println(" push frame");
+ currentFrame = pushFrame(null, currentFrame.lastSubFP, term.length, prevTermOrd);
+ // This is a "next" frame -- even if it's
+ // floor'd we must pretend it isn't so we don't
+ // try to scan to the right floor frame:
+ currentFrame.isFloor = false;
+ //currentFrame.hasTerms = true;
+ currentFrame.loadBlock();
+ } else {
+ //if (DEBUG) System.out.println(" return term=" + term.utf8ToString() + " " + term + " currentFrame.ord=" + currentFrame.ord);
+ positioned = true;
+ return term;
+ }
+ }
+ }
+
+ @Override
+ public BytesRef term() {
+ assert !eof;
+ return term;
+ }
+
+ @Override
+ public long ord() {
+ assert !eof;
+ assert currentFrame.termOrd > 0;
+ return currentFrame.termOrd-1;
+ }
+
+ @Override
+ public int docFreq() throws IOException {
+ assert !eof;
+ //if (DEBUG) System.out.println("BTR.docFreq");
+ currentFrame.decodeMetaData();
+ //if (DEBUG) System.out.println(" return " + currentFrame.state.docFreq);
+ return currentFrame.state.docFreq;
+ }
+
+ @Override
+ public long totalTermFreq() throws IOException {
+ assert !eof;
+ currentFrame.decodeMetaData();
+ return currentFrame.state.totalTermFreq;
+ }
+
+ @Override
+ public DocsEnum docs(Bits skipDocs, DocsEnum reuse, int flags) throws IOException {
+ assert !eof;
+ //if (DEBUG) {
+ //System.out.println("BTTR.docs seg=" + segment);
+ //}
+ currentFrame.decodeMetaData();
+ //if (DEBUG) {
+ //System.out.println(" state=" + currentFrame.state);
+ //}
+ return fr.parent.postingsReader.docs(fr.fieldInfo, currentFrame.state, skipDocs, reuse, flags);
+ }
+
+ @Override
+ public DocsAndPositionsEnum docsAndPositions(Bits skipDocs, DocsAndPositionsEnum reuse, int flags) throws IOException {
+ if (fr.fieldInfo.getIndexOptions().compareTo(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS) < 0) {
+ // Positions were not indexed:
+ return null;
+ }
+
+ assert !eof;
+ currentFrame.decodeMetaData();
+ return fr.parent.postingsReader.docsAndPositions(fr.fieldInfo, currentFrame.state, skipDocs, reuse, flags);
+ }
+
+ @Override
+ public void seekExact(BytesRef target, TermState otherState) {
+ // if (DEBUG) {
+ // System.out.println("BTTR.seekExact termState seg=" + segment + " target=" + target.utf8ToString() + " " + target + " state=" + otherState);
+ // }
+ assert clearEOF();
+ if (target.compareTo(term) != 0 || !termExists) {
+ assert otherState != null && otherState instanceof BlockTermState;
+ BlockTermState blockState = (BlockTermState) otherState;
+ currentFrame = staticFrame;
+ currentFrame.state.copyFrom(otherState);
+ term.copyBytes(target);
+ currentFrame.metaDataUpto = currentFrame.getTermBlockOrd();
+ currentFrame.termOrd = blockState.ord+1;
+ assert currentFrame.metaDataUpto > 0;
+ validIndexPrefix = 0;
+ } else {
+ // if (DEBUG) {
+ // System.out.println(" skip seek: already on target state=" + currentFrame.state);
+ // }
+ }
+ positioned = true;
+ }
+
+ @Override
+ public TermState termState() throws IOException {
+ assert !eof;
+ currentFrame.decodeMetaData();
+ BlockTermState ts = (BlockTermState) currentFrame.state.clone();
+ assert currentFrame.termOrd > 0;
+ ts.ord = currentFrame.termOrd-1;
+ //if (DEBUG) System.out.println("BTTR.termState seg=" + segment + " state=" + ts);
+ return ts;
+ }
+
+ @Override
+ public void seekExact(long targetOrd) throws IOException {
+ // System.out.println("seekExact targetOrd=" + targetOrd);
+ if (targetOrd < 0 || targetOrd >= fr.numTerms) {
+ throw new IllegalArgumentException("targetOrd out of bounds (got: " + targetOrd + ", numTerms=" + fr.numTerms + ")");
+ }
+
+ assert clearEOF();
+
+ // First do reverse lookup in the index to find the block that holds this term:
+ InputOutput io = getByOutput(targetOrd);
+ if (term.bytes.length < io.input.length) {
+ term.bytes = ArrayUtil.grow(term.bytes, io.input.length);
+ }
+
+ Util.toBytesRef(io.input, term);
+ if (io.input.length == 0) {
+ currentFrame = staticFrame;
+ } else {
+ currentFrame = getFrame(io.input.length-1);
+ }
+ FST.Arc<Output> arc = getArc(io.input.length);
+
+ // Don't force rewind based on term length; we rewind below based on ord:
+ targetBeforeCurrentLength = Integer.MAX_VALUE;
+ currentFrame = pushFrame(arc, io.output, io.input.length);
+ if (currentFrame.termOrd > targetOrd) {
+ //System.out.println(" do rewind: " + currentFrame.termOrd);
+ currentFrame.rewind();
+ }
+
+ currentFrame.scanToFloorFrame(targetOrd);
+ currentFrame.loadBlock();
+ // System.out.println(" after loadBlock termOrd=" + currentFrame.termOrd + " vs " + targetOrd);
+
+ while (currentFrame.termOrd <= targetOrd) {
+ currentFrame.next();
+ }
+
+ assert currentFrame.termOrd == targetOrd+1: "currentFrame.termOrd=" + currentFrame.termOrd + " vs ord=" + targetOrd;
+ assert termExists;
+
+ // Leave enum fully unpositioned, because we didn't set frames for each byte leading up to current term:
+ validIndexPrefix = 0;
+ positioned = false;
+ }
+
+ @Override
+ public String toString() {
+ return "OrdsSegmentTermsEnum(seg=" + fr.parent.segment + ")";
+ }
+
+ /** Holds a single input (IntsRef) + output pair. */
+ private static class InputOutput {
+ public IntsRef input;
+ public Output output;
+
+ @Override
+ public String toString() {
+ return "InputOutput(input=" + input + " output=" + output + ")";
+ }
+ }
+
+ private final FST.Arc<Output> arc = new FST.Arc<>();
+
+ // TODO: this is similar to Util.getByOutput ... can we refactor/share?
+ /** Specialized getByOutput that can understand the ranges (startOrd to endOrd) we use here, not just startOrd. */
+ private InputOutput getByOutput(long targetOrd) throws IOException {
+
+ final IntsRef result = new IntsRef();
+
+ fr.index.getFirstArc(arc);
+ Output output = arc.output;
+ int upto = 0;
+
+ int bestUpto = 0;
+ Output bestOutput = null;
+
+ /*
+ Writer w = new OutputStreamWriter(new FileOutputStream("/tmp/out.dot"));
+ Util.toDot(fr.index, w, true, true);
+ w.close();
+ */
+
+ // System.out.println("reverseLookup seg=" + fr.parent.segment + " output=" + targetOrd);
+
+ while (true) {
+ // System.out.println(" loop: output=" + output.startOrd + "-" + (Long.MAX_VALUE-output.endOrd) + " upto=" + upto + " arc=" + arc + " final?=" + arc.isFinal());
+ if (arc.isFinal()) {
+ final Output finalOutput = OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.nextFinalOutput);
+ // System.out.println(" isFinal: " + finalOutput.startOrd + "-" + (Long.MAX_VALUE-finalOutput.endOrd));
+ if (targetOrd >= finalOutput.startOrd && targetOrd <= Long.MAX_VALUE-finalOutput.endOrd) {
+ // Only one range should match across all arc leaving this node
+ //assert bestOutput == null;
+ bestOutput = finalOutput;
+ bestUpto = upto;
+ }
+ }
+
+ if (FST.targetHasArcs(arc)) {
+ // System.out.println(" targetHasArcs");
+ if (result.ints.length == upto) {
+ result.grow(1+upto);
+ }
+
+ fr.index.readFirstRealTargetArc(arc.target, arc, fstReader);
+
+ if (arc.bytesPerArc != 0) {
+ // System.out.println(" array arcs");
+
+ int low = 0;
+ int high = arc.numArcs-1;
+ int mid = 0;
+ //System.out.println("bsearch: numArcs=" + arc.numArcs + " target=" + targetOutput + " output=" + output);
+ boolean found = false;
+ while (low <= high) {
+ mid = (low + high) >>> 1;
+ fstReader.setPosition(arc.posArcsStart);
+ fstReader.skipBytes(arc.bytesPerArc*mid);
+ final byte flags = fstReader.readByte();
+ fr.index.readLabel(fstReader);
+ final Output minArcOutput;
+ if ((flags & FST.BIT_ARC_HAS_OUTPUT) != 0) {
+ minArcOutput = OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, OrdsBlockTreeTermsWriter.FST_OUTPUTS.read(fstReader));
+ } else {
+ minArcOutput = output;
+ }
+ // System.out.println(" cycle mid=" + mid + " targetOrd=" + targetOrd + " output=" + minArcOutput.startOrd + "-" + (Long.MAX_VALUE-minArcOutput.endOrd));
+ if (targetOrd > Long.MAX_VALUE-minArcOutput.endOrd) {
+ low = mid + 1;
+ } else if (targetOrd < minArcOutput.startOrd) {
+ high = mid - 1;
+ } else {
+ // System.out.println(" found!!");
+ found = true;
+ break;
+ }
+ }
+
+ if (found) {
+ // Keep recursing
+ arc.arcIdx = mid-1;
+ } else {
+ result.length = bestUpto;
+ InputOutput io = new InputOutput();
+ io.input = result;
+ io.output = bestOutput;
+ // System.out.println(" ret0=" + io);
+ return io;
+ }
+
+ fr.index.readNextRealArc(arc, fstReader);
+
+ // Recurse on this arc:
+ result.ints[upto++] = arc.label;
+ output = OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.output);
+
+ } else {
+ // System.out.println(" non-array arc");
+
+ while (true) {
+ // System.out.println(" cycle label=" + arc.label + " output=" + arc.output);
+
+ // This is the min output we'd hit if we follow
+ // this arc:
+ final Output minArcOutput = OrdsBlockTreeTermsWriter.FST_OUTPUTS.add(output, arc.output);
+ long endOrd = Long.MAX_VALUE - minArcOutput.endOrd;
+ // System.out.println(" endOrd=" + endOrd + " targetOrd=" + targetOrd);
+
+ if (targetOrd >= minArcOutput.startOrd && targetOrd <= endOrd) {
+ // Recurse on this arc:
+ output = minArcOutput;
+ result.ints[upto++] = arc.label;
+ break;
+ } else if (targetOrd < endOrd || arc.isLast()) {
+ result.length = bestUpto;
+ InputOutput io = new InputOutput();
+ io.input = result;
+ assert bestOutput != null;
+ io.output = bestOutput;
+ // System.out.println(" ret2=" + io);
+ return io;
+ } else {
+ // System.out.println(" next arc");
+ // Read next arc in this node:
+ fr.index.readNextRealArc(arc, fstReader);
+ }
+ }
+ }
+ } else {
+ result.length = bestUpto;
+ InputOutput io = new InputOutput();
+ io.input = result;
+ io.output = bestOutput;
+ // System.out.println(" ret3=" + io);
+ return io;
+ }
+ }
+ }
+}