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 "Bug reports for GNU Emacs, the Swiss army knife of text editors" Newsgroups: gmane.emacs.bugs Subject: bug#65726: 29.1.50; Crash in regexp engine Date: Fri, 15 Sep 2023 23:45:33 -0400 Message-ID: References: <8e1b4e50-0430-3eb3-e486-60def1e4821f@gmx.at> <83fs3u5e7u.fsf@gnu.org> <835y4q5apw.fsf@gnu.org> <776370AB-662F-4C0A-95BF-97DEA4F18F54@gmail.com> <3A0AC9E2-A420-47B6-870A-69C53FCAEF71@gmail.com> 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="28087"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: martin rudalics , Eli Zaretskii , 65726@debbugs.gnu.org To: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sat Sep 16 05:46:14 2023 Return-path: Envelope-to: geb-bug-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 1qhMG5-0006yc-Pt for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 16 Sep 2023 05:46:14 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qhMFr-0003HT-U7; Fri, 15 Sep 2023 23:46:00 -0400 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 1qhMFo-0003Gy-Ep for bug-gnu-emacs@gnu.org; Fri, 15 Sep 2023 23:45:57 -0400 Original-Received: from debbugs.gnu.org ([2001:470:142:5::43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1qhMFo-0003bU-6U for bug-gnu-emacs@gnu.org; Fri, 15 Sep 2023 23:45:56 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1qhMFu-0004FZ-CW for bug-gnu-emacs@gnu.org; Fri, 15 Sep 2023 23:46:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 16 Sep 2023 03:46:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 65726 X-GNU-PR-Package: emacs Original-Received: via spool by 65726-submit@debbugs.gnu.org id=B65726.169483595416321 (code B ref 65726); Sat, 16 Sep 2023 03:46:02 +0000 Original-Received: (at 65726) by debbugs.gnu.org; 16 Sep 2023 03:45:54 +0000 Original-Received: from localhost ([127.0.0.1]:45151 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qhMFl-0004FA-Fd for submit@debbugs.gnu.org; Fri, 15 Sep 2023 23:45:53 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:15162) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qhMFf-0004Et-OQ for 65726@debbugs.gnu.org; Fri, 15 Sep 2023 23:45:51 -0400 Original-Received: from pmg2.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 7F855805D6; Fri, 15 Sep 2023 23:45:35 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1694835934; bh=XgP9NEHtAcLOldGDNvBCMuaH+6Km0ejy5oW/rFsqVDU=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=ay7V0bXgHPqmWY4n6CSX+s3yHt9XXFrhHlxPWa12erSGBCe5WacOsm6IQopaRvrXf w/xiVZ0BWQe8dZszYQijkAV8fuiMgdwDEReLTSl1SMwMh0A/FHGacloAHxzaWd9Qjp h3ZkxQfH6VRP7zG80RtJKtJNcET5bJJN8WeGn84I24hA7Ezpj2K2DtVsLo8b7uD6Ys WBGbDE57D6RjZt2UvAzi0UiSRNBK6ld7xdZUJ3EyQ/kP498MOewFCkF1FfkcYcHmvv lLVNjXry4rmY7trrx5TMOuSJqUioLORfvPqbpE0Mt3cRDb1o1lUvBYgFTxDgWHH1+9 cRaIayUuT8j5w== Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 1A854803B1; Fri, 15 Sep 2023 23:45:34 -0400 (EDT) Original-Received: from pastel (unknown [104.247.237.102]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id DF1A612023D; Fri, 15 Sep 2023 23:45:33 -0400 (EDT) In-Reply-To: (Stefan Monnier's message of "Thu, 14 Sep 2023 10:41:30 -0400") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:270572 Archived-At: >> so yes, we may need to remember where we've been. (At this point >> someone will inevitably point out a helpful invariant that is obvious >> in hindsight. This is just my cunning attempt at making that happen.) I think I have a "helpful invariant", finally: Because of how we build our code, when we're at an `on_failure_jump` the two branches can either both go forward (typically for a "|" or a "?"), or *one* of them goes backward the other forward (for loops), where the one that goes backward (i.e. `p2 <= p2_orig`) is the edge (call it `p2_loop`) that goes back to the beginning of the loop and the other (call it `p2_exit`) is the one that exits the loop. Now, because our loops are nested with proper "structured programming", there can't be any jump from within the loop to outside the loop except for the current jump. And there can't be any jump from outside the loop to inside the loop except by entering via `p2_loop`. Since we have two recursive calls to `mutually_exclusive_p` (one for `p2_exit` and one for `p2_loop`) and each one only needs to check those positions not checked by the other, we can say that `p2_loop` only needs to check the positions within the loop (i.e. between `p2_loop` and `p2_exit`) and can presume that *all* other positions are checked by the other recursive call (the one that starts at `p2_exit`). So I think a single arg `done_end` (set, like the current `done_end`, to `p2_loop` when recursing into `p2_loop`) is indeed sufficient: there's no way to go from `p2_loop` to before `p2_loop` without first going to `p2_exit` (which is already checked by the other call). Stefan