Another way to address the ido flex matching performance problem (bug#12796)

gistfile1.diff

From 0aa950d6989e4129c53390422dcd1173189082e7 Mon Sep 17 00:00:00 2001
From: Leo Liu <sdl.web@gmail.com>
Date: Wed, 7 Nov 2012 21:14:45 +0800
Subject: [PATCH] Optimise flex matching with ido-chars-in-string

---
 lisp/ido.el | 26 ++++++++++++++++++++------
 1 file changed, 20 insertions(+), 6 deletions(-)

diff --git a/lisp/ido.el b/lisp/ido.el
index 31d5279d..95cd0d26 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3710,6 +3710,24 @@ (defun ido-get-bufname (win)
 		(cons buf ido-bufs-in-frame)))))
 
 ;;; FIND MATCHING ITEMS
+(defun ido-chars-in-string (chars str)
+  "Return non-nil if CHARS orderly appears in STR."
+  (let ((p 0)
+	(len (length chars))
+	c)
+    (catch 'exit
+      (when (zerop len)
+	(throw 'exit t))
+      (when (zerop (length str))
+	(throw 'exit nil))
+      (setq c (aref chars 0))
+      (dotimes (i (length str))
+	(when (char-equal (aref str i) c)
+	  (setq p (1+ p))
+	  (when (>= p len)
+	    (throw 'exit t))
+	  (setq c (aref chars p))))
+      (>= p len))))
 
 (defun ido-set-matches-1 (items &optional do-full)
   ;; Return list of matches in items
@@ -3783,14 +3801,10 @@ (defun ido-set-matches-1 (items &optional do-full)
 	       ido-enable-flex-matching
 	       (> (length ido-text) 1)
 	       (not ido-enable-regexp))
-      (setq re (mapconcat #'regexp-quote (split-string ido-text "") ".*"))
-      (if ido-enable-prefix
-	  (setq re (concat "\\`" re)))
       (mapc
        (lambda (item)
-	 (let ((name (ido-name item)))
-	   (if (string-match re name)
-	       (setq matches (cons item matches)))))
+	 (if (ido-chars-in-string ido-text (ido-name item))
+	     (setq matches (cons item matches))))
        items))
     matches))
 
-- 
1.8.0