Store references in SBCL-compiled code are "invisible"

> As discussed with Pierre at the R-B Summit, ‘sbcl-next’ lacks a

> reference to ‘next-gtk-webkit’ even though is invokes it:

>

> $ guix gc --references $(type -P next) | grep next-

> /gnu/store/9d66xb8wvggsp0x9pxj61mzqy007978f-sbcl-next-1.1.0

> /gnu/store/pqy064fw3vkfld6lw95vi0zavj19zvrc-sbcl-next-1.1.0-lib

> $ ./pre-inst-env guix run next

>

> WARNING: Setting locale failed.

> Check the following variables for correct values:

> LANG=en_US.utf8

> Unhandled SIMPLE-ERROR in thread #<SB-THREAD:THREAD "main thread" RUNNING

> {10005885B3}>:

> Couldn't execute "/gnu/store/7p6pbcmdgr53dff6033gcfl2jq0d762h-next-gtk-webkit-1.1.0/bin/next-gtk-webkit": No such file or directory

>

>

> (Here ‘guix run’ runs ‘next’ in a container with exactly the closure of

> ‘next’, nothing more, and the ‘next’ binary is grafted.)

>

> So the problem looks a lot like that this GCC issue we fixed a while

> back: <https://bugs.gnu.org/24703>.

>

> Looking at the ‘sbcl-next’ package, the reference to ‘next-gtk-webkit’

> is inserted in gtk-webkit.lisp:

>

> (defvar *gtk-webkit-command* "next-gtk-webkit"

> "Path to the GTK-Webkit platform port executable.")

>

>

> Through hexl-mode on the ‘next’ binary, we can find that reference:

>

> 01d0bac0: 2f00 0000 6700 0000 6e00 0000 7500 0000 /...g...n...u...

> 01d0bad0: 2f00 0000 7300 0000 7400 0000 6f00 0000 /...s...t...o...

> 01d0bae0: 7200 0000 6500 0000 2f00 0000 3700 0000 r...e.../...7...

> 01d0baf0: 7000 0000 3600 0000 7000 0000 6200 0000 p...6...p...b...

> 01d0bb00: 6300 0000 6d00 0000 6400 0000 6700 0000 c...m...d...g...

> 01d0bb10: 7200 0000 3500 0000 3300 0000 6400 0000 r...5...3...d...

> 01d0bb20: 6600 0000 6600 0000 3600 0000 3000 0000 f...f...6...0...

> 01d0bb30: 3300 0000 3300 0000 6700 0000 6300 0000 3...3...g...c...

> 01d0bb40: 6600 0000 6c00 0000 3200 0000 6a00 0000 f...l...2...j...

> 01d0bb50: 7100 0000 3000 0000 6400 0000 3700 0000 q...0...d...7...

> 01d0bb60: 3600 0000 3200 0000 6800 0000 2d00 0000 6...2...h...-...

> 01d0bb70: 6e00 0000 6500 0000 7800 0000 7400 0000 n...e...x...t...

> 01d0bb80: 2d00 0000 6700 0000 7400 0000 6b00 0000 -...g...t...k...

> 01d0bb90: 2d00 0000 7700 0000 6500 0000 6200 0000 -...w...e...b...

> 01d0bba0: 6b00 0000 6900 0000 7400 0000 2d00 0000 k...i...t...-...

> 01d0bbb0: 3100 0000 2e00 0000 3100 0000 2e00 0000 1.......1.......

> 01d0bbc0: 3000 0000 2f00 0000 6200 0000 6900 0000 0.../...b...i...

> 01d0bbd0: 6e00 0000 2f00 0000 6e00 0000 6500 0000 n.../...n...e...

> 01d0bbe0: 7800 0000 7400 0000 2d00 0000 6700 0000 x...t...-...g...

> 01d0bbf0: 7400 0000 6b00 0000 2d00 0000 7700 0000 t...k...-...w...

> 01d0bc00: 6500 0000 6200 0000 6b00 0000 6900 0000 e...b...k...i...

> 01d0bc10: 7400 0000 0000 0000 0000 0000 0000 0000 t...............

> 01d0bc20: e100 0100 0000 0000 2800 0000 0000 0000 ........(.......

> 01d0bc30: 2a47 544b 2d57 4542 4b49 542d 434f 4d4d *GTK-WEBKIT-COMM

> 01d0bc40: 414e 442a 0000 0000 0000 0000 0000 0000 AND*............

>

> Apparently this string literal is stored as UTF-32 (UCS-4) or similar,

> which prevents the reference scanner and the grafting code from finding

> it, and problems ensue. :-)

> Ludovic Courtès <ludo@gnu.org> writes:

>> Apparently this string literal is stored as UTF-32 (UCS-4) or similar,

>> which prevents the reference scanner and the grafting code from finding

>> it, and problems ensue. :-)

>

> IMO, we should consider modifying Guix to search for store references

> encoded in UTF-32 and/or UTF-16. I wouldn't be surprised if some other

> programs use those encodings. I'd be willing to work on it.

> I don’t think we’ve encountered the problem before.

> For now I lean towards looking for a way to address the issue

> specifically for SBCL.

> Thanks for looking into this, Ludo.

>

> At first glance, I'd say that this is not a compilation option but the way

> strings are encoded by default. It seems that multibyte encoding is used all

> over the place by a few compilers including SBCL (and CCL I think).

>

> One way I know around this (I'm by no mean a Common Lisp expert) is the

> flexi-streams package for re-encoding.

> More generally, shouldn't we make the reference scanner a bit smarter? In

> particular, how does it handle non-ASCII references? Maybe it would not be

> unreasonable to handle UTF-8 and UCS-4 for instance?

>> I don’t think we’ve encountered the problem before.

>

> Actually it does ring a bell for me. Didn't we have a similar issue with Fish,

> or some dependency?

>> For now I lean towards looking for a way to address the issue

>> specifically for SBCL.

>

> Don't forget that we currently have 5 Lisp compilers.

> Besides, it's not clear that this can be fixed on the compiler's side, it could

> very well be that patches will be required on a per-project basis.

> Store file names are always ASCII so problems arise when they are stored

> as UTF-16 or UTF-32/UCS-4.

> We did have a problem with Fish but I can no longer find it. Do you

> remember what it was? Something with C++, no?

> Pierre Neidhardt <mail@ambrevar.xyz> skribis:

>

>>> For now I lean towards looking for a way to address the issue

>>> specifically for SBCL.

>>

>> Don't forget that we currently have 5 Lisp compilers.

>> Besides, it's not clear that this can be fixed on the compiler's side, it could

>> very well be that patches will be required on a per-project basis.

>

> I know little about CL but maybe we can find a solution that works for

> all five compilers. At least that would be the first approach I would

> suggest following.

>> Store file names are always ASCII so problems arise when they are stored

>> as UTF-16 or UTF-32/UCS-4.

>

> I understand that most programs stick to ASCII filenames, but what about the odd

> one using non-English, special characters?

>> We did have a problem with Fish but I can no longer find it. Do you

>> remember what it was? Something with C++, no?

>

> I think bug #30265.

> Ludovic Courtès <ludo@gnu.org> writes:

>

>> Pierre Neidhardt <mail@ambrevar.xyz> skribis:

>>

>>>> For now I lean towards looking for a way to address the issue

>>>> specifically for SBCL.

>>>

>>> Don't forget that we currently have 5 Lisp compilers.

>>> Besides, it's not clear that this can be fixed on the compiler's side, it could

>>> very well be that patches will be required on a per-project basis.

>>

>> I know little about CL but maybe we can find a solution that works for

>> all five compilers. At least that would be the first approach I would

>> suggest following.

>

> I can't imagine a solution that would work for all five compilers, but

> perhaps that's a failure of imagination on my part. Of course, you're

> welcome to search for such a solution. Can you give me a rough outline

> of what you have in mind?

> : > Store file names are always ASCII so problems arise when they are stored

> : > as UTF-16 or UTF-32/UCS-4.

> :

> : I understand that most programs stick to ASCII filenames, but what about the odd

> : one using non-English, special characters?

>

> That’s a separate debate. :-) Essentially this restriction on store

> file names has always been there in Guix (and Nix before that). If we

> were to change it, that would raise compatibility issues.

> For example I guess we could always store the file name as a literal

> byte vector/list and add a call to turn that into a string.

> : > We did have a problem with Fish but I can no longer find it. Do you

> : > remember what it was? Something with C++, no?

> :

> : I think bug #30265.

>

> Oh I see, UCS-4 as well. (I can’t believe this bug is still open given

> the relatively simple solutions outlined at

> <https://issues.guix.info/issue/30265#8>. :-))

> Of course, the usual reason to choose UTF-32 is to support non-ASCII

> characters while retaining fixed-width code points, so that string

> lookups are straightforward and efficient.

> Using UTF-8 improves space efficiency, but at the cost of extra code

>complexity.

> That extra

> complexity is what I guess we would need to add to each program that

> currently uses UTF-32.

> Alternatively, we could extend the on-disk

> format to support UTF-8 and then add some kind of "load hook" that

> converts the string to UTF-32 at load time. Either way, it's likely to

> be a can of worms.

> I really think it would be a mistake to try to force every program and

> language implementation to use our preferred string representation. I

> suspect it would be vastly easier to compromise and support a few other

> popular string representations in Guix, namely UTF-16 and UTF-32.

> If you don't want to change the daemon, it could be worked around in our

> build-side code as follows: we could add a new phase to certain build

> systems (or possibly gnu-build-system) that scans each output for

> UTF-16/32 encoded store references that are never referenced in UTF-8.

> If such references exist, a file with an unobtrusive name would be added

> to that output containing those references encoded in UTF-8. This would

> enable our daemon's existing reference scanner to find all of the

> references.

>> : > Store file names are always ASCII so problems arise when they are stored

>> : > as UTF-16 or UTF-32/UCS-4.

>> :

>> : I understand that most programs stick to ASCII filenames, but what about the odd

>> : one using non-English, special characters?

>>

>> That’s a separate debate. :-) Essentially this restriction on store

>> file names has always been there in Guix (and Nix before that). If we

>> were to change it, that would raise compatibility issues.

>

> But what happens if we attempt to store "á" in the store?

> On Mon, 24 Dec 2018 13:12:23 -0500

> Mark H Weaver <mhw@netris.org> wrote:

>

>> Of course, the usual reason to choose UTF-32 is to support non-ASCII

>> characters while retaining fixed-width code points, so that string

>> lookups are straightforward and efficient.

>

> This kind of lookup is almost never what is necessary. There are many

> people who assume character is the same as codepoint and to those people

> UTF-32 brings something to the table, but it's really not useful if people

> do text processing correctly, see below.

>

> (Of course whether packages actually do this remains to be seen)

>

>> That extra

>> complexity is what I guess we would need to add to each program that

>> currently uses UTF-32.

>

> Yes, but they usually have to do stream processing even with UTF-32 (because

> a character can be composed of possibly infinite number of codepoints),

> so the infrastructure should be already there and the effort should be

> minimal.

> Also, if both UTF-32 and UTF-8 are used on disk, care needs to not misdetect

> an UTF-8 sequence as an UTF-32 sequence of different text - or the other way

> around -, but that's unlikely for ASCII strings.

>> I really think it would be a mistake to try to force every program and

>> language implementation to use our preferred string representation. I

>> suspect it would be vastly easier to compromise and support a few other

>> popular string representations in Guix, namely UTF-16 and UTF-32.

>

> In 1992, UTF-8 was invented. Subsequently, most of the Internet,

> all new GNU Linux distributions etc, all UNIX GUI frameworks, Subversion

> etc standardized on UTF-8, with the eventual goal of standardizing all

> network transfer and storage to UTF-8. I think that by now the outliers

> are the ones who need to change,

>> If you don't want to change the daemon, it could be worked around in our

>> build-side code as follows: we could add a new phase to certain build

>> systems (or possibly gnu-build-system) that scans each output for

>> UTF-16/32 encoded store references that are never referenced in UTF-8.

>> If such references exist, a file with an unobtrusive name would be added

>> to that output containing those references encoded in UTF-8. This would

>> enable our daemon's existing reference scanner to find all of the

>> references.

>

> I agree that that would be nice. As a first step, even just detecting

> problems like that and erroring out would be okay - in order to find them

> in the first place. Right now, it's difficult to detect and so also difficult

> to say how wide-spread the problem is. If the problem is wide-spread enough

> my tune could change very quickly.

> Pierre Neidhardt <mail@ambrevar.xyz> writes:

>

>>> : > Store file names are always ASCII so problems arise when they are stored

>>> : > as UTF-16 or UTF-32/UCS-4.

>>> :

>>> : I understand that most programs stick to ASCII filenames, but what about the odd

>>> : one using non-English, special characters?

>>>

>>> That’s a separate debate. :-) Essentially this restriction on store

>>> file names has always been there in Guix (and Nix before that). If we

>>> were to change it, that would raise compatibility issues.

>>

>> But what happens if we attempt to store "á" in the store?

>

> Indeed. Although we might restrict the immediate entries within

> /gnu/store to ASCII characters, file names deeper within those

> directories may have non-ASCII characters. More generally, store

> references may occur within larger strings which might include non-ASCII

> characters.

> In 1992, UTF-8 was invented. Subsequently, most of the Internet,

> all new GNU Linux distributions etc, all UNIX GUI frameworks, Subversion

> etc standardized on UTF-8, with the eventual goal of standardizing all

> network transfer and storage to UTF-8. I think that by now the outliers

> are the ones who need to change, otherwise these senseless encoding

> conversions will never cease. It's not like different encodings allow for

> better expression of writings or anything useful to the end user.

>

> As a distribution we can't force upstream to change, but just filing

> bug reports upstream would make us see where they stand on this.

> Just to be sure I understand: non-toplevel, non-ASCII file names will

> not be scanned properly, right?

> Every file in the store is properly scanned for references. It’s just

> that users cannot create top-level items with a non-ASCII file name.

>> Every file in the store is properly scanned for references. It’s just

>> that users cannot create top-level items with a non-ASCII file name.

>

> So if '/gnu/store/...-foo/á' is stored as UTF-8 in a binary, then it will be

> found? Is it because the filesystem encoding is also UTF-8 and Guix scans over

> byte arrays?

> The reference scanner, currently written in C++, traverses whole

> directory trees. Being C++ it treats file names as byte arrays so it

> doesn’t matter what the file name encoding is.

> Note also that the reference scanner only looks for “xyz…-foo”; what

> comes before and after doesn’t matter. So for example if you have

> “/gnu/store/xyz…-foo/à”, what’s important is the “xyz…-foo” bit.

>> The reference scanner, currently written in C++, traverses whole

>> directory trees. Being C++ it treats file names as byte arrays so it

>> doesn’t matter what the file name encoding is.

>

> But what matters then is that the filename encodings on the filesystem and in the

> binary match, right?

> I’m not sure what you call “the binary”. Do you mean the nar?

> Many grafting issues with Nyxt have been reported recently:

>

> https://github.com/atlas-engineer/nyxt/issues/1257

>

> Seems that glib is being grafted, which breaks cl-cffi-gtk and thus

> Nyxt.

>

> Is there a way to disable grafting for a given package? This would at

> least be a local workaround for Nyxt.

> I provided guidance in 2018 on how to address this issue:

>

> https://issues.guix.gnu.org/33848

> Did anyone talk to the SBCL folks? Please, let’s address this rather

> than look for workarounds.

> A brief discussion has ensued on SBCL bugtracker:

> - It's unlikely that SBCL will change its internal string

> representation.

> - The main recommendation for an easy fix without updating the scanner

> is that we tweaked our build system to dump the store reference to a

> separate ASCII file.

> What could have been nice is if there’s a way to mark specific strings

> as being ASCII, or if there’s a “byte vector” data type compatible with

> strings, for instance.

> 1. Some packages like ‘nyxt’ don’t use it, so we’d have to duplicate

> the phase there.

> 2. It may be coarse-grain compared to scanning binaries for references

> (for example, we might retain references to build-only tools, such

> as libraries used only for tests).

> - The main recommendation for an easy fix without updating the scanner

> is that we tweaked our build system to dump the store reference to a

> separate ASCII file.

> Pierre Neidhardt <mail@ambrevar.xyz> writes:

>> - The main recommendation for an easy fix without updating the scanner

>> is that we tweaked our build system to dump the store reference to a

>> separate ASCII file.

>

> Sounds good. I made a similar proposal in Dec 2018, earlier in this

> thread <https://bugs.gnu.org/33848#31>. I wrote:

>

> If you don't want to change the daemon, it could be worked around in our

> build-side code as follows: we could add a new phase to certain build

> systems (or possibly gnu-build-system) that scans each output for

> UTF-16/32 encoded store references that are never referenced in UTF-8.

> If such references exist, a file with an unobtrusive name would be added

> to that output containing those references encoded in UTF-8. This would

> enable our daemon's existing reference scanner to find all of the

> references.

>

> Our grafting code would then need to be extended to recognize and

> transform store references encoded in UTF-16/32 as well as UTF-8.

> The separate ASCII file doesn’t solve it all because, as you write, we’d

> need to change the grafting code as well.

>

> Then it might be simpler to use a “byte vector” data type for those

> strings.

> We’ll have to wait for Pierre’s patches to get a better idea.

> :-)

> If we are going for a SBCL-specific solution, I believe that all

> references are stored in plain text files at some points (the .asd files

> and the .lisp files) which are often encoded in ASCII / UTF-8, so

> searching these files without having to deal with their encoding might

> be enough. But of course this is less general and more brittle.

> Mark H Weaver <mhw@netris.org> skribis:

>

>> Pierre Neidhardt <mail@ambrevar.xyz> writes:

>>> - The main recommendation for an easy fix without updating the scanner

>>> is that we tweaked our build system to dump the store reference to a

>>> separate ASCII file.

>>

>> Sounds good. I made a similar proposal in Dec 2018, earlier in this

>> thread <https://bugs.gnu.org/33848#31>. I wrote:

>>

>> If you don't want to change the daemon, it could be worked around in our

>> build-side code as follows: we could add a new phase to certain build

>> systems (or possibly gnu-build-system) that scans each output for

>> UTF-16/32 encoded store references that are never referenced in UTF-8.

>> If such references exist, a file with an unobtrusive name would be added

>> to that output containing those references encoded in UTF-8. This would

>> enable our daemon's existing reference scanner to find all of the

>> references.

>>

>> Our grafting code would then need to be extended to recognize and

>> transform store references encoded in UTF-16/32 as well as UTF-8.

>

> Oh thanks for the reminder.

>

> The separate ASCII file doesn’t solve it all because, as you write, we’d

> need to change the grafting code as well.

>

> Then it might be simpler to use a “byte vector” data type for those

> strings. We’ll have to wait for Pierre’s patches to get a better idea.

> :-)

> A store reference to a C library in a standalone Lisp binary can come

> either from the current package or from some dependencies

> (cl+ssl, cl-cffi-gtk, etc.). So we would need to scan the source

> code of all the Lisp dependencies recursively to get the full list of

> store refrences.

> And as Mark wrote below, with the current grafting code, this list of

> store references will not solve grafting for paths that are in UTF-32 or

> both in ASCII and UTF-32 in the binary file.

> Hi Guillaume!

>

>> A store reference to a C library in a standalone Lisp binary can come

>> either from the current package or from some dependencies

>> (cl+ssl, cl-cffi-gtk, etc.). So we would need to scan the source

>> code of all the Lisp dependencies recursively to get the full list of

>> store refrences.

>

> I don't think there is need to scan recursively: if package A depends on

> B which depends on C, then A can lists the dependency on B in a file,

> and B can do the same for C. This way the relationship between A and C

> is properly stored.

>

> Am I missing something?

>> And as Mark wrote below, with the current grafting code, this list of

>> store references will not solve grafting for paths that are in UTF-32 or

>> both in ASCII and UTF-32 in the binary file.

>

> Indeed, and that's the core of the issue here I believe, since grafting

> is what breaks Nyxt in practice.

>

> Cheers!

> Oh, you say this file would be created for every Lisp package. I thought

> it would only be for the standalone binary case, because the "regular"

> asdf-build-system/sbcl used for Lisp libraries ships the sources and its

> make-asdf-configuration phase creates links to the required Lisp

> dependencies in '/gnu/store/...', so there should not be missing

> references.

> I just wondered: does the grafting code take '.fasl' files into

> consideration?

> If yes, I guess a Lisp library could also end up in a strange

> half-grafted state if the grafting code modifies ASCII references and

> not UTF-32 ones...

> I'm not familiar with the grafting code, so anyone who is (Mark? Ludo?)

> might be able to fix this much quicker than me! :)

> What could have been nice is if there’s a way to mark specific strings

> as being ASCII, or if there’s a “byte vector” data type compatible with

> strings, for instance.

> I'm not familiar with the grafting code, so anyone who is (Mark? Ludo?)

> might be able to fix this much quicker than me! :)

> Ludovic Courtès <ludo@gnu.org> writes:

>> What could have been nice is if there’s a way to mark specific strings

>> as being ASCII, or if there’s a “byte vector” data type compatible with

>> strings, for instance.

>

> Do we know that all strings containing store references will be

> representable in ASCII?

> Wow, that was fast, thank you Mark!

>

> Any idea how I can test this, i.e. how I can force a graft?

> Pierre Neidhardt <mail@ambrevar.xyz> writes:

>

>> Wow, that was fast, thank you Mark!

>> Any idea how I can test this, i.e. how I can force a graft?

>

> Just apply the patch to a git checkout of Guix, build it, and then use

> it to build anything you like, e.g. "./pre-inst-env guix build nyxt".

>

> With this patch applied, all graft derivations will be rebuilt, but

> *only* grafts. When it's ready (i.e. when it has better comments,

> docstrings, etc), this change is perfectly appropriate for 'master'.

> Mark H Weaver <mhw@netris.org> skribis:

>

>> With this patch applied, all graft derivations will be rebuilt, but

>> *only* grafts. When it's ready (i.e. when it has better comments,

>> docstrings, etc), this change is perfectly appropriate for 'master'.

>

> The GC’s scanner still gets it wrong though. I wonder whether having

> the grafting code more capable than the scanner could lead to bad

> surprises. WDYT?

> That the scanner fails to find all references is clearly an important

> problem that should be fixed ASAP, but as far as I can tell, improving

> the grafter would not make that problem any worse or create any new

> problems.

>

> Improving the grafter should have the following effects:

>

> (1) Reducing the number of cases where ungrafted code with security

> flaws is being used on our systems.

>

> (2) Fixing problems in our Fish, Nyxt, and Common Lisp packages.

> Improving the scanner, or adding phases to selected packages or build

> systems to copy hidden references to an ASCII file, should have the

> following effects:

>

> (1) Reducing the number of cases where run-time dependencies are not

> known to Guix, which could lead to dependencies being prematurely

> GC'd or excluded from things like "guix pack".

>

> So, it seems to me that we should persue both of these improvements

> concurrently, and I see no practical advantage to postponing one for the

> sake of rolling them both out at the same time. Of course, I welcome

> other opinions on this.

> After applying the patch you sent, I confirm that Nyxt starts just fine

> when running:

>

> ./pre-inst-env guix environment --ad-hoc nyxt -CN -E ^DISPLAY --share=/tmp/.X11-unix -- nyxt

>

> … whereas on master it fails to start with:

>

> --8<---------------cut here---------------start------------->8---

> Unhandled SIMPLE-ERROR in thread #<SB-THREAD:THREAD "main thread" RUNNING

> {10010D0103}>:

> Problem running initialization hook GLIB::RUN-INITIALIZERS:

> Unable to load any of the alternatives:

> ("/gnu/store/4vmhbc31cpbnlw3c96kcc094ihmaf7dv-glib-2.62.6/lib/libglib-2.0.so.0"

> "/gnu/store/4vmhbc31cpbnlw3c96kcc094ihmaf7dv-glib-2.62.6/lib/libglib-2.0.so")

> --8<---------------cut here---------------end--------------->8---

> The GC’s scanner still gets it wrong though. I wonder whether having

> the grafting code more capable than the scanner could lead to bad

> surprises. WDYT?

> On Mon, Apr 05, 2021 at 09:45:43PM +0200, Ludovic Courtès wrote:

>> The GC’s scanner still gets it wrong though. I wonder whether having

>> the grafting code more capable than the scanner could lead to bad

>> surprises. WDYT?

>

> I'm going off-topic, but I've wished we had a generic fast string-search

> (and replace?) procedure.

> The go-build-system has a slow "one byte a time" implementation because

> I couldn't figure out how to re-use the code in (guix build grafts):

>

> https://git.savannah.gnu.org/cgit/guix.git/tree/guix/build/go-build-system.scm?h=v1.2.0#n269

> From 6eec36e66d20d82fe02c6de793422875477b90d8 Mon Sep 17 00:00:00 2001

> From: Mark H Weaver <mhw@netris.org>

> Date: Fri, 2 Apr 2021 18:36:23 -0400

> Subject: [PATCH] DRAFT: grafts: Support rewriting UTF-16 and UTF-32 store

> references.

>

> * guix/build/graft.scm (replace-store-references): Add support for

> finding and rewriting UTF-16 and UTF-32 store references.

> * tests/grafts.scm: Add tests.

> +(define (possible-utf16-hash? buffer i w)

> + (and (<= (* 2 hash-length) (- i w))

> + (let loop ((j (+ 1 (- i (* 2 hash-length)))))

> + (or (>= j i)

> + (and (zero? (bytevector-u8-ref buffer j))

> + (loop (+ j 2)))))))

> +

> +(define (possible-utf32-hash? buffer i w)

> + (and (<= (* 4 hash-length) (- i w))

> + (let loop ((j (+ 1 (- i (* 4 hash-length)))))

> + (or (>= j i)

> + (and (zero? (bytevector-u8-ref buffer j))

> + (zero? (bytevector-u8-ref buffer (+ j 1)))

> + (zero? (bytevector-u8-ref buffer (+ j 2)))

> + (loop (+ j 4)))))))

> +

> +(define (insert-nuls char-size bv)

> +(for-each

> + (lambda (char-size1)

> + (for-each

> + (lambda (char-size2)

> + (for-each

> + (lambda (gap)

> + (for-each

> + (lambda (offset)

> + (test-equal (format #f "replace-store-references, char-sizes ~a ~a, gap ~s, offset ~a"

> + char-size1 char-size2 gap offset)

> + (string-append (make-string offset #\=)

> + (nul-expand (string-append "/gnu/store/"

> + (make-string 32 #\6)

> + "-BlahBlaH")

> + char-size1)

> + gap

> + (nul-expand (string-append "/gnu/store/"

> + (make-string 32 #\8)

> + "-SoMeTHiNG")

> + char-size2)

> + (list->string (map integer->char (iota 77 33))))

> +

> + ;; Create input data where the right-hand-size of the dash ("-something"

> + ;; here) goes beyond the end of the internal buffer of

> + ;; 'replace-store-references'.

> + (let* ((content (string-append (make-string offset #\=)

> + (nul-expand (string-append "/gnu/store/"

> + (make-string 32 #\5)

> + "-blahblah")

> + char-size1)

> + gap

> + (nul-expand (string-append "/gnu/store/"

> + (make-string 32 #\7)

> + "-something")

> + char-size2)

> + (list->string

> + (map integer->char (iota 77 33)))))

> + (replacement (alist->vhash

> + `((,(make-string 32 #\5)

> + . ,(string->utf8 (string-append

> + (make-string 32 #\6)

> + "-BlahBlaH")))

> + (,(make-string 32 #\7)

> + . ,(string->utf8 (string-append

> + (make-string 32 #\8)

> + "-SoMeTHiNG")))))))

> + (call-with-output-string

> + (lambda (output)

> + ((@@ (guix build graft) replace-store-references)

> + (open-input-string content) output

> + replacement

> + "/gnu/store"))))))

> + ;; offsets to test

> + (map (lambda (i) (- buffer-size (* 40 char-size1) i))

> + (iota 30))))

> + ;; gaps

> + '("" "-" " " "a")))

> + ;; char-size2 values to test

> + '(1 2)))

> + ;; char-size1 values to test

> + '(1 2 4))

> Please add a “Fixes” line in the commit log.

> I’m not reviewing the code in depth and I trust your judgment.

>

> The risks of bugs I can think of are: missed ASCII references (a

> regression, whereby some ASCII references would not get rewritten),

> and unrelated UTF-{16,32}-base32-looking references getting rewritten.

>

> I guess the latter is very unlikely because only sequences found in the

> replacement table may be rewritten, right?

> The former should be caught by ‘tests/grafts.scm’ but we could also

> check the closure of real-world systems, for instance, to make sure it

> doesn’t refer to ungrafted things.

> Do you know how this affects performance?

> Perhaps add short docstrings for clarity.

>> +(for-each

>> + (lambda (char-size1)

>> + (for-each

>> + (lambda (char-size2)

>> + (for-each

>> + (lambda (gap)

>> + (for-each

>> + (lambda (offset)

>> + (test-equal (format #f "replace-store-references, char-sizes ~a ~a, gap ~s, offset ~a"

>> + char-size1 char-size2 gap offset)

>> + ;; offsets to test

>> + (map (lambda (i) (- buffer-size (* 40 char-size1) i))

>> + (iota 30))))

>> + ;; gaps

>> + '("" "-" " " "a")))

>> + ;; char-size2 values to test

>> + '(1 2)))

>> + ;; char-size1 values to test

>> + '(1 2 4))

>

> For clarity, perhaps you can define a top-level procedure for the test

> and call it from ‘for-each’.

> Modulo these very minor issues, it looks like it’s ready to go!

>> The risks of bugs I can think of are: missed ASCII references (a

>> regression, whereby some ASCII references would not get rewritten),

>

> This is indeed a risk whenever we modify the grafting code, which is

> written for efficiency, not clarity. I've tried to be careful, and have

> checked that my newly grafted system and user profiles do not retain

> references to ungrafted code, modulo the following pre-existing issues:

>

> <https://bugs.gnu.org/47576>

> (ibus-daemon launches ungrafted subprocesses)

>

> <https://bugs.gnu.org/47614>

> (Chunked store references in .zo files in Racket 8)

>> and unrelated UTF-{16,32}-base32-looking references getting rewritten.

>>

>> I guess the latter is very unlikely because only sequences found in the

>> replacement table may be rewritten, right?

>

> Yes, that's correct.

>

>> The former should be caught by ‘tests/grafts.scm’ but we could also

>> check the closure of real-world systems, for instance, to make sure it

>> doesn’t refer to ungrafted things.

>

> As I mention above, I've already done so for my own GNOME-based Guix

> system.

>> Do you know how this affects performance?

>

> I have not yet measured it, but subjectively, I do not notice any

> obvious difference in speed.

>

> I expect that the main performance impact is that large blocks of NULs

> will be processed more slowly by the current draft version of the new

> grafting code. That's because NULs can now be part of a nix hash, and

> therefore the new grafting code can only advance 1 byte position when

> seeing a NUL, whereas previously it would skip ahead 33 positions in

> that case.

>

> If desired, the handling of NULs could be made more efficient, at the

> cost of a bit more complexity. When seeing a NUL, we could check the

> adjacent bytes to see if this is part of a nix-base32 character in

> UTF-16 or UTF-32 encoding. If not, we could skip ahead.

>> For clarity, perhaps you can define a top-level procedure for the test

>> and call it from ‘for-each’.

>

> Good idea. I'd like to optimize the tests a bit before pushing this.

> They take a fairly long time to run, and lead to a huge 1.5G grafts.log

> file. It might be sufficient to avoid 'test-equal' here.

> Below, I've attached my current revision of this draft patch, which

> incorporates your suggestions regarding the main code. What remains is

> to improve the tests.

> LGTM! Feel free to push this version or an improved one. I think it’s

> good to have it in the upcoming release, and if it’s pushed sooner,

> we’ll have more time to react in case something’s wrong.

> LGTM! Feel free to push this version or an improved one. I think it’s

> good to have it in the upcoming release, and if it’s pushed sooner,

> we’ll have more time to react in case something’s wrong.

> I also agree this looks like a net win even though the `guix gc` issue

> is not fix.

> The latter seems to be relatively easier to fix, doesn't it?

> I intend to write a scanner in Scheme that is able to find Nix hashes

> encoded in ASCII, UTF-16, or UTF-32. Using that, I'll write a procedure

> that, for each package output, finds all store references that are found

> encoded in UTF-16 or UTF-32 but never in ASCII, and write those

> references to a file (if that set is nonempty). This procedure can then

> be used by selected packages and/or build-systems.

>

> However, there's one thing I will need: the set of all transitive inputs

> (and native-inputs, including implicit inputs) available to the build,

> i.e. the set of possible hashes that might legitimately be found by the

> scanner.

>

> Ludovic: what's the best way to get that list from the build-side code?