Skip to content

Inserting a top-level statement renames every later statement, defeating the per-statement caches #1303

Closed

Description

@jsiek

Inserting or deleting a top-level statement renames the bound variables of every statement after it, so none of them can reuse the per-statement caches.

uniquify_deduce gives each top-level statement its own suffix space, s<N>_, where N is the statement's index in the file (abstract_syntax/ops.py, ctx.scope = outer_scope + 's' + str(i) + '_'). That keeps an edit inside statement N from renaming statement N+1, which is what docs/lsp-plan.md Step 14 needed. But adding a new lemma above statement N changes N, so every later statement's structural hash (_hash_ast) changes, and the check_proofs cache, and the type-check cache from #1301, miss on all of them.

Refs #1213 (iPad app), where adding a lemma is a common edit.

Repro

import sys
sys.path.insert(0, '.')
sys.argv = ['./deduce.py']
import proof_checker
from lsp.query import check

T = ''.join(f'theorem t{i}: all P:bool. if P then P\nproof\n  arbitrary P:bool\n  assume p: P\n  p\nend\n\n'
            for i in range(3))
check('test.pf', T)
for label, content in [('unchanged', T),
                       ('blank line at top', '\n' + T),
                       ('new theorem at top', 'theorem t_new: true\nproof\n  .\nend\n\n' + T)]:
    proof_checker._cache_stats['hits'].clear()
    proof_checker._cache_stats['misses'].clear()
    check('test.pf', content)
    print(f'{label:20} {proof_checker.get_cache_stats()}')

Observed

unchanged            {'hits': {'check_proofs': 3}, 'misses': {}}
blank line at top    {'hits': {'check_proofs': 3}, 'misses': {}}
new theorem at top   {'hits': {}, 'misses': {'check_proofs': 4}}

Expected

The new theorem misses, and t0, t1, t2, which did not change, hit:

new theorem at top   {'hits': {'check_proofs': 3}, 'misses': {'check_proofs': 1}}

Possible fix

Derive the scope segment from something that doesn't depend on the statement's position, such as the statement's own name, with a fallback (and a disambiguating counter) for unnamed statements like assert and for overloaded names. Check that bound names stay unique across statements wherever that matters, e.g. substitution in proofs.

Where found

While implementing the type-check cache for #1301 (test/lsp/test_type_check_cache.py keeps its edits to the same number of statements because of this).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions