text: // Copyright 2010-2020, Google Inc.
  // All rights reserved.
  //
  // Redistribution and use in source and binary forms, with or without
  // modification, are permitted provided that the following conditions are
  // met:
  //
  //     * Redistributions of source code must retain the above copyright
  // notice, this list of conditions and the following disclaimer.
  //     * Redistributions in binary form must reproduce the above
  // copyright notice, this list of conditions and the following disclaimer
  // in the documentation and/or other materials provided with the
  // distribution.
  //     * Neither the name of Google Inc. nor the names of its
  // contributors may be used to endorse or promote products derived from
  // this software without specific prior written permission.
  //
  // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  
  #include "converter/key_corrector.h"
  
  #include <cstring>
  
  #include "base/logging.h"
  #include "base/port.h"
  #include "base/util.h"
  
  namespace mozc {
  namespace {
  
  // maximum key length KeyCorrector can handle
  // if key is too long, we don't do key correction
  const size_t kMaxSize = 128;
  
  // invalid alignment marker
  const size_t kInvalidPos = static_cast<size_t>(-1);
  
  // "ん" (few "n" pettern)
  // "んあ" -> "んな"
  // "んい" -> "んに"
  // "んう" -> "んぬ"
  // "んえ" -> "んね"
  // "んお" -> "んの"
  bool RewriteNN(size_t key_pos, const char *begin, const char *end,
                 size_t *mblen, std::string *output) {
    if (key_pos == 0) {
      *mblen = 0;
      return false;
    }
  
    const char32 ucs4 = Util::UTF8ToUCS4(begin, end, mblen);
    if (ucs4 != 0x3093) {  // "ん"
      *mblen = 0;
      return false;
    }
  
    if (begin + *mblen >= end) {
      *mblen = 0;
      return false;
    }
  
    size_t mblen2 = 0;
    const uint16 next_ucs4 = Util::UTF8ToUCS4(begin + *mblen, end, &mblen2);
    uint16 output_ucs4 = 0x0000;
    switch (next_ucs4) {
      case 0x3042:             // "あ"
        output_ucs4 = 0x306A;  // "な"
        break;
      case 0x3044:             // "い"
        output_ucs4 = 0x306B;  // "に"
        break;
      case 0x3046:             // "う"
        output_ucs4 = 0x306C;  // "ぬ"
        break;
      case 0x3048:             // "え"
        output_ucs4 = 0x306D;  // "ね"
        break;
      case 0x304A:             // "お"
        output_ucs4 = 0x306E;  // "の"
        break;
      default:
        break;
    }
  
    if (output_ucs4 != 0x0000) {  // "ん[あいうえお]"
      Util::UCS4ToUTF8Append(ucs4, output);
      Util::UCS4ToUTF8Append(output_ucs4, output);
      *mblen += mblen2;
      return true;
    } else {  // others
      *mblen = 0;
      return false;
    }
  
    return false;
  }
  
  // "んん" (many "n" pattern)
  // "([^ん])んん[ん]" -> ignore
  // "([^ん])んん[あいうえお]" ->  $1 and leave "ん[あいうえお]"
  // "([^ん])んん[^あいうえお]" -> $1"ん" and leave "[^あいうえお]"
  bool RewriteDoubleNN(size_t key_pos, const char *begin, const char *end,
                       size_t *mblen, std::string *output) {
    // 0x3093: "ん"
    static const uint16 kPattern[] = {0x0000, 0x3093, 0x3093};
  
    *mblen = 0;
    uint16 first_char = 0x0000;
    size_t first_mblen = 0;
    for (size_t i = 0; i < arraysize(kPattern); ++i) {
      if (begin >= end) {
        *mblen = 0;
        return false;
      }
      size_t mblen2 = 0;
      const char32 ucs4 = Util::UTF8ToUCS4(begin, end, &mblen2);
      if ((kPattern[i] == 0x0000 && ucs4 != 0x3093 &&
           Util::GetScriptType(ucs4) == Util::HIRAGANA) ||
          (kPattern[i] == 0x3093 && ucs4 == 0x3093)) {
        if (i == 0) {
          first_mblen = mblen2;
          first_char = ucs4;
        }
      } else {
        *mblen = 0;
        return false;
      }
      begin += mblen2;
      *mblen += mblen2;
    }
  
    if (begin >= end) {
      *mblen = 0;
      return false;
    }
  
    if (first_char == 0x0000 || first_mblen == 0) {
      *mblen = 0;
      return false;
    }
  
    size_t mblen2 = 0;
    const char32 ucs4 = Util::UTF8ToUCS4(begin, end, &mblen2);
    if (ucs4 == 0x3093) {  // "ん" ignore
      *mblen = 0;
      return false;
    } else if (ucs4 == 0x3042 ||  // "[あいうえお]"
               ucs4 == 0x3044 || ucs4 == 0x3046 || ucs4 == 0x3048 ||
               ucs4 == 0x304A) {
      // drop first "ん" and leave "ん[あいうえお]"
      // remained part will be handled by RewriteNN(), e.g, "んあ" -> "んな"
      Util::UCS4ToUTF8Append(first_char, output);
      // Skip one Hiragana character in UTF-8, which is 3 bytes.
      *mblen = first_mblen + 3;
      return true;
    } else {  // "[^あいうえお]"
      Util::UCS4ToUTF8Append(first_char, output);
      Util::UCS4ToUTF8Append(0x3093, output);  // "ん"
      return true;
    }
  
    return false;
  }
  
  // "に" pattern
  // "にゃ" -> "んや"
  // "にゅ" -> "んゆ"
  // "にょ" -> "んよ"
  bool RewriteNI(size_t key_pos, const char *begin, const char *end,
                 size_t *mblen, std::string *output) {
    const char32 ucs4 = Util::UTF8ToUCS4(begin, end, mblen);
    if (ucs4 != 0x306B) {  // "に"
      *mblen = 0;
      return false;
    }
  
    if (begin + *mblen >= end) {
      *mblen = 0;
      return false;
    }
  
    size_t mblen2 = 0;
    const uint16 next_ucs4 = Util::UTF8ToUCS4(begin + *mblen, end, &mblen2);
    uint16 output_ucs4 = 0x0000;
    switch (next_ucs4) {
      case 0x3083:             // "ゃ"
        output_ucs4 = 0x3084;  // "や"
        break;
      case 0x3085:             // "ゅ"
        output_ucs4 = 0x3086;  // "ゆ"
        break;
      case 0x3087:             // "ょ"
        output_ucs4 = 0x3088;  // "よ"
        break;
      default:
        output_ucs4 = 0x0000;
        break;
    }
  
    if (output_ucs4 != 0x0000) {
      Util::UCS4ToUTF8Append(0x3093, output);  // "ん"
      Util::UCS4ToUTF8Append(output_ucs4, output);
      *mblen += mblen2;
      return true;
    } else {
      *mblen = 0;
      return false;
    }
  
    return false;
  }
  
  // "m" Pattern (not BOS)
  // "m[ばびぶべぼぱぴぷぺぽ]" -> "ん[ばびぶべぼぱぴぷぺぽ]"
  bool RewriteM(size_t key_pos, const char *begin, const char *end, size_t *mblen,
                std::string *output) {
    if (key_pos == 0) {
      *mblen = 0;
      return false;
    }
    const char32 ucs4 = Util::UTF8ToUCS4(begin, end, mblen);
    // "m" or "ｍ" (don't take capitial letter, as "M" might not be a misspelling)
    if (ucs4 != 0x006D && ucs4 != 0xFF4D) {
      *mblen = 0;
      return false;
    }
  
    if (begin + *mblen >= end) {
      *mblen = 0;
      return false;
    }
  
    size_t mblen2 = 0;
    const uint16 next_ucs4 = Util::UTF8ToUCS4(begin + *mblen, end, &mblen2);
    // "[はばぱひびぴふぶぷへべぺほぼぽ]" => [0x306F .. 0X307D]
    // Here we want to take "[は..ぽ]" except for "はひふへほ"
    if (next_ucs4 % 3 != 0 &&                          // not "はひふへほ"
        next_ucs4 >= 0x306F && next_ucs4 <= 0x307D) {  // "は..ぽ"
      Util::UCS4ToUTF8Append(0x3093, output);          // "ん"
      Util::UCS4ToUTF8Append(next_ucs4, output);
      *mblen += mblen2;
      return true;
    } else {
      *mblen = 0;
      return false;
    }
  
    return true;
  }
  
  // "きっって" ->" きって"
  // replace "([^っ])っっ([^っ])" => "$1っ$2"
  // Don't consider more that three "っっっ"
  // e.g, "かっっった" -> "かっっった"
  bool RewriteSmallTSU(size_t key_pos, const char *begin, const char *end,
                       size_t *mblen, std::string *output) {
    // 0x0000 is a place holder for "[^っ]"
    // "っ": 0x3063
    static const uint16 kPattern[] = {0x0000, 0x3063, 0x3063, 0x0000};
  
    uint16 first_char = 0x0000;
    uint16 last_char = 0x0000;
    for (size_t i = 0; i < arraysize(kPattern); ++i) {
      if (begin >= end) {
        *mblen = 0;
        return false;
      }
      size_t mblen2 = 0;
      const char32 ucs4 = Util::UTF8ToUCS4(begin, end, &mblen2);
      if ((kPattern[i] == 0x0000 && ucs4 != 0x3063 &&
           Util::GetScriptType(ucs4) == Util::HIRAGANA) ||
          (kPattern[i] == 0x3063 && ucs4 == 0x3063)) {
        if (i == 0) {
          first_char = ucs4;
        } else if (i == arraysize(kPattern) - 1) {
          last_char = ucs4;
        }
      } else {
        *mblen = 0;
        return false;
      }
      begin += mblen2;
      *mblen += mblen2;
    }
  
    if (first_char == 0x0000 || last_char == 0x0000) {
      *mblen = 0;
      return false;
    }
  
    Util::UCS4ToUTF8Append(first_char, output);
    Util::UCS4ToUTF8Append(0x3063, output);  // "っ"
    Util::UCS4ToUTF8Append(last_char, output);
  
    return true;
  }
  
  // Not implemented yet, as they looks minor
  // "[子音][ゃゅょ][^う]" Pattern
  // "きゅ[^う] -> きゅう"
  // "しゅ[^う] -> しゅう"
  // "ちゅ[^う] -> ちゅう"
  // "にゅ[^う] -> にゅう"
  // "ひゅ[^う] -> ひゅう"
  // "りゅ[^う] -> りゅう"
  bool RewriteYu(size_t key_pos, const char *begin, const char *end,
                 size_t *mblen, std::string *output) {
    const char32 first_char = Util::UTF8ToUCS4(begin, end, mblen);
    if (first_char != 0x304D && first_char != 0x3057 && first_char != 0x3061 &&
        first_char != 0x306B && first_char != 0x3072 &&
        first_char != 0x308A) {  // !"きしちにひり"
      *mblen = 0;
      return false;
    }
  
    if (begin + *mblen >= end) {
      *mblen = 0;
      return false;
    }
  
    size_t mblen2 = 0;
    const char32 next_char = Util::UTF8ToUCS4(begin + *mblen, end, &mblen2);
    if (next_char != 0x3085) {  // "ゅ"
      *mblen = 0;
      return false;
    }
  
    if (begin + *mblen + mblen2 >= end) {
      *mblen = 0;
      return false;
    }
  
    size_t mblen3 = 0;
    const char32 last_char =
        Util::UTF8ToUCS4(begin + *mblen + mblen2, end, &mblen3);
    if (last_char == 0x3046) {  // "う"
      *mblen = 0;
      return false;
    }
  
    // OK, rewrite
    *mblen += mblen2;
    Util::UCS4ToUTF8Append(first_char, output);
    Util::UCS4ToUTF8Append(next_char, output);  // "ゅ"
    Util::UCS4ToUTF8Append(0x3046, output);     // "う"
  
    return true;
  }
  }  // namespace
  
  KeyCorrector::KeyCorrector(const std::string &key, InputMode mode,
                             size_t history_size)
      : available_(false), mode_(mode) {
    CorrectKey(key, mode, history_size);
  }
  
  KeyCorrector::KeyCorrector() : available_(false), mode_(ROMAN) {}
  
  KeyCorrector::~KeyCorrector() {}
  
  KeyCorrector::InputMode KeyCorrector::mode() const { return mode_; }
  
  bool KeyCorrector::IsAvailable() const { return available_; }
  
  // return corrected key;
  const std::string &KeyCorrector::corrected_key() const {
    return corrected_key_;
  }
  
  const std::string &KeyCorrector::original_key() const { return original_key_; }
  
  size_t KeyCorrector::GetCorrectedPosition(const size_t original_key_pos) const {
    if (original_key_pos < alignment_.size()) {
      return alignment_[original_key_pos];
    }
    return kInvalidPos;
  }
  
  size_t KeyCorrector::GetOriginalPosition(const size_t corrected_key_pos) const {
    if (corrected_key_pos < rev_alignment_.size()) {
      return rev_alignment_[corrected_key_pos];
    }
    return kInvalidPos;
  }
  
  void KeyCorrector::Clear() {
    available_ = false;
    original_key_.clear();
    corrected_key_.clear();
    alignment_.clear();
    rev_alignment_.clear();
  }
  
  bool KeyCorrector::CorrectKey(const std::string &key, InputMode mode,
                                size_t history_size) {
    Clear();
  
    // TODO(taku)  support KANA
    if (mode == KANA) {
      return false;
    }
  
    if (key.size() == 0 || key.size() >= kMaxSize) {
      VLOG(1) << "invalid key length";
      return false;
    }
  
    original_key_ = key;
  
    const char *begin = key.data();
    const char *end = key.data() + key.size();
    const char *input_begin = key.data() + history_size;
    size_t key_pos = 0;
  
    while (begin < end) {
      size_t mblen = 0;
      const size_t org_len = corrected_key_.size();
      if (begin < input_begin ||
          (!RewriteDoubleNN(key_pos, begin, end, &mblen, &corrected_key_) &&
           !RewriteNN(key_pos, begin, end, &mblen, &corrected_key_) &&
           !RewriteYu(key_pos, begin, end, &mblen, &corrected_key_) &&
           !RewriteNI(key_pos, begin, end, &mblen, &corrected_key_) &&
           !RewriteSmallTSU(key_pos, begin, end, &mblen, &corrected_key_) &&
           !RewriteM(key_pos, begin, end, &mblen, &corrected_key_))) {
        const char32 ucs4 = Util::UTF8ToUCS4(begin, end, &mblen);
        Util::UCS4ToUTF8Append(ucs4, &corrected_key_);
      }
  
      const size_t corrected_mblen = corrected_key_.size() - org_len;
  
      if (corrected_mblen <= 0 && mblen <= 0) {
        LOG(ERROR) << "Invalid pattern: " << key;
        Clear();
        return false;
      }
  
      // one to one mapping
      if (mblen == corrected_mblen) {
        const size_t len = static_cast<size_t>(begin - key.data());
        for (size_t i = 0; i < mblen; ++i) {
          alignment_.push_back(org_len + i);
          rev_alignment_.push_back(len + i);
        }
      } else {
        // NOT a one to one maping, we take fist/last alignment only
        alignment_.push_back(org_len);
        for (size_t i = 1; i < mblen; ++i) {
          alignment_.push_back(kInvalidPos);
        }
        rev_alignment_.push_back(static_cast<size_t>(begin - key.data()));
        for (size_t i = 1; i < corrected_mblen; ++i) {
          rev_alignment_.push_back(kInvalidPos);
        }
      }
  
      begin += mblen;
      ++key_pos;
    }
  
    DCHECK_EQ(original_key_.size(), alignment_.size());
    DCHECK_EQ(corrected_key_.size(), rev_alignment_.size());
  
    available_ = true;
    return true;
  }
  
  const char *KeyCorrector::GetCorrectedPrefix(const size_t original_key_pos,
                                               size_t *length) const {
    if (!IsAvailable()) {
      *length = 0;
      return NULL;
    }
  
    if (mode_ == KANA) {
      *length = 0;
      return NULL;
    }
  
    const size_t corrected_key_pos = GetCorrectedPosition(original_key_pos);
    if (!IsValidPosition(corrected_key_pos)) {
      *length = 0;
      return NULL;
    }
  
    const char *corrected_substr = corrected_key_.data() + corrected_key_pos;
    const size_t corrected_length = corrected_key_.size() - corrected_key_pos;
    const char *original_substr = original_key_.data() + original_key_pos;
    const size_t original_length = original_key_.size() - original_key_pos;
    // substrs are different
    if (original_length != corrected_length ||
        memcmp(original_substr, corrected_substr, original_length) != 0) {
      *length = corrected_length;
      return corrected_substr;
    }
  
    *length = 0;
    return NULL;
  }
  
  size_t KeyCorrector::GetOriginalOffset(const size_t original_key_pos,
                                         const size_t new_key_offset) const {
    if (!IsAvailable()) {
      return kInvalidPos;
    }
  
    if (mode_ == KANA) {
      return kInvalidPos;
    }
  
    const size_t corrected_key_pos = GetCorrectedPosition(original_key_pos);
    if (!IsValidPosition(corrected_key_pos)) {
      return kInvalidPos;
    }
  
    if (rev_alignment_.size() == corrected_key_pos + new_key_offset) {
      return (alignment_.size() - GetOriginalPosition(corrected_key_pos));
    } else {
      // treat right edge
      const size_t original_key_pos2 =
          GetOriginalPosition(corrected_key_pos + new_key_offset);
  
      if (!IsValidPosition(original_key_pos2)) {
        return kInvalidPos;
      }
  
      // Don't allow NULL matching
      if (original_key_pos2 >= original_key_pos) {
        return static_cast<size_t>(original_key_pos2 - original_key_pos);
      }
    }
  
    return kInvalidPos;
  }
  
  // static
  bool KeyCorrector::IsValidPosition(size_t pos) { return (pos != kInvalidPos); }
  
  // static
  bool KeyCorrector::IsInvalidPosition(size_t pos) {
    return (pos == kInvalidPos);
  }
  
  // static
  size_t KeyCorrector::InvalidPosition() { return kInvalidPos; }
  
  // static
  int KeyCorrector::GetCorrectedCostPenalty(const std::string &key) {
    // "んん" and "っっ" must be mis-spelling.
    if (key.find("んん") != std::string::npos ||
        key.find("っっ") != std::string::npos) {
      return 0;
    }
    // add 3000 to the original word cost
    const int kCorrectedCostPenalty = 3000;
    return kCorrectedCostPenalty;
  }
  
  }  // namespace mozc
  