1// © 2016 and later: Unicode, Inc. and others.
2// License & terms of use: http://www.unicode.org/copyright.html
3/*
4 **********************************************************************
5 *   Copyright (C) 1999-2011, International Business Machines
6 *   Corporation and others.  All Rights Reserved.
7 **********************************************************************
8 *   Date        Name        Description
9 *   11/17/99    aliu        Creation.
10 **********************************************************************
11 */
12
13#include "unicode/utypes.h"
14
15#if !UCONFIG_NO_TRANSLITERATION
16
17#include "unicode/unistr.h"
18#include "unicode/uniset.h"
19#include "unicode/utf16.h"
20#include "rbt_set.h"
21#include "rbt_rule.h"
22#include "cmemory.h"
23#include "putilimp.h"
24
25U_CDECL_BEGIN
26static void U_CALLCONV _deleteRule(void *rule) {
27    delete (icu::TransliterationRule *)rule;
28}
29U_CDECL_END
30
31//----------------------------------------------------------------------
32// BEGIN Debugging support
33//----------------------------------------------------------------------
34
35// #define DEBUG_RBT
36
37#ifdef DEBUG_RBT
38#include <stdio.h>
39#include "charstr.h"
40
41/**
42 * @param appendTo result is appended to this param.
43 * @param input the string being transliterated
44 * @param pos the index struct
45 */
46static UnicodeString& _formatInput(UnicodeString &appendTo,
47                                   const UnicodeString& input,
48                                   const UTransPosition& pos) {
49    // Output a string of the form aaa{bbb|ccc|ddd}eee, where
50    // the {} indicate the context start and limit, and the ||
51    // indicate the start and limit.
52    if (0 <= pos.contextStart &&
53        pos.contextStart <= pos.start &&
54        pos.start <= pos.limit &&
55        pos.limit <= pos.contextLimit &&
56        pos.contextLimit <= input.length()) {
57
58        UnicodeString a, b, c, d, e;
59        input.extractBetween(0, pos.contextStart, a);
60        input.extractBetween(pos.contextStart, pos.start, b);
61        input.extractBetween(pos.start, pos.limit, c);
62        input.extractBetween(pos.limit, pos.contextLimit, d);
63        input.extractBetween(pos.contextLimit, input.length(), e);
64        appendTo.append(a).append((UChar)123/*{*/).append(b).
65            append((UChar)124/*|*/).append(c).append((UChar)124/*|*/).append(d).
66            append((UChar)125/*}*/).append(e);
67    } else {
68        appendTo.append("INVALID UTransPosition");
69        //appendTo.append((UnicodeString)"INVALID UTransPosition {cs=" +
70        //                pos.contextStart + ", s=" + pos.start + ", l=" +
71        //                pos.limit + ", cl=" + pos.contextLimit + "} on " +
72        //                input);
73    }
74    return appendTo;
75}
76
77// Append a hex string to the target
78UnicodeString& _appendHex(uint32_t number,
79                          int32_t digits,
80                          UnicodeString& target) {
81    static const UChar digitString[] = {
82        0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39,
83        0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0
84    };
85    while (digits--) {
86        target += digitString[(number >> (digits*4)) & 0xF];
87    }
88    return target;
89}
90
91// Replace nonprintable characters with unicode escapes
92UnicodeString& _escape(const UnicodeString &source,
93                       UnicodeString &target) {
94    for (int32_t i = 0; i < source.length(); ) {
95        UChar32 ch = source.char32At(i);
96        i += U16_LENGTH(ch);
97        if (ch < 0x09 || (ch > 0x0A && ch < 0x20)|| ch > 0x7E) {
98            if (ch <= 0xFFFF) {
99                target += "\\u";
100                _appendHex(ch, 4, target);
101            } else {
102                target += "\\U";
103                _appendHex(ch, 8, target);
104            }
105        } else {
106            target += ch;
107        }
108    }
109    return target;
110}
111
112inline void _debugOut(const char* msg, TransliterationRule* rule,
113                      const Replaceable& theText, UTransPosition& pos) {
114    UnicodeString buf(msg, "");
115    if (rule) {
116        UnicodeString r;
117        rule->toRule(r, TRUE);
118        buf.append((UChar)32).append(r);
119    }
120    buf.append(UnicodeString(" => ", ""));
121    UnicodeString* text = (UnicodeString*)&theText;
122    _formatInput(buf, *text, pos);
123    UnicodeString esc;
124    _escape(buf, esc);
125    CharString cbuf(esc);
126    printf("%s\n", (const char*) cbuf);
127}
128
129#else
130#define _debugOut(msg, rule, theText, pos)
131#endif
132
133//----------------------------------------------------------------------
134// END Debugging support
135//----------------------------------------------------------------------
136
137// Fill the precontext and postcontext with the patterns of the rules
138// that are masking one another.
139static void maskingError(const icu::TransliterationRule& rule1,
140                         const icu::TransliterationRule& rule2,
141                         UParseError& parseError) {
142    icu::UnicodeString r;
143    int32_t len;
144
145    parseError.line = parseError.offset = -1;
146
147    // for pre-context
148    rule1.toRule(r, FALSE);
149    len = uprv_min(r.length(), U_PARSE_CONTEXT_LEN-1);
150    r.extract(0, len, parseError.preContext);
151    parseError.preContext[len] = 0;
152
153    //for post-context
154    r.truncate(0);
155    rule2.toRule(r, FALSE);
156    len = uprv_min(r.length(), U_PARSE_CONTEXT_LEN-1);
157    r.extract(0, len, parseError.postContext);
158    parseError.postContext[len] = 0;
159}
160
161U_NAMESPACE_BEGIN
162
163/**
164 * Construct a new empty rule set.
165 */
166TransliterationRuleSet::TransliterationRuleSet(UErrorCode& status) : UMemory() {
167    ruleVector = new UVector(&_deleteRule, NULL, status);
168    if (U_FAILURE(status)) {
169        return;
170    }
171    if (ruleVector == NULL) {
172        status = U_MEMORY_ALLOCATION_ERROR;
173    }
174    rules = NULL;
175    maxContextLength = 0;
176}
177
178/**
179 * Copy constructor.
180 */
181TransliterationRuleSet::TransliterationRuleSet(const TransliterationRuleSet& other) :
182    UMemory(other),
183    ruleVector(0),
184    rules(0),
185    maxContextLength(other.maxContextLength) {
186
187    int32_t i, len;
188    uprv_memcpy(index, other.index, sizeof(index));
189    UErrorCode status = U_ZERO_ERROR;
190    ruleVector = new UVector(&_deleteRule, NULL, status);
191    if (other.ruleVector != 0 && ruleVector != 0 && U_SUCCESS(status)) {
192        len = other.ruleVector->size();
193        for (i=0; i<len && U_SUCCESS(status); ++i) {
194            TransliterationRule *tempTranslitRule = new TransliterationRule(*(TransliterationRule*)other.ruleVector->elementAt(i));
195            // Null pointer test
196            if (tempTranslitRule == NULL) {
197                status = U_MEMORY_ALLOCATION_ERROR;
198                break;
199            }
200            ruleVector->addElement(tempTranslitRule, status);
201            if (U_FAILURE(status)) {
202                break;
203            }
204        }
205    }
206    if (other.rules != 0 && U_SUCCESS(status)) {
207        UParseError p;
208        freeze(p, status);
209    }
210}
211
212/**
213 * Destructor.
214 */
215TransliterationRuleSet::~TransliterationRuleSet() {
216    delete ruleVector; // This deletes the contained rules
217    uprv_free(rules);
218}
219
220void TransliterationRuleSet::setData(const TransliterationRuleData* d) {
221    /**
222     * We assume that the ruleset has already been frozen.
223     */
224    int32_t len = index[256]; // see freeze()
225    for (int32_t i=0; i<len; ++i) {
226        rules[i]->setData(d);
227    }
228}
229
230/**
231 * Return the maximum context length.
232 * @return the length of the longest preceding context.
233 */
234int32_t TransliterationRuleSet::getMaximumContextLength(void) const {
235    return maxContextLength;
236}
237
238/**
239 * Add a rule to this set.  Rules are added in order, and order is
240 * significant.  The last call to this method must be followed by
241 * a call to <code>freeze()</code> before the rule set is used.
242 *
243 * <p>If freeze() has already been called, calling addRule()
244 * unfreezes the rules, and freeze() must be called again.
245 *
246 * @param adoptedRule the rule to add
247 */
248void TransliterationRuleSet::addRule(TransliterationRule* adoptedRule,
249                                     UErrorCode& status) {
250    if (U_FAILURE(status)) {
251        delete adoptedRule;
252        return;
253    }
254    ruleVector->addElement(adoptedRule, status);
255
256    int32_t len;
257    if ((len = adoptedRule->getContextLength()) > maxContextLength) {
258        maxContextLength = len;
259    }
260
261    uprv_free(rules);
262    rules = 0;
263}
264
265/**
266 * Check this for masked rules and index it to optimize performance.
267 * The sequence of operations is: (1) add rules to a set using
268 * <code>addRule()</code>; (2) freeze the set using
269 * <code>freeze()</code>; (3) use the rule set.  If
270 * <code>addRule()</code> is called after calling this method, it
271 * invalidates this object, and this method must be called again.
272 * That is, <code>freeze()</code> may be called multiple times,
273 * although for optimal performance it shouldn't be.
274 */
275void TransliterationRuleSet::freeze(UParseError& parseError,UErrorCode& status) {
276    /* Construct the rule array and index table.  We reorder the
277     * rules by sorting them into 256 bins.  Each bin contains all
278     * rules matching the index value for that bin.  A rule
279     * matches an index value if string whose first key character
280     * has a low byte equal to the index value can match the rule.
281     *
282     * Each bin contains zero or more rules, in the same order
283     * they were found originally.  However, the total rules in
284     * the bins may exceed the number in the original vector,
285     * since rules that have a variable as their first key
286     * character will generally fall into more than one bin.
287     *
288     * That is, each bin contains all rules that either have that
289     * first index value as their first key character, or have
290     * a set containing the index value as their first character.
291     */
292    int32_t n = ruleVector->size();
293    int32_t j;
294    int16_t x;
295    UVector v(2*n, status); // heuristic; adjust as needed
296
297    if (U_FAILURE(status)) {
298        return;
299    }
300
301    /* Precompute the index values.  This saves a LOT of time.
302     * Be careful not to call malloc(0).
303     */
304    int16_t* indexValue = (int16_t*) uprv_malloc( sizeof(int16_t) * (n > 0 ? n : 1) );
305    /* test for NULL */
306    if (indexValue == 0) {
307        status = U_MEMORY_ALLOCATION_ERROR;
308        return;
309    }
310    for (j=0; j<n; ++j) {
311        TransliterationRule* r = (TransliterationRule*) ruleVector->elementAt(j);
312        indexValue[j] = r->getIndexValue();
313    }
314    for (x=0; x<256; ++x) {
315        index[x] = v.size();
316        for (j=0; j<n; ++j) {
317            if (indexValue[j] >= 0) {
318                if (indexValue[j] == x) {
319                    v.addElement(ruleVector->elementAt(j), status);
320                }
321            } else {
322                // If the indexValue is < 0, then the first key character is
323                // a set, and we must use the more time-consuming
324                // matchesIndexValue check.  In practice this happens
325                // rarely, so we seldom tread this code path.
326                TransliterationRule* r = (TransliterationRule*) ruleVector->elementAt(j);
327                if (r->matchesIndexValue((uint8_t)x)) {
328                    v.addElement(r, status);
329                }
330            }
331        }
332    }
333    uprv_free(indexValue);
334    index[256] = v.size();
335
336    /* Freeze things into an array.
337     */
338    uprv_free(rules); // Contains alias pointers
339
340    /* You can't do malloc(0)! */
341    if (v.size() == 0) {
342        rules = NULL;
343        return;
344    }
345    rules = (TransliterationRule **)uprv_malloc(v.size() * sizeof(TransliterationRule *));
346    /* test for NULL */
347    if (rules == 0) {
348        status = U_MEMORY_ALLOCATION_ERROR;
349        return;
350    }
351    for (j=0; j<v.size(); ++j) {
352        rules[j] = (TransliterationRule*) v.elementAt(j);
353    }
354
355    // TODO Add error reporting that indicates the rules that
356    //      are being masked.
357    //UnicodeString errors;
358
359    /* Check for masking.  This is MUCH faster than our old check,
360     * which was each rule against each following rule, since we
361     * only have to check for masking within each bin now.  It's
362     * 256*O(n2^2) instead of O(n1^2), where n1 is the total rule
363     * count, and n2 is the per-bin rule count.  But n2<<n1, so
364     * it's a big win.
365     */
366    for (x=0; x<256; ++x) {
367        for (j=index[x]; j<index[x+1]-1; ++j) {
368            TransliterationRule* r1 = rules[j];
369            for (int32_t k=j+1; k<index[x+1]; ++k) {
370                TransliterationRule* r2 = rules[k];
371                if (r1->masks(*r2)) {
372//|                 if (errors == null) {
373//|                     errors = new StringBuffer();
374//|                 } else {
375//|                     errors.append("\n");
376//|                 }
377//|                 errors.append("Rule " + r1 + " masks " + r2);
378                    status = U_RULE_MASK_ERROR;
379                    maskingError(*r1, *r2, parseError);
380                    return;
381                }
382            }
383        }
384    }
385
386    //if (errors != null) {
387    //    throw new IllegalArgumentException(errors.toString());
388    //}
389}
390
391/**
392 * Transliterate the given text with the given UTransPosition
393 * indices.  Return TRUE if the transliteration should continue
394 * or FALSE if it should halt (because of a U_PARTIAL_MATCH match).
395 * Note that FALSE is only ever returned if isIncremental is TRUE.
396 * @param text the text to be transliterated
397 * @param pos the position indices, which will be updated
398 * @param incremental if TRUE, assume new text may be inserted
399 * at index.limit, and return FALSE if thre is a partial match.
400 * @return TRUE unless a U_PARTIAL_MATCH has been obtained,
401 * indicating that transliteration should stop until more text
402 * arrives.
403 */
404UBool TransliterationRuleSet::transliterate(Replaceable& text,
405                                            UTransPosition& pos,
406                                            UBool incremental) {
407    int16_t indexByte = (int16_t) (text.char32At(pos.start) & 0xFF);
408    for (int32_t i=index[indexByte]; i<index[indexByte+1]; ++i) {
409        UMatchDegree m = rules[i]->matchAndReplace(text, pos, incremental);
410        switch (m) {
411        case U_MATCH:
412            _debugOut("match", rules[i], text, pos);
413            return TRUE;
414        case U_PARTIAL_MATCH:
415            _debugOut("partial match", rules[i], text, pos);
416            return FALSE;
417        default: /* Ram: added default to make GCC happy */
418            break;
419        }
420    }
421    // No match or partial match from any rule
422    pos.start += U16_LENGTH(text.char32At(pos.start));
423    _debugOut("no match", NULL, text, pos);
424    return TRUE;
425}
426
427/**
428 * Create rule strings that represents this rule set.
429 */
430UnicodeString& TransliterationRuleSet::toRules(UnicodeString& ruleSource,
431                                               UBool escapeUnprintable) const {
432    int32_t i;
433    int32_t count = ruleVector->size();
434    ruleSource.truncate(0);
435    for (i=0; i<count; ++i) {
436        if (i != 0) {
437            ruleSource.append((UChar) 0x000A /*\n*/);
438        }
439        TransliterationRule *r =
440            (TransliterationRule*) ruleVector->elementAt(i);
441        r->toRule(ruleSource, escapeUnprintable);
442    }
443    return ruleSource;
444}
445
446/**
447 * Return the set of all characters that may be modified
448 * (getTarget=false) or emitted (getTarget=true) by this set.
449 */
450UnicodeSet& TransliterationRuleSet::getSourceTargetSet(UnicodeSet& result,
451                               UBool getTarget) const
452{
453    result.clear();
454    int32_t count = ruleVector->size();
455    for (int32_t i=0; i<count; ++i) {
456        TransliterationRule* r =
457            (TransliterationRule*) ruleVector->elementAt(i);
458        if (getTarget) {
459            r->addTargetSetTo(result);
460        } else {
461            r->addSourceSetTo(result);
462        }
463    }
464    return result;
465}
466
467U_NAMESPACE_END
468
469#endif /* #if !UCONFIG_NO_TRANSLITERATION */
470