path: root/library/cpp/unicode/normalization/normalization.h

#pragma once

#include "decomposition_table.h"

#include <util/charset/unidata.h>
#include <util/charset/wide.h>
#include <util/generic/hash.h>
#include <util/generic/vector.h>
#include <util/generic/algorithm.h>
#include <util/generic/singleton.h>
#include <util/generic/noncopyable.h>
#include <utility>

namespace NUnicode {
    enum ENormalization {
        NFD,
        NFC,
        NFKD,
        NFKC,
    };

    // Грубо говоря:
    // NFD расскладывает "ё" на "е + диакритику"
    // NFC сначала всё раскладывает, потом всё что может - складывает
    // NFKD делает то же, что и NFD. Кроме того, например, римскую IV (\x2163)
    //     превращает в латинские I и V
    // NFKC - NFKD + композиция (римская четвёрка из I и V, естественно, не образуется)

    // Формальная спецификация: http://www.unicode.org/reports/tr15/

    namespace NPrivate {
        inline const wchar32* Decomposition(const TDecompositionTable& table, wchar32 ch) {
            return table.Get(ch, static_cast<const wchar32*>(nullptr));
        }

        class TDecompositor {
        private:
            const TDecompositionTable& Table;

        public:
            inline TDecompositor(const TDecompositionTable& table)
                : Table(table)
            {
            }

            inline const wchar32* Decomposition(wchar32 ch) const {
                return NPrivate::Decomposition(Table, ch);
            }
        };

        template <bool IsCompat>
        struct TStandartDecompositor: public TDecompositor {
            TStandartDecompositor()
                : TDecompositor(NPrivate::DecompositionTable<IsCompat>())
            {
            }
        };

        template <ENormalization N>
        struct TShift;

        template <>
        struct TShift<NFD> {
            static const WC_TYPE Value = NFD_QC;
        };
        template <>
        struct TShift<NFC> {
            static const WC_TYPE Value = NFC_QC;
        };
        template <>
        struct TShift<NFKD> {
            static const WC_TYPE Value = NFKD_QC;
        };
        template <>
        struct TShift<NFKC> {
            static const WC_TYPE Value = NFKC_QC;
        };

        template <ENormalization N>
        inline bool Normalized(wchar32 ch) {
            return CharInfo(ch) & NPrivate::TShift<N>::Value;
        }

        class TComposition {
        private:
            struct TRawData {
                wchar32 Lead;
                wchar32 Tail;
                wchar32 Comp;
            };

            static const TRawData RawData[];
            static const size_t RawDataSize;

            class TKey: public std::pair<wchar32, wchar32> {
            public:
                inline TKey(wchar32 a, wchar32 b)
                    : std::pair<wchar32, wchar32>(a, b)
                {
                }

                inline size_t Hash() const {
                    return CombineHashes(first, second);
                }
            };

            template <class T>
            struct THash {
                inline size_t operator()(const T& t) const {
                    return t.Hash();
                }
            };

            typedef THashMap<TKey, wchar32, THash<TKey>> TData;
            TData Data;

        public:
            TComposition();

            inline wchar32 Composite(wchar32 lead, wchar32 tail) const {
                TData::const_iterator i = Data.find(TKey(lead, tail));
                if (i == Data.end())
                    return 0;

                return i->second;
            }
        };

        typedef std::pair<wchar32, TCombining> TSymbol;
        typedef TVector<TSymbol> TBuffer;

        template <bool doCompose>
        class TCompositor;

        template <>
        class TCompositor<false> {
        public:
            inline void DoComposition(TBuffer& buffer) {
                Y_UNUSED(buffer); 
            }
        };

        template <>
        class TCompositor<true> {
        private:
            static const wchar32 NonComposite = 0;
            const TComposition* Composition;

        public:
            inline TCompositor()
                : Composition(Singleton<TComposition>())
            {
            }

            inline void DoComposition(TBuffer& buffer) {
                if (buffer.size() < 2)
                    return;

                const TSymbol& leadSymbol = buffer[0];
                if (leadSymbol.second != 0)
                    return;

                wchar32 lead = leadSymbol.first;
                bool oneMoreTurnPlease = false;
                do {
                    oneMoreTurnPlease = false;
                    TCombining lastCombining = 0;
                    for (TBuffer::iterator i = buffer.begin() + 1, mi = buffer.end(); i != mi; ++i) {
                        TCombining currentCombining = i->second;
                        if (!(currentCombining != lastCombining && currentCombining != 0 || lastCombining == 0 && currentCombining == 0))
                            continue;

                        lastCombining = currentCombining;
                        wchar32 comb = Composition->Composite(lead, i->first);
                        if (comb == NonComposite)
                            continue;

                        lead = comb;
                        buffer.erase(i);
                        oneMoreTurnPlease = true;
                        break;
                    }
                } while (oneMoreTurnPlease);

                Y_ASSERT(DecompositionCombining(lead) == 0); 
                buffer[0] = TSymbol(lead, 0);
            }
        };

        template <ENormalization N, typename TCharType>
        inline bool Normalized(const TCharType* begin, const TCharType* end) {
            TCombining lastCanonicalClass = 0;
            for (const TCharType* i = begin; i != end;) {
                wchar32 ch = ReadSymbolAndAdvance(i, end);

                TCombining canonicalClass = DecompositionCombining(ch);
                if (lastCanonicalClass > canonicalClass && canonicalClass != 0)
                    return false;

                if (!Normalized<N>(ch))
                    return false;

                lastCanonicalClass = canonicalClass;
            }
            return true;
        }
    }

    template <bool compat>
    inline const wchar32* Decomposition(wchar32 ch) {
        return NPrivate::Decomposition(NPrivate::DecompositionTable<compat>(), ch);
    }

    template <ENormalization N, class TDecompositor = NPrivate::TDecompositor>
    class TNormalizer : NNonCopyable::TNonCopyable {
    private:
        static const ENormalization Norm = N;
        static const bool IsCompat = Norm == NFKD || Norm == NFKC;
        static const bool RequireComposition = Norm == NFC || Norm == NFKC;

        typedef NPrivate::TSymbol TSymbol;
        typedef NPrivate::TBuffer TBuffer;

        TBuffer Buffer;

        NPrivate::TCompositor<RequireComposition> Compositor;
        const TDecompositor& Decompositor;

    private:
        static inline bool Compare(const TSymbol& a, const TSymbol& b) {
            return a.second < b.second;
        }

        struct TComparer {
            inline bool operator()(const TSymbol& a, const TSymbol& b) {
                return Compare(a, b);
            }
        };

        template <class T>
        static inline void Write(const TBuffer::const_iterator& begin, const TBuffer::const_iterator& end, T& out) {
            for (TBuffer::const_iterator i = begin; i != end; ++i) {
                WriteSymbol(i->first, out);
            }
        }

        static inline void Write(const TBuffer::const_iterator& begin, const TBuffer::const_iterator& end, TUtf32String& out) {  // because WriteSymbol from util/charset/wide.h works wrong in this case
            for (TBuffer::const_iterator i = begin; i != end; ++i) {
                out += i->first;
            }
        }

        inline void SortBuffer() {
            if (Buffer.size() < 2)
                return;

            StableSort(Buffer.begin(), Buffer.end(), TComparer());
        }

        template <class T>
        inline void AddCharNoDecomposition(wchar32 c, T& out) {
            TCombining cc = DecompositionCombining(c);
            if (cc == 0) {
                SortBuffer();
                Buffer.push_back(TBuffer::value_type(c, cc));

                Compositor.DoComposition(Buffer);

                if (Buffer.size() > 1) {
                    Write(Buffer.begin(), Buffer.end() - 1, out);
                    Buffer.erase(Buffer.begin(), Buffer.end() - 1); // TODO I don't like this
                }
            } else {
                Buffer.push_back(TBuffer::value_type(c, cc));
            }
        }

        template <class T>
        inline void AddChar(wchar32 c, T& out) {
            const wchar32* decompBegin = Decompositor.Decomposition(c);
            if (decompBegin) {
                while (*decompBegin) {
                    Y_ASSERT(Decompositor.Decomposition(*decompBegin) == nullptr); 
                    AddCharNoDecomposition(*(decompBegin++), out);
                }
                return;
            } else {
                AddCharNoDecomposition(c, out);
            }
        }

        template <class T, typename TCharType>
        inline void DoNormalize(const TCharType* begin, const TCharType* end, T& out) {
            Buffer.clear();

            for (const TCharType* i = begin; i != end;) {
                AddChar(ReadSymbolAndAdvance(i, end), out);
            }

            SortBuffer();
            Compositor.DoComposition(Buffer);
            Write(Buffer.begin(), Buffer.end(), out);
        }

    public:
        TNormalizer()
            : Decompositor(*Singleton<NPrivate::TStandartDecompositor<IsCompat>>())
        {
        }

        TNormalizer(const TDecompositor& decompositor)
            : Decompositor(decompositor)
        {
        }

        template <class T, typename TCharType>
        inline void Normalize(const TCharType* begin, const TCharType* end, T& out) {
            if (NPrivate::Normalized<Norm>(begin, end)) {
                for (const TCharType* i = begin; i != end; ++i) {
                    WriteSymbol(*i, out);
                }
            } else {
                DoNormalize(begin, end, out);
            }
        }

        template <typename TCharType>
        inline void Normalize(const TCharType* begin, const TCharType* end, TUtf32String& out) {
            if (NPrivate::Normalized<Norm>(begin, end)) {
                for (const TCharType* i = begin; i != end;) {
                    out += ReadSymbolAndAdvance(i, end);
                }
            } else {
                DoNormalize(begin, end, out);
            }
        }

        template <class T, typename TCharType>
        inline void Normalize(const TCharType* begin, size_t len, T& out) {
            return Normalize(begin, begin + len, out);
        }

        template <typename TCharType>
        inline TBasicString<TCharType> Normalize(const TBasicString<TCharType>& src) {
            if (NPrivate::Normalized<Norm>(src.begin(), src.end())) {
                // nothing to normalize
                return src;
            } else {
                TBasicString<TCharType> res;
                res.reserve(src.length());
                DoNormalize(src.begin(), src.end(), res);
                return res;
            }
        }
    };
}

//! decompose utf16 or utf32 string to any container supporting push_back or to T*
template <NUnicode::ENormalization Norm, class T, typename TCharType>
inline void Normalize(const TCharType* begin, size_t len, T& out) {
    ::NUnicode::TNormalizer<Norm> dec;
    dec.Normalize(begin, len, out);
}

template <NUnicode::ENormalization N, typename TCharType>
inline TBasicString<TCharType> Normalize(const TCharType* str, size_t len) {
    TBasicString<TCharType> res;
    res.reserve(len);

    Normalize<N>(str, len, res);

    return res;
}

template <NUnicode::ENormalization N, typename TCharType>
inline TBasicString<TCharType> Normalize(const TBasicString<TCharType>& str) {
    ::NUnicode::TNormalizer<N> dec;
    return dec.Normalize(str);
}
 
template <NUnicode::ENormalization N, typename TCharType>
inline TBasicString<TCharType> Normalize(const TBasicStringBuf<TCharType> str) {
    return Normalize<N>(str.data(), str.size()); 
}