utf16_range.cc

Go to the documentation of this file.

#include "src/ir/regexp/encoding/utf16/utf16_range.h"
#include "src/ir/regexp/encoding/range_suffix.h"

namespace re2c {

/*
 * Add word range [w1-w2].
 */
void UTF16addContinuous1(RangeSuffix * & root, uint32_t l, uint32_t h)
{
    RangeSuffix ** p = &root;
    for (;;)
    {
        if (*p == NULL)
        {
            *p = new RangeSuffix(l, h);
            break;
        }
        else if ((*p)->l == l && (*p)->h == h)
        {
            break;
        }
        else
            p = &(*p)->next;
    }
}

/*
 * Now that we have catenation of word ranges [l1-h1],[l2-h2],
 * we want to add it to existing range, merging suffixes on the fly.
 */
void UTF16addContinuous2(RangeSuffix * & root, uint32_t l_ld, uint32_t h_ld, uint32_t l_tr, uint32_t h_tr)
{
    RangeSuffix ** p = &root;
    for (;;)
    {
        if (*p == NULL)
        {
            *p = new RangeSuffix(l_tr, h_tr);
            p = &(*p)->child;
            break;
        }
        else if ((*p)->l == l_tr && (*p)->h == h_tr)
        {
            p = &(*p)->child;
            break;
        }
        else
            p = &(*p)->next;
    }
    for (;;)
    {
        if (*p == NULL)
        {
            *p = new RangeSuffix(l_ld, h_ld);
            break;
        }
        else if ((*p)->l == l_ld && (*p)->h == h_ld)
        {
            break;
        }
        else
            p = &(*p)->next;
    }
}

/*
 * Split range into sub-ranges that agree on leading surrogates.
 *
 * We have two Unicode runes, L and H, both map to UTF-16
 * surrogate pairs 'L1 L2' and 'H1 H2'.
 * We want to represent Unicode range [L - H] as a catenation
 * of word ranges [L1 - H1],[L2 - H2].
 *
 * This is only possible if the following condition holds:
 * if L1 /= H1, then L2 == 0xdc00 and H2 == 0xdfff.
 * This condition ensures that:
 *  1) all possible UTF-16 sequences between L and H are allowed
 *  2) no word ranges [w1 - w2] appear, such that w1 > w2
 *
 * E.g.:
 * [\U00010001-\U00010400] => [d800-d801],[dc01-dc00].
 * The last word range, [dc01-dc00], is incorrect: its lower bound
 * is greater than its upper bound. To fix this, we must split
 * the original range into two sub-ranges:
 * [\U00010001-\U000103ff] => [d800-d800],[dc01-dfff]
 * [\U00010400-\U00010400] => [d801-d801],[dc00-dc00]
 *
 * This function finds all such 'points of discontinuity'
 * and represents original range as alternation of continuous
 * sub-ranges.
 */
void UTF16splitByContinuity(RangeSuffix * & root, uint32_t l_ld, uint32_t h_ld, uint32_t l_tr, uint32_t h_tr)
{
    if (l_ld != h_ld)
    {
        if (l_tr > utf16::MIN_TRAIL_SURR)
        {
            UTF16splitByContinuity(root, l_ld, l_ld, l_tr, utf16::MAX_TRAIL_SURR);
            UTF16splitByContinuity(root, l_ld + 1, h_ld, utf16::MIN_TRAIL_SURR, h_tr);
            return;
        }
        if (h_tr < utf16::MAX_TRAIL_SURR)
        {
            UTF16splitByContinuity(root, l_ld, h_ld - 1, l_tr, utf16::MAX_TRAIL_SURR);
            UTF16splitByContinuity(root, h_ld, h_ld, utf16::MIN_TRAIL_SURR, h_tr);
            return;
        }
    }
    UTF16addContinuous2(root, l_ld, h_ld, l_tr, h_tr);
}

/*
 * Split range into sub-ranges, so that all runes in the same
 * sub-range have equal length of UTF-16 sequence. E.g., full
 * Unicode range [0-0x10FFFF] gets split into sub-ranges:
 * [0 - 0xFFFF]         (2-byte UTF-16 sequences)
 * [0x10000 - 0x10FFFF] (4-byte UTF-16 sequences)
 */
void UTF16splitByRuneLength(RangeSuffix * & root, utf16::rune l, utf16::rune h)
{
    if (l <= utf16::MAX_1WORD_RUNE)
    {
        if (h <= utf16::MAX_1WORD_RUNE)
        {
            UTF16addContinuous1(root, l, h);
        }
        else
        {
            UTF16addContinuous1(root, l, utf16::MAX_1WORD_RUNE);
            const uint32_t h_ld = utf16::lead_surr(h);
            const uint32_t h_tr = utf16::trail_surr(h);
            UTF16splitByContinuity(root, utf16::MIN_LEAD_SURR, h_ld, utf16::MIN_TRAIL_SURR, h_tr);
        }
    }
    else
    {
            const uint32_t l_ld = utf16::lead_surr(l);
            const uint32_t l_tr = utf16::trail_surr(l);
            const uint32_t h_ld = utf16::lead_surr(h);
            const uint32_t h_tr = utf16::trail_surr(h);
            UTF16splitByContinuity(root, l_ld, h_ld, l_tr, h_tr);
    }
}

} // namespace re2c