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

Abierto
#286 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
4/5
Tiempo estimado
3-5 días
Aptitud para principiantes
49/100
Tipo de issue
Nueva funcionalidad
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
typescript

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.
Lenguaje dominante
TypeScript
Estrellas
113
Forks
13
Merge medio
16 h 22 min
PR fusionados (30 d)
40

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de midspiral/LemmaScript

Todos los issues de midspiral/LemmaScript

Issues similares

Más issues de TypeScript

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.