master f93f3b8: Fix slow operation of 'string-width'

[Eli Zaretskii]

branch: master
commit f93f3b80dde20a0c643b011d1bf78e34860870a2
Author: Eli Zaretskii <eliz@gnu.org>
Commit: Eli Zaretskii <eliz@gnu.org>

    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)
---
 src/character.c |  3 ++-
 src/composite.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++----------
 src/composite.h |  6 ++---
 3 files changed, 68 insertions(+), 17 deletions(-)

diff --git a/src/character.c b/src/character.c
index 70e6896..38a81d3 100644
--- a/src/character.c
+++ b/src/character.c
@@ -375,7 +375,8 @@ lisp_string_width (Lisp_Object string, ptrdiff_t from, 
ptrdiff_t to,
       else if (auto_comp
               && f && FRAME_WINDOW_P (f)
               && multibyte
-              && find_automatic_composition (i, -1, &ignore, &end, &val, 
string)
+              && find_automatic_composition (i, -1, i, &ignore,
+                                             &end, &val, string)
               && end > i)
        {
          int j;
diff --git a/src/composite.c b/src/composite.c
index 17d5914..129e9d6 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);
     }
diff --git a/src/composite.h b/src/composite.h
index 75e5f9b..660b1fa 100644
--- a/src/composite.h
+++ b/src/composite.h
@@ -320,9 +320,9 @@ extern bool composition_gstring_p (Lisp_Object);
 extern int composition_gstring_width (Lisp_Object, ptrdiff_t, ptrdiff_t,
                                       struct font_metrics *);
 
-extern bool find_automatic_composition (ptrdiff_t, ptrdiff_t, ptrdiff_t *,
-                                       ptrdiff_t *, Lisp_Object *,
-                                       Lisp_Object);
+extern bool find_automatic_composition (ptrdiff_t, ptrdiff_t, ptrdiff_t,
+                                       ptrdiff_t *, ptrdiff_t *,
+                                       Lisp_Object *, Lisp_Object);
 
 extern void composition_compute_stop_pos (struct composition_it *,
                                           ptrdiff_t, ptrdiff_t, ptrdiff_t,