From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-Status: No, score=-4.2 required=3.0 tests=AWL,BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,NICE_REPLY_A, RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE, SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id C74561F4B4 for ; Mon, 14 Sep 2020 02:03:49 +0000 (UTC) Received: from localhost ([::1]:43432 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kHdqN-0007Gi-SE for normalperson@yhbt.net; Sun, 13 Sep 2020 22:03:47 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:59844) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kHdqK-0007G2-5P; Sun, 13 Sep 2020 22:03:44 -0400 Received: from zimbra.cs.ucla.edu ([131.179.128.68]:45880) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kHdqG-0000TI-Hq; Sun, 13 Sep 2020 22:03:43 -0400 Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 17864160066; Sun, 13 Sep 2020 19:03:37 -0700 (PDT) Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id TTL4VJX9ijkC; Sun, 13 Sep 2020 19:03:34 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 5CB4B16008E; Sun, 13 Sep 2020 19:03:34 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id ZHzbTHZrwyGa; Sun, 13 Sep 2020 19:03:34 -0700 (PDT) Received: from [192.168.1.9] (cpe-75-82-69-226.socal.res.rr.com [75.82.69.226]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id 09A24160066; Sun, 13 Sep 2020 19:03:34 -0700 (PDT) Subject: Re: bug#40634: Massive pattern list handling with -E format seems very slow since 2.28. To: Jim Meyering References: <20200418002153.8771.27F6AC2D@kcn.ne.jp> <20200419074109.431A.27F6AC2D@kcn.ne.jp> <20200419111025.4326.27F6AC2D@kcn.ne.jp> <0417af9a-50a5-3462-6b38-393d80395085@cs.ucla.edu> From: Paul Eggert Autocrypt: addr=eggert@cs.ucla.edu; prefer-encrypt=mutual; keydata= LS0tLS1CRUdJTiBQR1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCgptUUlOQkV5QWNtUUJFQURB QXlIMnhvVHU3cHBHNUQzYThGTVpFb243NGRDdmM0K3ExWEEySjJ0QnkycHdhVHFmCmhweHhk R0E5Smo1MFVKM1BENGJTVUVnTjh0TFowc2FuNDdsNVhUQUZMaTI0NTZjaVNsNW04c0thSGxH ZHQ5WG0KQUF0bVhxZVpWSVlYL1VGUzk2ZkR6ZjR4aEVtbS95N0xiWUVQUWRVZHh1NDd4QTVL aFRZcDVibHRGM1dZRHoxWQpnZDdneDA3QXV3cDdpdzdlTnZub0RUQWxLQWw4S1lEWnpiRE5D UUdFYnBZM2VmWkl2UGRlSStGV1FONFcra2doCnkrUDZhdTZQcklJaFlyYWV1YTdYRGRiMkxT MWVuM1NzbUUzUWpxZlJxSS9BMnVlOEpNd3N2WGUvV0szOEV6czYKeDc0aVRhcUkzQUZINmls QWhEcXBNbmQvbXNTRVNORnQ3NkRpTzFaS1FNcjlhbVZQa25qZlBtSklTcWRoZ0IxRApsRWR3 MzRzUk9mNlY4bVp3MHhmcVQ2UEtFNDZMY0ZlZnpzMGtiZzRHT1JmOHZqRzJTZjF0azVlVThN Qml5Ti9iClowM2JLTmpOWU1wT0REUVF3dVA4NGtZTGtYMndCeHhNQWhCeHdiRFZadWR6eERa SjFDMlZYdWpDT0pWeHEya2wKakJNOUVUWXVVR3FkNzVBVzJMWHJMdzYrTXVJc0hGQVlBZ1Jy NytLY3dEZ0JBZndoUEJZWDM0blNTaUhsbUxDKwpLYUhMZUNMRjVaSTJ2S20zSEVlQ1R0bE9n N3haRU9OZ3d6TCtmZEtvK0Q2U29DOFJSeEpLczhhM3NWZkk0dDZDCm5yUXp2SmJCbjZneGRn Q3U1aTI5SjFRQ1lyQ1l2cWwyVXlGUEFLK2RvOTkvMWpPWFQ0bTI4MzZqMXdBUkFRQUIKdENC UVlYVnNJRVZuWjJWeWRDQThaV2RuWlhKMFFHTnpMblZqYkdFdVpXUjFQb2tDVlFRVEFRZ0FQ d0liQXdZTApDUWdIQXdJR0ZRZ0NDUW9MQkJZQ0F3RUNIZ0VDRjRBV0lRUitONUtwMkt6MzFq TzhGWWp0bCtrT1lxcCtOQVVDClh5Vzlsd1VKRks0THN3QUtDUkR0bCtrT1lxcCtOS05WRC85 SE1zSTE2MDZuMFV1VFhId0lUc3lPakFJOVNET1QKK0MzRFV2NnFsTTVCSDJuV0FNVGlJaXlB NXVnbHNKdjkzb2kydk50RmYvUS9tLzFjblpXZ25WbkV4a3lMSTRFTgpTZDF1QnZyMC9sQ1Nk UGxQME1nNkdXU3BYTXUreDB2ZFQwQWFaTk9URTBGblB1b2xkYzNYRDc2QzJxZzhzWC9pCmF4 WFRLSHk5UCtCbEFxL0NzNy9weERRMEV6U24wVVNaMkMwbDV2djRQTXBBL3BpY25TNks2MDlK dkRHYU9SbXcKWmVYSVpxUU5aVitaUXMrVVl0Vm9ndURUcWJ5M0lVWTFJOEJsWEhScHRhajlB TW40VW9oL0NxcFFsVm9qb3lXbApIcWFGbm5KQktlRjBodko5U0F5YWx3dXpBakc3dlFXMDdN WW5jYU9GbTB3b2lLYmc1SkxPOEY0U0JUSWt1TzBECkNmOW5MQWF5NlZzQjRyendkRWZSd2pQ TFlBbjdNUjNmdkhDRXpmcmtsZFRyYWlCTzFUMGllREs4MEk3c0xmNnAKTWVDWUkxOXBVbHgw L05STUdDZGRpRklRZGZ0aEtXWEdSUzVMQXM4andCZjhINkc1UFdpblByRUlhb21JUDIxaQp2 dWhRRDA3YllxOUlpSWRlbGpqVWRIY0dJMGkvQjRNNTZaYWE4RmYzOGluaU9sckRZQ21ZV1I0 ZENXWml1UWVaCjNPZ3FlUXM5YTZqVHZnZERHVm1SVnFZK2p6azhQbGFIZmNvazhST2hGY0hL a2NmaHVCaEwyNWhsUklzaFJET0UKc2tYcUt3bnpyYnFnYTNHWFpYZnNYQW9GYnpOaExkTHY5 QStMSkFZU2tYUDYvNXFkVHBFTFZHb3N5SDg4NFZkYgpCcGtHSTA0b1lWcXVsYmtDRFFSTWdI SmtBUkFBcG9YcnZ4UDNESWZqQ05PdFhVL1Bkd01TaEtkWC9SbFNzNVBmCnVuVjF3YktQOGhl clhIcnZRZEZWcUVDYVRTeG1saHpiazhYMFBrWTlnY1ZhVTJPNDlUM3FzT2QxY0hlRjUyWUYK R0V0MExoc0JlTWpnTlg1dVoxVjc2cjhneWVWbEZwV1diMFNJd0pVQkhyRFhleEY2N3VwZVJi MnZkSEJqWUROZQp5U24rMEI3Z0ZFcXZWbVp1K0xhZHVkRHA2a1FMamF0RnZIUUhVU0dOc2hC bmtrY2FUYmlJOVBzdDBHQ2MyYWl6Cm5CaVBQQTJXUXhBUGxQUmgzT0dUc241VEhBRG1ianFZ NkZFTUxhc1ZYOERTQ2JsTXZMd05lTy84U3h6aUJpZGgKcUxwSkNxZFFSV0hrdTVYeGdJa0dl S096NU9MRHZYSFdKeWFmckVZamprUzZBazZCNXo2c3ZLbGlDbFduakhRYwpqbFB6eW9GRmdL VEVmY3FEeENqNFJZMEQwRGd0RkQwTmZ5ZU9pZHJTQi9TelRlMmh3cnlRRTNycFNpcW8rMGNH CmR6aDR5QUhLWUorVXJYWjRwOTNaaGpHZktEMXhsck5ZRGxXeVc5UEdtYnZxRnVEbWlJQVFm OVdEL3d6RWZJQ2MKK0YrdURESSt1WWtSeFVGcDkyeWttZGhERUZnMXlqWXNVOGlHVTY5YUh5 dmhxMzZ6NHpjdHZicWhSTnpPV0IxYgpWSi9kSU1EdnNFeEdjWFFWRElUN3NETlh2MHdFM2pL U0twcDdOREcxb1hVWEwrMitTRjk5S2p5NzUzQWJRU0FtCkg2MTdmeUJOd2hKV3ZRWWcrbVV2 UHBpR090c2VzOUVYVUkzbFM0djBNRWFQRzQzZmxFczFVUisxcnBGUVdWSG8KMXkxT08rc0FF UUVBQVlrQ1BBUVlBUWdBSmdJYkRCWWhCSDQza3FuWXJQZldNN3dWaU8yWDZRNWlxbjQwQlFK ZgpKYjJ6QlFrVXJndlBBQW9KRU8yWDZRNWlxbjQwY25NUC8xN0NnVWtYVDlhSUpyaVBNOHdi Y2VZcmNsNytiZFlFCmY3OVNsd1NiYkhON1I0Q29JSkZPbE45Uy8zNHR5cEdWWXZwZ21DSkRZ RlRCeHlQTzkyaU1YRGdBNCtjV0h6dDUKVDFhWU85aHNLaGg3dkR0Sys2UHJvWkdjKzA4Z1VU WEhoYjk3aE1NUWhrbkpsbmZqcFNFQzllbTkwNkZVK0k5MwpUMWZUR3VwbkJhM2FXY0s4ak0w SmFCR2J5MmhHMVMzb2xhRExTVHRCSU5OQlltdnVXUjlNS09oaHFEcmxrNWN3CkZESkxoNU5y WHRlRVkwOFdBemNMekczcGtyWFBIa0ZlTVF0ZnFrMGpMZEdHdkdDM05DSWtxWXJkTGhpUnZH cHIKdTM4QzI2UkVuNWY0STB2R0UzVmZJWEhlOFRNQ05tUXV0MU50TXVVbXBESXkxYUx4R3p1 cHRVaG5PSk4vL3IrVgpqRFBvaTNMT3lTTllwaHFlL2RNdWJzZlVyNm9oUDQxbUtGODFGdXdJ NGFtcUp0cnFJTDJ5cWF4M2EwcWxmd0N4ClhmdGllcUpjdWVrWCtlQ1BEQ0tyWU1YUjBGWWd3 cEcySVRaVUd0ckVqRVNsRTZEc2N4NzM0SEtkcjVPUklvY0wKVVVLRU9HZWlVNkRHaEdGZGI1 VHd1MFNuK3UxbVVQRE4wTSsrQ2RNdkNsSUU4a2xvNEc5MUVPSW11MVVwYjh4YwpPUFF3eGgx andxU3JVNVF3b05tU1llZ1FTSExwSVV1ckZ6MWlRVWgxdnBQWHpLaW5rV0VxdjRJcUExY2lM K0x5CnlTdUxrcDdNc0pwVlJNYldKQ05XT09TYmFING9EQko1ZEhNR2MzNXg1bW9zQ2s5MFBY a251RkREc1lIZkRvNXMKbWY5bG82WVh4N045Cj0zTGFJCi0tLS0tRU5EIFBHUCBQVUJMSUMg S0VZIEJMT0NLLS0tLS0K Organization: UCLA Computer Science Department Message-ID: <78d13c9d-0426-b913-66fc-d7d652a5500c@cs.ucla.edu> Date: Sun, 13 Sep 2020 19:03:33 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/mixed; boundary="------------DD7B168845614FF54EE0C9E9" Content-Language: en-US Received-SPF: pass client-ip=131.179.128.68; envelope-from=eggert@cs.ucla.edu; helo=zimbra.cs.ucla.edu X-detected-operating-system: by eggs.gnu.org: First seen = 2020/09/13 21:41:58 X-ACL-Warn: Detected OS = Linux 3.1-3.10 [fuzzy] X-Spam_score_int: -41 X-Spam_score: -4.2 X-Spam_bar: ---- X-Spam_report: (-4.2 / 5.0 requ) BAYES_00=-1.9, NICE_REPLY_A=-0.001, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: bug-gnulib@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Gnulib discussion list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: fryasu@yahoo.co.jp, Gnulib bugs , 40634@debbugs.gnu.org, Norihiro Tanaka , GNU grep developers Errors-To: bug-gnulib-bounces+normalperson=yhbt.net@gnu.org Sender: "bug-gnulib" This is a multi-part message in MIME format. --------------DD7B168845614FF54EE0C9E9 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit On 9/11/20 11:41 PM, Jim Meyering wrote: >> https://bugs.gnu.org/40634#32 >> >> I'll try to take a look at the later patch. > > Oh! Glad you spotted that. I took a look and the basic idea sounds good though I admit I did not check every detail. While looking into it I found some opportunities for improvements, plus I found what appear to be some longstanding bugs in the area, one of which causes a grep test failure on Solaris (and I suspect the bug is also on GNU/Linux but the grep tests don't catch it). I installed the attached patches into Gnulib, updated grep to point to the new Gnulib version, and added a note in grep's NEWS file about this. Patch 1 is what Norihiro Tanaka proposed in Bug#40634#32, except I edited the commit message. Patch 2 consists of minor cleanups and performance tweaks for Patch 1. (Patches 3 and 4 are omitted as they were installed by others into Gnulib at about the same time I was installing these.) Patch 5 fixes a dfa-heap-overrun failure on Solaris that appears to be a longstanding bug exposed by Patch 1 when running on Solaris. Patch 6 merely cleans up code near Patch 5. Patch 7 fixes the use of an uninitialized constraint, which I discovered while debugging Patch 5 under Valgrind; this also appears to be a longstandiung bug. Coming up with test cases for all these bugs would be pretty tricky, unfortunately. --------------DD7B168845614FF54EE0C9E9 Content-Type: text/x-patch; charset=UTF-8; name="0001-dfa-use-backward-set-in-removal-of-epsilon-closure.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0001-dfa-use-backward-set-in-removal-of-epsilon-closure.patc"; filename*1="h" >From da0e8454a8e68035ef4b87dbb9097f85df6ece27 Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Sat, 12 Sep 2020 18:51:55 -0700 Subject: [PATCH 1/7] dfa: use backward set in removal of epsilon closure When removing in epsilon closure, the code searched all nodes sequentially, and this was slow for some cases. Build a backward set before search, and only check previous position with the set. Problem reported in . * lib/dfa.c (struct dfa): New member 'epsilon'. (addtok_mb): Check whether a pattern has epsilon node or not. (epsclosure): New arg BACKWORD; caller changed. When removing epsilon node and reconnecting, check only previous positions. Treat BEG as if it were character. (dfaanalyze): Build backward set. --- lib/dfa.c | 65 +++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 51 insertions(+), 14 deletions(-) diff --git a/lib/dfa.c b/lib/dfa.c index 1f0587a7a..7c8eb6685 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -488,6 +488,7 @@ struct dfa bool fast; /* The DFA is fast. */ token utf8_anychar_classes[9]; /* To lower ANYCHAR in UTF-8 locales. */ mbstate_t mbs; /* Multibyte conversion state. */ + bool epsilon; /* The following are valid only if MB_CUR_MAX > 1. */ @@ -1615,13 +1616,21 @@ addtok_mb (struct dfa *dfa, token t, char mbprop) dfa->parse.depth--; break; - case BACKREF: - dfa->fast = false; + case BEGLINE: + case ENDLINE: + case BEGWORD: + case ENDWORD: + case LIMWORD: + case NOTLIMWORD: + case EMPTY: + dfa->epsilon = true; FALLTHROUGH; + default: - dfa->nleaves++; - FALLTHROUGH; - case EMPTY: + if (t == BACKREF) + dfa->fast = false; + if (t != EMPTY) + dfa->nleaves++; dfa->parse.depth++; break; } @@ -2297,14 +2306,15 @@ state_index (struct dfa *d, position_set const *s, int context) constraint. Repeat exhaustively until no funny positions are left. S->elems must be large enough to hold the result. */ static void -epsclosure (struct dfa const *d) +epsclosure (struct dfa const *d, position_set *backword) { position_set tmp; alloc_position_set (&tmp, d->nleaves); for (idx_t i = 0; i < d->tindex; i++) if (d->follows[i].nelem > 0 && d->tokens[i] >= NOTCHAR && d->tokens[i] != BACKREF && d->tokens[i] != ANYCHAR - && d->tokens[i] != MBCSET && d->tokens[i] < CSET) + && d->tokens[i] != MBCSET && d->tokens[i] < CSET + && d->tokens[i] != BEG) { unsigned int constraint; switch (d->tokens[i]) @@ -2327,16 +2337,21 @@ epsclosure (struct dfa const *d) case NOTLIMWORD: constraint = NOTLIMWORD_CONSTRAINT; break; - default: + case EMPTY: constraint = NO_CONSTRAINT; break; + default: + abort (); } delete (i, &d->follows[i]); - for (idx_t j = 0; j < d->tindex; j++) - if (i != j && d->follows[j].nelem > 0) - replace (&d->follows[j], i, &d->follows[i], constraint, &tmp); + for (idx_t j = 0; j < backword[i].nelem; j++) + replace (&d->follows[backword[i].elems[j].index], i, &d->follows[i], + constraint, &tmp); + for (idx_t j = 0; j < d->follows[i].nelem; j++) + replace (&backword[d->follows[i].elems[j].index], i, &backword[i], + NO_CONSTRAINT, &tmp); } free (tmp.elems); } @@ -2643,6 +2658,7 @@ dfaanalyze (struct dfa *d, bool searchflag) /* Firstpos and lastpos elements. */ position *firstpos = posalloc; position *lastpos = firstpos + d->nleaves; + position_set *backword = NULL; position pos; position_set tmp; @@ -2675,6 +2691,9 @@ dfaanalyze (struct dfa *d, bool searchflag) alloc_position_set (&merged, d->nleaves); d->follows = xcalloc (d->tindex, sizeof *d->follows); + if (d->epsilon) + backword = xcalloc (d->tindex, sizeof *backword); + for (idx_t i = 0; i < d->tindex; i++) { switch (d->tokens[i]) @@ -2712,6 +2731,17 @@ dfaanalyze (struct dfa *d, bool searchflag) case CAT: /* Every element in the firstpos of the second argument is in the follow of every element in the lastpos of the first argument. */ + if (d->epsilon) + { + tmp.nelem = stk[-2].nlastpos; + tmp.elems = lastpos - stk[-1].nlastpos - stk[-2].nlastpos; + position *p = firstpos - stk[-1].nfirstpos; + for (idx_t j = 0; j < stk[-1].nfirstpos; j++) + { + merge (&tmp, &backword[p[j].index], &merged); + copy (&merged, &backword[p[j].index]); + } + } { tmp.nelem = stk[-1].nfirstpos; tmp.elems = firstpos - stk[-1].nfirstpos; @@ -2801,9 +2831,15 @@ dfaanalyze (struct dfa *d, bool searchflag) #endif } - /* For each follow set that is the follow set of a real position, replace - it with its epsilon closure. */ - epsclosure (d); + if (d->epsilon) + { + /* For each follow set that is the follow set of a real position, + replace it with its epsilon closure. */ + epsclosure (d, backword); + + for (idx_t i = 0; i < d->tindex; i++) + free (backword[i].elems); + } dfaoptimize (d); @@ -2865,6 +2901,7 @@ dfaanalyze (struct dfa *d, bool searchflag) d->min_trcount++; d->trcount = 0; + free (backword); free (posalloc); free (stkalloc); free (merged.elems); -- 2.17.1 --------------DD7B168845614FF54EE0C9E9 Content-Type: text/x-patch; charset=UTF-8; name="0002-dfa-epsilon-closure-tweaks-Bug-40634.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0002-dfa-epsilon-closure-tweaks-Bug-40634.patch" >From 4e14bef83b3c8096efebe343069baf13277337bc Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sat, 12 Sep 2020 18:51:55 -0700 Subject: [PATCH 2/7] dfa: epsilon-closure tweaks (Bug#40634) Rename BACKWORD to BACKWARD consistently. * lib/dfa.c (struct dfa): Reorder members to reduce fragmentation. (addtok_mb): Redo slightly to make it act more like a state machine. Check depth only when it increases. (epsclosure): Let the switch test the tokens. (dfaanalyze): Cache tindex. Simplify position loops. Prefer xcalloc to xnmalloc + explicit zeroing. Free BACKWARD only if it is not null, since we're testing that anyway. (dfaanalyze, build_state): Use merge2 instead of doing it by hand. --- ChangeLog | 27 ++++++++++++ lib/dfa.c | 124 ++++++++++++++++++++++++++---------------------------- 2 files changed, 87 insertions(+), 64 deletions(-) diff --git a/ChangeLog b/ChangeLog index bf39cc512..66aec61cb 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,30 @@ +2020-09-12 Paul Eggert + + dfa: epsilon-closure tweaks (Bug#40634) + Rename BACKWORD to BACKWARD consistently. + * lib/dfa.c (struct dfa): Reorder members to reduce fragmentation. + (addtok_mb): Redo slightly to make it act more like a state machine. + Check depth only when it increases. + (epsclosure): Let the switch test the tokens. + (dfaanalyze): Cache tindex. Simplify position loops. + Prefer xcalloc to xnmalloc + explicit zeroing. Free BACKWARD + only if it is not null, since we're testing that anyway. + (dfaanalyze, build_state): Use merge2 instead of doing it by hand. + +2020-09-12 Norihiro Tanaka + + dfa: use backward set in removal of epsilon closure + When removing in epsilon closure, the code searched all nodes + sequentially, and this was slow for some cases. Build a backward + set before search, and only check previous position with the set. + Problem reported in . + * lib/dfa.c (struct dfa): New member 'epsilon'. + (addtok_mb): Check whether a pattern has epsilon node or not. + (epsclosure): New arg BACKWORD; caller changed. When removing + epsilon node and reconnecting, check only previous positions. + Treat BEG as if it were character. + (dfaanalyze): Build backward set. + 2020-09-10 Paul Eggert canonicalize: fix pointer indexing bugs diff --git a/lib/dfa.c b/lib/dfa.c index 7c8eb6685..0f0764887 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -482,13 +482,14 @@ struct dfa idx_t depth; /* Depth required of an evaluation stack used for depth-first traversal of the parse tree. */ - idx_t nleaves; /* Number of leaves on the parse tree. */ + idx_t nleaves; /* Number of non-EMPTY leaves + in the parse tree. */ idx_t nregexps; /* Count of parallel regexps being built with dfaparse. */ bool fast; /* The DFA is fast. */ + bool epsilon; /* Does a token match only the empty string? */ token utf8_anychar_classes[9]; /* To lower ANYCHAR in UTF-8 locales. */ mbstate_t mbs; /* Multibyte conversion state. */ - bool epsilon; /* The following are valid only if MB_CUR_MAX > 1. */ @@ -1616,26 +1617,31 @@ addtok_mb (struct dfa *dfa, token t, char mbprop) dfa->parse.depth--; break; + case EMPTY: + dfa->epsilon = true; + goto increment_depth; + + case BACKREF: + dfa->fast = false; + goto increment_nleaves; + case BEGLINE: case ENDLINE: case BEGWORD: case ENDWORD: case LIMWORD: case NOTLIMWORD: - case EMPTY: dfa->epsilon = true; FALLTHROUGH; - default: - if (t == BACKREF) - dfa->fast = false; - if (t != EMPTY) - dfa->nleaves++; + increment_nleaves: + dfa->nleaves++; + increment_depth: dfa->parse.depth++; + if (dfa->depth < dfa->parse.depth) + dfa->depth = dfa->parse.depth; break; } - if (dfa->parse.depth > dfa->depth) - dfa->depth = dfa->parse.depth; } static void addtok_wc (struct dfa *dfa, wint_t wc); @@ -2156,6 +2162,8 @@ merge (position_set const *s1, position_set const *s2, position_set *m) merge_constrained (s1, s2, -1, m); } +/* Merge into DST all the elements of SRC, possibly destroying + the contents of the temporary M. */ static void merge2 (position_set *dst, position_set const *src, position_set *m) { @@ -2300,25 +2308,26 @@ state_index (struct dfa *d, position_set const *s, int context) return i; } -/* Find the epsilon closure of a set of positions. If any position of the set +/* Find the epsilon closure of D's set of positions. If any position of the set contains a symbol that matches the empty string in some context, replace that position with the elements of its follow labeled with an appropriate constraint. Repeat exhaustively until no funny positions are left. - S->elems must be large enough to hold the result. */ + S->elems must be large enough to hold the result. BACKWARD is D's + backward set; use and update it too. */ static void -epsclosure (struct dfa const *d, position_set *backword) +epsclosure (struct dfa const *d, position_set *backward) { position_set tmp; alloc_position_set (&tmp, d->nleaves); for (idx_t i = 0; i < d->tindex; i++) - if (d->follows[i].nelem > 0 && d->tokens[i] >= NOTCHAR - && d->tokens[i] != BACKREF && d->tokens[i] != ANYCHAR - && d->tokens[i] != MBCSET && d->tokens[i] < CSET - && d->tokens[i] != BEG) + if (0 < d->follows[i].nelem) { unsigned int constraint; switch (d->tokens[i]) { + default: + continue; + case BEGLINE: constraint = BEGLINE_CONSTRAINT; break; @@ -2340,17 +2349,15 @@ epsclosure (struct dfa const *d, position_set *backword) case EMPTY: constraint = NO_CONSTRAINT; break; - default: - abort (); } delete (i, &d->follows[i]); - for (idx_t j = 0; j < backword[i].nelem; j++) - replace (&d->follows[backword[i].elems[j].index], i, &d->follows[i], + for (idx_t j = 0; j < backward[i].nelem; j++) + replace (&d->follows[backward[i].elems[j].index], i, &d->follows[i], constraint, &tmp); for (idx_t j = 0; j < d->follows[i].nelem; j++) - replace (&backword[d->follows[i].elems[j].index], i, &backword[i], + replace (&backward[d->follows[i].elems[j].index], i, &backward[i], NO_CONSTRAINT, &tmp); } free (tmp.elems); @@ -2658,7 +2665,6 @@ dfaanalyze (struct dfa *d, bool searchflag) /* Firstpos and lastpos elements. */ position *firstpos = posalloc; position *lastpos = firstpos + d->nleaves; - position_set *backword = NULL; position pos; position_set tmp; @@ -2676,10 +2682,11 @@ dfaanalyze (struct dfa *d, bool searchflag) position_set merged; /* Result of merging sets. */ addtok (d, CAT); + idx_t tindex = d->tindex; #ifdef DEBUG fprintf (stderr, "dfaanalyze:\n"); - for (idx_t i = 0; i < d->tindex; i++) + for (idx_t i = 0; i < tindex; i++) { fprintf (stderr, " %td:", i); prtok (d->tokens[i]); @@ -2689,12 +2696,11 @@ dfaanalyze (struct dfa *d, bool searchflag) d->searchflag = searchflag; alloc_position_set (&merged, d->nleaves); - d->follows = xcalloc (d->tindex, sizeof *d->follows); - - if (d->epsilon) - backword = xcalloc (d->tindex, sizeof *backword); + d->follows = xcalloc (tindex, sizeof *d->follows); + position_set *backward + = d->epsilon ? xcalloc (tindex, sizeof *backward) : NULL; - for (idx_t i = 0; i < d->tindex; i++) + for (idx_t i = 0; i < tindex; i++) { switch (d->tokens[i]) { @@ -2714,12 +2720,8 @@ dfaanalyze (struct dfa *d, bool searchflag) { tmp.elems = firstpos - stk[-1].nfirstpos; tmp.nelem = stk[-1].nfirstpos; - position *p = lastpos - stk[-1].nlastpos; - for (idx_t j = 0; j < stk[-1].nlastpos; j++) - { - merge (&tmp, &d->follows[p[j].index], &merged); - copy (&merged, &d->follows[p[j].index]); - } + for (position *p = lastpos - stk[-1].nlastpos; p < lastpos; p++) + merge2 (&d->follows[p->index], &tmp, &merged); } FALLTHROUGH; case QMARK: @@ -2729,28 +2731,27 @@ dfaanalyze (struct dfa *d, bool searchflag) break; case CAT: - /* Every element in the firstpos of the second argument is in the - follow of every element in the lastpos of the first argument. */ - if (d->epsilon) + /* Every element in the lastpos of the first argument is in + the backward set of every element in the firstpos of the + second argument. */ + if (backward) { tmp.nelem = stk[-2].nlastpos; tmp.elems = lastpos - stk[-1].nlastpos - stk[-2].nlastpos; - position *p = firstpos - stk[-1].nfirstpos; - for (idx_t j = 0; j < stk[-1].nfirstpos; j++) - { - merge (&tmp, &backword[p[j].index], &merged); - copy (&merged, &backword[p[j].index]); - } + for (position *p = firstpos - stk[-1].nfirstpos; + p < firstpos; p++) + merge2 (&backward[p->index], &tmp, &merged); } + + /* Every element in the firstpos of the second argument is in the + follow of every element in the lastpos of the first argument. */ { tmp.nelem = stk[-1].nfirstpos; tmp.elems = firstpos - stk[-1].nfirstpos; - position *p = lastpos - stk[-1].nlastpos - stk[-2].nlastpos; - for (idx_t j = 0; j < stk[-2].nlastpos; j++) - { - merge (&tmp, &d->follows[p[j].index], &merged); - copy (&merged, &d->follows[p[j].index]); - } + for (position *plim = lastpos - stk[-1].nlastpos, + *p = plim - stk[-2].nlastpos; + p < plim; p++) + merge2 (&d->follows[p->index], &tmp, &merged); } /* The firstpos of a CAT node is the firstpos of the first argument, @@ -2831,20 +2832,21 @@ dfaanalyze (struct dfa *d, bool searchflag) #endif } - if (d->epsilon) + if (backward) { /* For each follow set that is the follow set of a real position, replace it with its epsilon closure. */ - epsclosure (d, backword); + epsclosure (d, backward); - for (idx_t i = 0; i < d->tindex; i++) - free (backword[i].elems); + for (idx_t i = 0; i < tindex; i++) + free (backward[i].elems); + free (backward); } dfaoptimize (d); #ifdef DEBUG - for (idx_t i = 0; i < d->tindex; i++) + for (idx_t i = 0; i < tindex; i++) if (d->tokens[i] == BEG || d->tokens[i] < NOTCHAR || d->tokens[i] == BACKREF || d->tokens[i] == ANYCHAR || d->tokens[i] == MBCSET || d->tokens[i] >= CSET) @@ -2868,12 +2870,10 @@ dfaanalyze (struct dfa *d, bool searchflag) append (pos, &tmp); - d->separates = xnmalloc (d->tindex, sizeof *d->separates); + d->separates = xcalloc (tindex, sizeof *d->separates); - for (idx_t i = 0; i < d->tindex; i++) + for (idx_t i = 0; i < tindex; i++) { - d->separates[i] = 0; - if (prev_newline_dependent (d->constraints[i])) d->separates[i] |= CTX_NEWLINE; if (prev_letter_dependent (d->constraints[i])) @@ -2901,7 +2901,6 @@ dfaanalyze (struct dfa *d, bool searchflag) d->min_trcount++; d->trcount = 0; - free (backword); free (posalloc); free (stkalloc); free (merged.elems); @@ -3172,10 +3171,7 @@ build_state (state_num s, struct dfa *d, unsigned char uc) mergeit &= d->multibyte_prop[group.elems[j].index]; } if (mergeit) - { - merge (&d->states[0].elems, &group, &tmp); - copy (&tmp, &group); - } + merge2 (&group, &d->states[0].elems, &tmp); } /* Find out if the new state will want any context information, -- 2.17.1 --------------DD7B168845614FF54EE0C9E9 Content-Type: text/x-patch; charset=UTF-8; name="0005-dfa-fix-dfa-heap-overrun-failure.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0005-dfa-fix-dfa-heap-overrun-failure.patch" >From cafb61533f5bfb989698e3924f97471498b2422b Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sun, 13 Sep 2020 18:20:01 -0700 Subject: [PATCH 5/7] dfa: fix dfa-heap-overrun failure * lib/dfa.c (reorder_tokens): When setting map[d->follows[i].elems[j].index], instead of incorrectly assuming that (i < d->follows[i].elems[j].index), use two loops, one to set the map array and the other to use it. The incorrect assumption caused some elements to be missed, and this in turn caused grep's dfa-heap-overrun test to fail on Solaris 10 sparc when compiled with GCC. I found this bug while investigating https://buildfarm.opencsw.org/buildbot/builders/ggrep-solaris10-sparc/builds/183 and I think the bug also occurs on GNU/Linux but with more-subtle symptoms. The bug predates the recent dfa.c changes; perhaps the recent changes make the bug more likely. --- ChangeLog | 15 +++++++++++++++ lib/dfa.c | 12 ++++++------ 2 files changed, 21 insertions(+), 6 deletions(-) diff --git a/ChangeLog b/ChangeLog index a5c14c45e..1b5720761 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,18 @@ +2020-09-13 Paul Eggert + + dfa: fix dfa-heap-overrun failure + * lib/dfa.c (reorder_tokens): When setting + map[d->follows[i].elems[j].index], instead of incorrectly assuming + that (i < d->follows[i].elems[j].index), use two loops, one to set + the map array and the other to use it. The incorrect assumption + caused some elements to be missed, and this in turn caused grep's + dfa-heap-overrun test to fail on Solaris 10 sparc when compiled + with GCC. I found this bug while investigating + https://buildfarm.opencsw.org/buildbot/builders/ggrep-solaris10-sparc/builds/183 + and I think the bug also occurs on GNU/Linux but with more-subtle + symptoms. The bug predates the recent dfa.c changes; perhaps the + recent changes make the bug more likely. + 2020-09-13 Bruno Haible parse-datetime: Make the build rule work with parallel 'make'. diff --git a/lib/dfa.c b/lib/dfa.c index 0f0764887..4992bcaf2 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -2519,6 +2519,11 @@ reorder_tokens (struct dfa *d) else multibyte_prop = NULL; + for (idx_t i = 0; i < d->tindex; i++) + for (idx_t j = 0; j < d->follows[i].nelem; j++) + if (map[d->follows[i].elems[j].index] == -1) + map[d->follows[i].elems[j].index] = nleaves++; + for (idx_t i = 0; i < d->tindex; i++) { if (map[i] == -1) @@ -2537,12 +2542,7 @@ reorder_tokens (struct dfa *d) multibyte_prop[map[i]] = d->multibyte_prop[i]; for (idx_t j = 0; j < d->follows[i].nelem; j++) - { - if (map[d->follows[i].elems[j].index] == -1) - map[d->follows[i].elems[j].index] = nleaves++; - - d->follows[i].elems[j].index = map[d->follows[i].elems[j].index]; - } + d->follows[i].elems[j].index = map[d->follows[i].elems[j].index]; qsort (d->follows[i].elems, d->follows[i].nelem, sizeof *d->follows[i].elems, compare); -- 2.17.1 --------------DD7B168845614FF54EE0C9E9 Content-Type: text/x-patch; charset=UTF-8; name="0006-dfa-assume-C99-in-reorder_tokens.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0006-dfa-assume-C99-in-reorder_tokens.patch" >From 5332a21b1188224ecddbbe8b234b618d0b84437a Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sun, 13 Sep 2020 18:27:07 -0700 Subject: [PATCH 6/7] dfa: assume C99 in reorder_tokens * lib/dfa.c (reorder_tokens): Assume C99 and simplify. --- ChangeLog | 3 +++ lib/dfa.c | 32 ++++++++++---------------------- 2 files changed, 13 insertions(+), 22 deletions(-) diff --git a/ChangeLog b/ChangeLog index 1b5720761..5f7a148e3 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,8 @@ 2020-09-13 Paul Eggert + dfa: assume C99 in reorder_tokens + * lib/dfa.c (reorder_tokens): Assume C99 and simplify. + dfa: fix dfa-heap-overrun failure * lib/dfa.c (reorder_tokens): When setting map[d->follows[i].elems[j].index], instead of incorrectly assuming diff --git a/lib/dfa.c b/lib/dfa.c index 4992bcaf2..0fa9958fd 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -2494,39 +2494,27 @@ compare (const void *a, const void *b) static void reorder_tokens (struct dfa *d) { - idx_t nleaves; - ptrdiff_t *map; - token *tokens; - position_set *follows; - int *constraints; - char *multibyte_prop; - - nleaves = 0; - - map = xnmalloc (d->tindex, sizeof *map); - + idx_t nleaves = 0; + ptrdiff_t *map = xnmalloc (d->tindex, sizeof *map); map[0] = nleaves++; - for (idx_t i = 1; i < d->tindex; i++) map[i] = -1; - tokens = xnmalloc (d->nleaves, sizeof *tokens); - follows = xnmalloc (d->nleaves, sizeof *follows); - constraints = xnmalloc (d->nleaves, sizeof *constraints); - - if (d->localeinfo.multibyte) - multibyte_prop = xnmalloc (d->nleaves, sizeof *multibyte_prop); - else - multibyte_prop = NULL; + token *tokens = xnmalloc (d->nleaves, sizeof *tokens); + position_set *follows = xnmalloc (d->nleaves, sizeof *follows); + int *constraints = xnmalloc (d->nleaves, sizeof *constraints); + char *multibyte_prop = (d->localeinfo.multibyte + ? xnmalloc (d->nleaves, sizeof *multibyte_prop) + : NULL); for (idx_t i = 0; i < d->tindex; i++) for (idx_t j = 0; j < d->follows[i].nelem; j++) - if (map[d->follows[i].elems[j].index] == -1) + if (map[d->follows[i].elems[j].index] < 0) map[d->follows[i].elems[j].index] = nleaves++; for (idx_t i = 0; i < d->tindex; i++) { - if (map[i] == -1) + if (map[i] < 0) { free (d->follows[i].elems); d->follows[i].elems = NULL; -- 2.17.1 --------------DD7B168845614FF54EE0C9E9 Content-Type: text/x-patch; charset=UTF-8; name="0007-dfa-avoid-use-of-uninitialized-constraint.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0007-dfa-avoid-use-of-uninitialized-constraint.patch" >From 46bdd627ff522193134d31bdfd3ac4e4fddb5975 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sun, 13 Sep 2020 18:40:08 -0700 Subject: [PATCH 7/7] dfa: avoid use of uninitialized constraint * lib/dfa.c (merge_nfa_state): Do not initialize the constraint to zero here. (dfaoptimize): Do it here instead, via xcalloc. This prevents the use of an uninitialized constraint by later code when ! (flags[i] & OPT_QUEUED) means merge_nfa_state was not called to initialize the constraint. Problem found by running 'valgrind src/grep -E '(^| )*(a|b)*(c|d)*( |$)' < /dev/null' on Ubuntu 18.04.5 x86-64. --- ChangeLog | 9 +++++++++ lib/dfa.c | 4 +--- 2 files changed, 10 insertions(+), 3 deletions(-) diff --git a/ChangeLog b/ChangeLog index 5f7a148e3..395ac6baf 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,14 @@ 2020-09-13 Paul Eggert + dfa: avoid use of uninitialized constraint + * lib/dfa.c (merge_nfa_state): Do not initialize the constraint + to zero here. + (dfaoptimize): Do it here instead, via xcalloc. This prevents the + use of an uninitialized constraint by later code when ! (flags[i] + & OPT_QUEUED) means merge_nfa_state was not called to initialize + the constraint. Problem found by running 'valgrind src/grep -E + '(^| )*(a|b)*(c|d)*( |$)' < /dev/null' on Ubuntu 18.04.5 x86-64. + dfa: assume C99 in reorder_tokens * lib/dfa.c (reorder_tokens): Assume C99 and simplify. diff --git a/lib/dfa.c b/lib/dfa.c index 0fa9958fd..746c7b568 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -2428,8 +2428,6 @@ merge_nfa_state (struct dfa *d, idx_t tindex, char *flags, position_set *follows = d->follows; idx_t nelem = 0; - d->constraints[tindex] = 0; - for (idx_t i = 0; i < follows[tindex].nelem; i++) { idx_t sindex = follows[tindex].elems[i].index; @@ -2581,7 +2579,7 @@ dfaoptimize (struct dfa *d) position_set *merged = &merged0; alloc_position_set (merged, d->nleaves); - d->constraints = xnmalloc (d->tindex, sizeof *d->constraints); + d->constraints = xcalloc (d->tindex, sizeof *d->constraints); for (idx_t i = 0; i < d->tindex; i++) if (flags[i] & OPT_QUEUED) -- 2.17.1 --------------DD7B168845614FF54EE0C9E9--