microsoft / trieste Goto Github PK

I was expecting the pattern Any++ * T(Bar) to match the sequence Foo Foo Foo Bar, just as the regular expression .*b matches aaab, but it seems like the Any++ matches all of Foo Foo Foo Bar, meaning the whole pattern fails to match (since there is no Bar after that sequence). I don't know if this is by design, nor what the consequences would be of making it more like the kleene star, but I thought I would bring it up for discussion.

My use case was for matching a Y inside an X, where the last child of Y is a Z (for reasonable values of X, Y, and Z):

In(X) * T(Y) << (Any++ * T(Z) * End)

If I didn't care about both the X and the Y I could just have T(Z) * End, but I now it's important that the Y is in an X and has the children specified. In this particular case I can do (!T(Z))++ * T(Z), but in general this might not be satisfactory.

I was debugging a hard-to-track issue in a build of rego where random files would be missing from the install tree after a call to cmake --install. Ultimately, it turned out to be the following command in the CMakeLists.txt of trieste.

I think it's not a good idea to do that, in particular in situations where the user install into /usr/local. But even for other destinations, trieste should not assume to be the only library in that tree. Is there a particular reason to do that, that I'm missing?

The pattern matching semantics has some surprising corner cases related to predicate patterns, i.e., patterns that do not consume tokens. I take predicate patterns to mean lookahead (++p and --p) as well as the "positional" patterns In(ty), Start and End.

For example, let's look at what happens when negating predicates with the ! pattern:

!(Start) * T(Foo) >>
  [](Match&) { return NodeDef::create(Bar); }

Running this on foo foo bar results in bar bar, since !(Start) matches on the first foo and consumes it together with the subsequent foo. I would say the expected result here is foo bar bar. If we instead match on T(Bar) * !(Start), nothing happens since ! only matches if there is a term to consume in that position.

More generally, I would expect the negation of a zero-width pattern to consume zero terms. The semantics for negation of patterns longer than one is also unintuitive:

!(T(Foo) * T(Bar)) * T(Bar) >>
  [](Match&) { return NodeDef::create(Baz); }

Running this on foo bar bar currently results in foo baz, whereas running it on foo foo bar does nothing. In the first case, the negation pattern is successfully matched against bar bar and then the first bar is consumed, after which T(Bar) matches on the second bar. In the second case, although foo foo matches the negation pattern, only the first foo is consumed, so the second foo does not match T(Bar). After advancing the cursor foo bar fails to match the negation pattern.

Another corner case is pattern matching the children of a zero-width sequence:

Start >> T(Foo)[Foo] >>
  [](Match& _) { return _(Foo); }

This example currently causes a segfault, since there are no children in the sequence matched by Start. More reasonable would be to fail matching, or possibly to (ideally statically) disallow the pattern since it will never succeed.

A related question is how to interpret matching on the the children of a sequence of more than one term:

(T(Foo) * T(Bar)) << (Any[Any]) >>
  [](Match& _) { return _(Any); }

Currently, Any binds to the first child of whatever comes first in the sequence (here Foo) which might be what we want. Other possible semantics include failing, or letting Any bind to the first child of every node in the parent pattern. If we go for requiring well formedness, we could disallow any <<-pattern where the parent pattern does not match exactly one term.