Fix slow operation of 'string-width'

* src/composite.c (find_automatic_composition): Accept one
additional argument BACKLIM; don't look back in buffer or string
farther than that.  Add an assertion for BACKLIM.
(composition_adjust_point, Ffind_composition_internal): Callers
adjusted.
* src/composite.h (find_automatic_composition): Adjust prototype.
* src/character.c (lisp_string_width): Call
'find_automatic_composition' with the value of BACKLIM equal to POS,
to avoid costly and unnecessary search back in the string, since
those previous characters were already checked for automatic
compositions.  (Bug#48734)  (Bug#48839)

1 files changed, 63 insertions, 13 deletions

diff --git a/src/composite.c b/src/composite.c
index 17d5914e634..129e9d6bb25 100644
--- a/src/composite.c
+++ b/src/composite.c
@@ -1473,14 +1473,60 @@ struct position_record
     (POSITION).pos--;				\
   } while (0)
 
-/* This is like find_composition, but find an automatic composition
-   instead.  It is assured that POS is not within a static
-   composition.  If found, set *GSTRING to the glyph-string
-   representing the composition, and return true.  Otherwise, *GSTRING to
-   Qnil, and return false.  */
+/* Similar to find_composition, but find an automatic composition instead.
+
+   This function looks for automatic composition at or near position
+   POS of OBJECT (a buffer or a string).  OBJECT defaults to the
+   current buffer.  It must be assured that POS is not within a static
+   composition.  Also, the current buffer must be displayed in some
+   window, otherwise the function will return FALSE.
+
+   If LIMIT is negative, and there's no composition that includes POS
+   (i.e. starts at or before POS and ends at or after POS), return
+   FALSE.  In this case, the function is allowed to look from POS as
+   far back as BACKLIM, and as far forward as POS+1 plus
+   MAX_AUTO_COMPOSITION_LOOKBACK, the maximum number of look-back for
+   automatic compositions (3) -- this is a limitation imposed by
+   composition rules in composition-function-table, which see.  If
+   BACKLIM is negative, it stands for the beginning of OBJECT: BEGV
+   for a buffer or position zero for a string.
+
+   If LIMIT is positive, search for a composition forward (LIMIT >
+   POS) or backward (LIMIT < POS).  In this case, LIMIT bounds the
+   search for the first character of a composed sequence.
+   (LIMIT == POS is the same as LIMIT < 0.)  If LIMIT > POS, the
+   function can find a composition that starts after POS.
+
+   BACKLIM limits how far back is the function allowed to look in
+   OBJECT while trying to find a position where it is safe to start
+   searching forward for compositions.  Such a safe place is generally
+   the position after a character that can never be composed.
+
+   If BACKLIM is negative, that means the first character position of
+   OBJECT; this is useful when calling the function for the first time
+   for a given buffer or string, since it is possible that a
+   composition begins before POS.  However, if POS is very far from
+   the beginning of OBJECT, a negative value of BACKLIM could make the
+   function slow.  Also, in this case the function may return START
+   and END that do not include POS, something that is not necessarily
+   wanted, and needs to be explicitly checked by the caller.
+
+   When calling the function in a loop for the same buffer/string, the
+   caller should generally set BACKLIM equal to POS, to avoid costly
+   repeated searches backward.  This is because if the previous
+   positions were already checked for compositions, there should be no
+   reason to re-check them.
+
+   If BACKLIM is positive, it must be less or equal to LIMIT.
+
+   If an automatic composition satisfying the above conditions is
+   found, set *GSTRING to the Lispy glyph-string representing the
+   composition, set *START and *END to the start and end of the
+   composed sequence, and return TRUE.  Otherwise, set *GSTRING to
+   nil, and return FALSE.  */
 
 bool
-find_automatic_composition (ptrdiff_t pos, ptrdiff_t limit,
+find_automatic_composition (ptrdiff_t pos, ptrdiff_t limit, ptrdiff_t backlim,
 			    ptrdiff_t *start, ptrdiff_t *end,
 			    Lisp_Object *gstring, Lisp_Object string)
 {
@@ -1502,13 +1548,13 @@ find_automatic_composition (ptrdiff_t pos, ptrdiff_t limit,
   cur.pos = pos;
   if (NILP (string))
     {
-      head = BEGV, tail = ZV, stop = GPT;
+      head = backlim < 0 ? BEGV : backlim, tail = ZV, stop = GPT;
       cur.pos_byte = CHAR_TO_BYTE (cur.pos);
       cur.p = BYTE_POS_ADDR (cur.pos_byte);
     }
   else
     {
-      head = 0, tail = SCHARS (string), stop = -1;
+      head = backlim < 0 ? 0 : backlim, tail = SCHARS (string), stop = -1;
       cur.pos_byte = string_char_to_byte (string, cur.pos);
       cur.p = SDATA (string) + cur.pos_byte;
     }
@@ -1516,6 +1562,9 @@ find_automatic_composition (ptrdiff_t pos, ptrdiff_t limit,
     /* Finding a composition covering the character after POS is the
        same as setting LIMIT to POS.  */
     limit = pos;
+
+  eassert (backlim < 0 || backlim <= limit);
+
   if (limit <= pos)
     fore_check_limit = min (tail, pos + 1 + MAX_AUTO_COMPOSITION_LOOKBACK);
   else
@@ -1696,8 +1745,8 @@ composition_adjust_point (ptrdiff_t last_pt, ptrdiff_t new_pt)
     return new_pt;
 
   /* Next check the automatic composition.  */
-  if (! find_automatic_composition (new_pt, (ptrdiff_t) -1, &beg, &end, &val,
-				    Qnil)
+  if (! find_automatic_composition (new_pt, (ptrdiff_t) -1, (ptrdiff_t) -1,
+				    &beg, &end, &val, Qnil)
       || beg == new_pt)
     return new_pt;
   for (i = 0; i < LGSTRING_GLYPH_LEN (val); i++)
@@ -1893,8 +1942,8 @@ See `find-composition' for more details.  */)
     {
       if (!NILP (BVAR (current_buffer, enable_multibyte_characters))
 	  && ! NILP (Vauto_composition_mode)
-	  && find_automatic_composition (from, to, &start, &end, &gstring,
-					 string))
+	  && find_automatic_composition (from, to, (ptrdiff_t) -1,
+					 &start, &end, &gstring, string))
 	return list3 (make_fixnum (start), make_fixnum (end), gstring);
       return Qnil;
     }
@@ -1902,7 +1951,8 @@ See `find-composition' for more details.  */)
     {
       ptrdiff_t s, e;
 
-      if (find_automatic_composition (from, to, &s, &e, &gstring, string)
+      if (find_automatic_composition (from, to, (ptrdiff_t) -1,
+				      &s, &e, &gstring, string)
 	  && (e <= fixed_pos ? e > end : s < start))
 	return list3 (make_fixnum (s), make_fixnum (e), gstring);
     }