d095bac84847d7edada96fb7257222a44cb373ba
[WebKit-https.git] / WebCore / platform / mac / FontData.mm
1 /*
2  * Copyright (C) 2005 Apple Computer, Inc.  All rights reserved.
3  * Copyright (C) 2006 Alexey Proskuryakov
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1.  Redistributions of source code must retain the above copyright
10  *     notice, this list of conditions and the following disclaimer. 
11  * 2.  Redistributions in binary form must reproduce the above copyright
12  *     notice, this list of conditions and the following disclaimer in the
13  *     documentation and/or other materials provided with the distribution. 
14  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
15  *     its contributors may be used to endorse or promote products derived
16  *     from this software without specific prior written permission. 
17  *
18  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
22  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29
30 #import "config.h"
31 #import "Font.h"
32 #import "FontData.h"
33 #import "Color.h"
34 #import "WebCoreTextRenderer.h"
35
36 #import <wtf/Assertions.h>
37
38 #import <ApplicationServices/ApplicationServices.h>
39 #import <Cocoa/Cocoa.h>
40
41 #import <WebTextRendererFactory.h>
42
43 #import "WebCoreSystemInterface.h"
44
45 #import "FloatRect.h"
46 #import "FontDescription.h"
47
48 #import <float.h>
49
50 #import <unicode/uchar.h>
51 #import <unicode/unorm.h>
52
53 // FIXME: Just temporary for the #defines of constants that we will eventually stop using.
54 #import "GlyphBuffer.h"
55
56 namespace WebCore
57 {
58
59 // FIXME: FATAL seems like a bad idea; lets stop using it.
60
61 #define SMALLCAPS_FONTSIZE_MULTIPLIER 0.7f
62 #define SYNTHETIC_OBLIQUE_ANGLE 14
63
64 // Should be more than enough for normal usage.
65 #define NUM_SUBSTITUTE_FONT_MAPS 10
66
67 // According to http://www.unicode.org/Public/UNIDATA/UCD.html#Canonical_Combining_Class_Values
68 #define HIRAGANA_KATAKANA_VOICING_MARKS 8
69
70 #define SPACE 0x0020
71 #define NO_BREAK_SPACE 0x00A0
72 #define ZERO_WIDTH_SPACE 0x200B
73 #define POP_DIRECTIONAL_FORMATTING 0x202C
74 #define LEFT_TO_RIGHT_OVERRIDE 0x202D
75 #define RIGHT_TO_LEFT_OVERRIDE 0x202E
76
77 // MAX_GLYPH_EXPANSION is the maximum numbers of glyphs that may be
78 // use to represent a single Unicode code point.
79 #define MAX_GLYPH_EXPANSION 4
80 #define LOCAL_BUFFER_SIZE 2048
81
82 // Covers Latin-1.
83 #define INITIAL_BLOCK_SIZE 0x200
84
85 // Get additional blocks of glyphs and widths in bigger chunks.
86 // This will typically be for other character sets.
87 #define INCREMENTAL_BLOCK_SIZE 0x400
88
89 #define CONTEXT_DPI (72.0)
90 #define SCALE_EM_TO_UNITS(X, U_PER_EM) (X * ((1.0 * CONTEXT_DPI) / (CONTEXT_DPI * U_PER_EM)))
91
92 #define WKGlyphVectorSize (50 * 32)
93
94 typedef float WebGlyphWidth;
95
96 struct WidthMap {
97     WidthMap() :next(0), widths(0) {}
98
99     ATSGlyphRef startRange;
100     ATSGlyphRef endRange;
101     WidthMap *next;
102     WebGlyphWidth *widths;
103 };
104
105 typedef struct GlyphEntry {
106     Glyph glyph;
107     const FontData *renderer;
108 } GlyphEntry;
109
110 struct GlyphMap {
111     UChar startRange;
112     UChar endRange;
113     GlyphMap *next;
114     GlyphEntry *glyphs;
115 };
116
117 typedef struct WidthIterator {
118     FontData *renderer;
119     const WebCoreTextRun *run;
120     const WebCoreTextStyle *style;
121     unsigned currentCharacter;
122     float runWidthSoFar;
123     float widthToStart;
124     float padding;
125     float padPerSpace;
126     float finalRoundingWidth;
127 } WidthIterator;
128
129 typedef struct ATSULayoutParameters
130 {
131     const WebCoreTextRun *run;
132     const WebCoreTextStyle *style;
133     ATSUTextLayout layout;
134     FontData **renderers;
135     UniChar *charBuffer;
136     bool hasSyntheticBold;
137     bool syntheticBoldPass;
138     float padPerSpace;
139 } ATSULayoutParameters;
140
141 static const FontData *rendererForAlternateFont(const FontData *, FontPlatformData);
142
143 static WidthMap *extendWidthMap(const FontData *, ATSGlyphRef);
144 static ATSGlyphRef extendGlyphMap(const FontData *, UChar32);
145
146 static void freeWidthMap(WidthMap *);
147 static void freeGlyphMap(GlyphMap *);
148
149 // Measuring runs.
150 static float CG_floatWidthForRun(FontData *, const WebCoreTextRun *, const WebCoreTextStyle *,
151     float *widthBuffer, FontData **rendererBuffer, CGGlyph *glyphBuffer, float *startPosition, int *numGlyphsResult);
152
153 // Selection point detection in runs.
154 static int CG_pointToOffset(FontData *, const WebCoreTextRun *, const WebCoreTextStyle *,
155     int x, bool includePartialGlyphs);
156 static int ATSU_pointToOffset(FontData *, const WebCoreTextRun *, const WebCoreTextStyle *,
157     int x, bool includePartialGlyphs);
158
159 // Selection rect.
160 static NSRect CG_selectionRect(FontData *, const WebCoreTextRun *, const WebCoreTextStyle *, const WebCoreTextGeometry *);
161 static NSRect ATSU_selectionRect(FontData *, const WebCoreTextRun *, const WebCoreTextStyle *, const WebCoreTextGeometry *);
162
163 static bool setUpFont(FontData *);
164
165 // Iterator functions
166 static void initializeWidthIterator(WidthIterator *iterator, FontData *renderer, const WebCoreTextRun *run, const WebCoreTextStyle *style);
167 static unsigned advanceWidthIterator(WidthIterator *iterator, unsigned offset, float *widths, FontData **renderersUsed, ATSGlyphRef *glyphsUsed);
168
169 static bool fillStyleWithAttributes(ATSUStyle style, NSFont *theFont);
170 static bool shouldUseATSU(const WebCoreTextRun *run);
171
172 #if !ERROR_DISABLED
173 static NSString *pathFromFont(NSFont *font);
174 #endif
175
176 static void createATSULayoutParameters(ATSULayoutParameters *params, FontData *renderer, const WebCoreTextRun *run, const WebCoreTextStyle *style);
177 static void disposeATSULayoutParameters(ATSULayoutParameters *params);
178
179 // Character property functions.
180
181 void WebCoreInitializeTextRun(WebCoreTextRun *run, const UniChar *characters, unsigned int length, int from, int to)
182 {
183     run->characters = characters;
184     run->length = length;
185     run->from = from;
186     run->to = to;
187 }
188
189 void WebCoreInitializeEmptyTextStyle(WebCoreTextStyle *style)
190 {
191     style->textColor = nil;
192     style->backgroundColor = nil;
193     style->letterSpacing = 0;
194     style->wordSpacing = 0;
195     style->padding = 0;
196     style->families = nil;
197     style->smallCaps = NO;
198     style->rtl = NO;
199     style->directionalOverride = NO;
200     style->applyRunRounding = YES;
201     style->applyWordRounding = YES;
202     style->attemptFontSubstitution = YES;
203 }
204
205 void WebCoreInitializeEmptyTextGeometry(WebCoreTextGeometry *geometry)
206 {
207     geometry->useFontMetricsForSelectionYAndHeight = YES;
208 }
209
210 // Map utility functions
211
212 float FontData::widthForGlyph(Glyph glyph) const
213 {
214     WidthMap *map;
215     for (map = m_glyphToWidthMap; 1; map = map->next) {
216         if (!map)
217             map = extendWidthMap(this, glyph);
218         if (glyph >= map->startRange && glyph <= map->endRange)
219             break;
220     }
221     float width = map->widths[glyph - map->startRange];
222     if (width >= 0)
223         return width;
224     NSFont *font = m_font.font;
225     float pointSize = [font pointSize];
226     CGAffineTransform m = CGAffineTransformMakeScale(pointSize, pointSize);
227     CGSize advance;
228     if (!wkGetGlyphTransformedAdvances(font, &m, &glyph, &advance)) {
229         LOG_ERROR("Unable to cache glyph widths for %@ %f", [font displayName], pointSize);
230         advance.width = 0;
231     }
232     width = advance.width + m_syntheticBoldOffset;
233     map->widths[glyph - map->startRange] = width;
234     return width;
235 }
236
237 static OSStatus overrideLayoutOperation(ATSULayoutOperationSelector iCurrentOperation, ATSULineRef iLineRef, UInt32 iRefCon, void *iOperationCallbackParameterPtr, ATSULayoutOperationCallbackStatus *oCallbackStatus)
238 {
239     ATSULayoutParameters *params = (ATSULayoutParameters *)iRefCon;
240     OSStatus status;
241     ItemCount count;
242     ATSLayoutRecord *layoutRecords;
243     const WebCoreTextStyle *style = params->style;
244
245     if (style->applyWordRounding) {
246         status = ATSUDirectGetLayoutDataArrayPtrFromLineRef(iLineRef, kATSUDirectDataLayoutRecordATSLayoutRecordCurrent, true, (void **)&layoutRecords, &count);
247         if (status != noErr) {
248             *oCallbackStatus = kATSULayoutOperationCallbackStatusContinue;
249             return status;
250         }
251         
252         Fixed lastNativePos = 0;
253         float lastAdjustedPos = 0;
254         const WebCoreTextRun *run = params->run;
255         const UniChar *characters = run->characters + run->from;
256         FontData **renderers = params->renderers + run->from;
257         FontData *renderer;
258         FontData *lastRenderer = 0;
259         UniChar ch, nextCh;
260         ByteCount offset = layoutRecords[0].originalOffset;
261         nextCh = *(UniChar *)(((char *)characters)+offset);
262         bool shouldRound = false;
263         bool syntheticBoldPass = params->syntheticBoldPass;
264         Fixed syntheticBoldOffset = 0;
265         ATSGlyphRef spaceGlyph = 0;
266         bool hasExtraSpacing = style->letterSpacing | style->wordSpacing | style->padding;
267         float padding = style->padding;
268         // In the CoreGraphics code path, the rounding hack is applied in logical order.
269         // Here it is applied in visual left-to-right order, which may be better.
270         ItemCount lastRoundingChar = 0;
271         ItemCount i;
272         for (i = 1; i < count; i++) {
273             bool isLastChar = i == count - 1;
274             renderer = renderers[offset / 2];
275             if (renderer != lastRenderer) {
276                 lastRenderer = renderer;
277                 // The CoreGraphics interpretation of NSFontAntialiasedIntegerAdvancementsRenderingMode seems
278                 // to be "round each glyph's width to the nearest integer". This is not the same as ATSUI
279                 // does in any of its device-metrics modes.
280                 shouldRound = [renderer->m_font.font renderingMode] == NSFontAntialiasedIntegerAdvancementsRenderingMode;
281                 if (syntheticBoldPass) {
282                     syntheticBoldOffset = FloatToFixed(renderer->m_syntheticBoldOffset);
283                     spaceGlyph = renderer->m_spaceGlyph;
284                 }
285             }
286             float width = FixedToFloat(layoutRecords[i].realPos - lastNativePos);
287             lastNativePos = layoutRecords[i].realPos;
288             if (shouldRound)
289                 width = roundf(width);
290             width += renderer->m_syntheticBoldOffset;
291             if (renderer->m_treatAsFixedPitch ? width == renderer->m_spaceWidth : (layoutRecords[i-1].flags & kATSGlyphInfoIsWhiteSpace))
292                 width = renderer->m_adjustedSpaceWidth;
293
294             if (hasExtraSpacing) {
295                 if (width && style->letterSpacing)
296                     width +=style->letterSpacing;
297                 if (Font::treatAsSpace(nextCh)) {
298                     if (style->padding) {
299                         if (padding < params->padPerSpace) {
300                             width += padding;
301                             padding = 0;
302                         } else {
303                             width += params->padPerSpace;
304                             padding -= params->padPerSpace;
305                         }
306                     }
307                     if (offset != 0 && !Font::treatAsSpace(*((UniChar *)(((char *)characters)+offset) - 1)) && style->wordSpacing)
308                         width += style->wordSpacing;
309                 }
310             }
311
312             ch = nextCh;
313             offset = layoutRecords[i].originalOffset;
314             // Use space for nextCh at the end of the loop so that we get inside the rounding hack code.
315             // We won't actually round unless the other conditions are satisfied.
316             nextCh = isLastChar ? ' ' : *(UniChar *)(((char *)characters)+offset);
317
318             if (Font::isRoundingHackCharacter(ch))
319                 width = ceilf(width);
320             lastAdjustedPos = lastAdjustedPos + width;
321             if (Font::isRoundingHackCharacter(nextCh)
322                 && (!isLastChar
323                     || style->applyRunRounding
324                     || (run->to < (int)run->length && Font::isRoundingHackCharacter(characters[run->to - run->from])))) {
325                 if (!style->rtl)
326                     lastAdjustedPos = ceilf(lastAdjustedPos);
327                 else {
328                     float roundingWidth = ceilf(lastAdjustedPos) - lastAdjustedPos;
329                     Fixed rw = FloatToFixed(roundingWidth);
330                     ItemCount j;
331                     for (j = lastRoundingChar; j < i; j++)
332                         layoutRecords[j].realPos += rw;
333                     lastRoundingChar = i;
334                     lastAdjustedPos += roundingWidth;
335                 }
336             }
337             if (syntheticBoldPass) {
338                 if (syntheticBoldOffset)
339                     layoutRecords[i-1].realPos += syntheticBoldOffset;
340                 else
341                     layoutRecords[i-1].glyphID = spaceGlyph;
342             }
343             layoutRecords[i].realPos = FloatToFixed(lastAdjustedPos);
344         }
345         
346         status = ATSUDirectReleaseLayoutDataArrayPtr(iLineRef, kATSUDirectDataLayoutRecordATSLayoutRecordCurrent, (void **)&layoutRecords);
347     }
348     *oCallbackStatus = kATSULayoutOperationCallbackStatusHandled;
349     return noErr;
350 }
351
352 static NSString *webFallbackFontFamily(void)
353 {
354     static NSString *webFallbackFontFamily = nil;
355     if (!webFallbackFontFamily)
356         webFallbackFontFamily = [[[NSFont systemFontOfSize:16.0] familyName] retain];
357     return webFallbackFontFamily;
358 }
359
360 FontData::FontData(const FontPlatformData& f)
361 :m_styleGroup(0), m_font(f), m_characterToGlyphMap(0), m_glyphToWidthMap(0), m_treatAsFixedPitch(false),
362  m_smallCapsFontData(0), m_ATSUStyleInitialized(false), m_ATSUMirrors(false)
363 {    
364     m_font = f;
365
366     m_syntheticBoldOffset = f.syntheticBold ? ceilf([f.font pointSize] / 24.0f) : 0.f;
367     
368     bool failedSetup = false;
369     if (!setUpFont(this)) {
370         // Ack! Something very bad happened, like a corrupt font.
371         // Try looking for an alternate 'base' font for this renderer.
372
373         // Special case hack to use "Times New Roman" in place of "Times".
374         // "Times RO" is a common font whose family name is "Times".
375         // It overrides the normal "Times" family font.
376         // It also appears to have a corrupt regular variant.
377         NSString *fallbackFontFamily;
378         if ([[m_font.font familyName] isEqual:@"Times"])
379             fallbackFontFamily = @"Times New Roman";
380         else
381             fallbackFontFamily = webFallbackFontFamily();
382         
383         // Try setting up the alternate font.
384         // This is a last ditch effort to use a substitute font when something has gone wrong.
385 #if !ERROR_DISABLED
386         NSFont *initialFont = m_font.font;
387 #endif
388         m_font.font = [[NSFontManager sharedFontManager] convertFont:m_font.font toFamily:fallbackFontFamily];
389 #if !ERROR_DISABLED
390         NSString *filePath = pathFromFont(initialFont);
391         if (!filePath)
392             filePath = @"not known";
393 #endif
394         if (!setUpFont(this)) {
395             if ([fallbackFontFamily isEqual:@"Times New Roman"]) {
396                 // OK, couldn't setup Times New Roman as an alternate to Times, fallback
397                 // on the system font.  If this fails we have no alternative left.
398                 m_font.font = [[NSFontManager sharedFontManager] convertFont:m_font.font toFamily:webFallbackFontFamily()];
399                 if (!setUpFont(this)) {
400                     // We tried, Times, Times New Roman, and the system font. No joy. We have to give up.
401                     LOG_ERROR("unable to initialize with font %@ at %@", initialFont, filePath);
402                     failedSetup = true;
403                 }
404             } else {
405                 // We tried the requested font and the system font. No joy. We have to give up.
406                 LOG_ERROR("unable to initialize with font %@ at %@", initialFont, filePath);
407                 failedSetup = true;
408             }
409         }
410
411         // Report the problem.
412         LOG_ERROR("Corrupt font detected, using %@ in place of %@ located at \"%@\".",
413             [m_font.font familyName], [initialFont familyName], filePath);
414     }
415
416     // If all else fails, try to set up using the system font.
417     // This is probably because Times and Times New Roman are both unavailable.
418     if (failedSetup) {
419         m_font.font = [NSFont systemFontOfSize:[m_font.font pointSize]];
420         LOG_ERROR("failed to set up font, using system font %s", m_font.font);
421         setUpFont(this);
422     }
423     
424     int iAscent;
425     int iDescent;
426     int iLineGap;
427     unsigned unitsPerEm;
428     wkGetFontMetrics(m_font.font, &iAscent, &iDescent, &iLineGap, &unitsPerEm); 
429     float pointSize = [m_font.font pointSize];
430     float fAscent = SCALE_EM_TO_UNITS(iAscent, unitsPerEm) * pointSize;
431     float fDescent = -SCALE_EM_TO_UNITS(iDescent, unitsPerEm) * pointSize;
432     float fLineGap = SCALE_EM_TO_UNITS(iLineGap, unitsPerEm) * pointSize;
433
434     // We need to adjust Times, Helvetica, and Courier to closely match the
435     // vertical metrics of their Microsoft counterparts that are the de facto
436     // web standard. The AppKit adjustment of 20% is too big and is
437     // incorrectly added to line spacing, so we use a 15% adjustment instead
438     // and add it to the ascent.
439     NSString *familyName = [m_font.font familyName];
440     if ([familyName isEqualToString:@"Times"] || [familyName isEqualToString:@"Helvetica"] || [familyName isEqualToString:@"Courier"])
441         fAscent += floorf(((fAscent + fDescent) * 0.15f) + 0.5f);
442
443     m_ascent = lroundf(fAscent);
444     m_descent = lroundf(fDescent);
445     m_lineGap = lroundf(fLineGap);
446
447     m_lineSpacing = m_ascent + m_descent + m_lineGap;
448
449     [m_font.font retain];
450 }
451
452 FontData::~FontData()
453 {
454     if (m_styleGroup)
455         wkReleaseStyleGroup(m_styleGroup);
456
457     freeWidthMap(m_glyphToWidthMap);
458     freeGlyphMap(m_characterToGlyphMap);
459
460     if (m_ATSUStyleInitialized)
461         ATSUDisposeStyle(m_ATSUStyle);
462         
463     [m_font.font release];
464     
465     // We only get deleted when the cache gets cleared.  Since the smallCapsRenderer is also in that cache,
466     // it will be deleted then, so we don't need to do anything here.
467 }
468
469 float FontData::xHeight() const
470 {
471     // Measure the actual character "x", because AppKit synthesizes X height rather than getting it from the font.
472     // Unfortunately, NSFont will round this for us so we don't quite get the right value.
473     const FontData *renderer = [[WebTextRendererFactory sharedFactory] rendererWithFont:m_font];
474     NSGlyph xGlyph = glyphForCharacter(&renderer, 'x');
475     if (xGlyph) {
476         NSRect xBox = [m_font.font boundingRectForGlyph:xGlyph];
477         // Use the maximum of either width or height because "x" is nearly square
478         // and web pages that foolishly use this metric for width will be laid out
479         // poorly if we return an accurate height. Classic case is Times 13 point,
480         // which has an "x" that is 7x6 pixels.
481         return MAX(NSMaxX(xBox), NSMaxY(xBox));
482     }
483
484     return [m_font.font xHeight];
485 }
486
487 FloatRect FontData::selectionRectForRun(const WebCoreTextRun* run, const WebCoreTextStyle* style, const WebCoreTextGeometry* geometry)
488 {
489     if (shouldUseATSU(run))
490         return ATSU_selectionRect(this, run, style, geometry);
491     else
492         return CG_selectionRect(this, run, style, geometry);
493 }
494
495 int FontData::pointToOffset(const WebCoreTextRun* run, const WebCoreTextStyle* style, int x, bool includePartialGlyphs)
496 {
497     if (shouldUseATSU(run))
498         return ATSU_pointToOffset(this, run, style, x, includePartialGlyphs);
499     return CG_pointToOffset(this, run, style, x, includePartialGlyphs);
500 }
501
502 FontData* FontData::smallCapsFontData() const
503 {
504     if (!m_smallCapsFontData) {
505         NS_DURING
506             float size = [m_font.font pointSize] * SMALLCAPS_FONTSIZE_MULTIPLIER;
507             FontPlatformData smallCapsFont([[NSFontManager sharedFontManager] convertFont:m_font.font toSize:size]);
508             m_smallCapsFontData = (FontData*)rendererForAlternateFont(this, smallCapsFont);
509         NS_HANDLER
510             NSLog(@"uncaught exception selecting font for small caps: %@", localException);
511         NS_ENDHANDLER
512     }
513     return m_smallCapsFontData;
514 }
515
516 static inline bool fontContainsString(NSFont *font, NSString *string)
517 {
518     NSCharacterSet *set = [[font coveredCharacterSet] invertedSet];
519     return set && [string rangeOfCharacterFromSet:set].location == NSNotFound;
520 }
521
522 static NSFont *findSubstituteFont(const FontData *renderer, NSString *string, NSString **families)
523 {
524     NSFont *substituteFont = nil;
525
526     // First search the CSS family fallback list.
527     // Start at 1 (2nd font) because we've already failed on the first lookup.
528     NSString *family = nil;
529     int i = 1;
530     while (families && families[i]) {
531         family = families[i++];
532         NSFont *f = [[WebTextRendererFactory sharedFactory] cachedFontFromFamily:family
533             traits:[[NSFontManager sharedFontManager] traitsOfFont:renderer->m_font.font]
534             size:[renderer->m_font.font pointSize]];
535         if (f && fontContainsString(f, string)) {
536             substituteFont = f; 
537             break;
538         }
539     }
540     
541     // Now do string based lookup.
542     if (substituteFont == nil)
543         substituteFont = wkGetFontInLanguageForRange(renderer->m_font.font, string, NSMakeRange(0, [string length]));
544
545     // Now do character based lookup.
546     if (substituteFont == nil && [string length] == 1)
547         substituteFont = wkGetFontInLanguageForCharacter(renderer->m_font.font, [string characterAtIndex:0]);
548
549     // Check to make sure this is a distinct font.
550     if (substituteFont && [[substituteFont screenFont] isEqual:[renderer->m_font.font screenFont]])
551         substituteFont = nil;
552
553     // Now that we have a substitute font, attempt to match it to the best variation.
554     // If we have a good match return that, otherwise return the font the AppKit has found.
555     if (substituteFont) {
556         NSFontManager *manager = [NSFontManager sharedFontManager];
557         NSFont *bestVariation = [manager fontWithFamily:[substituteFont familyName]
558             traits:[manager traitsOfFont:renderer->m_font.font]
559             weight:[manager weightOfFont:renderer->m_font.font]
560             size:[renderer->m_font.font pointSize]];
561         if (bestVariation)
562             substituteFont = bestVariation;
563     }
564
565     return substituteFont;
566 }
567
568 static const FontData *rendererForAlternateFont(const FontData *renderer, FontPlatformData alternateFont)
569 {
570     if (!alternateFont.font)
571         return nil;
572
573     NSFontManager *fontManager = [NSFontManager sharedFontManager];
574     NSFontTraitMask fontTraits = [fontManager traitsOfFont:renderer->m_font.font];
575     if (renderer->m_font.syntheticBold)
576         fontTraits |= NSBoldFontMask;
577     if (renderer->m_font.syntheticOblique)
578         fontTraits |= NSItalicFontMask;
579     NSFontTraitMask alternateFontTraits = [fontManager traitsOfFont:alternateFont.font];
580
581     alternateFont.syntheticBold = (fontTraits & NSBoldFontMask) && !(alternateFontTraits & NSBoldFontMask);
582     alternateFont.syntheticOblique = (fontTraits & NSItalicFontMask) && !(alternateFontTraits & NSItalicFontMask);
583     alternateFont.forPrinter = renderer->m_font.forPrinter;
584
585     return [[WebTextRendererFactory sharedFactory] rendererWithFont:alternateFont];
586 }
587
588 static const FontData *findSubstituteRenderer(const FontData *renderer, const unichar *characters, int numCharacters, NSString **families)
589 {
590     NSString *string = [[NSString alloc] initWithCharactersNoCopy:(unichar *)characters length: numCharacters freeWhenDone: NO];
591     FontPlatformData substituteFont(findSubstituteFont(renderer, string, families));
592     [string release];
593     return rendererForAlternateFont(renderer, substituteFont);
594 }
595
596 const FontData* FontData::findSubstituteFontData(const UChar* characters, unsigned numCharacters, const FontDescription& fontDescription) const
597 {
598     CREATE_FAMILY_ARRAY(fontDescription, families);
599     return findSubstituteRenderer(this, (const unichar*)characters, numCharacters, families);
600 }
601
602 // Nasty hack to determine if we should round or ceil space widths.
603 // If the font is monospace or fake monospace we ceil to ensure that 
604 // every character and the space are the same width.  Otherwise we round.
605 static bool computeWidthForSpace(FontData *renderer)
606 {
607     renderer->m_spaceGlyph = extendGlyphMap(renderer, SPACE);
608     if (renderer->m_spaceGlyph == 0)
609         return NO;
610
611     float width = renderer->widthForGlyph(renderer->m_spaceGlyph);
612
613     renderer->m_spaceWidth = width;
614
615     renderer->m_treatAsFixedPitch = [[WebTextRendererFactory sharedFactory] isFontFixedPitch:renderer->m_font];
616     renderer->m_adjustedSpaceWidth = renderer->m_treatAsFixedPitch ? ceilf(width) : roundf(width);
617     
618     return YES;
619 }
620
621 static bool setUpFont(FontData *renderer)
622 {
623     renderer->m_font.font = renderer->m_font.forPrinter ? [renderer->m_font.font printerFont] : [renderer->m_font.font screenFont];
624
625     ATSUStyle fontStyle;
626     if (ATSUCreateStyle(&fontStyle) != noErr)
627         return NO;
628
629     if (!fillStyleWithAttributes(fontStyle, renderer->m_font.font)) {
630         ATSUDisposeStyle(fontStyle);
631         return NO;
632     }
633
634     if (wkGetATSStyleGroup(fontStyle, &renderer->m_styleGroup) != noErr) {
635         ATSUDisposeStyle(fontStyle);
636         return NO;
637     }
638
639     ATSUDisposeStyle(fontStyle);
640
641     if (!computeWidthForSpace(renderer)) {
642         freeGlyphMap(renderer->m_characterToGlyphMap);
643         renderer->m_characterToGlyphMap = 0;
644         wkReleaseStyleGroup(renderer->m_styleGroup);
645         renderer->m_styleGroup = 0;
646         return NO;
647     }
648     
649     return YES;
650 }
651
652 #if !ERROR_DISABLED
653
654 static NSString *pathFromFont(NSFont *font)
655 {
656     FSSpec oFile;
657     OSStatus status = ATSFontGetFileSpecification(FMGetATSFontRefFromFont((FMFont)wkGetNSFontATSUFontId(font)), &oFile);
658     if (status == noErr) {
659         OSErr err;
660         FSRef fileRef;
661         err = FSpMakeFSRef(&oFile, &fileRef);
662         if (err == noErr) {
663             UInt8 filePathBuffer[PATH_MAX];
664             status = FSRefMakePath(&fileRef, filePathBuffer, PATH_MAX);
665             if (status == noErr)
666                 return [NSString stringWithUTF8String:(const char *)filePathBuffer];
667         }
668     }
669     return nil;
670 }
671
672 #endif
673
674 static NSRect CG_selectionRect(FontData *renderer, const WebCoreTextRun * run, const WebCoreTextStyle *style, const WebCoreTextGeometry *geometry)
675 {
676     float yPos = geometry->useFontMetricsForSelectionYAndHeight
677         ? geometry->point.y() - renderer->ascent() - (renderer->lineGap() / 2) : geometry->selectionY;
678     float height = geometry->useFontMetricsForSelectionYAndHeight
679         ? renderer->lineSpacing() : geometry->selectionHeight;
680
681     WebCoreTextRun completeRun = *run;
682     completeRun.from = 0;
683     completeRun.to = run->length;
684
685     WidthIterator it;
686     initializeWidthIterator(&it, renderer, &completeRun, style);
687     
688     advanceWidthIterator(&it, run->from, 0, 0, 0);
689     float beforeWidth = it.runWidthSoFar;
690     advanceWidthIterator(&it, run->to, 0, 0, 0);
691     float afterWidth = it.runWidthSoFar;
692     // Using roundf() rather than ceilf() for the right edge as a compromise to ensure correct caret positioning
693     if (style->rtl) {
694         advanceWidthIterator(&it, run->length, 0, 0, 0);
695         float totalWidth = it.runWidthSoFar;
696         return NSMakeRect(geometry->point.x() + floorf(totalWidth - afterWidth), yPos, roundf(totalWidth - beforeWidth) - floorf(totalWidth - afterWidth), height);
697     } else {
698         return NSMakeRect(geometry->point.x() + floorf(beforeWidth), yPos, roundf(afterWidth) - floorf(beforeWidth), height);
699     }
700 }
701
702 static float CG_floatWidthForRun(FontData *renderer, const WebCoreTextRun *run, const WebCoreTextStyle *style, float *widthBuffer, FontData **rendererBuffer, CGGlyph *glyphBuffer, float *startPosition, int *numGlyphsResult)
703 {
704     WidthIterator it;
705     WebCoreTextRun completeRun;
706     const WebCoreTextRun *aRun;
707     if (!style->rtl)
708         aRun = run;
709     else {
710         completeRun = *run;
711         completeRun.to = run->length;
712         aRun = &completeRun;
713     }
714     initializeWidthIterator(&it, renderer, aRun, style);
715     int numGlyphs = advanceWidthIterator(&it, run->to, widthBuffer, rendererBuffer, glyphBuffer);
716     float runWidth = it.runWidthSoFar;
717     if (startPosition) {
718         if (!style->rtl)
719             *startPosition = it.widthToStart;
720         else {
721             float finalRoundingWidth = it.finalRoundingWidth;
722             advanceWidthIterator(&it, run->length, 0, 0, 0);
723             *startPosition = it.runWidthSoFar - runWidth + finalRoundingWidth;
724         }
725     }
726     if (numGlyphsResult)
727         *numGlyphsResult = numGlyphs;
728     return runWidth;
729 }
730
731 void FontData::updateGlyphMapEntry(UChar c, ATSGlyphRef glyph, const FontData *substituteRenderer) const
732 {
733     GlyphMap *map;
734     for (map = m_characterToGlyphMap; map; map = map->next) {
735         UChar32 start = map->startRange;
736         if (c >= start && c <= map->endRange) {
737             int i = c - start;
738             map->glyphs[i].glyph = glyph;
739             // This renderer will leak.
740             // No problem though; we want it to stick around forever.
741             // Max theoretical retain counts applied here will be num_fonts_on_system * num_glyphs_in_font.
742             map->glyphs[i].renderer = substituteRenderer;
743             break;
744         }
745     }
746 }
747
748 static ATSGlyphRef extendGlyphMap(const FontData *renderer, UChar32 c)
749 {
750     GlyphMap *map = new GlyphMap;
751     ATSLayoutRecord *glyphRecord;
752     char glyphVector[WKGlyphVectorSize];
753     UChar32 end, start;
754     unsigned blockSize;
755     
756     if (renderer->m_characterToGlyphMap == 0)
757         blockSize = INITIAL_BLOCK_SIZE;
758     else
759         blockSize = INCREMENTAL_BLOCK_SIZE;
760     start = (c / blockSize) * blockSize;
761     end = start + (blockSize - 1);
762
763     map->startRange = start;
764     map->endRange = end;
765     map->next = 0;
766     
767     unsigned i;
768     unsigned count = end - start + 1;
769     unsigned short buffer[INCREMENTAL_BLOCK_SIZE * 2 + 2];
770     unsigned bufferLength;
771
772     if (start < 0x10000) {
773         bufferLength = count;
774         for (i = 0; i < count; i++)
775             buffer[i] = i + start;
776
777         if (start == 0) {
778             // Control characters must not render at all.
779             for (i = 0; i < 0x20; ++i)
780                 buffer[i] = ZERO_WIDTH_SPACE;
781             buffer[0x7F] = ZERO_WIDTH_SPACE;
782
783             // But \n, \t, and nonbreaking space must render as a space.
784             buffer[(int)'\n'] = ' ';
785             buffer[(int)'\t'] = ' ';
786             buffer[NO_BREAK_SPACE] = ' ';
787         }
788     } else {
789         bufferLength = count * 2;
790         for (i = 0; i < count; i++) {
791             int c = i + start;
792             buffer[i * 2] = U16_LEAD(c);
793             buffer[i * 2 + 1] = U16_TRAIL(c);
794         }
795     }
796
797     OSStatus status = wkInitializeGlyphVector(count, &glyphVector);
798     if (status != noErr) {
799         // This should never happen, perhaps indicates a bad font!  If it does the
800         // font substitution code will find an alternate font.
801         delete map;
802         return 0;
803     }
804
805     wkConvertCharToGlyphs(renderer->m_styleGroup, &buffer[0], bufferLength, &glyphVector);
806     unsigned numGlyphs = wkGetGlyphVectorNumGlyphs(&glyphVector);
807     if (numGlyphs != count) {
808         // This should never happen, perhaps indicates a bad font?
809         // If it does happen, the font substitution code will find an alternate font.
810         wkClearGlyphVector(&glyphVector);
811         delete map;
812         return 0;
813     }
814
815     map->glyphs = new GlyphEntry[count];
816     glyphRecord = (ATSLayoutRecord *)wkGetGlyphVectorFirstRecord(glyphVector);
817     for (i = 0; i < count; i++) {
818         map->glyphs[i].glyph = glyphRecord->glyphID;
819         map->glyphs[i].renderer = renderer;
820         glyphRecord = (ATSLayoutRecord *)((char *)glyphRecord + wkGetGlyphVectorRecordSize(glyphVector));
821     }
822     wkClearGlyphVector(&glyphVector);
823     
824     if (renderer->m_characterToGlyphMap == 0)
825         renderer->m_characterToGlyphMap = map;
826     else {
827         GlyphMap *lastMap = renderer->m_characterToGlyphMap;
828         while (lastMap->next != 0)
829             lastMap = lastMap->next;
830         lastMap->next = map;
831     }
832
833     ATSGlyphRef glyph = map->glyphs[c - start].glyph;
834
835     // Special case for characters 007F-00A0.
836     if (glyph == 0 && c >= 0x7F && c <= 0xA0) {
837         glyph = wkGetDefaultGlyphForChar(renderer->m_font.font, c);
838         map->glyphs[c - start].glyph = glyph;
839     }
840
841     return glyph;
842 }
843
844 static WidthMap *extendWidthMap(const FontData *renderer, ATSGlyphRef glyph)
845 {
846     WidthMap *map = new WidthMap;
847     unsigned end;
848     ATSGlyphRef start;
849     unsigned blockSize;
850     unsigned i, count;
851     
852     NSFont *f = renderer->m_font.font;
853     if (renderer->m_glyphToWidthMap == 0) {
854         if ([f numberOfGlyphs] < INITIAL_BLOCK_SIZE)
855             blockSize = [f numberOfGlyphs];
856          else
857             blockSize = INITIAL_BLOCK_SIZE;
858     } else {
859         blockSize = INCREMENTAL_BLOCK_SIZE;
860     }
861     if (blockSize == 0) {
862         start = 0;
863     } else {
864         start = (glyph / blockSize) * blockSize;
865     }
866     end = ((unsigned)start) + blockSize; 
867
868     map->startRange = start;
869     map->endRange = end;
870     count = end - start + 1;
871
872     map->widths = new WebGlyphWidth[count];
873     for (i = 0; i < count; i++)
874         map->widths[i] = NAN;
875
876     if (renderer->m_glyphToWidthMap == 0)
877         renderer->m_glyphToWidthMap = map;
878     else {
879         WidthMap *lastMap = renderer->m_glyphToWidthMap;
880         while (lastMap->next != 0)
881             lastMap = lastMap->next;
882         lastMap->next = map;
883     }
884
885     return map;
886 }
887
888 static void initializeATSUStyle(FontData *renderer)
889 {
890     // The two NSFont calls in this method (pointSize and _atsFontID) do not raise exceptions.
891
892     if (!renderer->m_ATSUStyleInitialized) {
893         OSStatus status;
894         ByteCount propTableSize;
895         
896         status = ATSUCreateStyle(&renderer->m_ATSUStyle);
897         if (status != noErr)
898             LOG_ERROR("ATSUCreateStyle failed (%d)", status);
899     
900         ATSUFontID fontID = wkGetNSFontATSUFontId(renderer->m_font.font);
901         if (fontID == 0) {
902             ATSUDisposeStyle(renderer->m_ATSUStyle);
903             LOG_ERROR("unable to get ATSUFontID for %@", renderer->m_font.font);
904             return;
905         }
906         
907         CGAffineTransform transform = CGAffineTransformMakeScale(1, -1);
908         if (renderer->m_font.syntheticOblique)
909             transform = CGAffineTransformConcat(transform, CGAffineTransformMake(1, 0, -tanf(SYNTHETIC_OBLIQUE_ANGLE * acosf(0) / 90), 1, 0, 0)); 
910         Fixed fontSize = FloatToFixed([renderer->m_font.font pointSize]);
911         // Turn off automatic kerning until it is supported in the CG code path (6136 in bugzilla)
912         Fract kerningInhibitFactor = FloatToFract(1.0);
913         ATSUAttributeTag styleTags[4] = { kATSUSizeTag, kATSUFontTag, kATSUFontMatrixTag, kATSUKerningInhibitFactorTag };
914         ByteCount styleSizes[4] = { sizeof(Fixed), sizeof(ATSUFontID), sizeof(CGAffineTransform), sizeof(Fract) };
915         ATSUAttributeValuePtr styleValues[4] = { &fontSize, &fontID, &transform, &kerningInhibitFactor };
916         status = ATSUSetAttributes(renderer->m_ATSUStyle, 4, styleTags, styleSizes, styleValues);
917         if (status != noErr)
918             LOG_ERROR("ATSUSetAttributes failed (%d)", status);
919         status = ATSFontGetTable(fontID, 'prop', 0, 0, 0, &propTableSize);
920         if (status == noErr)    // naively assume that if a 'prop' table exists then it contains mirroring info
921             renderer->m_ATSUMirrors = true;
922         else if (status == kATSInvalidFontTableAccess)
923             renderer->m_ATSUMirrors = false;
924         else
925             LOG_ERROR("ATSFontGetTable failed (%d)", status);
926
927         // Turn off ligatures such as 'fi' to match the CG code path's behavior, until bugzilla 6135 is fixed.
928         // Don't be too aggressive: if the font doesn't contain 'a', then assume that any ligatures it contains are
929         // in characters that always go through ATSUI, and therefore allow them. Geeza Pro is an example.
930         // See bugzilla 5166.
931         if ([[renderer->m_font.font coveredCharacterSet] characterIsMember:'a']) {
932             ATSUFontFeatureType featureTypes[] = { kLigaturesType };
933             ATSUFontFeatureSelector featureSelectors[] = { kCommonLigaturesOffSelector };
934             status = ATSUSetFontFeatures(renderer->m_ATSUStyle, 1, featureTypes, featureSelectors);
935         }
936
937         renderer->m_ATSUStyleInitialized = true;
938     }
939 }
940
941 static void createATSULayoutParameters(ATSULayoutParameters *params, FontData *renderer, const WebCoreTextRun *run, const WebCoreTextStyle *style)
942 {
943     params->run = run;
944     params->style = style;
945     // FIXME: It is probably best to always allocate a buffer for RTL, since even if for this
946     // renderer ATSUMirrors is true, for a substitute renderer it might be false.
947     FontData** renderers = new FontData*[run->length];
948     params->renderers = renderers;
949     UniChar *charBuffer = (UniChar*)((style->smallCaps || (style->rtl && !renderer->m_ATSUMirrors)) ? new UniChar[run->length] : 0);
950     params->charBuffer = charBuffer;
951     params->syntheticBoldPass = false;
952
953     // The only Cocoa calls here are to NSGraphicsContext, which does not raise exceptions.
954
955     ATSUTextLayout layout;
956     OSStatus status;
957     ATSULayoutOperationOverrideSpecifier overrideSpecifier;
958     
959     initializeATSUStyle(renderer);
960     
961     // FIXME: This is currently missing the following required features that the CoreGraphics code path has:
962     // - \n, \t, and nonbreaking space render as a space.
963     // - Other control characters do not render (other code path uses zero-width spaces).
964
965     UniCharCount totalLength = run->length;
966     UniCharArrayOffset runTo = (run->to == -1 ? totalLength : (unsigned int)run->to);
967     UniCharArrayOffset runFrom = run->from;
968     
969     if (charBuffer)
970         memcpy(charBuffer, run->characters, totalLength * sizeof(UniChar));
971
972     UniCharCount runLength = runTo - runFrom;
973     
974     status = ATSUCreateTextLayoutWithTextPtr(
975             (charBuffer ? charBuffer : run->characters),
976             runFrom,        // offset
977             runLength,      // length
978             totalLength,    // total length
979             1,              // styleRunCount
980             &runLength,     // length of style run
981             &renderer->m_ATSUStyle, 
982             &layout);
983     if (status != noErr)
984         LOG_ERROR("ATSUCreateTextLayoutWithTextPtr failed(%d)", status);
985     params->layout = layout;
986     ATSUSetTextLayoutRefCon(layout, (UInt32)params);
987
988     CGContextRef cgContext = (CGContextRef)[[NSGraphicsContext currentContext] graphicsPort];
989     ATSLineLayoutOptions lineLayoutOptions = kATSLineKeepSpacesOutOfMargin | kATSLineHasNoHangers;
990     Boolean rtl = style->rtl;
991     overrideSpecifier.operationSelector = kATSULayoutOperationPostLayoutAdjustment;
992     overrideSpecifier.overrideUPP = overrideLayoutOperation;
993     ATSUAttributeTag tags[] = { kATSUCGContextTag, kATSULineLayoutOptionsTag, kATSULineDirectionTag, kATSULayoutOperationOverrideTag };
994     ByteCount sizes[] = { sizeof(CGContextRef), sizeof(ATSLineLayoutOptions), sizeof(Boolean), sizeof(ATSULayoutOperationOverrideSpecifier) };
995     ATSUAttributeValuePtr values[] = { &cgContext, &lineLayoutOptions, &rtl, &overrideSpecifier };
996     
997     status = ATSUSetLayoutControls(layout, (style->applyWordRounding ? 4 : 3), tags, sizes, values);
998     if (status != noErr)
999         LOG_ERROR("ATSUSetLayoutControls failed(%d)", status);
1000
1001     status = ATSUSetTransientFontMatching(layout, YES);
1002     if (status != noErr)
1003         LOG_ERROR("ATSUSetTransientFontMatching failed(%d)", status);
1004
1005     params->hasSyntheticBold = false;
1006     ATSUFontID ATSUSubstituteFont;
1007     UniCharArrayOffset substituteOffset = runFrom;
1008     UniCharCount substituteLength;
1009     UniCharArrayOffset lastOffset;
1010     FontData *substituteRenderer = 0;
1011
1012     while (substituteOffset < runTo) {
1013         lastOffset = substituteOffset;
1014         status = ATSUMatchFontsToText(layout, substituteOffset, kATSUToTextEnd, &ATSUSubstituteFont, &substituteOffset, &substituteLength);
1015         if (status == kATSUFontsMatched || status == kATSUFontsNotMatched) {
1016             substituteRenderer = (FontData*)findSubstituteRenderer(renderer, run->characters+substituteOffset, substituteLength, style->families);
1017             if (substituteRenderer) {
1018                 initializeATSUStyle(substituteRenderer);
1019                 if (substituteRenderer->m_ATSUStyle)
1020                     ATSUSetRunStyle(layout, substituteRenderer->m_ATSUStyle, substituteOffset, substituteLength);
1021             } else
1022                 substituteRenderer = renderer;
1023         } else {
1024             substituteOffset = runTo;
1025             substituteLength = 0;
1026         }
1027
1028         bool isSmallCap = false;
1029         UniCharArrayOffset firstSmallCap = 0;
1030         FontData *r = renderer;
1031         UniCharArrayOffset i;
1032         for (i = lastOffset;  ; i++) {
1033             if (i == substituteOffset || i == substituteOffset + substituteLength) {
1034                 if (isSmallCap) {
1035                     isSmallCap = false;
1036                     initializeATSUStyle(r->smallCapsFontData());
1037                     ATSUSetRunStyle(layout, r->smallCapsFontData()->m_ATSUStyle, firstSmallCap, i - firstSmallCap);
1038                 }
1039                 if (i == substituteOffset && substituteLength > 0)
1040                     r = substituteRenderer;
1041                 else
1042                     break;
1043             }
1044             if (rtl && charBuffer && !r->m_ATSUMirrors)
1045                 charBuffer[i] = u_charMirror(charBuffer[i]);
1046             if (style->smallCaps) {
1047                 UniChar c = charBuffer[i];
1048                 UniChar newC;
1049                 if (U_GET_GC_MASK(c) & U_GC_M_MASK)
1050                     renderers[i] = isSmallCap ? r->smallCapsFontData() : r;
1051                 else if (!u_isUUppercase(c) && (newC = u_toupper(c)) != c) {
1052                     charBuffer[i] = newC;
1053                     if (!isSmallCap) {
1054                         isSmallCap = true;
1055                         firstSmallCap = i;
1056                     }
1057                     renderers[i] = r->smallCapsFontData();
1058                 } else {
1059                     if (isSmallCap) {
1060                         isSmallCap = false;
1061                         initializeATSUStyle(r->smallCapsFontData());
1062                         ATSUSetRunStyle(layout, r->smallCapsFontData()->m_ATSUStyle, firstSmallCap, i - firstSmallCap);
1063                     }
1064                     renderers[i] = r;
1065                 }
1066             } else
1067                 renderers[i] = r;
1068             if (renderers[i]->m_syntheticBoldOffset)
1069                 params->hasSyntheticBold = true;
1070         }
1071         substituteOffset += substituteLength;
1072     }
1073     if (style->padding) {
1074         float numSpaces = 0;
1075         unsigned k;
1076         for (k = 0; k < totalLength; k++)
1077             if (Font::treatAsSpace(run->characters[k]))
1078                 numSpaces++;
1079
1080         params->padPerSpace = ceilf(style->padding / numSpaces);
1081     } else
1082         params->padPerSpace = 0;
1083 }
1084
1085 static void disposeATSULayoutParameters(ATSULayoutParameters *params)
1086 {
1087     ATSUDisposeTextLayout(params->layout);
1088     delete []params->charBuffer;
1089     delete []params->renderers;
1090 }
1091
1092 // Be sure to free the run.characters allocated by this function.
1093 static WebCoreTextRun addDirectionalOverride(const WebCoreTextRun *run, bool rtl)
1094 {
1095     int from = run->from;
1096     int to = run->to;
1097     if (from == -1)
1098         from = 0;
1099     if (to == -1)
1100         to = run->length;
1101
1102     UniChar *charactersWithOverride = new UniChar[run->length + 2];
1103
1104     charactersWithOverride[0] = rtl ? RIGHT_TO_LEFT_OVERRIDE : LEFT_TO_RIGHT_OVERRIDE;
1105     memcpy(&charactersWithOverride[1], &run->characters[0], sizeof(UniChar) * run->length);
1106     charactersWithOverride[run->length + 1] = POP_DIRECTIONAL_FORMATTING;
1107
1108     WebCoreTextRun runWithOverride;
1109
1110     runWithOverride.from = from + 1;
1111     runWithOverride.to = to + 1;
1112     runWithOverride.length = run->length + 2;
1113     runWithOverride.characters = charactersWithOverride;
1114
1115     return runWithOverride;
1116 }
1117
1118 static NSRect ATSU_selectionRect(FontData *renderer, const WebCoreTextRun *run, const WebCoreTextStyle *style, const WebCoreTextGeometry *geometry)
1119 {
1120     int from = run->from;
1121     int to = run->to;
1122     if (from == -1)
1123         from = 0;
1124     if (to == -1)
1125         to = run->length;
1126         
1127     WebCoreTextRun completeRun = *run;
1128     completeRun.from = 0;
1129     completeRun.to = run->length;
1130     
1131     WebCoreTextRun *aRun = &completeRun;
1132     WebCoreTextRun swappedRun;
1133     
1134     if (style->directionalOverride) {
1135         swappedRun = addDirectionalOverride(aRun, style->rtl);
1136         aRun = &swappedRun;
1137         from++;
1138         to++;
1139     }
1140    
1141     ATSULayoutParameters params;
1142     createATSULayoutParameters(&params, renderer, aRun, style);
1143     
1144     ATSTrapezoid firstGlyphBounds;
1145     ItemCount actualNumBounds;
1146     
1147     OSStatus status = ATSUGetGlyphBounds(params.layout, 0, 0, from, to - from, kATSUseFractionalOrigins, 1, &firstGlyphBounds, &actualNumBounds);
1148     if (status != noErr || actualNumBounds != 1) {
1149         static ATSTrapezoid zeroTrapezoid = { {0, 0}, {0, 0}, {0, 0}, {0, 0} };
1150         firstGlyphBounds = zeroTrapezoid;
1151     }
1152     disposeATSULayoutParameters(&params);    
1153     
1154     float beforeWidth = MIN(FixedToFloat(firstGlyphBounds.lowerLeft.x), FixedToFloat(firstGlyphBounds.upperLeft.x));
1155     float afterWidth = MAX(FixedToFloat(firstGlyphBounds.lowerRight.x), FixedToFloat(firstGlyphBounds.upperRight.x));
1156     float yPos = geometry->useFontMetricsForSelectionYAndHeight
1157         ? geometry->point.y() - renderer->ascent() : geometry->selectionY;
1158     float height = geometry->useFontMetricsForSelectionYAndHeight
1159         ? renderer->lineSpacing() : geometry->selectionHeight;
1160
1161     NSRect rect = NSMakeRect(geometry->point.x() + floorf(beforeWidth), yPos, roundf(afterWidth) - floorf(beforeWidth), height);
1162
1163     if (style->directionalOverride)
1164         delete []swappedRun.characters;
1165
1166     return rect;
1167 }
1168
1169 static int ATSU_pointToOffset(FontData *renderer, const WebCoreTextRun *run, const WebCoreTextStyle *style,
1170     int x, bool includePartialGlyphs)
1171 {
1172     const WebCoreTextRun *aRun = run;
1173     WebCoreTextRun swappedRun;
1174     
1175     // Enclose in LRO/RLO - PDF to force ATSU to render visually.
1176     if (style->directionalOverride) {
1177         swappedRun = addDirectionalOverride(aRun, style->rtl);
1178         aRun = &swappedRun;
1179     }
1180
1181     ATSULayoutParameters params;
1182     createATSULayoutParameters(&params, renderer, aRun, style);
1183
1184     UniCharArrayOffset primaryOffset = aRun->from;
1185     
1186     // FIXME: No idea how to avoid including partial glyphs.
1187     // Not even sure if that's the behavior this yields now.
1188     Boolean isLeading;
1189     UniCharArrayOffset secondaryOffset = 0;
1190     OSStatus status = ATSUPositionToOffset(params.layout, FloatToFixed(x), FloatToFixed(-1), &primaryOffset, &isLeading, &secondaryOffset);
1191     unsigned offset;
1192     if (status == noErr) {
1193         offset = (unsigned)primaryOffset;
1194     } else {
1195         // Failed to find offset!  Return 0 offset.
1196         offset = 0;
1197     }
1198
1199     disposeATSULayoutParameters(&params);
1200     
1201     if (style->directionalOverride)
1202         delete []swappedRun.characters;
1203
1204     return offset - aRun->from;
1205 }
1206
1207 static bool advanceWidthIteratorOneCharacter(WidthIterator *iterator, float *totalWidth)
1208 {
1209     float widths[MAX_GLYPH_EXPANSION];
1210     FontData *renderers[MAX_GLYPH_EXPANSION];
1211     ATSGlyphRef glyphs[MAX_GLYPH_EXPANSION];            
1212     unsigned numGlyphs = advanceWidthIterator(iterator, iterator->currentCharacter + 1, widths, renderers, glyphs);
1213     unsigned i;
1214     float w = 0;
1215     for (i = 0; i < numGlyphs; ++i)
1216         w += widths[i];
1217     *totalWidth = w;
1218     return numGlyphs != 0;
1219 }
1220
1221 static int CG_pointToOffset(FontData *renderer, const WebCoreTextRun * run, const WebCoreTextStyle *style,
1222     int x, bool includePartialGlyphs)
1223 {
1224     float delta = (float)x;
1225
1226     WidthIterator it;    
1227     initializeWidthIterator(&it, renderer, run, style);
1228
1229     unsigned offset;
1230
1231     if (style->rtl) {
1232         delta -= CG_floatWidthForRun(renderer, run, style, 0, 0, 0, 0, 0);
1233         while (1) {
1234             offset = it.currentCharacter;
1235             float w;
1236             if (!advanceWidthIteratorOneCharacter(&it, &w))
1237                 break;
1238             delta += w;
1239             if (includePartialGlyphs) {
1240                 if (delta - w / 2 >= 0)
1241                     break;
1242             } else {
1243                 if (delta >= 0)
1244                     break;
1245             }
1246         }
1247     } else {
1248         while (1) {
1249             offset = it.currentCharacter;
1250             float w;
1251             if (!advanceWidthIteratorOneCharacter(&it, &w))
1252                 break;
1253             delta -= w;
1254             if (includePartialGlyphs) {
1255                 if (delta + w / 2 <= 0)
1256                     break;
1257             } else {
1258                 if (delta <= 0)
1259                     break;
1260             }
1261         }
1262     }
1263
1264     return offset - run->from;
1265 }
1266
1267 static void freeWidthMap(WidthMap *map)
1268 {
1269     while (map) {
1270         WidthMap *next = map->next;
1271         delete []map->widths;
1272         delete map;
1273         map = next;
1274     }
1275 }
1276
1277 static void freeGlyphMap(GlyphMap *map)
1278 {
1279     while (map) {
1280         GlyphMap *next = map->next;
1281         delete []map->glyphs;
1282         delete map;
1283         map = next;
1284     }
1285 }
1286
1287 Glyph FontData::glyphForCharacter(const FontData **renderer, unsigned c) const
1288 {
1289     // this loop is hot, so it is written to avoid LSU stalls
1290     GlyphMap *map;
1291     GlyphMap *nextMap;
1292     for (map = (*renderer)->m_characterToGlyphMap; map; map = nextMap) {
1293         UChar start = map->startRange;
1294         nextMap = map->next;
1295         if (c >= start && c <= map->endRange) {
1296             GlyphEntry *ge = &map->glyphs[c - start];
1297             *renderer = ge->renderer;
1298             return ge->glyph;
1299         }
1300     }
1301
1302     return extendGlyphMap(*renderer, c);
1303 }
1304
1305 static void initializeWidthIterator(WidthIterator *iterator, FontData *renderer, const WebCoreTextRun *run, const WebCoreTextStyle *style) 
1306 {
1307     iterator->renderer = renderer;
1308     iterator->run = run;
1309     iterator->style = style;
1310     iterator->currentCharacter = run->from;
1311     iterator->runWidthSoFar = 0;
1312     iterator->finalRoundingWidth = 0;
1313
1314     // If the padding is non-zero, count the number of spaces in the run
1315     // and divide that by the padding for per space addition.
1316     if (!style->padding) {
1317         iterator->padding = 0;
1318         iterator->padPerSpace = 0;
1319     } else {
1320         float numSpaces = 0;
1321         int k;
1322         for (k = run->from; k < run->to; k++)
1323             if (Font::treatAsSpace(run->characters[k]))
1324                 numSpaces++;
1325
1326         iterator->padding = style->padding;
1327         iterator->padPerSpace = ceilf(iterator->padding / numSpaces);
1328     }
1329     
1330     // Calculate width up to starting position of the run.  This is
1331     // necessary to ensure that our rounding hacks are always consistently
1332     // applied.
1333     if (run->from == 0) {
1334         iterator->widthToStart = 0;
1335     } else {
1336         WebCoreTextRun startPositionRun = *run;
1337         startPositionRun.from = 0;
1338         startPositionRun.to = run->length;
1339         WidthIterator startPositionIterator;
1340         initializeWidthIterator(&startPositionIterator, renderer, &startPositionRun, style);
1341         advanceWidthIterator(&startPositionIterator, run->from, 0, 0, 0);
1342         iterator->widthToStart = startPositionIterator.runWidthSoFar;
1343     }
1344 }
1345
1346 static UChar32 normalizeVoicingMarks(WidthIterator *iterator)
1347 {
1348     unsigned currentCharacter = iterator->currentCharacter;
1349     const WebCoreTextRun *run = iterator->run;
1350     if (currentCharacter + 1 < (unsigned)run->to) {
1351         if (u_getCombiningClass(run->characters[currentCharacter + 1]) == HIRAGANA_KATAKANA_VOICING_MARKS) {
1352             // Normalize into composed form using 3.2 rules.
1353             UChar normalizedCharacters[2] = { 0, 0 };
1354             UErrorCode uStatus = (UErrorCode)0;                
1355             int32_t resultLength = unorm_normalize(&run->characters[currentCharacter], 2,
1356                 UNORM_NFC, UNORM_UNICODE_3_2, &normalizedCharacters[0], 2, &uStatus);
1357             if (resultLength == 1 && uStatus == 0)
1358                 return normalizedCharacters[0];
1359         }
1360     }
1361     return 0;
1362 }
1363
1364 static unsigned advanceWidthIterator(WidthIterator *iterator, unsigned offset, float *widths, FontData **renderersUsed, ATSGlyphRef *glyphsUsed)
1365 {
1366     const WebCoreTextRun *run = iterator->run;
1367     if (offset > (unsigned)run->to)
1368         offset = run->to;
1369
1370     unsigned numGlyphs = 0;
1371
1372     unsigned currentCharacter = iterator->currentCharacter;
1373     const UniChar *cp = &run->characters[currentCharacter];
1374
1375     const WebCoreTextStyle *style = iterator->style;
1376     bool rtl = style->rtl;
1377     bool needCharTransform = rtl || style->smallCaps;
1378     bool hasExtraSpacing = style->letterSpacing || style->wordSpacing || style->padding;
1379
1380     float runWidthSoFar = iterator->runWidthSoFar;
1381     float lastRoundingWidth = iterator->finalRoundingWidth;
1382
1383     while (currentCharacter < offset) {
1384         UChar32 c = *cp;
1385
1386         unsigned clusterLength = 1;
1387         if (c >= 0x3041) {
1388             if (c <= 0x30FE) {
1389                 // Deal with Hiragana and Katakana voiced and semi-voiced syllables.
1390                 // Normalize into composed form, and then look for glyph with base + combined mark.
1391                 // Check above for character range to minimize performance impact.
1392                 UChar32 normalized = normalizeVoicingMarks(iterator);
1393                 if (normalized) {
1394                     c = normalized;
1395                     clusterLength = 2;
1396                 }
1397             } else if (U16_IS_SURROGATE(c)) {
1398                 if (!U16_IS_SURROGATE_LEAD(c))
1399                     break;
1400
1401                 // Do we have a surrogate pair?  If so, determine the full Unicode (32 bit)
1402                 // code point before glyph lookup.
1403                 // Make sure we have another character and it's a low surrogate.
1404                 if (currentCharacter + 1 >= run->length)
1405                     break;
1406                 UniChar low = cp[1];
1407                 if (!U16_IS_TRAIL(low))
1408                     break;
1409                 c = U16_GET_SUPPLEMENTARY(c, low);
1410                 clusterLength = 2;
1411             }
1412         }
1413
1414         const FontData *renderer = iterator->renderer;
1415
1416         if (needCharTransform) {
1417             if (rtl)
1418                 c = u_charMirror(c);
1419
1420             // If small-caps, convert lowercase to upper.
1421             if (style->smallCaps && !u_isUUppercase(c)) {
1422                 UChar32 upperC = u_toupper(c);
1423                 if (upperC != c) {
1424                     c = upperC;
1425                     renderer = renderer->smallCapsFontData();
1426                 }
1427             }
1428         }
1429
1430         Glyph glyph = renderer->glyphForCharacter(&renderer, c);
1431
1432         // Now that we have glyph and font, get its width.
1433         WebGlyphWidth width;
1434         if (c == '\t' && style->tabWidth) {
1435             width = style->tabWidth - fmodf(style->xpos + runWidthSoFar, style->tabWidth);
1436         } else {
1437             width = renderer->widthForGlyph(glyph);
1438             // We special case spaces in two ways when applying word rounding.
1439             // First, we round spaces to an adjusted width in all fonts.
1440             // Second, in fixed-pitch fonts we ensure that all characters that
1441             // match the width of the space character have the same width as the space character.
1442             if (width == renderer->m_spaceWidth && (renderer->m_treatAsFixedPitch || glyph == renderer->m_spaceGlyph) && style->applyWordRounding)
1443                 width = renderer->m_adjustedSpaceWidth;
1444         }
1445
1446         // Try to find a substitute font if this font didn't have a glyph for a character in the
1447         // string. If one isn't found we end up drawing and measuring the 0 glyph, usually a box.
1448         if (glyph == 0 && style->attemptFontSubstitution) {
1449             FontData *substituteRenderer = (FontData*)findSubstituteRenderer(renderer, cp, clusterLength, style->families);
1450             if (substituteRenderer) {
1451                 WebCoreTextRun clusterRun = { cp, clusterLength, 0, clusterLength };
1452                 WebCoreTextStyle clusterStyle = *style;
1453                 clusterStyle.padding = 0;
1454                 clusterStyle.applyRunRounding = NO;
1455                 clusterStyle.attemptFontSubstitution = NO;
1456                 
1457                 int cNumGlyphs;
1458                 float localWidthBuffer[MAX_GLYPH_EXPANSION];
1459                 FontData *localRendererBuffer[MAX_GLYPH_EXPANSION];
1460                 ATSGlyphRef localGlyphBuffer[MAX_GLYPH_EXPANSION];            
1461                 CG_floatWidthForRun(substituteRenderer, &clusterRun, &clusterStyle, localWidthBuffer, localRendererBuffer, localGlyphBuffer, 0, &cNumGlyphs);
1462                 if (cNumGlyphs == 1) {
1463                     assert(substituteRenderer == localRendererBuffer[0]);
1464                     width = localWidthBuffer[0];
1465                     glyph = localGlyphBuffer[0];
1466                     renderer->updateGlyphMapEntry(c, glyph, substituteRenderer);
1467                     renderer = substituteRenderer;
1468                 }
1469             }
1470         }
1471
1472         if (hasExtraSpacing) {
1473             // Account for letter-spacing.
1474             if (width && style->letterSpacing)
1475                 width += style->letterSpacing;
1476
1477             if (Font::treatAsSpace(c)) {
1478                 // Account for padding. WebCore uses space padding to justify text.
1479                 // We distribute the specified padding over the available spaces in the run.
1480                 if (style->padding) {
1481                     // Use left over padding if not evenly divisible by number of spaces.
1482                     if (iterator->padding < iterator->padPerSpace) {
1483                         width += iterator->padding;
1484                         iterator->padding = 0;
1485                     } else {
1486                         width += iterator->padPerSpace;
1487                         iterator->padding -= iterator->padPerSpace;
1488                     }
1489                 }
1490
1491                 // Account for word spacing.
1492                 // We apply additional space between "words" by adding width to the space character.
1493                 if (currentCharacter != 0 && !Font::treatAsSpace(cp[-1]) && style->wordSpacing)
1494                     width += style->wordSpacing;
1495             }
1496         }
1497
1498         // Advance past the character we just dealt with.
1499         cp += clusterLength;
1500         currentCharacter += clusterLength;
1501
1502         // Account for float/integer impedance mismatch between CG and KHTML. "Words" (characters 
1503         // followed by a character defined by isRoundingHackCharacter()) are always an integer width.
1504         // We adjust the width of the last character of a "word" to ensure an integer width.
1505         // If we move KHTML to floats we can remove this (and related) hacks.
1506
1507         float oldWidth = width;
1508
1509         // Force characters that are used to determine word boundaries for the rounding hack
1510         // to be integer width, so following words will start on an integer boundary.
1511         if (style->applyWordRounding && Font::isRoundingHackCharacter(c))
1512             width = ceilf(width);
1513
1514         // Check to see if the next character is a "rounding hack character", if so, adjust
1515         // width so that the total run width will be on an integer boundary.
1516         if ((style->applyWordRounding && currentCharacter < run->length && Font::isRoundingHackCharacter(*cp))
1517                 || (style->applyRunRounding && currentCharacter >= (unsigned)run->to)) {
1518             float totalWidth = iterator->widthToStart + runWidthSoFar + width;
1519             width += ceilf(totalWidth) - totalWidth;
1520         }
1521
1522         runWidthSoFar += width;
1523
1524         if (!widths) {
1525             assert(!renderersUsed);
1526             assert(!glyphsUsed);
1527         } else {
1528             assert(renderersUsed);
1529             assert(glyphsUsed);
1530             *widths++ = (rtl ? oldWidth + lastRoundingWidth : width);
1531             *renderersUsed++ = (FontData*)renderer;
1532             *glyphsUsed++ = glyph;
1533         }
1534
1535         lastRoundingWidth = width - oldWidth;
1536         ++numGlyphs;
1537     }
1538
1539     iterator->currentCharacter = currentCharacter;
1540     iterator->runWidthSoFar = runWidthSoFar;
1541     iterator->finalRoundingWidth = lastRoundingWidth;
1542
1543     return numGlyphs;
1544 }
1545
1546 static bool fillStyleWithAttributes(ATSUStyle style, NSFont *theFont)
1547 {
1548     if (!theFont)
1549         return NO;
1550     ATSUFontID fontId = wkGetNSFontATSUFontId(theFont);
1551     if (!fontId)
1552         return NO;
1553     ATSUAttributeTag tag = kATSUFontTag;
1554     ByteCount size = sizeof(ATSUFontID);
1555     ATSUFontID *valueArray[1] = {&fontId};
1556     OSStatus status = ATSUSetAttributes(style, 1, &tag, &size, (void* const*)valueArray);
1557     if (status != noErr)
1558         return NO;
1559     return YES;
1560 }
1561
1562 static bool shouldUseATSU(const WebCoreTextRun *run)
1563 {
1564     if (Font::gAlwaysUseComplexPath)
1565         return YES;
1566         
1567     const UniChar *characters = run->characters;
1568     int to = run->to;
1569     int i;
1570     // Start from 0 since drawing and highlighting also measure the characters before run->from
1571     for (i = 0; i < to; i++) {
1572         UniChar c = characters[i];
1573         if (c < 0x300)      // U+0300 through U+036F Combining diacritical marks
1574             continue;
1575         if (c <= 0x36F)
1576             return YES;
1577
1578         if (c < 0x0591 || c == 0x05BE)     // U+0591 through U+05CF excluding U+05BE Hebrew combining marks, Hebrew punctuation Paseq, Sof Pasuq and Nun Hafukha
1579             continue;
1580         if (c <= 0x05CF)
1581             return YES;
1582
1583         if (c < 0x0600)     // U+0600 through U+1059 Arabic, Syriac, Thaana, Devanagari, Bengali, Gurmukhi, Gujarati, Oriya, Tamil, Telugu, Kannada, Malayalam, Sinhala, Thai, Lao, Tibetan, Myanmar
1584             continue;
1585         if (c <= 0x1059)
1586             return YES;
1587
1588         if (c < 0x1100)     // U+1100 through U+11FF Hangul Jamo (only Ancient Korean should be left here if you precompose; Modern Korean will be precomposed as a result of step A)
1589             continue;
1590         if (c <= 0x11FF)
1591             return YES;
1592
1593         if (c < 0x1780)     // U+1780 through U+18AF Khmer, Mongolian
1594             continue;
1595         if (c <= 0x18AF)
1596             return YES;
1597
1598         if (c < 0x1900)     // U+1900 through U+194F Limbu (Unicode 4.0)
1599             continue;
1600         if (c <= 0x194F)
1601             return YES;
1602
1603         if (c < 0x20D0)     // U+20D0 through U+20FF Combining marks for symbols
1604             continue;
1605         if (c <= 0x20FF)
1606             return YES;
1607
1608         if (c < 0xFE20)     // U+FE20 through U+FE2F Combining half marks
1609             continue;
1610         if (c <= 0xFE2F)
1611             return YES;
1612     }
1613
1614     return NO;
1615 }
1616
1617 }