Skip to content

Conversation

herbelin
Copy link
Member

@herbelin herbelin commented Jul 20, 2023

This makes a step in direction to have gramlib respecting the choice of non-associativity and the choice of levels made by the user.

The PR adds internal flags to activate non-associativity and deactivate recovery (see #9008).

The flags are not activate yet as it would break the developments that exploit (even w/o knowing it) the non-respect of the grammar specification.

Level fallbacks

The code for deactivating the fallbacks of the recovery mode is in two parts:

  1. the two fallbacks changing levels are easy to protect behind the flag
  2. a second recovery mechanism (which I only discovered recently while implementing the PR) is in this situation:
Notation "x !" := (S x) (at level 2).
Check 0!%nat.

where the last line is currently parsed even though %type expects its argument at level 1: it is accepted because, after a notation at level XX, all continuations of level lower than XX are also tried (and this includes the continuation at Coq level "1").

To prevent the second recovery, we have to apply continuations on an interval of levels rather than on an interval starting necesarily from the last level.

Non-associativity

Adding a notion of interval for continuations is also exactly what we need to support non-associativity. Indeed, being non-associative means applying at most the continuation to the leftmost SELF in configurations such as SELF; "op"; SELF. So, when a level N is non-associative and the continuation matches, it is enough to shrink the interval of continuations to now exclude N.

Notes

On the contrary of left/right associativity, I don't know how to implement non-associativity on a rule-based view. Repeating a continuation at most one or repeating it arbitrarily often is a decision global to a level.

For the record, order of levels in gramlib is reversed from Coq (Coq top level "200" is level 0 for gramlib while Coq level "0" is the higher level for gramlib and has value equal to the number of levels minus 1).

Warning

To let every user adapt, it had been decided to only warn when using the recovery mode. Thanks to many other improvements in the latest years, adapting developments now seems reasonable. FTR, we tried to compile a few basic libraries with the warning as error:

Overlays (to be merged before the current PR)

Overlay (to be merged in sync with the current PR)

@herbelin herbelin added kind: enhancement Enhancement to an existing user-facing feature, tactic, etc. part: parser The parser (also called gramlib, forked from camlp5) labels Jul 20, 2023
@herbelin herbelin added this to the 8.19+rc1 milestone Jul 20, 2023
@herbelin herbelin requested a review from a team as a code owner July 20, 2023 09:54
@coqbot-app coqbot-app bot added the needs: full CI The latest GitLab pipeline that ran was a light CI. Say "@coqbot run full ci" to get a full CI. label Jul 20, 2023
@proux01 proux01 added the request: full CI Use this label when you want your next push to trigger a full CI. label Oct 11, 2023
@proux01 proux01 force-pushed the master+gramlib-support-for-non-assoc-and-non-recovery branch from 9fc014e to a1d3592 Compare October 11, 2023 15:32
@herbelin herbelin requested review from a team as code owners October 11, 2023 15:32
@coqbot-app coqbot-app bot removed request: full CI Use this label when you want your next push to trigger a full CI. needs: full CI The latest GitLab pipeline that ran was a light CI. Say "@coqbot run full ci" to get a full CI. labels Oct 11, 2023
@coqbot-app
Copy link
Contributor

coqbot-app bot commented Oct 11, 2023

The job library:ci-fiat_crypto_legacy has failed in allow failure mode
ping @JasonGross

proux01 added a commit to proux01/math-comp that referenced this pull request Oct 12, 2023
proux01 added a commit to proux01/math-comp that referenced this pull request Oct 14, 2023
proux01 added a commit to proux01/math-comp that referenced this pull request Oct 14, 2023
proux01 added a commit to proux01/math-comp that referenced this pull request Oct 15, 2023
@github-actions github-actions bot added the needs: rebase Should be rebased on the latest master to solve conflicts or have a newer CI run. label Oct 28, 2023
@herbelin
Copy link
Member Author

Here is a first analysis of the failures (up to math-classes). All seems legitimate and have a solution. For two of them (engine bench and iris), the solution is at the Coq level.

Bedrock2:

Notation "x {{ u }}" ... (at level 8).
Check x{{u}}.(field). (* now fails because "t.(...)" expects t at level 1 *)

Reasonable solution: move "x {{ u }}" at level 1?

Category theory:

Notation "⟨πD,πC⟩" := comma_proj (at level 100).
Check ⟨πD,πC⟩ ≈ ⟨πD,πC⟩ ◯ φ. (* ◯ at level 40 *)

Reasonable solution: move ⟨πD,πC⟩ at level 0

CoLoR:

Notation "x !" := (clos_trans x) (at level 35).
Check R! x y.

Reasonable solution: move "x !" at level < 10 (e.g. 1, since its argument seems to be a variable in practice).

Cross-crypto:

Notation "'ret' v" := (MRet _ v) (at level 75).
Check x = ret v.

Tentative solution: move "'ret' v" at level 69 (as it is sometimes applied to an application, or to "a::l")

Engine bench:

Ltac f := do 1000 let v := open_constr:(_ : True) in idtac. (* "let" at level 5 but "do" expects level 3)

Do like for binder_constr, i.e. move binder_tactic at level 1 (where application lives), and this would even simplify repeated rules like for tac + tac.

HoTT:

Notation "f ^-1" := (@equiv_inv _ _ f _) (at level 3).
Check f^-1%equiv. (* % expects its argument at level 1 *)

Reasonable solution: move "f ^-1" at level 1.

Iris:

split; [|done] => _. (* knowing that "=>" expects its argument at level 1, but ";" is at level 4 *)

Solution: decide if "=>" really wants to be at level 1.

itree:

Check pure (m := m) (a := a + (b + c))%type. (* %type does not apply to a (a:=b) as might be expected *)

Solution: move %type inside the parenthesis

Math classes:

Notation "∥ L ∥" := (norm L) (at level 50).
Check (abs a) * ∥v∥. (* "*" expects level 40 but ∥v∥ is at level 50 *)

Solution: move "∥ L ∥" at level 0.

@herbelin
Copy link
Member Author

herbelin commented Oct 28, 2023

At the Coq call (2023-10-24), the question of adding a warning so as to allow users to do the changes themselves was raised, and this is certainly that can be tried (i.e., in case of parsing error, we try the recovery mode even though it is deactivated, and if it succeeds, we warn that it has been used).

The investigations above also suggest the following:

  • For closed notations (such as ∥ L ∥ or ⟨πD,πC⟩), put them automatically at level 0 and warns (or warn that it could be better put at level 0).
  • For postfix notations (such as x {{ u }}, R ! or f ^-1), warn that it is in general clearer to put them at level 1.

@JasonGross
Copy link
Member

What is the status of Fiat Crypto Legacy?

@proux01
Copy link
Contributor

proux01 commented Oct 28, 2023

What is the status of Fiat Crypto Legacy?

The first error look similar to engine bench (ltac level issue, with repeat).

@proux01 proux01 force-pushed the master+gramlib-support-for-non-assoc-and-non-recovery branch from a1d3592 to e99791a Compare October 28, 2023 16:43
@proux01 proux01 requested a review from a team as a code owner October 28, 2023 16:43
@coqbot-app coqbot-app bot added needs: full CI The latest GitLab pipeline that ran was a light CI. Say "@coqbot run full ci" to get a full CI. and removed needs: rebase Should be rebased on the latest master to solve conflicts or have a newer CI run. labels Oct 28, 2023
@coqbot-app coqbot-app bot removed the request: full CI Use this label when you want your next push to trigger a full CI. label Jul 3, 2025
proux01 added 3 commits July 4, 2025 07:17
Until DeepSpec/sf#16 can get in / the process
for overlays there can be documented.
@proux01 proux01 added the request: full CI Use this label when you want your next push to trigger a full CI. label Jul 4, 2025
@proux01 proux01 force-pushed the master+gramlib-support-for-non-assoc-and-non-recovery branch from 3c1b212 to 4ef200e Compare July 4, 2025 05:19
@coqbot-app coqbot-app bot removed the request: full CI Use this label when you want your next push to trigger a full CI. label Jul 4, 2025
@rocq-prover rocq-prover deleted a comment from coqbot-app bot Jul 4, 2025
Until overlays for rocq-prover#17876
get properly merged
@proux01 proux01 force-pushed the master+gramlib-support-for-non-assoc-and-non-recovery branch from 4ef200e to 5d7b04d Compare July 4, 2025 06:23
@coqbot-app coqbot-app bot added the needs: full CI The latest GitLab pipeline that ran was a light CI. Say "@coqbot run full ci" to get a full CI. label Jul 4, 2025
@proux01 proux01 removed the needs: full CI The latest GitLab pipeline that ran was a light CI. Say "@coqbot run full ci" to get a full CI. label Jul 4, 2025
@proux01
Copy link
Contributor

proux01 commented Jul 4, 2025

@coqbot merge now

@coqbot-app coqbot-app bot merged commit ed67c98 into rocq-prover:master Jul 4, 2025
2 of 3 checks passed
proux01 added a commit to rocq-prover/stdlib that referenced this pull request Jul 4, 2025
@proux01
Copy link
Contributor

proux01 commented Jul 4, 2025

I had to temporarily disactivate kami and sf that are infriging the CI contract:

- You react in a timely manner to adapt to the few requested changes
required by Rocq developers or to integrate their patches (in a 7 days timeframe,

@samuelgruetter, @andres-erbsen, @bcpierce00, @liyishuai I'll happily merge any PR reverting the corresponding commit once things are fixed downstream.

CohenCyril added a commit to math-comp/math-comp that referenced this pull request Jul 4, 2025
proux01 added a commit to proux01/rocq that referenced this pull request Jul 6, 2025
proux01 added a commit to proux01/rocq that referenced this pull request Jul 7, 2025
proux01 added a commit to proux01/rocq that referenced this pull request Jul 11, 2025
@Zimmi48
Copy link
Member

Zimmi48 commented Jul 21, 2025

I had to temporarily disactivate kami and sf that are infriging the CI contract:

- You react in a timely manner to adapt to the few requested changes
required by Rocq developers or to integrate their patches (in a 7 days timeframe,

@samuelgruetter, @andres-erbsen, @bcpierce00, @liyishuai I'll happily merge any PR reverting the corresponding commit once things are fixed downstream.

You say disable Kami, but AFAIU the Kami overlay was merged, it was just incorrectly propagated to its reverse deps. There seems to have been some action to propagate it after your request (mit-plv/fiat-crypto#2112), so what was the final status of the issue when this PR got merged? There isn't much trace to get this info here or elsewhere.

@JasonGross
Copy link
Member

Indeed the update was propagated before this PR as described by Andres in

That's a stale PR. fiat-crypto is not auto-updating because the build is broken.

Manual update at mit-plv/fiat-crypto#2112

So please revert the disabling of Fiat Crypto and its dependencies.

@proux01
Copy link
Contributor

proux01 commented Jul 29, 2025

Indeed the update was propagated before this PR as described by Andres in

This is obviously wrong, kami was still red in CI at the time of merging. I wouldn't have had to disactivate it otherwise.
According to this PR, the last overlay still wasn't propagated through all the git submodules at the time of merging, 12 days after it's opening (in fact, Stdlib CI indicates that this propagation finally happened only ten more days later).
So apparently I was right to be tired of waiting, and having to rebase this PR several times, just because of that git submodule propagation taking weeks.
We have a CI policy, please adhere to it and don't waste developer's time!

@andres-erbsen
Copy link
Contributor

andres-erbsen commented Jul 29, 2025

I think what happened here is that there were two overlays to kami with identical commit summaries, and the second one missed the manual bump in fiat-crypto. I don't think it's worth our time debating what the letter of the CI policy says about this case, and specifically for this PR I am quite happy it is finally merged one way or another. At the same time, if you had contacted us instead of waiting, we would have happily made and merged a fiat-crypto overlay to the desired effect; at least i was unaware that another one was needed.

More generally, in situations like this where multiple things are failing for multiple reasons, I think communicating more earlier about what each of us sees is going on can help a lot. I do believe everyone is trying to do a good thing here, and trying to clear up ambiguity about how things are is more likely to be successful than reiterating how things should be.

In that spirit, I would like to reiterate that the automatic submodule bumper in fiat-crypto is a conservative best-effort measure. If it doesn't work in 24h, please contact us and ask for an overlay. If it doesn't work, and there isn't an underlying cause like fiat-crypto being broken by an earlier rocq change, we will treat this as a bug in the autobumper. But having triggered the autobumper isn't necessarily enough to get an overlay created and merged to fiat-crypto.

Details: The rocq-pr rebase right before disabling kami ran ci and at least according to gitlab logs it did include a kami overlay and the merge commit i linked to earlier. It also still failed, i think because it was missing the second overlay. And then after early-july holiday season and rocq fixing haskell extraction, we got the autobumper unstuck again, i presume catching up to the second overlay without anyone noticing.

Tragicus pushed a commit to Tragicus/coq that referenced this pull request Sep 3, 2025
Until overlays for rocq-prover#17876
get properly merged
Tragicus pushed a commit to Tragicus/coq that referenced this pull request Sep 3, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
kind: enhancement Enhancement to an existing user-facing feature, tactic, etc. part: parser The parser (also called gramlib, forked from camlp5)
Projects
None yet
Development

Successfully merging this pull request may close these issues.

7 participants