performance of lines containing 10000+ characters

6 files changed, 178 insertions, 48 deletions

diff --git a/ChangeLog b/ChangeLog
index 3325b4a..4cdcd3b 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,18 @@
+2003-12-05  Vince Darley <vincentdarley@users.sourceforge.net>
+
+	* tests/text.test:
+	* generic/tkText.c: after debate on sf, allow decreasing tab-stops, 
+	hence removing any potential backwards incompatibility, even for
+	buggy code. Added new test. [Bug 852949]
+	
+	* generic/tkText.h: 
+	* generic/tkTextDisp.c: 
+	* generic/tkTextTag.c: fix to performance problems in the text
+	widget when inserting lines which wrap thousands of times 
+	[Bug 853003].  Note that the text widget must now perform additional
+	calculations (pixel heights) compared to Tk <= 8.4, and so some
+	actions will be slower, be necessity.
+
 2003-12-05  Benjamin Riefenstahl  <Benjamin.Riefenstahl@epost.de>
 
 	* win/tkWinFont.c (Tk_MeasureChars): Fix indentation.  Fix memory
diff --git a/generic/tkText.c b/generic/tkText.c
index cdb376d..987bafa 100644
--- a/generic/tkText.c
+++ b/generic/tkText.c
@@ -14,7 +14,7 @@
  * See the file "license.terms" for information on usage and redistribution
  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  *
- * RCS: @(#) $Id: tkText.c,v 1.46 2003/12/04 12:28:37 vincentdarley Exp $
+ * RCS: @(#) $Id: tkText.c,v 1.47 2003/12/05 17:19:06 vincentdarley Exp $
  */
 
 #include "default.h"
@@ -27,6 +27,15 @@
 #define DInfo TkDInfo
 #endif
 
+/*
+ * For compatibility with Tk 4.0 through 8.4.x, we allow tabs to be
+ * mis-specified with non-increasing values.  These are converted into
+ * tabs which are the equivalent of at least a character width apart.
+ */
+#if (TK_MAJOR_VERSION < 9)
+#define _TK_ALLOW_DECREASING_TABS
+#endif
+
 #include "tkText.h"
 
 /*
@@ -743,7 +752,7 @@ TextWidgetObjCmd(clientData, interp, objc, objv)
 		     * with the last artificial line in the widget.
 		     */
 		    while (fromPtr != indexToPtr->linePtr) {
-			value += TkTextUpdateOneLine(textPtr, fromPtr);
+			value += TkTextUpdateOneLine(textPtr, fromPtr, 0, NULL);
 			fromPtr = TkBTreeNextLine(fromPtr);
 		    }
 		    /* 
@@ -1556,7 +1565,7 @@ ConfigureText(interp, textPtr, objc, objv)
 	textPtr->tabArrayPtr = NULL;
     }
     if (textPtr->tabOptionPtr != NULL) {
-	textPtr->tabArrayPtr = TkTextGetTabs(interp, textPtr->tkwin,
+	textPtr->tabArrayPtr = TkTextGetTabs(interp, textPtr,
 		textPtr->tabOptionPtr);
 	if (textPtr->tabArrayPtr == NULL) {
 	    Tcl_AddErrorInfo(interp,"\n    (while processing -tabs option)");
@@ -3301,10 +3310,10 @@ TextSearchFoundMatch(lineNum, searchSpecPtr, clientData, theLine,
  */
 
 TkTextTabArray *
-TkTextGetTabs(interp, tkwin, stringPtr)
+TkTextGetTabs(interp, textPtr, stringPtr)
     Tcl_Interp *interp;			/* Used for error reporting. */
-    Tk_Window tkwin;			/* Window in which the tabs will be
-					 * used. */
+    TkText *textPtr;			/* Information about the
+                    			 * text widget. */
     Tcl_Obj *stringPtr;			/* Description of the tab stops.  
                        			 * See the text manual entry for 
                        			 * details. */
@@ -3352,8 +3361,8 @@ TkTextGetTabs(interp, tkwin, stringPtr)
     for (i = 0, tabPtr = &tabArrayPtr->tabs[0]; i  < objc; i++, tabPtr++) {
 	int index;
 	
-	if (Tk_GetPixelsFromObj(interp, tkwin, objv[i], &tabPtr->location)
-		!= TCL_OK) {
+	if (Tk_GetPixelsFromObj(interp, textPtr->tkwin, objv[i], 
+				&tabPtr->location) != TCL_OK) {
 	    goto error;
 	}
 
@@ -3365,23 +3374,38 @@ TkTextGetTabs(interp, tkwin, stringPtr)
 	}
 	
 	prevStop = lastStop;
-	if (Tk_GetMMFromObj(interp, tkwin, objv[i], &lastStop) != TCL_OK) {
+	if (Tk_GetMMFromObj(interp, textPtr->tkwin, objv[i], 
+			    &lastStop) != TCL_OK) {
 	    goto error;
 	}
-	lastStop *= WidthOfScreen(Tk_Screen(tkwin));
-	lastStop /= WidthMMOfScreen(Tk_Screen(tkwin));
+	lastStop *= WidthOfScreen(Tk_Screen(textPtr->tkwin));
+	lastStop /= WidthMMOfScreen(Tk_Screen(textPtr->tkwin));
 	
 	if (i > 0 && (tabPtr->location <= (tabPtr-1)->location)) {
 	    /* 
 	     * This tab is actually to the left of the previous
 	     * one, which is illegal.
 	     */
+#ifdef _TK_ALLOW_DECREASING_TABS
+	    /* 
+	     * Force the tab to be a typical character width to the
+	     * right of the previous one, and update the 'lastStop'
+	     * with the changed position.
+	     */
+	    if (textPtr->charWidth > 0) {
+	        tabPtr->location = (tabPtr-1)->location + textPtr->charWidth;
+	    } else {
+		tabPtr->location = (tabPtr-1)->location + 8;
+	    }
+	    lastStop = tabPtr->location;
+#else
 	    Tcl_AppendResult(interp, 
 		 "tabs must be monotonically increasing, but \"",
 		 Tcl_GetString(objv[i]), 
 		 "\" is smaller than or equal to the previous tab",
 		 NULL);
 	    goto error;
+#endif
 	}
 	
 	tabArrayPtr->numTabs++;
diff --git a/generic/tkText.h b/generic/tkText.h
index bf79bc7..051c874 100644
--- a/generic/tkText.h
+++ b/generic/tkText.h
@@ -10,7 +10,7 @@
  * See the file "license.terms" for information on usage and redistribution
  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  *
- * RCS: @(#) $Id: tkText.h,v 1.22 2003/11/21 18:51:18 vincentdarley Exp $
+ * RCS: @(#) $Id: tkText.h,v 1.23 2003/12/05 17:19:06 vincentdarley Exp $
  */
 
 #ifndef _TKTEXT
@@ -970,7 +970,7 @@ EXTERN int		TkTextGetObjIndex _ANSI_ARGS_((Tcl_Interp *interp,
 EXTERN CONST TkTextIndex* TkTextGetIndexFromObj _ANSI_ARGS_((Tcl_Interp *interp,
 			    TkText *textPtr, Tcl_Obj *objPtr));
 EXTERN TkTextTabArray *	TkTextGetTabs _ANSI_ARGS_((Tcl_Interp *interp,
-			    Tk_Window tkwin, Tcl_Obj *stringPtr));
+			    TkText *textPtr, Tcl_Obj *stringPtr));
 EXTERN void             TkTextFindDisplayLineEnd _ANSI_ARGS_((
 			    TkText *textPtr, TkTextIndex *indexPtr, 
 			    int end, int *xOffset));
@@ -1025,7 +1025,8 @@ EXTERN void             TkTextInvalidateLineMetrics _ANSI_ARGS_((TkText *textPtr
 EXTERN int              TkTextUpdateLineMetrics _ANSI_ARGS_((TkText *textPtr,
 			    int lineNum, int endLine, int doThisMuch));
 EXTERN int              TkTextUpdateOneLine _ANSI_ARGS_((TkText *textPtr, 
-			    TkTextLine *linePtr));
+			    TkTextLine *linePtr, int pixelHeight, 
+			    TkTextIndex *indexPtr));
 EXTERN int		TkTextMarkCmd _ANSI_ARGS_((TkText *textPtr,
 			    Tcl_Interp *interp, int objc, Tcl_Obj *CONST objv[]));
 EXTERN int		TkTextMarkNameToIndex _ANSI_ARGS_((TkText *textPtr,
diff --git a/generic/tkTextDisp.c b/generic/tkTextDisp.c
index f015fd1..6968c82 100644
--- a/generic/tkTextDisp.c
+++ b/generic/tkTextDisp.c
@@ -13,7 +13,7 @@
  * See the file "license.terms" for information on usage and redistribution
  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  *
- * RCS: @(#) $Id: tkTextDisp.c,v 1.36 2003/12/04 12:28:37 vincentdarley Exp $
+ * RCS: @(#) $Id: tkTextDisp.c,v 1.37 2003/12/05 17:19:06 vincentdarley Exp $
  */
 
 #include "tkPort.h"
@@ -292,6 +292,9 @@ typedef struct TextDInfo {
 				 * contained in the widget and update
 				 * their geometry calculations, if they
 				 * are out of date.  */
+    TkTextIndex metricIndex;
+    int metricPixelHeight;
+    int metricEpoch;
     int lastMetricUpdateLine;   /* When the current update line reaches
 				 * this line, we are done and should
 				 * stop the asychronous callback
@@ -512,7 +515,10 @@ TkTextCreateDInfo(textPtr)
     dInfoPtr->currentMetricUpdateLine = -1;
     dInfoPtr->lastMetricUpdateLine = -1;
     dInfoPtr->lineMetricUpdateEpoch = 1;
-
+    dInfoPtr->metricEpoch = -1;
+    dInfoPtr->metricIndex.textPtr = NULL;
+    dInfoPtr->metricIndex.linePtr = NULL;
+    
     /* Add a refCount for each of the idle call-backs */
     textPtr->refCount++;
     dInfoPtr->lineUpdateTimer = Tcl_CreateTimerHandler(0, 
@@ -2642,12 +2648,56 @@ TkTextUpdateLineMetrics(textPtr, lineNum, endLine, doThisMuch)
 	    /* Now update the line's metrics if necessary */
 	    if (linePtr->pixelCalculationEpoch 
 		!= textPtr->dInfoPtr->lineMetricUpdateEpoch) {
-		/* 
-		 * Update the line and update the counter, counting
-		 * 10 for each line we actually re-layout.
-		 */
-		TkTextUpdateOneLine(textPtr, linePtr);
-		count += 10;
+		if (doThisMuch == -1) {
+		    count += 8 * TkTextUpdateOneLine(textPtr, linePtr, 
+						     0, NULL);
+		} else {
+		    TkTextIndex index;
+		    TkTextIndex *indexPtr;
+		    int pixelHeight;
+		    
+		    /* 
+		     * If the metric epoch is the same as the widget's 
+		     * epoch, then we know that indexPtrs are still
+		     * valid, and if the cached metricIndex (if any) is
+		     * for the same line as we wish to examine, then
+		     * we are looking at a long line wrapped many
+		     * times, which we will examine in pieces.
+		     */
+		    if (textPtr->dInfoPtr->metricEpoch == textPtr->stateEpoch 
+		      && textPtr->dInfoPtr->metricIndex.linePtr == linePtr) {
+			indexPtr = &textPtr->dInfoPtr->metricIndex;
+			pixelHeight = textPtr->dInfoPtr->metricPixelHeight;
+		    } else {
+			index.tree = textPtr->tree;
+			index.linePtr = linePtr;
+			index.byteIndex = 0;
+			index.textPtr = NULL;
+			indexPtr = &index;
+			pixelHeight = 0;
+		    }
+		    /* 
+		     * Update the line and update the counter, counting
+		     * 8 for each display line we actually re-layout.
+		     */
+		    count += 8 * TkTextUpdateOneLine(textPtr, linePtr, 
+						     pixelHeight, indexPtr);
+		    
+		    if (indexPtr->linePtr == linePtr) {
+			/* 
+			 * We didn't complete the logical line, because it
+			 * produced very many display lines -- it must be a
+			 * long line wrapped many times.  So we must
+			 * cache as far as we got for next time around.
+			 */
+			if (pixelHeight == 0) {
+			    textPtr->dInfoPtr->metricIndex = index;
+			    textPtr->dInfoPtr->metricEpoch = textPtr->stateEpoch;
+			}
+			textPtr->dInfoPtr->metricPixelHeight = linePtr->pixelHeight;
+			break;
+		    }
+		}
 	    }
 	} else {
 	    /* 
@@ -3094,18 +3144,32 @@ TkTextIndexYPixels(textPtr, indexPtr)
  */
 
 int
-TkTextUpdateOneLine(textPtr, linePtr)
+TkTextUpdateOneLine(textPtr, linePtr, pixelHeight, indexPtr)
     TkText *textPtr;        /* Widget record for text widget. */
     TkTextLine *linePtr;    /* The line of which to calculate the
                              * height. */
+    int pixelHeight;        /* If indexPtr is non-NULL, then this
+                             * is the number of pixels in the logical
+                             * line linePtr, up to the index which
+                             * has been given. */
+    TkTextIndex *indexPtr;  /* Either NULL or an index at the start of
+                             * a display line belonging to linePtr,
+                             * up to which we have already calculated. */
 {
     TkTextIndex index;
-    int pixelHeight, displayLines;
+    int displayLines, partialCalc;
     
-    index.tree = textPtr->tree;
-    index.linePtr = linePtr;
-    index.byteIndex = 0;
-    index.textPtr = NULL;
+    if (indexPtr == NULL) {
+	index.tree = textPtr->tree;
+	index.linePtr = linePtr;
+	index.byteIndex = 0;
+	index.textPtr = NULL;
+	indexPtr = &index;
+	pixelHeight = 0;
+	partialCalc = 0; 
+    } else {
+	partialCalc = 1; 
+    }
     
     /* 
      * Iterate through all display-lines corresponding to the
@@ -3114,7 +3178,6 @@ TkTextUpdateOneLine(textPtr, linePtr)
      * total is, therefore, the height of the logical line.
      */
 
-    pixelHeight = 0;
     displayLines = 0;
     
     while (1) {
@@ -3128,37 +3191,52 @@ TkTextUpdateOneLine(textPtr, linePtr)
 	 * specifically the 'linePtr->pixelHeight == pixelHeight' test 
 	 * below this while loop.
 	 */
-	height = CalculateDisplayLineHeight(textPtr, &index, &bytes);
+	height = CalculateDisplayLineHeight(textPtr, indexPtr, &bytes);
 	
 	if (height > 0) {
 	    pixelHeight += height;
 	    displayLines++;
 	}
 	
-	if (TkTextIndexForwBytes(&index, bytes, &index)) {
+	if (TkTextIndexForwBytes(indexPtr, bytes, indexPtr)) {
             break;
         }
 
-	if (index.linePtr != linePtr) {
+	if (indexPtr->linePtr != linePtr) {
+	    /* 
+	     * If we reached the end of the logical line, then
+	     * either way we don't have a partial calculation.
+	     */
+	    partialCalc = 0;
+	    break;
+	}
+	if (partialCalc && displayLines > 50) {
+	    /* 
+	     * Only calculate 50 display lines at a time, to 
+	     * avoid huge delays.  In any case it is very rare
+	     * that a single line wraps 50 times!
+	     */
 	    break;
 	}
     }
     
-    /* 
-     * Mark the logical line as being up to date (caution: it isn't
-     * yet up to date, that will happen in TkBTreeAdjustPixelHeight
-     * just below).
-     */
-    linePtr->pixelCalculationEpoch = textPtr->dInfoPtr->lineMetricUpdateEpoch;
+    if (!partialCalc) {
+	/* 
+	 * Mark the logical line as being up to date (caution: it isn't
+	 * yet up to date, that will happen in TkBTreeAdjustPixelHeight
+	 * just below).
+	 */
+	linePtr->pixelCalculationEpoch = textPtr->dInfoPtr->lineMetricUpdateEpoch;
 
-    if (linePtr->pixelHeight == pixelHeight) {
-	return displayLines;
+	if (linePtr->pixelHeight == pixelHeight) {
+	    return displayLines;
+	}
     }
-
+    
     /* 
-     * We now use the resulting 'pixelHeight' to refer to the
-     * height of the entire widget, which may be used just below
-     * for reporting/debugging purposes
+     * We set the line's height, but the return value is now the height
+     * of the entire widget, which may be used just below for
+     * reporting/debugging purposes.
      */
     pixelHeight = TkBTreeAdjustPixelHeight(linePtr, pixelHeight);
     
diff --git a/generic/tkTextTag.c b/generic/tkTextTag.c
index c56b217..3762de9 100644
--- a/generic/tkTextTag.c
+++ b/generic/tkTextTag.c
@@ -11,7 +11,7 @@
  * See the file "license.terms" for information on usage and redistribution
  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  *
- * RCS: @(#) $Id: tkTextTag.c,v 1.14 2003/11/15 02:33:51 vincentdarley Exp $
+ * RCS: @(#) $Id: tkTextTag.c,v 1.15 2003/12/05 17:19:06 vincentdarley Exp $
  */
 
 #include "default.h"
@@ -441,7 +441,7 @@ TkTextTagCmd(textPtr, interp, objc, objv)
 		    tagPtr->tabArrayPtr = NULL;
 		}
 		if (tagPtr->tabStringPtr != NULL) {
-		    tagPtr->tabArrayPtr = TkTextGetTabs(interp, textPtr->tkwin,
+		    tagPtr->tabArrayPtr = TkTextGetTabs(interp, textPtr,
 			    tagPtr->tabStringPtr);
 		    if (tagPtr->tabArrayPtr == NULL) {
 			return TCL_ERROR;
diff --git a/tests/text.test b/tests/text.test
index f7d0113..bf7314b 100644
--- a/tests/text.test
+++ b/tests/text.test
@@ -6,7 +6,7 @@
 # Copyright (c) 1998-1999 by Scriptics Corporation.
 # All rights reserved.
 #
-# RCS: @(#) $Id: text.test,v 1.26 2003/12/04 12:28:37 vincentdarley Exp $
+# RCS: @(#) $Id: text.test,v 1.27 2003/12/05 17:19:06 vincentdarley Exp $
 
 package require tcltest 2.1
 eval tcltest::configure $argv
@@ -2911,12 +2911,24 @@ test text-27.2 {tabs - must be positive and must be increasing} {
     list [catch {.t configure -tabs {-5}} msg] $msg
 } {1 {tab stop "-5" is not at a positive distance}}
 
-test text-27.3 {tabs - must be positive and must be increasing} {
+test text-27.3 {tabs - must be positive and must be increasing} {knownBug} {
+    # This bug will be fixed in Tk 9.0, when we can allow a minor
+    # incompatibility with Tk 8.x
     destroy .t
     pack [text .t -wrap none]
     list [catch {.t configure -tabs {10c 5c}} msg] $msg
 } {1 {tabs must be monotonically increasing, but "5c" is smaller than or equal to the previous tab}}
 
+test text-27.4 {tabs - must be positive and must be increasing} {
+    destroy .t
+    pack [text .t -wrap none]
+    .t insert end "a\tb\tc\td\te"
+    catch {.t configure -tabs {10c 5c}}
+    update ; update ; update
+    # This test must simply not go into an infinite loop to succeed
+    set result 1
+} {1}
+
 deleteWindows
 option clear