Feature: check that `//@ extern` axioms are consistent (an unsatisfiable one makes every proof that reaches it vacuous)

Aperta
#310 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

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

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:

  1. For each extern, have lsc check emit a sanity lemma that tries to prove false from its axioms. If it verifies, fail or warn: "extern loneSurrogate: its ensures are unsatisfiable under the current model". For an extern with parameters, the lemma would take arbitrary arguments satisfying the requires:

    lemma loneSurrogate_consistent() ensures false { var _ := loneSurrogate(); }
    

    I checked this by hand with dafny verify --unicode-char:true. With 55296, the lemma verifies, which flags the axiom. With 65, it fails as it should. A failure or timeout is inconclusive, so it should stay silent. Only a proof of false is reported.
    A symbolic probe catches only an axiom that is false for EVERY argument. The case we actually hit was partial: codePointText(n) (wrapping String.fromCodePoint) promised two UTF-16 units for n > 0xFFFF, so it was contradictory only for astral n, and lemma 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); proves false. We now run, per axiom, the symbolic probe plus one probe per edge value for int/nat/bool/string parameters (0, ±1, 0xD800, 0xDFFF, 0x10000, 0x10FFFF and one past it; "", letters, path characters), with dafny verify --filter-symbol <probe prefix> so only the probes are checked (1-2 s a file). Dafny's own --warn-contradictory-assumptions did not help: it does not report function postconditions proved from a contradiction, and it was silent on this file.

  2. More narrowly: under unicode-scalar, warn when an extern's contract mentions a code unit in 0xD800..0xDFFF (charCodeAt(...) === 0xD8xx, \uD8xx in a literal), since no char has 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

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di midspiral/LemmaScript

Tutte le issue di midspiral/LemmaScript

Issue simili

Altre issue su TypeScript

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.