Optimize redrawing so that the mouse is more responsive, from Marc Espie.

[micropolis] / src / tk / tktxdisp.c

/* 
 * tkTextDisp.c --
 *
 *      This module provides facilities to display text widgets.  It is
 *      the only place where information is kept about the screen layout
 *      of text widgets.
 *
 * Copyright 1992 Regents of the University of California.
 * Permission to use, copy, modify, and distribute this
 * software and its documentation for any purpose and without
 * fee is hereby granted, provided that the above copyright
 * notice appear in all copies.  The University of California
 * makes no representations about the suitability of this
 * software for any purpose.  It is provided "as is" without
 * express or implied warranty.
 */

#ifndef lint
static char rcsid[] = "$Header: /user6/ouster/wish/RCS/tkTextDisp.c,v 1.20 92/08/24 09:24:18 ouster Exp $ SPRITE (Berkeley)";
#endif

#include "tkconfig.h"
#include "tkint.h"
#include "tktext.h"

#include <assert.h>

/*
 * The following structure describes how to display a range of characters.
 * The information is generated by scanning all of the tags associated
 * with the characters and combining that with default information for
 * the overall widget.  These structures form the hash keys for
 * dInfoPtr->styleTable.
 */

typedef struct StyleValues {
    Tk_3DBorder border;         /* Used for drawing background under text.
                                 * NULL means use widget background. */
    int borderWidth;            /* Width of 3-D border for background. */
    int relief;                 /* 3-D relief for background. */
    Pixmap bgStipple;           /* Stipple bitmap for background.  None
                                 * means draw solid. */
    XColor *fgColor;            /* Foreground color for text. */
    XFontStruct *fontPtr;       /* Font for displaying text. */
    Pixmap fgStipple;           /* Stipple bitmap for text and other
                                 * foreground stuff.   None means draw
                                 * solid.*/
    int underline;              /* Non-zero means draw underline underneath
                                 * text. */
} StyleValues;

/*
 * The following structure extends the StyleValues structure above with
 * graphics contexts used to actually draw the characters.  The entries
 * in dInfoPtr->styleTable point to structures of this type.
 */

typedef struct Style {
    int refCount;               /* Number of times this structure is
                                 * referenced in Chunks. */
    GC bgGC;                    /* Graphics context for background.  None
                                 * unless background is stippled. */
    GC fgGC;                    /* Graphics context for foreground. */
    StyleValues *sValuePtr;     /* Raw information from which GCs were
                                 * derived. */
    Tcl_HashEntry *hPtr;        /* Pointer to entry in styleTable.  Used
                                 * to delete entry. */
} Style;

/*
 * The following structure describes a range of characters, all on the
 * same line of the display (which also means the same line of the text
 * widget) and all having the same display attributes.
 */

typedef struct Chunk {
    char *text;                 /* Characters to display. */
    int numChars;               /* Number of characters to display. */
    Style *stylePtr;            /* Style information used to display
                                 * characters. */
    int x;                      /* X-coordinate of pixel at which to display
                                 * the characters. */
    struct Chunk *nextPtr;      /* Next in list of all chunks displayed on the
                                 * same display line. */
} Chunk;

/*
 * The following structure describes one line of the display, which may
 * be either part or all of one line of the text.
 */

typedef struct DLine {
    TkTextLine *linePtr;        /* Pointer to structure in B-tree that
                                 * contains characters displayed in this
                                 * line. */
    int y;                      /* Y-position at which line is supposed to
                                 * be drawn (topmost pixel of rectangular
                                 * area occupied by line). */
    int oldY;                   /* Y-position at which line currently
                                 * appears on display.  -1 means line isn't
                                 * currently visible on display.  This is
                                 * used to move lines by scrolling rather
                                 * than re-drawing. */
    int height;                 /* Height of line, in pixels. */
    int baseline;               /* Offset of text baseline from y. */
    Chunk *chunkPtr;            /* Pointer to first chunk in list of all
                                 * of those that are displayed on this
                                 * line of the screen. */
    struct DLine *nextPtr;      /* Next in list of all display lines for
                                 * this window.   The list is sorted in
                                 * order from top to bottom.  Note:  the
                                 * next DLine doesn't always correspond
                                 * to the next line of text:  (a) can have
                                 * multiple DLines for one text line, and
                                 * (b) can have gaps where DLine's have been
                                 * deleted because they're out of date. */
} DLine;

/*
 * Overall display information for a text widget:
 */

typedef struct DInfo {
    Tcl_HashTable styleTable;   /* Hash table that maps from StyleValues to
                                 * Styles for this widget. */
    DLine *dLinePtr;            /* First in list of all display lines for
                                 * this widget, in order from top to bottom. */
    GC copyGC;                  /* Graphics context for copying from off-
                                 * screen pixmaps onto screen. */
    GC scrollGC;                /* Graphics context for copying from one place
                                 * in the window to another (scrolling):
                                 * differs from copyGC in that we need to get
                                 * GraphicsExpose events. */
    int x;                      /* First x-coordinate that may be used for
                                 * actually displaying line information.
                                 * Leaves space for border, etc. */
    int y;                      /* First y-coordinate that may be used for
                                 * actually displaying line information.
                                 * Leaves space for border, etc. */
    int maxX;                   /* First x-coordinate to right of available
                                 * space for displaying lines. */
    int maxY;                   /* First y-coordinate to bottom of available
                                 * space for displaying lines. */
    int topOfEof;               /* Top-most pixel (lowest y-value) that has
                                 * been drawn in the appropriate fashion for
                                 * the portion of the window after the last
                                 * line of the text.  This field is used to
                                 * figure out when to redraw part or all of
                                 * the eof field. */
    int flags;                  /* Various flag values:  see below for
                                 * definitions. */
} DInfo;

/*
 * Flag values for DInfo structures:
 *
 * DINFO_OUT_OF_DATE:           Non-zero means that the DLine structures
 *                              for this window are partially or completely
 *                              out of date and need to be recomputed.
 * REDRAW_PENDING:              Means that a when-idle handler has been
 *                              scheduled to update the display.
 * REDRAW_BORDERS:              Means window border or pad area has
 *                              potentially been damaged and must be redrawn.
 * REPICK_NEEDED:               1 means that the widget has been modified
 *                              in a way that could change the current
 *                              character (a different character might be
 *                              under the mouse cursor now).  Need to
 *                              recompute the current character before
 *                              the next redisplay.
 */

#define DINFO_OUT_OF_DATE       1
#define REDRAW_PENDING          2
#define REDRAW_BORDERS          4
#define REPICK_NEEDED           8

/*
 * Structures of the type defined below are used to keep track of
 * tags while scanning through the text to create DLine structures.
 */

typedef struct TagInfo {
    int numTags;                /* Number of tags currently active (the first
                                 * entries at *tagPtr). */
    int arraySize;              /* Total number of entries at *tagPtr.  We
                                 * over-allocate the array to avoid continual
                                 * reallocations. */
    TkTextTag **tagPtrs;        /* Pointer to array of pointers to active tags.
                                 * Array has space for arraySize tags, and
                                 * the first numTags are slots identify the
                                 * active tags. Malloc'ed (but may be NULL). */
    TkTextSearch search;        /* Used to scan for tag transitions.  Current
                                 * state identifies next tag transition. */
} TagInfo;

/*
 * The following counters keep statistics about redisplay that can be
 * checked to see how clever this code is at reducing redisplays.
 */

static int numRedisplays;       /* Number of calls to DisplayText. */
static int linesRedrawn;        /* Number of calls to DisplayDLine. */
static int numCopies;           /* Number of calls to XCopyArea to copy part
                                 * of the screen. */
static int damagedCopies;       /* Number of times that XCopyAreas didn't
                                 * completely work because some of the source
                                 * information was damaged. */
static int TextUpdateTime = 100; // Added by Don.

/*
 * Forward declarations for procedures defined later in this file:
 */

static void             ComputeStyleValues _ANSI_ARGS_((TkText *textPtr,
                            int numTags, TkTextTag **tagPtr,
                            StyleValues *sValuePtr));
static void             DisplayDLine _ANSI_ARGS_((TkText *textPtr,
                            DLine *dlPtr, Pixmap pixmap));
static void             DisplayText _ANSI_ARGS_((ClientData clientData));
static DLine *          FindDLine _ANSI_ARGS_((DLine *dlPtr, int line));
static void             FreeDLines _ANSI_ARGS_((TkText *textPtr,
                            DLine *firstPtr, DLine *lastPtr, int unlink));
static void             FreeStyle _ANSI_ARGS_((Style *stylePtr));
static Style *          GetStyle _ANSI_ARGS_((TkText *textPtr,
                            StyleValues *sValuePtr));
static DLine *          LayoutLine _ANSI_ARGS_((TkText *textPtr, int line,
                            TkTextLine *linePtr, TagInfo *tInfoPtr));
static void             ToggleTag _ANSI_ARGS_((TagInfo *tInfoPtr,
                            TkTextTag *tagPtr));
static void             UpdateDisplayInfo _ANSI_ARGS_((TkText *textPtr));
\f
/*
 *----------------------------------------------------------------------
 *
 * TkTextCreateDInfo --
 *
 *      This procedure is called when a new text widget is created.
 *      Its job is to set up display-related information for the widget.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      A DInfo data structure is allocated and initialized and attached
 *      to textPtr.
 *
 *----------------------------------------------------------------------
 */

void
TkTextCreateDInfo(textPtr)
    TkText *textPtr;            /* Overall information for text widget. */
{
    register DInfo *dInfoPtr;
    XGCValues gcValues;

    dInfoPtr = (DInfo *) ckalloc(sizeof(DInfo));
    Tcl_InitHashTable(&dInfoPtr->styleTable, sizeof(StyleValues)/sizeof(int));
    dInfoPtr->dLinePtr = NULL;
    gcValues.graphics_exposures = False;
    dInfoPtr->copyGC = Tk_GetGC(textPtr->tkwin, GCGraphicsExposures, &gcValues);
    gcValues.graphics_exposures = True;
    dInfoPtr->scrollGC = Tk_GetGC(textPtr->tkwin, GCGraphicsExposures,
            &gcValues);
    dInfoPtr->topOfEof = 0;
    dInfoPtr->flags = DINFO_OUT_OF_DATE;
    textPtr->dInfoPtr = dInfoPtr;
}
\f
/*
 *----------------------------------------------------------------------
 *
 * TkTextFreeDInfo --
 *
 *      This procedure is called to free up all of the private display
 *      information kept by this file for a text widget.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      Lots of resources get freed.
 *
 *----------------------------------------------------------------------
 */

void
TkTextFreeDInfo(textPtr)
    TkText *textPtr;            /* Overall information for text widget. */
{
    register DInfo *dInfoPtr = textPtr->dInfoPtr;

    /*
     * Be careful to free up styleTable *after* freeing up all the
     * DLines, so that the hash table is still intact to free up the
     * style-related information from the lines.  Once the lines are
     * all free then styleTable will be empty.
     */

    FreeDLines(textPtr, dInfoPtr->dLinePtr, (DLine *) NULL, 1);
    Tcl_DeleteHashTable(&dInfoPtr->styleTable);
    Tk_FreeGC(dInfoPtr->copyGC);
    Tk_FreeGC(dInfoPtr->scrollGC);
    if (dInfoPtr->flags & REDRAW_PENDING) {
//      Tk_CancelIdleCall(DisplayText, (ClientData) textPtr);
        assert(textPtr->updateTimerToken != NULL);
        if (textPtr->updateTimerToken != NULL) {
            Tk_DeleteTimerHandler(textPtr->updateTimerToken);
            textPtr->updateTimerToken = NULL;
        }
    }
    ckfree((char *) dInfoPtr);
}
\f
/*
 *----------------------------------------------------------------------
 *
 * GetStyle --
 *
 *      This procedure creates graphics contexts needed to display
 *      text in a particular style, determined by "sValuePtr".  It
 *      attempts to share style information as much as possible.
 *
 * Results:
 *      The return value is a pointer to a Style structure that
 *      corresponds to *sValuePtr.
 *
 * Side effects:
 *      A new entry may be created in the style table for the widget.
 *
 *----------------------------------------------------------------------
 */

static Style *
GetStyle(textPtr, sValuePtr)
    TkText *textPtr;            /* Overall information about text widget. */
    StyleValues *sValuePtr;     /* Information about desired style. */
{
    Style *stylePtr;
    Tcl_HashEntry *hPtr;
    int new;
    XGCValues gcValues;
    unsigned long mask;

    /*
     * Use an existing style if there's one around that matches.
     */

    hPtr = Tcl_CreateHashEntry(&textPtr->dInfoPtr->styleTable,
            (char *) sValuePtr, &new);
    if (!new) {
        stylePtr = (Style *) Tcl_GetHashValue(hPtr);
        stylePtr->refCount++;
        return stylePtr;
    }

    /*
     * No existing style matched.  Make a new one.
     */

    stylePtr = (Style *) ckalloc(sizeof(Style));
    stylePtr->refCount = 1;
    if ((sValuePtr->border != NULL) && (sValuePtr->bgStipple != None)) {
        gcValues.foreground = Tk_3DBorderColor(sValuePtr->border)->pixel;
        gcValues.stipple = sValuePtr->bgStipple;
        gcValues.fill_style = FillStippled;
        stylePtr->bgGC = Tk_GetGC(textPtr->tkwin,
                GCForeground|GCStipple|GCFillStyle, &gcValues);
    } else {
        stylePtr->bgGC = None;
    }
    mask = GCForeground|GCFont;
    gcValues.foreground = sValuePtr->fgColor->pixel;
    gcValues.font = sValuePtr->fontPtr->fid;
    if (sValuePtr->fgStipple != None) {
        gcValues.stipple = sValuePtr->fgStipple;
        gcValues.fill_style = FillStippled;
        mask |= GCStipple|GCFillStyle;
    }
    stylePtr->fgGC = Tk_GetGC(textPtr->tkwin, mask, &gcValues);
    stylePtr->sValuePtr = (StyleValues *)
            Tcl_GetHashKey(&textPtr->dInfoPtr->styleTable, hPtr);
    stylePtr->hPtr = hPtr;
    Tcl_SetHashValue(hPtr, stylePtr);
    return stylePtr;
}
\f
/*
 *----------------------------------------------------------------------
 *
 * FreeStyle --
 *
 *      This procedure is called when a Style structure is no longer
 *      needed.  It decrements the reference count and frees up the
 *      space for the style structure if the reference count is 0.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      The storage and other resources associated with the style
 *      are freed up if no-one's still using it.
 *
 *----------------------------------------------------------------------
 */

static void
FreeStyle(stylePtr)
    register Style *stylePtr;   /* Information about style to be freed. */

{
    stylePtr->refCount--;
    if (stylePtr->refCount == 0) {
        if (stylePtr->bgGC != None) {
            Tk_FreeGC(stylePtr->bgGC);
        }
        Tk_FreeGC(stylePtr->fgGC);
        Tcl_DeleteHashEntry(stylePtr->hPtr);
        ckfree((char *) stylePtr);
    }
}
\f
/*
 *----------------------------------------------------------------------
 *
 * ComputeStyleValues --
 *
 *      Given a list of tags that apply at a particular point, compute
 *      the StyleValues that correspond to that set of tags.
 *
 * Results:
 *      All of the fields of *sValuePtr get filled in to hold the
 *      appropriate display information for the given set of tags
 *      in the given widget.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */

static void
ComputeStyleValues(textPtr, numTags, tagPtrPtr, sValuePtr)
    TkText *textPtr;                    /* Overall information for widget. */
    int numTags;                        /* Number of tags at *tagPtr. */
    register TkTextTag **tagPtrPtr;     /* Pointer to array of tag pointers. */
    register StyleValues *sValuePtr;    /* Pointer to structure to fill in. */
{
    register TkTextTag *tagPtr;

    /*
     * The variables below keep track of the highest-priority specification
     * that has occurred for each of the various fields of the StyleValues.
     */

    int borderPrio, bgStipplePrio;
    int fgPrio, fontPrio, fgStipplePrio;

    borderPrio = bgStipplePrio = -1;
    fgPrio = fontPrio = fgStipplePrio = -1;
    memset((VOID *) sValuePtr, 0, sizeof(StyleValues));
    sValuePtr->fgColor = textPtr->fgColor;
    sValuePtr->fontPtr = textPtr->fontPtr;

    /*
     * Scan through all of the tags, updating the StyleValues to hold
     * the highest-priority information.
     */

    for ( ; numTags > 0; tagPtrPtr++, numTags--) {
        tagPtr = *tagPtrPtr;
        if ((tagPtr->border != NULL) && (tagPtr->priority > borderPrio)) {
            sValuePtr->border = tagPtr->border;
            sValuePtr->borderWidth = tagPtr->borderWidth;
            sValuePtr->relief = tagPtr->relief;
            borderPrio = tagPtr->priority;
        }
        if ((tagPtr->bgStipple != None)
                && (tagPtr->priority > bgStipplePrio)) {
            sValuePtr->bgStipple = tagPtr->bgStipple;
            bgStipplePrio = tagPtr->priority;
        }
        if ((tagPtr->fgColor != None) && (tagPtr->priority > fgPrio)) {
            sValuePtr->fgColor = tagPtr->fgColor;
            fgPrio = tagPtr->priority;
        }
        if ((tagPtr->fontPtr != None) && (tagPtr->priority > fontPrio)) {
            sValuePtr->fontPtr = tagPtr->fontPtr;
            fontPrio = tagPtr->priority;
        }
        if ((tagPtr->fgStipple != None)
                && (tagPtr->priority > fgStipplePrio)) {
            sValuePtr->fgStipple = tagPtr->fgStipple;
            fgStipplePrio = tagPtr->priority;
        }
        if (tagPtr->underline) {
            sValuePtr->underline = 1;
        }
    }
}
\f
/*
 *----------------------------------------------------------------------
 *
 * LayoutLine --
 *
 *      This procedure generates a linked list of one or more DLine
 *      structures, which describe how to display everything in one
 *      line of the text.
 *
 * Results:
 *      The return value is a pointer to one or more DLine structures
 *      linked into a linked list.  The structures are completely filled
 *      in except for the y field, which the caller must supply.  Also,
 *      the information at *tInfoPtr gets updated to refer to the state
 *      just after the last character of the line.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */

static DLine *
LayoutLine(textPtr, line, linePtr, tInfoPtr)
    TkText *textPtr;            /* Overall information about text widget. */
    int line;                   /* Index of line to layout. */
    TkTextLine *linePtr;        /* Line to layout (corresponds to line). */
    TagInfo *tInfoPtr;          /* Information to help keep track of tags.
                                 * Caller must have initialized to correspond
                                 * to state just before start of line. */
{
    DLine *firstLinePtr;
    DLine *lastLinePtr = NULL;  /* Initializations needed only to stop */
    Chunk *lastChunkPtr = NULL; /* compiler warnings. */
    register DLine *dlPtr;
    register Chunk *chunkPtr;
    StyleValues styleValues;
    int ch, charsThatFit, ascent, descent, x, maxX;

    firstLinePtr = NULL;

    /*
     * Each iteration of the loop below creates one DLine structure.
     */

    ch = 0;
    while (1) {

        /*
         * Create and initialize a new DLine structure.
         */

        dlPtr = (DLine *) ckalloc(sizeof(DLine));
        dlPtr->linePtr = linePtr;
        dlPtr->y = 0;
        dlPtr->oldY = -1;
        dlPtr->chunkPtr = NULL;
        dlPtr->nextPtr = NULL;
        if (firstLinePtr == NULL) {
            firstLinePtr = dlPtr;
        } else {
            lastLinePtr->nextPtr = dlPtr;
        }
        lastLinePtr = dlPtr;

        /*
         * Each iteration of the loop below creates one Chunk for the
         * new display line.
         */

        x = textPtr->dInfoPtr->x;
        maxX = textPtr->dInfoPtr->maxX;
        ascent = descent = 0;
        while (x < maxX) {
            chunkPtr = (Chunk *) ckalloc(sizeof(Chunk));
            chunkPtr->numChars = linePtr->numBytes - ch;
            chunkPtr->text = linePtr->bytes + ch;
            chunkPtr->x = x;
            chunkPtr->nextPtr = NULL;
            if (dlPtr->chunkPtr == NULL) {
                dlPtr->chunkPtr = chunkPtr;
            } else {
                lastChunkPtr->nextPtr = chunkPtr;
            }
            lastChunkPtr = chunkPtr;

            /*
             * Update the tag array to include any tag transitions up
             * through the current position, then find the next position
             * with a transition on a tag that impacts the way things are
             * displayed.
             */

            while (1) {
                int affectsDisplay;
                TkTextTag *tagPtr;

                if ((tInfoPtr->search.linePtr == NULL)
                        || (tInfoPtr->search.line1 > line)) {
                    break;
                }
                tagPtr = tInfoPtr->search.tagPtr;
                affectsDisplay = TK_TAG_AFFECTS_DISPLAY(tagPtr);
                if ((tInfoPtr->search.line1 < line)
                        || (tInfoPtr->search.ch1 <= ch)) {
                    if (affectsDisplay) {
                        ToggleTag(tInfoPtr, tagPtr);
                    }
                } else {
                    if (affectsDisplay) {
                        chunkPtr->numChars = tInfoPtr->search.ch1 - ch;
                        break;
                    }
                }
                (void) TkBTreeNextTag(&tInfoPtr->search);
            }

            /*
             * Create style information for this chunk.
             */

            ComputeStyleValues(textPtr, tInfoPtr->numTags, tInfoPtr->tagPtrs,
                    &styleValues);
            chunkPtr->stylePtr = GetStyle(textPtr, &styleValues);

            /*
             * See how many characters will fit on the line.  If they don't
             * all fit, then a number of compensations may have to be made.
             *
             * 1. Make sure that at least one character is displayed on
             *    each line.
             * 2. In wrap mode "none", allow a partial character to be
             *    displayed at the end of an incomplete line.
             * 3. In wrap mode "word", search back to find the last space
             *    character, and terminate the line just after that space
             *    character.  This involves a couple of extra complexities:
             *        - the last space may be several chunks back;  in this
             *          case, delete all the chunks that are after the
             *          space.
             *        - if no words fit at all, then use character-wrap for
             *          this DLine.
             *        - have to reinitialize the tag search information, since
             *          we may back up over tag toggles (they'll need to be
             *          reconsidered on the next DLine).
             */

            charsThatFit = TkMeasureChars(styleValues.fontPtr,
                    chunkPtr->text, chunkPtr->numChars, chunkPtr->x,
                    maxX, 0, &x);
            if ((charsThatFit < chunkPtr->numChars) || (x >= maxX)) {
                x = maxX;
                chunkPtr->numChars = charsThatFit;
                ch += charsThatFit;
                if (ch < (linePtr->numBytes - 1)) {
                    if ((charsThatFit == 0) && (chunkPtr == dlPtr->chunkPtr)) {
                        chunkPtr->numChars = 1;
                        ch++;
                    } else if (textPtr->wrapMode == tkTextWordUid) {
                        if (isspace(chunkPtr->text[charsThatFit])) {
                            ch += 1;    /* Include space on this line. */
                        } else {
                            register Chunk *chunkPtr2;
                            register char *p;
                            Chunk *spaceChunkPtr;
                            int count, space;

                            spaceChunkPtr = NULL;
                            space = 0;
                            for (chunkPtr2 = dlPtr->chunkPtr;
                                    chunkPtr2 != NULL;
                                    chunkPtr2 = chunkPtr2->nextPtr) {
                                for (count = chunkPtr2->numChars - 1,
                                        p = chunkPtr2->text + count;
                                        count >= 0; count--, p--) {
                                    if (isspace(*p)) {
                                        spaceChunkPtr = chunkPtr2;
                                        space = count;
                                        break;
                                    }
                                }
                            }
                            if (spaceChunkPtr != NULL) {
                                spaceChunkPtr->numChars = space;
                                ch = (spaceChunkPtr->text + space + 1)
                                        - linePtr->bytes;
                                if (chunkPtr != spaceChunkPtr) {
                                    chunkPtr = spaceChunkPtr;
                                    if (tInfoPtr->tagPtrs != NULL) {
                                        ckfree((char *) tInfoPtr->tagPtrs);
                                    }
                                    tInfoPtr->tagPtrs = TkBTreeGetTags(
                                            textPtr->tree, dlPtr->linePtr, ch,
                                            &tInfoPtr->numTags);
                                    TkBTreeStartSearch(textPtr->tree, line,
                                            ch+1,
                                            TkBTreeNumLines(textPtr->tree), 0,
                                            (TkTextTag *) NULL,
                                            &tInfoPtr->search);
                                    (void) TkBTreeNextTag(&tInfoPtr->search);
                                    tInfoPtr->arraySize = tInfoPtr->numTags;
                                    while (chunkPtr->nextPtr != NULL) {
                                        chunkPtr2 = chunkPtr->nextPtr;
                                        chunkPtr->nextPtr = chunkPtr2->nextPtr;
                                        FreeStyle(chunkPtr2->stylePtr);
                                        ckfree((char *) chunkPtr2);
                                    }
                                }
                            }
                        }
                    } else if (textPtr->wrapMode == tkTextNoneUid) {
                        chunkPtr->numChars++;
                        ch++;
                    }
                }
            } else {
                ch += chunkPtr->numChars;
            }

            /*
             * Update height information for use later in computing
             * line's overall height and baseline.
             */

            if (styleValues.fontPtr->ascent > ascent) {
                ascent = styleValues.fontPtr->ascent;
            }
            if (styleValues.fontPtr->descent > descent) {
                descent = styleValues.fontPtr->descent;
            }
        }

        dlPtr->height = ascent + descent;
        dlPtr->baseline = ascent;

        /*
         * Quit when every character but the last character (the newline)
         * has been accounted for.  Also quit if the wrap mode is "none":
         * this ignores all the characters that don't fit on the first
         * line.
         */

        if ((ch >= (linePtr->numBytes-1))
                || (textPtr->wrapMode == tkTextNoneUid)) {
            break;
        }
    }
    return firstLinePtr;
}
\f
/*
 *----------------------------------------------------------------------
 *
 * ToggleTag --
 *
 *      Update information about tags to reflect a transition on a
 *      particular tag.
 *
 * Results:
 *      The array at *tInfoPtr is modified to include tagPtr if it
 *      didn't already or to exclude it if it used to include it.
 *      The array will be reallocated to a larger size if needed.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */

static void
ToggleTag(tInfoPtr, tagPtr)
    register TagInfo *tInfoPtr;         /* Tag information to be updated. */
    TkTextTag *tagPtr;                  /* Tag to be toggled into or out of
                                         * *tInfoPtr. */
{
    register TkTextTag **tagPtrPtr;
    int i;

    for (i = tInfoPtr->numTags, tagPtrPtr = tInfoPtr->tagPtrs;
            i > 0; i--, tagPtrPtr++) {
        if (*tagPtrPtr == tagPtr) {
            tInfoPtr->numTags--;
            *tagPtrPtr = tInfoPtr->tagPtrs[tInfoPtr->numTags];
            return;
        }
    }

    /*
     * Tag not currently in array.  Grow the array if necessary, then
     * add the tag to it.
     */

    if (tInfoPtr->numTags == tInfoPtr->arraySize) {
        TkTextTag **newPtrs;

        newPtrs = (TkTextTag **) ckalloc((unsigned)
                ((tInfoPtr->arraySize+10) * sizeof(TkTextTag *)));
        if (tInfoPtr->tagPtrs != NULL) {
            memcpy((VOID *) newPtrs, (VOID *) tInfoPtr->tagPtrs,
                    tInfoPtr->arraySize * sizeof(TkTextTag *));
            ckfree((char *) tInfoPtr->tagPtrs);
        }
        tInfoPtr->tagPtrs = newPtrs;
        tInfoPtr->arraySize += 10;
    }
    tInfoPtr->tagPtrs[tInfoPtr->numTags] = tagPtr;
    tInfoPtr->numTags++;
}
\f
/*
 *----------------------------------------------------------------------
 *
 * UpdateDisplayInfo --
 *
 *      This procedure is invoked to recompute some or all of the
 *      DLine structures for a text widget.  At the time it is called
 *      the DLine structures still left in the widget are guaranteed
 *      to be correct (except for their y-coordinates), but there may
 *      be missing structures (the DLine structures get removed as
 *      soon as they are potentially out-of-date).
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      Upon return, the DLine information for textPtr correctly reflects
 *      the positions where characters will be displayed.  However, this
 *      procedure doesn't actually bring the display up-to-date.
 *
 *----------------------------------------------------------------------
 */

static void
UpdateDisplayInfo(textPtr)
    TkText *textPtr;            /* Text widget to update. */
{
    register DInfo *dInfoPtr = textPtr->dInfoPtr;
    register DLine *dlPtr, *prevPtr, *dlPtr2;
    TkTextLine *linePtr;
    TagInfo tagInfo;
    int line, y, maxY;

    if (!(dInfoPtr->flags & DINFO_OUT_OF_DATE)) {
        return;
    }
    dInfoPtr->flags &= ~DINFO_OUT_OF_DATE;

    linePtr = textPtr->topLinePtr;
    dlPtr = dInfoPtr->dLinePtr;
    tagInfo.tagPtrs = TkBTreeGetTags(textPtr->tree, linePtr, 0,
            &tagInfo.numTags);
    tagInfo.arraySize = tagInfo.numTags;

    /*
     * Tricky point:  initialize the tag search just *after* the first
     * character in the line, since the tagInfo structure already has all
     * the tags for the first character.
     */

    line = TkBTreeLineIndex(linePtr);
    TkBTreeStartSearch(textPtr->tree, line, 1, TkBTreeNumLines(textPtr->tree),
            0, (TkTextTag *) NULL, &tagInfo.search);
    TkBTreeNextTag(&tagInfo.search);
    prevPtr = NULL;
    y = dInfoPtr->y;
    maxY = dInfoPtr->maxY;
    while ((linePtr != NULL) && (y < maxY)) {
        register DLine *newPtr;
        /*
         * See if the next DLine matches the next line we want to
         * appear on the screen.  If so then we can just use its
         * information.  If not then create new DLine structures
         * for the desired line and insert them into the list.
         */

        if ((dlPtr == NULL) || (dlPtr->linePtr != linePtr)) {
            newPtr = LayoutLine(textPtr, line, linePtr, &tagInfo);
            if (prevPtr == NULL) {
                dInfoPtr->dLinePtr = newPtr;
            } else {
                prevPtr->nextPtr = newPtr;
            }
            for (dlPtr2 = newPtr; dlPtr2->nextPtr != NULL;
                    dlPtr2 = dlPtr2->nextPtr) {
                /* Empty loop body. */
            }
            dlPtr2->nextPtr = dlPtr;
            dlPtr = newPtr;
        }

        /*
         * Skip to the next line, and update the y-position while
         * skipping.
         */

        do {
            dlPtr->y = y;
            y += dlPtr->height;
            prevPtr = dlPtr;
            dlPtr = dlPtr->nextPtr;
        } while ((dlPtr != NULL) && (dlPtr->linePtr == linePtr));
        linePtr = TkBTreeNextLine(linePtr);
        line++;
    }

    /*
     * Delete any DLine structures that don't fit on the screen and free
     * up the tag array.
     */

    FreeDLines(textPtr, dlPtr, (DLine *) NULL, 1);
    if (tagInfo.tagPtrs != NULL) {
        ckfree((char *) tagInfo.tagPtrs);
    }

    /*
     * Update the vertical scrollbar, if there is one.
     */

    if (textPtr->yScrollCmd != NULL) {
        int numLines, first, result, maxY, height;
        char string[60];

        /*
         * Count the number of text lines on the screen.
         */

        maxY = 0;
        for (numLines = 0, linePtr = NULL, dlPtr = dInfoPtr->dLinePtr;
                dlPtr != NULL; dlPtr = dlPtr->nextPtr) {
            if (dlPtr->linePtr != linePtr) {
                numLines++;
                linePtr = dlPtr->linePtr;
            }
            maxY = dlPtr->y + dlPtr->height;
        }

        /*
         * If the screen isn't completely full, then estimate the number of
         * lines that would fit on it if it were full.
         */

        height = dInfoPtr->maxY - dInfoPtr->y;
        if (numLines == 0) {
            numLines = height /
                    (textPtr->fontPtr->ascent + textPtr->fontPtr->descent);
        } else if (maxY < height) {
            numLines = (numLines * height)/maxY;
        }
        /* DEH: be reasonable if dLinePtr is null */
        if (dInfoPtr->dLinePtr == NULL) {
          sprintf(string, " 0 0 0 0");
        } else {
          first = TkBTreeLineIndex(dInfoPtr->dLinePtr->linePtr);
          sprintf(string, " %d %d %d %d", TkBTreeNumLines(textPtr->tree),
                  numLines, first, first+numLines-1);
        }
        result = Tcl_VarEval(textPtr->interp, textPtr->yScrollCmd, string,
                (char *) NULL);
        if (result != TCL_OK) {
            TkBindError(textPtr->interp);
        }
    }
}
\f
/*
 *----------------------------------------------------------------------
 *
 * FreeDLines --
 *
 *      This procedure is called to free up all of the resources
 *      associated with one or more DLine structures.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      Memory gets freed and various other resources are released.
 *
 *----------------------------------------------------------------------
 */

static void
FreeDLines(textPtr, firstPtr, lastPtr, unlink)
    TkText *textPtr;                    /* Information about overall text
                                         * widget. */
    register DLine *firstPtr;           /* Pointer to first DLine to free up. */
    DLine *lastPtr;                     /* Pointer to DLine just after last
                                         * one to free (NULL means everything
                                         * starting with firstPtr). */
    int unlink;                         /* 1 means DLines are currently linked
                                         * into the list rooted at
                                         * textPtr->dInfoPtr->dLinePtr and
                                         * they have to be unlinked.  0 means
                                         * just free without unlinking. */
{
    register Chunk *chunkPtr, *nextChunkPtr;
    register DLine *nextDLinePtr;

    if (unlink) {
        if (textPtr->dInfoPtr->dLinePtr == firstPtr) {
            textPtr->dInfoPtr->dLinePtr = lastPtr;
        } else {
            register DLine *prevPtr;
            for (prevPtr = textPtr->dInfoPtr->dLinePtr;
                    prevPtr->nextPtr != firstPtr; prevPtr = prevPtr->nextPtr) {
                /* Empty loop body. */
            }
            prevPtr->nextPtr = lastPtr;
        }
    }
    while (firstPtr != lastPtr) {
        nextDLinePtr = firstPtr->nextPtr;
        for (chunkPtr = firstPtr->chunkPtr; chunkPtr != NULL;
                chunkPtr = nextChunkPtr) {
            FreeStyle(chunkPtr->stylePtr);
            nextChunkPtr = chunkPtr->nextPtr;
            ckfree((char *) chunkPtr);
        }
        ckfree((char *) firstPtr);
        firstPtr = nextDLinePtr;
    }
}
\f
/*
 *----------------------------------------------------------------------
 *
 * DisplayDLine --
 *
 *      This procedure is invoked to draw a single line on the
 *      screen.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      The line given by dlPtr is drawn at its correct position in
 *      textPtr's window.  Note that this is one *display* line, not
 *      one *text* line.
 *
 *----------------------------------------------------------------------
 */

static void
DisplayDLine(textPtr, dlPtr, pixmap)
    TkText *textPtr;            /* Text widget in which to draw line. */
    register DLine *dlPtr;      /* Information about line to draw. */
    Pixmap pixmap;              /* Pixmap to use for double-buffering.
                                 * Caller must make sure it's large enough
                                 * to hold line. */
{
    register Style *stylePtr;
    register StyleValues *sValuePtr;
    register Chunk *chunkPtr;
    DInfo *dInfoPtr = textPtr->dInfoPtr;
    Display *display;
    int width, height, count, x;
    XFontStruct *fontPtr;

    /*
     * First, clear the area of the line to the background color for the
     * text widget.
     */

    display = Tk_Display(textPtr->tkwin);
    Tk_Fill3DRectangle(display, pixmap, textPtr->border, 0, 0,
            Tk_Width(textPtr->tkwin), dlPtr->height, 0, TK_RELIEF_FLAT);

    /*
     * Next, cycle through all of the chunks in the line displaying
     * backgrounds.  We need to do two passes, one for the backgrounds
     * and one for the characters, because some characters (e.g. italics
     * with heavy slants) may cross background boundaries.  If some
     * backgrounds are drawn after some text, the later backgrounds may
     * obliterate parts of earlier characters.
     */

    for (chunkPtr = dlPtr->chunkPtr; chunkPtr != NULL;
            chunkPtr = chunkPtr->nextPtr) {

        /*
         * Draw a special background for this chunk if one is specified
         * in its style.  Two tricks here:
         * 1. if this is the last chunk in the line then extend the
         *    background across to the end of the line.
         * 2. if the background is stippled, then we have to draw the
         *    stippled part specially, since Tk_Fill3DRectangle doesn't
         *    do stipples.
         */

        stylePtr = chunkPtr->stylePtr;
        sValuePtr = stylePtr->sValuePtr;
        if (sValuePtr->border != NULL) {
            if (chunkPtr->nextPtr != NULL) {
                width = chunkPtr->nextPtr->x - chunkPtr->x;
            } else {
                width = Tk_Width(textPtr->tkwin) - chunkPtr->x;
            }
            if (stylePtr->bgGC != NULL) {
                XFillRectangle(display, pixmap, stylePtr->bgGC, chunkPtr->x,
                        0, (unsigned int) width, (unsigned int) dlPtr->height);
                Tk_Draw3DRectangle(display, pixmap, sValuePtr->border,
                        chunkPtr->x, 0, width, dlPtr->height,
                        sValuePtr->borderWidth, sValuePtr->relief);
            } else {
                Tk_Fill3DRectangle(display, pixmap, sValuePtr->border,
                        chunkPtr->x, 0, width, dlPtr->height,
                        sValuePtr->borderWidth, sValuePtr->relief);
            }
        }
    }

    /*
     * If the insertion cursor is displayed on this line, then draw it
     * now, on top of the background but before the text.  As a special
     * workaround to keep the cursor visible on mono displays, write the default
     * background in the cursor area (instead of nothing) when the cursor
     * isn't on.  Otherwise the selection would hide the cursor.
     */

    if ((textPtr->insertAnnotPtr->linePtr == dlPtr->linePtr)
            && (textPtr->state == tkTextNormalUid)
            && (textPtr->flags & GOT_FOCUS)) {
        for (chunkPtr = dlPtr->chunkPtr; chunkPtr != NULL;
                chunkPtr = chunkPtr->nextPtr) {
            count = textPtr->insertAnnotPtr->ch
                    - (chunkPtr->text - dlPtr->linePtr->bytes);
            if (count < 0) {
                break;
            }
            if (count > chunkPtr->numChars) {
                continue;
            }

            /*
             * Deciding whether to display the cursor just after the last
             * character in a line is tricky because of various wrap
             * modes.  Do it unless we're in character wrap mode and
             * this line wraps, in which case it's better to display the
             * cursor on the next line.  For word wrap, there's an
             * undisplayed space character that the user must be able to
             * position the cursor in front of.  For no wrap, there's no
             * next line on which to display the cursor.
             */
            if ((count == chunkPtr->numChars)
                    && (textPtr->wrapMode == tkTextCharUid)
                    && (chunkPtr->text[count] != '\n')) {
                continue;
            }
            fontPtr = chunkPtr->stylePtr->sValuePtr->fontPtr;
            TkMeasureChars(fontPtr, chunkPtr->text, count, chunkPtr->x,
                    (int) 1000000, 0, &x);
            if (textPtr->flags & INSERT_ON) {
                Tk_Fill3DRectangle(display, pixmap, textPtr->insertBorder,
                        x - textPtr->insertWidth/2,
                        dlPtr->baseline - fontPtr->ascent,
                        textPtr->insertWidth,
                        fontPtr->ascent + fontPtr->descent,
                        textPtr->insertBorderWidth, TK_RELIEF_RAISED);
            } else if (Tk_DefaultDepth(Tk_Screen(textPtr->tkwin)) == 1) {
                Tk_Fill3DRectangle(display, pixmap, textPtr->border,
                        x - textPtr->insertWidth/2,
                        dlPtr->baseline - fontPtr->ascent,
                        textPtr->insertWidth,
                        fontPtr->ascent + fontPtr->descent,
                        0, TK_RELIEF_FLAT);
            }

        }
    }

    /*
     * Make another pass through all of the chunks to redraw all of
     * the text (and underlines, etc., if they're wanted).
     */

    for (chunkPtr = dlPtr->chunkPtr; chunkPtr != NULL;
            chunkPtr = chunkPtr->nextPtr) {
        stylePtr = chunkPtr->stylePtr;
        sValuePtr = stylePtr->sValuePtr;
        if (chunkPtr->numChars > 0) {
            TkDisplayChars(display, pixmap, stylePtr->fgGC, sValuePtr->fontPtr,
                    chunkPtr->text, chunkPtr->numChars, chunkPtr->x,
                    dlPtr->baseline, 0);
            if (sValuePtr->underline) {
                TkUnderlineChars(display, pixmap, stylePtr->fgGC,
                        sValuePtr->fontPtr, chunkPtr->text, chunkPtr->x,
                        dlPtr->baseline, 0, 0, chunkPtr->numChars-1);
            }
        }
    }

    /*
     * Copy the pixmap onto the screen.  If this is the last line on
     * the screen, only copy a piece of the line, so that it doesn't
     * overflow into the border area.  Another special trick:  copy the
     * padding area to the left of the line;  this is because the
     * insertion cursor sometimes overflows onto that area and we want
     * to get as much of the cursor as possible.
     */

    height = dlPtr->height;
    if ((height + dlPtr->y) > dInfoPtr->maxY) {
        height = dInfoPtr->maxY - dlPtr->y;
    }
    XCopyArea(display, pixmap, Tk_WindowId(textPtr->tkwin),
            dInfoPtr->copyGC, dInfoPtr->x - textPtr->padX, 0,
            dInfoPtr->maxX - (dInfoPtr->x - textPtr->padX),
            height, dInfoPtr->x - textPtr->padX, dlPtr->y);
    linesRedrawn++;
}
\f
/*
 *----------------------------------------------------------------------
 *
 * DisplayText --
 *
 *      This procedure is invoked as a when-idle handler to update the
 *      display.  It only redisplays the parts of the text widget that
 *      are out of date.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      Information is redrawn on the screen.
 *
 *----------------------------------------------------------------------
 */

static void
DisplayText(clientData)
    ClientData clientData;      /* Information about widget. */
{
    register TkText *textPtr = (TkText *) clientData;
    DInfo *dInfoPtr = textPtr->dInfoPtr;
    Tk_Window tkwin;
    register DLine *dlPtr;
    Pixmap pixmap;
    int maxHeight;
    int bottomY = 0;            /* Initialization needed only to stop
                                 * compiler warnings. */

    assert(textPtr->updateTimerToken != NULL);
    
    textPtr->updateTimerToken = 0;

    if ((textPtr->tkwin == NULL) || !Tk_IsMapped(textPtr->tkwin)
            || (dInfoPtr->maxX <= dInfoPtr->x)
            || (dInfoPtr->maxY <= dInfoPtr->y)) {
        goto done;
    }
    numRedisplays++;

    /*
     * Choose a new current item if that is needed (this could cause
     * event handlers to be invoked, hence the preserve/release calls
     * and the loop, since the handlers could conceivably necessitate
     * yet another current item calculation).  The tkwin check is because
     * the whole window could go away in the Tk_Release call.
     */

    while (dInfoPtr->flags & REPICK_NEEDED) {
        Tk_Preserve((ClientData) textPtr);
        dInfoPtr->flags &= ~REPICK_NEEDED;
        TkTextPickCurrent(textPtr, &textPtr->pickEvent);
        tkwin = textPtr->tkwin;
        Tk_Release((ClientData) textPtr);
        if (tkwin == NULL) {
            return;
        }
    }

    /*
     * First recompute what's supposed to be displayed.
     */

    UpdateDisplayInfo(textPtr);

    /*
     * Redraw the borders if that's needed.
     */

    if (dInfoPtr->flags & REDRAW_BORDERS) {
        Tk_Draw3DRectangle(Tk_Display(textPtr->tkwin),
                Tk_WindowId(textPtr->tkwin), textPtr->border,
                0, 0, Tk_Width(textPtr->tkwin), Tk_Height(textPtr->tkwin),
                textPtr->borderWidth, textPtr->relief);
    }

    /*
     * See if it's possible to bring some parts of the screen up-to-date
     * by scrolling (copying from other parts of the screen).
     */

    for (dlPtr = dInfoPtr->dLinePtr; dlPtr != NULL; dlPtr = dlPtr->nextPtr) {
        register DLine *dlPtr2;
        int offset, height;

        if ((dlPtr->oldY == -1) || (dlPtr->y == dlPtr->oldY)
                || ((dlPtr->oldY + dlPtr->height) > dInfoPtr->maxY)) {
            continue;
        }

        /*
         * This line is already drawn somewhere in the window so it only
         * needs to be copied to its new location.  See if there's a group
         * of lines that can all be copied together.
         */

        offset = dlPtr->y - dlPtr->oldY;
        height = dlPtr->height;
        for (dlPtr2 = dlPtr->nextPtr; dlPtr2 != NULL;
                dlPtr2 = dlPtr2->nextPtr) {
            if ((dlPtr2->oldY == -1)
                    || ((dlPtr2->oldY + offset) != dlPtr2->y)
                    || ((dlPtr2->oldY + dlPtr2->height) > dInfoPtr->maxY)) {
                break;
            }
            height += dlPtr2->height;
        }

        /*
         * Copy the information and update the lines to show that they've
         * been copied.  Reduce the height of the area being copied if
         * necessary to avoid overwriting the border area.
         */

        if ((dlPtr->y + height) > dInfoPtr->maxY) {
            height = dInfoPtr->maxY - dlPtr->y;
        }
        XCopyArea(Tk_Display(textPtr->tkwin), Tk_WindowId(textPtr->tkwin),
                Tk_WindowId(textPtr->tkwin), dInfoPtr->scrollGC,
                dInfoPtr->x - textPtr->padX, dlPtr->oldY,
                dInfoPtr->maxX - (dInfoPtr->x - textPtr->padX),
                height, dInfoPtr->x - textPtr->padX, dlPtr->y);
        numCopies++;
        while (1) {
            dlPtr->oldY = dlPtr->y;
            if (dlPtr->nextPtr == dlPtr2) {
                break;
            }
            dlPtr = dlPtr->nextPtr;
        }

        /*
         * It's possible that part of the area copied above was obscured.
         * To handle this situation, read expose-related events generated
         * during the XCopyArea operation.
         */

        while (1) {
            XEvent event;

            XWindowEvent(Tk_Display(textPtr->tkwin),
                    Tk_WindowId(textPtr->tkwin), ExposureMask, &event);
            if (event.type == NoExpose) {
                break;
            } else if (event.type == GraphicsExpose) {
                TkTextRedrawRegion(textPtr, event.xgraphicsexpose.x,
                        event.xgraphicsexpose.y, event.xgraphicsexpose.width,
                        event.xgraphicsexpose.height);
                if (event.xgraphicsexpose.count == 0) {
                    damagedCopies++;
                    break;
                }
            } else if (event.type == Expose) {
                /*
                 * A tricky situation.  This event must already have been
                 * queued up before the XCopyArea was issued.  If the area
                 * in this event overlaps the area copied, then some of the
                 * bits that were copied were bogus.  The easiest way to
                 * handle this is to issue two redisplays:  one for the
                 * original area and one for the area shifted as if it was
                 * in the copied area.
                 */

                TkTextRedrawRegion(textPtr, event.xexpose.x,
                        event.xexpose.y, event.xexpose.width,
                        event.xexpose.height);
                TkTextRedrawRegion(textPtr, event.xexpose.x,
                        event.xexpose.y + offset, event.xexpose.width,
                        event.xexpose.height);
            } else {
                panic("DisplayText received unknown exposure event");
            }
        }
    }

    /*
     * Now we have to redraw the lines that couldn't be updated by
     * scrolling.  First, compute the height of the largest line and
     * allocate an off-screen pixmap to use for double-buffered
     * displays.
     */

    maxHeight = -1;
    for (dlPtr = textPtr->dInfoPtr->dLinePtr; dlPtr != NULL;
            dlPtr = dlPtr->nextPtr) {
        if ((dlPtr->height > maxHeight) && (dlPtr->oldY != dlPtr->y)) {
            maxHeight = dlPtr->height;
        }
        bottomY = dlPtr->y + dlPtr->height;
    }
    if (maxHeight >= 0) {
        pixmap = XCreatePixmap(Tk_Display(textPtr->tkwin),
                Tk_WindowId(textPtr->tkwin), Tk_Width(textPtr->tkwin),
                maxHeight, Tk_DefaultDepth(Tk_Screen(textPtr->tkwin)));
        for (dlPtr = textPtr->dInfoPtr->dLinePtr; dlPtr != NULL;
                dlPtr = dlPtr->nextPtr) {
            if (dlPtr->oldY != dlPtr->y) {
                DisplayDLine(textPtr, dlPtr, pixmap);
                dlPtr->oldY = dlPtr->y;
            }
        }
        XFreePixmap(Tk_Display(textPtr->tkwin), pixmap);
    }

    /*
     * Lastly, see if we need to refresh the part of the window below
     * the last line of text (if there is any such area).
     */

    if (dInfoPtr->topOfEof > dInfoPtr->maxY) {
        dInfoPtr->topOfEof = dInfoPtr->maxY;
    }
    if (bottomY < dInfoPtr->topOfEof) {
        Tk_Fill3DRectangle(Tk_Display(textPtr->tkwin),
                Tk_WindowId(textPtr->tkwin), textPtr->border,
                dInfoPtr->x, bottomY, dInfoPtr->maxX - dInfoPtr->x,
                dInfoPtr->topOfEof-bottomY, 0, TK_RELIEF_FLAT);
    }
    dInfoPtr->topOfEof = bottomY;
    if (dInfoPtr->topOfEof > dInfoPtr->maxY) {
        dInfoPtr->topOfEof = dInfoPtr->maxY;
    }

    done:
    dInfoPtr->flags &= ~(REDRAW_PENDING|REDRAW_BORDERS);
}
\f
/*
 *----------------------------------------------------------------------
 *
 * TkTextRedrawRegion --
 *
 *      This procedure is invoked to schedule a redisplay for a given
 *      region of a text widget.  The redisplay itself may not occur
 *      immediately:  it's scheduled as a when-idle handler.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      Information will eventually be redrawn on the screen.
 *
 *----------------------------------------------------------------------
 */

        /* ARGSUSED */
void
TkTextRedrawRegion(textPtr, x, y, width, height)
    TkText *textPtr;            /* Widget record for text widget. */
    int x, y;                   /* Coordinates of upper-left corner of area
                                 * to be redrawn, in pixels relative to
                                 * textPtr's window. */
    int width, height;          /* Width and height of area to be redrawn. */
{
    register DLine *dlPtr;
    DInfo *dInfoPtr = textPtr->dInfoPtr;
    int maxY;

    /*
     * Find all lines that overlap the given region and mark them for
     * redisplay.
     */

    maxY = y + height;
    for (dlPtr = dInfoPtr->dLinePtr; dlPtr != NULL;
            dlPtr = dlPtr->nextPtr) {
        if (((dlPtr->y + dlPtr->height) > y) && (dlPtr->y < maxY)) {
            dlPtr->oldY = -1;
        }
    }
    if (dInfoPtr->topOfEof < maxY) {
        dInfoPtr->topOfEof = maxY;
    }

    /*
     * Schedule the redisplay operation if there isn't one already
     * scheduled.
     */

    if (!(dInfoPtr->flags & REDRAW_PENDING)) {
        dInfoPtr->flags |= REDRAW_PENDING;
//      Tk_DoWhenIdle(DisplayText, (ClientData) textPtr);
        assert(textPtr->updateTimerToken == NULL);
        if (textPtr->updateTimerToken == NULL) {
            textPtr->updateTimerToken =
              Tk_CreateTimerHandler(
                TextUpdateTime,
                DisplayText,
                (ClientData) textPtr);
        }
    }
    if ((x < dInfoPtr->x) || (y < dInfoPtr->y)
            || ((x + width) > dInfoPtr->maxX) || (maxY > dInfoPtr->maxY)) {
        dInfoPtr->flags |= REDRAW_BORDERS;
    }
}
\f
/*
 *----------------------------------------------------------------------
 *
 * TkTextLinesChanged --
 *
 *      This procedure is invoked when lines in a text widget are about
 *      to be modified in a way that changes how they are displayed (e.g.
 *      characters were inserted, the line was deleted, or tag information
 *      was changed).  This procedure must be called *before* a change is
 *      made, so that pointers to TkTextLines in the display information
 *      are still valid.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      The indicated lines will be redisplayed at some point in the
 *      future (the actual redisplay is scheduled as a when-idle handler).
 *
 *----------------------------------------------------------------------
 */

void
TkTextLinesChanged(textPtr, first, last)
    TkText *textPtr;            /* Widget record for text widget. */
    int first;                  /* Index of first line that must be
                                 * redisplayed. */
    int last;                   /* Index of last line to redisplay. */
{
    DInfo *dInfoPtr = textPtr->dInfoPtr;
    DLine *firstPtr, *lastPtr;

    /*
     * Find the DLines corresponding to first and last+1.
     */

    firstPtr = FindDLine(dInfoPtr->dLinePtr, first);
    if (firstPtr == NULL) {
        return;
    }
    lastPtr = FindDLine(dInfoPtr->dLinePtr, last+1);
    if (firstPtr == lastPtr) {
        return;
    }

    /*
     * Delete all the DLines from first up through last (but not including
     * lastPtr, which points to the first line *outside* the range).
     */

    FreeDLines(textPtr, firstPtr, lastPtr, 1);

    /*
     * Schedule both a redisplay and a recomputation of display information.
     */

    if (!(dInfoPtr->flags & REDRAW_PENDING)) {
//      Tk_DoWhenIdle(DisplayText, (ClientData) textPtr);
        assert(textPtr->updateTimerToken == NULL);
        if (textPtr->updateTimerToken == NULL) {
            textPtr->updateTimerToken =
              Tk_CreateTimerHandler(
                TextUpdateTime,
                DisplayText,
                (ClientData) textPtr);
        }
    }
    dInfoPtr->flags |= REDRAW_PENDING | DINFO_OUT_OF_DATE | REPICK_NEEDED;
}
\f
/*
 *----------------------------------------------------------------------
 *
 * TkTextRedrawTag --
 *
 *      This procedure is invoked to request a redraw of all characters
 *      in a given range of characters that have a particular tag on or
 *      off.  It's called, for example, when characters are tagged or
 *      untagged, or when tag options change.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      Information on the screen may be redrawn, and the layout of
 *      the screen may change.
 *
 *----------------------------------------------------------------------
 */

void
TkTextRedrawTag(textPtr, line1, ch1, line2, ch2, tagPtr, withTag)
    TkText *textPtr;            /* Widget record for text widget. */
    int line1, ch1;             /* Index of first character in range of
                                 * interest. */
    int line2, ch2;             /* Index of character just after last one
                                 * in range of interest. */
    TkTextTag *tagPtr;          /* Information about tag. */
    int withTag;                /* 1 means redraw characters that have the
                                 * tag, 0 means redraw those without. */
{
    register DLine *dlPtr;
    DLine *endPtr;
    int topLine, tagOn;
    TkTextSearch search;
    DInfo *dInfoPtr = textPtr->dInfoPtr;

    /*
     * Round up the starting position if it's before the first line
     * visible on the screen (we only care about what's on the screen).
     */

    dlPtr = dInfoPtr->dLinePtr;
    if (dlPtr == NULL) {
        return;
    }
    topLine = TkBTreeLineIndex(dlPtr->linePtr);
    if (topLine > line1) {
        line1 = topLine;
        ch1 = 0;
    }

    /* 
     * Initialize a search through all transitions on the tag, starting
     * with the first transition where the tag's current state is different
     * from what it will eventually be.
     */

    TkBTreeStartSearch(textPtr->tree, line1, ch1+1, line2, ch2,
            tagPtr, &search);
    tagOn = TkBTreeCharTagged(search.linePtr, ch1, tagPtr);
    if (tagOn != withTag) {
        if (!TkBTreeNextTag(&search)) {
            return;
        }
    }

    /*
     * Each loop through the loop below is for one range of characters
     * where the tag's current state is different than its eventual
     * state.  At the top of the loop, search contains information about
     * the first character in the range.
     */

    while (1) {
        /*
         * Find the first DLine structure in the range.
         */

        dlPtr = FindDLine(dlPtr, search.line1);
        if (dlPtr == NULL) {
            break;
        }

        /*
         * Find the first DLine structure that's past the end of the range.
         */

        if (TkBTreeNextTag(&search)) {
            endPtr = FindDLine(dlPtr,
                    (search.ch1 > 0) ? (search.line1 + 1) : search.line1);
        } else {
            endPtr = FindDLine(dlPtr,
                    (ch2 > 0) ? (search.line2 + 1) : search.line2);
        }

        /*
         * Delete all of the display lines in the range, so that they'll
         * be re-layed out and redrawn.
         */

        FreeDLines(textPtr, dlPtr, endPtr, 1);
        dlPtr = endPtr;

        /*
         * Find the first text line in the next range.
         */

        if (!TkBTreeNextTag(&search)) {
            break;
        }
    }

    /*
     * Lastly, schedule a redisplay and layout recalculation if they
     * aren't already pending.
     */

    if (!(dInfoPtr->flags & REDRAW_PENDING)) {
//      Tk_DoWhenIdle(DisplayText, (ClientData) textPtr);
        assert(textPtr->updateTimerToken == NULL);
        if (textPtr->updateTimerToken == NULL) {
            textPtr->updateTimerToken =
              Tk_CreateTimerHandler(
                TextUpdateTime,
                DisplayText,
                (ClientData) textPtr);
        }
    }
    dInfoPtr->flags |= REDRAW_PENDING | DINFO_OUT_OF_DATE | REPICK_NEEDED;
}
\f
/*
 *----------------------------------------------------------------------
 *
 * TkTextRelayoutWindow --
 *
 *      This procedure is called when something has happened that
 *      invalidates the whole layout of characters on the screen, such
 *      as a change in a configuration option for the overall text
 *      widget or a change in the window size.  It causes all display
 *      information to be recomputed and the window to be redrawn.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      All the display information will be recomputed for the window
 *      and the window will be redrawn.
 *
 *----------------------------------------------------------------------
 */

void
TkTextRelayoutWindow(textPtr)
    TkText *textPtr;            /* Widget record for text widget. */
{
    DInfo *dInfoPtr = textPtr->dInfoPtr;

    /*
     * Throw away all the current layout information.
     */

    FreeDLines(textPtr, dInfoPtr->dLinePtr, (DLine *) NULL, 1);
    dInfoPtr->dLinePtr = NULL;

    /*
     * Recompute some overall things for the layout.
     */

    dInfoPtr->x = textPtr->borderWidth + textPtr->padX;
    dInfoPtr->y = textPtr->borderWidth + textPtr->padY;
    dInfoPtr->maxX = Tk_Width(textPtr->tkwin) - dInfoPtr->x;
    dInfoPtr->maxY = Tk_Height(textPtr->tkwin) - dInfoPtr->y;
    dInfoPtr->topOfEof = dInfoPtr->maxY;

    if (!(dInfoPtr->flags & REDRAW_PENDING)) {
//      Tk_DoWhenIdle(DisplayText, (ClientData) textPtr);
        assert(textPtr->updateTimerToken == NULL);
        if (textPtr->updateTimerToken == NULL) {
            textPtr->updateTimerToken =
              Tk_CreateTimerHandler(
                TextUpdateTime,
                DisplayText,
                (ClientData) textPtr);
        }
    }
    dInfoPtr->flags |= REDRAW_PENDING | REDRAW_BORDERS | DINFO_OUT_OF_DATE | REPICK_NEEDED;
}
\f
/*
 *----------------------------------------------------------------------
 *
 * TkTextSetView --
 *
 *      This procedure is called to specify what lines are to be
 *      displayed in a text widget.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      The display will (eventually) be updated so that the line
 *      given by "line" is visible on the screen at the position
 *      determined by "pickPlace".
 *
 *----------------------------------------------------------------------
 */

void
TkTextSetView(textPtr, line, pickPlace)
    TkText *textPtr;            /* Widget record for text widget. */
    int line;                   /* Number of line that is to appear somewhere
                                 * in the window.  This line number must
                                 * be a valid one in the file. */
    int pickPlace;              /* 0 means topLine must appear at top of
                                 * screen.  1 means we get to pick where it
                                 * appears:  minimize screen motion or else
                                 * display line at center of screen. */
{
    DInfo *dInfoPtr = textPtr->dInfoPtr;
    register DLine *dlPtr, *dlPtr2;
    TkTextLine *linePtr;
    int curTopLine, curBotLine;
    int bottomY;
    TagInfo tagInfo;
#define CLOSE_LINES 5

    if (!pickPlace) {
        /*
         * The line must go at the top of the screen.  See if the new
         * topmost line is already somewhere on the screen.  If so then
         * delete all the DLine structures ahead of it.  Otherwise just
         * leave all the DLine's alone (if the new topmost line is above
         * the top of the current window, i.e. we're scrolling back towards
         * the beginning of the file we may be able to reuse some of the
         * information that's currently on the screen without redisplaying
         * it all.
         */
    
        dlPtr = FindDLine(dInfoPtr->dLinePtr, line);
        if ((dlPtr != NULL) && (dlPtr != dInfoPtr->dLinePtr)) {
            FreeDLines(textPtr, dInfoPtr->dLinePtr, dlPtr, 1);
        }
    
        textPtr->topLinePtr = TkBTreeFindLine(textPtr->tree, line);
        goto scheduleUpdate;
    }

    /*
     * We have to pick where to display the given line.  First, bring
     * the display information up to date and see if the line will be
     * completely visible in the current screen configuration.  If so
     * then there's nothing to do.
     */

    if (dInfoPtr->flags & DINFO_OUT_OF_DATE) {
        UpdateDisplayInfo(textPtr);
    }
    linePtr = TkBTreeFindLine(textPtr->tree, line);
    /* DEH: return if dlPtr is null */
    if ((dlPtr = dInfoPtr->dLinePtr) == NULL)
        return;
    for (; ; dlPtr = dlPtr->nextPtr) {
        if (dlPtr->nextPtr == NULL) {
            break;
        }
        if ((dlPtr->linePtr == linePtr)
                && (dlPtr->nextPtr->linePtr != linePtr)) {
            break;
        }
    }
    if ((dlPtr->linePtr == linePtr)
            && ((dlPtr->y + dlPtr->height) <= dInfoPtr->maxY)) {
        return;
    }

    /*
     * The desired line isn't already on-screen.  See if it is within
     * a few lines of the top of the window.  If so then just make it
     * the top line on the screen.
     */

    bottomY = (dInfoPtr->y + dInfoPtr->maxY)/2;
    curTopLine = TkBTreeLineIndex(dInfoPtr->dLinePtr->linePtr);
    if (line < curTopLine) {
        if (line >= (curTopLine-CLOSE_LINES)) {
            textPtr->topLinePtr = TkBTreeFindLine(textPtr->tree, line);
            goto scheduleUpdate;
        }
    } else {
        /*
         * The desired line is below the bottom of the screen.  If it is
         * within a few lines of the bottom of the screen then position
         * it at the bottom of the screen. (At this point dlPtr points to
         * the last line on the screen)
         */
    
        curBotLine = TkBTreeLineIndex(dlPtr->linePtr);
        if (line <= (curBotLine+5)) {
            bottomY = dInfoPtr->maxY;
        }
    }

    /*
     * Our job now is arrange the display so that "line" appears as
     * low on the screen as possible but with its bottom no lower
     * than bottomY (bottomY is the bottom of the window if the
     * desired line is just below the current screen, otherwise it
     * is the center of the window.  Work upwards (through smaller
     * line numbers) computing how much space lines take, until we
     * fine the line that should be at the top of the screen.
     */

    for (textPtr->topLinePtr = linePtr = TkBTreeFindLine(textPtr->tree, line);
            ; line--, textPtr->topLinePtr = linePtr,
            linePtr = TkBTreeFindLine(textPtr->tree, line)) {
        tagInfo.tagPtrs = TkBTreeGetTags(textPtr->tree, linePtr, 0,
                &tagInfo.numTags);
        tagInfo.arraySize = tagInfo.numTags;
        TkBTreeStartSearch(textPtr->tree, line, 1, line+1, 0,
                (TkTextTag *) NULL, &tagInfo.search);
        TkBTreeNextTag(&tagInfo.search);
        dlPtr = LayoutLine(textPtr, line, linePtr, &tagInfo);
        for (dlPtr2 = dlPtr; dlPtr2 != NULL; dlPtr2 = dlPtr2->nextPtr) {
            bottomY -= dlPtr2->height;
        }
        FreeDLines(textPtr, dlPtr, (DLine *) NULL, 0);
        if (tagInfo.tagPtrs != NULL) {
            ckfree((char *) tagInfo.tagPtrs);
        }
        if ((bottomY <= 0) || (line <= 0)) {
            break;
        }
    }

    scheduleUpdate:
    if (!(dInfoPtr->flags & REDRAW_PENDING)) {
//      Tk_DoWhenIdle(DisplayText, (ClientData) textPtr);
        assert(textPtr->updateTimerToken == NULL);
        if (textPtr->updateTimerToken == NULL) {
            textPtr->updateTimerToken =
              Tk_CreateTimerHandler(
                TextUpdateTime,
                DisplayText,
                (ClientData) textPtr);
        }
    }
    dInfoPtr->flags |= REDRAW_PENDING | DINFO_OUT_OF_DATE | REPICK_NEEDED;
}
\f
/*
 *----------------------------------------------------------------------
 *
 * FindDLine --
 *
 *      This procedure is called to find the DLine corresponding to a
 *      given text line.
 *
 * Results:
 *      The return value is a pointer to the first DLine found in the
 *      list headed by dlPtr whose line number is greater or equal to
 *      line.  If there is no such line in the list then NULL is returned.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */

static DLine *
FindDLine(dlPtr, line)
    register DLine *dlPtr;      /* Pointer to first in list of DLines
                                 * to search. */
    int line;                   /* Line number in text that is desired. */
{
    TkTextLine *linePtr;
    int thisLine;

    if (dlPtr == NULL) {
        return NULL;
    }
    thisLine = TkBTreeLineIndex(dlPtr->linePtr);
    while (thisLine < line) {
        /*
         * This DLine isn't the right one.  Go on to the next DLine
         * (skipping multiple DLine's for the same text line).
         */

        linePtr = dlPtr->linePtr;
        do {
            dlPtr = dlPtr->nextPtr;
            if (dlPtr == NULL) {
                return NULL;
            }
        } while (dlPtr->linePtr == linePtr);

        /*
         * Step through text lines, keeping track of the line number
         * we're on, until we catch up to dlPtr (remember, there could
         * be gaps in the DLine list where DLine's have been deleted).
         */

        do {
            linePtr = TkBTreeNextLine(linePtr);
            thisLine++;
            if (linePtr == NULL) {
                panic("FindDLine reached end of text");
            }
        } while (linePtr != dlPtr->linePtr);
    }
    return dlPtr;
}
\f
/*
 *----------------------------------------------------------------------
 *
 * TkTextCharAtLoc --
 *
 *      Given an (x,y) coordinate on the screen, find the location of
 *      the closest character to that location.
 *
 * Results:
 *      The return value is a pointer to the text line containing the
 *      character displayed closest to (x,y).  The value at *chPtr is
 *      overwritten with the index with that line of the closest
 *      character.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */

TkTextLine *
TkTextCharAtLoc(textPtr, x, y, chPtr)
    TkText *textPtr;            /* Widget record for text widget. */
    int x, y;                   /* Pixel coordinates of point in widget's
                                 * window. */
    int *chPtr;                 /* Place to store index-within-line of
                                 * closest character. */
{
    DInfo *dInfoPtr = textPtr->dInfoPtr;
    register DLine *dlPtr;
    register Chunk *chunkPtr;
    int count;
    int endX;

    /*
     * Make sure that all of the layout information about what's
     * displayed where on the screen is up-to-date.
     */

    if (dInfoPtr->flags & DINFO_OUT_OF_DATE) {
        UpdateDisplayInfo(textPtr);
    }

    /*
     * If the coordinates are above the top of the window, then adjust
     * them to refer to the upper-right corner of the window.
     */

    if (y < dInfoPtr->y) {
        y = dInfoPtr->y;
        x = dInfoPtr->x;
    } else if (y >= dInfoPtr->topOfEof) {
        y = dInfoPtr->topOfEof;
        x = dInfoPtr->maxX;
    }
    for (dlPtr = dInfoPtr->dLinePtr; dlPtr != NULL; dlPtr = dlPtr->nextPtr) {
        if (y > (dlPtr->y + dlPtr->height)) {
            if (dlPtr->nextPtr != NULL) {
                continue;
            }

            /*
             * The coordinates are off the bottom of the window.  Adjust
             * them to refer to the lower-right character on the window.
             */

            y = dlPtr->y;
            x = dInfoPtr->maxX;
        }
        for (chunkPtr = dlPtr->chunkPtr; ; chunkPtr = chunkPtr->nextPtr) {
            if ((chunkPtr->nextPtr == NULL) || (chunkPtr->nextPtr->x > x)) {
                break;
            }
        }
        count = TkMeasureChars(chunkPtr->stylePtr->sValuePtr->fontPtr,
            chunkPtr->text, chunkPtr->numChars, chunkPtr->x, x, 0, &endX);
        if (count >= chunkPtr->numChars) {
            /*
             * The point is off the end of the line.  Return the character
             * after the last one that fit, unless that character appears
             * as the first character on the next DLine or unless the last
             * one that fit extends beyond the edge of the window.
             */

            if ((dlPtr->nextPtr != NULL)
                    && (dlPtr->nextPtr->chunkPtr->text
                    == (chunkPtr->text + chunkPtr->numChars))) {
                count = chunkPtr->numChars-1;
            }
            if (endX >= dInfoPtr->maxX) {
                count = chunkPtr->numChars-1;
            }
        }
        *chPtr = count + (chunkPtr->text - dlPtr->linePtr->bytes);
        return dlPtr->linePtr;
    }
    panic("TkTextCharAtLoc ran out of lines");
    return (TkTextLine *) NULL;
}