[Updated] D12089: encoding: fix trim() to be O(n) instead of O(n^2)

[martinvonz (Martin von Zweigbergk)]

Closed by commit rHGf1ed5c304f45: encoding: fix trim() to be O(n) instead of O(n^2) (authored by martinvonz).
This revision was automatically updated to reflect the committed changes.
This revision was not accepted when it landed; it landed in state "Needs Review".

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D12089?vs=31981&id=31982

CHANGES SINCE LAST ACTION
  https://phab.mercurial-scm.org/D12089/new/

REVISION DETAIL
  https://phab.mercurial-scm.org/D12089

AFFECTED FILES
  mercurial/encoding.py

CHANGE DETAILS

diff --git a/mercurial/encoding.py b/mercurial/encoding.py
--- a/mercurial/encoding.py
+++ b/mercurial/encoding.py
@@ -511,17 +511,21 @@
     if width <= 0:  # no enough room even for ellipsis
         return ellipsis[: width + len(ellipsis)]
 
+    chars = list(u)
     if leftside:
-        uslice = lambda i: u[i:]
-        concat = lambda s: ellipsis + s
-    else:
-        uslice = lambda i: u[:-i]
-        concat = lambda s: s + ellipsis
-    for i in pycompat.xrange(1, len(u)):
-        usub = uslice(i)
-        if ucolwidth(usub) <= width:
-            return concat(usub.encode(_sysstr(encoding)))
-    return ellipsis  # no enough room for multi-column characters
+        chars.reverse()
+    width_so_far = 0
+    for i, c in enumerate(chars):
+        width_so_far += ucolwidth(c)
+        if width_so_far > width:
+            break
+    chars = chars[:i]
+    if leftside:
+        chars.reverse()
+    u = u''.join(chars).encode(_sysstr(encoding))
+    if leftside:
+        return ellipsis + u
+    return u + ellipsis
 
 
 class normcasespecs(object):



To: martinvonz, #hg-reviewers
Cc: mercurial-patches
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mercurial-scm.org/pipermail/mercurial-patches/attachments/20220126/74df65df/attachment-0002.html>