6715538135e11dce362a5cb66e4c1e1f54350f56
[WebKit-https.git] / WebKit / WebCoreSupport.subproj / WebTextRenderer.m
1 /*      
2     WebTextRenderer.m       
3     Copyright 2004, Apple, Inc. All rights reserved.
4 */
5
6 #import "WebTextRenderer.h"
7
8 #import <ApplicationServices/ApplicationServices.h>
9 #import <Cocoa/Cocoa.h>
10
11 #import <AppKit/NSFont_Private.h>
12 #import <CoreGraphics/CoreGraphicsPrivate.h>
13 #import <QD/ATSUnicodePriv.h>
14
15 #import <WebCore/WebCoreUnicode.h>
16
17 #import <WebKit/WebGlyphBuffer.h>
18 #import <WebKit/WebGraphicsBridge.h>
19 #import <WebKit/WebKitLogging.h>
20 #import <WebKit/WebNSObjectExtras.h>
21 #import <WebKit/WebTextRendererFactory.h>
22 #import <WebKit/WebUnicode.h>
23
24 #import <float.h>
25
26 #import <unicode/uchar.h>
27
28 // FIXME: FATAL_ALWAYS seems like a bad idea; lets stop using it.
29
30 // SPI from other frameworks.
31
32 @interface NSLanguage : NSObject 
33 + (NSLanguage *)defaultLanguage;
34 @end
35
36 @interface NSFont (WebPrivate)
37 - (ATSUFontID)_atsFontID;
38 - (CGFontRef)_backingCGSFont;
39 // Private method to find a font for a character.
40 + (NSFont *) findFontLike:(NSFont *)aFont forCharacter:(UInt32)c inLanguage:(NSLanguage *) language;
41 + (NSFont *) findFontLike:(NSFont *)aFont forString:(NSString *)string withRange:(NSRange)range inLanguage:(NSLanguage *) language;
42 - (NSGlyph)_defaultGlyphForChar:(unichar)uu;
43 - (BOOL)_isFakeFixedPitch;
44 @end
45
46 // Macros
47 #define SPACE 0x0020
48 #define NO_BREAK_SPACE 0x00A0
49 #define ZERO_WIDTH_SPACE 0x200B
50
51 #define ROUND_TO_INT(x) (int)((x)+.5)
52
53 // Lose precision beyond 1000ths place. This is to work around an apparent
54 // bug in CoreGraphics where there seem to be small errors to some metrics.
55 #define CEIL_TO_INT(x) ((int)(x + 0.999)) /* ((int)(x + 1.0 - FLT_EPSILON)) */
56
57 // MAX_GLYPH_EXPANSION is the maximum numbers of glyphs that may be
58 // use to represent a single Unicode code point.
59 #define MAX_GLYPH_EXPANSION 4
60 #define LOCAL_BUFFER_SIZE 2048
61
62 // Covers Latin-1.
63 #define INITIAL_BLOCK_SIZE 0x200
64
65 // Get additional blocks of glyphs and widths in bigger chunks.
66 // This will typically be for other character sets.
67 #define INCREMENTAL_BLOCK_SIZE 0x400
68
69 #define UNINITIALIZED_GLYPH_WIDTH 65535
70
71 #define ATSFontRefFromNSFont(font) (FMGetATSFontRefFromFont((FMFont)[font _atsFontID]))
72
73 #define SMALLCAPS_FONTSIZE_MULTIPLIER 0.7
74 #define INVALID_WIDTH -(__FLT_MAX__)
75
76 #if !defined(ScaleEmToUnits)
77 #define CONTEXT_DPI     (72.0)
78
79 #define ScaleEmToUnits(X, U_PER_EM)     (X * ((1.0 * CONTEXT_DPI) / (CONTEXT_DPI * U_PER_EM)))
80 #endif
81
82 // Datatypes
83 typedef float WebGlyphWidth;
84 typedef UInt32 UnicodeChar;
85
86 struct WidthEntry {
87     WebGlyphWidth width;
88 };
89
90 struct WidthMap {
91     ATSGlyphRef startRange;
92     ATSGlyphRef endRange;
93     WidthMap *next;
94     WidthEntry *widths;
95 };
96
97 struct GlyphEntry
98 {
99     ATSGlyphRef glyph;
100     NSFont *font;
101 };
102
103 struct GlyphMap {
104     UniChar startRange;
105     UniChar endRange;
106     GlyphMap *next;
107     GlyphEntry *glyphs;
108 };
109
110 struct UnicodeGlyphMap {
111     UnicodeChar startRange;
112     UnicodeChar endRange;
113     UnicodeGlyphMap *next;
114     GlyphEntry *glyphs;
115 };
116
117 struct SubstituteFontWidthMap {
118     NSFont *font;
119     WidthMap *map;
120 };
121
122 struct CharacterWidthIterator
123 {
124     WebTextRenderer *renderer;
125     const WebCoreTextRun *run;
126     const WebCoreTextStyle *style;
127     unsigned currentCharacter;
128     float runWidthSoFar;
129     float widthToStart;
130     int padding;
131     int padPerSpace;
132 };
133
134 // Internal API
135 @interface WebTextRenderer (WebInternal)
136
137 - (NSFont *)_substituteFontForCharacters: (const unichar *)characters length: (int)numCharacters families: (NSString **)families;
138
139 - (WidthMap *)_extendGlyphToWidthMapToInclude:(ATSGlyphRef)glyphID font:(NSFont *)font;
140 - (ATSGlyphRef)_extendCharacterToGlyphMapToInclude:(UniChar) c;
141 - (ATSGlyphRef)_extendUnicodeCharacterToGlyphMapToInclude: (UnicodeChar)c;
142 - (void)_updateGlyphEntryForCharacter: (UniChar)c glyphID: (ATSGlyphRef)glyphID font: (NSFont *)substituteFont;
143
144 - (float)_floatWidthForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style widths:(float *)widthBuffer fonts:(NSFont **)fontBuffer glyphs:(CGGlyph *)glyphBuffer startPosition:(float *)startPosition numGlyphs:(int *)_numGlyphs;
145
146 // Measuring runs.
147 - (float)_CG_floatWidthForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style widths: (float *)widthBuffer fonts: (NSFont **)fontBuffer glyphs: (CGGlyph *)glyphBuffer startPosition:(float *)startPosition numGlyphs: (int *)_numGlyphs;
148 - (float)_ATSU_floatWidthForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style;
149
150 // Drawing runs.
151 - (void)_CG_drawRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style geometry:(const WebCoreTextGeometry *)geometry;
152 - (void)_ATSU_drawRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style geometry:(const WebCoreTextGeometry *)geometry;
153
154 // Selection point detection in runs.
155 - (int)_CG_pointToOffset:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style position:(int)x reversed:(BOOL)reversed includePartialGlyphs:(BOOL)includePartialGlyphs;
156 - (int)_ATSU_pointToOffset:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style position:(int)x reversed:(BOOL)reversed includePartialGlyphs:(BOOL)includePartialGlyphs;
157
158 // Drawing highlight for runs.
159 - (void)_CG_drawHighlightForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style geometry:(const WebCoreTextGeometry *)geometry;
160 - (void)_ATSU_drawHighlightForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style geometry:(const WebCoreTextGeometry *)geometry;
161
162 - (BOOL)_setupFont;
163
164 // Small caps
165 - (void)_setIsSmallCapsRenderer:(BOOL)flag;
166 - (BOOL)_isSmallCapsRenderer;
167 - (WebTextRenderer *)_smallCapsRenderer;
168 - (NSFont *)_smallCapsFont;
169
170 @end
171
172
173 // Character property functions.
174
175 static inline BOOL isSpace(UniChar c)
176 {
177     return c == SPACE || c == '\n' || c == NO_BREAK_SPACE;
178 }
179
180 static const uint8_t isRoundingHackCharacterTable[0x100] = {
181     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 /*\n*/, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
182     1 /*space*/, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 /*-*/, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 /*?*/,
183     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
184     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
185     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
186     1 /*no-break space*/, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
187     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
188     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
189 };
190
191 static inline BOOL isRoundingHackCharacter(UniChar c)
192 {
193     return (c & ~0xFF) == 0 && isRoundingHackCharacterTable[c];
194 }
195
196 // Map utility functions
197 static void freeWidthMap(WidthMap *map);
198 static void freeGlyphMap(GlyphMap *map);
199 static void freeUnicodeGlyphMap(UnicodeGlyphMap *map);
200 static inline ATSGlyphRef glyphForUnicodeCharacter (UnicodeGlyphMap *map, UnicodeChar c, NSFont **font);
201 static inline SubstituteFontWidthMap *mapForSubstituteFont(WebTextRenderer *renderer, NSFont *font);
202 static inline ATSGlyphRef glyphForCharacter (GlyphMap *map, UniChar c, NSFont **font);
203 static inline SubstituteFontWidthMap *mapForSubstituteFont(WebTextRenderer *renderer, NSFont *font);
204 static inline WebGlyphWidth widthFromMap (WebTextRenderer *renderer, WidthMap *map, ATSGlyphRef glyph, NSFont *font);
205 static inline WebGlyphWidth widthForGlyph (WebTextRenderer *renderer, ATSGlyphRef glyph, NSFont *font);
206
207 #if BUILDING_ON_PANTHER
208
209 static WebGlyphWidth getUncachedWidth(WebTextRenderer *renderer, WidthMap *map, ATSGlyphRef glyph, NSFont *font)
210 {
211     WebGlyphWidth width;
212
213     if (font == NULL)
214         font = renderer->font;
215
216     if (!CGFontGetGlyphScaledAdvances ([font _backingCGSFont], &glyph, 1, &width, [font pointSize]))
217         FATAL_ALWAYS ("Unable to cache glyph widths for %@ %f",  [font displayName], [font pointSize]);
218
219     return width;
220 }
221
222 #else
223
224 static inline CGFontRenderingMode _AppkitGetCGRenderingMode(NSFont *font) {
225     switch ([font renderingMode]) {
226         case NSFontIntegerAdvancementsRenderingMode: return kCGFontRenderingMode1BitPixelAligned;
227         case NSFontAntialiasedIntegerAdvancementsRenderingMode: return kCGFontRenderingModeAntialiasedPixelAligned;
228         default: return kCGFontRenderingModeAntialiased;
229     }
230 }
231
232 static WebGlyphWidth getUncachedWidth(WebTextRenderer *renderer, WidthMap *map, ATSGlyphRef glyph, NSFont *font)
233 {
234     float pointSize;
235     CGAffineTransform m;
236     CGSize advance;
237
238     if (font == NULL)
239         font = renderer->font;
240
241     pointSize = [font pointSize];
242     m = CGAffineTransformMakeScale(pointSize, pointSize);
243     if (!CGFontGetGlyphTransformedAdvances([font _backingCGSFont], &m, _AppkitGetCGRenderingMode(font), &glyph, 1, &advance))
244         FATAL_ALWAYS ("Unable to cache glyph widths for %@ %f", [font displayName], pointSize);
245
246     return advance.width;
247 }
248
249 #endif
250
251 static inline WebGlyphWidth widthFromMap (WebTextRenderer *renderer, WidthMap *map, ATSGlyphRef glyph, NSFont *font)
252 {
253     WebGlyphWidth width = UNINITIALIZED_GLYPH_WIDTH;
254     
255     while (1){
256         if (map == 0)
257             map = [renderer _extendGlyphToWidthMapToInclude: glyph font:font];
258
259         if (glyph >= map->startRange && glyph <= map->endRange){
260             width = map->widths[glyph - map->startRange].width;
261             if (width == UNINITIALIZED_GLYPH_WIDTH){
262                 width = getUncachedWidth (renderer, map, glyph, font);
263                 map->widths[glyph - map->startRange].width = width;
264             }
265         }
266         else {
267             map = map->next;
268             continue;
269         }
270         
271         return width;
272     }
273 }    
274
275 static inline WebGlyphWidth widthForGlyph (WebTextRenderer *renderer, ATSGlyphRef glyph, NSFont *font)
276 {
277     WidthMap *map;
278
279     if (font && font != renderer->font)
280         map = mapForSubstituteFont(renderer, font)->map;
281     else
282         map = renderer->glyphToWidthMap;
283
284     return widthFromMap (renderer, map, glyph, font);
285 }
286
287 // Iterator functions
288 static void initializeCharacterWidthIterator (CharacterWidthIterator *iterator, WebTextRenderer *renderer, const WebCoreTextRun *run , const WebCoreTextStyle *style);
289 static float widthForNextCharacter (CharacterWidthIterator *iterator, ATSGlyphRef *glyphUsed, NSFont **fontUsed);
290
291
292 // Misc.
293 static BOOL fillStyleWithAttributes(ATSUStyle style, NSFont *theFont);
294 static BOOL shouldUseATSU(const WebCoreTextRun *run);
295 static NSString *pathFromFont(NSFont *font);
296
297
298 // Globals
299 static CFCharacterSetRef nonBaseChars = NULL;
300 static BOOL bufferTextDrawing = NO;
301 static BOOL alwaysUseATSU = NO;
302
303
304 @implementation WebTextRenderer
305
306 + (NSString *)webFallbackFontFamily
307 {
308     static NSString *webFallbackFontFamily = nil;
309     if (!webFallbackFontFamily)
310         webFallbackFontFamily = [[[NSFont systemFontOfSize:16.0] familyName] retain];
311     return webFallbackFontFamily;
312 }
313
314 + (BOOL)shouldBufferTextDrawing
315 {
316     return bufferTextDrawing;
317 }
318
319 + (void)initialize
320 {
321     nonBaseChars = CFCharacterSetGetPredefined(kCFCharacterSetNonBase);
322     bufferTextDrawing = [[[NSUserDefaults standardUserDefaults] stringForKey:@"BufferTextDrawing"] isEqual: @"YES"];
323 }
324
325 - initWithFont:(NSFont *)f usingPrinterFont:(BOOL)p
326 {
327     [super init];
328     
329     // Quartz can only handle fonts with these glyph packings.  Other packings have
330     // been deprecated.
331     if ([f glyphPacking] != NSNativeShortGlyphPacking &&
332         [f glyphPacking] != NSTwoByteGlyphPacking) {
333         // Apparantly there are many deprecated fonts out there with unsupported packing types.
334         // Log and use fallback font.
335         // This change fixes the many crashes reported in 3782533.  Most likely, the
336         // problem is encountered when people upgrade from OS 9, or have OS 9
337         // fonts installed on OS X.
338         NSLog (@"%s:%d  Unable to use deprecated font %@ %f, using system font instead", __FILE__, __LINE__, [f displayName], [f pointSize]);
339         f = [NSFont systemFontOfSize:[f pointSize]];
340     }
341         
342     maxSubstituteFontWidthMaps = NUM_SUBSTITUTE_FONT_MAPS;
343     substituteFontWidthMaps = calloc (1, maxSubstituteFontWidthMaps * sizeof(SubstituteFontWidthMap));
344     font = [(p ? [f printerFont] : [f screenFont]) retain];
345     usingPrinterFont = p;
346     
347     if (![self _setupFont]){
348         // Ack!  Something very bad happened, like a corrupt font.  Try
349         // looking for an alternate 'base' font for this renderer.
350
351         // Special case hack to use "Times New Roman" in place of "Times".  "Times RO" is a common font
352         // whose family name is "Times".  It overrides the normal "Times" family font.  It also
353         // appears to have a corrupt regular variant.
354         NSString *fallbackFontFamily;
355
356         if ([[font familyName] isEqual:@"Times"])
357             fallbackFontFamily = @"Times New Roman";
358         else {
359             fallbackFontFamily = [WebTextRenderer webFallbackFontFamily];
360         }
361         
362         // Try setting up the alternate font.  This is a last ditch effort to use a
363         // substitute font when something has gone wrong.
364         NSFont *initialFont = font;
365         [initialFont autorelease];
366         NSFont *af = [[NSFontManager sharedFontManager] convertFont:font toFamily:fallbackFontFamily];
367         font = [(p ? [af printerFont] : [af screenFont]) retain];
368         NSString *filePath = pathFromFont(initialFont);
369         filePath = filePath ? filePath : @"not known";
370         if (![self _setupFont]){
371             if ([fallbackFontFamily isEqual:@"Times New Roman"]) {
372                 // OK, couldn't setup Times New Roman as an alternate to Times, fallback
373                 // on the system font.  If this fails we have no alternative left.
374                 af = [[NSFontManager sharedFontManager] convertFont:font toFamily:[WebTextRenderer webFallbackFontFamily]];
375                 font = [(p ? [af printerFont] : [af screenFont]) retain];
376                 if (![self _setupFont]){
377                     // We tried, Times, Times New Roman, and the system font.  No joy.  We have to give up.
378                     FATAL_ALWAYS ("%@ unable to initialize with font %@ at %@", self, initialFont, filePath);
379                 }
380             }
381             else {
382                 // We tried the requested font and the syste, font.  No joy.  We have to give up.
383                 FATAL_ALWAYS ("%@ unable to initialize with font %@ at %@", self, initialFont, filePath);
384             }
385         }
386
387         // Report the problem.
388         ERROR ("Corrupt font detected, using %@ in place of %@ located at \"%@\".", 
389                     [font familyName], 
390                     [initialFont familyName],
391                     filePath);
392     }
393
394     // We emulate the appkit metrics by applying rounding as is done
395     // in the appkit.
396     CGFontRef cgFont = [font _backingCGSFont];
397     const CGFontHMetrics *metrics = CGFontGetHMetrics(cgFont);
398     unsigned unitsPerEm = CGFontGetUnitsPerEm(cgFont);
399     float pointSize = [font pointSize];
400     float asc = (ScaleEmToUnits(metrics->ascent, unitsPerEm)*pointSize);
401     float dsc = (-ScaleEmToUnits(metrics->descent, unitsPerEm)*pointSize);
402     float _lineGap = ScaleEmToUnits(metrics->lineGap, unitsPerEm)*pointSize;
403     float adjustment;
404
405     // We need to adjust Times, Helvetica, and Courier to closely match the
406     // vertical metrics of their Microsoft counterparts that are the de facto
407     // web standard.  The AppKit adjustment of 20% is too big and is
408     // incorrectly added to line spacing, so we use a 15% adjustment instead
409     // and add it to the ascent.
410     if ([[font familyName] isEqualToString:@"Times"] ||
411         [[font familyName] isEqualToString:@"Helvetica"] ||
412         [[font familyName] isEqualToString:@"Courier"]) {
413         adjustment = floor(((asc + dsc) * 0.15) + 0.5);
414     } else {
415         adjustment = 0.0;
416     }
417
418     ascent = ROUND_TO_INT(asc + adjustment);
419     descent = ROUND_TO_INT(dsc);
420
421     _lineGap = (_lineGap > 0.0 ? floor(_lineGap + 0.5) : 0.0);
422     lineGap = (int)_lineGap;
423     lineSpacing =  ascent + descent + lineGap;
424
425 #ifdef COMPARE_APPKIT_CG_METRICS
426     printf ("\nCG/Appkit metrics for font %s, %f, lineGap %f, adjustment %f\n", [[font displayName] cString], [font pointSize], lineGap, adjustment);
427     if (ROUND_TO_INT([font ascender]) != ascent ||
428         ROUND_TO_INT(-[font descender]) != descent ||
429         ROUND_TO_INT([font defaultLineHeightForFont]) != lineSpacing){
430         printf ("\nCG/Appkit mismatched metrics for font %s, %f (%s)\n", [[font displayName] cString], [font pointSize],
431                 ([font screenFont] ? [[[font screenFont] displayName] cString] : "none"));
432         printf ("ascent(%s), descent(%s), lineSpacing(%s)\n",
433                 (ROUND_TO_INT([font ascender]) != ascent) ? "different" : "same",
434                 (ROUND_TO_INT(-[font descender]) != descent) ? "different" : "same",
435                 (ROUND_TO_INT([font defaultLineHeightForFont]) != lineSpacing) ? "different" : "same");
436         printf ("CG:  ascent %f, ", asc);
437         printf ("descent %f, ", dsc);
438         printf ("lineGap %f, ", lineGap);
439         printf ("lineSpacing %d\n", lineSpacing);
440         
441         printf ("NSFont:  ascent %f, ", [font ascender]);
442         printf ("descent %f, ", [font descender]);
443         printf ("lineSpacing %f\n", [font defaultLineHeightForFont]);
444     }
445 #endif
446      
447     isSmallCapsRenderer = NO;
448     
449     return self;
450 }
451
452 - (void)dealloc
453 {
454     [font release];
455     [smallCapsFont release];
456     [smallCapsRenderer release];
457
458     if (styleGroup)
459         ATSUDisposeStyleGroup(styleGroup);
460
461     freeWidthMap(glyphToWidthMap);
462     freeGlyphMap(characterToGlyphMap);
463     freeUnicodeGlyphMap(unicodeCharacterToGlyphMap);
464
465     if (ATSUStyleInitialized)
466         ATSUDisposeStyle(_ATSUSstyle);
467     
468     [super dealloc];
469 }
470
471 - (void)finalize
472 {
473     if (styleGroup)
474         ATSUDisposeStyleGroup(styleGroup);
475
476     freeWidthMap(glyphToWidthMap);
477     freeGlyphMap(characterToGlyphMap);
478     freeUnicodeGlyphMap(unicodeCharacterToGlyphMap);
479
480     if (ATSUStyleInitialized)
481         ATSUDisposeStyle(_ATSUSstyle);
482     
483     [super finalize];
484 }
485
486 - (int)ascent
487 {
488     // This simple return obviously can't throw an exception.
489     return ascent;
490 }
491
492 - (int)descent
493 {
494     // This simple return obviously can't throw an exception.
495     return descent;
496 }
497
498 - (int)lineSpacing
499 {
500     // This simple return obviously can't throw an exception.
501     return lineSpacing;
502 }
503
504 - (float)xHeight
505 {
506     // Measure the actual character "x", because AppKit synthesizes X height rather
507     // than getting it from the font. Unfortunately, NSFont will round this for us
508     // so we don't quite get the right value.
509     NSGlyph xGlyph = [font glyphWithName:@"x"];
510     if (xGlyph) {
511         NSRect xBox = [font boundingRectForGlyph:xGlyph];
512         return NSMaxY(xBox);
513     }
514
515     return [font xHeight];
516 }
517
518 - (void)drawRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style geometry:(const WebCoreTextGeometry *)geometry
519 {
520     if (style->smallCaps && !isSmallCapsRenderer) {
521         [[self _smallCapsRenderer] drawRun:run style:style geometry:geometry];
522     }
523     else {
524         if (shouldUseATSU(run))
525             [self _ATSU_drawRun:run style:style geometry:geometry];
526         else
527             [self _CG_drawRun:run style:style geometry:geometry];
528     }
529 }
530
531 - (float)floatWidthForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style widths:(float *)widthBuffer
532 {
533     if (style->smallCaps && !isSmallCapsRenderer) {
534         return [[self _smallCapsRenderer] _floatWidthForRun:run style:style widths:widthBuffer fonts:nil glyphs:nil startPosition:nil numGlyphs:nil];
535     }
536     return [self _floatWidthForRun:run style:style widths:widthBuffer fonts:nil glyphs:nil startPosition:nil numGlyphs:nil];
537 }
538
539 - (void)drawLineForCharacters:(NSPoint)point yOffset:(float)yOffset withWidth: (int)width withColor:(NSColor *)color
540 {
541     // XXX MJS
542
543     NSGraphicsContext *graphicsContext = [NSGraphicsContext currentContext];
544     CGContextRef cgContext;
545
546     // This will draw the text from the top of the bounding box down.
547     // Qt expects to draw from the baseline.
548     // Remember that descender is negative.
549     point.y -= [self lineSpacing] - [self descent];
550     
551     BOOL flag = [graphicsContext shouldAntialias];
552
553     // We don't want antialiased lines on screen, but we do when printing (else they are too thick)
554     if ([graphicsContext isDrawingToScreen]) {
555         [graphicsContext setShouldAntialias:NO];
556     }
557     
558     [color set];
559
560     cgContext = (CGContextRef)[graphicsContext graphicsPort];
561     CGSize size = CGSizeApplyAffineTransform(CGSizeMake(1.0, 1.0), CGAffineTransformInvert(CGContextGetCTM(cgContext)));
562     CGContextSetLineWidth(cgContext, size.width);
563
564 #if BUILDING_ON_PANTHER            
565     CGContextMoveToPoint(cgContext, point.x, point.y + [self lineSpacing] + 1.5 - [self descent] + yOffset);
566     // Subtract 1 to ensure that the line is always within bounds of element.
567     CGContextAddLineToPoint(cgContext, point.x + width - 1.0, point.y + [self lineSpacing] + 1.5 - [self descent] + yOffset);
568     CGContextStrokePath(cgContext);
569 #else
570     // Use CGContextStrokeLineSegments on Tiger.  J. Burkey says this will be a big performance win.
571
572     CGPoint linePoints[2];
573     linePoints[0].x = point.x;
574     linePoints[0].y = point.y + [self lineSpacing] + 1.5 - [self descent] + yOffset;
575     linePoints[1].x = point.x + width - 1.0;
576     linePoints[1].y = linePoints[0].y;
577     CGContextStrokeLineSegments (cgContext, linePoints, 2);
578 #endif
579
580     [graphicsContext setShouldAntialias: flag];
581 }
582
583
584 - (void)drawHighlightForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style geometry:(const WebCoreTextGeometry *)geometry
585 {
586     if (style->smallCaps && !isSmallCapsRenderer) {
587         [[self _smallCapsRenderer] drawHighlightForRun:run style:style geometry:geometry];
588     }
589     else {
590         if (shouldUseATSU(run))
591             [self _ATSU_drawHighlightForRun:run style:style geometry:geometry];
592         else
593             [self _CG_drawHighlightForRun:run style:style geometry:geometry];
594     }
595 }
596
597 // Constants for pattern underline
598 #define patternWidth 4
599 #define patternHeight 3
600
601 - (void)drawLineForMisspelling:(NSPoint)point withWidth:(int)width
602 {
603     // Constants for pattern color
604     static NSColor *spellingPatternColor = nil;
605     static bool usingDot = false;
606  
607     // Initialize pattern color if needed
608     if (!spellingPatternColor) {
609         NSImage *image = [NSImage imageNamed:@"SpellingDot"];
610         ASSERT(image); // if image is not available, we want to know
611         NSColor *color = (image ? [NSColor colorWithPatternImage:image] : nil);
612         if (color)
613             usingDot = true;
614         else
615             color = [NSColor redColor];
616         spellingPatternColor = [color retain];
617     }
618
619     // Width must be divisible by 4 to make sure we always draw full misspelling dots under words.
620     // Do a small adjustment to shift the underline back to the left if the pattern was
621     // expanded to the right "too much" to accomodate the drawing of a full dot.
622     if (usingDot) {
623         int w = (width + patternWidth) - (width % patternWidth);
624         if (w - width > 2) 
625             point.x -= 1;
626         width = w;
627     }
628
629     // Compute the appropriate phase relative to the top level view in the window.
630     NSPoint originInWindow = [[NSView focusView] convertPoint:point toView:nil];
631     // WebCore may translate the focus, and thus need an extra phase correction
632     NSPoint extraPhase = [[WebGraphicsBridge sharedBridge] additionalPatternPhase];
633     originInWindow.x += extraPhase.x;
634     originInWindow.y += extraPhase.y;
635     CGSize phase = CGSizeMake(fmodf(originInWindow.x, patternWidth), fmodf(originInWindow.y, patternHeight));
636
637     // Draw underline
638     NSGraphicsContext *currentContext = [NSGraphicsContext currentContext];
639     [currentContext saveGraphicsState];
640     [spellingPatternColor set];
641     CGContextSetPatternPhase((CGContextRef)[currentContext graphicsPort], phase);
642     NSRectFillUsingOperation(NSMakeRect(point.x, point.y, width, patternHeight), NSCompositeSourceOver);
643     [currentContext restoreGraphicsState];
644 }
645
646 #undef patternWidth
647 #undef patternHeight
648
649 - (int)pointToOffset:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style position:(int)x reversed:(BOOL)reversed includePartialGlyphs:(BOOL)includePartialGlyphs
650 {
651     if (style->smallCaps && !isSmallCapsRenderer) {
652         return [[self _smallCapsRenderer] pointToOffset:run style:style position:x reversed:reversed includePartialGlyphs:includePartialGlyphs];
653     }
654
655     if (shouldUseATSU(run))
656         return [self _ATSU_pointToOffset:run style:style position:x reversed:reversed includePartialGlyphs:includePartialGlyphs];
657     return [self _CG_pointToOffset:run style:style position:x reversed:reversed includePartialGlyphs:includePartialGlyphs];
658 }
659
660 @end
661
662
663 // ------------------- Private API -------------------
664
665
666 @implementation WebTextRenderer (WebInternal)
667
668 + (void)_setAlwaysUseATSU:(BOOL)f
669 {
670     alwaysUseATSU = f;
671 }
672
673 - (void)_setIsSmallCapsRenderer:(BOOL)flag
674 {
675     isSmallCapsRenderer = flag;
676 }
677
678 - (BOOL)_isSmallCapsRenderer
679 {
680     return isSmallCapsRenderer;
681 }
682
683 - (WebTextRenderer *)_smallCapsRenderer
684 {
685     if (!smallCapsRenderer) {
686         NS_DURING
687             smallCapsRenderer = [[WebTextRenderer alloc] initWithFont:font usingPrinterFont:usingPrinterFont];
688         NS_HANDLER
689             if (ASSERT_DISABLED) {
690                 NSLog(@"Uncaught exception - %@\n", localException);
691             } else {
692                 ASSERT_WITH_MESSAGE(0, "Uncaught exception - %@", localException);
693             } 
694         NS_ENDHANDLER
695
696         [smallCapsRenderer _setIsSmallCapsRenderer:YES];
697     }
698     return smallCapsRenderer;
699 }
700
701 - (NSFont *)_smallCapsFont
702 {
703     if (!smallCapsFont)
704         smallCapsFont = [[NSFontManager sharedFontManager] convertFont:font toSize:([font pointSize] * SMALLCAPS_FONTSIZE_MULTIPLIER)];
705     return smallCapsFont;
706 }
707
708 static inline BOOL fontContainsString(NSFont *font, NSString *string)
709 {
710     NSCharacterSet *set = [[font coveredCharacterSet] invertedSet];
711     return set && [string rangeOfCharacterFromSet:set].location == NSNotFound;
712 }
713
714 - (NSFont *)_substituteFontForString: (NSString *)string families: (NSString **)families
715 {
716     NSFont *substituteFont = nil;
717
718     // First search the CSS family fallback list.  Start at 1 (2nd font)
719     // because we've already failed on the first lookup.
720     NSString *family = nil;
721     int i = 1;
722     while (families && families[i] != 0) {
723         family = families[i++];
724         substituteFont = [[WebTextRendererFactory sharedFactory] cachedFontFromFamily: family traits:[[NSFontManager sharedFontManager] traitsOfFont:font] size:[font pointSize]];
725         if (substituteFont) {
726             if (fontContainsString(substituteFont, string))
727                 break;
728             substituteFont = nil; 
729         }
730     }
731     
732     // Now do string based lookup.
733     if (substituteFont == nil)
734         substituteFont = [NSFont findFontLike:font forString:string withRange:NSMakeRange (0,[string length]) inLanguage:[NSLanguage defaultLanguage]];
735
736     // Now do character based lookup.
737     if (substituteFont == nil && [string length] == 1)
738         substituteFont = [NSFont findFontLike:font forCharacter: [string characterAtIndex: 0] inLanguage:[NSLanguage defaultLanguage]];
739
740     // Get the screen or printer variation of the font.
741     substituteFont = usingPrinterFont ? [substituteFont printerFont] : [substituteFont screenFont];
742
743     if ([substituteFont isEqual: font])
744         substituteFont = nil;
745
746     return substituteFont;
747 }
748
749 - (NSFont *)_substituteFontForCharacters: (const unichar *)characters length: (int)numCharacters families: (NSString **)families
750 {
751     NSString *string = [[NSString alloc] initWithCharactersNoCopy:(unichar *)characters length: numCharacters freeWhenDone: NO];
752     NSFont *substituteFont = [self _substituteFontForString: string families: families];
753     [string release];
754     return substituteFont;
755 }
756
757 - (void)_convertCharacters: (const UniChar *)characters length: (unsigned)numCharacters toGlyphs: (ATSGlyphVector *)glyphs
758 {
759     OSStatus status = ATSUConvertCharToGlyphs(styleGroup, characters, 0, numCharacters, 0, glyphs);
760     if (status != noErr){
761         FATAL_ALWAYS ("unable to get glyphsfor %@ %f error = (%d)", self, [font displayName], [font pointSize], status);
762     }
763
764 #ifdef DEBUG_GLYPHS
765     int foundGlyphs = 0;
766     ATSLayoutRecord *glyphRecord;
767     for (i = 0; i < numCharacters; i++) {
768         glyphRecord = (ATSLayoutRecord *)glyphs->firstRecord;
769         for (i = 0; i < numCharacters; i++) {
770             if (glyphRecord->glyphID != 0)
771                 foundGlyphs++;
772             glyphRecord = (ATSLayoutRecord *)((char *)glyphRecord + glyphs->recordSize);
773         }
774     }
775     printf ("For %s found %d glyphs in range 0x%04x to 0x%04x\n", [[font displayName] cString], foundGlyphs, characters[0], characters[numCharacters-1]);
776 #endif
777 }
778
779 - (void)_convertUnicodeCharacters: (const UnicodeChar *)characters length: (unsigned)numCharacters toGlyphs: (ATSGlyphVector *)glyphs
780 {
781     UniChar localBuffer[LOCAL_BUFFER_SIZE];
782     UniChar *buffer = localBuffer;
783     unsigned i, bufPos = 0;
784     
785     if (numCharacters*2 > LOCAL_BUFFER_SIZE) {
786         buffer = (UniChar *)malloc(sizeof(UniChar) * numCharacters * 2);
787     }
788     
789     for (i = 0; i < numCharacters; i++) {
790         UnicodeChar c = characters[i];
791         UniChar h = HighSurrogatePair(c);
792         UniChar l = LowSurrogatePair(c);
793         buffer[bufPos++] = h;
794         buffer[bufPos++] = l;
795     }
796         
797     OSStatus status = ATSUConvertCharToGlyphs(styleGroup, buffer, 0, numCharacters*2, 0, glyphs);
798     if (status != noErr){
799         FATAL_ALWAYS ("unable to get glyphsfor %@ %f error = (%d)", self, [font displayName], [font pointSize], status);
800     }
801     
802     if (buffer != localBuffer) {
803         free(buffer);
804     }
805 }
806
807 // Nasty hack to determine if we should round or ceil space widths.
808 // If the font is monospace or fake monospace we ceil to ensure that 
809 // every character and the space are the same width.  Otherwise we round.
810 - (BOOL)_computeWidthForSpace
811 {
812     spaceGlyph = [self _extendCharacterToGlyphMapToInclude:SPACE];
813     if (spaceGlyph == 0) {
814         return NO;
815     }
816
817     float width = widthForGlyph(self, spaceGlyph, 0);
818     spaceWidth = width;
819
820     treatAsFixedPitch = [font isFixedPitch] || [font _isFakeFixedPitch];
821     adjustedSpaceWidth = treatAsFixedPitch ? CEIL_TO_INT(width) : ROUND_TO_INT(width);
822     
823     return YES;
824 }
825
826 - (BOOL)_setupFont
827 {
828     ATSUStyle fontStyle;
829     if (ATSUCreateStyle(&fontStyle) != noErr)
830         return NO;
831
832     if (!fillStyleWithAttributes(fontStyle, font)) {
833         ATSUDisposeStyle(fontStyle);
834         return NO;
835     }
836
837     if (ATSUGetStyleGroup(fontStyle, &styleGroup) != noErr) {
838         ATSUDisposeStyle(fontStyle);
839         return NO;
840     }
841     
842     ATSUDisposeStyle(fontStyle);
843
844     if (![self _computeWidthForSpace]) {
845         freeGlyphMap(characterToGlyphMap);
846         characterToGlyphMap = NULL;
847         ATSUDisposeStyleGroup(styleGroup);
848         styleGroup = NULL;
849         return NO;
850     }
851     
852     return YES;
853 }
854
855 static NSString *pathFromFont (NSFont *font)
856 {
857     UInt8 _filePathBuffer[PATH_MAX];
858     NSString *filePath = nil;
859     FSSpec oFile;
860     OSStatus status = ATSFontGetFileSpecification(
861             ATSFontRefFromNSFont(font),
862             &oFile);
863     if (status == noErr){
864         OSErr err;
865         FSRef fileRef;
866         err = FSpMakeFSRef(&oFile,&fileRef);
867         if (err == noErr){
868             status = FSRefMakePath(&fileRef,_filePathBuffer, PATH_MAX);
869             if (status == noErr){
870                 filePath = [NSString stringWithUTF8String:&_filePathBuffer[0]];
871             }
872         }
873     }
874     return filePath;
875 }
876
877 // Useful page for testing http://home.att.net/~jameskass
878 static void _drawGlyphs(NSFont *font, NSColor *color, CGGlyph *glyphs, CGSize *advances, float x, float y, int numGlyphs)
879 {
880     CGContextRef cgContext;
881
882     if ([WebTextRenderer shouldBufferTextDrawing] && [[WebTextRendererFactory sharedFactory] coalesceTextDrawing]){
883         // Add buffered glyphs and advances
884         // FIXME:  If we ever use this again, need to add RTL.
885         WebGlyphBuffer *gBuffer = [[WebTextRendererFactory sharedFactory] glyphBufferForFont: font andColor: color];
886         [gBuffer addGlyphs: glyphs advances: advances count: numGlyphs at: x : y];
887     }
888     else {
889         NSGraphicsContext *gContext = [NSGraphicsContext currentContext];
890         cgContext = (CGContextRef)[gContext graphicsPort];
891         // Setup the color and font.
892         
893 #if BUILDING_ON_PANTHER        
894         if ([gContext isDrawingToScreen]){
895             NSFont *screenFont = [font screenFont];
896             if (screenFont != font){
897                 // We are getting this in too many places (3406411); use ERROR so it only prints on
898                 // debug versions for now. (We should debug this also, eventually).
899                 ERROR ("Attempting to set non-screen font (%@) when drawing to screen.  Using screen font anyway, may result in incorrect metrics.", [[[font fontDescriptor] fontAttributes] objectForKey: NSFontNameAttribute]);
900             }
901             [screenFont set];
902         }
903         else {
904             NSFont *printerFont = [font printerFont];
905             if (printerFont != font){
906                 NSLog (@"Attempting to set non-printer font (%@) when printing.  Using printer font anyway, may result in incorrect metrics.", [[[font fontDescriptor] fontAttributes] objectForKey: NSFontNameAttribute]);
907             }
908             [printerFont set];
909         }
910 #else
911         NSFont *drawFont;
912         
913         if ([gContext isDrawingToScreen]){
914             drawFont = [font screenFont];
915             if (drawFont != font){
916                 // We are getting this in too many places (3406411); use ERROR so it only prints on
917                 // debug versions for now. (We should debug this also, eventually).
918                 ERROR ("Attempting to set non-screen font (%@) when drawing to screen.  Using screen font anyway, may result in incorrect metrics.", [[[font fontDescriptor] fontAttributes] objectForKey: NSFontNameAttribute]);
919             }
920         }
921         else {
922             drawFont = [font printerFont];
923             if (drawFont != font){
924                 NSLog (@"Attempting to set non-printer font (%@) when printing.  Using printer font anyway, may result in incorrect metrics.", [[[font fontDescriptor] fontAttributes] objectForKey: NSFontNameAttribute]);
925             }
926         }
927         
928         CGContextSetFont (cgContext, [drawFont _backingCGSFont]);
929         
930         // Deal will flipping flippyness.
931         const float *matrix = [drawFont matrix];
932         float flip = [[NSView focusView] isFlipped] ? -1 : 1;
933         CGContextSetTextMatrix(cgContext, CGAffineTransformMake(matrix[0], matrix[1] * flip, matrix[2], matrix[3] * flip, matrix[4], matrix[5]));
934         CGContextSetFontRenderingMode (cgContext, _AppkitGetCGRenderingMode(drawFont));
935         CGContextSetFontSize(cgContext, 1.0);
936 #endif
937
938         [color set];
939
940         CGContextSetTextPosition (cgContext, x, y);
941         CGContextShowGlyphsWithAdvances (cgContext, glyphs, advances, numGlyphs);
942     }
943 }
944
945
946 - (void)_CG_drawHighlightForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style geometry:(const WebCoreTextGeometry *)geometry
947 {
948     if (run->length == 0)
949         return;
950
951     CharacterWidthIterator widthIterator;
952     WebCoreTextRun completeRun = *run;
953     completeRun.from = 0;
954     completeRun.to = run->length;
955     initializeCharacterWidthIterator(&widthIterator, self, &completeRun, style);
956     
957     float startPosition = 0;
958
959     // The starting point needs to be adjusted to account for the width of
960     // the glyphs at the start of the run.
961     while (widthIterator.currentCharacter < (unsigned)run->from) {
962         startPosition += widthForNextCharacter(&widthIterator, 0, 0);
963     }
964     float startX = startPosition + geometry->point.x;
965     
966     float backgroundWidth = 0.0;
967     while (widthIterator.currentCharacter < (unsigned)run->to) {
968         backgroundWidth += widthForNextCharacter(&widthIterator, 0, 0);
969     }
970
971     if (style->backgroundColor != nil){
972         // Calculate the width of the selection background by adding
973         // up the advances of all the glyphs in the selection.
974         
975         [style->backgroundColor set];
976
977         float yPos = geometry->useFontMetricsForSelectionYAndHeight ? geometry->point.y - [self ascent] - (lineGap/2) : geometry->selectionY;
978         float height = geometry->useFontMetricsForSelectionYAndHeight ? [self lineSpacing] : geometry->selectionHeight;
979         if (style->rtl){
980             float completeRunWidth = startPosition + backgroundWidth;
981             while (widthIterator.currentCharacter < run->length) {
982                 completeRunWidth += widthForNextCharacter(&widthIterator, 0, 0);
983             }
984
985             [NSBezierPath fillRect:NSMakeRect(geometry->point.x + completeRunWidth - startPosition - backgroundWidth, yPos, backgroundWidth, height)];
986         }
987         else {
988             [NSBezierPath fillRect:NSMakeRect(startX, yPos, backgroundWidth, height)];
989         }
990     }
991 }
992
993
994 - (void)_CG_drawRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style geometry:(const WebCoreTextGeometry *)geometry
995 {
996     float *widthBuffer, localWidthBuffer[LOCAL_BUFFER_SIZE];
997     CGGlyph *glyphBuffer, localGlyphBuffer[LOCAL_BUFFER_SIZE];
998     NSFont **fontBuffer, *localFontBuffer[LOCAL_BUFFER_SIZE];
999     CGSize *advances, localAdvanceBuffer[LOCAL_BUFFER_SIZE];
1000     int numGlyphs = 0, i;
1001     float startX;
1002     unsigned length = run->length;
1003     
1004     if (run->length == 0)
1005         return;
1006
1007     if (length*MAX_GLYPH_EXPANSION > LOCAL_BUFFER_SIZE) {
1008         advances = (CGSize *)calloc(length*MAX_GLYPH_EXPANSION, sizeof(CGSize));
1009         widthBuffer = (float *)calloc(length*MAX_GLYPH_EXPANSION, sizeof(float));
1010         glyphBuffer = (CGGlyph *)calloc(length*MAX_GLYPH_EXPANSION, sizeof(ATSGlyphRef));
1011         fontBuffer = (NSFont **)calloc(length*MAX_GLYPH_EXPANSION, sizeof(NSFont *));
1012     } else {
1013         advances = localAdvanceBuffer;
1014         widthBuffer = localWidthBuffer;
1015         glyphBuffer = localGlyphBuffer;
1016         fontBuffer = localFontBuffer;
1017     }
1018
1019     [self _floatWidthForRun:run
1020         style:style
1021         widths:widthBuffer 
1022         fonts:fontBuffer
1023         glyphs:glyphBuffer
1024         startPosition:&startX
1025         numGlyphs: &numGlyphs];
1026         
1027     // Eek.  We couldn't generate ANY glyphs for the run.
1028     if (numGlyphs <= 0)
1029         return;
1030         
1031     // Fill the advances array.
1032     for (i = 0; i < numGlyphs; i++){
1033         advances[i].width = widthBuffer[i];
1034         advances[i].height = 0;
1035     }
1036
1037     // Calculate the starting point of the glyphs to be displayed by adding
1038     // all the advances up to the first glyph.
1039     startX += geometry->point.x;
1040
1041     if (style->backgroundColor != nil)
1042         [self _CG_drawHighlightForRun:run style:style geometry:geometry];
1043     
1044     // Finally, draw the glyphs.
1045     int lastFrom = 0;
1046     int pos = 0;
1047
1048     // Swap the order of the glyphs if right-to-left.
1049     if (style->rtl && numGlyphs > 1){
1050         int i;
1051         int end = numGlyphs;
1052         CGGlyph gswap1, gswap2;
1053         CGSize aswap1, aswap2;
1054         NSFont *fswap1, *fswap2;
1055         
1056         for (i = pos, end = numGlyphs-1; i < (numGlyphs - pos)/2; i++){
1057             gswap1 = glyphBuffer[i];
1058             gswap2 = glyphBuffer[--end];
1059             glyphBuffer[i] = gswap2;
1060             glyphBuffer[end] = gswap1;
1061         }
1062         for (i = pos, end = numGlyphs - 1; i < (numGlyphs - pos)/2; i++){
1063             aswap1 = advances[i];
1064             aswap2 = advances[--end];
1065             advances[i] = aswap2;
1066             advances[end] = aswap1;
1067         }
1068         for (i = pos, end = numGlyphs - 1; i < (numGlyphs - pos)/2; i++){
1069             fswap1 = fontBuffer[i];
1070             fswap2 = fontBuffer[--end];
1071             fontBuffer[i] = fswap2;
1072             fontBuffer[end] = fswap1;
1073         }
1074     }
1075
1076     // Draw each contiguous run of glyphs that are included in the same font.
1077     NSFont *currentFont = fontBuffer[pos];
1078     float nextX = startX;
1079     int nextGlyph = pos;
1080
1081     while (nextGlyph < numGlyphs){
1082         if ((fontBuffer[nextGlyph] != 0 && fontBuffer[nextGlyph] != currentFont)){
1083             _drawGlyphs(currentFont, style->textColor, &glyphBuffer[lastFrom], &advances[lastFrom], startX, geometry->point.y, nextGlyph - lastFrom);
1084             lastFrom = nextGlyph;
1085             currentFont = fontBuffer[nextGlyph];
1086             startX = nextX;
1087         }
1088         nextX += advances[nextGlyph].width;
1089         nextGlyph++;
1090     }
1091     _drawGlyphs(currentFont, style->textColor, &glyphBuffer[lastFrom], &advances[lastFrom], startX, geometry->point.y, nextGlyph - lastFrom);
1092
1093     if (advances != localAdvanceBuffer) {
1094         free(advances);
1095         free(widthBuffer);
1096         free(glyphBuffer);
1097         free(fontBuffer);
1098     }
1099 }
1100
1101 #ifdef DEBUG_COMBINING
1102 static const char *directionNames[] = {
1103         "DirectionL",   // Left Letter 
1104         "DirectionR",   // Right Letter
1105         "DirectionEN",  // European Number
1106         "DirectionES",  // European Separator
1107         "DirectionET",  // European Terminator (post/prefix e.g. $ and %)
1108         "DirectionAN",  // Arabic Number
1109         "DirectionCS",  // Common Separator 
1110         "DirectionB",   // Paragraph Separator (aka as PS)
1111         "DirectionS",   // Segment Separator (TAB)
1112         "DirectionWS",  // White space
1113         "DirectionON",  // Other Neutral
1114
1115         // types for explicit controls
1116         "DirectionLRE", 
1117         "DirectionLRO", 
1118
1119         "DirectionAL",  // Arabic Letter (Right-to-left)
1120
1121         "DirectionRLE", 
1122         "DirectionRLO", 
1123         "DirectionPDF", 
1124
1125         "DirectionNSM",         // Non-spacing Mark
1126         "DirectionBN"   // Boundary neutral (type of RLE etc after explicit levels)
1127 };
1128
1129 static const char *joiningNames[] = {
1130         "JoiningOther",
1131         "JoiningDual",
1132         "JoiningRight",
1133         "JoiningCausing"
1134 };
1135 #endif
1136
1137 - (float)_floatWidthForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style widths:(float *)widthBuffer fonts:(NSFont **)fontBuffer glyphs:(CGGlyph *)glyphBuffer startPosition:(float *)startPosition numGlyphs:(int *)_numGlyphs
1138 {
1139     if (shouldUseATSU(run))
1140         return [self _ATSU_floatWidthForRun:run style:style];
1141     
1142     return [self _CG_floatWidthForRun:run style:style widths:widthBuffer fonts:fontBuffer glyphs:glyphBuffer startPosition:startPosition numGlyphs:_numGlyphs];
1143
1144 }
1145
1146 - (float)_CG_floatWidthForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style widths: (float *)widthBuffer fonts: (NSFont **)fontBuffer glyphs: (CGGlyph *)glyphBuffer startPosition:(float *)startPosition numGlyphs: (int *)_numGlyphs
1147 {
1148     float _totalWidth = 0, _nextWidth;
1149     CharacterWidthIterator widthIterator;
1150     NSFont *fontUsed = 0;
1151     ATSGlyphRef glyphUsed;
1152     int numGlyphs = 0;
1153     
1154     initializeCharacterWidthIterator(&widthIterator, self, run, style);
1155     if (startPosition)
1156         *startPosition = widthIterator.widthToStart;
1157     while ((_nextWidth = widthForNextCharacter(&widthIterator, &glyphUsed, &fontUsed)) != INVALID_WIDTH){
1158         if (fontBuffer)
1159             fontBuffer[numGlyphs] = fontUsed;
1160         if (glyphBuffer)
1161             glyphBuffer[numGlyphs] = glyphUsed;
1162         if (widthBuffer)
1163             widthBuffer[numGlyphs] = _nextWidth;
1164         numGlyphs++;
1165         _totalWidth += _nextWidth;
1166     }
1167         
1168     if (_numGlyphs)
1169         *_numGlyphs = numGlyphs;
1170
1171     return _totalWidth;
1172 }
1173
1174 - (ATSGlyphRef)_extendUnicodeCharacterToGlyphMapToInclude:(UnicodeChar)c
1175 {
1176     UnicodeGlyphMap *map = (UnicodeGlyphMap *)calloc (1, sizeof(UnicodeGlyphMap));
1177     ATSLayoutRecord *glyphRecord;
1178     ATSGlyphVector glyphVector;
1179     UnicodeChar end, start;
1180     unsigned blockSize;
1181     ATSGlyphRef glyphID;
1182     
1183     if (unicodeCharacterToGlyphMap == 0)
1184         blockSize = INITIAL_BLOCK_SIZE;
1185     else
1186         blockSize = INCREMENTAL_BLOCK_SIZE;
1187     start = (c / blockSize) * blockSize;
1188     end = start + (blockSize - 1);
1189         
1190     LOG(FontCache, "%@ (0x%04x) adding glyphs for 0x%04x to 0x%04x", font, c, start, end);
1191
1192     map->startRange = start;
1193     map->endRange = end;
1194     
1195     unsigned i, count = end - start + 1;
1196     UnicodeChar buffer[INCREMENTAL_BLOCK_SIZE+2];
1197     
1198     for (i = 0; i < count; i++){
1199         buffer[i] = i+start;
1200     }
1201
1202     OSStatus status;
1203     status = ATSInitializeGlyphVector(count*2, 0, &glyphVector);
1204     if (status != noErr){
1205         // This should never happen, indicates a bad font!  If it does the
1206         // font substitution code will find an alternate font.
1207         free(map);
1208         return 0;
1209     }
1210     
1211     [self _convertUnicodeCharacters: &buffer[0] length: count toGlyphs: &glyphVector];
1212     unsigned numGlyphs = glyphVector.numGlyphs;
1213     if (numGlyphs != count){
1214         // This should never happen, indicates a bad font!  If it does the
1215         // font substitution code will find an alternate font.
1216         free(map);
1217         return 0;
1218     }
1219             
1220     map->glyphs = (GlyphEntry *)malloc (count * sizeof(GlyphEntry));
1221     glyphRecord = (ATSLayoutRecord *)glyphVector.firstRecord;
1222     for (i = 0; i < count; i++) {
1223         map->glyphs[i].glyph = glyphRecord->glyphID;
1224         map->glyphs[i].font = 0;
1225         glyphRecord = (ATSLayoutRecord *)((char *)glyphRecord + glyphVector.recordSize);
1226     }
1227     ATSClearGlyphVector(&glyphVector);
1228     
1229     if (unicodeCharacterToGlyphMap == 0)
1230         unicodeCharacterToGlyphMap = map;
1231     else {
1232         UnicodeGlyphMap *lastMap = unicodeCharacterToGlyphMap;
1233         while (lastMap->next != 0)
1234             lastMap = lastMap->next;
1235         lastMap->next = map;
1236     }
1237
1238     glyphID = map->glyphs[c - start].glyph;
1239     
1240     return glyphID;
1241 }
1242
1243 - (void)_updateGlyphEntryForCharacter:(UniChar)c glyphID:(ATSGlyphRef)glyphID font:(NSFont *)substituteFont
1244 {
1245     GlyphMap *lastMap = characterToGlyphMap;
1246     while (lastMap != 0){
1247         if (c >= lastMap->startRange && c <= lastMap->endRange){
1248             lastMap->glyphs[c - lastMap->startRange].glyph = glyphID;
1249             // This font will leak.  No problem though, it has to stick around
1250             // forever.  Max theoretical retain counts applied here will be
1251             // num_fonts_on_system * num_glyphs_in_font.
1252             lastMap->glyphs[c - lastMap->startRange].font = [substituteFont retain];
1253             break;
1254         }
1255         lastMap = lastMap->next;
1256     }
1257 }
1258
1259 - (ATSGlyphRef)_extendCharacterToGlyphMapToInclude:(UniChar) c
1260 {
1261     GlyphMap *map = (GlyphMap *)calloc (1, sizeof(GlyphMap));
1262     ATSLayoutRecord *glyphRecord;
1263     ATSGlyphVector glyphVector;
1264     UniChar end, start;
1265     unsigned blockSize;
1266     ATSGlyphRef glyphID;
1267     
1268     if (characterToGlyphMap == 0)
1269         blockSize = INITIAL_BLOCK_SIZE;
1270     else
1271         blockSize = INCREMENTAL_BLOCK_SIZE;
1272     start = (c / blockSize) * blockSize;
1273     end = start + (blockSize - 1);
1274         
1275     LOG(FontCache, "%@ (0x%04x) adding glyphs for 0x%04x to 0x%04x", font, c, start, end);
1276
1277     map->startRange = start;
1278     map->endRange = end;
1279     
1280     unsigned i, count = end - start + 1;
1281     short unsigned buffer[INCREMENTAL_BLOCK_SIZE+2];
1282     
1283     for (i = 0; i < count; i++) {
1284         buffer[i] = i+start;
1285     }
1286
1287     if (start == 0) {
1288         // Control characters must not render at all.
1289         for (i = 0; i < 0x20; ++i)
1290             buffer[i] = ZERO_WIDTH_SPACE;
1291         buffer[0x7F] = ZERO_WIDTH_SPACE;
1292
1293         // But both \n and nonbreaking space must render as a space.
1294         buffer['\n'] = ' ';
1295         buffer[NO_BREAK_SPACE] = ' ';
1296     }
1297
1298     OSStatus status = ATSInitializeGlyphVector(count, 0, &glyphVector);
1299     if (status != noErr) {
1300         // This should never happen, perhaps indicates a bad font!  If it does the
1301         // font substitution code will find an alternate font.
1302         free(map);
1303         return 0;
1304     }
1305
1306     [self _convertCharacters: &buffer[0] length: count toGlyphs: &glyphVector];
1307     unsigned numGlyphs = glyphVector.numGlyphs;
1308     if (numGlyphs != count){
1309         // This should never happen, perhaps indicates a bad font!  If it does the
1310         // font substitution code will find an alternate font.
1311         free(map);
1312         return 0;
1313     }
1314             
1315     map->glyphs = (GlyphEntry *)malloc (count * sizeof(GlyphEntry));
1316     glyphRecord = (ATSLayoutRecord *)glyphVector.firstRecord;
1317     for (i = 0; i < count; i++) {
1318         map->glyphs[i].glyph = glyphRecord->glyphID;
1319         map->glyphs[i].font = 0;
1320         glyphRecord = (ATSLayoutRecord *)((char *)glyphRecord + glyphVector.recordSize);
1321     }
1322     ATSClearGlyphVector(&glyphVector);
1323     
1324     if (characterToGlyphMap == 0)
1325         characterToGlyphMap = map;
1326     else {
1327         GlyphMap *lastMap = characterToGlyphMap;
1328         while (lastMap->next != 0)
1329             lastMap = lastMap->next;
1330         lastMap->next = map;
1331     }
1332
1333     glyphID = map->glyphs[c - start].glyph;
1334     
1335     // Special case for characters 007F-00A0.
1336     if (glyphID == 0 && c >= 0x7F && c <= 0xA0){
1337         glyphID = [font _defaultGlyphForChar: c];
1338         map->glyphs[c - start].glyph = glyphID;
1339         map->glyphs[c - start].font = 0;
1340     }
1341
1342     return glyphID;
1343 }
1344
1345
1346 - (WidthMap *)_extendGlyphToWidthMapToInclude:(ATSGlyphRef)glyphID font:(NSFont *)subFont
1347 {
1348     WidthMap *map = (WidthMap *)calloc (1, sizeof(WidthMap)), **rootMap;
1349     unsigned end;
1350     ATSGlyphRef start;
1351     unsigned blockSize;
1352     unsigned i, count;
1353     
1354     if (subFont && subFont != font)
1355         rootMap = &mapForSubstituteFont(self,subFont)->map;
1356     else
1357         rootMap = &glyphToWidthMap;
1358         
1359     if (*rootMap == 0){
1360         if ([(subFont ? subFont : font) numberOfGlyphs] < INITIAL_BLOCK_SIZE)
1361             blockSize = [font numberOfGlyphs];
1362          else
1363             blockSize = INITIAL_BLOCK_SIZE;
1364     }
1365     else
1366         blockSize = INCREMENTAL_BLOCK_SIZE;
1367     start = (glyphID / blockSize) * blockSize;
1368     end = ((unsigned)start) + blockSize; 
1369     if (end > 0xffff)
1370         end = 0xffff;
1371
1372     LOG(FontCache, "%@ (0x%04x) adding widths for range 0x%04x to 0x%04x", font, glyphID, start, end);
1373
1374     map->startRange = start;
1375     map->endRange = end;
1376     count = end - start + 1;
1377
1378     map->widths = (WidthEntry *)malloc (count * sizeof(WidthEntry));
1379
1380     for (i = 0; i < count; i++){
1381         map->widths[i].width = UNINITIALIZED_GLYPH_WIDTH;
1382     }
1383
1384     if (*rootMap == 0)
1385         *rootMap = map;
1386     else {
1387         WidthMap *lastMap = *rootMap;
1388         while (lastMap->next != 0)
1389             lastMap = lastMap->next;
1390         lastMap->next = map;
1391     }
1392
1393 #ifdef _TIMING
1394     LOG(FontCache, "%@ total time to advances lookup %f seconds", font, totalCGGetAdvancesTime);
1395 #endif
1396     return map;
1397 }
1398
1399
1400 - (void)_initializeATSUStyle
1401 {
1402     // The two NSFont calls in this method (pointSize and _atsFontID)
1403     // are both exception-safe.
1404
1405     if (!ATSUStyleInitialized){
1406         OSStatus status;
1407         
1408         status = ATSUCreateStyle(&_ATSUSstyle);
1409         if(status != noErr)
1410             FATAL_ALWAYS ("ATSUCreateStyle failed (%d)", status);
1411     
1412         ATSUFontID fontID = [font _atsFontID];
1413         if (fontID == 0){
1414             ATSUDisposeStyle(_ATSUSstyle);
1415             ERROR ("unable to get ATSUFontID for %@", font);
1416             return;
1417         }
1418         
1419         CGAffineTransform transform = CGAffineTransformMakeScale (1,-1);
1420         Fixed fontSize = FloatToFixed([font pointSize]);
1421         ATSUAttributeTag styleTags[] = { kATSUSizeTag, kATSUFontTag, kATSUFontMatrixTag};
1422         ByteCount styleSizes[] = {  sizeof(Fixed), sizeof(ATSUFontID), sizeof(CGAffineTransform) };
1423         ATSUAttributeValuePtr styleValues[] = { &fontSize, &fontID, &transform  };
1424         status = ATSUSetAttributes (_ATSUSstyle, 3, styleTags, styleSizes, styleValues);
1425         if(status != noErr)
1426             FATAL_ALWAYS ("ATSUSetAttributes failed (%d)", status);
1427
1428         ATSUStyleInitialized = YES;
1429     }
1430 }
1431
1432 - (ATSUTextLayout)_createATSUTextLayoutForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style
1433 {
1434     // The only Cocoa calls here are to NSGraphicsContext and the self
1435     // call to _initializeATSUStyle, which are all exception-safe.
1436
1437     ATSUTextLayout layout;
1438     UniCharCount runLength;
1439     OSStatus status;
1440     
1441     [self _initializeATSUStyle];
1442     
1443     // FIXME: This is missing the following features that the CoreGraphics code path has:
1444     // - Both \n and nonbreaking space render as a space.
1445     // - All other control characters must not render at all (other code path uses zero-width spaces).
1446
1447     runLength = run->to - run->from;
1448     status = ATSUCreateTextLayoutWithTextPtr(
1449             run->characters,
1450             run->from,           // offset
1451             runLength,        // length
1452             run->length,         // total length
1453             1,              // styleRunCount
1454             &runLength,    // length of style run
1455             &_ATSUSstyle, 
1456             &layout);
1457     if(status != noErr)
1458         FATAL_ALWAYS ("ATSUCreateTextLayoutWithTextPtr failed(%d)", status);
1459
1460     CGContextRef cgContext = (CGContextRef)[[NSGraphicsContext currentContext] graphicsPort];
1461     ATSLineLayoutOptions lineLayoutOptions = (kATSLineFractDisable | kATSLineDisableAutoAdjustDisplayPos | kATSLineUseDeviceMetrics);
1462     Boolean rtl = style->rtl;
1463     ATSUAttributeTag tags[] = { kATSUCGContextTag, kATSULineLayoutOptionsTag, kATSULineDirectionTag };
1464     ByteCount sizes[] = { sizeof(CGContextRef), sizeof(ATSLineLayoutOptions), sizeof(Boolean)  };
1465     ATSUAttributeValuePtr values[] = { &cgContext, &lineLayoutOptions, &rtl };
1466     
1467     status = ATSUSetLayoutControls(layout, 3, tags, sizes, values);
1468     if(status != noErr)
1469         FATAL_ALWAYS ("ATSUSetLayoutControls failed(%d)", status);
1470
1471     status = ATSUSetTransientFontMatching (layout, YES);
1472     if(status != noErr)
1473         FATAL_ALWAYS ("ATSUSetTransientFontMatching failed(%d)", status);
1474         
1475     return layout;
1476 }
1477
1478
1479 - (ATSTrapezoid)_trapezoidForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style atPoint:(NSPoint )p
1480 {
1481     // The only Cocoa call here is the self call to
1482     // _createATSUTextLayoutForRun:, which is exception-safe.
1483
1484     OSStatus status;
1485     
1486     if (run->to - run->from <= 0){
1487         ATSTrapezoid nilTrapezoid = { {0,0} , {0,0}, {0,0}, {0,0} };
1488         return nilTrapezoid;
1489     }
1490         
1491     ATSUTextLayout layout = [self _createATSUTextLayoutForRun:run style:style];
1492
1493     ATSTrapezoid firstGlyphBounds;
1494     ItemCount actualNumBounds;
1495     status = ATSUGetGlyphBounds (layout, FloatToFixed(p.x), FloatToFixed(p.y), run->from, run->to - run->from, kATSUseDeviceOrigins, 1, &firstGlyphBounds, &actualNumBounds);    
1496     if(status != noErr)
1497         FATAL_ALWAYS ("ATSUGetGlyphBounds() failed(%d)", status);
1498     
1499     if (actualNumBounds != 1)
1500         FATAL_ALWAYS ("unexpected result from ATSUGetGlyphBounds():  actualNumBounds(%d) != 1", actualNumBounds);
1501
1502     ATSUDisposeTextLayout (layout); // Ignore the error.  Nothing we can do anyway.
1503             
1504     return firstGlyphBounds;
1505 }
1506
1507
1508 - (float)_ATSU_floatWidthForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style
1509 {
1510     ATSTrapezoid oGlyphBounds;
1511     
1512     oGlyphBounds = [self _trapezoidForRun:run style:style atPoint:NSMakePoint (0,0)];
1513     
1514     float width = 
1515         MAX(FixedToFloat(oGlyphBounds.upperRight.x), FixedToFloat(oGlyphBounds.lowerRight.x)) - 
1516         MIN(FixedToFloat(oGlyphBounds.upperLeft.x), FixedToFloat(oGlyphBounds.lowerLeft.x));
1517     
1518     return width;
1519 }
1520
1521 // Be sure to free the run.characters allocated by this function.
1522 static WebCoreTextRun reverseCharactersInRun(const WebCoreTextRun *run)
1523 {
1524     WebCoreTextRun swappedRun;
1525     unsigned int i;
1526     
1527     UniChar *swappedCharacters = (UniChar *)malloc(sizeof(UniChar)*run->length);
1528     for (i = 0; i < run->length; i++) {
1529         swappedCharacters[i] = run->characters[run->length-i-1];
1530     }
1531     swappedRun.characters = swappedCharacters;
1532     swappedRun.from = run->length - (run->to == -1 ? (int)run->length : run->to);
1533     swappedRun.to = run->length - (run->from == -1 ? 0 : run->from);
1534     swappedRun.length = run->length;
1535
1536     return swappedRun;
1537 }
1538
1539 - (void)_ATSU_drawHighlightForRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style geometry:(const WebCoreTextGeometry *)geometry
1540 {
1541     // The only Cocoa calls made here are to NSColor and NSBezierPath,
1542     // plus the self calls to _createATSUTextLayoutForRun: and
1543     // _trapezoidForRun:. These are all exception-safe.
1544
1545     ATSUTextLayout layout;
1546     int from, to;
1547     float selectedLeftX;
1548     const WebCoreTextRun *aRun = run;
1549     WebCoreTextRun swappedRun;
1550
1551     if (style->backgroundColor == nil)
1552         return;
1553     
1554     if (style->visuallyOrdered) {
1555         swappedRun = reverseCharactersInRun(run);
1556         aRun = &swappedRun;
1557     }
1558
1559     from = aRun->from;
1560     to = aRun->to;
1561     if (from == -1)
1562         from = 0;
1563     if (to == -1)
1564         to = run->length;
1565    
1566     int runLength = to - from;
1567     if (runLength <= 0){
1568         return;
1569     }
1570
1571     layout = [self _createATSUTextLayoutForRun:aRun style:style];
1572
1573     WebCoreTextRun leadingRun = *aRun;
1574     leadingRun.from = 0;
1575     leadingRun.to = run->from;
1576     
1577     // ATSU provides the bounds of the glyphs for the run with an origin of
1578     // (0,0), so we need to find the width of the glyphs immediately before
1579     // the actually selected glyphs.
1580     ATSTrapezoid leadingTrapezoid = [self _trapezoidForRun:&leadingRun style:style atPoint:geometry->point];
1581     ATSTrapezoid selectedTrapezoid = [self _trapezoidForRun:run style:style atPoint:geometry->point];
1582
1583     float backgroundWidth = 
1584             MAX(FixedToFloat(selectedTrapezoid.upperRight.x), FixedToFloat(selectedTrapezoid.lowerRight.x)) - 
1585             MIN(FixedToFloat(selectedTrapezoid.upperLeft.x), FixedToFloat(selectedTrapezoid.lowerLeft.x));
1586
1587     if (run->from == 0)
1588         selectedLeftX = geometry->point.x;
1589     else
1590         selectedLeftX = MIN(FixedToFloat(leadingTrapezoid.upperRight.x), FixedToFloat(leadingTrapezoid.lowerRight.x));
1591     
1592     [style->backgroundColor set];
1593
1594     float yPos = geometry->useFontMetricsForSelectionYAndHeight ? geometry->point.y - [self ascent] : geometry->selectionY;
1595     float height = geometry->useFontMetricsForSelectionYAndHeight ? [self lineSpacing] : geometry->selectionHeight;
1596     if (style->rtl || style->visuallyOrdered){
1597         WebCoreTextRun completeRun = *aRun;
1598         completeRun.from = 0;
1599         completeRun.to = aRun->length;
1600         float completeRunWidth = [self floatWidthForRun:&completeRun style:style widths:0];
1601         [NSBezierPath fillRect:NSMakeRect(geometry->point.x + completeRunWidth - (selectedLeftX-geometry->point.x) - backgroundWidth, yPos, backgroundWidth, height)];
1602     }
1603     else {
1604         [NSBezierPath fillRect:NSMakeRect(selectedLeftX, yPos, backgroundWidth, height)];
1605     }
1606
1607     ATSUDisposeTextLayout (layout); // Ignore the error.  Nothing we can do anyway.
1608
1609     if (style->visuallyOrdered)
1610         free ((void *)swappedRun.characters);
1611 }
1612
1613
1614 - (void)_ATSU_drawRun:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style geometry:(const WebCoreTextGeometry *)geometry
1615 {
1616     // The only Cocoa calls made here are to NSColor, plus the self
1617     // calls to _createATSUTextLayoutForRun: and
1618     // _ATSU_drawHighlightForRun:. These are all exception-safe.
1619
1620     ATSUTextLayout layout;
1621     OSStatus status;
1622     int from, to;
1623     const WebCoreTextRun *aRun = run;
1624     WebCoreTextRun swappedRun;
1625     
1626     if (style->visuallyOrdered) {
1627         swappedRun = reverseCharactersInRun(run);
1628         aRun = &swappedRun;
1629     }
1630
1631     from = aRun->from;
1632     to = aRun->to;
1633     if (from == -1)
1634         from = 0;
1635     if (to == -1)
1636         to = run->length;
1637
1638     int runLength = to - from;
1639     if (runLength <= 0)
1640         return;
1641
1642     layout = [self _createATSUTextLayoutForRun:aRun style:style];
1643
1644     if (style->backgroundColor != nil)
1645         [self _ATSU_drawHighlightForRun:run style:style geometry:geometry];
1646
1647     [style->textColor set];
1648
1649     status = ATSUDrawText(layout, 
1650             aRun->from,
1651             runLength,
1652             FloatToFixed(geometry->point.x),   // these values are
1653             FloatToFixed(geometry->point.y));  // also of type Fixed
1654     if (status != noErr){
1655         // Nothing to do but report the error (dev build only).
1656         ERROR ("ATSUDrawText() failed(%d)", status);
1657     }
1658
1659     ATSUDisposeTextLayout (layout); // Ignore the error.  Nothing we can do anyway.
1660     
1661     if (style->visuallyOrdered)
1662         free ((void *)swappedRun.characters);
1663 }
1664
1665 - (int)_ATSU_pointToOffset:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style position:(int)x reversed:(BOOL)reversed includePartialGlyphs:(BOOL)includePartialGlyphs
1666 {
1667     // The only Cocoa calls made here is to the self call to
1668     // _createATSUTextLayoutForRun:. This is exception-safe.
1669
1670     unsigned offset = 0;
1671     ATSUTextLayout layout;
1672     UniCharArrayOffset primaryOffset = 0;
1673     UniCharArrayOffset secondaryOffset = 0;
1674     OSStatus status;
1675     Boolean isLeading;
1676     const WebCoreTextRun *aRun = run;
1677     WebCoreTextRun swappedRun;
1678     
1679     // Reverse the visually ordered characters.  ATSU will re-reverse.  Ick!
1680     if (style->visuallyOrdered) {
1681         swappedRun = reverseCharactersInRun(run);
1682         aRun = &swappedRun;
1683     }
1684
1685     layout = [self _createATSUTextLayoutForRun:aRun style:style];
1686
1687     primaryOffset = aRun->from;
1688     
1689     // FIXME: No idea how to avoid including partial glyphs.   Not even sure if that's the behavior
1690     // this yields now.
1691     status = ATSUPositionToOffset(layout, FloatToFixed(x), FloatToFixed(-1), &primaryOffset, &isLeading, &secondaryOffset);
1692     if (status == noErr){
1693         offset = (unsigned)primaryOffset;
1694     }
1695     else {
1696         // Failed to find offset!  Return 0 offset.
1697     }
1698        
1699     if (style->visuallyOrdered) {
1700         free ((void *)swappedRun.characters);
1701     }
1702
1703     return offset - aRun->from;
1704 }
1705
1706 - (int)_CG_pointToOffset:(const WebCoreTextRun *)run style:(const WebCoreTextStyle *)style position:(int)x reversed:(BOOL)reversed includePartialGlyphs:(BOOL)includePartialGlyphs
1707 {
1708     float delta = (float)x;
1709     float width;
1710     unsigned offset = run->from;
1711     CharacterWidthIterator widthIterator;
1712     
1713     initializeCharacterWidthIterator(&widthIterator, self, run, style);
1714
1715     if (reversed) {
1716         width = [self floatWidthForRun:run style:style widths:nil];
1717         delta -= width;
1718         while (offset < run->length) {
1719             float w = widthForNextCharacter(&widthIterator, 0, 0);
1720             if (w == INVALID_WIDTH) {
1721                 // Something very bad happened, like we only have half of a surrogate pair.
1722                 break;
1723             }
1724             else {
1725                 if (w) {
1726                     if (includePartialGlyphs)
1727                        w -= w/2;
1728                     delta += w;
1729                     if(delta >= 0)
1730                         break;
1731                     if (includePartialGlyphs)
1732                         delta += w;
1733                 }
1734                 offset = widthIterator.currentCharacter;
1735             }
1736         }
1737     } else {
1738         while (offset < run->length) {
1739             float w = widthForNextCharacter(&widthIterator, 0, 0);
1740             if (w == INVALID_WIDTH) {
1741                 // Something very bad happened, like we only have half of a surrogate pair.
1742                 break;
1743             }
1744             else {
1745                 if (w) {
1746                     if (includePartialGlyphs)
1747                         w -= w/2;
1748                     delta -= w;
1749                     if(delta <= 0) 
1750                         break;
1751                     if (includePartialGlyphs)
1752                         delta -= w;
1753                 }
1754                 offset = widthIterator.currentCharacter;
1755             }
1756         }
1757     }
1758     
1759     return offset - run->from;
1760 }
1761
1762 @end
1763
1764 // ------------------- Private functions -------------------
1765
1766 static void freeWidthMap(WidthMap *map)
1767 {
1768     while (map) {
1769         WidthMap *next = map->next;
1770         free(map->widths);
1771         free(map);
1772         map = next;
1773     }
1774 }
1775
1776
1777 static void freeGlyphMap(GlyphMap *map)
1778 {
1779     while (map) {
1780         GlyphMap *next = map->next;
1781         free(map->glyphs);
1782         free(map);
1783         map = next;
1784     }
1785 }
1786
1787
1788 static void freeUnicodeGlyphMap(UnicodeGlyphMap *map)
1789 {
1790     while (map) {
1791         UnicodeGlyphMap *next = map->next;
1792         free(map->glyphs);
1793         free(map);
1794         map = next;
1795     }
1796 }
1797
1798
1799 static inline ATSGlyphRef glyphForCharacter (GlyphMap *map, UniChar c, NSFont **font)
1800 {
1801     if (map == 0)
1802         return nonGlyphID;
1803         
1804     while (map) {
1805         if (c >= map->startRange && c <= map->endRange){
1806             *font = map->glyphs[c-map->startRange].font;
1807             return map->glyphs[c-map->startRange].glyph;
1808         }
1809         map = map->next;
1810     }
1811     return nonGlyphID;
1812 }
1813  
1814  
1815 static inline ATSGlyphRef glyphForUnicodeCharacter (UnicodeGlyphMap *map, UnicodeChar c, NSFont **font)
1816 {
1817     if (map == 0)
1818         return nonGlyphID;
1819         
1820     while (map) {
1821         if (c >= map->startRange && c <= map->endRange){
1822             *font = map->glyphs[c-map->startRange].font;
1823             return map->glyphs[c-map->startRange].glyph;
1824         }
1825         map = map->next;
1826     }
1827     return nonGlyphID;
1828 }
1829  
1830
1831 #ifdef _TIMING        
1832 static double totalCGGetAdvancesTime = 0;
1833 #endif
1834
1835 static inline SubstituteFontWidthMap *mapForSubstituteFont(WebTextRenderer *renderer, NSFont *font)
1836 {
1837     int i;
1838     
1839     for (i = 0; i < renderer->numSubstituteFontWidthMaps; i++){
1840         if (font == renderer->substituteFontWidthMaps[i].font)
1841             return &renderer->substituteFontWidthMaps[i];
1842     }
1843     
1844     if (renderer->numSubstituteFontWidthMaps == renderer->maxSubstituteFontWidthMaps){
1845         renderer->maxSubstituteFontWidthMaps = renderer->maxSubstituteFontWidthMaps * 2;
1846         renderer->substituteFontWidthMaps = realloc (renderer->substituteFontWidthMaps, renderer->maxSubstituteFontWidthMaps * sizeof(SubstituteFontWidthMap));
1847         for (i = renderer->numSubstituteFontWidthMaps; i < renderer->maxSubstituteFontWidthMaps; i++){
1848             renderer->substituteFontWidthMaps[i].font = 0;
1849             renderer->substituteFontWidthMaps[i].map = 0;
1850         }
1851     }
1852     
1853     renderer->substituteFontWidthMaps[renderer->numSubstituteFontWidthMaps].font = font;
1854     return &renderer->substituteFontWidthMaps[renderer->numSubstituteFontWidthMaps++];
1855 }
1856
1857 static void initializeCharacterWidthIterator (CharacterWidthIterator *iterator, WebTextRenderer *renderer, const WebCoreTextRun *run , const WebCoreTextStyle *style) 
1858 {
1859     iterator->renderer = renderer;
1860     iterator->run = run;
1861     iterator->style = style;
1862     iterator->currentCharacter = run->from;
1863     iterator->runWidthSoFar = 0;
1864
1865     // If the padding is non-zero, count the number of spaces in the run
1866     // and divide that by the padding for per space addition.
1867     iterator->padding = style->padding;
1868     if (iterator->padding > 0){
1869         uint numSpaces = 0;
1870         int from = run->from;
1871         int len = run->to - from;
1872         int k;
1873         for (k = from; k < from + len; k++) {
1874             if (isSpace(run->characters[k])) {
1875                 numSpaces++;
1876             }
1877         }
1878         iterator->padPerSpace = CEIL_TO_INT ((((float)style->padding) / ((float)numSpaces)));
1879     }
1880     else {
1881         iterator->padPerSpace = 0;
1882     }
1883     
1884     // Calculate width up to starting position of the run.  This is
1885     // necessary to ensure that our rounding hacks are always consistently
1886     // applied.
1887     if (run->from != 0){
1888         WebCoreTextRun startPositionRun = *run;
1889         startPositionRun.from = 0;
1890         startPositionRun.to = run->from;
1891         CharacterWidthIterator startPositionIterator;
1892         initializeCharacterWidthIterator (&startPositionIterator, renderer, &startPositionRun, style);
1893         
1894         while (startPositionIterator.currentCharacter < (unsigned)startPositionRun.to){
1895             widthForNextCharacter(&startPositionIterator, 0, 0);
1896         }
1897         iterator->widthToStart = startPositionIterator.runWidthSoFar;
1898     }
1899     else
1900         iterator->widthToStart = 0;
1901 }
1902
1903 static inline float ceilCurrentWidth (CharacterWidthIterator *iterator)
1904 {
1905     float delta = CEIL_TO_INT(iterator->widthToStart + iterator->runWidthSoFar) - (iterator->widthToStart + iterator->runWidthSoFar);
1906     iterator->runWidthSoFar += delta;
1907     return delta;
1908 }
1909
1910 // Return INVALID_WIDTH if an error is encountered or we're at the end of the range in the run.
1911 static float widthForNextCharacter(CharacterWidthIterator *iterator, ATSGlyphRef *glyphUsed, NSFont **fontUsed)
1912 {
1913     WebTextRenderer *renderer = iterator->renderer;
1914     const WebCoreTextRun *run = iterator->run;
1915     unsigned currentCharacter = iterator->currentCharacter;
1916
1917     NSFont *_fontUsed = nil;
1918     ATSGlyphRef _glyphUsed;
1919
1920     if (!fontUsed)
1921         fontUsed = &_fontUsed;
1922     if (!glyphUsed)
1923         glyphUsed = &_glyphUsed;
1924         
1925     if (currentCharacter >= (unsigned)run->to)
1926         // Error! Offset specified beyond end of run.
1927         return INVALID_WIDTH;
1928
1929     const UniChar *cp = &run->characters[currentCharacter];
1930     UnicodeChar c = *cp;
1931
1932     if (IsLowSurrogatePair(c))
1933         return INVALID_WIDTH;
1934
1935     // Do we have a surrogate pair?  If so, determine the full Unicode (32 bit)
1936     // code point before glyph lookup.
1937     unsigned clusterLength = 1;
1938     if (IsHighSurrogatePair(c)) {
1939         // Make sure we have another character and it's a low surrogate.
1940         UniChar low;
1941         if (currentCharacter + 1 >= run->length || !IsLowSurrogatePair((low = cp[1]))) {
1942             // Error!  The second component of the surrogate pair is missing.
1943             return INVALID_WIDTH;
1944         }
1945
1946         c = UnicodeValueForSurrogatePair(c, low);
1947         clusterLength = 2;
1948     }
1949
1950     // If small-caps convert lowercase to upper.
1951     BOOL useSmallCapsFont = NO;
1952     if (renderer->isSmallCapsRenderer) {
1953         if (!u_isUUppercase(c)) {
1954             // Only use small cap font if the the uppercase version of the character
1955             // is different than the lowercase.
1956             UnicodeChar newC = u_toupper(c);
1957             if (newC != c) {
1958                 useSmallCapsFont = YES;
1959                 c = newC;
1960             }
1961         }
1962     }
1963
1964     if (c <= 0xFFFF) {
1965         *glyphUsed = glyphForCharacter(renderer->characterToGlyphMap, c, fontUsed);
1966         if (*glyphUsed == nonGlyphID) {
1967             *glyphUsed = [renderer _extendCharacterToGlyphMapToInclude:c];
1968         }
1969     } else {
1970         *glyphUsed = glyphForUnicodeCharacter(renderer->unicodeCharacterToGlyphMap, c, fontUsed);
1971         if (*glyphUsed == nonGlyphID) {
1972             *glyphUsed = [renderer _extendUnicodeCharacterToGlyphMapToInclude:c];
1973         }
1974     }
1975
1976     // Check to see if we're rendering in 'small-caps' mode.
1977     // ASSUMPTION:  We assume the same font in a smaller size has
1978     // the same glyphs as the large font.
1979     if (useSmallCapsFont) {
1980         if (*fontUsed == nil)
1981             *fontUsed = [renderer _smallCapsFont];
1982         else {
1983             // Potential for optimization.  This path should only be taken if we're
1984             // using a cached substituted font.
1985             *fontUsed = [[NSFontManager sharedFontManager] convertFont:*fontUsed toSize:[*fontUsed pointSize] * SMALLCAPS_FONTSIZE_MULTIPLIER];
1986         }
1987     }
1988
1989     // Now that we have glyph and font, get its width.
1990     WebGlyphWidth width = widthForGlyph(renderer, *glyphUsed, *fontUsed);
1991
1992     // We special case spaces in two ways when applying word rounding.
1993     // First, we round spaces to an adjusted width in all fonts.
1994     // Second, in fixed-pitch fonts we ensure that all characters that
1995     // match the width of the space character have the same width as the space character.
1996     if ((renderer->treatAsFixedPitch ? width == renderer->spaceWidth : *glyphUsed == renderer->spaceGlyph) && iterator->style->applyWordRounding)
1997         width = renderer->adjustedSpaceWidth;
1998
1999     // Try to find a substitute font if this font didn't have a glyph for a character in the
2000     // string.  If one isn't found we end up drawing and measuring the 0 glyph, usually a box.
2001     if (*glyphUsed == 0 && iterator->style->attemptFontSubstitution) {
2002         UniChar characterArray[2];
2003         unsigned characterArrayLength;
2004         
2005         if (c <= 0xFFFF) {
2006             characterArray[0] = c;
2007             characterArrayLength = 1;
2008         } else {
2009             characterArray[0] = HighSurrogatePair(c);
2010             characterArray[1] = LowSurrogatePair(c);
2011             characterArrayLength = 2;
2012         }
2013         
2014         NSFont *substituteFont = [renderer _substituteFontForCharacters:characterArray length:characterArrayLength
2015             families:iterator->style->families];
2016         if (substituteFont) {
2017             int cNumGlyphs = 0;
2018             ATSGlyphRef localGlyphBuffer[MAX_GLYPH_EXPANSION];
2019             
2020             WebCoreTextRun clusterRun;
2021             WebCoreInitializeTextRun(&clusterRun, characterArray, characterArrayLength, 0, characterArrayLength);
2022             WebCoreTextStyle clusterStyle = *iterator->style;
2023             clusterStyle.padding = 0;
2024             clusterStyle.applyRunRounding = false;
2025             clusterStyle.attemptFontSubstitution = false;
2026             
2027             WebTextRenderer *substituteRenderer;
2028             substituteRenderer = [[WebTextRendererFactory sharedFactory] rendererWithFont:substituteFont usingPrinterFont:renderer->usingPrinterFont];
2029             width = [substituteRenderer
2030                             _floatWidthForRun:&clusterRun
2031                             style:&clusterStyle 
2032                             widths: nil
2033                             fonts: nil
2034                             glyphs: &localGlyphBuffer[0]
2035                             startPosition:nil
2036                             numGlyphs:&cNumGlyphs];
2037             
2038             *fontUsed = substituteFont;
2039             *glyphUsed = localGlyphBuffer[0];
2040             
2041             if (c <= 0xFFFF && cNumGlyphs == 1 && localGlyphBuffer[0] != 0){
2042                 [renderer _updateGlyphEntryForCharacter:c glyphID:localGlyphBuffer[0] font:substituteFont];
2043             }
2044         }
2045     }
2046
2047     if (!*fontUsed)
2048         *fontUsed = renderer->font;
2049
2050     // Force characters that are used to determine word boundaries for the rounding hack
2051     // to be integer width, so following words will start on an integer boundary.
2052     if (isRoundingHackCharacter(c) && iterator->style->applyWordRounding) {
2053         width = CEIL_TO_INT(width);
2054     }
2055     
2056     // Account for letter-spacing
2057     if (iterator->style->letterSpacing && width > 0)
2058         width += iterator->style->letterSpacing;
2059
2060     // Account for padding.  khtml uses space padding to justify text.  We
2061     // distribute the specified padding over the available spaces in the run.
2062     if (isSpace(c)) {
2063         if (iterator->padding > 0) {
2064             // Only use left over padding if note evenly divisible by 
2065             // number of spaces.
2066             if (iterator->padding < iterator->padPerSpace){
2067                 width += iterator->padding;
2068                 iterator->padding = 0;
2069             }
2070             else {
2071                 width += iterator->padPerSpace;
2072                 iterator->padding -= iterator->padPerSpace;
2073             }
2074         }
2075         
2076         // Account for word-spacing.  We apply additional space between "words" by
2077         // adding width to the space character.
2078         if (currentCharacter > 0 && !isSpace(cp[-1]))
2079             width += iterator->style->wordSpacing;
2080     }
2081
2082     iterator->runWidthSoFar += width;
2083
2084     // Advance past the character we just dealt with.
2085     currentCharacter += clusterLength;
2086     iterator->currentCharacter = currentCharacter;
2087
2088     int len = run->to - run->from;
2089
2090     // Account for float/integer impedance mismatch between CG and khtml.  "Words" (characters 
2091     // followed by a character defined by isSpace()) are always an integer width.  We adjust the 
2092     // width of the last character of a "word" to ensure an integer width.  When we move khtml to
2093     // floats we can remove this (and related) hacks.
2094     //
2095     // Check to see if the next character is a "RoundingHackCharacter", if so, adjust.
2096     if (currentCharacter < run->length && isRoundingHackCharacter(cp[clusterLength]) && iterator->style->applyWordRounding) {
2097         width += ceilCurrentWidth(iterator);
2098     }
2099     else if (currentCharacter >= (unsigned)run->to && (len > 1 || run->length == 1) && iterator->style->applyRunRounding) {
2100         width += ceilCurrentWidth(iterator);
2101     }
2102     
2103     return width;
2104 }
2105
2106
2107 static BOOL fillStyleWithAttributes(ATSUStyle style, NSFont *theFont)
2108 {
2109     if (theFont) {
2110         ATSUFontID fontId = [theFont _atsFontID];
2111         LOG (FontCache, "fillStyleWithAttributes:  font = %p,%@, _atsFontID = %x\n", theFont, theFont, (unsigned)fontId);
2112         ATSUAttributeTag tag = kATSUFontTag;
2113         ByteCount size = sizeof(ATSUFontID);
2114         ATSUFontID *valueArray[1] = {&fontId};
2115         OSStatus status;
2116
2117         if (fontId) {
2118             status = ATSUSetAttributes(style, 1, &tag, &size, (void *)valueArray);
2119             if (status != noErr){
2120                 LOG (FontCache, "fillStyleWithAttributes failed(%d):  font = %p,%@, _atsFontID = %x\n", (int)status, theFont, theFont, (unsigned)fontId);
2121                 return NO;
2122             }
2123         }
2124         else {
2125             return NO;
2126         }
2127         return YES;
2128     }
2129     return NO;
2130 }
2131
2132 static BOOL shouldUseATSU(const WebCoreTextRun *run)
2133 {
2134     UniChar c;
2135     const UniChar *characters = run->characters;
2136     int i, from = run->from, to = run->to;
2137     
2138     if (alwaysUseATSU)
2139         return YES;
2140         
2141     for (i = from; i < to; i++){
2142         c = characters[i];
2143         if (c < 0x300)                      // Early continue to avoid other checks for the common case.
2144             continue;
2145             
2146         if (c >= 0x300 && c <= 0x36F)       // U+0300 through U+036F Combining diacritical marks
2147             return YES;
2148         if (c >= 0x20D0 && c <= 0x20FF)     // U+20D0 through U+20FF Combining marks for symbols
2149             return YES;
2150         if (c >= 0xFE20 && c <= 0xFE2f)     // U+FE20 through U+FE2F Combining half marks
2151             return YES;
2152         if (c >= 0x591 && c <= 0x1059)      // U+0591 through U+1059 Arabic, Hebrew, Syriac, Thaana, Devanagari, Bengali, Gurmukhi, Gujarati, Oriya, Tamil, Telugu, Kannada, Malayalam, Sinhala, Thai, Lao, Tibetan, Myanmar
2153             return YES;
2154         if (c >= 0x1100 && c <= 0x11FF)     // 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)
2155             return YES;
2156         if (c >= 0x1780 && c <= 0x18AF)     // U+1780 through U+18AF Khmer, Mongolian
2157             return YES;
2158         if (c >= 0x1900 && c <= 0x194F)     // U+1900 through U+194F Limbu (Unicode 4.0)
2159             return YES;
2160     }
2161     
2162     return NO;
2163 }