Generic interfaces and object type aliases lose their type parameters in Dafny

オープン
#286 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
49/100
issue の種類
機能追加
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
typescript

調査の方向性

Start with tools/src/extract.ts at extractRecord, then compare its type parameter handling with parseDeclareType; inspect the signature scan around line 2821 and the lemma call generation in tools/src/transform.ts around line 2528. Add fixtures for the Stack/Popped example, generic empty, and the type table in SPEC.md. Done when the interface and alias examples and empty<T>() verify, and generic records are documented as retaining unbounded type parameters.

索引モデルが issue の本文から書いたものです。

説明

This was generated by AI during triage.

Context

DESIGN_LS_IN_LS.md §5.1 and §9 step 3 deferred generic datatype work on 2026-07-21. The note says erasure is uneven ("record decls erase, Dafny union decls stay parametric"), to be picked up "if a case study ever hits it", and that today "no case study hits the broken path".

I hit it in my production code. An undo/redo history module is generic over the snapshot it stores (HistoryState<TSnapshot>, HistoryEntry<TSnapshot>). Its eight helper functions have no extends bound on TSnapshot, so SPEC.md's type table applies its <T> / <T extends U> row: "T kept as type param (bound dropped)". The functions do keep it. The record declarations do not, so the model does not resolve.

Problem

export interface Entry<T> {
  value: T;
  label: string;
}

export interface Stack<T> {
  items: readonly Entry<T>[];
}

export interface Popped<T> {
  stack: Stack<T>;
  top: Entry<T>;
}

export function push<T>(s: Stack<T>, e: Entry<T>): Stack<T> {
  //@ verify
  //@ ensures \result.items.length === s.items.length + 1
  return { items: [...s.items, e] };
}

export function pop<T>(s: Stack<T>): Popped<T> | null {
  //@ verify
  //@ ensures (\result === null) === (s.items.length === 0)
  if (s.items.length === 0) return null;
  return {
    stack: { items: s.items.slice(0, s.items.length - 1) },
    top: s.items[s.items.length - 1],
  };
}

lsc gen --backend=dafny emits:

type Popped(==)

datatype Stack = Stack(items: seq<Entry<T>>)

datatype Entry = Entry(value: T, label_: string)

function push<T>(s: Stack<T>, e: Entry<T>): Stack<T>
{
  Stack((s.items + [e]))
}

function pop<T>(s: Stack<T>): Option<Popped<T>>
{
  if (|s.items| == 0) then
    None
  else
    Some((Stack(s.items[0..(|s.items| - 1)]), s.items[(|s.items| - 1)]))
}

Dafny reports 11 resolution errors: Wrong number of type arguments (1 instead of 0) for each use of Stack, Entry and Popped, and Type or type parameter is not declared in this scope: T inside the two datatypes.

There are three separate problems here:

  1. The record declarations drop <T>. extractRecord in tools/src/extract.ts (around line 1168) returns { name, kind: "record", fields } without type parameters, while the field types still say Entry<T>. The same source written as type Stack<T> = { … } aliases fails the same way (14 errors).
  2. A generic type used only in a return type becomes opaque. Popped<T> appears only in Popped<T> | null, and it is emitted as type Popped(==), with the result built as a tuple. The signature scan around line 2821 marks a type as needed only when its base name matches ^[A-Za-z_]\w*(?:\.\w+)*$, which Popped<T> does not. A zero-argument function makes this worse: function empty<T>(): Stack<T> { return { items: [] }; } emits type Stack(==) and the body ([]).
  3. A zero-argument generic function cannot be called from its own lemma. Once the datatypes are generic, ensures (|empty().items| == 0) fails with type parameter 'T' (inferred to be '?') in the function call to 'empty' could not be determined. The lemma call built in tools/src/transform.ts (around line 2528) has no type arguments. Writing empty<T>() verifies.

For comparison, the same records written as //@ declare-type Entry<T> { value: T, label: string } and //@ declare-type Stack<T> { items: Entry<T>[] } emit datatype Entry<T> and datatype Stack<T>, and push verifies (1 verified, 0 errors). That form is our current workaround, but it needs the type written twice.

Checked on main at 6b18f23 (0.6.8) with Dafny 4.11.0. I did not check the Lean backend.

Proposal

Keep the deferred parametricity design out of scope. Make the record path match what declare-type and discriminated unions already do:

  1. extractRecord records the declaration's type parameters, as parseDeclareType does.
  2. The signature scan marks the base name of a generic reference such as Popped<T>, so the record is emitted.
  3. The lemma's call to a pure generic function passes the function's type parameters as explicit type arguments, for example empty<T>().

Non-generic records keep byte-identical output. Instantiated generics such as Stack<number> stay out of scope, as §5.1 describes.

We have run equivalent changes as a local patch against 0.6.6 in a downstream project, where the history module now verifies (24 Dafny tasks). I can port them to tools/src as a PR with fixtures.

Acceptance criteria

  • The Stack/Popped example above verifies, written with interface and with type aliases.
  • empty<T>() with ensures \result.items.length === 0 verifies.
  • SPEC.md's type table says that generic records keep unbounded type parameters.
主要言語
TypeScript
スター
113
フォーク
13
平均マージ
16時間 22分
マージ済み PR(30日)
40

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

midspiral/LemmaScript のほかの issue

midspiral/LemmaScript の issue をすべて見る

似ている issue

TypeScript の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。