From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Le Wang Newsgroups: gmane.emacs.devel Subject: Re: Emacs needs truely useful flex matching Date: Fri, 22 Mar 2013 09:00:14 +0800 Message-ID: References: <877gl0od6x.fsf@wanadoo.es> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 X-Trace: ger.gmane.org 1363914029 5653 80.91.229.3 (22 Mar 2013 01:00:29 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 22 Mar 2013 01:00:29 +0000 (UTC) Cc: =?ISO-8859-1?Q?=D3scar_Fuentes?= , emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Mar 22 02:00:55 2013 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1UIqLk-0005je-Rz for ged-emacs-devel@m.gmane.org; Fri, 22 Mar 2013 02:00:52 +0100 Original-Received: from localhost ([::1]:49245 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UIqLN-0001QD-Ht for ged-emacs-devel@m.gmane.org; Thu, 21 Mar 2013 21:00:29 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:41326) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UIqLE-0001PQ-U6 for emacs-devel@gnu.org; Thu, 21 Mar 2013 21:00:26 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UIqLA-0006oT-1q for emacs-devel@gnu.org; Thu, 21 Mar 2013 21:00:20 -0400 Original-Received: from mail-wi0-x22a.google.com ([2a00:1450:400c:c05::22a]:32939) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UIqL9-0006oL-RO for emacs-devel@gnu.org; Thu, 21 Mar 2013 21:00:15 -0400 Original-Received: by mail-wi0-f170.google.com with SMTP id hm11so7958826wib.5 for ; Thu, 21 Mar 2013 18:00:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:in-reply-to:references:date:message-id :subject:from:to:cc:content-type; bh=7gq0Ywjn4EUYOwgco+Z8oeTvzippkyyGymJnKcaYzDo=; b=qcR4DE+iICWmFFQgPzG1ecgtWLVXo6D4QWw1uv89Uovj5k+ocAy49tIsdSjTsWSThr HRQzui5rkHVVXB6eiaVB9qVoJWoxz2ZwzHLi5TpiGeoLMfsq0Aoq/XEGfH/nq9OtVoo4 OzeLAcOtC97MpZYZ2YhIP2jdGlcqPEcqYLzL7qLVs91Q3V2PvVdCBJneap6hrW/893Zd GgnSrs7DEVhlon7w3anKYTcwZZglabn9ohQKTFgkyWAjNX2xcWl1EGr3E42lI2sWAG7q Eq5ZO0F6na+wviBNEkrAlX94BoivORU7e4vz+TvALMIjGS9r4r0OZLsJGqLpMNvkhGG0 aWLw== X-Received: by 10.180.84.162 with SMTP id a2mr7898974wiz.14.1363914014820; Thu, 21 Mar 2013 18:00:14 -0700 (PDT) Original-Received: by 10.217.116.8 with HTTP; Thu, 21 Mar 2013 18:00:14 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:400c:c05::22a X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:158047 Archived-At: On Fri, Mar 22, 2013 at 7:58 AM, Stefan Monnier wrote: >>> The sorting algorithm is roughly this for a query: "abcd" >>> >>> 1. Get all matches for "a.*b.*c.*c" >>> 2. Calculate score of each match >>> - contiguous matched chars gets a boost >>> - matches at word and camelCase boundaries (abbreviation) get a boost >>> - matches with smallest starting index gets a boost >>> 2. Sort list according to score. > > I think that if you turn "abcd" into a regexp of the form > "\\(\\<\\)?a\\([^b]*\\)\\(\\<\\)?b\\([^c]*\\)\\(\\<\\)?c\\([^d]*\\)\\(\\<\\)?d" > the regexp matching should be fairly efficient and you should be able to > compute the score efficiently as well (at least if > you ignore the camelCase boundaries). I hadn't thought of this, and I'll try it soon. > Have you tried such an approach and it really was too slow? > I'd welcome a new completion-style using the above flex matching. You're right that in generally that my claim of "emacs-lisp would be too slow" needs to be verified. >> IIUC the vim plugin you mention depends on a pre-built list of files. > > Indeed when searching for a file in a file hierarchy, you'd need > a pre-built list of files, otherwise the time taken to find the files > would dwarf the flex-matching time in any case. "git ls-files" is very fast on a solid state drive, and the list can also be cached. But let's assume we already have the list of strings. -- Le