dictionary/bigram/dynamic_bigram_list_policy.cpp

/*
 * 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/bigram/dynamic_bigram_list_policy.h"

#include "suggest/core/policy/dictionary_shortcuts_structure_policy.h"
#include "suggest/policyimpl/dictionary/dynamic_patricia_trie_node_reader.h"
#include "suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h"
#include "suggest/policyimpl/dictionary/utils/buffer_with_extendable_buffer.h"
#include "suggest/policyimpl/dictionary/utils/forgetting_curve_utils.h"

namespace latinime {

const int DynamicBigramListPolicy::CONTINUING_BIGRAM_LINK_COUNT_LIMIT = 10000;
const int DynamicBigramListPolicy::BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT = 100000;

void DynamicBigramListPolicy::getNextBigram(int *const outBigramPos, int *const outProbability,
        bool *const outHasNext, int *const bigramEntryPos) const {
    const bool usesAdditionalBuffer = mBuffer->isInAdditionalBuffer(*bigramEntryPos);
    const uint8_t *const buffer = mBuffer->getBuffer(usesAdditionalBuffer);
    if (usesAdditionalBuffer) {
        *bigramEntryPos -= mBuffer->getOriginalBufferSize();
    }
    BigramListReadWriteUtils::BigramFlags bigramFlags;
    int originalBigramPos;
    BigramListReadWriteUtils::getBigramEntryPropertiesAndAdvancePosition(buffer, &bigramFlags,
            &originalBigramPos, bigramEntryPos);
    if (usesAdditionalBuffer && originalBigramPos != NOT_A_DICT_POS) {
        originalBigramPos += mBuffer->getOriginalBufferSize();
    }
    *outProbability = BigramListReadWriteUtils::getProbabilityFromFlags(bigramFlags);
    *outHasNext = BigramListReadWriteUtils::hasNext(bigramFlags);
    if (mIsDecayingDict && !ForgettingCurveUtils::isValidEncodedProbability(*outProbability)) {
        // This bigram is too weak to output.
        *outBigramPos = NOT_A_DICT_POS;
    } else {
        *outBigramPos = followBigramLinkAndGetCurrentBigramPtNodePos(originalBigramPos);
    }
    if (usesAdditionalBuffer) {
        *bigramEntryPos += mBuffer->getOriginalBufferSize();
    }
}

void DynamicBigramListPolicy::skipAllBigrams(int *const bigramListPos) const {
    const bool usesAdditionalBuffer = mBuffer->isInAdditionalBuffer(*bigramListPos);
    const uint8_t *const buffer = mBuffer->getBuffer(usesAdditionalBuffer);
    if (usesAdditionalBuffer) {
        *bigramListPos -= mBuffer->getOriginalBufferSize();
    }
    BigramListReadWriteUtils::skipExistingBigrams(buffer, bigramListPos);
    if (usesAdditionalBuffer) {
        *bigramListPos += mBuffer->getOriginalBufferSize();
    }
}

bool DynamicBigramListPolicy::copyAllBigrams(BufferWithExtendableBuffer *const bufferToWrite,
        int *const fromPos, int *const toPos, int *const outBigramsCount) const {
    const bool usesAdditionalBuffer = mBuffer->isInAdditionalBuffer(*fromPos);
    if (usesAdditionalBuffer) {
        *fromPos -= mBuffer->getOriginalBufferSize();
    }
    *outBigramsCount = 0;
    BigramListReadWriteUtils::BigramFlags bigramFlags;
    int bigramEntryCount = 0;
    int lastWrittenEntryPos = NOT_A_DICT_POS;
    do {
        if (++bigramEntryCount > BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT) {
            AKLOGE("Too many bigram entries. Entry count: %d, Limit: %d",
                    bigramEntryCount, BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT);
            ASSERT(false);
            return false;
        }
        // The buffer address can be changed after calling buffer writing methods.
        int originalBigramPos;
        BigramListReadWriteUtils::getBigramEntryPropertiesAndAdvancePosition(
                mBuffer->getBuffer(usesAdditionalBuffer), &bigramFlags, &originalBigramPos,
                fromPos);
        if (originalBigramPos == NOT_A_DICT_POS) {
            // skip invalid bigram entry.
            continue;
        }
        if (usesAdditionalBuffer) {
            originalBigramPos += mBuffer->getOriginalBufferSize();
        }
        const int bigramPos = followBigramLinkAndGetCurrentBigramPtNodePos(originalBigramPos);
        if (bigramPos == NOT_A_DICT_POS) {
            // Target PtNode has been invalidated.
            continue;
        }
        lastWrittenEntryPos = *toPos;
        if (!BigramListReadWriteUtils::createAndWriteBigramEntry(bufferToWrite, bigramPos,
                BigramListReadWriteUtils::getProbabilityFromFlags(bigramFlags),
                BigramListReadWriteUtils::hasNext(bigramFlags), toPos)) {
            return false;
        }
        (*outBigramsCount)++;
    } while(BigramListReadWriteUtils::hasNext(bigramFlags));
    // Makes the last entry the terminal of the list. Updates the flags.
    if (lastWrittenEntryPos != NOT_A_DICT_POS) {
        if (!BigramListReadWriteUtils::setHasNextFlag(bufferToWrite, false /* hasNext */,
                lastWrittenEntryPos)) {
            return false;
        }
    }
    if (usesAdditionalBuffer) {
        *fromPos += mBuffer->getOriginalBufferSize();
    }
    return true;
}

// Finding useless bigram entries and remove them. Bigram entry is useless when the target PtNode
// has been deleted or is not a valid terminal.
bool DynamicBigramListPolicy::updateAllBigramEntriesAndDeleteUselessEntries(
        int *const bigramListPos, int *const outValidBigramEntryCount) {
    const bool usesAdditionalBuffer = mBuffer->isInAdditionalBuffer(*bigramListPos);
    if (usesAdditionalBuffer) {
        *bigramListPos -= mBuffer->getOriginalBufferSize();
    }
    DynamicPatriciaTrieNodeReader nodeReader(mBuffer, this /* bigramsPolicy */, mShortcutPolicy);
    BigramListReadWriteUtils::BigramFlags bigramFlags;
    int bigramEntryCount = 0;
    do {
        if (++bigramEntryCount > BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT) {
            AKLOGE("Too many bigram entries. Entry count: %d, Limit: %d",
                    bigramEntryCount, BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT);
            ASSERT(false);
            return false;
        }
        int bigramEntryPos = *bigramListPos;
        int originalBigramPos;
        // The buffer address can be changed after calling buffer writing methods.
        BigramListReadWriteUtils::getBigramEntryPropertiesAndAdvancePosition(
                mBuffer->getBuffer(usesAdditionalBuffer), &bigramFlags, &originalBigramPos,
                bigramListPos);
        if (usesAdditionalBuffer) {
            bigramEntryPos += mBuffer->getOriginalBufferSize();
        }
        if (originalBigramPos == NOT_A_DICT_POS) {
            // This entry has already been removed.
            continue;
        }
        if (usesAdditionalBuffer) {
            originalBigramPos += mBuffer->getOriginalBufferSize();
        }
        const int bigramTargetNodePos =
                followBigramLinkAndGetCurrentBigramPtNodePos(originalBigramPos);
        nodeReader.fetchNodeInfoInBufferFromPtNodePos(bigramTargetNodePos);
        if (nodeReader.isDeleted() || !nodeReader.isTerminal()
                || bigramTargetNodePos == NOT_A_DICT_POS) {
            // The target is no longer valid terminal. Invalidate the current bigram entry.
            if (!BigramListReadWriteUtils::writeBigramEntry(mBuffer, bigramFlags,
                    NOT_A_DICT_POS /* targetPtNodePos */, &bigramEntryPos)) {
                return false;
            }
            continue;
        }
        bool isRemoved = false;
        if (!updateProbabilityForDecay(bigramFlags, bigramTargetNodePos, &bigramEntryPos,
                &isRemoved)) {
            return false;
        }
        if (!isRemoved) {
            (*outValidBigramEntryCount) += 1;
        }
    } while(BigramListReadWriteUtils::hasNext(bigramFlags));
    return true;
}

// Updates bigram target PtNode positions in the list after the placing step in GC.
bool DynamicBigramListPolicy::updateAllBigramTargetPtNodePositions(int *const bigramListPos,
        const DynamicPatriciaTrieWritingHelper::PtNodePositionRelocationMap *const
                ptNodePositionRelocationMap, int *const outBigramEntryCount) {
    const bool usesAdditionalBuffer = mBuffer->isInAdditionalBuffer(*bigramListPos);
    if (usesAdditionalBuffer) {
        *bigramListPos -= mBuffer->getOriginalBufferSize();
    }
    BigramListReadWriteUtils::BigramFlags bigramFlags;
    int bigramEntryCount = 0;
    do {
        if (++bigramEntryCount > BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT) {
            AKLOGE("Too many bigram entries. Entry count: %d, Limit: %d",
                    bigramEntryCount, BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT);
            ASSERT(false);
            return false;
        }
        int bigramEntryPos = *bigramListPos;
        if (usesAdditionalBuffer) {
            bigramEntryPos += mBuffer->getOriginalBufferSize();
        }
        int bigramTargetPtNodePos;
        // The buffer address can be changed after calling buffer writing methods.
        BigramListReadWriteUtils::getBigramEntryPropertiesAndAdvancePosition(
                mBuffer->getBuffer(usesAdditionalBuffer), &bigramFlags, &bigramTargetPtNodePos,
                bigramListPos);
        if (bigramTargetPtNodePos == NOT_A_DICT_POS) {
            continue;
        }
        if (usesAdditionalBuffer) {
            bigramTargetPtNodePos += mBuffer->getOriginalBufferSize();
        }

        DynamicPatriciaTrieWritingHelper::PtNodePositionRelocationMap::const_iterator it =
                ptNodePositionRelocationMap->find(bigramTargetPtNodePos);
        if (it != ptNodePositionRelocationMap->end()) {
            bigramTargetPtNodePos = it->second;
        } else {
            bigramTargetPtNodePos = NOT_A_DICT_POS;
        }
        if (!BigramListReadWriteUtils::writeBigramEntry(mBuffer, bigramFlags,
                bigramTargetPtNodePos, &bigramEntryPos)) {
            return false;
        }
    } while(BigramListReadWriteUtils::hasNext(bigramFlags));
    (*outBigramEntryCount) = bigramEntryCount;
    return true;
}

bool DynamicBigramListPolicy::addNewBigramEntryToBigramList(const int bigramTargetPos,
        const int probability, int *const bigramListPos, bool *const outAddedNewBigram) {
    const bool usesAdditionalBuffer = mBuffer->isInAdditionalBuffer(*bigramListPos);
    if (usesAdditionalBuffer) {
        *bigramListPos -= mBuffer->getOriginalBufferSize();
    }
    BigramListReadWriteUtils::BigramFlags bigramFlags;
    int bigramEntryCount = 0;
    do {
        if (++bigramEntryCount > BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT) {
            AKLOGE("Too many bigram entries. Entry count: %d, Limit: %d",
                    bigramEntryCount, BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT);
            ASSERT(false);
            return false;
        }
        int entryPos = *bigramListPos;
        if (usesAdditionalBuffer) {
            entryPos += mBuffer->getOriginalBufferSize();
        }
        int originalBigramPos;
        // The buffer address can be changed after calling buffer writing methods.
        BigramListReadWriteUtils::getBigramEntryPropertiesAndAdvancePosition(
                mBuffer->getBuffer(usesAdditionalBuffer), &bigramFlags, &originalBigramPos,
                bigramListPos);
        if (usesAdditionalBuffer && originalBigramPos != NOT_A_DICT_POS) {
            originalBigramPos += mBuffer->getOriginalBufferSize();
        }
        if (followBigramLinkAndGetCurrentBigramPtNodePos(originalBigramPos) == bigramTargetPos) {
            // Update this bigram entry.
            *outAddedNewBigram = false;
            const int originalProbability = BigramListReadWriteUtils::getProbabilityFromFlags(
                    bigramFlags);
            const int probabilityToWrite = mIsDecayingDict ?
                    ForgettingCurveUtils::getUpdatedEncodedProbability(originalProbability,
                            probability) : probability;
            const BigramListReadWriteUtils::BigramFlags updatedFlags =
                    BigramListReadWriteUtils::setProbabilityInFlags(bigramFlags,
                            probabilityToWrite);
            return BigramListReadWriteUtils::writeBigramEntry(mBuffer, updatedFlags,
                    originalBigramPos, &entryPos);
        }
        if (BigramListReadWriteUtils::hasNext(bigramFlags)) {
            continue;
        }
        // The current last entry is found.
        // First, update the flags of the last entry.
        if (!BigramListReadWriteUtils::setHasNextFlag(mBuffer, true /* hasNext */, entryPos)) {
            *outAddedNewBigram = false;
            return false;
        }
        if (usesAdditionalBuffer) {
            *bigramListPos += mBuffer->getOriginalBufferSize();
        }
        // Then, add a new entry after the last entry.
        *outAddedNewBigram = true;
        return writeNewBigramEntry(bigramTargetPos, probability, bigramListPos);
    } while(BigramListReadWriteUtils::hasNext(bigramFlags));
    // We return directly from the while loop.
    ASSERT(false);
    return false;
}

bool DynamicBigramListPolicy::writeNewBigramEntry(const int bigramTargetPos, const int probability,
        int *const writingPos) {
    // hasNext is false because we are adding a new bigram entry at the end of the bigram list.
    const int probabilityToWrite = mIsDecayingDict ?
            ForgettingCurveUtils::getUpdatedEncodedProbability(NOT_A_PROBABILITY, probability) :
                    probability;
    return BigramListReadWriteUtils::createAndWriteBigramEntry(mBuffer, bigramTargetPos,
            probabilityToWrite, false /* hasNext */, writingPos);
}

bool DynamicBigramListPolicy::removeBigram(const int bigramListPos, const int bigramTargetPos) {
    const bool usesAdditionalBuffer = mBuffer->isInAdditionalBuffer(bigramListPos);
    int pos = bigramListPos;
    if (usesAdditionalBuffer) {
        pos -= mBuffer->getOriginalBufferSize();
    }
    BigramListReadWriteUtils::BigramFlags bigramFlags;
    int bigramEntryCount = 0;
    do {
        if (++bigramEntryCount > BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT) {
            AKLOGE("Too many bigram entries. Entry count: %d, Limit: %d",
                    bigramEntryCount, BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT);
            ASSERT(false);
            return false;
        }
        int bigramEntryPos = pos;
        int originalBigramPos;
        // The buffer address can be changed after calling buffer writing methods.
        BigramListReadWriteUtils::getBigramEntryPropertiesAndAdvancePosition(
                mBuffer->getBuffer(usesAdditionalBuffer), &bigramFlags, &originalBigramPos, &pos);
        if (usesAdditionalBuffer) {
            bigramEntryPos += mBuffer->getOriginalBufferSize();
        }
        if (usesAdditionalBuffer && originalBigramPos != NOT_A_DICT_POS) {
            originalBigramPos += mBuffer->getOriginalBufferSize();
        }
        const int bigramPos = followBigramLinkAndGetCurrentBigramPtNodePos(originalBigramPos);
        if (bigramPos != bigramTargetPos) {
            continue;
        }
        // Target entry is found. Write an invalid target position to mark the bigram invalid.
        return BigramListReadWriteUtils::writeBigramEntry(mBuffer, bigramFlags,
                NOT_A_DICT_POS /* targetOffset */, &bigramEntryPos);
    } while(BigramListReadWriteUtils::hasNext(bigramFlags));
    return false;
}

int DynamicBigramListPolicy::followBigramLinkAndGetCurrentBigramPtNodePos(
        const int originalBigramPos) const {
    if (originalBigramPos == NOT_A_DICT_POS) {
        return NOT_A_DICT_POS;
    }
    int currentPos = originalBigramPos;
    DynamicPatriciaTrieNodeReader nodeReader(mBuffer, this /* bigramsPolicy */, mShortcutPolicy);
    nodeReader.fetchNodeInfoInBufferFromPtNodePos(currentPos);
    int bigramLinkCount = 0;
    while (nodeReader.getBigramLinkedNodePos() != NOT_A_DICT_POS) {
        currentPos = nodeReader.getBigramLinkedNodePos();
        nodeReader.fetchNodeInfoInBufferFromPtNodePos(currentPos);
        bigramLinkCount++;
        if (bigramLinkCount > CONTINUING_BIGRAM_LINK_COUNT_LIMIT) {
            AKLOGE("Bigram link is invalid. start position: %d", originalBigramPos);
            ASSERT(false);
            return NOT_A_DICT_POS;
        }
    }
    return currentPos;
}

bool DynamicBigramListPolicy::updateProbabilityForDecay(
        const BigramListReadWriteUtils::BigramFlags bigramFlags, const int targetPtNodePos,
        int *const bigramEntryPos, bool *const outRemoved) const {
    *outRemoved = false;
    if (mIsDecayingDict) {
        // Update bigram probability for decaying.
        const int newProbability = ForgettingCurveUtils::getEncodedProbabilityToSave(
                BigramListReadWriteUtils::getProbabilityFromFlags(bigramFlags), mHeaderPolicy);
        if (ForgettingCurveUtils::isValidEncodedProbability(newProbability)) {
            // Write new probability.
            const BigramListReadWriteUtils::BigramFlags updatedBigramFlags =
                    BigramListReadWriteUtils::setProbabilityInFlags(
                            bigramFlags, newProbability);
            if (!BigramListReadWriteUtils::writeBigramEntry(mBuffer, updatedBigramFlags,
                    targetPtNodePos, bigramEntryPos)) {
                return false;
            }
        } else {
            // Remove current bigram entry.
            *outRemoved = true;
            if (!BigramListReadWriteUtils::writeBigramEntry(mBuffer, bigramFlags,
                    NOT_A_DICT_POS /* targetPtNodePos */, bigramEntryPos)) {
                return false;
            }
        }
    }
    return true;
}

} // namespace latinime