Feature: check that `//@ extern` axioms are consistent (an unsatisfiable one makes every proof that reaches it vacuous)
I maintainer di solito rispondono entro 1 giorno
Nessuno ha ancora preso questa issue.
Valutazione
- Difficoltà
- 5/5
- Tempo stimato
- Più di una settimana
- Idoneità per principianti
- 48/100
- Tipo di issue
- Funzionalità
- Chiarezza
- Specificata chiaramente
- Stato di attività
- Attiva
- Stack tecnologico
- typescript
- Ambito
- backend-api-design, testing-qa
Direzione di ricerca
Start by reading how lsc check emits and verifies Dafny code for //@ extern contracts, then inspect the existing handling of string semantics and the linked issue #301 for context. The report describes a symbolic probe and edge-value probes, with Dafny's --filter-symbol to check only those probes; reproduce the surrogate example first. Done means contradictory extern axioms are reported while failed or timed-out probes remain inconclusive, with the unicode-scalar surrogate case covered.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
Version: lsc 0.6.10 (npm), Dafny 4.11.
An //@ extern function's //@ ensures is trusted. It is emitted as an {:axiom} function. If the ensures can't hold in the model, any proof that reaches the extern is vacuous, and lsc says nothing.
One easy way to get there: under the default "string-semantics": "unicode-scalar" (--unicode-char:true), a Dafny char can't be a surrogate. An extern that describes JavaScript's UTF-16 behaviour, e.g. a lone surrogate, is then false:
//@ backend dafny
/** A lone high surrogate, as JavaScript can hold it. */
export function loneSurrogate(): string {
//@ extern
//@ ensures \result.length === 1 && \result.charCodeAt(0) === 0xD800
return String.fromCharCode(0xD800)
}
export function width(s: string): number {
//@ verify
//@ ensures \result === 42
return loneSurrogate().length + s.length
}
function {:axiom} loneSurrogate(): string
ensures ((|loneSurrogate()| == 1) && ((loneSurrogate()[0] as int) == 55296))
function width(s: string): int
{
(|loneSurrogate()| + |s|)
}
lemma width_ensures(s: string)
ensures (width(s) == 42)
{
}
Dafny program verifier finished with 2 verified, 0 errors
In JavaScript, width("abc") is 4. With //@ option string-semantics javascript-utf16 (and //@ option dafny-library local), the same file correctly fails on width(s) == 42. The extern is fine as JavaScript, but it contradicts the unicode-scalar model.
Surrogates are only one case. Any hand-written extern axiom can be contradictory, e.g. a typo, or two ensures that can't hold together. The effect is the same: the file reports green and proves nothing.
Suggested feature:
-
For each extern, have
lsc checkemit a sanity lemma that tries to provefalsefrom its axioms. If it verifies, fail or warn: "externloneSurrogate: its ensures are unsatisfiable under the current model". For an extern with parameters, the lemma would take arbitrary arguments satisfying therequires:lemma loneSurrogate_consistent() ensures false { var _ := loneSurrogate(); }I checked this by hand with
dafny verify --unicode-char:true. With55296, the lemma verifies, which flags the axiom. With65, it fails as it should. A failure or timeout is inconclusive, so it should stay silent. Only a proof offalseis reported.
A symbolic probe catches only an axiom that is false for EVERY argument. The case we actually hit was partial:codePointText(n)(wrappingString.fromCodePoint) promised two UTF-16 units forn > 0xFFFF, so it was contradictory only for astraln, andlemma P(n: int) requires 0 <= n <= 0x10FFFF ensures false { var _ := codePointText(n); }does not verify. What found it was instantiating the axiom on fixed edge values:var _ := codePointText(65536);provesfalse. We now run, per axiom, the symbolic probe plus one probe per edge value forint/nat/bool/stringparameters (0, ±1, 0xD800, 0xDFFF, 0x10000, 0x10FFFF and one past it;"", letters, path characters), withdafny verify --filter-symbol <probe prefix>so only the probes are checked (1-2 s a file). Dafny's own--warn-contradictory-assumptionsdid not help: it does not report function postconditions proved from a contradiction, and it was silent on this file. -
More narrowly: under
unicode-scalar, warn when an extern's contract mentions a code unit in0xD800..0xDFFF(charCodeAt(...) === 0xD8xx,\uD8xxin a literal), since nocharhas that value.
This complements #301, which is about proof files adding obligations. Here the obligation comes from the .ts itself.
Workaround: none in lsc. Review extern contracts by hand, and verify files whose externs talk about UTF-16 code units under "string-semantics": "javascript-utf16".
- Lingua principale
- TypeScript
- Stelle
- 113
- Fork
- 13
- Merge medio
- 16h 22m
- PR unite (30g)
- 40
Preparare l'ambiente
Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di midspiral/LemmaScript
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 82/100
midspiral/LemmaScript#308 ·
I maintainer di solito rispondono entro 1 giorno
-
Dafny: `toUpperCase`/`toLowerCase` are modeled as ASCII-only, so false contracts about non-ASCII text verifyForse già presa @quangng2000 l’ha presa 1 giorno fa. Aperta
midspiral/LemmaScript#312 · 1 commento · 1 assegnatario ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 4/5 1-2 giorni Idoneità per principianti 56/100
midspiral/LemmaScript#311 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 3/5 1-2 giorni Idoneità per principianti 67/100
midspiral/LemmaScript#309 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 4/5 3-5 giorni Idoneità per principianti 43/100
midspiral/LemmaScript#307 ·
I maintainer di solito rispondono entro 1 giorno
Tutte le issue di midspiral/LemmaScript
Issue simili
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 67/100
ilan-pinto/roaring-lions#1552 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 72/100
I maintainer di solito rispondono entro 1 giorno
-
bug: [React Native/Android] KeepAliveService never starts when CAMERA is not granted (Android 14+)Aperta
Difficoltà 2/5 1-3 ore Idoneità per principianti 78/100
cloudflare/realtimekit-ui#208 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 68/100
usebruno/bruno-vscode#235 ·
I maintainer di solito rispondono entro 3 giorni
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 78/100
I maintainer di solito rispondono entro 1 giorno