1/*
2 **********************************************************************
3 *   Copyright (C) 2002-2009, 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};
270
271
272const char ParagraphLayout::fgClassID = 0;
273
274/*
275 * How to deal with composite fonts:
276 *
277 * Don't store the client's FontRuns; we'll need to compute sub-font FontRuns using Doug's
278 * LEFontInstance method. Do that by intersecting the client's FontRuns with fScriptRuns. Use
279 * that to compute fFontRuns, and then intersect fFontRuns, fScriptRuns and fLevelRuns. Doing
280 * it in this order means we do a two-way intersection and a three-way intersection.
281 *
282 * An optimization would be to only do this if there's at least one composite font...
283 *
284 * Other notes:
285 *
286 * * Return the sub-fonts as the run fonts... could keep the mapping back to the client's FontRuns
287 *   but that probably makes it more complicated of everyone...
288 *
289 * * Take the LineInfo and LineRun types from Paragraph and use them here, incorporate them into the API.
290 *
291 * * Might want to change the name of the StyleRun type, and make a new one that holds fonts, scripts and levels?
292 *
293 */
294ParagraphLayout::ParagraphLayout(const LEUnicode chars[], le_int32 count,
295                                 const FontRuns   *fontRuns,
296                                 const ValueRuns  *levelRuns,
297                                 const ValueRuns  *scriptRuns,
298                                 const LocaleRuns *localeRuns,
299                                 UBiDiLevel paragraphLevel, le_bool vertical,
300                                 LEErrorCode &status)
301                                 : fChars(chars), fCharCount(count),
302                                   fFontRuns(NULL), fLevelRuns(levelRuns), fScriptRuns(scriptRuns), fLocaleRuns(localeRuns),
303                                   fVertical(vertical), fClientLevels(TRUE), fClientScripts(TRUE), fClientLocales(TRUE), fEmbeddingLevels(NULL),
304                                   fAscent(0), fDescent(0), fLeading(0),
305                                   fGlyphToCharMap(NULL), fCharToMinGlyphMap(NULL), fCharToMaxGlyphMap(NULL), fGlyphWidths(NULL), fGlyphCount(0),
306                                   fParaBidi(NULL), fLineBidi(NULL),
307                                   fStyleRunLimits(NULL), fStyleIndices(NULL), fStyleRunCount(0),
308                                   fBreakIterator(NULL), fLineStart(-1), fLineEnd(0),
309                                 /*fVisualRuns(NULL), fStyleRunInfo(NULL), fVisualRunCount(-1),
310                                   fFirstVisualRun(-1), fLastVisualRun(-1),*/ fVisualRunLastX(0), fVisualRunLastY(0)
311{
312
313    if (LE_FAILURE(status)) {
314        fCharCount = -1;
315        return;
316    }
317
318    // FIXME: should check the limit arrays for consistency...
319
320    computeLevels(paragraphLevel);
321
322    if (scriptRuns == NULL) {
323        computeScripts();
324    }
325
326    if (localeRuns == NULL) {
327        computeLocales();
328    }
329
330    computeSubFonts(fontRuns, status);
331
332    if (LE_FAILURE(status)) {
333        //other stuff?
334        fCharCount = -1;
335        return;
336    }
337
338    // now intersect the font, direction and script runs...
339    const RunArray *styleRunArrays[] = {fFontRuns, fLevelRuns, fScriptRuns, fLocaleRuns};
340    le_int32  styleCount = sizeof styleRunArrays / sizeof styleRunArrays[0];
341    StyleRuns styleRuns(styleRunArrays, styleCount);
342    LEErrorCode layoutStatus = LE_NO_ERROR;
343
344    fStyleRunCount = styleRuns.getRuns(NULL, NULL);
345
346    fStyleRunLimits = LE_NEW_ARRAY(le_int32, fStyleRunCount);
347    fStyleIndices   = LE_NEW_ARRAY(le_int32, fStyleRunCount * styleCount);
348    if ((fStyleRunLimits == NULL) || (fStyleIndices == NULL)) {
349        status = LE_MEMORY_ALLOCATION_ERROR;
350        return;
351    }
352
353    styleRuns.getRuns(fStyleRunLimits, fStyleIndices);
354
355    // now build a LayoutEngine for each style run...
356    le_int32 *styleIndices = fStyleIndices;
357    le_int32 run, runStart;
358
359    fStyleRunInfo = LE_NEW_ARRAY(StyleRunInfo, fStyleRunCount);
360    if (fStyleRunInfo == NULL) {
361        status = LE_MEMORY_ALLOCATION_ERROR;
362        return;
363    }
364    else {
365        // initialize
366        for (runStart = 0, run = 0; run < fStyleRunCount; run += 1) {
367            fStyleRunInfo[run].font = NULL;
368            fStyleRunInfo[run].runBase = 0;
369            fStyleRunInfo[run].runLimit = 0;
370            fStyleRunInfo[run].script = (UScriptCode)0;
371            fStyleRunInfo[run].locale = NULL;
372            fStyleRunInfo[run].level = 0;
373            fStyleRunInfo[run].glyphBase = 0;
374            fStyleRunInfo[run].engine = NULL;
375            fStyleRunInfo[run].glyphCount = 0;
376            fStyleRunInfo[run].glyphs = NULL;
377            fStyleRunInfo[run].positions = NULL;
378        }
379    }
380
381    fGlyphCount = 0;
382    for (runStart = 0, run = 0; run < fStyleRunCount; run += 1) {
383        fStyleRunInfo[run].font      = fFontRuns->getFont(styleIndices[0]);
384        fStyleRunInfo[run].runBase   = runStart;
385        fStyleRunInfo[run].runLimit  = fStyleRunLimits[run];
386        fStyleRunInfo[run].script    = (UScriptCode) fScriptRuns->getValue(styleIndices[2]);
387        fStyleRunInfo[run].locale    = fLocaleRuns->getLocale(styleIndices[3]);
388        fStyleRunInfo[run].level     = (UBiDiLevel) fLevelRuns->getValue(styleIndices[1]);
389        fStyleRunInfo[run].glyphBase = fGlyphCount;
390
391        fStyleRunInfo[run].engine = LayoutEngine::layoutEngineFactory(fStyleRunInfo[run].font,
392            fStyleRunInfo[run].script, getLanguageCode(fStyleRunInfo[run].locale), layoutStatus);
393        if (LE_FAILURE(layoutStatus)) {
394            status = layoutStatus;
395            return;
396        }
397
398        fStyleRunInfo[run].glyphCount = fStyleRunInfo[run].engine->layoutChars(fChars, runStart, fStyleRunLimits[run] - runStart, fCharCount,
399            fStyleRunInfo[run].level & 1, 0, 0, layoutStatus);
400        if (LE_FAILURE(layoutStatus)) {
401            status = layoutStatus;
402            return;
403        }
404
405        runStart = fStyleRunLimits[run];
406        styleIndices += styleCount;
407        fGlyphCount += fStyleRunInfo[run].glyphCount;
408    }
409
410    // Make big arrays for the glyph widths, glyph-to-char and char-to-glyph maps,
411    // in logical order. (Both maps need an extra entry for the end of the text.)
412    //
413    // For each layout get the positions and convert them into glyph widths, in
414    // logical order. Get the glyph-to-char mapping, offset by starting index in the
415    // character array. Swap the glyph width and glyph-to-char arrays into logical order.
416    // Finally, fill in the char-to-glyph mappings.
417    fGlyphWidths       = LE_NEW_ARRAY(float, fGlyphCount);
418    fGlyphToCharMap    = LE_NEW_ARRAY(le_int32, fGlyphCount + 1);
419    fCharToMinGlyphMap = LE_NEW_ARRAY(le_int32, fCharCount + 1);
420    fCharToMaxGlyphMap = LE_NEW_ARRAY(le_int32, fCharCount + 1);
421    if ((fGlyphWidths == NULL) || (fGlyphToCharMap == NULL) ||
422        (fCharToMinGlyphMap == NULL) || (fCharToMaxGlyphMap == NULL)) {
423        status = LE_MEMORY_ALLOCATION_ERROR;
424        return;
425    }
426
427    le_int32 glyph;
428
429    for (runStart = 0, run = 0; run < fStyleRunCount; run += 1) {
430        LayoutEngine *engine = fStyleRunInfo[run].engine;
431        le_int32 glyphCount  = fStyleRunInfo[run].glyphCount;
432        le_int32 glyphBase   = fStyleRunInfo[run].glyphBase;
433
434        fStyleRunInfo[run].glyphs = LE_NEW_ARRAY(LEGlyphID, glyphCount);
435        fStyleRunInfo[run].positions = LE_NEW_ARRAY(float, glyphCount * 2 + 2);
436        if ((fStyleRunInfo[run].glyphs == NULL) ||
437            (fStyleRunInfo[run].positions == NULL)) {
438            status = LE_MEMORY_ALLOCATION_ERROR;
439            return;
440        }
441
442        engine->getGlyphs(fStyleRunInfo[run].glyphs, layoutStatus);
443        if (LE_FAILURE(layoutStatus)) {
444            status = layoutStatus;
445            return;
446        }
447
448        engine->getGlyphPositions(fStyleRunInfo[run].positions, layoutStatus);
449        if (LE_FAILURE(layoutStatus)) {
450            status = layoutStatus;
451            return;
452        }
453
454        engine->getCharIndices(&fGlyphToCharMap[glyphBase], runStart, layoutStatus);
455        if (LE_FAILURE(layoutStatus)) {
456            status = layoutStatus;
457            return;
458        }
459
460        for (glyph = 0; glyph < glyphCount; glyph += 1) {
461            fGlyphWidths[glyphBase + glyph] = fStyleRunInfo[run].positions[glyph * 2 + 2] - fStyleRunInfo[run].positions[glyph * 2];
462        }
463
464        if ((fStyleRunInfo[run].level & 1) != 0) {
465            LXUtilities::reverse(&fGlyphWidths[glyphBase], glyphCount);
466            LXUtilities::reverse(&fGlyphToCharMap[glyphBase], glyphCount);
467        }
468
469        runStart = fStyleRunLimits[run];
470
471        delete engine;
472        fStyleRunInfo[run].engine = NULL;
473    }
474
475    fGlyphToCharMap[fGlyphCount] = fCharCount;
476
477    for (glyph = fGlyphCount - 1; glyph >= 0; glyph -= 1) {
478        le_int32 ch = fGlyphToCharMap[glyph];
479
480        fCharToMinGlyphMap[ch] = glyph;
481    }
482
483    fCharToMinGlyphMap[fCharCount] = fGlyphCount;
484
485    for (glyph = 0; glyph < fGlyphCount; glyph += 1) {
486        le_int32 ch = fGlyphToCharMap[glyph];
487
488        fCharToMaxGlyphMap[ch] = glyph;
489    }
490
491    fCharToMaxGlyphMap[fCharCount] = fGlyphCount;
492}
493
494ParagraphLayout::~ParagraphLayout()
495{
496    delete (FontRuns *) fFontRuns;
497
498    if (! fClientLevels) {
499        delete (ValueRuns *) fLevelRuns;
500        fLevelRuns = NULL;
501
502        fClientLevels = TRUE;
503    }
504
505    if (! fClientScripts) {
506        delete (ValueRuns *) fScriptRuns;
507        fScriptRuns = NULL;
508
509        fClientScripts = TRUE;
510    }
511
512    if (! fClientLocales) {
513        delete (LocaleRuns *) fLocaleRuns;
514        fLocaleRuns = NULL;
515
516        fClientLocales = TRUE;
517    }
518
519    if (fEmbeddingLevels != NULL) {
520        LE_DELETE_ARRAY(fEmbeddingLevels);
521        fEmbeddingLevels = NULL;
522    }
523
524    if (fGlyphToCharMap != NULL) {
525        LE_DELETE_ARRAY(fGlyphToCharMap);
526        fGlyphToCharMap = NULL;
527    }
528
529    if (fCharToMinGlyphMap != NULL) {
530        LE_DELETE_ARRAY(fCharToMinGlyphMap);
531        fCharToMinGlyphMap = NULL;
532    }
533
534    if (fCharToMaxGlyphMap != NULL) {
535        LE_DELETE_ARRAY(fCharToMaxGlyphMap);
536        fCharToMaxGlyphMap = NULL;
537    }
538
539    if (fGlyphWidths != NULL) {
540        LE_DELETE_ARRAY(fGlyphWidths);
541        fGlyphWidths = NULL;
542    }
543
544    if (fParaBidi != NULL) {
545        ubidi_close(fParaBidi);
546        fParaBidi = NULL;
547    }
548
549    if (fLineBidi != NULL) {
550        ubidi_close(fLineBidi);
551        fLineBidi = NULL;
552    }
553
554    if (fStyleRunCount > 0) {
555        le_int32 run;
556
557        LE_DELETE_ARRAY(fStyleRunLimits);
558        LE_DELETE_ARRAY(fStyleIndices);
559
560        for (run = 0; run < fStyleRunCount; run += 1) {
561            LE_DELETE_ARRAY(fStyleRunInfo[run].glyphs);
562            LE_DELETE_ARRAY(fStyleRunInfo[run].positions);
563
564            fStyleRunInfo[run].glyphs    = NULL;
565            fStyleRunInfo[run].positions = NULL;
566        }
567
568        LE_DELETE_ARRAY(fStyleRunInfo);
569
570        fStyleRunLimits = NULL;
571        fStyleIndices   = NULL;
572        fStyleRunInfo        = NULL;
573        fStyleRunCount  = 0;
574    }
575
576    if (fBreakIterator != NULL) {
577        delete fBreakIterator;
578        fBreakIterator = NULL;
579    }
580}
581
582
583le_bool ParagraphLayout::isComplex(const LEUnicode chars[], le_int32 count)
584{
585    UErrorCode scriptStatus = U_ZERO_ERROR;
586    UScriptCode scriptCode  = USCRIPT_INVALID_CODE;
587    UScriptRun *sr = uscript_openRun(chars, count, &scriptStatus);
588    le_bool result = FALSE;
589
590    while (uscript_nextRun(sr, NULL, NULL, &scriptCode)) {
591        if (isComplex(scriptCode)) {
592            result = TRUE;
593            break;
594        }
595    }
596
597    uscript_closeRun(sr);
598    return result;
599}
600
601le_int32 ParagraphLayout::getAscent() const
602{
603    if (fAscent <= 0 && fCharCount > 0) {
604        ((ParagraphLayout *) this)->computeMetrics();
605    }
606
607    return fAscent;
608}
609
610le_int32 ParagraphLayout::getDescent() const
611{
612    if (fAscent <= 0 && fCharCount > 0) {
613        ((ParagraphLayout *) this)->computeMetrics();
614    }
615
616    return fDescent;
617}
618
619le_int32 ParagraphLayout::getLeading() const
620{
621    if (fAscent <= 0 && fCharCount > 0) {
622        ((ParagraphLayout *) this)->computeMetrics();
623    }
624
625    return fLeading;
626}
627
628ParagraphLayout::Line *ParagraphLayout::nextLine(float width)
629{
630    if (fLineEnd >= fCharCount) {
631        return NULL;
632    }
633
634    fLineStart = fLineEnd;
635
636    if (width > 0) {
637        le_int32 glyph    = fCharToMinGlyphMap[fLineStart];
638        float widthSoFar  = 0;
639
640        while (glyph < fGlyphCount && widthSoFar + fGlyphWidths[glyph] <= width) {
641            widthSoFar += fGlyphWidths[glyph++];
642        }
643
644        // If no glyphs fit on the line, force one to fit.
645        //
646        // (There shouldn't be any zero width glyphs at the
647        // start of a line unless the paragraph consists of
648        // only zero width glyphs, because otherwise the zero
649        // width glyphs will have been included on the end of
650        // the previous line...)
651        if (widthSoFar == 0 && glyph < fGlyphCount) {
652            glyph += 1;
653        }
654
655        fLineEnd = previousBreak(fGlyphToCharMap[glyph]);
656
657        // If this break is at or before the last one,
658        // find a glyph, starting at the one which didn't
659        // fit, that produces a break after the last one.
660        while (fLineEnd <= fLineStart) {
661            fLineEnd = fGlyphToCharMap[glyph++];
662        }
663    } else {
664        fLineEnd = fCharCount;
665    }
666
667    return computeVisualRuns();
668}
669
670void ParagraphLayout::computeLevels(UBiDiLevel paragraphLevel)
671{
672    UErrorCode bidiStatus = U_ZERO_ERROR;
673
674    if (fLevelRuns != NULL) {
675        le_int32 ch;
676        le_int32 run;
677
678        fEmbeddingLevels = LE_NEW_ARRAY(UBiDiLevel, fCharCount);
679
680        for (ch = 0, run = 0; run < fLevelRuns->getCount(); run += 1) {
681            UBiDiLevel runLevel = (UBiDiLevel) fLevelRuns->getValue(run) | UBIDI_LEVEL_OVERRIDE;
682            le_int32   runLimit = fLevelRuns->getLimit(run);
683
684            while (ch < runLimit) {
685                fEmbeddingLevels[ch++] = runLevel;
686            }
687        }
688    }
689
690    fParaBidi = ubidi_openSized(fCharCount, 0, &bidiStatus);
691    ubidi_setPara(fParaBidi, fChars, fCharCount, paragraphLevel, fEmbeddingLevels, &bidiStatus);
692
693    if (fLevelRuns == NULL) {
694        le_int32 levelRunCount = ubidi_countRuns(fParaBidi, &bidiStatus);
695        ValueRuns *levelRuns = new ValueRuns(levelRunCount);
696
697        le_int32 logicalStart = 0;
698        le_int32 run;
699        le_int32 limit;
700        UBiDiLevel level;
701
702        for (run = 0; run < levelRunCount; run += 1) {
703            ubidi_getLogicalRun(fParaBidi, logicalStart, &limit, &level);
704            levelRuns->add(level, limit);
705            logicalStart = limit;
706        }
707
708        fLevelRuns    = levelRuns;
709        fClientLevels = FALSE;
710    }
711}
712
713void ParagraphLayout::computeScripts()
714{
715    UErrorCode scriptStatus = U_ZERO_ERROR;
716    UScriptRun *sr = uscript_openRun(fChars, fCharCount, &scriptStatus);
717    ValueRuns  *scriptRuns = new ValueRuns(0);
718    le_int32 limit;
719    UScriptCode script;
720
721    while (uscript_nextRun(sr, NULL, &limit, &script)) {
722        scriptRuns->add(script, limit);
723    }
724
725    uscript_closeRun(sr);
726
727    fScriptRuns    = scriptRuns;
728    fClientScripts = FALSE;
729}
730
731void ParagraphLayout::computeLocales()
732{
733    LocaleRuns *localeRuns = new LocaleRuns(0);
734    const Locale *defaultLocale = &Locale::getDefault();
735
736    localeRuns->add(defaultLocale, fCharCount);
737
738    fLocaleRuns    = localeRuns;
739    fClientLocales = FALSE;
740}
741
742void ParagraphLayout::computeSubFonts(const FontRuns *fontRuns, LEErrorCode &status)
743{
744    if (LE_FAILURE(status)) {
745        return;
746    }
747
748    const RunArray *styleRunArrays[] = {fontRuns, fScriptRuns};
749    le_int32 styleCount = sizeof styleRunArrays / sizeof styleRunArrays[0];
750    StyleRuns styleRuns(styleRunArrays, styleCount);
751    le_int32 styleRunCount = styleRuns.getRuns(NULL, NULL);
752    le_int32 *styleRunLimits = LE_NEW_ARRAY(le_int32, styleRunCount);
753    le_int32 *styleIndices = LE_NEW_ARRAY(le_int32, styleRunCount * styleCount);
754    FontRuns *subFontRuns  = new FontRuns(0);
755    le_int32  run, offset, *si;
756
757    styleRuns.getRuns(styleRunLimits, styleIndices);
758
759    si = styleIndices;
760    offset = 0;
761
762    for (run = 0; run < styleRunCount; run += 1) {
763        const LEFontInstance *runFont = fontRuns->getFont(si[0]);
764        le_int32 script = fScriptRuns->getValue(si[1]);
765
766        while (offset < styleRunLimits[run]) {
767            const LEFontInstance *subFont = runFont->getSubFont(fChars, &offset, styleRunLimits[run], script, status);
768
769            if (LE_FAILURE(status)) {
770                delete subFontRuns;
771                goto cleanUp;
772            }
773
774            subFontRuns->add(subFont, offset);
775        }
776
777        si += styleCount;
778    }
779
780    fFontRuns = subFontRuns;
781
782cleanUp:
783    LE_DELETE_ARRAY(styleIndices);
784    LE_DELETE_ARRAY(styleRunLimits);
785}
786
787void ParagraphLayout::computeMetrics()
788{
789    le_int32 i, count = fFontRuns->getCount();
790    le_int32 maxDL = 0;
791
792    for (i = 0; i < count; i += 1) {
793        const LEFontInstance *font = fFontRuns->getFont(i);
794        le_int32 ascent  = font->getAscent();
795        le_int32 descent = font->getDescent();
796        le_int32 leading = font->getLeading();
797        le_int32 dl      = descent + leading;
798
799        if (ascent > fAscent) {
800            fAscent = ascent;
801        }
802
803        if (descent > fDescent) {
804            fDescent = descent;
805        }
806
807        if (leading > fLeading) {
808            fLeading = leading;
809        }
810
811        if (dl > maxDL) {
812            maxDL = dl;
813        }
814    }
815
816    fLeading = maxDL - fDescent;
817}
818
819#if 1
820struct LanguageMap
821{
822    const char *localeCode;
823    le_int32 languageCode;
824};
825
826static const LanguageMap languageMap[] =
827{
828    {"afr", afkLanguageCode}, // Afrikaans
829    {"ara", araLanguageCode}, // Arabic
830    {"asm", asmLanguageCode}, // Assamese
831    {"bel", belLanguageCode}, // Belarussian
832    {"ben", benLanguageCode}, // Bengali
833    {"bod", tibLanguageCode}, // Tibetan
834    {"bul", bgrLanguageCode}, // Bulgarian
835    {"cat", catLanguageCode}, // Catalan
836    {"ces", csyLanguageCode}, // Czech
837    {"che", cheLanguageCode}, // Chechen
838    {"cop", copLanguageCode}, // Coptic
839    {"cym", welLanguageCode}, // Welsh
840    {"dan", danLanguageCode}, // Danish
841    {"deu", deuLanguageCode}, // German
842    {"dzo", dznLanguageCode}, // Dzongkha
843    {"ell", ellLanguageCode}, // Greek
844    {"eng", engLanguageCode}, // English
845    {"est", etiLanguageCode}, // Estonian
846    {"eus", euqLanguageCode}, // Basque
847    {"fas", farLanguageCode}, // Farsi
848    {"fin", finLanguageCode}, // Finnish
849    {"fra", fraLanguageCode}, // French
850    {"gle", gaeLanguageCode}, // Irish Gaelic
851    {"guj", gujLanguageCode}, // Gujarati
852    {"hau", hauLanguageCode}, // Hausa
853    {"heb", iwrLanguageCode}, // Hebrew
854    {"hin", hinLanguageCode}, // Hindi
855    {"hrv", hrvLanguageCode}, // Croatian
856    {"hun", hunLanguageCode}, // Hungarian
857    {"hye", hyeLanguageCode}, // Armenian
858    {"ind", indLanguageCode}, // Indonesian
859    {"ita", itaLanguageCode}, // Italian
860    {"jpn", janLanguageCode}, // Japanese
861    {"kan", kanLanguageCode}, // Kannada
862    {"kas", kshLanguageCode}, // Kashmiri
863    {"khm", khmLanguageCode}, // Khmer
864    {"kok", kokLanguageCode}, // Konkani
865    {"kor", korLanguageCode}, // Korean
866//  {"mal_XXX", malLanguageCode}, // Malayalam - Traditional
867    {"mal", mlrLanguageCode}, // Malayalam - Reformed
868    {"mar", marLanguageCode}, // Marathi
869    {"mlt", mtsLanguageCode}, // Maltese
870    {"mni", mniLanguageCode}, // Manipuri
871    {"mon", mngLanguageCode}, // Mongolian
872    {"nep", nepLanguageCode}, // Nepali
873    {"ori", oriLanguageCode}, // Oriya
874    {"pol", plkLanguageCode}, // Polish
875    {"por", ptgLanguageCode}, // Portuguese
876    {"pus", pasLanguageCode}, // Pashto
877    {"ron", romLanguageCode}, // Romanian
878    {"rus", rusLanguageCode}, // Russian
879    {"san", sanLanguageCode}, // Sanskrit
880    {"sin", snhLanguageCode}, // Sinhalese
881    {"slk", skyLanguageCode}, // Slovak
882    {"snd", sndLanguageCode}, // Sindhi
883    {"slv", slvLanguageCode}, // Slovenian
884    {"spa", espLanguageCode}, // Spanish
885    {"sqi", sqiLanguageCode}, // Albanian
886    {"srp", srbLanguageCode}, // Serbian
887    {"swe", sveLanguageCode}, // Swedish
888    {"syr", syrLanguageCode}, // Syriac
889    {"tam", tamLanguageCode}, // Tamil
890    {"tel", telLanguageCode}, // Telugu
891    {"tha", thaLanguageCode}, // Thai
892    {"tur", trkLanguageCode}, // Turkish
893    {"urd", urdLanguageCode}, // Urdu
894    {"yid", jiiLanguageCode}, // Yiddish
895//  {"zhp", zhpLanguageCode}, // Chinese - Phonetic
896    {"zho", zhsLanguageCode}, // Chinese
897    {"zho_CHN", zhsLanguageCode}, // Chinese - China
898    {"zho_HKG", zhsLanguageCode}, // Chinese - Hong Kong
899    {"zho_MAC", zhtLanguageCode}, // Chinese - Macao
900    {"zho_SGP", zhsLanguageCode}, // Chinese - Singapore
901    {"zho_TWN", zhtLanguageCode}  // Chinese - Taiwan
902};
903
904static const le_int32 languageMapCount = ARRAY_SIZE(languageMap);
905
906le_int32 ParagraphLayout::getLanguageCode(const Locale *locale)
907{
908    char code[8] = {0, 0, 0, 0, 0, 0, 0, 0};
909    const char *language = locale->getISO3Language();
910    const char *country  = locale->getISO3Country();
911
912    uprv_strcat(code, language);
913
914    if ((uprv_strcmp(language, "zho") == 0) && country != NULL) {
915        uprv_strcat(code, "_");
916        uprv_strcat(code, country);
917    }
918
919    for (le_int32 i = 0; i < languageMapCount; i += 1) {
920        if (uprv_strcmp(code, languageMap[i].localeCode) == 0) {
921            return languageMap[i].languageCode;
922        }
923    }
924
925    return nullLanguageCode;
926}
927#else
928
929// TODO - dummy implementation for right now...
930le_int32 ParagraphLayout::getLanguageCode(const Locale *locale)
931{
932    return nullLanguageCode;
933}
934#endif
935
936le_bool ParagraphLayout::isComplex(UScriptCode script)
937{
938    if (script < 0 || script >= (UScriptCode) scriptCodeCount) {
939        return FALSE;
940    }
941
942    return complexTable[script];
943}
944
945le_int32 ParagraphLayout::previousBreak(le_int32 charIndex)
946{
947    // skip over any whitespace or control characters,
948    // because they can hang in the margin.
949    while (charIndex < fCharCount &&
950           (u_isWhitespace(fChars[charIndex]) ||
951            u_iscntrl(fChars[charIndex]))) {
952        charIndex += 1;
953    }
954
955    // Create the BreakIterator if we don't already have one
956    if (fBreakIterator == NULL) {
957        Locale thai("th");
958        UCharCharacterIterator *iter = new UCharCharacterIterator(fChars, fCharCount);
959        UErrorCode status = U_ZERO_ERROR;
960
961        fBreakIterator = BreakIterator::createLineInstance(thai, status);
962        fBreakIterator->adoptText(iter);
963    }
964
965    // return the break location that's at or before
966    // the character we stopped on. Note: if we're
967    // on a break, the "+ 1" will cause preceding to
968    // back up to it.
969    return fBreakIterator->preceding(charIndex + 1);
970}
971
972ParagraphLayout::Line *ParagraphLayout::computeVisualRuns()
973{
974    UErrorCode bidiStatus = U_ZERO_ERROR;
975    le_int32 dirRunCount, visualRun;
976
977    fVisualRunLastX = 0;
978    fVisualRunLastY = 0;
979    fFirstVisualRun = getCharRun(fLineStart);
980    fLastVisualRun  = getCharRun(fLineEnd - 1);
981
982    if (fLineBidi == NULL) {
983        fLineBidi = ubidi_openSized(fCharCount, 0, &bidiStatus);
984    }
985
986    ubidi_setLine(fParaBidi, fLineStart, fLineEnd, fLineBidi, &bidiStatus);
987    dirRunCount = ubidi_countRuns(fLineBidi, &bidiStatus);
988
989    Line *line = new Line();
990
991    for (visualRun = 0; visualRun < dirRunCount; visualRun += 1) {
992        le_int32 relStart, run, runLength;
993        UBiDiDirection runDirection = ubidi_getVisualRun(fLineBidi, visualRun, &relStart, &runLength);
994        le_int32 runStart = fLineStart + relStart;
995        le_int32 runEnd   = runStart + runLength - 1;
996        le_int32 firstRun = getCharRun(runStart);
997        le_int32 lastRun  = getCharRun(runEnd);
998        le_int32 startRun = (runDirection == UBIDI_LTR)? firstRun : lastRun;
999        le_int32 stopRun  = (runDirection == UBIDI_LTR)? lastRun + 1 : firstRun - 1;
1000        le_int32 dir      = (runDirection == UBIDI_LTR)?  1 : -1;
1001
1002        for (run = startRun; run != stopRun; run += dir) {
1003            le_int32 firstChar = (run == firstRun)? runStart : fStyleRunInfo[run].runBase;
1004            le_int32 lastChar  = (run == lastRun)?  runEnd   : fStyleRunInfo[run].runLimit - 1;
1005
1006            appendRun(line, run, firstChar, lastChar);
1007        }
1008    }
1009
1010    return line;
1011}
1012
1013void ParagraphLayout::appendRun(ParagraphLayout::Line *line, le_int32 run, le_int32 firstChar, le_int32 lastChar)
1014{
1015    le_int32 glyphBase = fStyleRunInfo[run].glyphBase;
1016    le_int32 inGlyph, outGlyph;
1017
1018    // Get the glyph indices for all the characters between firstChar and lastChar,
1019    // make the minimum one be leftGlyph and the maximum one be rightGlyph.
1020    // (need to do this to handle local reorderings like Indic left matras)
1021    le_int32 leftGlyph  = fGlyphCount;
1022    le_int32 rightGlyph = -1;
1023    le_int32 ch;
1024
1025    for (ch = firstChar; ch <= lastChar; ch += 1) {
1026        le_int32 minGlyph = fCharToMinGlyphMap[ch];
1027        le_int32 maxGlyph = fCharToMaxGlyphMap[ch];
1028
1029        if (minGlyph < leftGlyph) {
1030            leftGlyph = minGlyph;
1031        }
1032
1033        if (maxGlyph > rightGlyph) {
1034            rightGlyph = maxGlyph;
1035        }
1036    }
1037
1038    if ((fStyleRunInfo[run].level & 1) != 0) {
1039        le_int32 swap = rightGlyph;
1040        le_int32 last = glyphBase + fStyleRunInfo[run].glyphCount - 1;
1041
1042        // Here, we want to remove the glyphBase bias...
1043        rightGlyph = last - leftGlyph;
1044        leftGlyph  = last - swap;
1045    } else {
1046        rightGlyph -= glyphBase;
1047        leftGlyph  -= glyphBase;
1048    }
1049
1050    // Set the position bias for the glyphs. If we're at the start of
1051    // a line, we want the first glyph to be at x = 0, even if it comes
1052    // from the middle of a layout. If we've got a right-to-left run, we
1053    // want the left-most glyph to start at the final x position of the
1054    // previous run, even though this glyph may be in the middle of the
1055    // run.
1056    fVisualRunLastX -= fStyleRunInfo[run].positions[leftGlyph * 2];
1057
1058    // Make rightGlyph be the glyph just to the right of
1059    // the run's glyphs
1060    rightGlyph += 1;
1061
1062    UBiDiDirection direction  = ((fStyleRunInfo[run].level & 1) == 0)? UBIDI_LTR : UBIDI_RTL;
1063    le_int32   glyphCount     = rightGlyph - leftGlyph;
1064    LEGlyphID *glyphs         = LE_NEW_ARRAY(LEGlyphID, glyphCount);
1065    float     *positions      = LE_NEW_ARRAY(float, glyphCount * 2 + 2);
1066    le_int32  *glyphToCharMap = LE_NEW_ARRAY(le_int32, glyphCount);
1067
1068    LE_ARRAY_COPY(glyphs, &fStyleRunInfo[run].glyphs[leftGlyph], glyphCount);
1069
1070    for (outGlyph = 0, inGlyph = leftGlyph * 2; inGlyph <= rightGlyph * 2; inGlyph += 2, outGlyph += 2) {
1071        positions[outGlyph]     = fStyleRunInfo[run].positions[inGlyph] + fVisualRunLastX;
1072        positions[outGlyph + 1] = fStyleRunInfo[run].positions[inGlyph + 1] /* + fVisualRunLastY */;
1073    }
1074
1075    // Save the ending position of this run
1076    // to use for the start of the next run
1077    fVisualRunLastX = positions[outGlyph - 2];
1078 // fVisualRunLastY = positions[rightGlyph * 2 + 2];
1079
1080    if ((fStyleRunInfo[run].level & 1) == 0) {
1081        for (outGlyph = 0, inGlyph = leftGlyph; inGlyph < rightGlyph; inGlyph += 1, outGlyph += 1) {
1082            glyphToCharMap[outGlyph] = fGlyphToCharMap[glyphBase + inGlyph];
1083        }
1084    } else {
1085        // Because fGlyphToCharMap is stored in logical order to facilitate line breaking,
1086        // we need to map the physical glyph indices to logical indices while we copy the
1087        // character indices.
1088        le_int32 base = glyphBase + fStyleRunInfo[run].glyphCount - 1;
1089
1090        for (outGlyph = 0, inGlyph = leftGlyph; inGlyph < rightGlyph; inGlyph += 1, outGlyph += 1) {
1091            glyphToCharMap[outGlyph] = fGlyphToCharMap[base - inGlyph];
1092        }
1093    }
1094
1095    line->append(fStyleRunInfo[run].font, direction, glyphCount, glyphs, positions, glyphToCharMap);
1096}
1097
1098le_int32 ParagraphLayout::getCharRun(le_int32 charIndex)
1099{
1100    if (charIndex < 0 || charIndex > fCharCount) {
1101        return -1;
1102    }
1103
1104    le_int32 run;
1105
1106    // NOTE: as long as fStyleRunLimits is well-formed
1107    // the above range check guarantees that we'll never
1108    // fall off the end of the array.
1109    run = 0;
1110    while (charIndex >= fStyleRunLimits[run]) {
1111        run += 1;
1112    }
1113
1114    return run;
1115}
1116
1117
1118const char ParagraphLayout::Line::fgClassID = 0;
1119
1120#define INITIAL_RUN_CAPACITY 4
1121#define RUN_CAPACITY_GROW_LIMIT 16
1122
1123ParagraphLayout::Line::~Line()
1124{
1125    le_int32 i;
1126
1127    for (i = 0; i < fRunCount; i += 1) {
1128        delete fRuns[i];
1129    }
1130
1131    LE_DELETE_ARRAY(fRuns);
1132}
1133
1134le_int32 ParagraphLayout::Line::getAscent() const
1135{
1136    if (fAscent <= 0) {
1137        ((ParagraphLayout::Line *)this)->computeMetrics();
1138    }
1139
1140    return fAscent;
1141}
1142
1143le_int32 ParagraphLayout::Line::getDescent() const
1144{
1145    if (fAscent <= 0) {
1146        ((ParagraphLayout::Line *)this)->computeMetrics();
1147    }
1148
1149    return fDescent;
1150}
1151
1152le_int32 ParagraphLayout::Line::getLeading() const
1153{
1154    if (fAscent <= 0) {
1155        ((ParagraphLayout::Line *)this)->computeMetrics();
1156    }
1157
1158    return fLeading;
1159}
1160
1161le_int32 ParagraphLayout::Line::getWidth() const
1162{
1163    const VisualRun *lastRun = getVisualRun(fRunCount - 1);
1164
1165    if (lastRun == NULL) {
1166        return 0;
1167    }
1168
1169    le_int32 glyphCount = lastRun->getGlyphCount();
1170    const float *positions = lastRun->getPositions();
1171
1172    return (le_int32) positions[glyphCount * 2];
1173}
1174
1175const ParagraphLayout::VisualRun *ParagraphLayout::Line::getVisualRun(le_int32 runIndex) const
1176{
1177    if (runIndex < 0 || runIndex >= fRunCount) {
1178        return NULL;
1179    }
1180
1181    return fRuns[runIndex];
1182}
1183
1184void ParagraphLayout::Line::append(const LEFontInstance *font, UBiDiDirection direction, le_int32 glyphCount,
1185                                   const LEGlyphID glyphs[], const float positions[], const le_int32 glyphToCharMap[])
1186{
1187    if (fRunCount >= fRunCapacity) {
1188        if (fRunCapacity == 0) {
1189            fRunCapacity = INITIAL_RUN_CAPACITY;
1190            fRuns = LE_NEW_ARRAY(ParagraphLayout::VisualRun *, fRunCapacity);
1191        } else {
1192            fRunCapacity += (fRunCapacity < RUN_CAPACITY_GROW_LIMIT? fRunCapacity : RUN_CAPACITY_GROW_LIMIT);
1193            fRuns = (ParagraphLayout::VisualRun **) LE_GROW_ARRAY(fRuns, fRunCapacity);
1194        }
1195    }
1196
1197    fRuns[fRunCount++] = new ParagraphLayout::VisualRun(font, direction, glyphCount, glyphs, positions, glyphToCharMap);
1198}
1199
1200void ParagraphLayout::Line::computeMetrics()
1201{
1202    le_int32 maxDL = 0;
1203
1204    for (le_int32 i = 0; i < fRunCount; i += 1) {
1205        le_int32 ascent  = fRuns[i]->getAscent();
1206        le_int32 descent = fRuns[i]->getDescent();
1207        le_int32 leading = fRuns[i]->getLeading();
1208        le_int32 dl      = descent + leading;
1209
1210        if (ascent > fAscent) {
1211            fAscent = ascent;
1212        }
1213
1214        if (descent > fDescent) {
1215            fDescent = descent;
1216        }
1217
1218        if (leading > fLeading) {
1219            fLeading = leading;
1220        }
1221
1222        if (dl > maxDL) {
1223            maxDL = dl;
1224        }
1225    }
1226
1227    fLeading = maxDL - fDescent;
1228}
1229
1230const char ParagraphLayout::VisualRun::fgClassID = 0;
1231
1232ParagraphLayout::VisualRun::~VisualRun()
1233{
1234    LE_DELETE_ARRAY(fGlyphToCharMap);
1235    LE_DELETE_ARRAY(fPositions);
1236    LE_DELETE_ARRAY(fGlyphs);
1237}
1238
1239U_NAMESPACE_END
1240
1241#endif
1242
1243
1244