PATCH: more sorting: multibyte case-insensitivity

PATCH: more sorting: multibyte case-insensitivity

[Peter Stephenson]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 4064 bytes --]

This extends the new sort code to handle lowering of case properly with
multibyte characters.  The locales (other than C) that I've seen mostly
seem to force case insensitivity within collate() anyway, but we might as
well do this properly.

Index: Src/sort.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/sort.c,v
retrieving revision 1.1
diff -u -r1.1 sort.c
--- Src/sort.c	21 Jan 2007 22:47:41 -0000	1.1
+++ Src/sort.c	22 Jan 2007 14:20:58 -0000
@@ -248,7 +248,8 @@
 	    || *metaptr == Meta) {
 	    char *s, *t, *src = *arrptr, *dst;
 	    int len;
-	    sortarrptr->cmp = dst = (char *)zhalloc(strlen(src) + 1);
+	    sortarrptr->cmp = dst =
+		(char *)zhalloc(((sortwhat & SORTIT_IGNORING_CASE)?2:1)*strlen(src)+1);
 
 	    if (unmetalenp) {
 		/* Already unmetafied and we have the length. */
@@ -283,8 +284,49 @@
 		len = metaptr - src;
 	    }
 	    if (sortwhat & SORTIT_IGNORING_CASE) {
-		for (s = src, t = dst; s - src != len; )
-		    *t++ = tulower(*s++);
+		char *send = src + len;
+#ifdef MULTIBYTE_SUPPORT
+		if (isset(MULTIBYTE)) {
+		    /*
+		     * Lower the case the hard way.  Convert to a wide
+		     * character, process that, and convert back.  We
+		     * don't assume the characters have the same
+		     * multibyte length.  We can't use casemodify()
+		     * because we have unmetafied data, which may have
+		     * been passed down to use.
+		     */
+		    mbstate_t mbsin, mbsout;
+		    int clen;
+		    wchar_t wc;
+		    memset(&mbsin, 0, sizeof(mbstate_t));
+		    memset(&mbsout, 0, sizeof(mbstate_t));
+
+		    for (s = src, t = dst; s < send; ) {
+			clen = mbrtowc(&wc, s, send-s, &mbsin);
+			if (clen < 0) {
+			    /* invalid or unfinished: treat as single bytes */
+			    while (s < send)
+				*t++ = tulower(*s++);
+			    break;
+			}
+			if (clen == 0) {
+			    /* embedded null */
+			    *t++ = '\0';
+			    s++;
+			    continue;
+			}
+			s += clen;
+			wc = towlower(wc);
+			clen = wcrtomb(t, wc, &mbsout);
+			t += clen;
+			DPUTS(clen < 0, "Bad conversion when lowering case");
+		    }
+		    *t = '\0';
+		    len = t - dst;
+		} else
+#endif
+		    for (s = src, t = dst; s < send; )
+			*t++ = tulower(*s++);
 		src = dst;
 	    }
 	    if (sortwhat & SORTIT_IGNORING_BACKSLASHES) {
Index: Test/B03print.ztst
===================================================================
RCS file: /cvsroot/zsh/zsh/Test/B03print.ztst,v
retrieving revision 1.18
diff -u -r1.18 B03print.ztst
--- Test/B03print.ztst	21 Jan 2007 22:47:42 -0000	1.18
+++ Test/B03print.ztst	22 Jan 2007 14:20:58 -0000
@@ -34,7 +34,12 @@
 >baz
 >bar
 
- print -io a B c
+# some locales 
+ (LC_ALL=C; print -o a B c)
+0:case-sensitive argument sorting
+>B a c
+
+ (LC_ALL=C; print -io a B c)
 0:case-insensitive argument sorting
 >a B c
 
Index: Test/D07multibyte.ztst
===================================================================
RCS file: /cvsroot/zsh/zsh/Test/D07multibyte.ztst,v
retrieving revision 1.13
diff -u -r1.13 D07multibyte.ztst
--- Test/D07multibyte.ztst	9 Jan 2007 21:45:45 -0000	1.13
+++ Test/D07multibyte.ztst	22 Jan 2007 14:20:58 -0000
@@ -2,6 +2,8 @@
 
 # Find a UTF-8 locale.
   setopt multibyte
+# Don't let LC_* override our choice of locale.
+  unset -m LC_\*
   mb_ok=
   langs=(en_US.UTF-8 en_GB.UTF-8 en.UTF-8
 	 $(locale -a 2>/dev/null | sed -e 's/utf8/UTF-8/' | grep UTF-8))
@@ -315,3 +317,12 @@
   printf "%4.3s\n" főobar
 0:Multibyte characters in printf widths
 > főo
+
+# We ask for case-insensitive sorting here (and supply upper case
+# characters) so that we exercise the logic in the shell that lowers the
+# case of the string for case-insensitive sorting.
+  print -oi HAH HUH HEH HÉH HÈH
+  (LC_ALL=C; print -oi HAH HUH HEH HÉH HÈH)
+0:Multibyte characters in print sorting
+>HAH HEH HÉH HÈH HUH
+>HAH HEH HUH HÈH HÉH

-- 
Peter Stephenson <pws@csr.com>                  Software Engineer
CSR PLC, Churchill House, Cambridge Business Park, Cowley Road
Cambridge, CB4 0WZ, UK                          Tel: +44 (0)1223 692070

Re: PATCH: more sorting: multibyte case-insensitivity

[Bart Schaefer]

On Jan 22,  2:23pm, Peter Stephenson wrote:
}
} This extends the new sort code to handle lowering of case properly with
} multibyte characters.

I'm beginning to worry that we're piling up some pretty severe performance
penalties with this stuff.  Zsh was already about 1/3 the speed of bash on
some benchmarks, as I recall.  Has anyone lately compared a recent CVS
build to something a bit older?

Re: PATCH: more sorting: multibyte case-insensitivity

[Peter Stephenson]

Bart Schaefer wrote:
> On Jan 22,  2:23pm, Peter Stephenson wrote:
> }
> } This extends the new sort code to handle lowering of case properly with
> } multibyte characters.
> 
> I'm beginning to worry that we're piling up some pretty severe performance
> penalties with this stuff.  Zsh was already about 1/3 the speed of bash on
> some benchmarks, as I recall.  Has anyone lately compared a recent CVS
> build to something a bit older?

"unsetopt MULTIBYTE" is supposed to get you pretty much back to where we
were before if you don't care about multibyte characters.  I'm not aware
of a general solution to the efficiency problem with proper multibyte
handling.

In this particular case, it should be more efficient than before, at
least with a long list to sort, since now the strings are transformed
once each instead of every time two strings are compared.

I haven't done any benchmarking.  At the moment I'm happy if it works.

-- 
Peter Stephenson <pws@csr.com>                  Software Engineer
CSR PLC, Churchill House, Cambridge Business Park, Cowley Road
Cambridge, CB4 0WZ, UK                          Tel: +44 (0)1223 692070


To access the latest news from CSR copy this link into a web browser:  http://www.csr.com/email_sig.php

To get further information regarding CSR, please visit our Investor Relations page at http://ir.csr.com/csr/about/overview

Re: PATCH: more sorting: multibyte case-insensitivity

[Nikolai Weibull]

On 1/22/07, Bart Schaefer <schaefer@brasslantern.com> wrote:

> On Jan 22,  2:23pm, Peter Stephenson wrote:

> } This extends the new sort code to handle lowering of case properly with
> } multibyte characters.

> I'm beginning to worry that we're piling up some pretty severe performance
> penalties with this stuff.

I'll trade almost any amount of performance for proper handling of
multibyte characters.

  nikolai