From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Stephen J. Turnbull" Newsgroups: gmane.emacs.devel Subject: Re: Possible problem with looking-back function Date: Thu, 19 Aug 2010 18:02:24 +0900 Message-ID: <8739ubug9r.fsf@uwakimon.sk.tsukuba.ac.jp> 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=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: dough.gmane.org 1282209711 2795 80.91.229.12 (19 Aug 2010 09:21:51 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 19 Aug 2010 09:21:51 +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 11:21:49 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 1Om1Ji-0005D4-T9 for ged-emacs-devel@m.gmane.org; Thu, 19 Aug 2010 11:21:47 +0200 Original-Received: from localhost ([127.0.0.1]:54672 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Om1Jh-0006eZ-Ro for ged-emacs-devel@m.gmane.org; Thu, 19 Aug 2010 05:21:45 -0400 Original-Received: from [140.186.70.92] (port=54168 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Om1JY-0006dl-1i for emacs-devel@gnu.org; Thu, 19 Aug 2010 05:21:36 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1Om1JX-0004fI-21 for emacs-devel@gnu.org; Thu, 19 Aug 2010 05:21:35 -0400 Original-Received: from [130.158.254.170] (port=48436 helo=dmail01.cc.tsukuba.ac.jp) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1Om1JW-0004eR-QO for emacs-devel@gnu.org; Thu, 19 Aug 2010 05:21:35 -0400 Original-Received: from imss12.cc.tsukuba.ac.jp (unknown [130.158.254.130]) by dmail01.cc.tsukuba.ac.jp (Postfix) with ESMTP id 8A353F50B7 for ; Thu, 19 Aug 2010 18:05:19 +0900 (JST) Original-Received: from imss12.cc.tsukuba.ac.jp (imss12.cc.tsukuba.ac.jp [127.0.0.1]) by postfix.imss70 (Postfix) with ESMTP id 61BF7F4004; Thu, 19 Aug 2010 18:05:10 +0900 (JST) Original-Received: from mgmt2.sk.tsukuba.ac.jp (unknown [130.158.97.224]) by imss12.cc.tsukuba.ac.jp (Postfix) with ESMTP id 53BB4F4002; Thu, 19 Aug 2010 18:05:10 +0900 (JST) Original-Received: from uwakimon.sk.tsukuba.ac.jp (uwakimon.sk.tsukuba.ac.jp [130.158.99.156]) by mgmt2.sk.tsukuba.ac.jp (Postfix) with ESMTP id 51698970283; Thu, 19 Aug 2010 18:05:10 +0900 (JST) Original-Received: by uwakimon.sk.tsukuba.ac.jp (Postfix, from userid 1000) id D50581A2C38; Thu, 19 Aug 2010 18:02:24 +0900 (JST) In-Reply-To: <4C6CCA8B.5060106@online.de> X-Mailer: VM undefined under 21.5 (beta29) "garbanzo" ed3b274cc037 XEmacs Lucid (x86_64-unknown-linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) 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:128864 Archived-At: Andreas R=F6hler writes: > that surprises me. Check must be done against the string already > found. So workload should grow lineary resp. slightly ascending. That's incorrect. In regexp matching abstractly defined, there is no "string already matched." In general backtracking must be done to get a correct POSIX match, and it's potentially very expensive. It would be sometimes possible (as in this case) to identify a non-backtracking algorithm as you suggest, but that would mean that different regexps would be treated differently, or that some regexps would be ridiculously expensive.