Avoid hyperbracket capture by using sets of scopes

[rocketnia]

Punctaffy's present design may be susceptible to some code injection gotchas if a macro inserts one of its caller-provided subforms into a hyperbracketed region. In that situtation, I believe closing hyperbrackets appearing in the subform will match up with ones generated by the macro (e.g. to open the region). I believe something similar is possible with quasiquote and unquote, but Punctaffy doesn't have to preserve that.

To address this, we can have each bracket refer to an "interposition point" anaphoric variable representing the surrounding lexical context. Usually, this variable is not specified explicitly, and it has the lexical information of the hyperbracket's beginning syntax object. This variable can carry a hyperstack in its syntax-local-value.

We've partially prepared for this with the 'context part of the taffy-notation-akin-to-^<>d-parse result, which currently uses #%context as the name of the interposition point. Let's change this to 'lexical-context and #%lexical-context.

Many other implicit bindings we might want to create should eventually be carried in that variable too. That way, their bindings can be in scope only for a delimited hypersnippet of code, and their preexisting bindings can be visible again in the hypersnippet's holes. But let's focus on matching brackets for now.

• Make sure that it's an issue in the first place.
  • Create an example of the issue using quasiquote and unquote. [We've done so in the comments below.]
  • Create an example of the issue using Punctaffy's ^< and ^>. [We've done so in the comments below.]
• Rename 'context and #%context to 'lexical-context and #%lexical-context.
• Carry a simple hyperstack of trivial values in #%lexical-context. In taffy-notation-akin-to-^<>d? traversals, update the stack, and error out if a closing hyperbracket is of too high degree for the stack's current dimension. Initially, don't worry about whether the bindings of #%lexical-context behave in a set-of-scopes way.
• Figure out how to make the bindings behave in a set-of-scopes way. This might be tricky if we're code-walking rather than expanding into let-syntax as we go along.
• Test that the example we created using Punctaffy's ^< and ^> now avoids hyperbracket capture.

[rocketnia]

Here's an example of hyperbracket capture with quasiquote and unquote:

#lang racket/base

(define-syntax-rule (test subform)
  `(subform ,(+ 3 4)))

(writeln (test (+ 1 2)))
(writeln (test ,(+ 1 2)))

Output:

((+ 1 2) 7)
(3 7)

I'm not sure whether to add a unit test for this one way or the other, since I wouldn't mind for Racket to change this behavior someday.

Here's a corresponding file written with the current version of taffy-quote. It has the same output, demonstrating the same hyperbracket capture:

#lang parendown/slash racket/base

(require /only-in punctaffy ^< ^>)
(require /only-in punctaffy/quote taffy-quote)

(define-syntax-rule (test subform)
  (taffy-quote /^< (subform (^> /list /+ 3 4))))

(writeln (test (+ 1 2)))
(writeln (test (^> /list /+ 1 2)))

[rocketnia]

While I believe this is an issue, I now think it may run much deeper in Racket's approach, and now I'm indecisive.

As I've pursued an approach for this lately, I initially thought I would only need to preface any free-identifier=? check with a check that the identifier occurring in the macro's input had a superset of the scopes of the macro call site. But conceptually, the problem is not limited to identifiers. Any piece of data in a macro's input that gets special casing by the macro is essentially being imbued with meaning by the macro, whether that's an identifier, a cons cell, a literal datum, etc. If that node of the input data doesn't have a superset of the scopes the macro call does (in the sense of Racket's sets-of-scopes hygiene model), then this imbued meaning can be captured in a potentially undesirable way, very much analogous to capturing an identifier.

To avoid this kind of capture in Racket, we would pretty much have to modify syntax-parse itself so that its cons cell patterns (and various other patterns) don't match any node that has the wrong set of scopes on it. This is a pervasive issue throughout all Racket core syntaxes.

For Punctaffy's sake, we could take a stand and fix this. But doing so would make Punctaffy the odd one out in the Racket ecosystem and could make Punctaffy harder to understand for Racket users. A much easier approach would be to change our attitude and embrace that we're enabling this kind of capture just like everyone else is.

Still, accepting the status quo might lead to disappointments in the experiences people have with Punctaffy which are mostly unprecedented in the rest of the ecosystem. Unlike most other Racket syntaxes (but at least like quasiquote, etc.), Punctaffy traverses deeply into the s-expression trees it receives. This deep traversal creates a hazardous scenario:

• Users of the macro who are reluctant to go to the effort to write their own deep traversal functions, unwilling to keep them in feature parity with all the features the macro offers, or concerned about the algorithmic complexity of macroexpansion may be motivated to pass along their data directly to the macro for it to traverse. (It's an algorithmic complexity issue because if an input tree of size N is traversed by each of the M macro calls surrounding it, that's a cost of O(N*M).)
• Users of the macro who pass along their data directly to the macro may also be unimaginative about all the things that data could someday be. If the data comes from user input, the user may take advantage of that overlooked expressiveness to perform a code injection attack.

Because of this, it may be worth it to implement sets-of-scopes-respecting behavior for Punctaffy's deep traversals even though it's inconsistent with the rest of the ecosystem.

[rocketnia]

For reference, here are two places I brought up the free-identifier=? topic on the Racket Discourse forum (not that much discussion has come from it):

• The thread "Opinions on quasiquote..unquote matching up when not lexically together?"
• A reply on "RFC: hash table pattern matching." "Actually, free-identifier=? doesn't have perfect hygiene itself. [...]"