From debbugs-submit-bounces@debbugs.gnu.org Mon Mar 30 10:46:06 2015 Received: (at submit) by debbugs.gnu.org; 30 Mar 2015 14:46:06 +0000 Received: from localhost ([127.0.0.1]:40583 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Ycax4-0001w2-67 for submit@debbugs.gnu.org; Mon, 30 Mar 2015 10:46:06 -0400 Received: from eggs.gnu.org ([208.118.235.92]:35189) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Ycax1-0001vQ-PY for submit@debbugs.gnu.org; Mon, 30 Mar 2015 10:46:04 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Ycawv-0004n5-9B for submit@debbugs.gnu.org; Mon, 30 Mar 2015 10:45:58 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-0.5 required=5.0 tests=BAYES_05,FREEMAIL_FROM autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:58648) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ycawv-0004my-7B for submit@debbugs.gnu.org; Mon, 30 Mar 2015 10:45:57 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:36892) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ycawu-0001P4-9D for bug-gnu-emacs@gnu.org; Mon, 30 Mar 2015 10:45:57 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Ycawq-0004m5-Et for bug-gnu-emacs@gnu.org; Mon, 30 Mar 2015 10:45:56 -0400 Received: from mxin.ulb.ac.be ([164.15.128.112]:17636) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ycawq-0004lw-9P for bug-gnu-emacs@gnu.org; Mon, 30 Mar 2015 10:45:52 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: As4SAP1gGVWkD4Xx/2dsb2JhbABcg1hcgkWvVAaTHod1AQEBAQEBfUEBAYRpJDQBBIh2ARQNog+RN5BdAYZNhg+CM4d8hBcFlE2GA4FWhSKNPSKBRQELAYIePDEBgkIBAQE Received: from mathsrv4.ulb.ac.be (HELO localhost) ([164.15.133.241]) by smtp.ulb.ac.be with ESMTP; 30 Mar 2015 16:45:37 +0200 From: Nicolas Richard To: bug-gnu-emacs@gnu.org Subject: 24.4.91; slow regexp Date: Mon, 30 Mar 2015 16:46:45 +0200 Message-ID: <87619iv8yy.fsf@yahoo.fr> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.91 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) Consider this snippet: (with-temp-buffer (insert "**** foo\n") (insert ":PROPERTIES:\n") (dotimes (_ 7) (insert ":a: \n")) (insert ":bar: foo\n\n:END:") (goto-char 10) ;; beginning of second line (looking-at "^[ ]*:PROPERTIES:[ ]* \\(?:[ ]*:\\S-+:\\(?: .*\\)?[ ]* \\)*[ ]*:END:[ ]*$")) If that doesn't take several seconds, increasing the number 7 to 8, 9 or more probably will. It does for me. The regexp is one from org mode. (It was suggested that a file this as a separate bug report in http://debbugs.gnu.org/cgi/bugreport.cgi?bug=20191#28) -- Nicolas From debbugs-submit-bounces@debbugs.gnu.org Sun Jun 26 14:49:17 2016 Received: (at 20230) by debbugs.gnu.org; 26 Jun 2016 18:49:18 +0000 Received: from localhost ([127.0.0.1]:57036 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bHF7N-0005Af-ND for submit@debbugs.gnu.org; Sun, 26 Jun 2016 14:49:17 -0400 Received: from mail-oi0-f66.google.com ([209.85.218.66]:32826) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bHF7L-0005AM-Qt for 20230@debbugs.gnu.org; Sun, 26 Jun 2016 14:49:16 -0400 Received: by mail-oi0-f66.google.com with SMTP id w141so27068775oia.0 for <20230@debbugs.gnu.org>; Sun, 26 Jun 2016 11:49:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:from:date:message-id:subject:to:cc; bh=/5oVgw0VP0LR3W8nQrlx/QjN+tgrJQbhUlUiQEhvBzg=; b=iIdRTlJzwG3VjPTfNAAy0J8o1/OoKMegiy8xeMHm2klV9Dz/8iFQoYQQgJkakrO5AP +ypa8fulOQOy0ZxDzI4MCVFZYDWzvBfzsXpN8Uc69qZgYQqg6RUSU0Q4GqAk6FCcJGNr uB8ypLtf8jYa6qyGoAO3IindgiqiZGOkhQ18I+1SJv4K7nmB8hFQguGeHfc0mqfuufjH POQhSR9ABT+p6a6TTPabnmxqVod3+cJKwmHFS5NXTmQHaVEAzWegicWXSfMe78hJTKvL QO8wKdnztW8hm6VeNWbZ4TIR7cz4NqoPPflORa9vVfOITCberr91/am+WNBLE+BOe3Rp aiWA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:from:date:message-id:subject :to:cc; bh=/5oVgw0VP0LR3W8nQrlx/QjN+tgrJQbhUlUiQEhvBzg=; b=J/f15cRSkXUWktx4F319x6CR9VORIK4JshWY8Iu/XFUQrNFXMakr1hBkPNWzikzRu/ F62Tvdz3LwPuWaF3fT98M/05EreIlsqkhYZSj1hb/xb51F7Gd6JfCwfEouvfUgndF4Ai SiEIidPDNk60/Bh/GiW51u/h2wuqx/7wLSqOFR9sd6Svw84+SKU/k68+cDP35+wG+K0C 9OhM/nWHuXTNjkhJ8k/8OzlOXf/tfl7zD/mfH+iIhhoGzLA9mEvGagj4nNbhR6SyxS0K kxCiMz7I6vdjiRGwTG7E+BGQ0R79wv2mdB6qVsQCQanMlL4XrrZunk5ldEBR5j9ML27b l9dA== X-Gm-Message-State: ALyK8tJMYK5lJYOx0XML6gTANLH8HOJwCpoNP5t7KkKcW+mFojs5zUb9IAavacFTLlEQfS0V8LN2FUrdj56xUA== X-Received: by 10.157.1.107 with SMTP id 98mr9229282otu.17.1466966950302; Sun, 26 Jun 2016 11:49:10 -0700 (PDT) MIME-Version: 1.0 Received: by 10.157.52.238 with HTTP; Sun, 26 Jun 2016 11:49:09 -0700 (PDT) From: Noam Postavsky Date: Sun, 26 Jun 2016 14:49:09 -0400 X-Google-Sender-Auth: JOxBGUvidaPpIB7RPTb1IfKw1Ps Message-ID: Subject: Bug #20230: 24.4.91; slow regexp To: 20230@debbugs.gnu.org Content-Type: text/plain; charset=UTF-8 X-Spam-Score: -0.7 (/) X-Debbugs-Envelope-To: 20230 Cc: Nicolas Richard X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) merge 6640 20230 quit Same problem as http://debbugs.gnu.org/cgi/bugreport.cgi?bug=6640: Emacs uses backtracking regexp engine, so when then you have a failing regexp with repeated sub-parts that can match in many different ways, you hit exponential behaviour. In this case \\(?: .*\\)?[ ]* can match a stretch of n spaces in n different ways, and since that part is itself inside a * repetition, each those n ways has to be tried on each line giving n^L runtime (where L is number of lines). A faster regexp which should match the same is (looking-at "^[ \t]*:PROPERTIES:[ \t]* \\(?:[ \t]*:\\S-+:[^\n]* \\)*[ \t]*:END:[ \t]*$") From debbugs-submit-bounces@debbugs.gnu.org Sat Jun 16 09:55:29 2018 Received: (at control) by debbugs.gnu.org; 16 Jun 2018 13:55:29 +0000 Received: from localhost ([127.0.0.1]:51738 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1fUBft-0000XA-9g for submit@debbugs.gnu.org; Sat, 16 Jun 2018 09:55:29 -0400 Received: from mail-io0-f179.google.com ([209.85.223.179]:37270) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1fUBfs-0000X4-C6 for control@debbugs.gnu.org; Sat, 16 Jun 2018 09:55:28 -0400 Received: by mail-io0-f179.google.com with SMTP id s26-v6so13141421ioj.4 for ; Sat, 16 Jun 2018 06:55:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:subject:date:message-id:mime-version; bh=1aPqTYuBnF+jwc/oCE3TfLU9OokMPaGyn3OVbvycqCE=; b=dX+OikGxo5f6iRyZCdPOZAzfw6F/BXH30sT+i9phL1mi4gZeNwVnDSWCtQLhvandub H/a8RV8wTiwjTyY0mBy3hFI5qE38R0JxpVqmhgfteYq9XL61YuWr+GzFlaTIGaOxWyZI o5mDzDKX5wwfR86cdR6yIhy6i3xgrNfGrAeHPFMkqQ6GQ2zhTn1S47JoisXckigyIBi6 pRSX9wYhCJ0UyhKuv2JBuuwwkdaJu0SV6zN7nHDyZeNKbpQ5v9GOoTHGQXtV6puDSZ4N XYED5rIWaoIaUixa3LjdRTRi5HVwLOuln47+1yUSOY46PNtarBU1kX/4Rd5P0ScXWvO1 ai7g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:mime-version; bh=1aPqTYuBnF+jwc/oCE3TfLU9OokMPaGyn3OVbvycqCE=; b=RYJSCHOucOeVF+qlDiYfbejHoS/frKtzgWKYsNu5tYpuswRqlf8pr3cJupb44Xn+fh AFdC8FCb2TO9zUO+Xf8vY/PBrEtin5EOc35LhI5RH1BgKmfsx4Y6syURRe1ANO5em9f4 FHlJwbHzgN0J2QCStJ/w7t/Qr2Lyopy61qhwOKotpX0vOEaSFEQScsL6y3x5v9a1YmeT 3uIGPglodJ8wzFb+lYtT3niiA6w0HZEOW/JeHIwuSWvDFnZFh9YxvhRchh5WUJAGZkOR pGbA7gail21WrcsjpRgGlYqpqbOp/DbLtR8XV6bhmrIxek2KCD+yiYjzOdwJ0a5CCkfd DG1A== X-Gm-Message-State: APt69E3oJMu1rOgKlqzcer/JnSbsrQ7SSnDCdWy45SEjCnAij+eLqSWU 8CsE5D1my4CWRijayI+f6NJ0yg== X-Google-Smtp-Source: ADUXVKJ5SC6QEcr3OS24YcBMQsrs8jkke1h2cSpa9UU9cMIMuU4JBXfdynl2dpQNm/KqZGdnsJUS8A== X-Received: by 2002:a5e:860f:: with SMTP id z15-v6mr4992689ioj.73.1529157322602; Sat, 16 Jun 2018 06:55:22 -0700 (PDT) Received: from zebian (cbl-45-2-119-34.yyz.frontiernetworks.ca. [45.2.119.34]) by smtp.googlemail.com with ESMTPSA id i10-v6sm2237165itb.38.2018.06.16.06.55.21 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 16 Jun 2018 06:55:22 -0700 (PDT) From: Noam Postavsky To: control@debbugs.gnu.org Subject: control message for bug #6640 Date: Sat, 16 Jun 2018 09:55:21 -0400 Message-ID: <878t7evnsm.fsf@gmail.com> MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: control X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) merge 6640 31817 quit From debbugs-submit-bounces@debbugs.gnu.org Mon Apr 01 21:20:12 2019 Received: (at control) by debbugs.gnu.org; 2 Apr 2019 01:20:12 +0000 Received: from localhost ([127.0.0.1]:40190 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1hB860-0001pp-De for submit@debbugs.gnu.org; Mon, 01 Apr 2019 21:20:12 -0400 Received: from mail-qt1-f170.google.com ([209.85.160.170]:44638) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1hB85y-0001pV-Bn for control@debbugs.gnu.org; Mon, 01 Apr 2019 21:20:10 -0400 Received: by mail-qt1-f170.google.com with SMTP id w5so13077948qtb.11 for ; Mon, 01 Apr 2019 18:20:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:subject:date:message-id:mime-version; bh=cIYmh7bmSfa0zBRukzUDekfEHPMVEIOthQJnM+Q4wlI=; b=L0BuubmCGbhWg41QDDmfSKBVRD9B7Vpgx6yRThTPpY3eospnOJFAlppelM3fPZyqVH 9bc8CWUupx8/LhNvRztlD+LAPkieNYa9reBZvMJYoKyuYr+fmO8AGZs/082nLKT5CfEU axpGdIC9hcMQjhemKw6X+06deO0ob150EGTDk5SX9cRJ9iEQj/s+ab00qndZPvM1u4By 1luCITAt+1CLFtvV4Z1X5Yh3FEyXNQ4v92PuW9KT0w8tko+OM7t0poHIRqn5mddZhhit /o5MfGyP05tCdEm1+OenECj0LwmABMb2/nae6Ja7ayaMSgRMN5wJ789GkqU692p3zZqe ZblQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:mime-version; bh=cIYmh7bmSfa0zBRukzUDekfEHPMVEIOthQJnM+Q4wlI=; b=ryNY/Kx1rTOZ6gxPKoYMKW73OYEYBwtdTf4suu4Qdz5aV9Qy8omAWP4qL1StEWQ++x w/30chKALIg8a1vuNKElkbbBOFe9DjpRr7eUrbaYK61SIMbTC7K8xRNP8o+JyKiXubmQ FRIGUHq2XbY0Jh90zfOnCNAAO4H2MDSjzGFLJK+3v+m7n5zgwyKrVgePdHyuCuvW8ds8 gKkgPqq9EP1/hrL82dsH9bodGANiWzUppV2nUZ9AGYhBN9tjC6JYuDk5wRYR6Uvi+vMi TMFxGpQm9frC+XMu+KrNgeHnTMuSL18T+GYsM43gAf/B3T+UtUYzWc8096D4BSF5HuMr 9Z/w== X-Gm-Message-State: APjAAAXkt1ssSpZBBoNRPrTeBMT2jOuZ0fItimsJmwNFQFj1PyignlDY PJfGvq/OUKrfpY/qURW6ATRj4q2i X-Google-Smtp-Source: APXvYqygCJ74fvxh5pD0xw9uqkBTD1f2Oxnq4AaeE86G3+H4cdNR8dTFGruxfKEvQ7H1WCE3faRacw== X-Received: by 2002:ac8:2df8:: with SMTP id q53mr56290591qta.132.1554168004572; Mon, 01 Apr 2019 18:20:04 -0700 (PDT) Received: from minid (cbl-45-2-119-34.yyz.frontiernetworks.ca. [45.2.119.34]) by smtp.googlemail.com with ESMTPSA id z8sm7466736qth.62.2019.04.01.18.20.03 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 01 Apr 2019 18:20:03 -0700 (PDT) From: Noam Postavsky To: control@debbugs.gnu.org Subject: control message for bug #6640 Date: Mon, 01 Apr 2019 21:20:03 -0400 Message-ID: <878swtgq4c.fsf@gmail.com> MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: control X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) merge 6640 34823 quit