1/*
2   GSTextStorage.m
3
4   Implementation of concrete subclass of a string class with attributes
5
6   Copyright (C) 1999 Free Software Foundation, Inc.
7
8   Based on code by: ANOQ of the sun <anoq@vip.cybercity.dk>
9   Written by: Richard Frith-Macdonald <richard@brainstorm.co.uk>
10   Date: July 1999
11
12   This file is part of the GNUstep GUI Library.
13
14   This library is free software; you can redistribute it and/or
15   modify it under the terms of the GNU Lesser General Public
16   License as published by the Free Software Foundation; either
17   version 2 of the License, or (at your option) any later version.
18
19   This library is distributed in the hope that it will be useful,
20   but WITHOUT ANY WARRANTY; without even the implied warranty of
21   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
22   Lesser General Public License for more details.
23
24   You should have received a copy of the GNU Lesser General Public
25   License along with this library; see the file COPYING.LIB.
26   If not, see <http://www.gnu.org/licenses/> or write to the
27   Free Software Foundation, 51 Franklin Street, Fifth Floor,
28   Boston, MA 02110-1301, USA.
29*/
30
31/* Warning -	[-initWithString:attributes:] is the designated initialiser,
32 *		but it doesn't provide any way to perform the function of the
33 *		[-initWithAttributedString:] initialiser.
34 *		In order to work youd this, the string argument of the
35 *		designated initialiser has been overloaded such that it
36 *		is expected to accept an NSAttributedString here instead of
37 *		a string.  If you create an NSAttributedString subclass, you
38 *		must make sure that your implementation of the initialiser
39 *		copes with either an NSString or an NSAttributedString.
40 *		If it receives an NSAttributedString, it should ignore the
41 *		attributes argument and use the values from the string.
42 */
43
44#import <Foundation/NSAttributedString.h>
45#import <Foundation/NSException.h>
46#import <Foundation/NSRange.h>
47#import <Foundation/NSArray.h>
48#import <Foundation/NSDebug.h>
49#import <Foundation/NSZone.h>
50#import <Foundation/NSLock.h>
51#import <Foundation/NSThread.h>
52#import <Foundation/NSProxy.h>
53#import <Foundation/NSInvocation.h>
54#import <Foundation/NSNotification.h>
55#import "AppKit/NSTextStorage.h"
56#import "GSTextStorage.h"
57
58#define		SANITY_CHECKS	0
59
60static BOOL     adding;
61
62/* When caching attributes we make a shallow copy of the dictionary cached,
63 * so that it is immutable and safe to cache.
64 * However, we have a potential problem if the objects within the attributes
65 * dictionary are themselves mutable, and something mutates them while they
66 * are in the cache.  In this case we could items added while different and
67 * then mutated to have the same contents, so we would not know which of
68 * the equal dictionaries to remove.
69 * The solution is to require dictionaries to be identical for removal.
70 */
71static inline BOOL
72cacheEqual(id A, id B)
73{
74  if (YES == adding)
75    return [A isEqualToDictionary: B];
76  else
77    return A == B;
78}
79
80#define	GSI_MAP_RETAIN_KEY(M, X)
81#define	GSI_MAP_RELEASE_KEY(M, X)
82#define	GSI_MAP_RETAIN_VAL(M, X)
83#define	GSI_MAP_RELEASE_VAL(M, X)
84#define	GSI_MAP_EQUAL(M, X,Y)	cacheEqual((X).obj, (Y).obj)
85#define GSI_MAP_KTYPES	GSUNION_OBJ
86#define GSI_MAP_VTYPES	GSUNION_NSINT
87#define	GSI_MAP_NOCLEAN	1
88#include <GNUstepBase/GSIMap.h>
89
90static NSDictionary	*blank;
91static NSLock		*attrLock = nil;
92static GSIMapTable_t	attrMap;
93static SEL		lockSel;
94static SEL		unlockSel;
95static IMP		lockImp;
96static IMP		unlockImp;
97
98#define	ALOCK()	if (attrLock != nil) (*lockImp)(attrLock, lockSel)
99#define	AUNLOCK() if (attrLock != nil) (*unlockImp)(attrLock, unlockSel)
100
101@interface GSTextStorageProxy : NSProxy
102{
103  NSString	*string;
104}
105- (id) _initWithString: (NSString*)s;
106@end
107
108@implementation	GSTextStorageProxy
109
110static Class NSObjectClass = nil;
111static Class NSStringClass = nil;
112
113+ (void) initialize
114{
115  NSObjectClass = [NSObject class];
116  NSStringClass = [NSString class];
117}
118
119- (Class) class
120{
121  return NSStringClass;
122}
123
124- (void) dealloc
125{
126  [string release];
127  [super dealloc];
128}
129
130- (void) forwardInvocation: (NSInvocation*)anInvocation
131{
132  SEL	aSel = [anInvocation selector];
133
134  if (YES == [NSStringClass instancesRespondToSelector: aSel])
135    {
136      [anInvocation invokeWithTarget: string];
137    }
138  else
139    {
140      [NSException raise: NSGenericException
141	          format: @"NSString(instance) does not recognize %s",
142	aSel ? GSNameFromSelector(aSel) : "(null)"];
143    }
144}
145
146- (NSUInteger) hash
147{
148  return [string hash];
149}
150
151- (id) _initWithString: (NSString*)s
152{
153  string = [s retain];
154  return self;
155}
156
157- (BOOL) isEqual: (id)other
158{
159  return [string isEqual: other];
160}
161
162- (BOOL) isMemberOfClass: (Class)c
163{
164  return (c == NSStringClass) ? YES : NO;
165}
166
167- (BOOL) isKindOfClass: (Class)c
168{
169  return (c == NSStringClass || c == NSObjectClass) ? YES : NO;
170}
171
172- (NSMethodSignature*) methodSignatureForSelector: (SEL)aSelector
173{
174  NSMethodSignature	*sig;
175
176  if (YES == [NSStringClass instancesRespondToSelector: aSelector])
177    {
178      sig = [string methodSignatureForSelector: aSelector];
179    }
180  else
181    {
182      sig = [super methodSignatureForSelector: aSelector];
183    }
184  return sig;
185}
186
187- (BOOL) respondsToSelector: (SEL)aSelector
188{
189  if (YES == [NSStringClass instancesRespondToSelector: aSelector])
190    {
191      return YES;
192    }
193  return [super respondsToSelector: aSelector];
194}
195
196@end
197
198/*
199 * Add a dictionary to the cache - if it was not already there, return
200 * the copy added to the cache, if it was, count it and return retained
201 * object that was there.
202 */
203static NSDictionary*
204cacheAttributes(NSDictionary *attrs)
205{
206  GSIMapNode	node;
207
208  ALOCK();
209  adding = YES;
210  node = GSIMapNodeForKey(&attrMap, (GSIMapKey)((id)attrs));
211  if (node == 0)
212    {
213      /*
214       * Shallow copy of dictionary, without copying objects ... results
215       * in an immutable dictionary that can safely be cached.
216       */
217      attrs = [[NSDictionary alloc] initWithDictionary: attrs copyItems: NO];
218      GSIMapAddPair(&attrMap,
219        (GSIMapKey)((id)attrs), (GSIMapVal)(NSUInteger)1);
220    }
221  else
222    {
223      node->value.nsu++;
224      attrs = RETAIN(node->key.obj);
225    }
226  AUNLOCK();
227  return attrs;
228}
229
230static void
231unCacheAttributes(NSDictionary *attrs)
232{
233  GSIMapBucket       bucket;
234
235  ALOCK();
236  adding = NO;
237  bucket = GSIMapBucketForKey(&attrMap, (GSIMapKey)((id)attrs));
238  if (bucket != 0)
239    {
240      GSIMapNode     node;
241
242      node = GSIMapNodeForKeyInBucket(&attrMap,
243        bucket, (GSIMapKey)((id)attrs));
244      if (node != 0)
245	{
246	  if (--node->value.nsu == 0)
247	    {
248	      GSIMapRemoveNodeFromMap(&attrMap, bucket, node);
249	      GSIMapFreeNode(&attrMap, node);
250	    }
251	}
252    }
253  AUNLOCK();
254}
255
256
257
258@interface	GSTextInfo : NSObject
259{
260@public
261  unsigned	loc;
262  NSDictionary	*attrs;
263}
264
265+ (GSTextInfo*) newWithZone: (NSZone*)z value: (NSDictionary*)a at: (unsigned)l;
266
267@end
268
269@implementation	GSTextInfo
270
271/*
272 * Called to record attributes at a particular location - the given attributes
273 * dictionary must have been produced by 'cacheAttributes()' so that it is
274 * already copied/retained and this method doesn't need to do it.
275 */
276+ (GSTextInfo*) newWithZone: (NSZone*)z value: (NSDictionary*)a at: (unsigned)l;
277{
278  GSTextInfo	*info = (GSTextInfo*)NSAllocateObject(self, 0, z);
279
280  info->loc = l;
281  info->attrs = a;
282  return info;
283}
284
285- (Class) classForPortCoder
286{
287  return [self class];
288}
289
290- (void) dealloc
291{
292  [self finalize];
293  [super dealloc];
294}
295
296- (NSString*) description
297{
298  return [NSString stringWithFormat: @"Attributes at %u are - %@",
299    loc, attrs];
300}
301
302- (void) encodeWithCoder: (NSCoder*)aCoder
303{
304  if ([aCoder allowsKeyedCoding] == NO)
305    {
306      [aCoder encodeValueOfObjCType: @encode(unsigned) at: &loc];
307      [aCoder encodeValueOfObjCType: @encode(id) at: &attrs];
308    }
309}
310
311- (void) finalize
312{
313  unCacheAttributes(attrs);
314  DESTROY(attrs);
315}
316
317- (id) initWithCoder: (NSCoder*)aCoder
318{
319  if ([aCoder allowsKeyedCoding] == NO)
320    {
321      NSDictionary	*a;
322      [aCoder decodeValueOfObjCType: @encode(unsigned) at: &loc];
323      a = [aCoder decodeObject];
324      attrs = cacheAttributes(a);
325    }
326  return self;
327}
328
329- (id) replacementObjectForPortCoder: (NSPortCoder*)aCoder
330{
331  return self;
332}
333
334@end
335
336
337
338static Class	infCls = 0;
339
340static SEL infSel;
341static SEL addSel;
342static SEL cntSel;
343static SEL insSel;
344static SEL oatSel;
345static SEL remSel;
346
347static IMP	infImp;
348static void	(*addImp)();
349static unsigned (*cntImp)();
350static void	(*insImp)();
351static IMP	oatImp;
352static void	(*remImp)();
353
354#define	NEWINFO(Z,O,L)	((*infImp)(infCls, infSel, (Z), (O), (L)))
355#define	ADDOBJECT(O)	((*addImp)(_infoArray, addSel, (O)))
356#define	INSOBJECT(O,I)	((*insImp)(_infoArray, insSel, (O), (I)))
357#define	OBJECTAT(I)	((*oatImp)(_infoArray, oatSel, (I)))
358#define	REMOVEAT(I)	((*remImp)(_infoArray, remSel, (I)))
359
360static inline NSDictionary *attrDict(GSTextInfo* info)
361{
362  return info->attrs;
363}
364
365
366static void _setup()
367{
368  if (infCls == 0)
369    {
370      NSMutableArray	*a;
371      NSDictionary	*d;
372
373      GSIMapInitWithZoneAndCapacity(&attrMap, NSDefaultMallocZone(), 32);
374
375      infSel = @selector(newWithZone:value:at:);
376      addSel = @selector(addObject:);
377      cntSel = @selector(count);
378      insSel = @selector(insertObject:atIndex:);
379      oatSel = @selector(objectAtIndex:);
380      remSel = @selector(removeObjectAtIndex:);
381
382      infCls = [GSTextInfo class];
383      infImp = [infCls methodForSelector: infSel];
384
385      a = [NSMutableArray allocWithZone: NSDefaultMallocZone()];
386      a = [a initWithCapacity: 1];
387      addImp = (void (*)())[a methodForSelector: addSel];
388      cntImp = (unsigned (*)())[a methodForSelector: cntSel];
389      insImp = (void (*)())[a methodForSelector: insSel];
390      oatImp = [a methodForSelector: oatSel];
391      remImp = (void (*)())[a methodForSelector: remSel];
392      RELEASE(a);
393
394      d = [NSDictionary new];
395      blank = cacheAttributes(d);
396      RELEASE(d);
397    }
398}
399
400static void
401_setAttributesFrom(
402  NSAttributedString *attributedString,
403  NSRange aRange,
404  NSMutableArray *_infoArray)
405{
406  NSZone	*z = [_infoArray zone];
407  NSRange	range;
408  NSDictionary	*attr;
409  GSTextInfo	*info;
410  unsigned	loc;
411
412  /*
413   * remove any old attributes of the string.
414   */
415  [_infoArray removeAllObjects];
416
417  if (aRange.length <= 0)
418    {
419      attr = blank;
420      range = aRange; /* Set to satisfy the loop condition below. */
421    }
422  else
423    {
424      attr = [attributedString attributesAtIndex: aRange.location
425				  effectiveRange: &range];
426    }
427  attr = cacheAttributes(attr);
428  info = NEWINFO(z, attr, 0);
429  ADDOBJECT(info);
430  RELEASE(info);
431
432  while ((loc = NSMaxRange(range)) < NSMaxRange(aRange))
433    {
434      attr = [attributedString attributesAtIndex: loc
435				  effectiveRange: &range];
436      attr = cacheAttributes(attr);
437      info = NEWINFO(z, attr, loc - aRange.location);
438      ADDOBJECT(info);
439      RELEASE(info);
440    }
441}
442
443inline static NSDictionary*
444_attributesAtIndexEffectiveRange(
445  unsigned int index,
446  NSRange *aRange,
447  unsigned int tmpLength,
448  NSMutableArray *_infoArray,
449  unsigned int *foundIndex)
450{
451  unsigned	low, high, used, cnt, nextLoc;
452  GSTextInfo	*found = nil;
453
454  used = (*cntImp)(_infoArray, cntSel);
455  NSCAssert(used > 0, NSInternalInconsistencyException);
456  high = used - 1;
457
458  if (index >= tmpLength)
459    {
460      if (index == tmpLength)
461	{
462	  found = OBJECTAT(high);
463	  if (foundIndex != 0)
464	    {
465	      *foundIndex = high;
466	    }
467	  if (aRange != 0)
468	    {
469	      aRange->location = found->loc;
470	      aRange->length = tmpLength - found->loc;
471	    }
472	  return attrDict(found);
473	}
474      [NSException raise: NSRangeException
475		  format: @"index is out of range in function "
476			  @"_attributesAtIndexEffectiveRange()"];
477    }
478
479  /*
480   * Binary search for efficiency in huge attributed strings
481   */
482  low = 0;
483  while (low <= high)
484    {
485      cnt = (low + high) / 2;
486      found = OBJECTAT(cnt);
487      if (found->loc > index)
488	{
489	  high = cnt - 1;
490	}
491      else
492	{
493	  if (cnt >= used - 1)
494	    {
495	      nextLoc = tmpLength;
496	    }
497	  else
498	    {
499	      GSTextInfo	*inf = OBJECTAT(cnt + 1);
500
501	      nextLoc = inf->loc;
502	    }
503	  if (found->loc == index || index < nextLoc)
504	    {
505	      //Found
506	      if (aRange != 0)
507		{
508		  aRange->location = found->loc;
509		  aRange->length = nextLoc - found->loc;
510		}
511	      if (foundIndex != 0)
512		{
513		  *foundIndex = cnt;
514		}
515	      return attrDict(found);
516	    }
517	  else
518	    {
519	      low = cnt + 1;
520	    }
521	}
522    }
523  NSCAssert(NO,@"Error in binary search algorithm");
524  return nil;
525}
526
527@implementation GSTextStorage
528
529#if	SANITY_CHECKS
530
531#define	SANITY()	[self sanity]
532#else
533#define	SANITY()
534#endif
535
536/* We always compile in this method so that it is available from
537 * regression test cases.  */
538- (void) _sanity
539{
540  GSTextInfo	*info;
541  unsigned	i;
542  unsigned	l = 0;
543  unsigned	len = [_textChars length];
544  unsigned	c = (*cntImp)(_infoArray, cntSel);
545
546  NSAssert(c > 0, NSInternalInconsistencyException);
547  info = OBJECTAT(0);
548  NSAssert(info->loc == 0, NSInternalInconsistencyException);
549  for (i = 1; i < c; i++)
550    {
551      info = OBJECTAT(i);
552      NSAssert(info->loc > l, NSInternalInconsistencyException);
553      NSAssert(info->loc < len, NSInternalInconsistencyException);
554      l = info->loc;
555    }
556}
557
558/*
559 * If we are multi-threaded, we must guard access to the uniquing set.
560 */
561+ (void) _becomeThreaded: (id)notification
562{
563  attrLock = [NSLock new];
564  lockSel = @selector(lock);
565  unlockSel = @selector(unlock);
566  lockImp = [attrLock methodForSelector: lockSel];
567  unlockImp = [attrLock methodForSelector: unlockSel];
568}
569
570+ (void) initialize
571{
572  _setup();
573
574  if ([NSThread isMultiThreaded])
575    {
576      [self _becomeThreaded: nil];
577    }
578  else
579    {
580      [[NSNotificationCenter defaultCenter]
581	addObserver: self
582	   selector: @selector(_becomeThreaded:)
583	       name: NSWillBecomeMultiThreadedNotification
584	     object: nil];
585    }
586}
587
588- (id) initWithCoder: (NSCoder*)aCoder
589{
590  self = [super initWithCoder: aCoder];
591  if([aCoder allowsKeyedCoding] == NO)
592    {
593      if ([aCoder versionForClassName: @"GSTextStorage"] != (NSInteger)NSNotFound)
594        {
595          NSLog(@"Warning - decoding archive containing obsolete %@ object - please delete/replace this archive", NSStringFromClass([self class]));
596          [aCoder decodeValueOfObjCType: @encode(id) at: &_textChars];
597          [aCoder decodeValueOfObjCType: @encode(id) at: &_infoArray];
598        }
599    }
600  return self;
601}
602
603- (id) initWithString: (NSString*)aString
604	   attributes: (NSDictionary*)attributes
605{
606  NSZone *z = [self zone];
607
608  self = [super initWithString: aString attributes: attributes];
609  _infoArray = [[NSMutableArray allocWithZone: z] initWithCapacity: 1];
610  if (aString != nil && [aString isKindOfClass: [NSAttributedString class]])
611    {
612      NSAttributedString *as = (NSAttributedString*)aString;
613
614      aString = [as string];
615      _setAttributesFrom(as, NSMakeRange(0, [aString length]), _infoArray);
616    }
617  else
618    {
619      GSTextInfo *info;
620
621      if (attributes == nil)
622        {
623          attributes = blank;
624        }
625      attributes = cacheAttributes(attributes);
626      info = NEWINFO(z, attributes, 0);
627      ADDOBJECT(info);
628      RELEASE(info);
629    }
630  if (aString == nil)
631    _textChars = [[NSMutableString allocWithZone: z] init];
632  else
633    _textChars = [aString mutableCopyWithZone: z];
634  return self;
635}
636
637- (NSString*) string
638{
639  /* NB. This method is SUPPOSED to return a proxy to the mutable string!
640   * This is a performance feature documented ifor OSX.
641   */
642  if (_textProxy == nil)
643    {
644      _textProxy = [[_textChars immutableProxy] retain];
645    }
646  return _textProxy;
647}
648
649- (NSDictionary*) attributesAtIndex: (NSUInteger)index
650		     effectiveRange: (NSRange*)aRange
651{
652  unsigned dummy;
653
654  return _attributesAtIndexEffectiveRange(
655    index, aRange, [_textChars length], _infoArray, &dummy);
656}
657
658/*
659 *	Primitive method! Sets attributes and values for a given range of
660 *	characters, replacing any previous attributes and values for that
661 *	range.
662 *
663 *	Sets the attributes for the characters in aRange to attributes.
664 *	These new attributes replace any attributes previously associated
665 *	with the characters in aRange. Raises an NSRangeException if any
666 *	part of aRange lies beyond the end of the receiver's characters.
667 *	See also: - addAtributes: range: , - removeAttributes: range:
668 */
669- (void) setAttributes: (NSDictionary*)attributes
670		 range: (NSRange)range
671{
672  unsigned	tmpLength;
673  unsigned      arrayIndex = 0;
674  unsigned      arraySize;
675  NSRange	effectiveRange = NSMakeRange(0, NSNotFound);
676  NSRange	originalRange = range;
677  unsigned	afterRangeLoc, beginRangeLoc;
678  NSDictionary	*attrs;
679  NSZone	*z = [self zone];
680  GSTextInfo	*info;
681
682  if (range.length == 0)
683    {
684      NSWarnMLog(@"Attempt to set attribute for zero-length range");
685      return;
686    }
687  if (attributes == nil)
688    {
689      attributes = blank;
690    }
691  attributes = cacheAttributes(attributes);
692SANITY();
693  tmpLength = [_textChars length];
694  GS_RANGE_CHECK(range, tmpLength);
695  arraySize = (*cntImp)(_infoArray, cntSel);
696  beginRangeLoc = range.location;
697  afterRangeLoc = NSMaxRange(range);
698  if (afterRangeLoc < tmpLength)
699    {
700      /*
701       * Locate the first range that extends beyond our range.
702       */
703      attrs = _attributesAtIndexEffectiveRange(
704	afterRangeLoc, &effectiveRange, tmpLength, _infoArray, &arrayIndex);
705      if (attrs == attributes)
706	{
707	  /*
708	   * The located range has the same attributes as us - so we can
709	   * extend our range to include it.
710	   */
711	  if (effectiveRange.location < beginRangeLoc)
712	    {
713	      range.length += beginRangeLoc - effectiveRange.location;
714	      range.location = effectiveRange.location;
715	      beginRangeLoc = range.location;
716	    }
717	  if (NSMaxRange(effectiveRange) > afterRangeLoc)
718	    {
719	      range.length = NSMaxRange(effectiveRange) - range.location;
720	    }
721	}
722      else if (effectiveRange.location > beginRangeLoc)
723	{
724	  /*
725	   * The located range also starts at or after our range.
726	   */
727	  info = OBJECTAT(arrayIndex);
728	  info->loc = afterRangeLoc;
729	  arrayIndex--;
730	}
731      else if (NSMaxRange(effectiveRange) > afterRangeLoc)
732	{
733	  /*
734	   * The located range starts before our range.
735	   * Create a subrange to go from our end to the end of the old range.
736	   */
737	  info = NEWINFO(z, cacheAttributes(attrs), afterRangeLoc);
738	  arrayIndex++;
739	  INSOBJECT(info, arrayIndex);
740	  RELEASE(info);
741	  arrayIndex--;
742	}
743    }
744  else
745    {
746      arrayIndex = arraySize - 1;
747    }
748
749  /*
750   * Remove any ranges completely within ours
751   */
752  while (arrayIndex > 0)
753    {
754      info = OBJECTAT(arrayIndex-1);
755      if (info->loc < beginRangeLoc)
756	break;
757      REMOVEAT(arrayIndex);
758      arrayIndex--;
759    }
760
761  /*
762   * Use the location/attribute info in the current slot if possible,
763   * otherwise, add a new slot and use that.
764   */
765  info = OBJECTAT(arrayIndex);
766  if (info->loc >= beginRangeLoc)
767    {
768      info->loc = beginRangeLoc;
769      if (info->attrs == attributes)
770	{
771	  unCacheAttributes(attributes);
772	  RELEASE(attributes);
773	}
774      else
775	{
776	  unCacheAttributes(info->attrs);
777	  RELEASE(info->attrs);
778	  info->attrs = attributes;
779	}
780    }
781  else if (info->attrs == attributes)
782    {
783      unCacheAttributes(attributes);
784      RELEASE(attributes);
785    }
786  else
787    {
788      arrayIndex++;
789      info = NEWINFO(z, attributes, beginRangeLoc);
790      INSOBJECT(info, arrayIndex);
791      RELEASE(info);
792    }
793
794SANITY();
795  [self edited: NSTextStorageEditedAttributes
796	 range: originalRange
797changeInLength: 0];
798}
799
800- (void) replaceCharactersInRange: (NSRange)range
801		       withString: (NSString*)aString
802{
803  unsigned	tmpLength;
804  unsigned      arrayIndex = 0;
805  unsigned      arraySize;
806  NSRange	effectiveRange = NSMakeRange(0, NSNotFound);
807  GSTextInfo	*info;
808  int		moveLocations;
809  unsigned	start;
810
811SANITY();
812  if (aString == nil)
813    {
814      aString = @"";
815    }
816  tmpLength = [_textChars length];
817  GS_RANGE_CHECK(range, tmpLength);
818  if (range.location == tmpLength)
819    {
820      /*
821       * Special case - replacing a zero length string at the end
822       * simply appends the new string and attributes are inherited.
823       */
824      [_textChars appendString: aString];
825      goto finish;
826    }
827
828  arraySize = (*cntImp)(_infoArray, cntSel);
829  if (arraySize == 1)
830    {
831      /*
832       * Special case - if the string has only one set of attributes
833       * then the replacement characters will get them too.
834       */
835      [_textChars replaceCharactersInRange: range withString: aString];
836      goto finish;
837    }
838
839  /*
840   * Get the attributes to associate with our replacement string.
841   * Should be those of the first character replaced.
842   * If the range replaced is empty, we use the attributes of the
843   * previous character (if possible).
844   */
845  if (range.length == 0 && range.location > 0)
846    start = range.location - 1;
847  else
848    start = range.location;
849  _attributesAtIndexEffectiveRange(start, &effectiveRange,
850                                   tmpLength, _infoArray, &arrayIndex);
851
852  moveLocations = [aString length] - range.length;
853
854  arrayIndex++;
855  if (NSMaxRange(effectiveRange) < NSMaxRange(range))
856    {
857      /*
858       * Remove all range info for ranges enclosed within the one
859       * we are replacing.  Adjust the start point of a range that
860       * extends beyond ours.
861       */
862      info = OBJECTAT(arrayIndex);
863      if (info->loc < NSMaxRange(range))
864	{
865	  unsigned int	next = arrayIndex + 1;
866
867	  while (next < arraySize)
868	    {
869	      GSTextInfo	*n = OBJECTAT(next);
870	      if (n->loc <= NSMaxRange(range))
871		{
872		  REMOVEAT(arrayIndex);
873		  arraySize--;
874		  info = n;
875		}
876	      else
877		{
878		  break;
879		}
880	    }
881	}
882      if (NSMaxRange(range) < [_textChars length])
883	{
884	  info->loc = NSMaxRange(range);
885	}
886      else
887	{
888	  REMOVEAT(arrayIndex);
889	  arraySize--;
890	}
891    }
892
893  /*
894   * If we are replacing a range with a zero length string and the
895   * range we are using matches the range replaced, then we must
896   * remove it from the array to avoid getting a zero length range.
897   */
898  if ((moveLocations + range.length) == 0)
899    {
900      _attributesAtIndexEffectiveRange(start, &effectiveRange,
901                                       tmpLength, _infoArray, &arrayIndex);
902      arrayIndex++;
903
904      if (effectiveRange.location == range.location
905	&& effectiveRange.length == range.length)
906	{
907	  arrayIndex--;
908	  if (arrayIndex != 0 || arraySize > 1)
909	    {
910	      REMOVEAT(arrayIndex);
911	      arraySize--;
912	    }
913	  else
914	    {
915	      NSDictionary	*d = blank;
916
917	      info = OBJECTAT(0);
918	      unCacheAttributes(info->attrs);
919	      DESTROY(info->attrs);
920	      d = cacheAttributes(d);
921	      info->attrs = d;
922	      info->loc = NSMaxRange(range);
923	    }
924	}
925    }
926
927  /*
928   * Now adjust the positions of the ranges following the one we are using.
929   */
930  while (arrayIndex < arraySize)
931    {
932      info = OBJECTAT(arrayIndex);
933      info->loc += moveLocations;
934      arrayIndex++;
935    }
936  [_textChars replaceCharactersInRange: range withString: aString];
937
938finish:
939SANITY();
940  [self edited: NSTextStorageEditedCharacters
941         range: range
942changeInLength: [aString length] - range.length];
943}
944
945- (void) dealloc
946{
947  RELEASE(_textChars);
948  RELEASE(_infoArray);
949  RELEASE(_textProxy);
950  [super dealloc];
951}
952
953// The superclass implementation is correct but too slow
954- (NSUInteger) length
955{
956  return [_textChars length];
957}
958@end
959