From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Possible problem with looking-back function Date: Thu, 19 Aug 2010 10:01:53 +0200 Message-ID: References: <4C6C85AD.1010500@ig.com.br> <49933.130.55.132.107.1282185810.squirrel@webmail.lanl.gov> <4C6CCA8B.5060106@online.de> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1282205354 9359 80.91.229.12 (19 Aug 2010 08:09:14 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 19 Aug 2010 08:09:14 +0000 (UTC) Cc: Emacs developers To: Andreas =?iso-8859-1?Q?R=F6hler?= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Aug 19 10:09:13 2010 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Om0BT-0001xl-FI for ged-emacs-devel@m.gmane.org; Thu, 19 Aug 2010 10:09:11 +0200 Original-Received: from localhost ([127.0.0.1]:52211 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Om0BS-0000L1-RI for ged-emacs-devel@m.gmane.org; Thu, 19 Aug 2010 04:09:10 -0400 Original-Received: from [140.186.70.92] (port=38664 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Om0BC-0000Cu-DW for emacs-devel@gnu.org; Thu, 19 Aug 2010 04:08:55 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1Om04S-0001Ql-L0 for emacs-devel@gnu.org; Thu, 19 Aug 2010 04:01:57 -0400 Original-Received: from impaqm2.telefonica.net ([213.4.138.2]:15773) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1Om04S-0001QU-Ej for emacs-devel@gnu.org; Thu, 19 Aug 2010 04:01:56 -0400 Original-Received: from IMPmailhost3.adm.correo ([10.20.102.124]) by IMPaqm2.telefonica.net with bizsmtp id w7RQ1e0062h2L9m3M81uzl; Thu, 19 Aug 2010 10:01:54 +0200 Original-Received: from ceviche.home ([83.61.35.93]) by IMPmailhost3.adm.correo with BIZ IMP id w81t1e00820aCvn1j81tca; Thu, 19 Aug 2010 10:01:54 +0200 X-Brightmail-Tracker: AAAAAA== X-TE-authinfo: authemail="monnier$movistar.es" |auth_email="monnier@movistar.es" X-TE-AcuTerraCos: auth_cuTerraCos="cosuitnetc01" Original-Received: by ceviche.home (Postfix, from userid 20848) id 2340C660E9; Thu, 19 Aug 2010 10:01:53 +0200 (CEST) In-Reply-To: <4C6CCA8B.5060106@online.de> ("Andreas =?iso-8859-1?Q?R=F6hle?= =?iso-8859-1?Q?r=22's?= message of "Thu, 19 Aug 2010 08:09:15 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:128863 Archived-At: >>> Shouldn't it return 1? Not according to the docstring: If GREEDY is non-nil, extend the match backwards as far as possible, stopping when a single additional previous character cannot be part of a match for REGEXP. When the match is extended, its starting position is allowed to occur before LIMIT. >> The algorithm searches backward until it finds a position from which there >> is a match that extends to point. Doing more would be quadratic Actually our regexp matcher (i.e. "looking-at") is already much worse than quadratic in worst-case complexity. > AFAIK exists a bug, resp. missing implementation in re-search-backward. Ignoring back-references, our regexps are pretty much within the "regular language" domain, so in theory matching and searching can be performed in linear time. But our regexp engine uses a backtracking implementation, so it's not even close to linear. And the "backward" matcher is not implemented, so we "simulate" it with a forward matcher, which is why looking-back is slow and doesn't behave like we want. Stefan