| /* |
| * Copyright (C) 2013, The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #include "suggest/policyimpl/dictionary/dynamic_patricia_trie_reading_helper.h" |
| |
| #include "suggest/policyimpl/dictionary/utils/buffer_with_extendable_buffer.h" |
| |
| namespace latinime { |
| |
| // To avoid infinite loop caused by invalid or malicious forward links. |
| const int DynamicPatriciaTrieReadingHelper::MAX_CHILD_COUNT_TO_AVOID_INFINITE_LOOP = 100000; |
| const int DynamicPatriciaTrieReadingHelper::MAX_NODE_ARRAY_COUNT_TO_AVOID_INFINITE_LOOP = 100000; |
| const size_t DynamicPatriciaTrieReadingHelper::MAX_READING_STATE_STACK_SIZE = MAX_WORD_LENGTH; |
| |
| // Visits all PtNodes in post-order depth first manner. |
| // For example, visits c -> b -> y -> x -> a for the following dictionary: |
| // a _ b _ c |
| // \ x _ y |
| bool DynamicPatriciaTrieReadingHelper::traverseAllPtNodesInPostorderDepthFirstManner( |
| TraversingEventListener *const listener) { |
| bool alreadyVisitedChildren = false; |
| // Descend from the root to the root PtNode array. |
| if (!listener->onDescend(getPosOfLastPtNodeArrayHead())) { |
| return false; |
| } |
| while (!isEnd()) { |
| if (!alreadyVisitedChildren) { |
| if (mNodeReader.hasChildren()) { |
| // Move to the first child. |
| if (!listener->onDescend(mNodeReader.getChildrenPos())) { |
| return false; |
| } |
| pushReadingStateToStack(); |
| readChildNode(); |
| } else { |
| alreadyVisitedChildren = true; |
| } |
| } else { |
| if (!listener->onVisitingPtNode(&mNodeReader, mMergedNodeCodePoints)) { |
| return false; |
| } |
| readNextSiblingNode(); |
| if (isEnd()) { |
| // All PtNodes in current linked PtNode arrays have been visited. |
| // Return to the parent. |
| if (!listener->onReadingPtNodeArrayTail()) { |
| return false; |
| } |
| if (mReadingStateStack.size() <= 0) { |
| break; |
| } |
| if (!listener->onAscend()) { |
| return false; |
| } |
| popReadingStateFromStack(); |
| alreadyVisitedChildren = true; |
| } else { |
| // Process sibling PtNode. |
| alreadyVisitedChildren = false; |
| } |
| } |
| } |
| // Ascend from the root PtNode array to the root. |
| if (!listener->onAscend()) { |
| return false; |
| } |
| return !isError(); |
| } |
| |
| // Visits all PtNodes in PtNode array level pre-order depth first manner, which is the same order |
| // that PtNodes are written in the dictionary buffer. |
| // For example, visits a -> b -> x -> c -> y for the following dictionary: |
| // a _ b _ c |
| // \ x _ y |
| bool DynamicPatriciaTrieReadingHelper::traverseAllPtNodesInPtNodeArrayLevelPreorderDepthFirstManner( |
| TraversingEventListener *const listener) { |
| bool alreadyVisitedAllPtNodesInArray = false; |
| bool alreadyVisitedChildren = false; |
| // Descend from the root to the root PtNode array. |
| if (!listener->onDescend(getPosOfLastPtNodeArrayHead())) { |
| return false; |
| } |
| if (isEnd()) { |
| // Empty dictionary. Needs to notify the listener of the tail of empty PtNode array. |
| if (!listener->onReadingPtNodeArrayTail()) { |
| return false; |
| } |
| } |
| pushReadingStateToStack(); |
| while (!isEnd()) { |
| if (alreadyVisitedAllPtNodesInArray) { |
| if (alreadyVisitedChildren) { |
| // Move to next sibling PtNode's children. |
| readNextSiblingNode(); |
| if (isEnd()) { |
| // Return to the parent PTNode. |
| if (!listener->onAscend()) { |
| return false; |
| } |
| if (mReadingStateStack.size() <= 0) { |
| break; |
| } |
| popReadingStateFromStack(); |
| alreadyVisitedChildren = true; |
| alreadyVisitedAllPtNodesInArray = true; |
| } else { |
| alreadyVisitedChildren = false; |
| } |
| } else { |
| if (mNodeReader.hasChildren()) { |
| // Move to the first child. |
| if (!listener->onDescend(mNodeReader.getChildrenPos())) { |
| return false; |
| } |
| pushReadingStateToStack(); |
| readChildNode(); |
| // Push state to return the head of PtNode array. |
| pushReadingStateToStack(); |
| alreadyVisitedAllPtNodesInArray = false; |
| alreadyVisitedChildren = false; |
| } else { |
| alreadyVisitedChildren = true; |
| } |
| } |
| } else { |
| if (!listener->onVisitingPtNode(&mNodeReader, mMergedNodeCodePoints)) { |
| return false; |
| } |
| readNextSiblingNode(); |
| if (isEnd()) { |
| if (!listener->onReadingPtNodeArrayTail()) { |
| return false; |
| } |
| // Return to the head of current PtNode array. |
| popReadingStateFromStack(); |
| alreadyVisitedAllPtNodesInArray = true; |
| } |
| } |
| } |
| popReadingStateFromStack(); |
| // Ascend from the root PtNode array to the root. |
| if (!listener->onAscend()) { |
| return false; |
| } |
| return !isError(); |
| } |
| |
| // Read node array size and process empty node arrays. Nodes and arrays are counted up in this |
| // method to avoid an infinite loop. |
| void DynamicPatriciaTrieReadingHelper::nextPtNodeArray() { |
| if (mReadingState.mPos < 0 || mReadingState.mPos >= mBuffer->getTailPosition()) { |
| // Reading invalid position because of a bug or a broken dictionary. |
| AKLOGE("Reading PtNode array info from invalid dictionary position: %d, dict size: %d", |
| mReadingState.mPos, mBuffer->getTailPosition()); |
| ASSERT(false); |
| mIsError = true; |
| mReadingState.mPos = NOT_A_DICT_POS; |
| return; |
| } |
| mReadingState.mPosOfLastPtNodeArrayHead = mReadingState.mPos; |
| const bool usesAdditionalBuffer = mBuffer->isInAdditionalBuffer(mReadingState.mPos); |
| const uint8_t *const dictBuf = mBuffer->getBuffer(usesAdditionalBuffer); |
| if (usesAdditionalBuffer) { |
| mReadingState.mPos -= mBuffer->getOriginalBufferSize(); |
| } |
| mReadingState.mNodeCount = PatriciaTrieReadingUtils::getPtNodeArraySizeAndAdvancePosition( |
| dictBuf, &mReadingState.mPos); |
| if (usesAdditionalBuffer) { |
| mReadingState.mPos += mBuffer->getOriginalBufferSize(); |
| } |
| // Count up nodes and node arrays to avoid infinite loop. |
| mReadingState.mTotalNodeCount += mReadingState.mNodeCount; |
| mReadingState.mNodeArrayCount++; |
| if (mReadingState.mNodeCount < 0 |
| || mReadingState.mTotalNodeCount > MAX_CHILD_COUNT_TO_AVOID_INFINITE_LOOP |
| || mReadingState.mNodeArrayCount > MAX_NODE_ARRAY_COUNT_TO_AVOID_INFINITE_LOOP) { |
| // Invalid dictionary. |
| AKLOGI("Invalid dictionary. nodeCount: %d, totalNodeCount: %d, MAX_CHILD_COUNT: %d" |
| "nodeArrayCount: %d, MAX_NODE_ARRAY_COUNT: %d", |
| mReadingState.mNodeCount, mReadingState.mTotalNodeCount, |
| MAX_CHILD_COUNT_TO_AVOID_INFINITE_LOOP, mReadingState.mNodeArrayCount, |
| MAX_NODE_ARRAY_COUNT_TO_AVOID_INFINITE_LOOP); |
| ASSERT(false); |
| mIsError = true; |
| mReadingState.mPos = NOT_A_DICT_POS; |
| return; |
| } |
| if (mReadingState.mNodeCount == 0) { |
| // Empty node array. Try following forward link. |
| followForwardLink(); |
| } |
| } |
| |
| // Follow the forward link and read the next node array if exists. |
| void DynamicPatriciaTrieReadingHelper::followForwardLink() { |
| if (mReadingState.mPos < 0 || mReadingState.mPos >= mBuffer->getTailPosition()) { |
| // Reading invalid position because of bug or broken dictionary. |
| AKLOGE("Reading forward link from invalid dictionary position: %d, dict size: %d", |
| mReadingState.mPos, mBuffer->getTailPosition()); |
| ASSERT(false); |
| mIsError = true; |
| mReadingState.mPos = NOT_A_DICT_POS; |
| return; |
| } |
| const bool usesAdditionalBuffer = mBuffer->isInAdditionalBuffer(mReadingState.mPos); |
| const uint8_t *const dictBuf = mBuffer->getBuffer(usesAdditionalBuffer); |
| if (usesAdditionalBuffer) { |
| mReadingState.mPos -= mBuffer->getOriginalBufferSize(); |
| } |
| const int forwardLinkPosition = |
| DynamicPatriciaTrieReadingUtils::getForwardLinkPosition(dictBuf, mReadingState.mPos); |
| if (usesAdditionalBuffer) { |
| mReadingState.mPos += mBuffer->getOriginalBufferSize(); |
| } |
| mReadingState.mPosOfLastForwardLinkField = mReadingState.mPos; |
| if (DynamicPatriciaTrieReadingUtils::isValidForwardLinkPosition(forwardLinkPosition)) { |
| // Follow the forward link. |
| mReadingState.mPos += forwardLinkPosition; |
| nextPtNodeArray(); |
| } else { |
| // All node arrays have been read. |
| mReadingState.mPos = NOT_A_DICT_POS; |
| } |
| } |
| |
| } // namespace latinime |