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