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