From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Noam Postavsky Newsgroups: gmane.emacs.bugs Subject: bug#36444: [PATCH] Improved regexp-opt KEEP-ORDER check Date: Wed, 03 Jul 2019 15:29:33 -0400 Message-ID: <85v9wiex2a.fsf@gmail.com> References: <2CE5D98F-8F07-4E79-9132-FDBA0062D8E2@acm.org> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="106006"; mail-complaints-to="usenet@blaine.gmane.org" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.1.92 (windows-nt) Cc: 36444@debbugs.gnu.org To: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Wed Jul 03 21:30:12 2019 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.89) (envelope-from ) id 1hikxI-000RU7-Eb for geb-bug-gnu-emacs@m.gmane.org; Wed, 03 Jul 2019 21:30:12 +0200 Original-Received: from localhost ([::1]:39690 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.86_2) (envelope-from ) id 1hikxH-0003lT-Dq for geb-bug-gnu-emacs@m.gmane.org; Wed, 03 Jul 2019 15:30:11 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:47461) by lists.gnu.org with esmtp (Exim 4.86_2) (envelope-from ) id 1hikxA-0003kH-0O for bug-gnu-emacs@gnu.org; Wed, 03 Jul 2019 15:30:04 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1hikx9-0007qT-1Y for bug-gnu-emacs@gnu.org; Wed, 03 Jul 2019 15:30:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:41283) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1hikx8-0007qK-UC for bug-gnu-emacs@gnu.org; Wed, 03 Jul 2019 15:30:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1hikx8-0008G2-Mc for bug-gnu-emacs@gnu.org; Wed, 03 Jul 2019 15:30:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Noam Postavsky Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 03 Jul 2019 19:30:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 36444 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 36444-submit@debbugs.gnu.org id=B36444.156218218331693 (code B ref 36444); Wed, 03 Jul 2019 19:30:02 +0000 Original-Received: (at 36444) by debbugs.gnu.org; 3 Jul 2019 19:29:43 +0000 Original-Received: from localhost ([127.0.0.1]:50104 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1hikwp-0008F7-6V for submit@debbugs.gnu.org; Wed, 03 Jul 2019 15:29:43 -0400 Original-Received: from mail-io1-f44.google.com ([209.85.166.44]:45635) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1hikwm-0008Es-Q8 for 36444@debbugs.gnu.org; Wed, 03 Jul 2019 15:29:41 -0400 Original-Received: by mail-io1-f44.google.com with SMTP id e3so7207481ioc.12 for <36444@debbugs.gnu.org>; Wed, 03 Jul 2019 12:29:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-transfer-encoding; bh=5X5Jx80KEFWaNHNXaekN4sUuVWe9G/y+7VeHRb4w/Hc=; b=kyNwB901BxSCXPs9ieZn2gLW9UCyVJigVTpzSxnpHqxSLLK8UCykQyaSvyZgl9dyY4 Nh8IWRBAPnzN3+YXsIaJhzSMXWs6l4oIketsUx1mTDqPwNKcT/d+KBYTc6V4X6WihY1a xAHkfum2F+fDFL7RZmr2vOksXOWNG97GV2DSzyBNBKGp6i44uFhSkaw8vCT90ni+eA6d izeLnP6zgMJpdYr+Hd0MlfckwqXHb3o/xRnOA/1TTRw75WBeXyOIH3MHzWR28xUewClT HU8fseKyV2nNxVLJ7n+dMJCQb+au0Xl4qB3Ly6B3keIEaOomUspK1L2kHGABzljpj2Ax Flfw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to :message-id:user-agent:mime-version:content-transfer-encoding; bh=5X5Jx80KEFWaNHNXaekN4sUuVWe9G/y+7VeHRb4w/Hc=; b=LC/PMW2KmpwNMBqfifZZ1yPi/FlYZDwjmiGmRz1xnzM3IKh9XzwyVmVAN7vKMxUABg bzTNgn1jLSIPPubb0DInnvxi1rp6K1Hu3gCcxJphRAjYKo/TQdA0L4wCpWbBcuVkLvNA W+Mq9eFumbIDqwXujNm/OdO5Aw9KjnIzaV/gx6JMyQU3cCvD9xpKMVPtGuI8fayoKjUW YmdDPdMFAJmgnH0/3EEUaXxcdTOj70BxDYsrF5rIAR5m+SDiGI+z338iMffCjhNIoD7A 4cZxV/S7j1qmuM7GvqqwW7cbn44NosbcvdSQ6DVC9LYMewW37Dl/iU2ytGU6f2kVdIN0 bA0w== X-Gm-Message-State: APjAAAUJYGrPrsoipSS+ixdaFrMY7zGh+MXGbr085x1Vuw//MxhJdFwx Bs0D8uPuqka65dFb+JF0Od9cKsxC X-Google-Smtp-Source: APXvYqyYXwiCPchrymrP9KN4IOKOwSthigYjLu1pIqCqLf4xFo1WVg4RalWjV1gGQbpW2MeMQ1WndA== X-Received: by 2002:a02:aa1d:: with SMTP id r29mr22796419jam.127.1562182174878; Wed, 03 Jul 2019 12:29:34 -0700 (PDT) Original-Received: from vhost2 (CPE001143542e1f-CMf81d0f809fa0.cpe.net.cable.rogers.com. [99.230.51.196]) by smtp.gmail.com with ESMTPSA id a2sm2765808iod.57.2019.07.03.12.29.33 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 03 Jul 2019 12:29:33 -0700 (PDT) In-Reply-To: <2CE5D98F-8F07-4E79-9132-FDBA0062D8E2@acm.org> ("Mattias \=\?iso-8859-1\?Q\?Engdeg\=E5rd\=22's\?\= message of "Sun, 30 Jun 2019 14:28:57 +0200") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 209.51.188.43 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.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:162030 Archived-At: Mattias Engdeg=E5rd writes: > + ;; The algorithm will generate a pattern that matches > + ;; longer strings in the list before shorter. If the > + ;; list order matters, then no string must come after a > + ;; proper prefix of that string. To check this, verify > + ;; that a straight or-pattern matches each string > + ;; entirely. > + ((and keep-order > + (let* ((case-fold-search nil) > + (alts (mapconcat #'regexp-quote strings "\\|")= )) > + (and (save-match-data You don't actually need this save-match-data, right? Because there is already one at the top level of the function (which I'm also not sure is really needed, but probably best not to touch that). > + (let ((s strings)) > + (while (and s > + (string-match alts (car s)) > + (=3D (match-end 0) (length (ca= r s)))) > + (setq s (cdr s))) > + s)) > + (concat (or open "\\(?:") alts "\\)"))))) IMO, a dolist + catch & throw would be a bit more readable; it took me some puzzling to realize that the early exit was the "non-optimized" case. (and keep-order (let* ((case-fold-search nil) (alts (mapconcat #'regexp-quote strings "\\|"))) (and (catch 'has-prefix (dolist (s strings) (unless (and (string-match alts s) (=3D (match-end 0) (length s))) (throw 'has-prefix s)))) (concat (or open "\\(?:") alts "\\)"))))