From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier via Users list for the GNU Emacs text editor Newsgroups: gmane.emacs.help Subject: Re: How are regexen implemented in Emacs? Date: Mon, 12 Dec 2022 14:17:48 -0500 Message-ID: References: <87a63see6m.fsf@mbork.pl> <877cywe8w9.fsf@mbork.pl> Reply-To: Stefan Monnier Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="38064"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) To: help-gnu-emacs@gnu.org Cancel-Lock: sha1:t9+7ZUjD39942DSrcLPGr3Tgkdk= Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Mon Dec 12 20:19:09 2022 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1p4oKT-0009WY-Fo for geh-help-gnu-emacs@m.gmane-mx.org; Mon, 12 Dec 2022 20:19:09 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1p4oJS-0005dI-FV; Mon, 12 Dec 2022 14:18:06 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1p4oJN-0005d0-SG for help-gnu-emacs@gnu.org; Mon, 12 Dec 2022 14:18:01 -0500 Original-Received: from ciao.gmane.io ([116.202.254.214]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1p4oJL-0002BX-2w for help-gnu-emacs@gnu.org; Mon, 12 Dec 2022 14:18:01 -0500 Original-Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1p4oJG-000842-Qx for help-gnu-emacs@gnu.org; Mon, 12 Dec 2022 20:17:54 +0100 X-Injected-Via-Gmane: http://gmane.org/ Received-SPF: pass client-ip=116.202.254.214; envelope-from=geh-help-gnu-emacs@m.gmane-mx.org; helo=ciao.gmane.io X-Spam_score_int: -15 X-Spam_score: -1.6 X-Spam_bar: - X-Spam_report: (-1.6 / 5.0 requ) BAYES_00=-1.9, HEADER_FROM_DIFFERENT_DOMAINS=0.25, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.help:141687 Archived-At: >>> https://www.gnu.org/software/emacs/manual/html_node/elisp/Regexp-Problems.html >>> and started to wonder if the hints there mean that Emacs has a "naive", >>> backtracking regex engine or a FA-based one? >> Naive! > And what are the reasons? Largely historical, but changing it is a lot of work with uncertain outcome: - Reproducing the exact behavior of the naive match with a non-naive match can be tricky. - The naive approach sucks when the match fails in many different ways, but it's quite efficient when the match succeeds without any backtracking. Ideally, we'd like to replace the regexp engine with a "standard one", but it's not easy to find one that satisfies all the requirements (e.g. ability to add Emacs-specific elements like \_<, \s, and \c, ability to operate on "two-part strings" (i.e. with a gap in the middle), ...). Stefan