[cfe-dev] [libc++] debug mode

[M.E. O'Neill]

Steven Watanabe wrote:
> In any event, the messy case is invalidating some iterators.  This is still the same under your scheme.  The only difference is that you've made it lazy, so we sometimes avoid the extra work.  The worst case is still the same.

Actually, I'm not nearly so sure.  Let's do a worked example.

WLoG, let's imagine simple linear tags, in an array with 20 elements. 

- iter1 refers to tag v1 (actually element 3)
- iter2 refers to tag v1 (actually element 11)
	- v1 is partially invalid, elements 0..15 remain valid
	- v1's successor is v2
	- v1's refcount is 2

- iter3 refers to tag v2 (actually element 16)
- iter4 refers to tag v2 (actually element 9)
- iter5 refers to tag v2 (actually element 12)
	- v2 is partially invalid, elements 0..9 remain valid
	- v2's successor is v3
	- v2's predecessor is v1
	- v2's refcount is 3

- iter6 refers to tag v3 (actually element 14)
	- v3 is partially invalid, elements 0..17 remain valid
	- v3's successor is v4
	- v3's predecessor is v2
	- v3's refcount is 1

- iter7 refers to tag v4 (actually element 5)
	- v4 is valid
	- v4's predecessor is v3
	- v4's refcount is 2 (one iterator, plus the container)

Notice that although there is a "long" history (v1..v4), its length is <= the number of active iterators.

Now, suppose iter6 goes away.  At this point, v3's refcount drops to zero, so no one needs it except earlier things in the history.  BUT, you can fold the info from v3 down into v2.  In this case, since v2 already has a smaller range, there's no change to v2's valid range.  Here's the new history with v3 removed.

- iter1 refers to tag v1 (actually element 3)
- iter2 refers to tag v1 (actually element 11)
	- v1 is partially invalid, elements 0..15 remain valid
	- v1's successor is v2
	- v1's refcount is 2

- iter3 refers to tag v2 (actually element 16)
- iter4 refers to tag v2 (actually element 9)
- iter5 refers to tag v2 (actually element 12)
	- v2 is partially invalid, elements 0..9 remain valid
	- v2's successor is v4
	- v2's predecessor is v1
	- v2's refcount is 3

- iter7 refers to tag v4 (actually element 5)
	- v4 is valid
	- v4's predecessor is v2
	- v4's refcount is 2 (one iterator, plus the container)

Now suppose that iter3, iter4 and iter5 are also destroyed.  v2's refcount drops to zero, so we remove the history node and merge.  v1's valid range drops from 0..15 to 0..9.

- iter1 refers to tag v1 (actually element 3)
- iter2 refers to tag v1 (actually element 11)
	- v1 is partially invalid, elements 0..9 remain valid
	- v1's successor is v4
	- v1's refcount is 2

- iter7 refers to tag v4 (actually element 5)
	- v4 is valid
	- v4's predecessor is v1
	- v4's refcount is 2 (one iterator, plus the container)

Now, if iter1 is used, everything is good -- we follow the chain and find everything is valid.  After the access, we've updated iter1's tag, so the world looks like this:

- iter2 refers to tag v1 (actually element 11)
	- v1 is partially invalid, elements 0..9 remain valid
	- v1's successor is v4
	- v1's refcount is 1

- iter1 refers to tag v4 (actually element 3)
- iter7 refers to tag v4 (actually element 5)
	- v4 is valid
	- v4's predecessor is v1
	- v4's refcount is 3 (two iterators, plus the container)

But, if we attempt to use iter2, we'll find it to be invalid.

As far as I can tell (and I'll admit, I may not be giving this as much attention as I should), no "unreasonably long" history chains in this case, but perhaps I'm missing some nuance somewhere...?

    M.E.O.