1/*
2 **********************************************************************
3 *   Copyright (C) 2002-2010, International Business Machines
4 *   Corporation and others.  All Rights Reserved.
5 **********************************************************************
6 */
7
8/*
9 * paragraphLayout doesn't make much sense without
10 * BreakIterator...
11 */
12#include "layout/LETypes.h"
13#include "layout/LEScripts.h"
14#include "layout/LELanguages.h"
15#include "layout/LayoutEngine.h"
16#include "layout/LEFontInstance.h"
17
18#include "unicode/ubidi.h"
19#include "unicode/uchriter.h"
20#include "unicode/brkiter.h"
21
22#if ! UCONFIG_NO_BREAK_ITERATION
23#include "LXUtilities.h"
24#include "usc_impl.h" /* this is currently private! */
25#include "cstring.h"  /* this too! */
26
27#include "layout/ParagraphLayout.h"
28
29U_NAMESPACE_BEGIN
30
31#define ARRAY_SIZE(array) (sizeof array  / sizeof array[0])
32
33/* Leave this copyright notice here! It needs to go somewhere in this library. */
34static const char copyright[] = U_COPYRIGHT_STRING;
35
36class StyleRuns
37{
38public:
39    StyleRuns(const RunArray *styleRunArrays[], le_int32 styleCount);
40
41    ~StyleRuns();
42
43    le_int32 getRuns(le_int32 runLimits[], le_int32 styleIndices[]);
44
45private:
46    le_int32 fStyleCount;
47    le_int32 fRunCount;
48
49    le_int32 *fRunLimits;
50    le_int32 *fStyleIndices;
51};
52
53StyleRuns::StyleRuns(const RunArray *styleRunArrays[], le_int32 styleCount)
54    : fStyleCount(styleCount), fRunCount(0), fRunLimits(NULL), fStyleIndices(NULL)
55{
56    le_int32 maxRunCount = 0;
57    le_int32 style, run, runStyle;
58    le_int32 *currentRun = LE_NEW_ARRAY(le_int32, styleCount);
59
60    for (int i = 0; i < styleCount; i += 1) {
61        maxRunCount += styleRunArrays[i]->getCount();
62    }
63
64    maxRunCount -= styleCount - 1;
65
66    fRunLimits    = LE_NEW_ARRAY(le_int32, maxRunCount);
67    fStyleIndices = LE_NEW_ARRAY(le_int32, maxRunCount * styleCount);
68
69    for (style = 0; style < styleCount; style += 1) {
70        currentRun[style] = 0;
71    }
72
73    run = 0;
74    runStyle = 0;
75
76    /*
77     * Since the last run limit for each style run must be
78     * the same, all the styles will hit the last limit at
79     * the same time, so we know when we're done when the first
80     * style hits the last limit.
81     */
82    while (currentRun[0] < styleRunArrays[0]->getCount()) {
83        fRunLimits[run] = 0x7FFFFFFF;
84
85        // find the minimum run limit for all the styles
86        for (style = 0; style < styleCount; style += 1) {
87            if (styleRunArrays[style]->getLimit(currentRun[style]) < fRunLimits[run]) {
88                fRunLimits[run] = styleRunArrays[style]->getLimit(currentRun[style]);
89            }
90        }
91
92        // advance all styles whose current run is at this limit to the next run
93        for (style = 0; style < styleCount; style += 1) {
94            fStyleIndices[runStyle++] = currentRun[style];
95
96            if (styleRunArrays[style]->getLimit(currentRun[style]) == fRunLimits[run]) {
97                currentRun[style] += 1;
98            }
99        }
100
101        run += 1;
102    }
103
104    fRunCount = run;
105    LE_DELETE_ARRAY(currentRun);
106}
107
108StyleRuns::~StyleRuns()
109{
110    fRunCount = 0;
111
112    LE_DELETE_ARRAY(fStyleIndices);
113    fStyleIndices = NULL;
114
115    LE_DELETE_ARRAY(fRunLimits);
116    fRunLimits = NULL;
117}
118
119le_int32 StyleRuns::getRuns(le_int32 runLimits[], le_int32 styleIndices[])
120{
121    if (runLimits != NULL) {
122        LE_ARRAY_COPY(runLimits, fRunLimits, fRunCount);
123    }
124
125    if (styleIndices != NULL) {
126        LE_ARRAY_COPY(styleIndices, fStyleIndices, fRunCount * fStyleCount);
127    }
128
129    return fRunCount;
130}
131
132/*
133 * NOTE: This table only has "TRUE" values for
134 * those scripts which the LayoutEngine can currently
135 * process, rather for all scripts which require
136 * complex processing for correct rendering.
137 */
138static const le_bool complexTable[scriptCodeCount] = {
139    FALSE , /* Zyyy */
140    FALSE,  /* Qaai */
141    TRUE,   /* Arab */
142    FALSE,  /* Armn */
143    TRUE,   /* Beng */
144    FALSE,  /* Bopo */
145    FALSE,  /* Cher */
146    FALSE,  /* Copt=Qaac */
147    FALSE,  /* Cyrl */
148    FALSE,  /* Dsrt */
149    TRUE,   /* Deva */
150    FALSE,  /* Ethi */
151    FALSE,  /* Geor */
152    FALSE,  /* Goth */
153    FALSE,  /* Grek */
154    TRUE,   /* Gujr */
155    TRUE,   /* Guru */
156    FALSE,  /* Hani */
157    FALSE,  /* Hang */
158    TRUE,   /* Hebr */
159    FALSE,  /* Hira */
160    TRUE,   /* Knda */
161    FALSE,  /* Kana */
162    FALSE,  /* Khmr */
163    FALSE,  /* Laoo */
164    FALSE,  /* Latn */
165    TRUE,   /* Mlym */
166    FALSE,  /* Mong */
167    FALSE,  /* Mymr */
168    FALSE,  /* Ogam */
169    FALSE,  /* Ital */
170    TRUE,   /* Orya */
171    FALSE,  /* Runr */
172    FALSE,  /* Sinh */
173    FALSE,  /* Syrc */
174    TRUE,   /* Taml */
175    TRUE,   /* Telu */
176    FALSE,  /* Thaa */
177    TRUE,   /* Thai */
178    FALSE,  /* Tibt */
179    FALSE,  /* Cans */
180    FALSE,  /* Yiii */
181    FALSE,  /* Tglg */
182    FALSE,  /* Hano */
183    FALSE,  /* Buhd */
184    FALSE,  /* Tagb */
185    FALSE,  /* Brai */
186    FALSE,  /* Cprt */
187    FALSE,  /* Limb */
188    FALSE,  /* Linb */
189    FALSE,  /* Osma */
190    FALSE,  /* Shaw */
191    FALSE,  /* Tale */
192    FALSE,  /* Ugar */
193    FALSE,  /* Hrkt */
194    FALSE,  /* Bugi */
195    FALSE,  /* Glag */
196    FALSE,  /* Khar */
197    FALSE,  /* Sylo */
198    FALSE,  /* Talu */
199    FALSE,  /* Tfng */
200    FALSE,  /* Xpeo */
201    FALSE,  /* Bali */
202    FALSE,  /* Batk */
203    FALSE,  /* Blis */
204    FALSE,  /* Brah */
205    FALSE,  /* Cham */
206    FALSE,  /* Cirt */
207    FALSE,  /* Cyrs */
208    FALSE,  /* Egyd */
209    FALSE,  /* Egyh */
210    FALSE,  /* Egyp */
211    FALSE,  /* Geok */
212    FALSE,  /* Hans */
213    FALSE,  /* Hant */
214    FALSE,  /* Hmng */
215    FALSE,  /* Hung */
216    FALSE,  /* Inds */
217    FALSE,  /* Java */
218    FALSE,  /* Kali */
219    FALSE,  /* Latf */
220    FALSE,  /* Latg */
221    FALSE,  /* Lepc */
222    FALSE,  /* Lina */
223    FALSE,  /* Mand */
224    FALSE,  /* Maya */
225    FALSE,  /* Mero */
226    FALSE,  /* Nkoo */
227    FALSE,  /* Orkh */
228    FALSE,  /* Perm */
229    FALSE,  /* Phag */
230    FALSE,  /* Phnx */
231    FALSE,  /* Plrd */
232    FALSE,  /* Roro */
233    FALSE,  /* Sara */
234    FALSE,  /* Syre */
235    FALSE,  /* Syrj */
236    FALSE,  /* Syrn */
237    FALSE,  /* Teng */
238    FALSE,  /* Taii */
239    FALSE,  /* Visp */
240    FALSE,  /* Xsux */
241    FALSE,  /* Zxxx */
242    FALSE,  /* Zzzz */
243    FALSE,  /* Cari */
244    FALSE,  /* Jpan */
245    FALSE,  /* Lana */
246    FALSE,  /* Lyci */
247    FALSE,  /* Lydi */
248    FALSE,  /* Olck */
249    FALSE,  /* Rjng */
250    FALSE,  /* Saur */
251    FALSE,  /* Sgnw */
252    FALSE,  /* Sund */
253    FALSE,  /* Moon */
254    FALSE,  /* Mtei */
255    FALSE,  /* Armi */
256    FALSE,  /* Avst */
257    FALSE,  /* Cakm */
258    FALSE,  /* Kore */
259    FALSE,  /* Kthi */
260    FALSE,  /* Mani */
261    FALSE,  /* Phli */
262    FALSE,  /* Phlp */
263    FALSE,  /* Phlv */
264    FALSE,  /* Prti */
265    FALSE,  /* Samr */
266    FALSE,  /* Tavt */
267    FALSE,  /* Zmth */
268    FALSE,  /* Zsym */
269    FALSE,  /* Bamu */
270    FALSE,  /* Lisu */
271    FALSE,  /* Nkgb */
272    FALSE   /* Sarb */
273};
274
275
276const char ParagraphLayout::fgClassID = 0;
277
278/*
279 * How to deal with composite fonts:
280 *
281 * Don't store the client's FontRuns; we'll need to compute sub-font FontRuns using Doug's
282 * LEFontInstance method. Do that by intersecting the client's FontRuns with fScriptRuns. Use
283 * that to compute fFontRuns, and then intersect fFontRuns, fScriptRuns and fLevelRuns. Doing
284 * it in this order means we do a two-way intersection and a three-way intersection.
285 *
286 * An optimization would be to only do this if there's at least one composite font...
287 *
288 * Other notes:
289 *
290 * * Return the sub-fonts as the run fonts... could keep the mapping back to the client's FontRuns
291 *   but that probably makes it more complicated of everyone...
292 *
293 * * Take the LineInfo and LineRun types from Paragraph and use them here, incorporate them into the API.
294 *
295 * * Might want to change the name of the StyleRun type, and make a new one that holds fonts, scripts and levels?
296 *
297 */
298ParagraphLayout::ParagraphLayout(const LEUnicode chars[], le_int32 count,
299                                 const FontRuns   *fontRuns,
300                                 const ValueRuns  *levelRuns,
301                                 const ValueRuns  *scriptRuns,
302                                 const LocaleRuns *localeRuns,
303                                 UBiDiLevel paragraphLevel, le_bool vertical,
304                                 LEErrorCode &status)
305                                 : fChars(chars), fCharCount(count),
306                                   fFontRuns(NULL), fLevelRuns(levelRuns), fScriptRuns(scriptRuns), fLocaleRuns(localeRuns),
307                                   fVertical(vertical), fClientLevels(TRUE), fClientScripts(TRUE), fClientLocales(TRUE), fEmbeddingLevels(NULL),
308                                   fAscent(0), fDescent(0), fLeading(0),
309                                   fGlyphToCharMap(NULL), fCharToMinGlyphMap(NULL), fCharToMaxGlyphMap(NULL), fGlyphWidths(NULL), fGlyphCount(0),
310                                   fParaBidi(NULL), fLineBidi(NULL),
311                                   fStyleRunLimits(NULL), fStyleIndices(NULL), fStyleRunCount(0),
312                                   fBreakIterator(NULL), fLineStart(-1), fLineEnd(0),
313                                 /*fVisualRuns(NULL), fStyleRunInfo(NULL), fVisualRunCount(-1),
314                                   fFirstVisualRun(-1), fLastVisualRun(-1),*/ fVisualRunLastX(0), fVisualRunLastY(0)
315{
316
317    if (LE_FAILURE(status)) {
318        fCharCount = -1;
319        return;
320    }
321
322    // FIXME: should check the limit arrays for consistency...
323
324    computeLevels(paragraphLevel);
325
326    if (scriptRuns == NULL) {
327        computeScripts();
328    }
329
330    if (localeRuns == NULL) {
331        computeLocales();
332    }
333
334    computeSubFonts(fontRuns, status);
335
336    if (LE_FAILURE(status)) {
337        //other stuff?
338        fCharCount = -1;
339        return;
340    }
341
342    // now intersect the font, direction and script runs...
343    const RunArray *styleRunArrays[] = {fFontRuns, fLevelRuns, fScriptRuns, fLocaleRuns};
344    le_int32  styleCount = sizeof styleRunArrays / sizeof styleRunArrays[0];
345    StyleRuns styleRuns(styleRunArrays, styleCount);
346    LEErrorCode layoutStatus = LE_NO_ERROR;
347
348    fStyleRunCount = styleRuns.getRuns(NULL, NULL);
349
350    fStyleRunLimits = LE_NEW_ARRAY(le_int32, fStyleRunCount);
351    fStyleIndices   = LE_NEW_ARRAY(le_int32, fStyleRunCount * styleCount);
352    if ((fStyleRunLimits == NULL) || (fStyleIndices == NULL)) {
353        status = LE_MEMORY_ALLOCATION_ERROR;
354        return;
355    }
356
357    styleRuns.getRuns(fStyleRunLimits, fStyleIndices);
358
359    // now build a LayoutEngine for each style run...
360    le_int32 *styleIndices = fStyleIndices;
361    le_int32 run, runStart;
362
363    fStyleRunInfo = LE_NEW_ARRAY(StyleRunInfo, fStyleRunCount);
364    if (fStyleRunInfo == NULL) {
365        status = LE_MEMORY_ALLOCATION_ERROR;
366        return;
367    }
368    else {
369        // initialize
370        for (runStart = 0, run = 0; run < fStyleRunCount; run += 1) {
371            fStyleRunInfo[run].font = NULL;
372            fStyleRunInfo[run].runBase = 0;
373            fStyleRunInfo[run].runLimit = 0;
374            fStyleRunInfo[run].script = (UScriptCode)0;
375            fStyleRunInfo[run].locale = NULL;
376            fStyleRunInfo[run].level = 0;
377            fStyleRunInfo[run].glyphBase = 0;
378            fStyleRunInfo[run].engine = NULL;
379            fStyleRunInfo[run].glyphCount = 0;
380            fStyleRunInfo[run].glyphs = NULL;
381            fStyleRunInfo[run].positions = NULL;
382        }
383    }
384
385    fGlyphCount = 0;
386    for (runStart = 0, run = 0; run < fStyleRunCount; run += 1) {
387        fStyleRunInfo[run].font      = fFontRuns->getFont(styleIndices[0]);
388        fStyleRunInfo[run].runBase   = runStart;
389        fStyleRunInfo[run].runLimit  = fStyleRunLimits[run];
390        fStyleRunInfo[run].script    = (UScriptCode) fScriptRuns->getValue(styleIndices[2]);
391        fStyleRunInfo[run].locale    = fLocaleRuns->getLocale(styleIndices[3]);
392        fStyleRunInfo[run].level     = (UBiDiLevel) fLevelRuns->getValue(styleIndices[1]);
393        fStyleRunInfo[run].glyphBase = fGlyphCount;
394
395        fStyleRunInfo[run].engine = LayoutEngine::layoutEngineFactory(fStyleRunInfo[run].font,
396            fStyleRunInfo[run].script, getLanguageCode(fStyleRunInfo[run].locale), layoutStatus);
397        if (LE_FAILURE(layoutStatus)) {
398            status = layoutStatus;
399            return;
400        }
401
402        fStyleRunInfo[run].glyphCount = fStyleRunInfo[run].engine->layoutChars(fChars, runStart, fStyleRunLimits[run] - runStart, fCharCount,
403            fStyleRunInfo[run].level & 1, 0, 0, layoutStatus);
404        if (LE_FAILURE(layoutStatus)) {
405            status = layoutStatus;
406            return;
407        }
408
409        runStart = fStyleRunLimits[run];
410        styleIndices += styleCount;
411        fGlyphCount += fStyleRunInfo[run].glyphCount;
412    }
413
414    // Make big arrays for the glyph widths, glyph-to-char and char-to-glyph maps,
415    // in logical order. (Both maps need an extra entry for the end of the text.)
416    //
417    // For each layout get the positions and convert them into glyph widths, in
418    // logical order. Get the glyph-to-char mapping, offset by starting index in the
419    // character array. Swap the glyph width and glyph-to-char arrays into logical order.
420    // Finally, fill in the char-to-glyph mappings.
421    fGlyphWidths       = LE_NEW_ARRAY(float, fGlyphCount);
422    fGlyphToCharMap    = LE_NEW_ARRAY(le_int32, fGlyphCount + 1);
423    fCharToMinGlyphMap = LE_NEW_ARRAY(le_int32, fCharCount + 1);
424    fCharToMaxGlyphMap = LE_NEW_ARRAY(le_int32, fCharCount + 1);
425    if ((fGlyphWidths == NULL) || (fGlyphToCharMap == NULL) ||
426        (fCharToMinGlyphMap == NULL) || (fCharToMaxGlyphMap == NULL)) {
427        status = LE_MEMORY_ALLOCATION_ERROR;
428        return;
429    }
430
431    le_int32 glyph;
432
433    for (runStart = 0, run = 0; run < fStyleRunCount; run += 1) {
434        LayoutEngine *engine = fStyleRunInfo[run].engine;
435        le_int32 glyphCount  = fStyleRunInfo[run].glyphCount;
436        le_int32 glyphBase   = fStyleRunInfo[run].glyphBase;
437
438        fStyleRunInfo[run].glyphs = LE_NEW_ARRAY(LEGlyphID, glyphCount);
439        fStyleRunInfo[run].positions = LE_NEW_ARRAY(float, glyphCount * 2 + 2);
440        if ((fStyleRunInfo[run].glyphs == NULL) ||
441            (fStyleRunInfo[run].positions == NULL)) {
442            status = LE_MEMORY_ALLOCATION_ERROR;
443            return;
444        }
445
446        engine->getGlyphs(fStyleRunInfo[run].glyphs, layoutStatus);
447        if (LE_FAILURE(layoutStatus)) {
448            status = layoutStatus;
449            return;
450        }
451
452        engine->getGlyphPositions(fStyleRunInfo[run].positions, layoutStatus);
453        if (LE_FAILURE(layoutStatus)) {
454            status = layoutStatus;
455            return;
456        }
457
458        engine->getCharIndices(&fGlyphToCharMap[glyphBase], runStart, layoutStatus);
459        if (LE_FAILURE(layoutStatus)) {
460            status = layoutStatus;
461            return;
462        }
463
464        for (glyph = 0; glyph < glyphCount; glyph += 1) {
465            fGlyphWidths[glyphBase + glyph] = fStyleRunInfo[run].positions[glyph * 2 + 2] - fStyleRunInfo[run].positions[glyph * 2];
466        }
467
468        if ((fStyleRunInfo[run].level & 1) != 0) {
469            LXUtilities::reverse(&fGlyphWidths[glyphBase], glyphCount);
470            LXUtilities::reverse(&fGlyphToCharMap[glyphBase], glyphCount);
471        }
472
473        runStart = fStyleRunLimits[run];
474
475        delete engine;
476        fStyleRunInfo[run].engine = NULL;
477    }
478
479    fGlyphToCharMap[fGlyphCount] = fCharCount;
480
481    for (glyph = fGlyphCount - 1; glyph >= 0; glyph -= 1) {
482        le_int32 ch = fGlyphToCharMap[glyph];
483
484        fCharToMinGlyphMap[ch] = glyph;
485    }
486
487    fCharToMinGlyphMap[fCharCount] = fGlyphCount;
488
489    for (glyph = 0; glyph < fGlyphCount; glyph += 1) {
490        le_int32 ch = fGlyphToCharMap[glyph];
491
492        fCharToMaxGlyphMap[ch] = glyph;
493    }
494
495    fCharToMaxGlyphMap[fCharCount] = fGlyphCount;
496}
497
498ParagraphLayout::~ParagraphLayout()
499{
500    delete (FontRuns *) fFontRuns;
501
502    if (! fClientLevels) {
503        delete (ValueRuns *) fLevelRuns;
504        fLevelRuns = NULL;
505
506        fClientLevels = TRUE;
507    }
508
509    if (! fClientScripts) {
510        delete (ValueRuns *) fScriptRuns;
511        fScriptRuns = NULL;
512
513        fClientScripts = TRUE;
514    }
515
516    if (! fClientLocales) {
517        delete (LocaleRuns *) fLocaleRuns;
518        fLocaleRuns = NULL;
519
520        fClientLocales = TRUE;
521    }
522
523    if (fEmbeddingLevels != NULL) {
524        LE_DELETE_ARRAY(fEmbeddingLevels);
525        fEmbeddingLevels = NULL;
526    }
527
528    if (fGlyphToCharMap != NULL) {
529        LE_DELETE_ARRAY(fGlyphToCharMap);
530        fGlyphToCharMap = NULL;
531    }
532
533    if (fCharToMinGlyphMap != NULL) {
534        LE_DELETE_ARRAY(fCharToMinGlyphMap);
535        fCharToMinGlyphMap = NULL;
536    }
537
538    if (fCharToMaxGlyphMap != NULL) {
539        LE_DELETE_ARRAY(fCharToMaxGlyphMap);
540        fCharToMaxGlyphMap = NULL;
541    }
542
543    if (fGlyphWidths != NULL) {
544        LE_DELETE_ARRAY(fGlyphWidths);
545        fGlyphWidths = NULL;
546    }
547
548    if (fParaBidi != NULL) {
549        ubidi_close(fParaBidi);
550        fParaBidi = NULL;
551    }
552
553    if (fLineBidi != NULL) {
554        ubidi_close(fLineBidi);
555        fLineBidi = NULL;
556    }
557
558    if (fStyleRunCount > 0) {
559        le_int32 run;
560
561        LE_DELETE_ARRAY(fStyleRunLimits);
562        LE_DELETE_ARRAY(fStyleIndices);
563
564        for (run = 0; run < fStyleRunCount; run += 1) {
565            LE_DELETE_ARRAY(fStyleRunInfo[run].glyphs);
566            LE_DELETE_ARRAY(fStyleRunInfo[run].positions);
567
568            fStyleRunInfo[run].glyphs    = NULL;
569            fStyleRunInfo[run].positions = NULL;
570        }
571
572        LE_DELETE_ARRAY(fStyleRunInfo);
573
574        fStyleRunLimits = NULL;
575        fStyleIndices   = NULL;
576        fStyleRunInfo        = NULL;
577        fStyleRunCount  = 0;
578    }
579
580    if (fBreakIterator != NULL) {
581        delete fBreakIterator;
582        fBreakIterator = NULL;
583    }
584}
585
586
587le_bool ParagraphLayout::isComplex(const LEUnicode chars[], le_int32 count)
588{
589    UErrorCode scriptStatus = U_ZERO_ERROR;
590    UScriptCode scriptCode  = USCRIPT_INVALID_CODE;
591    UScriptRun *sr = uscript_openRun(chars, count, &scriptStatus);
592    le_bool result = FALSE;
593
594    while (uscript_nextRun(sr, NULL, NULL, &scriptCode)) {
595        if (isComplex(scriptCode)) {
596            result = TRUE;
597            break;
598        }
599    }
600
601    uscript_closeRun(sr);
602    return result;
603}
604
605le_int32 ParagraphLayout::getAscent() const
606{
607    if (fAscent <= 0 && fCharCount > 0) {
608        ((ParagraphLayout *) this)->computeMetrics();
609    }
610
611    return fAscent;
612}
613
614le_int32 ParagraphLayout::getDescent() const
615{
616    if (fAscent <= 0 && fCharCount > 0) {
617        ((ParagraphLayout *) this)->computeMetrics();
618    }
619
620    return fDescent;
621}
622
623le_int32 ParagraphLayout::getLeading() const
624{
625    if (fAscent <= 0 && fCharCount > 0) {
626        ((ParagraphLayout *) this)->computeMetrics();
627    }
628
629    return fLeading;
630}
631
632le_bool ParagraphLayout::isDone() const
633{
634    return fLineEnd >= fCharCount;
635}
636
637ParagraphLayout::Line *ParagraphLayout::nextLine(float width)
638{
639    if (isDone()) {
640        return NULL;
641    }
642
643    fLineStart = fLineEnd;
644
645    if (width > 0) {
646        le_int32 glyph    = fCharToMinGlyphMap[fLineStart];
647        float widthSoFar  = 0;
648
649        while (glyph < fGlyphCount && widthSoFar + fGlyphWidths[glyph] <= width) {
650            widthSoFar += fGlyphWidths[glyph++];
651        }
652
653        // If no glyphs fit on the line, force one to fit.
654        //
655        // (There shouldn't be any zero width glyphs at the
656        // start of a line unless the paragraph consists of
657        // only zero width glyphs, because otherwise the zero
658        // width glyphs will have been included on the end of
659        // the previous line...)
660        if (widthSoFar == 0 && glyph < fGlyphCount) {
661            glyph += 1;
662        }
663
664        fLineEnd = previousBreak(fGlyphToCharMap[glyph]);
665
666        // If this break is at or before the last one,
667        // find a glyph, starting at the one which didn't
668        // fit, that produces a break after the last one.
669        while (fLineEnd <= fLineStart) {
670            fLineEnd = fGlyphToCharMap[glyph++];
671        }
672    } else {
673        fLineEnd = fCharCount;
674    }
675
676    return computeVisualRuns();
677}
678
679void ParagraphLayout::computeLevels(UBiDiLevel paragraphLevel)
680{
681    UErrorCode bidiStatus = U_ZERO_ERROR;
682
683    if (fLevelRuns != NULL) {
684        le_int32 ch;
685        le_int32 run;
686
687        fEmbeddingLevels = LE_NEW_ARRAY(UBiDiLevel, fCharCount);
688
689        for (ch = 0, run = 0; run < fLevelRuns->getCount(); run += 1) {
690            UBiDiLevel runLevel = (UBiDiLevel) fLevelRuns->getValue(run) | UBIDI_LEVEL_OVERRIDE;
691            le_int32   runLimit = fLevelRuns->getLimit(run);
692
693            while (ch < runLimit) {
694                fEmbeddingLevels[ch++] = runLevel;
695            }
696        }
697    }
698
699    fParaBidi = ubidi_openSized(fCharCount, 0, &bidiStatus);
700    ubidi_setPara(fParaBidi, fChars, fCharCount, paragraphLevel, fEmbeddingLevels, &bidiStatus);
701
702    if (fLevelRuns == NULL) {
703        le_int32 levelRunCount = ubidi_countRuns(fParaBidi, &bidiStatus);
704        ValueRuns *levelRuns = new ValueRuns(levelRunCount);
705
706        le_int32 logicalStart = 0;
707        le_int32 run;
708        le_int32 limit;
709        UBiDiLevel level;
710
711        for (run = 0; run < levelRunCount; run += 1) {
712            ubidi_getLogicalRun(fParaBidi, logicalStart, &limit, &level);
713            levelRuns->add(level, limit);
714            logicalStart = limit;
715        }
716
717        fLevelRuns    = levelRuns;
718        fClientLevels = FALSE;
719    }
720}
721
722void ParagraphLayout::computeScripts()
723{
724    UErrorCode scriptStatus = U_ZERO_ERROR;
725    UScriptRun *sr = uscript_openRun(fChars, fCharCount, &scriptStatus);
726    ValueRuns  *scriptRuns = new ValueRuns(0);
727    le_int32 limit;
728    UScriptCode script;
729
730    while (uscript_nextRun(sr, NULL, &limit, &script)) {
731        scriptRuns->add(script, limit);
732    }
733
734    uscript_closeRun(sr);
735
736    fScriptRuns    = scriptRuns;
737    fClientScripts = FALSE;
738}
739
740void ParagraphLayout::computeLocales()
741{
742    LocaleRuns *localeRuns = new LocaleRuns(0);
743    const Locale *defaultLocale = &Locale::getDefault();
744
745    localeRuns->add(defaultLocale, fCharCount);
746
747    fLocaleRuns    = localeRuns;
748    fClientLocales = FALSE;
749}
750
751void ParagraphLayout::computeSubFonts(const FontRuns *fontRuns, LEErrorCode &status)
752{
753    if (LE_FAILURE(status)) {
754        return;
755    }
756
757    const RunArray *styleRunArrays[] = {fontRuns, fScriptRuns};
758    le_int32 styleCount = sizeof styleRunArrays / sizeof styleRunArrays[0];
759    StyleRuns styleRuns(styleRunArrays, styleCount);
760    le_int32 styleRunCount = styleRuns.getRuns(NULL, NULL);
761    le_int32 *styleRunLimits = LE_NEW_ARRAY(le_int32, styleRunCount);
762    le_int32 *styleIndices = LE_NEW_ARRAY(le_int32, styleRunCount * styleCount);
763    FontRuns *subFontRuns  = new FontRuns(0);
764    le_int32  run, offset, *si;
765
766    styleRuns.getRuns(styleRunLimits, styleIndices);
767
768    si = styleIndices;
769    offset = 0;
770
771    for (run = 0; run < styleRunCount; run += 1) {
772        const LEFontInstance *runFont = fontRuns->getFont(si[0]);
773        le_int32 script = fScriptRuns->getValue(si[1]);
774
775        while (offset < styleRunLimits[run]) {
776            const LEFontInstance *subFont = runFont->getSubFont(fChars, &offset, styleRunLimits[run], script, status);
777
778            if (LE_FAILURE(status)) {
779                delete subFontRuns;
780                goto cleanUp;
781            }
782
783            subFontRuns->add(subFont, offset);
784        }
785
786        si += styleCount;
787    }
788
789    fFontRuns = subFontRuns;
790
791cleanUp:
792    LE_DELETE_ARRAY(styleIndices);
793    LE_DELETE_ARRAY(styleRunLimits);
794}
795
796void ParagraphLayout::computeMetrics()
797{
798    le_int32 i, count = fFontRuns->getCount();
799    le_int32 maxDL = 0;
800
801    for (i = 0; i < count; i += 1) {
802        const LEFontInstance *font = fFontRuns->getFont(i);
803        le_int32 ascent  = font->getAscent();
804        le_int32 descent = font->getDescent();
805        le_int32 leading = font->getLeading();
806        le_int32 dl      = descent + leading;
807
808        if (ascent > fAscent) {
809            fAscent = ascent;
810        }
811
812        if (descent > fDescent) {
813            fDescent = descent;
814        }
815
816        if (leading > fLeading) {
817            fLeading = leading;
818        }
819
820        if (dl > maxDL) {
821            maxDL = dl;
822        }
823    }
824
825    fLeading = maxDL - fDescent;
826}
827
828#if 1
829struct LanguageMap
830{
831    const char *localeCode;
832    le_int32 languageCode;
833};
834
835static const LanguageMap languageMap[] =
836{
837    {"afr", afkLanguageCode}, // Afrikaans
838    {"ara", araLanguageCode}, // Arabic
839    {"asm", asmLanguageCode}, // Assamese
840    {"bel", belLanguageCode}, // Belarussian
841    {"ben", benLanguageCode}, // Bengali
842    {"bod", tibLanguageCode}, // Tibetan
843    {"bul", bgrLanguageCode}, // Bulgarian
844    {"cat", catLanguageCode}, // Catalan
845    {"ces", csyLanguageCode}, // Czech
846    {"che", cheLanguageCode}, // Chechen
847    {"cop", copLanguageCode}, // Coptic
848    {"cym", welLanguageCode}, // Welsh
849    {"dan", danLanguageCode}, // Danish
850    {"deu", deuLanguageCode}, // German
851    {"dzo", dznLanguageCode}, // Dzongkha
852    {"ell", ellLanguageCode}, // Greek
853    {"eng", engLanguageCode}, // English
854    {"est", etiLanguageCode}, // Estonian
855    {"eus", euqLanguageCode}, // Basque
856    {"fas", farLanguageCode}, // Farsi
857    {"fin", finLanguageCode}, // Finnish
858    {"fra", fraLanguageCode}, // French
859    {"gle", gaeLanguageCode}, // Irish Gaelic
860    {"guj", gujLanguageCode}, // Gujarati
861    {"hau", hauLanguageCode}, // Hausa
862    {"heb", iwrLanguageCode}, // Hebrew
863    {"hin", hinLanguageCode}, // Hindi
864    {"hrv", hrvLanguageCode}, // Croatian
865    {"hun", hunLanguageCode}, // Hungarian
866    {"hye", hyeLanguageCode}, // Armenian
867    {"ind", indLanguageCode}, // Indonesian
868    {"ita", itaLanguageCode}, // Italian
869    {"jpn", janLanguageCode}, // Japanese
870    {"kan", kanLanguageCode}, // Kannada
871    {"kas", kshLanguageCode}, // Kashmiri
872    {"khm", khmLanguageCode}, // Khmer
873    {"kok", kokLanguageCode}, // Konkani
874    {"kor", korLanguageCode}, // Korean
875//  {"mal_XXX", malLanguageCode}, // Malayalam - Traditional
876    {"mal", mlrLanguageCode}, // Malayalam - Reformed
877    {"mar", marLanguageCode}, // Marathi
878    {"mlt", mtsLanguageCode}, // Maltese
879    {"mni", mniLanguageCode}, // Manipuri
880    {"mon", mngLanguageCode}, // Mongolian
881    {"nep", nepLanguageCode}, // Nepali
882    {"ori", oriLanguageCode}, // Oriya
883    {"pol", plkLanguageCode}, // Polish
884    {"por", ptgLanguageCode}, // Portuguese
885    {"pus", pasLanguageCode}, // Pashto
886    {"ron", romLanguageCode}, // Romanian
887    {"rus", rusLanguageCode}, // Russian
888    {"san", sanLanguageCode}, // Sanskrit
889    {"sin", snhLanguageCode}, // Sinhalese
890    {"slk", skyLanguageCode}, // Slovak
891    {"snd", sndLanguageCode}, // Sindhi
892    {"slv", slvLanguageCode}, // Slovenian
893    {"spa", espLanguageCode}, // Spanish
894    {"sqi", sqiLanguageCode}, // Albanian
895    {"srp", srbLanguageCode}, // Serbian
896    {"swe", sveLanguageCode}, // Swedish
897    {"syr", syrLanguageCode}, // Syriac
898    {"tam", tamLanguageCode}, // Tamil
899    {"tel", telLanguageCode}, // Telugu
900    {"tha", thaLanguageCode}, // Thai
901    {"tur", trkLanguageCode}, // Turkish
902    {"urd", urdLanguageCode}, // Urdu
903    {"yid", jiiLanguageCode}, // Yiddish
904//  {"zhp", zhpLanguageCode}, // Chinese - Phonetic
905    {"zho", zhsLanguageCode}, // Chinese
906    {"zho_CHN", zhsLanguageCode}, // Chinese - China
907    {"zho_HKG", zhsLanguageCode}, // Chinese - Hong Kong
908    {"zho_MAC", zhtLanguageCode}, // Chinese - Macao
909    {"zho_SGP", zhsLanguageCode}, // Chinese - Singapore
910    {"zho_TWN", zhtLanguageCode}  // Chinese - Taiwan
911};
912
913static const le_int32 languageMapCount = ARRAY_SIZE(languageMap);
914
915le_int32 ParagraphLayout::getLanguageCode(const Locale *locale)
916{
917    char code[8] = {0, 0, 0, 0, 0, 0, 0, 0};
918    const char *language = locale->getISO3Language();
919    const char *country  = locale->getISO3Country();
920
921    uprv_strcat(code, language);
922
923    if ((uprv_strcmp(language, "zho") == 0) && country != NULL) {
924        uprv_strcat(code, "_");
925        uprv_strcat(code, country);
926    }
927
928    for (le_int32 i = 0; i < languageMapCount; i += 1) {
929        if (uprv_strcmp(code, languageMap[i].localeCode) == 0) {
930            return languageMap[i].languageCode;
931        }
932    }
933
934    return nullLanguageCode;
935}
936#else
937
938// TODO - dummy implementation for right now...
939le_int32 ParagraphLayout::getLanguageCode(const Locale *locale)
940{
941    return nullLanguageCode;
942}
943#endif
944
945le_bool ParagraphLayout::isComplex(UScriptCode script)
946{
947    if (script < 0 || script >= (UScriptCode) scriptCodeCount) {
948        return FALSE;
949    }
950
951    return complexTable[script];
952}
953
954le_int32 ParagraphLayout::previousBreak(le_int32 charIndex)
955{
956    // skip over any whitespace or control characters,
957    // because they can hang in the margin.
958    while (charIndex < fCharCount &&
959           (u_isWhitespace(fChars[charIndex]) ||
960            u_iscntrl(fChars[charIndex]))) {
961        charIndex += 1;
962    }
963
964    // Create the BreakIterator if we don't already have one
965    if (fBreakIterator == NULL) {
966        Locale thai("th");
967        UCharCharacterIterator *iter = new UCharCharacterIterator(fChars, fCharCount);
968        UErrorCode status = U_ZERO_ERROR;
969
970        fBreakIterator = BreakIterator::createLineInstance(thai, status);
971        fBreakIterator->adoptText(iter);
972    }
973
974    // return the break location that's at or before
975    // the character we stopped on. Note: if we're
976    // on a break, the "+ 1" will cause preceding to
977    // back up to it.
978    return fBreakIterator->preceding(charIndex + 1);
979}
980
981ParagraphLayout::Line *ParagraphLayout::computeVisualRuns()
982{
983    UErrorCode bidiStatus = U_ZERO_ERROR;
984    le_int32 dirRunCount, visualRun;
985
986    fVisualRunLastX = 0;
987    fVisualRunLastY = 0;
988    fFirstVisualRun = getCharRun(fLineStart);
989    fLastVisualRun  = getCharRun(fLineEnd - 1);
990
991    if (fLineBidi == NULL) {
992        fLineBidi = ubidi_openSized(fCharCount, 0, &bidiStatus);
993    }
994
995    ubidi_setLine(fParaBidi, fLineStart, fLineEnd, fLineBidi, &bidiStatus);
996    dirRunCount = ubidi_countRuns(fLineBidi, &bidiStatus);
997
998    Line *line = new Line();
999
1000    for (visualRun = 0; visualRun < dirRunCount; visualRun += 1) {
1001        le_int32 relStart, run, runLength;
1002        UBiDiDirection runDirection = ubidi_getVisualRun(fLineBidi, visualRun, &relStart, &runLength);
1003        le_int32 runStart = fLineStart + relStart;
1004        le_int32 runEnd   = runStart + runLength - 1;
1005        le_int32 firstRun = getCharRun(runStart);
1006        le_int32 lastRun  = getCharRun(runEnd);
1007        le_int32 startRun = (runDirection == UBIDI_LTR)? firstRun : lastRun;
1008        le_int32 stopRun  = (runDirection == UBIDI_LTR)? lastRun + 1 : firstRun - 1;
1009        le_int32 dir      = (runDirection == UBIDI_LTR)?  1 : -1;
1010
1011        for (run = startRun; run != stopRun; run += dir) {
1012            le_int32 firstChar = (run == firstRun)? runStart : fStyleRunInfo[run].runBase;
1013            le_int32 lastChar  = (run == lastRun)?  runEnd   : fStyleRunInfo[run].runLimit - 1;
1014
1015            appendRun(line, run, firstChar, lastChar);
1016        }
1017    }
1018
1019    return line;
1020}
1021
1022void ParagraphLayout::appendRun(ParagraphLayout::Line *line, le_int32 run, le_int32 firstChar, le_int32 lastChar)
1023{
1024    le_int32 glyphBase = fStyleRunInfo[run].glyphBase;
1025    le_int32 inGlyph, outGlyph;
1026
1027    // Get the glyph indices for all the characters between firstChar and lastChar,
1028    // make the minimum one be leftGlyph and the maximum one be rightGlyph.
1029    // (need to do this to handle local reorderings like Indic left matras)
1030    le_int32 leftGlyph  = fGlyphCount;
1031    le_int32 rightGlyph = -1;
1032    le_int32 ch;
1033
1034    for (ch = firstChar; ch <= lastChar; ch += 1) {
1035        le_int32 minGlyph = fCharToMinGlyphMap[ch];
1036        le_int32 maxGlyph = fCharToMaxGlyphMap[ch];
1037
1038        if (minGlyph < leftGlyph) {
1039            leftGlyph = minGlyph;
1040        }
1041
1042        if (maxGlyph > rightGlyph) {
1043            rightGlyph = maxGlyph;
1044        }
1045    }
1046
1047    if ((fStyleRunInfo[run].level & 1) != 0) {
1048        le_int32 swap = rightGlyph;
1049        le_int32 last = glyphBase + fStyleRunInfo[run].glyphCount - 1;
1050
1051        // Here, we want to remove the glyphBase bias...
1052        rightGlyph = last - leftGlyph;
1053        leftGlyph  = last - swap;
1054    } else {
1055        rightGlyph -= glyphBase;
1056        leftGlyph  -= glyphBase;
1057    }
1058
1059    // Set the position bias for the glyphs. If we're at the start of
1060    // a line, we want the first glyph to be at x = 0, even if it comes
1061    // from the middle of a layout. If we've got a right-to-left run, we
1062    // want the left-most glyph to start at the final x position of the
1063    // previous run, even though this glyph may be in the middle of the
1064    // run.
1065    fVisualRunLastX -= fStyleRunInfo[run].positions[leftGlyph * 2];
1066
1067    // Make rightGlyph be the glyph just to the right of
1068    // the run's glyphs
1069    rightGlyph += 1;
1070
1071    UBiDiDirection direction  = ((fStyleRunInfo[run].level & 1) == 0)? UBIDI_LTR : UBIDI_RTL;
1072    le_int32   glyphCount     = rightGlyph - leftGlyph;
1073    LEGlyphID *glyphs         = LE_NEW_ARRAY(LEGlyphID, glyphCount);
1074    float     *positions      = LE_NEW_ARRAY(float, glyphCount * 2 + 2);
1075    le_int32  *glyphToCharMap = LE_NEW_ARRAY(le_int32, glyphCount);
1076
1077    LE_ARRAY_COPY(glyphs, &fStyleRunInfo[run].glyphs[leftGlyph], glyphCount);
1078
1079    for (outGlyph = 0, inGlyph = leftGlyph * 2; inGlyph <= rightGlyph * 2; inGlyph += 2, outGlyph += 2) {
1080        positions[outGlyph]     = fStyleRunInfo[run].positions[inGlyph] + fVisualRunLastX;
1081        positions[outGlyph + 1] = fStyleRunInfo[run].positions[inGlyph + 1] + fVisualRunLastY;
1082    }
1083
1084    // Save the ending position of this run
1085    // to use for the start of the next run
1086    fVisualRunLastX = positions[outGlyph - 2];
1087    fVisualRunLastY = positions[outGlyph - 1];
1088
1089    if ((fStyleRunInfo[run].level & 1) == 0) {
1090        for (outGlyph = 0, inGlyph = leftGlyph; inGlyph < rightGlyph; inGlyph += 1, outGlyph += 1) {
1091            glyphToCharMap[outGlyph] = fGlyphToCharMap[glyphBase + inGlyph];
1092        }
1093    } else {
1094        // Because fGlyphToCharMap is stored in logical order to facilitate line breaking,
1095        // we need to map the physical glyph indices to logical indices while we copy the
1096        // character indices.
1097        le_int32 base = glyphBase + fStyleRunInfo[run].glyphCount - 1;
1098
1099        for (outGlyph = 0, inGlyph = leftGlyph; inGlyph < rightGlyph; inGlyph += 1, outGlyph += 1) {
1100            glyphToCharMap[outGlyph] = fGlyphToCharMap[base - inGlyph];
1101        }
1102    }
1103
1104    line->append(fStyleRunInfo[run].font, direction, glyphCount, glyphs, positions, glyphToCharMap);
1105}
1106
1107le_int32 ParagraphLayout::getCharRun(le_int32 charIndex)
1108{
1109    if (charIndex < 0 || charIndex > fCharCount) {
1110        return -1;
1111    }
1112
1113    le_int32 run;
1114
1115    // NOTE: as long as fStyleRunLimits is well-formed
1116    // the above range check guarantees that we'll never
1117    // fall off the end of the array.
1118    run = 0;
1119    while (charIndex >= fStyleRunLimits[run]) {
1120        run += 1;
1121    }
1122
1123    return run;
1124}
1125
1126
1127const char ParagraphLayout::Line::fgClassID = 0;
1128
1129#define INITIAL_RUN_CAPACITY 4
1130#define RUN_CAPACITY_GROW_LIMIT 16
1131
1132ParagraphLayout::Line::~Line()
1133{
1134    le_int32 i;
1135
1136    for (i = 0; i < fRunCount; i += 1) {
1137        delete fRuns[i];
1138    }
1139
1140    LE_DELETE_ARRAY(fRuns);
1141}
1142
1143le_int32 ParagraphLayout::Line::getAscent() const
1144{
1145    if (fAscent <= 0) {
1146        ((ParagraphLayout::Line *)this)->computeMetrics();
1147    }
1148
1149    return fAscent;
1150}
1151
1152le_int32 ParagraphLayout::Line::getDescent() const
1153{
1154    if (fAscent <= 0) {
1155        ((ParagraphLayout::Line *)this)->computeMetrics();
1156    }
1157
1158    return fDescent;
1159}
1160
1161le_int32 ParagraphLayout::Line::getLeading() const
1162{
1163    if (fAscent <= 0) {
1164        ((ParagraphLayout::Line *)this)->computeMetrics();
1165    }
1166
1167    return fLeading;
1168}
1169
1170le_int32 ParagraphLayout::Line::getWidth() const
1171{
1172    const VisualRun *lastRun = getVisualRun(fRunCount - 1);
1173
1174    if (lastRun == NULL) {
1175        return 0;
1176    }
1177
1178    le_int32 glyphCount = lastRun->getGlyphCount();
1179    const float *positions = lastRun->getPositions();
1180
1181    return (le_int32) positions[glyphCount * 2];
1182}
1183
1184const ParagraphLayout::VisualRun *ParagraphLayout::Line::getVisualRun(le_int32 runIndex) const
1185{
1186    if (runIndex < 0 || runIndex >= fRunCount) {
1187        return NULL;
1188    }
1189
1190    return fRuns[runIndex];
1191}
1192
1193void ParagraphLayout::Line::append(const LEFontInstance *font, UBiDiDirection direction, le_int32 glyphCount,
1194                                   const LEGlyphID glyphs[], const float positions[], const le_int32 glyphToCharMap[])
1195{
1196    if (fRunCount >= fRunCapacity) {
1197        if (fRunCapacity == 0) {
1198            fRunCapacity = INITIAL_RUN_CAPACITY;
1199            fRuns = LE_NEW_ARRAY(ParagraphLayout::VisualRun *, fRunCapacity);
1200        } else {
1201            fRunCapacity += (fRunCapacity < RUN_CAPACITY_GROW_LIMIT? fRunCapacity : RUN_CAPACITY_GROW_LIMIT);
1202            fRuns = (ParagraphLayout::VisualRun **) LE_GROW_ARRAY(fRuns, fRunCapacity);
1203        }
1204    }
1205
1206    fRuns[fRunCount++] = new ParagraphLayout::VisualRun(font, direction, glyphCount, glyphs, positions, glyphToCharMap);
1207}
1208
1209void ParagraphLayout::Line::computeMetrics()
1210{
1211    le_int32 maxDL = 0;
1212
1213    for (le_int32 i = 0; i < fRunCount; i += 1) {
1214        le_int32 ascent  = fRuns[i]->getAscent();
1215        le_int32 descent = fRuns[i]->getDescent();
1216        le_int32 leading = fRuns[i]->getLeading();
1217        le_int32 dl      = descent + leading;
1218
1219        if (ascent > fAscent) {
1220            fAscent = ascent;
1221        }
1222
1223        if (descent > fDescent) {
1224            fDescent = descent;
1225        }
1226
1227        if (leading > fLeading) {
1228            fLeading = leading;
1229        }
1230
1231        if (dl > maxDL) {
1232            maxDL = dl;
1233        }
1234    }
1235
1236    fLeading = maxDL - fDescent;
1237}
1238
1239const char ParagraphLayout::VisualRun::fgClassID = 0;
1240
1241ParagraphLayout::VisualRun::~VisualRun()
1242{
1243    LE_DELETE_ARRAY(fGlyphToCharMap);
1244    LE_DELETE_ARRAY(fPositions);
1245    LE_DELETE_ARRAY(fGlyphs);
1246}
1247
1248U_NAMESPACE_END
1249
1250#endif
1251
1252