Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Move from globally-unique ScopedId to function-local IDs #50

Open
SnirkImmington opened this issue Jun 2, 2018 · 1 comment
Open

Move from globally-unique ScopedId to function-local IDs #50

SnirkImmington opened this issue Jun 2, 2018 · 1 comment
Labels
area: AST Issues which affect AST code area: check Code validation area: identify The "identify pass" - the ScopedId De Brujin index, or "ensure name exists in scope" change: expansion A change which includes new features, improvements, or APIs priority: low Consider higher priority issues first

Comments

@SnirkImmington
Copy link
Collaborator

SnirkImmington commented Jun 2, 2018

Edit: See my comment below.

This is a tracking issue regarding the use of ScopedIds in the AST (currently in the typeck branch). These de Bruijn indices currently have some properties that I try to uphold but don't depend on; the structure of a ScopedId could be useful in the future (if the AST design is upheld.

When creating ScopedIds on variables:

  • The default() of [0] is never assigned (this is depended upon).
  • Top-level items in visit_unit are numbered [0, 0] .. [0, n].
  • If visit_unit is called k times then items in unit k are numbered [k, 0] .. [k, n].
  • The k parameters of function [0, n] are numbered [0, n, 0] .. [0, n, k].
  • The opening block of a function [0, n] is [0, n, 0, 0]
  • The kth top-level variable defined in a function [0, n] is [0, n, 0, k].

When creating ScopedIds on types:

  • (), bool, and float are [1], [2], and [3] respectively.
  • The types of functions are equivalent to the functions' ScopedIds, i.e. [0, n]

Additional things we could do:

  • [ ] Dump function parameters into the top level scope (see identify/names/item_identifier.rs

These changes are all in the typeck branch. I'll revisit this issue after that is merged in.

@SnirkImmington SnirkImmington added area: AST Issues which affect AST code area: identify The "identify pass" - the ScopedId De Brujin index, or "ensure name exists in scope" area: check Code validation priority: low Consider higher priority issues first change: expansion A change which includes new features, improvements, or APIs labels Jun 2, 2018
@SnirkImmington
Copy link
Collaborator Author

Revisiting:

We don't really need the ScopedIds to be globally unique. Instead, we should track function-local data separately from globally-reachable data.

In the pre-typeck branch, the ScopedId was used for small things like a warning reporting. We built up a big table of variable ScopedIds and mapped each to a state of whether it was declared mutable, whether it was used, and whether it was mutated. (Plus a copy of its Ident so we could report its position.) This depended on no two variables in an entire Unit having the same ScopedId, so the ScopedId consists of a Vec of numbers.

In the typeck branch, type checking is done globally, across the entire program. Because all the local variables are added to the type graph, they must all be unique - see #98. Sure, local variables in different functions shouldn't have depended on each other, but since there was one graph, they all had to be unique.

We should change the ScopedIds into standard De Brujin indices which are only unique at the function-local level. Items (i.e. functions) should have a separate global identifier that is kept unique with other things at the global level. We could even give this a separate Rust type to keep them from being confused. Finally, we should have a separate single-number, Unit-unique ID system for types.

@SnirkImmington SnirkImmington changed the title Leverage data provided by ScopedIds Move from globally-unique ScopedId to function-local IDs Jan 15, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area: AST Issues which affect AST code area: check Code validation area: identify The "identify pass" - the ScopedId De Brujin index, or "ensure name exists in scope" change: expansion A change which includes new features, improvements, or APIs priority: low Consider higher priority issues first
Projects
None yet
Development

No branches or pull requests

1 participant