more clearly mark the original post as historic
[web.git] / personal / _posts / 2019-04-30-stacked-borrows-2.md
index d9037c06db94bcd337920a5b0d35b1008a4efbb3..c57098c4aa7d977ac85fdc2b4be20d1542fce5b3 100644 (file)
@@ -10,9 +10,18 @@ I assume some familiarity with the prior version and will not explain everything
 
 <!-- MORE -->
 
 
 <!-- MORE -->
 
+## Stacked Borrows: Table of Contents
+
+Before we start, let me give a brief overview over the posts on Stacked Borrows that I have written so far.
+I didn't plan this out in advance, so things are a bit more messy than I would like.
+
+* [Stacked Borrows: An Aliasing Model For Rust]({% post_url 2018-08-07-stacked-borrows %}) is the first post of the series and describes my initial ideas of what Stacked Borrows would look like before I started implementing them. It might be interesting for some of the context it gives, but is largely superseded by the next post.
+* [Stacked Borrows Implemented]({% post_url 2018-11-16-stacked-borrows-implementation %}) describes Stacked Borrows 1 and my experience implementing it. It is self-contained; I was not happy with some of my explanations in the original post so I decided to give it another shot. This is the best post to start with, if you are catching up.
+* [Barriers and Two-phase Borrows in Stacked Borrows]({% post_url 2018-12-26-stacked-borrows-barriers %}) describes how I extended Stacked Borrows 1 with partial support for two-phase borrows and explains the idea of "barriers". You do not have to have read that post to understand Stacked Borrows 2, except for the parts that specifically refer to barriers and two-phase borrows.
+
 ## The problem
 
 ## The problem
 
-The problem I wanted to solve was that the first version of Stacked Borrows only performed very little tracking of shared references.
+The problem I wanted to solve with Stacked Borrows 2 was that the first version of Stacked Borrows only performed very little tracking of shared references.
 My thinking was, if the location is read-only anyway, then it does not harm to grant anyone read access.
 However, [as @arielby noted](https://github.com/rust-lang/unsafe-code-guidelines/issues/87), this leads to loss of optimization potential in cases where a function receives a mutable reference (which is supposed to have no aliases) and then creates a shared reference from it:
 {% highlight rust %}
 My thinking was, if the location is read-only anyway, then it does not harm to grant anyone read access.
 However, [as @arielby noted](https://github.com/rust-lang/unsafe-code-guidelines/issues/87), this leads to loss of optimization potential in cases where a function receives a mutable reference (which is supposed to have no aliases) and then creates a shared reference from it:
 {% highlight rust %}
@@ -88,6 +97,7 @@ For each affected location, we go through two steps: first we try to find the *g
 **Finding the granting item.**
 To find the granting item, we traverse the borrow stack top-to-bottom and search for an item that has the same tag.
 If this is a write access, we go on looking until we find an item with the right tag whose permission is `SharedReadWrite` or `Unique`---we do not consider items with `SharedReadOnly` permission to grant a write access.
 **Finding the granting item.**
 To find the granting item, we traverse the borrow stack top-to-bottom and search for an item that has the same tag.
 If this is a write access, we go on looking until we find an item with the right tag whose permission is `SharedReadWrite` or `Unique`---we do not consider items with `SharedReadOnly` permission to grant a write access.
+This is the item that grants pointers tagged `tag` the permission to perform the given access, hence the name (the same concept used to be called "matching item" in Stacked Borrows 1).
 Once we found the granting item, we remember its position in the stack; that will be important for the second step.
 If no granting item can be found, the access causes undefined behavior.
 
 Once we found the granting item, we remember its position in the stack; that will be important for the second step.
 If no granting item can be found, the access causes undefined behavior.
 
@@ -366,4 +376,4 @@ It puts us into a good position to do more precise tracking for raw pointers, si
 That will be needed for compatibility with LLVM.
 However, [there are still some known issues](https://github.com/rust-lang/unsafe-code-guidelines/issues?q=is%3Aissue+is%3Aopen+label%3Atopic-stacked-borrows), and also the fact that we do not actually use the "stack" as a stack indicates that maybe we should use a different structure there (potentially something more like a tree).
 This is definitely not the final word, but I think it is a step in the right direction, and I am curious to see how it works out.
 That will be needed for compatibility with LLVM.
 However, [there are still some known issues](https://github.com/rust-lang/unsafe-code-guidelines/issues?q=is%3Aissue+is%3Aopen+label%3Atopic-stacked-borrows), and also the fact that we do not actually use the "stack" as a stack indicates that maybe we should use a different structure there (potentially something more like a tree).
 This is definitely not the final word, but I think it is a step in the right direction, and I am curious to see how it works out.
-As usual, if you have any questions or comments, please join the discussion in the forums!
+As usual, if you have any questions or comments, please join the [discussion in the forums](https://internals.rust-lang.org/t/stacked-borrows-2/9951)!