Re: faster unicode character name completion

[Stefan Monnier <monnier@iro.umontreal.ca>]

>> > (defun ucs-name-completion (str)
>> >   (when (string-match "^[A-Za-z]*" str)
>> >     (let ((head (match-string 0 str))
>> > 	  slot names)
>> >       (if (and (= (length head) (length str))
>> > 	       (not (assoc-string str ucs-name-head-table)))
>> > 	  (ucs-name-filter str ucs-name-head-table)
>> > 	(ucs-name-filter str (ucs-name-expand-table head))))))

>> I don't understand what ucs-name-filter is trying to do.

> ?? It simply filters out elements that doesn't match with
> STR from NAMES (alist).

But then why is it needed?
Doesn't `completion-table-dynamic' take care of that already?

BTW, I tried the "precompute the table and autoload it" approach, and it
works fine in the sense that it's fast.  The generated file is about
1.3MB.  Basically, the main downside of this approach is that it doesn't
use the very strings we already have for the names, so after loading it
we have 2 copies of every char name in memory.

But I have a better idea: most of the time is not spent building the
completion table, but rather just weeding out all the "chars" that don't
have names, or should I say, looking for the few rare chars that do
have a name.

So the patch below seems to eb a good compromise: it uses up just about
1000K cons cells (i.e. 16KB on 64bit systems) to keep the precomputed
set of ~34K chars that do have a name, so that building the completion
table takes only a couple seconds.


        Stefan


--- mule-cmds.el.~1.383.~	2009-11-11 21:01:36.000000000 -0500
+++ mule-cmds.el	2009-12-07 09:55:16.000000000 -0500
@@ -2883,6 +2883,31 @@
 (defvar nonascii-insert-offset 0 "This variable is obsolete.")
 (defvar nonascii-translation-table nil "This variable is obsolete.")
 
+(defvar ucs-named-char-ranges
+  (purecopy
+   (eval-when-compile
+     (let ((ranges ())
+           (first 0)
+           (last 0))
+       (dotimes-with-progress-reporter (c #xEFFFF)
+           "Loading Unicode character names..."
+         (unless (or
+                  (and (>= c #x3400 ) (<= c #x4dbf )) ; CJK Ideograph Extension Arch
+                  (and (>= c #x4e00 ) (<= c #x9fff )) ; CJK Ideograph
+                  (and (>= c #xd800 ) (<= c #xfaff )) ; Private/Surrogate
+                  (and (>= c #x20000) (<= c #x2ffff)) ; CJK Ideograph Extensions B, C
+                  (null (get-char-code-property c 'name)))
+           ;; This char has a name.
+           (if (<= c (1+ last))
+               ;; Extend the current range.
+               (setq last c)
+             ;; We have to split the range.
+             (push (cons first last) ranges)
+             (setq first (setq last c)))))
+       (cons (cons first last) ranges))))
+  "List of ranges of chars that have names.
+Every range is of the form (FIRST . LAST).")
+
 (defvar ucs-names nil
   "Alist of cached (CHAR-NAME . CHAR-CODE) pairs.")
 
@@ -2891,18 +2916,16 @@
   (or ucs-names
       (setq ucs-names
 	    (let (name names)
-	      (dotimes-with-progress-reporter (c #xEFFFF)
-		  "Loading Unicode character names..."
-		(unless (or
-			 (and (>= c #x3400 ) (<= c #x4dbf )) ; CJK Ideograph Extension A
-			 (and (>= c #x4e00 ) (<= c #x9fff )) ; CJK Ideograph
-			 (and (>= c #xd800 ) (<= c #xfaff )) ; Private/Surrogate
-			 (and (>= c #x20000) (<= c #x2ffff)) ; CJK Ideograph Extensions B, C
-			 )
+              (dolist (range ucs-named-char-ranges)
+                (let ((c (car range))
+                      (end (cdr range)))
+                  (while (<= c end)
 		  (if (setq name (get-char-code-property c 'name))
-		      (setq names (cons (cons name c) names)))
+                        (setq names (cons (cons name c) names))
+                      (error "Wrong range"))
 		  (if (setq name (get-char-code-property c 'old-name))
-		      (setq names (cons (cons name c) names)))))
+                        (setq names (cons (cons name c) names)))
+                    (setq c (1+ c)))))
 	      names))))
 
 (defvar ucs-completions (lazy-completion-table ucs-completions ucs-names)