1/** <title>NSStringAdditions</title>
2
3   <abstract>Categories which add drawing capabilities to NSAttributedString
4   and NSString.</abstract>
5
6   Copyright (C) 1999, 2003, 2004, 2017 Free Software Foundation, Inc.
7
8   Author: Richard Frith-Macdonald <richard@brainstorm.co.uk>
9   Date: Mar 1999 - rewrite from scratch
10
11   Author: Alexander Malmberg <alexander@malmberg.org>
12   Date: November 2002 - February 2003 (rewrite to use NSLayoutManager et al)
13
14   This file is part of the GNUstep GUI Library.
15
16   This library is free software; you can redistribute it and/or
17   modify it under the terms of the GNU Lesser General Public
18   License as published by the Free Software Foundation; either
19   version 2 of the License, or (at your option) any later version.
20
21   This library is distributed in the hope that it will be useful,
22   but WITHOUT ANY WARRANTY; without even the implied warranty of
23   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
24   Lesser General Public License for more details.
25
26   You should have received a copy of the GNU Lesser General Public
27   License along with this library; see the file COPYING.LIB.
28   If not, see <http://www.gnu.org/licenses/> or write to the
29   Free Software Foundation, 51 Franklin Street, Fifth Floor,
30   Boston, MA 02110-1301, USA.
31*/
32
33#include <math.h>
34
35#import <Foundation/NSException.h>
36#import <Foundation/NSLock.h>
37
38#import "AppKit/NSAffineTransform.h"
39#import "AppKit/NSLayoutManager.h"
40#import "AppKit/NSStringDrawing.h"
41#import "AppKit/NSTextContainer.h"
42#import "AppKit/NSTextStorage.h"
43#import "AppKit/DPSOperators.h"
44
45/*
46Apple uses this as the maximum width of an NSTextContainer.
47For bigger values the width gets ignored.
48*/
49#define LARGE_SIZE 1e7
50
51
52/*
53A size of 16 and these constants give a hit rate of 80%-90% for normal app
54use (based on real world statistics gathered with the help of some users
55from #GNUstep).
56We use the last entry of the cache as a scratch element to set up an initial
57text network.
58*/
59#define NUM_CACHE_ENTRIES 16
60#define HIT_BOOST         2
61#define MISS_COST         1
62
63
64typedef struct
65{
66  int used;
67  NSUInteger string_hash;
68  BOOL hasSize, useScreenFonts;
69
70  NSTextStorage *textStorage;
71  NSLayoutManager *layoutManager;
72  NSTextContainer *textContainer;
73
74  NSSize givenSize;
75  NSRect usedRect;
76} cache_t;
77
78
79static BOOL did_init = NO;
80static cache_t cache[NUM_CACHE_ENTRIES + 1];
81
82
83static NSRecursiveLock *cacheLock = nil;
84
85/* For collecting statistics. */
86//#define STATS
87
88#ifdef STATS
89static int total, hits, misses, hash_hits;
90
91static void NSStringDrawing_dump_stats(void)
92{
93#define P(x) printf("%15i %s\n", x, #x);
94  P(total)
95  P(hits)
96  P(misses)
97  P(hash_hits)
98#undef P
99  printf("%15.8f hit ratio\n", hits / (double)total);
100}
101#endif
102
103static void init_string_drawing(void)
104{
105  int i;
106  NSTextStorage *textStorage;
107  NSLayoutManager *layoutManager;
108  NSTextContainer *textContainer;
109
110  if (did_init)
111    return;
112  did_init = YES;
113
114#ifdef STATS
115  atexit(NSStringDrawing_dump_stats);
116#endif
117
118  for (i = 0; i < NUM_CACHE_ENTRIES + 1; i++)
119    {
120      textStorage = [[NSTextStorage alloc] init];
121      layoutManager = [[NSLayoutManager alloc] init];
122      [textStorage addLayoutManager: layoutManager];
123      [layoutManager release];
124      textContainer = [[NSTextContainer alloc]
125			initWithContainerSize: NSMakeSize(10, 10)];
126      [textContainer setLineFragmentPadding: 0];
127      [layoutManager addTextContainer: textContainer];
128      [textContainer release];
129
130      cache[i].textStorage = textStorage;
131      cache[i].layoutManager = layoutManager;
132      cache[i].textContainer = textContainer;
133    }
134}
135
136static inline void cache_lock()
137{
138  // FIXME: Put all the init code into an +initialize method
139  // to let the runtime take care of it.
140  if (cacheLock == nil)
141    {
142      cacheLock = [[NSRecursiveLock alloc] init];
143    }
144  [cacheLock lock];
145  if (!did_init)
146    {
147      init_string_drawing();
148    }
149}
150
151static inline void cache_unlock()
152{
153  [cacheLock unlock];
154}
155
156static inline BOOL is_size_match(cache_t *c, cache_t *scratch)
157{
158  if ((!c->hasSize && !scratch->hasSize) ||
159      (c->hasSize && scratch->hasSize
160       && NSEqualSizes(c->givenSize, scratch->givenSize)))
161    {
162      return YES;
163    }
164  else
165    {
166      return NO;
167    }
168}
169
170static inline BOOL is_match(cache_t *c, cache_t *scratch)
171{
172  if (c->string_hash != scratch->string_hash
173      || c->useScreenFonts != scratch->useScreenFonts)
174    return NO;
175
176#ifdef STATS
177  hash_hits++;
178#endif
179
180  if (![scratch->textStorage isEqualToAttributedString: c->textStorage])
181    return NO;
182
183  /* String and attributes match, check size. */
184  return is_size_match(c, scratch);
185}
186
187static cache_t *cache_match(cache_t *scratch, BOOL *matched)
188{
189  int i, j;
190  cache_t *c;
191  int least_used = -1;
192  int replace = -1;
193
194#ifdef STATS
195  total++;
196#endif
197
198  /*
199  A deterministic pattern for replacing cache entries can hit ugly worst
200  cases on certain matching use patterns (where the cache is full of old
201  unused entries, but the new entries keep replacing each other).
202
203  By starting at a random index, we avoid this kind of problem.
204  */
205  j = rand() % NUM_CACHE_ENTRIES;
206  for (i = 0; i < NUM_CACHE_ENTRIES; i++, j++)
207    {
208      if (j == NUM_CACHE_ENTRIES)
209        {
210          j = 0;
211        }
212      c = cache + j;
213      if (least_used == -1 || c->used < least_used)
214	{
215	  least_used = c->used;
216	  replace = j;
217	}
218
219      if (!c->used)
220	continue;
221
222      if (is_match(c, scratch))
223	{
224#ifdef STATS
225	  hits++;
226#endif
227
228	  c->used += HIT_BOOST;
229          *matched = YES;
230	  return c;
231	}
232      else
233        {
234          if (c->used > MISS_COST)
235            {
236              c->used -= MISS_COST;
237            }
238          else
239            {
240              c->used = 1;
241            }
242        }
243    }
244
245  NSCAssert(replace != -1, @"Couldn't find a cache entry to replace.");
246
247#ifdef STATS
248  misses++;
249#endif
250  *matched = NO;
251
252  /* We did not find a matching entry, return the least used one */
253  return cache + replace;
254}
255
256static cache_t *cache_lookup(BOOL hasSize, NSSize size, BOOL useScreenFonts)
257{
258  BOOL hit;
259  cache_t *c;
260  cache_t *scratch = cache + NUM_CACHE_ENTRIES;
261
262  scratch->used = 1;
263  scratch->string_hash = [[scratch->textStorage string] hash];
264  scratch->hasSize = hasSize;
265  scratch->useScreenFonts = useScreenFonts;
266  scratch->givenSize = size;
267
268  c = cache_match(scratch, &hit);
269  if (!hit)
270    {
271      // Swap c and scratch
272      cache_t temp;
273
274      temp = *c;
275      *c = *scratch;
276      *scratch = temp;
277
278      // Cache miss, need to set up the text system
279      if (hasSize)
280        {
281          [c->textContainer setContainerSize: NSMakeSize(size.width, size.height)];
282        }
283      else
284        {
285          [c->textContainer setContainerSize: NSMakeSize(LARGE_SIZE, LARGE_SIZE)];
286        }
287      [c->layoutManager setUsesScreenFonts: useScreenFonts];
288      // Layout the whole container
289      [c->layoutManager glyphRangeForTextContainer: c->textContainer];
290      c->usedRect = [c->layoutManager usedRectForTextContainer: c->textContainer];
291    }
292
293  return c;
294}
295
296static inline void prepare_string(NSString *string, NSDictionary *attributes)
297{
298  cache_t *scratch = cache + NUM_CACHE_ENTRIES;
299  NSTextStorage *scratchTextStorage = scratch->textStorage;
300
301  [scratchTextStorage beginEditing];
302  [scratchTextStorage replaceCharactersInRange: NSMakeRange(0, [scratchTextStorage length])
303                                    withString: string];
304  if ([string length])
305    {
306      [scratchTextStorage setAttributes: attributes
307			  range: NSMakeRange(0, [string length])];
308    }
309  [scratchTextStorage endEditing];
310}
311
312static inline void prepare_attributed_string(NSAttributedString *string)
313{
314  cache_t *scratch = cache + NUM_CACHE_ENTRIES;
315  NSTextStorage *scratchTextStorage = scratch->textStorage;
316
317  [scratchTextStorage replaceCharactersInRange: NSMakeRange(0, [scratchTextStorage length])
318                          withAttributedString: string];
319}
320
321static BOOL use_screen_fonts(void)
322{
323  NSGraphicsContext		*ctxt = GSCurrentContext();
324  NSAffineTransform		*ctm = GSCurrentCTM(ctxt);
325  NSAffineTransformStruct	ts = [ctm transformStruct];
326
327  if (ts.m11 != 1.0 || ts.m12 != 0.0 || ts.m21 != 0.0 || fabs(ts.m22) != 1.0)
328    {
329      return NO;
330    }
331  else
332    {
333      return YES;
334    }
335}
336
337/*
338This is an ugly hack to get text to display correctly in non-flipped views.
339
340The text system always has positive y down, so we flip the coordinate
341system when drawing (if the view isn't flipped already). This causes the
342glyphs to be drawn upside-down, so we need to tell NSFont to flip the fonts.
343*/
344@interface NSFont (FontFlipHack)
345+(void) _setFontFlipHack: (BOOL)flip;
346@end
347
348static void draw_at_point(cache_t *c, NSPoint point)
349{
350  NSRange r;
351  BOOL need_flip = ![[NSView focusView] isFlipped];
352  NSGraphicsContext *ctxt = GSCurrentContext();
353
354  r = NSMakeRange(0, [c->layoutManager numberOfGlyphs]);
355
356  if (need_flip)
357    {
358      DPSscale(ctxt, 1, -1);
359      point.y = -point.y;
360
361      /*
362        Adjust point.y so the lower left corner of the used rect is at the
363        point that was passed to us.
364      */
365      point.y -= NSMaxY(c->usedRect);
366
367      [NSFont _setFontFlipHack: YES];
368    }
369
370  [c->layoutManager drawBackgroundForGlyphRange: r
371                                        atPoint: point];
372  [c->layoutManager drawGlyphsForGlyphRange: r
373                                    atPoint: point];
374
375  if (need_flip)
376    {
377      DPSscale(ctxt, 1, -1);
378      [NSFont _setFontFlipHack: NO];
379    }
380}
381
382static void draw_in_rect(cache_t *c, NSRect rect)
383{
384  NSRange r;
385  BOOL need_flip = ![[NSView focusView] isFlipped];
386  BOOL need_clip = NO;
387  NSGraphicsContext *ctxt = GSCurrentContext();
388
389  /*
390    If the used rect fits completely in the rect we draw in, we save time
391    by avoiding the DPSrectclip (and the state save and restore).
392
393    This isn't completely safe; the used rect isn't guaranteed to contain
394    all parts of all glyphs.
395  */
396  if (c->usedRect.origin.x >= 0 && c->usedRect.origin.y <= 0
397      && NSMaxX(c->usedRect) <= rect.size.width
398      && NSMaxY(c->usedRect) <= rect.size.height)
399    {
400      need_clip = NO;
401    }
402  else
403    {
404      need_clip = YES;
405      DPSgsave(ctxt);
406      DPSrectclip(ctxt, rect.origin.x, rect.origin.y,
407                  rect.size.width, rect.size.height);
408    }
409
410  r = [c->layoutManager
411          glyphRangeForBoundingRect: NSMakeRect(0, 0, rect.size.width,
412                                                rect.size.height)
413          inTextContainer: c->textContainer];
414
415  if (need_flip)
416    {
417      DPSscale(ctxt, 1, -1);
418      rect.origin.y = -NSMaxY(rect);
419      [NSFont _setFontFlipHack: YES];
420    }
421
422  [c->layoutManager drawBackgroundForGlyphRange: r
423                                        atPoint: rect.origin];
424  [c->layoutManager drawGlyphsForGlyphRange: r
425                                    atPoint: rect.origin];
426
427  if (need_flip)
428    {
429      DPSscale(ctxt, 1, -1);
430      [NSFont _setFontFlipHack: NO];
431    }
432
433  if (need_clip)
434    {
435      /* Restore the original clipping path. */
436      DPSgrestore(ctxt);
437    }
438}
439
440@implementation NSAttributedString (NSStringDrawing)
441
442- (void) drawAtPoint: (NSPoint)point
443{
444  cache_t *c;
445
446  cache_lock();
447  NS_DURING
448    {
449      prepare_attributed_string(self);
450      c = cache_lookup(NO, NSZeroSize, use_screen_fonts());
451
452      draw_at_point(c, point);
453    }
454  NS_HANDLER
455    {
456      cache_unlock();
457      [localException raise];
458    }
459  NS_ENDHANDLER;
460  cache_unlock();
461}
462
463- (void) drawInRect: (NSRect)rect
464{
465  [self drawWithRect: rect
466             options: NSStringDrawingUsesLineFragmentOrigin];
467}
468
469- (void) drawWithRect: (NSRect)rect
470              options: (NSStringDrawingOptions)options
471{
472  // FIXME: This ignores options
473  cache_t *c;
474
475  if (rect.size.width <= 0 || rect.size.height <= 0)
476    return;
477
478  cache_lock();
479  NS_DURING
480    {
481      prepare_attributed_string(self);
482      c = cache_lookup(YES, rect.size, use_screen_fonts());
483      draw_in_rect(c, rect);
484    }
485  NS_HANDLER
486    {
487      cache_unlock();
488      [localException raise];
489    }
490  NS_ENDHANDLER;
491  cache_unlock();
492}
493
494- (NSSize) size
495{
496  NSRect usedRect = [self boundingRectWithSize: NSZeroSize
497                                       options: NSStringDrawingUsesLineFragmentOrigin];
498  return usedRect.size;
499}
500
501- (NSRect) boundingRectWithSize: (NSSize)size
502                        options: (NSStringDrawingOptions)options
503{
504  // FIXME: This ignores options
505  cache_t *c;
506  NSRect result = NSZeroRect;
507  BOOL hasSize = !NSEqualSizes(NSZeroSize, size);
508
509  cache_lock();
510  NS_DURING
511    {
512      prepare_attributed_string(self);
513      c = cache_lookup(hasSize, size, YES);
514      result = c->usedRect;
515    }
516  NS_HANDLER
517    {
518      cache_unlock();
519      [localException raise];
520    }
521  NS_ENDHANDLER;
522  cache_unlock();
523
524  return result;
525}
526
527@end
528
529
530@implementation NSString (NSStringDrawing)
531
532- (void) drawAtPoint: (NSPoint)point withAttributes: (NSDictionary *)attrs
533{
534  cache_t *c;
535
536  cache_lock();
537  NS_DURING
538    {
539      prepare_string(self, attrs);
540      c = cache_lookup(NO, NSZeroSize, use_screen_fonts());
541      draw_at_point(c, point);
542    }
543  NS_HANDLER
544    {
545      cache_unlock();
546      [localException raise];
547    }
548  NS_ENDHANDLER;
549  cache_unlock();
550}
551
552- (void) drawInRect: (NSRect)rect withAttributes: (NSDictionary *)attrs
553{
554  [self drawWithRect: rect
555             options: NSStringDrawingUsesLineFragmentOrigin
556          attributes: attrs];
557}
558
559- (void) drawWithRect: (NSRect)rect
560              options: (NSStringDrawingOptions)options
561           attributes: (NSDictionary *)attrs
562{
563  // FIXME: This ignores options
564  cache_t *c;
565
566  if (rect.size.width <= 0 || rect.size.height <= 0)
567    return;
568
569  cache_lock();
570  NS_DURING
571    {
572      prepare_string(self, attrs);
573      c = cache_lookup(YES, rect.size, use_screen_fonts());
574      draw_in_rect(c, rect);
575    }
576  NS_HANDLER
577    {
578      cache_unlock();
579      [localException raise];
580    }
581  NS_ENDHANDLER;
582  cache_unlock();
583}
584
585- (NSSize) sizeWithAttributes: (NSDictionary *)attrs
586{
587  NSRect usedRect = [self boundingRectWithSize: NSZeroSize
588                                       options: NSStringDrawingUsesLineFragmentOrigin
589                                    attributes: attrs];
590  return usedRect.size;
591}
592
593- (NSRect) boundingRectWithSize: (NSSize)size
594                        options: (NSStringDrawingOptions)options
595                     attributes: (NSDictionary *)attrs
596{
597  // FIXME: This ignores options
598  cache_t *c;
599  NSRect result = NSZeroRect;
600  BOOL hasSize = !NSEqualSizes(NSZeroSize, size);
601
602  cache_lock();
603  NS_DURING
604    {
605      prepare_string(self, attrs);
606      c = cache_lookup(hasSize, size, YES);
607      result = c->usedRect;
608    }
609  NS_HANDLER
610    {
611      cache_unlock();
612      [localException raise];
613    }
614  NS_ENDHANDLER;
615  cache_unlock();
616
617  return result;
618}
619
620@end
621
622
623/*
624Dummy function; see comment in NSApplication.m, +initialize.
625*/
626void GSStringDrawingDummyFunction(void)
627{
628}
629
630