# HG changeset patch
# User Christian Brabandt <cb@256bit.org>
# Date 1706215504 -3600
# Node ID 19c88c3d8c4398df824f72dc51db0710fe4fe2f6
# Parent  ee25a9f7b9b876be18a043d1864ed2028e3f172b
patch 9.1.0055: formatting long lines is slow

Commit: https://github.com/vim/vim/commit/78019df645400796831670ec166e7e3b55ae8310
Author: kawaii-Code <nia.personal.0@gmail.com>
Date:   Thu Jan 25 21:40:05 2024 +0100

    patch 9.1.0055: formatting long lines is slow

    Problem:  formatting long lines is slow
              (kawaii-Code)
    Solution: optimize gq (internal_format) for long
              lines (kawaii-Code)

    Implemented two workarounds that significantly reduce
    the amount of pointless calls. Ideally the algorithm
    would be rewritten not to be n^2, but it's too complicated
    with too many corner cases.

    closes: #13914

    Signed-off-by: kawaii-Code <nia.personal.0@gmail.com>
    Signed-off-by: Christian Brabandt <cb@256bit.org>

diff --git a/src/textformat.c b/src/textformat.c
--- a/src/textformat.c
+++ b/src/textformat.c
@@ -90,11 +90,18 @@ internal_format(
 	colnr_T	end_col;
 	int	wcc;			// counter for whitespace chars
 	int	did_do_comment = FALSE;
+	int	first_pass;
 
-	virtcol = get_nolist_virtcol()
-				   + char2cells(c != NUL ? c : gchar_cursor());
-	if (virtcol <= (colnr_T)textwidth)
-	    break;
+	// Cursor is currently at the end of line. No need to format
+	// if line length is less than textwidth (8 * textwidth for
+	// utf safety)
+	if (curwin->w_cursor.col < 8 * textwidth)
+	{
+	    virtcol = get_nolist_virtcol()
+		+ char2cells(c != NUL ? c : gchar_cursor());
+	    if (virtcol <= (colnr_T)textwidth)
+		break;
+	}
 
 	if (no_leader)
 	    do_comments = FALSE;
@@ -144,9 +151,17 @@ internal_format(
 	coladvance((colnr_T)textwidth);
 	wantcol = curwin->w_cursor.col;
 
-	curwin->w_cursor.col = startcol;
+	// If startcol is large (a long line), formatting takes too much
+	// time. The algorithm is O(n^2), it walks from the end of the
+	// line to textwidth border every time for each line break.
+	//
+	// Ceil to 8 * textwidth to optimize.
+	curwin->w_cursor.col = startcol < 8 * textwidth ? startcol :
+	    8 * textwidth;
+
 	foundcol = 0;
 	skip_pos = 0;
+	first_pass = TRUE;
 
 	// Find position to break at.
 	// Stop at first entered white when 'formatoptions' has 'v'
@@ -155,8 +170,11 @@ internal_format(
 		    || curwin->w_cursor.lnum != Insstart.lnum
 		    || curwin->w_cursor.col >= Insstart.col)
 	{
-	    if (curwin->w_cursor.col == startcol && c != NUL)
+	    if (first_pass && c != NUL)
+	    {
 		cc = c;
+		first_pass = FALSE;
+	    }
 	    else
 		cc = gchar_cursor();
 	    if (WHITECHAR(cc))
diff --git a/src/version.c b/src/version.c
--- a/src/version.c
+++ b/src/version.c
@@ -705,6 +705,8 @@ static char *(features[]) =
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    55,
+/**/
     54,
 /**/
     53,