/*
   GSHorizontalTypesetter.h

   Copyright (C) 2002 Free Software Foundation, Inc.

   Author: Alexander Malmberg <[email protected]>
   Date: 2002

   This file is part of the GNUstep GUI Library.

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.

   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with this library; see the file COPYING.LIB.
   If not, see <http://www.gnu.org/licenses/ > or write to the
   Free Software Foundation, 51 Franklin Street, Fifth Floor,
   Boston, MA 02110-1301, USA.
*/

#ifndef _GNUstep_H_GSHorizontalTypesetter
#define _GNUstep_H_GSHorizontalTypesetter

#import <GNUstepGUI/GSTypesetter.h>

@class NSLock;
@class GSLayoutManager, NSTextContainer, NSTextStorage;
@class NSDictionary;
@class NSParagraphStyle, NSFont;

APPKIT_EXPORT_CLASS
@interface GSHorizontalTypesetter : GSTypesetter
{
  /* Reentrancy lock - since this is a shared singleton, we need to handle
     recursive calls (e.g., if layout is triggered during existing layout) */
  NSLock *lock;

  /* Current layout context - these are set at the start of layoutGlyphsInLayoutManager:
     and remain valid for the duration of the layout operation */
  GSLayoutManager *currentLayoutManager;
  NSTextContainer *currentTextContainer;
  NSTextStorage *currentTextStorage;

  /* Current position in the glyph stream and the current drawing point
     (y-coordinate tracks the top of the current line being laid out) */
  unsigned int currentGlyphIndex;
  NSPoint currentPoint;

  /* Paragraph style caching: currentParagraphStyle is valid for paragraphRange.
     This avoids repeated attribute lookups for paragraph-level formatting. */
  NSParagraphStyle *currentParagraphStyle;
  NSRange paragraphRange; /* character indices, not glyph indices */

  /* Character attributes caching: currentAttributes is valid for attributeRange.
     This caches kern, baselineOffset, and superscript attributes. */
  NSDictionary *currentAttributes;
  NSRange attributeRange; /* character indices */
  struct
    {
      BOOL explicitKern;    /* YES if NSKernAttributeName was explicitly set */
      float kern;           /* Kerning adjustment value */
      float baselineOffset; /* Vertical offset from baseline (positive = up in user coords, down in flipped coords) */
      int superscript;      /* Superscript level (positive=super, negative=sub) */
    } attributes;

  /* Font caching: currentFont is valid for fontRange to avoid repeated font lookups */
  NSFont *currentFont;
  NSRange fontRange; /* glyph indices, unlike the ranges above which are character indices */

  /* Glyph cache: a growable array of GlyphCacheEntry structures.
     This caches glyph information to avoid repeated calls to the layout manager
     during the layout process. */
  struct GSHorizontalTypesetterGlyphCacheStruct *glyphCache;
  
  /* cacheBase: index (in the layout manager) of the first glyph stored in glyphCache[0]
     cacheSize: allocated capacity of the glyphCache array
     cacheLength: number of valid entries currently in the cache (from cacheBase) */
  unsigned int cacheBase, cacheSize, cacheLength;
  
  /* atEnd: set to YES when we've cached all available glyphs (reached end of text) */
  BOOL atEnd;

  /* Line fragment tracking: array of LineFragment structures representing
     the rectangular areas available for the current line of text.
     These are obtained from the text container and may represent multiple
     rectangles if the text flows around shapes (exclusion paths). */
  struct GSHorizontalTypesetterLineFragmentStruct *lineFragments;
  int lineFragmentCount;     /* Number of valid entries in lineFragments */
  int lineFragmentCapacity;  /* Allocated size of lineFragments array */
}

/* Returns the per-thread shared instance. Each thread gets its own instance
   to avoid locking contention, stored in the thread's dictionary. */
+(GSHorizontalTypesetter *) sharedInstance;

@end

#endif

/*
   GSHorizontalTypesetter.m

   Copyright (C) 2002, 2003 Free Software Foundation, Inc.

   Author: Alexander Malmberg <[email protected]>
   Date: November 2002 - February 2003

   This file is part of the GNUstep GUI Library.

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.

   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with this library; see the file COPYING.LIB.
   If not, see <http://www.gnu.org/licenses/> or write to the
   Free Software Foundation, 51 Franklin Street, Fifth Floor,
   Boston, MA 02110-1301, USA.
*/


#include <math.h>

#import <Foundation/NSDebug.h>
#import <Foundation/NSException.h>
#import <Foundation/NSGeometry.h>
#import <Foundation/NSLock.h>
#import <Foundation/NSThread.h>
#import <Foundation/NSValue.h>

#import "AppKit/NSAttributedString.h"
#import "AppKit/NSParagraphStyle.h"
#import "AppKit/NSTextAttachment.h"
#import "AppKit/NSTextContainer.h"
#import "AppKit/NSTextStorage.h"
#import "GNUstepGUI/GSLayoutManager.h"
#import "GNUstepGUI/GSHorizontalTypesetter.h"



/*
Note that unless the user creates extra instances, there will only be one
instance of GSHorizontalTypesetter for all text typesetting, so we can
cache fairly aggressively without having to worry about memory consumption.
*/


@implementation GSHorizontalTypesetter

- init
{
  if (!(self = [super init])) return nil;
  lock = [[NSLock alloc] init];
  return self;
}

-(void) dealloc
{
  if (glyphCache)
    {
      free(glyphCache);
      glyphCache = NULL;
    }
  if (lineFragments)
    {
      free(lineFragments);
      lineFragments = NULL;
    }
  DESTROY(lock);
  [super dealloc];
}

+(GSHorizontalTypesetter *) sharedInstance
{
  NSMutableDictionary *threadDict =
    [[NSThread currentThread] threadDictionary];
  GSHorizontalTypesetter *shared =
    [threadDict objectForKey: @"sharedHorizontalTypesetter"];

  if (!shared)
    {
      shared = [[self alloc] init];
      [threadDict setObject: shared
                     forKey: @"sharedHorizontalTypesetter"];
      RELEASE(shared);
    }

  return shared;
}

#define CACHE_INITIAL 192
#define CACHE_STEP 192


/* 
   GlyphCacheEntry stores all information needed to position and render a single glyph.
   This structure is filled in two phases:
   1. Caching phase (_cacheGlyphsUpToLength:): fills glyph, characterIndex, font, and attributes
   2. Layout phase (_baseLayoutBlock...): fills position, size, dontShow, outsideLineFragment, nominal
   
   Note on coordinates: The position is relative to the line's baseline. In the standard
   flipped AppKit coordinate system (origin at top-left, y increasing downward), the baseline
   is positioned at 'lineHeight - descender' from the top of the line fragment rect.
   Thus, a glyph's final y-coordinate = lineFragmentTop + baseline + glyphEntry->position.y
*/
struct GSHorizontalTypesetterGlyphCacheStruct
{
  /* Filled during caching phase: */
  NSGlyph glyph;                /* The glyph index (NSGlyph is an unsigned int) */
  unsigned int characterIndex;  /* Corresponding character index in text storage */

  NSFont *font;                 /* Font to use for this glyph */
  struct
    {
      BOOL explicitKern;
      float kern;
      float baselineOffset;
      int superscript;
    } attributes;               /* Copy of relevant text attributes */

  /* Filled during layout phase: */
  BOOL nominal;                 /* YES if glyph is at its "nominal" (standard) position 
                                   relative to previous glyph. Used to determine if we need 
                                   to record a specific location for the glyph run. */
  NSPoint position;             /* Position relative to the line's baseline. 
                                   x = horizontal offset from line start
                                   y = vertical offset from baseline (up=negative in flipped coords) */
  NSSize size;                  /* Advancement (width) of glyph. Height used only for attachments. */
  BOOL dontShow;                /* YES for control characters (space, tab, newline) that have 
                                   visual representation in the glyph stream but shouldn't render */
  BOOL outsideLineFragment;     /* YES if glyph extends beyond line fragment bounds (for clipping modes) */
};
typedef struct GSHorizontalTypesetterGlyphCacheStruct GlyphCacheEntry;

/* TODO: if we could know whether the layout manager had been modified since
   the last time or not, we wouldn't need to clear the cache every time */
-(void) _clearCache
{
  cacheLength = 0;

  currentParagraphStyle = nil;
  paragraphRange = NSMakeRange(0, 0);
  currentAttributes = nil;
  attributeRange = NSMakeRange(0, 0);
  currentFont = nil;
  fontRange = NSMakeRange(0, 0);
}

/* 
   Caches text attributes (kern, baselineOffset, superscript) for the character at the given index.
   Uses attributeRange to avoid redundant dictionary lookups. This method updates both
   currentAttributes (the dictionary) and the attributes struct (extracted values).
*/
-(void) _cacheAttributesAtCharacterIndex: (unsigned int)characterIndex
{
  NSNumber *numberValue;

  if (NSLocationInRange(characterIndex, attributeRange))
    {
      return;
    }
  
  currentAttributes = [currentTextStorage attributesAtIndex: characterIndex
                                             effectiveRange: &attributeRange];

  numberValue = [currentAttributes objectForKey: NSKernAttributeName];
  if (!numberValue)
    attributes.explicitKern = NO;
  else
    {
      attributes.explicitKern = YES;
      attributes.kern = [numberValue floatValue];
    }

  numberValue = [currentAttributes objectForKey: NSBaselineOffsetAttributeName];
  if (numberValue)
    attributes.baselineOffset = [numberValue floatValue];
  else
    attributes.baselineOffset = 0.0;

  numberValue = [currentAttributes objectForKey: NSSuperscriptAttributeName];
  if (numberValue)
    attributes.superscript = [numberValue intValue];
  else
    attributes.superscript = 0;
}

/* 
   Repositions the cache window to start at the specified glyph index.
   If the requested index is already within the current cache window, this efficiently
   shifts the existing data to the front of the buffer (memmove).
   
   If the index is outside the current cache, this resets the cache and looks up
   the paragraph style, attributes, and font for the new position.
*/
-(void) _moveCacheToGlyph: (unsigned int)glyphIndex
{
  BOOL valid;

  /* Case 1: Requested glyph is already in our cache window */
  if (cacheBase <= glyphIndex && cacheBase + cacheLength > glyphIndex)
    {
      int delta = glyphIndex - cacheBase;
      cacheLength -= delta;
      /* Shift remaining entries to the start of the buffer */
      memmove(glyphCache, &glyphCache[delta], sizeof(GlyphCacheEntry) * cacheLength);
      cacheBase = glyphIndex;
      return;
    }

  /* Case 2: New position - reset cache and look up context */
  cacheBase = glyphIndex;
  cacheLength = 0;

  [currentLayoutManager glyphAtIndex: glyphIndex
                        isValidIndex: &valid];

  if (valid)
    {
      unsigned int charIndex;

      atEnd = NO;
      charIndex = [currentLayoutManager characterIndexForGlyphAtIndex: glyphIndex];
      [self _cacheAttributesAtCharacterIndex: charIndex];

      /* Look up paragraph style - this affects indentation, tab stops, alignment, etc. */
      paragraphRange = NSMakeRange(charIndex, [currentTextStorage length] - charIndex);
      currentParagraphStyle = [currentTextStorage attribute: NSParagraphStyleAttributeName
                                                    atIndex: charIndex
                                      longestEffectiveRange: &paragraphRange
                                                    inRange: paragraphRange];
      if (currentParagraphStyle == nil)
        {
          currentParagraphStyle = [NSParagraphStyle defaultParagraphStyle];
        }

      currentFont = [currentLayoutManager effectiveFontForGlyphAtIndex: glyphIndex
                                                                 range: &fontRange];
    }
  else
    {
      /* No valid glyph at this index - we've reached the end of text */
      atEnd = YES;
    }
}

/* 
   Ensures the cache contains at least newLength entries starting from cacheBase.
   This method fills in glyphCache[cacheLength] through glyphCache[newLength-1] with
   glyph information from the layout manager.
   
   The method stops early if:
   - We run out of glyphs (atEnd = YES)
   - We reach the end of the current paragraph (paragraph separator)
*/
-(void) _cacheGlyphsUpToLength: (unsigned int)newLength
{
  GlyphCacheEntry *glyphEntry;
  BOOL valid;

  /* Grow buffer if necessary */
  if (cacheSize < newLength)
    {
      cacheSize = newLength;
      glyphCache = realloc(glyphCache, sizeof(GlyphCacheEntry) * cacheSize);
    }

  /* Fill in entries from current end of cache up to requested length */
  for (glyphEntry = &glyphCache[cacheLength]; cacheLength < newLength; cacheLength++, glyphEntry++)
    {
      glyphEntry->glyph = [currentLayoutManager glyphAtIndex: cacheBase + cacheLength
                                                isValidIndex: &valid];
      if (!valid)
        {
          atEnd = YES;
          break;
        }
      glyphEntry->characterIndex = [currentLayoutManager characterIndexForGlyphAtIndex: cacheBase + cacheLength];
      
      /* Stop if we've moved to the next paragraph (hit paragraph separator) */
      if (glyphEntry->characterIndex >= paragraphRange.location + paragraphRange.length)
        {
          atEnd = YES;
          break;
        }

      /* Cache attributes if we've moved past the current attribute range */
      if (glyphEntry->characterIndex >= attributeRange.location + attributeRange.length)
        {
          [self _cacheAttributesAtCharacterIndex: glyphEntry->characterIndex];
        }

      /* Copy cached attributes into the glyph entry */
      glyphEntry->attributes.explicitKern = attributes.explicitKern;
      glyphEntry->attributes.kern = attributes.kern;
      glyphEntry->attributes.baselineOffset = attributes.baselineOffset;
      glyphEntry->attributes.superscript = attributes.superscript;

      /* Update font if we've moved past the current font range */
      if (cacheBase + cacheLength >= fontRange.location + fontRange.length)
        {
          currentFont = [currentLayoutManager effectiveFontForGlyphAtIndex: cacheBase + cacheLength
                                                                     range: &fontRange];
        }
      glyphEntry->font = currentFont;

      /* Initialize layout-related fields */
      glyphEntry->dontShow = NO;
      glyphEntry->outsideLineFragment = NO;
      glyphEntry->nominal = YES;

      /* Get the advancement (width) of this glyph */
      // FIXME: This assumes the layout manager implements this GNUstep extension
      glyphEntry->size = [currentLayoutManager advancementForGlyphAtIndex: cacheBase + cacheLength];
    }
}


/*
   Performs word wrapping by searching backward from glyphIndex for a valid line break point.
   Valid break points are:
   - Whitespace characters (space, newline, carriage return, tab)
   - CJK characters (treated as word boundaries)
   - Control glyphs
   
   Returns the glyph index of the first glyph on the next line (the glyph after the break).
   
   IMPORTANT: This method assumes glyphCache contains entries up to glyphIndex.
   It marks whitespace characters with dontShow=YES so they don't render at line ends.
   
   Note: The return value is a glyph index in the layout manager's coordinate space,
   not relative to cacheBase.
*/
-(unsigned int) breakLineByWordWrappingBefore: (unsigned int)glyphIndex
{
  GlyphCacheEntry *glyphEntry;
  unichar character;
  NSString *string = [currentTextStorage string];

  /* Convert to cache-relative index */
  glyphIndex -= cacheBase;
  glyphEntry = glyphCache + glyphIndex;

  while (glyphIndex > 0)
    {
      if (glyphEntry->glyph == NSControlGlyph)
        return glyphIndex + cacheBase;

      character = [string characterAtIndex: glyphEntry->characterIndex];
      /* TODO: paragraph/line separator */
      if (character == 0x20 || // space
          character == 0x0a || // new line
          character == 0x0d || // carriage return
          character == 0x09)   // horiz. tab
        {
          /* Mark the whitespace as "don't show" - it provides spacing but no visual */
          glyphEntry->dontShow = YES;
          /* Position it after the previous glyph for proper caret positioning */
          if (glyphIndex > 0)
            {
              glyphEntry->position = glyphEntry[-1].position;
              glyphEntry->position.x += glyphEntry[-1].size.width;
            }
          else
            glyphEntry->position = NSMakePoint(0, 0);

          glyphEntry->size.width = 0;
          /* Return the glyph AFTER the whitespace (start of next line) */
          return glyphIndex + 1 + cacheBase;
        }
      /* Each CJK glyph should be treated as a word when wrapping word.
         The range should work for most cases */
      else if ((character > 0x2ff0) && (character < 0x9fff))
         {
           glyphEntry->dontShow = NO;
           if (glyphIndex > 0)
             {
               glyphEntry->position = glyphEntry[-1].position;
               glyphEntry->position.x += glyphEntry[-1].size.width;
             }
           else
             glyphEntry->position = NSMakePoint(0,0);

           return glyphIndex + cacheBase;
         }

      glyphIndex--;
      glyphEntry--;
    }

  return glyphIndex + cacheBase;
}


/* 
   LineFragment tracks the geometry of a rectangular area available for text.
   A single "line" of text may consist of multiple fragments if the text flows
   around non-rectangular exclusion paths or multiple columns.
*/
struct GSHorizontalTypesetterLineFragmentStruct
{
  NSRect rect;                /* The rectangle (in text container coordinates) */
  CGFloat lastUsed;           /* Rightmost x-coordinate actually used by glyphs */
  unsigned int lastGlyphIndex; /* One past the last glyph index in this fragment (cache-relative) */
};
typedef struct GSHorizontalTypesetterLineFragmentStruct LineFragment;

/*
Apple uses this as the maximum width of an NSTextContainer.
For bigger values the width gets ignored.
*/
#define LARGE_SIZE 1e7

/* 
   Distributes extra space across space characters to justify the line.
   Only modifies inter-word spacing; intra-word spacing remains unchanged.
   
   Algorithm:
   1. Count spaces in the line
   2. Calculate extraSpace = lineWidth - usedWidth
   3. Distribute extraSpace evenly across all spaces
   4. Adjust glyph positions cumulatively (delta accumulates across the line)
   
   Note: This processes multiple line fragments if the line wraps around shapes.
*/
-(void) fullJustifyLine: (LineFragment *)lineFragment : (int)numLineFragments
{
  unsigned int index, start;
  CGFloat extraSpace, delta;
  unsigned int numSpaces;
  NSString *string = [currentTextStorage string];
  GlyphCacheEntry *glyphEntry;
  unichar character;

  /* Don't attempt to justify lines that are effectively infinite (unwrapped) */
  if (lineFragment->rect.size.width >= LARGE_SIZE)
    {
      return;
    }

  for (start = 0; numLineFragments; numLineFragments--, lineFragment++)
    {
      numSpaces = 0;
      /* Count spaces in this fragment */
      for (index = start, glyphEntry = glyphCache + index; index < lineFragment->lastGlyphIndex; index++, glyphEntry++)
        {
          if (glyphEntry->dontShow)
            continue;

          character = [string characterAtIndex: glyphEntry->characterIndex];
          if (character == 0x20)
            numSpaces++;
        }
      if (!numSpaces)
        continue;

      /* Calculate per-space adjustment */
      extraSpace = lineFragment->rect.size.width - lineFragment->lastUsed;
      extraSpace /= numSpaces;
      delta = 0;
      
      /* Apply cumulative adjustments */
      for (index = start, glyphEntry = glyphCache + index; index < lineFragment->lastGlyphIndex; index++, glyphEntry++)
        {
          glyphEntry->position.x += delta;
          if (!glyphEntry->dontShow && [string characterAtIndex: glyphEntry->characterIndex] == 0x20)
            {
              /* Mark the following glyph as non-nominal since we adjusted spacing */
              if (index < lineFragment->lastGlyphIndex)
                glyphEntry[1].nominal = NO;

              delta += extraSpace;
            }
        }

      start = lineFragment->lastGlyphIndex;
      lineFragment->lastUsed = lineFragment->rect.size.width;
    }
}

/* 
   Shifts all glyphs right so the line is flush with the right margin.
   Calculates delta = lineWidth - usedWidth and adds it to all x positions.
*/
-(void) rightAlignLine: (LineFragment *)lineFragment : (int)numLineFragments
{
  unsigned int index;
  CGFloat delta;
  GlyphCacheEntry *glyphEntry;

  if (lineFragment->rect.size.width >= LARGE_SIZE)
    {
      return;
    }

  for (index = 0, glyphEntry = glyphCache; numLineFragments; numLineFragments--, lineFragment++)
    {
      delta = lineFragment->rect.size.width - lineFragment->lastUsed;
      for (; index < lineFragment->lastGlyphIndex; index++, glyphEntry++)
        glyphEntry->position.x += delta;

      lineFragment->lastUsed += delta;
    }
}

/* 
   Centers the line by adding half the remaining space to all glyph positions.
   delta = (lineWidth - usedWidth) / 2.0
*/
-(void) centerAlignLine: (LineFragment *)lineFragment : (int)numLineFragments
{
  unsigned int index;
  CGFloat delta;
  GlyphCacheEntry *glyphEntry;

  if (lineFragment->rect.size.width >= LARGE_SIZE)
    {
      return;
    }

  for (index = 0, glyphEntry = glyphCache; numLineFragments; numLineFragments--, lineFragment++)
    {
      delta = (lineFragment->rect.size.width - lineFragment->lastUsed) / 2.0;
      for (; index < lineFragment->lastGlyphIndex; index++, glyphEntry++)
        glyphEntry->position.x += delta;

      lineFragment->lastUsed += delta;
    }
}


/* 
   Soft invalidation optimization: When text is edited, the layout manager may mark
   existing line fragments as "soft invalidated" rather than removing them entirely.
   
   This method attempts to reuse existing line fragment rectangles by shifting them
   vertically to the current position. This avoids recomputing glyph positions when
   only the vertical position changed (e.g., when text is inserted at the top).
   
   Returns YES if we successfully reused the invalidated layout, NO if we need to
   perform standard layout.
   
   Current limitation: Only handles simple rectangular text containers.
*/
-(BOOL) _reuseSoftInvalidatedLayout
{
  /*
  We only handle the simple-horizontal-text-container case currently.
  */
  NSRect firstRect, rect;
  NSSize shift;
  int index;
  unsigned int glyph, nextGlyph, firstGlyph;
  CGFloat containerHeight;
  /*
  Ask the layout manager for soft-invalidated layout for the current
  glyph. If there is a set of line fragments starting at the current glyph,
  and we can get rects with the same size and horizontal position, we
  tell the layout manager to use the soft-invalidated information.
  */
  firstRect = [currentLayoutManager _softInvalidateLineFragRect: 0
                                                     firstGlyph: &firstGlyph
                                                      nextGlyph: &glyph
                                                inTextContainer: currentTextContainer];

  containerHeight = [currentTextContainer containerSize].height;
  if (!(currentPoint.y + firstRect.size.height <= containerHeight))
    return NO;

  /*
  We can shift the rects and still have things fit. Find all the line
  fragments in the line and shift them.
  */
  shift.width = 0;
  shift.height = currentPoint.y - firstRect.origin.y;
  index = 1;
  currentPoint.y = NSMaxY(firstRect) + shift.height;
  for (; 1; index++)
    {
      rect = [currentLayoutManager _softInvalidateLineFragRect: index
                                                    firstGlyph: &firstGlyph
                                                     nextGlyph: &nextGlyph
                                               inTextContainer: currentTextContainer];

      /*
      If there's a gap in soft invalidated information, we need to
      fill it in before we can continue.
      */
      if (firstGlyph != glyph)
        {
          break;
        }

      if (NSIsEmptyRect(rect) || NSMaxY(rect) + shift.height > containerHeight)
        break;

      glyph = nextGlyph;
      currentPoint.y = NSMaxY(rect) + shift.height;
    }

  [currentLayoutManager _softInvalidateUseLineFrags: index
                                          withShift: shift
                                    inTextContainer: currentTextContainer];

  currentGlyphIndex = glyph;

  return YES;
}


/* 
   Calculates the proposed rectangle for a new line.
   
   For new paragraphs: uses firstLineHeadIndent (special first-line indentation)
   For continuing lines: uses headIndent (standard paragraph indentation)
   
   tailIndent is interpreted relative to the container width if negative.
*/
- (NSRect)_getProposedRectForNewParagraph: (BOOL)newParagraph
                           withLineHeight: (CGFloat) lineHeight
{
  CGFloat headIndent;
  CGFloat tailIndent = [currentParagraphStyle tailIndent];

  if (newParagraph)
    headIndent = [currentParagraphStyle firstLineHeadIndent];
  else
    headIndent = [currentParagraphStyle headIndent];

  if (tailIndent <= 0.0)
    {
      NSSize size;

      size = [currentTextContainer containerSize];
      tailIndent = size.width + tailIndent;  /* tailIndent is negative, so this subtracts from width */
    }

  return NSMakeRect(headIndent,
                    currentPoint.y,
                    tailIndent - headIndent,
                    lineHeight + [currentParagraphStyle lineSpacing]);
}

/* 
   Creates an extra line fragment rect at the end of text when the last character
   is a paragraph separator (newline). This provides a place for the insertion point
   to blink after the final newline.
   
   The rect is sized according to the typing attributes (font/paragraph style that
   will be used for newly typed text).
*/
- (void) _addExtraLineFragment
{
  NSRect rect, extraRect, remain;
  CGFloat lineHeight;

  /*
    We aren't actually interested in the glyph data, but we want the
    attributes for the final character so we can make the extra line
    frag rect match it. This call makes sure that currentParagraphStyle
    and currentFont are set.
  */
  if (currentGlyphIndex)
    {
      [self _moveCacheToGlyph: currentGlyphIndex - 1];
    }
  else
    {
      /* No text yet - use typing attributes */
      NSDictionary *typingAttributes = [currentLayoutManager typingAttributes];
      currentParagraphStyle = [typingAttributes
                                    objectForKey: NSParagraphStyleAttributeName];
      if (currentParagraphStyle == nil)
        {
          currentParagraphStyle = [NSParagraphStyle defaultParagraphStyle];
        }
      currentFont = [typingAttributes objectForKey: NSFontAttributeName];
    }

  if (currentFont)
    {
      lineHeight = [currentFont defaultLineHeightForFont];
    }
  else
    {
      lineHeight = 15.0;
    }

  rect = [self _getProposedRectForNewParagraph: YES
                                withLineHeight: lineHeight];
  rect = [currentTextContainer lineFragmentRectForProposedRect: rect
                                                sweepDirection: NSLineSweepRight
                                             movementDirection: NSLineMovesDown
                                                 remainingRect: &remain];

  if (!NSIsEmptyRect(rect))
    {
      extraRect = rect;
      extraRect.size.width = 1;  /* Minimal width for the extra fragment */
      [currentLayoutManager setExtraLineFragmentRect: rect
                                            usedRect: extraRect
                                       textContainer: currentTextContainer];
    }
}

/* 
   Utility function: Updates lineHeight if the requested height exceeds current value,
   respecting maxLineHeight constraints.
   
   Returns YES if the line height was increased, indicating that layout needs to restart
   with the new height (since line fragment rects depend on height).
*/
static inline BOOL wantNewLineHeight(CGFloat height, CGFloat *lineHeight, CGFloat maxLineHeight)
{
  CGFloat newHeight = height;

  if (maxLineHeight > 0 && newHeight > maxLineHeight)
    {
      newHeight = maxLineHeight;
    }

  if (newHeight > *lineHeight)
    {
      *lineHeight = newHeight;
      return YES;
    }

  return NO;
}

/* 
   CORE LAYOUT ALGORITHM
   
   This method performs the actual glyph positioning for a single line of text.
   It handles:
   - Glyph positioning with kerning
   - Baseline calculation (ascender/descender tracking)
   - Line breaking (word wrap, char wrap, truncation)
   - Text attachments (images/embeddings)
   - Control characters (tabs, newlines)
   
   The method operates on the current contents of glyphCache and fills in positioning
   information. It may return YES to request that the caller restart layout with a
   larger line height (if content requires more space than initially allocated).
   
   Parameters:
   - newParagraph: OUTPUT - set to YES if line ends with paragraph break
   - lineHeight: INPUT/OUTPUT - current/updated line height
   - maxLineHeight: maximum allowed line height (0 = unlimited)
   - ascender: OUTPUT - maximum ascender for the line
   - descender: OUTPUT - maximum descender for the line
   
   Returns: YES if layout must restart with new lineHeight, NO if complete
*/
- (BOOL)_baseLayoutBlockNewParagraph:(BOOL *)newParagraph
                        onLineHeight:(CGFloat *)lineHeight
                         considering:(CGFloat)maxLineHeight
                       usingAscender:(CGFloat *)ascender
                        andDescender:(CGFloat *)descender
{
  unsigned int index = 0;
  GlyphCacheEntry *glyphEntry;

  NSPoint position;

  NSFont *font = glyphCache->font;

  CGFloat baseline; /* Baseline position (0 is top of line-height, positive is down in flipped coords). */
  CGFloat fontAscender = [font ascender];
  CGFloat fontDescender = -[font descender];

  NSGlyph lastGlyph = NSNullGlyph;
  NSPoint lastPosition;

  unsigned int firstGlyphIndex;
  LineFragment *lineFragment = lineFragments;
  int lineFragmentIndex = 0;

  BOOL previousHadNonNominalWidth;


  lastPosition = position = NSMakePoint(0, 0);

  glyphEntry = glyphCache;
  firstGlyphIndex = 0;
  previousHadNonNominalWidth = NO;
  /*
    Main glyph layout loop.
  */
  /* TODO: handling of newParagraph is ugly. must be set on all exits
     from this loop */
  while (1)
    {
      BOOL doesGlyphFitInLine = YES;

      //        printf("at %3i+%3i\n", cacheBase, index);
      /* Ensure we have glyphs cached */
      if (index >= cacheLength)
        {
          if (atEnd)
            {
              *newParagraph = NO;
              break;
            }
          [self _cacheGlyphsUpToLength: cacheLength + CACHE_STEP];
          if (index >= cacheLength)
            {
              *newParagraph = NO;
              break;
            }
          glyphEntry = glyphCache + index;
        }

      /*
        At this point:

        position is the current insertion point - where the next nominally-spaced 
        glyph would be placed if it fits.

        glyphEntry is the current glyph. index is the current glyph index, relative to
        the start of the cache.

        lastPosition and lastGlyph are used for kerning and hold the previous
        glyph and its position. If there's no previous glyph (for kerning
        purposes), lastGlyph is NSNullGlyph and lastPosition is undefined.

        lineFragment and lineFragmentIndex track the current line fragment rect. firstGlyphIndex is the
        first glyph in the current line fragment rect.

        Note: The variables tracking the previous glyph shouldn't be
        updated until we know that the current glyph will fit in the line
        fragment rect.
      */

      /* Handle font changes: update ascender/descender tracking.
         Note: We update metrics even if no glyphs end up using this font,
         ensuring the line height accommodates font changes. */
      if (glyphEntry->font != font)
        {
          font = glyphEntry->font;
          fontAscender = [font ascender];
          fontDescender = -[font descender];
          lastGlyph = NSNullGlyph;  /* Can't kern across font changes */
        }


      /* Set up glyph information */

      /*
        TODO:
        Currently, the attributes of the attachment character (eg. font)
        affect the layout. Think hard about this.
      */
      glyphEntry->nominal =

/*
   GSHorizontalTypesetter.m

   Copyright (C) 2002, 2003 Free Software Foundation, Inc.

   Author: Alexander Malmberg <[email protected]>
   Date: November 2002 - February 2003

   This file is part of the GNUstep GUI Library.

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.

   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with this library; see the file COPYING.LIB.
   If not, see <http://www.gnu.org/licenses/> or write to the
   Free Software Foundation, 51 Franklin Street, Fifth Floor,
   Boston, MA 02110-1301, USA.
*/


#include <math.h>

#import <Foundation/NSDebug.h>
#import <Foundation/NSException.h>
#import <Foundation/NSGeometry.h>
#import <Foundation/NSLock.h>
#import <Foundation/NSThread.h>
#import <Foundation/NSValue.h>

#import "AppKit/NSAttributedString.h"
#import "AppKit/NSParagraphStyle.h"
#import "AppKit/NSTextAttachment.h"
#import "AppKit/NSTextContainer.h"
#import "AppKit/NSTextStorage.h"
#import "GNUstepGUI/GSLayoutManager.h"
#import "GNUstepGUI/GSHorizontalTypesetter.h"



/*
Note that unless the user creates extra instances, there will only be one
instance of GSHorizontalTypesetter for all text typesetting, so we can
cache fairly aggressively without having to worry about memory consumption.
*/


@implementation GSHorizontalTypesetter

- init
{
  if (!(self = [super init])) return nil;
  lock = [[NSLock alloc] init];
  return self;
}

-(void) dealloc
{
  if (glyphCache)
    {
      free(glyphCache);
      glyphCache = NULL;
    }
  if (lineFragments)
    {
      free(lineFragments);
      lineFragments = NULL;
    }
  DESTROY(lock);
  [super dealloc];
}

+(GSHorizontalTypesetter *) sharedInstance
{
  NSMutableDictionary *threadDict =
    [[NSThread currentThread] threadDictionary];
  GSHorizontalTypesetter *shared =
    [threadDict objectForKey: @"sharedHorizontalTypesetter"];

  if (!shared)
    {
      shared = [[self alloc] init];
      [threadDict setObject: shared
                     forKey: @"sharedHorizontalTypesetter"];
      RELEASE(shared);
    }

  return shared;
}

#define CACHE_INITIAL 192
#define CACHE_STEP 192


/* 
   GlyphCacheEntry stores all information needed to position and render a single glyph.
   This structure is filled in two phases:
   1. Caching phase (_cacheGlyphsUpToLength:): fills glyph, characterIndex, font, and attributes
   2. Layout phase (_baseLayoutBlock...): fills position, size, dontShow, outsideLineFragment, nominal
   
   Note on coordinates: The position is relative to the line's baseline. In the standard
   flipped AppKit coordinate system (origin at top-left, y increasing downward), the baseline
   is positioned at 'lineHeight - descender' from the top of the line fragment rect.
   Thus, a glyph's final y-coordinate = lineFragmentTop + baseline + glyphEntry->position.y
*/
struct GSHorizontalTypesetterGlyphCacheStruct
{
  /* Filled during caching phase: */
  NSGlyph glyph;                /* The glyph index (NSGlyph is an unsigned int) */
  unsigned int characterIndex;  /* Corresponding character index in text storage */

  NSFont *font;                 /* Font to use for this glyph */
  struct
    {
      BOOL explicitKern;
      float kern;
      float baselineOffset;
      int superscript;
    } attributes;               /* Copy of relevant text attributes */

  /* Filled during layout phase: */
  BOOL nominal;                 /* YES if glyph is at its "nominal" (standard) position 
                                   relative to previous glyph. Used to determine if we need 
                                   to record a specific location for the glyph run. */
  NSPoint position;             /* Position relative to the line's baseline. 
                                   x = horizontal offset from line start
                                   y = vertical offset from baseline (up=negative in flipped coords) */
  NSSize size;                  /* Advancement (width) of glyph. Height used only for attachments. */
  BOOL dontShow;                /* YES for control characters (space, tab, newline) that have 
                                   visual representation in the glyph stream but shouldn't render */
  BOOL outsideLineFragment;     /* YES if glyph extends beyond line fragment bounds (for clipping modes) */
};
typedef struct GSHorizontalTypesetterGlyphCacheStruct GlyphCacheEntry;

/* TODO: if we could know whether the layout manager had been modified since
   the last time or not, we wouldn't need to clear the cache every time */
-(void) _clearCache
{
  cacheLength = 0;

  currentParagraphStyle = nil;
  paragraphRange = NSMakeRange(0, 0);
  currentAttributes = nil;
  attributeRange = NSMakeRange(0, 0);
  currentFont = nil;
  fontRange = NSMakeRange(0, 0);
}

/* 
   Caches text attributes (kern, baselineOffset, superscript) for the character at the given index.
   Uses attributeRange to avoid redundant dictionary lookups. This method updates both
   currentAttributes (the dictionary) and the attributes struct (extracted values).
*/
-(void) _cacheAttributesAtCharacterIndex: (unsigned int)characterIndex
{
  NSNumber *numberValue;

  if (NSLocationInRange(characterIndex, attributeRange))
    {
      return;
    }
  
  currentAttributes = [currentTextStorage attributesAtIndex: characterIndex
                                             effectiveRange: &attributeRange];

  numberValue = [currentAttributes objectForKey: NSKernAttributeName];
  if (!numberValue)
    attributes.explicitKern = NO;
  else
    {
      attributes.explicitKern = YES;
      attributes.kern = [numberValue floatValue];
    }

  numberValue = [currentAttributes objectForKey: NSBaselineOffsetAttributeName];
  if (numberValue)
    attributes.baselineOffset = [numberValue floatValue];
  else
    attributes.baselineOffset = 0.0;

  numberValue = [currentAttributes objectForKey: NSSuperscriptAttributeName];
  if (numberValue)
    attributes.superscript = [numberValue intValue];
  else
    attributes.superscript = 0;
}

/* 
   Repositions the cache window to start at the specified glyph index.
   If the requested index is already within the current cache window, this efficiently
   shifts the existing data to the front of the buffer (memmove).
   
   If the index is outside the current cache, this resets the cache and looks up
   the paragraph style, attributes, and font for the new position.
*/
-(void) _moveCacheToGlyph: (unsigned int)glyphIndex
{
  BOOL valid;

  /* Case 1: Requested glyph is already in our cache window */
  if (cacheBase <= glyphIndex && cacheBase + cacheLength > glyphIndex)
    {
      int delta = glyphIndex - cacheBase;
      cacheLength -= delta;
      /* Shift remaining entries to the start of the buffer */
      memmove(glyphCache, &glyphCache[delta], sizeof(GlyphCacheEntry) * cacheLength);
      cacheBase = glyphIndex;
      return;
    }

  /* Case 2: New position - reset cache and look up context */
  cacheBase = glyphIndex;
  cacheLength = 0;

  [currentLayoutManager glyphAtIndex: glyphIndex
                        isValidIndex: &valid];

  if (valid)
    {
      unsigned int charIndex;

      atEnd = NO;
      charIndex = [currentLayoutManager characterIndexForGlyphAtIndex: glyphIndex];
      [self _cacheAttributesAtCharacterIndex: charIndex];

      /* Look up paragraph style - this affects indentation, tab stops, alignment, etc. */
      paragraphRange = NSMakeRange(charIndex, [currentTextStorage length] - charIndex);
      currentParagraphStyle = [currentTextStorage attribute: NSParagraphStyleAttributeName
                                                    atIndex: charIndex
                                      longestEffectiveRange: &paragraphRange
                                                    inRange: paragraphRange];
      if (currentParagraphStyle == nil)
        {
          currentParagraphStyle = [NSParagraphStyle defaultParagraphStyle];
        }

      currentFont = [currentLayoutManager effectiveFontForGlyphAtIndex: glyphIndex
                                                                 range: &fontRange];
    }
  else
    {
      /* No valid glyph at this index - we've reached the end of text */
      atEnd = YES;
    }
}

/* 
   Ensures the cache contains at least newLength entries starting from cacheBase.
   This method fills in glyphCache[cacheLength] through glyphCache[newLength-1] with
   glyph information from the layout manager.
   
   The method stops early if:
   - We run out of glyphs (atEnd = YES)
   - We reach the end of the current paragraph (paragraph separator)
*/
-(void) _cacheGlyphsUpToLength: (unsigned int)newLength
{
  GlyphCacheEntry *glyphEntry;
  BOOL valid;

  /* Grow buffer if necessary */
  if (cacheSize < newLength)
    {
      cacheSize = newLength;
      glyphCache = realloc(glyphCache, sizeof(GlyphCacheEntry) * cacheSize);
    }

  /* Fill in entries from current end of cache up to requested length */
  for (glyphEntry = &glyphCache[cacheLength]; cacheLength < newLength; cacheLength++, glyphEntry++)
    {
      glyphEntry->glyph = [currentLayoutManager glyphAtIndex: cacheBase + cacheLength
                                                isValidIndex: &valid];
      if (!valid)
        {
          atEnd = YES;
          break;
        }
      glyphEntry->characterIndex = [currentLayoutManager characterIndexForGlyphAtIndex: cacheBase + cacheLength];
      
      /* Stop if we've moved to the next paragraph (hit paragraph separator) */
      if (glyphEntry->characterIndex >= paragraphRange.location + paragraphRange.length)
        {
          atEnd = YES;
          break;
        }

      /* Cache attributes if we've moved past the current attribute range */
      if (glyphEntry->characterIndex >= attributeRange.location + attributeRange.length)
        {
          [self _cacheAttributesAtCharacterIndex: glyphEntry->characterIndex];
        }

      /* Copy cached attributes into the glyph entry */
      glyphEntry->attributes.explicitKern = attributes.explicitKern;
      glyphEntry->attributes.kern = attributes.kern;
      glyphEntry->attributes.baselineOffset = attributes.baselineOffset;
      glyphEntry->attributes.superscript = attributes.superscript;

      /* Update font if we've moved past the current font range */
      if (cacheBase + cacheLength >= fontRange.location + fontRange.length)
        {
          currentFont = [currentLayoutManager effectiveFontForGlyphAtIndex: cacheBase + cacheLength
                                                                     range: &fontRange];
        }
      glyphEntry->font = currentFont;

      /* Initialize layout-related fields */
      glyphEntry->dontShow = NO;
      glyphEntry->outsideLineFragment = NO;
      glyphEntry->nominal = YES;

      /* Get the advancement (width) of this glyph */
      // FIXME: This assumes the layout manager implements this GNUstep extension
      glyphEntry->size = [currentLayoutManager advancementForGlyphAtIndex: cacheBase + cacheLength];
    }
}


/*
   Performs word wrapping by searching backward from glyphIndex for a valid line break point.
   Valid break points are:
   - Whitespace characters (space, newline, carriage return, tab)
   - CJK characters (treated as word boundaries)
   - Control glyphs
   
   Returns the glyph index of the first glyph on the next line (the glyph after the break).
   
   IMPORTANT: This method assumes glyphCache contains entries up to glyphIndex.
   It marks whitespace characters with dontShow=YES so they don't render at line ends.
   
   Note: The return value is a glyph index in the layout manager's coordinate space,
   not relative to cacheBase.
*/
-(unsigned int) breakLineByWordWrappingBefore: (unsigned int)glyphIndex
{
  GlyphCacheEntry *glyphEntry;
  unichar character;
  NSString *string = [currentTextStorage string];

  /* Convert to cache-relative index */
  glyphIndex -= cacheBase;
  glyphEntry = glyphCache + glyphIndex;

  while (glyphIndex > 0)
    {
      if (glyphEntry->glyph == NSControlGlyph)
        return glyphIndex + cacheBase;

      character = [string characterAtIndex: glyphEntry->characterIndex];
      /* TODO: paragraph/line separator */
      if (character == 0x20 || // space
          character == 0x0a || // new line
          character == 0x0d || // carriage return
          character == 0x09)   // horiz. tab
        {
          /* Mark the whitespace as "don't show" - it provides spacing but no visual */
          glyphEntry->dontShow = YES;
          /* Position it after the previous glyph for proper caret positioning */
          if (glyphIndex > 0)
            {
              glyphEntry->position = glyphEntry[-1].position;
              glyphEntry->position.x += glyphEntry[-1].size.width;
            }
          else
            glyphEntry->position = NSMakePoint(0, 0);

          glyphEntry->size.width = 0;
          /* Return the glyph AFTER the whitespace (start of next line) */
          return glyphIndex + 1 + cacheBase;
        }
      /* Each CJK glyph should be treated as a word when wrapping word.
         The range should work for most cases */
      else if ((character > 0x2ff0) && (character < 0x9fff))
         {
           glyphEntry->dontShow = NO;
           if (glyphIndex > 0)
             {
               glyphEntry->position = glyphEntry[-1].position;
               glyphEntry->position.x += glyphEntry[-1].size.width;
             }
           else
             glyphEntry->position = NSMakePoint(0,0);

           return glyphIndex + cacheBase;
         }

      glyphIndex--;
      glyphEntry--;
    }

  return glyphIndex + cacheBase;
}


/* 
   LineFragment tracks the geometry of a rectangular area available for text.
   A single "line" of text may consist of multiple fragments if the text flows
   around non-rectangular exclusion paths or multiple columns.
*/
struct GSHorizontalTypesetterLineFragmentStruct
{
  NSRect rect;                /* The rectangle (in text container coordinates) */
  CGFloat lastUsed;           /* Rightmost x-coordinate actually used by glyphs */
  unsigned int lastGlyphIndex; /* One past the last glyph index in this fragment (cache-relative) */
};
typedef struct GSHorizontalTypesetterLineFragmentStruct LineFragment;

/*
Apple uses this as the maximum width of an NSTextContainer.
For bigger values the width gets ignored.
*/
#define LARGE_SIZE 1e7

/* 
   Distributes extra space across space characters to justify the line.
   Only modifies inter-word spacing; intra-word spacing remains unchanged.
   
   Algorithm:
   1. Count spaces in the line
   2. Calculate extraSpace = lineWidth - usedWidth
   3. Distribute extraSpace evenly across all spaces
   4. Adjust glyph positions cumulatively (delta accumulates across the line)
   
   Note: This processes multiple line fragments if the line wraps around shapes.
*/
-(void) fullJustifyLine: (LineFragment *)lineFragment : (int)numLineFragments
{
  unsigned int index, start;
  CGFloat extraSpace, delta;
  unsigned int numSpaces;
  NSString *string = [currentTextStorage string];
  GlyphCacheEntry *glyphEntry;
  unichar character;

  /* Don't attempt to justify lines that are effectively infinite (unwrapped) */
  if (lineFragment->rect.size.width >= LARGE_SIZE)
    {
      return;
    }

  for (start = 0; numLineFragments; numLineFragments--, lineFragment++)
    {
      numSpaces = 0;
      /* Count spaces in this fragment */
      for (index = start, glyphEntry = glyphCache + index; index < lineFragment->lastGlyphIndex; index++, glyphEntry++)
        {
          if (glyphEntry->dontShow)
            continue;

          character = [string characterAtIndex: glyphEntry->characterIndex];
          if (character == 0x20)
            numSpaces++;
        }
      if (!numSpaces)
        continue;

      /* Calculate per-space adjustment */
      extraSpace = lineFragment->rect.size.width - lineFragment->lastUsed;
      extraSpace /= numSpaces;
      delta = 0;
      
      /* Apply cumulative adjustments */
      for (index = start, glyphEntry = glyphCache + index; index < lineFragment->lastGlyphIndex; index++, glyphEntry++)
        {
          glyphEntry->position.x += delta;
          if (!glyphEntry->dontShow && [string characterAtIndex: glyphEntry->characterIndex] == 0x20)
            {
              /* Mark the following glyph as non-nominal since we adjusted spacing */
              if (index < lineFragment->lastGlyphIndex)
                glyphEntry[1].nominal = NO;

              delta += extraSpace;
            }
        }

      start = lineFragment->lastGlyphIndex;
      lineFragment->lastUsed = lineFragment->rect.size.width;
    }
}

/* 
   Shifts all glyphs right so the line is flush with the right margin.
   Calculates delta = lineWidth - usedWidth and adds it to all x positions.
*/
-(void) rightAlignLine: (LineFragment *)lineFragment : (int)numLineFragments
{
  unsigned int index;
  CGFloat delta;
  GlyphCacheEntry *glyphEntry;

  if (lineFragment->rect.size.width >= LARGE_SIZE)
    {
      return;
    }

  for (index = 0, glyphEntry = glyphCache; numLineFragments; numLineFragments--, lineFragment++)
    {
      delta = lineFragment->rect.size.width - lineFragment->lastUsed;
      for (; index < lineFragment->lastGlyphIndex; index++, glyphEntry++)
        glyphEntry->position.x += delta;

      lineFragment->lastUsed += delta;
    }
}

/* 
   Centers the line by adding half the remaining space to all glyph positions.
   delta = (lineWidth - usedWidth) / 2.0
*/
-(void) centerAlignLine: (LineFragment *)lineFragment : (int)numLineFragments
{
  unsigned int index;
  CGFloat delta;
  GlyphCacheEntry *glyphEntry;

  if (lineFragment->rect.size.width >= LARGE_SIZE)
    {
      return;
    }

  for (index = 0, glyphEntry = glyphCache; numLineFragments; numLineFragments--, lineFragment++)
    {
      delta = (lineFragment->rect.size.width - lineFragment->lastUsed) / 2.0;
      for (; index < lineFragment->lastGlyphIndex; index++, glyphEntry++)
        glyphEntry->position.x += delta;

      lineFragment->lastUsed += delta;
    }
}


/* 
   Soft invalidation optimization: When text is edited, the layout manager may mark
   existing line fragments as "soft invalidated" rather than removing them entirely.
   
   This method attempts to reuse existing line fragment rectangles by shifting them
   vertically to the current position. This avoids recomputing glyph positions when
   only the vertical position changed (e.g., when text is inserted at the top).
   
   Returns YES if we successfully reused the invalidated layout, NO if we need to
   perform standard layout.
   
   Current limitation: Only handles simple rectangular text containers.
*/
-(BOOL) _reuseSoftInvalidatedLayout
{
  /*
  We only handle the simple-horizontal-text-container case currently.
  */
  NSRect firstRect, rect;
  NSSize shift;
  int index;
  unsigned int glyph, nextGlyph, firstGlyph;
  CGFloat containerHeight;
  /*
  Ask the layout manager for soft-invalidated layout for the current
  glyph. If there is a set of line fragments starting at the current glyph,
  and we can get rects with the same size and horizontal position, we
  tell the layout manager to use the soft-invalidated information.
  */
  firstRect = [currentLayoutManager _softInvalidateLineFragRect: 0
                                                     firstGlyph: &firstGlyph
                                                      nextGlyph: &glyph
                                                inTextContainer: currentTextContainer];

  containerHeight = [currentTextContainer containerSize].height;
  if (!(currentPoint.y + firstRect.size.height <= containerHeight))
    return NO;

  /*
  We can shift the rects and still have things fit. Find all the line
  fragments in the line and shift them.
  */
  shift.width = 0;
  shift.height = currentPoint.y - firstRect.origin.y;
  index = 1;
  currentPoint.y = NSMaxY(firstRect) + shift.height;
  for (; 1; index++)
    {
      rect = [currentLayoutManager _softInvalidateLineFragRect: index
                                                    firstGlyph: &firstGlyph
                                                     nextGlyph: &nextGlyph
                                               inTextContainer: currentTextContainer];

      /*
      If there's a gap in soft invalidated information, we need to
      fill it in before we can continue.
      */
      if (firstGlyph != glyph)
        {
          break;
        }

      if (NSIsEmptyRect(rect) || NSMaxY(rect) + shift.height > containerHeight)
        break;

      glyph = nextGlyph;
      currentPoint.y = NSMaxY(rect) + shift.height;
    }

  [currentLayoutManager _softInvalidateUseLineFrags: index
                                          withShift: shift
                                    inTextContainer: currentTextContainer];

  currentGlyphIndex = glyph;

  return YES;
}


/* 
   Calculates the proposed rectangle for a new line.
   
   For new paragraphs: uses firstLineHeadIndent (special first-line indentation)
   For continuing lines: uses headIndent (standard paragraph indentation)
   
   tailIndent is interpreted relative to the container width if negative.
*/
- (NSRect)_getProposedRectForNewParagraph: (BOOL)newParagraph
                           withLineHeight: (CGFloat) lineHeight
{
  CGFloat headIndent;
  CGFloat tailIndent = [currentParagraphStyle tailIndent];

  if (newParagraph)
    headIndent = [currentParagraphStyle firstLineHeadIndent];
  else
    headIndent = [currentParagraphStyle headIndent];

  if (tailIndent <= 0.0)
    {
      NSSize size;

      size = [currentTextContainer containerSize];
      tailIndent = size.width + tailIndent;  /* tailIndent is negative, so this subtracts from width */
    }

  return NSMakeRect(headIndent,
                    currentPoint.y,
                    tailIndent - headIndent,
                    lineHeight + [currentParagraphStyle lineSpacing]);
}

/* 
   Creates an extra line fragment rect at the end of text when the last character
   is a paragraph separator (newline). This provides a place for the insertion point
   to blink after the final newline.
   
   The rect is sized according to the typing attributes (font/paragraph style that
   will be used for newly typed text).
*/
- (void) _addExtraLineFragment
{
  NSRect rect, extraRect, remain;
  CGFloat lineHeight;

  /*
    We aren't actually interested in the glyph data, but we want the
    attributes for the final character so we can make the extra line
    frag rect match it. This call makes sure that currentParagraphStyle
    and currentFont are set.
  */
  if (currentGlyphIndex)
    {
      [self _moveCacheToGlyph: currentGlyphIndex - 1];
    }
  else
    {
      /* No text yet - use typing attributes */
      NSDictionary *typingAttributes = [currentLayoutManager typingAttributes];
      currentParagraphStyle = [typingAttributes
                                    objectForKey: NSParagraphStyleAttributeName];
      if (currentParagraphStyle == nil)
        {
          currentParagraphStyle = [NSParagraphStyle defaultParagraphStyle];
        }
      currentFont = [typingAttributes objectForKey: NSFontAttributeName];
    }

  if (currentFont)
    {
      lineHeight = [currentFont defaultLineHeightForFont];
    }
  else
    {
      lineHeight = 15.0;
    }

  rect = [self _getProposedRectForNewParagraph: YES
                                withLineHeight: lineHeight];
  rect = [currentTextContainer lineFragmentRectForProposedRect: rect
                                                sweepDirection: NSLineSweepRight
                                             movementDirection: NSLineMovesDown
                                                 remainingRect: &remain];

  if (!NSIsEmptyRect(rect))
    {
      extraRect = rect;
      extraRect.size.width = 1;  /* Minimal width for the extra fragment */
      [currentLayoutManager setExtraLineFragmentRect: rect
                                            usedRect: extraRect
                                       textContainer: currentTextContainer];
    }
}

/* 
   Utility function: Updates lineHeight if the requested height exceeds current value,
   respecting maxLineHeight constraints.
   
   Returns YES if the line height was increased, indicating that layout needs to restart
   with the new height (since line fragment rects depend on height).
*/
static inline BOOL wantNewLineHeight(CGFloat height, CGFloat *lineHeight, CGFloat maxLineHeight)
{
  CGFloat newHeight = height;

  if (maxLineHeight > 0 && newHeight > maxLineHeight)
    {
      newHeight = maxLineHeight;
    }

  if (newHeight > *lineHeight)
    {
      *lineHeight = newHeight;
      return YES;
    }

  return NO;
}

/* 
   CORE LAYOUT ALGORITHM
   
   This method performs the actual glyph positioning for a single line of text.
   It handles:
   - Glyph positioning with kerning
   - Baseline calculation (ascender/descender tracking)
   - Line breaking (word wrap, char wrap, truncation)
   - Text attachments (images/embeddings)
   - Control characters (tabs, newlines)
   
   The method operates on the current contents of glyphCache and fills in positioning
   information. It may return YES to request that the caller restart layout with a
   larger line height (if content requires more space than initially allocated).
   
   Parameters:
   - newParagraph: OUTPUT - set to YES if line ends with paragraph break
   - lineHeight: INPUT/OUTPUT - current/updated line height
   - maxLineHeight: maximum allowed line height (0 = unlimited)
   - ascender: OUTPUT - maximum ascender for the line
   - descender: OUTPUT - maximum descender for the line
   
   Returns: YES if layout must restart with new lineHeight, NO if complete
*/
- (BOOL)_baseLayoutBlockNewParagraph:(BOOL *)newParagraph
                        onLineHeight:(CGFloat *)lineHeight
                         considering:(CGFloat)maxLineHeight
                       usingAscender:(CGFloat *)ascender
                        andDescender:(CGFloat *)descender
{
  unsigned int index = 0;
  GlyphCacheEntry *glyphEntry;

  NSPoint position;

  NSFont *font = glyphCache->font;

  CGFloat baseline; /* Baseline position (0 is top of line-height, positive is down in flipped coords). */
  CGFloat fontAscender = [font ascender];
  CGFloat fontDescender = -[font descender];

  NSGlyph lastGlyph = NSNullGlyph;
  NSPoint lastPosition;

  unsigned int firstGlyphIndex;
  LineFragment *lineFragment = lineFragments;
  int lineFragmentIndex = 0;

  BOOL previousHadNonNominalWidth;


  lastPosition = position = NSMakePoint(0, 0);

  glyphEntry = glyphCache;
  firstGlyphIndex = 0;
  previousHadNonNominalWidth = NO;
  /*
    Main glyph layout loop.
  */
  /* TODO: handling of newParagraph is ugly. must be set on all exits
     from this loop */
  while (1)
    {
      BOOL doesGlyphFitInLine = YES;

      //        printf("at %3i+%3i\n", cacheBase, index);
      /* Ensure we have glyphs cached */
      if (index >= cacheLength)
        {
          if (atEnd)
            {
              *newParagraph = NO;
              break;
            }
          [self _cacheGlyphsUpToLength: cacheLength + CACHE_STEP];
          if (index >= cacheLength)
            {
              *newParagraph = NO;
              break;
            }
          glyphEntry = glyphCache + index;
        }

      /*
        At this point:

        position is the current insertion point - where the next nominally-spaced 
        glyph would be placed if it fits.

        glyphEntry is the current glyph. index is the current glyph index, relative to
        the start of the cache.

        lastPosition and lastGlyph are used for kerning and hold the previous
        glyph and its position. If there's no previous glyph (for kerning
        purposes), lastGlyph is NSNullGlyph and lastPosition is undefined.

        lineFragment and lineFragmentIndex track the current line fragment rect. firstGlyphIndex is the
        first glyph in the current line fragment rect.

        Note: The variables tracking the previous glyph shouldn't be
        updated until we know that the current glyph will fit in the line
        fragment rect.
      */

      /* Handle font changes: update ascender/descender tracking.
         Note: We update metrics even if no glyphs end up using this font,
         ensuring the line height accommodates font changes. */
      if (glyphEntry->font != font)
        {
          font = glyphEntry->font;
          fontAscender = [font ascender];
          fontDescender = -[font descender];
          lastGlyph = NSNullGlyph;  /* Can't kern across font changes */
        }


      /* Set up glyph information */

      /*
        TODO:
        Currently, the attributes of the attachment character (eg. font)
        affect the layout. Think hard about this.
      */
      glyphEntry->nominal = !previousHadNonNominalWidth;

      /* Apply explicit kerning if specified */
      if (glyphEntry->attributes.explicitKern &&
          glyphEntry->attributes.kern != 0)
        {
          position.x += glyphEntry->attributes.kern;
          glyphEntry->nominal = NO;
        }


      /* Check if glyph fits in current line fragment */
      doesGlyphFitInLine = !((index > firstGlyphIndex) && (position.x + glyphEntry->size.width > lineFragment->rect.size.width));
      if (doesGlyphFitInLine)
        {
          /* Calculate vertical adjustments for this glyph */
          CGFloat yOffset = 0;

          /* Superscript moves up (negative y in flipped coords) */
          if (glyphEntry->attributes.superscript)
            {
              yOffset -= glyphEntry->attributes.superscript * [font xHeight];
            }
          /* Baseline offset - positive moves up (negative y in flipped coords) */
          if (glyphEntry->attributes.baselineOffset)
            {
              yOffset += glyphEntry->attributes.baselineOffset;
            }

          if (yOffset != position.y)
            {
              position.y = yOffset;
              glyphEntry->nominal = NO;
            }

          /* Update line metrics based on this glyph */
          /* defaultLineHeightForFont is ascender+descender, match calculation here */

          /* Update from current font metrics */
          if (fontAscender > *ascender)
            *ascender = fontAscender;
          if (fontDescender > *descender)
            *descender = fontDescender;

          /* Adjust for superscript/subscript positioning */
          if (yOffset < 0 && fontAscender - yOffset > *ascender)
            *ascender = fontAscender - yOffset;
          if (yOffset > 0 && fontDescender + yOffset > *descender)
            *descender = fontDescender + yOffset;

          /* Check if we need to increase line height and restart */
          if (wantNewLineHeight(*ascender + *descender, lineHeight, maxLineHeight))
            return YES;
        }

      /* Handle control glyphs (newlines, tabs, etc.) */
      if (glyphEntry->glyph == NSControlGlyph)
        {
          unichar character = [[currentTextStorage string] characterAtIndex: glyphEntry->characterIndex];

          /* TODO: need to handle other control characters */

          glyphEntry->position = position;
          glyphEntry->size.width = 0;
          glyphEntry->dontShow = YES;
          glyphEntry->nominal = !previousHadNonNominalWidth;

          index++;
          glyphEntry++;

          lastGlyph = NSNullGlyph;

          previousHadNonNominalWidth = NO;

          /* Newline - end of paragraph */
          if (character == 0xa) // new line
            {
              *newParagraph = YES;
              break;
            }

          /* Tab - advance to next tab stop */
          if (character == 0x9) // horiz. tab
            {
              /*
                Handle tabs. This is a very basic and stupid implementation.
                TODO: implement properly
              */
              NSArray *tabs = [currentParagraphStyle tabStops];
              NSTextTab *tab = nil;
              CGFloat defaultInterval = [currentParagraphStyle defaultTabInterval];

              /* Set it to something reasonable if unset */
              if (defaultInterval == 0.0)
                {
                  defaultInterval = 100.0;
                }

              unsigned int tabIndex;
              unsigned int tabCount = [tabs count];
              /* Find first tab beyond our current position. */
              for (tabIndex = 0; tabIndex < tabCount; tabIndex++)
                {
                  tab = [tabs objectAtIndex: tabIndex];
                  /*
                     We cannot use a tab at our exact location; we must
                     use one beyond it. The reason is that several tabs in
                     a row would get very odd behavior. Eg. given "\t\t",
                     the first tab would move (exactly) to the next tab
                     stop, and the next tab stop would move to the same
                     tab, thus having no effect.
                  */
                  if ([tab location] > position.x + lineFragment->rect.origin.x)
                    {
                      break;
                    }
                }
              if (tabIndex == tabCount)
                {
                  /*
                     Tabs after the last value in tabStops should use the
                     defaultTabInterval provided by NSParagraphStyle.
                  */
                  position.x = (floor(position.x / defaultInterval) + 1.0) * defaultInterval;
                }
              else
                {
                  position.x = [tab location] - lineFragment->rect.origin.x;
                }
              previousHadNonNominalWidth = YES;
              continue;
            }

          NSDebugLLog(@"GSHorizontalTypesetter",
                      @"ignoring unknown control character %04x\n", character);

          continue;
        }

      /* Handle text attachments (embedded images, etc.) */
      if (glyphEntry->glyph == GSAttachmentGlyph)
        {
          NSTextAttachment *attachment;
          NSTextAttachmentCell *cell;
          NSRect cellFrame;

          attachment = [currentTextStorage attribute: NSAttachmentAttributeName
                                             atIndex: glyphEntry->characterIndex
                                      effectiveRange: NULL];
          cell = (NSTextAttachmentCell*)[attachment attachmentCell];
          if (!cell)
            {
              /* No cell for attachment - treat as zero-width invisible glyph */
              glyphEntry->position = position;
              glyphEntry->size = NSMakeSize(0, 0);
              glyphEntry->dontShow = YES;
              glyphEntry->nominal = YES;

              index++;
              glyphEntry++;
              lastGlyph = NSNullGlyph;

              continue;
            }

          /* Calculate baseline position within the line */
          baseline = *lineHeight - *descender;

          /* Ask the attachment cell for its desired frame */
          cellFrame = [cell cellFrameForTextContainer: currentTextContainer
                                 proposedLineFragment: lineFragment->rect
                                        glyphPosition: NSMakePoint(position.x, lineFragment->rect.size.height - baseline)
                                       characterIndex: glyphEntry->characterIndex];

          /* For some obscure reason, the rectangle we get is up-side-down
             compared to everything else here, and has it's origin in position.
             (Makes sense from the cell's pov, though.) */

          /* Check if attachment fits (and it is not the first element in line) */
          doesGlyphFitInLine = !((index > firstGlyphIndex) && (position.x + NSMaxX(cellFrame) > lineFragment->rect.size.width));
          if (doesGlyphFitInLine)
            {
              /* Update descender to accommodate attachment extending below baseline */
              if (-NSMinY(cellFrame) > *descender)
                *descender = -NSMinY(cellFrame);

              /* Update ascender to accommodate attachment extending above baseline */
              if (NSMaxY(cellFrame) > *ascender)
                *ascender = NSMaxY(cellFrame);

              /* Check if we need more line height */
              if (wantNewLineHeight(*ascender + *descender, lineHeight, maxLineHeight))
                return YES;
            }

          /* Record attachment position and size */
          glyphEntry->size = cellFrame.size;
          glyphEntry->position.x = position.x + cellFrame.origin.x;
          glyphEntry->position.y = position.y - cellFrame.origin.y;

          position.x = glyphEntry->position.x + glyphEntry->size.width;

          /* An attachment is always in a point range of its own. */
          glyphEntry->nominal = NO;
        }
      else
        {
          /* Regular glyph - apply kerning if we have a previous glyph */
          /* TODO: this is a major bottleneck */
          /*
          if (lastGlyph)
            {
              BOOL n;
              position = [font positionOfGlyph: glyphEntry->glyph
                               precededByGlyph: lastGlyph
                                     isNominal: &n];
              if (!n)
                glyphEntry->nominal = NO;
              position.x += lastPosition.x;
              position.y += lastPosition.y;
            }
          */
          /* For now, just place at current position without kerning */
          lastPosition = glyphEntry->position = position;
          /* Only the width is used. */
          position.x += glyphEntry->size.width;
        }

      /* Did the glyph fit in the line fragment rect? */
      if (!doesGlyphFitInLine)
        {
          /* It didn't. Try to break the line. */
          switch ([currentParagraphStyle lineBreakMode])
            { /* TODO: implement all modes */
              default:
              case NSLineBreakByCharWrapping:
                lineFragment->lastGlyphIndex = index;
                break;

              case NSLineBreakByWordWrapping:
                lineFragment->lastGlyphIndex = [self breakLineByWordWrappingBefore: cacheBase + index] - cacheBase;
                if (lineFragment->lastGlyphIndex <= firstGlyphIndex)
                  {
                    /* Word wrapping failed to find a break point - fall back to char wrapping */
                    lineFragment->lastGlyphIndex = index;
                  }
                break;

              case NSLineBreakByTruncatingHead:
              case NSLineBreakByTruncatingMiddle:
              case NSLineBreakByTruncatingTail:
                /* Pretending that these are clipping is far from perfect,
                   but it's the closest we've got. */
              case NSLineBreakByClipping:
                /* Scan forward to the next paragraph separator and mark
                   all the glyphs up to there as not visible. */
                glyphEntry->outsideLineFragment = YES;
                while (1)
                  {
                    index++;
                    glyphEntry++;

                    /* Ensure we have the next glyph cached */
                    if (index >= cacheLength)
                      {
                        if (atEnd)
                          {
                            *newParagraph = NO;
                            index--;
                            break;
                          }
                        [self _cacheGlyphsUpToLength: cacheLength + CACHE_STEP];
                        if (index >= cacheLength)
                          {
                            *newParagraph = NO;
                            index--;
                            break;
                          }
                        glyphEntry = glyphCache + index;
                      }

                    glyphEntry->dontShow = YES;
                    glyphEntry->position = position;

                    if (glyphEntry->glyph == NSControlGlyph
                        && [[currentTextStorage string] characterAtIndex: glyphEntry->characterIndex] == 0xa)
                      break;
                  }

                lineFragment->lastGlyphIndex = index + 1;
                break;
            }

          /* We force at least one glyph into each line fragment rect. This
             ensures that typesetting will never get stuck (ie. if the text
             container is too narrow to fit even a single glyph). */
          if (lineFragment->lastGlyphIndex <= firstGlyphIndex)
            lineFragment->lastGlyphIndex = index + 1;

          /* Prepare for next line fragment */
          lastPosition = position = NSMakePoint(0, 0);
          index = lineFragment->lastGlyphIndex;
          glyphEntry = glyphCache + index;
          /* The -1 is always valid since there's at least one glyph in the
             line fragment rect (see above). */
          lineFragment->lastUsed = glyphEntry[-1].position.x + glyphEntry[-1].size.width;
          lastGlyph = NSNullGlyph;
          previousHadNonNominalWidth = NO;

          /* Move to next line fragment */
          lineFragment++;
          lineFragmentIndex++;
          if (lineFragmentIndex == lineFragmentCount)
            {
              *newParagraph = NO;
              break;
            }
          firstGlyphIndex = index;
        }
      else
        {
          /* Glyph fit - advance to next glyph */
          lastGlyph = glyphEntry->glyph;

          /* Attachments break kerning chains */
          if (lastGlyph == GSAttachmentGlyph)
            {
              lastGlyph = NSNullGlyph;
              previousHadNonNominalWidth = YES;
            }
          else
            {
              previousHadNonNominalWidth = NO;
            }

          index++;
          glyphEntry++;
        }
    }
  /* Basic layout is done. */

  /* Apply text alignment */
  if (lineFragmentIndex != lineFragmentCount)
    {
      /* We didn't fill all fragments - this is the last line */
      lineFragment->lastGlyphIndex = index;
      lineFragment->lastUsed = position.x;

      /* Note: alignment only makes sense if we have one line fragment.
         Multiple fragments imply text wrapping around shapes where
         alignment is ambiguous. */
      if ([currentParagraphStyle alignment] == NSRightTextAlignment)
        [self rightAlignLine: lineFragments : lineFragmentCount];
      else if ([currentParagraphStyle alignment] == NSCenterTextAlignment)
        [self centerAlignLine: lineFragments : lineFragmentCount];
    }
  else
    {
      /* We filled all fragments - apply alignment */
      if ([currentParagraphStyle lineBreakMode] == NSLineBreakByWordWrapping &&
          [currentParagraphStyle alignment] == NSJustifiedTextAlignment)
        {
          [self fullJustifyLine: lineFragments : lineFragmentCount];
        }
      else if ([currentParagraphStyle alignment] == NSRightTextAlignment)
        {
          [self rightAlignLine: lineFragments : lineFragmentCount];
        }
      else if ([currentParagraphStyle alignment] == NSCenterTextAlignment)
        {
          [self centerAlignLine: lineFragments : lineFragmentCount];
        }

      lineFragmentIndex--;
    }

  /* Layout is complete. Package it and give it to the layout manager. */
  [currentLayoutManager setTextContainer: currentTextContainer
                           forGlyphRange: NSMakeRange(cacheBase, index)];
  currentGlyphIndex = index + cacheBase;
  {
    LineFragment *lineFragment;
    NSPoint glyphPosition;
    unsigned int lineFragCounter, lineFragCounter2;
    GlyphCacheEntry *glyphEntry;
    NSRect usedRect;

    /* Calculate final baseline position: baseline is measured from top of line */
    baseline = *lineHeight - *descender;

    /* Iterate through all line fragments and commit layout to layout manager */
    for (lineFragment = lineFragments, lineFragCounter = 0, glyphEntry = glyphCache; lineFragmentIndex >= 0; lineFragmentIndex--, lineFragment++)
      {
        /* Calculate used rect (actual area occupied by glyphs) */
        usedRect.origin.x = glyphEntry->position.x + lineFragment->rect.origin.x;
        usedRect.size.width = lineFragment->lastUsed - glyphEntry->position.x;
        /* TODO: be pickier about height? */
        usedRect.origin.y = lineFragment->rect.origin.y;
        usedRect.size.height = lineFragment->rect.size.height;

        /* Record the line fragment rectangle and used rectangle */
        [currentLayoutManager setLineFragmentRect: lineFragment->rect
                                    forGlyphRange: NSMakeRange(cacheBase + lineFragCounter, lineFragment->lastGlyphIndex - lineFragCounter)
                                         usedRect: usedRect];
        
        /* Set glyph positions relative to the baseline */
        glyphPosition = glyphEntry->position;
        glyphPosition.y += baseline;
        lineFragCounter2 = lineFragCounter;
        
        /* Process each glyph in this fragment */
        while (lineFragCounter < lineFragment->lastGlyphIndex)
          {
            /* Mark glyphs that extend outside the fragment (for clipping) */
            if (glyphEntry->outsideLineFragment)
              {
                [currentLayoutManager setDrawsOutsideLineFragment: YES
                                                  forGlyphAtIndex: cacheBase + lineFragCounter];
              }
            /* Mark control characters that shouldn't render */
            if (glyphEntry->dontShow)
              {
                [currentLayoutManager setNotShownAttribute: YES
                                           forGlyphAtIndex: cacheBase + lineFragCounter];
              }
            /* Record location for non-nominal glyph runs */
            if (!glyphEntry->nominal && lineFragCounter != lineFragCounter2)
              {
                [currentLayoutManager setLocation: glyphPosition
                             forStartOfGlyphRange: NSMakeRange(cacheBase + lineFragCounter2, lineFragCounter - lineFragCounter2)];
                if (glyphEntry[-1].glyph == GSAttachmentGlyph)
                  {
                    [currentLayoutManager setAttachmentSize: glyphEntry[-1].size
                                              forGlyphRange: NSMakeRange(cacheBase + lineFragCounter2, lineFragCounter - lineFragCounter2)];
                  }
                glyphPosition = glyphEntry->position;
                glyphPosition.y += baseline;
                lineFragCounter2 = lineFragCounter;
              }
            lineFragCounter++;
            glyphEntry++;
          }
        /* Record location for final run in this fragment */
        if (lineFragCounter != lineFragCounter2)
          {
            [currentLayoutManager setLocation: glyphPosition
                         forStartOfGlyphRange: NSMakeRange(cacheBase + lineFragCounter2, lineFragCounter - lineFragCounter2)];
            if (glyphEntry[-1].glyph == GSAttachmentGlyph)
              {
                [currentLayoutManager setAttachmentSize: glyphEntry[-1].size
                                          forGlyphRange: NSMakeRange(cacheBase + lineFragCounter2, lineFragCounter - lineFragCounter2)];
              }
          }
      }
  }
  return NO;
}

/*
   Return values 0, 1, 2 are mostly the same as from
   -layoutGlyphsInLayoutManager:.... Additions:

   0   Last typeset character was not a newline; next glyph does not start
       a new paragraph.

   3   Last typeset character was a newline; next glyph starts a new
       paragraph.

   4   Last typeset character may or may not have been a newline; must
       test before next call.

*/
-(int) layoutLineNewParagraph: (BOOL)newParagraph
{
  NSRect rect;

  /* Baseline and line height handling. */
  CGFloat lineHeight;      /* Current line height. */
  CGFloat maxLineHeight;   /* Maximum line height (usually from the paragraph style). */
  CGFloat ascender;        /* Amount of space we want above the baseline (always>=0). */
  CGFloat descender;       /* Amount of space we want below the baseline (always>=0). */

  /*
     These are values for the line as a whole. We start out by initializing
     for the first glyph on the line and then update these as we add more
     glyphs.

     If we need to increase the line height, we jump back to 'restart:' and
     rebuild our array of line fragment rects.

     (TODO (optimization): if we're dealing with a "simple rectangular
     text container", we should try to extend the existing line fragment in place
     before jumping back to do all the expensive checking).
  */

  /* Try to reuse soft-invalidated layout if possible (optimization for text edits) */
  /* TODO: doesn't have to be a simple horizontal container, but it's easier
     to handle that way. */
  if ([currentTextContainer isSimpleRectangularTextContainer] &&
      [currentLayoutManager _softInvalidateFirstGlyphInTextContainer: currentTextContainer] == currentGlyphIndex)
    {
      if ([self _reuseSoftInvalidatedLayout])
        return 4;
    }


  [self _moveCacheToGlyph: currentGlyphIndex];
  if (!cacheLength)
    [self _cacheGlyphsUpToLength: CACHE_INITIAL];
    
  if (!cacheLength && atEnd)
    {
      /*
      We've typeset all glyphs, and thus return 2. If we ended with a
      new-line, we set the extra line fragment rect here so the insertion point
      will be properly positioned after a trailing newline in the text.
      */
      if (newParagraph)
        {
          [self _addExtraLineFragment];
        }

      return 2;
    }

  /* Set up our initial baseline info based on the first glyph's font. */
  {
    CGFloat min = [currentParagraphStyle minimumLineHeight];
    maxLineHeight = [currentParagraphStyle maximumLineHeight];

    /* sanity check: ensure max >= min if both are specified */
    if (maxLineHeight > 0 && maxLineHeight < min)
      maxLineHeight = min;

    lineHeight = [glyphCache->font defaultLineHeightForFont];
    ascender = [glyphCache->font ascender];
    descender = -[glyphCache->font descender];

    if (lineHeight < min)
      lineHeight = min;

    if (maxLineHeight > 0 && lineHeight > maxLineHeight)
      lineHeight = maxLineHeight;
  }

  /*
     If we find out that we need to increase the line height, we have to
     start over. The increased line height might give _completely_ different
     line fragment rects, so we can't reuse the layout information.

     OPT: However, we could recreate the line fragment rects and see if they
     match before throwing away layout information, since most of the time
     they will be equivalent.

     Also, in the very common case of a simple rectangular text container, we
     can always extend the current line fragment rects as long as they don't extend
     past the bottom of the container.
  */

  BOOL recalculateLineHeight = NO;
  do
    {
      /* Build list of line fragment rects for this line */
      do
        {
          NSRect remain;

          remain = [self _getProposedRectForNewParagraph: newParagraph
                                          withLineHeight: lineHeight];

          /*
            Build a list of all line fragment rects for this line.

            TODO: it's very convenient to do this in advance, but it might be
            inefficient, and in theory, we might end up with an insane number of line
            rects (eg. a text container with "hole"-columns every 100 points and
            width 1e8)
          */
          lineFragmentCount = 0;
          rect = [currentTextContainer lineFragmentRectForProposedRect: remain
                                                        sweepDirection: NSLineSweepRight
                                                     movementDirection: NSLineMovesDown
                                                         remainingRect: &remain];
          while (!NSIsEmptyRect(rect))
            {
              lineFragmentCount++;
              if (lineFragmentCount > lineFragmentCapacity)
                {
                  lineFragmentCapacity += 2;
                  lineFragments = realloc(lineFragments, sizeof(LineFragment) * lineFragmentCapacity);
                }
              lineFragments[lineFragmentCount - 1].rect = rect;

              /* Continue sweeping right for more fragments in this line */
              rect = [currentTextContainer lineFragmentRectForProposedRect: remain
                                                            sweepDirection: NSLineSweepRight
                                                         movementDirection: NSLineDoesntMove
                                                             remainingRect: &remain];
            }
          if (lineFragmentCount == 0)
            {
              /* No room for even one fragment. If we're at the top and the
                 container is smaller than our line height, try shrinking the line. */
              if (currentPoint.y == 0.0 &&
                  lineHeight > [currentTextContainer containerSize].height &&
                  [currentTextContainer containerSize].height > 0.0)
                {
                  /* Try to make sure each container contains at least one line fragment
                     rect by shrinking our line height. */
                  lineHeight = [currentTextContainer containerSize].height;
                  maxLineHeight = lineHeight;
                  continue;
                }
              return 1;  /* No room - stop layout */
            }
        }
      while (lineFragmentCount == 0);

      /* Perform the actual glyph layout */
      recalculateLineHeight = [self _baseLayoutBlockNewParagraph: &newParagraph
                                                    onLineHeight: &lineHeight
                                                     considering: maxLineHeight
                                                   usingAscender: &ascender
                                                    andDescender: &descender];

    }
  while (recalculateLineHeight);  /* Restart if line height increased */

  /* Update current point to after this line */
  currentPoint = NSMakePoint(0, NSMaxY(lineFragments->rect));

  if (newParagraph)
    return 3;  /* Line ended with paragraph break */
  else
    return 0;  /* Line ended normally */
}


/*
   Main entry point for layout. Lays out glyphs in the specified text container
   starting from glyphIndex.
   
   Return values:
   0 - Layout stopped because we ran out of text (atEnd)
   1 - Layout stopped because we ran out of room in the text container
   2 - Layout stopped because we reached the requested number of line fragments
   
   This method is reentrant-safe: if the shared instance is already in use,
   it creates a temporary instance to handle the recursive call.
*/
-(int) layoutGlyphsInLayoutManager: (GSLayoutManager *)layoutManager
                   inTextContainer: (NSTextContainer *)textContainer
              startingAtGlyphIndex: (unsigned int)glyphIndex
          previousLineFragmentRect: (NSRect)previousLineFragRect
                    nextGlyphIndex: (unsigned int *)nextGlyphIndex
             numberOfLineFragments: (unsigned int)howMany
{
  int ret, realRet;
  BOOL newParagraph;

  /* Reentrancy check: if we're already laying out text, create a temporary instance */
  if (![lock tryLock])
    {
      /* Since we might be the shared system typesetter, we must be
      reentrant. Thus, if we are already in use and can't lock our lock,
      we create a new instance and let it handle the call. */
      GSHorizontalTypesetter *tempTypesetter;

      tempTypesetter = [[object_getClass(self) alloc] init];
      ret = [tempTypesetter layoutGlyphsInLayoutManager: layoutManager
                                        inTextContainer: textContainer
                                   startingAtGlyphIndex: glyphIndex
                               previousLineFragmentRect: previousLineFragRect
                                         nextGlyphIndex: nextGlyphIndex
                                  numberOfLineFragments: howMany];
      DESTROY(tempTypesetter);
      return ret;
    }

NS_DURING
  /* Set up layout context */
  currentLayoutManager = layoutManager;
  currentTextContainer = textContainer;
  currentTextStorage = [layoutManager textStorage];

/*    printf("*** layout some stuff |%@|\n", currentTextStorage);
    [currentLayoutManager _glyphDumpRuns];*/

  currentGlyphIndex = glyphIndex;

  [self _clearCache];

  realRet = 4;  /* Start with "unknown if new paragraph" state */
  currentPoint = NSMakePoint(0, NSMaxY(previousLineFragRect));
  while (1)
    {
      /* Determine if we're starting a new paragraph */
      if (realRet == 4)
        {
          /*
          -layoutLineNewParagraph: needs to know if the starting glyph is the
          first glyph of a paragraph so it can apply eg. -firstLineHeadIndent and
          paragraph spacing properly.
          */
          if (!currentGlyphIndex)
            {
              newParagraph = YES;  /* Very first glyph in text */
            }
          else
            {
              unsigned int charIndex;
              unichar character;
              charIndex = [currentLayoutManager characterRangeForGlyphRange: NSMakeRange(currentGlyphIndex - 1, 1)
                                                           actualGlyphRange: NULL].location;

              character = [[currentTextStorage string] characterAtIndex: charIndex];

              if (character == '\n')
                newParagraph = YES;  /* Previous character was newline */
              else
                newParagraph = NO;
            }
        }
      else if (realRet == 3)
        {
          newParagraph = YES;  /* Previous line ended with paragraph break */
        }
      else
        {
          newParagraph = NO;  /* Continuing current paragraph */
        }

      /* Layout one line of text */
      ret = [self layoutLineNewParagraph: newParagraph];

      /* Map internal return codes to standard ones */
      realRet = ret;
      if (ret == 3 || ret == 4)
        ret = 0;  /* These indicate successful line layout */

      /* Check for stop conditions */
      if (ret)
        break;  /* ret 1 (no room) or 2 (end of text) */

      if (howMany)
        if (!--howMany)
          break;  /* Completed requested number of lines */
   }

  *nextGlyphIndex = currentGlyphIndex;  /* Return where we stopped */
NS_HANDLER
  /* Log error and re-raise after unlocking */
  NSLog(@"GSHorizontalTypesetter - %@", [localException reason]);
  [lock unlock];
  [localException raise];
  ret = 0; /* This is never reached, but it shuts up the compiler. */
NS_ENDHANDLER
  [lock unlock];
  return ret;
}

@end

// CURRENT (incorrect):
else if ((character > 0x2ff0) && (character < 0x9fff))

// PROPOSED (comprehensive CJK support):
else if ((character >= 0x4E00 && character <= 0x9FFF) ||      // CJK Unified Ideographs
         (character >= 0x3400 && character <= 0x4DBF) ||      // CJK Extension A
         (character >= 0xAC00 && character <= 0xD7AF) ||      // Hangul Syllables
         (character >= 0x3040 && character <= 0x309F) ||      // Hiragana
         (character >= 0x30A0 && character <= 0x30FF) ||      // Katakana
         (character >= 0xFF65 && character <= 0xFF9F))       // Halfwidth Katakana

// CURRENT (confusing and potentially buggy):
if ([tab location] > position.x + lineFragment->rect.origin.x)
  break;
// ...
position.x = [tab location] - lineFragment->rect.origin.x;

// PROPOSED (clearer):
CGFloat absolutePosition = position.x + lineFragment->rect.origin.x;
if ([tab location] > absolutePosition)
  break;
// ...
position.x = [tab location] - lineFragment->rect.origin.x;

// PROPOSED: Add kerning cache to avoid repeated font metrics calls
struct {
    NSGlyph prevGlyph;
    NSGlyph currGlyph;
    float kernAdjustment;
} *kerningCache;
size_t kerningCacheSize;

// Use conservative kerning: only query when glyph pair changes
if (lastGlyph && lastGlyph != NSNullGlyph && glyphEntry->font == font) {
    float kern = [font advancementForGlyph: lastGlyph].width + 
                 [font advancementForGlyph: glyphEntry->glyph].width -
                 [font advancementForGlyphPair: lastGlyph : glyphEntry->glyph].width;
    if (kern != 0) {
        position.x += kern;
        glyphEntry->nominal = NO;
    }
}

// CURRENT:
#define CACHE_STEP 192
cacheSize = newLength;
glyphCache = realloc(glyphCache, sizeof(GlyphCacheEntry) * cacheSize);

// PROPOSED:
if (cacheSize < newLength) {
    cacheSize = MAX(newLength, cacheSize * 2);  // Exponential growth
    cacheSize = MAX(cacheSize, 64);             // Minimum allocation
    glyphCache = realloc(glyphCache, sizeof(GlyphCacheEntry) * cacheSize);
}

- (BOOL) _useSimpleRectangularLayout: (NSRect)proposedRect
                          lineHeight: (CGFloat)lineHeight
{
    if (![currentTextContainer isSimpleRectangularTextContainer])
        return NO;
    
    NSSize containerSize = [currentTextContainer containerSize];
    NSRect simpleRect = proposedRect;
    
    // Single rectangle for the entire width
    if (lineFragmentCount == 0) {
        lineFragmentCapacity = MAX(lineFragmentCapacity, 2);
        lineFragments = realloc(lineFragments, sizeof(LineFragment) * lineFragmentCapacity);
    }
    
    lineFragments[0].rect = simpleRect;
    lineFragmentCount = 1;
    
    // Skip the expensive lineFragmentRectForProposedRect: loop
    return YES;
}

// PROPOSED additions to header or file-static:
static const unichar kNewlineCharacter = 0x0A;
static const unichar kCarriageReturn = 0x0D;
static const unichar kTabCharacter = 0x09;
static const unichar kSpaceCharacter = 0x20;
static const CGFloat kDefaultTabInterval = 100.0;
static const CGFloat kMinimumLineHeight = 15.0;
static const NSUInteger kGlyphCacheInitialSize = 192;

// CURRENT: fontDescender is actually the positive value of descender
CGFloat fontDescender = -[font descender];  // Confusing: "descender" is positive

// PROPOSED:
CGFloat fontDescent = -[font descender];  // Clear: this is the descent magnitude

- (BOOL) _layoutGlyphsInCurrentLineFragment: ...;
- (BOOL) _handleControlCharacter: ...;
- (BOOL) _handleAttachment: ...;
- (void) _applyLineBreakMode: ...;
- (void) _commitLineToLayoutManager: ...;

// CURRENT: No validation that glyphEntry is within bounds
glyphEntry = glyphCache + index;

// PROPOSED:
NSAssert(index < cacheLength, @"Glyph index %u exceeds cache length %u", index, cacheLength);
if (index >= cacheLength) {
    // Graceful handling: trigger cache fill or return error
    [self _cacheGlyphsUpToLength: index + 1];
    if (index >= cacheLength) {
        // Handle failure case
        return YES;  // Request restart with adjusted parameters
    }
}
glyphEntry = glyphCache + index;

// CURRENT: No check if currentFont is nil
lineHeight = [glyphCache->font defaultLineHeightForFont];

// PROPOSED:
if (!glyphCache->font) {
    // Use system default font as fallback
    currentFont = [NSFont systemFontOfSize: 12.0];
    // Log warning in debug builds
    NSDebugLLog(@"GSHorizontalTypesetter", @"Missing font at glyph %u, using system default", cacheBase);
}

// PROPOSED: In GlyphCacheEntry, use __strong or retain explicitly
// Or better, store font index/identifier rather than pointer
struct GSHorizontalTypesetterGlyphCacheStruct {
    // ...
    NSUInteger fontIndex;  // Index into layout manager's font cache
    // ...
};

case NSLineBreakByTruncatingTail: {
    // Calculate if truncation is needed
    if (position.x + glyphEntry->size.width > lineFragment->rect.size.width) {
        // Find truncation glyph (ellipsis) and fit it
        NSGlyph ellipsisGlyph = [font glyphWithName: @"ellipsis"];
        CGFloat ellipsisWidth = [font advancementForGlyph: ellipsisGlyph].width;
        
        // Remove glyphs until ellipsis fits
        while (index > firstGlyphIndex && 
               glyphEntry[-1].position.x + ellipsisWidth > lineFragment->rect.size.width) {
            index--;
            glyphEntry--;
        }
        
        // Insert ellipsis
        glyphEntry->glyph = ellipsisGlyph;
        glyphEntry->position = position;
        glyphEntry->size.width = ellipsisWidth;
        glyphEntry->dontShow = NO;
        
        lineFragment->lastGlyphIndex = index + 1;
        *newParagraph = NO;
        return NO;  // Line is complete
    }
    break;
}

- (NSRect)_getProposedRectForNewParagraph: (BOOL)newParagraph
                           withLineHeight: (CGFloat) lineHeight
{
    // ...
    CGFloat padding = [currentTextContainer lineFragmentPadding];
    headIndent += padding;
    // tailIndent already accounts for padding in standard implementation
    // ...
}

// In layoutLineNewParagraph:, after completing a paragraph:
if (newParagraph) {
    CGFloat paragraphSpacing = [currentParagraphStyle paragraphSpacing];
    currentPoint.y += paragraphSpacing;  // Add space after paragraph
}

// In header:
@property (nonatomic, weak) GSLayoutManager *currentLayoutManager;
@property (nonatomic, weak) NSTextContainer *currentTextContainer;
// etc.

// CURRENT:
+ (GSHorizontalTypesetter *) sharedInstance;

// PROPOSED:
+ (instancetype) sharedInstance;

// CURRENT:
[NSDictionary dictionaryWithObject: value forKey: key]

// PROPOSED:
@{key: value}

// PROPOSED: Per-thread instances are already used, but add assertion
NSAssert([[NSThread currentThread] threadDictionary][@"sharedHorizontalTypesetter"] == self,
         @"Typesetter used from wrong thread without temp instance");