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