From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Alan Mackenzie Newsgroups: gmane.emacs.devel Subject: Re: Circular records: how do I best handle them? (The new correct warning position branch now bootstraps in native compilation!) Date: Fri, 24 Dec 2021 20:37:49 +0000 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="9219"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Fri Dec 24 21:38:31 2021 Return-path: Envelope-to: ged-emacs-devel@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 1n0rKg-0002HG-P7 for ged-emacs-devel@m.gmane-mx.org; Fri, 24 Dec 2021 21:38:30 +0100 Original-Received: from localhost ([::1]:59312 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1n0rKe-0002wV-R4 for ged-emacs-devel@m.gmane-mx.org; Fri, 24 Dec 2021 15:38:28 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:53580) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1n0rK8-0002Gj-1k for emacs-devel@gnu.org; Fri, 24 Dec 2021 15:37:56 -0500 Original-Received: from colin.muc.de ([193.149.48.1]:35756 helo=mail.muc.de) by eggs.gnu.org with smtp (Exim 4.90_1) (envelope-from ) id 1n0rK5-000111-Rl for emacs-devel@gnu.org; Fri, 24 Dec 2021 15:37:55 -0500 Original-Received: (qmail 37987 invoked by uid 3782); 24 Dec 2021 20:37:51 -0000 Original-Received: from acm.muc.de (p4fe1590f.dip0.t-ipconnect.de [79.225.89.15]) (using STARTTLS) by colin.muc.de (tmda-ofmipd) with ESMTP; Fri, 24 Dec 2021 21:37:50 +0100 Original-Received: (qmail 2283 invoked by uid 1000); 24 Dec 2021 20:37:49 -0000 Content-Disposition: inline In-Reply-To: X-Submission-Agent: TMDA/1.3.x (Ph3nix) X-Primary-Address: acm@muc.de Received-SPF: pass client-ip=193.149.48.1; envelope-from=acm@muc.de; helo=mail.muc.de X-Spam_score_int: -17 X-Spam_score: -1.8 X-Spam_bar: - X-Spam_report: (-1.8 / 5.0 requ) BAYES_00=-1.9, PLING_QUERY=0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:283167 Archived-At: Hello, Stefan. On Fri, Dec 24, 2021 at 08:56:56 -0500, Stefan Monnier wrote: > > The recursion was in the (new) function `byte-compile-strip-s-p-1' > > (where "strip-s-p" stands for "strip-symbol-positions"). This function > > recursively descends list and vector structures, stripping positions > > from symbols-with-position it finds. > > However, I seem to have circularity in a record structure, where two > > records seem to point to eachother. I suspect that it is the zeroth > > elements of these records (which are meant to be symbols) that are > > pointing at eachother. > Hmm... circularity is quite normal in data structures, yes. > But presumably this is only applied to source code where circularity is > very rare. Could it be that you end up recursing in elements which > actually aren't part of the source code (and hence can't have > symbols-with-positions)? I honestly don't know at the moment. > Also, I see in `byte-compile-strip-s-p-1` that you only look inside conses > and vectors. So I'm not sure what makes you say the recursion was in > records since records are similar to vectors but aren't `vectorp` so > AFAICT your code won't recurse into them. byte-compile-strip-s-p-1 has been enhanced to handle records, too, though I haven't committed that bit yet (along with quite a lot of other amendments, too). > Also that means your code won't handle the case where the source code > includes literal hash-tables, literal records, literal char-tables, > literal strings-with-properties, ... The positions get stripped off hash-table keys in puthash. I'm unsure about the others, just offhand. Put it this way, make bootstrap is currently working, although a bit delicate. My preliminary timings on a benchmark are as fast as expected, so it's looking good. > These are quite rare and maybe it's OK to disallow them in source code, > but maybe a more robust approach would be to make sure your lread.c code > doesn't generate symbols-with-positions within anything else than conses > and vectors? > [ Tho it wouldn't prevent a macro from expanding into a literal hash-table > from source that only has conses&vectors :-( ] > > Would somebody (?Stefan M, perhaps) please suggest to me how I might > > efficiently cope with these circular structures. Do I need to maintain > > a list of already encountered Lisp Objects, somehow, and check this list > > before recursing into the function? > That's what we do elsewhere, yes, except that history taught us that > a hash-table is a better choice to avoid scalability problems. > Tho in your case you'd only need to keep the stack of objects inside of > which you're currently recursing, so maybe a list is good enough. I've tried the list approach (using memq to check for an already processed cons/vector/record. It fell flat on its face with lisp/leim/ja-dic/ja-dec.el, which has a list with over 60,000 strings in it. I Ctrl-C'd out of this after five minutes, and it took me a while to establish I didn't have an infinite loop; not quite. So I disabled the checking for circularity in conses, leaving it in for vectors and records. That's what I meant when I said "a bit delicate" above. There's nothing to stop somebody building a circular list in a source file. Maybe the way to handle this would be to allow it to hit max-lisp-eval-depth, catch the error, then turn on the circularity detector and try again. Circular lists in source code are surely rare. Large circular lists must be rarer still. > BTW, instead of doing it by hand, you can call `print--preprocess` which > will do the recurse-and-fill-hash-table for you. You can see how it's > used in `cl-print.el`. Thanks, I'll have a closer look at this, probably in a few days time. Have a good tomorrow! > Stefan -- Alan Mackenzie (Nuremberg, Germany).