summaryrefslogtreecommitdiff
path: root/TODO.md
blob: 62eb95d58fa95ee4f667c194ed230b869cc55292 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
# TODO

0. borrows which are never ended? Drop locals in *symbolic* modes upon return

0. improve variable names generation: "hash_map" -> "hm" (and not just "h")

0. replace all the `failwith` with `raise (Failure ...)`: in CPS, it messes
   up with provenance tracking

0. In SymbolicToPure we do a few simplifications on types and values (simplification
   of box type, removal of tuples which contain exactly one field - some fields
   may have been filtered for the backward functions...): there are already a
   few sanity checks, but we may to add more of them, which would type check
   entire expressions for instance.

0. merge the "read determinant" and the "switch" occurrences to "match"

0. reaggregate the ADTs

0. when going from symbolic to pure, remove the useless tuples (as some fields
   might be erased).

0. Update the high-level comments, in particular in Values.ml

0. Rename Pure -> PureAst

0. For variables pretty names: we could try to use the meta places used for the
   forward function input vars to compute pretty names for the backward functions
   output vars.

0. sanity checks in symbolic to pure!

0. update the end borrows internal to abstractions to not introduce a Bottom

0. remove AConcrete from avalue

0. remove ABottom from avalue

0. micro-passes for pure:
   - remove unused variables
   - remove useless function calls:
     - calls which don't introduce values *if* they are followed by associated
       backward calls (because they may panic!)
     - calls which don't take inputs (can happen with backward functions - for
       instance, if a rust function only returns shared borrows)
   - monadic lets to matches
   - no tuple deconstruction on returned monadic values (introduce intermediate
     variables to deconstruct in two times)
   - matching on values (ex.: `let Cons hd tl = ls in` ~~>
     `match ls with | Nil -> Panic | Cons hd tl -> ...`)

1. reorder the branches of matches

1. stateful maps/sets modules (hashtbl?)

1. Check the occurrence of visitors like visit_AEndedMutLoan: the parameters are
   sometimes inverted!

2. check types are not "infinite"

3. in MIR, erased regions are completely erased (no list of erased regions...):
  update functions like `ty_has_regions` (and rename to `ty_has_borrows`),
  `erase_regions`

4. check that no borrow_overwrites upon ending abstractions

5. add a check in function inputs: ok to take as parameters symbolic values with
  borrow parameters *if* they come from the "input abstractions".
  In order to do this, add a symbolic value kind (would make things easier than
  adding ad-hoc lookups...): `FunRet`, `FunGivenBack`, `SynthInput`, `SynthGivenBack`
  Rk.: pay attention: we can't give borrows of borrows to functions, but borrows
  are ok.

6. add `mvalue` (meta values) stored in abstractions when ending loans

8. The following doesn't work:
  ```
  fn f1<'c, T>(p : (&'c mut T, &'c mut T)) -> (&'c mut T, &'c mut T)

  fn f2<'a, 'b, T>(p: (&'a mut T, &'b mut T)) -> (&'a mut T, &'b mut T)

  let p1 = f1<'c>(p0);
  let p2 = f2<'a, 'b>(p1);
  ```
  (end borrows)
  I think we should change the proj_loans to:
  `AProjLoans of symbolic_value * (mvalue * aproj) list`
  (to accumulate the given back values)
  Then, once we collected all the borrows, we would convert it to:
  `AEndedProjLoans of (mvalue * aproj) list`
  If the list is empty, it means the value was not modified.

9. The way we currently give back symbolic values to symbolic values (inside
   abstractions) is wrong.
   We get things like :
   `AProjLoans (s0 <: &'a mut T) [AProjBorrows (s1 <: &'a mut T)]`
   while in the case of `s1` we should ignore the outer borrow (what we give
   back actually has type `T`...)
  
10. Write "bodies" for the assumed functions.

* write a function to check that the code we are about to synthesize is in the proper
  subset. In particular:
  * borrow overwrites
  * type parameters instantiation
  * uniform polymorphism
  Also, write nice debug messages which refer to the original code in case
  something fails.
* write an interesting example to study with Jonathan

* add option for: `allow_borrow_overwrites_on_input_values`
  (rather: `will_overwrite_input_borrows`)
  (but always disallow borrow overwrites on returned values)
  at the level of abstractions (not at the level of loans!)

* invariant: if there is a `proj_loans rset1 (s:rty)` where `s` contains mutable
  borrows, then:
  * either there is exactly one `s` in the current context
  * or there is exactly one `proj_borrows rset2 (s:rty<:rty')` which intersects
    the `proj_loans ...`
  However, one `proj_borrows s` may intersect several `proj_loans` (in which
  case we will need to split the value given back - for now: disallow this
  behaviour?).

* remove the rule which says that we can end a borrow under an abstraction if
  the corresponding loan is in the same abstraction.
  Actually: update the rule, rather.

* update end_borrow_get_borrow to keep track of the ignored borrows/loans as
  outer borrows, and track the ids of the ignored shared loans?
  or: make sure there are no parent abstractions when ending inner loans in
  abstractions.

* `ended_proj_loans` (with ghost value)

* make the projected shared borrows more structured? I don't think that's necessary

* add a `allow_borrow_overwrites` in the loan projectors.

* During printing, contexts are often big, with many variables containing "bottom".
  Some variables also actually never get assigned, especially when they are used
  for auxiliary assignments which don't exist anymore (because they were merged
  with other operations - for arithmetic operations, for instance).
  Maybe we should register which variable has been assigned at least once, and
  print only those (thus skipping a big part of the environment for some time).

* Some variables have the same name. It might be good to also print their id
  to disambiguate?

* it would be good to find a "core", which implements the rules (like
  "end_borrow") and on top of which we build more complex functions which
  chose in which order to apply the rules, etc. This way we would make very
  explicit where we need to insert sanity checks, what the preconditions are,
  where invariants might be broken, etc.

* intensively test with PLT-redex

* remove the config parameters when they are useless

# DONE

* update the assignment to move the destination value (which will be overriden)
  to a dummy variable, and end all the outer borrows.
  Also update pop_frame.

* Check what happens when symbolic borrows are not expanded (when looking for
  borrows/abstractions to end).

* Detect loops in end_borrow/end_abstraction

* recheck give_back_symbolic_value (use regions!)

* expand symbolic values which are primitively copyable upon using them as
  function arguments or putting them in the return value, in order to deduplicate
  those values.
  Completion: we expand those values only upon copying them (that's enough).

* invariant: if a symbolic value is present multiple times in the concrete environment,
  it means it is primitively copyable

* update the printing of mut_borrows and mut_loans ([s@0 <: ...]) and (s@0)

* add a switch to allow general symbolic values (containing references, etc.)
  or not.

* split `apply_proj_borrows` into two:
  * `apply_proj_borrows_on_input_values` : ... -> value -> rty -> avalue
  * `apply_proj_borrows_on_given_back_values` : ... -> value -> avalue -> avalue
  Actually: didn't do it: bad idea.

* Reduce projectors to `_` (ignored) when there are no region intersections

* Add a `Collections.ml` file, with `Map` and `Set`

* improve the use of [comp] for composition of functions with continuations

* derive [ord] for types

* compute the region constraints for the type definitions

* set of types with mutable borrows (what to do when type variables appear under
  shared borrows?), nested borrows...
  necessary to know what to return.

* fix the static regions (with projectors)
  Before that, introduce a sanity check to make sure we don't use static regions.

* add a meta-value in shared borrows to carry the shared value