From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.3 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 6899 invoked from network); 29 Jul 2023 01:36:30 -0000 Received: from zero.zsh.org (2a02:898:31:0:48:4558:7a:7368) by inbox.vuxu.org with ESMTPUTF8; 29 Jul 2023 01:36:30 -0000 ARC-Seal: i=1; cv=none; a=rsa-sha256; d=zsh.org; s=rsa-20210803; t=1690594591; b=G8INU1OJSueCmRv6QQka88D0I4OCHgUXQViDpLvDMNovetn4IyetfS20PXwwkciutQEFBL0JSM BqHQa7yscFl2/J74LjBQiaMpEmCkCeQGuQMwnjkl+vA0Tf8kQXnMOQH1KY1alsYmuG/xNKdb5C FbVv6XOJZbSCQ8tlbGdXyjTsOnDni7w2VhEmcp1a9DZ/GL1JeuR92OpJb3FPcOlVqbVjyb9hWW aH7eJwhL+lDRi1pRx+hbed7p6rblTrtwfwRSnwbtRsOHJLlG+naqTgbc4gMJTrvA9lDCtjaEie ofwscBUKcHQ3u7b5HpuVng47TqJpOG55oirzCuI2yy49Rw==; ARC-Authentication-Results: i=1; zsh.org; iprev=pass (mail-ed1-f50.google.com) smtp.remote-ip=209.85.208.50; dkim=pass header.d=brasslantern-com.20221208.gappssmtp.com header.s=20221208 header.a=rsa-sha256; dmarc=none header.from=brasslantern.com; arc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed; d=zsh.org; s=rsa-20210803; t=1690594591; bh=viqpADJsgMm1s/MXBhDSFTpLaKqGzZjzf69XtNC1+b4=; h=List-Archive:List-Owner:List-Post:List-Unsubscribe:List-Subscribe:List-Help: List-Id:Sender:Content-Transfer-Encoding:Content-Type:To:Subject:Message-ID: Date:From:In-Reply-To:References:MIME-Version:DKIM-Signature:DKIM-Signature; b=jiP4ntDfg9JzPjOfJEBIJlFKcBqGdPUL81WTobFUkRr6GNMM73ERSSEQpVImRXoKlGA/wDl4IB M3x+GyFrfKGNx7KEkpAWjI7HxpUTHZd3gkevVfG7uUVubFj92EBXlJHvwc9H6nZq/rZY67UQ57 QZBnIAuMx7U/ZykGEcged2YDHCC0MEjapil+n/FdXgJtd9khHO4/IgIFhHs+X+Q3JefoFAKwhJ fMxvKEuzdJf+i//1SJEjPrSJ7xDnuxibgPpmPsbQaoNQllf/k7E3Tkey4ySC9IxaVC7WKKOcLV xLHkc/gRADaFvky6MB6Sujm57cphoofi5wPkNaj2e/Q0nw==; DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=zsh.org; s=rsa-20210803; h=List-Archive:List-Owner:List-Post:List-Unsubscribe: List-Subscribe:List-Help:List-Id:Sender:Content-Transfer-Encoding: Content-Type:To:Subject:Message-ID:Date:From:In-Reply-To:References: MIME-Version:Reply-To:Cc:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID; bh=FdepuPz3pFR7XiWCqEiBVUKYgGfCVhjUle+J38ivGSA=; b=iUHvmer3qgnxva4KiChRguOkmP VhdSDlbOljeOs81szPkA5fm8LVIcMrmGba4lT6nAwiA8X3Xl4Fo8i3a5izwwnLGt/ZSt7wP2pLS/i SQG1f6LFt+VXt2wss08OqmuNzolVd7+Le0uNU/1WU8FQ8JmvFK2VUI+9sxDv/AeJJyTGdSaucH5Pb F8wrtzgMNo2Gfcs0QDZxW4L3bi0DchfJFt53wfnFzmqJUAJfDu177FXjRNDogFNU7+xpXLRfplxqZ 0VU90in1dTAYknGUsK+Ji7uCu2K7ITns8nrN/vL7G5mLwY49GQguV8kX8j7qcj22RdSf0gpOly1pp EvLgsmGg==; Received: by zero.zsh.org with local id 1qPYse-000Grk-Mj; Sat, 29 Jul 2023 01:36:28 +0000 Authentication-Results: zsh.org; iprev=pass (mail-ed1-f50.google.com) smtp.remote-ip=209.85.208.50; dkim=pass header.d=brasslantern-com.20221208.gappssmtp.com header.s=20221208 header.a=rsa-sha256; dmarc=none header.from=brasslantern.com; arc=none Received: from mail-ed1-f50.google.com ([209.85.208.50]:49571) by zero.zsh.org with esmtps (TLS1.3:TLS_AES_128_GCM_SHA256:128) id 1qPYs3-000GYP-CV; Sat, 29 Jul 2023 01:35:53 +0000 Received: by mail-ed1-f50.google.com with SMTP id 4fb4d7f45d1cf-52222562f1eso3529619a12.3 for ; Fri, 28 Jul 2023 18:35:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=brasslantern-com.20221208.gappssmtp.com; s=20221208; t=1690594550; x=1691199350; h=content-transfer-encoding:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=FdepuPz3pFR7XiWCqEiBVUKYgGfCVhjUle+J38ivGSA=; b=mwjllOjjISb8ZqzpgZYHM90Cz8WToCnbpehaiyLcZ/CpGcaWIYVE9a1hiQF7isxLaW IewOEYexD27StwUa6/jQC1NU6j0MLPyGfh4lIokI88Aw64db0Q5WRS9HtnmN7bIXalR7 cCxhH9uBKsDA2GArDYWJtlutrm7NX1qs0j+Asg9ER+7+GF1o4unDGAVx9RBVlye2/hHp EAfRDRTfC8biCNrX4AOQaafApDtrW2/M9s2B6H2Xg/9fvCAl1gEHakgTBro1Y7zmLKTv asKP1pBYnU929ZuG4kbonCl3/dedQ0l5bsZcCI+mm4ytCOVPeVIBZnlS99H85Bis4DoT 0rEg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690594550; x=1691199350; h=content-transfer-encoding:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=FdepuPz3pFR7XiWCqEiBVUKYgGfCVhjUle+J38ivGSA=; b=hZ6kzuVDkZTfRiaAuf/XaDBw6YJ3KU6EkxK+QtCdPKH/ivZHnUrkyWM/l4AG+x3Y4H VT0wCb+s9TyDSKBMkDDMiJpr/tqcqlqFFndBZXoX7BMWz0mSX5h+HdshW2u72Z/R65OL C2/Jou+XWJqrf0t/oZDYNFNsWLlfmEelmC8ds5E9yQdeOZ8Ptc5L5LR2iqZQb6J7cNB8 EheMSXsFlcOi0eB+xXr5qZLeWr4ydr+O7NBAEU3X1LCp+InG4lDIaE6myuKEqC2kunzv 7Uhi4FVAU8OFVPQXmXkk+F5s6lxGruQIVjwQLxTzneT34+Fwtvf0QSWnh7mhFbHWcjjM u8Rg== X-Gm-Message-State: ABy/qLbZLbQOBeExofWy5wgsNahAkzj3wKCVhJs1hxjCd55E4DCurdsO Zy3he6AZySdJOPG77EUv7/uKWxkshXH/v1Yfsh515A== X-Google-Smtp-Source: APBJJlEKXM+Qy/gfTnh0kHPISjEZPjwAo0DDI+1iWYhvVm/W92OF1uaMF7iuva4dSuS5oHisAAsO154R8HTGRumSR9M= X-Received: by 2002:a17:906:18:b0:994:4e16:d430 with SMTP id 24-20020a170906001800b009944e16d430mr872919eja.20.1690594549936; Fri, 28 Jul 2023 18:35:49 -0700 (PDT) MIME-Version: 1.0 References: <599e3c13-53a5-1823-6d0d-68dd722967d9@crans.org> <8c33aa3a-fde5-45ce-8f22-c817c6fa4a9a@crans.org> <20230728064106.ufcfaqondhn3wge7@chazelas.org> In-Reply-To: <20230728064106.ufcfaqondhn3wge7@chazelas.org> From: Bart Schaefer Date: Fri, 28 Jul 2023 18:35:38 -0700 Message-ID: Subject: Re: Pattern bug on (a*|)~^(*b) To: Bart Schaefer , Johan Grande , zsh-workers@zsh.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Seq: 52005 Archived-At: X-Loop: zsh-workers@zsh.org Errors-To: zsh-workers-owner@zsh.org Precedence: list Precedence: bulk Sender: zsh-workers-request@zsh.org X-no-archive: yes List-Id: List-Help: , List-Subscribe: , List-Unsubscribe: , List-Post: List-Owner: List-Archive: On Thu, Jul 27, 2023 at 11:41=E2=80=AFPM Stephane Chazelas wrote: > > I have to say I'm with the OP and don't understand that > explanation either. In the absence of a direct response from PWS, I'll just point you to his comments in pattern.c, some of which date from before we had a git repository: * The strategy is to test the asserted pattern, * recording via P_EXCSYNC how far the part to * be excluded matched. We then set the * length of the test string to that * point and see if the exclusion as far as * P_EXCEND also matches that string. * We need to keep testing the asserted pattern * by backtracking, since the first attempt * may be excluded while a later attempt may not. * For this we keep a pointer just after * the P_EXCLUDE which is tested by the P_EXCSYNC * to see if we matched there last time, in which * case we fail. If there is nothing to backtrack * over, that doesn't matter: we should fail anyway. * The pointer also tells us where the asserted * pattern matched for use by the exclusion. * P.S. in case you were wondering, this code * is horrible. * This is where we make sure that we are not * repeatedly matching zero-length strings in * a closure, which would cause an infinite loop, * and also remove exponential behaviour in * backtracking nested closures. * If we come round to the same branch again, and * there is already a 1, then the test fails. By my reading, zero-length matches may be short-circuited to avoid pathological behavior.